Update LLVM to r86025.

18 files changed, 263 insertions, 136 deletions

diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp
index 35907fd..c728c0b 100644
--- a/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -65,9 +65,6 @@ void llvm::DeleteDeadBlock(BasicBlock *BB) {
 /// when all entries to the PHI nodes in a block are guaranteed equal, such as
 /// when the block has exactly one predecessor.
 void llvm::FoldSingleEntryPHINodes(BasicBlock *BB) {
-  if (!isa<PHINode>(BB->begin()))
-    return;
-  
   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
     if (PN->getIncomingValue(0) != PN)
       PN->replaceAllUsesWith(PN->getIncomingValue(0));
@@ -97,10 +94,14 @@ void llvm::DeleteDeadPHIs(BasicBlock *BB) {
 
 /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
 /// if possible.  The return value indicates success or failure.
-bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) {
+bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, Pass *P) {
   pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
-  // Can't merge the entry block.
-  if (pred_begin(BB) == pred_end(BB)) return false;
+  // Can't merge the entry block.  Don't merge away blocks who have their
+  // address taken: this is a bug if the predecessor block is the entry node
+  // (because we'd end up taking the address of the entry) and undesirable in
+  // any case.
+  if (pred_begin(BB) == pred_end(BB) ||
+      BB->hasAddressTaken()) return false;
   
   BasicBlock *PredBB = *PI++;
   for (; PI != PE; ++PI)  // Search all predecessors, see if they are all same
@@ -274,6 +275,8 @@ void llvm::RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum) {
 /// SplitEdge -  Split the edge connecting specified block. Pass P must 
 /// not be NULL. 
 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) {
+  assert(!isa<IndirectBrInst>(BB->getTerminator()) &&
+         "Cannot split an edge from an IndirectBrInst");
   TerminatorInst *LatchTerm = BB->getTerminator();
   unsigned SuccNum = 0;
 #ifndef NDEBUG
@@ -675,7 +678,7 @@ void llvm::CopyPrecedingStopPoint(Instruction *I,
   if (I != I->getParent()->begin()) {
     BasicBlock::iterator BBI = I;  --BBI;
     if (DbgStopPointInst *DSPI = dyn_cast<DbgStopPointInst>(BBI)) {
-      CallInst *newDSPI = DSPI->clone();
+      CallInst *newDSPI = cast<CallInst>(DSPI->clone());
       newDSPI->insertBefore(InsertPos);
     }
   }
diff --git a/lib/Transforms/Utils/BasicInliner.cpp b/lib/Transforms/Utils/BasicInliner.cpp
index 4b720b1..b5ffe06 100644
--- a/lib/Transforms/Utils/BasicInliner.cpp
+++ b/lib/Transforms/Utils/BasicInliner.cpp
@@ -34,7 +34,7 @@ namespace llvm {
 
   /// BasicInlinerImpl - BasicInliner implemantation class. This hides
   /// container info, used by basic inliner, from public interface.
-  struct VISIBILITY_HIDDEN BasicInlinerImpl {
+  struct BasicInlinerImpl {
     
     BasicInlinerImpl(const BasicInlinerImpl&); // DO NOT IMPLEMENT
     void operator=(const BasicInlinerImpl&); // DO NO IMPLEMENT
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index 849b2b5..ccd97c8 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -26,7 +26,6 @@
 #include "llvm/Instructions.h"
 #include "llvm/Type.h"
 #include "llvm/Support/CFG.h"
-#include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -35,7 +34,7 @@ using namespace llvm;
 STATISTIC(NumBroken, "Number of blocks inserted");
 
 namespace {
-  struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass {
+  struct BreakCriticalEdges : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     BreakCriticalEdges() : FunctionPass(&ID) {}
 
@@ -70,7 +69,7 @@ bool BreakCriticalEdges::runOnFunction(Function &F) {
   bool Changed = false;
   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
     TerminatorInst *TI = I->getTerminator();
-    if (TI->getNumSuccessors() > 1)
+    if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
         if (SplitCriticalEdge(TI, i, this)) {
           ++NumBroken;
@@ -151,14 +150,29 @@ static void CreatePHIsForSplitLoopExit(SmallVectorImpl<BasicBlock *> &Preds,
 
 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
 /// split the critical edge.  This will update DominatorTree and
-/// DominatorFrontier  information if it is available, thus calling this pass
-/// will not invalidate  any of them.  This returns true if the edge was split,
-/// false otherwise.  This ensures that all edges to that dest go to one block
-/// instead of each going to a different block.
-//
+/// DominatorFrontier information if it is available, thus calling this pass
+/// will not invalidate either of them. This returns the new block if the edge
+/// was split, null otherwise.
+///
+/// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
+/// specified successor will be merged into the same critical edge block.  
+/// This is most commonly interesting with switch instructions, which may 
+/// have many edges to any one destination.  This ensures that all edges to that
+/// dest go to one block instead of each going to a different block, but isn't 
+/// the standard definition of a "critical edge".
+///
+/// It is invalid to call this function on a critical edge that starts at an
+/// IndirectBrInst.  Splitting these edges will almost always create an invalid
+/// program because the address of the new block won't be the one that is jumped
+/// to.
+///
 BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
                                     Pass *P, bool MergeIdenticalEdges) {
   if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return 0;
+  
+  assert(!isa<IndirectBrInst>(TI) &&
+         "Cannot split critical edge from IndirectBrInst");
+  
   BasicBlock *TIBB = TI->getParent();
   BasicBlock *DestBB = TI->getSuccessor(SuccNum);
 
diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt
index f4394ea..93577b4 100644
--- a/lib/Transforms/Utils/CMakeLists.txt
+++ b/lib/Transforms/Utils/CMakeLists.txt
@@ -13,7 +13,7 @@ add_llvm_library(LLVMTransformUtils
   LCSSA.cpp
   Local.cpp
   LoopSimplify.cpp
-  LowerAllocations.cpp
+  LoopUnroll.cpp
   LowerInvoke.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
@@ -22,7 +22,6 @@ add_llvm_library(LLVMTransformUtils
   SSI.cpp
   SimplifyCFG.cpp
   UnifyFunctionExitNodes.cpp
-  UnrollLoop.cpp
   ValueMapper.cpp
   )
 
diff --git a/lib/Transforms/Utils/CloneFunction.cpp b/lib/Transforms/Utils/CloneFunction.cpp
index 30130fa..fd8862c 100644
--- a/lib/Transforms/Utils/CloneFunction.cpp
+++ b/lib/Transforms/Utils/CloneFunction.cpp
@@ -20,9 +20,7 @@
 #include "llvm/IntrinsicInst.h"
 #include "llvm/GlobalVariable.h"
 #include "llvm/Function.h"
-#include "llvm/LLVMContext.h"
 #include "llvm/Support/CFG.h"
-#include "llvm/Support/Compiler.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/DebugInfo.h"
@@ -176,7 +174,7 @@ Function *llvm::CloneFunction(const Function *F,
 namespace {
   /// PruningFunctionCloner - This class is a private class used to implement
   /// the CloneAndPruneFunctionInto method.
-  struct VISIBILITY_HIDDEN PruningFunctionCloner {
+  struct PruningFunctionCloner {
     Function *NewFunc;
     const Function *OldFunc;
     DenseMap<const Value*, Value*> &ValueMap;
@@ -329,8 +327,7 @@ ConstantFoldMappedInstruction(const Instruction *I) {
   SmallVector<Constant*, 8> Ops;
   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
     if (Constant *Op = dyn_cast_or_null<Constant>(MapValue(I->getOperand(i),
-                                                           ValueMap,
-                                                           Context)))
+                                                           ValueMap)))
       Ops.push_back(Op);
     else
       return 0;  // All operands not constant!
@@ -366,7 +363,6 @@ void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
                                      ClonedCodeInfo *CodeInfo,
                                      const TargetData *TD) {
   assert(NameSuffix && "NameSuffix cannot be null!");
-  LLVMContext &Context = OldFunc->getContext();
   
 #ifndef NDEBUG
   for (Function::const_arg_iterator II = OldFunc->arg_begin(), 
@@ -437,7 +433,7 @@ void llvm::CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
         if (BasicBlock *MappedBlock = 
             cast_or_null<BasicBlock>(ValueMap[PN->getIncomingBlock(pred)])) {
           Value *InVal = MapValue(PN->getIncomingValue(pred),
-                                  ValueMap, Context);
+                                  ValueMap);
           assert(InVal && "Unknown input value?");
           PN->setIncomingValue(pred, InVal);
           PN->setIncomingBlock(pred, MappedBlock);
diff --git a/lib/Transforms/Utils/CloneModule.cpp b/lib/Transforms/Utils/CloneModule.cpp
index 0285f8c..a163f89 100644
--- a/lib/Transforms/Utils/CloneModule.cpp
+++ b/lib/Transforms/Utils/CloneModule.cpp
@@ -89,8 +89,7 @@ Module *llvm::CloneModule(const Module *M,
     GlobalVariable *GV = cast<GlobalVariable>(ValueMap[I]);
     if (I->hasInitializer())
       GV->setInitializer(cast<Constant>(MapValue(I->getInitializer(),
-                                                 ValueMap,
-                                                 M->getContext())));
+                                                 ValueMap)));
     GV->setLinkage(I->getLinkage());
     GV->setThreadLocal(I->isThreadLocal());
     GV->setConstant(I->isConstant());
@@ -121,7 +120,7 @@ Module *llvm::CloneModule(const Module *M,
     GlobalAlias *GA = cast<GlobalAlias>(ValueMap[I]);
     GA->setLinkage(I->getLinkage());
     if (const Constant* C = I->getAliasee())
-      GA->setAliasee(cast<Constant>(MapValue(C, ValueMap, M->getContext())));
+      GA->setAliasee(cast<Constant>(MapValue(C, ValueMap)));
   }
   
   return New;
diff --git a/lib/Transforms/Utils/CodeExtractor.cpp b/lib/Transforms/Utils/CodeExtractor.cpp
index c39ccf7..f966681 100644
--- a/lib/Transforms/Utils/CodeExtractor.cpp
+++ b/lib/Transforms/Utils/CodeExtractor.cpp
@@ -26,7 +26,6 @@
 #include "llvm/Analysis/Verifier.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
@@ -44,7 +43,7 @@ AggregateArgsOpt("aggregate-extracted-args", cl::Hidden,
                  cl::desc("Aggregate arguments to code-extracted functions"));
 
 namespace {
-  class VISIBILITY_HIDDEN CodeExtractor {
+  class CodeExtractor {
     typedef std::vector<Value*> Values;
     std::set<BasicBlock*> BlocksToExtract;
     DominatorTree* DT;
diff --git a/lib/Transforms/Utils/InlineFunction.cpp b/lib/Transforms/Utils/InlineFunction.cpp
index 619c939..20f5a4a 100644
--- a/lib/Transforms/Utils/InlineFunction.cpp
+++ b/lib/Transforms/Utils/InlineFunction.cpp
@@ -619,8 +619,17 @@ bool llvm::InlineFunction(CallSite CS, CallGraph *CG, const TargetData *TD,
                "Ret value not consistent in function!");
         PHI->addIncoming(RI->getReturnValue(), RI->getParent());
       }
+    
+      // Now that we inserted the PHI, check to see if it has a single value
+      // (e.g. all the entries are the same or undef).  If so, remove the PHI so
+      // it doesn't block other optimizations.
+      if (Value *V = PHI->hasConstantValue()) {
+        PHI->replaceAllUsesWith(V);
+        PHI->eraseFromParent();
+      }
     }
 
+
     // Add a branch to the merge points and remove return instructions.
     for (unsigned i = 0, e = Returns.size(); i != e; ++i) {
       ReturnInst *RI = Returns[i];
diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp
index b622611..543ddf1 100644
--- a/lib/Transforms/Utils/Local.cpp
+++ b/lib/Transforms/Utils/Local.cpp
@@ -59,9 +59,8 @@ bool llvm::isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) {
 
     // If we see a free or a call which may write to memory (i.e. which might do
     // a free) the pointer could be marked invalid.
-    if (isa<FreeInst>(BBI) || 
-        (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&
-         !isa<DbgInfoIntrinsic>(BBI)))
+    if (isa<CallInst>(BBI) && BBI->mayWriteToMemory() &&
+        !isa<DbgInfoIntrinsic>(BBI))
       return false;
 
     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
@@ -110,7 +109,9 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
       // unconditional branch.
       BI->setUnconditionalDest(Destination);
       return true;
-    } else if (Dest2 == Dest1) {       // Conditional branch to same location?
+    }
+    
+    if (Dest2 == Dest1) {       // Conditional branch to same location?
       // This branch matches something like this:
       //     br bool %cond, label %Dest, label %Dest
       // and changes it into:  br label %Dest
@@ -123,7 +124,10 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
       BI->setUnconditionalDest(Dest1);
       return true;
     }
-  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
+    return false;
+  }
+  
+  if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
     // If we are switching on a constant, we can convert the switch into a
     // single branch instruction!
     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
@@ -132,7 +136,7 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
     assert(TheOnlyDest == SI->getDefaultDest() &&
            "Default destination is not successor #0?");
 
-    // Figure out which case it goes to...
+    // Figure out which case it goes to.
     for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
       // Found case matching a constant operand?
       if (SI->getSuccessorValue(i) == CI) {
@@ -143,7 +147,7 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
       // Check to see if this branch is going to the same place as the default
       // dest.  If so, eliminate it as an explicit compare.
       if (SI->getSuccessor(i) == DefaultDest) {
-        // Remove this entry...
+        // Remove this entry.
         DefaultDest->removePredecessor(SI->getParent());
         SI->removeCase(i);
         --i; --e;  // Don't skip an entry...
@@ -165,7 +169,7 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
     // If we found a single destination that we can fold the switch into, do so
     // now.
     if (TheOnlyDest) {
-      // Insert the new branch..
+      // Insert the new branch.
       BranchInst::Create(TheOnlyDest, SI);
       BasicBlock *BB = SI->getParent();
 
@@ -179,22 +183,54 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB) {
           Succ->removePredecessor(BB);
       }
 
-      // Delete the old switch...
+      // Delete the old switch.
       BB->getInstList().erase(SI);
       return true;
-    } else if (SI->getNumSuccessors() == 2) {
+    }
+    
+    if (SI->getNumSuccessors() == 2) {
       // Otherwise, we can fold this switch into a conditional branch
       // instruction if it has only one non-default destination.
       Value *Cond = new ICmpInst(SI, ICmpInst::ICMP_EQ, SI->getCondition(),
                                  SI->getSuccessorValue(1), "cond");
-      // Insert the new branch...
+      // Insert the new branch.
       BranchInst::Create(SI->getSuccessor(1), SI->getSuccessor(0), Cond, SI);
 
-      // Delete the old switch...
+      // Delete the old switch.
       SI->eraseFromParent();
       return true;
     }
+    return false;
   }
+
+  if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
+    // indirectbr blockaddress(@F, @BB) -> br label @BB
+    if (BlockAddress *BA =
+          dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
+      BasicBlock *TheOnlyDest = BA->getBasicBlock();
+      // Insert the new branch.
+      BranchInst::Create(TheOnlyDest, IBI);
+      
+      for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
+        if (IBI->getDestination(i) == TheOnlyDest)
+          TheOnlyDest = 0;
+        else
+          IBI->getDestination(i)->removePredecessor(IBI->getParent());
+      }
+      IBI->eraseFromParent();
+      
+      // If we didn't find our destination in the IBI successor list, then we
+      // have undefined behavior.  Replace the unconditional branch with an
+      // 'unreachable' instruction.
+      if (TheOnlyDest) {
+        BB->getTerminator()->eraseFromParent();
+        new UnreachableInst(BB->getContext(), BB);
+      }
+      
+      return true;
+    }
+  }
+  
   return false;
 }
 
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index c22708a..cd8d952 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -46,7 +46,6 @@
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Support/CFG.h"
-#include "llvm/Support/Compiler.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -57,7 +56,7 @@ STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
 STATISTIC(NumNested  , "Number of nested loops split out");
 
 namespace {
-  struct VISIBILITY_HIDDEN LoopSimplify : public LoopPass {
+  struct LoopSimplify : public LoopPass {
     static char ID; // Pass identification, replacement for typeid
     LoopSimplify() : LoopPass(&ID) {}
 
diff --git a/lib/Transforms/Utils/UnrollLoop.cpp b/lib/Transforms/Utils/LoopUnroll.cpp
index 4d838b5..d68427a 100644
--- a/lib/Transforms/Utils/UnrollLoop.cpp
+++ b/lib/Transforms/Utils/LoopUnroll.cpp
@@ -44,8 +44,8 @@ static inline void RemapInstruction(Instruction *I,
   for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
     Value *Op = I->getOperand(op);
     DenseMap<const Value *, Value*>::iterator It = ValueMap.find(Op);
-    if (It != ValueMap.end()) Op = It->second;
-    I->setOperand(op, Op);
+    if (It != ValueMap.end())
+      I->setOperand(op, It->second);
   }
 }
 
diff --git a/lib/Transforms/Utils/LowerInvoke.cpp b/lib/Transforms/Utils/LowerInvoke.cpp
index 9a3de26..6e6e8d2 100644
--- a/lib/Transforms/Utils/LowerInvoke.cpp
+++ b/lib/Transforms/Utils/LowerInvoke.cpp
@@ -47,7 +47,6 @@
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Compiler.h"
 #include "llvm/Target/TargetLowering.h"
 #include <csetjmp>
 #include <set>
@@ -61,7 +60,7 @@ static cl::opt<bool> ExpensiveEHSupport("enable-correct-eh-support",
  cl::desc("Make the -lowerinvoke pass insert expensive, but correct, EH code"));
 
 namespace {
-  class VISIBILITY_HIDDEN LowerInvoke : public FunctionPass {
+  class LowerInvoke : public FunctionPass {
     // Used for both models.
     Constant *WriteFn;
     Constant *AbortFn;
@@ -87,7 +86,6 @@ namespace {
       // This is a cluster of orthogonal Transforms
       AU.addPreservedID(PromoteMemoryToRegisterID);
       AU.addPreservedID(LowerSwitchID);
-      AU.addPreservedID(LowerAllocationsID);
     }
 
   private:
diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp
index 764f098..8c18b59 100644
--- a/lib/Transforms/Utils/LowerSwitch.cpp
+++ b/lib/Transforms/Utils/LowerSwitch.cpp
@@ -21,8 +21,8 @@
 #include "llvm/LLVMContext.h"
 #include "llvm/Pass.h"
 #include "llvm/ADT/STLExtras.h"
-#include "llvm/Support/Debug.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 using namespace llvm;
@@ -31,7 +31,7 @@ namespace {
   /// LowerSwitch Pass - Replace all SwitchInst instructions with chained branch
   /// instructions.  Note that this cannot be a BasicBlock pass because it
   /// modifies the CFG!
-  class VISIBILITY_HIDDEN LowerSwitch : public FunctionPass {
+  class LowerSwitch : public FunctionPass {
   public:
     static char ID; // Pass identification, replacement for typeid
     LowerSwitch() : FunctionPass(&ID) {} 
@@ -43,7 +43,6 @@ namespace {
       AU.addPreserved<UnifyFunctionExitNodes>();
       AU.addPreservedID(PromoteMemoryToRegisterID);
       AU.addPreservedID(LowerInvokePassID);
-      AU.addPreservedID(LowerAllocationsID);
     }
 
     struct CaseRange {
diff --git a/lib/Transforms/Utils/Mem2Reg.cpp b/lib/Transforms/Utils/Mem2Reg.cpp
index 5df0832..9416604 100644
--- a/lib/Transforms/Utils/Mem2Reg.cpp
+++ b/lib/Transforms/Utils/Mem2Reg.cpp
@@ -20,13 +20,12 @@
 #include "llvm/Instructions.h"
 #include "llvm/Function.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/Support/Compiler.h"
 using namespace llvm;
 
 STATISTIC(NumPromoted, "Number of alloca's promoted");
 
 namespace {
-  struct VISIBILITY_HIDDEN PromotePass : public FunctionPass {
+  struct PromotePass : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     PromotePass() : FunctionPass(&ID) {}
 
@@ -45,7 +44,6 @@ namespace {
       AU.addPreserved<UnifyFunctionExitNodes>();
       AU.addPreservedID(LowerSwitchID);
       AU.addPreservedID(LowerInvokePassID);
-      AU.addPreservedID(LowerAllocationsID);
     }
   };
 }  // end of anonymous namespace
diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
index 9ca06bd..de6ad1d 100644
--- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
+++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp
@@ -32,7 +32,6 @@
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CFG.h"
-#include "llvm/Support/Compiler.h"
 #include <algorithm>
 using namespace llvm;
 
@@ -100,7 +99,7 @@ namespace {
   struct AllocaInfo;
 
   // Data package used by RenamePass()
-  class VISIBILITY_HIDDEN RenamePassData {
+  class RenamePassData {
   public:
     typedef std::vector<Value *> ValVector;
     
@@ -123,7 +122,7 @@ namespace {
   ///
   /// This functionality is important because it avoids scanning large basic
   /// blocks multiple times when promoting many allocas in the same block.
-  class VISIBILITY_HIDDEN LargeBlockInfo {
+  class LargeBlockInfo {
     /// InstNumbers - For each instruction that we track, keep the index of the
     /// instruction.  The index starts out as the number of the instruction from
     /// the start of the block.
@@ -170,7 +169,7 @@ namespace {
     }
   };
 
-  struct VISIBILITY_HIDDEN PromoteMem2Reg {
+  struct PromoteMem2Reg {
     /// Allocas - The alloca instructions being promoted.
     ///
     std::vector<AllocaInst*> Allocas;
@@ -750,7 +749,12 @@ void PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI,
     }
     
     // Otherwise, we *can* safely rewrite this load.
-    LI->replaceAllUsesWith(OnlyStore->getOperand(0));
+    Value *ReplVal = OnlyStore->getOperand(0);
+    // If the replacement value is the load, this must occur in unreachable
+    // code.
+    if (ReplVal == LI)
+      ReplVal = UndefValue::get(LI->getType());
+    LI->replaceAllUsesWith(ReplVal);
     if (AST && isa<PointerType>(LI->getType()))
       AST->deleteValue(LI);
     LI->eraseFromParent();
diff --git a/lib/Transforms/Utils/SSI.cpp b/lib/Transforms/Utils/SSI.cpp
index 3bb2e8e..1c4afff 100644
--- a/lib/Transforms/Utils/SSI.cpp
+++ b/lib/Transforms/Utils/SSI.cpp
@@ -396,7 +396,7 @@ static RegisterPass<SSI> X("ssi", "Static Single Information Construction");
 /// SSIEverything - A pass that runs createSSI on every non-void variable,
 /// intended for debugging.
 namespace {
-  struct VISIBILITY_HIDDEN SSIEverything : public FunctionPass {
+  struct SSIEverything : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     SSIEverything() : FunctionPass(&ID) {}
 
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 6fd7d7b..8e1fb98 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -24,6 +24,7 @@
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
@@ -1748,6 +1749,68 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) {
   return true;
 }
 
+/// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
+/// nodes in this block. This doesn't try to be clever about PHI nodes
+/// which differ only in the order of the incoming values, but instcombine
+/// orders them so it usually won't matter.
+///
+static bool EliminateDuplicatePHINodes(BasicBlock *BB) {
+  bool Changed = false;
+  
+  // This implementation doesn't currently consider undef operands
+  // specially. Theroetically, two phis which are identical except for
+  // one having an undef where the other doesn't could be collapsed.
+
+  // Map from PHI hash values to PHI nodes. If multiple PHIs have
+  // the same hash value, the element is the first PHI in the
+  // linked list in CollisionMap.
+  DenseMap<uintptr_t, PHINode *> HashMap;
+
+  // Maintain linked lists of PHI nodes with common hash values.
+  DenseMap<PHINode *, PHINode *> CollisionMap;
+
+  // Examine each PHI.
+  for (BasicBlock::iterator I = BB->begin();
+       PHINode *PN = dyn_cast<PHINode>(I++); ) {
+    // Compute a hash value on the operands. Instcombine will likely have sorted
+    // them, which helps expose duplicates, but we have to check all the
+    // operands to be safe in case instcombine hasn't run.
+    uintptr_t Hash = 0;
+    for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) {
+      // This hash algorithm is quite weak as hash functions go, but it seems
+      // to do a good enough job for this particular purpose, and is very quick.
+      Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I));
+      Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
+    }
+    // If we've never seen this hash value before, it's a unique PHI.
+    std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair =
+      HashMap.insert(std::make_pair(Hash, PN));
+    if (Pair.second) continue;
+    // Otherwise it's either a duplicate or a hash collision.
+    for (PHINode *OtherPN = Pair.first->second; ; ) {
+      if (OtherPN->isIdenticalTo(PN)) {
+        // A duplicate. Replace this PHI with its duplicate.
+        PN->replaceAllUsesWith(OtherPN);
+        PN->eraseFromParent();
+        Changed = true;
+        break;
+      }
+      // A non-duplicate hash collision.
+      DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN);
+      if (I == CollisionMap.end()) {
+        // Set this PHI to be the head of the linked list of colliding PHIs.
+        PHINode *Old = Pair.first->second;
+        Pair.first->second = PN;
+        CollisionMap[PN] = Old;
+        break;
+      }
+      // Procede to the next PHI in the list.
+      OtherPN = I->second;
+    }
+  }
+
+  return Changed;
+}
 
 /// SimplifyCFG - This function is used to do simplification of a CFG.  For
 /// example, it adjusts branches to branches to eliminate the extra hop, it
@@ -1777,6 +1840,9 @@ bool llvm::SimplifyCFG(BasicBlock *BB) {
   // away...
   Changed |= ConstantFoldTerminator(BB);
 
+  // Check for and eliminate duplicate PHI nodes in this block.
+  Changed |= EliminateDuplicatePHINodes(BB);
+
   // If there is a trivial two-entry PHI node in this basic block, and we can
   // eliminate it, do so now.
   if (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
diff --git a/lib/Transforms/Utils/ValueMapper.cpp b/lib/Transforms/Utils/ValueMapper.cpp
index 2d8332f..39331d7 100644
--- a/lib/Transforms/Utils/ValueMapper.cpp
+++ b/lib/Transforms/Utils/ValueMapper.cpp
@@ -13,18 +13,15 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/ValueMapper.h"
-#include "llvm/BasicBlock.h"
 #include "llvm/DerivedTypes.h"  // For getNullValue(Type::Int32Ty)
 #include "llvm/Constants.h"
-#include "llvm/GlobalValue.h"
-#include "llvm/Instruction.h"
-#include "llvm/LLVMContext.h"
+#include "llvm/Function.h"
 #include "llvm/Metadata.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/ErrorHandling.h"
 using namespace llvm;
 
-Value *llvm::MapValue(const Value *V, ValueMapTy &VM, LLVMContext &Context) {
+Value *llvm::MapValue(const Value *V, ValueMapTy &VM) {
   Value *&VMSlot = VM[V];
   if (VMSlot) return VMSlot;      // Does it exist in the map yet?
   
@@ -36,80 +33,91 @@ Value *llvm::MapValue(const Value *V, ValueMapTy &VM, LLVMContext &Context) {
   if (isa<GlobalValue>(V) || isa<InlineAsm>(V) || isa<MetadataBase>(V))
     return VMSlot = const_cast<Value*>(V);
 
-  if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) {
-    if (isa<ConstantInt>(C) || isa<ConstantFP>(C) ||
-        isa<ConstantPointerNull>(C) || isa<ConstantAggregateZero>(C) ||
-        isa<UndefValue>(C) || isa<MDString>(C))
-      return VMSlot = C;           // Primitive constants map directly
-    else if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
-      for (User::op_iterator b = CA->op_begin(), i = b, e = CA->op_end();
-           i != e; ++i) {
-        Value *MV = MapValue(*i, VM, Context);
-        if (MV != *i) {
-          // This array must contain a reference to a global, make a new array
-          // and return it.
-          //
-          std::vector<Constant*> Values;
-          Values.reserve(CA->getNumOperands());
-          for (User::op_iterator j = b; j != i; ++j)
-            Values.push_back(cast<Constant>(*j));
-          Values.push_back(cast<Constant>(MV));
-          for (++i; i != e; ++i)
-            Values.push_back(cast<Constant>(MapValue(*i, VM, Context)));
-          return VM[V] = ConstantArray::get(CA->getType(), Values);
-        }
+  Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V));
+  if (C == 0) return 0;
+  
+  if (isa<ConstantInt>(C) || isa<ConstantFP>(C) ||
+      isa<ConstantPointerNull>(C) || isa<ConstantAggregateZero>(C) ||
+      isa<UndefValue>(C) || isa<MDString>(C))
+    return VMSlot = C;           // Primitive constants map directly
+  
+  if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
+    for (User::op_iterator b = CA->op_begin(), i = b, e = CA->op_end();
+         i != e; ++i) {
+      Value *MV = MapValue(*i, VM);
+      if (MV != *i) {
+        // This array must contain a reference to a global, make a new array
+        // and return it.
+        //
+        std::vector<Constant*> Values;
+        Values.reserve(CA->getNumOperands());
+        for (User::op_iterator j = b; j != i; ++j)
+          Values.push_back(cast<Constant>(*j));
+        Values.push_back(cast<Constant>(MV));
+        for (++i; i != e; ++i)
+          Values.push_back(cast<Constant>(MapValue(*i, VM)));
+        return VM[V] = ConstantArray::get(CA->getType(), Values);
       }
-      return VM[V] = C;
-
-    } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
-      for (User::op_iterator b = CS->op_begin(), i = b, e = CS->op_end();
-           i != e; ++i) {
-        Value *MV = MapValue(*i, VM, Context);
-        if (MV != *i) {
-          // This struct must contain a reference to a global, make a new struct
-          // and return it.
-          //
-          std::vector<Constant*> Values;
-          Values.reserve(CS->getNumOperands());
-          for (User::op_iterator j = b; j != i; ++j)
-            Values.push_back(cast<Constant>(*j));
-          Values.push_back(cast<Constant>(MV));
-          for (++i; i != e; ++i)
-            Values.push_back(cast<Constant>(MapValue(*i, VM, Context)));
-          return VM[V] = ConstantStruct::get(CS->getType(), Values);
-        }
+    }
+    return VM[V] = C;
+  }
+  
+  if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
+    for (User::op_iterator b = CS->op_begin(), i = b, e = CS->op_end();
+         i != e; ++i) {
+      Value *MV = MapValue(*i, VM);
+      if (MV != *i) {
+        // This struct must contain a reference to a global, make a new struct
+        // and return it.
+        //
+        std::vector<Constant*> Values;
+        Values.reserve(CS->getNumOperands());
+        for (User::op_iterator j = b; j != i; ++j)
+          Values.push_back(cast<Constant>(*j));
+        Values.push_back(cast<Constant>(MV));
+        for (++i; i != e; ++i)
+          Values.push_back(cast<Constant>(MapValue(*i, VM)));
+        return VM[V] = ConstantStruct::get(CS->getType(), Values);
       }
-      return VM[V] = C;
-
-    } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
-      std::vector<Constant*> Ops;
-      for (User::op_iterator i = CE->op_begin(), e = CE->op_end(); i != e; ++i)
-        Ops.push_back(cast<Constant>(MapValue(*i, VM, Context)));
-      return VM[V] = CE->getWithOperands(Ops);
-    } else if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) {
-      for (User::op_iterator b = CP->op_begin(), i = b, e = CP->op_end();
-           i != e; ++i) {
-        Value *MV = MapValue(*i, VM, Context);
-        if (MV != *i) {
-          // This vector value must contain a reference to a global, make a new
-          // vector constant and return it.
-          //
-          std::vector<Constant*> Values;
-          Values.reserve(CP->getNumOperands());
-          for (User::op_iterator j = b; j != i; ++j)
-            Values.push_back(cast<Constant>(*j));
-          Values.push_back(cast<Constant>(MV));
-          for (++i; i != e; ++i)
-            Values.push_back(cast<Constant>(MapValue(*i, VM, Context)));
-          return VM[V] = ConstantVector::get(Values);
-        }
+    }
+    return VM[V] = C;
+  }
+  
+  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
+    std::vector<Constant*> Ops;
+    for (User::op_iterator i = CE->op_begin(), e = CE->op_end(); i != e; ++i)
+      Ops.push_back(cast<Constant>(MapValue(*i, VM)));
+    return VM[V] = CE->getWithOperands(Ops);
+  }
+  
+  if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
+    for (User::op_iterator b = CV->op_begin(), i = b, e = CV->op_end();
+         i != e; ++i) {
+      Value *MV = MapValue(*i, VM);
+      if (MV != *i) {
+        // This vector value must contain a reference to a global, make a new
+        // vector constant and return it.
+        //
+        std::vector<Constant*> Values;
+        Values.reserve(CV->getNumOperands());
+        for (User::op_iterator j = b; j != i; ++j)
+          Values.push_back(cast<Constant>(*j));
+        Values.push_back(cast<Constant>(MV));
+        for (++i; i != e; ++i)
+          Values.push_back(cast<Constant>(MapValue(*i, VM)));
+        return VM[V] = ConstantVector::get(Values);
       }
-      return VM[V] = C;
-      
-    } else {
-      llvm_unreachable("Unknown type of constant!");
     }
+    return VM[V] = C;
   }
+  
+  if (BlockAddress *BA = dyn_cast<BlockAddress>(C)) {
+    Function *F = cast<Function>(MapValue(BA->getFunction(), VM));
+    BasicBlock *BB = cast_or_null<BasicBlock>(MapValue(BA->getBasicBlock(),VM));
+    return VM[V] = BlockAddress::get(F, BB ? BB : BA->getBasicBlock());
+  }
+  
+  llvm_unreachable("Unknown type of constant!");
   return 0;
 }
 
@@ -118,7 +126,7 @@ Value *llvm::MapValue(const Value *V, ValueMapTy &VM, LLVMContext &Context) {
 ///
 void llvm::RemapInstruction(Instruction *I, ValueMapTy &ValueMap) {
   for (User::op_iterator op = I->op_begin(), E = I->op_end(); op != E; ++op) {
-    Value *V = MapValue(*op, ValueMap, I->getParent()->getContext());
+    Value *V = MapValue(*op, ValueMap);
     assert(V && "Referenced value not in value map!");
     *op = V;
   }