diff options
Diffstat (limited to 'include/llvm/CodeGen')
49 files changed, 2636 insertions, 1556 deletions
diff --git a/include/llvm/CodeGen/Analysis.h b/include/llvm/CodeGen/Analysis.h index ce9ca0a0583a3..b2cc7047b30b7 100644 --- a/include/llvm/CodeGen/Analysis.h +++ b/include/llvm/CodeGen/Analysis.h @@ -26,6 +26,7 @@ namespace llvm { class GlobalVariable; class TargetLowering; +class TargetLoweringBase; class SDNode; class SDValue; class SelectionDAG; @@ -88,6 +89,14 @@ ISD::CondCode getICmpCondCode(ICmpInst::Predicate Pred); /// This function only tests target-independent requirements. bool isInTailCallPosition(ImmutableCallSite CS, const TargetLowering &TLI); +/// Test if given that the input instruction is in the tail call position if the +/// return type or any attributes of the function will inhibit tail call +/// optimization. +bool returnTypeIsEligibleForTailCall(const Function *F, + const Instruction *I, + const ReturnInst *Ret, + const TargetLoweringBase &TLI); + } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h index c2fd6ce3679cc..4bda0f1603acb 100644 --- a/include/llvm/CodeGen/AsmPrinter.h +++ b/include/llvm/CodeGen/AsmPrinter.h @@ -38,9 +38,10 @@ namespace llvm { class MachineConstantPoolValue; class MachineJumpTableInfo; class MachineModuleInfo; - class MachineMove; class MCAsmInfo; + class MCCFIInstruction; class MCContext; + class MCInstrInfo; class MCSection; class MCStreamer; class MCSymbol; @@ -64,6 +65,7 @@ namespace llvm { /// const MCAsmInfo *MAI; + const MCInstrInfo *MII; /// OutContext - This is the context for the output file that we are /// streaming. This owns all of the global MC-related objects for the /// generated translation unit. @@ -121,6 +123,8 @@ namespace llvm { public: virtual ~AsmPrinter(); + const DwarfDebug *getDwarfDebug() const { return DD; } + /// isVerbose - Return true if assembly output should contain comments. /// bool isVerbose() const { return VerboseAsm; } @@ -141,6 +145,7 @@ namespace llvm { /// getCurrentSection() - Return the current section we are emitting to. const MCSection *getCurrentSection() const; + MCSymbol *getSymbol(const GlobalValue *GV) const; //===------------------------------------------------------------------===// // MachineFunctionPass Implementation. @@ -233,8 +238,8 @@ namespace llvm { /// it if appropriate. void EmitBasicBlockStart(const MachineBasicBlock *MBB) const; - /// EmitGlobalConstant - Print a general LLVM constant to the .s file. - void EmitGlobalConstant(const Constant *CV, unsigned AddrSpace = 0); + /// \brief Print a general LLVM constant to the .s file. + void EmitGlobalConstant(const Constant *CV); //===------------------------------------------------------------------===// @@ -282,6 +287,10 @@ namespace llvm { virtual bool isBlockOnlyReachableByFallthrough(const MachineBasicBlock *MBB) const; + /// emitImplicitDef - Targets can override this to customize the output of + /// IMPLICIT_DEF instructions in verbose mode. + virtual void emitImplicitDef(const MachineInstr *MI) const; + //===------------------------------------------------------------------===// // Symbol Lowering Routines. //===------------------------------------------------------------------===// @@ -357,13 +366,15 @@ namespace llvm { /// where the size in bytes of the directive is specified by Size and Label /// specifies the label. This implicitly uses .set if it is available. void EmitLabelPlusOffset(const MCSymbol *Label, uint64_t Offset, - unsigned Size) const; + unsigned Size, + bool IsSectionRelative = false) const; /// EmitLabelReference - Emit something like ".long Label" /// where the size in bytes of the directive is specified by Size and Label /// specifies the label. - void EmitLabelReference(const MCSymbol *Label, unsigned Size) const { - EmitLabelPlusOffset(Label, 0, Size); + void EmitLabelReference(const MCSymbol *Label, unsigned Size, + bool IsSectionRelative = false) const { + EmitLabelPlusOffset(Label, 0, Size, IsSectionRelative); } //===------------------------------------------------------------------===// @@ -371,10 +382,10 @@ namespace llvm { //===------------------------------------------------------------------===// /// EmitSLEB128 - emit the specified signed leb128 value. - void EmitSLEB128(int Value, const char *Desc = 0) const; + void EmitSLEB128(int64_t Value, const char *Desc = 0) const; /// EmitULEB128 - emit the specified unsigned leb128 value. - void EmitULEB128(unsigned Value, const char *Desc = 0, + void EmitULEB128(uint64_t Value, const char *Desc = 0, unsigned PadTo = 0) const; /// EmitCFAByte - Emit a .byte 42 directive for a DW_CFA_xxx value. @@ -402,24 +413,20 @@ namespace llvm { void EmitSectionOffset(const MCSymbol *Label, const MCSymbol *SectionLabel) const; - /// getDebugValueLocation - Get location information encoded by DBG_VALUE - /// operands. - virtual MachineLocation getDebugValueLocation(const MachineInstr *MI) const; - /// getISAEncoding - Get the value for DW_AT_APPLE_isa. Zero if no isa /// encoding specified. virtual unsigned getISAEncoding() { return 0; } /// EmitDwarfRegOp - Emit dwarf register operation. - virtual void EmitDwarfRegOp(const MachineLocation &MLoc) const; + virtual void EmitDwarfRegOp(const MachineLocation &MLoc, + bool Indirect) const; //===------------------------------------------------------------------===// // Dwarf Lowering Routines //===------------------------------------------------------------------===// - /// EmitCFIFrameMove - Emit frame instruction to describe the layout of the - /// frame. - void EmitCFIFrameMove(const MachineMove &Move) const; + /// \brief Emit frame instruction to describe the layout of the frame. + void emitCFIInstruction(const MCCFIInstruction &Inst) const; //===------------------------------------------------------------------===// // Inline Asm Support @@ -451,8 +458,7 @@ namespace llvm { /// return true if the operand is erroneous. virtual bool PrintAsmMemoryOperand(const MachineInstr *MI, unsigned OpNo, unsigned AsmVariant, - const char *ExtraCode, - raw_ostream &OS); + const char *ExtraCode, raw_ostream &OS); private: /// Private state for PrintSpecial() @@ -464,7 +470,8 @@ namespace llvm { /// EmitInlineAsm - Emit a blob of inline asm to the output streamer. void EmitInlineAsm(StringRef Str, const MDNode *LocMDNode = 0, - InlineAsm::AsmDialect AsmDialect = InlineAsm::AD_ATT) const; + InlineAsm::AsmDialect AsmDialect = + InlineAsm::AD_ATT) const; /// EmitInlineAsm - This method formats and emits the specified machine /// instruction that is an inline asm. @@ -479,12 +486,13 @@ namespace llvm { void EmitVisibility(MCSymbol *Sym, unsigned Visibility, bool IsDefinition = true) const; - void EmitLinkage(unsigned Linkage, MCSymbol *GVSym) const; + void EmitLinkage(const GlobalValue *GV, MCSymbol *GVSym) const; void EmitJumpTableEntry(const MachineJumpTableInfo *MJTI, - const MachineBasicBlock *MBB, - unsigned uid) const; + const MachineBasicBlock *MBB, unsigned uid) const; void EmitLLVMUsedList(const ConstantArray *InitList); + /// Emit llvm.ident metadata in an '.ident' directive. + void EmitModuleIdents(Module &M); void EmitXXStructorList(const Constant *List, bool isCtor); GCMetadataPrinter *GetOrCreateGCPrinter(GCStrategy *C); }; diff --git a/include/llvm/CodeGen/CalcSpillWeights.h b/include/llvm/CodeGen/CalcSpillWeights.h index 9cd2decfacff0..0d79b1d41bdbc 100644 --- a/include/llvm/CodeGen/CalcSpillWeights.h +++ b/include/llvm/CodeGen/CalcSpillWeights.h @@ -18,9 +18,12 @@ namespace llvm { class LiveInterval; class LiveIntervals; + class MachineBlockFrequencyInfo; class MachineLoopInfo; - /// normalizeSpillWeight - The spill weight of a live interval is computed as: + /// \brief Normalize the spill weight of a live interval + /// + /// The spill weight of a live interval is computed as: /// /// (sum(use freq) + sum(def freq)) / (K + size) /// @@ -37,42 +40,38 @@ namespace llvm { return UseDefFreq / (Size + 25*SlotIndex::InstrDist); } - /// VirtRegAuxInfo - Calculate auxiliary information for a virtual - /// register such as its spill weight and allocation hint. + /// \brief Calculate auxiliary information for a virtual register such as its + /// spill weight and allocation hint. class VirtRegAuxInfo { + public: + typedef float (*NormalizingFn)(float, unsigned); + + private: MachineFunction &MF; LiveIntervals &LIS; const MachineLoopInfo &Loops; + const MachineBlockFrequencyInfo &MBFI; DenseMap<unsigned, float> Hint; + NormalizingFn normalize; + public: VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis, - const MachineLoopInfo &loops) : - MF(mf), LIS(lis), Loops(loops) {} + const MachineLoopInfo &loops, + const MachineBlockFrequencyInfo &mbfi, + NormalizingFn norm = normalizeSpillWeight) + : MF(mf), LIS(lis), Loops(loops), MBFI(mbfi), normalize(norm) {} - /// CalculateWeightAndHint - (re)compute li's spill weight and allocation - /// hint. - void CalculateWeightAndHint(LiveInterval &li); + /// \brief (re)compute li's spill weight and allocation hint. + void calculateSpillWeightAndHint(LiveInterval &li); }; - /// CalculateSpillWeights - Compute spill weights for all virtual register + /// \brief Compute spill weights and allocation hints for all virtual register /// live intervals. - class CalculateSpillWeights : public MachineFunctionPass { - public: - static char ID; - - CalculateSpillWeights() : MachineFunctionPass(ID) { - initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); - } - - virtual void getAnalysisUsage(AnalysisUsage &au) const; - - virtual bool runOnMachineFunction(MachineFunction &fn); - - private: - /// Returns true if the given live interval is zero length. - bool isZeroLengthInterval(LiveInterval *li) const; - }; - + void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, + const MachineLoopInfo &MLI, + const MachineBlockFrequencyInfo &MBFI, + VirtRegAuxInfo::NormalizingFn norm = + normalizeSpillWeight); } #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H diff --git a/include/llvm/CodeGen/CallingConvLower.h b/include/llvm/CodeGen/CallingConvLower.h index fa9d60f0d4174..a18f433bda405 100644 --- a/include/llvm/CodeGen/CallingConvLower.h +++ b/include/llvm/CodeGen/CallingConvLower.h @@ -158,7 +158,7 @@ private: MachineFunction &MF; const TargetMachine &TM; const TargetRegisterInfo &TRI; - SmallVector<CCValAssign, 16> &Locs; + SmallVectorImpl<CCValAssign> &Locs; LLVMContext &Context; unsigned StackOffset; @@ -219,7 +219,7 @@ protected: public: CCState(CallingConv::ID CC, bool isVarArg, MachineFunction &MF, - const TargetMachine &TM, SmallVector<CCValAssign, 16> &locs, + const TargetMachine &TM, SmallVectorImpl<CCValAssign> &locs, LLVMContext &C); void addLoc(const CCValAssign &V) { diff --git a/include/llvm/CodeGen/CommandFlags.h b/include/llvm/CodeGen/CommandFlags.h index 9a27661b51904..bc8dce33356e4 100644 --- a/include/llvm/CodeGen/CommandFlags.h +++ b/include/llvm/CodeGen/CommandFlags.h @@ -110,11 +110,6 @@ DisableFPElim("disable-fp-elim", cl::init(false)); cl::opt<bool> -DisableFPElimNonLeaf("disable-non-leaf-fp-elim", - cl::desc("Disable frame pointer elimination optimization for non-leaf funcs"), - cl::init(false)); - -cl::opt<bool> EnableUnsafeFPMath("enable-unsafe-fp-math", cl::desc("Enable optimizations that may decrease FP precision"), cl::init(false)); @@ -155,7 +150,7 @@ FloatABIForCalls("float-abi", cl::opt<llvm::FPOpFusion::FPOpFusionMode> FuseFPOps("fp-contract", - cl::desc("Enable aggresive formation of fused FP ops"), + cl::desc("Enable aggressive formation of fused FP ops"), cl::init(FPOpFusion::Standard), cl::values( clEnumValN(FPOpFusion::Fast, "fast", @@ -186,11 +181,6 @@ OverrideStackAlignment("stack-alignment", cl::desc("Override default stack alignment"), cl::init(0)); -cl::opt<bool> -EnableRealignStack("realign-stack", - cl::desc("Realign stack if needed"), - cl::init(true)); - cl::opt<std::string> TrapFuncName("trap-func", cl::Hidden, cl::desc("Emit a call to trap function rather than a trap instruction"), @@ -220,8 +210,4 @@ cl::opt<std::string> StartAfter("start-after", cl::value_desc("pass-name"), cl::init("")); -cl::opt<unsigned> -SSPBufferSize("stack-protector-buffer-size", cl::init(8), - cl::desc("Lower bound for a buffer to be considered for " - "stack protection")); #endif diff --git a/include/llvm/CodeGen/FastISel.h b/include/llvm/CodeGen/FastISel.h index 471e9bfc40bb3..1e0ef6b545eac 100644 --- a/include/llvm/CodeGen/FastISel.h +++ b/include/llvm/CodeGen/FastISel.h @@ -1,4 +1,4 @@ -//===-- FastISel.h - Definition of the FastISel class ---------------------===// +//===-- FastISel.h - Definition of the FastISel class ---*- C++ -*---------===// // // The LLVM Compiler Infrastructure // @@ -6,9 +6,10 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// This file defines the FastISel class. -// +/// +/// \file +/// This file defines the FastISel class. +/// //===----------------------------------------------------------------------===// #ifndef LLVM_CODEGEN_FASTISEL_H @@ -26,7 +27,6 @@ class ConstantFP; class FunctionLoweringInfo; class Instruction; class LoadInst; -class MachineBasicBlock; class MachineConstantPool; class MachineFunction; class MachineInstr; @@ -42,9 +42,8 @@ class TargetRegisterInfo; class User; class Value; -/// FastISel - This is a fast-path instruction selection class that -/// generates poor code and doesn't support illegal types or non-trivial -/// lowering, but runs quickly. +/// This is a fast-path instruction selection class that generates poor code and +/// doesn't support illegal types or non-trivial lowering, but runs quickly. class FastISel { protected: DenseMap<const Value *, unsigned> LocalValueMap; @@ -60,99 +59,92 @@ protected: const TargetRegisterInfo &TRI; const TargetLibraryInfo *LibInfo; - /// The position of the last instruction for materializing constants - /// for use in the current block. It resets to EmitStartPt when it - /// makes sense (for example, it's usually profitable to avoid function - /// calls between the definition and the use) + /// The position of the last instruction for materializing constants for use + /// in the current block. It resets to EmitStartPt when it makes sense (for + /// example, it's usually profitable to avoid function calls between the + /// definition and the use) MachineInstr *LastLocalValue; - /// The top most instruction in the current block that is allowed for - /// emitting local variables. LastLocalValue resets to EmitStartPt when - /// it makes sense (for example, on function calls) + /// The top most instruction in the current block that is allowed for emitting + /// local variables. LastLocalValue resets to EmitStartPt when it makes sense + /// (for example, on function calls) MachineInstr *EmitStartPt; public: - /// getLastLocalValue - Return the position of the last instruction - /// emitted for materializing constants for use in the current block. + /// Return the position of the last instruction emitted for materializing + /// constants for use in the current block. MachineInstr *getLastLocalValue() { return LastLocalValue; } - /// setLastLocalValue - Update the position of the last instruction - /// emitted for materializing constants for use in the current block. + /// Update the position of the last instruction emitted for materializing + /// constants for use in the current block. void setLastLocalValue(MachineInstr *I) { EmitStartPt = I; LastLocalValue = I; } - /// startNewBlock - Set the current block to which generated machine - /// instructions will be appended, and clear the local CSE map. - /// + /// Set the current block to which generated machine instructions will be + /// appended, and clear the local CSE map. void startNewBlock(); - /// getCurDebugLoc() - Return current debug location information. + /// Return current debug location information. DebugLoc getCurDebugLoc() const { return DL; } - /// LowerArguments - Do "fast" instruction selection for function arguments - /// and append machine instructions to the current block. Return true if - /// it is successful. + /// Do "fast" instruction selection for function arguments and append machine + /// instructions to the current block. Return true if it is successful. bool LowerArguments(); - /// SelectInstruction - Do "fast" instruction selection for the given - /// LLVM IR instruction, and append generated machine instructions to - /// the current block. Return true if selection was successful. - /// + /// Do "fast" instruction selection for the given LLVM IR instruction, and + /// append generated machine instructions to the current block. Return true if + /// selection was successful. bool SelectInstruction(const Instruction *I); - /// SelectOperator - Do "fast" instruction selection for the given - /// LLVM IR operator (Instruction or ConstantExpr), and append - /// generated machine instructions to the current block. Return true - /// if selection was successful. - /// + /// Do "fast" instruction selection for the given LLVM IR operator + /// (Instruction or ConstantExpr), and append generated machine instructions + /// to the current block. Return true if selection was successful. bool SelectOperator(const User *I, unsigned Opcode); - /// getRegForValue - Create a virtual register and arrange for it to - /// be assigned the value for the given LLVM value. + /// Create a virtual register and arrange for it to be assigned the value for + /// the given LLVM value. unsigned getRegForValue(const Value *V); - /// lookUpRegForValue - Look up the value to see if its value is already - /// cached in a register. It may be defined by instructions across blocks or - /// defined locally. + /// Look up the value to see if its value is already cached in a register. It + /// may be defined by instructions across blocks or defined locally. unsigned lookUpRegForValue(const Value *V); - /// getRegForGEPIndex - This is a wrapper around getRegForValue that also - /// takes care of truncating or sign-extending the given getelementptr - /// index value. + /// This is a wrapper around getRegForValue that also takes care of truncating + /// or sign-extending the given getelementptr index value. std::pair<unsigned, bool> getRegForGEPIndex(const Value *V); - /// \brief We're checking to see if we can fold \p LI into \p FoldInst. - /// Note that we could have a sequence where multiple LLVM IR instructions - /// are folded into the same machineinstr. For example we could have: + /// \brief We're checking to see if we can fold \p LI into \p FoldInst. Note + /// that we could have a sequence where multiple LLVM IR instructions are + /// folded into the same machineinstr. For example we could have: + /// /// A: x = load i32 *P /// B: y = icmp A, 42 /// C: br y, ... /// - /// In this scenario, \p LI is "A", and \p FoldInst is "C". We know - /// about "B" (and any other folded instructions) because it is between - /// A and C. + /// In this scenario, \p LI is "A", and \p FoldInst is "C". We know about "B" + /// (and any other folded instructions) because it is between A and C. /// /// If we succeed folding, return true. - /// bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst); - /// \brief The specified machine instr operand is a vreg, and that - /// vreg is being provided by the specified load instruction. If possible, - /// try to fold the load as an operand to the instruction, returning true if + /// \brief The specified machine instr operand is a vreg, and that vreg is + /// being provided by the specified load instruction. If possible, try to + /// fold the load as an operand to the instruction, returning true if /// possible. + /// /// This method should be implemented by targets. virtual bool tryToFoldLoadIntoMI(MachineInstr * /*MI*/, unsigned /*OpNo*/, const LoadInst * /*LI*/) { return false; } - /// recomputeInsertPt - Reset InsertPt to prepare for inserting instructions - /// into the current block. + /// Reset InsertPt to prepare for inserting instructions into the current + /// block. void recomputeInsertPt(); - /// removeDeadCode - Remove all dead instructions between the I and E. + /// Remove all dead instructions between the I and E. void removeDeadCode(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E); @@ -161,11 +153,11 @@ public: DebugLoc DL; }; - /// enterLocalValueArea - Prepare InsertPt to begin inserting instructions - /// into the local value area and return the old insert position. + /// Prepare InsertPt to begin inserting instructions into the local value area + /// and return the old insert position. SavePoint enterLocalValueArea(); - /// leaveLocalValueArea - Reset InsertPt to the given old insert position. + /// Reset InsertPt to the given old insert position. void leaveLocalValueArea(SavePoint Old); virtual ~FastISel(); @@ -174,69 +166,59 @@ protected: explicit FastISel(FunctionLoweringInfo &funcInfo, const TargetLibraryInfo *libInfo); - /// TargetSelectInstruction - This method is called by target-independent - /// code when the normal FastISel process fails to select an instruction. - /// This gives targets a chance to emit code for anything that doesn't - /// fit into FastISel's framework. It returns true if it was successful. - /// + /// This method is called by target-independent code when the normal FastISel + /// process fails to select an instruction. This gives targets a chance to + /// emit code for anything that doesn't fit into FastISel's framework. It + /// returns true if it was successful. virtual bool TargetSelectInstruction(const Instruction *I) = 0; - /// FastLowerArguments - This method is called by target-independent code to - /// do target specific argument lowering. It returns true if it was - /// successful. + /// This method is called by target-independent code to do target specific + /// argument lowering. It returns true if it was successful. virtual bool FastLowerArguments(); - /// FastEmit_r - This method is called by target-independent code - /// to request that an instruction with the given type and opcode - /// be emitted. + /// This method is called by target-independent code to request that an + /// instruction with the given type and opcode be emitted. virtual unsigned FastEmit_(MVT VT, MVT RetVT, unsigned Opcode); - /// FastEmit_r - This method is called by target-independent code - /// to request that an instruction with the given type, opcode, and - /// register operand be emitted. - /// + /// This method is called by target-independent code to request that an + /// instruction with the given type, opcode, and register operand be emitted. virtual unsigned FastEmit_r(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0, bool Op0IsKill); - /// FastEmit_rr - This method is called by target-independent code - /// to request that an instruction with the given type, opcode, and - /// register operands be emitted. - /// + /// This method is called by target-independent code to request that an + /// instruction with the given type, opcode, and register operands be emitted. virtual unsigned FastEmit_rr(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0, bool Op0IsKill, unsigned Op1, bool Op1IsKill); - /// FastEmit_ri - This method is called by target-independent code - /// to request that an instruction with the given type, opcode, and - /// register and immediate operands be emitted. - /// + /// This method is called by target-independent code to request that an + /// instruction with the given type, opcode, and register and immediate + /// operands be emitted. virtual unsigned FastEmit_ri(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0, bool Op0IsKill, uint64_t Imm); - /// FastEmit_rf - This method is called by target-independent code - /// to request that an instruction with the given type, opcode, and - /// register and floating-point immediate operands be emitted. - /// + /// This method is called by target-independent code to request that an + /// instruction with the given type, opcode, and register and floating-point + /// immediate operands be emitted. virtual unsigned FastEmit_rf(MVT VT, MVT RetVT, unsigned Opcode, unsigned Op0, bool Op0IsKill, const ConstantFP *FPImm); - /// FastEmit_rri - This method is called by target-independent code - /// to request that an instruction with the given type, opcode, and - /// register and immediate operands be emitted. - /// + /// This method is called by target-independent code to request that an + /// instruction with the given type, opcode, and register and immediate + /// operands be emitted. virtual unsigned FastEmit_rri(MVT VT, MVT RetVT, unsigned Opcode, @@ -244,142 +226,130 @@ protected: unsigned Op1, bool Op1IsKill, uint64_t Imm); - /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries - /// to emit an instruction with an immediate operand using FastEmit_ri. - /// If that fails, it materializes the immediate into a register and try - /// FastEmit_rr instead. + /// \brief This method is a wrapper of FastEmit_ri. + /// + /// It first tries to emit an instruction with an immediate operand using + /// FastEmit_ri. If that fails, it materializes the immediate into a register + /// and try FastEmit_rr instead. unsigned FastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0, bool Op0IsKill, uint64_t Imm, MVT ImmType); - /// FastEmit_i - This method is called by target-independent code - /// to request that an instruction with the given type, opcode, and - /// immediate operand be emitted. + /// This method is called by target-independent code to request that an + /// instruction with the given type, opcode, and immediate operand be emitted. virtual unsigned FastEmit_i(MVT VT, MVT RetVT, unsigned Opcode, uint64_t Imm); - /// FastEmit_f - This method is called by target-independent code - /// to request that an instruction with the given type, opcode, and - /// floating-point immediate operand be emitted. + /// This method is called by target-independent code to request that an + /// instruction with the given type, opcode, and floating-point immediate + /// operand be emitted. virtual unsigned FastEmit_f(MVT VT, MVT RetVT, unsigned Opcode, const ConstantFP *FPImm); - /// FastEmitInst_ - Emit a MachineInstr with no operands and a - /// result register in the given register class. - /// + /// Emit a MachineInstr with no operands and a result register in the given + /// register class. unsigned FastEmitInst_(unsigned MachineInstOpcode, const TargetRegisterClass *RC); - /// FastEmitInst_r - Emit a MachineInstr with one register operand - /// and a result register in the given register class. - /// + /// Emit a MachineInstr with one register operand and a result register in the + /// given register class. unsigned FastEmitInst_r(unsigned MachineInstOpcode, const TargetRegisterClass *RC, unsigned Op0, bool Op0IsKill); - /// FastEmitInst_rr - Emit a MachineInstr with two register operands - /// and a result register in the given register class. - /// + /// Emit a MachineInstr with two register operands and a result register in + /// the given register class. unsigned FastEmitInst_rr(unsigned MachineInstOpcode, const TargetRegisterClass *RC, unsigned Op0, bool Op0IsKill, unsigned Op1, bool Op1IsKill); - /// FastEmitInst_rrr - Emit a MachineInstr with three register operands - /// and a result register in the given register class. - /// + /// Emit a MachineInstr with three register operands and a result register in + /// the given register class. unsigned FastEmitInst_rrr(unsigned MachineInstOpcode, const TargetRegisterClass *RC, unsigned Op0, bool Op0IsKill, unsigned Op1, bool Op1IsKill, unsigned Op2, bool Op2IsKill); - /// FastEmitInst_ri - Emit a MachineInstr with a register operand, - /// an immediate, and a result register in the given register class. - /// + /// Emit a MachineInstr with a register operand, an immediate, and a result + /// register in the given register class. unsigned FastEmitInst_ri(unsigned MachineInstOpcode, const TargetRegisterClass *RC, unsigned Op0, bool Op0IsKill, uint64_t Imm); - /// FastEmitInst_rii - Emit a MachineInstr with one register operand - /// and two immediate operands. - /// + /// Emit a MachineInstr with one register operand and two immediate operands. unsigned FastEmitInst_rii(unsigned MachineInstOpcode, const TargetRegisterClass *RC, unsigned Op0, bool Op0IsKill, uint64_t Imm1, uint64_t Imm2); - /// FastEmitInst_rf - Emit a MachineInstr with two register operands - /// and a result register in the given register class. - /// + /// Emit a MachineInstr with two register operands and a result register in + /// the given register class. unsigned FastEmitInst_rf(unsigned MachineInstOpcode, const TargetRegisterClass *RC, unsigned Op0, bool Op0IsKill, const ConstantFP *FPImm); - /// FastEmitInst_rri - Emit a MachineInstr with two register operands, - /// an immediate, and a result register in the given register class. - /// + /// Emit a MachineInstr with two register operands, an immediate, and a result + /// register in the given register class. unsigned FastEmitInst_rri(unsigned MachineInstOpcode, const TargetRegisterClass *RC, unsigned Op0, bool Op0IsKill, unsigned Op1, bool Op1IsKill, uint64_t Imm); - /// FastEmitInst_rrii - Emit a MachineInstr with two register operands, - /// two immediates operands, and a result register in the given register - /// class. + /// Emit a MachineInstr with two register operands, two immediates operands, + /// and a result register in the given register class. unsigned FastEmitInst_rrii(unsigned MachineInstOpcode, const TargetRegisterClass *RC, unsigned Op0, bool Op0IsKill, unsigned Op1, bool Op1IsKill, uint64_t Imm1, uint64_t Imm2); - /// FastEmitInst_i - Emit a MachineInstr with a single immediate - /// operand, and a result register in the given register class. + /// Emit a MachineInstr with a single immediate operand, and a result register + /// in the given register class. unsigned FastEmitInst_i(unsigned MachineInstrOpcode, const TargetRegisterClass *RC, uint64_t Imm); - /// FastEmitInst_ii - Emit a MachineInstr with a two immediate operands. + /// Emit a MachineInstr with a two immediate operands. unsigned FastEmitInst_ii(unsigned MachineInstrOpcode, const TargetRegisterClass *RC, uint64_t Imm1, uint64_t Imm2); - /// FastEmitInst_extractsubreg - Emit a MachineInstr for an extract_subreg - /// from a specified index of a superregister to a specified type. + /// Emit a MachineInstr for an extract_subreg from a specified index of a + /// superregister to a specified type. unsigned FastEmitInst_extractsubreg(MVT RetVT, unsigned Op0, bool Op0IsKill, uint32_t Idx); - /// FastEmitZExtFromI1 - Emit MachineInstrs to compute the value of Op - /// with all but the least significant bit set to zero. + /// Emit MachineInstrs to compute the value of Op with all but the least + /// significant bit set to zero. unsigned FastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill); - /// FastEmitBranch - Emit an unconditional branch to the given block, - /// unless it is the immediate (fall-through) successor, and update - /// the CFG. + /// Emit an unconditional branch to the given block, unless it is the + /// immediate (fall-through) successor, and update the CFG. void FastEmitBranch(MachineBasicBlock *MBB, DebugLoc DL); void UpdateValueMap(const Value* I, unsigned Reg, unsigned NumRegs = 1); unsigned createResultReg(const TargetRegisterClass *RC); - /// TargetMaterializeConstant - Emit a constant in a register using - /// target-specific logic, such as constant pool loads. + /// Emit a constant in a register using target-specific logic, such as + /// constant pool loads. virtual unsigned TargetMaterializeConstant(const Constant* C) { return 0; } - /// TargetMaterializeAlloca - Emit an alloca address in a register using - /// target-specific logic. + /// Emit an alloca address in a register using target-specific logic. virtual unsigned TargetMaterializeAlloca(const AllocaInst* C) { return 0; } @@ -388,6 +358,15 @@ protected: return 0; } + /// \brief Check if \c Add is an add that can be safely folded into \c GEP. + /// + /// \c Add can be folded into \c GEP if: + /// - \c Add is an add, + /// - \c Add's size matches \c GEP's, + /// - \c Add is in the same basic block as \c GEP, and + /// - \c Add has a constant operand. + bool canFoldAddIntoGEP(const User *GEP, const Value *Add); + private: bool SelectBinaryOp(const User *I, unsigned ISDOpcode); @@ -405,25 +384,26 @@ private: bool SelectInsertValue(const User *I); - /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks. + /// \brief Handle PHI nodes in successor blocks. + /// /// Emit code to ensure constants are copied into registers 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. + /// 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. bool HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB); - /// materializeRegForValue - Helper for getRegForVale. This function is - /// called when the value isn't already available in a register and must - /// be materialized with new instructions. + /// Helper for getRegForVale. This function is called when the value isn't + /// already available in a register and must be materialized with new + /// instructions. unsigned materializeRegForValue(const Value *V, MVT VT); - /// flushLocalValueMap - clears LocalValueMap and moves the area for the - /// new local variables to the beginning of the block. It helps to avoid - /// spilling cached variables across heavy instructions like calls. + /// Clears LocalValueMap and moves the area for the new local variables to the + /// beginning of the block. It helps to avoid spilling cached variables across + /// heavy instructions like calls. void flushLocalValueMap(); - /// hasTrivialKill - Test whether the given value has exactly one use. + /// Test whether the given value has exactly one use. bool hasTrivialKill(const Value *V) const; }; diff --git a/include/llvm/CodeGen/FunctionLoweringInfo.h b/include/llvm/CodeGen/FunctionLoweringInfo.h index ea6cb27b7b136..50d320f8e839d 100644 --- a/include/llvm/CodeGen/FunctionLoweringInfo.h +++ b/include/llvm/CodeGen/FunctionLoweringInfo.h @@ -49,8 +49,8 @@ class Value; /// function that is used when lowering a region of the function. /// class FunctionLoweringInfo { + const TargetMachine &TM; public: - const TargetLowering &TLI; const Function *Fn; MachineFunction *MF; MachineRegisterInfo *RegInfo; @@ -115,7 +115,12 @@ public: /// there's no other convenient place for it to live right now. std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; - explicit FunctionLoweringInfo(const TargetLowering &TLI); + /// If the current MBB is a landing pad, the exception pointer and exception + /// selector registers are copied into these virtual registers by + /// SelectionDAGISel::PrepareEHLandingPad(). + unsigned ExceptionPointerVirtReg, ExceptionSelectorVirtReg; + + explicit FunctionLoweringInfo(const TargetMachine &TM) : TM(TM) {} /// set - Initialize this FunctionLoweringInfo with the given Function /// and its associated MachineFunction. diff --git a/include/llvm/CodeGen/ISDOpcodes.h b/include/llvm/CodeGen/ISDOpcodes.h index 0fd211b4a8656..48a0523dc6189 100644 --- a/include/llvm/CodeGen/ISDOpcodes.h +++ b/include/llvm/CodeGen/ISDOpcodes.h @@ -77,18 +77,6 @@ namespace ISD { /// adjustment during unwind. FRAME_TO_ARGS_OFFSET, - /// RESULT, OUTCHAIN = EXCEPTIONADDR(INCHAIN) - This node represents the - /// address of the exception block on entry to an landing pad block. - EXCEPTIONADDR, - - /// RESULT, OUTCHAIN = LSDAADDR(INCHAIN) - This node represents the - /// address of the Language Specific Data Area for the enclosing function. - LSDAADDR, - - /// RESULT, OUTCHAIN = EHSELECTION(INCHAIN, EXCEPTION) - This node - /// represents the selection index of the exception thrown. - EHSELECTION, - /// OUTCHAIN = EH_RETURN(INCHAIN, OFFSET, HANDLER) - This node represents /// 'eh_return' gcc dwarf builtin, which is used to return from /// exception. The general meaning is: adjust stack by OFFSET and pass @@ -431,6 +419,10 @@ namespace ISD { /// getNode(). BITCAST, + /// ADDRSPACECAST - This operator converts between pointers of different + /// address spaces. + ADDRSPACECAST, + /// CONVERT_RNDSAT - This operator is used to support various conversions /// between various types (float, signed, unsigned and vectors of those /// types) with rounding and saturation. NOTE: Avoid using this operator as @@ -452,11 +444,11 @@ namespace ISD { /// FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW, /// FLOG, FLOG2, FLOG10, FEXP, FEXP2, - /// FCEIL, FTRUNC, FRINT, FNEARBYINT, FFLOOR - Perform various unary + /// FCEIL, FTRUNC, FRINT, FNEARBYINT, FROUND, FFLOOR - Perform various unary /// floating point operations. These are inspired by libm. FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW, FLOG, FLOG2, FLOG10, FEXP, FEXP2, - FCEIL, FTRUNC, FRINT, FNEARBYINT, FFLOOR, + FCEIL, FTRUNC, FRINT, FNEARBYINT, FROUND, FFLOOR, /// FSINCOS - Compute both fsin and fcos as a single operation. FSINCOS, @@ -616,11 +608,17 @@ namespace ISD { ATOMIC_STORE, /// Val, OUTCHAIN = ATOMIC_CMP_SWAP(INCHAIN, ptr, cmp, swap) + /// For double-word atomic operations: + /// ValLo, ValHi, OUTCHAIN = ATOMIC_CMP_SWAP(INCHAIN, ptr, cmpLo, cmpHi, + /// swapLo, swapHi) /// This corresponds to the cmpxchg instruction. ATOMIC_CMP_SWAP, /// Val, OUTCHAIN = ATOMIC_SWAP(INCHAIN, ptr, amt) /// Val, OUTCHAIN = ATOMIC_LOAD_[OpName](INCHAIN, ptr, amt) + /// For double-word atomic operations: + /// ValLo, ValHi, OUTCHAIN = ATOMIC_SWAP(INCHAIN, ptr, amtLo, amtHi) + /// ValLo, ValHi, OUTCHAIN = ATOMIC_LOAD_[OpName](INCHAIN, ptr, amtLo, amtHi) /// These correspond to the atomicrmw instruction. ATOMIC_SWAP, ATOMIC_LOAD_ADD, @@ -647,7 +645,7 @@ namespace ISD { /// which do not reference a specific memory location should be less than /// this value. Those that do must not be less than this value, and can /// be used with SelectionDAG::getMemIntrinsicNode. - static const int FIRST_TARGET_MEMORY_OPCODE = BUILTIN_OP_END+150; + static const int FIRST_TARGET_MEMORY_OPCODE = BUILTIN_OP_END+180; //===--------------------------------------------------------------------===// /// MemIndexedMode enum - This enum defines the load / store indexed diff --git a/include/llvm/CodeGen/LexicalScopes.h b/include/llvm/CodeGen/LexicalScopes.h index ff65db4ee4ce9..26563a605574d 100644 --- a/include/llvm/CodeGen/LexicalScopes.h +++ b/include/llvm/CodeGen/LexicalScopes.h @@ -141,8 +141,8 @@ private: DenseMap<const MDNode *, LexicalScope *> AbstractScopeMap; /// AbstractScopesList - Tracks abstract scopes constructed while processing - /// a function. - SmallVector<LexicalScope *, 4>AbstractScopesList; + /// a function. + SmallVector<LexicalScope *, 4> AbstractScopesList; /// CurrentFnLexicalScope - Top level scope for the current function. /// @@ -166,13 +166,13 @@ public: virtual ~LexicalScope() {} // Accessors. - LexicalScope *getParent() const { return Parent; } - const MDNode *getDesc() const { return Desc; } - const MDNode *getInlinedAt() const { return InlinedAtLocation; } - const MDNode *getScopeNode() const { return Desc; } - bool isAbstractScope() const { return AbstractScope; } - SmallVector<LexicalScope *, 4> &getChildren() { return Children; } - SmallVector<InsnRange, 4> &getRanges() { return Ranges; } + LexicalScope *getParent() const { return Parent; } + const MDNode *getDesc() const { return Desc; } + const MDNode *getInlinedAt() const { return InlinedAtLocation; } + const MDNode *getScopeNode() const { return Desc; } + bool isAbstractScope() const { return AbstractScope; } + SmallVectorImpl<LexicalScope *> &getChildren() { return Children; } + SmallVectorImpl<InsnRange> &getRanges() { return Ranges; } /// addChild - Add a child scope. void addChild(LexicalScope *S) { Children.push_back(S); } diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index cb09a49666387..3a9fef6fbd781 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -9,12 +9,12 @@ // // This file implements the LiveRange and LiveInterval classes. Given some // numbering of each the machine instructions an interval [i, j) is said to be a -// live interval for register v if there is no instruction with number j' >= j +// live range for register v if there is no instruction with number j' >= j // such that v is live at j' and there is no instruction with number i' < i such -// that v is live at i'. In this implementation intervals can have holes, -// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each -// individual range is represented as an instance of LiveRange, and the whole -// interval is represented as an instance of LiveInterval. +// that v is live at i'. In this implementation ranges can have holes, +// i.e. a range might look like [1,20), [50,65), [1000,1001). Each +// individual segment is represented as an instance of LiveRange::Segment, +// and the whole range is represented as an instance of LiveRange. // //===----------------------------------------------------------------------===// @@ -35,6 +35,7 @@ namespace llvm { class MachineRegisterInfo; class TargetRegisterInfo; class raw_ostream; + template <typename T, unsigned Small> class SmallPtrSet; /// VNInfo - Value Number Information. /// This class holds information about a machine level values, including @@ -66,7 +67,7 @@ namespace llvm { } /// Returns true if this value is defined by a PHI instruction (or was, - /// PHI instrucions may have been eliminated). + /// PHI instructions may have been eliminated). /// PHI-defs begin at a block boundary, all other defs begin at register or /// EC slots. bool isPHIDef() const { return def.isBlock(); } @@ -78,107 +79,136 @@ namespace llvm { void markUnused() { def = SlotIndex(); } }; - /// LiveRange structure - This represents a simple register range in the - /// program, with an inclusive start point and an exclusive end point. - /// These ranges are rendered as [start,end). - struct LiveRange { - SlotIndex start; // Start point of the interval (inclusive) - SlotIndex end; // End point of the interval (exclusive) - VNInfo *valno; // identifier for the value contained in this interval. + /// Result of a LiveRange query. This class hides the implementation details + /// of live ranges, and it should be used as the primary interface for + /// examining live ranges around instructions. + class LiveQueryResult { + VNInfo *const EarlyVal; + VNInfo *const LateVal; + const SlotIndex EndPoint; + const bool Kill; - LiveRange() : valno(0) {} + public: + LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, + bool Kill) + : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill) + {} - LiveRange(SlotIndex S, SlotIndex E, VNInfo *V) - : start(S), end(E), valno(V) { - assert(S < E && "Cannot create empty or backwards range"); + /// Return the value that is live-in to the instruction. This is the value + /// that will be read by the instruction's use operands. Return NULL if no + /// value is live-in. + VNInfo *valueIn() const { + return EarlyVal; } - /// contains - Return true if the index is covered by this range. - /// - bool contains(SlotIndex I) const { - return start <= I && I < end; + /// Return true if the live-in value is killed by this instruction. This + /// means that either the live range ends at the instruction, or it changes + /// value. + bool isKill() const { + return Kill; } - /// containsRange - Return true if the given range, [S, E), is covered by - /// this range. - bool containsRange(SlotIndex S, SlotIndex E) const { - assert((S < E) && "Backwards interval?"); - return (start <= S && S < end) && (start < E && E <= end); + /// Return true if this instruction has a dead def. + bool isDeadDef() const { + return EndPoint.isDead(); } - bool operator<(const LiveRange &LR) const { - return start < LR.start || (start == LR.start && end < LR.end); + /// Return the value leaving the instruction, if any. This can be a + /// live-through value, or a live def. A dead def returns NULL. + VNInfo *valueOut() const { + return isDeadDef() ? 0 : LateVal; } - bool operator==(const LiveRange &LR) const { - return start == LR.start && end == LR.end; + + /// Return the value defined by this instruction, if any. This includes + /// dead defs, it is the value created by the instruction's def operands. + VNInfo *valueDefined() const { + return EarlyVal == LateVal ? 0 : LateVal; } - void dump() const; - void print(raw_ostream &os) const; + /// Return the end point of the last live range segment to interact with + /// the instruction, if any. + /// + /// The end point is an invalid SlotIndex only if the live range doesn't + /// intersect the instruction at all. + /// + /// The end point may be at or past the end of the instruction's basic + /// block. That means the value was live out of the block. + SlotIndex endPoint() const { + return EndPoint; + } }; - template <> struct isPodLike<LiveRange> { static const bool value = true; }; - - raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); - + /// This class represents the liveness of a register, stack slot, etc. + /// It manages an ordered list of Segment objects. + /// The Segments are organized in a static single assignment form: At places + /// where a new value is defined or different values reach a CFG join a new + /// segment with a new value number is used. + class LiveRange { + public: - inline bool operator<(SlotIndex V, const LiveRange &LR) { - return V < LR.start; - } + /// This represents a simple continuous liveness interval for a value. + /// The start point is inclusive, the end point exclusive. These intervals + /// are rendered as [start,end). + struct Segment { + SlotIndex start; // Start point of the interval (inclusive) + SlotIndex end; // End point of the interval (exclusive) + VNInfo *valno; // identifier for the value contained in this segment. - inline bool operator<(const LiveRange &LR, SlotIndex V) { - return LR.start < V; - } + Segment() : valno(0) {} - /// LiveInterval - This class represents some number of live ranges for a - /// register or value. This class also contains a bit of register allocator - /// state. - class LiveInterval { - public: + Segment(SlotIndex S, SlotIndex E, VNInfo *V) + : start(S), end(E), valno(V) { + assert(S < E && "Cannot create empty or backwards segment"); + } - typedef SmallVector<LiveRange,4> Ranges; - typedef SmallVector<VNInfo*,4> VNInfoList; + /// Return true if the index is covered by this segment. + bool contains(SlotIndex I) const { + return start <= I && I < end; + } - const unsigned reg; // the register or stack slot of this interval. - float weight; // weight of this interval - Ranges ranges; // the ranges in which this register is live - VNInfoList valnos; // value#'s + /// Return true if the given interval, [S, E), is covered by this segment. + bool containsInterval(SlotIndex S, SlotIndex E) const { + assert((S < E) && "Backwards interval?"); + return (start <= S && S < end) && (start < E && E <= end); + } - struct InstrSlots { - enum { - LOAD = 0, - USE = 1, - DEF = 2, - STORE = 3, - NUM = 4 - }; + bool operator<(const Segment &Other) const { + return start < Other.start || (start == Other.start && end < Other.end); + } + bool operator==(const Segment &Other) const { + return start == Other.start && end == Other.end; + } + void dump() const; }; - LiveInterval(unsigned Reg, float Weight) - : reg(Reg), weight(Weight) {} + typedef SmallVector<Segment,4> Segments; + typedef SmallVector<VNInfo*,4> VNInfoList; + + Segments segments; // the liveness segments + VNInfoList valnos; // value#'s - typedef Ranges::iterator iterator; - iterator begin() { return ranges.begin(); } - iterator end() { return ranges.end(); } + typedef Segments::iterator iterator; + iterator begin() { return segments.begin(); } + iterator end() { return segments.end(); } - typedef Ranges::const_iterator const_iterator; - const_iterator begin() const { return ranges.begin(); } - const_iterator end() const { return ranges.end(); } + typedef Segments::const_iterator const_iterator; + const_iterator begin() const { return segments.begin(); } + const_iterator end() const { return segments.end(); } typedef VNInfoList::iterator vni_iterator; vni_iterator vni_begin() { return valnos.begin(); } - vni_iterator vni_end() { return valnos.end(); } + vni_iterator vni_end() { return valnos.end(); } typedef VNInfoList::const_iterator const_vni_iterator; const_vni_iterator vni_begin() const { return valnos.begin(); } - const_vni_iterator vni_end() const { return valnos.end(); } + const_vni_iterator vni_end() const { return valnos.end(); } - /// advanceTo - Advance the specified iterator to point to the LiveRange + /// advanceTo - Advance the specified iterator to point to the Segment /// containing the specified position, or end() if the position is past the - /// end of the interval. If no LiveRange contains this position, but the + /// end of the range. If no Segment contains this position, but the /// position is in a hole, this method returns an iterator pointing to the - /// LiveRange immediately after the hole. + /// Segment immediately after the hole. iterator advanceTo(iterator I, SlotIndex Pos) { assert(I != end()); if (Pos >= endIndex()) @@ -187,22 +217,26 @@ namespace llvm { return I; } - /// find - Return an iterator pointing to the first range that ends after + /// find - Return an iterator pointing to the first segment that ends after /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster - /// when searching large intervals. + /// when searching large ranges. /// - /// If Pos is contained in a LiveRange, that range is returned. - /// If Pos is in a hole, the following LiveRange is returned. + /// If Pos is contained in a Segment, that segment is returned. + /// If Pos is in a hole, the following Segment is returned. /// If Pos is beyond endIndex, end() is returned. iterator find(SlotIndex Pos); const_iterator find(SlotIndex Pos) const { - return const_cast<LiveInterval*>(this)->find(Pos); + return const_cast<LiveRange*>(this)->find(Pos); } void clear() { valnos.clear(); - ranges.clear(); + segments.clear(); + } + + size_t size() const { + return segments.size(); } bool hasAtLeastOneValue() const { return !valnos.empty(); } @@ -220,7 +254,7 @@ namespace llvm { return valnos[ValNo]; } - /// containsValue - Returns true if VNI belongs to this interval. + /// containsValue - Returns true if VNI belongs to this range. bool containsValue(const VNInfo *VNI) const { return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); } @@ -234,7 +268,7 @@ namespace llvm { return VNI; } - /// createDeadDef - Make sure the interval has a value defined at Def. + /// createDeadDef - Make sure the range has a value defined at Def. /// If one already exists, return it. Otherwise allocate a new value and /// add liveness for a dead def. VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); @@ -251,42 +285,42 @@ namespace llvm { /// RenumberValues - Renumber all values in order of appearance and remove /// unused values. - void RenumberValues(LiveIntervals &lis); + void RenumberValues(); - /// MergeValueNumberInto - This method is called when two value nubmers + /// MergeValueNumberInto - This method is called when two value numbers /// are found to be equivalent. This eliminates V1, replacing all - /// LiveRanges with the V1 value number with the V2 value number. This can + /// segments with the V1 value number with the V2 value number. This can /// cause merging of V1/V2 values numbers and compaction of the value space. VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); - /// MergeValueInAsValue - Merge all of the live ranges of a specific val# - /// in RHS into this live interval as the specified value number. - /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the - /// current interval, it will replace the value numbers of the overlaped - /// live ranges with the specified value number. - void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo); - - /// MergeValueInAsValue - Merge all of the live ranges of a specific val# - /// in RHS into this live interval as the specified value number. - /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the - /// current interval, but only if the overlapping LiveRanges have the + /// Merge all of the live segments of a specific val# in RHS into this live + /// range as the specified value number. The segments in RHS are allowed + /// to overlap with segments in the current range, it will replace the + /// value numbers of the overlaped live segments with the specified value + /// number. + void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo); + + /// MergeValueInAsValue - Merge all of the segments of a specific val# + /// in RHS into this live range as the specified value number. + /// The segments in RHS are allowed to overlap with segments in the + /// current range, but only if the overlapping segments have the /// specified value number. - void MergeValueInAsValue(const LiveInterval &RHS, + void MergeValueInAsValue(const LiveRange &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo); - bool empty() const { return ranges.empty(); } + bool empty() const { return segments.empty(); } - /// beginIndex - Return the lowest numbered slot covered by interval. + /// beginIndex - Return the lowest numbered slot covered. SlotIndex beginIndex() const { - assert(!empty() && "Call to beginIndex() on empty interval."); - return ranges.front().start; + assert(!empty() && "Call to beginIndex() on empty range."); + return segments.front().start; } - /// endNumber - return the maximum point of the interval of the whole, + /// endNumber - return the maximum point of the range of the whole, /// exclusive. SlotIndex endIndex() const { - assert(!empty() && "Call to endIndex() on empty interval."); - return ranges.back().end; + assert(!empty() && "Call to endIndex() on empty range."); + return segments.back().end; } bool expiredAt(SlotIndex index) const { @@ -298,31 +332,23 @@ namespace llvm { return r != end() && r->start <= index; } - /// killedAt - Return true if a live range ends at index. Note that the kill - /// point is not contained in the half-open live range. It is usually the - /// getDefIndex() slot following its last use. - bool killedAt(SlotIndex index) const { - const_iterator r = find(index.getRegSlot(true)); - return r != end() && r->end == index; - } - - /// getLiveRangeContaining - Return the live range that contains the - /// specified index, or null if there is none. - const LiveRange *getLiveRangeContaining(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx); + /// Return the segment that contains the specified index, or null if there + /// is none. + const Segment *getSegmentContaining(SlotIndex Idx) const { + const_iterator I = FindSegmentContaining(Idx); return I == end() ? 0 : &*I; } - /// getLiveRangeContaining - Return the live range that contains the - /// specified index, or null if there is none. - LiveRange *getLiveRangeContaining(SlotIndex Idx) { - iterator I = FindLiveRangeContaining(Idx); + /// Return the live segment that contains the specified index, or null if + /// there is none. + Segment *getSegmentContaining(SlotIndex Idx) { + iterator I = FindSegmentContaining(Idx); return I == end() ? 0 : &*I; } /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. VNInfo *getVNInfoAt(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx); + const_iterator I = FindSegmentContaining(Idx); return I == end() ? 0 : I->valno; } @@ -330,76 +356,68 @@ namespace llvm { /// necessarilly including Idx, or NULL. Use this to find the reaching def /// used by an instruction at this SlotIndex position. VNInfo *getVNInfoBefore(SlotIndex Idx) const { - const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot()); + const_iterator I = FindSegmentContaining(Idx.getPrevSlot()); return I == end() ? 0 : I->valno; } - /// FindLiveRangeContaining - Return an iterator to the live range that - /// contains the specified index, or end() if there is none. - iterator FindLiveRangeContaining(SlotIndex Idx) { + /// Return an iterator to the segment that contains the specified index, or + /// end() if there is none. + iterator FindSegmentContaining(SlotIndex Idx) { iterator I = find(Idx); return I != end() && I->start <= Idx ? I : end(); } - const_iterator FindLiveRangeContaining(SlotIndex Idx) const { + const_iterator FindSegmentContaining(SlotIndex Idx) const { const_iterator I = find(Idx); return I != end() && I->start <= Idx ? I : end(); } - /// overlaps - Return true if the intersection of the two live intervals is + /// overlaps - Return true if the intersection of the two live ranges is /// not empty. - bool overlaps(const LiveInterval& other) const { + bool overlaps(const LiveRange &other) const { if (other.empty()) return false; return overlapsFrom(other, other.begin()); } - /// overlaps - Return true if the two intervals have overlapping segments + /// overlaps - Return true if the two ranges have overlapping segments /// that are not coalescable according to CP. /// - /// Overlapping segments where one interval is defined by a coalescable + /// Overlapping segments where one range is defined by a coalescable /// copy are allowed. - bool overlaps(const LiveInterval &Other, const CoalescerPair &CP, + bool overlaps(const LiveRange &Other, const CoalescerPair &CP, const SlotIndexes&) const; - /// overlaps - Return true if the live interval overlaps a range specified + /// overlaps - Return true if the live range overlaps an interval specified /// by [Start, End). bool overlaps(SlotIndex Start, SlotIndex End) const; - /// overlapsFrom - Return true if the intersection of the two live intervals + /// overlapsFrom - Return true if the intersection of the two live ranges /// is not empty. The specified iterator is a hint that we can begin - /// scanning the Other interval starting at I. - bool overlapsFrom(const LiveInterval& other, const_iterator I) const; + /// scanning the Other range starting at I. + bool overlapsFrom(const LiveRange &Other, const_iterator I) const; - /// addRange - Add the specified LiveRange to this interval, merging - /// intervals as appropriate. This returns an iterator to the inserted live - /// range (which may have grown since it was inserted. - iterator addRange(LiveRange LR) { - return addRangeFrom(LR, ranges.begin()); + /// Add the specified Segment to this range, merging segments as + /// appropriate. This returns an iterator to the inserted segment (which + /// may have grown since it was inserted). + iterator addSegment(Segment S) { + return addSegmentFrom(S, segments.begin()); } - /// extendInBlock - If this interval is live before Kill in the basic block + /// extendInBlock - If this range is live before Kill in the basic block /// that starts at StartIdx, extend it to be live up to Kill, and return - /// the value. If there is no live range before Kill, return NULL. + /// the value. If there is no segment before Kill, return NULL. VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); - /// join - Join two live intervals (this, and other) together. This applies - /// mappings to the value numbers in the LHS/RHS intervals as specified. If - /// the intervals are not joinable, this aborts. - void join(LiveInterval &Other, + /// join - Join two live ranges (this, and other) together. This applies + /// mappings to the value numbers in the LHS/RHS ranges as specified. If + /// the ranges are not joinable, this aborts. + void join(LiveRange &Other, const int *ValNoAssignments, const int *RHSValNoAssignments, - SmallVector<VNInfo*, 16> &NewVNInfo, - MachineRegisterInfo *MRI); + SmallVectorImpl<VNInfo *> &NewVNInfo); - /// isInOneLiveRange - Return true if the range specified is entirely in the - /// a single LiveRange of the live interval. - bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const { - const_iterator r = find(Start); - return r != end() && r->containsRange(Start, End); - } - - /// True iff this live range is a single segment that lies between the + /// True iff this segment is a single segment that lies between the /// specified boundaries, exclusively. Vregs live across a backedge are not /// considered local. The boundaries are expected to lie within an extended /// basic block, so vregs that are not live out should contain no holes. @@ -408,25 +426,63 @@ namespace llvm { endIndex() < End.getBoundaryIndex(); } - /// removeRange - Remove the specified range from this interval. Note that - /// the range must be a single LiveRange in its entirety. - void removeRange(SlotIndex Start, SlotIndex End, - bool RemoveDeadValNo = false); + /// Remove the specified segment from this range. Note that the segment + /// must be a single Segment in its entirety. + void removeSegment(SlotIndex Start, SlotIndex End, + bool RemoveDeadValNo = false); - void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { - removeRange(LR.start, LR.end, RemoveDeadValNo); + void removeSegment(Segment S, bool RemoveDeadValNo = false) { + removeSegment(S.start, S.end, RemoveDeadValNo); } - /// removeValNo - Remove all the ranges defined by the specified value#. + /// Query Liveness at Idx. + /// The sub-instruction slot of Idx doesn't matter, only the instruction + /// it refers to is considered. + LiveQueryResult Query(SlotIndex Idx) const { + // Find the segment that enters the instruction. + const_iterator I = find(Idx.getBaseIndex()); + const_iterator E = end(); + if (I == E) + return LiveQueryResult(0, 0, SlotIndex(), false); + + // Is this an instruction live-in segment? + // If Idx is the start index of a basic block, include live-in segments + // that start at Idx.getBaseIndex(). + VNInfo *EarlyVal = 0; + VNInfo *LateVal = 0; + SlotIndex EndPoint; + bool Kill = false; + if (I->start <= Idx.getBaseIndex()) { + EarlyVal = I->valno; + EndPoint = I->end; + // Move to the potentially live-out segment. + if (SlotIndex::isSameInstr(Idx, I->end)) { + Kill = true; + if (++I == E) + return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); + } + // Special case: A PHIDef value can have its def in the middle of a + // segment if the value happens to be live out of the layout + // predecessor. + // Such a value is not live-in. + if (EarlyVal->def == Idx.getBaseIndex()) + EarlyVal = 0; + } + // I now points to the segment that may be live-through, or defined by + // this instr. Ignore segments starting after the current instr. + if (!SlotIndex::isEarlierInstr(Idx, I->start)) { + LateVal = I->valno; + EndPoint = I->end; + } + return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); + } + + /// removeValNo - Remove all the segments defined by the specified value#. /// Also remove the value# from value# list. void removeValNo(VNInfo *ValNo); - /// getSize - Returns the sum of sizes of all the LiveRange's. - /// - unsigned getSize() const; - - /// Returns true if the live interval is zero length, i.e. no live ranges - /// span instructions. It doesn't pay to spill such an interval. + /// Returns true if the live range is zero length, i.e. no live segments + /// span instructions. It doesn't pay to spill such a range. bool isZeroLength(SlotIndexes *Indexes) const { for (const_iterator i = begin(), e = end(); i != e; ++i) if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() < @@ -435,27 +491,16 @@ namespace llvm { return true; } - /// isSpillable - Can this interval be spilled? - bool isSpillable() const { - return weight != HUGE_VALF; - } - - /// markNotSpillable - Mark interval as not spillable - void markNotSpillable() { - weight = HUGE_VALF; - } - - bool operator<(const LiveInterval& other) const { + bool operator<(const LiveRange& other) const { const SlotIndex &thisIndex = beginIndex(); const SlotIndex &otherIndex = other.beginIndex(); - return (thisIndex < otherIndex || - (thisIndex == otherIndex && reg < other.reg)); + return thisIndex < otherIndex; } void print(raw_ostream &OS) const; void dump() const; - /// \brief Walk the interval and assert if any invariants fail to hold. + /// \brief Walk the range and assert if any invariants fail to hold. /// /// Note that this is a no-op when asserts are disabled. #ifdef NDEBUG @@ -466,11 +511,55 @@ namespace llvm { private: - Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From); - void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd); - Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr); + iterator addSegmentFrom(Segment S, iterator From); + void extendSegmentEndTo(iterator I, SlotIndex NewEnd); + iterator extendSegmentStartTo(iterator I, SlotIndex NewStr); void markValNoForDeletion(VNInfo *V); + }; + + inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { + LR.print(OS); + return OS; + } + + /// LiveInterval - This class represents the liveness of a register, + /// or stack slot. + class LiveInterval : public LiveRange { + public: + typedef LiveRange super; + + const unsigned reg; // the register or stack slot of this interval. + float weight; // weight of this interval + + LiveInterval(unsigned Reg, float Weight) + : reg(Reg), weight(Weight) {} + + /// getSize - Returns the sum of sizes of all the LiveRange's. + /// + unsigned getSize() const; + + /// isSpillable - Can this interval be spilled? + bool isSpillable() const { + return weight != llvm::huge_valf; + } + + /// markNotSpillable - Mark interval as not spillable + void markNotSpillable() { + weight = llvm::huge_valf; + } + + bool operator<(const LiveInterval& other) const { + const SlotIndex &thisIndex = beginIndex(); + const SlotIndex &otherIndex = other.beginIndex(); + return thisIndex < otherIndex || + (thisIndex == otherIndex && reg < other.reg); + } + + void print(raw_ostream &OS) const; + void dump() const; + + private: LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION; }; @@ -480,54 +569,65 @@ namespace llvm { return OS; } - /// Helper class for performant LiveInterval bulk updates. + raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S); + + inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { + return V < S.start; + } + + inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { + return S.start < V; + } + + /// Helper class for performant LiveRange bulk updates. /// - /// Calling LiveInterval::addRange() repeatedly can be expensive on large + /// Calling LiveRange::addSegment() repeatedly can be expensive on large /// live ranges because segments after the insertion point may need to be /// shifted. The LiveRangeUpdater class can defer the shifting when adding /// many segments in order. /// - /// The LiveInterval will be in an invalid state until flush() is called. + /// The LiveRange will be in an invalid state until flush() is called. class LiveRangeUpdater { - LiveInterval *LI; + LiveRange *LR; SlotIndex LastStart; - LiveInterval::iterator WriteI; - LiveInterval::iterator ReadI; - SmallVector<LiveRange, 16> Spills; + LiveRange::iterator WriteI; + LiveRange::iterator ReadI; + SmallVector<LiveRange::Segment, 16> Spills; void mergeSpills(); public: - /// Create a LiveRangeUpdater for adding segments to LI. - /// LI will temporarily be in an invalid state until flush() is called. - LiveRangeUpdater(LiveInterval *li = 0) : LI(li) {} + /// Create a LiveRangeUpdater for adding segments to LR. + /// LR will temporarily be in an invalid state until flush() is called. + LiveRangeUpdater(LiveRange *lr = 0) : LR(lr) {} ~LiveRangeUpdater() { flush(); } - /// Add a segment to LI and coalesce when possible, just like LI.addRange(). - /// Segments should be added in increasing start order for best performance. - void add(LiveRange); + /// Add a segment to LR and coalesce when possible, just like + /// LR.addSegment(). Segments should be added in increasing start order for + /// best performance. + void add(LiveRange::Segment); void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { - add(LiveRange(Start, End, VNI)); + add(LiveRange::Segment(Start, End, VNI)); } - /// Return true if the LI is currently in an invalid state, and flush() + /// Return true if the LR is currently in an invalid state, and flush() /// needs to be called. bool isDirty() const { return LastStart.isValid(); } - /// Flush the updater state to LI so it is valid and contains all added + /// Flush the updater state to LR so it is valid and contains all added /// segments. void flush(); /// Select a different destination live range. - void setDest(LiveInterval *li) { - if (LI != li && isDirty()) + void setDest(LiveRange *lr) { + if (LR != lr && isDirty()) flush(); - LI = li; + LR = lr; } /// Get the current destination live range. - LiveInterval *getDest() const { return LI; } + LiveRange *getDest() const { return LR; } void dump() const; void print(raw_ostream&) const; @@ -538,99 +638,6 @@ namespace llvm { return OS; } - /// LiveRangeQuery - Query information about a live range around a given - /// instruction. This class hides the implementation details of live ranges, - /// and it should be used as the primary interface for examining live ranges - /// around instructions. - /// - class LiveRangeQuery { - VNInfo *EarlyVal; - VNInfo *LateVal; - SlotIndex EndPoint; - bool Kill; - - public: - /// Create a LiveRangeQuery for the given live range and instruction index. - /// The sub-instruction slot of Idx doesn't matter, only the instruction it - /// refers to is considered. - LiveRangeQuery(const LiveInterval &LI, SlotIndex Idx) - : EarlyVal(0), LateVal(0), Kill(false) { - // Find the segment that enters the instruction. - LiveInterval::const_iterator I = LI.find(Idx.getBaseIndex()); - LiveInterval::const_iterator E = LI.end(); - if (I == E) - return; - // Is this an instruction live-in segment? - // If Idx is the start index of a basic block, include live-in segments - // that start at Idx.getBaseIndex(). - if (I->start <= Idx.getBaseIndex()) { - EarlyVal = I->valno; - EndPoint = I->end; - // Move to the potentially live-out segment. - if (SlotIndex::isSameInstr(Idx, I->end)) { - Kill = true; - if (++I == E) - return; - } - // Special case: A PHIDef value can have its def in the middle of a - // segment if the value happens to be live out of the layout - // predecessor. - // Such a value is not live-in. - if (EarlyVal->def == Idx.getBaseIndex()) - EarlyVal = 0; - } - // I now points to the segment that may be live-through, or defined by - // this instr. Ignore segments starting after the current instr. - if (SlotIndex::isEarlierInstr(Idx, I->start)) - return; - LateVal = I->valno; - EndPoint = I->end; - } - - /// Return the value that is live-in to the instruction. This is the value - /// that will be read by the instruction's use operands. Return NULL if no - /// value is live-in. - VNInfo *valueIn() const { - return EarlyVal; - } - - /// Return true if the live-in value is killed by this instruction. This - /// means that either the live range ends at the instruction, or it changes - /// value. - bool isKill() const { - return Kill; - } - - /// Return true if this instruction has a dead def. - bool isDeadDef() const { - return EndPoint.isDead(); - } - - /// Return the value leaving the instruction, if any. This can be a - /// live-through value, or a live def. A dead def returns NULL. - VNInfo *valueOut() const { - return isDeadDef() ? 0 : LateVal; - } - - /// Return the value defined by this instruction, if any. This includes - /// dead defs, it is the value created by the instruction's def operands. - VNInfo *valueDefined() const { - return EarlyVal == LateVal ? 0 : LateVal; - } - - /// Return the end point of the last live range segment to interact with - /// the instruction, if any. - /// - /// The end point is an invalid SlotIndex only if the live range doesn't - /// intersect the instruction at all. - /// - /// The end point may be at or past the end of the instruction's basic - /// block. That means the value was live out of the block. - SlotIndex endPoint() const { - return EndPoint; - } - }; - /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a /// LiveInterval into equivalence clases of connected components. A /// LiveInterval that has multiple connected components can be broken into diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 7d72f37255b4c..d8437f09aaa7a 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -35,6 +35,7 @@ namespace llvm { class AliasAnalysis; class BitVector; + class BlockFrequency; class LiveRangeCalc; class LiveVariables; class MachineDominatorTree; @@ -89,9 +90,9 @@ namespace llvm { /// block. SmallVector<std::pair<unsigned, unsigned>, 8> RegMaskBlocks; - /// RegUnitIntervals - Keep a live interval for each register unit as a way - /// of tracking fixed physreg interference. - SmallVector<LiveInterval*, 0> RegUnitIntervals; + /// Keeps a live range set for each register unit to track fixed physreg + /// interference. + SmallVector<LiveRange*, 0> RegUnitRanges; public: static char ID; // Pass identification, replacement for typeid @@ -99,12 +100,13 @@ namespace llvm { virtual ~LiveIntervals(); // Calculate the spill weight to assign to a single instruction. - static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth); + static float getSpillWeight(bool isDef, bool isUse, BlockFrequency freq); LiveInterval &getInterval(unsigned Reg) { - LiveInterval *LI = VirtRegIntervals[Reg]; - assert(LI && "Interval does not exist for virtual register"); - return *LI; + if (hasInterval(Reg)) + return *VirtRegIntervals[Reg]; + else + return createAndComputeVirtRegInterval(Reg); } const LiveInterval &getInterval(unsigned Reg) const { @@ -116,12 +118,17 @@ namespace llvm { } // Interval creation. - LiveInterval &getOrCreateInterval(unsigned Reg) { - if (!hasInterval(Reg)) { - VirtRegIntervals.grow(Reg); - VirtRegIntervals[Reg] = createInterval(Reg); - } - return getInterval(Reg); + LiveInterval &createEmptyInterval(unsigned Reg) { + assert(!hasInterval(Reg) && "Interval already exists!"); + VirtRegIntervals.grow(Reg); + VirtRegIntervals[Reg] = createInterval(Reg); + return *VirtRegIntervals[Reg]; + } + + LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { + LiveInterval &LI = createEmptyInterval(Reg); + computeVirtRegInterval(LI); + return LI; } // Interval removal. @@ -130,10 +137,10 @@ namespace llvm { VirtRegIntervals[Reg] = 0; } - /// addLiveRangeToEndOfBlock - Given a register and an instruction, - /// adds a live range from that instruction to the end of its MBB. - LiveRange addLiveRangeToEndOfBlock(unsigned reg, - MachineInstr* startInst); + /// Given a register and an instruction, adds a live segment from that + /// instruction to the end of its MBB. + LiveInterval::Segment addSegmentToEndOfBlock(unsigned reg, + MachineInstr* startInst); /// shrinkToUses - After removing some uses of a register, shrink its live /// range to just the remaining uses. This method does not compute reaching @@ -153,7 +160,7 @@ namespace llvm { /// extended to be live out of the basic block. /// /// See also LiveRangeCalc::extend(). - void extendToIndices(LiveInterval *LI, ArrayRef<SlotIndex> Indices); + void extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Indices); /// pruneValue - If an LI value is live at Kill, prune its live range by /// removing any liveness reachable from Kill. Add live range end points to @@ -199,14 +206,14 @@ namespace llvm { return Indexes->getMBBEndIdx(mbb); } - bool isLiveInToMBB(const LiveInterval &li, + bool isLiveInToMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const { - return li.liveAt(getMBBStartIdx(mbb)); + return LR.liveAt(getMBBStartIdx(mbb)); } - bool isLiveOutOfMBB(const LiveInterval &li, + bool isLiveOutOfMBB(const LiveRange &LR, const MachineBasicBlock *mbb) const { - return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); + return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot()); } MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { @@ -224,6 +231,12 @@ namespace llvm { return Indexes->insertMachineInstrInMaps(MI); } + void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, + MachineBasicBlock::iterator E) { + for (MachineBasicBlock::iterator I = B; I != E; ++I) + Indexes->insertMachineInstrInMaps(I); + } + void RemoveMachineInstrFromMaps(MachineInstr *MI) { Indexes->removeMachineInstrFromMaps(MI); } @@ -351,24 +364,24 @@ namespace llvm { /// getRegUnit - Return the live range for Unit. /// It will be computed if it doesn't exist. - LiveInterval &getRegUnit(unsigned Unit) { - LiveInterval *LI = RegUnitIntervals[Unit]; - if (!LI) { + LiveRange &getRegUnit(unsigned Unit) { + LiveRange *LR = RegUnitRanges[Unit]; + if (!LR) { // Compute missing ranges on demand. - RegUnitIntervals[Unit] = LI = new LiveInterval(Unit, HUGE_VALF); - computeRegUnitInterval(LI); + RegUnitRanges[Unit] = LR = new LiveRange(); + computeRegUnitRange(*LR, Unit); } - return *LI; + return *LR; } /// getCachedRegUnit - Return the live range for Unit if it has already /// been computed, or NULL if it hasn't been computed yet. - LiveInterval *getCachedRegUnit(unsigned Unit) { - return RegUnitIntervals[Unit]; + LiveRange *getCachedRegUnit(unsigned Unit) { + return RegUnitRanges[Unit]; } - const LiveInterval *getCachedRegUnit(unsigned Unit) const { - return RegUnitIntervals[Unit]; + const LiveRange *getCachedRegUnit(unsigned Unit) const { + return RegUnitRanges[Unit]; } private: @@ -384,8 +397,8 @@ namespace llvm { void dumpInstrs() const; void computeLiveInRegUnits(); - void computeRegUnitInterval(LiveInterval*); - void computeVirtRegInterval(LiveInterval*); + void computeRegUnitRange(LiveRange&, unsigned Unit); + void computeVirtRegInterval(LiveInterval&); class HMEditor; }; diff --git a/include/llvm/CodeGen/LiveIntervalUnion.h b/include/llvm/CodeGen/LiveIntervalUnion.h index 615b339bd79cc..95933d11dbb3a 100644 --- a/include/llvm/CodeGen/LiveIntervalUnion.h +++ b/include/llvm/CodeGen/LiveIntervalUnion.h @@ -32,7 +32,7 @@ typedef SparseBitVector<128> LiveVirtRegBitSet; /// Compare a live virtual register segment to a LiveIntervalUnion segment. inline bool -overlap(const LiveRange &VRSeg, +overlap(const LiveInterval::Segment &VRSeg, const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) { return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end; } diff --git a/include/llvm/CodeGen/LiveRangeEdit.h b/include/llvm/CodeGen/LiveRangeEdit.h index e59276fd6d95d..7edf67cc24d1a 100644 --- a/include/llvm/CodeGen/LiveRangeEdit.h +++ b/include/llvm/CodeGen/LiveRangeEdit.h @@ -19,19 +19,21 @@ #define LLVM_CODEGEN_LIVERANGEEDIT_H #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Target/TargetMachine.h" namespace llvm { class AliasAnalysis; class LiveIntervals; +class MachineBlockFrequencyInfo; class MachineLoopInfo; -class MachineRegisterInfo; class VirtRegMap; -class LiveRangeEdit { +class LiveRangeEdit : private MachineRegisterInfo::Delegate { public: /// Callback methods for LiveRangeEdit owners. class Delegate { @@ -56,7 +58,7 @@ public: private: LiveInterval *Parent; - SmallVectorImpl<LiveInterval*> &NewRegs; + SmallVectorImpl<unsigned> &NewRegs; MachineRegisterInfo &MRI; LiveIntervals &LIS; VirtRegMap *VRM; @@ -89,6 +91,16 @@ private: /// a load, eliminate the register by folding the def into the use. bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr*> &Dead); + typedef SetVector<LiveInterval*, + SmallVector<LiveInterval*, 8>, + SmallPtrSet<LiveInterval*, 8> > ToShrinkSet; + /// Helper for eliminateDeadDefs. + void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink); + + /// MachineRegisterInfo callback to notify when new virtual + /// registers are created. + void MRI_NoteNewVirtualRegister(unsigned VReg); + public: /// Create a LiveRangeEdit for breaking down parent into smaller pieces. /// @param parent The register being spilled or split. @@ -100,7 +112,7 @@ public: /// function. If NULL, no virtual register map updates will /// be done. This could be the case if called before Regalloc. LiveRangeEdit(LiveInterval *parent, - SmallVectorImpl<LiveInterval*> &newRegs, + SmallVectorImpl<unsigned> &newRegs, MachineFunction &MF, LiveIntervals &lis, VirtRegMap *vrm, @@ -110,7 +122,9 @@ public: TII(*MF.getTarget().getInstrInfo()), TheDelegate(delegate), FirstNew(newRegs.size()), - ScannedRemattable(false) {} + ScannedRemattable(false) { MRI.setDelegate(this); } + + ~LiveRangeEdit() { MRI.resetDelegate(this); } LiveInterval &getParent() const { assert(Parent && "No parent LiveInterval"); @@ -119,23 +133,30 @@ public: unsigned getReg() const { return getParent().reg; } /// Iterator for accessing the new registers added by this edit. - typedef SmallVectorImpl<LiveInterval*>::const_iterator iterator; + typedef SmallVectorImpl<unsigned>::const_iterator iterator; iterator begin() const { return NewRegs.begin()+FirstNew; } iterator end() const { return NewRegs.end(); } unsigned size() const { return NewRegs.size()-FirstNew; } bool empty() const { return size() == 0; } - LiveInterval *get(unsigned idx) const { return NewRegs[idx+FirstNew]; } + unsigned get(unsigned idx) const { return NewRegs[idx+FirstNew]; } - ArrayRef<LiveInterval*> regs() const { + ArrayRef<unsigned> regs() const { return makeArrayRef(NewRegs).slice(FirstNew); } + /// createEmptyIntervalFrom - Create a new empty interval based on OldReg. + LiveInterval &createEmptyIntervalFrom(unsigned OldReg); + /// createFrom - Create a new virtual register based on OldReg. - LiveInterval &createFrom(unsigned OldReg); + unsigned createFrom(unsigned OldReg); /// create - Create a new register with the same class and original slot as /// parent. - LiveInterval &create() { + LiveInterval &createEmptyInterval() { + return createEmptyIntervalFrom(getReg()); + } + + unsigned create() { return createFrom(getReg()); } @@ -201,7 +222,8 @@ public: /// calculateRegClassAndHint - Recompute register class and hint for each new /// register. void calculateRegClassAndHint(MachineFunction&, - const MachineLoopInfo&); + const MachineLoopInfo&, + const MachineBlockFrequencyInfo&); }; } diff --git a/include/llvm/CodeGen/LiveRegUnits.h b/include/llvm/CodeGen/LiveRegUnits.h new file mode 100644 index 0000000000000..02b9c55cc61f2 --- /dev/null +++ b/include/llvm/CodeGen/LiveRegUnits.h @@ -0,0 +1,88 @@ +//===-- llvm/CodeGen/LiveRegUnits.h - Live register unit set ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a Set of live register units. This can be used for ad +// hoc liveness tracking after register allocation. You can start with the +// live-ins/live-outs at the beginning/end of a block and update the information +// while walking the instructions inside the block. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVEREGUNITS_H +#define LLVM_CODEGEN_LIVEREGUNITS_H + +#include "llvm/ADT/SparseSet.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include <cassert> + +namespace llvm { + +class MachineInstr; + +/// A set of live register units with functions to track liveness when walking +/// backward/forward through a basic block. +class LiveRegUnits { + SparseSet<unsigned> LiveUnits; + + LiveRegUnits(const LiveRegUnits&) LLVM_DELETED_FUNCTION; + LiveRegUnits &operator=(const LiveRegUnits&) LLVM_DELETED_FUNCTION; +public: + /// \brief Constructs a new empty LiveRegUnits set. + LiveRegUnits() {} + + void init(const TargetRegisterInfo *TRI) { + LiveUnits.clear(); + LiveUnits.setUniverse(TRI->getNumRegs()); + } + + void clear() { LiveUnits.clear(); } + + bool empty() const { return LiveUnits.empty(); } + + /// \brief Adds a register to the set. + void addReg(unsigned Reg, const MCRegisterInfo &MCRI) { + for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits) + LiveUnits.insert(*RUnits); + } + + /// \brief Removes a register from the set. + void removeReg(unsigned Reg, const MCRegisterInfo &MCRI) { + for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits) + LiveUnits.erase(*RUnits); + } + + /// \brief Removes registers clobbered by the regmask operand @p Op. + void removeRegsInMask(const MachineOperand &Op, const MCRegisterInfo &MCRI); + + /// \brief Returns true if register @p Reg (or one of its super register) is + /// contained in the set. + bool contains(unsigned Reg, const MCRegisterInfo &MCRI) const { + for (MCRegUnitIterator RUnits(Reg, &MCRI); RUnits.isValid(); ++RUnits) { + if (LiveUnits.count(*RUnits)) + return true; + } + return false; + } + + /// \brief Simulates liveness when stepping backwards over an + /// instruction(bundle): Remove Defs, add uses. + void stepBackward(const MachineInstr &MI, const MCRegisterInfo &MCRI); + + /// \brief Simulates liveness when stepping forward over an + /// instruction(bundle): Remove killed-uses, add defs. + void stepForward(const MachineInstr &MI, const MCRegisterInfo &MCRI); + + /// \brief Adds all registers in the live-in list of block @p BB. + void addLiveIns(const MachineBasicBlock *MBB, const MCRegisterInfo &MCRI); +}; + +} // namespace llvm + +#endif diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index 6628fd278e452..dc735f7b50b9a 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -157,8 +157,8 @@ private: // Intermediate data structures void HandlePhysRegUse(unsigned Reg, MachineInstr *MI); void HandlePhysRegDef(unsigned Reg, MachineInstr *MI, - SmallVector<unsigned, 4> &Defs); - void UpdatePhysRegDefs(MachineInstr *MI, SmallVector<unsigned, 4> &Defs); + SmallVectorImpl<unsigned> &Defs); + void UpdatePhysRegDefs(MachineInstr *MI, SmallVectorImpl<unsigned> &Defs); /// FindLastRefOrPartRef - Return the last reference or partial reference of /// the specified register. diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 0f2f8746b3825..7717809e0d9fc 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -296,6 +296,11 @@ public: /// is an error to add the same register to the same set more than once. void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); } + /// Add PhysReg as live in to this block, and ensure that there is a copy of + /// PhysReg to a virtual register of class RC. Return the virtual register + /// that is a copy of the live in PhysReg. + unsigned addLiveIn(unsigned PhysReg, const TargetRegisterClass *RC); + /// removeLiveIn - Remove the specified register from the live in set. /// void removeLiveIn(unsigned Reg); @@ -405,8 +410,8 @@ public: /// branch to do so (e.g., a table jump). True is a conservative answer. bool canFallThrough(); - /// Returns a pointer to the first instructon in this block that is not a - /// PHINode instruction. When adding instruction to the beginning of the + /// Returns a pointer to the first instruction in this block that is not a + /// PHINode instruction. When adding instructions to the beginning of the /// basic block, they should be added before the returned value, not before /// the first instruction, which might be PHI. /// Returns end() is there's no non-PHI instruction. @@ -728,6 +733,31 @@ template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > { } }; + + +/// MachineInstrSpan provides an interface to get an iteration range +/// containing the instruction it was initialized with, along with all +/// those instructions inserted prior to or following that instruction +/// at some point after the MachineInstrSpan is constructed. +class MachineInstrSpan { + MachineBasicBlock &MBB; + MachineBasicBlock::iterator I, B, E; +public: + MachineInstrSpan(MachineBasicBlock::iterator I) + : MBB(*I->getParent()), + I(I), + B(I == MBB.begin() ? MBB.end() : llvm::prior(I)), + E(llvm::next(I)) {} + + MachineBasicBlock::iterator begin() { + return B == MBB.end() ? MBB.begin() : llvm::next(B); + } + MachineBasicBlock::iterator end() { return E; } + bool empty() { return begin() == end(); } + + MachineBasicBlock::iterator getInitial() { return I; } +}; + } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h index 98dd03b45cf78..c59948fd654e8 100644 --- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -1,4 +1,4 @@ -//==- MachineBranchProbabilityInfo.h - Machine Branch Probability Analysis -==// +//=- MachineBranchProbabilityInfo.h - Branch Probability Analysis -*- C++ -*-=// // // The LLVM Compiler Infrastructure // diff --git a/include/llvm/CodeGen/MachineConstantPool.h b/include/llvm/CodeGen/MachineConstantPool.h index 8ed215d75bcf0..912ce89662685 100644 --- a/include/llvm/CodeGen/MachineConstantPool.h +++ b/include/llvm/CodeGen/MachineConstantPool.h @@ -132,15 +132,17 @@ public: /// address of the function constant pool values. /// @brief The machine constant pool. class MachineConstantPool { - const DataLayout *TD; ///< The machine's DataLayout. - unsigned PoolAlignment; ///< The alignment for the pool. + const TargetMachine &TM; ///< The target machine. + unsigned PoolAlignment; ///< The alignment for the pool. std::vector<MachineConstantPoolEntry> Constants; ///< The pool of constants. /// MachineConstantPoolValues that use an existing MachineConstantPoolEntry. DenseSet<MachineConstantPoolValue*> MachineCPVsSharingEntries; + + const DataLayout *getDataLayout() const; public: /// @brief The only constructor. - explicit MachineConstantPool(const DataLayout *td) - : TD(td), PoolAlignment(1) {} + explicit MachineConstantPool(const TargetMachine &TM) + : TM(TM), PoolAlignment(1) {} ~MachineConstantPool(); /// getConstantPoolAlignment - Return the alignment required by diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h index cdec7e663708a..022634df87cf5 100644 --- a/include/llvm/CodeGen/MachineFrameInfo.h +++ b/include/llvm/CodeGen/MachineFrameInfo.h @@ -27,6 +27,7 @@ class Type; class MachineFunction; class MachineBasicBlock; class TargetFrameLowering; +class TargetMachine; class BitVector; class Value; class AllocaInst; @@ -119,6 +120,8 @@ class MachineFrameInfo { isSpillSlot(isSS), MayNeedSP(NSP), Alloca(Val), PreAllocated(false) {} }; + const TargetMachine &TM; + /// Objects - The list of stack objects allocated... /// std::vector<StackObject> Objects; @@ -201,10 +204,6 @@ class MachineFrameInfo { /// CSIValid - Has CSInfo been set yet? bool CSIValid; - /// TargetFrameLowering - Target information about frame layout. - /// - const TargetFrameLowering &TFI; - /// LocalFrameObjects - References to frame indices which are mapped /// into the local frame allocation block. <FrameIdx, LocalOffset> SmallVector<std::pair<int, int64_t>, 32> LocalFrameObjects; @@ -223,9 +222,11 @@ class MachineFrameInfo { /// Whether the "realign-stack" option is on. bool RealignOption; + + const TargetFrameLowering *getFrameLowering() const; public: - explicit MachineFrameInfo(const TargetFrameLowering &tfi, bool RealignOpt) - : TFI(tfi), RealignOption(RealignOpt) { + explicit MachineFrameInfo(const TargetMachine &TM, bool RealignOpt) + : TM(TM), RealignOption(RealignOpt) { StackSize = NumFixedObjects = OffsetAdjustment = MaxAlignment = 0; HasVarSizedObjects = false; FrameAddressTaken = false; diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index 195cce7a64d75..cccab81efbb29 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -397,8 +397,8 @@ public: return isBranch(Type) & isBarrier(Type) & !isIndirectBranch(Type); } - // isPredicable - Return true if this instruction has a predicate operand that - // controls execution. It may be set to 'always', or may be set to other + /// Return true if this instruction has a predicate operand that + /// controls execution. It may be set to 'always', or may be set to other /// values. There are various methods in TargetInstrInfo that can be used to /// control and modify the predicate in this instruction. bool isPredicable(QueryType Type = AllInBundle) const { @@ -637,6 +637,13 @@ public: bool isEHLabel() const { return getOpcode() == TargetOpcode::EH_LABEL; } bool isGCLabel() const { return getOpcode() == TargetOpcode::GC_LABEL; } bool isDebugValue() const { return getOpcode() == TargetOpcode::DBG_VALUE; } + /// A DBG_VALUE is indirect iff the first operand is a register and + /// the second operand is an immediate. + bool isIndirectDebugValue() const { + return isDebugValue() + && getOperand(0).isReg() + && getOperand(1).isImm(); + } bool isPHI() const { return getOpcode() == TargetOpcode::PHI; } bool isKill() const { return getOpcode() == TargetOpcode::KILL; } @@ -886,13 +893,12 @@ public: /// Look for the operand that defines it and mark it as IsDead. If /// AddIfNotFound is true, add a implicit operand if it's not found. Returns /// true if the operand exists / is added. - bool addRegisterDead(unsigned IncomingReg, const TargetRegisterInfo *RegInfo, + bool addRegisterDead(unsigned Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound = false); /// addRegisterDefined - We have determined MI defines a register. Make sure /// there is an operand defining Reg. - void addRegisterDefined(unsigned IncomingReg, - const TargetRegisterInfo *RegInfo = 0); + void addRegisterDefined(unsigned Reg, const TargetRegisterInfo *RegInfo = 0); /// setPhysRegsDeadExcept - Mark every physreg used by this instruction as /// dead except those in the UsedRegs list. @@ -908,11 +914,6 @@ public: bool isSafeToMove(const TargetInstrInfo *TII, AliasAnalysis *AA, bool &SawStore) const; - /// isSafeToReMat - Return true if it's safe to rematerialize the specified - /// instruction which defined the specified register instead of copying it. - bool isSafeToReMat(const TargetInstrInfo *TII, AliasAnalysis *AA, - unsigned DstReg) const; - /// hasOrderedMemoryRef - Return true if this instruction may have an ordered /// or volatile memory reference, or if the information describing the memory /// reference is not available. Return false if it is known to have no diff --git a/include/llvm/CodeGen/MachineInstrBuilder.h b/include/llvm/CodeGen/MachineInstrBuilder.h index 92c8da991ca44..df01371a47ec5 100644 --- a/include/llvm/CodeGen/MachineInstrBuilder.h +++ b/include/llvm/CodeGen/MachineInstrBuilder.h @@ -335,6 +335,51 @@ inline MachineInstrBuilder BuildMI(MachineBasicBlock *BB, return BuildMI(*BB, BB->end(), DL, MCID, DestReg); } +/// BuildMI - This version of the builder builds a DBG_VALUE intrinsic +/// for either a value in a register or a register-indirect+offset +/// address. The convention is that a DBG_VALUE is indirect iff the +/// second operand is an immediate. +/// +inline MachineInstrBuilder BuildMI(MachineFunction &MF, + DebugLoc DL, + const MCInstrDesc &MCID, + bool IsIndirect, + unsigned Reg, + unsigned Offset, + const MDNode *MD) { + if (IsIndirect) + return BuildMI(MF, DL, MCID) + .addReg(Reg, RegState::Debug) + .addImm(Offset) + .addMetadata(MD); + else { + assert(Offset == 0 && "A direct address cannot have an offset."); + return BuildMI(MF, DL, MCID) + .addReg(Reg, RegState::Debug) + .addReg(0U, RegState::Debug) + .addMetadata(MD); + } +} + +/// BuildMI - This version of the builder builds a DBG_VALUE intrinsic +/// for either a value in a register or a register-indirect+offset +/// address and inserts it at position I. +/// +inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB, + MachineBasicBlock::iterator I, + DebugLoc DL, + const MCInstrDesc &MCID, + bool IsIndirect, + unsigned Reg, + unsigned Offset, + const MDNode *MD) { + MachineFunction &MF = *BB.getParent(); + MachineInstr *MI = BuildMI(MF, DL, MCID, IsIndirect, Reg, Offset, MD); + BB.insert(I, MI); + return MachineInstrBuilder(MF, MI); +} + + inline unsigned getDefRegState(bool B) { return B ? RegState::Define : 0; } diff --git a/include/llvm/CodeGen/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h index a3acec8095473..460c08c8ca7ee 100644 --- a/include/llvm/CodeGen/MachineModuleInfo.h +++ b/include/llvm/CodeGen/MachineModuleInfo.h @@ -106,9 +106,9 @@ class MachineModuleInfo : public ImmutablePass { /// want. MachineModuleInfoImpl *ObjFileMMI; - /// FrameMoves - List of moves done by a function's prolog. Used to construct - /// frame maps by debug and exception handling consumers. - std::vector<MachineMove> FrameMoves; + /// List of moves done by a function's prolog. Used to construct frame maps + /// by debug and exception handling consumers. + std::vector<MCCFIInstruction> FrameInstructions; /// CompactUnwindEncoding - If the target supports it, this is the compact /// unwind encoding. It replaces a function's CIE and FDE. @@ -231,10 +231,16 @@ public: UsesVAFloatArgument = b; } - /// getFrameMoves - Returns a reference to a list of moves done in the current + /// \brief Returns a reference to a list of cfi instructions in the current /// function's prologue. Used to construct frame maps for debug and exception /// handling comsumers. - std::vector<MachineMove> &getFrameMoves() { return FrameMoves; } + const std::vector<MCCFIInstruction> &getFrameInstructions() const { + return FrameInstructions; + } + + void addFrameInst(const MCCFIInstruction &Inst) { + FrameInstructions.push_back(Inst); + } /// getCompactUnwindEncoding - Returns the compact unwind encoding for a /// function if the target supports the encoding. This encoding replaces a diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h index 414770b9ecf0f..40f3580bfdb49 100644 --- a/include/llvm/CodeGen/MachineOperand.h +++ b/include/llvm/CodeGen/MachineOperand.h @@ -391,7 +391,7 @@ public: } void setIsDebug(bool Val = true) { - assert(isReg() && IsDef && "Wrong MachineOperand accessor"); + assert(isReg() && !IsDef && "Wrong MachineOperand accessor"); IsDebug = Val; } @@ -564,6 +564,8 @@ public: unsigned SubReg = 0, bool isDebug = false, bool isInternalRead = false) { + assert(!(isDead && !isDef) && "Dead flag on non-def"); + assert(!(isKill && isDef) && "Kill flag on def"); MachineOperand Op(MachineOperand::MO_Register); Op.IsDef = isDef; Op.IsImp = isImp; diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h index 24ba7bb1ac58e..58ca907316acc 100644 --- a/include/llvm/CodeGen/MachineRegisterInfo.h +++ b/include/llvm/CodeGen/MachineRegisterInfo.h @@ -17,16 +17,29 @@ #include "llvm/ADT/BitVector.h" #include "llvm/ADT/IndexedMap.h" #include "llvm/CodeGen/MachineInstrBundle.h" +#include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" #include <vector> namespace llvm { +class PSetIterator; /// MachineRegisterInfo - Keep track of information for virtual and physical /// registers, including vreg register classes, use/def chains for registers, /// etc. class MachineRegisterInfo { - const TargetRegisterInfo *const TRI; +public: + class Delegate { + virtual void anchor(); + public: + virtual void MRI_NoteNewVirtualRegister(unsigned Reg) = 0; + + virtual ~Delegate() {} + }; + +private: + const TargetMachine &TM; + Delegate *TheDelegate; /// IsSSA - True when the machine function is in SSA form and virtual /// registers have a single def. @@ -108,9 +121,30 @@ class MachineRegisterInfo { MachineRegisterInfo(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION; void operator=(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION; public: - explicit MachineRegisterInfo(const TargetRegisterInfo &TRI); + explicit MachineRegisterInfo(const TargetMachine &TM); ~MachineRegisterInfo(); + const TargetRegisterInfo *getTargetRegisterInfo() const { + return TM.getRegisterInfo(); + } + + void resetDelegate(Delegate *delegate) { + // Ensure another delegate does not take over unless the current + // delegate first unattaches itself. If we ever need to multicast + // notifications, we will need to change to using a list. + assert(TheDelegate == delegate && + "Only the current delegate can perform reset!"); + TheDelegate = 0; + } + + void setDelegate(Delegate *delegate) { + assert(delegate && !TheDelegate && + "Attempted to set delegate to null, or to change it without " + "first resetting it!"); + + TheDelegate = delegate; + } + //===--------------------------------------------------------------------===// // Function State //===--------------------------------------------------------------------===// @@ -294,6 +328,11 @@ public: /// a physreg. bool isConstantPhysReg(unsigned PhysReg, const MachineFunction &MF) const; + /// Get an iterator over the pressure sets affected by the given physical or + /// virtual register. If RegUnit is physical, it must be a register unit (from + /// MCRegUnitIterator). + PSetIterator getPressureSets(unsigned RegUnit) const; + //===--------------------------------------------------------------------===// // Virtual Register Info //===--------------------------------------------------------------------===// @@ -377,7 +416,8 @@ public: bool isPhysRegUsed(unsigned Reg) const { if (UsedPhysRegMask.test(Reg)) return true; - for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) + for (MCRegUnitIterator Units(Reg, getTargetRegisterInfo()); + Units.isValid(); ++Units) if (UsedRegUnits.test(*Units)) return true; return false; @@ -392,7 +432,8 @@ public: /// setPhysRegUsed - Mark the specified register used in this function. /// This should only be called during and after register allocation. void setPhysRegUsed(unsigned Reg) { - for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) + for (MCRegUnitIterator Units(Reg, getTargetRegisterInfo()); + Units.isValid(); ++Units) UsedRegUnits.set(*Units); } @@ -406,7 +447,8 @@ public: /// This should only be called during and after register allocation. void setPhysRegUnused(unsigned Reg) { UsedPhysRegMask.reset(Reg); - for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) + for (MCRegUnitIterator Units(Reg, getTargetRegisterInfo()); + Units.isValid(); ++Units) UsedRegUnits.reset(*Units); } @@ -466,7 +508,8 @@ public: /// register, so a register allocator needs to track its liveness and /// availability. bool isAllocatable(unsigned PhysReg) const { - return TRI->isInAllocatableClass(PhysReg) && !isReserved(PhysReg); + return getTargetRegisterInfo()->isInAllocatableClass(PhysReg) && + !isReserved(PhysReg); } //===--------------------------------------------------------------------===// @@ -611,9 +654,49 @@ public: return Op->getParent(); } }; +}; +/// Iterate over the pressure sets affected by the given physical or virtual +/// register. If Reg is physical, it must be a register unit (from +/// MCRegUnitIterator). +class PSetIterator { + const int *PSet; + unsigned Weight; +public: + PSetIterator(): PSet(0), Weight(0) {} + PSetIterator(unsigned RegUnit, const MachineRegisterInfo *MRI) { + const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo(); + if (TargetRegisterInfo::isVirtualRegister(RegUnit)) { + const TargetRegisterClass *RC = MRI->getRegClass(RegUnit); + PSet = TRI->getRegClassPressureSets(RC); + Weight = TRI->getRegClassWeight(RC).RegWeight; + } + else { + PSet = TRI->getRegUnitPressureSets(RegUnit); + Weight = TRI->getRegUnitWeight(RegUnit); + } + if (*PSet == -1) + PSet = 0; + } + bool isValid() const { return PSet; } + + unsigned getWeight() const { return Weight; } + + unsigned operator*() const { return *PSet; } + + void operator++() { + assert(isValid() && "Invalid PSetIterator."); + ++PSet; + if (*PSet == -1) + PSet = 0; + } }; +inline PSetIterator MachineRegisterInfo:: +getPressureSets(unsigned RegUnit) const { + return PSetIterator(RegUnit, this); +} + } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/MachineRelocation.h b/include/llvm/CodeGen/MachineRelocation.h index 244b466e17282..e77845745165a 100644 --- a/include/llvm/CodeGen/MachineRelocation.h +++ b/include/llvm/CodeGen/MachineRelocation.h @@ -57,7 +57,7 @@ class MachineRelocation { union { void *Result; // If this has been resolved to a resolved pointer GlobalValue *GV; // If this is a pointer to a GV or an indirect ref. - MachineBasicBlock *MBB; // If this is a pointer to a LLVM BB + MachineBasicBlock *MBB; // If this is a pointer to an LLVM BB const char *ExtSym; // If this is a pointer to a named symbol unsigned Index; // Constant pool / jump table index unsigned GOTIndex; // Index in the GOT of this symbol/global diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index 769e4b42a5f16..77828953347c6 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -7,8 +7,48 @@ // //===----------------------------------------------------------------------===// // -// This file provides a MachineSchedRegistry for registering alternative machine -// schedulers. A Target may provide an alternative scheduler implementation by +// This file provides an interface for customizing the standard MachineScheduler +// pass. Note that the entire pass may be replaced as follows: +// +// <Target>TargetMachine::createPassConfig(PassManagerBase &PM) { +// PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID); +// ...} +// +// The MachineScheduler pass is only responsible for choosing the regions to be +// scheduled. Targets can override the DAG builder and scheduler without +// replacing the pass as follows: +// +// ScheduleDAGInstrs *<Target>PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// return new CustomMachineScheduler(C); +// } +// +// The default scheduler, ScheduleDAGMI, builds the DAG and drives list +// scheduling while updating the instruction stream, register pressure, and live +// intervals. Most targets don't need to override the DAG builder and list +// schedulier, but subtargets that require custom scheduling heuristics may +// plugin an alternate MachineSchedStrategy. The strategy is responsible for +// selecting the highest priority node from the list: +// +// ScheduleDAGInstrs *<Target>PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// return new ScheduleDAGMI(C, CustomStrategy(C)); +// } +// +// The DAG builder can also be customized in a sense by adding DAG mutations +// that will run after DAG building and before list scheduling. DAG mutations +// can adjust dependencies based on target-specific knowledge or add weak edges +// to aid heuristics: +// +// ScheduleDAGInstrs *<Target>PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// ScheduleDAGMI *DAG = new ScheduleDAGMI(C, CustomStrategy(C)); +// DAG->addMutation(new CustomDependencies(DAG->TII, DAG->TRI)); +// return DAG; +// } +// +// A target that supports alternative schedulers can use the +// MachineSchedRegistry to allow command line selection. This can be done by // implementing the following boilerplate: // // static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) { @@ -18,9 +58,19 @@ // SchedCustomRegistry("custom", "Run my target's custom scheduler", // createCustomMachineSched); // -// Inside <Target>PassConfig: -// enablePass(&MachineSchedulerID); -// MachineSchedRegistry::setDefault(createCustomMachineSched); +// +// Finally, subtargets that don't need to implement custom heuristics but would +// like to configure the GenericScheduler's policy for a given scheduler region, +// including scheduling direction and register pressure tracking policy, can do +// this: +// +// void <SubTarget>Subtarget:: +// overrideSchedPolicy(MachineSchedPolicy &Policy, +// MachineInstr *begin, +// MachineInstr *end, +// unsigned NumRegionInstrs) const { +// Policy.<Flag> = true; +// } // //===----------------------------------------------------------------------===// @@ -30,7 +80,6 @@ #include "llvm/CodeGen/MachinePassRegistry.h" #include "llvm/CodeGen/RegisterPressure.h" #include "llvm/CodeGen/ScheduleDAGInstrs.h" -#include "llvm/Target/TargetInstrInfo.h" namespace llvm { @@ -86,15 +135,6 @@ public: static MachineSchedRegistry *getList() { return (MachineSchedRegistry *)Registry.getList(); } - static ScheduleDAGCtor getDefault() { - return (ScheduleDAGCtor)Registry.getDefault(); - } - static void setDefault(ScheduleDAGCtor C) { - Registry.setDefault((MachinePassCtor)C); - } - static void setDefault(StringRef Name) { - Registry.setDefault(Name); - } static void setListener(MachinePassRegistryListener *L) { Registry.setListener(L); } @@ -102,12 +142,41 @@ public: class ScheduleDAGMI; +/// Define a generic scheduling policy for targets that don't provide their own +/// MachineSchedStrategy. This can be overriden for each scheduling region +/// before building the DAG. +struct MachineSchedPolicy { + // Allow the scheduler to disable register pressure tracking. + bool ShouldTrackPressure; + + // Allow the scheduler to force top-down or bottom-up scheduling. If neither + // is true, the scheduler runs in both directions and converges. + bool OnlyTopDown; + bool OnlyBottomUp; + + MachineSchedPolicy(): + ShouldTrackPressure(false), OnlyTopDown(false), OnlyBottomUp(false) {} +}; + /// MachineSchedStrategy - Interface to the scheduling algorithm used by /// ScheduleDAGMI. +/// +/// Initialization sequence: +/// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots class MachineSchedStrategy { + virtual void anchor(); public: virtual ~MachineSchedStrategy() {} + /// Optionally override the per-region scheduling policy. + virtual void initPolicy(MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + unsigned NumRegionInstrs) {} + + /// Check if pressure tracking is needed before building the DAG and + /// initializing this strategy. Called after initPolicy. + virtual bool shouldTrackPressure() const { return true; } + /// Initialize the strategy after building the DAG for a new region. virtual void initialize(ScheduleDAGMI *DAG) = 0; @@ -194,6 +263,7 @@ public: /// Mutate the DAG as a postpass after normal DAG building. class ScheduleDAGMutation { + virtual void anchor(); public: virtual ~ScheduleDAGMutation() {} @@ -222,14 +292,20 @@ protected: MachineBasicBlock::iterator LiveRegionEnd; - /// Register pressure in this region computed by buildSchedGraph. + // Map each SU to its summary of pressure changes. This array is updated for + // liveness during bottom-up scheduling. Top-down scheduling may proceed but + // has no affect on the pressure diffs. + PressureDiffs SUPressureDiffs; + + /// Register pressure in this region computed by initRegPressure. + bool ShouldTrackPressure; IntervalPressure RegPressure; RegPressureTracker RPTracker; /// List of pressure sets that exceed the target's pressure limit before /// scheduling, listed in increasing set ID order. Each pressure set is paired /// with its max pressure in the currently scheduled regions. - std::vector<PressureElement> RegionCriticalPSets; + std::vector<PressureChange> RegionCriticalPSets; /// The top of the unscheduled zone. MachineBasicBlock::iterator CurrentTop; @@ -255,8 +331,9 @@ public: ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0), - Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), - TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), + Topo(SUnits, &ExitSU), ShouldTrackPressure(false), + RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), + CurrentBottom(), BotRPTracker(BotPressure), NextClusterPred(NULL), NextClusterSucc(NULL) { #ifndef NDEBUG NumInstrsScheduled = 0; @@ -265,6 +342,9 @@ public: virtual ~ScheduleDAGMI(); + /// \brief Return true if register pressure tracking is enabled. + bool isTrackingPressure() const { return ShouldTrackPressure; } + /// Add a postprocessing step to the DAG builder. /// Mutations are applied in the order that they are added after normal DAG /// building and before MachineSchedStrategy initialization. @@ -294,8 +374,7 @@ public: void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, - unsigned endcount); - + unsigned regioninstrs) LLVM_OVERRIDE; /// Implement ScheduleDAGInstrs interface for scheduling a sequence of /// reorderable instructions. @@ -316,10 +395,14 @@ public: /// Get register pressure for the entire scheduling region before scheduling. const IntervalPressure &getRegPressure() const { return RegPressure; } - const std::vector<PressureElement> &getRegionCriticalPSets() const { + const std::vector<PressureChange> &getRegionCriticalPSets() const { return RegionCriticalPSets; } + PressureDiff &getPressureDiff(const SUnit *SU) { + return SUPressureDiffs[SU->NodeNum]; + } + const SUnit *getNextClusterPred() const { return NextClusterPred; } const SUnit *getNextClusterSucc() const { return NextClusterSucc; } @@ -333,6 +416,9 @@ public: BitVector &getScheduledTrees() { return ScheduledTrees; } + /// Compute the cyclic critical path through the DAG. + unsigned computeCyclicCriticalPath(); + void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE; void viewGraph() LLVM_OVERRIDE; @@ -368,7 +454,10 @@ protected: void initRegPressure(); - void updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure); + void updatePressureDiffs(ArrayRef<unsigned> LiveUses); + + void updateScheduledPressure(const SUnit *SU, + const std::vector<unsigned> &NewMaxPressure); bool checkSchedLimit(); diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index 85bf511d60229..aca0a91303426 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -20,79 +20,63 @@ #include "llvm/ADT/ilist_node.h" #include <list> #include <map> +#include <set> namespace PBQP { /// PBQP Graph class. /// Instances of this class describe PBQP problems. class Graph { - private: - - // ----- TYPEDEFS ----- - class NodeEntry; - class EdgeEntry; - - typedef llvm::ilist<NodeEntry> NodeList; - typedef llvm::ilist<EdgeEntry> EdgeList; - public: - typedef NodeEntry* NodeItr; - typedef const NodeEntry* ConstNodeItr; - - typedef EdgeEntry* EdgeItr; - typedef const EdgeEntry* ConstEdgeItr; + typedef unsigned NodeId; + typedef unsigned EdgeId; private: - typedef std::list<EdgeItr> AdjEdgeList; - + typedef std::set<NodeId> AdjEdgeList; + public: typedef AdjEdgeList::iterator AdjEdgeItr; private: - class NodeEntry : public llvm::ilist_node<NodeEntry> { - friend struct llvm::ilist_sentinel_traits<NodeEntry>; + class NodeEntry { private: - Vector costs; + Vector costs; AdjEdgeList adjEdges; - unsigned degree; void *data; NodeEntry() : costs(0, 0) {} public: - NodeEntry(const Vector &costs) : costs(costs), degree(0) {} + NodeEntry(const Vector &costs) : costs(costs), data(0) {} Vector& getCosts() { return costs; } const Vector& getCosts() const { return costs; } - unsigned getDegree() const { return degree; } + unsigned getDegree() const { return adjEdges.size(); } AdjEdgeItr edgesBegin() { return adjEdges.begin(); } AdjEdgeItr edgesEnd() { return adjEdges.end(); } - AdjEdgeItr addEdge(EdgeItr e) { - ++degree; + AdjEdgeItr addEdge(EdgeId e) { return adjEdges.insert(adjEdges.end(), e); } void removeEdge(AdjEdgeItr ae) { - --degree; adjEdges.erase(ae); } void setData(void *data) { this->data = data; } void* getData() { return data; } }; - class EdgeEntry : public llvm::ilist_node<EdgeEntry> { - friend struct llvm::ilist_sentinel_traits<EdgeEntry>; + class EdgeEntry { private: - NodeItr node1, node2; + NodeId node1, node2; Matrix costs; AdjEdgeItr node1AEItr, node2AEItr; void *data; - EdgeEntry() : costs(0, 0, 0) {} + EdgeEntry() : costs(0, 0, 0), data(0) {} public: - EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs) + EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs) : node1(node1), node2(node2), costs(costs) {} - NodeItr getNode1() const { return node1; } - NodeItr getNode2() const { return node2; } + NodeId getNode1() const { return node1; } + NodeId getNode2() const { return node2; } Matrix& getCosts() { return costs; } const Matrix& getCosts() const { return costs; } void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; } @@ -105,254 +89,305 @@ namespace PBQP { // ----- MEMBERS ----- - NodeList nodes; - unsigned numNodes; + typedef std::vector<NodeEntry> NodeVector; + typedef std::vector<NodeId> FreeNodeVector; + NodeVector nodes; + FreeNodeVector freeNodes; - EdgeList edges; - unsigned numEdges; + typedef std::vector<EdgeEntry> EdgeVector; + typedef std::vector<EdgeId> FreeEdgeVector; + EdgeVector edges; + FreeEdgeVector freeEdges; // ----- INTERNAL METHODS ----- - NodeEntry& getNode(NodeItr nItr) { return *nItr; } - const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; } - - EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; } - const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; } - - NodeItr addConstructedNode(const NodeEntry &n) { - ++numNodes; - return nodes.insert(nodes.end(), n); + NodeEntry& getNode(NodeId nId) { return nodes[nId]; } + const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; } + + EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; } + const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; } + + NodeId addConstructedNode(const NodeEntry &n) { + NodeId nodeId = 0; + if (!freeNodes.empty()) { + nodeId = freeNodes.back(); + freeNodes.pop_back(); + nodes[nodeId] = n; + } else { + nodeId = nodes.size(); + nodes.push_back(n); + } + return nodeId; } - EdgeItr addConstructedEdge(const EdgeEntry &e) { - assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() && + EdgeId addConstructedEdge(const EdgeEntry &e) { + assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() && "Attempt to add duplicate edge."); - ++numEdges; - EdgeItr edgeItr = edges.insert(edges.end(), e); - EdgeEntry &ne = getEdge(edgeItr); + EdgeId edgeId = 0; + if (!freeEdges.empty()) { + edgeId = freeEdges.back(); + freeEdges.pop_back(); + edges[edgeId] = e; + } else { + edgeId = edges.size(); + edges.push_back(e); + } + + EdgeEntry &ne = getEdge(edgeId); NodeEntry &n1 = getNode(ne.getNode1()); NodeEntry &n2 = getNode(ne.getNode2()); + // Sanity check on matrix dimensions: assert((n1.getCosts().getLength() == ne.getCosts().getRows()) && (n2.getCosts().getLength() == ne.getCosts().getCols()) && "Edge cost dimensions do not match node costs dimensions."); - ne.setNode1AEItr(n1.addEdge(edgeItr)); - ne.setNode2AEItr(n2.addEdge(edgeItr)); - return edgeItr; + + ne.setNode1AEItr(n1.addEdge(edgeId)); + ne.setNode2AEItr(n2.addEdge(edgeId)); + return edgeId; } - inline void copyFrom(const Graph &other); + Graph(const Graph &other) {} + void operator=(const Graph &other) {} + public: - /// \brief Construct an empty PBQP graph. - Graph() : numNodes(0), numEdges(0) {} + class NodeItr { + public: + NodeItr(NodeId nodeId, const Graph &g) + : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) { + this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId + } - /// \brief Copy construct this graph from "other". Note: Does not copy node - /// and edge data, only graph structure and costs. - /// @param other Source graph to copy from. - Graph(const Graph &other) : numNodes(0), numEdges(0) { - copyFrom(other); - } + bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; } + bool operator!=(const NodeItr& n) const { return !(*this == n); } + NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; } + NodeId operator*() const { return nodeId; } - /// \brief Make this graph a copy of "other". Note: Does not copy node and - /// edge data, only graph structure and costs. - /// @param other The graph to copy from. - /// @return A reference to this graph. - /// - /// This will clear the current graph, erasing any nodes and edges added, - /// before copying from other. - Graph& operator=(const Graph &other) { - clear(); - copyFrom(other); - return *this; - } + private: + NodeId findNextInUse(NodeId n) const { + while (n < endNodeId && + std::find(freeNodes.begin(), freeNodes.end(), n) != + freeNodes.end()) { + ++n; + } + return n; + } + + NodeId nodeId, endNodeId; + const FreeNodeVector& freeNodes; + }; + + class EdgeItr { + public: + EdgeItr(EdgeId edgeId, const Graph &g) + : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) { + this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId + } + + bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; } + bool operator!=(const EdgeItr& n) const { return !(*this == n); } + EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; } + EdgeId operator*() const { return edgeId; } + + private: + EdgeId findNextInUse(EdgeId n) const { + while (n < endEdgeId && + std::find(freeEdges.begin(), freeEdges.end(), n) != + freeEdges.end()) { + ++n; + } + return n; + } + + EdgeId edgeId, endEdgeId; + const FreeEdgeVector& freeEdges; + }; + + /// \brief Construct an empty PBQP graph. + Graph() {} /// \brief Add a node with the given costs. /// @param costs Cost vector for the new node. /// @return Node iterator for the added node. - NodeItr addNode(const Vector &costs) { + NodeId addNode(const Vector &costs) { return addConstructedNode(NodeEntry(costs)); } /// \brief Add an edge between the given nodes with the given costs. - /// @param n1Itr First node. - /// @param n2Itr Second node. + /// @param n1Id First node. + /// @param n2Id Second node. /// @return Edge iterator for the added edge. - EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr, - const Matrix &costs) { - assert(getNodeCosts(n1Itr).getLength() == costs.getRows() && - getNodeCosts(n2Itr).getLength() == costs.getCols() && + EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) { + assert(getNodeCosts(n1Id).getLength() == costs.getRows() && + getNodeCosts(n2Id).getLength() == costs.getCols() && "Matrix dimensions mismatch."); - return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); + return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs)); } /// \brief Get the number of nodes in the graph. /// @return Number of nodes in the graph. - unsigned getNumNodes() const { return numNodes; } + unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); } /// \brief Get the number of edges in the graph. /// @return Number of edges in the graph. - unsigned getNumEdges() const { return numEdges; } + unsigned getNumEdges() const { return edges.size() - freeEdges.size(); } /// \brief Get a node's cost vector. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Node cost vector. - Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); } + Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); } /// \brief Get a node's cost vector (const version). - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Node cost vector. - const Vector& getNodeCosts(ConstNodeItr nItr) const { - return getNode(nItr).getCosts(); + const Vector& getNodeCosts(NodeId nId) const { + return getNode(nId).getCosts(); } /// \brief Set a node's data pointer. - /// @param nItr Node iterator. + /// @param nId Node id. /// @param data Pointer to node data. /// /// Typically used by a PBQP solver to attach data to aid in solution. - void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); } + void setNodeData(NodeId nId, void *data) { getNode(nId).setData(data); } /// \brief Get the node's data pointer. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Pointer to node data. - void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); } - + void* getNodeData(NodeId nId) { return getNode(nId).getData(); } + /// \brief Get an edge's cost matrix. - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @return Edge cost matrix. - Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); } + Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); } /// \brief Get an edge's cost matrix (const version). - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @return Edge cost matrix. - const Matrix& getEdgeCosts(ConstEdgeItr eItr) const { - return getEdge(eItr).getCosts(); + const Matrix& getEdgeCosts(EdgeId eId) const { + return getEdge(eId).getCosts(); } /// \brief Set an edge's data pointer. - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @param data Pointer to edge data. /// /// Typically used by a PBQP solver to attach data to aid in solution. - void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); } + void setEdgeData(EdgeId eId, void *data) { getEdge(eId).setData(data); } /// \brief Get an edge's data pointer. - /// @param eItr Edge iterator. - /// @return Pointer to edge data. - void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); } + /// @param eId Edge id. + /// @return Pointer to edge data. + void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); } /// \brief Get a node's degree. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return The degree of the node. - unsigned getNodeDegree(NodeItr nItr) const { - return getNode(nItr).getDegree(); + unsigned getNodeDegree(NodeId nId) const { + return getNode(nId).getDegree(); } /// \brief Begin iterator for node set. - NodeItr nodesBegin() { return nodes.begin(); } - - /// \brief Begin const iterator for node set. - ConstNodeItr nodesBegin() const { return nodes.begin(); } + NodeItr nodesBegin() const { return NodeItr(0, *this); } /// \brief End iterator for node set. - NodeItr nodesEnd() { return nodes.end(); } - - /// \brief End const iterator for node set. - ConstNodeItr nodesEnd() const { return nodes.end(); } + NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); } /// \brief Begin iterator for edge set. - EdgeItr edgesBegin() { return edges.begin(); } + EdgeItr edgesBegin() const { return EdgeItr(0, *this); } /// \brief End iterator for edge set. - EdgeItr edgesEnd() { return edges.end(); } + EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); } /// \brief Get begin iterator for adjacent edge set. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Begin iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesBegin(NodeItr nItr) { - return getNode(nItr).edgesBegin(); + AdjEdgeItr adjEdgesBegin(NodeId nId) { + return getNode(nId).edgesBegin(); } /// \brief Get end iterator for adjacent edge set. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return End iterator for the set of edges connected to the given node. - AdjEdgeItr adjEdgesEnd(NodeItr nItr) { - return getNode(nItr).edgesEnd(); + AdjEdgeItr adjEdgesEnd(NodeId nId) { + return getNode(nId).edgesEnd(); } /// \brief Get the first node connected to this edge. - /// @param eItr Edge iterator. - /// @return The first node connected to the given edge. - NodeItr getEdgeNode1(EdgeItr eItr) { - return getEdge(eItr).getNode1(); + /// @param eId Edge id. + /// @return The first node connected to the given edge. + NodeId getEdgeNode1(EdgeId eId) { + return getEdge(eId).getNode1(); } /// \brief Get the second node connected to this edge. - /// @param eItr Edge iterator. - /// @return The second node connected to the given edge. - NodeItr getEdgeNode2(EdgeItr eItr) { - return getEdge(eItr).getNode2(); - } + /// @param eId Edge id. + /// @return The second node connected to the given edge. + NodeId getEdgeNode2(EdgeId eId) { + return getEdge(eId).getNode2(); + } /// \brief Get the "other" node connected to this edge. - /// @param eItr Edge iterator. - /// @param nItr Node iterator for the "given" node. - /// @return The iterator for the "other" node connected to this edge. - NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) { - EdgeEntry &e = getEdge(eItr); - if (e.getNode1() == nItr) { + /// @param eId Edge id. + /// @param nId Node id for the "given" node. + /// @return The iterator for the "other" node connected to this edge. + NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) { + EdgeEntry &e = getEdge(eId); + if (e.getNode1() == nId) { return e.getNode2(); } // else return e.getNode1(); } + EdgeId invalidEdgeId() const { + return std::numeric_limits<EdgeId>::max(); + } + /// \brief Get the edge connecting two nodes. - /// @param n1Itr First node iterator. - /// @param n2Itr Second node iterator. - /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists, - /// otherwise returns edgesEnd(). - EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) { - for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr); + /// @param n1Id First node id. + /// @param n2Id Second node id. + /// @return An id for edge (n1Id, n2Id) if such an edge exists, + /// otherwise returns an invalid edge id. + EdgeId findEdge(NodeId n1Id, NodeId n2Id) { + for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id); aeItr != aeEnd; ++aeItr) { - if ((getEdgeNode1(*aeItr) == n2Itr) || - (getEdgeNode2(*aeItr) == n2Itr)) { + if ((getEdgeNode1(*aeItr) == n2Id) || + (getEdgeNode2(*aeItr) == n2Id)) { return *aeItr; } } - return edges.end(); + return invalidEdgeId(); } /// \brief Remove a node from the graph. - /// @param nItr Node iterator. - void removeNode(NodeItr nItr) { - NodeEntry &n = getNode(nItr); - for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) { - EdgeItr eItr = *itr; - ++itr; - removeEdge(eItr); + /// @param nId Node id. + void removeNode(NodeId nId) { + NodeEntry &n = getNode(nId); + for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) { + EdgeId eId = *itr; + removeEdge(eId); } - nodes.erase(nItr); - --numNodes; + freeNodes.push_back(nId); } /// \brief Remove an edge from the graph. - /// @param eItr Edge iterator. - void removeEdge(EdgeItr eItr) { - EdgeEntry &e = getEdge(eItr); + /// @param eId Edge id. + void removeEdge(EdgeId eId) { + EdgeEntry &e = getEdge(eId); NodeEntry &n1 = getNode(e.getNode1()); NodeEntry &n2 = getNode(e.getNode2()); n1.removeEdge(e.getNode1AEItr()); n2.removeEdge(e.getNode2AEItr()); - edges.erase(eItr); - --numEdges; + freeEdges.push_back(eId); } /// \brief Remove all nodes and edges from the graph. void clear() { nodes.clear(); + freeNodes.clear(); edges.clear(); - numNodes = numEdges = 0; + freeEdges.clear(); } /// \brief Dump a graph to an output stream. @@ -362,7 +397,7 @@ namespace PBQP { for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); nodeItr != nodeEnd; ++nodeItr) { - const Vector& v = getNodeCosts(nodeItr); + const Vector& v = getNodeCosts(*nodeItr); os << "\n" << v.getLength() << "\n"; assert(v.getLength() != 0 && "Empty vector in graph."); os << v[0]; @@ -374,10 +409,10 @@ namespace PBQP { for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); edgeItr != edgeEnd; ++edgeItr) { - unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr)); - unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr)); + NodeId n1 = getEdgeNode1(*edgeItr); + NodeId n2 = getEdgeNode2(*edgeItr); assert(n1 != n2 && "PBQP graphs shound not have self-edges."); - const Matrix& m = getEdgeCosts(edgeItr); + const Matrix& m = getEdgeCosts(*edgeItr); os << "\n" << n1 << " " << n2 << "\n" << m.getRows() << " " << m.getCols() << "\n"; assert(m.getRows() != 0 && "No rows in matrix."); @@ -396,14 +431,14 @@ namespace PBQP { /// @param os Output stream to print on. template <typename OStream> void printDot(OStream &os) { - + os << "graph {\n"; for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); nodeItr != nodeEnd; ++nodeItr) { os << " node" << nodeItr << " [ label=\"" - << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n"; + << nodeItr << ": " << getNodeCosts(*nodeItr) << "\" ]\n"; } os << " edge [ len=" << getNumNodes() << " ]\n"; @@ -411,11 +446,11 @@ namespace PBQP { for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); edgeItr != edgeEnd; ++edgeItr) { - os << " node" << getEdgeNode1(edgeItr) - << " -- node" << getEdgeNode2(edgeItr) + os << " node" << getEdgeNode1(*edgeItr) + << " -- node" << getEdgeNode2(*edgeItr) << " [ label=\""; - const Matrix &edgeCosts = getEdgeCosts(edgeItr); + const Matrix &edgeCosts = getEdgeCosts(*edgeItr); for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { os << edgeCosts.getRowAsVector(i) << "\\n"; @@ -427,39 +462,16 @@ namespace PBQP { }; - class NodeItrComparator { - public: - bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const { - return &*n1 < &*n2; - } - - bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const { - return &*n1 < &*n2; - } - }; - - class EdgeItrCompartor { - public: - bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const { - return &*e1 < &*e2; - } - - bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const { - return &*e1 < &*e2; - } - }; - - void Graph::copyFrom(const Graph &other) { - std::map<Graph::ConstNodeItr, Graph::NodeItr, - NodeItrComparator> nodeMap; +// void Graph::copyFrom(const Graph &other) { +// std::map<Graph::ConstNodeItr, Graph::NodeItr, +// NodeItrComparator> nodeMap; - for (Graph::ConstNodeItr nItr = other.nodesBegin(), - nEnd = other.nodesEnd(); - nItr != nEnd; ++nItr) { - nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); - } - - } +// for (Graph::ConstNodeItr nItr = other.nodesBegin(), +// nEnd = other.nodesEnd(); +// nItr != nEnd; ++nItr) { +// nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); +// } +// } } diff --git a/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h index 0c1fcb7eaf78d..8bcbb9ed1d6b5 100644 --- a/include/llvm/CodeGen/PBQP/HeuristicBase.h +++ b/include/llvm/CodeGen/PBQP/HeuristicBase.h @@ -27,7 +27,7 @@ namespace PBQP { /// <li> void heuristicReduce() : Perform a single heuristic reduction. /// <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent) /// change to the cost matrix on the given edge (by R2). - /// <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new + /// <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new /// costs on the given edge. /// <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new /// edge into the PBQP graph (by R2). @@ -39,7 +39,7 @@ namespace PBQP { /// /// These methods are implemented in this class for documentation purposes, /// but will assert if called. - /// + /// /// Note that this class uses the curiously recursive template idiom to /// forward calls to the derived class. These methods need not be made /// virtual, and indeed probably shouldn't for performance reasons. @@ -52,7 +52,7 @@ namespace PBQP { class HeuristicBase { private: - typedef std::list<Graph::NodeItr> OptimalList; + typedef std::list<Graph::NodeId> OptimalList; HeuristicSolverImpl<HImpl> &s; Graph &g; @@ -62,9 +62,9 @@ namespace PBQP { HImpl& impl() { return static_cast<HImpl&>(*this); } // Add the given node to the optimal reductions list. Keep an iterator to - // its location for fast removal. - void addToOptimalReductionList(Graph::NodeItr nItr) { - optimalList.insert(optimalList.end(), nItr); + // its location for fast removal. + void addToOptimalReductionList(Graph::NodeId nId) { + optimalList.insert(optimalList.end(), nId); } public: @@ -94,7 +94,7 @@ namespace PBQP { /// behaviour. bool solverRunSimplify() const { return true; } - /// \brief Decide whether a node should be optimally or heuristically + /// \brief Decide whether a node should be optimally or heuristically /// reduced. /// @return Whether or not the given node should be listed for optimal /// reduction (via R0, R1 or R2). @@ -105,21 +105,21 @@ namespace PBQP { /// criteria. Note however that your criteria for selecting optimal nodes /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or /// higher should not be selected under any circumstances. - bool shouldOptimallyReduce(Graph::NodeItr nItr) { - if (g.getNodeDegree(nItr) < 3) + bool shouldOptimallyReduce(Graph::NodeId nId) { + if (g.getNodeDegree(nId) < 3) return true; // else return false; } /// \brief Add the given node to the list of nodes to be optimally reduced. - /// @param nItr Node iterator to be added. + /// @param nId Node id to be added. /// /// You probably don't want to over-ride this, except perhaps to record /// statistics before calling this implementation. HeuristicBase relies on /// its behaviour. - void addToOptimalReduceList(Graph::NodeItr nItr) { - optimalList.push_back(nItr); + void addToOptimalReduceList(Graph::NodeId nId) { + optimalList.push_back(nId); } /// \brief Initialise the heuristic. @@ -132,10 +132,10 @@ namespace PBQP { void setup() { for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); nItr != nEnd; ++nItr) { - if (impl().shouldOptimallyReduce(nItr)) { - addToOptimalReduceList(nItr); + if (impl().shouldOptimallyReduce(*nItr)) { + addToOptimalReduceList(*nItr); } else { - impl().addToHeuristicReduceList(nItr); + impl().addToHeuristicReduceList(*nItr); } } } @@ -150,13 +150,13 @@ namespace PBQP { if (optimalList.empty()) return false; - Graph::NodeItr nItr = optimalList.front(); + Graph::NodeId nId = optimalList.front(); optimalList.pop_front(); - switch (s.getSolverDegree(nItr)) { - case 0: s.applyR0(nItr); break; - case 1: s.applyR1(nItr); break; - case 2: s.applyR2(nItr); break; + switch (s.getSolverDegree(nId)) { + case 0: s.applyR0(nId); break; + case 1: s.applyR1(nId); break; + case 2: s.applyR2(nId); break; default: llvm_unreachable( "Optimal reductions of degree > 2 nodes is invalid."); } @@ -184,8 +184,8 @@ namespace PBQP { } /// \brief Add a node to the heuristic reduce list. - /// @param nItr Node iterator to add to the heuristic reduce list. - void addToHeuristicList(Graph::NodeItr nItr) { + /// @param nId Node id to add to the heuristic reduce list. + void addToHeuristicList(Graph::NodeId nId) { llvm_unreachable("Must be implemented in derived class."); } @@ -199,31 +199,31 @@ namespace PBQP { } /// \brief Prepare a change in the costs on the given edge. - /// @param eItr Edge iterator. - void preUpdateEdgeCosts(Graph::EdgeItr eItr) { + /// @param eId Edge id. + void preUpdateEdgeCosts(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle the change in the costs on the given edge. - /// @param eItr Edge iterator. - void postUpdateEdgeCostts(Graph::EdgeItr eItr) { + /// @param eId Edge id. + void postUpdateEdgeCostts(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle the addition of a new edge into the PBQP graph. - /// @param eItr Edge iterator for the added edge. - void handleAddEdge(Graph::EdgeItr eItr) { + /// @param eId Edge id for the added edge. + void handleAddEdge(Graph::EdgeId eId) { llvm_unreachable("Must be implemented in derived class."); } /// \brief Handle disconnection of an edge from a node. - /// @param eItr Edge iterator for edge being disconnected. - /// @param nItr Node iterator for the node being disconnected from. + /// @param eId Edge id for edge being disconnected. + /// @param nId Node id for the node being disconnected from. /// /// Edges are frequently removed due to the removal of a node. This /// method allows for the effect to be computed only for the remaining /// node in the graph. - void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) { + void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) { llvm_unreachable("Must be implemented in derived class."); } diff --git a/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h index 47e15b27e7444..e26ca02fff7ee 100644 --- a/include/llvm/CodeGen/PBQP/HeuristicSolver.h +++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h @@ -9,7 +9,7 @@ // // Heuristic PBQP solver. This solver is able to perform optimal reductions for // nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is -// used to select a node for reduction. +// used to select a node for reduction. // //===----------------------------------------------------------------------===// @@ -40,10 +40,10 @@ namespace PBQP { typedef typename HImpl::NodeData HeuristicNodeData; typedef typename HImpl::EdgeData HeuristicEdgeData; - typedef std::list<Graph::EdgeItr> SolverEdges; + typedef std::list<Graph::EdgeId> SolverEdges; public: - + /// \brief Iterator type for edges in the solver graph. typedef SolverEdges::iterator SolverEdgeItr; @@ -55,9 +55,9 @@ namespace PBQP { HeuristicNodeData& getHeuristicData() { return hData; } - SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) { + SolverEdgeItr addSolverEdge(Graph::EdgeId eId) { ++solverDegree; - return solverEdges.insert(solverEdges.end(), eItr); + return solverEdges.insert(solverEdges.end(), eId); } void removeSolverEdge(SolverEdgeItr seItr) { @@ -70,15 +70,15 @@ namespace PBQP { unsigned getSolverDegree() const { return solverDegree; } void clearSolverEdges() { solverDegree = 0; - solverEdges.clear(); + solverEdges.clear(); } - + private: HeuristicNodeData hData; unsigned solverDegree; SolverEdges solverEdges; }; - + class EdgeData { public: HeuristicEdgeData& getHeuristicData() { return hData; } @@ -104,7 +104,7 @@ namespace PBQP { Graph &g; HImpl h; Solution s; - std::vector<Graph::NodeItr> stack; + std::vector<Graph::NodeId> stack; typedef std::list<NodeData> NodeDataList; NodeDataList nodeDataList; @@ -117,7 +117,7 @@ namespace PBQP { /// \brief Construct a heuristic solver implementation to solve the given /// graph. /// @param g The graph representing the problem instance to be solved. - HeuristicSolverImpl(Graph &g) : g(g), h(*this) {} + HeuristicSolverImpl(Graph &g) : g(g), h(*this) {} /// \brief Get the graph being solved by this solver. /// @return The graph representing the problem instance being solved by this @@ -125,46 +125,46 @@ namespace PBQP { Graph& getGraph() { return g; } /// \brief Get the heuristic data attached to the given node. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return The heuristic data attached to the given node. - HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).getHeuristicData(); + HeuristicNodeData& getHeuristicNodeData(Graph::NodeId nId) { + return getSolverNodeData(nId).getHeuristicData(); } /// \brief Get the heuristic data attached to the given edge. - /// @param eItr Edge iterator. + /// @param eId Edge id. /// @return The heuristic data attached to the given node. - HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { - return getSolverEdgeData(eItr).getHeuristicData(); + HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeId eId) { + return getSolverEdgeData(eId).getHeuristicData(); } /// \brief Begin iterator for the set of edges adjacent to the given node in /// the solver graph. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return Begin iterator for the set of edges adjacent to the given node - /// in the solver graph. - SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).solverEdgesBegin(); + /// in the solver graph. + SolverEdgeItr solverEdgesBegin(Graph::NodeId nId) { + return getSolverNodeData(nId).solverEdgesBegin(); } /// \brief End iterator for the set of edges adjacent to the given node in /// the solver graph. - /// @param nItr Node iterator. + /// @param nId Node id. /// @return End iterator for the set of edges adjacent to the given node in - /// the solver graph. - SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).solverEdgesEnd(); + /// the solver graph. + SolverEdgeItr solverEdgesEnd(Graph::NodeId nId) { + return getSolverNodeData(nId).solverEdgesEnd(); } /// \brief Remove a node from the solver graph. - /// @param eItr Edge iterator for edge to be removed. + /// @param eId Edge id for edge to be removed. /// /// Does <i>not</i> notify the heuristic of the removal. That should be /// done manually if necessary. - void removeSolverEdge(Graph::EdgeItr eItr) { - EdgeData &eData = getSolverEdgeData(eItr); - NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), - &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); + void removeSolverEdge(Graph::EdgeId eId) { + EdgeData &eData = getSolverEdgeData(eId); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eId)); n1Data.removeSolverEdge(eData.getN1SolverEdgeItr()); n2Data.removeSolverEdge(eData.getN2SolverEdgeItr()); @@ -188,66 +188,66 @@ namespace PBQP { } /// \brief Add to the end of the stack. - /// @param nItr Node iterator to add to the reduction stack. - void pushToStack(Graph::NodeItr nItr) { - getSolverNodeData(nItr).clearSolverEdges(); - stack.push_back(nItr); + /// @param nId Node id to add to the reduction stack. + void pushToStack(Graph::NodeId nId) { + getSolverNodeData(nId).clearSolverEdges(); + stack.push_back(nId); } /// \brief Returns the solver degree of the given node. - /// @param nItr Node iterator for which degree is requested. + /// @param nId Node id for which degree is requested. /// @return Node degree in the <i>solver</i> graph (not the original graph). - unsigned getSolverDegree(Graph::NodeItr nItr) { - return getSolverNodeData(nItr).getSolverDegree(); + unsigned getSolverDegree(Graph::NodeId nId) { + return getSolverNodeData(nId).getSolverDegree(); } /// \brief Set the solution of the given node. - /// @param nItr Node iterator to set solution for. + /// @param nId Node id to set solution for. /// @param selection Selection for node. - void setSolution(const Graph::NodeItr &nItr, unsigned selection) { - s.setSelection(nItr, selection); + void setSolution(const Graph::NodeId &nId, unsigned selection) { + s.setSelection(nId, selection); - for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), - aeEnd = g.adjEdgesEnd(nItr); + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId), + aeEnd = g.adjEdgesEnd(nId); aeItr != aeEnd; ++aeItr) { - Graph::EdgeItr eItr(*aeItr); - Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr)); - getSolverNodeData(anItr).addSolverEdge(eItr); + Graph::EdgeId eId(*aeItr); + Graph::NodeId anId(g.getEdgeOtherNode(eId, nId)); + getSolverNodeData(anId).addSolverEdge(eId); } } /// \brief Apply rule R0. - /// @param nItr Node iterator for node to apply R0 to. + /// @param nId Node id for node to apply R0 to. /// /// Node will be automatically pushed to the solver stack. - void applyR0(Graph::NodeItr nItr) { - assert(getSolverNodeData(nItr).getSolverDegree() == 0 && + void applyR0(Graph::NodeId nId) { + assert(getSolverNodeData(nId).getSolverDegree() == 0 && "R0 applied to node with degree != 0."); // Nothing to do. Just push the node onto the reduction stack. - pushToStack(nItr); + pushToStack(nId); s.recordR0(); } /// \brief Apply rule R1. - /// @param xnItr Node iterator for node to apply R1 to. + /// @param xnId Node id for node to apply R1 to. /// /// Node will be automatically pushed to the solver stack. - void applyR1(Graph::NodeItr xnItr) { - NodeData &nd = getSolverNodeData(xnItr); + void applyR1(Graph::NodeId xnId) { + NodeData &nd = getSolverNodeData(xnId); assert(nd.getSolverDegree() == 1 && "R1 applied to node with degree != 1."); - Graph::EdgeItr eItr = *nd.solverEdgesBegin(); + Graph::EdgeId eId = *nd.solverEdgesBegin(); + + const Matrix &eCosts = g.getEdgeCosts(eId); + const Vector &xCosts = g.getNodeCosts(xnId); - const Matrix &eCosts = g.getEdgeCosts(eItr); - const Vector &xCosts = g.getNodeCosts(xnItr); - // Duplicate a little to avoid transposing matrices. - if (xnItr == g.getEdgeNode1(eItr)) { - Graph::NodeItr ynItr = g.getEdgeNode2(eItr); - Vector &yCosts = g.getNodeCosts(ynItr); + if (xnId == g.getEdgeNode1(eId)) { + Graph::NodeId ynId = g.getEdgeNode2(eId); + Vector &yCosts = g.getNodeCosts(ynId); for (unsigned j = 0; j < yCosts.getLength(); ++j) { PBQPNum min = eCosts[0][j] + xCosts[0]; for (unsigned i = 1; i < xCosts.getLength(); ++i) { @@ -257,10 +257,10 @@ namespace PBQP { } yCosts[j] += min; } - h.handleRemoveEdge(eItr, ynItr); + h.handleRemoveEdge(eId, ynId); } else { - Graph::NodeItr ynItr = g.getEdgeNode1(eItr); - Vector &yCosts = g.getNodeCosts(ynItr); + Graph::NodeId ynId = g.getEdgeNode1(eId); + Vector &yCosts = g.getNodeCosts(ynId); for (unsigned i = 0; i < yCosts.getLength(); ++i) { PBQPNum min = eCosts[i][0] + xCosts[0]; for (unsigned j = 1; j < xCosts.getLength(); ++j) { @@ -270,48 +270,48 @@ namespace PBQP { } yCosts[i] += min; } - h.handleRemoveEdge(eItr, ynItr); + h.handleRemoveEdge(eId, ynId); } - removeSolverEdge(eItr); + removeSolverEdge(eId); assert(nd.getSolverDegree() == 0 && "Degree 1 with edge removed should be 0."); - pushToStack(xnItr); + pushToStack(xnId); s.recordR1(); } /// \brief Apply rule R2. - /// @param xnItr Node iterator for node to apply R2 to. + /// @param xnId Node id for node to apply R2 to. /// /// Node will be automatically pushed to the solver stack. - void applyR2(Graph::NodeItr xnItr) { - assert(getSolverNodeData(xnItr).getSolverDegree() == 2 && + void applyR2(Graph::NodeId xnId) { + assert(getSolverNodeData(xnId).getSolverDegree() == 2 && "R2 applied to node with degree != 2."); - NodeData &nd = getSolverNodeData(xnItr); - const Vector &xCosts = g.getNodeCosts(xnItr); + NodeData &nd = getSolverNodeData(xnId); + const Vector &xCosts = g.getNodeCosts(xnId); SolverEdgeItr aeItr = nd.solverEdgesBegin(); - Graph::EdgeItr yxeItr = *aeItr, - zxeItr = *(++aeItr); + Graph::EdgeId yxeId = *aeItr, + zxeId = *(++aeItr); - Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr), - znItr = g.getEdgeOtherNode(zxeItr, xnItr); + Graph::NodeId ynId = g.getEdgeOtherNode(yxeId, xnId), + znId = g.getEdgeOtherNode(zxeId, xnId); - bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr), - flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr); + bool flipEdge1 = (g.getEdgeNode1(yxeId) == xnId), + flipEdge2 = (g.getEdgeNode1(zxeId) == xnId); const Matrix *yxeCosts = flipEdge1 ? - new Matrix(g.getEdgeCosts(yxeItr).transpose()) : - &g.getEdgeCosts(yxeItr); + new Matrix(g.getEdgeCosts(yxeId).transpose()) : + &g.getEdgeCosts(yxeId); const Matrix *zxeCosts = flipEdge2 ? - new Matrix(g.getEdgeCosts(zxeItr).transpose()) : - &g.getEdgeCosts(zxeItr); + new Matrix(g.getEdgeCosts(zxeId).transpose()) : + &g.getEdgeCosts(zxeId); unsigned xLen = xCosts.getLength(), yLen = yxeCosts->getRows(), zLen = zxeCosts->getRows(); - + Matrix delta(yLen, zLen); for (unsigned i = 0; i < yLen; ++i) { @@ -333,79 +333,79 @@ namespace PBQP { if (flipEdge2) delete zxeCosts; - Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr); + Graph::EdgeId yzeId = g.findEdge(ynId, znId); bool addedEdge = false; - if (yzeItr == g.edgesEnd()) { - yzeItr = g.addEdge(ynItr, znItr, delta); + if (yzeId == g.invalidEdgeId()) { + yzeId = g.addEdge(ynId, znId, delta); addedEdge = true; } else { - Matrix &yzeCosts = g.getEdgeCosts(yzeItr); - h.preUpdateEdgeCosts(yzeItr); - if (ynItr == g.getEdgeNode1(yzeItr)) { + Matrix &yzeCosts = g.getEdgeCosts(yzeId); + h.preUpdateEdgeCosts(yzeId); + if (ynId == g.getEdgeNode1(yzeId)) { yzeCosts += delta; } else { yzeCosts += delta.transpose(); } } - bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr); + bool nullCostEdge = tryNormaliseEdgeMatrix(yzeId); if (!addedEdge) { // If we modified the edge costs let the heuristic know. - h.postUpdateEdgeCosts(yzeItr); + h.postUpdateEdgeCosts(yzeId); } - + if (nullCostEdge) { // If this edge ended up null remove it. if (!addedEdge) { // We didn't just add it, so we need to notify the heuristic // and remove it from the solver. - h.handleRemoveEdge(yzeItr, ynItr); - h.handleRemoveEdge(yzeItr, znItr); - removeSolverEdge(yzeItr); + h.handleRemoveEdge(yzeId, ynId); + h.handleRemoveEdge(yzeId, znId); + removeSolverEdge(yzeId); } - g.removeEdge(yzeItr); + g.removeEdge(yzeId); } else if (addedEdge) { // If the edge was added, and non-null, finish setting it up, add it to // the solver & notify heuristic. edgeDataList.push_back(EdgeData()); - g.setEdgeData(yzeItr, &edgeDataList.back()); - addSolverEdge(yzeItr); - h.handleAddEdge(yzeItr); + g.setEdgeData(yzeId, &edgeDataList.back()); + addSolverEdge(yzeId); + h.handleAddEdge(yzeId); } - h.handleRemoveEdge(yxeItr, ynItr); - removeSolverEdge(yxeItr); - h.handleRemoveEdge(zxeItr, znItr); - removeSolverEdge(zxeItr); + h.handleRemoveEdge(yxeId, ynId); + removeSolverEdge(yxeId); + h.handleRemoveEdge(zxeId, znId); + removeSolverEdge(zxeId); - pushToStack(xnItr); + pushToStack(xnId); s.recordR2(); } /// \brief Record an application of the RN rule. /// /// For use by the HeuristicBase. - void recordRN() { s.recordRN(); } + void recordRN() { s.recordRN(); } private: - NodeData& getSolverNodeData(Graph::NodeItr nItr) { - return *static_cast<NodeData*>(g.getNodeData(nItr)); + NodeData& getSolverNodeData(Graph::NodeId nId) { + return *static_cast<NodeData*>(g.getNodeData(nId)); } - EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) { - return *static_cast<EdgeData*>(g.getEdgeData(eItr)); + EdgeData& getSolverEdgeData(Graph::EdgeId eId) { + return *static_cast<EdgeData*>(g.getEdgeData(eId)); } - void addSolverEdge(Graph::EdgeItr eItr) { - EdgeData &eData = getSolverEdgeData(eItr); - NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), - &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); + void addSolverEdge(Graph::EdgeId eId) { + EdgeData &eData = getSolverEdgeData(eId); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eId)); - eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr)); - eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr)); + eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eId)); + eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eId)); } void setup() { @@ -417,15 +417,15 @@ namespace PBQP { for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); nItr != nEnd; ++nItr) { nodeDataList.push_back(NodeData()); - g.setNodeData(nItr, &nodeDataList.back()); + g.setNodeData(*nItr, &nodeDataList.back()); } // Create edge data objects. for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); eItr != eEnd; ++eItr) { edgeDataList.push_back(EdgeData()); - g.setEdgeData(eItr, &edgeDataList.back()); - addSolverEdge(eItr); + g.setEdgeData(*eItr, &edgeDataList.back()); + addSolverEdge(*eItr); } } @@ -441,28 +441,30 @@ namespace PBQP { for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); nItr != nEnd; ++nItr) { - if (g.getNodeCosts(nItr).getLength() == 1) { + Graph::NodeId nId = *nItr; + + if (g.getNodeCosts(nId).getLength() == 1) { - std::vector<Graph::EdgeItr> edgesToRemove; + std::vector<Graph::EdgeId> edgesToRemove; - for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), - aeEnd = g.adjEdgesEnd(nItr); + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId), + aeEnd = g.adjEdgesEnd(nId); aeItr != aeEnd; ++aeItr) { - Graph::EdgeItr eItr = *aeItr; + Graph::EdgeId eId = *aeItr; - if (g.getEdgeNode1(eItr) == nItr) { - Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr); - g.getNodeCosts(otherNodeItr) += - g.getEdgeCosts(eItr).getRowAsVector(0); + if (g.getEdgeNode1(eId) == nId) { + Graph::NodeId otherNodeId = g.getEdgeNode2(eId); + g.getNodeCosts(otherNodeId) += + g.getEdgeCosts(eId).getRowAsVector(0); } else { - Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr); - g.getNodeCosts(otherNodeItr) += - g.getEdgeCosts(eItr).getColAsVector(0); + Graph::NodeId otherNodeId = g.getEdgeNode1(eId); + g.getNodeCosts(otherNodeId) += + g.getEdgeCosts(eId).getColAsVector(0); } - edgesToRemove.push_back(eItr); + edgesToRemove.push_back(eId); } if (!edgesToRemove.empty()) @@ -477,12 +479,12 @@ namespace PBQP { } void eliminateIndependentEdges() { - std::vector<Graph::EdgeItr> edgesToProcess; + std::vector<Graph::EdgeId> edgesToProcess; unsigned numEliminated = 0; for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); eItr != eEnd; ++eItr) { - edgesToProcess.push_back(eItr); + edgesToProcess.push_back(*eItr); } while (!edgesToProcess.empty()) { @@ -492,21 +494,21 @@ namespace PBQP { } } - bool tryToEliminateEdge(Graph::EdgeItr eItr) { - if (tryNormaliseEdgeMatrix(eItr)) { - g.removeEdge(eItr); - return true; + bool tryToEliminateEdge(Graph::EdgeId eId) { + if (tryNormaliseEdgeMatrix(eId)) { + g.removeEdge(eId); + return true; } return false; } - bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) { + bool tryNormaliseEdgeMatrix(Graph::EdgeId &eId) { const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity(); - Matrix &edgeCosts = g.getEdgeCosts(eItr); - Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)), - &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr)); + Matrix &edgeCosts = g.getEdgeCosts(eId); + Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eId)), + &vCosts = g.getNodeCosts(g.getEdgeNode2(eId)); for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { PBQPNum rowMin = infinity; @@ -554,34 +556,34 @@ namespace PBQP { } } - void computeSolution(Graph::NodeItr nItr) { + void computeSolution(Graph::NodeId nId) { - NodeData &nodeData = getSolverNodeData(nItr); + NodeData &nodeData = getSolverNodeData(nId); - Vector v(g.getNodeCosts(nItr)); + Vector v(g.getNodeCosts(nId)); // Solve based on existing solved edges. for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(), solvedEdgeEnd = nodeData.solverEdgesEnd(); solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) { - Graph::EdgeItr eItr(*solvedEdgeItr); - Matrix &edgeCosts = g.getEdgeCosts(eItr); + Graph::EdgeId eId(*solvedEdgeItr); + Matrix &edgeCosts = g.getEdgeCosts(eId); - if (nItr == g.getEdgeNode1(eItr)) { - Graph::NodeItr adjNode(g.getEdgeNode2(eItr)); + if (nId == g.getEdgeNode1(eId)) { + Graph::NodeId adjNode(g.getEdgeNode2(eId)); unsigned adjSolution = s.getSelection(adjNode); v += edgeCosts.getColAsVector(adjSolution); } else { - Graph::NodeItr adjNode(g.getEdgeNode1(eItr)); + Graph::NodeId adjNode(g.getEdgeNode1(eId)); unsigned adjSolution = s.getSelection(adjNode); v += edgeCosts.getRowAsVector(adjSolution); } } - setSolution(nItr, v.minIndex()); + setSolution(nId, v.minIndex()); } void cleanup() { diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h index 307d81e1d161c..c355c2c2f81a0 100644 --- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h +++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h @@ -27,7 +27,7 @@ namespace PBQP { /// \brief PBQP Heuristic which applies an allocability test based on /// Briggs. - /// + /// /// This heuristic assumes that the elements of cost vectors in the PBQP /// problem represent storage options, with the first being the spill /// option and subsequent elements representing legal registers for the @@ -39,16 +39,16 @@ namespace PBQP { /// solver stack. If no nodes can be proven allocable then the node with /// the lowest estimated spill cost is selected and push to the solver stack /// instead. - /// - /// This implementation is built on top of HeuristicBase. + /// + /// This implementation is built on top of HeuristicBase. class Briggs : public HeuristicBase<Briggs> { private: class LinkDegreeComparator { public: LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {} - bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { - if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr)) + bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const { + if (s->getSolverDegree(n1Id) > s->getSolverDegree(n2Id)) return true; return false; } @@ -60,12 +60,12 @@ namespace PBQP { public: SpillCostComparator(HeuristicSolverImpl<Briggs> &s) : s(&s), g(&s.getGraph()) {} - bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const { - const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr); - const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr); + bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const { + const PBQP::Vector &cv1 = g->getNodeCosts(n1Id); + const PBQP::Vector &cv2 = g->getNodeCosts(n2Id); - PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr); - PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr); + PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Id); + PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Id); if (cost1 < cost2) return true; @@ -77,10 +77,10 @@ namespace PBQP { Graph *g; }; - typedef std::list<Graph::NodeItr> RNAllocableList; + typedef std::list<Graph::NodeId> RNAllocableList; typedef RNAllocableList::iterator RNAllocableListItr; - typedef std::list<Graph::NodeItr> RNUnallocableList; + typedef std::list<Graph::NodeId> RNUnallocableList; typedef RNUnallocableList::iterator RNUnallocableListItr; public: @@ -114,7 +114,7 @@ namespace PBQP { /// \brief Determine whether a node should be reduced using optimal /// reduction. - /// @param nItr Node iterator to be considered. + /// @param nId Node id to be considered. /// @return True if the given node should be optimally reduced, false /// otherwise. /// @@ -123,8 +123,8 @@ namespace PBQP { /// infinite are checked for allocability first. Allocable nodes may be /// optimally reduced, but nodes whose allocability cannot be proven are /// selected for heuristic reduction instead. - bool shouldOptimallyReduce(Graph::NodeItr nItr) { - if (getSolver().getSolverDegree(nItr) < 3) { + bool shouldOptimallyReduce(Graph::NodeId nId) { + if (getSolver().getSolverDegree(nId) < 3) { return true; } // else @@ -132,15 +132,15 @@ namespace PBQP { } /// \brief Add a node to the heuristic reduce list. - /// @param nItr Node iterator to add to the heuristic reduce list. - void addToHeuristicReduceList(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); - initializeNode(nItr); + /// @param nId Node id to add to the heuristic reduce list. + void addToHeuristicReduceList(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); + initializeNode(nId); nd.isHeuristic = true; if (nd.isAllocable) { - nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); + nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId); } else { - nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr); + nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nId); } } @@ -159,19 +159,19 @@ namespace PBQP { RNAllocableListItr rnaItr = min_element(rnAllocableList.begin(), rnAllocableList.end(), LinkDegreeComparator(getSolver())); - Graph::NodeItr nItr = *rnaItr; + Graph::NodeId nId = *rnaItr; rnAllocableList.erase(rnaItr); - handleRemoveNode(nItr); - getSolver().pushToStack(nItr); + handleRemoveNode(nId); + getSolver().pushToStack(nId); return true; } else if (!rnUnallocableList.empty()) { RNUnallocableListItr rnuItr = min_element(rnUnallocableList.begin(), rnUnallocableList.end(), SpillCostComparator(getSolver())); - Graph::NodeItr nItr = *rnuItr; + Graph::NodeId nId = *rnuItr; rnUnallocableList.erase(rnuItr); - handleRemoveNode(nItr); - getSolver().pushToStack(nItr); + handleRemoveNode(nId); + getSolver().pushToStack(nId); return true; } // else @@ -179,43 +179,43 @@ namespace PBQP { } /// \brief Prepare a change in the costs on the given edge. - /// @param eItr Edge iterator. - void preUpdateEdgeCosts(Graph::EdgeItr eItr) { + /// @param eId Edge id. + void preUpdateEdgeCosts(Graph::EdgeId eId) { Graph &g = getGraph(); - Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), - n2Itr = g.getEdgeNode2(eItr); - NodeData &n1 = getHeuristicNodeData(n1Itr), - &n2 = getHeuristicNodeData(n2Itr); + Graph::NodeId n1Id = g.getEdgeNode1(eId), + n2Id = g.getEdgeNode2(eId); + NodeData &n1 = getHeuristicNodeData(n1Id), + &n2 = getHeuristicNodeData(n2Id); if (n1.isHeuristic) - subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr)); + subtractEdgeContributions(eId, getGraph().getEdgeNode1(eId)); if (n2.isHeuristic) - subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr)); + subtractEdgeContributions(eId, getGraph().getEdgeNode2(eId)); - EdgeData &ed = getHeuristicEdgeData(eItr); + EdgeData &ed = getHeuristicEdgeData(eId); ed.isUpToDate = false; } /// \brief Handle the change in the costs on the given edge. - /// @param eItr Edge iterator. - void postUpdateEdgeCosts(Graph::EdgeItr eItr) { + /// @param eId Edge id. + void postUpdateEdgeCosts(Graph::EdgeId eId) { // This is effectively the same as adding a new edge now, since // we've factored out the costs of the old one. - handleAddEdge(eItr); + handleAddEdge(eId); } /// \brief Handle the addition of a new edge into the PBQP graph. - /// @param eItr Edge iterator for the added edge. + /// @param eId Edge id for the added edge. /// /// Updates allocability of any nodes connected by this edge which are /// being managed by the heuristic. If allocability changes they are /// moved to the appropriate list. - void handleAddEdge(Graph::EdgeItr eItr) { + void handleAddEdge(Graph::EdgeId eId) { Graph &g = getGraph(); - Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), - n2Itr = g.getEdgeNode2(eItr); - NodeData &n1 = getHeuristicNodeData(n1Itr), - &n2 = getHeuristicNodeData(n2Itr); + Graph::NodeId n1Id = g.getEdgeNode1(eId), + n2Id = g.getEdgeNode2(eId); + NodeData &n1 = getHeuristicNodeData(n1Id), + &n2 = getHeuristicNodeData(n2Id); // If neither node is managed by the heuristic there's nothing to be // done. @@ -223,60 +223,60 @@ namespace PBQP { return; // Ok - we need to update at least one node. - computeEdgeContributions(eItr); + computeEdgeContributions(eId); // Update node 1 if it's managed by the heuristic. if (n1.isHeuristic) { bool n1WasAllocable = n1.isAllocable; - addEdgeContributions(eItr, n1Itr); - updateAllocability(n1Itr); + addEdgeContributions(eId, n1Id); + updateAllocability(n1Id); if (n1WasAllocable && !n1.isAllocable) { rnAllocableList.erase(n1.rnaItr); n1.rnuItr = - rnUnallocableList.insert(rnUnallocableList.end(), n1Itr); + rnUnallocableList.insert(rnUnallocableList.end(), n1Id); } } // Likewise for node 2. if (n2.isHeuristic) { bool n2WasAllocable = n2.isAllocable; - addEdgeContributions(eItr, n2Itr); - updateAllocability(n2Itr); + addEdgeContributions(eId, n2Id); + updateAllocability(n2Id); if (n2WasAllocable && !n2.isAllocable) { rnAllocableList.erase(n2.rnaItr); n2.rnuItr = - rnUnallocableList.insert(rnUnallocableList.end(), n2Itr); + rnUnallocableList.insert(rnUnallocableList.end(), n2Id); } } } /// \brief Handle disconnection of an edge from a node. - /// @param eItr Edge iterator for edge being disconnected. - /// @param nItr Node iterator for the node being disconnected from. + /// @param eId Edge id for edge being disconnected. + /// @param nId Node id for the node being disconnected from. /// /// Updates allocability of the given node and, if appropriate, moves the /// node to a new list. - void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); + void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) { + NodeData &nd =getHeuristicNodeData(nId); // If the node is not managed by the heuristic there's nothing to be // done. if (!nd.isHeuristic) return; - EdgeData &ed = getHeuristicEdgeData(eItr); + EdgeData &ed = getHeuristicEdgeData(eId); (void)ed; assert(ed.isUpToDate && "Edge data is not up to date."); // Update node. bool ndWasAllocable = nd.isAllocable; - subtractEdgeContributions(eItr, nItr); - updateAllocability(nItr); + subtractEdgeContributions(eId, nId); + updateAllocability(nId); // If the node has gone optimal... - if (shouldOptimallyReduce(nItr)) { + if (shouldOptimallyReduce(nId)) { nd.isHeuristic = false; - addToOptimalReduceList(nItr); + addToOptimalReduceList(nId); if (ndWasAllocable) { rnAllocableList.erase(nd.rnaItr); } else { @@ -287,36 +287,36 @@ namespace PBQP { // from "unallocable" to "allocable". if (!ndWasAllocable && nd.isAllocable) { rnUnallocableList.erase(nd.rnuItr); - nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); + nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId); } } } private: - NodeData& getHeuristicNodeData(Graph::NodeItr nItr) { - return getSolver().getHeuristicNodeData(nItr); + NodeData& getHeuristicNodeData(Graph::NodeId nId) { + return getSolver().getHeuristicNodeData(nId); } - EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { - return getSolver().getHeuristicEdgeData(eItr); + EdgeData& getHeuristicEdgeData(Graph::EdgeId eId) { + return getSolver().getHeuristicEdgeData(eId); } // Work out what this edge will contribute to the allocability of the // nodes connected to it. - void computeEdgeContributions(Graph::EdgeItr eItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); + void computeEdgeContributions(Graph::EdgeId eId) { + EdgeData &ed = getHeuristicEdgeData(eId); if (ed.isUpToDate) return; // Edge data is already up to date. - Matrix &eCosts = getGraph().getEdgeCosts(eItr); + Matrix &eCosts = getGraph().getEdgeCosts(eId); unsigned numRegs = eCosts.getRows() - 1, numReverseRegs = eCosts.getCols() - 1; std::vector<unsigned> rowInfCounts(numRegs, 0), - colInfCounts(numReverseRegs, 0); + colInfCounts(numReverseRegs, 0); ed.worst = 0; ed.reverseWorst = 0; @@ -348,19 +348,19 @@ namespace PBQP { ed.isUpToDate = true; } - // Add the contributions of the given edge to the given node's + // Add the contributions of the given edge to the given node's // numDenied and safe members. No action is taken other than to update // these member values. Once updated these numbers can be used by clients // to update the node's allocability. - void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); + void addEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) { + EdgeData &ed = getHeuristicEdgeData(eId); assert(ed.isUpToDate && "Using out-of-date edge numbers."); - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; - - bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; + + bool nIsNode1 = nId == getGraph().getEdgeNode1(eId); EdgeData::UnsafeArray &unsafe = nIsNode1 ? ed.unsafe : ed.reverseUnsafe; nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst; @@ -375,25 +375,25 @@ namespace PBQP { } } - // Subtract the contributions of the given edge to the given node's + // Subtract the contributions of the given edge to the given node's // numDenied and safe members. No action is taken other than to update // these member values. Once updated these numbers can be used by clients // to update the node's allocability. - void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) { - EdgeData &ed = getHeuristicEdgeData(eItr); + void subtractEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) { + EdgeData &ed = getHeuristicEdgeData(eId); assert(ed.isUpToDate && "Using out-of-date edge numbers."); - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; - - bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr); + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; + + bool nIsNode1 = nId == getGraph().getEdgeNode1(eId); EdgeData::UnsafeArray &unsafe = nIsNode1 ? ed.unsafe : ed.reverseUnsafe; nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst; for (unsigned r = 0; r < numRegs; ++r) { - if (unsafe[r]) { + if (unsafe[r]) { if (nd.unsafeDegrees[r] == 1) { ++nd.numSafe; } @@ -402,22 +402,22 @@ namespace PBQP { } } - void updateAllocability(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; + void updateAllocability(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0; } - void initializeNode(Graph::NodeItr nItr) { - NodeData &nd = getHeuristicNodeData(nItr); + void initializeNode(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); if (nd.isInitialized) return; // Node data is already up to date. - unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; nd.numDenied = 0; - const Vector& nCosts = getGraph().getNodeCosts(nItr); + const Vector& nCosts = getGraph().getNodeCosts(nId); for (unsigned i = 1; i < nCosts.getLength(); ++i) { if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity()) ++nd.numDenied; @@ -428,27 +428,27 @@ namespace PBQP { typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; - for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr), - aeEnd = getSolver().solverEdgesEnd(nItr); + for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nId), + aeEnd = getSolver().solverEdgesEnd(nId); aeItr != aeEnd; ++aeItr) { - - Graph::EdgeItr eItr = *aeItr; - computeEdgeContributions(eItr); - addEdgeContributions(eItr, nItr); + + Graph::EdgeId eId = *aeItr; + computeEdgeContributions(eId); + addEdgeContributions(eId, nId); } - updateAllocability(nItr); + updateAllocability(nId); nd.isInitialized = true; } - void handleRemoveNode(Graph::NodeItr xnItr) { + void handleRemoveNode(Graph::NodeId xnId) { typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; - std::vector<Graph::EdgeItr> edgesToRemove; - for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr), - aeEnd = getSolver().solverEdgesEnd(xnItr); + std::vector<Graph::EdgeId> edgesToRemove; + for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnId), + aeEnd = getSolver().solverEdgesEnd(xnId); aeItr != aeEnd; ++aeItr) { - Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr); - handleRemoveEdge(*aeItr, ynItr); + Graph::NodeId ynId = getGraph().getEdgeOtherNode(*aeItr, xnId); + handleRemoveEdge(*aeItr, ynId); edgesToRemove.push_back(*aeItr); } while (!edgesToRemove.empty()) { diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h index b9f288bbeeb48..091805d00f3e2 100644 --- a/include/llvm/CodeGen/PBQP/Solution.h +++ b/include/llvm/CodeGen/PBQP/Solution.h @@ -26,8 +26,7 @@ namespace PBQP { class Solution { private: - typedef std::map<Graph::ConstNodeItr, unsigned, - NodeItrComparator> SelectionsMap; + typedef std::map<Graph::NodeId, unsigned> SelectionsMap; SelectionsMap selections; unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions; @@ -71,17 +70,17 @@ namespace PBQP { unsigned numRNReductions() const { return rNReductions; } /// \brief Set the selection for a given node. - /// @param nItr Node iterator. - /// @param selection Selection for nItr. - void setSelection(Graph::NodeItr nItr, unsigned selection) { - selections[nItr] = selection; + /// @param nodeId Node id. + /// @param selection Selection for nodeId. + void setSelection(Graph::NodeId nodeId, unsigned selection) { + selections[nodeId] = selection; } /// \brief Get a node's selection. - /// @param nItr Node iterator. - /// @return The selection for nItr; - unsigned getSelection(Graph::ConstNodeItr nItr) const { - SelectionsMap::const_iterator sItr = selections.find(nItr); + /// @param nodeId Node id. + /// @return The selection for nodeId; + unsigned getSelection(Graph::NodeId nodeId) const { + SelectionsMap::const_iterator sItr = selections.find(nodeId); assert(sItr != selections.end() && "No selection for node."); return sItr->second; } diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index b02f63e70b9fc..ae4a2fa0bf83e 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -21,19 +21,22 @@ namespace llvm { - class FunctionPass; - class MachineFunctionPass; - class PassInfo; - class PassManagerBase; - class TargetLoweringBase; - class TargetLowering; - class TargetRegisterClass; - class raw_ostream; -} - -namespace llvm { - +class FunctionPass; +class MachineFunctionPass; class PassConfigImpl; +class PassInfo; +class ScheduleDAGInstrs; +class TargetLowering; +class TargetLoweringBase; +class TargetRegisterClass; +class raw_ostream; +struct MachineSchedContext; + +// The old pass manager infrastructure is hidden in a legacy namespace now. +namespace legacy { +class PassManagerBase; +} +using legacy::PassManagerBase; /// Discriminated union of Pass ID types. /// @@ -204,6 +207,20 @@ public: /// Fully developed targets will not generally override this. virtual void addMachinePasses(); + /// createTargetScheduler - Create an instance of ScheduleDAGInstrs to be run + /// within the standard MachineScheduler pass for this function and target at + /// the current optimization level. + /// + /// This can also be used to plug a new MachineSchedStrategy into an instance + /// of the standard ScheduleDAGMI: + /// return new ScheduleDAGMI(C, new MyStrategy(C)) + /// + /// Return NULL to select the default (generic) machine scheduler. + virtual ScheduleDAGInstrs * + createMachineScheduler(MachineSchedContext *C) const { + return 0; + } + protected: // Helper to verify the analysis is really immutable. void setOpt(bool &Opt, bool Val); @@ -308,7 +325,8 @@ protected: AnalysisID addPass(AnalysisID PassID); /// Add a pass to the PassManager if that pass is supposed to be run, as - /// determined by the StartAfter and StopAfter options. + /// determined by the StartAfter and StopAfter options. Takes ownership of the + /// pass. void addPass(Pass *P); /// addMachinePasses helper to create the target-selected or overriden @@ -329,7 +347,7 @@ namespace llvm { /// This pass implements the target transform info analysis using the target /// independent information available to the LLVM code generator. ImmutablePass * - createBasicTargetTransformInfoPass(const TargetLoweringBase *TLI); + createBasicTargetTransformInfoPass(const TargetMachine *TM); /// createUnreachableBlockEliminationPass - The LLVM code generator does not /// work well with unreachable basic blocks (what live ranges make sense for a @@ -364,14 +382,6 @@ namespace llvm { /// these register allocator like this: AU.addRequiredID(PHIEliminationID); extern char &PHIEliminationID; - /// StrongPHIElimination - This pass eliminates machine instruction PHI - /// nodes by inserting copy instructions. This destroys SSA information, but - /// is the desired input for some register allocators. This pass is - /// "required" by these register allocator like this: - /// AU.addRequiredID(PHIEliminationID); - /// This pass is still in development - extern char &StrongPHIEliminationID; - /// LiveIntervals - This analysis keeps track of the live ranges of virtual /// and physical registers. extern char &LiveIntervalsID; @@ -518,7 +528,7 @@ namespace llvm { /// createStackProtectorPass - This pass adds stack protectors to functions. /// - FunctionPass *createStackProtectorPass(const TargetLoweringBase *tli); + FunctionPass *createStackProtectorPass(const TargetMachine *TM); /// createMachineVerifierPass - This pass verifies cenerated machine code /// instructions for correctness. @@ -527,12 +537,12 @@ namespace llvm { /// createDwarfEHPass - This pass mulches exception handling code into a form /// adapted to code generation. Required if using dwarf exception handling. - FunctionPass *createDwarfEHPass(const TargetMachine *tm); + FunctionPass *createDwarfEHPass(const TargetMachine *TM); /// createSjLjEHPreparePass - This pass adapts exception handling code to use /// the GCC-style builtin setjmp/longjmp (sjlj) to handling EH control flow. /// - FunctionPass *createSjLjEHPreparePass(const TargetLoweringBase *tli); + FunctionPass *createSjLjEHPreparePass(const TargetMachine *TM); /// LocalStackSlotAllocation - This pass assigns local frame indices to stack /// slots relative to one another and allocates base registers to access them diff --git a/include/llvm/CodeGen/PseudoSourceValue.h b/include/llvm/CodeGen/PseudoSourceValue.h index df74d08888bb7..705086c22b459 100644 --- a/include/llvm/CodeGen/PseudoSourceValue.h +++ b/include/llvm/CodeGen/PseudoSourceValue.h @@ -44,7 +44,7 @@ namespace llvm { virtual bool isAliased(const MachineFrameInfo *) const; /// mayAlias - Return true if the memory pointed to by this - /// PseudoSourceValue can ever alias a LLVM IR Value. + /// PseudoSourceValue can ever alias an LLVM IR Value. virtual bool mayAlias(const MachineFrameInfo *) const; /// classof - Methods for support type inquiry through isa, cast, and diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index 8b8e3d90f73e8..7472e5a62d6b5 100644 --- a/include/llvm/CodeGen/RegAllocPBQP.h +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -26,8 +26,8 @@ namespace llvm { class LiveIntervals; + class MachineBlockFrequencyInfo; class MachineFunction; - class MachineLoopInfo; class TargetRegisterInfo; template<class T> class OwningPtr; @@ -52,22 +52,22 @@ namespace llvm { /// PBQPBuilder you are unlikely to need this: Nodes and options for all /// vregs will already have been set up for you by the base class. template <typename AllowedRegsItr> - void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node, + void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId, AllowedRegsItr arBegin, AllowedRegsItr arEnd) { - assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node."); + assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node."); assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg."); assert(allowedSets[vreg].empty() && "vreg already has pregs."); - node2VReg[node] = vreg; - vreg2Node[vreg] = node; + node2VReg[nodeId] = vreg; + vreg2Node[vreg] = nodeId; std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg])); } /// Get the virtual register corresponding to the given PBQP node. - unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const; + unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const; /// Get the PBQP node corresponding to the given virtual register. - PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const; + PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const; /// Returns true if the given PBQP option represents a physical register, /// false otherwise. @@ -92,9 +92,8 @@ namespace llvm { private: - typedef std::map<PBQP::Graph::ConstNodeItr, unsigned, - PBQP::NodeItrComparator> Node2VReg; - typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node; + typedef std::map<PBQP::Graph::NodeId, unsigned> Node2VReg; + typedef DenseMap<unsigned, PBQP::Graph::NodeId> VReg2Node; typedef DenseMap<unsigned, AllowedSet> AllowedSetMap; PBQP::Graph graph; @@ -125,7 +124,7 @@ namespace llvm { /// Build a PBQP instance to represent the register allocation problem for /// the given MachineFunction. virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis, - const MachineLoopInfo *loopInfo, + const MachineBlockFrequencyInfo *mbfi, const RegSet &vregs); private: @@ -144,7 +143,7 @@ namespace llvm { /// Build a PBQP instance to represent the register allocation problem for /// the given MachineFunction. virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis, - const MachineLoopInfo *loopInfo, + const MachineBlockFrequencyInfo *mbfi, const RegSet &vregs); private: diff --git a/include/llvm/CodeGen/RegisterClassInfo.h b/include/llvm/CodeGen/RegisterClassInfo.h index 3ad22e65c8c7d..9ec12bdea0ad3 100644 --- a/include/llvm/CodeGen/RegisterClassInfo.h +++ b/include/llvm/CodeGen/RegisterClassInfo.h @@ -62,6 +62,8 @@ class RegisterClassInfo { // Reserved registers in the current MF. BitVector Reserved; + OwningArrayPtr<unsigned> PSetLimits; + // Compute all information about RC. void compute(const TargetRegisterClass *RC) const; @@ -126,8 +128,19 @@ public: unsigned getLastCostChange(const TargetRegisterClass *RC) { return get(RC).LastCostChange; } + + /// Get the register unit limit for the given pressure set index. + /// + /// RegisterClassInfo adjusts this limit for reserved registers. + unsigned getRegPressureSetLimit(unsigned Idx) const { + if (!PSetLimits[Idx]) + PSetLimits[Idx] = computePSetLimit(Idx); + return PSetLimits[Idx]; + } + +protected: + unsigned computePSetLimit(unsigned Idx) const; }; } // end namespace llvm #endif - diff --git a/include/llvm/CodeGen/RegisterPressure.h b/include/llvm/CodeGen/RegisterPressure.h index 267018074677d..a801d1d1eee9b 100644 --- a/include/llvm/CodeGen/RegisterPressure.h +++ b/include/llvm/CodeGen/RegisterPressure.h @@ -22,7 +22,7 @@ namespace llvm { class LiveIntervals; -class LiveInterval; +class LiveRange; class RegisterClassInfo; class MachineInstr; @@ -89,16 +89,89 @@ struct RegionPressure : RegisterPressure { void openBottom(MachineBasicBlock::const_iterator PrevBottom); }; -/// An element of pressure difference that identifies the pressure set and -/// amount of increase or decrease in units of pressure. -struct PressureElement { - unsigned PSetID; - int UnitIncrease; +/// Capture a change in pressure for a single pressure set. UnitInc may be +/// expressed in terms of upward or downward pressure depending on the client +/// and will be dynamically adjusted for current liveness. +/// +/// Pressure increments are tiny, typically 1-2 units, and this is only for +/// heuristics, so we don't check UnitInc overflow. Instead, we may have a +/// higher level assert that pressure is consistent within a region. We also +/// effectively ignore dead defs which don't affect heuristics much. +class PressureChange { + uint16_t PSetID; // ID+1. 0=Invalid. + int16_t UnitInc; +public: + PressureChange(): PSetID(0), UnitInc(0) {} + PressureChange(unsigned id): PSetID(id+1), UnitInc(0) { + assert(id < UINT16_MAX && "PSetID overflow."); + } + + bool isValid() const { return PSetID > 0; } + + unsigned getPSet() const { + assert(isValid() && "invalid PressureChange"); + return PSetID - 1; + } + // If PSetID is invalid, return UINT16_MAX to give it lowest priority. + unsigned getPSetOrMax() const { return (PSetID - 1) & UINT16_MAX; } + + int getUnitInc() const { return UnitInc; } + + void setUnitInc(int Inc) { UnitInc = Inc; } + + bool operator==(const PressureChange &RHS) const { + return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc; + } +}; + +template <> struct isPodLike<PressureChange> { + static const bool value = true; +}; + +/// List of PressureChanges in order of increasing, unique PSetID. +/// +/// Use a small fixed number, because we can fit more PressureChanges in an +/// empty SmallVector than ever need to be tracked per register class. If more +/// PSets are affected, then we only track the most constrained. +class PressureDiff { + // The initial design was for MaxPSets=4, but that requires PSet partitions, + // which are not yet implemented. (PSet partitions are equivalent PSets given + // the register classes actually in use within the scheduling region.) + enum { MaxPSets = 16 }; + + PressureChange PressureChanges[MaxPSets]; +public: + typedef PressureChange* iterator; + typedef const PressureChange* const_iterator; + iterator begin() { return &PressureChanges[0]; } + iterator end() { return &PressureChanges[MaxPSets]; } + const_iterator begin() const { return &PressureChanges[0]; } + const_iterator end() const { return &PressureChanges[MaxPSets]; } + + void addPressureChange(unsigned RegUnit, bool IsDec, + const MachineRegisterInfo *MRI); +}; + +/// Array of PressureDiffs. +class PressureDiffs { + PressureDiff *PDiffArray; + unsigned Size; + unsigned Max; +public: + PressureDiffs(): PDiffArray(0), Size(0), Max(0) {} + ~PressureDiffs() { free(PDiffArray); } - PressureElement(): PSetID(~0U), UnitIncrease(0) {} - PressureElement(unsigned id, int inc): PSetID(id), UnitIncrease(inc) {} + void clear() { Size = 0; } - bool isValid() const { return PSetID != ~0U; } + void init(unsigned N); + + PressureDiff &operator[](unsigned Idx) { + assert(Idx < Size && "PressureDiff index out of bounds"); + return PDiffArray[Idx]; + } + const PressureDiff &operator[](unsigned Idx) const { + return const_cast<PressureDiffs*>(this)->operator[](Idx); + } }; /// Store the effects of a change in pressure on things that MI scheduler cares @@ -116,11 +189,19 @@ struct PressureElement { /// CurrentMax records the largest increase in the tracker's max pressure that /// exceeds the current limit for some pressure set determined by the client. struct RegPressureDelta { - PressureElement Excess; - PressureElement CriticalMax; - PressureElement CurrentMax; + PressureChange Excess; + PressureChange CriticalMax; + PressureChange CurrentMax; RegPressureDelta() {} + + bool operator==(const RegPressureDelta &RHS) const { + return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax + && CurrentMax == RHS.CurrentMax; + } + bool operator!=(const RegPressureDelta &RHS) const { + return !operator==(RHS); + } }; /// \brief A set of live virtual registers and physical register units. @@ -131,7 +212,7 @@ struct LiveRegSet { SparseSet<unsigned> PhysRegs; SparseSet<unsigned, VirtReg2IndexFunctor> VirtRegs; - bool contains(unsigned Reg) { + bool contains(unsigned Reg) const { if (TargetRegisterInfo::isVirtualRegister(Reg)) return VirtRegs.count(Reg); return PhysRegs.count(Reg); @@ -183,6 +264,9 @@ class RegPressureTracker { /// or RegisterPressure. If requireIntervals is false, LIS are ignored. bool RequireIntervals; + /// True if UntiedDefs will be populated. + bool TrackUntiedDefs; + /// Register pressure corresponds to liveness before this instruction /// iterator. It may point to the end of the block or a DebugValue rather than /// an instruction. @@ -194,16 +278,26 @@ class RegPressureTracker { /// Set of live registers. LiveRegSet LiveRegs; + /// Set of vreg defs that start a live range. + SparseSet<unsigned, VirtReg2IndexFunctor> UntiedDefs; + /// Live-through pressure. + std::vector<unsigned> LiveThruPressure; + public: RegPressureTracker(IntervalPressure &rp) : - MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(true) {} + MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(true), + TrackUntiedDefs(false) {} RegPressureTracker(RegionPressure &rp) : - MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false) {} + MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false), + TrackUntiedDefs(false) {} + + void reset(); void init(const MachineFunction *mf, const RegisterClassInfo *rci, const LiveIntervals *lis, const MachineBasicBlock *mbb, - MachineBasicBlock::const_iterator pos); + MachineBasicBlock::const_iterator pos, + bool ShouldTrackUntiedDefs = false); /// Force liveness of virtual registers or physical register /// units. Particularly useful to initialize the livein/out state of the @@ -224,7 +318,7 @@ public: SlotIndex getCurrSlot() const; /// Recede across the previous instruction. - bool recede(); + bool recede(SmallVectorImpl<unsigned> *LiveUses = 0, PressureDiff *PDiff = 0); /// Advance across the current instruction. bool advance(); @@ -232,6 +326,17 @@ public: /// Finalize the region boundaries and recored live ins and live outs. void closeRegion(); + /// Initialize the LiveThru pressure set based on the untied defs found in + /// RPTracker. + void initLiveThru(const RegPressureTracker &RPTracker); + + /// Copy an existing live thru pressure result. + void initLiveThru(ArrayRef<unsigned> PressureSet) { + LiveThruPressure.assign(PressureSet.begin(), PressureSet.end()); + } + + ArrayRef<unsigned> getLiveThru() const { return LiveThruPressure; } + /// Get the resulting register pressure over the traversed region. /// This result is complete if either advance() or recede() has returned true, /// or if closeRegion() was explicitly invoked. @@ -256,31 +361,39 @@ public: /// limit based on the tracker's current pressure, and record the number of /// excess register units of that pressure set introduced by this instruction. void getMaxUpwardPressureDelta(const MachineInstr *MI, + PressureDiff *PDiff, RegPressureDelta &Delta, - ArrayRef<PressureElement> CriticalPSets, + ArrayRef<PressureChange> CriticalPSets, ArrayRef<unsigned> MaxPressureLimit); + void getUpwardPressureDelta(const MachineInstr *MI, + /*const*/ PressureDiff &PDiff, + RegPressureDelta &Delta, + ArrayRef<PressureChange> CriticalPSets, + ArrayRef<unsigned> MaxPressureLimit) const; + /// Consider the pressure increase caused by traversing this instruction /// top-down. Find the pressure set with the most change beyond its pressure /// limit based on the tracker's current pressure, and record the number of /// excess register units of that pressure set introduced by this instruction. void getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, - ArrayRef<PressureElement> CriticalPSets, + ArrayRef<PressureChange> CriticalPSets, ArrayRef<unsigned> MaxPressureLimit); /// Find the pressure set with the most change beyond its pressure limit after /// traversing this instruction either upward or downward depending on the /// closed end of the current region. - void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, - ArrayRef<PressureElement> CriticalPSets, + void getMaxPressureDelta(const MachineInstr *MI, + RegPressureDelta &Delta, + ArrayRef<PressureChange> CriticalPSets, ArrayRef<unsigned> MaxPressureLimit) { if (isTopClosed()) return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, MaxPressureLimit); assert(isBottomClosed() && "Uninitialized pressure tracker"); - return getMaxUpwardPressureDelta(MI, Delta, CriticalPSets, + return getMaxUpwardPressureDelta(MI, 0, Delta, CriticalPSets, MaxPressureLimit); } @@ -304,10 +417,14 @@ public: return getDownwardPressure(MI, PressureResult, MaxPressureResult); } + bool hasUntiedDef(unsigned VirtReg) const { + return UntiedDefs.count(VirtReg); + } + void dump() const; protected: - const LiveInterval *getInterval(unsigned Reg) const; + const LiveRange *getLiveRange(unsigned Reg) const; void increaseRegPressure(ArrayRef<unsigned> Regs); void decreaseRegPressure(ArrayRef<unsigned> Regs); @@ -315,6 +432,11 @@ protected: void bumpUpwardPressure(const MachineInstr *MI); void bumpDownwardPressure(const MachineInstr *MI); }; + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +void dumpRegSetPressure(ArrayRef<unsigned> SetPressure, + const TargetRegisterInfo *TRI); +#endif } // end namespace llvm #endif diff --git a/include/llvm/CodeGen/RegisterScavenging.h b/include/llvm/CodeGen/RegisterScavenging.h index 95bf29167c201..28ebe5361b4a9 100644 --- a/include/llvm/CodeGen/RegisterScavenging.h +++ b/include/llvm/CodeGen/RegisterScavenging.h @@ -131,7 +131,7 @@ public: /// Query whether a frame index is a scavenging frame index. bool isScavengingFrameIndex(int FI) const { - for (SmallVector<ScavengedInfo, 2>::const_iterator I = Scavenged.begin(), + for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), IE = Scavenged.end(); I != IE; ++I) if (I->FrameIndex == FI) return true; @@ -141,7 +141,7 @@ public: /// Get an array of scavenging frame indices. void getScavengingFrameIndices(SmallVectorImpl<int> &A) const { - for (SmallVector<ScavengedInfo, 2>::const_iterator I = Scavenged.begin(), + for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(), IE = Scavenged.end(); I != IE; ++I) if (I->FrameIndex >= 0) A.push_back(I->FrameIndex); diff --git a/include/llvm/CodeGen/RuntimeLibcalls.h b/include/llvm/CodeGen/RuntimeLibcalls.h index 41289a42c4387..009b8a0f697a1 100644 --- a/include/llvm/CodeGen/RuntimeLibcalls.h +++ b/include/llvm/CodeGen/RuntimeLibcalls.h @@ -1,4 +1,4 @@ -//===-- CodeGen/RuntimeLibcall.h - Runtime Library Calls --------*- C++ -*-===// +//===-- CodeGen/RuntimeLibcalls.h - Runtime Library Calls -------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -188,6 +188,11 @@ namespace RTLIB { NEARBYINT_F80, NEARBYINT_F128, NEARBYINT_PPCF128, + ROUND_F32, + ROUND_F64, + ROUND_F80, + ROUND_F128, + ROUND_PPCF128, FLOOR_F32, FLOOR_F64, FLOOR_F80, @@ -320,34 +325,65 @@ namespace RTLIB { SYNC_VAL_COMPARE_AND_SWAP_2, SYNC_VAL_COMPARE_AND_SWAP_4, SYNC_VAL_COMPARE_AND_SWAP_8, + SYNC_VAL_COMPARE_AND_SWAP_16, SYNC_LOCK_TEST_AND_SET_1, SYNC_LOCK_TEST_AND_SET_2, SYNC_LOCK_TEST_AND_SET_4, SYNC_LOCK_TEST_AND_SET_8, + SYNC_LOCK_TEST_AND_SET_16, SYNC_FETCH_AND_ADD_1, SYNC_FETCH_AND_ADD_2, SYNC_FETCH_AND_ADD_4, SYNC_FETCH_AND_ADD_8, + SYNC_FETCH_AND_ADD_16, SYNC_FETCH_AND_SUB_1, SYNC_FETCH_AND_SUB_2, SYNC_FETCH_AND_SUB_4, SYNC_FETCH_AND_SUB_8, + SYNC_FETCH_AND_SUB_16, SYNC_FETCH_AND_AND_1, SYNC_FETCH_AND_AND_2, SYNC_FETCH_AND_AND_4, SYNC_FETCH_AND_AND_8, + SYNC_FETCH_AND_AND_16, SYNC_FETCH_AND_OR_1, SYNC_FETCH_AND_OR_2, SYNC_FETCH_AND_OR_4, SYNC_FETCH_AND_OR_8, + SYNC_FETCH_AND_OR_16, SYNC_FETCH_AND_XOR_1, SYNC_FETCH_AND_XOR_2, SYNC_FETCH_AND_XOR_4, SYNC_FETCH_AND_XOR_8, + SYNC_FETCH_AND_XOR_16, SYNC_FETCH_AND_NAND_1, SYNC_FETCH_AND_NAND_2, SYNC_FETCH_AND_NAND_4, SYNC_FETCH_AND_NAND_8, + SYNC_FETCH_AND_NAND_16, + SYNC_FETCH_AND_MAX_1, + SYNC_FETCH_AND_MAX_2, + SYNC_FETCH_AND_MAX_4, + SYNC_FETCH_AND_MAX_8, + SYNC_FETCH_AND_MAX_16, + SYNC_FETCH_AND_UMAX_1, + SYNC_FETCH_AND_UMAX_2, + SYNC_FETCH_AND_UMAX_4, + SYNC_FETCH_AND_UMAX_8, + SYNC_FETCH_AND_UMAX_16, + SYNC_FETCH_AND_MIN_1, + SYNC_FETCH_AND_MIN_2, + SYNC_FETCH_AND_MIN_4, + SYNC_FETCH_AND_MIN_8, + SYNC_FETCH_AND_MIN_16, + SYNC_FETCH_AND_UMIN_1, + SYNC_FETCH_AND_UMIN_2, + SYNC_FETCH_AND_UMIN_4, + SYNC_FETCH_AND_UMIN_8, + SYNC_FETCH_AND_UMIN_16, + + // Stack Protector Fail. + STACKPROTECTOR_CHECK_FAIL, UNKNOWN_LIBCALL }; diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 7cff27e17240b..ccba1b0364e44 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -90,11 +90,6 @@ namespace llvm { /// the value of the Latency field of the predecessor, however advanced /// models may provide additional information about specific edges. unsigned Latency; - /// Record MinLatency seperately from "expected" Latency. - /// - /// FIXME: this field is not packed on LP64. Convert to 16-bit DAG edge - /// latency after introducing saturating truncation. - unsigned MinLatency; public: /// SDep - Construct a null SDep. This is only for use by container @@ -120,10 +115,9 @@ namespace llvm { Latency = 1; break; } - MinLatency = Latency; } SDep(SUnit *S, OrderKind kind) - : Dep(S, Order), Contents(), Latency(0), MinLatency(0) { + : Dep(S, Order), Contents(), Latency(0) { Contents.OrdKind = kind; } @@ -142,8 +136,7 @@ namespace llvm { } bool operator==(const SDep &Other) const { - return overlaps(Other) - && Latency == Other.Latency && MinLatency == Other.MinLatency; + return overlaps(Other) && Latency == Other.Latency; } bool operator!=(const SDep &Other) const { @@ -163,18 +156,6 @@ namespace llvm { Latency = Lat; } - /// getMinLatency - Return the minimum latency for this edge. Minimum - /// latency is used for scheduling groups, while normal (expected) latency - /// is for instruction cost and critical path. - unsigned getMinLatency() const { - return MinLatency; - } - - /// setMinLatency - Set the minimum latency for this edge. - void setMinLatency(unsigned Lat) { - MinLatency = Lat; - } - //// getSUnit - Return the SUnit to which this edge points. SUnit *getSUnit() const { return Dep.getPointer(); @@ -267,7 +248,7 @@ namespace llvm { /// SUnit - Scheduling unit. This is a node in the scheduling DAG. class SUnit { private: - enum { BoundaryID = ~0u }; + enum LLVM_ENUM_INT_TYPE(unsigned) { BoundaryID = ~0u }; SDNode *Node; // Representative node. MachineInstr *Instr; // Alternatively, a MachineInstr. @@ -282,10 +263,10 @@ namespace llvm { SmallVector<SDep, 4> Preds; // All sunit predecessors. SmallVector<SDep, 4> Succs; // All sunit successors. - typedef SmallVector<SDep, 4>::iterator pred_iterator; - typedef SmallVector<SDep, 4>::iterator succ_iterator; - typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; - typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator; + typedef SmallVectorImpl<SDep>::iterator pred_iterator; + typedef SmallVectorImpl<SDep>::iterator succ_iterator; + typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator; + typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator; unsigned NodeNum; // Entry # of node in the node vector. unsigned NodeQueueId; // Queue id of node. diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h index 990cac6348b1e..fe4f3c2de3b6b 100644 --- a/include/llvm/CodeGen/ScheduleDAGInstrs.h +++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -28,6 +28,7 @@ namespace llvm { class MachineDominatorTree; class LiveIntervals; class RegPressureTracker; + class PressureDiffs; /// An individual mapping from virtual register number to SUnit. struct VReg2SUnit { @@ -56,7 +57,8 @@ namespace llvm { /// Use a SparseMultiSet to track physical registers. Storage is only /// allocated once for the pass. It can be cleared in constant time and reused /// without any frees. - typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t> Reg2SUnitsMap; + typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t> + Reg2SUnitsMap; /// Use SparseSet as a SparseMap by relying on the fact that it never /// compares ValueT's, only unsigned keys. This allows the set to be cleared @@ -64,6 +66,11 @@ namespace llvm { /// require a destructor. typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap; + /// Track local uses of virtual registers. These uses are gathered by the DAG + /// builder and may be consulted by the scheduler to avoid iterating an entire + /// vreg use list. + typedef SparseMultiSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2UseMap; + /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of /// MachineInstrs. class ScheduleDAGInstrs : public ScheduleDAG { @@ -81,10 +88,6 @@ namespace llvm { /// isPostRA flag indicates vregs cannot be present. bool IsPostRA; - /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using - /// the def-side latency only. - bool UnitLatencies; - /// The standard DAG builder does not normally include terminators as DAG /// nodes because it does not create the necessary dependencies to prevent /// reordering. A specialized scheduler can overide @@ -104,17 +107,18 @@ namespace llvm { /// The end of the range to be scheduled. MachineBasicBlock::iterator RegionEnd; - /// The index in BB of RegionEnd. - /// - /// This is the instruction number from the top of the current block, not - /// the SlotIndex. It is only used by the AntiDepBreaker and should be - /// removed once that client is obsolete. - unsigned EndIndex; + /// Instructions in this region (distance(RegionBegin, RegionEnd)). + unsigned NumRegionInstrs; /// After calling BuildSchedGraph, each machine instruction in the current /// scheduling region is mapped to an SUnit. DenseMap<MachineInstr*, SUnit*> MISUnitMap; + /// After calling BuildSchedGraph, each vreg used in the scheduling region + /// is mapped to a set of SUnits. These include all local vreg uses, not + /// just the uses for a singly defined vreg. + VReg2UseMap VRegUses; + /// State internal to DAG building. /// ------------------------------- @@ -125,7 +129,7 @@ namespace llvm { Reg2SUnitsMap Defs; Reg2SUnitsMap Uses; - /// Track the last instructon in this region defining each virtual register. + /// Track the last instruction in this region defining each virtual register. VReg2SUnitMap VRegDefs; /// PendingLoads - Remember where unknown loads are after the most recent @@ -158,7 +162,7 @@ namespace llvm { /// \brief Resolve and cache a resolved scheduling class for an SUnit. const MCSchedClassDesc *getSchedClass(SUnit *SU) const { - if (!SU->SchedClass) + if (!SU->SchedClass && SchedModel.hasInstrSchedModel()) SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr()); return SU->SchedClass; } @@ -185,14 +189,15 @@ namespace llvm { virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, - unsigned endcount); + unsigned regioninstrs); /// Notify that the scheduler has finished scheduling the current region. virtual void exitRegion(); /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are /// input. - void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0); + void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0, + PressureDiffs *PDiffs = 0); /// addSchedBarrierDeps - Add dependencies from instructions in the current /// list of instructions being scheduled to scheduling barrier. We want to diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 8c064bf2d446e..82becca315a14 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -33,12 +33,50 @@ class AliasAnalysis; class MachineConstantPoolValue; class MachineFunction; class MDNode; -class SDNodeOrdering; class SDDbgValue; class TargetLowering; class TargetSelectionDAGInfo; class TargetTransformInfo; +class SDVTListNode : public FoldingSetNode { + friend struct FoldingSetTrait<SDVTListNode>; + /// FastID - A reference to an Interned FoldingSetNodeID for this node. + /// The Allocator in SelectionDAG holds the data. + /// SDVTList contains all types which are frequently accessed in SelectionDAG. + /// The size of this list is not expected big so it won't introduce memory penalty. + FoldingSetNodeIDRef FastID; + const EVT *VTs; + unsigned int NumVTs; + /// The hash value for SDVTList is fixed so cache it to avoid hash calculation + unsigned HashValue; +public: + SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) : + FastID(ID), VTs(VT), NumVTs(Num) { + HashValue = ID.ComputeHash(); + } + SDVTList getSDVTList() { + SDVTList result = {VTs, NumVTs}; + return result; + } +}; + +// Specialize FoldingSetTrait for SDVTListNode +// To avoid computing temp FoldingSetNodeID and hash value. +template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> { + static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) { + ID = X.FastID; + } + static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID, + unsigned IDHash, FoldingSetNodeID &TempID) { + if (X.HashValue != IDHash) + return false; + return ID == X.FastID; + } + static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) { + return X.HashValue; + } +}; + template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> { private: mutable ilist_half_node<SDNode> Sentinel; @@ -73,7 +111,8 @@ private: class SDDbgInfo { SmallVector<SDDbgValue*, 32> DbgValues; SmallVector<SDDbgValue*, 32> ByvalParmDbgValues; - DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMap; + typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType; + DbgValMapType DbgValMap; void operator=(const SDDbgInfo&) LLVM_DELETED_FUNCTION; SDDbgInfo(const SDDbgInfo&) LLVM_DELETED_FUNCTION; @@ -99,14 +138,13 @@ public: } ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) { - DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> >::iterator I = - DbgValMap.find(Node); + DbgValMapType::iterator I = DbgValMap.find(Node); if (I != DbgValMap.end()) return I->second; return ArrayRef<SDDbgValue*>(); } - typedef SmallVector<SDDbgValue*,32>::iterator DbgIterator; + typedef SmallVectorImpl<SDDbgValue*>::iterator DbgIterator; DbgIterator DbgBegin() { return DbgValues.begin(); } DbgIterator DbgEnd() { return DbgValues.end(); } DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); } @@ -130,9 +168,9 @@ void checkForCycles(const SelectionDAG *DAG); /// class SelectionDAG { const TargetMachine &TM; - const TargetLowering &TLI; const TargetSelectionDAGInfo &TSI; const TargetTransformInfo *TTI; + const TargetLowering *TLI; MachineFunction *MF; LLVMContext *Context; CodeGenOpt::Level OptLevel; @@ -166,10 +204,6 @@ class SelectionDAG { /// SelectionDAG. BumpPtrAllocator Allocator; - /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to - /// the ordering of the original LLVM instructions. - SDNodeOrdering *Ordering; - /// DbgInfo - Tracks dbg_value information through SDISel. SDDbgInfo *DbgInfo; @@ -203,6 +237,13 @@ public: virtual void NodeUpdated(SDNode *N); }; + /// NewNodesMustHaveLegalTypes - When true, additional steps are taken to + /// ensure that getConstant() and similar functions return DAG nodes that + /// have legal types. This is important after type legalization since + /// any illegally typed nodes generated after this point will not experience + /// type legalization. + bool NewNodesMustHaveLegalTypes; + private: /// DAGUpdateListener is a friend so it can manipulate the listener stack. friend struct DAGUpdateListener; @@ -228,7 +269,8 @@ public: /// init - Prepare this SelectionDAG to process code in the given /// MachineFunction. /// - void init(MachineFunction &mf, const TargetTransformInfo *TTI); + void init(MachineFunction &mf, const TargetTransformInfo *TTI, + const TargetLowering *TLI); /// clear - Clear state and free memory necessary to make this /// SelectionDAG ready to process a new block. @@ -237,7 +279,7 @@ public: MachineFunction &getMachineFunction() const { return *MF; } const TargetMachine &getTarget() const { return TM; } - const TargetLowering &getTargetLoweringInfo() const { return TLI; } + const TargetLowering &getTargetLoweringInfo() const { return *TLI; } const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; } const TargetTransformInfo *getTargetTransformInfo() const { return TTI; } LLVMContext *getContext() const {return Context; } @@ -386,10 +428,10 @@ public: SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) { return getConstantFP(Val, VT, true); } - SDValue getGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT, + SDValue getGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT, int64_t offset = 0, bool isTargetGA = false, unsigned char TargetFlags = 0); - SDValue getTargetGlobalAddress(const GlobalValue *GV, DebugLoc DL, EVT VT, + SDValue getTargetGlobalAddress(const GlobalValue *GV, SDLoc DL, EVT VT, int64_t offset = 0, unsigned char TargetFlags = 0) { return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags); @@ -424,15 +466,15 @@ public: // When generating a branch to a BB, we don't in general know enough // to provide debug info for the BB at that time, so keep this one around. SDValue getBasicBlock(MachineBasicBlock *MBB); - SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl); + SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl); SDValue getExternalSymbol(const char *Sym, EVT VT); - SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT); + SDValue getExternalSymbol(const char *Sym, SDLoc dl, EVT VT); SDValue getTargetExternalSymbol(const char *Sym, EVT VT, unsigned char TargetFlags = 0); SDValue getValueType(EVT); SDValue getRegister(unsigned Reg, EVT VT); SDValue getRegisterMask(const uint32_t *RegMask); - SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label); + SDValue getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label); SDValue getBlockAddress(const BlockAddress *BA, EVT VT, int64_t Offset = 0, bool isTarget = false, unsigned char TargetFlags = 0); @@ -442,7 +484,7 @@ public: return getBlockAddress(BA, VT, Offset, true, TargetFlags); } - SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) { + SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N) { return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, getRegister(Reg, N.getValueType()), N); } @@ -450,7 +492,7 @@ public: // This version of the getCopyToReg method takes an extra operand, which // indicates that there is potentially an incoming glue value (if Glue is not // null) and that there should be a glue result. - SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N, + SDValue getCopyToReg(SDValue Chain, SDLoc dl, unsigned Reg, SDValue N, SDValue Glue) { SDVTList VTs = getVTList(MVT::Other, MVT::Glue); SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue }; @@ -458,14 +500,14 @@ public: } // Similar to last getCopyToReg() except parameter Reg is a SDValue - SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N, + SDValue getCopyToReg(SDValue Chain, SDLoc dl, SDValue Reg, SDValue N, SDValue Glue) { SDVTList VTs = getVTList(MVT::Other, MVT::Glue); SDValue Ops[] = { Chain, Reg, N, Glue }; return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3); } - SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) { + SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT) { SDVTList VTs = getVTList(VT, MVT::Other); SDValue Ops[] = { Chain, getRegister(Reg, VT) }; return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2); @@ -474,7 +516,7 @@ public: // This version of the getCopyFromReg method takes an extra operand, which // indicates that there is potentially an incoming glue value (if Glue is not // null) and that there should be a glue result. - SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT, + SDValue getCopyFromReg(SDValue Chain, SDLoc dl, unsigned Reg, EVT VT, SDValue Glue) { SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue); SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue }; @@ -485,7 +527,7 @@ public: /// Returns the ConvertRndSat Note: Avoid using this node because it may /// disappear in the future and most targets don't support it. - SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy, + SDValue getConvertRndSat(EVT VT, SDLoc dl, SDValue Val, SDValue DTy, SDValue STy, SDValue Rnd, SDValue Sat, ISD::CvtCode Code); @@ -493,95 +535,95 @@ public: /// elements in VT, which must be a vector type, must match the number of /// mask elements NumElts. A integer mask element equal to -1 is treated as /// undefined. - SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2, + SDValue getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, SDValue N2, const int *MaskElts); /// getAnyExtOrTrunc - Convert Op, which must be of integer type, to the /// integer type VT, by either any-extending or truncating it. - SDValue getAnyExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT); + SDValue getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT); /// getSExtOrTrunc - Convert Op, which must be of integer type, to the /// integer type VT, by either sign-extending or truncating it. - SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT); + SDValue getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT); /// getZExtOrTrunc - Convert Op, which must be of integer type, to the /// integer type VT, by either zero-extending or truncating it. - SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT); + SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT); /// getZeroExtendInReg - Return the expression required to zero extend the Op /// value assuming it was the smaller SrcTy value. - SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy); + SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy); /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). - SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT); + SDValue getNOT(SDLoc DL, SDValue Val, EVT VT); /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have /// a glue result (to ensure it's not CSE'd). CALLSEQ_START does not have a - /// useful DebugLoc. - SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) { + /// useful SDLoc. + SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) { SDVTList VTs = getVTList(MVT::Other, MVT::Glue); SDValue Ops[] = { Chain, Op }; - return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2); + return getNode(ISD::CALLSEQ_START, DL, VTs, Ops, 2); } /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have - /// a useful DebugLoc. + /// a useful SDLoc. SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, - SDValue InGlue) { + SDValue InGlue, SDLoc DL) { SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue); SmallVector<SDValue, 4> Ops; Ops.push_back(Chain); Ops.push_back(Op1); Ops.push_back(Op2); Ops.push_back(InGlue); - return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0], + return getNode(ISD::CALLSEQ_END, DL, NodeTys, &Ops[0], (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0)); } - /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc. + /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful SDLoc. SDValue getUNDEF(EVT VT) { - return getNode(ISD::UNDEF, DebugLoc(), VT); + return getNode(ISD::UNDEF, SDLoc(), VT); } /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node. This does - /// not have a useful DebugLoc. + /// not have a useful SDLoc. SDValue getGLOBAL_OFFSET_TABLE(EVT VT) { - return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc(), VT); + return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT); } /// getNode - Gets or creates the specified node. /// - SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT); - SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N); - SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2); - SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT); + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N); + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2); + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, SDValue N3); - SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, SDValue N3, SDValue N4); - SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2, SDValue N3, SDValue N4, SDValue N5); - SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, const SDUse *Ops, unsigned NumOps); - SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, + SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, const SDValue *Ops, unsigned NumOps); - SDValue getNode(unsigned Opcode, DebugLoc DL, + SDValue getNode(unsigned Opcode, SDLoc DL, ArrayRef<EVT> ResultTys, const SDValue *Ops, unsigned NumOps); - SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs, + SDValue getNode(unsigned Opcode, SDLoc DL, const EVT *VTs, unsigned NumVTs, const SDValue *Ops, unsigned NumOps); - SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, const SDValue *Ops, unsigned NumOps); - SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs); - SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N); - SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs); + SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N); + SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1, SDValue N2); - SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1, SDValue N2, SDValue N3); - SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1, SDValue N2, SDValue N3, SDValue N4); - SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, + SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N1, SDValue N2, SDValue N3, SDValue N4, SDValue N5); @@ -591,36 +633,50 @@ public: /// clobbered. SDValue getStackArgumentTokenFactor(SDValue Chain); - SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, + SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src, SDValue Size, unsigned Align, bool isVol, bool AlwaysInline, MachinePointerInfo DstPtrInfo, MachinePointerInfo SrcPtrInfo); - SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, + SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src, SDValue Size, unsigned Align, bool isVol, MachinePointerInfo DstPtrInfo, MachinePointerInfo SrcPtrInfo); - SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, + SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src, SDValue Size, unsigned Align, bool isVol, MachinePointerInfo DstPtrInfo); /// getSetCC - Helper function to make it easier to build SetCC's if you just /// have an ISD::CondCode instead of an SDValue. /// - SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS, + SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS, ISD::CondCode Cond) { assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() && "Cannot compare scalars to vectors"); assert(LHS.getValueType().isVector() == VT.isVector() && "Cannot compare scalars to vectors"); + assert(Cond != ISD::SETCC_INVALID && + "Cannot create a setCC of an invalid node."); return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond)); } + // getSelect - Helper function to make it easier to build Select's if you just + // have operands and don't want to check for vector. + SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond, + SDValue LHS, SDValue RHS) { + assert(LHS.getValueType() == RHS.getValueType() && + "Cannot use select on differing types"); + assert(VT.isVector() == LHS.getValueType().isVector() && + "Cannot mix vectors and scalars"); + return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT, + Cond, LHS, RHS); + } + /// getSelectCC - Helper function to make it easier to build SelectCC's if you /// just have an ISD::CondCode instead of an SDValue. /// - SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS, + SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS, SDValue True, SDValue False, ISD::CondCode Cond) { return getNode(ISD::SELECT_CC, DL, True.getValueType(), LHS, RHS, True, False, getCondCode(Cond)); @@ -628,17 +684,17 @@ public: /// getVAArg - VAArg produces a result and token chain, and takes a pointer /// and a source value as input. - SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, + SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, SDValue SV, unsigned Align); /// getAtomic - Gets a node for an atomic op, produces result and chain and /// takes 3 operands - SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, + SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo, unsigned Alignment, AtomicOrdering Ordering, SynchronizationScope SynchScope); - SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, + SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp, MachineMemOperand *MMO, AtomicOrdering Ordering, @@ -646,93 +702,105 @@ public: /// getAtomic - Gets a node for an atomic op, produces result (if relevant) /// and chain and takes 2 operands. - SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, + SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Val, const Value* PtrVal, unsigned Alignment, AtomicOrdering Ordering, SynchronizationScope SynchScope); - SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, + SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Val, MachineMemOperand *MMO, AtomicOrdering Ordering, SynchronizationScope SynchScope); /// getAtomic - Gets a node for an atomic op, produces result and chain and /// takes 1 operand. - SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT, + SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT, SDValue Chain, SDValue Ptr, const Value* PtrVal, unsigned Alignment, AtomicOrdering Ordering, SynchronizationScope SynchScope); - SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, EVT VT, + SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT, SDValue Chain, SDValue Ptr, MachineMemOperand *MMO, AtomicOrdering Ordering, SynchronizationScope SynchScope); + /// getAtomic - Gets a node for an atomic op, produces result and chain and + /// takes N operands. + SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList, + SDValue* Ops, unsigned NumOps, MachineMemOperand *MMO, + AtomicOrdering Ordering, + SynchronizationScope SynchScope); + /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a /// result and takes a list of operands. Opcode may be INTRINSIC_VOID, /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not /// less than FIRST_TARGET_MEMORY_OPCODE. - SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, + SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, const EVT *VTs, unsigned NumVTs, const SDValue *Ops, unsigned NumOps, EVT MemVT, MachinePointerInfo PtrInfo, unsigned Align = 0, bool Vol = false, bool ReadMem = true, bool WriteMem = true); - SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, + SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList, const SDValue *Ops, unsigned NumOps, EVT MemVT, MachinePointerInfo PtrInfo, unsigned Align = 0, bool Vol = false, bool ReadMem = true, bool WriteMem = true); - SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, + SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList, const SDValue *Ops, unsigned NumOps, EVT MemVT, MachineMemOperand *MMO); /// getMergeValues - Create a MERGE_VALUES node from the given operands. - SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl); + SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, SDLoc dl); /// getLoad - Loads are not normal binary operators: their result type is not /// determined by their operands, and they produce a value AND a token chain. /// - SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, + SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, bool isVolatile, bool isNonTemporal, bool isInvariant, unsigned Alignment, const MDNode *TBAAInfo = 0, const MDNode *Ranges = 0); - SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT, + SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, + MachineMemOperand *MMO); + SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT, SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT, bool isVolatile, bool isNonTemporal, unsigned Alignment, const MDNode *TBAAInfo = 0); - SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, + SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT, + SDValue Chain, SDValue Ptr, EVT MemVT, + MachineMemOperand *MMO); + SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base, SDValue Offset, ISD::MemIndexedMode AM); SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, - EVT VT, DebugLoc dl, + EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, SDValue Offset, MachinePointerInfo PtrInfo, EVT MemVT, bool isVolatile, bool isNonTemporal, bool isInvariant, unsigned Alignment, const MDNode *TBAAInfo = 0, const MDNode *Ranges = 0); SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, - EVT VT, DebugLoc dl, + EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr, SDValue Offset, EVT MemVT, MachineMemOperand *MMO); /// getStore - Helper function to build ISD::STORE nodes. /// - SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, + SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr, MachinePointerInfo PtrInfo, bool isVolatile, bool isNonTemporal, unsigned Alignment, const MDNode *TBAAInfo = 0); - SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, + SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr, MachineMemOperand *MMO); - SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, + SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr, MachinePointerInfo PtrInfo, EVT TVT, bool isNonTemporal, bool isVolatile, unsigned Alignment, const MDNode *TBAAInfo = 0); - SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, + SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr, EVT TVT, MachineMemOperand *MMO); - SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base, + SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base, SDValue Offset, ISD::MemIndexedMode AM); /// getSrcValue - Construct a node to track a Value* through the backend. @@ -741,6 +809,10 @@ public: /// getMDNode - Return an MDNodeSDNode which holds an MDNode. SDValue getMDNode(const MDNode *MD); + /// getAddrSpaceCast - Return an AddrSpaceCastSDNode. + SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr, + unsigned SrcAS, unsigned DestAS); + /// getShiftAmountOperand - Return the specified value casted to /// the target's desired shift amount type. SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op); @@ -804,47 +876,47 @@ public: /// Note that getMachineNode returns the resultant node. If there is already /// a node of the specified opcode and operands, it returns that node instead /// of the current one. - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT); + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1, SDValue Op2); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1, SDValue Op2, SDValue Op3); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, ArrayRef<SDValue> Ops); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2); + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, SDValue Op1); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, SDValue Op1, SDValue Op2); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, ArrayRef<SDValue> Ops); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, EVT VT3, SDValue Op1, SDValue Op2); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, EVT VT3, ArrayRef<SDValue> Ops); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops); - MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs, + MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs, ArrayRef<SDValue> Ops); /// getTargetExtractSubreg - A convenience function for creating /// TargetInstrInfo::EXTRACT_SUBREG nodes. - SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT, + SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT, SDValue Operand); /// getTargetInsertSubreg - A convenience function for creating /// TargetInstrInfo::INSERT_SUBREG nodes. - SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT, + SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT, SDValue Operand, SDValue Subreg); /// getNodeIfExists - Get the specified node if it's already available, or @@ -950,12 +1022,6 @@ public: } } - /// AssignOrdering - Assign an order to the SDNode. - void AssignOrdering(const SDNode *SD, unsigned Order); - - /// GetOrdering - Get the order for the SDNode. - unsigned GetOrdering(const SDNode *SD) const; - /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the /// value is produced by SD. void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter); @@ -998,7 +1064,7 @@ public: /// FoldSetCC - Constant fold a setcc to true or false. SDValue FoldSetCC(EVT VT, SDValue N1, - SDValue N2, ISD::CondCode Cond, DebugLoc dl); + SDValue N2, ISD::CondCode Cond, SDLoc dl); /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We /// use this predicate to simplify operations downstream. @@ -1064,6 +1130,30 @@ public: /// it cannot be inferred. unsigned InferPtrAlignment(SDValue Ptr) const; + /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type + /// which is split (or expanded) into two not necessarily identical pieces. + std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const; + + /// SplitVector - Split the vector with EXTRACT_SUBVECTOR using the provides + /// VTs and return the low/high part. + std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL, + const EVT &LoVT, const EVT &HiVT); + + /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the + /// low/high part. + std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) { + EVT LoVT, HiVT; + llvm::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType()); + return SplitVector(N, DL, LoVT, HiVT); + } + + /// SplitVectorOperand - Split the node's operand with EXTRACT_SUBVECTOR and + /// return the low/high part. + std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo) + { + return SplitVector(N->getOperand(OpNo), SDLoc(N)); + } + private: bool RemoveNodeFromCSEMaps(SDNode *N); void AddModifiedNodeToCSEMaps(SDNode *N); @@ -1072,7 +1162,7 @@ private: void *&InsertPos); SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps, void *&InsertPos); - SDNode *UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc loc); + SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc); void DeleteNodeNotInCSEMaps(SDNode *N); void DeallocateNode(SDNode *N); @@ -1082,7 +1172,7 @@ private: void allnodes_clear(); /// VTList - List of non-single value types. - std::vector<SDVTList> VTList; + FoldingSet<SDVTListNode> VTListMap; /// CondCodeNodes - Maps to auto-CSE operations. std::vector<CondCodeSDNode*> CondCodeNodes; diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index a4721db6851f0..b5ec8cb075dca 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -30,7 +30,6 @@ namespace llvm { class MachineInstr; class TargetLowering; class TargetLibraryInfo; - class TargetInstrInfo; class TargetTransformInfo; class FunctionLoweringInfo; class ScheduleHazardRecognizer; @@ -42,8 +41,7 @@ namespace llvm { /// pattern-matching instruction selectors. class SelectionDAGISel : public MachineFunctionPass { public: - const TargetMachine &TM; - const TargetLowering &TLI; + TargetMachine &TM; const TargetLibraryInfo *LibInfo; const TargetTransformInfo *TTI; FunctionLoweringInfo *FuncInfo; @@ -56,11 +54,13 @@ public: CodeGenOpt::Level OptLevel; static char ID; - explicit SelectionDAGISel(const TargetMachine &tm, + explicit SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL = CodeGenOpt::Default); virtual ~SelectionDAGISel(); - const TargetLowering &getTargetLowering() { return TLI; } + const TargetLowering *getTargetLowering() const { + return TM.getTargetLowering(); + } virtual void getAnalysisUsage(AnalysisUsage &AU) const; @@ -113,6 +113,8 @@ public: OPC_MoveChild, OPC_MoveParent, OPC_CheckSame, + OPC_CheckChild0Same, OPC_CheckChild1Same, + OPC_CheckChild2Same, OPC_CheckChild3Same, OPC_CheckPatternPredicate, OPC_CheckPredicate, OPC_CheckOpcode, diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index fef567f56bce2..70c15e6c6e6f7 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -344,6 +344,13 @@ private: /// debugLoc - source line information. DebugLoc debugLoc; + // The ordering of the SDNodes. It roughly corresponds to the ordering of the + // original LLVM instructions. + // This is used for turning off scheduling, because we'll forgo + // the normal scheduling algorithms and output the instructions according to + // this ordering. + unsigned IROrder; + /// getValueTypeList - Return a pointer to the specified value type. static const EVT *getValueTypeList(EVT VT); @@ -365,7 +372,7 @@ public: /// \<target\>ISD namespace). bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; } - /// isTargetMemoryOpcode - Test if this node has a target-specific + /// isTargetMemoryOpcode - Test if this node has a target-specific /// memory-referencing opcode (in the \<target\>ISD namespace and /// greater than FIRST_TARGET_MEMORY_OPCODE). bool isTargetMemoryOpcode() const { @@ -412,6 +419,14 @@ public: /// setNodeId - Set unique node id. void setNodeId(int Id) { NodeId = Id; } + /// getIROrder - Return the node ordering. + /// + unsigned getIROrder() const { return IROrder; } + + /// setIROrder - Set the node ordering. + /// + void setIROrder(unsigned Order) { IROrder = Order; } + /// getDebugLoc - Return the source location info. const DebugLoc getDebugLoc() const { return debugLoc; } @@ -505,7 +520,9 @@ public: /// isPredecessorOf - Return true if this node is a predecessor of N. /// NOTE: Implemented on top of hasPredecessor and every bit as /// expensive. Use carefully. - bool isPredecessorOf(const SDNode *N) const { return N->hasPredecessor(this); } + bool isPredecessorOf(const SDNode *N) const { + return N->hasPredecessor(this); + } /// hasPredecessor - Return true if N is a predecessor of this node. /// N is either an operand of this node, or can be reached by recursively @@ -524,7 +541,7 @@ public: /// NOTE: This is still very expensive. Use carefully. bool hasPredecessorHelper(const SDNode *N, SmallPtrSet<const SDNode *, 32> &Visited, - SmallVector<const SDNode *, 16> &Worklist) const; + SmallVectorImpl<const SDNode *> &Worklist) const; /// getNumOperands - Return the number of values used by this operation. /// @@ -681,14 +698,14 @@ protected: return Ret; } - SDNode(unsigned Opc, const DebugLoc dl, SDVTList VTs, const SDValue *Ops, - unsigned NumOps) + SDNode(unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs, + const SDValue *Ops, unsigned NumOps) : NodeType(Opc), OperandsNeedDelete(true), HasDebugValue(false), SubclassData(0), NodeId(-1), OperandList(NumOps ? new SDUse[NumOps] : 0), ValueList(VTs.VTs), UseList(NULL), NumOperands(NumOps), NumValues(VTs.NumVTs), - debugLoc(dl) { + debugLoc(dl), IROrder(Order) { for (unsigned i = 0; i != NumOps; ++i) { OperandList[i].setUser(this); OperandList[i].setInitial(Ops[i]); @@ -698,11 +715,11 @@ protected: /// This constructor adds no operands itself; operands can be /// set later with InitOperands. - SDNode(unsigned Opc, const DebugLoc dl, SDVTList VTs) + SDNode(unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs) : NodeType(Opc), OperandsNeedDelete(false), HasDebugValue(false), - SubclassData(0), NodeId(-1), OperandList(0), ValueList(VTs.VTs), - UseList(NULL), NumOperands(0), NumValues(VTs.NumVTs), - debugLoc(dl) {} + SubclassData(0), NodeId(-1), OperandList(0), + ValueList(VTs.VTs), UseList(NULL), NumOperands(0), NumValues(VTs.NumVTs), + debugLoc(dl), IROrder(Order) {} /// InitOperands - Initialize the operands list of this with 1 operand. void InitOperands(SDUse *Ops, const SDValue &Op0) { @@ -770,6 +787,53 @@ protected: void DropOperands(); }; +/// Wrapper class for IR location info (IR ordering and DebugLoc) to be passed +/// into SDNode creation functions. +/// When an SDNode is created from the DAGBuilder, the DebugLoc is extracted +/// from the original Instruction, and IROrder is the ordinal position of +/// the instruction. +/// When an SDNode is created after the DAG is being built, both DebugLoc and +/// the IROrder are propagated from the original SDNode. +/// So SDLoc class provides two constructors besides the default one, one to +/// be used by the DAGBuilder, the other to be used by others. +class SDLoc { +private: + // Ptr could be used for either Instruction* or SDNode*. It is used for + // Instruction* if IROrder is not -1. + const void *Ptr; + int IROrder; + +public: + SDLoc() : Ptr(NULL), IROrder(0) {} + SDLoc(const SDNode *N) : Ptr(N), IROrder(-1) { + assert(N && "null SDNode"); + } + SDLoc(const SDValue V) : Ptr(V.getNode()), IROrder(-1) { + assert(Ptr && "null SDNode"); + } + SDLoc(const Instruction *I, int Order) : Ptr(I), IROrder(Order) { + assert(Order >= 0 && "bad IROrder"); + } + unsigned getIROrder() { + if (IROrder >= 0 || Ptr == NULL) { + return (unsigned)IROrder; + } + const SDNode *N = (const SDNode*)(Ptr); + return N->getIROrder(); + } + DebugLoc getDebugLoc() { + if (Ptr == NULL) { + return DebugLoc(); + } + if (IROrder >= 0) { + const Instruction *I = (const Instruction*)(Ptr); + return I->getDebugLoc(); + } + const SDNode *N = (const SDNode*)(Ptr); + return N->getDebugLoc(); + } +}; + // Define inline functions from the SDValue class. @@ -839,8 +903,9 @@ inline void SDUse::setNode(SDNode *N) { class UnarySDNode : public SDNode { SDUse Op; public: - UnarySDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, SDValue X) - : SDNode(Opc, dl, VTs) { + UnarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + SDValue X) + : SDNode(Opc, Order, dl, VTs) { InitOperands(&Op, X); } }; @@ -850,8 +915,9 @@ public: class BinarySDNode : public SDNode { SDUse Ops[2]; public: - BinarySDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, SDValue X, SDValue Y) - : SDNode(Opc, dl, VTs) { + BinarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + SDValue X, SDValue Y) + : SDNode(Opc, Order, dl, VTs) { InitOperands(Ops, X, Y); } }; @@ -861,9 +927,9 @@ public: class TernarySDNode : public SDNode { SDUse Ops[3]; public: - TernarySDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, SDValue X, SDValue Y, - SDValue Z) - : SDNode(Opc, dl, VTs) { + TernarySDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + SDValue X, SDValue Y, SDValue Z) + : SDNode(Opc, Order, dl, VTs) { InitOperands(Ops, X, Y, Z); } }; @@ -876,20 +942,31 @@ public: class HandleSDNode : public SDNode { SDUse Op; public: - // FIXME: Remove the "noinline" attribute once <rdar://problem/5852746> is - // fixed. -#if __GNUC__==4 && __GNUC_MINOR__==2 && defined(__APPLE__) && !defined(__llvm__) - explicit __attribute__((__noinline__)) HandleSDNode(SDValue X) -#else explicit HandleSDNode(SDValue X) -#endif - : SDNode(ISD::HANDLENODE, DebugLoc(), getSDVTList(MVT::Other)) { + : SDNode(ISD::HANDLENODE, 0, DebugLoc(), getSDVTList(MVT::Other)) { InitOperands(&Op, X); } ~HandleSDNode(); const SDValue &getValue() const { return Op; } }; +class AddrSpaceCastSDNode : public UnarySDNode { +private: + unsigned SrcAddrSpace; + unsigned DestAddrSpace; + +public: + AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT, SDValue X, + unsigned SrcAS, unsigned DestAS); + + unsigned getSrcAddressSpace() const { return SrcAddrSpace; } + unsigned getDestAddressSpace() const { return DestAddrSpace; } + + static bool classof(const SDNode *N) { + return N->getOpcode() == ISD::ADDRSPACECAST; + } +}; + /// Abstact virtual class for operations for memory operations class MemSDNode : public SDNode { private: @@ -901,17 +978,18 @@ protected: MachineMemOperand *MMO; public: - MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT MemoryVT, - MachineMemOperand *MMO); + MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + EVT MemoryVT, MachineMemOperand *MMO); - MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, const SDValue *Ops, + MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, + const SDValue *Ops, unsigned NumOps, EVT MemoryVT, MachineMemOperand *MMO); bool readMem() const { return MMO->isLoad(); } bool writeMem() const { return MMO->isStore(); } /// Returns alignment and volatility of the memory access - unsigned getOriginalAlignment() const { + unsigned getOriginalAlignment() const { return MMO->getBaseAlignment(); } unsigned getAlignment() const { @@ -1028,30 +1106,43 @@ public: // Swp: swap value // SrcVal: address to update as a Value (used for MemOperand) // Align: alignment of memory - AtomicSDNode(unsigned Opc, DebugLoc dl, SDVTList VTL, EVT MemVT, + AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, + EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp, MachineMemOperand *MMO, AtomicOrdering Ordering, SynchronizationScope SynchScope) - : MemSDNode(Opc, dl, VTL, MemVT, MMO) { + : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) { InitAtomic(Ordering, SynchScope); InitOperands(Ops, Chain, Ptr, Cmp, Swp); } - AtomicSDNode(unsigned Opc, DebugLoc dl, SDVTList VTL, EVT MemVT, + AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, + EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Val, MachineMemOperand *MMO, AtomicOrdering Ordering, SynchronizationScope SynchScope) - : MemSDNode(Opc, dl, VTL, MemVT, MMO) { + : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) { InitAtomic(Ordering, SynchScope); InitOperands(Ops, Chain, Ptr, Val); } - AtomicSDNode(unsigned Opc, DebugLoc dl, SDVTList VTL, EVT MemVT, + AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, + EVT MemVT, SDValue Chain, SDValue Ptr, MachineMemOperand *MMO, AtomicOrdering Ordering, SynchronizationScope SynchScope) - : MemSDNode(Opc, dl, VTL, MemVT, MMO) { + : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) { InitAtomic(Ordering, SynchScope); InitOperands(Ops, Chain, Ptr); } + AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT, + SDValue* AllOps, SDUse *DynOps, unsigned NumOps, + MachineMemOperand *MMO, + AtomicOrdering Ordering, SynchronizationScope SynchScope) + : MemSDNode(Opc, Order, dl, VTL, MemVT, MMO) { + InitAtomic(Ordering, SynchScope); + assert((DynOps || NumOps <= array_lengthof(Ops)) && + "Too many ops for internal storage!"); + InitOperands(DynOps ? DynOps : Ops, AllOps, NumOps); + } const SDValue &getBasePtr() const { return getOperand(1); } const SDValue &getVal() const { return getOperand(2); } @@ -1086,10 +1177,10 @@ public: /// with a value not less than FIRST_TARGET_MEMORY_OPCODE. class MemIntrinsicSDNode : public MemSDNode { public: - MemIntrinsicSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, + MemIntrinsicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs, const SDValue *Ops, unsigned NumOps, EVT MemoryVT, MachineMemOperand *MMO) - : MemSDNode(Opc, dl, VTs, Ops, NumOps, MemoryVT, MMO) { + : MemSDNode(Opc, Order, dl, VTs, Ops, NumOps, MemoryVT, MMO) { } // Methods to support isa and dyn_cast @@ -1119,9 +1210,9 @@ class ShuffleVectorSDNode : public SDNode { const int *Mask; protected: friend class SelectionDAG; - ShuffleVectorSDNode(EVT VT, DebugLoc dl, SDValue N1, SDValue N2, - const int *M) - : SDNode(ISD::VECTOR_SHUFFLE, dl, getSDVTList(VT)), Mask(M) { + ShuffleVectorSDNode(EVT VT, unsigned Order, DebugLoc dl, SDValue N1, + SDValue N2, const int *M) + : SDNode(ISD::VECTOR_SHUFFLE, Order, dl, getSDVTList(VT)), Mask(M) { InitOperands(Ops, N1, N2); } public: @@ -1134,16 +1225,16 @@ public: assert(Idx < getValueType(0).getVectorNumElements() && "Idx out of range!"); return Mask[Idx]; } - + bool isSplat() const { return isSplatMask(Mask, getValueType(0)); } - int getSplatIndex() const { + int getSplatIndex() const { assert(isSplat() && "Cannot get splat index for non-splat!"); EVT VT = getValueType(0); for (unsigned i = 0, e = VT.getVectorNumElements(); i != e; ++i) { - if (Mask[i] != -1) + if (Mask[i] >= 0) return Mask[i]; } - return -1; + llvm_unreachable("Splat with all undef indices?"); } static bool isSplatMask(const int *Mask, EVT VT); @@ -1151,13 +1242,13 @@ public: return N->getOpcode() == ISD::VECTOR_SHUFFLE; } }; - + class ConstantSDNode : public SDNode { const ConstantInt *Value; friend class SelectionDAG; ConstantSDNode(bool isTarget, const ConstantInt *val, EVT VT) : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant, - DebugLoc(), getSDVTList(VT)), Value(val) { + 0, DebugLoc(), getSDVTList(VT)), Value(val) { } public: @@ -1181,7 +1272,7 @@ class ConstantFPSDNode : public SDNode { friend class SelectionDAG; ConstantFPSDNode(bool isTarget, const ConstantFP *val, EVT VT) : SDNode(isTarget ? ISD::TargetConstantFP : ISD::ConstantFP, - DebugLoc(), getSDVTList(VT)), Value(val) { + 0, DebugLoc(), getSDVTList(VT)), Value(val) { } public: @@ -1224,8 +1315,9 @@ class GlobalAddressSDNode : public SDNode { int64_t Offset; unsigned char TargetFlags; friend class SelectionDAG; - GlobalAddressSDNode(unsigned Opc, DebugLoc DL, const GlobalValue *GA, EVT VT, - int64_t o, unsigned char TargetFlags); + GlobalAddressSDNode(unsigned Opc, unsigned Order, DebugLoc DL, + const GlobalValue *GA, EVT VT, int64_t o, + unsigned char TargetFlags); public: const GlobalValue *getGlobal() const { return TheGlobal; } @@ -1247,7 +1339,7 @@ class FrameIndexSDNode : public SDNode { friend class SelectionDAG; FrameIndexSDNode(int fi, EVT VT, bool isTarg) : SDNode(isTarg ? ISD::TargetFrameIndex : ISD::FrameIndex, - DebugLoc(), getSDVTList(VT)), FI(fi) { + 0, DebugLoc(), getSDVTList(VT)), FI(fi) { } public: @@ -1265,7 +1357,7 @@ class JumpTableSDNode : public SDNode { friend class SelectionDAG; JumpTableSDNode(int jti, EVT VT, bool isTarg, unsigned char TF) : SDNode(isTarg ? ISD::TargetJumpTable : ISD::JumpTable, - DebugLoc(), getSDVTList(VT)), JTI(jti), TargetFlags(TF) { + 0, DebugLoc(), getSDVTList(VT)), JTI(jti), TargetFlags(TF) { } public: @@ -1289,23 +1381,22 @@ class ConstantPoolSDNode : public SDNode { friend class SelectionDAG; ConstantPoolSDNode(bool isTarget, const Constant *c, EVT VT, int o, unsigned Align, unsigned char TF) - : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, - DebugLoc(), - getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) { + : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, + DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align), + TargetFlags(TF) { assert(Offset >= 0 && "Offset is too large"); Val.ConstVal = c; } ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v, EVT VT, int o, unsigned Align, unsigned char TF) - : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, - DebugLoc(), - getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) { + : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, 0, + DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align), + TargetFlags(TF) { assert(Offset >= 0 && "Offset is too large"); Val.MachineCPVal = v; Offset |= 1 << (sizeof(unsigned)*CHAR_BIT-1); } public: - bool isMachineConstantPoolEntry() const { return Offset < 0; @@ -1347,7 +1438,7 @@ class TargetIndexSDNode : public SDNode { public: TargetIndexSDNode(int Idx, EVT VT, int64_t Ofs, unsigned char TF) - : SDNode(ISD::TargetIndex, DebugLoc(), getSDVTList(VT)), + : SDNode(ISD::TargetIndex, 0, DebugLoc(), getSDVTList(VT)), TargetFlags(TF), Index(Idx), Offset(Ofs) {} public: @@ -1367,8 +1458,8 @@ class BasicBlockSDNode : public SDNode { /// blocks out of order when they're jumped to, which makes it a bit /// harder. Let's see if we need it first. explicit BasicBlockSDNode(MachineBasicBlock *mbb) - : SDNode(ISD::BasicBlock, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb) { - } + : SDNode(ISD::BasicBlock, 0, DebugLoc(), getSDVTList(MVT::Other)), MBB(mbb) + {} public: MachineBasicBlock *getBasicBlock() const { return MBB; } @@ -1411,7 +1502,7 @@ class SrcValueSDNode : public SDNode { friend class SelectionDAG; /// Create a SrcValue for a general value. explicit SrcValueSDNode(const Value *v) - : SDNode(ISD::SRCVALUE, DebugLoc(), getSDVTList(MVT::Other)), V(v) {} + : SDNode(ISD::SRCVALUE, 0, DebugLoc(), getSDVTList(MVT::Other)), V(v) {} public: /// getValue - return the contained Value. @@ -1421,27 +1512,27 @@ public: return N->getOpcode() == ISD::SRCVALUE; } }; - + class MDNodeSDNode : public SDNode { const MDNode *MD; friend class SelectionDAG; explicit MDNodeSDNode(const MDNode *md) - : SDNode(ISD::MDNODE_SDNODE, DebugLoc(), getSDVTList(MVT::Other)), MD(md) {} + : SDNode(ISD::MDNODE_SDNODE, 0, DebugLoc(), getSDVTList(MVT::Other)), MD(md) + {} public: - + const MDNode *getMD() const { return MD; } - + static bool classof(const SDNode *N) { return N->getOpcode() == ISD::MDNODE_SDNODE; } }; - class RegisterSDNode : public SDNode { unsigned Reg; friend class SelectionDAG; RegisterSDNode(unsigned reg, EVT VT) - : SDNode(ISD::Register, DebugLoc(), getSDVTList(VT)), Reg(reg) { + : SDNode(ISD::Register, 0, DebugLoc(), getSDVTList(VT)), Reg(reg) { } public: @@ -1457,7 +1548,7 @@ class RegisterMaskSDNode : public SDNode { const uint32_t *RegMask; friend class SelectionDAG; RegisterMaskSDNode(const uint32_t *mask) - : SDNode(ISD::RegisterMask, DebugLoc(), getSDVTList(MVT::Untyped)), + : SDNode(ISD::RegisterMask, 0, DebugLoc(), getSDVTList(MVT::Untyped)), RegMask(mask) {} public: @@ -1475,7 +1566,7 @@ class BlockAddressSDNode : public SDNode { friend class SelectionDAG; BlockAddressSDNode(unsigned NodeTy, EVT VT, const BlockAddress *ba, int64_t o, unsigned char Flags) - : SDNode(NodeTy, DebugLoc(), getSDVTList(VT)), + : SDNode(NodeTy, 0, DebugLoc(), getSDVTList(VT)), BA(ba), Offset(o), TargetFlags(Flags) { } public: @@ -1493,8 +1584,8 @@ class EHLabelSDNode : public SDNode { SDUse Chain; MCSymbol *Label; friend class SelectionDAG; - EHLabelSDNode(DebugLoc dl, SDValue ch, MCSymbol *L) - : SDNode(ISD::EH_LABEL, dl, getSDVTList(MVT::Other)), Label(L) { + EHLabelSDNode(unsigned Order, DebugLoc dl, SDValue ch, MCSymbol *L) + : SDNode(ISD::EH_LABEL, Order, dl, getSDVTList(MVT::Other)), Label(L) { InitOperands(&Chain, ch); } public: @@ -1508,11 +1599,11 @@ public: class ExternalSymbolSDNode : public SDNode { const char *Symbol; unsigned char TargetFlags; - + friend class SelectionDAG; ExternalSymbolSDNode(bool isTarget, const char *Sym, unsigned char TF, EVT VT) : SDNode(isTarget ? ISD::TargetExternalSymbol : ISD::ExternalSymbol, - DebugLoc(), getSDVTList(VT)), Symbol(Sym), TargetFlags(TF) { + 0, DebugLoc(), getSDVTList(VT)), Symbol(Sym), TargetFlags(TF) { } public: @@ -1529,7 +1620,7 @@ class CondCodeSDNode : public SDNode { ISD::CondCode Condition; friend class SelectionDAG; explicit CondCodeSDNode(ISD::CondCode Cond) - : SDNode(ISD::CONDCODE, DebugLoc(), getSDVTList(MVT::Other)), + : SDNode(ISD::CONDCODE, 0, DebugLoc(), getSDVTList(MVT::Other)), Condition(Cond) { } public: @@ -1540,15 +1631,16 @@ public: return N->getOpcode() == ISD::CONDCODE; } }; - + /// CvtRndSatSDNode - NOTE: avoid using this node as this may disappear in the /// future and most targets don't support it. class CvtRndSatSDNode : public SDNode { ISD::CvtCode CvtCode; friend class SelectionDAG; - explicit CvtRndSatSDNode(EVT VT, DebugLoc dl, const SDValue *Ops, - unsigned NumOps, ISD::CvtCode Code) - : SDNode(ISD::CONVERT_RNDSAT, dl, getSDVTList(VT), Ops, NumOps), + explicit CvtRndSatSDNode(EVT VT, unsigned Order, DebugLoc dl, + const SDValue *Ops, unsigned NumOps, + ISD::CvtCode Code) + : SDNode(ISD::CONVERT_RNDSAT, Order, dl, getSDVTList(VT), Ops, NumOps), CvtCode(Code) { assert(NumOps == 5 && "wrong number of operations"); } @@ -1566,7 +1658,7 @@ class VTSDNode : public SDNode { EVT ValueType; friend class SelectionDAG; explicit VTSDNode(EVT VT) - : SDNode(ISD::VALUETYPE, DebugLoc(), getSDVTList(MVT::Other)), + : SDNode(ISD::VALUETYPE, 0, DebugLoc(), getSDVTList(MVT::Other)), ValueType(VT) { } public: @@ -1589,10 +1681,11 @@ class LSBaseSDNode : public MemSDNode { */ SDUse Ops[4]; public: - LSBaseSDNode(ISD::NodeType NodeTy, DebugLoc dl, SDValue *Operands, - unsigned numOperands, SDVTList VTs, ISD::MemIndexedMode AM, - EVT MemVT, MachineMemOperand *MMO) - : MemSDNode(NodeTy, dl, VTs, MemVT, MMO) { + LSBaseSDNode(ISD::NodeType NodeTy, unsigned Order, DebugLoc dl, + SDValue *Operands, unsigned numOperands, + SDVTList VTs, ISD::MemIndexedMode AM, EVT MemVT, + MachineMemOperand *MMO) + : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) { SubclassData |= AM << 2; assert(getAddressingMode() == AM && "MemIndexedMode encoding error!"); InitOperands(Ops, Operands, numOperands); @@ -1626,11 +1719,10 @@ public: /// class LoadSDNode : public LSBaseSDNode { friend class SelectionDAG; - LoadSDNode(SDValue *ChainPtrOff, DebugLoc dl, SDVTList VTs, + LoadSDNode(SDValue *ChainPtrOff, unsigned Order, DebugLoc dl, SDVTList VTs, ISD::MemIndexedMode AM, ISD::LoadExtType ETy, EVT MemVT, MachineMemOperand *MMO) - : LSBaseSDNode(ISD::LOAD, dl, ChainPtrOff, 3, - VTs, AM, MemVT, MMO) { + : LSBaseSDNode(ISD::LOAD, Order, dl, ChainPtrOff, 3, VTs, AM, MemVT, MMO) { SubclassData |= (unsigned short)ETy; assert(getExtensionType() == ETy && "LoadExtType encoding error!"); assert(readMem() && "Load MachineMemOperand is not a load!"); @@ -1656,10 +1748,10 @@ public: /// class StoreSDNode : public LSBaseSDNode { friend class SelectionDAG; - StoreSDNode(SDValue *ChainValuePtrOff, DebugLoc dl, SDVTList VTs, - ISD::MemIndexedMode AM, bool isTrunc, EVT MemVT, + StoreSDNode(SDValue *ChainValuePtrOff, unsigned Order, DebugLoc dl, + SDVTList VTs, ISD::MemIndexedMode AM, bool isTrunc, EVT MemVT, MachineMemOperand *MMO) - : LSBaseSDNode(ISD::STORE, dl, ChainValuePtrOff, 4, + : LSBaseSDNode(ISD::STORE, Order, dl, ChainValuePtrOff, 4, VTs, AM, MemVT, MMO) { SubclassData |= (unsigned short)isTrunc; assert(isTruncatingStore() == isTrunc && "isTrunc encoding error!"); @@ -1692,8 +1784,8 @@ public: private: friend class SelectionDAG; - MachineSDNode(unsigned Opc, const DebugLoc DL, SDVTList VTs) - : SDNode(Opc, DL, VTs), MemRefs(0), MemRefsEnd(0) {} + MachineSDNode(unsigned Opc, unsigned Order, const DebugLoc DL, SDVTList VTs) + : SDNode(Opc, Order, DL, VTs), MemRefs(0), MemRefsEnd(0) {} /// LocalOperands - Operands for this instruction, if they fit here. If /// they don't, this field is unused. @@ -1781,7 +1873,7 @@ template <> struct GraphTraits<SDNode*> { /// LargestSDNode - The largest SDNode class. /// -typedef LoadSDNode LargestSDNode; +typedef AtomicSDNode LargestSDNode; /// MostAlignedSDNode - The SDNode class with the greatest alignment /// requirement. diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index 26d0433f3e87c..984796af8644e 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -59,7 +59,7 @@ namespace llvm { // poisoned, so that dangling SlotIndex access can be reliably detected. void setPoison() { intptr_t tmp = reinterpret_cast<intptr_t>(mi); - assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?"); + assert(((tmp & 0x1) == 0x0) && "Pointer already poisoned?"); tmp |= 0x1; mi = reinterpret_cast<MachineInstr*>(tmp); } @@ -162,7 +162,7 @@ namespace llvm { } /// Return true for a valid index. - operator bool() const { return isValid(); } + LLVM_EXPLICIT operator bool() const { return isValid(); } /// Print this index to the given raw_ostream. void print(raw_ostream &os) const; @@ -218,6 +218,13 @@ namespace llvm { return other.getIndex() - getIndex(); } + /// Return the scaled distance from this index to the given one, where all + /// slots on the same instruction have zero distance. + int getInstrDistance(SlotIndex other) const { + return (other.listEntry()->getIndex() - listEntry()->getIndex()) + / Slot_Count; + } + /// isBlock - Returns true if this is a block boundary slot. bool isBlock() const { return getSlot() == Slot_Block; } @@ -672,7 +679,7 @@ namespace llvm { /// performance. Any remaining SlotIndex objects that point to the same /// index are left 'dangling' (much the same as a dangling pointer to a /// freed object) and should not be accessed, except to destruct them. - /// + /// /// Like dangling pointers, access to dangling SlotIndexes can cause /// painful-to-track-down bugs, especially if the memory for the index /// previously pointed to has been re-used. To detect dangling SlotIndex diff --git a/include/llvm/CodeGen/StackMaps.h b/include/llvm/CodeGen/StackMaps.h new file mode 100644 index 0000000000000..e90f22e5b69a6 --- /dev/null +++ b/include/llvm/CodeGen/StackMaps.h @@ -0,0 +1,175 @@ +//===------------------- StackMaps.h - StackMaps ----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_STACKMAPS +#define LLVM_STACKMAPS + +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/MachineInstr.h" +#include <map> +#include <vector> + +namespace llvm { + +class AsmPrinter; +class MCExpr; + +/// \brief MI-level patchpoint operands. +/// +/// MI patchpoint operations take the form: +/// [<def>], <id>, <numBytes>, <target>, <numArgs>, <cc>, ... +/// +/// IR patchpoint intrinsics do not have the <cc> operand because calling +/// convention is part of the subclass data. +/// +/// SD patchpoint nodes do not have a def operand because it is part of the +/// SDValue. +/// +/// Patchpoints following the anyregcc convention are handled specially. For +/// these, the stack map also records the location of the return value and +/// arguments. +class PatchPointOpers { +public: + /// Enumerate the meta operands. + enum { IDPos, NBytesPos, TargetPos, NArgPos, CCPos, MetaEnd }; +private: + const MachineInstr *MI; + bool HasDef; + bool IsAnyReg; +public: + explicit PatchPointOpers(const MachineInstr *MI); + + bool isAnyReg() const { return IsAnyReg; } + bool hasDef() const { return HasDef; } + + unsigned getMetaIdx(unsigned Pos = 0) const { + assert(Pos < MetaEnd && "Meta operand index out of range."); + return (HasDef ? 1 : 0) + Pos; + } + + const MachineOperand &getMetaOper(unsigned Pos) { + return MI->getOperand(getMetaIdx(Pos)); + } + + unsigned getArgIdx() const { return getMetaIdx() + MetaEnd; } + + /// Get the operand index of the variable list of non-argument operands. + /// These hold the "live state". + unsigned getVarIdx() const { + return getMetaIdx() + MetaEnd + + MI->getOperand(getMetaIdx(NArgPos)).getImm(); + } + + /// Get the index at which stack map locations will be recorded. + /// Arguments are not recorded unless the anyregcc convention is used. + unsigned getStackMapStartIdx() const { + if (IsAnyReg) + return getArgIdx(); + return getVarIdx(); + } + + /// \brief Get the next scratch register operand index. + unsigned getNextScratchIdx(unsigned StartIdx = 0) const; +}; + +class StackMaps { +public: + struct Location { + enum LocationType { Unprocessed, Register, Direct, Indirect, Constant, + ConstantIndex }; + LocationType LocType; + unsigned Size; + unsigned Reg; + int64_t Offset; + Location() : LocType(Unprocessed), Size(0), Reg(0), Offset(0) {} + Location(LocationType LocType, unsigned Size, unsigned Reg, int64_t Offset) + : LocType(LocType), Size(Size), Reg(Reg), Offset(Offset) {} + }; + + // Typedef a function pointer for functions that parse sequences of operands + // and return a Location, plus a new "next" operand iterator. + typedef std::pair<Location, MachineInstr::const_mop_iterator> + (*OperandParser)(MachineInstr::const_mop_iterator, + MachineInstr::const_mop_iterator, const TargetMachine&); + + // OpTypes are used to encode information about the following logical + // operand (which may consist of several MachineOperands) for the + // OpParser. + typedef enum { DirectMemRefOp, IndirectMemRefOp, ConstantOp } OpType; + + StackMaps(AsmPrinter &AP, OperandParser OpParser) + : AP(AP), OpParser(OpParser) {} + + /// \brief Generate a stackmap record for a stackmap instruction. + /// + /// MI must be a raw STACKMAP, not a PATCHPOINT. + void recordStackMap(const MachineInstr &MI); + + /// \brief Generate a stackmap record for a patchpoint instruction. + void recordPatchPoint(const MachineInstr &MI); + + /// If there is any stack map data, create a stack map section and serialize + /// the map info into it. This clears the stack map data structures + /// afterwards. + void serializeToStackMapSection(); + +private: + typedef SmallVector<Location, 8> LocationVec; + + struct CallsiteInfo { + const MCExpr *CSOffsetExpr; + unsigned ID; + LocationVec Locations; + CallsiteInfo() : CSOffsetExpr(0), ID(0) {} + CallsiteInfo(const MCExpr *CSOffsetExpr, unsigned ID, + LocationVec Locations) + : CSOffsetExpr(CSOffsetExpr), ID(ID), Locations(Locations) {} + }; + + typedef std::vector<CallsiteInfo> CallsiteInfoList; + + struct ConstantPool { + private: + typedef std::map<int64_t, size_t> ConstantsMap; + std::vector<int64_t> ConstantsList; + ConstantsMap ConstantIndexes; + + public: + size_t getNumConstants() const { return ConstantsList.size(); } + int64_t getConstant(size_t Idx) const { return ConstantsList[Idx]; } + size_t getConstantIndex(int64_t ConstVal) { + size_t NextIdx = ConstantsList.size(); + ConstantsMap::const_iterator I = + ConstantIndexes.insert(ConstantIndexes.end(), + std::make_pair(ConstVal, NextIdx)); + if (I->second == NextIdx) + ConstantsList.push_back(ConstVal); + return I->second; + } + }; + + AsmPrinter &AP; + OperandParser OpParser; + CallsiteInfoList CSInfos; + ConstantPool ConstPool; + + /// This should be called by the MC lowering code _immediately_ before + /// lowering the MI to an MCInst. It records where the operands for the + /// instruction are stored, and outputs a label to record the offset of + /// the call from the start of the text section. In special cases (e.g. AnyReg + /// calling convention) the return register is also recorded if requested. + void recordStackMapOpers(const MachineInstr &MI, uint32_t ID, + MachineInstr::const_mop_iterator MOI, + MachineInstr::const_mop_iterator MOE, + bool recordResult = false); +}; + +} + +#endif // LLVM_STACKMAPS diff --git a/include/llvm/CodeGen/StackProtector.h b/include/llvm/CodeGen/StackProtector.h new file mode 100644 index 0000000000000..d09a933a663b4 --- /dev/null +++ b/include/llvm/CodeGen/StackProtector.h @@ -0,0 +1,127 @@ +//===-- StackProtector.h - Stack Protector Insertion ----------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass inserts stack protectors into functions which need them. A variable +// with a random value in it is stored onto the stack before the local variables +// are allocated. Upon exiting the block, the stored value is checked. If it's +// changed, then there was some sort of violation and the program aborts. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_STACKPROTECTOR_H +#define LLVM_CODEGEN_STACKPROTECTOR_H + +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/Triple.h" +#include "llvm/ADT/ValueMap.h" +#include "llvm/Pass.h" +#include "llvm/Target/TargetLowering.h" + +namespace llvm { +class DominatorTree; +class Function; +class Module; +class PHINode; + +class StackProtector : public FunctionPass { +public: + /// SSPLayoutKind. Stack Smashing Protection (SSP) rules require that + /// vulnerable stack allocations are located close the stack protector. + enum SSPLayoutKind { + SSPLK_None, ///< Did not trigger a stack protector. No effect on data + ///< layout. + SSPLK_LargeArray, ///< Array or nested array >= SSP-buffer-size. Closest + ///< to the stack protector. + SSPLK_SmallArray, ///< Array or nested array < SSP-buffer-size. 2nd closest + ///< to the stack protector. + SSPLK_AddrOf ///< The address of this allocation is exposed and + ///< triggered protection. 3rd closest to the protector. + }; + + /// A mapping of AllocaInsts to their required SSP layout. + typedef ValueMap<const AllocaInst *, SSPLayoutKind> SSPLayoutMap; + +private: + const TargetMachine *TM; + + /// TLI - Keep a pointer of a TargetLowering to consult for determining + /// target type sizes. + const TargetLoweringBase *TLI; + const Triple Trip; + + Function *F; + Module *M; + + DominatorTree *DT; + + /// Layout - Mapping of allocations to the required SSPLayoutKind. + /// StackProtector analysis will update this map when determining if an + /// AllocaInst triggers a stack protector. + SSPLayoutMap Layout; + + /// \brief The minimum size of buffers that will receive stack smashing + /// protection when -fstack-protection is used. + unsigned SSPBufferSize; + + /// VisitedPHIs - The set of PHI nodes visited when determining + /// if a variable's reference has been taken. This set + /// is maintained to ensure we don't visit the same PHI node multiple + /// times. + SmallPtrSet<const PHINode *, 16> VisitedPHIs; + + /// InsertStackProtectors - Insert code into the prologue and epilogue of + /// the function. + /// + /// - The prologue code loads and stores the stack guard onto the stack. + /// - The epilogue checks the value stored in the prologue against the + /// original value. It calls __stack_chk_fail if they differ. + bool InsertStackProtectors(); + + /// CreateFailBB - Create a basic block to jump to when the stack protector + /// check fails. + BasicBlock *CreateFailBB(); + + /// ContainsProtectableArray - Check whether the type either is an array or + /// contains an array of sufficient size so that we need stack protectors + /// for it. + /// \param [out] IsLarge is set to true if a protectable array is found and + /// it is "large" ( >= ssp-buffer-size). In the case of a structure with + /// multiple arrays, this gets set if any of them is large. + bool ContainsProtectableArray(Type *Ty, bool &IsLarge, bool Strong = false, + bool InStruct = false) const; + + /// \brief Check whether a stack allocation has its address taken. + bool HasAddressTaken(const Instruction *AI); + + /// RequiresStackProtector - Check whether or not this function needs a + /// stack protector based upon the stack protector level. + bool RequiresStackProtector(); + +public: + static char ID; // Pass identification, replacement for typeid. + StackProtector() : FunctionPass(ID), TM(0), TLI(0), SSPBufferSize(0) { + initializeStackProtectorPass(*PassRegistry::getPassRegistry()); + } + StackProtector(const TargetMachine *TM) + : FunctionPass(ID), TM(TM), TLI(0), Trip(TM->getTargetTriple()), + SSPBufferSize(8) { + initializeStackProtectorPass(*PassRegistry::getPassRegistry()); + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addPreserved<DominatorTree>(); + } + + SSPLayoutKind getSSPLayout(const AllocaInst *AI) const; + + virtual bool runOnFunction(Function &Fn); +}; +} // end namespace llvm + +#endif // LLVM_CODEGEN_STACKPROTECTOR_H diff --git a/include/llvm/CodeGen/TargetSchedule.h b/include/llvm/CodeGen/TargetSchedule.h index 3e22252eeac13..8ef26b7ca5480 100644 --- a/include/llvm/CodeGen/TargetSchedule.h +++ b/include/llvm/CodeGen/TargetSchedule.h @@ -84,9 +84,6 @@ public: /// \brief Maximum number of micro-ops that may be scheduled per cycle. unsigned getIssueWidth() const { return SchedModel.IssueWidth; } - /// \brief Number of cycles the OOO processor is expected to hide. - unsigned getILPWindow() const { return SchedModel.ILPWindow; } - /// \brief Return the number of issue slots required for this MI. unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC = 0) const; @@ -131,18 +128,23 @@ public: return ResourceLCM; } + /// \brief Number of micro-ops that may be buffered for OOO execution. + unsigned getMicroOpBufferSize() const { return SchedModel.MicroOpBufferSize; } + + /// \brief Number of resource units that may be buffered for OOO execution. + /// \return The buffer size in resource units or -1 for unlimited. + int getResourceBufferSize(unsigned PIdx) const { + return SchedModel.getProcResource(PIdx)->BufferSize; + } + /// \brief Compute operand latency based on the available machine model. /// - /// Computes and return the latency of the given data dependent def and use + /// Compute and return the latency of the given data dependent def and use /// when the operand indices are already known. UseMI may be NULL for an /// unknown user. - /// - /// FindMin may be set to get the minimum vs. expected latency. Minimum - /// latency is used for scheduling groups, while expected latency is for - /// instruction cost and critical path. unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, - const MachineInstr *UseMI, unsigned UseOperIdx, - bool FindMin) const; + const MachineInstr *UseMI, unsigned UseOperIdx) + const; /// \brief Compute the instruction latency based on the available machine /// model. @@ -150,19 +152,19 @@ public: /// Compute and return the expected latency of this instruction independent of /// a particular use. computeOperandLatency is the prefered API, but this is /// occasionally useful to help estimate instruction cost. - unsigned computeInstrLatency(const MachineInstr *MI) const; + /// + /// If UseDefaultDefLatency is false and no new machine sched model is + /// present this method falls back to TII->getInstrLatency with an empty + /// instruction itinerary (this is so we preserve the previous behavior of the + /// if converter after moving it to TargetSchedModel). + unsigned computeInstrLatency(const MachineInstr *MI, + bool UseDefaultDefLatency = true) const; /// \brief Output dependency latency of a pair of defs of the same register. /// /// This is typically one cycle. unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefIdx, const MachineInstr *DepMI) const; - -private: - /// getDefLatency is a helper for computeOperandLatency. Return the - /// instruction's latency if operand lookup is not required. - /// Otherwise return -1. - int getDefLatency(const MachineInstr *DefMI, bool FindMin) const; }; } // namespace llvm diff --git a/include/llvm/CodeGen/ValueTypes.h b/include/llvm/CodeGen/ValueTypes.h index ec48b67b993c2..79f323341fd07 100644 --- a/include/llvm/CodeGen/ValueTypes.h +++ b/include/llvm/CodeGen/ValueTypes.h @@ -27,9 +27,9 @@ namespace llvm { class LLVMContext; struct EVT; - /// MVT - Machine Value Type. Every type that is supported natively by some - /// processor targeted by LLVM occurs here. This means that any legal value - /// type can be represented by a MVT. + /// MVT - Machine Value Type. Every type that is supported natively by some + /// processor targeted by LLVM occurs here. This means that any legal value + /// type can be represented by an MVT. class MVT { public: enum SimpleValueType { @@ -67,40 +67,45 @@ namespace llvm { v32i1 = 17, // 32 x i1 v64i1 = 18, // 64 x i1 - v2i8 = 19, // 2 x i8 - v4i8 = 20, // 4 x i8 - v8i8 = 21, // 8 x i8 - v16i8 = 22, // 16 x i8 - v32i8 = 23, // 32 x i8 - v64i8 = 24, // 64 x i8 - v1i16 = 25, // 1 x i16 - v2i16 = 26, // 2 x i16 - v4i16 = 27, // 4 x i16 - v8i16 = 28, // 8 x i16 - v16i16 = 29, // 16 x i16 - v32i16 = 30, // 32 x i16 - v1i32 = 31, // 1 x i32 - v2i32 = 32, // 2 x i32 - v4i32 = 33, // 4 x i32 - v8i32 = 34, // 8 x i32 - v16i32 = 35, // 16 x i32 - v1i64 = 36, // 1 x i64 - v2i64 = 37, // 2 x i64 - v4i64 = 38, // 4 x i64 - v8i64 = 39, // 8 x i64 - v16i64 = 40, // 16 x i64 + v1i8 = 19, // 1 x i8 + v2i8 = 20, // 2 x i8 + v4i8 = 21, // 4 x i8 + v8i8 = 22, // 8 x i8 + v16i8 = 23, // 16 x i8 + v32i8 = 24, // 32 x i8 + v64i8 = 25, // 64 x i8 + v1i16 = 26, // 1 x i16 + v2i16 = 27, // 2 x i16 + v4i16 = 28, // 4 x i16 + v8i16 = 29, // 8 x i16 + v16i16 = 30, // 16 x i16 + v32i16 = 31, // 32 x i16 + v1i32 = 32, // 1 x i32 + v2i32 = 33, // 2 x i32 + v4i32 = 34, // 4 x i32 + v8i32 = 35, // 8 x i32 + v16i32 = 36, // 16 x i32 + v1i64 = 37, // 1 x i64 + v2i64 = 38, // 2 x i64 + v4i64 = 39, // 4 x i64 + v8i64 = 40, // 8 x i64 + v16i64 = 41, // 16 x i64 FIRST_INTEGER_VECTOR_VALUETYPE = v2i1, LAST_INTEGER_VECTOR_VALUETYPE = v16i64, - v2f16 = 41, // 2 x f16 - v2f32 = 42, // 2 x f32 - v4f32 = 43, // 4 x f32 - v8f32 = 44, // 8 x f32 - v16f32 = 45, // 16 x f32 - v2f64 = 46, // 2 x f64 - v4f64 = 47, // 4 x f64 - v8f64 = 48, // 8 x f64 + v2f16 = 42, // 2 x f16 + v4f16 = 43, // 4 x f16 + v8f16 = 44, // 8 x f16 + v1f32 = 45, // 1 x f32 + v2f32 = 46, // 2 x f32 + v4f32 = 47, // 4 x f32 + v8f32 = 48, // 8 x f32 + v16f32 = 49, // 16 x f32 + v1f64 = 50, // 1 x f64 + v2f64 = 51, // 2 x f64 + v4f64 = 52, // 4 x f64 + v8f64 = 53, // 8 x f64 FIRST_FP_VECTOR_VALUETYPE = v2f16, LAST_FP_VECTOR_VALUETYPE = v8f64, @@ -108,17 +113,17 @@ namespace llvm { FIRST_VECTOR_VALUETYPE = v2i1, LAST_VECTOR_VALUETYPE = v8f64, - x86mmx = 49, // This is an X86 MMX value + x86mmx = 54, // This is an X86 MMX value - Glue = 50, // This glues nodes together during pre-RA sched + Glue = 55, // This glues nodes together during pre-RA sched - isVoid = 51, // This has no value + isVoid = 56, // This has no value - Untyped = 52, // This value takes a register, but has + Untyped = 57, // This value takes a register, but has // unspecified type. The register class // will be determined by the opcode. - LAST_VALUETYPE = 53, // This always remains at the end of the list. + LAST_VALUETYPE = 58, // This always remains at the end of the list. // This is the current maximum for LAST_VALUETYPE. // MVT::MAX_ALLOWED_VALUETYPE is used for asserts and to size bit vectors @@ -203,7 +208,7 @@ namespace llvm { bool is64BitVector() const { return (SimpleTy == MVT::v8i8 || SimpleTy == MVT::v4i16 || SimpleTy == MVT::v2i32 || SimpleTy == MVT::v1i64 || - SimpleTy == MVT::v2f32); + SimpleTy == MVT::v1f64 || SimpleTy == MVT::v2f32); } /// is128BitVector - Return true if this is a 128-bit vector type. @@ -265,6 +270,7 @@ namespace llvm { case v16i1 : case v32i1 : case v64i1: return i1; + case v1i8 : case v2i8 : case v4i8 : case v8i8 : @@ -287,11 +293,15 @@ namespace llvm { case v4i64: case v8i64: case v16i64: return i64; - case v2f16: return f16; + case v2f16: + case v4f16: + case v8f16: return f16; + case v1f32: case v2f32: case v4f32: case v8f32: case v16f32: return f32; + case v1f64: case v2f64: case v4f64: case v8f64: return f64; @@ -318,6 +328,7 @@ namespace llvm { case v8i16: case v8i32: case v8i64: + case v8f16: case v8f32: case v8f64: return 8; case v4i1: @@ -325,6 +336,7 @@ namespace llvm { case v4i16: case v4i32: case v4i64: + case v4f16: case v4f32: case v4f64: return 4; case v2i1: @@ -335,14 +347,21 @@ namespace llvm { case v2f16: case v2f32: case v2f64: return 2; + case v1i8: case v1i16: case v1i32: - case v1i64: return 1; + case v1i64: + case v1f32: + case v1f64: return 1; } } unsigned getSizeInBits() const { switch (SimpleTy) { + default: + llvm_unreachable("getSizeInBits called on extended MVT."); + case Other: + llvm_unreachable("Value type is non-standard value, Other."); case iPTR: llvm_unreachable("Value type size is target-dependent. Ask TLI."); case iPTRAny: @@ -352,12 +371,11 @@ namespace llvm { llvm_unreachable("Value type is overloaded."); case Metadata: llvm_unreachable("Value type is metadata."); - default: - llvm_unreachable("getSizeInBits called on extended MVT."); case i1 : return 1; case v2i1: return 2; case v4i1: return 4; case i8 : + case v1i8: case v8i1: return 8; case i16 : case f16: @@ -370,6 +388,7 @@ namespace llvm { case v4i8: case v2i16: case v2f16: + case v1f32: case v1i32: return 32; case x86mmx: case f64 : @@ -379,7 +398,9 @@ namespace llvm { case v4i16: case v2i32: case v1i64: - case v2f32: return 64; + case v4f16: + case v2f32: + case v1f64: return 64; case f80 : return 80; case f128: case ppcf128: @@ -388,6 +409,7 @@ namespace llvm { case v8i16: case v4i32: case v2i64: + case v8f16: case v4f32: case v2f64: return 128; case v32i8: @@ -488,6 +510,7 @@ namespace llvm { if (NumElements == 64) return MVT::v64i1; break; case MVT::i8: + if (NumElements == 1) return MVT::v1i8; if (NumElements == 2) return MVT::v2i8; if (NumElements == 4) return MVT::v4i8; if (NumElements == 8) return MVT::v8i8; @@ -519,14 +542,18 @@ namespace llvm { break; case MVT::f16: if (NumElements == 2) return MVT::v2f16; + if (NumElements == 4) return MVT::v4f16; + if (NumElements == 8) return MVT::v8f16; break; case MVT::f32: + if (NumElements == 1) return MVT::v1f32; if (NumElements == 2) return MVT::v2f32; if (NumElements == 4) return MVT::v4f32; if (NumElements == 8) return MVT::v8f32; if (NumElements == 16) return MVT::v16f32; break; case MVT::f64: + if (NumElements == 1) return MVT::v1f64; if (NumElements == 2) return MVT::v2f64; if (NumElements == 4) return MVT::v4f64; if (NumElements == 8) return MVT::v8f64; diff --git a/include/llvm/CodeGen/ValueTypes.td b/include/llvm/CodeGen/ValueTypes.td index da269859491ba..b5fa0e8c6a231 100644 --- a/include/llvm/CodeGen/ValueTypes.td +++ b/include/llvm/CodeGen/ValueTypes.td @@ -26,7 +26,7 @@ def i16 : ValueType<16 , 3>; // 16-bit integer value def i32 : ValueType<32 , 4>; // 32-bit integer value def i64 : ValueType<64 , 5>; // 64-bit integer value def i128 : ValueType<128, 6>; // 128-bit integer value -def f16 : ValueType<16 , 7>; // 32-bit floating point value +def f16 : ValueType<16 , 7>; // 16-bit floating point value def f32 : ValueType<32 , 8>; // 32-bit floating point value def f64 : ValueType<64 , 9>; // 64-bit floating point value def f80 : ValueType<80 , 10>; // 80-bit floating point value @@ -39,43 +39,48 @@ def v8i1 : ValueType<8 , 15>; // 8 x i1 vector value def v16i1 : ValueType<16, 16>; // 16 x i1 vector value def v32i1 : ValueType<32 , 17>; // 32 x i1 vector value def v64i1 : ValueType<64 , 18>; // 64 x i1 vector value -def v2i8 : ValueType<16 , 19>; // 2 x i8 vector value -def v4i8 : ValueType<32 , 20>; // 4 x i8 vector value -def v8i8 : ValueType<64 , 21>; // 8 x i8 vector value -def v16i8 : ValueType<128, 22>; // 16 x i8 vector value -def v32i8 : ValueType<256, 23>; // 32 x i8 vector value -def v64i8 : ValueType<512, 24>; // 64 x i8 vector value -def v1i16 : ValueType<16 , 25>; // 1 x i16 vector value -def v2i16 : ValueType<32 , 26>; // 2 x i16 vector value -def v4i16 : ValueType<64 , 27>; // 4 x i16 vector value -def v8i16 : ValueType<128, 28>; // 8 x i16 vector value -def v16i16 : ValueType<256, 29>; // 16 x i16 vector value -def v32i16 : ValueType<512, 30>; // 32 x i16 vector value -def v1i32 : ValueType<32 , 31>; // 1 x i32 vector value -def v2i32 : ValueType<64 , 32>; // 2 x i32 vector value -def v4i32 : ValueType<128, 33>; // 4 x i32 vector value -def v8i32 : ValueType<256, 34>; // 8 x i32 vector value -def v16i32 : ValueType<512, 35>; // 16 x i32 vector value -def v1i64 : ValueType<64 , 36>; // 1 x i64 vector value -def v2i64 : ValueType<128, 37>; // 2 x i64 vector value -def v4i64 : ValueType<256, 38>; // 4 x i64 vector value -def v8i64 : ValueType<512, 39>; // 8 x i64 vector value -def v16i64 : ValueType<1024,40>; // 16 x i64 vector value +def v1i8 : ValueType<16, 19>; // 1 x i8 vector value +def v2i8 : ValueType<16 , 20>; // 2 x i8 vector value +def v4i8 : ValueType<32 , 21>; // 4 x i8 vector value +def v8i8 : ValueType<64 , 22>; // 8 x i8 vector value +def v16i8 : ValueType<128, 23>; // 16 x i8 vector value +def v32i8 : ValueType<256, 24>; // 32 x i8 vector value +def v64i8 : ValueType<512, 25>; // 64 x i8 vector value +def v1i16 : ValueType<16 , 26>; // 1 x i16 vector value +def v2i16 : ValueType<32 , 27>; // 2 x i16 vector value +def v4i16 : ValueType<64 , 28>; // 4 x i16 vector value +def v8i16 : ValueType<128, 29>; // 8 x i16 vector value +def v16i16 : ValueType<256, 30>; // 16 x i16 vector value +def v32i16 : ValueType<512, 31>; // 32 x i16 vector value +def v1i32 : ValueType<32 , 32>; // 1 x i32 vector value +def v2i32 : ValueType<64 , 33>; // 2 x i32 vector value +def v4i32 : ValueType<128, 34>; // 4 x i32 vector value +def v8i32 : ValueType<256, 35>; // 8 x i32 vector value +def v16i32 : ValueType<512, 36>; // 16 x i32 vector value +def v1i64 : ValueType<64 , 37>; // 1 x i64 vector value +def v2i64 : ValueType<128, 38>; // 2 x i64 vector value +def v4i64 : ValueType<256, 39>; // 4 x i64 vector value +def v8i64 : ValueType<512, 40>; // 8 x i64 vector value +def v16i64 : ValueType<1024,41>; // 16 x i64 vector value -def v2f16 : ValueType<32 , 41>; // 2 x f16 vector value -def v2f32 : ValueType<64 , 42>; // 2 x f32 vector value -def v4f32 : ValueType<128, 43>; // 4 x f32 vector value -def v8f32 : ValueType<256, 44>; // 8 x f32 vector value -def v16f32 : ValueType<512, 45>; // 16 x f32 vector value -def v2f64 : ValueType<128, 46>; // 2 x f64 vector value -def v4f64 : ValueType<256, 47>; // 4 x f64 vector value -def v8f64 : ValueType<512, 48>; // 8 x f64 vector value +def v2f16 : ValueType<32 , 42>; // 2 x f16 vector value +def v4f16 : ValueType<64 , 43>; // 4 x f16 vector value +def v8f16 : ValueType<128, 44>; // 8 x f16 vector value +def v1f32 : ValueType<32 , 45>; // 1 x f32 vector value +def v2f32 : ValueType<64 , 46>; // 2 x f32 vector value +def v4f32 : ValueType<128, 47>; // 4 x f32 vector value +def v8f32 : ValueType<256, 48>; // 8 x f32 vector value +def v16f32 : ValueType<512, 49>; // 16 x f32 vector value +def v1f64 : ValueType<64, 50>; // 1 x f64 vector value +def v2f64 : ValueType<128, 51>; // 2 x f64 vector value +def v4f64 : ValueType<256, 52>; // 4 x f64 vector value +def v8f64 : ValueType<512, 53>; // 8 x f64 vector value -def x86mmx : ValueType<64 , 49>; // X86 MMX value -def FlagVT : ValueType<0 , 50>; // Pre-RA sched glue -def isVoid : ValueType<0 , 51>; // Produces no value -def untyped: ValueType<8 , 52>; // Produces an untyped value +def x86mmx : ValueType<64 , 54>; // X86 MMX value +def FlagVT : ValueType<0 , 55>; // Pre-RA sched glue +def isVoid : ValueType<0 , 56>; // Produces no value +def untyped: ValueType<8 , 57>; // Produces an untyped value def MetadataVT: ValueType<0, 250>; // Metadata // Pseudo valuetype mapped to the current pointer size to any address space. |