[MachineBlockPlacement] Make sure PreferredLoopExit is cleared everytime new loop is processed

[trentxintong]

Summary

Rotate on exit that actually exits the current loop.

I found this by looking this nested loop. When loop@Depth3 is processed, BB#193 is the exiting block. And when loop@Depth2 is processed, the loop is rotated w.r.t BB#193 because PreferredLoopExit is not cleared. Should not we clear PreferredLoopExit every time we process a new loop ?

BB#193: derived from LLVM BB %cleanup.i.i781

Live Ins: %RAX %RBP %RBX %RSI %R9 %R10 %R11 %R13 %R14 %R15
Predecessors according to CFG: BB#192
    %RBX<def,tied1> = ADD64ri8 %RBX<kill,tied0>, 8, %EFLAGS<imp-def,dead>
    %RBP<def,tied1> = ADD64ri8 %RBP<kill,tied0>, 8, %EFLAGS<imp-def,dead>
    CMP64rr %RBX, %R15, %EFLAGS<imp-def>
    JB_1 <BB#192>, %EFLAGS<imp-use>
    JMP_1 <BB#174>
Successors according to CFG: BB#192(0x7fef9fcb / 0x80000000 = 99.95%) BB#174(0x00106035 / 0x80000000 = 0.05%)

Loop at depth 2 containing: BB#191<header>,BB#192,BB#182,BB#193,BB#174,BB#175,BB#176,BB#177,BB#178,BB#179,BB#180,BB#181,BB#183,BB#187<exiting>,BB#184,BB#185,BB#186<exiting>,BB#188<exiting>,BB#189<exiting>,BB#190<latch>
Loop at depth 3 containing: BB#192<header><exiting>,BB#193<latch><exiting>

[davidxl]

A test case?

[trentxintong]

In D38563#888831, @davidxl wrote:

A test case?

I thought about adding a .ll test case, but should not an assert guard against future failures better than a shoehorn'ed test case to check just this sort of thing ?

[skatkov]

I believe that added assert is invalid. PreferredLoopExit might be easily part of the loop L if it was not added to hot chain. In other words pass decided to layout this BB in a scope of outer loop or function at all.

If you agree with me, please fix this asap.

[gyiu]

@trentxintong Hello, this change is actually causing the assert to trigger in 15 SPEC2006 benchmarks on PPC64LE with '-O3 -mcpu=pwr8 -m64 -fprofile-use -flto=thin'. Failures are during the link step.

lib/CodeGen/MachineBlockPlacement.cpp:2246: void {anonymous}::MachineBlockPlacement::buildLoopChains(const llvm::MachineLoop&): Assertion `L.isLoopExiting(PreferredLoopExit) && "not an exiting block of current loop"' failed.

Benchmarks: 400.perlbench 401.bzip2 403.gcc 433.milc 445.gobmk 447.dealII 450.soplex 453.povray 456.hmmer 458.sjeng 464.h264ref 471.omnetpp 473.astar 482.sphinx3 483.xalancbmk

llvm/trunk/lib/CodeGen/MachineBlockPlacement.cpp

void MachineBlockPlacement::buildLoopChains(const MachineLoop &L) {
   // fewer branches in the loop body.
   // When we use profile data to rotate the loop, this is unnecessary.
   MachineBasicBlock *LoopTop =
       RotateLoopWithProfile ? L.getHeader() : findBestLoopTop(L, LoopBlockSet);
 
   // If we selected just the header for the loop top, look for a potentially
   // profitable exit block in the event that rotating the loop can eliminate
   // branches by placing an exit edge at the bottom.
+  //
+  // Loops are processed innermost to uttermost, make sure we clear
+  // PreferredLoopExit before processing a new loop.
+  PreferredLoopExit = nullptr;
   if (!RotateLoopWithProfile && LoopTop == L.getHeader())
     PreferredLoopExit = findBestLoopExit(L, LoopBlockSet);
 
+  // Make sure PreferredLoopExit actually exits the current loop.
+  if (PreferredLoopExit) {
+    assert(L.isLoopExiting(PreferredLoopExit) &&
+           "not an exiting block of current loop");
+  }
+
   BlockChain &LoopChain = *BlockToChain[LoopTop];
 
   // FIXME: This is a really lame way of walking the chains in the loop: we
   // walk the blocks, and use a set to prevent visiting a particular chain
   // twice.
   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
   assert(LoopChain.UnscheduledPredecessors == 0 &&
          "LoopChain should not have unscheduled predecessors.");