diff options
24 files changed, 368 insertions, 222 deletions
diff --git a/Makefile.rules b/Makefile.rules index 6658edce04..ce31f22ee0 100644 --- a/Makefile.rules +++ b/Makefile.rules @@ -361,6 +361,15 @@ ifeq ($(ARCH),Alpha) LD.Flags += -Wl,--no-relax endif +ifeq ($(OS),MingW) + ifeq ($(LLVM_CROSS_COMPILING),1) + # Work around http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=525016 + ifdef TOOLNAME + LD.Flags += -Wl,--allow-multiple-definition + endif + endif +endif + #-------------------------------------------------------------------- # Directory locations #-------------------------------------------------------------------- diff --git a/docs/GettingStarted.html b/docs/GettingStarted.html index 70c5912479..1cca5ac8e0 100644 --- a/docs/GettingStarted.html +++ b/docs/GettingStarted.html @@ -545,6 +545,9 @@ to miscompile parts of LLVM 2.4. One symptom is ValueSymbolTable complaining about symbols remaining in the table on destruction.</p> <p><b>GCC 4.1.2 20071124 (Red Hat 4.1.2-42)</b>: Suffers from the same symptoms as the previous one. It appears to work with ENABLE_OPTIMIZED=0 (the default).</p> +<p><b>Cygwin GCC 4.3.2 20080827 (beta) 2</b>: + Users <a href="http://llvm.org/PR4145">reported</a> various problems related + with link errors when using this GCC version.</p> <p><b>GNU ld 2.16.X</b>. Some 2.16.X versions of the ld linker will produce very long warning messages complaining that some ".gnu.linkonce.t.*" symbol was diff --git a/include/llvm/ADT/SmallSet.h b/include/llvm/ADT/SmallSet.h index 75e8c64885..caaa96c045 100644 --- a/include/llvm/ADT/SmallSet.h +++ b/include/llvm/ADT/SmallSet.h @@ -76,6 +76,12 @@ public: return true; } + template <typename IterT> + void insert(IterT I, IterT E) { + for (; I != E; ++I) + insert(*I); + } + bool erase(const T &V) { if (!isSmall()) return Set.erase(V); diff --git a/include/llvm/CodeGen/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h index e5f7c6a9a2..1872bd26d8 100644 --- a/include/llvm/CodeGen/MachineModuleInfo.h +++ b/include/llvm/CodeGen/MachineModuleInfo.h @@ -170,11 +170,6 @@ public: return ID; } - /// RecordSourceLine - Records location information and associates it with a - /// label. Returns a unique label ID used to generate a label and - /// provide correspondence to the source line list. - unsigned RecordSourceLine(unsigned Line, unsigned Column, unsigned Source); - /// InvalidateLabel - Inhibit use of the specified label # from /// MachineModuleInfo, for example because the code was deleted. void InvalidateLabel(unsigned LabelID) { diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 6105416a40..367e4b4b06 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -89,7 +89,14 @@ Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB, BasicBlock::iterator &ScanFrom, unsigned MaxInstsToScan = 6, AliasAnalysis *AA = 0); - + +/// 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 FindFunctionBackedges(const Function &F, + SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result); // RemoveSuccessor - Change the specified terminator instruction such that its diff --git a/lib/Analysis/CaptureTracking.cpp b/lib/Analysis/CaptureTracking.cpp index ceb964619c..773f53d2cd 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 848f45ea8c..8ca8590c33 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 afcda1f82e..f7100515b2 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 acdb04339b..fc45bbda22 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 6406b1cc25..dd36bdd604 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 f2f6ab02be..29637b954f 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 91c8322a75..507557d24c 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 32e1f7a57a..bf49ec0bff 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 9c09f5c74e..342b1e563d 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 69d17993b5..c0ca2df1ce 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); |