[SimplifyCFG] Reduce memory churn during common case for branch commoning [NFC]

[reames]

Summary

I figured this one was worthy of an extra set of eyes despite being reasonable straight forward code wise. While the patch does exactly what the subject says, the motivation is really to simplify a follow on patch (https://reviews.llvm.org/D51458). I'm legitimately unsure if it makes sense to land this in isolation, or just role it into the combined patch.

[reames]

(slightly modified patch to reduce overhead for multiple predecessor case too)

[reames]

reverse last rebase, the small addition was buggy (iterator invalidation)

[mkazantsev]

lib/Transforms/Utils/SimplifyCFG.cpp

2694

What if the predecessor block has more than one successor? You'll end up moving loads and other dangerous instruction across conditional branches.

[mkazantsev]

Oh, I've misread what function that was. If both branches go to the same block then it should be fine.

lib/Transforms/Utils/SimplifyCFG.cpp

2694

I've misread what method was that, my bad. :) This should be fine.
However I have no idea how iterators interact with moveBefore, it may be safier to use an auxiliary vector here for that.

[reames]

Not something I expect to get back to.

lib/Transforms/Utils/SimplifyCFG.cpp

if (InvertPredCond) {
         NewCond =
             Builder.CreateNot(NewCond, PBI->getCondition()->getName() + ".not");
       }
 
       PBI->setCondition(NewCond);
       PBI->swapSuccessors();
     }
 
-    // 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.
+    // Ensure all instructions are cloned to the predecessor block, and
+    // identify the copy of Cond in the predecessor.  As a small optimization
+    // for the common case to reduce allocation traffic, we move instructions
+    // if we know there is at most a single predecessor.
+    Instruction *CondInPred = nullptr;
+    if (PredCount == 1) {
+      for (auto BonusInstItr = BB->begin(); Cond != &*BonusInstItr;) {
+        auto BonusInst = BonusInstItr++;
+        BonusInst->moveBefore(PBI);
+        // Remove all potentially control dependent facts (TODO: could be more
+        // fine grained here)
+        BonusInst->dropUnknownNonDebugMetadata();
+      }
+      CondInPred = Cond;
+      CondInPred->moveBefore(PBI);
+    } else {
+      // Handle the general case where we may have more than one predecessor
+      // and thus need to clone rather than move.  
       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) {
         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();
+        // Remove all potentially control dependent facts (TODO: could be more
+        // fine grained here)
+        BonusInst->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 *CondInPred = Cond->clone();
+      // Clone Cond into the predecessor basic block
+      CondInPred = Cond->clone();
       RemapInstruction(CondInPred, VMap,
                        RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
       PredBlock->getInstList().insert(PBI->getIterator(), CondInPred);
       CondInPred->takeName(Cond);
       Cond->setName(CondInPred->getName() + ".old");
-
+    }
     if (BI->isConditional()) {
       Instruction *NewCond = cast<Instruction>(
           Builder.CreateBinOp(Opc, PBI->getCondition(), CondInPred, "or.cond"));
       PBI->setCondition(NewCond);
 
       uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight;
       bool HasWeights =
           extractPredSuccWeights(PBI, BI, PredTrueWeight, PredFalseWeight,