[WIP] Support merging common destinations checks w/uses outside of block

[reames]

Summary

[WIP] Do not review, cleanup needed.

[reames]

No longer actively working on this, may return to it in the future.

lib/Transforms/Utils/SimplifyCFG.cpp

static bool extractPredSuccWeights(BranchInst *PBI, BranchInst *BI,
   }
 }
 
 /// If this basic block is simple enough, and if a predecessor branches to us
 /// and one of our successors, fold the block into the predecessor and use
 /// logical operations to pick the right destination.
 bool llvm::FoldBranchToCommonDest(BranchInst *BI, unsigned BonusInstThreshold) {
   BasicBlock *BB = BI->getParent();
+  dbgs() << "candidate: " << *BI << "\n";
+
+  if (pred_empty(BB))
+    return false;
+
+  // If we have a single predecessor, we can be slightly more general below
+  const BasicBlock *SinglePredBB = BB->getSinglePredecessor();
 
   Instruction *Cond = nullptr;
   if (BI->isConditional())
     Cond = dyn_cast<Instruction>(BI->getCondition());
   else {
     // For unconditional branch, check for a simple CFG pattern, where
     // BB has a single predecessor and BB's successor is also its predecessor's
     // successor. If such pattern exists, check for CSE between BB and its
else {
     if (!Cond)
       return false;
   }
 
   if (!Cond || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) ||
       Cond->getParent() != BB || !Cond->hasOneUse())
     return false;
 
+  dbgs() << "here-1\n";
+
   // Make sure the instruction after the condition is the cond branch.
   BasicBlock::iterator CondIt = ++Cond->getIterator();
 
   // Ignore dbg intrinsics.
   while (isa<DbgInfoIntrinsic>(CondIt))
     ++CondIt;
 
   if (&*CondIt != BI)
     return false;
 
+  dbgs() << "here-2\n";
   // Only allow this transformation if computing the condition doesn't involve
   // too many instructions and these involved instructions can be executed
   // unconditionally. We denote all involved instructions except the condition
   // as "bonus instructions", and only allow this transformation when the
   // number of the bonus instructions does not exceed a certain threshold.
   unsigned NumBonusInsts = 0;
   for (auto I = BB->begin(); Cond != &*I; ++I) {
+    dbgs() << *I << "\n";
     // Ignore dbg intrinsics.
     if (isa<DbgInfoIntrinsic>(I))
       continue;
-    if (!I->hasOneUse() || !isSafeToSpeculativelyExecute(&*I))
+    dbgs() << I->hasOneUse() << " && " << isSafeToSpeculativelyExecute(&*I) << " \n";
+    if (!isSafeToSpeculativelyExecute(&*I))
+      return false;
+    // If we have more than one predecessor, there's no single value with which
+    // to update out of block uses.
+    if (!SinglePredBB) {
+      if (!I->hasOneUse())
         return false;
       // I has only one use and can be executed unconditionally.
       Instruction *User = dyn_cast<Instruction>(I->user_back());
       if (User == nullptr || User->getParent() != BB)
         return false;
+    }
+    dbgs() << *I << " (3)\n";
     // I is used in the same BB. Since BI uses Cond and doesn't have more slots
     // to use any other instruction, User must be an instruction between next(I)
     // and Cond.
     ++NumBonusInsts;
     // Early exits once we reach the limit.
     if (NumBonusInsts > BonusInstThreshold)
       return false;
+    dbgs() << *I << "(4)\n";
   }
 
+  dbgs() << "here-3\n";
+
+
   // Cond is known to be a compare or binary operator.  Check to make sure that
   // neither operand is a potentially-trapping constant expression.
   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0)))
     if (CE->canTrap())
       return false;
   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1)))
     if (CE->canTrap())
       return false;
 
+  dbgs() << "here-4\n";
+
   // Finally, don't infinitely unroll conditional loops.
   BasicBlock *TrueDest = BI->getSuccessor(0);
   BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : nullptr;
   if (TrueDest == BB || FalseDest == BB)
     return false;
 
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
     BasicBlock *PredBlock = *PI;
     BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator());
 
+    dbgs() << "PBI: " << *PBI << "\n";
+
+
     // Check that we have two conditional branches.  If there is a PHI node in
     // the common successor, verify that the same value flows in from both
     // blocks.
     SmallVector<PHINode *, 4> PHIs;
     if (!PBI || PBI->isUnconditional() ||
         (BI->isConditional() && !SafeToMergeTerminators(BI, PBI)) ||
         (!BI->isConditional() &&
          !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs)))
if (InvertPredCond) {
         NewCond =
             Builder.CreateNot(NewCond, PBI->getCondition()->getName() + ".not");
       }
 
       PBI->setCondition(NewCond);
       PBI->swapSuccessors();
     }
 
+    Instruction *New = nullptr;
+    if (SinglePredBB) {
+      // For a single predeccessor we know we can a) move rather than clone and
+      // b) be sure any uses outside BB are themselves dominated by our single
+      // predecessor.  
+      for (auto BonusInstItr = BB->begin(); Cond != &*BonusInstItr;) {
+        auto BonusInst = BonusInstItr;
+        BonusInstItr++;
+        if (isa<DbgInfoIntrinsic>(BonusInst))
+          // Could move now, but sake of consistency, fall through to common
+          // code.  
+          continue;
+        BonusInst->moveBefore(PBI);
+        
+        // Remove all potentially control dependent facts (TODO: could be more
+        // fine grained here)
+        BonusInst->dropUnknownNonDebugMetadata();
+      }
+      // TODO: Not actually new, rename probably warranted.
+      New = Cond;
+      Cond->moveBefore(PBI);
+    } else {
       // If we have bonus instructions, clone them into the predecessor block.
       // Note that there may be multiple predecessor blocks, so we cannot move
       // bonus instructions to a predecessor block.
       ValueToValueMapTy VMap; // maps original values to cloned values
       // We already make sure Cond is the last instruction before BI. Therefore,
       // all instructions before Cond other than DbgInfoIntrinsic are bonus
       // instructions.
       for (auto BonusInst = BB->begin(); Cond != &*BonusInst; ++BonusInst) {
         if (isa<DbgInfoIntrinsic>(BonusInst))
           continue;
         Instruction *NewBonusInst = BonusInst->clone();
         RemapInstruction(NewBonusInst, VMap,
                          RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
         VMap[&*BonusInst] = NewBonusInst;
         
         // If we moved a load, we cannot any longer claim any knowledge about
         // its potential value. The previous information might have been valid
         // only given the branch precondition.
         // For an analogous reason, we must also drop all the metadata whose
         // semantics we don't understand.
         NewBonusInst->dropUnknownNonDebugMetadata();
         
         PredBlock->getInstList().insert(PBI->getIterator(), NewBonusInst);
         NewBonusInst->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();
+      New = Cond->clone();
       RemapInstruction(New, VMap,
                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
       PredBlock->getInstList().insert(PBI->getIterator(), New);
       New->takeName(Cond);
       Cond->setName(New->getName() + ".old");
+    }
+    assert(New && "populated above!");
 
     if (BI->isConditional()) {
       Instruction *NewCond = cast<Instruction>(
           Builder.CreateBinOp(Opc, PBI->getCondition(), New, "or.cond"));
       PBI->setCondition(NewCond);
 
       uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
       bool HasWeights =
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
     // TODO: If BB is reachable from all paths through PredBlock, then we
     // could replace PBI's branch probabilities with BI's.
 
     // Copy any debug value intrinsics into the end of PredBlock.
     for (Instruction &I : *BB)
       if (isa<DbgInfoIntrinsic>(I))
         I.clone()->insertBefore(PBI);
 
+    BB->getParent()->dump();
     return true;
   }
   return false;
 }
 
 // If there is only one store in BB1 and BB2, return it, otherwise return
 // nullptr.
 static StoreInst *findUniqueStoreInBlocks(BasicBlock *BB1, BasicBlock *BB2) {