diff options
author | Mike Stump <mrs@apple.com> | 2009-05-04 18:40:41 +0000 |
---|---|---|
committer | Mike Stump <mrs@apple.com> | 2009-05-04 18:40:41 +0000 |
commit | fe095f39e7009c51d1c86769792ccbcad8cdd2ec (patch) | |
tree | c9883b04cd8a1416361a0b29a6a91bf2417bbf3e /lib | |
parent | 04fa35ab13afbbc5b2f12437a256db84a27485d2 (diff) | |
download | external_llvm-fe095f39e7009c51d1c86769792ccbcad8cdd2ec.zip external_llvm-fe095f39e7009c51d1c86769792ccbcad8cdd2ec.tar.gz external_llvm-fe095f39e7009c51d1c86769792ccbcad8cdd2ec.tar.bz2 |
Restore minor deletion.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70892 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Analysis/CaptureTracking.cpp | 75 | ||||
-rw-r--r-- | lib/CodeGen/AsmPrinter/DwarfWriter.cpp | 11 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/FastISel.cpp | 10 | ||||
-rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGBuild.cpp | 5 | ||||
-rw-r--r-- | lib/CodeGen/StackSlotColoring.cpp | 81 | ||||
-rw-r--r-- | lib/CodeGen/VirtRegMap.cpp | 9 | ||||
-rw-r--r-- | lib/CodeGen/VirtRegMap.h | 8 | ||||
-rw-r--r-- | lib/Target/MSP430/MSP430ISelDAGToDAG.cpp | 2 | ||||
-rw-r--r-- | lib/Transforms/Scalar/CodeGenPrepare.cpp | 51 | ||||
-rw-r--r-- | lib/Transforms/Scalar/JumpThreading.cpp | 155 | ||||
-rw-r--r-- | lib/Transforms/Utils/BasicBlockUtils.cpp | 50 | ||||
-rw-r--r-- | lib/VMCore/Value.cpp | 6 |
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. |