add support for phi translation and incorpation of new expression.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@90782 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 144 insertions, 121 deletions

diff --git a/lib/Analysis/PHITransAddr.cpp b/lib/Analysis/PHITransAddr.cpp
index bdaaac1eaa..40800b4e58 100644
--- a/lib/Analysis/PHITransAddr.cpp
+++ b/lib/Analysis/PHITransAddr.cpp
@@ -16,27 +16,32 @@
 #include "llvm/Analysis/InstructionSimplify.h"
 using namespace llvm;
 
-/// IsPotentiallyPHITranslatable - If this needs PHI translation, return true
-/// if we have some hope of doing it.  This should be used as a filter to
-/// avoid calling PHITranslateValue in hopeless situations.
-bool PHITransAddr::IsPotentiallyPHITranslatable() const {
-  // If the input value is not an instruction, or if it is not defined in CurBB,
-  // then we don't need to phi translate it.
-  Instruction *Inst = dyn_cast<Instruction>(Addr);
+static bool CanPHITrans(Instruction *Inst) {
   if (isa<PHINode>(Inst) ||
       isa<BitCastInst>(Inst) ||
-      isa<GetElementPtrInst>(Inst) ||
-      (Inst->getOpcode() == Instruction::And &&
-       isa<ConstantInt>(Inst->getOperand(1))))
+      isa<GetElementPtrInst>(Inst))
     return true;
-
+  
+  if (Inst->getOpcode() == Instruction::And &&
+      isa<ConstantInt>(Inst->getOperand(1)))
+    return true;
+  
   //   cerr << "MEMDEP: Could not PHI translate: " << *Pointer;
   //   if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst))
   //     cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0);
-
   return false;
 }
 
+/// IsPotentiallyPHITranslatable - If this needs PHI translation, return true
+/// if we have some hope of doing it.  This should be used as a filter to
+/// avoid calling PHITranslateValue in hopeless situations.
+bool PHITransAddr::IsPotentiallyPHITranslatable() const {
+  // If the input value is not an instruction, or if it is not defined in CurBB,
+  // then we don't need to phi translate it.
+  Instruction *Inst = dyn_cast<Instruction>(Addr);
+  return Inst == 0 || CanPHITrans(Inst);
+}
+
 
 Value *PHITransAddr::PHITranslateSubExpr(Value *V, BasicBlock *CurBB,
                                          BasicBlock *PredBB) {
@@ -44,129 +49,147 @@ Value *PHITransAddr::PHITranslateSubExpr(Value *V, BasicBlock *CurBB,
   Instruction *Inst = dyn_cast<Instruction>(V);
   if (Inst == 0) return V;
   
-  // Determine whether 'Inst' is an input to our PHI translatable expression.
-  bool isInput = std::count(InstInputs.begin(), InstInputs.end(), Inst);
-  
-  // If 'Inst' is not defined in this block, it is either an input, or an
-  // intermediate result.
-  if (Inst->getParent() != CurBB) {
-    // If it is an input, then it remains an input.
+  // If 'Inst' is defined in this block, it must be an input that needs to be
+  // phi translated or an intermediate expression that needs to be incorporated
+  // into the expression.
+  if (Inst->getParent() == CurBB) {
+    assert(std::count(InstInputs.begin(), InstInputs.end(), Inst) &&
+           "Not an input?");
+    
+    // If this is a PHI, go ahead and translate it.
+    if (PHINode *PN = dyn_cast<PHINode>(Inst))
+      return PN->getIncomingValueForBlock(PredBB);
+
+    
+    // If this is a non-phi value, and it is analyzable, we can incorporate it
+    // into the expression by making all instruction operands be inputs.
+    if (!CanPHITrans(Inst))
+      return 0;
+    
+    // Okay, we can incorporate it, this instruction is no longer an input.
+    InstInputs.erase(std::find(InstInputs.begin(), InstInputs.end(), Inst));
+    
+    // All instruction operands are now inputs (and of course, they may also be
+    // defined in this block, so they may need to be phi translated themselves.
+    for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
+      if (Instruction *Op = dyn_cast<Instruction>(Inst->getOperand(i)))
+        InstInputs.push_back(Op);
+    
+  } else {
+    // Determine whether 'Inst' is an input to our PHI translatable expression.
+    bool isInput = std::count(InstInputs.begin(), InstInputs.end(), Inst);
+    
+    // If it is an input defined in a different block, then it remains an input.
     if (isInput)
       return Inst;
+  }
+
+  // Ok, it must be an intermediate result (either because it started that way
+  // or because we just incorporated it into the expression).  See if its
+  // operands need to be phi translated, and if so, reconstruct it.
   
-    // Otherwise, it must be an intermediate result.  See if its operands need
-    // to be phi translated, and if so, reconstruct it.
+  if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
+    Value *PHIIn = PHITranslateSubExpr(BC->getOperand(0), CurBB, PredBB);
+    if (PHIIn == 0) return 0;
+    if (PHIIn == BC->getOperand(0))
+      return BC;
     
-    if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
-      Value *PHIIn = PHITranslateSubExpr(BC->getOperand(0), CurBB, PredBB);
-      if (PHIIn == 0) return 0;
-      if (PHIIn == BC->getOperand(0))
-        return BC;
-      
-      // Find an available version of this cast.
-      
-      // Constants are trivial to find.
-      if (Constant *C = dyn_cast<Constant>(PHIIn))
-        return ConstantExpr::getBitCast(C, BC->getType());
+    // Find an available version of this cast.
+    
+    // Constants are trivial to find.
+    if (Constant *C = dyn_cast<Constant>(PHIIn))
+      return ConstantExpr::getBitCast(C, BC->getType());
+    
+    // Otherwise we have to see if a bitcasted version of the incoming pointer
+    // is available.  If so, we can use it, otherwise we have to fail.
+    for (Value::use_iterator UI = PHIIn->use_begin(), E = PHIIn->use_end();
+         UI != E; ++UI) {
+      if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI))
+        if (BCI->getType() == BC->getType())
+          return BCI;
+    }
+    return 0;
+  }
+  
+  // Handle getelementptr with at least one PHI translatable operand.
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
+    SmallVector<Value*, 8> GEPOps;
+    BasicBlock *CurBB = GEP->getParent();
+    bool AnyChanged = false;
+    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
+      Value *GEPOp = PHITranslateSubExpr(GEP->getOperand(i), CurBB, PredBB);
+      if (GEPOp == 0) return 0;
       
-      // Otherwise we have to see if a bitcasted version of the incoming pointer
-      // is available.  If so, we can use it, otherwise we have to fail.
-      for (Value::use_iterator UI = PHIIn->use_begin(), E = PHIIn->use_end();
-           UI != E; ++UI) {
-        if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI))
-          if (BCI->getType() == BC->getType())
-            return BCI;
-      }
-      return 0;
+      AnyChanged = GEPOp != GEP->getOperand(i);
+      GEPOps.push_back(GEPOp);
     }
     
-    // Handle getelementptr with at least one PHI translatable operand.
-    if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
-      SmallVector<Value*, 8> GEPOps;
-      BasicBlock *CurBB = GEP->getParent();
-      bool AnyChanged = false;
-      for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
-        Value *GEPOp = PHITranslateSubExpr(GEP->getOperand(i), CurBB, PredBB);
-        if (GEPOp == 0) return 0;
-        
-        AnyChanged = GEPOp != GEP->getOperand(i);
-        GEPOps.push_back(GEPOp);
-      }
-      
-      if (!AnyChanged)
-        return GEP;
-      
-      // Simplify the GEP to handle 'gep x, 0' -> x etc.
-      if (Value *V = SimplifyGEPInst(&GEPOps[0], GEPOps.size(), TD))
-        return V;
-      
-      // Scan to see if we have this GEP available.
-      Value *APHIOp = GEPOps[0];
-      for (Value::use_iterator UI = APHIOp->use_begin(), E = APHIOp->use_end();
-           UI != E; ++UI) {
-        if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
-          if (GEPI->getType() == GEP->getType() &&
-              GEPI->getNumOperands() == GEPOps.size() &&
-              GEPI->getParent()->getParent() == CurBB->getParent()) {
-            bool Mismatch = false;
-            for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
-              if (GEPI->getOperand(i) != GEPOps[i]) {
-                Mismatch = true;
-                break;
-              }
-            if (!Mismatch)
-              return GEPI;
-          }
-      }
-      return 0;
+    if (!AnyChanged)
+      return GEP;
+    
+    // Simplify the GEP to handle 'gep x, 0' -> x etc.
+    if (Value *V = SimplifyGEPInst(&GEPOps[0], GEPOps.size(), TD))
+      return V;
+    
+    // Scan to see if we have this GEP available.
+    Value *APHIOp = GEPOps[0];
+    for (Value::use_iterator UI = APHIOp->use_begin(), E = APHIOp->use_end();
+         UI != E; ++UI) {
+      if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
+        if (GEPI->getType() == GEP->getType() &&
+            GEPI->getNumOperands() == GEPOps.size() &&
+            GEPI->getParent()->getParent() == CurBB->getParent()) {
+          bool Mismatch = false;
+          for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
+            if (GEPI->getOperand(i) != GEPOps[i]) {
+              Mismatch = true;
+              break;
+            }
+          if (!Mismatch)
+            return GEPI;
+        }
     }
+    return 0;
+  }
+  
+  // Handle add with a constant RHS.
+  if (Inst->getOpcode() == Instruction::Add &&
+      isa<ConstantInt>(Inst->getOperand(1))) {
+    // PHI translate the LHS.
+    Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
+    bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
+    bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
     
-    // Handle add with a constant RHS.
-    if (Inst->getOpcode() == Instruction::Add &&
-        isa<ConstantInt>(Inst->getOperand(1))) {
-      // PHI translate the LHS.
-      Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
-      bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
-      bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
-      
-      Value *LHS = PHITranslateSubExpr(Inst->getOperand(0), CurBB, PredBB);
-      if (LHS == 0) return 0;
-      
-      // If the PHI translated LHS is an add of a constant, fold the immediates.
-      if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
-        if (BOp->getOpcode() == Instruction::Add)
-          if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
-            LHS = BOp->getOperand(0);
-            RHS = ConstantExpr::getAdd(RHS, CI);
-            isNSW = isNUW = false;
-          }
-      
-      // See if the add simplifies away.
-      if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, TD))
-        return Res;
-      
-      // Otherwise, see if we have this add available somewhere.
-      for (Value::use_iterator UI = LHS->use_begin(), E = LHS->use_end();
-           UI != E; ++UI) {
-        if (BinaryOperator *BO = dyn_cast<BinaryOperator>(*UI))
-          if (BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
-              BO->getParent()->getParent() == CurBB->getParent())
-            return BO;
-      }
-      
-      return 0;
+    Value *LHS = PHITranslateSubExpr(Inst->getOperand(0), CurBB, PredBB);
+    if (LHS == 0) return 0;
+    
+    // If the PHI translated LHS is an add of a constant, fold the immediates.
+    if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
+      if (BOp->getOpcode() == Instruction::Add)
+        if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
+          LHS = BOp->getOperand(0);
+          RHS = ConstantExpr::getAdd(RHS, CI);
+          isNSW = isNUW = false;
+        }
+    
+    // See if the add simplifies away.
+    if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, TD))
+      return Res;
+    
+    // Otherwise, see if we have this add available somewhere.
+    for (Value::use_iterator UI = LHS->use_begin(), E = LHS->use_end();
+         UI != E; ++UI) {
+      if (BinaryOperator *BO = dyn_cast<BinaryOperator>(*UI))
+        if (BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
+            BO->getParent()->getParent() == CurBB->getParent())
+          return BO;
     }
     
-    // Otherwise, we failed.
     return 0;
   }
-
-  // Otherwise, it is defined in this block.  It must be an input and must be
-  // phi translated.
-  assert(isInput && "Instruction defined in block must be an input");
   
-  
-  abort(); // unimplemented so far.
+  // Otherwise, we failed.
+  return 0;
 }