Prevent rotating the blocks of a loop (and thus getting a backedge to be

fallthrough) in cases where we might fail to rotate an exit to an outer
loop onto the end of the loop chain.

Having *some* rotation, but not performing this rotation, is the primary
fix of thep performance regression with -enable-block-placement for
Olden/em3d (a whopping 30% regression). Still working on reducing the
test case that actually exercises this and the new rotation strategy out
of this code, but I want to check if this regresses other test cases
first as that may indicate it isn't the correct fix.

llvm-svn: 145195

1 files changed, 16 insertions, 0 deletions

diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index 56ad856b167..584290bd0fc 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -571,6 +571,11 @@ MachineBlockPlacement::findBestLoopTop(MachineFunction &F,
   BlockFrequency BestExitEdgeFreq;
   MachineBasicBlock *ExitingBB = 0;
   MachineBasicBlock *LoopingBB = 0;
+  // If there are exits to outer loops, loop rotation can severely limit
+  // fallthrough opportunites unless it selects such an exit. Keep a set of
+  // blocks where rotating to exit with that block will reach an outer loop.
+  SmallPtrSet<MachineBasicBlock *, 4> BlocksExitingToOuterLoop;
+
   DEBUG(dbgs() << "Finding best loop exit for: "
                << getBlockName(L.getHeader()) << "\n");
   for (MachineLoop::block_iterator I = L.block_begin(),
@@ -641,6 +646,10 @@ MachineBlockPlacement::findBestLoopTop(MachineFunction &F,
         BestExitEdgeFreq = ExitEdgeFreq;
         ExitingBB = *I;
       }
+
+      if (MachineLoop *ExitLoop = MLI->getLoopFor(*SI))
+        if (ExitLoop->contains(&L))
+          BlocksExitingToOuterLoop.insert(*I);
     }
 
     // Restore the old exiting state, no viable looping successor was found.
@@ -659,6 +668,13 @@ MachineBlockPlacement::findBestLoopTop(MachineFunction &F,
   if (!ExitingBB || L.getNumBlocks() == 1)
     return L.getHeader();
 
+  // Also, if we have exit blocks which lead to outer loops but didn't select
+  // one of them as the exiting block we are rotating toward, disable loop
+  // rotation altogether.
+  if (!BlocksExitingToOuterLoop.empty() &&
+      !BlocksExitingToOuterLoop.count(ExitingBB))
+    return L.getHeader();
+
   assert(LoopingBB && "All successors of a loop block are exit blocks!");
   DEBUG(dbgs() << "  Best exiting block: " << getBlockName(ExitingBB) << "\n");
   DEBUG(dbgs() << "  Best top block: " << getBlockName(LoopingBB) << "\n");