diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index 638d895..d874f2a 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -116,7 +116,7 @@
   /// a contiguous sequence of basic blocks, updating the edge list, and
   /// updating the block -> chain mapping. It does not free or tear down the
   /// old chain, but the old chain's block list is no longer valid.
-  void merge(MachineBasicBlock *BB, BlockChain *Chain) {
+  void merge(MachineBasicBlock *BB, const BlockChain *Chain) {
     assert(BB);
     assert(!Blocks.empty());
 
@@ -185,28 +185,27 @@
   /// between basic blocks.
   DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
 
-  void markChainSuccessors(BlockChain &Chain,
-                           MachineBasicBlock *LoopHeaderBB,
+  void markChainSuccessors(const BlockChain &Chain,
+                           const MachineBasicBlock *LoopHeaderBB,
                            SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
-                           const BlockFilterSet *BlockFilter = 0);
-  MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
-                                         BlockChain &Chain,
-                                         const BlockFilterSet *BlockFilter);
+                           const BlockFilterSet *BlockFilter = 0) const;
+  MachineBasicBlock *selectBestSuccessor(const MachineBasicBlock *BB,
+      const BlockChain &Chain, const BlockFilterSet *BlockFilter) const;
   MachineBasicBlock *selectBestCandidateBlock(
-      BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
-      const BlockFilterSet *BlockFilter);
+      const BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
+      const BlockFilterSet *BlockFilter) const;
   MachineBasicBlock *getFirstUnplacedBlock(
       MachineFunction &F,
       const BlockChain &PlacedChain,
       MachineFunction::iterator &PrevUnplacedBlockIt,
-      const BlockFilterSet *BlockFilter);
+      const BlockFilterSet *BlockFilter) const;
   void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
                   SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
-                  const BlockFilterSet *BlockFilter = 0);
+                  const BlockFilterSet *BlockFilter = 0) const;
   MachineBasicBlock *findBestLoopTop(MachineFunction &F,
                                      MachineLoop &L,
-                                     const BlockFilterSet &LoopBlockSet);
-  void buildLoopChains(MachineFunction &F, MachineLoop &L);
+                                     const BlockFilterSet &LoopBlockSet) const;
+  void buildLoopChains(MachineFunction &F, MachineLoop &L) const;
   void buildCFGChains(MachineFunction &F);
   void AlignLoops(MachineFunction &F);
 
@@ -246,7 +245,7 @@
 /// \brief Helper to print the name of a MBB.
 ///
 /// Only used by debug logging.
-static std::string getBlockName(MachineBasicBlock *BB) {
+static std::string getBlockName(const MachineBasicBlock *BB) {
   std::string Result;
   raw_string_ostream OS(Result);
   OS << "BB#" << BB->getNumber()
@@ -258,7 +257,7 @@
 /// \brief Helper to print the number of a MBB.
 ///
 /// Only used by debug logging.
-static std::string getBlockNum(MachineBasicBlock *BB) {
+static std::string getBlockNum(const MachineBasicBlock *BB) {
   std::string Result;
   raw_string_ostream OS(Result);
   OS << "BB#" << BB->getNumber();
@@ -274,10 +273,10 @@
 /// having one fewer active predecessor. It also adds any successors of this
 /// chain which reach the zero-predecessor state to the worklist passed in.
 void MachineBlockPlacement::markChainSuccessors(
-    BlockChain &Chain,
-    MachineBasicBlock *LoopHeaderBB,
+    const BlockChain &Chain,
+    const MachineBasicBlock *LoopHeaderBB,
     SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
-    const BlockFilterSet *BlockFilter) {
+    const BlockFilterSet *BlockFilter) const {
   // Walk all the blocks in this chain, marking their successors as having
   // a predecessor placed.
   for (BlockChain::iterator CBI = Chain.begin(), CBE = Chain.end();
@@ -291,7 +290,7 @@
          SI != SE; ++SI) {
       if (BlockFilter && !BlockFilter->count(*SI))
         continue;
-      BlockChain &SuccChain = *BlockToChain[*SI];
+      BlockChain &SuccChain = *BlockToChain.lookup(*SI);
       // Disregard edges within a fixed chain, or edges to the loop header.
       if (&Chain == &SuccChain || *SI == LoopHeaderBB)
         continue;
@@ -314,8 +313,8 @@
 ///
 /// \returns The best successor block found, or null if none are viable.
 MachineBasicBlock *MachineBlockPlacement::selectBestSuccessor(
-    MachineBasicBlock *BB, BlockChain &Chain,
-    const BlockFilterSet *BlockFilter) {
+    const MachineBasicBlock *BB, const BlockChain &Chain,
+    const BlockFilterSet *BlockFilter) const {
   const BranchProbability HotProb(4, 5); // 80%
 
   MachineBasicBlock *BestSucc = 0;
@@ -329,12 +328,11 @@
   uint32_t WeightScale = 0;
   uint32_t SumWeight = MBPI->getSumForBlock(BB, WeightScale);
   DEBUG(dbgs() << "Attempting merge from: " << getBlockName(BB) << "\n");
-  for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
-                                        SE = BB->succ_end();
-       SI != SE; ++SI) {
+  for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(),
+       SE = BB->succ_end(); SI != SE; ++SI) {
     if (BlockFilter && !BlockFilter->count(*SI))
       continue;
-    BlockChain &SuccChain = *BlockToChain[*SI];
+    const BlockChain &SuccChain = *BlockToChain.lookup(*SI);
     if (&SuccChain == &Chain) {
       DEBUG(dbgs() << "    " << getBlockName(*SI) << " -> Already merged!\n");
       continue;
@@ -364,7 +362,7 @@
                                             PE = (*SI)->pred_end();
            PI != PE; ++PI) {
         if (*PI == *SI || (BlockFilter && !BlockFilter->count(*PI)) ||
-            BlockToChain[*PI] == &Chain)
+            BlockToChain.lookup(*PI) == &Chain)
           continue;
         BlockFrequency PredEdgeFreq
           = MBFI->getBlockFreq(*PI) * MBPI->getEdgeProbability(*PI, *SI);
@@ -420,8 +418,8 @@
 ///
 /// \returns The best block found, or null if none are viable.
 MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock(
-    BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
-    const BlockFilterSet *BlockFilter) {
+    const BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
+    const BlockFilterSet *BlockFilter) const {
   // Once we need to walk the worklist looking for a candidate, cleanup the
   // worklist of already placed entries.
   // FIXME: If this shows up on profiles, it could be folded (at the cost of
@@ -436,7 +434,7 @@
                                                       WBE = WorkList.end();
        WBI != WBE; ++WBI) {
     assert(!BlockFilter || BlockFilter->count(*WBI));
-    BlockChain &SuccChain = *BlockToChain[*WBI];
+    const BlockChain &SuccChain = *BlockToChain.lookup(*WBI);
     if (&SuccChain == &Chain) {
       DEBUG(dbgs() << "    " << getBlockName(*WBI)
                    << " -> Already merged!\n");
@@ -465,17 +463,17 @@
 MachineBasicBlock *MachineBlockPlacement::getFirstUnplacedBlock(
     MachineFunction &F, const BlockChain &PlacedChain,
     MachineFunction::iterator &PrevUnplacedBlockIt,
-    const BlockFilterSet *BlockFilter) {
+    const BlockFilterSet *BlockFilter) const {
   for (MachineFunction::iterator I = PrevUnplacedBlockIt, E = F.end(); I != E;
        ++I) {
     if (BlockFilter && !BlockFilter->count(I))
       continue;
-    if (BlockToChain[I] != &PlacedChain) {
+    if (BlockToChain.lookup(I) != &PlacedChain) {
       PrevUnplacedBlockIt = I;
       // Now select the head of the chain to which the unplaced block belongs
       // as the block to place. This will force the entire chain to be placed,
       // and satisfies the requirements of merging chains.
-      return *BlockToChain[I]->begin();
+      return *BlockToChain.lookup(I)->begin();
     }
   }
   return 0;
@@ -485,9 +483,9 @@
     MachineBasicBlock *BB,
     BlockChain &Chain,
     SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
-    const BlockFilterSet *BlockFilter) {
+    const BlockFilterSet *BlockFilter) const {
   assert(BB);
-  assert(BlockToChain[BB] == &Chain);
+  assert(BlockToChain.lookup(BB) == &Chain);
   MachineFunction &F = *BB->getParent();
   MachineFunction::iterator PrevUnplacedBlockIt = F.begin();
 
@@ -496,7 +494,7 @@
   BB = *llvm::prior(Chain.end());
   for (;;) {
     assert(BB);
-    assert(BlockToChain[BB] == &Chain);
+    assert(BlockToChain.lookup(BB) == &Chain);
     assert(*llvm::prior(Chain.end()) == BB);
     MachineBasicBlock *BestSucc = 0;
 
@@ -521,7 +519,7 @@
     }
 
     // Place this block, updating the datastructures to reflect its placement.
-    BlockChain &SuccChain = *BlockToChain[BestSucc];
+    BlockChain &SuccChain = *BlockToChain.lookup(BestSucc);
     // Zero out LoopPredecessors for the successor we're about to merge in case
     // we selected a successor that didn't fit naturally into the CFG.
     SuccChain.LoopPredecessors = 0;
@@ -544,7 +542,7 @@
 MachineBasicBlock *
 MachineBlockPlacement::findBestLoopTop(MachineFunction &F,
                                        MachineLoop &L,
-                                       const BlockFilterSet &LoopBlockSet) {
+                                       const BlockFilterSet &LoopBlockSet) const {
   BlockFrequency BestExitEdgeFreq;
   MachineBasicBlock *ExitingBB = 0;
   MachineBasicBlock *LoopingBB = 0;
@@ -558,7 +556,7 @@
   for (MachineLoop::block_iterator I = L.block_begin(),
                                    E = L.block_end();
        I != E; ++I) {
-    BlockChain &Chain = *BlockToChain[*I];
+    const BlockChain &Chain = *BlockToChain.lookup(*I);
     // Ensure that this block is at the end of a chain; otherwise it could be
     // mid-way through an inner loop or a successor of an analyzable branch.
     if (*I != *llvm::prior(Chain.end()))
@@ -588,7 +586,7 @@
         continue;
       if (*SI == *I)
         continue;
-      BlockChain &SuccChain = *BlockToChain[*SI];
+      const BlockChain &SuccChain = *BlockToChain.lookup(*SI);
       // Don't split chains, either this chain or the successor's chain.
       if (&Chain == &SuccChain || *SI != *SuccChain.begin()) {
         DEBUG(dbgs() << "    " << (LoopBlockSet.count(*SI) ? "looping: "
@@ -665,7 +663,7 @@
 /// both preserves the topological structure and minimizes taken conditional
 /// branches.
 void MachineBlockPlacement::buildLoopChains(MachineFunction &F,
-                                            MachineLoop &L) {
+                                            MachineLoop &L) const {
   // First recurse through any nested loops, building chains for those inner
   // loops.
   for (MachineLoop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
@@ -675,29 +673,29 @@
   BlockFilterSet LoopBlockSet(L.block_begin(), L.block_end());
 
   MachineBasicBlock *LayoutTop = findBestLoopTop(F, L, LoopBlockSet);
-  BlockChain &LoopChain = *BlockToChain[LayoutTop];
+  BlockChain &LoopChain = *BlockToChain.lookup(LayoutTop);
 
   // 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;
+  SmallPtrSet<const BlockChain *, 4> UpdatedPreds;
   assert(LoopChain.LoopPredecessors == 0);
   UpdatedPreds.insert(&LoopChain);
   for (MachineLoop::block_iterator BI = L.block_begin(),
                                    BE = L.block_end();
        BI != BE; ++BI) {
-    BlockChain &Chain = *BlockToChain[*BI];
+    BlockChain &Chain = *BlockToChain.lookup(*BI);
     if (!UpdatedPreds.insert(&Chain))
       continue;
 
     assert(Chain.LoopPredecessors == 0);
     for (BlockChain::iterator BCI = Chain.begin(), BCE = Chain.end();
          BCI != BCE; ++BCI) {
-      assert(BlockToChain[*BCI] == &Chain);
+      assert(BlockToChain.lookup(*BCI) == &Chain);
       for (MachineBasicBlock::pred_iterator PI = (*BCI)->pred_begin(),
                                             PE = (*BCI)->pred_end();
            PI != PE; ++PI) {
-        if (BlockToChain[*PI] == &Chain || !LoopBlockSet.count(*PI))
+        if (BlockToChain.lookup(*PI) == &Chain || !LoopBlockSet.count(*PI))
           continue;
         ++Chain.LoopPredecessors;
       }