Implement Transforms/InstCombine/cast-load-gep.ll, which allows us to devirtualize

[oota-llvm.git] / lib / Transforms / Scalar / SCCP.cpp

diff --git a/lib/Transforms/Scalar/SCCP.cpp b/lib/Transforms/Scalar/SCCP.cpp
index 9a8d26bb7b8c2b50795121dcdea41008b2dce1c2..c769b549916162707e7f0bb86768f89cbc36e793 100644 (file)
--- a/lib/Transforms/Scalar/SCCP.cpp
+++ b/lib/Transforms/Scalar/SCCP.cpp
@@ -217,7 +217,11 @@ private:
   
   inline void markOverdefined(LatticeVal &IV, Value *V) {
     if (IV.markOverdefined()) {
-      DEBUG(std::cerr << "markOverdefined: " << *V);
+      DEBUG(std::cerr << "markOverdefined: ";
+            if (Function *F = dyn_cast<Function>(V))
+              std::cerr << "Function '" << F->getName() << "'\n";
+            else
+              std::cerr << *V);
       // Only instructions go on the work list
       OverdefinedInstWorkList.push_back(V);
     }
@@ -611,6 +615,43 @@ void SCCPSolver::visitBinaryOperator(Instruction &I) {
   LatticeVal &V2State = getValueState(I.getOperand(1));
 
   if (V1State.isOverdefined() || V2State.isOverdefined()) {
+    // If this is an AND or OR with 0 or -1, it doesn't matter that the other
+    // operand is overdefined.
+    if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Or) {
+      LatticeVal *NonOverdefVal = 0;
+      if (!V1State.isOverdefined()) {
+        NonOverdefVal = &V1State;
+      } else if (!V2State.isOverdefined()) {
+        NonOverdefVal = &V2State;
+      }
+
+      if (NonOverdefVal) {
+        if (NonOverdefVal->isUndefined()) {
+          // Could annihilate value.
+          if (I.getOpcode() == Instruction::And)
+            markConstant(IV, &I, Constant::getNullValue(I.getType()));
+          else
+            markConstant(IV, &I, ConstantInt::getAllOnesValue(I.getType()));
+          return;
+        } else {
+          if (I.getOpcode() == Instruction::And) {
+            if (NonOverdefVal->getConstant()->isNullValue()) {
+              markConstant(IV, &I, NonOverdefVal->getConstant());
+              return;      // X or 0 = -1
+            }
+          } else {
+            if (ConstantIntegral *CI =
+                     dyn_cast<ConstantIntegral>(NonOverdefVal->getConstant()))
+              if (CI->isAllOnesValue()) {
+                markConstant(IV, &I, NonOverdefVal->getConstant());
+                return;    // X or -1 = -1
+              }
+          }
+        }
+      }
+    }
+
+
     // If both operands are PHI nodes, it is possible that this instruction has
     // a constant value, despite the fact that the PHI node doesn't.  Check for
     // this condition now.
@@ -730,12 +771,12 @@ static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
       ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
       if (CS == 0) return 0;
       if (CU->getValue() >= CS->getNumOperands()) return 0;
-      C = CS->getOperand(CU->getValue());
+      C = CS->getOperand((unsigned)CU->getValue());
     } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
       ConstantArray *CA = dyn_cast<ConstantArray>(C);
       if (CA == 0) return 0;
       if ((uint64_t)CS->getValue() >= CA->getNumOperands()) return 0;
-      C = CA->getOperand(CS->getValue());
+      C = CA->getOperand((unsigned)CS->getValue());
     } else
       return 0;
   return C;
@@ -934,26 +975,29 @@ void SCCPSolver::Solve() {
 /// should be rerun.
 bool SCCPSolver::ResolveBranchesIn(Function &F) {
   bool BranchesResolved = false;
-  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
-    TerminatorInst *TI = BB->getTerminator();
-    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
-      if (BI->isConditional()) {
-        LatticeVal &BCValue = getValueState(BI->getCondition());
-        if (BCValue.isUndefined()) {
-          BI->setCondition(ConstantBool::True);
+  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
+    if (BBExecutable.count(BB)) {
+      TerminatorInst *TI = BB->getTerminator();
+      if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+        if (BI->isConditional()) {
+          LatticeVal &BCValue = getValueState(BI->getCondition());
+          if (BCValue.isUndefined()) {
+            BI->setCondition(ConstantBool::True);
+            BranchesResolved = true;
+            visit(BI);
+          }
+        }
+      } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+        LatticeVal &SCValue = getValueState(SI->getCondition());
+        if (SCValue.isUndefined()) {
+          const Type *CondTy = SI->getCondition()->getType();
+          SI->setCondition(Constant::getNullValue(CondTy));
           BranchesResolved = true;
-          visit(BI);
+          visit(SI);
         }
       }
-    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
-      LatticeVal &SCValue = getValueState(SI->getCondition());
-      if (SCValue.isUndefined()) {
-        SI->setCondition(Constant::getNullValue(SI->getCondition()->getType()));
-        BranchesResolved = true;
-        visit(SI);
-      }
     }
-  }
+
   return BranchesResolved;
 }
 
@@ -1007,6 +1051,7 @@ bool SCCP::runOnFunction(Function &F) {
   bool ResolvedBranches = true;
   while (ResolvedBranches) {
     Solver.Solve();
+    DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n");
     ResolvedBranches = Solver.ResolveBranchesIn(F);
   }
 
@@ -1146,6 +1191,7 @@ bool IPSCCP::runOnModule(Module &M) {
   while (ResolvedBranches) {
     Solver.Solve();
 
+    DEBUG(std::cerr << "RESOLVING UNDEF BRANCHES\n");
     ResolvedBranches = false;
     for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
       ResolvedBranches |= Solver.ResolveBranchesIn(*F);
@@ -1178,7 +1224,6 @@ bool IPSCCP::runOnModule(Module &M) {
       if (!ExecutableBBs.count(BB)) {
         DEBUG(std::cerr << "  BasicBlock Dead:" << *BB);
         ++IPNumDeadBlocks;
-        BlocksToErase.push_back(BB);
 
         // Delete the instructions backwards, as it has a reduced likelihood of
         // having to update as many def-use and use-def chains.
@@ -1206,6 +1251,11 @@ bool IPSCCP::runOnModule(Module &M) {
           TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
         BB->getInstList().erase(TI);
 
+        if (&*BB != &F->front())
+          BlocksToErase.push_back(BB);
+        else
+          new UnreachableInst(BB);
+
       } else {
         for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
           Instruction *Inst = BI++;
@@ -1280,6 +1330,7 @@ bool IPSCCP::runOnModule(Module &M) {
       SI->eraseFromParent();
     }
     M.getGlobalList().erase(GV);
+    ++IPNumGlobalConst;
   }
   
   return MadeChanges;