[StructurizeCFG] Improve basic block ordering

[bcahoon]

Summary

StructurizeCFG linearizes the successors of branching basic block
by adding Flow blocks to record the true/false path for branches
and back edges. This patch reduces the number of Phi values needed
to capture the control flow path by improving the basic block
ordering.

Previously, StructurizeCFG adds loop exit blocks outside of the
loop. StructurizeCFG sets a boolean value to indicate the path
taken, and all exit block live values extend to after the loop.
For loops with a large number of exits blocks, this creates a
huge number of values that are maintained, which increases
compilation time and register pressure. This is problem
especially with ASAN, which adds early exits to basic blocks with
unreachable instructions for each instrumented check in the loop.

In specific cases, this patch reduces the number of values needed
after loop by moving the exit block to the loop. This is done
for blocks that have a single predecessor and single successor by
moving the block to appear just after the predecessor.

[sameerds]

Needs more reviewers ... I would suggest authors of previous non-trivial changes to the structurizer, and their reviewers.

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

454–456

Lots of questions because the structurizer itself is so under-specified:

1. Seems like a block can be moved multiple times until it "floats" to its final place. Is this movement monotonic?
2. Can you please add a comment explaining the criterion in terms of the "Visited" state of the Structurizer itself?
3. Are there invariants about MoveTo and Moved that we could assert in each of the two for loops?
4. What happens when MoveTo[X] == MoveTo[Y]?

[foad]

I'm being picky about the description because I'd really like to understand it clearly before reading the code.

This patch reduces the of Phi values needed

"the number of Phi values"

This is problem
especially with ASAN, which adds early exits to unreachable
blocks for each instrumented check in the loop.

I don't understand what "unreachable" refers to here.

In specific cases, this patch reduces the number of values needed
after loop by moving the exit block to the loop.

I think "into the loop" would be clearer if that's what you mean.

[sameerds]

In D123231#3445000, @foad wrote:

In specific cases, this patch reduces the number of values needed
after loop by moving the exit block to the loop.

I think "into the loop" would be clearer if that's what you mean.

Good points, all of them. Additionally, note that loops are different before and after structurization. So moving an exit block into a loop is not as crazy as it seems at first glance!

[ruiling]

which increases compilation time and register pressure.

Have you looked at which part is responsible for the compilation time increase? Is is possible that we hit inefficiency in certain pass?
The "register pressure" here specifically means SGPR usage, right?

I don't think it is a good idea to move exist blocks into the loop especially when threads in a wave exit the loop in different iterations. Executing the exit block after loop should benefit for runtime performance.

[sameerds]

In D123231#3445997, @ruiling wrote:

which increases compilation time and register pressure.

Have you looked at which part is responsible for the compilation time increase? Is is possible that we hit inefficiency in certain pass?
The "register pressure" here specifically means SGPR usage, right?

I don't think it is a good idea to move exist blocks into the loop especially when threads in a wave exit the loop in different iterations. Executing the exit block after loop should benefit for runtime performance.

We do know exactly why we need this patch, which is for the address sanitizer. Performance is not an issue when asan is ON. Then one safe way forward could be to hide this patch behind a new command-line option, which is turned on by default when asan is enabled. The new option will also allow us to separately investigate impact on important workloads before we make any call on enabling it by default with or without asan.

[bcahoon]

Made several changes based upon suggestions and to fix a correctness issue:

• The new function, reorderNodes, must appear before collectInfos because collectInfos collects branch predicate information based upon the order of the nodes, so the wrong branch information was used after nodes were reordered.
• Changed name of the function, from improveNodeOrder to reorderNodes because changing the order is an improvement under certain conditions.
• Only reorder the nodes for large regions. The size of the region can be changed with a command-line option. The issues fixed by this patch are seen only with very large regions, so this flag limits the impact of this patch. I'm open to other ways to do this.
• Since reorderNodes appears before collectInfos, it no longer can use Visited. Instead, reorderNodes keeps track of the basic blocks in Order and uses that as part of the criteria to reorder. We only want to reorder a node that has a predecessor in Order.

[bcahoon]

In D123231#3450908, @sameerds wrote:

In D123231#3445997, @ruiling wrote:

which increases compilation time and register pressure.

Have you looked at which part is responsible for the compilation time increase? Is is possible that we hit inefficiency in certain pass?
The "register pressure" here specifically means SGPR usage, right?

Yes, the register pressure is SGPR usage. In large regions with a large number of loop exit blocks, a common case when ASAN is enabled, StrucuturizeCFG creates an ordering that creates a very large number of values that are live across the loop, e.g. to capture the control flow path.

I don't think it is a good idea to move exist blocks into the loop especially when threads in a wave exit the loop in different iterations. Executing the exit block after loop should benefit for runtime performance.

We do know exactly why we need this patch, which is for the address sanitizer. Performance is not an issue when asan is ON. Then one safe way forward could be to hide this patch behind a new command-line option, which is turned on by default when asan is enabled. The new option will also allow us to separately investigate impact on important workloads before we make any call on enabling it by default with or without asan.

I added an option to limit when the nodes are reordered. I plan to do some testing with the nodes are always reordered just to see the impact. Open to other ways to implement this, such as your suggestion.

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

454–456

A block is moved only once. It will move to just after its predecessor. However, the predecessor may have multiple successors. Only one of the successors will move, if there are multiple successors that meet the critertia (a single predecessor in the Order list, and a single successor that is the region exit block).

Visited is no longer used in reorderNodes. But, we still need to seen track of the blocks in the region that are in Order. We only want to move a block if it's predecessor is in Order. Otherwise, it's not obvious that moving it will be valid.

Still working on a simple invariant to check w.r.t MoveTo and Moved. MoveTo[X] != MoveTo[Y] because an basic block that is in MoveTo has only a single predecessor, either X or Y.

[bcahoon]

No changes with this patch. It's been a while since this patch was added. I was investigating an internal test failure, which turns out to be unrelated to this patch. So, I'd like to move forward with reviewing this again.

[sameerds]

The change itself looks okay to me, to the extent that it does not seem to break the structurizer. Just by putting nodes in the right order, it is still able to generate predicates that preserve the original control flow. I think that's good enough to boldly make this change. I do have some comments/questions about the tests.

llvm/test/Transforms/StructurizeCFG/improve-order.ll

6

What happens when an edge exits a loop nest? Do we need a test for that?

11

Would be very useful to have comments that indicate which blocks to look out for in each test, and where do they end up. For example, in this first function, B and D are exit blocks from A and C respectively. Flow and Flow1 form the diamond pattern around them. Without this change, this whole pattern would be outside the loop, but now it is inside. The structurizer automatically sets up predicates so that B and D are not actually executed as part of the loop, but only when it's time to exit. Is that correct?

65

To maintain convention, this should be PredC?

193

Or in particular, the successor is not outside the region, right?

272

I am not sure what this means by "multiple common successors". Was unable to spot that in the input LLVM IR. Does this refer to a structurized output without the modifications in this change?

429

Would it be wrong to say that this case is too simple because there is no loop involved? Is there a use-case where reordering is beneficial without a loop?

[ruiling]

I had tried a different approach to avoid inserting excessive number of boolean values during the loop-exit-unify in D127831. I just did some testing of that change against the LLVM IR Brendon shared with me. It shows the change could help reducing the number of registers as well as compile time. But it is sad that I still hit the error: "unhandled SGPR spill to memory" from SGPRSpillBuilder in SIRegisterInfo.cpp. Can the limitation be fixed? I did some register pressure comparison, seems the way I proposed would use much less VGPR than (D123230 + D123231), but use more SGPR. I haven't looked further why there is such behavior difference. I think we need more investigation to know why. But looks like D127831 might help us generate better code because we can use one VGPR as the backup storage for spilling of 64/32 SGPRs. And the idea used there is much easy to follow.

[bcahoon]

Updates to the comments in the improve-order.ll test, based up reviewer suggestions.

[bcahoon]

llvm/test/Transforms/StructurizeCFG/improve-order.ll

6

Yes, it's the next test called reorder_inner_loop.

11

I've added comments that provide more information, based upon your suggestions. You are correct that, without this change exit blocks appear after the loop because they are dependent on the Flow block that contains the back edge for the loop (and maybe a series of dependent Flow edges). And, yes, the structurizer sets up predicates so that B and D are not actually executed, unless the exit occurs.

65

I changed this and other similar occurrences.

193

That's correct. I added that to the comment below.

272

This test contains more exit blocks. Also, blocks J and K are created that branch to a common block. Basically, a level of indirection that doesn't occur in the other tests.

429

I doubt the reordering is beneficial without a loop. There isn't an easy way to check for a loop in StructurizeCFG, so reorderNodes may change the order even if there isn't a loop. The patch just looks for a simple pattern, when a block has a single predecessor and a single successor. But, that causes the blocks to be reordered in this test. To stop that, the check to reorder also looks for a successor that exits the region.

[bcahoon]

In D123231#3584389, @ruiling wrote:

I had tried a different approach to avoid inserting excessive number of boolean values during the loop-exit-unify in D127831. I just did some testing of that change against the LLVM IR Brendon shared with me. It shows the change could help reducing the number of registers as well as compile time. But it is sad that I still hit the error: "unhandled SGPR spill to memory" from SGPRSpillBuilder in SIRegisterInfo.cpp. Can the limitation be fixed? I did some register pressure comparison, seems the way I proposed would use much less VGPR than (D123230 + D123231), but use more SGPR. I haven't looked further why there is such behavior difference. I think we need more investigation to know why. But looks like D127831 might help us generate better code because we can use one VGPR as the backup storage for spilling of 64/32 SGPRs. And the idea used there is much easy to follow.

I tried your approach and it does improve compile-time, but I also see the register allocation error in another test. I'm not sure when that register allocation error will be fixed. But, it's surprising that it occurs because I do see register pressions improvements with your patch.

[sameerds]

In D123231#3584389, @ruiling wrote:

I had tried a different approach to avoid inserting excessive number of boolean values during the loop-exit-unify in D127831. I just did some testing of that change against the LLVM IR Brendon shared with me. It shows the change could help reducing the number of registers as well as compile time. But it is sad that I still hit the error: "unhandled SGPR spill to memory" from SGPRSpillBuilder in SIRegisterInfo.cpp. Can the limitation be fixed? I did some register pressure comparison, seems the way I proposed would use much less VGPR than (D123230 + D123231), but use more SGPR. I haven't looked further why there is such behavior difference. I think we need more investigation to know why. But looks like D127831 might help us generate better code because we can use one VGPR as the backup storage for spilling of 64/32 SGPRs. And the idea used there is much easy to follow.

Is there any dependency before submitting the current patch?

[ruiling]

The issue @critson reported in the related change reminds to take a careful look of this change. I think there is one critical correctness issue need to be fixed. When we are moving the exit block into the loop, we need to make sure there is no convergent operation in the exit block, otherwise we may change the threads that will participate the convergent operation if the threads exit the loop non-uniformly. So we have to scan all the instructions in the exit block before making the reorder decision. Another thing I just noticed is the existing implementation does not actually check it is moving loop/SCC exits. It also tries to reorder the blocks for an ordinary if-else region, which is really unnecessary. Now that we need to scan all the instructions to check against convergent operations, I think we need to make sure we are only scanning the loop-exits. To achieve this, I think you can remember the blocks of each SCC in StructurizeCFG::orderNodes(), and when you try to check whether it needs reorder, please make sure its single predecessor is inside an SCC but the block itself is not. I hope the threshold value check applies to both number of blocks in SCC as well as the number of exits. Apply the threshold value to number of blocks in SCC just helps us filter out loops that we don't need to care early. Checking the number of region nodes sounds not strong enough, even we have a large loop, we still don't want to move the loop exits into the loop unless it has lots of exits.

[bcahoon]

In D123231#3611240, @ruiling wrote:

The issue @critson reported in the related change reminds to take a careful look of this change. I think there is one critical correctness issue need to be fixed. When we are moving the exit block into the loop, we need to make sure there is no convergent operation in the exit block, otherwise we may change the threads that will participate the convergent operation if the threads exit the loop non-uniformly. So we have to scan all the instructions in the exit block before making the reorder decision.

Hi @ruiling can you expand upon this a little bit since I'm not sure I understand. The exit block isn't part of the loop after the transformation, meaning that it's not executed as part of the loop. The block appears in the control flow after the exiting block. It's only executed if the loop exits. There shouldn't be any change in blocks executed with this patch.

Another thing I just noticed is the existing implementation does not actually check it is moving loop/SCC exits. It also tries to reorder the blocks for an ordinary if-else region, which is really unnecessary. Now that we need to scan all the instructions to check against convergent operations, I think we need to make sure we are only scanning the loop-exits. To achieve this, I think you can remember the blocks of each SCC in StructurizeCFG::orderNodes(), and when you try to check whether it needs reorder, please make sure its single predecessor is inside an SCC but the block itself is not.

You're correct that the code doesn't check for a loop and will try to reorder the blocks for ordinary if-then-else sequences. My thinking was that it wouldn't be worth keeping track of which blocks are in each SCC since the situation of reordering the if-then-else regions seemed to occur infrequently given the other constraints for reordering. But, I can add that functionality.

I hope the threshold value check applies to both number of blocks in SCC as well as the number of exits. Apply the threshold value to number of blocks in SCC just helps us filter out loops that we don't need to care early. Checking the number of region nodes sounds not strong enough, even we have a large loop, we still don't want to move the loop exits into the loop unless it has lots of exits.

Sure, I think that's reasonable to check for loops with a large number of exits. I can create a patch that keeps track of the region exits and uses that metric instead.

[ruiling]

In D123231#3613586, @bcahoon wrote:

In D123231#3611240, @ruiling wrote:

The issue @critson reported in the related change reminds to take a careful look of this change. I think there is one critical correctness issue need to be fixed. When we are moving the exit block into the loop, we need to make sure there is no convergent operation in the exit block, otherwise we may change the threads that will participate the convergent operation if the threads exit the loop non-uniformly. So we have to scan all the instructions in the exit block before making the reorder decision.

Hi @ruiling can you expand upon this a little bit since I'm not sure I understand. The exit block isn't part of the loop after the transformation, meaning that it's not executed as part of the loop. The block appears in the control flow after the exiting block. It's only executed if the loop exits. There shouldn't be any change in blocks executed with this patch.

I think by placing the loop-exit after loop exiting, the structurizer will wire the loop-exit inside the loop. I have add some note based on one lit test to explain the divergent loop exits case, hope it would help.

llvm/test/Transforms/StructurizeCFG/improve-order.ll

10

For this example, the block B and D are loop exits. Before this change, they are placed outside of the loop after structurization, so they will only start executing after all the threads in a wave exit the loop. But with this change, they appear inside the loop after structurization. By putting the exits inside the loop, if part of the threads in a wave exit the loop into B, then these threads will start executing B while other threads continue executing the blocks that have been inside the thread-level loop before structurization. This basically describe the wave execution when loop exit condition is divergent. Before this change, the loop-exits will only be executed once after all the threads exit the loop.

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

static cl::opt<bool> ForceSkipUniformRegions(
   cl::desc("Force whether the StructurizeCFG pass skips uniform regions"),
   cl::init(false));
 
 static cl::opt<bool>
     RelaxedUniformRegions("structurizecfg-relaxed-uniform-regions", cl::Hidden,
                           cl::desc("Allow relaxed uniform region checks"),
                           cl::init(true));
 
+static cl::opt<unsigned>
+    ReorderNodeSize("structurizecfg-node-reorder-size",
+                     cl::desc("Limit region size for reordering nodes"),
+                     cl::init(100), cl::Hidden);
+
 // Definition of the complex types used in this pass.
 
 using BBValuePair = std::pair<BasicBlock *, Value *>;
 
 using RNVector = SmallVector<RegionNode *, 8>;
 using BBVector = SmallVector<BasicBlock *, 8>;
 using BranchVector = SmallVector<BranchInst *, 8>;
 using BBValueVector = SmallVector<BBValuePair, 2>;
class StructurizeCFG {
   BB2BBMap Loops;
   PredMap LoopPreds;
   BranchVector LoopConds;
 
   RegionNode *PrevNode;
 
   void orderNodes();
 
+  void reorderNodes();
+
   void analyzeLoops(RegionNode *N);
 
   Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert);
 
   void gatherPredicates(RegionNode *N);
 
   void collectInfos();
 
while (true) {
     Nodes.insert(Order.begin() + I, Order.begin() + E - 1);
 
     // Update the entry node.
     EntryNode.first = Order[E - 1];
     EntryNode.second = &Nodes;
   }
 }
 
+/// Change the node ordering to decrease the range of live values, especially
+/// the values that capture the control flow path for branches. We do this
+/// by moving blocks with a single predecessor and successor to appear after
+/// predecessor. The motivation is to move some loop exit blocks into a loop.
+/// In cases where a loop has a large number of exit blocks, this reduces the
+/// amount of values needed across the loop boundary.
+void StructurizeCFG::reorderNodes() {
+  SmallVector<RegionNode *, 8> NewOrder;
+  DenseMap<BasicBlock *, unsigned> MoveTo;
+  BitVector Moved(Order.size());
+
+  // The benefits of reordering nodes occurs for large regions.
+  if (Order.size() <= ReorderNodeSize)
+    return;
+
+  // The algorithm works with two passes over Order. The first pass identifies
+  // the blocks to move and the position to move them to. The second pass
+  // creates the new order based upon this information. We move blocks with
+  // a single predecessor and successor. If there are multiple candidates then
+  // maintain the original order.
+  BBSet Seen;
+  for (int I = Order.size() - 1; I >= 0; --I) {
+    auto *BB = Order[I]->getEntry();
+    Seen.insert(BB);
+    auto *Pred = BB->getSinglePredecessor();
+    auto *Succ = BB->getSingleSuccessor();
+    // Consider only those basic blocks that have a predecessor in Order and a
+    // successor that exits the region. The region may contain subregions that
+    // have been structurized and are not included in Order.
+    if (Pred && Succ && Seen.count(Pred) && Succ == ParentRegion->getExit() &&
+        !MoveTo.count(Pred)) {
+      MoveTo[Pred] = I;
+      Moved.set(I);
+    }
+  }
+
+  // If no blocks have been moved then the original order is good.
+  if (!Moved.count())
+    return;
+
+  for (size_t I = 0, E = Order.size(); I < E; ++I) {
+    auto *BB = Order[I]->getEntry();
+    if (MoveTo.count(BB))
+      NewOrder.push_back(Order[MoveTo[BB]]);
+    if (!Moved[I])
+      NewOrder.push_back(Order[I]);
+  }
+
+  Order.assign(NewOrder);
+}
+
 /// Determine the end of the loops
 void StructurizeCFG::analyzeLoops(RegionNode *N) {
   if (N->isSubRegion()) {
     // Test for exit as back edge
     BasicBlock *Exit = N->getNodeAs<Region>()->getExit();
     if (Visited.count(Exit))
       Loops[Exit] = N->getEntry();
 
if (R->isTopLevelRegion())
     return false;
 
   this->DT = DT;
 
   Func = R->getEntry()->getParent();
   ParentRegion = R;
 
   orderNodes();
+  reorderNodes();
   collectInfos();
   createFlow();
   insertConditions(false);
   insertConditions(true);
   setPhiValues();
   simplifyConditions();
   simplifyAffectedPhis();
   rebuildSSA();

llvm/test/CodeGen/AMDGPU/nested-loop-conditions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: opt -mtriple=amdgcn-- -S -structurizecfg -si-annotate-control-flow %s | FileCheck -check-prefix=IR %s
 ; RUN: llc -march=amdgcn -mcpu=hawaii -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
 
 ; After structurizing, there are 3 levels of loops. The i1 phi
 ; conditions mutually depend on each other, so it isn't safe to delete
 ; the condition that appears to have no uses until the loop is
 ; completely processed.
 

 ; GCN-NEXT:  .LBB0_6: ; %bb9
 ; GCN-NEXT:    ; =>This Inner Loop Header: Depth=1
 ; GCN-NEXT:    s_mov_b64 vcc, vcc
 ; GCN-NEXT:    s_cbranch_vccz .LBB0_6
 ; GCN-NEXT:  .LBB0_7: ; %DummyReturnBlock
 ; GCN-NEXT:    s_endpgm
 ; IR-LABEL: @reduced_nested_loop_conditions(
 ; IR-NEXT:  bb:
-; IR-NEXT:    [[MY_TMP:%.*]] = tail call i32 @llvm.amdgcn.workitem.id.x() #4
+; IR-NEXT:    [[MY_TMP:%.*]] = tail call i32 @llvm.amdgcn.workitem.id.x() #[[ATTR4:[0-9]+]]
 ; IR-NEXT:    [[MY_TMP1:%.*]] = getelementptr inbounds i64, i64 addrspace(3)* [[ARG:%.*]], i32 [[MY_TMP]]
-; IR-NEXT:    [[MY_TMP2:%.*]] = load volatile i64, i64 addrspace(3)* [[MY_TMP1]]
+; IR-NEXT:    [[MY_TMP2:%.*]] = load volatile i64, i64 addrspace(3)* [[MY_TMP1]], align 4
 ; IR-NEXT:    br label [[BB5:%.*]]
 ; IR:       bb3:
 ; IR-NEXT:    br i1 true, label [[BB4:%.*]], label [[BB13:%.*]]
 ; IR:       bb4:
 ; IR-NEXT:    br label [[FLOW:%.*]]
 ; IR:       bb5:
 ; IR-NEXT:    [[PHI_BROKEN:%.*]] = phi i64 [ [[TMP6:%.*]], [[BB10:%.*]] ], [ 0, [[BB:%.*]] ]
 ; IR-NEXT:    [[MY_TMP6:%.*]] = phi i32 [ 0, [[BB]] ], [ [[TMP5:%.*]], [[BB10]] ]

 ; IR-NEXT:    br label [[BB10]]
 ; IR:       bb13:
 ; IR-NEXT:    [[MY_TMP14:%.*]] = phi i1 [ [[MY_TMP22]], [[BB3]] ], [ true, [[BB8]] ]
 ; IR-NEXT:    [[MY_TMP15:%.*]] = bitcast i64 [[MY_TMP2]] to <2 x i32>
 ; IR-NEXT:    br i1 [[MY_TMP14]], label [[BB16:%.*]], label [[BB20:%.*]]
 ; IR:       bb16:
 ; IR-NEXT:    [[MY_TMP17:%.*]] = extractelement <2 x i32> [[MY_TMP15]], i64 1
 ; IR-NEXT:    [[MY_TMP18:%.*]] = getelementptr inbounds i32, i32 addrspace(3)* undef, i32 [[MY_TMP17]]
-; IR-NEXT:    [[MY_TMP19:%.*]] = load volatile i32, i32 addrspace(3)* [[MY_TMP18]]
+; IR-NEXT:    [[MY_TMP19:%.*]] = load volatile i32, i32 addrspace(3)* [[MY_TMP18]], align 4
 ; IR-NEXT:    br label [[BB20]]
 ; IR:       bb20:
 ; IR-NEXT:    [[MY_TMP21]] = phi i32 [ [[MY_TMP19]], [[BB16]] ], [ 0, [[BB13]] ]
 ; IR-NEXT:    [[MY_TMP22]] = phi i1 [ false, [[BB16]] ], [ [[MY_TMP14]], [[BB13]] ]
 ; IR-NEXT:    br label [[BB9]]
 ; IR:       bb23:
 ; IR-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP6]])
 ; IR-NEXT:    ret void
+;
 bb:
   %my.tmp = tail call i32 @llvm.amdgcn.workitem.id.x() #1
   %my.tmp1 = getelementptr inbounds i64, i64 addrspace(3)* %arg, i32 %my.tmp
   %my.tmp2 = load volatile i64, i64 addrspace(3)* %my.tmp1
   br label %bb5
 
 bb3:                                              ; preds = %bb9
   br i1 true, label %bb4, label %bb13

 ; GCN-NEXT:    s_branch .LBB1_2
 ; GCN-NEXT:  .LBB1_6: ; %bb31
 ; GCN-NEXT:    v_mov_b32_e32 v0, 0
 ; GCN-NEXT:    buffer_store_dword v0, off, s[0:3], 0
 ; GCN-NEXT:    s_waitcnt vmcnt(0)
 ; GCN-NEXT:    s_endpgm
 ; IR-LABEL: @nested_loop_conditions(
 ; IR-NEXT:  bb:
-; IR-NEXT:    [[MY_TMP:%.*]] = tail call i32 @llvm.amdgcn.workitem.id.x() #4
+; IR-NEXT:    [[MY_TMP:%.*]] = tail call i32 @llvm.amdgcn.workitem.id.x() #[[ATTR4]]
 ; IR-NEXT:    [[MY_TMP1:%.*]] = zext i32 [[MY_TMP]] to i64
 ; IR-NEXT:    [[MY_TMP2:%.*]] = getelementptr inbounds i64, i64 addrspace(1)* [[ARG:%.*]], i64 [[MY_TMP1]]
 ; IR-NEXT:    [[MY_TMP3:%.*]] = load i64, i64 addrspace(1)* [[MY_TMP2]], align 16
 ; IR-NEXT:    [[MY_TMP932:%.*]] = load <4 x i32>, <4 x i32> addrspace(1)* undef, align 16
 ; IR-NEXT:    [[MY_TMP1033:%.*]] = extractelement <4 x i32> [[MY_TMP932]], i64 0
-; IR-NEXT:    [[MY_TMP1134:%.*]] = load volatile i32, i32 addrspace(1)* undef
+; IR-NEXT:    [[MY_TMP1134:%.*]] = load volatile i32, i32 addrspace(1)* undef, align 4
 ; IR-NEXT:    [[MY_TMP1235:%.*]] = icmp slt i32 [[MY_TMP1134]], 9
 ; IR-NEXT:    br i1 [[MY_TMP1235]], label [[BB14_LR_PH:%.*]], label [[FLOW:%.*]]
 ; IR:       bb14.lr.ph:
 ; IR-NEXT:    br label [[BB14:%.*]]
 ; IR:       Flow3:
-; IR-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP21:%.*]])
+; IR-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP20:%.*]])
 ; IR-NEXT:    [[TMP0:%.*]] = call { i1, i64 } @llvm.amdgcn.if.i64(i1 [[TMP14:%.*]])
 ; IR-NEXT:    [[TMP1:%.*]] = extractvalue { i1, i64 } [[TMP0]], 0
 ; IR-NEXT:    [[TMP2:%.*]] = extractvalue { i1, i64 } [[TMP0]], 1
 ; IR-NEXT:    br i1 [[TMP1]], label [[BB4_BB13_CRIT_EDGE:%.*]], label [[FLOW4:%.*]]
 ; IR:       bb4.bb13_crit_edge:
 ; IR-NEXT:    br label [[FLOW4]]
 ; IR:       Flow4:
 ; IR-NEXT:    [[TMP3:%.*]] = phi i1 [ true, [[BB4_BB13_CRIT_EDGE]] ], [ false, [[FLOW3:%.*]] ]

 ; IR-NEXT:    [[TMP13:%.*]] = phi i1 [ [[MY_TMP12:%.*]], [[BB21]] ], [ true, [[BB14]] ]
 ; IR-NEXT:    [[TMP14]] = phi i1 [ [[MY_TMP12]], [[BB21]] ], [ false, [[BB14]] ]
 ; IR-NEXT:    [[TMP15:%.*]] = phi i1 [ false, [[BB21]] ], [ true, [[BB14]] ]
 ; IR-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP10]])
 ; IR-NEXT:    [[TMP16]] = call i64 @llvm.amdgcn.if.break.i64(i1 [[TMP13]], i64 [[PHI_BROKEN]])
 ; IR-NEXT:    [[TMP17:%.*]] = call i1 @llvm.amdgcn.loop.i64(i64 [[TMP16]])
 ; IR-NEXT:    br i1 [[TMP17]], label [[FLOW2:%.*]], label [[BB14]]
 ; IR:       bb18:
-; IR-NEXT:    [[MY_TMP19:%.*]] = load volatile i32, i32 addrspace(1)* undef
+; IR-NEXT:    [[MY_TMP19:%.*]] = load volatile i32, i32 addrspace(1)* undef, align 4
 ; IR-NEXT:    [[MY_TMP20:%.*]] = icmp slt i32 [[MY_TMP19]], 9
 ; IR-NEXT:    br i1 [[MY_TMP20]], label [[BB21]], label [[BB18]]
 ; IR:       bb21:
 ; IR-NEXT:    [[MY_TMP22:%.*]] = extractelement <2 x i32> [[MY_TMP17]], i64 1
 ; IR-NEXT:    [[MY_TMP23:%.*]] = lshr i32 [[MY_TMP22]], 16
 ; IR-NEXT:    [[MY_TMP24:%.*]] = select i1 undef, i32 undef, i32 [[MY_TMP23]]
 ; IR-NEXT:    [[MY_TMP25:%.*]] = uitofp i32 [[MY_TMP24]] to float
 ; IR-NEXT:    [[MY_TMP26:%.*]] = fmul float [[MY_TMP25]], 0x3EF0001000000000
 ; IR-NEXT:    [[MY_TMP27:%.*]] = fsub float [[MY_TMP26]], undef
 ; IR-NEXT:    [[MY_TMP28:%.*]] = fcmp olt float [[MY_TMP27]], 5.000000e-01
 ; IR-NEXT:    [[MY_TMP29:%.*]] = select i1 [[MY_TMP28]], i64 1, i64 2
 ; IR-NEXT:    [[MY_TMP30:%.*]] = extractelement <4 x i32> [[MY_TMP936]], i64 [[MY_TMP29]]
 ; IR-NEXT:    [[MY_TMP7:%.*]] = zext i32 [[MY_TMP30]] to i64
 ; IR-NEXT:    [[MY_TMP8:%.*]] = getelementptr inbounds <4 x i32>, <4 x i32> addrspace(1)* undef, i64 [[MY_TMP7]]
 ; IR-NEXT:    [[MY_TMP9]] = load <4 x i32>, <4 x i32> addrspace(1)* [[MY_TMP8]], align 16
 ; IR-NEXT:    [[MY_TMP10]] = extractelement <4 x i32> [[MY_TMP9]], i64 0
-; IR-NEXT:    [[MY_TMP11:%.*]] = load volatile i32, i32 addrspace(1)* undef
+; IR-NEXT:    [[MY_TMP11:%.*]] = load volatile i32, i32 addrspace(1)* undef, align 4
 ; IR-NEXT:    [[MY_TMP12]] = icmp sge i32 [[MY_TMP11]], 9
 ; IR-NEXT:    br label [[FLOW1]]
 ; IR:       Flow2:
 ; IR-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP16]])
-; IR-NEXT:    [[TMP19:%.*]] = call { i1, i64 } @llvm.amdgcn.if.i64(i1 [[TMP15]])
-; IR-NEXT:    [[TMP20:%.*]] = extractvalue { i1, i64 } [[TMP19]], 0
-; IR-NEXT:    [[TMP21]] = extractvalue { i1, i64 } [[TMP19]], 1
-; IR-NEXT:    br i1 [[TMP20]], label [[BB31_LOOPEXIT:%.*]], label [[FLOW3]]
+; IR-NEXT:    [[TMP18:%.*]] = call { i1, i64 } @llvm.amdgcn.if.i64(i1 [[TMP15]])
+; IR-NEXT:    [[TMP19:%.*]] = extractvalue { i1, i64 } [[TMP18]], 0
+; IR-NEXT:    [[TMP20]] = extractvalue { i1, i64 } [[TMP18]], 1
+; IR-NEXT:    br i1 [[TMP19]], label [[BB31_LOOPEXIT:%.*]], label [[FLOW3]]
 ; IR:       bb31.loopexit:
 ; IR-NEXT:    br label [[FLOW3]]
 ; IR:       bb31:
 ; IR-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP7]])
-; IR-NEXT:    store volatile i32 0, i32 addrspace(1)* undef
+; IR-NEXT:    store volatile i32 0, i32 addrspace(1)* undef, align 4
 ; IR-NEXT:    ret void
+;
 bb:
   %my.tmp = tail call i32 @llvm.amdgcn.workitem.id.x() #1
   %my.tmp1 = zext i32 %my.tmp to i64
   %my.tmp2 = getelementptr inbounds i64, i64 addrspace(1)* %arg, i64 %my.tmp1
   %my.tmp3 = load i64, i64 addrspace(1)* %my.tmp2, align 16
   %my.tmp932 = load <4 x i32>, <4 x i32> addrspace(1)* undef, align 16
   %my.tmp1033 = extractelement <4 x i32> %my.tmp932, i64 0
   %my.tmp1134 = load volatile i32, i32 addrspace(1)* undef

llvm/test/Transforms/StructurizeCFG/improve-order.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -structurizecfg -structurizecfg-node-reorder-size=3 %s -o - | FileCheck %s
+; RUN: opt -S -passes=structurizecfg -structurizecfg-node-reorder-size=3 %s -o - | FileCheck %s
+
+; Test that exit blocks for a loop are reordered so that they
+; appear after their predecessors rather than after the loop.
+; This reduces the number of values needed after the loop
+; to record if the exit blocks are taken/not taken.
+
+define void @reorder_loop(i1 %PredEntry, i1 %PredA, i1 %PredC) {
+; CHECK-LABEL: @reorder_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP1:%.*]], [[FLOW1:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[B:%.*]], label [[FLOW:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       Flow:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[B]] ], [ true, [[A]] ]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[C:%.*]], label [[FLOW1]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[FLOW2:%.*]]
+; CHECK:       Flow1:
+; CHECK-NEXT:    [[TMP1]] = phi i32 [ [[TMP5:%.*]], [[FLOW3:%.*]] ], [ undef, [[FLOW]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP6:%.*]], [[FLOW3]] ], [ false, [[FLOW]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW3]] ], [ true, [[FLOW]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_EXIT_GUARD:%.*]], label [[A]]
+; CHECK:       D:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[FLOW2]]
+; CHECK:       Flow2:
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ false, [[D]] ], [ true, [[C]] ]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[E:%.*]], label [[FLOW3]]
+; CHECK:       E:
+; CHECK-NEXT:    [[INC2:%.*]] = add i32 [[INC1]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[INC2]], 10
+; CHECK-NEXT:    br label [[FLOW3]]
+; CHECK:       F:
+; CHECK-NEXT:    unreachable
+; CHECK:       G:
+; CHECK-NEXT:    ret void
+; CHECK:       Flow3:
+; CHECK-NEXT:    [[TMP5]] = phi i32 [ [[INC2]], [[E]] ], [ undef, [[FLOW2]] ]
+; CHECK-NEXT:    [[TMP6]] = phi i1 [ true, [[E]] ], [ false, [[FLOW2]] ]
+; CHECK-NEXT:    [[TMP7]] = phi i1 [ [[CMP]], [[E]] ], [ true, [[FLOW2]] ]
+; CHECK-NEXT:    br label [[FLOW1]]
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    br i1 [[TMP2]], label [[G]], label [[F:%.*]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %G
+
+; A is the loop header.
+A:
+  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %E ]
+  br i1 %PredA, label %B, label %C
+
+; B is a loop exit block. After reorderNodes in StructurizeCFG, this block
+; remains after A. Without reorderNodes, B is dependent on the Flow block for
+; the loop back edge. B is executes only when the loop exits from A. It does not
+; execute during the loop iterations.
+B:
+  tail call fastcc void @check(i32 1) #0
+  br label %loop.exit.guard
+
+C:
+  br i1 %PredC, label %D, label %E
+
+; D is a loop exit block. After reorderNodes, this block remains in the loop
+; and is not dependent on the Flow block that contains the back edge to the
+; loop header.
+D:
+  tail call fastcc void @check(i32 2) #0
+  br label %loop.exit.guard
+
+; E is a latch and exiting block.
+E:
+  %inc2 = add i32 %inc1, 1
+  %cmp = icmp ult i32 %inc2, 10
+  br i1 %cmp, label %A, label %loop.exit.guard
+
+; Paths fom the exit blocks come here through loop.exit.gaurd.
+F:
+  unreachable
+
+G:
+  ret void
+
+; loop.exit.guard is added by UnifyLoopExits as a common block for all loop
+; exits. After StructurizeCFG, the predecessor B will remain in the loop.
+loop.exit.guard:
+  %Guard.G = phi i1 [ true, %E ], [ false, %B ], [ false, %D ]
+  br i1 %Guard.G, label %G, label %F
+}
+
+; Test that the exit blocks for a nested loop are reordered so that they are
+; not dependent on the Flow block that contains the loop back edge. That
+; dependence forces the block to appear after the loop, which increases the
+; number of live values exiting the loop.
+
+define void @reorder_inner_loop(i1 %PredEntry, i1 %PredB, i1 %PredD) {
+; CHECK-LABEL: @reorder_inner_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[I:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[OUTER1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP5:%.*]], [[FLOW4:%.*]] ]
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[INNER1:%.*]] = phi i32 [ [[TMP1:%.*]], [[FLOW1:%.*]] ], [ 0, [[A]] ]
+; CHECK-NEXT:    br i1 [[PREDB_INV]], label [[C:%.*]], label [[FLOW:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       Flow:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[C]] ], [ true, [[B]] ]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[D:%.*]], label [[FLOW1]]
+; CHECK:       D:
+; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[E:%.*]], label [[FLOW2:%.*]]
+; CHECK:       Flow1:
+; CHECK-NEXT:    [[TMP1]] = phi i32 [ [[TMP8:%.*]], [[FLOW3:%.*]] ], [ undef, [[FLOW]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP9:%.*]], [[FLOW3]] ], [ false, [[FLOW]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP10:%.*]], [[FLOW3]] ], [ true, [[FLOW]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_EXIT_GUARD1:%.*]], label [[B]]
+; CHECK:       E:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[FLOW2]]
+; CHECK:       Flow2:
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ false, [[E]] ], [ true, [[D]] ]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[F:%.*]], label [[FLOW3]]
+; CHECK:       F:
+; CHECK-NEXT:    [[INNER2:%.*]] = add i32 [[INNER1]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp uge i32 [[INNER2]], 20
+; CHECK-NEXT:    br label [[FLOW3]]
+; CHECK:       G:
+; CHECK-NEXT:    [[OUTER2:%.*]] = add i32 [[OUTER1]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp uge i32 [[OUTER2]], 10
+; CHECK-NEXT:    br label [[FLOW4]]
+; CHECK:       H:
+; CHECK-NEXT:    unreachable
+; CHECK:       I:
+; CHECK-NEXT:    ret void
+; CHECK:       Flow4:
+; CHECK-NEXT:    [[TMP5]] = phi i32 [ [[OUTER2]], [[G:%.*]] ], [ undef, [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ true, [[G]] ], [ false, [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    [[TMP7:%.*]] = phi i1 [ [[CMP2]], [[G]] ], [ true, [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    br i1 [[TMP7]], label [[LOOP_EXIT_GUARD:%.*]], label [[A]]
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    br i1 [[TMP6]], label [[I]], label [[H:%.*]]
+; CHECK:       Flow3:
+; CHECK-NEXT:    [[TMP8]] = phi i32 [ [[INNER2]], [[F]] ], [ undef, [[FLOW2]] ]
+; CHECK-NEXT:    [[TMP9]] = phi i1 [ true, [[F]] ], [ false, [[FLOW2]] ]
+; CHECK-NEXT:    [[TMP10]] = phi i1 [ [[CMP1]], [[F]] ], [ true, [[FLOW2]] ]
+; CHECK-NEXT:    br label [[FLOW1]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    br i1 [[TMP2]], label [[G]], label [[FLOW4]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %I
+
+; A is the outer loop header block.
+A:
+  %outer1 = phi i32 [ 0, %entry ], [ %outer2, %G ]
+  br label %B
+
+; B is the inner loop header block.
+B:
+  %inner1 = phi i32 [ 0, %A ], [ %inner2, %F ]
+  br i1 %PredB, label %D, label %C
+
+; C is a loop exit block. After reorderNodes in StructureCFG, this block
+; remains after B rather and is not dependent on the Flow block that contains
+; the back edge to the loop header.
+C:
+  tail call fastcc void @check(i32 1) #0
+  br label %loop.exit.guard1
+
+D:
+  br i1 %PredD, label %E, label %F
+
+; E is a loop exit block. After reorderNodes in StructurizeCFG, this block
+; remains in the loop and is not dependent on the Flow block that contains
+; the back edge to the loop header.
+E:
+  tail call fastcc void @check(i32 2) #0
+  br label %loop.exit.guard1
+
+; F is a latch block for the inner loop.
+F:
+  %inner2 = add i32 %inner1, 1
+  %cmp1 = icmp ult i32 %inner2, 20
+  br i1 %cmp1, label %B, label %loop.exit.guard1
+
+; G is a latch block for the outer loop.
+G:
+  %outer2 = add i32 %outer1, 1
+  %cmp2 = icmp ult i32 %outer2, 10
+  br i1 %cmp2, label %A, label %loop.exit.guard
+
+; Paths from the exit blocks come here through loop.exit.gaurd.
+H:
+  unreachable
+
+I:
+  ret void
+
+; loop.exit.guard is added by UnifyLoopExits as a common block for all loop
+; exits. This instance is for the outer loop.
+loop.exit.guard:
+  %Guard.I = phi i1 [ true, %G ], [ %Guard.I.moved, %loop.exit.guard1 ]
+  br i1 %Guard.I, label %I, label %H
+
+; loop.exit.guard is added for the inner loop.
+loop.exit.guard1:
+  %Guard.G = phi i1 [ true, %F ], [ false, %C ], [ false, %E ]
+  %Guard.I.moved = phi i1 [ undef, %F ], [ false, %C ], [ false, %E ]
+  br i1 %Guard.G, label %G, label %loop.exit.guard
+}
+
+; Test when the common successor is not unreachable. In particular, the common
+; successor is inside the region. In this case, it is still helpful to keep
+; the exit blocks inside the loop to reduce live values that exit the loop.
+
+define void @common_exit(i1 %PredEntry, i1 %PredA, i1 %PredB) {
+; CHECK-LABEL: @common_exit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true
+; CHECK-NEXT:    [[PREDA_INV:%.*]] = xor i1 [[PREDA:%.*]], true
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ [[TMP4:%.*]], [[FLOW:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA_INV]], label [[C:%.*]], label [[FLOW]]
+; CHECK:       Flow3:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[D:%.*]] ], [ false, [[FLOW2:%.*]] ]
+; CHECK-NEXT:    br i1 [[TMP6:%.*]], label [[B:%.*]], label [[FLOW4:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    tail call fastcc void @check1(i32 1) #[[ATTR1:[0-9]+]]
+; CHECK-NEXT:    br label [[FLOW4]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDB_INV]], label [[E:%.*]], label [[FLOW1:%.*]]
+; CHECK:       Flow1:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[INC2:%.*]], [[E]] ], [ undef, [[C]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[CMP:%.*]], [[E]] ], [ true, [[C]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ false, [[E]] ], [ true, [[C]] ]
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       Flow2:
+; CHECK-NEXT:    br i1 [[TMP7:%.*]], label [[D]], label [[FLOW3:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    tail call fastcc void @check1(i32 2) #[[ATTR1]]
+; CHECK-NEXT:    br label [[FLOW3]]
+; CHECK:       Flow:
+; CHECK-NEXT:    [[TMP4]] = phi i32 [ [[TMP1]], [[FLOW1]] ], [ undef, [[A]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ [[TMP2]], [[FLOW1]] ], [ true, [[A]] ]
+; CHECK-NEXT:    [[TMP6]] = phi i1 [ false, [[FLOW1]] ], [ true, [[A]] ]
+; CHECK-NEXT:    [[TMP7]] = phi i1 [ [[TMP3]], [[FLOW1]] ], [ false, [[A]] ]
+; CHECK-NEXT:    br i1 [[TMP5]], label [[FLOW2]], label [[A]]
+; CHECK:       E:
+; CHECK-NEXT:    [[INC2]] = add i32 [[INC1]], 1
+; CHECK-NEXT:    [[CMP]] = icmp uge i32 [[INC2]], 10
+; CHECK-NEXT:    br label [[FLOW1]]
+; CHECK:       Flow4:
+; CHECK-NEXT:    [[TMP8:%.*]] = phi i1 [ true, [[B]] ], [ [[TMP0]], [[FLOW3]] ]
+; CHECK-NEXT:    br i1 [[TMP8]], label [[F:%.*]], label [[FLOW5:%.*]]
+; CHECK:       F:
+; CHECK-NEXT:    br label [[FLOW5]]
+; CHECK:       Flow5:
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       G:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %PredEntry, label %A, label %G
+
+; A is the loop header.
+A:
+  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %E ]
+  br i1 %PredA, label %B, label %C
+
+; B is a loop exit block. After reorderNodes in StructurizeCFG, this block
+; remains after A rather than moving to after the loop due to a dependence on
+; the Flow block that contains the loop back edge.
+B:
+  tail call fastcc void @check1(i32 1) #1
+  br label %F
+
+C:
+  br i1 %PredB, label %D, label %E
+
+; D is a loop exit block. After reorderNodes, this block remains in the loop
+; rather than moving to after the loop due to a dependence on the Flow block
+; that contains the loop back edge.
+D:
+  tail call fastcc void @check1(i32 2) #1
+  br label %F
+
+; E is a latch and exiting block.
+E:
+  %inc2 = add i32 %inc1, 1
+  %cmp = icmp ult i32 %inc2, 10
+  br i1 %cmp, label %A, label %G
+
+; F is reached by the loop exit blocks, B and D.
+F:
+  br label %G
+
+G:
+  ret void
+}
+
+; Test when there are many loop exiting blocks. Previous tests have two exiting
+; blocks. This test contains five. Each of the exiting blocks remain in the loop
+; rather than being moved to after the loop.
+
+define void @many_exiting_blocks(i1 %PredEntry, i1 %PredA, i1 %PredC, i1 %PredE, i1 %PredG) {
+; CHECK-LABEL: @many_exiting_blocks(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[FLOW11:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ [[TMP1:%.*]], [[FLOW4:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[B:%.*]], label [[FLOW3:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; CHECK-NEXT:    br label [[FLOW3]]
+; CHECK:       Flow3:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[B]] ], [ true, [[A]] ]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[C:%.*]], label [[FLOW4]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[FLOW5:%.*]]
+; CHECK:       Flow4:
+; CHECK-NEXT:    [[TMP1]] = phi i32 [ [[TMP6:%.*]], [[FLOW6:%.*]] ], [ undef, [[FLOW3]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW6]] ], [ true, [[FLOW3]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP8:%.*]], [[FLOW6]] ], [ false, [[FLOW3]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP9:%.*]], [[FLOW6]] ], [ true, [[FLOW3]] ]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP_EXIT_GUARD:%.*]], label [[A]]
+; CHECK:       D:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[FLOW5]]
+; CHECK:       Flow5:
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[D]] ], [ true, [[C]] ]
+; CHECK-NEXT:    br i1 [[TMP5]], label [[E:%.*]], label [[FLOW6]]
+; CHECK:       E:
+; CHECK-NEXT:    br i1 [[PREDE:%.*]], label [[F:%.*]], label [[FLOW7:%.*]]
+; CHECK:       Flow6:
+; CHECK-NEXT:    [[TMP6]] = phi i32 [ [[TMP12:%.*]], [[FLOW8:%.*]] ], [ undef, [[FLOW5]] ]
+; CHECK-NEXT:    [[TMP7]] = phi i1 [ [[TMP13:%.*]], [[FLOW8]] ], [ true, [[FLOW5]] ]
+; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP14:%.*]], [[FLOW8]] ], [ false, [[FLOW5]] ]
+; CHECK-NEXT:    [[TMP9]] = phi i1 [ [[TMP15:%.*]], [[FLOW8]] ], [ true, [[FLOW5]] ]
+; CHECK-NEXT:    br label [[FLOW4]]
+; CHECK:       F:
+; CHECK-NEXT:    tail call fastcc void @check(i32 3) #[[ATTR0]]
+; CHECK-NEXT:    br label [[FLOW7]]
+; CHECK:       Flow7:
+; CHECK-NEXT:    [[TMP10:%.*]] = phi i1 [ false, [[F]] ], [ true, [[E]] ]
+; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ false, [[F]] ], [ true, [[E]] ]
+; CHECK-NEXT:    br i1 [[TMP11]], label [[G:%.*]], label [[FLOW8]]
+; CHECK:       G:
+; CHECK-NEXT:    br i1 [[PREDG:%.*]], label [[H:%.*]], label [[FLOW9:%.*]]
+; CHECK:       Flow8:
+; CHECK-NEXT:    [[TMP12]] = phi i32 [ [[TMP19:%.*]], [[FLOW10:%.*]] ], [ undef, [[FLOW7]] ]
+; CHECK-NEXT:    [[TMP13]] = phi i1 [ [[TMP20:%.*]], [[FLOW10]] ], [ [[TMP10]], [[FLOW7]] ]
+; CHECK-NEXT:    [[TMP14]] = phi i1 [ [[TMP21:%.*]], [[FLOW10]] ], [ false, [[FLOW7]] ]
+; CHECK-NEXT:    [[TMP15]] = phi i1 [ [[TMP22:%.*]], [[FLOW10]] ], [ true, [[FLOW7]] ]
+; CHECK-NEXT:    br label [[FLOW6]]
+; CHECK:       H:
+; CHECK-NEXT:    tail call fastcc void @check(i32 4) #[[ATTR0]]
+; CHECK-NEXT:    br label [[FLOW9]]
+; CHECK:       Flow9:
+; CHECK-NEXT:    [[TMP16:%.*]] = phi i1 [ false, [[H]] ], [ [[TMP10]], [[G]] ]
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i1 [ false, [[H]] ], [ true, [[G]] ]
+; CHECK-NEXT:    br i1 [[TMP17]], label [[I:%.*]], label [[FLOW10]]
+; CHECK:       I:
+; CHECK-NEXT:    [[INC2:%.*]] = add i32 [[INC1]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[INC2]], 10
+; CHECK-NEXT:    br label [[FLOW10]]
+; CHECK:       Flow:
+; CHECK-NEXT:    [[TMP18:%.*]] = phi i1 [ false, [[K:%.*]] ], [ true, [[LOOP_EXIT_GUARD1:%.*]] ]
+; CHECK-NEXT:    br i1 [[TMP18]], label [[J:%.*]], label [[FLOW1:%.*]]
+; CHECK:       J:
+; CHECK-NEXT:    br label [[FLOW1]]
+; CHECK:       K:
+; CHECK-NEXT:    br label [[FLOW:%.*]]
+; CHECK:       Flow1:
+; CHECK-NEXT:    br label [[FLOW2:%.*]]
+; CHECK:       Flow2:
+; CHECK-NEXT:    br label [[FLOW11]]
+; CHECK:       L:
+; CHECK-NEXT:    ret void
+; CHECK:       Flow10:
+; CHECK-NEXT:    [[TMP19]] = phi i32 [ [[INC2]], [[I]] ], [ undef, [[FLOW9]] ]
+; CHECK-NEXT:    [[TMP20]] = phi i1 [ false, [[I]] ], [ [[TMP16]], [[FLOW9]] ]
+; CHECK-NEXT:    [[TMP21]] = phi i1 [ true, [[I]] ], [ false, [[FLOW9]] ]
+; CHECK-NEXT:    [[TMP22]] = phi i1 [ [[CMP]], [[I]] ], [ true, [[FLOW9]] ]
+; CHECK-NEXT:    br label [[FLOW8]]
+; CHECK:       Flow11:
+; CHECK-NEXT:    br label [[L:%.*]]
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_L_INV:%.*]] = xor i1 [[TMP3]], true
+; CHECK-NEXT:    [[GUARD_J_INV:%.*]] = xor i1 [[TMP2]], true
+; CHECK-NEXT:    br i1 [[GUARD_L_INV]], label [[LOOP_EXIT_GUARD1]], label [[FLOW2]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    br i1 [[GUARD_J_INV]], label [[K]], label [[FLOW]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %L
+
+; A is the loop header block.
+A:
+  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %I ]
+  br i1 %PredA, label %B, label %C
+
+; B is a loop exit block. After reorderNodes in StructurizeCFG, this block
+; remains after A rather than moving to after the loop due to a dependence
+; on the Flow block that contains the loop back edge.
+B:
+  tail call fastcc void @check(i32 1) #0
+  br label %loop.exit.guard
+
+C:
+  br i1 %PredC, label %D, label %E
+
+; D is a loop exit block. After reorderNodes, this block remains in the loop
+; rather than moving to after the loop.
+D:
+  tail call fastcc void @check(i32 2) #0
+  br label %loop.exit.guard
+
+E:
+  br i1 %PredE, label %F, label %G
+
+; F is a loop exit block. After reorderNodes, this block remains in the loop
+; rather than moving to after the loop.
+F:
+  tail call fastcc void @check(i32 3) #0
+  br label %loop.exit.guard
+
+G:
+  br i1 %PredG, label %H, label %I
+
+; H is a loop exit block. After reorderNodes, this block remains in the loop
+; rather than moving to after the loop.
+H:
+  tail call fastcc void @check(i32 4) #0
+  br label %loop.exit.guard
+
+; I is a latch block.
+I:
+  %inc2 = add i32 %inc1, 1
+  %cmp = icmp ult i32 %inc2, 10
+  br i1 %cmp, label %A, label %loop.exit.guard
+
+J:
+  br label %L
+
+K:
+  br label %L
+
+L:
+  ret void
+
+loop.exit.guard:
+  %Guard.L = phi i1 [ true, %I ], [ false, %B ], [ false, %D ], [ false, %F ], [ false, %H ]
+  %Guard.J = phi i1 [ false, %I ], [ true, %B ], [ true, %D ], [ false, %F ], [ false, %H ]
+  br i1 %Guard.L, label %L, label %loop.exit.guard1
+
+loop.exit.guard1:
+  br i1 %Guard.J, label %J, label %K
+}
+
+declare void @check(i32 noundef) #0
+declare void @check1(i32 noundef) #1
+
+attributes #0 = { noreturn nounwind }
+attributes #1 = { nounwind }
+
+
+; When there are two blocks that can be moved closer to the predecessor,
+; maintain the original, relative order since swapping the order should not
+; provide any benefit. In this case both B and C have a single predecessor
+; and a single successor.
+
+define void @same_predecessor(i1 %PredA) {
+; CHECK-LABEL: @same_predecessor(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[PREDA_INV:%.*]] = xor i1 [[PREDA:%.*]], true
+; CHECK-NEXT:    br i1 [[PREDA_INV]], label [[B:%.*]], label [[FLOW:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       Flow:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[B]] ], [ true, [[A:%.*]] ]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[C:%.*]], label [[D:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    br label [[D]]
+; CHECK:       D:
+; CHECK-NEXT:    ret void
+;
+A:
+  br i1 %PredA, label %C, label %B
+
+B:
+  br label %D
+
+C:
+  br label %D
+
+D:
+  ret void
+}
+
+