[SimplifyCFG] Transform for redirecting phis between unmergeable BB and SuccBB

[XChy]

Summary

This patch extends function TryToSimplifyUncondBranchFromEmptyBlock to handle the similar cases below.

define i8 @src(i8 noundef %arg) {
start:
  switch i8 %arg, label %unreachable [
    i8 0, label %case012
    i8 1, label %case1
    i8 2, label %case2
    i8 3, label %end
  ]

unreachable:
  unreachable

case1:
  br label %case012

case2:
  br label %case012

case012:
  %phi1 = phi i8 [ 3, %case2 ], [ 2, %case1 ], [ 1, %start ]
  br label %end

end:
  %phi2 = phi i8 [ %phi1, %case012 ], [ 4, %start ]
  ret i8 %phi2
}

The phis here should be merged into one phi, so that we can better optimize it:

define i8 @tgt(i8 noundef %arg) {
start:
  switch i8 %arg, label %unreachable [
    i8 0, label %end
    i8 1, label %case1
    i8 2, label %case2
    i8 3, label %case3
  ]

unreachable:
  unreachable

case1:
  br label %end

case2:
  br label %end

case3:
  br label %end

end:
  %phi = phi i8 [ 4, %case3 ], [ 3, %case2 ], [ 2, %case1 ], [ 1, %start ]
  ret i8 %phi
}

Proof:
normal
multiple stages
multiple stages 2
multiple phi combinations

And lookup table optimization should convert it into add %arg 1.
This patch just match similar CFG structure and merge the phis in different cases.

Maybe such transform can be applied to other situations besides switch,
but I'm not sure whether it's better than not merging. Therefore, I only try it in switch,

Related issue:
Switch not fully optimized #63876

[XChy]

Avoid infinite loops

[XChy]

• Preserve domtree

[XChy]

Fix the bugs of merging the phis from the BasicBlock out of switch.

[nikic]

Just some nits for now, I need to go over the logic carefully another time.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

284 ↗

(On Diff #543242)

nit: wrong & formatting

6750 ↗

(On Diff #543242)

drop "the"

6771 ↗

(On Diff #543242)

Missing period at end of sentence.

6776 ↗

(On Diff #543242)

Omit braces

6778 ↗

(On Diff #543242)

Using successors() instead of cases() would be more direct here?

6791 ↗

(On Diff #543242)

Move this logic into a separate function, so you can use early return instead of IsMatched.

6825 ↗

(On Diff #543242)

Just because something has a single successor, does not mean it's a plain branch.

6832 ↗

(On Diff #543242)

CasePhi->use_empty()?

[XChy]

• Fix all the nits.
• Extract the logic of canMergePhisOfCase

[nikic]

Okay, I think the logic here is mostly correct, though I'm not sure whether the overall framing for the transform is the right one.

I think the core of the transform is the following:

1. We have a block A containing only phi nodes.
2. With an unconditional branch to a block B that uses the phi nodes from A only in phi nodes.
3. For edges PA -> A, PB -> B we have two cases:

3a. PA != PB. This is the straightforward case, where we can just redirect PA -> B without causing a phi conflict.
3b. PA == PB. This is the interesting case. We keep both edges here, and keep the phi node in A. If there is just one such conflict, then the phi node in A because a single-element phi, and we can remove it entirely. Otherwise, we should have to keep the phi. In that case the transform is probably(?) not worthwhile, so we should limit to the case where A and B have a single common predecessor.

This makes the root of the transform the "uncond branch with only phis" block, and has no direct relation to switch instructions. This would be pretty close to TryToSimplifyUncondBranchFromEmptyBlock(), just for the case where we have a conflict on one predecessor, and as such cannot actually remove the block completely, but can rewrite in order to remove the phi nodes.

Does this framing make sense to you?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6752 ↗

(On Diff #543392)

SmallPtrSetImpl for arguments

6767–6773 ↗

(On Diff #543392)

6780 ↗

(On Diff #543392)

Omit braces

6784 ↗

(On Diff #543392)

Unless I'm missing something, nothing here prevents CaseBB from dominating SuccBB, in which case there might be uses of phis from CaseBB outside of phis in SuccBB. Is the transform valid in that case?

6837 ↗

(On Diff #543392)

2 *

[XChy]

Thanks for your review! I understand your framing and it clear my mind. This framing is much general, not just for switch. And as you analyse, actually, a large part of the logic of this patch is copied from TryToSimplifyUncondBranchFromEmptyBlock, specified for switch. I restrict this fold in a narrow situation. Though this transformation is not directly related to switch, but I didn't apply such mergence to all BasicBlocks, since it's not always worthwhile as you say.

In switch, there are often empty case successors with only phis that can be merged into CommonDest, and such phis mergence

• Can be much more friendly to LookupTable optimization or something else.
• May prevent multiple calls to getCaseResults, I think.
• Bring better IR.
• Can serve as a canonicalization of switch.

But for other situation, I'm not sure if this mergence is always a good transform. I have concerns here:

• Too much inefficient mergeablity checks.
• Such mergence may not help with other transforms (Quite a few transforms are based on two branches, but not multiple branches)

Maybe it's possible to refactor TryToSimplifyUncondBranchFromEmptyBlock to implement the same thing, but it's too large and too hard for me.
I'll highly appreciate it if you have other suggestions or some knowledge about the stuff above.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6784 ↗

(On Diff #543392)

CaseBB doesn't dominate SuccBB here. Because SuccBB is a case successor of switch, SuccBB has at least two predecessors (CaseBB, Switch Block). And what dominates SuccBB should be Switch Block or other predecessors, but not CaseBB.
CaseBBs.contains(SuccBB) guarantees it.

[XChy]

• Fix the nits
• Clear the logic

[XChy]

Here is an optimized example related to the lookup table optimization in the issue in summary:
add 1

[DianQK]

You may need to run git clang-format HEAD~1.
The jump-table-islands.ll test case looks like it needs updating.

First time reviewer, please let me know if anything is wrong.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6206 ↗

(On Diff #543634)

Unnecessary debugging logs?

6758 ↗

(On Diff #543634)

SuccBB looks like it could be a parameter?

6775 ↗

(On Diff #543634)

Performing this check first may reduce unnecessary CasePredBBs updates?

6781 ↗

(On Diff #543634)

Does it make sense to use a Changed variable to update multiple Cases at once?

[DianQK]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6762 ↗

(On Diff #543634)

Can these checks be used to create a small enough CaseBBs at MergePhisInSwitch?

[XChy]

• Fix the nits
• Change the order of checks to increase efficiency.

jump-table-islands.ll belongs to ARM's CodeGen test and it seems to be handwritten. Could anyone familiar with it suggest me how to update it?

[XChy]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6758 ↗

(On Diff #543634)

Sure.

6762 ↗

(On Diff #543634)

I don't think it's necessary to create a small enough CaseBBs here. Instead, CaseBBs should include the successors of all cases, in order to guarantee correct checks like All predecessors of CaseBB is also the successor of one case. SuccBB is the successor of one case.

6775 ↗

(On Diff #543634)

Thanks. That's more efficient

6781 ↗

(On Diff #543634)

It may be much more complex to update them at once. There may be some diamond-like CFG or loops in Cases. Updating at once would bring some conflicts here.

[XChy]

Omit jump-table-islands.ll test temporarily. (Sorry, I'm not familiar with ARM and unable to update it)
Contact related committers to update if this patch is approved.

[nikic]

llvm/test/CodeGen/ARM/jump-table-islands.ll

1

You can probably avoid the test change using -arm-atomic-cfg-tidy=0.

[nikic]

Such mergence may not help with other transforms (Quite a few transforms are based on two branches, but not multiple branches)

Do you have any particular issues this could cause in mind?

I think even if we don't always perform the transform, we should still express it generically, and then have a profitability heuristic on top: E.g. say that the one common predecessor must have a switch terminator. That way we can clearly separate correctness from profitability requirements.

Edit: Just for reference, this is an example of the non-switch CFG I have in mind where such a transform should be possible: https://gist.github.com/nikic/8f22ef4e366fd3041c7e150c228f9673

[XChy]

In D155940#4538561, @nikic wrote:

Do you have any particular issues this could cause in mind?

Sure, something like FoldTwoEntryPHINode/HoistThenElseToIf may miss/delay. Or some Phi to Select may be delayed/sunk. I haven't constructed counter-examples here. (Maybe it's my intuitive fault, I actually constructed some examples optimized well).
I think the probitability can be tested by the existing testcases here. I'll try to generalize TryToSimplifyUncondBranchFromEmptyBlock to perform the tests.

I think even if we don't always perform the transform, we should still express it generically, and then have a profitability heuristic on top: E.g. say that the one common predecessor must have a switch terminator. That way we can clearly separate correctness from profitability requirements.

I agree with you. The generalization is indeed necessary. It may take some time to complete it. At that time can we determine what profitability heuristic shoud be.

Edit: Just for reference, this is an example of the non-switch CFG I have in mind where such a transform should be possible: https://gist.github.com/nikic/8f22ef4e366fd3041c7e150c228f9673

Thanks! That could serve as a testcase to be expanded/reduced.

[XChy]

Add -arm-atomic-cfg-tidy=0 option.

[XChy]

• Refactor TryToSimplifyUncondBranchFromEmptyBlock to merge phis between BB and Succ with a common predecessor. Logic correctly embedded (OK in Local tests), but not efficient currently.
• A regression found, in switch-simplify-crash2.ll. But InstCombine would solve it.
• Testcases not added now, incoming. And ARM/jump-islands-table.ll doesn't test well still.

llvm/test/CodeGen/ARM/jump-table-islands.ll

1

Fail still

[XChy]

• Add complete positive tests
• Fix bugs about preserving domtree

Enhance further possible: If BB and Succ share more than one predecessor and combine some phis meanwhile, we can also simplify CFG.
However, we are not able to erase the phi in BB completely here. Does it make sense still?
example

[XChy]

Update codesize-loop.ll

[XChy]

[Clang-format]
It seems perform correctly and well in most cases.

[XChy]

Update AArch64's codegen tests.

[XChy]

ping.

[XChy]

Remove unnecessary helper function

[DianQK]

Too much irrelevant formatting. It causes review to become complicated. It also affects other people blame related changes.
Could you ignore this formatting?

In fact, I'm not sure why. It could be that some commits are not formatted, or it could be a change in formatting rules. Or something else.
My formatting workflow is:

• Ignore all irrelevant formatting if present.
• Add and commit.
• git clang-format HEAD~1
• Since the latest submission is my own. Then I just run git add . and git clang-format HEAD~1.

And why didi stlxrb w9, w1, [x2] became stlxrb wzr, w1, [x2]?

[XChy]

Drop unnecessary formatting.

[XChy]

In D155940#4633497, @DianQK wrote:

Too much irrelevant formatting. It causes review to become complicated. It also affects other people blame related changes.
Could you ignore this formatting?

In fact, I'm not sure why. It could be that some commits are not formatted, or it could be a change in formatting rules. Or something else.
My formatting workflow is:

• Ignore all irrelevant formatting if present.
• Add and commit.
• git clang-format HEAD~1
• Since the latest submission is my own. Then I just run git add . and git clang-format HEAD~1.

Sorry for bringing irrelevant formatting, which may be caused by my incautious global formatting.
You workflow advice is highly appreicated.

And why didi stlxrb w9, w1, [x2] became stlxrb wzr, w1, [x2]?

The cause is that we remove dead PHI nodes before elimination of mostly empty blocks. Actually the up-to-date llvm-repo has implemented it. You can see details in D158503.
I would make this patch up-to-date later.

[DianQK]

I read the history of jump-table-islands.ll.
This test checks for oversized jump tables jumping over each other.
You transform changes from

end:                                              ; preds = %complex, %simple
  %val = phi i8500 [ %l, %complex ], [ -1, %simple ]
  br label %common.ret

to

end:                                              ; preds = %complex
  br label %common.ret

The test was to check disappears.
Increasing BigInt makes no sense.
Sorry I don't know how to create a friendly diff display.
You could remove -arm-atomic-cfg-tidy=0 and change the end bb to:

end:
  %val = phi %BigInt [ %l, %complex ], [ -1, %simple ]
  %val2 = add %BigInt %val, 1
  ret %BigInt %val2
}

https://reviews.llvm.org/differential/diff/555646/

I feel the SKIP_TABLE name is confusing and should be changed to CONTINUE_TABLE/ISLAND_JUMP?

[XChy]

In D155940#4636482, @DianQK wrote:

I read the history of jump-table-islands.ll.
This test checks for oversized jump tables jumping over each other.
You transform changes from

end:                                              ; preds = %complex, %simple
  %val = phi i8500 [ %l, %complex ], [ -1, %simple ]
  br label %common.ret

to

end:                                              ; preds = %complex
  br label %common.ret

The test was to check disappears.
Increasing BigInt makes no sense.
Sorry I don't know how to create a friendly diff display.
You could remove -arm-atomic-cfg-tidy=0 and change the end bb to:

end:
  %val = phi %BigInt [ %l, %complex ], [ -1, %simple ]
  %val2 = add %BigInt %val, 1
  ret %BigInt %val2
}

https://reviews.llvm.org/differential/diff/555646/

I feel the SKIP_TABLE name is confusing and should be changed to CONTINUE_TABLE/ISLAND_JUMP?

Thanks for your information and suggestions. It's OK to apply IR below to avoid related transform:

declare void @use(%BigInt)
......
end:
  %val = phi %BigInt [ %l, %complex ], [ -1, %simple ]
  call void @use(%BigInt %val)
  ret %BigInt %val

If possible, however, it would be better if there is any other available option that does not modify the original IR.

[XChy]

Insert use function into jump-table-islands.ll to avoid unrelated transform.

[DianQK]

LGTM. But before landing, you'd better request @nikic approval for this.

If possible, however, it would be better if there is any other available option that does not modify the original IR.

I don't know. The purpose of your transformation is to tweak this test case.

llvm/lib/Transforms/Utils/Local.cpp

886

Irrelevant formatting.

1004

Should clang-tidy recommend lowercase beginnings?

1149–1150

Again.

1150

Irrelevant formatting.

llvm/test/CodeGen/ARM/jump-table-islands.ll

39

“The purpose is to prevent SimplifyCFG from simplifying the phi node above.”
Would this description be better?

[XChy]

In D155940#4641865, @DianQK wrote:

LGTM. But before landing, you'd better request @nikic approval for this.

If possible, however, it would be better if there is any other available option that does not modify the original IR.

I don't know. The purpose of your transformation is to tweak this test case.

Sure, thanks for your review!

[XChy]

Reduce irrelevant formatting

[nikic]

llvm/lib/Transforms/Utils/Local.cpp

1147–1149

This sentence did not parse to me. Maybe something like this?

1151

Is it intentional that if BBKillable is true we still call CanRedirectPredsOfEmptyBBToSucc? Should this be !BBKillable &&?

1179

Why is this set no longer needed? Can no predecessors appear multiple times in this code?

1318

use -> U

[XChy]

Polish comment and fix when to print log.

[nikic]

llvm/lib/Transforms/Utils/Local.cpp

1151

In particular, what worries me here is that we set BBKillable = true, then call CanRedirectPredsOfEmptyBBToSucc() which may set CommonPred (even if the function ultimately returns false) and then various code in the following will do things differently based on CommonPred. It's not clear to me whether this will result in misbehavior or not.

(With that in mind, I think it may also be cleaner if the BBPhisMergeable flag is removed and only CommonPred left, so that CommonPred != nullptr is equivalent to BBPhisMergeable and we don't leave dangling CommonPred if CanRedirectPredsOfEmptyBBToSucc exits early.)

[XChy]

llvm/lib/Transforms/Utils/Local.cpp

1004

Yes. But I just follow the original style like CanPropagatePredecessorsForPHIs.

1147–1149

Thanks for polishing my comment.

1151

Both BBKillable || redirect() and !BBKillable && redirect() do not call CanRedirectPredsOfEmptyBBToSucc when BBKillable is true.
What is different is , that when BBKillable is true, the former BBPhisMergeable is true while the latter is false.
Actually it's logically OK, since when BBKillable is true, whether BBPhisMergeable doesn't have any impact.
I write BBKillable || redirect() based on semantic meaning : Phis are mergeable if BB can be killed.

1179

BBPreds is a SmallPtrSet, on which we would not iterate the same predecessor multiple times.

[nikic]

llvm/lib/Transforms/Utils/Local.cpp

1179

Oh, I missed that this does the updates based on SmallPtrSet now. This is not allowed, because it makes the updates non-deterministic (order matters here). You should replace SmallPtrSet with SmallSetVector to keep order deterministic.

[XChy]

Keep order when updating dom-tree.

[XChy]

llvm/lib/Transforms/Utils/Local.cpp

1151

What you're worried about make sense to me. But as far as I know, the assumption "BBKillable || redirect() will call redirect() when BBKillable is true" is wrong。

1179

Sure, restore to original codem though I don't know why order matters here. Because the algorithm for updating dom-tree?

[nikic]

LG

llvm/lib/Transforms/Utils/Local.cpp

1151

Yeah, sorry, I got confused here.

1179

The structure of the dominator tree will be the same regardless of update order, but the order of the children in the tree may be different, which can lead to optimization differences.

[XChy]

Thanks for @DianQK and @nikic! This patch will be submitted as Github PR (It seems that doc
about submitting by Phabricator has been removed).

llvm/lib/Transforms/Utils/Local.cpp

 static bool CanMergeValues(Value *First, Value *Second) {
   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
 }
 
 /// Return true if we can fold BB, an almost-empty BB ending in an unconditional
 /// branch to Succ, into Succ.
 ///
 /// Assumption: Succ is the single successor for BB.
-static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
+static bool
+CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ,
+                                const SmallPtrSetImpl<BasicBlock *> &BBPreds) {
   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
 
   LLVM_DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
                     << Succ->getName() << "\n");
   // Shortcut, if there is only a single predecessor it must be BB and merging
   // is always safe
-  if (Succ->getSinglePredecessor()) return true;
-
-  // Make a list of the predecessors of BB
-  SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
+  if (Succ->getSinglePredecessor())
+    return true;
 
   // Look at all the phi nodes in Succ, to see if they present a conflict when
   // merging these blocks
   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
     PHINode *PN = cast<PHINode>(I);
 
     // If the incoming value from BB is again a PHINode in
     // BB which has the same incoming value for *PI as PN does, we can
if (BBPN && BBPN->getParent() == BB) {
                      << "Can't fold, phi node " << PN->getName() << " in "
                      << Succ->getName() << " is conflicting with "
                      << BBPN->getName() << " with regard to common predecessor "
                      << IBB->getName() << "\n");
           return false;
         }
       }
     } else {
-      Value* Val = PN->getIncomingValueForBlock(BB);
+      Value *Val = PN->getIncomingValueForBlock(BB);
       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
         // See if the incoming value for the common predecessor is equal to the
         // one for BB, in which case this phi node will not prevent the merging
         // of the block.
         BasicBlock *IBB = PN->getIncomingBlock(PI);
         if (BBPreds.count(IBB) &&
             !CanMergeValues(Val, PN->getIncomingValue(PI))) {
           LLVM_DEBUG(dbgs() << "Can't fold, phi node " << PN->getName()
unsigned PoisonCount = count_if(TrueUndefOps, [&](unsigned i) {
     return isa<PoisonValue>(PN->getIncomingValue(i));
   });
   if (PoisonCount != 0 && PoisonCount != TrueUndefOps.size()) {
     for (unsigned i : TrueUndefOps)
       PN->setIncomingValue(i, UndefValue::get(PN->getType()));
   }
 }
 
+static bool
+CanMergeEmptyBBToSucc(BasicBlock *BB, BasicBlock *Succ,
+                      const SmallPtrSetImpl<BasicBlock *> &BBPreds) {
+  // Check to see if merging these blocks would cause conflicts for any of the
+  // phi nodes in BB or Succ. If not, we can safely merge.
+  if (!CanPropagatePredecessorsForPHIs(BB, Succ, BBPreds))
+    return false;
+
+  // Check to see if merging these blocks would cause conflicts for any of
+  // the phi nodes in BB or Succ. If not, we can safely merge.
+
+  // Check for cases where Succ has multiple predecessors and a PHI node in BB
+  // has uses which will not disappear when the PHI nodes are merged.  It is
+  // possible to handle such cases, but difficult: it requires checking whether
+  // BB dominates Succ, which is non-trivial to calculate in the case where
+  // Succ has multiple predecessors.  Also, it requires checking whether
+  // constructing the necessary self-referential PHI node doesn't introduce any
+  // conflicts; this isn't too difficult, but the previous code for doing this
+  // was incorrect.
+  //
+  // Note that if this check finds a live use, BB dominates Succ, so BB is
+  // something like a loop pre-header (or rarely, a part of an irreducible CFG);
+  // folding the branch isn't profitable in that case anyway.
+
+  if (!Succ->getSinglePredecessor()) {
+    BasicBlock::iterator BBI = BB->begin();
+    while (isa<PHINode>(*BBI)) {
+      for (Use &U : BBI->uses()) {
+        if (PHINode *PN = dyn_cast<PHINode>(U.getUser())) {
+          if (PN->getIncomingBlock(U) != BB)
+            return false;
+        } else {
+          return false;
+        }
+      }
+      ++BBI;
+    }
+  }
+
+  return true;
+}
+
+// Find the single common predecessor of BB and its single successor Succ.
+// If there are more than 1 common predecessors, set MoreThanOnePred to be true.
+static BasicBlock *
+getSingleCommonPred(const SmallPtrSetImpl<BasicBlock *> &BBPreds,
+                    const SmallPtrSetImpl<BasicBlock *> &SuccPreds) {
+  BasicBlock *Ret = nullptr;
+  for (BasicBlock *SuccPred : SuccPreds) {
+    if (BBPreds.count(SuccPred)) {
+      if (Ret)
+        return nullptr;
+
+      Ret = SuccPred;
+    }
+  }
+
+  return Ret;
+}
+
 /// Replace a value flowing from a block to a phi with
 /// potentially multiple instances of that value flowing from the
 /// block's predecessors to the phi.
 ///
 /// \param BB The block with the value flowing into the phi.
 /// \param BBPreds The predecessors of BB.
 /// \param PN The phi that we are updating.
+/// \param CommonPred The common predecessor of BB and PN's BasicBlock
 static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
                                                 const PredBlockVector &BBPreds,
-                                                PHINode *PN) {
+                                                PHINode *PN,
+                                                BasicBlock *CommonPred) {
   Value *OldVal = PN->removeIncomingValue(BB, false);
   assert(OldVal && "No entry in PHI for Pred BB!");
 
   IncomingValueMap IncomingValues;
 
   // We are merging two blocks - BB, and the block containing PN - and
   // as a result we need to redirect edges from the predecessors of BB
   // to go to the block containing PN, and update PN
if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
     PHINode *OldValPN = cast<PHINode>(OldVal);
     for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
       // Note that, since we are merging phi nodes and BB and Succ might
       // have common predecessors, we could end up with a phi node with
       // identical incoming branches. This will be cleaned up later (and
       // will trigger asserts if we try to clean it up now, without also
       // simplifying the corresponding conditional branch).
       BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
+
+      if (PredBB == CommonPred)
+        continue;
+
       Value *PredVal = OldValPN->getIncomingValue(i);
-      Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
-                                                    IncomingValues);
+      Value *Selected =
+          selectIncomingValueForBlock(PredVal, PredBB, IncomingValues);
 
       // And add a new incoming value for this predecessor for the
       // newly retargeted branch.
       PN->addIncoming(Selected, PredBB);
     }
+    if (CommonPred)
+      PN->addIncoming(OldValPN->getIncomingValueForBlock(CommonPred), BB);
+
   } else {
     for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
       // Update existing incoming values in PN for this
       // predecessor of BB.
       BasicBlock *PredBB = BBPreds[i];
-      Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
-                                                    IncomingValues);
+
+      if (PredBB == CommonPred)
+        continue;
+
+      Value *Selected =
+          selectIncomingValueForBlock(OldVal, PredBB, IncomingValues);
 
       // And add a new incoming value for this predecessor for the
       // newly retargeted branch.
       PN->addIncoming(Selected, PredBB);
     }
+    if (CommonPred)
+      PN->addIncoming(OldVal, BB);
   }
 
   replaceUndefValuesInPhi(PN, IncomingValues);
 }
 
 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
                                                    DomTreeUpdater *DTU) {
   assert(BB != &BB->getParent()->getEntryBlock() &&
          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
 
-  // We can't eliminate infinite loops.
+  // We can't simplify infinite loops.
   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
-  if (BB == Succ) return false;
+  if (BB == Succ)
+    return false;
 
-  // Check to see if merging these blocks would cause conflicts for any of the
-  // phi nodes in BB or Succ. If not, we can safely merge.
-  if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
+  SmallPtrSet<BasicBlock *, 16> BBPreds(pred_begin(BB), pred_end(BB));
+  SmallPtrSet<BasicBlock *, 16> SuccPreds(pred_begin(Succ), pred_end(Succ));
 
-  // Check for cases where Succ has multiple predecessors and a PHI node in BB
-  // has uses which will not disappear when the PHI nodes are merged.  It is
-  // possible to handle such cases, but difficult: it requires checking whether
-  // BB dominates Succ, which is non-trivial to calculate in the case where
-  // Succ has multiple predecessors.  Also, it requires checking whether
-  // constructing the necessary self-referential PHI node doesn't introduce any
-  // conflicts; this isn't too difficult, but the previous code for doing this
-  // was incorrect.
-  //
-  // Note that if this check finds a live use, BB dominates Succ, so BB is
-  // something like a loop pre-header (or rarely, a part of an irreducible CFG);
-  // folding the branch isn't profitable in that case anyway.
-  if (!Succ->getSinglePredecessor()) {
-    BasicBlock::iterator BBI = BB->begin();
-    while (isa<PHINode>(*BBI)) {
-      for (Use &U : BBI->uses()) {
-        if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
-          if (PN->getIncomingBlock(U) != BB)
-            return false;
-        } else {
-          return false;
-        }
-      }
-      ++BBI;
-    }
-  }
+  // Find the single common predecessor of BB and Succ
+  BasicBlock *CommonPred = nullptr;
+
+  bool BBKillable = CanMergeEmptyBBToSucc(BB, Succ, BBPreds);
+
+  if (!BBKillable)
+    CommonPred = getSingleCommonPred(BBPreds, SuccPreds);
+
+  bool BBPhisMergeable =
+      CommonPred && !BB->phis().empty() && !Succ->phis().empty();
+
+  if (!BBKillable && !BBPhisMergeable)
+
+  if (BBPhisMergeable)
+    LLVM_DEBUG(dbgs() << "Found Common Predecessor between: " << BB->getName()
+                      << " and " << Succ->getName() << " : "
+                      << CommonPred->getName() << "\n");
 
   // 'BB' and 'BB->Pred' are loop latches, bail out to presrve inner loop
   // metadata.
   //
   // FIXME: This is a stop-gap solution to preserve inner-loop metadata given
   // current status (that loop metadata is implemented as metadata attached to
   // the branch instruction in the loop latch block). To quote from review
   // comments, "the current representation of loop metadata (using a loop latch
bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
   // |_______|  |______|
   if (Instruction *TI = BB->getTerminator())
     if (TI->hasMetadata(LLVMContext::MD_loop))
       for (BasicBlock *Pred : predecessors(BB))
         if (Instruction *PredTI = Pred->getTerminator())
           if (PredTI->hasMetadata(LLVMContext::MD_loop))
             return false;
 
+  if (BBKillable)
     LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
+  else if (BBPhisMergeable)
+    LLVM_DEBUG(dbgs() << "Merge Phis in Trivial BB: \n" << *BB);
 
   SmallVector<DominatorTree::UpdateType, 32> Updates;
+
   if (DTU) {
     // To avoid processing the same predecessor more than once.
-    SmallPtrSet<BasicBlock *, 8> SeenPreds;
-    // All predecessors of BB will be moved to Succ.
-    SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ));
+    // All predecessors of BB (except the common predecessor) will be moved to
+    // Succ.
     Updates.reserve(Updates.size() + 2 * pred_size(BB) + 1);
-    for (auto *PredOfBB : predecessors(BB))
+
+    for (auto *PredOfBB : BBPreds)
+      Updates.push_back({DominatorTree::Delete, PredOfBB, BB});
+
+    for (auto *PredOfBB : BBPreds)
       // This predecessor of BB may already have Succ as a successor.
-      if (!PredsOfSucc.contains(PredOfBB))
-        if (SeenPreds.insert(PredOfBB).second)
-          Updates.push_back({DominatorTree::Insert, PredOfBB, Succ});
-    SeenPreds.clear();
-    for (auto *PredOfBB : predecessors(BB))
-      if (SeenPreds.insert(PredOfBB).second)
-        Updates.push_back({DominatorTree::Delete, PredOfBB, BB});
+      if (!SuccPreds.contains(PredOfBB))
+
+    if (BBKillable)
       Updates.push_back({DominatorTree::Delete, BB, Succ});
   }
 
   if (isa<PHINode>(Succ->begin())) {
     // If there is more than one pred of succ, and there are PHI nodes in
     // the successor, then we need to add incoming edges for the PHI nodes
     //
     const PredBlockVector BBPreds(predecessors(BB));
 
     // Loop over all of the PHI nodes in the successor of BB.
     for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
       PHINode *PN = cast<PHINode>(I);
 
-      redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
+      redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN, CommonPred);
     }
   }
 
   if (Succ->getSinglePredecessor()) {
     // BB is the only predecessor of Succ, so Succ will end up with exactly
     // the same predecessors BB had.
 
     // Copy over any phi, debug or lifetime instruction.
     BB->getTerminator()->eraseFromParent();
     Succ->splice(Succ->getFirstNonPHI()->getIterator(), BB);
   } else {
     while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
-      // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
+      // We explicitly check for such uses for merging phis.
       assert(PN->use_empty() && "There shouldn't be any uses here!");
       PN->eraseFromParent();
     }
   }
 
   // If the unconditional branch we replaced contains llvm.loop metadata, we
   // add the metadata to the branch instructions in the predecessors.
   if (Instruction *TI = BB->getTerminator())
     if (MDNode *LoopMD = TI->getMetadata(LLVMContext::MD_loop))
       for (BasicBlock *Pred : predecessors(BB))
         Pred->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopMD);
 
+  if (BBKillable) {
     // Everything that jumped to BB now goes to Succ.
     BB->replaceAllUsesWith(Succ);
-  if (!Succ->hasName()) Succ->takeName(BB);
+
+    if (!Succ->hasName())
+      Succ->takeName(BB);
 
     // Clear the successor list of BB to match updates applying to DTU later.
     if (BB->getTerminator())
       BB->back().eraseFromParent();
+
     new UnreachableInst(BB->getContext(), BB);
     assert(succ_empty(BB) && "The successor list of BB isn't empty before "
                              "applying corresponding DTU updates.");
+  } else if (BBPhisMergeable) {
+    //  Everything except CommonPred that jumped to BB now goes to Succ.
+    BB->replaceUsesWithIf(Succ, [BBPreds, CommonPred](Use &use) -> bool {
+      if (Instruction *UseInst = dyn_cast<Instruction>(use.getUser()))
+        return UseInst->getParent() != CommonPred &&
+               BBPreds.contains(UseInst->getParent());
+      return false;
+    });
+  }
 
   if (DTU)
     DTU->applyUpdates(Updates);
 
+  if (BBKillable)
     DeleteDeadBlock(BB, DTU);
 
   return true;
 }
 
 static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB) {
   // This implementation doesn't currently consider undef operands
   // specially. Theoretically, two phis which are identical except for
   // one having an undef where the other doesn't could be collapsed.

llvm/test/CodeGen/ARM/jump-table-islands.ll

-; RUN: llc -mtriple=armv7-apple-ios8.0 -o - %s | FileCheck %s
+; RUN: llc -arm-atomic-cfg-tidy=0 -mtriple=armv7-apple-ios8.0 -o - %s | FileCheck %s
 
 %BigInt = type i8500
 
+; FIXME: SimplifyCFG optimizes the CFG here, resulting different asm.
+; Update is needed.
 define %BigInt @test_moved_jumptable(i1 %tst, i32 %sw, %BigInt %l) {
 ; CHECK-LABEL: test_moved_jumptable:
 
 ; CHECK:   adr {{r[0-9]+}}, [[JUMP_TABLE:LJTI[0-9]+_[0-9]+]]
 ; CHECK:   b [[SKIP_TABLE:LBB[0-9]+_[0-9]+]]
 
 ; CHECK: [[JUMP_TABLE]]:
 ; CHECK:   .data_region jt32
third:
   ret %BigInt 0
 
 other:
   call void @bar()
   unreachable
 
 end:
   %val = phi %BigInt [ %l, %complex ], [ -1, %simple ]
   ret %BigInt %val
 }
 
 declare void @bar()

llvm/test/Transforms/SimplifyCFG/merge-phis-in-switch.ll

 ; CHECK-NEXT:    switch i8 [[ARG]], label [[UNREACHABLE:%.*]] [
 ; CHECK-NEXT:    i8 0, label [[CASE01:%.*]]
 ; CHECK-NEXT:    i8 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    i8 2, label [[END:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       unreachable:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       case1:
-; CHECK-NEXT:    br label [[CASE01]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case01:
-; CHECK-NEXT:    [[PHI1:%.*]] = phi i8 [ 2, [[CASE1]] ], [ 1, [[START:%.*]] ]
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[PHI2:%.*]] = phi i8 [ [[PHI1]], [[CASE01]] ], [ 3, [[START]] ]
+; CHECK-NEXT:    [[PHI2:%.*]] = phi i8 [ 3, [[START:%.*]] ], [ 2, [[CASE1]] ], [ 1, [[CASE01]] ]
 ; CHECK-NEXT:    ret i8 [[PHI2]]
 ;
 start:
   switch i8 %arg, label %unreachable [
   i8 0, label %case01
   i8 1, label %case1
   i8 2, label %end
   ]

 ; CHECK-NEXT:    i8 0, label [[CASE012:%.*]]
 ; CHECK-NEXT:    i8 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    i8 2, label [[CASE2:%.*]]
 ; CHECK-NEXT:    i8 3, label [[END:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       unreachable:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       case1:
-; CHECK-NEXT:    br label [[CASE012]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case2:
-; CHECK-NEXT:    br label [[CASE012]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case012:
-; CHECK-NEXT:    [[PHI1:%.*]] = phi i8 [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[START:%.*]] ]
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[PHI2:%.*]] = phi i8 [ [[PHI1]], [[CASE012]] ], [ 4, [[START]] ]
+; CHECK-NEXT:    [[PHI2:%.*]] = phi i8 [ 4, [[START:%.*]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[CASE012]] ]
 ; CHECK-NEXT:    ret i8 [[PHI2]]
 ;
 start:
   switch i8 %arg, label %unreachable [
   i8 0, label %case012
   i8 1, label %case1
   i8 2, label %case2
   i8 3, label %end

 ; CHECK-NEXT:    i8 0, label [[CASE012:%.*]]
 ; CHECK-NEXT:    i8 1, label [[CASE1:%.*]]
 ; CHECK-NEXT:    i8 2, label [[CASE2:%.*]]
 ; CHECK-NEXT:    i8 3, label [[END:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       unreachable:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       case1:
-; CHECK-NEXT:    br label [[CASE012]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case2:
-; CHECK-NEXT:    br label [[CASE012]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case012:
-; CHECK-NEXT:    [[PHI1_1:%.*]] = phi i8 [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[START:%.*]] ]
-; CHECK-NEXT:    [[PHI1_2:%.*]] = phi i8 [ 6, [[CASE2]] ], [ 5, [[CASE1]] ], [ 4, [[START]] ]
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[PHI2_1:%.*]] = phi i8 [ [[PHI1_1]], [[CASE012]] ], [ 4, [[START]] ]
-; CHECK-NEXT:    [[PHI2_2:%.*]] = phi i8 [ [[PHI1_1]], [[CASE012]] ], [ 5, [[START]] ]
-; CHECK-NEXT:    [[PHI2_3:%.*]] = phi i8 [ [[PHI1_2]], [[CASE012]] ], [ 3, [[START]] ]
+; CHECK-NEXT:    [[PHI2_1:%.*]] = phi i8 [ 4, [[START:%.*]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[CASE012]] ]
+; CHECK-NEXT:    [[PHI2_2:%.*]] = phi i8 [ 5, [[START]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[CASE012]] ]
+; CHECK-NEXT:    [[PHI2_3:%.*]] = phi i8 [ 3, [[START]] ], [ 6, [[CASE2]] ], [ 5, [[CASE1]] ], [ 4, [[CASE012]] ]
 ; CHECK-NEXT:    call void @use(i8 [[PHI2_1]])
 ; CHECK-NEXT:    call void @use(i8 [[PHI2_2]])
 ; CHECK-NEXT:    call void @use(i8 [[PHI2_3]])
 ; CHECK-NEXT:    ret i8 [[PHI2_1]]
 ;
 start:
   switch i8 %arg, label %unreachable [
   i8 0, label %case012

 ; CHECK-NEXT:    i8 2, label [[CASE2:%.*]]
 ; CHECK-NEXT:    i8 3, label [[CASE0123:%.*]]
 ; CHECK-NEXT:    i8 4, label [[CASE01234:%.*]]
 ; CHECK-NEXT:    i8 5, label [[END:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       unreachable:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       case0:
-; CHECK-NEXT:    br label [[CASE0123]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case1:
-; CHECK-NEXT:    br label [[CASE0123]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case2:
-; CHECK-NEXT:    br label [[CASE0123]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case0123:
-; CHECK-NEXT:    [[PHI1:%.*]] = phi i8 [ 4, [[START:%.*]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[CASE0]] ]
-; CHECK-NEXT:    br label [[CASE01234]]
+; CHECK-NEXT:    br label [[END]]
 ; CHECK:       case01234:
-; CHECK-NEXT:    [[PHI2:%.*]] = phi i8 [ [[PHI1]], [[CASE0123]] ], [ 5, [[START]] ]
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[PHI3:%.*]] = phi i8 [ [[PHI2]], [[CASE01234]] ], [ 6, [[START]] ]
+; CHECK-NEXT:    [[PHI3:%.*]] = phi i8 [ 6, [[START:%.*]] ], [ 3, [[CASE2]] ], [ 2, [[CASE1]] ], [ 1, [[CASE0]] ], [ 4, [[CASE0123]] ], [ 5, [[CASE01234]] ]
 ; CHECK-NEXT:    ret i8 [[PHI3]]
 ;
 start:
   switch i8 %arg, label %unreachable [
   i8 0, label %case0
   i8 1, label %case1
   i8 2, label %case2
   i8 3, label %case0123

 ; CHECK-NEXT:    i8 3, label [[CASE3:%.*]]
 ; CHECK-NEXT:    i8 4, label [[CASE4:%.*]]
 ; CHECK-NEXT:    i8 5, label [[CASE345:%.*]]
 ; CHECK-NEXT:    i8 6, label [[CASE0123456:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       unreachable:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       case0:
-; CHECK-NEXT:    br label [[CASE012]]
+; CHECK-NEXT:    br label [[CASE0123456]]
 ; CHECK:       case1:
-; CHECK-NEXT:    br label [[CASE012]]
+; CHECK-NEXT:    br label [[CASE0123456]]
 ; CHECK:       case012:
-; CHECK-NEXT:    [[PHI123:%.*]] = phi i8 [ 3, [[START:%.*]] ], [ 2, [[CASE1]] ], [ 1, [[CASE0]] ]
 ; CHECK-NEXT:    br label [[CASE0123456]]
 ; CHECK:       case3:
-; CHECK-NEXT:    br label [[CASE345]]
+; CHECK-NEXT:    br label [[CASE0123456]]
 ; CHECK:       case4:
-; CHECK-NEXT:    br label [[CASE345]]
+; CHECK-NEXT:    br label [[CASE0123456]]
 ; CHECK:       case345:
-; CHECK-NEXT:    [[PHI456:%.*]] = phi i8 [ 6, [[START]] ], [ 5, [[CASE4]] ], [ 4, [[CASE3]] ]
 ; CHECK-NEXT:    br label [[CASE0123456]]
 ; CHECK:       case0123456:
-; CHECK-NEXT:    [[PHI1234567:%.*]] = phi i8 [ 7, [[START]] ], [ [[PHI456]], [[CASE345]] ], [ [[PHI123]], [[CASE012]] ]
+; CHECK-NEXT:    [[PHI1234567:%.*]] = phi i8 [ 7, [[START:%.*]] ], [ 2, [[CASE1]] ], [ 1, [[CASE0]] ], [ 3, [[CASE012]] ], [ 5, [[CASE4]] ], [ 4, [[CASE3]] ], [ 6, [[CASE345]] ]
 ; CHECK-NEXT:    ret i8 [[PHI1234567]]
 ;
 start:
   switch i8 %arg, label %unreachable [
   i8 0, label %case0
   i8 1, label %case1
   i8 2, label %case012
   i8 3, label %case3

llvm/test/Transforms/SimplifyCFG/switch-simplify-crash2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes="simplifycfg<forward-switch-cond;no-keep-loops>" < %s | FileCheck %s
 
 define i8 @test() {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
+; CHECK-NEXT:    [[PHI2:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[SPEC_SELECT:%.*]], [[LOOP2]] ]
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i8 [[PHI2]], 0
+; CHECK-NEXT:    [[SPEC_SELECT]] = select i1 [[COND]], i8 0, i8 [[PHI2]]
 ; CHECK-NEXT:    br label [[LOOP2]]
 ;
 entry:
   br label %loop
 
 loop:
   %phi1 = phi i8 [ 0, %entry ], [ %phi2, %loop2 ]
   br label %loop2