Restore minor deletion.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70892 91177308-0d34-0410-b5e6-96231b3b80d8

12 files changed, 255 insertions, 208 deletions

diff --git a/lib/Analysis/CaptureTracking.cpp b/lib/Analysis/CaptureTracking.cpp
index ceb9646..773f53d 100644
--- a/lib/Analysis/CaptureTracking.cpp
+++ b/lib/Analysis/CaptureTracking.cpp
@@ -49,11 +49,7 @@ bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) {
     switch (I->getOpcode()) {
     case Instruction::Call:
     case Instruction::Invoke: {
-      CallSite CS = CallSite::get(I);
-      // Not captured if the callee is readonly and doesn't return a copy
-      // through its return value.
-      if (CS.onlyReadsMemory() && I->getType() == Type::VoidTy)
-        break;
+      CallSite CS(I);
 
       // Not captured if only passed via 'nocapture' arguments.  Note that
       // calling a function pointer does not in itself cause the pointer to
@@ -62,46 +58,69 @@ bool llvm::PointerMayBeCaptured(const Value *V, bool ReturnCaptures) {
       // that loading a value from a pointer does not cause the pointer to be
       // captured, even though the loaded value might be the pointer itself
       // (think of self-referential objects).
+      bool MayBeCaptured = false;
       CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
       for (CallSite::arg_iterator A = B; A != E; ++A)
-        if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture))
-          // The parameter is not marked 'nocapture' - captured.
-          return true;
-      // Only passed via 'nocapture' arguments, or is the called function - not
-      // captured.
+        if (A->get() == V && !CS.paramHasAttr(A-B+1, Attribute::NoCapture)) {
+          // The parameter is not marked 'nocapture' - handled by generic code
+          // below.
+          MayBeCaptured = true;
+          break;
+        }
+      if (!MayBeCaptured)
+        // Only passed via 'nocapture' arguments, or is the called function -
+        // not captured.
+        continue;
+      if (!CS.doesNotThrow())
+        // Even a readonly function can leak bits by throwing an exception or
+        // not depending on the input value.
+        return true;
+      // Fall through to the generic code.
       break;
     }
     case Instruction::Free:
       // Freeing a pointer does not cause it to be captured.
-      break;
+      continue;
     case Instruction::Load:
       // Loading from a pointer does not cause it to be captured.
-      break;
+      continue;
     case Instruction::Ret:
       if (ReturnCaptures)
         return true;
-      break;
+      continue;
     case Instruction::Store:
       if (V == I->getOperand(0))
         // Stored the pointer - it may be captured.
         return true;
       // Storing to the pointee does not cause the pointer to be captured.
-      break;
-    case Instruction::BitCast:
-    case Instruction::GetElementPtr:
-    case Instruction::PHI:
-    case Instruction::Select:
-      // The original value is not captured via this if the new value isn't.
-      for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
-           UI != UE; ++UI) {
-        Use *U = &UI.getUse();
-        if (Visited.insert(U))
-          Worklist.push_back(U);
-      }
-      break;
-    default:
-      // Something else - be conservative and say it is captured.
+      continue;
+    }
+
+    // If it may write to memory and isn't one of the special cases above,
+    // be conservative and assume the pointer is captured.
+    if (I->mayWriteToMemory())
       return true;
+
+    // If the instruction doesn't write memory, it can only capture by
+    // having its own value depend on the input value.
+    const Type* Ty = I->getType();
+    if (Ty == Type::VoidTy)
+      // The value of an instruction can't be a copy if it can't contain any
+      // information.
+      continue;
+    if (!isa<PointerType>(Ty))
+      // At the moment, we don't track non-pointer values, so be conservative
+      // and assume the pointer is captured.
+      // FIXME: Track these too.  This would need to be done very carefully as
+      // it is easy to leak bits via control flow if integer values are allowed.
+      return true;
+
+    // The original value is not captured via this if the new value isn't.
+    for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
+         UI != UE; ++UI) {
+      Use *U = &UI.getUse();
+      if (Visited.insert(U))
+        Worklist.push_back(U);
     }
   }
 
diff --git a/lib/CodeGen/AsmPrinter/DwarfWriter.cpp b/lib/CodeGen/AsmPrinter/DwarfWriter.cpp
index 848f45e..8ca8590 100644
--- a/lib/CodeGen/AsmPrinter/DwarfWriter.cpp
+++ b/lib/CodeGen/AsmPrinter/DwarfWriter.cpp
@@ -3262,11 +3262,12 @@ public:
     // Assumes in correct section after the entry point.
     EmitLabel("func_begin", ++SubprogramCount);
 
-    // Emit label for the implicitly defined dbg.stoppoint at the start of
-    // the function.
-    if (!Lines.empty()) {
-      const SrcLineInfo &LineInfo = Lines[0];
-      Asm->printLabel(LineInfo.getLabelID());
+    DebugLoc FDL = MF->getDefaultDebugLoc();
+    if (!FDL.isUnknown()) {
+      DebugLocTuple DLT = MF->getDebugLocTuple(FDL);
+      unsigned LabelID = RecordSourceLine(DLT.Line, DLT.Col,
+                                          DICompileUnit(DLT.CompileUnit));
+      Asm->printLabel(LabelID);
     }
 
     if (TimePassesIsEnabled)
diff --git a/lib/CodeGen/SelectionDAG/FastISel.cpp b/lib/CodeGen/SelectionDAG/FastISel.cpp
index afcda1f..f710051 100644
--- a/lib/CodeGen/SelectionDAG/FastISel.cpp
+++ b/lib/CodeGen/SelectionDAG/FastISel.cpp
@@ -333,11 +333,6 @@ bool FastISel::SelectCall(User *I) {
       unsigned Col = SPI->getColumn();
       unsigned Idx = MF.getOrCreateDebugLocID(CU.getGV(), Line, Col);
       setCurDebugLoc(DebugLoc::get(Idx));
-      if (DW && DW->ShouldEmitDwarfDebug()) {
-        unsigned ID = DW->RecordSourceLine(Line, Col, CU);
-        const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL);
-        BuildMI(MBB, DL, II).addImm(ID);
-      }
     }
     return true;
   }
@@ -402,7 +397,7 @@ bool FastISel::SelectCall(User *I) {
                                               CompileUnit.getGV(), Line, 0)));
 
       if (DW && DW->ShouldEmitDwarfDebug()) {
-        unsigned LabelID = DW->RecordSourceLine(Line, 0, CompileUnit);
+        unsigned LabelID = MMI->NextLabelID();
         const TargetInstrDesc &II = TII.get(TargetInstrInfo::DBG_LABEL);
         BuildMI(MBB, DL, II).addImm(LabelID);
         DebugLocTuple PrevLocTpl = MF.getDebugLocTuple(PrevLoc);
@@ -414,10 +409,9 @@ bool FastISel::SelectCall(User *I) {
     } else {
       // Record the source line.
       unsigned Line = Subprogram.getLineNumber();
-      setCurDebugLoc(DebugLoc::get(MF.getOrCreateDebugLocID(
+      MF.setDefaultDebugLoc(DebugLoc::get(MF.getOrCreateDebugLocID(
                                               CompileUnit.getGV(), Line, 0)));
       if (DW && DW->ShouldEmitDwarfDebug()) {
-        DW->RecordSourceLine(Line, 0, CompileUnit);
         // llvm.dbg.func_start also defines beginning of function scope.
         DW->RecordRegionStart(cast<GlobalVariable>(FSI->getSubprogram()));
       }
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
index acdb043..fc45bbd 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp
@@ -3980,7 +3980,7 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
                      MF.getOrCreateDebugLocID(CompileUnit.getGV(), Line, 0)));
 
         if (DW && DW->ShouldEmitDwarfDebug()) {
-          unsigned LabelID = DW->RecordSourceLine(Line, 0, CompileUnit);
+          unsigned LabelID = DAG.getMachineModuleInfo()->NextLabelID();
           DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getCurDebugLoc(),
                                    getRoot(), LabelID));
           DebugLocTuple PrevLocTpl = MF.getDebugLocTuple(PrevLoc);
@@ -3992,10 +3992,9 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) {
       } else {
         // Record the source line.
         unsigned Line = Subprogram.getLineNumber();
-        setCurDebugLoc(DebugLoc::get(
+        MF.setDefaultDebugLoc(DebugLoc::get(
                      MF.getOrCreateDebugLocID(CompileUnit.getGV(), Line, 0)));
         if (DW && DW->ShouldEmitDwarfDebug()) {
-          DW->RecordSourceLine(Line, 0, CompileUnit);
           // llvm.dbg.func_start also defines beginning of function scope.
           DW->RecordRegionStart(cast<GlobalVariable>(FSI.getSubprogram()));
         }
diff --git a/lib/CodeGen/StackSlotColoring.cpp b/lib/CodeGen/StackSlotColoring.cpp
index 6406b1c..dd36bdd 100644
--- a/lib/CodeGen/StackSlotColoring.cpp
+++ b/lib/CodeGen/StackSlotColoring.cpp
@@ -232,61 +232,54 @@ StackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping,
     int SS = li->getStackSlotIndex();
     if (!UsedColors[SS])
       continue;
-    // Get the largest common sub- register class of all the stack slots that
-    // are colored to this stack slot.
-    const TargetRegisterClass *RC = 0;
-    for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) {
-      int RSS = RevMap[SS][j];
-      const TargetRegisterClass *RRC = LS->getIntervalRegClass(RSS);
-      if (!RC)
-        RC = RRC;
-      else
-        RC = getCommonSubClass(RC, RRC);
-    }
 
-    // If it's not colored to another stack slot, try coloring it
-    // to a "free" register.
-    if (!RC)
-      continue;
-    unsigned Reg = VRM->getFirstUnusedRegister(RC);
-    if (!Reg)
-      continue;
-    bool IsSafe = true;
+    // These slots allow to share the same registers.
+    bool AllColored = true;
+    SmallVector<unsigned, 4> ColoredRegs;
     for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) {
       int RSS = RevMap[SS][j];
+      const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS);
+      // If it's not colored to another stack slot, try coloring it
+      // to a "free" register.
+      if (!RC) {
+        AllColored = false;
+        continue;
+      }
+      unsigned Reg = VRM->getFirstUnusedRegister(RC);
+      if (!Reg) {
+        AllColored = false;
+        continue;
+      }
       if (!AllMemRefsCanBeUnfolded(RSS)) {
-        IsSafe = false;
-        break;
+        AllColored = false;
+        continue;
+      } else {
+        DOUT << "Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n';
+        ColoredRegs.push_back(Reg);
+        SlotMapping[RSS] = Reg;
+        SlotIsReg.set(RSS);
+        Changed = true;
       }
     }
-    if (!IsSafe)
-      // Try color the next spill slot.
-      continue;
 
-    DOUT << "Assigning fi#" << SS << " to " << TRI->getName(Reg)
-         << ", which in turn means...\n";
     // Register and its sub-registers are no longer free.
-    VRM->setRegisterUsed(Reg);
-    // If reg is a callee-saved register, it will have to be spilled in
-    // the prologue.
-    MRI->setPhysRegUsed(Reg);
-    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
-      VRM->setRegisterUsed(*AS);
-      MRI->setPhysRegUsed(*AS);
+    while (!ColoredRegs.empty()) {
+      unsigned Reg = ColoredRegs.back();
+      ColoredRegs.pop_back();
+      VRM->setRegisterUsed(Reg);
+      // If reg is a callee-saved register, it will have to be spilled in
+      // the prologue.
+      MRI->setPhysRegUsed(Reg);
+      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
+        VRM->setRegisterUsed(*AS);
+        MRI->setPhysRegUsed(*AS);
+      }
     }
     // This spill slot is dead after the rewrites
-    MFI->RemoveStackObject(SS);
-
-    // Remember all these FI references will have to be unfolded.
-    for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) {
-      int RSS = RevMap[SS][j];
-      DOUT << "  Assigning fi#" << RSS << " to " << TRI->getName(Reg) << '\n';
-      SlotMapping[RSS] = Reg;
-      SlotIsReg.set(RSS);
+    if (AllColored) {
+      MFI->RemoveStackObject(SS);
+      ++NumEliminated;
     }
-
-    ++NumEliminated;
-    Changed = true;
   }
   DOUT << '\n';
 
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index f2f6ab0..29637b9 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -26,6 +26,7 @@
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
@@ -51,6 +52,7 @@ X("virtregmap", "Virtual Register Map");
 
 bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
   TII = mf.getTarget().getInstrInfo();
+  TRI = mf.getTarget().getRegisterInfo();
   MF = &mf;
   
   ReMatId = MAX_STACK_SLOT+1;
@@ -73,6 +75,13 @@ bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
   SpillSlotToUsesMap.resize(8);
   ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1-
                        TargetRegisterInfo::FirstVirtualRegister);
+
+  allocatableRCRegs.clear();
+  for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(),
+         E = TRI->regclass_end(); I != E; ++I)
+    allocatableRCRegs.insert(std::make_pair(*I,
+                                            TRI->getAllocatableSet(mf, *I)));
+
   grow();
   
   return false;
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index 91c8322..507557d 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -32,6 +32,7 @@ namespace llvm {
   class MachineInstr;
   class MachineFunction;
   class TargetInstrInfo;
+  class TargetRegisterInfo;
 
   class VirtRegMap : public MachineFunctionPass {
   public:
@@ -47,8 +48,11 @@ namespace llvm {
 
   private:
     const TargetInstrInfo *TII;
-
+    const TargetRegisterInfo *TRI;
     MachineFunction *MF;
+
+    DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs;
+
     /// Virt2PhysMap - This is a virtual to physical register
     /// mapping. Each virtual register is required to have an entry in
     /// it; even spilled virtual registers (the register mapped to a
@@ -466,7 +470,7 @@ namespace llvm {
     unsigned getFirstUnusedRegister(const TargetRegisterClass *RC) {
       int Reg = UnusedRegs.find_first();
       while (Reg != -1) {
-        if (RC->contains(Reg))
+        if (allocatableRCRegs[RC][Reg])
           return (unsigned)Reg;
         Reg = UnusedRegs.find_next(Reg);
       }
diff --git a/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp b/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp
index 32e1f7a..bf49ec0 100644
--- a/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp
+++ b/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp
@@ -28,8 +28,6 @@
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
-#include <queue>
-#include <set>
 using namespace llvm;
 
 /// MSP430DAGToDAGISel - MSP430 specific code to select MSP430 machine
diff --git a/lib/Transforms/Scalar/CodeGenPrepare.cpp b/lib/Transforms/Scalar/CodeGenPrepare.cpp
index 9c09f5c..342b1e5 100644
--- a/lib/Transforms/Scalar/CodeGenPrepare.cpp
+++ b/lib/Transforms/Scalar/CodeGenPrepare.cpp
@@ -52,7 +52,7 @@ namespace {
 
     /// BackEdges - Keep a set of all the loop back edges.
     ///
-    SmallSet<std::pair<BasicBlock*,BasicBlock*>, 8> BackEdges;
+    SmallSet<std::pair<const BasicBlock*, const BasicBlock*>, 8> BackEdges;
   public:
     static char ID; // Pass identification, replacement for typeid
     explicit CodeGenPrepare(const TargetLowering *tli = 0)
@@ -69,7 +69,7 @@ namespace {
     bool OptimizeInlineAsmInst(Instruction *I, CallSite CS,
                                DenseMap<Value*,Value*> &SunkAddrs);
     bool OptimizeExtUses(Instruction *I);
-    void findLoopBackEdges(Function &F);
+    void findLoopBackEdges(const Function &F);
   };
 }
 
@@ -83,45 +83,11 @@ FunctionPass *llvm::createCodeGenPreparePass(const TargetLowering *TLI) {
 
 /// findLoopBackEdges - Do a DFS walk to find loop back edges.
 ///
-void CodeGenPrepare::findLoopBackEdges(Function &F) {
-  SmallPtrSet<BasicBlock*, 8> Visited;
-  SmallVector<std::pair<BasicBlock*, succ_iterator>, 8> VisitStack;
-  SmallPtrSet<BasicBlock*, 8> InStack;
-
-  BasicBlock *BB = &F.getEntryBlock();
-  if (succ_begin(BB) == succ_end(BB))
-    return;
-  Visited.insert(BB);
-  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
-  InStack.insert(BB);
-  do {
-    std::pair<BasicBlock*, succ_iterator> &Top = VisitStack.back();
-    BasicBlock *ParentBB = Top.first;
-    succ_iterator &I = Top.second;
-
-    bool FoundNew = false;
-    while (I != succ_end(ParentBB)) {
-      BB = *I++;
-      if (Visited.insert(BB)) {
-        FoundNew = true;
-        break;
-      }
-      // Successor is in VisitStack, it's a back edge.
-      if (InStack.count(BB))
-        BackEdges.insert(std::make_pair(ParentBB, BB));
-    }
-
-    if (FoundNew) {
-      // Go down one level if there is a unvisited successor.
-      InStack.insert(BB);
-      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
-    } else {
-      // Go up one level.
-      std::pair<BasicBlock*, succ_iterator> &Pop = VisitStack.back();
-      InStack.erase(Pop.first);
-      VisitStack.pop_back();
-    }
-  } while (!VisitStack.empty());
+void CodeGenPrepare::findLoopBackEdges(const Function &F) {
+  SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges;
+  FindFunctionBackedges(F, Edges);
+  
+  BackEdges.insert(Edges.begin(), Edges.end());
 }
 
 
@@ -328,7 +294,8 @@ void CodeGenPrepare::EliminateMostlyEmptyBlock(BasicBlock *BB) {
 /// predecessor of the succ that is empty (and thus has no phi nodes), use it
 /// instead of introducing a new block.
 static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum,
-                     SmallSet<std::pair<BasicBlock*,BasicBlock*>, 8> &BackEdges,
+                     SmallSet<std::pair<const BasicBlock*,
+                                        const BasicBlock*>, 8> &BackEdges,
                              Pass *P) {
   BasicBlock *TIBB = TI->getParent();
   BasicBlock *Dest = TI->getSuccessor(SuccNum);
diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp
index 69d1799..c0ca2df 100644
--- a/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/lib/Transforms/Scalar/JumpThreading.cpp
@@ -15,17 +15,19 @@
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/IntrinsicInst.h"
 #include "llvm/Pass.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Target/TargetData.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
-#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/ValueHandle.h"
 using namespace llvm;
 
 STATISTIC(NumThreads, "Number of jumps threaded");
@@ -55,6 +57,11 @@ namespace {
   ///
   class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
     TargetData *TD;
+#ifdef NDEBUG
+    SmallPtrSet<BasicBlock*, 16> LoopHeaders;
+#else
+    SmallSet<AssertingVH<BasicBlock>, 16> LoopHeaders;
+#endif
   public:
     static char ID; // Pass identification
     JumpThreading() : FunctionPass(&ID) {}
@@ -64,8 +71,11 @@ namespace {
     }
 
     bool runOnFunction(Function &F);
+    void FindLoopHeaders(Function &F);
+    
     bool ProcessBlock(BasicBlock *BB);
-    void ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB);
+    bool ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, BasicBlock *SuccBB,
+                    unsigned JumpThreadCost);
     BasicBlock *FactorCommonPHIPreds(PHINode *PN, Constant *CstVal);
     bool ProcessBranchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
     bool ProcessSwitchOnDuplicateCond(BasicBlock *PredBB, BasicBlock *DestBB);
@@ -91,6 +101,8 @@ bool JumpThreading::runOnFunction(Function &F) {
   DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
   TD = &getAnalysis<TargetData>();
   
+  FindLoopHeaders(F);
+  
   bool AnotherIteration = true, EverChanged = false;
   while (AnotherIteration) {
     AnotherIteration = false;
@@ -108,6 +120,7 @@ bool JumpThreading::runOnFunction(Function &F) {
           BB != &BB->getParent()->getEntryBlock()) {
         DOUT << "  JT: Deleting dead block '" << BB->getNameStart()
              << "' with terminator: " << *BB->getTerminator();
+        LoopHeaders.erase(BB);
         DeleteDeadBlock(BB);
         Changed = true;
       }
@@ -115,9 +128,35 @@ bool JumpThreading::runOnFunction(Function &F) {
     AnotherIteration = Changed;
     EverChanged |= Changed;
   }
+  
+  LoopHeaders.clear();
   return EverChanged;
 }
 
+/// FindLoopHeaders - We do not want jump threading to turn proper loop
+/// structures into irreducible loops.  Doing this breaks up the loop nesting
+/// hierarchy and pessimizes later transformations.  To prevent this from
+/// happening, we first have to find the loop headers.  Here we approximate this
+/// by finding targets of backedges in the CFG.
+///
+/// Note that there definitely are cases when we want to allow threading of
+/// edges across a loop header.  For example, threading a jump from outside the
+/// loop (the preheader) to an exit block of the loop is definitely profitable.
+/// It is also almost always profitable to thread backedges from within the loop
+/// to exit blocks, and is often profitable to thread backedges to other blocks
+/// within the loop (forming a nested loop).  This simple analysis is not rich
+/// enough to track all of these properties and keep it up-to-date as the CFG
+/// mutates, so we don't allow any of these transformations.
+///
+void JumpThreading::FindLoopHeaders(Function &F) {
+  SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges;
+  FindFunctionBackedges(F, Edges);
+  
+  for (unsigned i = 0, e = Edges.size(); i != e; ++i)
+    LoopHeaders.insert(const_cast<BasicBlock*>(Edges[i].second));
+}
+
+
 /// FactorCommonPHIPreds - If there are multiple preds with the same incoming
 /// value for the PHI, factor them together so we get one block to thread for
 /// the whole group.
@@ -191,6 +230,10 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) {
   if (BasicBlock *SinglePred = BB->getSinglePredecessor())
     if (SinglePred->getTerminator()->getNumSuccessors() == 1 &&
         SinglePred != BB) {
+      // If SinglePred was a loop header, BB becomes one.
+      if (LoopHeaders.erase(SinglePred))
+        LoopHeaders.insert(BB);
+      
       // Remember if SinglePred was the entry block of the function.  If so, we
       // will need to move BB back to the entry position.
       bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
@@ -389,22 +432,8 @@ bool JumpThreading::ProcessBranchOnDuplicateCond(BasicBlock *PredBB,
   // Next, figure out which successor we are threading to.
   BasicBlock *SuccBB = DestBI->getSuccessor(!BranchDir);
   
-  // If threading to the same block as we come from, we would infinite loop.
-  if (SuccBB == BB) {
-    DOUT << "  Not threading BB '" << BB->getNameStart()
-         << "' - would thread to self!\n";
-    return false;
-  }
-  
-  // And finally, do it!
-  DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
-       << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
-       << ", across block:\n    "
-       << *BB << "\n";
-  
-  ThreadEdge(BB, PredBB, SuccBB);
-  ++NumThreads;
-  return true;
+  // Ok, try to thread it!
+  return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
 }
 
 /// ProcessSwitchOnDuplicateCond - We found a block and a predecessor of that
@@ -675,22 +704,8 @@ bool JumpThreading::ProcessJumpOnPHI(PHINode *PN) {
     SuccBB = SI->getSuccessor(SI->findCaseValue(PredCst));
   }
   
-  // If threading to the same block as we come from, we would infinite loop.
-  if (SuccBB == BB) {
-    DOUT << "  Not threading BB '" << BB->getNameStart()
-         << "' - would thread to self!\n";
-    return false;
-  }
-  
-  // And finally, do it!
-  DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
-       << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
-       << ", across block:\n    "
-       << *BB << "\n";
-       
-  ThreadEdge(BB, PredBB, SuccBB);
-  ++NumThreads;
-  return true;
+  // Ok, try to thread it!
+  return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
 }
 
 /// ProcessJumpOnLogicalPHI - PN's basic block contains a conditional branch
@@ -751,22 +766,8 @@ bool JumpThreading::ProcessBranchOnLogical(Value *V, BasicBlock *BB,
   // 'true' block.
   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(isAnd);
   
-  // If threading to the same block as we come from, we would infinite loop.
-  if (SuccBB == BB) {
-    DOUT << "  Not threading BB '" << BB->getNameStart()
-    << "' - would thread to self!\n";
-    return false;
-  }
-  
-  // And finally, do it!
-  DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
-       << "' to '" << SuccBB->getNameStart() << "' with cost: "
-       << JumpThreadCost << ", across block:\n    "
-       << *BB << "\n";
-  
-  ThreadEdge(BB, PredBB, SuccBB);
-  ++NumThreads;
-  return true;
+  // Ok, try to thread it!
+  return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
 }
 
 /// ProcessBranchOnCompare - We found a branch on a comparison between a phi
@@ -829,32 +830,40 @@ bool JumpThreading::ProcessBranchOnCompare(CmpInst *Cmp, BasicBlock *BB) {
   // Next, get our successor.
   BasicBlock *SuccBB = BB->getTerminator()->getSuccessor(!TrueDirection);
   
+  // Ok, try to thread it!
+  return ThreadEdge(BB, PredBB, SuccBB, JumpThreadCost);
+}
+
+
+/// ThreadEdge - We have decided that it is safe and profitable to thread an
+/// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
+/// change.
+bool JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, 
+                               BasicBlock *SuccBB, unsigned JumpThreadCost) {
+
   // If threading to the same block as we come from, we would infinite loop.
   if (SuccBB == BB) {
-    DOUT << "  Not threading BB '" << BB->getNameStart()
-    << "' - would thread to self!\n";
+    DOUT << "  Not threading across BB '" << BB->getNameStart()
+         << "' - would thread to self!\n";
     return false;
   }
   
-  
+  // If threading this would thread across a loop header, don't thread the edge.
+  // See the comments above FindLoopHeaders for justifications and caveats.
+  if (LoopHeaders.count(BB)) {
+    DOUT << "  Not threading from '" << PredBB->getNameStart()
+         << "' across loop header BB '" << BB->getNameStart()
+         << "' to dest BB '" << SuccBB->getNameStart()
+         << "' - it might create an irreducible loop!\n";
+    return false;
+  }
+
   // And finally, do it!
-  DOUT << "  Threading edge through bool from '" << PredBB->getNameStart()
-       << "' to '" << SuccBB->getNameStart() << "' with cost: "
-       << JumpThreadCost << ", across block:\n    "
+  DOUT << "  Threading edge from '" << PredBB->getNameStart() << "' to '"
+       << SuccBB->getNameStart() << "' with cost: " << JumpThreadCost
+       << ", across block:\n    "
        << *BB << "\n";
   
-  ThreadEdge(BB, PredBB, SuccBB);
-  ++NumThreads;
-  return true;
-}
-
-
-/// ThreadEdge - We have decided that it is safe and profitable to thread an
-/// edge from PredBB to SuccBB across BB.  Transform the IR to reflect this
-/// change.
-void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB, 
-                               BasicBlock *SuccBB) {
-
   // Jump Threading can not update SSA properties correctly if the values
   // defined in the duplicated block are used outside of the block itself.  For
   // this reason, we spill all values that are used outside of BB to the stack.
@@ -938,4 +947,8 @@ void JumpThreading::ThreadEdge(BasicBlock *BB, BasicBlock *PredBB,
     
     RecursivelyDeleteTriviallyDeadInstructions(Inst);
   }
+  
+  // Threaded an edge!
+  ++NumThreads;
+  return true;
 }
diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp
index 076f89e..0a6d7ef 100644
--- a/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -442,6 +442,56 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
   return NewBB;
 }
 
+/// FindFunctionBackedges - Analyze the specified function to find all of the
+/// loop backedges in the function and return them.  This is a relatively cheap
+/// (compared to computing dominators and loop info) analysis.
+///
+/// The output is added to Result, as pairs of <from,to> edge info.
+void llvm::FindFunctionBackedges(const Function &F,
+     SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
+  const BasicBlock *BB = &F.getEntryBlock();
+  if (succ_begin(BB) == succ_end(BB))
+    return;
+  
+  SmallPtrSet<const BasicBlock*, 8> Visited;
+  SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
+  SmallPtrSet<const BasicBlock*, 8> InStack;
+  
+  Visited.insert(BB);
+  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
+  InStack.insert(BB);
+  do {
+    std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
+    const BasicBlock *ParentBB = Top.first;
+    succ_const_iterator &I = Top.second;
+    
+    bool FoundNew = false;
+    while (I != succ_end(ParentBB)) {
+      BB = *I++;
+      if (Visited.insert(BB)) {
+        FoundNew = true;
+        break;
+      }
+      // Successor is in VisitStack, it's a back edge.
+      if (InStack.count(BB))
+        Result.push_back(std::make_pair(ParentBB, BB));
+    }
+    
+    if (FoundNew) {
+      // Go down one level if there is a unvisited successor.
+      InStack.insert(BB);
+      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
+    } else {
+      // Go up one level.
+      InStack.erase(VisitStack.pop_back_val().first);
+    }
+  } while (!VisitStack.empty());
+  
+  
+}
+
+
+
 /// AreEquivalentAddressValues - Test if A and B will obviously have the same
 /// value. This includes recognizing that %t0 and %t1 will have the same
 /// value in code like this:
diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp
index 35c8ccf..3af161f 100644
--- a/lib/VMCore/Value.cpp
+++ b/lib/VMCore/Value.cpp
@@ -406,8 +406,8 @@ Value *Value::DoPHITranslation(const BasicBlock *CurBB,
 typedef DenseMap<Value*, ValueHandleBase*> ValueHandlesTy;
 static ManagedStatic<ValueHandlesTy> ValueHandles;
 
-/// AddToUseList - Add this ValueHandle to the use list for VP, where List is
-/// known to point into the existing use list.
+/// AddToExistingUseList - Add this ValueHandle to the use list for VP, where
+/// List is known to point into the existing use list.
 void ValueHandleBase::AddToExistingUseList(ValueHandleBase **List) {
   assert(List && "Handle list is null?");
   
@@ -443,7 +443,7 @@ void ValueHandleBase::AddToUseList() {
   ValueHandleBase *&Entry = Handles[VP];
   assert(Entry == 0 && "Value really did already have handles?");
   AddToExistingUseList(&Entry);
-  VP->HasValueHandle = 1;
+  VP->HasValueHandle = true;
   
   // If reallocation didn't happen or if this was the first insertion, don't
   // walk the table.