Post-ra LICM should take care not to hoist an instruction that would clobber a

[oota-llvm.git] / lib / CodeGen / MachineBlockPlacement.cpp

diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp
index 56ad856b167ed0480d97f0cfea55807c8156794c..63892af890a816e1b0739e6c931639c5296c9466 100644 (file)
--- a/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/lib/CodeGen/MachineBlockPlacement.cpp
@@ -36,10 +36,7 @@
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
-#include "llvm/Support/ErrorHandling.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/PostOrderIterator.h"
-#include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -55,22 +52,6 @@ STATISTIC(CondBranchTakenFreq,
 STATISTIC(UncondBranchTakenFreq,
           "Potential frequency of taking unconditional branches");
 
-namespace {
-/// \brief A structure for storing a weighted edge.
-///
-/// This stores an edge and its weight, computed as the product of the
-/// frequency that the starting block is entered with the probability of
-/// a particular exit block.
-struct WeightedEdge {
-  BlockFrequency EdgeFrequency;
-  MachineBasicBlock *From, *To;
-
-  bool operator<(const WeightedEdge &RHS) const {
-    return EdgeFrequency < RHS.EdgeFrequency;
-  }
-};
-}
-
 namespace {
 class BlockChain;
 /// \brief Type for our function-wide basic block -> block chain mapping.
@@ -121,17 +102,13 @@ public:
   }
 
   /// \brief Iterator over blocks within the chain.
-  typedef SmallVectorImpl<MachineBasicBlock *>::iterator iterator;
-  typedef SmallVectorImpl<MachineBasicBlock *>::reverse_iterator
-      reverse_iterator;
+  typedef SmallVectorImpl<MachineBasicBlock *>::const_iterator iterator;
 
   /// \brief Beginning of blocks within the chain.
-  iterator begin() { return Blocks.begin(); }
-  reverse_iterator rbegin() { return Blocks.rbegin(); }
+  iterator begin() const { return Blocks.begin(); }
 
   /// \brief End of blocks within the chain.
-  iterator end() { return Blocks.end(); }
-  reverse_iterator rend() { return Blocks.rend(); }
+  iterator end() const { return Blocks.end(); }
 
   /// \brief Merge a block chain into this one.
   ///
@@ -247,12 +224,11 @@ public:
     AU.addRequired<MachineLoopInfo>();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
-
-  const char *getPassName() const { return "Block Placement"; }
 };
 }
 
 char MachineBlockPlacement::ID = 0;
+char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID;
 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2",
                       "Branch Probability Basic Block Placement", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
@@ -261,10 +237,6 @@ INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2",
                     "Branch Probability Basic Block Placement", false, false)
 
-FunctionPass *llvm::createMachineBlockPlacementPass() {
-  return new MachineBlockPlacement();
-}
-
 #ifndef NDEBUG
 /// \brief Helper to print the name of a MBB.
 ///
@@ -553,7 +525,7 @@ void MachineBlockPlacement::buildChain(
     markChainSuccessors(SuccChain, LoopHeaderBB, BlockWorkList, BlockFilter);
     Chain.merge(BestSucc, &SuccChain);
     BB = *llvm::prior(Chain.end());
-  };
+  }
 
   DEBUG(dbgs() << "Finished forming chain for header block "
                << getBlockNum(*Chain.begin()) << "\n");
@@ -571,6 +543,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 +618,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 +640,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");
@@ -688,8 +676,8 @@ void MachineBlockPlacement::buildLoopChains(MachineFunction &F,
   // walk the blocks, and use a set to prevent visiting a particular chain
   // twice.
   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
-  assert(BlockToChain[LayoutTop]->LoopPredecessors == 0);
-  UpdatedPreds.insert(BlockToChain[LayoutTop]);
+  assert(LoopChain.LoopPredecessors == 0);
+  UpdatedPreds.insert(&LoopChain);
   for (MachineLoop::block_iterator BI = L.block_begin(),
                                    BE = L.block_end();
        BI != BE; ++BI) {
@@ -950,12 +938,11 @@ public:
     AU.setPreservesAll();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
-
-  const char *getPassName() const { return "Block Placement Stats"; }
 };
 }
 
 char MachineBlockPlacementStats::ID = 0;
+char &llvm::MachineBlockPlacementStatsID = MachineBlockPlacementStats::ID;
 INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats",
                       "Basic Block Placement Stats", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
@@ -963,10 +950,6 @@ INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
 INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats",
                     "Basic Block Placement Stats", false, false)
 
-FunctionPass *llvm::createMachineBlockPlacementStatsPass() {
-  return new MachineBlockPlacementStats();
-}
-
 bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) {
   // Check for single-block functions and skip them.
   if (llvm::next(F.begin()) == F.end())