X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAGISel.cpp;h=b4b81cd4f1368a11e70d27c9a55a337b1a684b95;hb=edfba7e707a4f2f2e800843a7ef980c27d7f4eff;hp=50799d10edcb4a2014218aac003f924e4db68273;hpb=a47c6c37034f4e57bc8187e959da4eadb6e24afa;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 50799d10edc..b4b81cd4f13 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -42,12 +42,19 @@ #include "llvm/Target/TargetLowering.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetOptions.h" -#include "llvm/Support/MathExtras.h" -#include "llvm/Support/Debug.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/Timer.h" #include using namespace llvm; +static cl::opt +EnableValueProp("enable-value-prop", cl::Hidden); +static cl::opt +EnableLegalizeTypes("enable-legalize-types", cl::Hidden); + + #ifndef NDEBUG static cl::opt ViewISelDAGs("view-isel-dags", cl::Hidden, @@ -96,37 +103,31 @@ static unsigned ComputeLinearIndex(const TargetLowering &TLI, const Type *Ty, const unsigned *IndicesEnd, unsigned CurIndex = 0) { // Base case: We're done. - if (Indices == IndicesEnd) + if (Indices && Indices == IndicesEnd) return CurIndex; - // Otherwise we need to recurse. A non-negative value is used to - // indicate the final result value; a negative value carries the - // complemented position to continue the search. - CurIndex = ~CurIndex; - // Given a struct type, recursively traverse the elements. if (const StructType *STy = dyn_cast(Ty)) { - for (StructType::element_iterator EI = STy->element_begin(), + for (StructType::element_iterator EB = STy->element_begin(), + EI = EB, EE = STy->element_end(); EI != EE; ++EI) { - CurIndex = ComputeLinearIndex(TLI, *EI, Indices+1, IndicesEnd, - ~CurIndex); - if ((int)CurIndex >= 0) - return CurIndex; + if (Indices && *Indices == unsigned(EI - EB)) + return ComputeLinearIndex(TLI, *EI, Indices+1, IndicesEnd, CurIndex); + CurIndex = ComputeLinearIndex(TLI, *EI, 0, 0, CurIndex); } } // Given an array type, recursively traverse the elements. else if (const ArrayType *ATy = dyn_cast(Ty)) { const Type *EltTy = ATy->getElementType(); for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { - CurIndex = ComputeLinearIndex(TLI, EltTy, Indices+1, IndicesEnd, - ~CurIndex); - if ((int)CurIndex >= 0) - return CurIndex; + if (Indices && *Indices == i) + return ComputeLinearIndex(TLI, EltTy, Indices+1, IndicesEnd, CurIndex); + CurIndex = ComputeLinearIndex(TLI, EltTy, 0, 0, CurIndex); } } // We haven't found the type we're looking for, so keep searching. - return CurIndex; + return CurIndex + 1; } /// ComputeValueVTs - Given an LLVM IR type, compute a sequence of @@ -266,15 +267,16 @@ namespace llvm { /// for the target. ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB) { + MachineBasicBlock *BB, + bool Fast) { TargetLowering &TLI = IS->getTargetLowering(); if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) { - return createTDListDAGScheduler(IS, DAG, BB); + return createTDListDAGScheduler(IS, DAG, BB, Fast); } else { assert(TLI.getSchedulingPreference() == TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); - return createBURRListDAGScheduler(IS, DAG, BB); + return createBURRListDAGScheduler(IS, DAG, BB, Fast); } } @@ -326,6 +328,16 @@ namespace llvm { assert(R == 0 && "Already initialized this value register!"); return R = CreateRegForValue(V); } + + struct LiveOutInfo { + unsigned NumSignBits; + APInt KnownOne, KnownZero; + LiveOutInfo() : NumSignBits(0) {} + }; + + /// LiveOutRegInfo - Information about live out vregs, indexed by their + /// register number offset by 'FirstVirtualRegister'. + std::vector LiveOutRegInfo; }; } @@ -404,9 +416,9 @@ FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, // also creates the initial PHI MachineInstrs, though none of the input // operands are populated. for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) { - MachineBasicBlock *MBB = new MachineBasicBlock(BB); + MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB); MBBMap[BB] = MBB; - MF.getBasicBlockList().push_back(MBB); + MF.push_back(MBB); // Create Machine PHI nodes for LLVM PHI nodes, lowering them as // appropriate. @@ -465,7 +477,7 @@ class SelectionDAGLowering { /// them up and then emit token factor nodes when possible. This allows us to /// get simple disambiguation between loads without worrying about alias /// analysis. - std::vector PendingLoads; + SmallVector PendingLoads; /// PendingExports - CopyToReg nodes that copy values to virtual registers /// for export to other blocks need to be emitted before any terminator @@ -1147,18 +1159,13 @@ SDOperand SelectionDAGLowering::getValue(const Value *V) { if (isa(C) || isa(C)) { SmallVector Constants; - SmallVector ValueVTs; for (User::const_op_iterator OI = C->op_begin(), OE = C->op_end(); OI != OE; ++OI) { SDNode *Val = getValue(*OI).Val; - for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i) { + for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i) Constants.push_back(SDOperand(Val, i)); - ValueVTs.push_back(Val->getValueType(i)); - } } - return DAG.getNode(ISD::MERGE_VALUES, - DAG.getVTList(&ValueVTs[0], ValueVTs.size()), - &Constants[0], Constants.size()); + return DAG.getMergeValues(&Constants[0], Constants.size()); } if (const ArrayType *ATy = dyn_cast(C->getType())) { @@ -1169,7 +1176,6 @@ SDOperand SelectionDAGLowering::getValue(const Value *V) { return SDOperand(); // empty array MVT EltVT = TLI.getValueType(ATy->getElementType()); SmallVector Constants(NumElts); - SmallVector ValueVTs(NumElts, EltVT); for (unsigned i = 0, e = NumElts; i != e; ++i) { if (isa(C)) Constants[i] = DAG.getNode(ISD::UNDEF, EltVT); @@ -1178,9 +1184,7 @@ SDOperand SelectionDAGLowering::getValue(const Value *V) { else Constants[i] = DAG.getConstant(0, EltVT); } - return DAG.getNode(ISD::MERGE_VALUES, - DAG.getVTList(&ValueVTs[0], ValueVTs.size()), - &Constants[0], Constants.size()); + return DAG.getMergeValues(&Constants[0], Constants.size()); } if (const StructType *STy = dyn_cast(C->getType())) { @@ -1190,10 +1194,8 @@ SDOperand SelectionDAGLowering::getValue(const Value *V) { if (NumElts == 0) return SDOperand(); // empty struct SmallVector Constants(NumElts); - SmallVector ValueVTs(NumElts); for (unsigned i = 0, e = NumElts; i != e; ++i) { MVT EltVT = TLI.getValueType(STy->getElementType(i)); - ValueVTs[i] = EltVT; if (isa(C)) Constants[i] = DAG.getNode(ISD::UNDEF, EltVT); else if (EltVT.isFloatingPoint()) @@ -1201,9 +1203,7 @@ SDOperand SelectionDAGLowering::getValue(const Value *V) { else Constants[i] = DAG.getConstant(0, EltVT); } - return DAG.getNode(ISD::MERGE_VALUES, - DAG.getVTList(&ValueVTs[0], ValueVTs.size()), - &Constants[0], Constants.size()); + return DAG.getMergeValues(&Constants[0], Constants.size()); } const VectorType *VecTy = cast(V->getType()); @@ -1262,32 +1262,38 @@ void SelectionDAGLowering::visitRet(ReturnInst &I) { NewValues.push_back(getControlRoot()); for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { SDOperand RetOp = getValue(I.getOperand(i)); - MVT VT = RetOp.getValueType(); - - // FIXME: C calling convention requires the return type to be promoted to - // at least 32-bit. But this is not necessary for non-C calling conventions. - if (VT.isInteger()) { - MVT MinVT = TLI.getRegisterType(MVT::i32); - if (VT.bitsLT(MinVT)) - VT = MinVT; - } - unsigned NumParts = TLI.getNumRegisters(VT); - MVT PartVT = TLI.getRegisterType(VT); - SmallVector Parts(NumParts); - ISD::NodeType ExtendKind = ISD::ANY_EXTEND; + SmallVector ValueVTs; + ComputeValueVTs(TLI, I.getOperand(i)->getType(), ValueVTs); + for (unsigned j = 0, f = ValueVTs.size(); j != f; ++j) { + MVT VT = ValueVTs[j]; + + // FIXME: C calling convention requires the return type to be promoted to + // at least 32-bit. But this is not necessary for non-C calling conventions. + if (VT.isInteger()) { + MVT MinVT = TLI.getRegisterType(MVT::i32); + if (VT.bitsLT(MinVT)) + VT = MinVT; + } - const Function *F = I.getParent()->getParent(); - if (F->paramHasAttr(0, ParamAttr::SExt)) - ExtendKind = ISD::SIGN_EXTEND; - else if (F->paramHasAttr(0, ParamAttr::ZExt)) - ExtendKind = ISD::ZERO_EXTEND; + unsigned NumParts = TLI.getNumRegisters(VT); + MVT PartVT = TLI.getRegisterType(VT); + SmallVector Parts(NumParts); + ISD::NodeType ExtendKind = ISD::ANY_EXTEND; + + const Function *F = I.getParent()->getParent(); + if (F->paramHasAttr(0, ParamAttr::SExt)) + ExtendKind = ISD::SIGN_EXTEND; + else if (F->paramHasAttr(0, ParamAttr::ZExt)) + ExtendKind = ISD::ZERO_EXTEND; - getCopyToParts(DAG, RetOp, &Parts[0], NumParts, PartVT, ExtendKind); + getCopyToParts(DAG, SDOperand(RetOp.Val, RetOp.ResNo + j), + &Parts[0], NumParts, PartVT, ExtendKind); - for (unsigned i = 0; i < NumParts; ++i) { - NewValues.push_back(Parts[i]); - NewValues.push_back(DAG.getArgFlags(ISD::ArgFlagsTy())); + for (unsigned i = 0; i < NumParts; ++i) { + NewValues.push_back(Parts[i]); + NewValues.push_back(DAG.getArgFlags(ISD::ArgFlagsTy())); + } } } DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, @@ -1428,8 +1434,9 @@ void SelectionDAGLowering::FindMergedConditions(Value *Cond, // Create TmpBB after CurBB. MachineFunction::iterator BBI = CurBB; - MachineBasicBlock *TmpBB = new MachineBasicBlock(CurBB->getBasicBlock()); - CurBB->getParent()->getBasicBlockList().insert(++BBI, TmpBB); + MachineFunction &MF = DAG.getMachineFunction(); + MachineBasicBlock *TmpBB = MF.CreateMachineBasicBlock(CurBB->getBasicBlock()); + CurBB->getParent()->insert(++BBI, TmpBB); if (Opc == Instruction::Or) { // Codegen X | Y as: @@ -1550,7 +1557,7 @@ void SelectionDAGLowering::visitBr(BranchInst &I) { // Okay, we decided not to do this, remove any inserted MBB's and clear // SwitchCases. for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) - CurMBB->getParent()->getBasicBlockList().erase(SwitchCases[i].ThisBB); + CurMBB->getParent()->erase(SwitchCases[i].ThisBB); SwitchCases.clear(); } @@ -1748,12 +1755,11 @@ void SelectionDAGLowering::visitBitTestCase(MachineBasicBlock* NextMBB, unsigned Reg, SelectionDAGISel::BitTestCase &B) { // Emit bit tests and jumps - SDOperand SwitchVal = DAG.getCopyFromReg(getControlRoot(), Reg, TLI.getPointerTy()); + SDOperand SwitchVal = DAG.getCopyFromReg(getControlRoot(), Reg, + TLI.getPointerTy()); - SDOperand AndOp = DAG.getNode(ISD::AND, TLI.getPointerTy(), - SwitchVal, - DAG.getConstant(B.Mask, - TLI.getPointerTy())); + SDOperand AndOp = DAG.getNode(ISD::AND, TLI.getPointerTy(), SwitchVal, + DAG.getConstant(B.Mask, TLI.getPointerTy())); SDOperand AndCmp = DAG.getSetCC(TLI.getSetCCResultType(AndOp), AndOp, DAG.getConstant(0, TLI.getPointerTy()), ISD::SETNE); @@ -1858,8 +1864,8 @@ bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR, for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) { MachineBasicBlock *FallThrough; if (I != E-1) { - FallThrough = new MachineBasicBlock(CurBlock->getBasicBlock()); - CurMF->getBasicBlockList().insert(BBI, FallThrough); + FallThrough = CurMF->CreateMachineBasicBlock(CurBlock->getBasicBlock()); + CurMF->insert(BBI, FallThrough); } else { // If the last case doesn't match, go to the default block. FallThrough = Default; @@ -1942,8 +1948,8 @@ bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR, // of the jump table, and jumping to it. Update successor information; // we will either branch to the default case for the switch, or the jump // table. - MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB); - CurMF->getBasicBlockList().insert(BBI, JumpTableBB); + MachineBasicBlock *JumpTableBB = CurMF->CreateMachineBasicBlock(LLVMBB); + CurMF->insert(BBI, JumpTableBB); CR.CaseBB->addSuccessor(Default); CR.CaseBB->addSuccessor(JumpTableBB); @@ -2080,8 +2086,8 @@ bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR, (cast(CR.GE)->getSExtValue() + 1LL)) { TrueBB = LHSR.first->BB; } else { - TrueBB = new MachineBasicBlock(LLVMBB); - CurMF->getBasicBlockList().insert(BBI, TrueBB); + TrueBB = CurMF->CreateMachineBasicBlock(LLVMBB); + CurMF->insert(BBI, TrueBB); WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR)); } @@ -2094,8 +2100,8 @@ bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR, (cast(CR.LT)->getSExtValue() - 1LL)) { FalseBB = RHSR.first->BB; } else { - FalseBB = new MachineBasicBlock(LLVMBB); - CurMF->getBasicBlockList().insert(BBI, FalseBB); + FalseBB = CurMF->CreateMachineBasicBlock(LLVMBB); + CurMF->insert(BBI, FalseBB); WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR)); } @@ -2217,8 +2223,8 @@ bool SelectionDAGLowering::handleBitTestsSwitchCase(CaseRec& CR, DOUT << "Mask: " << CasesBits[i].Mask << ", Bits: " << CasesBits[i].Bits << ", BB: " << CasesBits[i].BB << "\n"; - MachineBasicBlock *CaseBB = new MachineBasicBlock(LLVMBB); - CurMF->getBasicBlockList().insert(BBI, CaseBB); + MachineBasicBlock *CaseBB = CurMF->CreateMachineBasicBlock(LLVMBB); + CurMF->insert(BBI, CaseBB); BTC.push_back(SelectionDAGISel::BitTestCase(CasesBits[i].Mask, CaseBB, CasesBits[i].BB)); @@ -2708,9 +2714,8 @@ void SelectionDAGLowering::visitInsertValue(InsertValueInst &I) { Values[i] = IntoUndef ? DAG.getNode(ISD::UNDEF, AggValueVTs[i]) : SDOperand(Agg.Val, Agg.ResNo + i); - setValue(&I, DAG.getNode(ISD::MERGE_VALUES, - DAG.getVTList(&AggValueVTs[0], NumAggValues), - &Values[0], NumAggValues)); + setValue(&I, DAG.getMergeValues(DAG.getVTList(&AggValueVTs[0], NumAggValues), + &Values[0], NumAggValues)); } void SelectionDAGLowering::visitExtractValue(ExtractValueInst &I) { @@ -2732,12 +2737,11 @@ 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(i)) : - SDOperand(Agg.Val, Agg.ResNo + i - LinearIndex); + OutOfUndef ? DAG.getNode(ISD::UNDEF, Agg.Val->getValueType(Agg.ResNo + i)) : + SDOperand(Agg.Val, Agg.ResNo + i); - setValue(&I, DAG.getNode(ISD::MERGE_VALUES, - DAG.getVTList(&ValValueVTs[0], NumValValues), - &Values[0], NumValValues)); + setValue(&I, DAG.getMergeValues(DAG.getVTList(&ValValueVTs[0], NumValValues), + &Values[0], NumValValues)); } @@ -2892,9 +2896,8 @@ void SelectionDAGLowering::visitLoad(LoadInst &I) { else PendingLoads.push_back(Chain); - setValue(&I, DAG.getNode(ISD::MERGE_VALUES, - DAG.getVTList(&ValueVTs[0], NumValues), - &Values[0], NumValues)); + setValue(&I, DAG.getMergeValues(DAG.getVTList(&ValueVTs[0], NumValues), + &Values[0], NumValues)); } @@ -3072,10 +3075,10 @@ static void addCatchInfo(CallInst &I, MachineModuleInfo *MMI, const char * SelectionDAGLowering::implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op) { SDOperand Root = getRoot(); - SDOperand O2 = getValue(I.getOperand(2)); SDOperand L = DAG.getAtomic(Op, Root, getValue(I.getOperand(1)), - O2, O2.getValueType()); + getValue(I.getOperand(2)), + I.getOperand(1)); setValue(&I, L); DAG.setRoot(L.getValue(1)); return 0; @@ -3155,20 +3158,12 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); DbgStopPointInst &SPI = cast(I); if (MMI && SPI.getContext() && MMI->Verify(SPI.getContext())) { - SDOperand Ops[5]; - - Ops[0] = getRoot(); - Ops[1] = getValue(SPI.getLineValue()); - Ops[2] = getValue(SPI.getColumnValue()); - DebugInfoDesc *DD = MMI->getDescFor(SPI.getContext()); assert(DD && "Not a debug information descriptor"); - CompileUnitDesc *CompileUnit = cast(DD); - - Ops[3] = DAG.getString(CompileUnit->getFileName()); - Ops[4] = DAG.getString(CompileUnit->getDirectory()); - - DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops, 5)); + DAG.setRoot(DAG.getDbgStopPoint(getRoot(), + SPI.getLine(), + SPI.getColumn(), + cast(DD))); } return 0; @@ -3178,9 +3173,7 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { DbgRegionStartInst &RSI = cast(I); if (MMI && RSI.getContext() && MMI->Verify(RSI.getContext())) { unsigned LabelID = MMI->RecordRegionStart(RSI.getContext()); - DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(), - DAG.getConstant(LabelID, MVT::i32), - DAG.getConstant(0, MVT::i32))); + DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getRoot(), LabelID)); } return 0; @@ -3190,9 +3183,7 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { DbgRegionEndInst &REI = cast(I); if (MMI && REI.getContext() && MMI->Verify(REI.getContext())) { unsigned LabelID = MMI->RecordRegionEnd(REI.getContext()); - DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(), - DAG.getConstant(LabelID, MVT::i32), - DAG.getConstant(0, MVT::i32))); + DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getRoot(), LabelID)); } return 0; @@ -3209,8 +3200,7 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { assert(DD && "Not a debug information descriptor"); SubprogramDesc *Subprogram = cast(DD); const CompileUnitDesc *CompileUnit = Subprogram->getFile(); - unsigned SrcFile = MMI->RecordSource(CompileUnit->getDirectory(), - CompileUnit->getFileName()); + unsigned SrcFile = MMI->RecordSource(CompileUnit); // Record the source line but does create a label. It will be emitted // at asm emission time. MMI->RecordSourceLine(Subprogram->getLine(), 0, SrcFile); @@ -3505,21 +3495,21 @@ SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { DAG.setRoot(DAG.getNode(ISD::MEMBARRIER, MVT::Other, &Ops[0], 6)); return 0; } - case Intrinsic::atomic_lcs: { + case Intrinsic::atomic_cmp_swap: { SDOperand Root = getRoot(); - SDOperand O3 = getValue(I.getOperand(3)); - SDOperand L = DAG.getAtomic(ISD::ATOMIC_LCS, Root, + SDOperand L = DAG.getAtomic(ISD::ATOMIC_CMP_SWAP, Root, getValue(I.getOperand(1)), getValue(I.getOperand(2)), - O3, O3.getValueType()); + getValue(I.getOperand(3)), + I.getOperand(1)); setValue(&I, L); DAG.setRoot(L.getValue(1)); return 0; } - case Intrinsic::atomic_las: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LAS); - case Intrinsic::atomic_lss: - return implVisitBinaryAtomic(I, ISD::ATOMIC_LSS); + case Intrinsic::atomic_load_add: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_ADD); + case Intrinsic::atomic_load_sub: + return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_SUB); case Intrinsic::atomic_load_and: return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_AND); case Intrinsic::atomic_load_or: @@ -3576,9 +3566,7 @@ void SelectionDAGLowering::LowerCallTo(CallSite CS, SDOperand Callee, // Both PendingLoads and PendingExports must be flushed here; // this call might not return. (void)getRoot(); - DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getControlRoot(), - DAG.getConstant(BeginLabel, MVT::i32), - DAG.getConstant(1, MVT::i32))); + DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, getControlRoot(), BeginLabel)); } std::pair Result = @@ -3595,9 +3583,7 @@ void SelectionDAGLowering::LowerCallTo(CallSite CS, SDOperand Callee, // Insert a label at the end of the invoke call to mark the try range. This // can be used to detect deletion of the invoke via the MachineModuleInfo. EndLabel = MMI->NextLabelID(); - DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(), - DAG.getConstant(EndLabel, MVT::i32), - DAG.getConstant(1, MVT::i32))); + DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, getRoot(), EndLabel)); // Inform MachineModuleInfo of range. MMI->addInvoke(LandingPad, BeginLabel, EndLabel); @@ -3706,7 +3692,7 @@ void SelectionDAGLowering::visitGetResult(GetResultInst &I) { /// this value and returns the result as a ValueVT value. This uses /// Chain/Flag as the input and updates them for the output Chain/Flag. /// If the Flag pointer is NULL, no flag is used. -SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, +SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, SDOperand &Chain, SDOperand *Flag) const { // Assemble the legal parts into the final values. @@ -3728,6 +3714,49 @@ SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, *Flag = P.getValue(2); } Chain = P.getValue(1); + + // If the source register was virtual and if we know something about it, + // add an assert node. + if (TargetRegisterInfo::isVirtualRegister(Regs[Part+i]) && + RegisterVT.isInteger() && !RegisterVT.isVector()) { + unsigned SlotNo = Regs[Part+i]-TargetRegisterInfo::FirstVirtualRegister; + FunctionLoweringInfo &FLI = DAG.getFunctionLoweringInfo(); + if (FLI.LiveOutRegInfo.size() > SlotNo) { + FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[SlotNo]; + + unsigned RegSize = RegisterVT.getSizeInBits(); + unsigned NumSignBits = LOI.NumSignBits; + unsigned NumZeroBits = LOI.KnownZero.countLeadingOnes(); + + // FIXME: We capture more information than the dag can represent. For + // now, just use the tightest assertzext/assertsext possible. + bool isSExt = true; + MVT FromVT(MVT::Other); + if (NumSignBits == RegSize) + isSExt = true, FromVT = MVT::i1; // ASSERT SEXT 1 + else if (NumZeroBits >= RegSize-1) + isSExt = false, FromVT = MVT::i1; // ASSERT ZEXT 1 + else if (NumSignBits > RegSize-8) + isSExt = true, FromVT = MVT::i8; // ASSERT SEXT 8 + else if (NumZeroBits >= RegSize-9) + isSExt = false, FromVT = MVT::i8; // ASSERT ZEXT 8 + else if (NumSignBits > RegSize-16) + isSExt = true, FromVT = MVT::i16; // ASSERT SEXT 16 + else if (NumZeroBits >= RegSize-17) + isSExt = false, FromVT = MVT::i16; // ASSERT ZEXT 16 + else if (NumSignBits > RegSize-32) + isSExt = true, FromVT = MVT::i32; // ASSERT SEXT 32 + else if (NumZeroBits >= RegSize-33) + isSExt = false, FromVT = MVT::i32; // ASSERT ZEXT 32 + + if (FromVT != MVT::Other) { + P = DAG.getNode(isSExt ? ISD::AssertSext : ISD::AssertZext, + RegisterVT, P, DAG.getValueType(FromVT)); + + } + } + } + Parts[Part+i] = P; } @@ -3735,13 +3764,9 @@ SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, ValueVT); Part += NumRegs; } - - if (ValueVTs.size() == 1) - return Values[0]; - - return DAG.getNode(ISD::MERGE_VALUES, - DAG.getVTList(&ValueVTs[0], ValueVTs.size()), - &Values[0], ValueVTs.size()); + + return DAG.getMergeValues(DAG.getVTList(&ValueVTs[0], ValueVTs.size()), + &Values[0], ValueVTs.size()); } /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the @@ -4562,16 +4587,16 @@ void SelectionDAGLowering::visitVACopy(CallInst &I) { /// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be /// integrated into SDISel. -std::vector -TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) { +void TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG, + SmallVectorImpl &ArgValues) { // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node. - std::vector Ops; + SmallVector Ops; Ops.push_back(DAG.getRoot()); Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy())); Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy())); // Add one result value for each formal argument. - std::vector RetVals; + SmallVector RetVals; unsigned j = 1; for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I, ++j) { @@ -4649,7 +4674,6 @@ TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) { DAG.setRoot(SDOperand(Result, NumArgRegs)); // Set up the return result vector. - Ops.clear(); unsigned i = 0; unsigned Idx = 1; for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; @@ -4672,12 +4696,11 @@ TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) { else if (F.paramHasAttr(Idx, ParamAttr::ZExt)) AssertOp = ISD::AssertZext; - Ops.push_back(getCopyFromParts(DAG, &Parts[0], NumParts, PartVT, VT, - AssertOp)); + ArgValues.push_back(getCopyFromParts(DAG, &Parts[0], NumParts, PartVT, VT, + AssertOp)); } } assert(i == NumArgRegs && "Argument register count mismatch!"); - return Ops; } @@ -4810,10 +4833,8 @@ TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy, AssertOp); ReturnValues.push_back(ReturnValue); } - Res = ReturnValues.size() == 1 ? ReturnValues.front() : - DAG.getNode(ISD::MERGE_VALUES, - DAG.getVTList(&RetTys[0], RetTys.size()), - &ReturnValues[0], ReturnValues.size()); + Res = DAG.getMergeValues(DAG.getVTList(&RetTys[0], RetTys.size()), + &ReturnValues[0], ReturnValues.size()); } return std::make_pair(Res, Chain); @@ -4825,12 +4846,6 @@ SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) { return SDOperand(); } -SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op, - SelectionDAG &DAG) { - assert(0 && "CustomPromoteOperation not implemented for this target!"); - abort(); - return SDOperand(); -} //===----------------------------------------------------------------------===// // SelectionDAGISel code @@ -4865,8 +4880,7 @@ bool SelectionDAGISel::runOnFunction(Function &Fn) { // Mark landing pad. FuncInfo.MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); - for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) - SelectBasicBlock(I, MF, FuncInfo); + SelectAllBasicBlocks(Fn, MF, FuncInfo); // Add function live-ins to entry block live-in set. BasicBlock *EntryBB = &Fn.getEntryBlock(); @@ -4903,7 +4917,8 @@ LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL) { Function &F = *LLVMBB->getParent(); FunctionLoweringInfo &FuncInfo = SDL.FuncInfo; SDOperand OldRoot = SDL.DAG.getRoot(); - std::vector Args = TLI.LowerArguments(F, SDL.DAG); + SmallVector Args; + TLI.LowerArguments(F, SDL.DAG, Args); unsigned a = 0; for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); @@ -4912,13 +4927,7 @@ LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL) { ComputeValueVTs(TLI, AI->getType(), ValueVTs); unsigned NumValues = ValueVTs.size(); if (!AI->use_empty()) { - SmallVector LegalValueVTs(NumValues); - for (unsigned VI = 0; VI != NumValues; ++VI) - LegalValueVTs[VI] = Args[a + VI].getValueType(); - SDL.setValue(AI, SDL.DAG.getNode(ISD::MERGE_VALUES, - SDL.DAG.getVTList(&LegalValueVTs[0], - NumValues), - &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); @@ -4995,10 +5004,11 @@ static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG, // Fix tail call attribute of CALL nodes. for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(), - BI = prior(DAG.allnodes_end()); BI != BE; --BI) { + BI = DAG.allnodes_end(); BI != BE; ) { + --BI; if (BI->getOpcode() == ISD::CALL) { SDOperand OpRet(Ret, 0); - SDOperand OpCall(static_cast(BI), 0); + SDOperand OpCall(BI, 0); bool isMarkedTailCall = cast(OpCall.getOperand(3))->getValue() != 0; // If CALL node has tail call attribute set to true and the call is not @@ -5073,9 +5083,7 @@ void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, // 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.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(), - DAG.getConstant(LabelID, MVT::i32), - DAG.getConstant(1, MVT::i32))); + DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, DAG.getEntryNode(), LabelID)); // Mark exception register as live in. unsigned Reg = TLI.getExceptionAddressRegister(); @@ -5218,48 +5226,159 @@ void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, CheckDAGForTailCallsAndFixThem(DAG, TLI); } +void SelectionDAGISel::ComputeLiveOutVRegInfo(SelectionDAG &DAG) { + SmallPtrSet VisitedNodes; + SmallVector Worklist; + + Worklist.push_back(DAG.getRoot().Val); + + APInt Mask; + APInt KnownZero; + APInt KnownOne; + + while (!Worklist.empty()) { + SDNode *N = Worklist.back(); + Worklist.pop_back(); + + // If we've already seen this node, ignore it. + if (!VisitedNodes.insert(N)) + continue; + + // Otherwise, add all chain operands to the worklist. + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) + if (N->getOperand(i).getValueType() == MVT::Other) + Worklist.push_back(N->getOperand(i).Val); + + // If this is a CopyToReg with a vreg dest, process it. + if (N->getOpcode() != ISD::CopyToReg) + continue; + + unsigned DestReg = cast(N->getOperand(1))->getReg(); + if (!TargetRegisterInfo::isVirtualRegister(DestReg)) + continue; + + // Ignore non-scalar or non-integer values. + SDOperand Src = N->getOperand(2); + MVT SrcVT = Src.getValueType(); + if (!SrcVT.isInteger() || SrcVT.isVector()) + continue; + + unsigned NumSignBits = DAG.ComputeNumSignBits(Src); + Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits()); + DAG.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(); + if (DestReg >= FLI.LiveOutRegInfo.size()) + FLI.LiveOutRegInfo.resize(DestReg+1); + FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[DestReg]; + LOI.NumSignBits = NumSignBits; + LOI.KnownOne = NumSignBits; + LOI.KnownZero = NumSignBits; + } + } +} + void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { DOUT << "Lowered selection DAG:\n"; DEBUG(DAG.dump()); // Run the DAG combiner in pre-legalize mode. - DAG.Combine(false, *AA); + if (TimePassesIsEnabled) { + NamedRegionTimer T("DAG Combining 1"); + DAG.Combine(false, *AA); + } else { + DAG.Combine(false, *AA); + } DOUT << "Optimized lowered selection DAG:\n"; DEBUG(DAG.dump()); // Second step, hack on the DAG until it only uses operations and types that // the target supports. -#if 0 // Enable this some day. - DAG.LegalizeTypes(); - // Someday even later, enable a dag combine pass here. -#endif - DAG.Legalize(); + if (EnableLegalizeTypes) {// Enable this some day. + DAG.LegalizeTypes(); + // TODO: enable a dag combine pass here. + } + + if (TimePassesIsEnabled) { + NamedRegionTimer T("DAG Legalization"); + DAG.Legalize(); + } else { + DAG.Legalize(); + } DOUT << "Legalized selection DAG:\n"; DEBUG(DAG.dump()); // Run the DAG combiner in post-legalize mode. - DAG.Combine(true, *AA); + if (TimePassesIsEnabled) { + NamedRegionTimer T("DAG Combining 2"); + DAG.Combine(true, *AA); + } else { + DAG.Combine(true, *AA); + } DOUT << "Optimized legalized selection DAG:\n"; DEBUG(DAG.dump()); if (ViewISelDAGs) DAG.viewGraph(); + + if (!FastISel && EnableValueProp) + ComputeLiveOutVRegInfo(DAG); // Third, instruction select all of the operations to machine code, adding the // code to the MachineBasicBlock. - InstructionSelectBasicBlock(DAG); + if (TimePassesIsEnabled) { + NamedRegionTimer T("Instruction Selection"); + InstructionSelect(DAG); + } else { + InstructionSelect(DAG); + } + + // Emit machine code to BB. This can change 'BB' to the last block being + // inserted into. + if (TimePassesIsEnabled) { + NamedRegionTimer T("Instruction Scheduling"); + ScheduleAndEmitDAG(DAG); + } else { + ScheduleAndEmitDAG(DAG); + } + + // Perform target specific isel post processing. + if (TimePassesIsEnabled) { + NamedRegionTimer T("Instruction Selection Post Processing"); + InstructionSelectPostProcessing(DAG); + } else { + InstructionSelectPostProcessing(DAG); + } DOUT << "Selected machine code:\n"; DEBUG(BB->dump()); } +void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF, + FunctionLoweringInfo &FuncInfo) { + // Define AllNodes here so that memory allocation is reused for + // each basic block. + alist AllNodes; + + for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { + SelectBasicBlock(I, MF, FuncInfo, AllNodes); + AllNodes.clear(); + } +} + void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, - FunctionLoweringInfo &FuncInfo) { + FunctionLoweringInfo &FuncInfo, + alist &AllNodes) { std::vector > PHINodesToUpdate; { - SelectionDAG DAG(TLI, MF, getAnalysisToUpdate()); + SelectionDAG DAG(TLI, MF, FuncInfo, + getAnalysisToUpdate(), + AllNodes); CurDAG = &DAG; // First step, lower LLVM code to some DAG. This DAG may use operations and @@ -5293,7 +5412,9 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i) { // Lower header first, if it wasn't already lowered if (!BitTestCases[i].Emitted) { - SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate()); + SelectionDAG HSDAG(TLI, MF, FuncInfo, + getAnalysisToUpdate(), + AllNodes); CurDAG = &HSDAG; SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into @@ -5306,7 +5427,9 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, } for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) { - SelectionDAG BSDAG(TLI, MF, getAnalysisToUpdate()); + SelectionDAG BSDAG(TLI, MF, FuncInfo, + getAnalysisToUpdate(), + AllNodes); CurDAG = &BSDAG; SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into @@ -5363,7 +5486,9 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, for (unsigned i = 0, e = JTCases.size(); i != e; ++i) { // Lower header first, if it wasn't already lowered if (!JTCases[i].first.Emitted) { - SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate()); + SelectionDAG HSDAG(TLI, MF, FuncInfo, + getAnalysisToUpdate(), + AllNodes); CurDAG = &HSDAG; SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into @@ -5375,7 +5500,9 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, CodeGenAndEmitDAG(HSDAG); } - SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate()); + SelectionDAG JSDAG(TLI, MF, FuncInfo, + getAnalysisToUpdate(), + AllNodes); CurDAG = &JSDAG; SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI); // Set the current basic block to the mbb we wish to insert the code into @@ -5423,7 +5550,9 @@ void 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, getAnalysisToUpdate()); + SelectionDAG SDAG(TLI, MF, FuncInfo, + getAnalysisToUpdate(), + AllNodes); CurDAG = &SDAG; SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI); @@ -5481,7 +5610,7 @@ void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) { RegisterScheduler::setDefault(Ctor); } - ScheduleDAG *SL = Ctor(this, &DAG, BB); + ScheduleDAG *SL = Ctor(this, &DAG, BB, FastISel); BB = SL->Run(); if (ViewSUnitDAGs) SL->viewGraph();