X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAGISel.cpp;h=2f43222760c37f89e9eced8cdb068a8cc851d05a;hb=91ee5454ae8f15de769a7316b4c36734b6103e45;hp=ef90400023c5117990af51f80952129678e93830;hpb=7232464bdaae5e6e48986a1e3b9a95fac7aa7bdf;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index ef90400023c..2f43222760c 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -12,10 +12,9 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "isel" +#include "llvm/CodeGen/SelectionDAGISel.h" #include "llvm/ADT/BitVector.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/CodeGen/SelectionDAGISel.h" -#include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/Constants.h" #include "llvm/CallingConv.h" #include "llvm/DerivedTypes.h" @@ -26,13 +25,16 @@ #include "llvm/Intrinsics.h" #include "llvm/IntrinsicInst.h" #include "llvm/ParameterAttributes.h" -#include "llvm/CodeGen/Collector.h" +#include "llvm/CodeGen/FastISel.h" +#include "llvm/CodeGen/GCStrategy.h" +#include "llvm/CodeGen/GCMetadata.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineJumpTableInfo.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/CodeGen/SelectionDAG.h" #include "llvm/Target/TargetRegisterInfo.h" @@ -53,7 +55,13 @@ static cl::opt EnableValueProp("enable-value-prop", cl::Hidden); static cl::opt EnableLegalizeTypes("enable-legalize-types", cl::Hidden); - +static cl::opt +EnableFastISel("fast-isel", cl::Hidden, + cl::desc("Enable the experimental \"fast\" instruction selector")); +static cl::opt +DisableFastISelAbort("fast-isel-no-abort", cl::Hidden, + cl::desc("Use the SelectionDAGISel when \"fast\" instruction " + "selection fails")); #ifndef NDEBUG static cl::opt @@ -305,14 +313,19 @@ namespace llvm { class FunctionLoweringInfo { public: TargetLowering &TLI; - Function &Fn; - MachineFunction &MF; - MachineRegisterInfo &RegInfo; + Function *Fn; + MachineFunction *MF; + MachineRegisterInfo *RegInfo; - FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF); + explicit FunctionLoweringInfo(TargetLowering &TLI); + + /// set - Initialize this FunctionLoweringInfo with the given Function + /// and its associated MachineFunction. + /// + void set(Function &Fn, MachineFunction &MF); /// MBBMap - A mapping from LLVM basic blocks to their machine code entry. - std::map MBBMap; + DenseMap MBBMap; /// ValueMap - Since we emit code for the function a basic block at a time, /// we must remember which virtual registers hold the values for @@ -322,7 +335,7 @@ namespace llvm { /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in /// the entry block. This allows the allocas to be efficiently referenced /// anywhere in the function. - std::map StaticAllocaMap; + DenseMap StaticAllocaMap; #ifndef NDEBUG SmallSet CatchInfoLost; @@ -330,7 +343,7 @@ namespace llvm { #endif unsigned MakeReg(MVT VT) { - return RegInfo.createVirtualRegister(TLI.getRegClassFor(VT)); + return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); } /// isExportedInst - Return true if the specified value is an instruction @@ -356,6 +369,20 @@ namespace llvm { /// LiveOutRegInfo - Information about live out vregs, indexed by their /// register number offset by 'FirstVirtualRegister'. std::vector LiveOutRegInfo; + + /// clear - Clear out all the function-specific state. This returns this + /// FunctionLoweringInfo to an empty state, ready to be used for a + /// different function. + void clear() { + MBBMap.clear(); + ValueMap.clear(); + StaticAllocaMap.clear(); +#ifndef NDEBUG + CatchInfoLost.clear(); + CatchInfoFound.clear(); +#endif + LiveOutRegInfo.clear(); + } }; } @@ -386,6 +413,11 @@ static bool isUsedOutsideOfDefiningBlock(Instruction *I) { /// entry block, return true. This includes arguments used by switches, since /// the switch may expand into multiple basic blocks. static bool isOnlyUsedInEntryBlock(Argument *A) { + // With FastISel active, we may be splitting blocks, so force creation + // of virtual registers for all non-dead arguments. + if (EnableFastISel) + return A->use_empty(); + BasicBlock *Entry = A->getParent()->begin(); for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI) if (cast(*UI)->getParent() != Entry || isa(*UI)) @@ -393,13 +425,18 @@ static bool isOnlyUsedInEntryBlock(Argument *A) { return true; } -FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, - Function &fn, MachineFunction &mf) - : TLI(tli), Fn(fn), MF(mf), RegInfo(MF.getRegInfo()) { +FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli) + : TLI(tli) { +} + +void FunctionLoweringInfo::set(Function &fn, MachineFunction &mf) { + Fn = &fn; + MF = &mf; + RegInfo = &MF->getRegInfo(); // Create a vreg for each argument register that is not dead and is used // outside of the entry block for the function. - for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end(); + for (Function::arg_iterator AI = Fn->arg_begin(), E = Fn->arg_end(); AI != E; ++AI) if (!isOnlyUsedInEntryBlock(AI)) InitializeRegForValue(AI); @@ -407,7 +444,7 @@ FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, // Initialize the mapping of values to registers. This is only set up for // instruction values that are used outside of the block that defines // them. - Function::iterator BB = Fn.begin(), EB = Fn.end(); + Function::iterator BB = Fn->begin(), EB = Fn->end(); for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) if (AllocaInst *AI = dyn_cast(I)) if (ConstantInt *CUI = dyn_cast(AI->getArraySize())) { @@ -420,7 +457,7 @@ FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, TySize *= CUI->getZExtValue(); // Get total allocated size. if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects. StaticAllocaMap[AI] = - MF.getFrameInfo()->CreateStackObject(TySize, Align); + MF->getFrameInfo()->CreateStackObject(TySize, Align); } for (; BB != EB; ++BB) @@ -433,10 +470,10 @@ FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This // also creates the initial PHI MachineInstrs, though none of the input // operands are populated. - for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) { + for (BB = Fn->begin(), EB = Fn->end(); BB != EB; ++BB) { MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB); MBBMap[BB] = MBB; - MF.push_back(MBB); + MF->push_back(MBB); // Create Machine PHI nodes for LLVM PHI nodes, lowering them as // appropriate. @@ -444,13 +481,19 @@ FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast(I)); ++I){ if (PN->use_empty()) continue; - MVT VT = TLI.getValueType(PN->getType()); - unsigned NumRegisters = TLI.getNumRegisters(VT); unsigned PHIReg = ValueMap[PN]; assert(PHIReg && "PHI node does not have an assigned virtual register!"); - const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo(); - for (unsigned i = 0; i != NumRegisters; ++i) - BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i); + + SmallVector ValueVTs; + ComputeValueVTs(TLI, PN->getType(), ValueVTs); + for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) { + MVT VT = ValueVTs[vti]; + unsigned NumRegisters = TLI.getNumRegisters(VT); + const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo(); + for (unsigned i = 0; i != NumRegisters; ++i) + BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i); + PHIReg += NumRegisters; + } } } } @@ -480,6 +523,84 @@ unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) { return FirstReg; } +namespace { + +/// CaseBlock - This structure is used to communicate between SDLowering and +/// SDISel for the code generation of additional basic blocks needed by multi- +/// case switch statements. +struct CaseBlock { + CaseBlock(ISD::CondCode cc, Value *cmplhs, Value *cmprhs, Value *cmpmiddle, + MachineBasicBlock *truebb, MachineBasicBlock *falsebb, + MachineBasicBlock *me) + : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), + TrueBB(truebb), FalseBB(falsebb), ThisBB(me) {} + // CC - the condition code to use for the case block's setcc node + ISD::CondCode CC; + // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit. + // Emit by default LHS op RHS. MHS is used for range comparisons: + // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). + Value *CmpLHS, *CmpMHS, *CmpRHS; + // TrueBB/FalseBB - the block to branch to if the setcc is true/false. + MachineBasicBlock *TrueBB, *FalseBB; + // ThisBB - the block into which to emit the code for the setcc and branches + MachineBasicBlock *ThisBB; +}; +struct JumpTable { + JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, + MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {} + + /// Reg - the virtual register containing the index of the jump table entry + //. to jump to. + unsigned Reg; + /// JTI - the JumpTableIndex for this jump table in the function. + unsigned JTI; + /// MBB - the MBB into which to emit the code for the indirect jump. + MachineBasicBlock *MBB; + /// Default - the MBB of the default bb, which is a successor of the range + /// check MBB. This is when updating PHI nodes in successors. + MachineBasicBlock *Default; +}; +struct JumpTableHeader { + JumpTableHeader(uint64_t F, uint64_t L, Value* SV, MachineBasicBlock* H, + bool E = false): + First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {} + uint64_t First; + uint64_t Last; + Value *SValue; + MachineBasicBlock *HeaderBB; + bool Emitted; +}; +typedef std::pair JumpTableBlock; + +struct BitTestCase { + BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr): + Mask(M), ThisBB(T), TargetBB(Tr) { } + uint64_t Mask; + MachineBasicBlock* ThisBB; + MachineBasicBlock* TargetBB; +}; + +typedef SmallVector BitTestInfo; + +struct BitTestBlock { + BitTestBlock(uint64_t F, uint64_t R, Value* SV, + unsigned Rg, bool E, + MachineBasicBlock* P, MachineBasicBlock* D, + const BitTestInfo& C): + First(F), Range(R), SValue(SV), Reg(Rg), Emitted(E), + Parent(P), Default(D), Cases(C) { } + uint64_t First; + uint64_t Range; + Value *SValue; + unsigned Reg; + bool Emitted; + MachineBasicBlock *Parent; + MachineBasicBlock *Default; + BitTestInfo Cases; +}; + +} // end anonymous namespace + //===----------------------------------------------------------------------===// /// SelectionDAGLowering - This is the common target-independent lowering /// implementation that is parameterized by a TargetLowering object. @@ -502,7 +623,7 @@ class SelectionDAGLowering { /// instruction, but they have no other ordering requirements. We bunch them /// up and the emit a single tokenfactor for them just before terminator /// instructions. - std::vector PendingExports; + SmallVector PendingExports; /// Case - A struct to record the Value for a switch case, and the /// case's target basic block. @@ -580,29 +701,53 @@ public: TargetLowering &TLI; SelectionDAG &DAG; const TargetData *TD; - AliasAnalysis &AA; + AliasAnalysis *AA; /// SwitchCases - Vector of CaseBlock structures used to communicate /// SwitchInst code generation information. - std::vector SwitchCases; + std::vector SwitchCases; /// JTCases - Vector of JumpTable structures used to communicate /// SwitchInst code generation information. - std::vector JTCases; - std::vector BitTestCases; + std::vector JTCases; + /// BitTestCases - Vector of BitTestBlock structures used to communicate + /// SwitchInst code generation information. + std::vector BitTestCases; + std::vector > PHINodesToUpdate; + + // Emit PHI-node-operand constants only once even if used by multiple + // PHI nodes. + DenseMap ConstantsOut; + /// FuncInfo - Information about the function as a whole. /// FunctionLoweringInfo &FuncInfo; - /// GCI - Garbage collection metadata for the function. - CollectorMetadata *GCI; + /// GFI - Garbage collection metadata for the function. + GCFunctionInfo *GFI; SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli, - AliasAnalysis &aa, - FunctionLoweringInfo &funcinfo, - CollectorMetadata *gci) - : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), AA(aa), - FuncInfo(funcinfo), GCI(gci) { + FunctionLoweringInfo &funcinfo) + : TLI(tli), DAG(dag), FuncInfo(funcinfo) { + } + + void init(GCFunctionInfo *gfi, AliasAnalysis &aa) { + AA = &aa; + GFI = gfi; + TD = DAG.getTarget().getTargetData(); + } + + /// clear - Clear out the curret SelectionDAG and the associated + /// state and prepare this SelectionDAGLowering object to be used + /// for a new block. This doesn't clear out information about + /// additional blocks that are needed to complete switch lowering + /// or PHI node updating; that information is cleared out as it is + /// consumed. + void clear() { + NodeMap.clear(); + PendingLoads.clear(); + PendingExports.clear(); + DAG.clear(); } /// getRoot - Return the current virtual root of the Selection DAG, @@ -722,14 +867,13 @@ public: CaseRecVector& WorkList, Value* SV, MachineBasicBlock* Default); - void visitSwitchCase(SelectionDAGISel::CaseBlock &CB); - void visitBitTestHeader(SelectionDAGISel::BitTestBlock &B); + void visitSwitchCase(CaseBlock &CB); + void visitBitTestHeader(BitTestBlock &B); void visitBitTestCase(MachineBasicBlock* NextMBB, unsigned Reg, - SelectionDAGISel::BitTestCase &B); - void visitJumpTable(SelectionDAGISel::JumpTable &JT); - void visitJumpTableHeader(SelectionDAGISel::JumpTable &JT, - SelectionDAGISel::JumpTableHeader &JTH); + BitTestCase &B); + void visitJumpTable(JumpTable &JT); + void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH); // These all get lowered before this pass. void visitInvoke(InvokeInst &I); @@ -1184,34 +1328,18 @@ SDValue SelectionDAGLowering::getValue(const Value *V) { return DAG.getMergeValues(&Constants[0], Constants.size()); } - if (const ArrayType *ATy = dyn_cast(C->getType())) { + if (isa(C->getType()) || isa(C->getType())) { assert((isa(C) || isa(C)) && - "Unknown array constant!"); - unsigned NumElts = ATy->getNumElements(); - if (NumElts == 0) - return SDValue(); // empty array - MVT EltVT = TLI.getValueType(ATy->getElementType()); - SmallVector Constants(NumElts); - for (unsigned i = 0, e = NumElts; i != e; ++i) { - if (isa(C)) - Constants[i] = DAG.getNode(ISD::UNDEF, EltVT); - else if (EltVT.isFloatingPoint()) - Constants[i] = DAG.getConstantFP(0, EltVT); - else - Constants[i] = DAG.getConstant(0, EltVT); - } - return DAG.getMergeValues(&Constants[0], Constants.size()); - } + "Unknown struct or array constant!"); - if (const StructType *STy = dyn_cast(C->getType())) { - assert((isa(C) || isa(C)) && - "Unknown struct constant!"); - unsigned NumElts = STy->getNumElements(); + SmallVector ValueVTs; + ComputeValueVTs(TLI, C->getType(), ValueVTs); + unsigned NumElts = ValueVTs.size(); if (NumElts == 0) return SDValue(); // empty struct SmallVector Constants(NumElts); - for (unsigned i = 0, e = NumElts; i != e; ++i) { - MVT EltVT = TLI.getValueType(STy->getElementType(i)); + for (unsigned i = 0; i != NumElts; ++i) { + MVT EltVT = ValueVTs[i]; if (isa(C)) Constants[i] = DAG.getNode(ISD::UNDEF, EltVT); else if (EltVT.isFloatingPoint()) @@ -1219,7 +1347,7 @@ SDValue SelectionDAGLowering::getValue(const Value *V) { else Constants[i] = DAG.getConstant(0, EltVT); } - return DAG.getMergeValues(&Constants[0], Constants.size()); + return DAG.getMergeValues(&Constants[0], NumElts); } const VectorType *VecTy = cast(V->getType()); @@ -1253,7 +1381,7 @@ SDValue SelectionDAGLowering::getValue(const Value *V) { // If this is a static alloca, generate it as the frameindex instead of // computation. if (const AllocaInst *AI = dyn_cast(V)) { - std::map::iterator SI = + DenseMap::iterator SI = FuncInfo.StaticAllocaMap.find(AI); if (SI != FuncInfo.StaticAllocaMap.end()) return DAG.getFrameIndex(SI->second, TLI.getPointerTy()); @@ -1303,7 +1431,7 @@ void SelectionDAGLowering::visitRet(ReturnInst &I) { else if (F->paramHasAttr(0, ParamAttr::ZExt)) ExtendKind = ISD::ZERO_EXTEND; - getCopyToParts(DAG, SDValue(RetOp.Val, RetOp.ResNo + j), + getCopyToParts(DAG, SDValue(RetOp.Val, RetOp.getResNo() + j), &Parts[0], NumParts, PartVT, ExtendKind); for (unsigned i = 0; i < NumParts; ++i) { @@ -1434,15 +1562,15 @@ void SelectionDAGLowering::FindMergedConditions(Value *Cond, assert(0 && "Unknown compare instruction"); } - SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0), - BOp->getOperand(1), NULL, TBB, FBB, CurBB); + CaseBlock CB(Condition, BOp->getOperand(0), + BOp->getOperand(1), NULL, TBB, FBB, CurBB); SwitchCases.push_back(CB); return; } // Create a CaseBlock record representing this branch. - SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(), - NULL, TBB, FBB, CurBB); + CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(), + NULL, TBB, FBB, CurBB); SwitchCases.push_back(CB); return; } @@ -1491,7 +1619,7 @@ void SelectionDAGLowering::FindMergedConditions(Value *Cond, /// If we should emit this as a bunch of and/or'd together conditions, return /// false. static bool -ShouldEmitAsBranches(const std::vector &Cases) { +ShouldEmitAsBranches(const std::vector &Cases) { if (Cases.size() != 2) return true; // If this is two comparisons of the same values or'd or and'd together, they @@ -1580,8 +1708,8 @@ void SelectionDAGLowering::visitBr(BranchInst &I) { } // Create a CaseBlock record representing this branch. - SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(), - NULL, Succ0MBB, Succ1MBB, CurMBB); + CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(), + NULL, Succ0MBB, Succ1MBB, CurMBB); // Use visitSwitchCase to actually insert the fast branch sequence for this // cond branch. visitSwitchCase(CB); @@ -1589,7 +1717,7 @@ void SelectionDAGLowering::visitBr(BranchInst &I) { /// visitSwitchCase - Emits the necessary code to represent a single node in /// the binary search tree resulting from lowering a switch instruction. -void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) { +void SelectionDAGLowering::visitSwitchCase(CaseBlock &CB) { SDValue Cond; SDValue CondLHS = getValue(CB.CmpLHS); @@ -1642,15 +1770,26 @@ void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) { } SDValue BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getControlRoot(), Cond, DAG.getBasicBlock(CB.TrueBB)); - if (CB.FalseBB == NextBlock) + + // If the branch was constant folded, fix up the CFG. + if (BrCond.getOpcode() == ISD::BR) { + CurMBB->removeSuccessor(CB.FalseBB); DAG.setRoot(BrCond); - else - DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, - DAG.getBasicBlock(CB.FalseBB))); + } else { + // Otherwise, go ahead and insert the false branch. + if (BrCond == getControlRoot()) + CurMBB->removeSuccessor(CB.TrueBB); + + if (CB.FalseBB == NextBlock) + DAG.setRoot(BrCond); + else + DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, + DAG.getBasicBlock(CB.FalseBB))); + } } /// visitJumpTable - Emit JumpTable node in the current MBB -void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) { +void SelectionDAGLowering::visitJumpTable(JumpTable &JT) { // Emit the code for the jump table assert(JT.Reg != -1U && "Should lower JT Header first!"); MVT PTy = TLI.getPointerTy(); @@ -1663,8 +1802,8 @@ void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) { /// visitJumpTableHeader - This function emits necessary code to produce index /// in the JumpTable from switch case. -void SelectionDAGLowering::visitJumpTableHeader(SelectionDAGISel::JumpTable &JT, - SelectionDAGISel::JumpTableHeader &JTH) { +void SelectionDAGLowering::visitJumpTableHeader(JumpTable &JT, + JumpTableHeader &JTH) { // Subtract the lowest switch case value from the value being switched on // and conditional branch to default mbb if the result is greater than the // difference between smallest and largest cases. @@ -1715,7 +1854,7 @@ void SelectionDAGLowering::visitJumpTableHeader(SelectionDAGISel::JumpTable &JT, /// visitBitTestHeader - This function emits necessary code to produce value /// suitable for "bit tests" -void SelectionDAGLowering::visitBitTestHeader(SelectionDAGISel::BitTestBlock &B) { +void SelectionDAGLowering::visitBitTestHeader(BitTestBlock &B) { // Subtract the minimum value SDValue SwitchOp = getValue(B.SValue); MVT VT = SwitchOp.getValueType(); @@ -1769,7 +1908,7 @@ void SelectionDAGLowering::visitBitTestHeader(SelectionDAGISel::BitTestBlock &B) /// visitBitTestCase - this function produces one "bit test" void SelectionDAGLowering::visitBitTestCase(MachineBasicBlock* NextMBB, unsigned Reg, - SelectionDAGISel::BitTestCase &B) { + BitTestCase &B) { // Emit bit tests and jumps SDValue SwitchVal = DAG.getCopyFromReg(getControlRoot(), Reg, TLI.getPointerTy()); @@ -1897,8 +2036,7 @@ bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR, CC = ISD::SETLE; LHS = I->Low; MHS = SV; RHS = I->High; } - SelectionDAGISel::CaseBlock CB(CC, LHS, RHS, MHS, - I->BB, FallThrough, CurBlock); + CaseBlock CB(CC, LHS, RHS, MHS, I->BB, FallThrough, CurBlock); // If emitting the first comparison, just call visitSwitchCase to emit the // code into the current block. Otherwise, push the CaseBlock onto the @@ -2005,13 +2143,12 @@ bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR, // Set the jump table information so that we can codegen it as a second // MachineBasicBlock - SelectionDAGISel::JumpTable JT(-1U, JTI, JumpTableBB, Default); - SelectionDAGISel::JumpTableHeader JTH(First, Last, SV, CR.CaseBB, - (CR.CaseBB == CurMBB)); + JumpTable JT(-1U, JTI, JumpTableBB, Default); + JumpTableHeader JTH(First, Last, SV, CR.CaseBB, (CR.CaseBB == CurMBB)); if (CR.CaseBB == CurMBB) visitJumpTableHeader(JT, JTH); - JTCases.push_back(SelectionDAGISel::JumpTableBlock(JTH, JT)); + JTCases.push_back(JumpTableBlock(JTH, JT)); return true; } @@ -2125,8 +2262,7 @@ bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR, // Create a CaseBlock record representing a conditional branch to // the LHS node if the value being switched on SV is less than C. // Otherwise, branch to LHS. - SelectionDAGISel::CaseBlock CB(ISD::SETLT, SV, C, NULL, - TrueBB, FalseBB, CR.CaseBB); + CaseBlock CB(ISD::SETLT, SV, C, NULL, TrueBB, FalseBB, CR.CaseBB); if (CR.CaseBB == CurMBB) visitSwitchCase(CB); @@ -2227,7 +2363,7 @@ bool SelectionDAGLowering::handleBitTestsSwitchCase(CaseRec& CR, } std::sort(CasesBits.begin(), CasesBits.end(), CaseBitsCmp()); - SelectionDAGISel::BitTestInfo BTC; + BitTestInfo BTC; // Figure out which block is immediately after the current one. MachineFunction::iterator BBI = CR.CaseBB; @@ -2242,14 +2378,14 @@ bool SelectionDAGLowering::handleBitTestsSwitchCase(CaseRec& CR, MachineBasicBlock *CaseBB = CurMF->CreateMachineBasicBlock(LLVMBB); CurMF->insert(BBI, CaseBB); - BTC.push_back(SelectionDAGISel::BitTestCase(CasesBits[i].Mask, - CaseBB, - CasesBits[i].BB)); + BTC.push_back(BitTestCase(CasesBits[i].Mask, + CaseBB, + CasesBits[i].BB)); } - SelectionDAGISel::BitTestBlock BTB(lowBound, range, SV, - -1U, (CR.CaseBB == CurMBB), - CR.CaseBB, Default, BTC); + BitTestBlock BTB(lowBound, range, SV, + -1U, (CR.CaseBB == CurMBB), + CR.CaseBB, Default, BTC); if (CR.CaseBB == CurMBB) visitBitTestHeader(BTB); @@ -2722,15 +2858,15 @@ void SelectionDAGLowering::visitInsertValue(InsertValueInst &I) { // Copy the beginning value(s) from the original aggregate. for (; i != LinearIndex; ++i) Values[i] = IntoUndef ? DAG.getNode(ISD::UNDEF, AggValueVTs[i]) : - SDValue(Agg.Val, Agg.ResNo + i); + SDValue(Agg.Val, Agg.getResNo() + i); // Copy values from the inserted value(s). for (; i != LinearIndex + NumValValues; ++i) Values[i] = FromUndef ? DAG.getNode(ISD::UNDEF, AggValueVTs[i]) : - SDValue(Val.Val, Val.ResNo + i - LinearIndex); + SDValue(Val.Val, Val.getResNo() + i - LinearIndex); // Copy remaining value(s) from the original aggregate. for (; i != NumAggValues; ++i) Values[i] = IntoUndef ? DAG.getNode(ISD::UNDEF, AggValueVTs[i]) : - SDValue(Agg.Val, Agg.ResNo + i); + SDValue(Agg.Val, Agg.getResNo() + i); setValue(&I, DAG.getMergeValues(DAG.getVTList(&AggValueVTs[0], NumAggValues), &Values[0], NumAggValues)); @@ -2755,8 +2891,8 @@ void SelectionDAGLowering::visitExtractValue(ExtractValueInst &I) { // Copy out the selected value(s). for (unsigned i = LinearIndex; i != LinearIndex + NumValValues; ++i) Values[i - LinearIndex] = - OutOfUndef ? DAG.getNode(ISD::UNDEF, Agg.Val->getValueType(Agg.ResNo + i)) : - SDValue(Agg.Val, Agg.ResNo + i); + OutOfUndef ? DAG.getNode(ISD::UNDEF, Agg.Val->getValueType(Agg.getResNo() + i)) : + SDValue(Agg.Val, Agg.getResNo() + i); setValue(&I, DAG.getMergeValues(DAG.getVTList(&ValValueVTs[0], NumValValues), &Values[0], NumValValues)); @@ -2798,23 +2934,24 @@ void SelectionDAGLowering::visitGetElementPtr(User &I) { // If the index is smaller or larger than intptr_t, truncate or extend // it. - if (IdxN.getValueType().bitsLT(N.getValueType())) { + if (IdxN.getValueType().bitsLT(N.getValueType())) IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN); - } else if (IdxN.getValueType().bitsGT(N.getValueType())) + else if (IdxN.getValueType().bitsGT(N.getValueType())) IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN); // If this is a multiply by a power of two, turn it into a shl // immediately. This is a very common case. - if (isPowerOf2_64(ElementSize)) { - unsigned Amt = Log2_64(ElementSize); - IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN, - DAG.getConstant(Amt, TLI.getShiftAmountTy())); - N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); - continue; + if (ElementSize != 1) { + if (isPowerOf2_64(ElementSize)) { + unsigned Amt = Log2_64(ElementSize); + IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN, + DAG.getConstant(Amt, TLI.getShiftAmountTy())); + } else { + SDValue Scale = DAG.getIntPtrConstant(ElementSize); + IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale); + } } - - SDValue Scale = DAG.getIntPtrConstant(ElementSize); - IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale); + N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); } } @@ -2891,7 +3028,7 @@ void SelectionDAGLowering::visitLoad(LoadInst &I) { if (I.isVolatile()) // Serialize volatile loads with other side effects. Root = getRoot(); - else if (AA.pointsToConstantMemory(SV)) { + else if (AA->pointsToConstantMemory(SV)) { // Do not serialize (non-volatile) loads of constant memory with anything. Root = DAG.getEntryNode(); ConstantMemory = true; @@ -2950,7 +3087,7 @@ void SelectionDAGLowering::visitStore(StoreInst &I) { bool isVolatile = I.isVolatile(); unsigned Alignment = I.getAlignment(); for (unsigned i = 0; i != NumValues; ++i) - Chains[i] = DAG.getStore(Root, SDValue(Src.Val, Src.ResNo + i), + Chains[i] = DAG.getStore(Root, SDValue(Src.Val, Src.getResNo() + i), DAG.getNode(ISD::ADD, PtrVT, Ptr, DAG.getConstant(Offsets[i], PtrVT)), PtrV, Offsets[i], @@ -3173,7 +3310,7 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { uint64_t Size = -1ULL; if (ConstantSDNode *C = dyn_cast(Op3)) Size = C->getValue(); - if (AA.alias(I.getOperand(1), Size, I.getOperand(2), Size) == + if (AA->alias(I.getOperand(1), Size, I.getOperand(2), Size) == AliasAnalysis::NoAlias) { DAG.setRoot(DAG.getMemcpy(getRoot(), Op1, Op2, Op3, Align, false, I.getOperand(1), 0, I.getOperand(2), 0)); @@ -3483,18 +3620,18 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { } case Intrinsic::gcroot: - if (GCI) { + if (GFI) { Value *Alloca = I.getOperand(1); Constant *TypeMap = cast(I.getOperand(2)); FrameIndexSDNode *FI = cast(getValue(Alloca).Val); - GCI->addStackRoot(FI->getIndex(), TypeMap); + GFI->addStackRoot(FI->getIndex(), TypeMap); } return 0; case Intrinsic::gcread: case Intrinsic::gcwrite: - assert(0 && "Collector failed to lower gcread/gcwrite intrinsics!"); + assert(0 && "GC failed to lower gcread/gcwrite intrinsics!"); return 0; case Intrinsic::flt_rounds: { @@ -3527,37 +3664,198 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { } case Intrinsic::atomic_cmp_swap: { SDValue Root = getRoot(); - SDValue L = DAG.getAtomic(ISD::ATOMIC_CMP_SWAP, Root, - getValue(I.getOperand(1)), - getValue(I.getOperand(2)), - getValue(I.getOperand(3)), - I.getOperand(1)); + SDValue L; + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + L = DAG.getAtomic(ISD::ATOMIC_CMP_SWAP_8, Root, + getValue(I.getOperand(1)), + getValue(I.getOperand(2)), + getValue(I.getOperand(3)), + I.getOperand(1)); + break; + case MVT::i16: + L = DAG.getAtomic(ISD::ATOMIC_CMP_SWAP_16, Root, + getValue(I.getOperand(1)), + getValue(I.getOperand(2)), + getValue(I.getOperand(3)), + I.getOperand(1)); + break; + case MVT::i32: + L = DAG.getAtomic(ISD::ATOMIC_CMP_SWAP_32, Root, + getValue(I.getOperand(1)), + getValue(I.getOperand(2)), + getValue(I.getOperand(3)), + I.getOperand(1)); + break; + case MVT::i64: + L = DAG.getAtomic(ISD::ATOMIC_CMP_SWAP_64, Root, + getValue(I.getOperand(1)), + getValue(I.getOperand(2)), + getValue(I.getOperand(3)), + I.getOperand(1)); + break; + default: + assert(0 && "Invalid atomic type"); + abort(); + } setValue(&I, L); DAG.setRoot(L.getValue(1)); return 0; } case Intrinsic::atomic_load_add: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_ADD); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_ADD_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_ADD_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_ADD_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_ADD_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } case Intrinsic::atomic_load_sub: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_SUB); - case Intrinsic::atomic_load_and: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_AND); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_SUB_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_SUB_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_SUB_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_SUB_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } case Intrinsic::atomic_load_or: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_OR); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_OR_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_OR_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_OR_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_OR_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } case Intrinsic::atomic_load_xor: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_XOR); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_XOR_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_XOR_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_XOR_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_XOR_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } + case Intrinsic::atomic_load_and: + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_AND_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_AND_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_AND_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_AND_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } case Intrinsic::atomic_load_nand: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_NAND); - case Intrinsic::atomic_load_min: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MIN); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_NAND_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_NAND_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_NAND_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_NAND_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } case Intrinsic::atomic_load_max: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MAX); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MAX_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MAX_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MAX_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MAX_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } + case Intrinsic::atomic_load_min: + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MIN_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MIN_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MIN_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MIN_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } case Intrinsic::atomic_load_umin: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMIN); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMIN_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMIN_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMIN_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMIN_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } case Intrinsic::atomic_load_umax: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMAX); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMAX_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMAX_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMAX_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMAX_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } case Intrinsic::atomic_swap: - return implVisitBinaryAtomic(I, ISD::ATOMIC_SWAP); + switch (getValue(I.getOperand(2)).getValueType().getSimpleVT()) { + case MVT::i8: + return implVisitBinaryAtomic(I, ISD::ATOMIC_SWAP_8); + case MVT::i16: + return implVisitBinaryAtomic(I, ISD::ATOMIC_SWAP_16); + case MVT::i32: + return implVisitBinaryAtomic(I, ISD::ATOMIC_SWAP_32); + case MVT::i64: + return implVisitBinaryAtomic(I, ISD::ATOMIC_SWAP_64); + default: + assert(0 && "Invalid atomic type"); + abort(); + } } } @@ -3769,12 +4067,13 @@ SDValue RegsForValue::getCopyFromRegs(SelectionDAG &DAG, } } - Parts[Part+i] = P; + Parts[i] = P; } - Values[Value] = getCopyFromParts(DAG, &Parts[Part], NumRegs, RegisterVT, + Values[Value] = getCopyFromParts(DAG, Parts.begin(), NumRegs, RegisterVT, ValueVT); Part += NumRegs; + Parts.clear(); } return DAG.getMergeValues(DAG.getVTList(&ValueVTs[0], ValueVTs.size()), @@ -3795,7 +4094,7 @@ void RegsForValue::getCopyToRegs(SDValue Val, SelectionDAG &DAG, unsigned NumParts = TLI->getNumRegisters(ValueVT); MVT RegisterVT = RegVTs[Value]; - getCopyToParts(DAG, Val.getValue(Val.ResNo + Value), + getCopyToParts(DAG, Val.getValue(Val.getResNo() + Value), &Parts[Part], NumParts, RegisterVT); Part += NumParts; } @@ -4216,7 +4515,7 @@ void SelectionDAGLowering::visitInlineAsm(CallSite CS) { if (!SawEarlyClobber && OpInfo.Type == InlineAsm::isClobber && OpInfo.ConstraintType == TargetLowering::C_Register) { - // Note that we want to ignore things that we don't trick here, like + // Note that we want to ignore things that we don't track here, like // dirflag, fpsr, flags, etc. std::pair PhysReg = TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode, @@ -4748,7 +5047,7 @@ TargetLowering::LowerCallTo(SDValue Chain, const Type *RetTy, Value != NumValues; ++Value) { MVT VT = ValueVTs[Value]; const Type *ArgTy = VT.getTypeForMVT(); - SDValue Op = SDValue(Args[i].Node.Val, Args[i].Node.ResNo + Value); + SDValue Op = SDValue(Args[i].Node.Val, Args[i].Node.getResNo() + Value); ISD::ArgFlagsTy Flags; unsigned OriginalAlignment = getTargetData()->getABITypeAlignment(ArgTy); @@ -4870,13 +5169,29 @@ SDValue TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) { // SelectionDAGISel code //===----------------------------------------------------------------------===// +SelectionDAGISel::SelectionDAGISel(TargetLowering &tli, bool fast) : + FunctionPass((intptr_t)&ID), TLI(tli), + FuncInfo(new FunctionLoweringInfo(TLI)), + CurDAG(new SelectionDAG(TLI, *FuncInfo)), + SDL(new SelectionDAGLowering(*CurDAG, TLI, *FuncInfo)), + GFI(), + Fast(fast), + DAGSize(0) +{} + +SelectionDAGISel::~SelectionDAGISel() { + delete SDL; + delete CurDAG; + delete FuncInfo; +} + unsigned SelectionDAGISel::MakeReg(MVT VT) { return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); } void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } @@ -4885,35 +5200,39 @@ bool SelectionDAGISel::runOnFunction(Function &Fn) { AA = &getAnalysis(); MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine()); - if (MF.getFunction()->hasCollector()) - GCI = &getAnalysis().get(*MF.getFunction()); + if (MF.getFunction()->hasGC()) + GFI = &getAnalysis().getFunctionInfo(*MF.getFunction()); else - GCI = 0; + GFI = 0; RegInfo = &MF.getRegInfo(); DOUT << "\n\n\n=== " << Fn.getName() << "\n"; - FunctionLoweringInfo FuncInfo(TLI, Fn, MF); + FuncInfo->set(Fn, MF); + CurDAG->init(MF, getAnalysisToUpdate()); + SDL->init(GFI, *AA); for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) if (InvokeInst *Invoke = dyn_cast(I->getTerminator())) // Mark landing pad. - FuncInfo.MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); + FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); - SelectAllBasicBlocks(Fn, MF, FuncInfo); + SelectAllBasicBlocks(Fn, MF); // Add function live-ins to entry block live-in set. BasicBlock *EntryBB = &Fn.getEntryBlock(); - BB = FuncInfo.MBBMap[EntryBB]; + BB = FuncInfo->MBBMap[EntryBB]; if (!RegInfo->livein_empty()) for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(), E = RegInfo->livein_end(); I != E; ++I) BB->addLiveIn(I->first); #ifndef NDEBUG - assert(FuncInfo.CatchInfoFound.size() == FuncInfo.CatchInfoLost.size() && + assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() && "Not all catch info was assigned to a landing pad!"); #endif + FuncInfo->clear(); + return true; } @@ -4931,13 +5250,12 @@ void SelectionDAGLowering::CopyValueToVirtualRegister(Value *V, unsigned Reg) { } void SelectionDAGISel:: -LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL) { +LowerArguments(BasicBlock *LLVMBB) { // If this is the entry block, emit arguments. Function &F = *LLVMBB->getParent(); - FunctionLoweringInfo &FuncInfo = SDL.FuncInfo; - SDValue OldRoot = SDL.DAG.getRoot(); + SDValue OldRoot = SDL->DAG.getRoot(); SmallVector Args; - TLI.LowerArguments(F, SDL.DAG, Args); + TLI.LowerArguments(F, SDL->DAG, Args); unsigned a = 0; for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); @@ -4946,12 +5264,12 @@ LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL) { ComputeValueVTs(TLI, AI->getType(), ValueVTs); unsigned NumValues = ValueVTs.size(); if (!AI->use_empty()) { - SDL.setValue(AI, SDL.DAG.getMergeValues(&Args[a], NumValues)); + SDL->setValue(AI, SDL->DAG.getMergeValues(&Args[a], NumValues)); // If this argument is live outside of the entry block, insert a copy from // whereever we got it to the vreg that other BB's will reference it as. - DenseMap::iterator VMI=FuncInfo.ValueMap.find(AI); - if (VMI != FuncInfo.ValueMap.end()) { - SDL.CopyValueToVirtualRegister(AI, VMI->second); + DenseMap::iterator VMI=FuncInfo->ValueMap.find(AI); + if (VMI != FuncInfo->ValueMap.end()) { + SDL->CopyValueToVirtualRegister(AI, VMI->second); } } a += NumValues; @@ -4959,7 +5277,7 @@ LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL) { // Finally, if the target has anything special to do, allow it to do so. // FIXME: this should insert code into the DAG! - EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction()); + EmitFunctionEntryCode(F, SDL->DAG.getMachineFunction()); } static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB, @@ -5002,8 +5320,8 @@ static bool IsPossiblyOverwrittenArgumentOfTailCall(SDValue Op, (Op.getOpcode() == ISD::LOAD && IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(1))) || (Op.getOpcode() == ISD::MERGE_VALUES && - Op.getOperand(Op.ResNo).getOpcode() == ISD::LOAD && - IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(Op.ResNo). + Op.getOperand(Op.getResNo()).getOpcode() == ISD::LOAD && + IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(Op.getResNo()). getOperand(1)))) return true; return false; @@ -5084,25 +5402,99 @@ static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG, } } -void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, - std::vector > &PHINodesToUpdate, - FunctionLoweringInfo &FuncInfo) { - SelectionDAGLowering SDL(DAG, TLI, *AA, FuncInfo, GCI); +/// Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to +/// ensure constants are generated when needed. Remember the virtual registers +/// that need to be added to the Machine PHI nodes as input. We cannot just +/// directly add them, because expansion might result in multiple MBB's for one +/// BB. As such, the start of the BB might correspond to a different MBB than +/// the end. +/// +void +SelectionDAGISel::HandlePHINodesInSuccessorBlocks(BasicBlock *LLVMBB) { + TerminatorInst *TI = LLVMBB->getTerminator(); + + SmallPtrSet SuccsHandled; + // Check successor nodes' PHI nodes that expect a constant to be available + // from this block. + for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { + BasicBlock *SuccBB = TI->getSuccessor(succ); + if (!isa(SuccBB->begin())) continue; + MachineBasicBlock *SuccMBB = FuncInfo->MBBMap[SuccBB]; + + // If this terminator has multiple identical successors (common for + // switches), only handle each succ once. + if (!SuccsHandled.insert(SuccMBB)) continue; + + MachineBasicBlock::iterator MBBI = SuccMBB->begin(); + PHINode *PN; + + // At this point we know that there is a 1-1 correspondence between LLVM PHI + // nodes and Machine PHI nodes, but the incoming operands have not been + // emitted yet. + for (BasicBlock::iterator I = SuccBB->begin(); + (PN = dyn_cast(I)); ++I) { + // Ignore dead phi's. + if (PN->use_empty()) continue; + + unsigned Reg; + Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); + + if (Constant *C = dyn_cast(PHIOp)) { + unsigned &RegOut = SDL->ConstantsOut[C]; + if (RegOut == 0) { + RegOut = FuncInfo->CreateRegForValue(C); + SDL->CopyValueToVirtualRegister(C, RegOut); + } + Reg = RegOut; + } else { + Reg = FuncInfo->ValueMap[PHIOp]; + if (Reg == 0) { + assert(isa(PHIOp) && + FuncInfo->StaticAllocaMap.count(cast(PHIOp)) && + "Didn't codegen value into a register!??"); + Reg = FuncInfo->CreateRegForValue(PHIOp); + SDL->CopyValueToVirtualRegister(PHIOp, Reg); + } + } + + // Remember that this register needs to added to the machine PHI node as + // the input for this MBB. + SmallVector ValueVTs; + ComputeValueVTs(TLI, PN->getType(), ValueVTs); + for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) { + MVT VT = ValueVTs[vti]; + unsigned NumRegisters = TLI.getNumRegisters(VT); + for (unsigned i = 0, e = NumRegisters; i != e; ++i) + SDL->PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); + Reg += NumRegisters; + } + } + } + SDL->ConstantsOut.clear(); + + // Lower the terminator after the copies are emitted. + SDL->visit(*LLVMBB->getTerminator()); +} + +void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, + BasicBlock::iterator Begin, + BasicBlock::iterator End, + bool DoArgs) { // Lower any arguments needed in this block if this is the entry block. - if (LLVMBB == &LLVMBB->getParent()->getEntryBlock()) - LowerArguments(LLVMBB, SDL); + if (DoArgs) + LowerArguments(LLVMBB); - BB = FuncInfo.MBBMap[LLVMBB]; - SDL.setCurrentBasicBlock(BB); + SDL->setCurrentBasicBlock(BB); - MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); + MachineModuleInfo *MMI = CurDAG->getMachineModuleInfo(); if (MMI && BB->isLandingPad()) { // Add a label to mark the beginning of the landing pad. Deletion of the // landing pad can thus be detected via the MachineModuleInfo. unsigned LabelID = MMI->addLandingPad(BB); - DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, DAG.getEntryNode(), LabelID)); + CurDAG->setRoot(CurDAG->getLabel(ISD::EH_LABEL, + CurDAG->getEntryNode(), LabelID)); // Mark exception register as live in. unsigned Reg = TLI.getExceptionAddressRegister(); @@ -5133,123 +5525,47 @@ void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, if (I == E) // No catch info found - try to extract some from the successor. - copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, FuncInfo); + copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo); } } // Lower all of the non-terminator instructions. - for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end(); - I != E; ++I) - SDL.visit(*I); + for (BasicBlock::iterator I = Begin; I != End; ++I) + if (!isa(I)) + SDL->visit(*I); // Ensure that all instructions which are used outside of their defining // blocks are available as virtual registers. Invoke is handled elsewhere. - for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I) + for (BasicBlock::iterator I = Begin; I != End; ++I) if (!I->use_empty() && !isa(I) && !isa(I)) { - DenseMap::iterator VMI =FuncInfo.ValueMap.find(I); - if (VMI != FuncInfo.ValueMap.end()) - SDL.CopyValueToVirtualRegister(I, VMI->second); + DenseMap::iterator VMI =FuncInfo->ValueMap.find(I); + if (VMI != FuncInfo->ValueMap.end()) + SDL->CopyValueToVirtualRegister(I, VMI->second); } - // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to - // ensure constants are generated when needed. Remember the virtual registers - // that need to be added to the Machine PHI nodes as input. We cannot just - // directly add them, because expansion might result in multiple MBB's for one - // BB. As such, the start of the BB might correspond to a different MBB than - // the end. - // - TerminatorInst *TI = LLVMBB->getTerminator(); - - // Emit constants only once even if used by multiple PHI nodes. - std::map ConstantsOut; - - // Vector bool would be better, but vector is really slow. - std::vector SuccsHandled; - if (TI->getNumSuccessors()) - SuccsHandled.resize(BB->getParent()->getNumBlockIDs()); - - // Check successor nodes' PHI nodes that expect a constant to be available - // from this block. - for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { - BasicBlock *SuccBB = TI->getSuccessor(succ); - if (!isa(SuccBB->begin())) continue; - MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB]; - - // If this terminator has multiple identical successors (common for - // switches), only handle each succ once. - unsigned SuccMBBNo = SuccMBB->getNumber(); - if (SuccsHandled[SuccMBBNo]) continue; - SuccsHandled[SuccMBBNo] = true; - - MachineBasicBlock::iterator MBBI = SuccMBB->begin(); - PHINode *PN; - - // At this point we know that there is a 1-1 correspondence between LLVM PHI - // nodes and Machine PHI nodes, but the incoming operands have not been - // emitted yet. - for (BasicBlock::iterator I = SuccBB->begin(); - (PN = dyn_cast(I)); ++I) { - // Ignore dead phi's. - if (PN->use_empty()) continue; - - unsigned Reg; - Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); - - if (Constant *C = dyn_cast(PHIOp)) { - unsigned &RegOut = ConstantsOut[C]; - if (RegOut == 0) { - RegOut = FuncInfo.CreateRegForValue(C); - SDL.CopyValueToVirtualRegister(C, RegOut); - } - Reg = RegOut; - } else { - Reg = FuncInfo.ValueMap[PHIOp]; - if (Reg == 0) { - assert(isa(PHIOp) && - FuncInfo.StaticAllocaMap.count(cast(PHIOp)) && - "Didn't codegen value into a register!??"); - Reg = FuncInfo.CreateRegForValue(PHIOp); - SDL.CopyValueToVirtualRegister(PHIOp, Reg); - } - } - - // Remember that this register needs to added to the machine PHI node as - // the input for this MBB. - MVT VT = TLI.getValueType(PN->getType()); - unsigned NumRegisters = TLI.getNumRegisters(VT); - for (unsigned i = 0, e = NumRegisters; i != e; ++i) - PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); - } - } - ConstantsOut.clear(); - - // Lower the terminator after the copies are emitted. - SDL.visit(*LLVMBB->getTerminator()); - - // Copy over any CaseBlock records that may now exist due to SwitchInst - // lowering, as well as any jump table information. - SwitchCases.clear(); - SwitchCases = SDL.SwitchCases; - JTCases.clear(); - JTCases = SDL.JTCases; - BitTestCases.clear(); - BitTestCases = SDL.BitTestCases; + // Handle PHI nodes in successor blocks. + if (Begin != End && End == LLVMBB->end()) + HandlePHINodesInSuccessorBlocks(LLVMBB); // Make sure the root of the DAG is up-to-date. - DAG.setRoot(SDL.getControlRoot()); + CurDAG->setRoot(SDL->getControlRoot()); // Check whether calls in this block are real tail calls. Fix up CALL nodes // with correct tailcall attribute so that the target can rely on the tailcall // attribute indicating whether the call is really eligible for tail call // optimization. - CheckDAGForTailCallsAndFixThem(DAG, TLI); + CheckDAGForTailCallsAndFixThem(*CurDAG, TLI); + + // Final step, emit the lowered DAG as machine code. + CodeGenAndEmitDAG(); + SDL->clear(); } -void SelectionDAGISel::ComputeLiveOutVRegInfo(SelectionDAG &DAG) { +void SelectionDAGISel::ComputeLiveOutVRegInfo() { SmallPtrSet VisitedNodes; SmallVector Worklist; - Worklist.push_back(DAG.getRoot().Val); + Worklist.push_back(CurDAG->getRoot().Val); APInt Mask; APInt KnownZero; @@ -5282,14 +5598,14 @@ void SelectionDAGISel::ComputeLiveOutVRegInfo(SelectionDAG &DAG) { if (!SrcVT.isInteger() || SrcVT.isVector()) continue; - unsigned NumSignBits = DAG.ComputeNumSignBits(Src); + unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits()); - DAG.ComputeMaskedBits(Src, Mask, KnownZero, KnownOne); + CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne); // Only install this information if it tells us something. if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) { DestReg -= TargetRegisterInfo::FirstVirtualRegister; - FunctionLoweringInfo &FLI = DAG.getFunctionLoweringInfo(); + FunctionLoweringInfo &FLI = CurDAG->getFunctionLoweringInfo(); if (DestReg >= FLI.LiveOutRegInfo.size()) FLI.LiveOutRegInfo.resize(DestReg+1); FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[DestReg]; @@ -5300,102 +5616,102 @@ void SelectionDAGISel::ComputeLiveOutVRegInfo(SelectionDAG &DAG) { } } -void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { +void SelectionDAGISel::CodeGenAndEmitDAG() { std::string GroupName; if (TimePassesIsEnabled) GroupName = "Instruction Selection and Scheduling"; std::string BlockName; if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs || ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs || ViewSUnitDAGs) - BlockName = DAG.getMachineFunction().getFunction()->getName() + ':' + + BlockName = CurDAG->getMachineFunction().getFunction()->getName() + ':' + BB->getBasicBlock()->getName(); DOUT << "Initial selection DAG:\n"; - DEBUG(DAG.dump()); + DEBUG(CurDAG->dump()); - if (ViewDAGCombine1) DAG.viewGraph("dag-combine1 input for " + BlockName); + if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName); // Run the DAG combiner in pre-legalize mode. if (TimePassesIsEnabled) { NamedRegionTimer T("DAG Combining 1", GroupName); - DAG.Combine(false, *AA); + CurDAG->Combine(false, *AA, Fast); } else { - DAG.Combine(false, *AA); + CurDAG->Combine(false, *AA, Fast); } DOUT << "Optimized lowered selection DAG:\n"; - DEBUG(DAG.dump()); + DEBUG(CurDAG->dump()); // Second step, hack on the DAG until it only uses operations and types that // the target supports. if (EnableLegalizeTypes) {// Enable this some day. - if (ViewLegalizeTypesDAGs) DAG.viewGraph("legalize-types input for " + - BlockName); + if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " + + BlockName); if (TimePassesIsEnabled) { NamedRegionTimer T("Type Legalization", GroupName); - DAG.LegalizeTypes(); + CurDAG->LegalizeTypes(); } else { - DAG.LegalizeTypes(); + CurDAG->LegalizeTypes(); } DOUT << "Type-legalized selection DAG:\n"; - DEBUG(DAG.dump()); + DEBUG(CurDAG->dump()); // TODO: enable a dag combine pass here. } - if (ViewLegalizeDAGs) DAG.viewGraph("legalize input for " + BlockName); + if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName); if (TimePassesIsEnabled) { NamedRegionTimer T("DAG Legalization", GroupName); - DAG.Legalize(); + CurDAG->Legalize(); } else { - DAG.Legalize(); + CurDAG->Legalize(); } DOUT << "Legalized selection DAG:\n"; - DEBUG(DAG.dump()); + DEBUG(CurDAG->dump()); - if (ViewDAGCombine2) DAG.viewGraph("dag-combine2 input for " + BlockName); + if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName); // Run the DAG combiner in post-legalize mode. if (TimePassesIsEnabled) { NamedRegionTimer T("DAG Combining 2", GroupName); - DAG.Combine(true, *AA); + CurDAG->Combine(true, *AA, Fast); } else { - DAG.Combine(true, *AA); + CurDAG->Combine(true, *AA, Fast); } DOUT << "Optimized legalized selection DAG:\n"; - DEBUG(DAG.dump()); + DEBUG(CurDAG->dump()); - if (ViewISelDAGs) DAG.viewGraph("isel input for " + BlockName); + if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName); - if (!FastISel && EnableValueProp) - ComputeLiveOutVRegInfo(DAG); + if (!Fast && EnableValueProp) + ComputeLiveOutVRegInfo(); // Third, instruction select all of the operations to machine code, adding the // code to the MachineBasicBlock. if (TimePassesIsEnabled) { NamedRegionTimer T("Instruction Selection", GroupName); - InstructionSelect(DAG); + InstructionSelect(); } else { - InstructionSelect(DAG); + InstructionSelect(); } DOUT << "Selected selection DAG:\n"; - DEBUG(DAG.dump()); + DEBUG(CurDAG->dump()); - if (ViewSchedDAGs) DAG.viewGraph("scheduler input for " + BlockName); + if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName); // Schedule machine code. ScheduleDAG *Scheduler; if (TimePassesIsEnabled) { NamedRegionTimer T("Instruction Scheduling", GroupName); - Scheduler = Schedule(DAG); + Scheduler = Schedule(); } else { - Scheduler = Schedule(DAG); + Scheduler = Schedule(); } if (ViewSUnitDAGs) Scheduler->viewGraph(); @@ -5417,200 +5733,224 @@ void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { delete Scheduler; } - // Perform target specific isel post processing. - if (TimePassesIsEnabled) { - NamedRegionTimer T("Instruction Selection Post Processing", GroupName); - InstructionSelectPostProcessing(); - } else { - InstructionSelectPostProcessing(); - } - DOUT << "Selected machine code:\n"; DEBUG(BB->dump()); } -void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF, - FunctionLoweringInfo &FuncInfo) { - // Define NodeAllocator here so that memory allocation is reused for - // each basic block. - NodeAllocatorType NodeAllocator; +void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF) { + for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { + BasicBlock *LLVMBB = &*I; + BB = FuncInfo->MBBMap[LLVMBB]; + + BasicBlock::iterator Begin = LLVMBB->begin(); + BasicBlock::iterator End = LLVMBB->end(); + bool DoArgs = LLVMBB == &Fn.getEntryBlock(); + + // Before doing SelectionDAG ISel, see if FastISel has been requested. + // FastISel doesn't support EH landing pads, which require special handling. + if (EnableFastISel && !BB->isLandingPad()) { + if (FastISel *F = TLI.createFastISel(*FuncInfo->MF)) { + while (Begin != End) { + Begin = F->SelectInstructions(Begin, End, FuncInfo->ValueMap, + FuncInfo->MBBMap, BB); + + if (Begin == End) + // The "fast" selector selected the entire block, so we're done. + break; - for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) - SelectBasicBlock(I, MF, FuncInfo, NodeAllocator); + // Handle certain instructions as single-LLVM-Instruction blocks. + if (isa(Begin) || isa(Begin) || + isa(Begin)) { + if (Begin->getType() != Type::VoidTy) { + unsigned &R = FuncInfo->ValueMap[Begin]; + if (!R) + R = FuncInfo->CreateRegForValue(Begin); + } + + SelectBasicBlock(LLVMBB, Begin, next(Begin), DoArgs); + + ++Begin; + DoArgs = false; + continue; + } + + if (!DisableFastISelAbort && + // For now, don't abort on non-conditional-branch terminators. + (!isa(Begin) || + (isa(Begin) && + cast(Begin)->isUnconditional()))) { + // The "fast" selector couldn't handle something and bailed. + // For the purpose of debugging, just abort. +#ifndef NDEBUG + Begin->dump(); +#endif + assert(0 && "FastISel didn't select the entire block"); + } + break; + } + delete F; + } + } + + if (Begin != End || DoArgs) + SelectBasicBlock(LLVMBB, Begin, End, DoArgs); + + FinishBasicBlock(); + } } void -SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, - FunctionLoweringInfo &FuncInfo, - NodeAllocatorType &NodeAllocator) { - std::vector > PHINodesToUpdate; - { - SelectionDAG DAG(TLI, MF, FuncInfo, - getAnalysisToUpdate(), - NodeAllocator); - CurDAG = &DAG; - - // First step, lower LLVM code to some DAG. This DAG may use operations and - // types that are not supported by the target. - BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo); +SelectionDAGISel::FinishBasicBlock() { - // Second step, emit the lowered DAG as machine code. - CodeGenAndEmitDAG(DAG); - } + // Perform target specific isel post processing. + InstructionSelectPostProcessing(); + + DOUT << "Target-post-processed machine code:\n"; + DEBUG(BB->dump()); DOUT << "Total amount of phi nodes to update: " - << PHINodesToUpdate.size() << "\n"; - DEBUG(for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) - DOUT << "Node " << i << " : (" << PHINodesToUpdate[i].first - << ", " << PHINodesToUpdate[i].second << ")\n";); + << SDL->PHINodesToUpdate.size() << "\n"; + DEBUG(for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) + DOUT << "Node " << i << " : (" << SDL->PHINodesToUpdate[i].first + << ", " << SDL->PHINodesToUpdate[i].second << ")\n";); // Next, now that we know what the last MBB the LLVM BB expanded is, update // PHI nodes in successors. - if (SwitchCases.empty() && JTCases.empty() && BitTestCases.empty()) { - for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { - MachineInstr *PHI = PHINodesToUpdate[i].first; + if (SDL->SwitchCases.empty() && + SDL->JTCases.empty() && + SDL->BitTestCases.empty()) { + for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { + MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; assert(PHI->getOpcode() == TargetInstrInfo::PHI && "This is not a machine PHI node that we are updating!"); - PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second, + PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, false)); PHI->addOperand(MachineOperand::CreateMBB(BB)); } + SDL->PHINodesToUpdate.clear(); return; } - for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i) { + for (unsigned i = 0, e = SDL->BitTestCases.size(); i != e; ++i) { // Lower header first, if it wasn't already lowered - if (!BitTestCases[i].Emitted) { - SelectionDAG HSDAG(TLI, MF, FuncInfo, - getAnalysisToUpdate(), - NodeAllocator); - CurDAG = &HSDAG; - SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); + if (!SDL->BitTestCases[i].Emitted) { // Set the current basic block to the mbb we wish to insert the code into - BB = BitTestCases[i].Parent; - HSDL.setCurrentBasicBlock(BB); + BB = SDL->BitTestCases[i].Parent; + SDL->setCurrentBasicBlock(BB); // Emit the code - HSDL.visitBitTestHeader(BitTestCases[i]); - HSDAG.setRoot(HSDL.getRoot()); - CodeGenAndEmitDAG(HSDAG); + SDL->visitBitTestHeader(SDL->BitTestCases[i]); + CurDAG->setRoot(SDL->getRoot()); + CodeGenAndEmitDAG(); + SDL->clear(); } - for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) { - SelectionDAG BSDAG(TLI, MF, FuncInfo, - getAnalysisToUpdate(), - NodeAllocator); - CurDAG = &BSDAG; - SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo, GCI); + for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); j != ej; ++j) { // Set the current basic block to the mbb we wish to insert the code into - BB = BitTestCases[i].Cases[j].ThisBB; - BSDL.setCurrentBasicBlock(BB); + BB = SDL->BitTestCases[i].Cases[j].ThisBB; + SDL->setCurrentBasicBlock(BB); // Emit the code if (j+1 != ej) - BSDL.visitBitTestCase(BitTestCases[i].Cases[j+1].ThisBB, - BitTestCases[i].Reg, - BitTestCases[i].Cases[j]); + SDL->visitBitTestCase(SDL->BitTestCases[i].Cases[j+1].ThisBB, + SDL->BitTestCases[i].Reg, + SDL->BitTestCases[i].Cases[j]); else - BSDL.visitBitTestCase(BitTestCases[i].Default, - BitTestCases[i].Reg, - BitTestCases[i].Cases[j]); + SDL->visitBitTestCase(SDL->BitTestCases[i].Default, + SDL->BitTestCases[i].Reg, + SDL->BitTestCases[i].Cases[j]); - BSDAG.setRoot(BSDL.getRoot()); - CodeGenAndEmitDAG(BSDAG); + CurDAG->setRoot(SDL->getRoot()); + CodeGenAndEmitDAG(); + SDL->clear(); } // Update PHI Nodes - for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { - MachineInstr *PHI = PHINodesToUpdate[pi].first; + for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { + MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; MachineBasicBlock *PHIBB = PHI->getParent(); assert(PHI->getOpcode() == TargetInstrInfo::PHI && "This is not a machine PHI node that we are updating!"); // This is "default" BB. We have two jumps to it. From "header" BB and // from last "case" BB. - if (PHIBB == BitTestCases[i].Default) { - PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, + if (PHIBB == SDL->BitTestCases[i].Default) { + PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, false)); - PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Parent)); - PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, + PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Parent)); + PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, false)); - PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Cases. + PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Cases. back().ThisBB)); } // One of "cases" BB. - for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) { - MachineBasicBlock* cBB = BitTestCases[i].Cases[j].ThisBB; + for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); + j != ej; ++j) { + MachineBasicBlock* cBB = SDL->BitTestCases[i].Cases[j].ThisBB; if (cBB->succ_end() != std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) { - PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, + PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, false)); PHI->addOperand(MachineOperand::CreateMBB(cBB)); } } } } + SDL->BitTestCases.clear(); // If the JumpTable record is filled in, then we need to emit a jump table. // Updating the PHI nodes is tricky in this case, since we need to determine // whether the PHI is a successor of the range check MBB or the jump table MBB - for (unsigned i = 0, e = JTCases.size(); i != e; ++i) { + for (unsigned i = 0, e = SDL->JTCases.size(); i != e; ++i) { // Lower header first, if it wasn't already lowered - if (!JTCases[i].first.Emitted) { - SelectionDAG HSDAG(TLI, MF, FuncInfo, - getAnalysisToUpdate(), - NodeAllocator); - CurDAG = &HSDAG; - SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); + if (!SDL->JTCases[i].first.Emitted) { // Set the current basic block to the mbb we wish to insert the code into - BB = JTCases[i].first.HeaderBB; - HSDL.setCurrentBasicBlock(BB); + BB = SDL->JTCases[i].first.HeaderBB; + SDL->setCurrentBasicBlock(BB); // Emit the code - HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first); - HSDAG.setRoot(HSDL.getRoot()); - CodeGenAndEmitDAG(HSDAG); + SDL->visitJumpTableHeader(SDL->JTCases[i].second, SDL->JTCases[i].first); + CurDAG->setRoot(SDL->getRoot()); + CodeGenAndEmitDAG(); + SDL->clear(); } - SelectionDAG JSDAG(TLI, MF, FuncInfo, - getAnalysisToUpdate(), - NodeAllocator); - CurDAG = &JSDAG; - SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into - BB = JTCases[i].second.MBB; - JSDL.setCurrentBasicBlock(BB); + BB = SDL->JTCases[i].second.MBB; + SDL->setCurrentBasicBlock(BB); // Emit the code - JSDL.visitJumpTable(JTCases[i].second); - JSDAG.setRoot(JSDL.getRoot()); - CodeGenAndEmitDAG(JSDAG); + SDL->visitJumpTable(SDL->JTCases[i].second); + CurDAG->setRoot(SDL->getRoot()); + CodeGenAndEmitDAG(); + SDL->clear(); // Update PHI Nodes - for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { - MachineInstr *PHI = PHINodesToUpdate[pi].first; + for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { + MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; MachineBasicBlock *PHIBB = PHI->getParent(); assert(PHI->getOpcode() == TargetInstrInfo::PHI && "This is not a machine PHI node that we are updating!"); // "default" BB. We can go there only from header BB. - if (PHIBB == JTCases[i].second.Default) { - PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, + if (PHIBB == SDL->JTCases[i].second.Default) { + PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, false)); - PHI->addOperand(MachineOperand::CreateMBB(JTCases[i].first.HeaderBB)); + PHI->addOperand(MachineOperand::CreateMBB(SDL->JTCases[i].first.HeaderBB)); } // JT BB. Just iterate over successors here if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { - PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, + PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, false)); PHI->addOperand(MachineOperand::CreateMBB(BB)); } } } + SDL->JTCases.clear(); // If the switch block involved a branch to one of the actual successors, we // need to update PHI nodes in that block. - for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { - MachineInstr *PHI = PHINodesToUpdate[i].first; + for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { + MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; assert(PHI->getOpcode() == TargetInstrInfo::PHI && "This is not a machine PHI node that we are updating!"); if (BB->isSuccessor(PHI->getParent())) { - PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second, + PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, false)); PHI->addOperand(MachineOperand::CreateMBB(BB)); } @@ -5618,58 +5958,57 @@ SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, // If we generated any switch lowering information, build and codegen any // additional DAGs necessary. - for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) { - SelectionDAG SDAG(TLI, MF, FuncInfo, - getAnalysisToUpdate(), - NodeAllocator); - CurDAG = &SDAG; - SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI); - + for (unsigned i = 0, e = SDL->SwitchCases.size(); i != e; ++i) { // Set the current basic block to the mbb we wish to insert the code into - BB = SwitchCases[i].ThisBB; - SDL.setCurrentBasicBlock(BB); + BB = SDL->SwitchCases[i].ThisBB; + SDL->setCurrentBasicBlock(BB); // Emit the code - SDL.visitSwitchCase(SwitchCases[i]); - SDAG.setRoot(SDL.getRoot()); - CodeGenAndEmitDAG(SDAG); + SDL->visitSwitchCase(SDL->SwitchCases[i]); + CurDAG->setRoot(SDL->getRoot()); + CodeGenAndEmitDAG(); + SDL->clear(); // Handle any PHI nodes in successors of this chunk, as if we were coming // from the original BB before switch expansion. Note that PHI nodes can // occur multiple times in PHINodesToUpdate. We have to be very careful to // handle them the right number of times. - while ((BB = SwitchCases[i].TrueBB)) { // Handle LHS and RHS. + while ((BB = SDL->SwitchCases[i].TrueBB)) { // Handle LHS and RHS. for (MachineBasicBlock::iterator Phi = BB->begin(); Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){ // This value for this PHI node is recorded in PHINodesToUpdate, get it. for (unsigned pn = 0; ; ++pn) { - assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!"); - if (PHINodesToUpdate[pn].first == Phi) { - Phi->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pn]. + assert(pn != SDL->PHINodesToUpdate.size() && + "Didn't find PHI entry!"); + if (SDL->PHINodesToUpdate[pn].first == Phi) { + Phi->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pn]. second, false)); - Phi->addOperand(MachineOperand::CreateMBB(SwitchCases[i].ThisBB)); + Phi->addOperand(MachineOperand::CreateMBB(SDL->SwitchCases[i].ThisBB)); break; } } } // Don't process RHS if same block as LHS. - if (BB == SwitchCases[i].FalseBB) - SwitchCases[i].FalseBB = 0; + if (BB == SDL->SwitchCases[i].FalseBB) + SDL->SwitchCases[i].FalseBB = 0; // If we haven't handled the RHS, do so now. Otherwise, we're done. - SwitchCases[i].TrueBB = SwitchCases[i].FalseBB; - SwitchCases[i].FalseBB = 0; + SDL->SwitchCases[i].TrueBB = SDL->SwitchCases[i].FalseBB; + SDL->SwitchCases[i].FalseBB = 0; } - assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0); + assert(SDL->SwitchCases[i].TrueBB == 0 && SDL->SwitchCases[i].FalseBB == 0); } + SDL->SwitchCases.clear(); + + SDL->PHINodesToUpdate.clear(); } /// Schedule - Pick a safe ordering for instructions for each /// target node in the graph. /// -ScheduleDAG *SelectionDAGISel::Schedule(SelectionDAG &DAG) { +ScheduleDAG *SelectionDAGISel::Schedule() { RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); if (!Ctor) { @@ -5677,7 +6016,7 @@ ScheduleDAG *SelectionDAGISel::Schedule(SelectionDAG &DAG) { RegisterScheduler::setDefault(Ctor); } - ScheduleDAG *Scheduler = Ctor(this, &DAG, BB, FastISel); + ScheduleDAG *Scheduler = Ctor(this, CurDAG, BB, Fast); Scheduler->Run(); return Scheduler; @@ -5760,7 +6099,7 @@ bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated /// by tblgen. Others should not call it. void SelectionDAGISel:: -SelectInlineAsmMemoryOperands(std::vector &Ops, SelectionDAG &DAG) { +SelectInlineAsmMemoryOperands(std::vector &Ops) { std::vector InOps; std::swap(InOps, Ops); @@ -5781,15 +6120,15 @@ SelectInlineAsmMemoryOperands(std::vector &Ops, SelectionDAG &DAG) { assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); // Otherwise, this is a memory operand. Ask the target to select it. std::vector SelOps; - if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) { + if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) { cerr << "Could not match memory address. Inline asm failure!\n"; exit(1); } // Add this to the output node. - MVT IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy(); - Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3), - IntPtrTy)); + MVT IntPtrTy = CurDAG->getTargetLoweringInfo().getPointerTy(); + Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size() << 3), + IntPtrTy)); Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); i += 2; }