[SimplifyCFG] Rewrite SinkThenElseCodeToEnd

[jmolloy]

Summary

The new version has several advantages:

1. (IMNSHO) it's more readable and neater
2. It handles loads and stores properly
3. It can handle any number of incoming blocks rather than just two. I'll be taking advantage of this in a followup patch.

With this change we can now finally sink load-modify-store idioms such as:

if (a)
  return *b += 3;
else
  return *b += 4;

=>

%z = load i32, i32* %y
%.sink = select i1 %a, i32 3, i32 4
%b = add i32 %z, %.sink
store i32 %b, i32* %y
ret i32 %b

When this works for switches it'll be even more powerful.

[sanjoy]

lib/Transforms/Utils/SimplifyCFG.cpp

1263

Why not use Instruction::isIdenticalTo or Instruction::isIdenticalToWhenDefined?

1295

This is minor and optional to fix, but I'd write all of the any_of checks you have as all_of checks, I think that reads more natural -- "I want all of Insts to have this property, if not leave".

1299

Why not use llvm::any_of?

1301

Instead of having a dense block of code here, I'd piecemeal put the comments down here, like:

if (is not load or store)
  return may have side effects or mayreadorwritememory; // why?
...

also, why do you care about I->mayHaveSideEffects() || I->mayReadOrWriteMemory())?

1322

Can the number of operands vary between instructions in Inst? How about if they are all readnone calls with different # of arguments?

1324

Does areValuesTriviallySame take into account things like:

%a = load %x
*%x = 42;
%b = load %x

above %a and %b are trivially same, but won't compute the same value.

[jmolloy]

lib/Transforms/Utils/SimplifyCFG.cpp

1301

also, why do you care about I->mayHaveSideEffects() || I->mayReadOrWriteMemory())?

Primarily to keep this as NFC as possible. It now handles loads and stores, but I hadn't done an audit of the possible things that could go wrong if we allowed movement of sideeffect instructions.

I suppose this is probably fine. Would you like me to delete the restriction?

1322

This is enforced by Instruction::isSameOperationAs.

[jmolloy]

Thanks Sanjoy for the review! I think all your comments should be addressed now with the exception of one.

Cheers,

James

[jmolloy]

Ping!

[jmolloy]

Ping! Hans, do you have any comments on this?

[hans]

Looks good as far as I can tell. It would be good to hear if Sanjoy's happy with it too though, since he started reviewing it.

lib/Transforms/Utils/SimplifyCFG.cpp

1388

I know I'm oldfashioned, but I'd find this easier to read as a simple loop over Insts rather than all_of :-)

Since we want to return false for the cases below, we might as well do that directly rather than returning false in the lambda and then checking that return value.

1408

I think this would be easier to read as a for-loop too.

[hans]

When this works for switches it'll be even more powerful.

Oh yes.

And can it work for function calls too? I.e. transforming

if (foo)
  x = f(1)
else
  x = f(2)

to

x = f(foo ? 1 : 2);

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

1388

I think the llvm:: is a little superfluous here.

1395

The comment says "change memory" but you are using mayReadOrWriteMemory.

Which is right?

1458

I think llvm:: here is not needed.

1509

Use llvm's all_of?

[sanjoy]

Some comments inline (and apologies for the delay!).

lib/Transforms/Utils/SimplifyCFG.cpp

1322

I think this needs a comment describing what it does (especially the role of At0 and At1).

1337

Does this do the right thing for alloca instructions? If it does, can you please add a test case?

1415

The isa<PHINode>(U) seems repeated -- why not:

if (I0 is not store) {
  auto *PNUse = dyn_cast<>(*I0->user_begin());
  if (!PNUse || !all_of(Insts, [](I) { return *I->user_begin == PNUse; }))
    return false;
}

1420

Very minor, but I'd s/O/OI and s/E/OE.

1423

Does this work with token types (which cannot be PHI'ed)?

1444

Can't you use getPrevNode() here and earlier?

1470

You at least need to handle token types here.

[jmolloy]

Thanks all for the comments! Patch updated.

lib/Transforms/Utils/SimplifyCFG.cpp

1395

mayReadOrWriteMemory was intended to be a proxy for "sideeffects". mayHaveSideEffects() is better.

1423

The checks to isEHPad() catch all instructions that can take or return token types apart from catchret, which as a terminator can never be considered for sinking here.

1470

Tokens should never ever get here. I've added an assert to that effect.

[majnemer]

lib/Transforms/Utils/SimplifyCFG.cpp

1461

extra llvm::

1463

There are intrinsics which take an return tokens.

[jmolloy]

Thanks again for the review; sorry I forgot to update the last diff to the very latest version so it didn't have all the changes I'd intended to publish.

I think all comments are now addressed.

[sanjoy]

I think all comments are now addressed.

I think you missed two?

lib/Transforms/Utils/SimplifyCFG.cpp

1322

This one wasn't addressed.

1337

This one wasn't addressed.

[jmolloy]

Thanks Sanjoy. Sorry for not addressing those; must have got a bit lost in the "comment soup".

Addressed, and after extra testing I've discovered we could be sinking GEPs and replacing an operand that must be constant with a variable (struct indexing) so I've fixed that and added a testcase.

[sanjoy]

lgtm with minor comments inline.

lib/Transforms/Utils/SimplifyCFG.cpp

1328

Stray / at EOL?

1369

Optional, but I'd extract out a WritesMemory lambda out and use it twice. I suspect the conditions will be more readable that way.

1442

Again, I personally would've extracted out a named SameAsI0 lambda here. That way the condition will read more naturally.

[jmolloy]

Thanks Sanjoy - committed with your suggestions in r278660!

lib/Transforms/Utils/SimplifyCFG.cpp

1337

This is never called for alloca instructions. There is a known set of semantics-breaking instructions pruned out in line 1389.

[sebpop]

Hi James,

a big regression on a proprietary benchmark attracted my attention to your patch.
I need to do a bit more perf analysis to figure out why the regression happened.

Reading through the patch, I remembered my tries to make the CFG simplifier stronger
to catch a hoist testcase. I think there are serious limitations to the CFG simplifier, and
also because it is called a gazillion times (after every other CFG transform pass), it may
be quite cost prohibitive to implement anything stronger than what it currently does.

I was wondering whether you would consider extending GVN-hoist to sink instructions?

lib/Transforms/Utils/SimplifyCFG.cpp

1368

Have you considered implementing sinking in the GVN-hoist pass?
That would make sinking more powerful as it works on MemorySSA,
more general by handling switch stmts, and arbitrarily complex CFG.

Sinking candidates are already detected as equivalent expressions
by the hoister using value numbering. In some cases some expressions
can only be sinked because of side effects in the upper CFG: those are
good candidates to be sinked if there are no hazards below.

[jmolloy]

Hi Sebastien,

Sorry to hear this caused a regression; perhaps it's similar to https://llvm.org/bugs/show_bug.cgi?id=30188 ? There, improved SimplifyCFG confuses SROA.

SimplifyCFG's sinking logic was and is indeed dumb. It being run a million times is a dual-edged sword though - yes, complex algorithms are difficult to run in the time constraint but also you get many attempts at optimizing across the compilation pipeline. Code sinking is a really important optimization that I think really needs to be done multiple times during canonicalization as more opportunities are opened up (by CSE, InstCombine etc).

I think there's certainly an upside in implementing a better, higher runtime algorithm in something like GVN hoist, but I don't think that should replace the dumb logic in SimplifyCFG entirely. In fact, this rewrite makes it slightly less dumb at no extra algorithmic complexity, and the code you commented on (that is deliberately conservative) gets deleted in https://reviews.llvm.org/D23911 as it becomes no longer needed.

Cheers,

James

lib/Transforms/Utils/SimplifyCFG.cpp

     for (BasicBlock::iterator BBI = Succ->begin();
          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
       Value *BB1V = PN->getIncomingValueForBlock(BB1);
       Value *BB2V = PN->getIncomingValueForBlock(BB2);
       if (BB1V == BB2V)
         continue;
 
       // Check for passingValueIsAlwaysUndefined here because we would rather
       // eliminate undefined control flow then converting it to a select.
       if (passingValueIsAlwaysUndefined(BB1V, PN) ||
           passingValueIsAlwaysUndefined(BB2V, PN))
         return Changed;
 
       if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V))
         return Changed;
       if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V))
         return Changed;

   // them.  If they do, all PHI entries for BB1/BB2 must agree for all PHI
   // nodes, so we insert select instruction to compute the final result.
   std::map<std::pair<Value *, Value *>, SelectInst *> InsertedSelects;
   for (BasicBlock *Succ : successors(BB1)) {
     PHINode *PN;
     for (BasicBlock::iterator BBI = Succ->begin();
          (PN = dyn_cast<PHINode>(BBI)); ++BBI) {
       Value *BB1V = PN->getIncomingValueForBlock(BB1);
       Value *BB2V = PN->getIncomingValueForBlock(BB2);
       if (BB1V == BB2V)
         continue;
 
       // These values do not agree.  Insert a select instruction before NT
       // that determines the right value.
       SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)];
       if (!SI)
         SI = cast<SelectInst>(
             Builder.CreateSelect(BI->getCondition(), BB1V, BB2V,
                                  BB1V->getName() + "." + BB2V->getName(), BI));
 
       // Make the PHI node use the select for all incoming values for BB1/BB2
       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
         if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2)
           PN->setIncomingValue(i, SI);
     }
   }
 
   // Update any PHI nodes in our new successors.
   for (BasicBlock *Succ : successors(BB1))
     AddPredecessorToBlock(Succ, BIParent, BB1);
 
   EraseTerminatorInstAndDCECond(BI);
   return true;
 }
 
-/// Given an unconditional branch that goes to BBEnd,
-/// check whether BBEnd has only two predecessors and the other predecessor
-/// ends with an unconditional branch. If it is true, sink any common code
-/// in the two predecessors to BBEnd.
-static bool SinkThenElseCodeToEnd(BranchInst *BI1) {
-  assert(BI1->isUnconditional());
-  BasicBlock *BB1 = BI1->getParent();
-  BasicBlock *BBEnd = BI1->getSuccessor(0);
-
-  // Check that BBEnd has two predecessors and the other predecessor ends with
-  // an unconditional branch.
-  pred_iterator PI = pred_begin(BBEnd), PE = pred_end(BBEnd);
-  BasicBlock *Pred0 = *PI++;
-  if (PI == PE) // Only one predecessor.
-    return false;
-  BasicBlock *Pred1 = *PI++;
-  if (PI != PE) // More than two predecessors.
+// Return true if V0 and V1 are equivalent. This handles the obvious cases
+// where V0 == V1 and V0 and V1 are both identical instructions, but also
+// handles loads and stores with identical operands.
+//
+// Because determining if two memory instructions are equivalent
+// depends on control flow, the \c At0 and \c At1 parameters specify a
+// location for the query. This function is essentially answering the/
+// query "If V0 were moved to At0, and V1 were moved to At1, are V0 and V1
+// equivalent?". In practice this means checking that moving V0 to At0
+// doesn't cross any other memory instructions.
+static bool areValuesTriviallySame(Value *V0, BasicBlock::const_iterator At0,
+                                   Value *V1, BasicBlock::const_iterator At1) {
+  if (V0 == V1)
+    return true;
+  
+  // Also check for instructions that are identical but not pointer-identical.
+  // This can include load instructions that haven't been CSE'd.
+  if (!isa<Instruction>(V0) || !isa<Instruction>(V1))
     return false;
-  BasicBlock *BB2 = (Pred0 == BB1) ? Pred1 : Pred0;
-  BranchInst *BI2 = dyn_cast<BranchInst>(BB2->getTerminator());
-  if (!BI2 || !BI2->isUnconditional())
+  const auto *I0 = cast<Instruction>(V0);
+  const auto *I1 = cast<Instruction>(V1);
+  if (!I0->isIdenticalToWhenDefined(I1))
     return false;
 
-  // Gather the PHI nodes in BBEnd.
-  SmallDenseMap<std::pair<Value *, Value *>, PHINode *> JointValueMap;
-  Instruction *FirstNonPhiInBBEnd = nullptr;
-  for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end(); I != E; ++I) {
-    if (PHINode *PN = dyn_cast<PHINode>(I)) {
-      Value *BB1V = PN->getIncomingValueForBlock(BB1);
-      Value *BB2V = PN->getIncomingValueForBlock(BB2);
-      JointValueMap[std::make_pair(BB1V, BB2V)] = PN;
-    } else {
-      FirstNonPhiInBBEnd = &*I;
-      break;
-    }
-  }
-  if (!FirstNonPhiInBBEnd)
+  if (!I0->mayReadOrWriteMemory())
+    return true;
+
+  // Instructions that may read or write memory have extra restrictions. We
+  // must ensure we don't treat %a and %b as equivalent in code such as:
+  //
+  //  %a = load %x
+  //  store %x, 1
+  //  if (%c) {
+  //    %b = load %x
+  //    %d = add %b, 1
+  //  } else {
+  //    %d = add %a, 1
+  //  }
+
+  // Be conservative. We don't want to search the entire CFG between def
+  // and use; if the def isn't in the same block as the use just bail.
+  if (I0->getParent() != At0->getParent() ||
+      I1->getParent() != At1->getParent())
     return false;
 
-  // This does very trivial matching, with limited scanning, to find identical
-  // instructions in the two blocks.  We scan backward for obviously identical
-  // instructions in an identical order.
-  BasicBlock::InstListType::reverse_iterator RI1 = BB1->getInstList().rbegin(),
-                                             RE1 = BB1->getInstList().rend(),
-                                             RI2 = BB2->getInstList().rbegin(),
-                                             RE2 = BB2->getInstList().rend();
-  // Skip debug info.
-  while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1))
-    ++RI1;
-  if (RI1 == RE1)
+  // Again, be super conservative. Ideally we'd be able to query AliasAnalysis
+  // but we currently don't have that available.
+  if (std::any_of(std::next(I0->getIterator()), At0, [](const Instruction &I) {
+        return I.mayReadOrWriteMemory();
+      }))
     return false;
-  while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2))
-    ++RI2;
-  if (RI2 == RE2)
+  if (std::any_of(std::next(I1->getIterator()), At1, [](const Instruction &I) {
+        return I.mayReadOrWriteMemory();
+      }))
     return false;
-  // Skip the unconditional branches.
-  ++RI1;
-  ++RI2;
+  return true;
+}
 
-  bool Changed = false;
-  while (RI1 != RE1 && RI2 != RE2) {
-    // Skip debug info.
-    while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1))
-      ++RI1;
-    if (RI1 == RE1)
-      return Changed;
-    while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2))
-      ++RI2;
-    if (RI2 == RE2)
-      return Changed;
+// Is it legal to replace the operand \c OpIdx of \c GEP with a PHI node?
+static bool canReplaceGEPOperandWithPHI(const Instruction *GEP,
+                                        unsigned OpIdx) {
+  if (OpIdx == 0)
+    return true;
+  gep_type_iterator It = std::next(gep_type_begin(GEP), OpIdx - 1);
+  return !It->isStructTy();
+}
 
-    Instruction *I1 = &*RI1, *I2 = &*RI2;
-    auto InstPair = std::make_pair(I1, I2);
-    // I1 and I2 should have a single use in the same PHI node, and they
-    // perform the same operation.
-    // Cannot move control-flow-involving, volatile loads, vaarg, etc.
-    if (isa<PHINode>(I1) || isa<PHINode>(I2) || isa<TerminatorInst>(I1) ||
-        isa<TerminatorInst>(I2) || I1->isEHPad() || I2->isEHPad() ||
-        isa<AllocaInst>(I1) || isa<AllocaInst>(I2) ||
-        I1->mayHaveSideEffects() || I2->mayHaveSideEffects() ||
-        I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() ||
-        !I1->hasOneUse() || !I2->hasOneUse() || !JointValueMap.count(InstPair))
-      return Changed;
+// All blocks in Blocks unconditionally jump to a common successor. Analyze
+// the last non-terminator instruction in each block and return true if it would
+// be possible to sink them into their successor, creating one common
+// instruction instead. Set NumPHIsRequired to the number of PHI nodes that
+// would need to be created during sinking.
+static bool canSinkLastInstruction(ArrayRef<BasicBlock*> Blocks,
+                                   unsigned &NumPHIsRequired) {
+  SmallVector<Instruction*,4> Insts;
+  for (auto *BB : Blocks) {
+    if (BB->getTerminator() == &BB->front())
+      // Block was empty.
+      return false;
+    Insts.push_back(BB->getTerminator()->getPrevNode());
+  }
 
-    // Check whether we should swap the operands of ICmpInst.
-    // TODO: Add support of communativity.
-    ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2);
-    bool SwapOpnds = false;
-    if (ICmp1 && ICmp2 && ICmp1->getOperand(0) != ICmp2->getOperand(0) &&
-        ICmp1->getOperand(1) != ICmp2->getOperand(1) &&
-        (ICmp1->getOperand(0) == ICmp2->getOperand(1) ||
-         ICmp1->getOperand(1) == ICmp2->getOperand(0))) {
-      ICmp2->swapOperands();
-      SwapOpnds = true;
-    }
-    if (!I1->isSameOperationAs(I2)) {
-      if (SwapOpnds)
-        ICmp2->swapOperands();
-      return Changed;
-    }
+  // Prune out obviously bad instructions to move. Any non-store instruction
+  // must have exactly one use, and we check later that use is by a single,
+  // common PHI instruction in the successor.
+  for (auto *I : Insts) {
+    // These instructions may change or break semantics if moved.
+    if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
+        I->getType()->isTokenTy())
+      return false;
+    // Apart from loads and stores, we won't move anything that could
+    // change memory or have sideeffects.
+    if (!isa<StoreInst>(I) && !isa<LoadInst>(I) &&
+        (I->mayHaveSideEffects() || I->mayHaveSideEffects()))
+      return false;
+    // Everything must have only one use too, apart from stores which
+    // have no uses.
+    if (!isa<StoreInst>(I) && !I->hasOneUse())
+      return false;
+  }
 
-    // The operands should be either the same or they need to be generated
-    // with a PHI node after sinking. We only handle the case where there is
-    // a single pair of different operands.
-    Value *DifferentOp1 = nullptr, *DifferentOp2 = nullptr;
-    unsigned Op1Idx = ~0U;
-    for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) {
-      if (I1->getOperand(I) == I2->getOperand(I))
-        continue;
-      // Early exit if we have more-than one pair of different operands or if
-      // we need a PHI node to replace a constant.
-      if (Op1Idx != ~0U || isa<Constant>(I1->getOperand(I)) ||
-          isa<Constant>(I2->getOperand(I))) {
-        // If we can't sink the instructions, undo the swapping.
-        if (SwapOpnds)
-          ICmp2->swapOperands();
-        return Changed;
-      }
-      DifferentOp1 = I1->getOperand(I);
-      Op1Idx = I;
-      DifferentOp2 = I2->getOperand(I);
+  const Instruction *I0 = Insts.front();
+  for (auto *I : Insts)
+    if (!I->isSameOperationAs(I0))
+      return false;
+
+  // If this isn't a store, check the only user is a single PHI.
+  if (!isa<StoreInst>(I0)) {
+    auto *PNUse = dyn_cast<PHINode>(*I0->user_begin());
+    if (!PNUse ||
+        !all_of(Insts, [&PNUse](const Instruction *I) {
+          return *I->user_begin() == PNUse;
+        }))
+      return false;
+  }
+
+  NumPHIsRequired = 0;
+  for (unsigned OI = 0, OE = I0->getNumOperands(); OI != OE; ++OI) {
+    if (I0->getOperand(OI)->getType()->isTokenTy())
+      // Don't touch any operand of token type.
+      return false;
+    if (!all_of(Insts, [&I0, OI](const Instruction *I) {
+          return areValuesTriviallySame(I->getOperand(OI), I->getIterator(),
+                                        I0->getOperand(OI), I0->getIterator());
+        })) {
+      if (isa<GetElementPtrInst>(I0) && !canReplaceGEPOperandWithPHI(I0, OI))
+        // We can't create a PHI from this GEP.
+        return false;
+      ++NumPHIsRequired;
     }
+  }
+  return true;
+}
 
-    DEBUG(dbgs() << "SINK common instructions " << *I1 << "\n");
-    DEBUG(dbgs() << "                         " << *I2 << "\n");
-
-    // We insert the pair of different operands to JointValueMap and
-    // remove (I1, I2) from JointValueMap.
-    if (Op1Idx != ~0U) {
-      auto &NewPN = JointValueMap[std::make_pair(DifferentOp1, DifferentOp2)];
-      if (!NewPN) {
-        NewPN =
-            PHINode::Create(DifferentOp1->getType(), 2,
-                            DifferentOp1->getName() + ".sink", &BBEnd->front());
-        NewPN->addIncoming(DifferentOp1, BB1);
-        NewPN->addIncoming(DifferentOp2, BB2);
-        DEBUG(dbgs() << "Create PHI node " << *NewPN << "\n";);
-      }
-      // I1 should use NewPN instead of DifferentOp1.
-      I1->setOperand(Op1Idx, NewPN);
+// Assuming canSinkLastInstruction(Blocks) has returned true, sink the last
+// instruction of every block in Blocks to their common successor, commoning
+// into one instruction.
+static void sinkLastInstruction(ArrayRef<BasicBlock*> Blocks) {
+  unsigned Dummy;
+  (void)Dummy;
+  assert(canSinkLastInstruction(Blocks, Dummy) &&
+         "Must analyze before transforming!");
+  auto *BBEnd = Blocks[0]->getTerminator()->getSuccessor(0);
+
+  // canSinkLastInstruction returning true guarantees that every block has at
+  // least one non-terminator instruction.
+  SmallVector<Instruction*,4> Insts;
+  for (auto *BB : Blocks)
+    Insts.push_back(BB->getTerminator()->getPrevNode());
+
+  // We don't need to do any checking here; canSinkLastInstruction should have
+  // done it all for us.
+  Instruction *I0 = Insts.front();
+  SmallVector<Value*, 4> NewOperands;
+  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O) {
+    // This check is different to that in canSinkLastInstruction. There, we
+    // cared about the global view once simplifycfg (and instcombine) have
+    // completed - it takes into account PHIs that become trivially
+    // simplifiable.  However here we need a more local view; if an operand
+    // differs we create a PHI and rely on instcombine to clean up the very
+    // small mess we may make.
+    bool NeedPHI = any_of(Insts, [&I0, O](const Instruction *I) {
+      return I->getOperand(O) != I0->getOperand(O);
+    });
+    if (!NeedPHI) {
+      NewOperands.push_back(I0->getOperand(O));
+      continue;
     }
-    PHINode *OldPN = JointValueMap[InstPair];
-    JointValueMap.erase(InstPair);
-
-    // We need to update RE1 and RE2 if we are going to sink the first
-    // instruction in the basic block down.
-    bool UpdateRE1 = (I1 == &BB1->front()), UpdateRE2 = (I2 == &BB2->front());
-    // Sink the instruction.
-    BBEnd->getInstList().splice(FirstNonPhiInBBEnd->getIterator(),
-                                BB1->getInstList(), I1);
-    if (!OldPN->use_empty())
-      OldPN->replaceAllUsesWith(I1);
-    OldPN->eraseFromParent();
 
-    if (!I2->use_empty())
-      I2->replaceAllUsesWith(I1);
-    I1->intersectOptionalDataWith(I2);
-    // TODO: Use combineMetadata here to preserve what metadata we can
-    // (analogous to the hoisting case above).
-    I2->eraseFromParent();
+    // Create a new PHI in the successor block and populate it.
+    auto *Op = I0->getOperand(O);
+    assert(!Op->getType()->isTokenTy() && "Can't PHI tokens!");
+    auto *PN = PHINode::Create(Op->getType(), Insts.size(),
+                               Op->getName() + ".sink", &BBEnd->front());
+    for (auto *I : Insts)
+      PN->addIncoming(I->getOperand(O), I->getParent());
+    NewOperands.push_back(PN);
+  }
+
+  // Arbitrarily use I0 as the new "common" instruction; remap its operands
+  // and move it to the start of the successor block.
+  for (unsigned O = 0, E = I0->getNumOperands(); O != E; ++O)
+    I0->getOperandUse(O).set(NewOperands[O]);
+  I0->moveBefore(&*BBEnd->getFirstInsertionPt());
+
+  if (!isa<StoreInst>(I0)) {
+    // canSinkLastInstruction checked that all instructions were used by
+    // one and only one PHI node. Find that now, RAUW it to our common
+    // instruction and nuke it.
+    assert(I0->hasOneUse());
+    auto *PN = cast<PHINode>(*I0->user_begin());
+    PN->replaceAllUsesWith(I0);
+    PN->eraseFromParent();
+  }
 
-    if (UpdateRE1)
-      RE1 = BB1->getInstList().rend();
-    if (UpdateRE2)
-      RE2 = BB2->getInstList().rend();
-    FirstNonPhiInBBEnd = &*I1;
+  // Finally nuke all instructions apart from the common instruction.
+  for (auto *I : Insts)
+    if (I != I0)
+      I->eraseFromParent();
+}
+
+/// Given an unconditional branch that goes to BBEnd,
+/// check whether BBEnd has only two predecessors and the other predecessor
+/// ends with an unconditional branch. If it is true, sink any common code
+/// in the two predecessors to BBEnd.
+static bool SinkThenElseCodeToEnd(BranchInst *BI1) {
+  assert(BI1->isUnconditional());
+  BasicBlock *BBEnd = BI1->getSuccessor(0);
+
+  SmallVector<BasicBlock*,4> Blocks;
+  for (auto *BB : predecessors(BBEnd))
+    Blocks.push_back(BB);
+  if (Blocks.size() != 2 ||
+      !all_of(Blocks, [](const BasicBlock *BB) {
+        auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
+        return BI && BI->isUnconditional();
+      }))
+    return false;
+
+  bool Changed = false;
+  unsigned NumPHIsToInsert;
+  while (canSinkLastInstruction(Blocks, NumPHIsToInsert) && NumPHIsToInsert <= 1) {
+    sinkLastInstruction(Blocks);
     NumSinkCommons++;
     Changed = true;
   }
   return Changed;
 }
 
 /// \brief Determine if we can hoist sink a sole store instruction out of a
 /// conditional block.

test/CodeGen/ARM/avoid-cpsr-rmw.ll

if.then:
   store i32 7, i32* %p, align 4
   %incdec.ptr2 = getelementptr inbounds i32, i32* %p, i32 2
   store i32 8, i32* %incdec.ptr1, align 4
   store i32 9, i32* %incdec.ptr2, align 4
   br label %if.end
 
 if.else:
   store i32 3, i32* %p, align 4
-  %incdec.ptr5 = getelementptr inbounds i32, i32* %p, i32 2
+  %incdec.ptr5 = getelementptr inbounds i32, i32* %p, i32 3
   store i32 5, i32* %incdec.ptr1, align 4
   store i32 6, i32* %incdec.ptr5, align 4
   br label %if.end
 
 if.end:
   ret void
 }

test/DebugInfo/ARM/single-constant-use-preserves-dbgloc.ll

 ; RUN: llc -filetype=asm -asm-verbose=0 < %s | FileCheck %s
 
 ; int main()
 ; {
 ;     int x = 0;
 ;     if (x > 0)
 ;         return x;
 ;     x = -1; // <== this line should have correct debug location
 ;     return -1;
 ; }
 
+; CHECK: mvnlt
 ; CHECK: .loc 1 6 7
-; CHECK: mvn
+; CHECK: strlt
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "armv7--linux-gnueabihf"
 
 ; Function Attrs: nounwind
 define i32 @main() !dbg !4 {
 entry:
   %retval = alloca i32, align 4

test/Transforms/SimplifyCFG/AArch64/prefer-fma.ll

 ; fsub ((fmul x, y), z)
 if.else:                                          ; preds = %entry
 ; CHECK-LABEL: if.else:
 ; CHECK:   %mul1 = fmul fast double %1, %2
 ; CHECK-NEXT:   %sub1 = fsub fast double %mul1, %0
   %4 = load double, double* %a, align 8
   %mul1 = fmul fast double %1, %4
   %sub1 = fsub fast double %mul1, %0
-  store double %sub1, double* %y, align 8
+  %gep1 = getelementptr double, double* %y, i32 1
+  store double %sub1, double* %gep1, align 8
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   %5 = load double, double* %y, align 8
   %cmp2 = fcmp oeq double %5, 2.000000e+00
   %6 = load double, double* %x, align 8
   br i1 %cmp2, label %if.then2, label %if.else2
 

test/Transforms/SimplifyCFG/sink-common-code.ll

 }
 
 ; CHECK-LABEL: test3
 ; CHECK: select
 ; CHECK: call
 ; CHECK: call
 ; CHECK: add
 ; CHECK-NOT: br
+
+define i32 @test4(i1 zeroext %flag, i32 %x, i32* %y) {
+entry:
+  br i1 %flag, label %if.then, label %if.else
+
+if.then:
+  %a = add i32 %x, 5
+  store i32 %a, i32* %y
+  br label %if.end
+
+if.else:
+  %b = add i32 %x, 7
+  store i32 %b, i32* %y
+  br label %if.end
+
+if.end:
+  ret i32 1
+}
+
+; CHECK-LABEL: test4
+; CHECK: select
+; CHECK: store
+; CHECK-NOT: store
+
+define i32 @test5(i1 zeroext %flag, i32 %x, i32* %y) {
+entry:
+  br i1 %flag, label %if.then, label %if.else
+
+if.then:
+  %a = add i32 %x, 5
+  store volatile i32 %a, i32* %y
+  br label %if.end
+
+if.else:
+  %b = add i32 %x, 7
+  store i32 %b, i32* %y
+  br label %if.end
+
+if.end:
+  ret i32 1
+}
+
+; CHECK-LABEL: test5
+; CHECK: store volatile
+; CHECK: store
+
+define i32 @test6(i1 zeroext %flag, i32 %x, i32* %y) {
+entry:
+  br i1 %flag, label %if.then, label %if.else
+
+if.then:
+  %a = add i32 %x, 5
+  store volatile i32 %a, i32* %y
+  br label %if.end
+
+if.else:
+  %b = add i32 %x, 7
+  store volatile i32 %b, i32* %y
+  br label %if.end
+
+if.end:
+  ret i32 1
+}
+
+; CHECK-LABEL: test6
+; CHECK: select
+; CHECK: store volatile
+; CHECK-NOT: store
+
+define i32 @test7(i1 zeroext %flag, i32 %x, i32* %y) {
+entry:
+  br i1 %flag, label %if.then, label %if.else
+
+if.then:
+  %z = load volatile i32, i32* %y
+  %a = add i32 %z, 5
+  store volatile i32 %a, i32* %y
+  br label %if.end
+
+if.else:
+  %w = load volatile i32, i32* %y
+  %b = add i32 %w, 7
+  store volatile i32 %b, i32* %y
+  br label %if.end
+
+if.end:
+  ret i32 1
+}
+
+; CHECK-LABEL: test7
+; CHECK-DAG: select
+; CHECK-DAG: load volatile
+; CHECK: store volatile
+; CHECK-NOT: load
+; CHECK-NOT: store
+
+; %z and %w are in different blocks. We shouldn't sink the add because
+; there may be intervening memory instructions.
+define i32 @test8(i1 zeroext %flag, i32 %x, i32* %y) {
+entry:
+  %z = load volatile i32, i32* %y
+  br i1 %flag, label %if.then, label %if.else
+
+if.then:
+  %a = add i32 %z, 5
+  store volatile i32 %a, i32* %y
+  br label %if.end
+
+if.else:
+  %w = load volatile i32, i32* %y
+  %b = add i32 %w, 7
+  store volatile i32 %b, i32* %y
+  br label %if.end
+
+if.end:
+  ret i32 1
+}
+
+; CHECK-LABEL: test8
+; CHECK: add
+; CHECK: add
+
+; The extra store in %if.then means %z and %w are not equivalent.
+define i32 @test9(i1 zeroext %flag, i32 %x, i32* %y, i32* %p) {
+entry:
+  br i1 %flag, label %if.then, label %if.else
+
+if.then:
+  store i32 7, i32* %p
+  %z = load volatile i32, i32* %y
+  store i32 6, i32* %p
+  %a = add i32 %z, 5
+  store volatile i32 %a, i32* %y
+  br label %if.end
+
+if.else:
+  %w = load volatile i32, i32* %y
+  %b = add i32 %w, 7
+  store volatile i32 %b, i32* %y
+  br label %if.end
+
+if.end:
+  ret i32 1
+}
+
+; CHECK-LABEL: test9
+; CHECK: add
+; CHECK: add
+
+%struct.anon = type { i32, i32 }
+
+; The GEP indexes a struct type so cannot have a variable last index.
+define i32 @test10(i1 zeroext %flag, i32 %x, i32* %y, %struct.anon* %s) {
+entry:
+  br i1 %flag, label %if.then, label %if.else
+
+if.then:
+  %dummy = add i32 %x, 5
+  %gepa = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 0
+  store volatile i32 %x, i32* %gepa
+  br label %if.end
+
+if.else:
+  %dummy1 = add i32 %x, 6
+  %gepb = getelementptr inbounds %struct.anon, %struct.anon* %s, i32 0, i32 1
+  store volatile i32 %x, i32* %gepb
+  br label %if.end
+
+if.end:
+  ret i32 1
+}
+
+; CHECK-LABEL: test10
+; CHECK: getelementptr
+; CHECK: getelementptr
+; CHECK: phi
+; CHECK: store volatile