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); + // 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 076f89e337..0a6d7ef5db 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 35c8ccfae6..3af161fa08 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. diff --git a/test/DebugInfo/2009-01-29-HeaderLocation.ll b/test/DebugInfo/2009-01-29-HeaderLocation.ll index c59a1c730c..a201bd5a02 100644 --- a/test/DebugInfo/2009-01-29-HeaderLocation.ll +++ b/test/DebugInfo/2009-01-29-HeaderLocation.ll @@ -1,4 +1,4 @@ -; RUN: llvm-as < %s | llc | grep "m.h" | count 1 +; RUN: llvm-as < %s | llc | grep "\\"m.h\\"" | count 1 target triple = "i386-apple-darwin9.6" %llvm.dbg.anchor.type = type { i32, i32 } %llvm.dbg.basictype.type = type { i32, { }*, i8*, { }*, i32, i64, i64, i64, i32, i32 } diff --git a/test/FrontendC++/2009-05-04-PureConstNounwind.cpp b/test/FrontendC++/2009-05-04-PureConstNounwind.cpp new file mode 100644 index 0000000000..a4b4653e12 --- /dev/null +++ b/test/FrontendC++/2009-05-04-PureConstNounwind.cpp @@ -0,0 +1,8 @@ +// RUN: %llvmgxx -S -emit-llvm %s -o - | grep nounwind | count 4 +int c(void) __attribute__((const)); +int p(void) __attribute__((pure)); +int t(void); + +int f(void) { + return c() + p() + t(); +} diff --git a/test/FrontendC/2009-05-04-EnumInreg.c b/test/FrontendC/2009-05-04-EnumInreg.c new file mode 100644 index 0000000000..8a76f5f8e9 --- /dev/null +++ b/test/FrontendC/2009-05-04-EnumInreg.c @@ -0,0 +1,17 @@ +// RUN: %llvmgcc -S -m32 -mregparm=3 %s -emit-llvm -o - | grep {inreg %action} +// XTARGET: x86 +// PR3967 + +enum kobject_action { + KOBJ_ADD, + KOBJ_REMOVE, + KOBJ_CHANGE, + KOBJ_MOVE, + KOBJ_ONLINE, + KOBJ_OFFLINE, + KOBJ_MAX +}; + +struct kobject; + +int kobject_uevent(struct kobject *kobj, enum kobject_action action) {} diff --git a/test/Transforms/FunctionAttrs/2008-12-31-NoCapture.ll b/test/Transforms/FunctionAttrs/2008-12-31-NoCapture.ll index b874c824e0..aec134a8c7 100644 --- a/test/Transforms/FunctionAttrs/2008-12-31-NoCapture.ll +++ b/test/Transforms/FunctionAttrs/2008-12-31-NoCapture.ll @@ -39,6 +39,16 @@ define i1 @c5(i32* %q, i32 %bitno) { ret i1 %val } +declare void @throw_if_bit_set(i8*, i8) readonly +define i1 @c6(i8* %q, i8 %bit) { + invoke void @throw_if_bit_set(i8* %q, i8 %bit) + to label %ret0 unwind label %ret1 +ret0: + ret i1 0 +ret1: + ret i1 1 +} + define i32 @nc1(i32* %q, i32* %p, i1 %b) { e: br label %l @@ -63,14 +73,20 @@ define void @nc3(void ()* %p) { ret void } -declare void @external(i8*) readonly +declare void @external(i8*) readonly nounwind define void @nc4(i8* %p) { call void @external(i8* %p) ret void } -define void @nc5(void (i8*)* %f, i8* %p) { - call void %f(i8* %p) readonly - call void %f(i8* nocapture %p) +define void @nc5(void (i8*)* %p, i8* %r) { + call void %p(i8* %r) + call void %p(i8* nocapture %r) + ret void +} + +declare i8* @external_identity(i8*) readonly nounwind +define void @nc6(i8* %p) { + call i8* @external_identity(i8* %p) ret void } diff --git a/test/Transforms/JumpThreading/no-irreducible-loops.ll b/test/Transforms/JumpThreading/no-irreducible-loops.ll new file mode 100644 index 0000000000..0c729d1a9b --- /dev/null +++ b/test/Transforms/JumpThreading/no-irreducible-loops.ll @@ -0,0 +1,38 @@ +; RUN: llvm-as < %s | opt -jump-threading -loop-rotate -instcombine -indvars -loop-unroll -simplifycfg | llvm-dis > %t +; RUN: grep {volatile store} %t | count 3 +; RUN: not grep {br label} %t + +; Jump threading should not prevent this loop from being unrolled. + +target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128" +target triple = "i386-apple-darwin9.6" +@v1 = external global i32 ; <i32*> [#uses=2] + +define i32 @unroll() nounwind { +entry: + br label %bb4 + +bb: ; preds = %bb4 + %0 = icmp eq i32 %i.0, 0 ; <i1> [#uses=1] + br i1 %0, label %bb1, label %bb2 + +bb1: ; preds = %bb + volatile store i32 1000, i32* @v1, align 4 + br label %bb3 + +bb2: ; preds = %bb + volatile store i32 1001, i32* @v1, align 4 + br label %bb3 + +bb3: ; preds = %bb2, %bb1 + %1 = add i32 %i.0, 1 ; <i32> [#uses=1] + br label %bb4 + +bb4: ; preds = %bb3, %entry + %i.0 = phi i32 [ 0, %entry ], [ %1, %bb3 ] ; <i32> [#uses=3] + %2 = icmp sgt i32 %i.0, 2 ; <i1> [#uses=1] + br i1 %2, label %bb5, label %bb + +bb5: ; preds = %bb4 + ret i32 0 +} diff --git a/utils/TableGen/AsmWriterEmitter.cpp b/utils/TableGen/AsmWriterEmitter.cpp index 2c259e5ee0..3937fd104a 100644 --- a/utils/TableGen/AsmWriterEmitter.cpp +++ b/utils/TableGen/AsmWriterEmitter.cpp @@ -650,12 +650,12 @@ void AsmWriterEmitter::run(std::ostream &O) { O << "\";\n\n"; O << " if (TAI->doesSupportDebugInformation() &&\n" - << " DW->ShouldEmitDwarfDebug() && OptLevel != CodeGenOpt::None) {\n" + << " DW->ShouldEmitDwarfDebug()) {\n" << " DebugLoc CurDL = MI->getDebugLoc();\n\n" << " if (!CurDL.isUnknown()) {\n" << " static DebugLocTuple PrevDLT(0, ~0U, ~0U);\n" << " DebugLocTuple CurDLT = MF->getDebugLocTuple(CurDL);\n\n" - << " if (PrevDLT.CompileUnit != 0 && PrevDLT != CurDLT)\n" + << " if (CurDLT.CompileUnit != 0 && PrevDLT != CurDLT)\n" << " printLabel(DW->RecordSourceLine(CurDLT.Line, CurDLT.Col,\n" << " DICompileUnit(CurDLT.CompileUnit)));\n\n" << " PrevDLT = CurDLT;\n" diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp index e3858cc3fc..39791e2cba 100644 --- a/utils/TableGen/DAGISelEmitter.cpp +++ b/utils/TableGen/DAGISelEmitter.cpp @@ -2102,7 +2102,7 @@ void DAGISelEmitter::run(std::ostream &OS) { OS << "// Include standard, target-independent definitions and methods used\n" << "// by the instruction selector.\n"; - OS << "#include <llvm/CodeGen/DAGISelHeader.h>\n\n"; + OS << "#include \"llvm/CodeGen/DAGISelHeader.h\"\n\n"; EmitNodeTransforms(OS); EmitPredicateFunctions(OS); |