Changeset 319 for clamav/trunk/libclamav/c++/llvm/lib/Transforms/Utils/SimplifyCFG.cpp

Timestamp:

Apr 19, 2011, 11:12:07 PM (14 years ago)

Author:

Yuri Dario

Message:

clamav: update trunk to 0.97.

Location:

clamav/trunk

Files:

• . (modified) (1 prop)
• libclamav/c++/llvm/lib/Transforms/Utils/SimplifyCFG.cpp (modified) (19 diffs)

clamav/trunk/libclamav/c++/llvm/lib/Transforms/Utils/SimplifyCFG.cpp ¶

@@ -225 +225 @@
       if (!AggressiveInsts) return false;
       // Okay, it looks like the instruction IS in the "condition".  Check to
-      // see if its a cheap instruction to unconditionally compute, and if it
+      // see if it's a cheap instruction to unconditionally compute, and if it
       // only uses stuff defined outside of the condition.  If so, hoist it out.
       if (!I->isSafeToSpeculativelyExecute())
@@ -950 +950 @@
     // Ignore any user that is not a PHI node in BB2.  These can only occur in
     // unreachable blocks, because they would not be dominated by the instr.
-    PHINode *PN = dyn_cast<PHINode>(UI);
+    PHINode *PN = dyn_cast<PHINode>(*UI);
     if (!PN || PN->getParent() != BB2)
       return false;
@@ -1378 +1378 @@
   BasicBlock *BB = BI->getParent();
   Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
-  if (Cond == 0) return false;
-
+  if (Cond == 0 || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
+    Cond->getParent() != BB || !Cond->hasOneUse())
+  return false;
   
   // Only allow this if the condition is a simple instruction that can be
@@ -1388 +1389 @@
   while(isa<DbgInfoIntrinsic>(FrontIt))
     ++FrontIt;
-  if ((!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
-      Cond->getParent() != BB || &*FrontIt != Cond || !Cond->hasOneUse()) {
+    
+  // Allow a single instruction to be hoisted in addition to the compare
+  // that feeds the branch.  We later ensure that any values that _it_ uses
+  // were also live in the predecessor, so that we don't unnecessarily create
+  // register pressure or inhibit out-of-order execution.
+  Instruction *BonusInst = 0;
+  if (&*FrontIt != Cond &&
+      FrontIt->hasOneUse() && *FrontIt->use_begin() == Cond &&
+      FrontIt->isSafeToSpeculativelyExecute()) {
+    BonusInst = &*FrontIt;
+    ++FrontIt;
+  }
+  
+  // Only a single bonus inst is allowed.
+  if (&*FrontIt != Cond)
     return false;
-  }
   
   // Make sure the instruction after the condition is the cond branch.
@@ -1429 +1442 @@
         !SafeToMergeTerminators(BI, PBI))
       continue;
+    
+    // Ensure that any values used in the bonus instruction are also used
+    // by the terminator of the predecessor.  This means that those values
+    // must already have been resolved, so we won't be inhibiting the 
+    // out-of-order core by speculating them earlier.
+    if (BonusInst) {
+      // Collect the values used by the bonus inst
+      SmallPtrSet<Value*, 4> UsedValues;
+      for (Instruction::op_iterator OI = BonusInst->op_begin(),
+           OE = BonusInst->op_end(); OI != OE; ++OI) {
+        Value* V = *OI;
+        if (!isa<Constant>(V))
+          UsedValues.insert(V);
+      }
+
+      SmallVector<std::pair<Value*, unsigned>, 4> Worklist;
+      Worklist.push_back(std::make_pair(PBI->getOperand(0), 0));
+      
+      // Walk up to four levels back up the use-def chain of the predecessor's
+      // terminator to see if all those values were used.  The choice of four
+      // levels is arbitrary, to provide a compile-time-cost bound.
+      while (!Worklist.empty()) {
+        std::pair<Value*, unsigned> Pair = Worklist.back();
+        Worklist.pop_back();
+        
+        if (Pair.second >= 4) continue;
+        UsedValues.erase(Pair.first);
+        if (UsedValues.empty()) break;
+        
+        if (Instruction* I = dyn_cast<Instruction>(Pair.first)) {
+          for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end();
+               OI != OE; ++OI)
+            Worklist.push_back(std::make_pair(OI->get(), Pair.second+1));
+        }       
+      }
+      
+      if (!UsedValues.empty()) return false;
+    }
     
     Instruction::BinaryOps Opc;
@@ -1458 +1509 @@
     }
     
+    // If we have a bonus inst, clone it into the predecessor block.
+    Instruction *NewBonus = 0;
+    if (BonusInst) {
+      NewBonus = BonusInst->clone();
+      PredBlock->getInstList().insert(PBI, NewBonus);
+      NewBonus->takeName(BonusInst);
+      BonusInst->setName(BonusInst->getName()+".old");
+    }
+    
     // Clone Cond into the predecessor basic block, and or/and the
     // two conditions together.
     Instruction *New = Cond->clone();
+    if (BonusInst) New->replaceUsesOfWith(BonusInst, NewBonus);
     PredBlock->getInstList().insert(PBI, New);
     New->takeName(Cond);
@@ -1514 +1575 @@
       // predecessor, compute the PHI'd conditional value for all of the preds.
       // Any predecessor where the condition is not computable we keep symbolic.
-      for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
-        if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) &&
+      for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+        BasicBlock *P = *PI;
+        if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) &&
             PBI != BI && PBI->isConditional() &&
             PBI->getCondition() == BI->getCondition() &&
@@ -1521 +1583 @@
           bool CondIsTrue = PBI->getSuccessor(0) == BB;
           NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 
-                                              CondIsTrue), *PI);
+                                              CondIsTrue), P);
         } else {
-          NewPN->addIncoming(BI->getCondition(), *PI);
+          NewPN->addIncoming(BI->getCondition(), P);
         }
+      }
       
       BI->setCondition(NewPN);
@@ -1662 +1725 @@
   assert(BB && BB->getParent() && "Block not embedded in function!");
   assert(BB->getTerminator() && "Degenerate basic block encountered!");
-  assert(&BB->getParent()->getEntryBlock() != BB &&
-         "Can't Simplify entry block!");
-
-  // Remove basic blocks that have no predecessors... or that just have themself
-  // as a predecessor.  These are unreachable.
-  if (pred_begin(BB) == pred_end(BB) || BB->getSinglePredecessor() == BB) {
+
+  // Remove basic blocks that have no predecessors (except the entry block)...
+  // or that just have themself as a predecessor.  These are unreachable.
+  if ((pred_begin(BB) == pred_end(BB) &&
+       &BB->getParent()->getEntryBlock() != BB) ||
+      BB->getSinglePredecessor() == BB) {
     DEBUG(dbgs() << "Removing BB: \n" << *BB);
     DeleteDeadBlock(BB);
@@ -1698 +1761 @@
       SmallVector<BranchInst*, 8> CondBranchPreds;
       for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
-        TerminatorInst *PTI = (*PI)->getTerminator();
+        BasicBlock *P = *PI;
+        TerminatorInst *PTI = P->getTerminator();
         if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) {
           if (BI->isUnconditional())
-            UncondBranchPreds.push_back(*PI);
+            UncondBranchPreds.push_back(P);
           else
             CondBranchPreds.push_back(BI);
@@ -1769 +1833 @@
 
           // Insert the call now.
-          SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end());
+          SmallVector<Value*,8> Args(II->op_begin(), II->op_end()-3);
           CallInst *CI = CallInst::Create(II->getCalledValue(),
                                           Args.begin(), Args.end(),
@@ -1817 +1881 @@
         ++BBI;
       if (BBI->isTerminator()) // Terminator is the only non-phi instruction!
-        if (TryToSimplifyUncondBranchFromEmptyBlock(BB))
-          return true;
+        if (BB != &BB->getParent()->getEntryBlock())
+          if (TryToSimplifyUncondBranchFromEmptyBlock(BB))
+            return true;
       
     } else {  // Conditional branch
@@ -1827 +1892 @@
         if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
           if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred))
-            return SimplifyCFG(BB) || 1;
+            return SimplifyCFG(BB) | true;
 
         // This block must be empty, except for the setcond inst, if it exists.
@@ -1861 +1926 @@
       // predecessor and use logical operations to pick the right destination.
       if (FoldBranchToCommonDest(BI))
-        return SimplifyCFG(BB) | 1;
+        return SimplifyCFG(BB) | true;
 
 
@@ -1971 +2036 @@
 
             // Insert the call now...
-            SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
+            SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3);
             CallInst *CI = CallInst::Create(II->getCalledValue(),
                                             Args.begin(), Args.end(),
@@ -1977 +2042 @@
             CI->setCallingConv(II->getCallingConv());
             CI->setAttributes(II->getAttributes());
-            // If the invoke produced a value, the Call does now instead.
+            // If the invoke produced a value, the call does now instead.
             II->replaceAllUsesWith(CI);
             delete II;
@@ -1986 +2051 @@
 
       // If this block is now dead, remove it.
-      if (pred_begin(BB) == pred_end(BB)) {
+      if (pred_begin(BB) == pred_end(BB) &&
+          BB != &BB->getParent()->getEntryBlock()) {
         // We know there are no successors, so just nuke the block.
         M->getBasicBlockList().erase(BB);
         return true;
       }
+    }
+  } else if (IndirectBrInst *IBI =
+               dyn_cast<IndirectBrInst>(BB->getTerminator())) {
+    // Eliminate redundant destinations.
+    SmallPtrSet<Value *, 8> Succs;
+    for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
+      BasicBlock *Dest = IBI->getDestination(i);
+      if (!Dest->hasAddressTaken() || !Succs.insert(Dest)) {
+        Dest->removePredecessor(BB);
+        IBI->removeDestination(i);
+        --i; --e;
+        Changed = true;
+      }
+    } 
+
+    if (IBI->getNumDestinations() == 0) {
+      // If the indirectbr has no successors, change it to unreachable.
+      new UnreachableInst(IBI->getContext(), IBI);
+      IBI->eraseFromParent();
+      Changed = true;
+    } else if (IBI->getNumDestinations() == 1) {
+      // If the indirectbr has one successor, change it to a direct branch.
+      BranchInst::Create(IBI->getDestination(0), IBI);
+      IBI->eraseFromParent();
+      Changed = true;
     }
   }
@@ -2005 +2096 @@
   // into our predecessor.
   pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
-  BasicBlock *OnlyPred = *PI++;
-  for (; PI != PE; ++PI)  // Search all predecessors, see if they are all same
-    if (*PI != OnlyPred) {
+  BasicBlock *OnlyPred = 0;
+  for (; PI != PE; ++PI) { // Search all predecessors, see if they are all same
+    if (!OnlyPred)
+      OnlyPred = *PI;
+    else if (*PI != OnlyPred) {
       OnlyPred = 0;       // There are multiple different predecessors...
       break;
     }
+  }
   
   if (OnlyPred)
@@ -2109 +2203 @@
 /// of the CFG.  It returns true if a modification was made.
 ///
-/// WARNING:  The entry node of a function may not be simplified.
-///
 bool llvm::SimplifyCFG(BasicBlock *BB, const TargetData *TD) {
   return SimplifyCFGOpt(TD).run(BB);