diff options
| author | dim <dim@FreeBSD.org> | 2011-02-20 12:57:14 +0000 |
|---|---|---|
| committer | dim <dim@FreeBSD.org> | 2011-02-20 12:57:14 +0000 |
| commit | cbb70ce070d220642b038ea101d9c0f9fbf860d6 (patch) | |
| tree | d2b61ce94e654cb01a254d2195259db5f9cc3f3c /include/llvm/CodeGen | |
| parent | 4ace901e87dac5bbbac78ed325e75462e48e386e (diff) | |
| download | FreeBSD-src-cbb70ce070d220642b038ea101d9c0f9fbf860d6.zip FreeBSD-src-cbb70ce070d220642b038ea101d9c0f9fbf860d6.tar.gz | |
Vendor import of llvm trunk r126079:
http://llvm.org/svn/llvm-project/llvm/trunk@126079
Diffstat (limited to 'include/llvm/CodeGen')
57 files changed, 3554 insertions, 682 deletions
diff --git a/include/llvm/CodeGen/Analysis.h b/include/llvm/CodeGen/Analysis.h index f33a9db..78bf9fc 100644 --- a/include/llvm/CodeGen/Analysis.h +++ b/include/llvm/CodeGen/Analysis.h @@ -23,14 +23,16 @@ namespace llvm { -class TargetLowering; class GlobalVariable; +class TargetLowering; +class SDNode; +class SelectionDAG; /// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence /// of insertvalue or extractvalue indices that identify a member, return /// the linearized index of the start of the member. /// -unsigned ComputeLinearIndex(const TargetLowering &TLI, const Type *Ty, +unsigned ComputeLinearIndex(const Type *Ty, const unsigned *Indices, const unsigned *IndicesEnd, unsigned CurIndex = 0); @@ -52,7 +54,7 @@ GlobalVariable *ExtractTypeInfo(Value *V); /// hasInlineAsmMemConstraint - Return true if the inline asm instruction being /// processed uses a memory 'm' constraint. -bool hasInlineAsmMemConstraint(std::vector<InlineAsm::ConstraintInfo> &CInfos, +bool hasInlineAsmMemConstraint(InlineAsm::ConstraintInfoVector &CInfos, const TargetLowering &TLI); /// getFCmpCondCode - Return the ISD condition code corresponding to @@ -75,6 +77,9 @@ ISD::CondCode getICmpCondCode(ICmpInst::Predicate Pred); bool isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, const TargetLowering &TLI); +bool isInTailCallPosition(SelectionDAG &DAG, SDNode *Node, + const TargetLowering &TLI); + } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h index b018603..357b933 100644 --- a/include/llvm/CodeGen/AsmPrinter.h +++ b/include/llvm/CodeGen/AsmPrinter.h @@ -17,7 +17,7 @@ #define LLVM_CODEGEN_ASMPRINTER_H #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/Support/DebugLoc.h" +#include "llvm/Support/DataTypes.h" namespace llvm { class BlockAddress; @@ -49,6 +49,7 @@ namespace llvm { class MCSection; class MCStreamer; class MCSymbol; + class MDNode; class DwarfDebug; class DwarfException; class Mangler; @@ -388,7 +389,7 @@ namespace llvm { /// frame. void EmitFrameMoves(const std::vector<MachineMove> &Moves, MCSymbol *BaseLabel, bool isEH) const; - + void EmitCFIFrameMoves(const std::vector<MachineMove> &Moves) const; //===------------------------------------------------------------------===// // Inline Asm Support @@ -432,7 +433,7 @@ namespace llvm { mutable unsigned SetCounter; /// EmitInlineAsm - Emit a blob of inline asm to the output streamer. - void EmitInlineAsm(StringRef Str, unsigned LocCookie) const; + void EmitInlineAsm(StringRef Str, const MDNode *LocMDNode = 0) const; /// EmitInlineAsm - This method formats and emits the specified machine /// instruction that is an inline asm. diff --git a/include/llvm/CodeGen/BinaryObject.h b/include/llvm/CodeGen/BinaryObject.h index 3ade7c9..8c1431f 100644 --- a/include/llvm/CodeGen/BinaryObject.h +++ b/include/llvm/CodeGen/BinaryObject.h @@ -16,7 +16,7 @@ #define LLVM_CODEGEN_BINARYOBJECT_H #include "llvm/CodeGen/MachineRelocation.h" -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include <string> #include <vector> diff --git a/include/llvm/CodeGen/CalcSpillWeights.h b/include/llvm/CodeGen/CalcSpillWeights.h index 240734f..853ebf9 100644 --- a/include/llvm/CodeGen/CalcSpillWeights.h +++ b/include/llvm/CodeGen/CalcSpillWeights.h @@ -20,6 +20,26 @@ namespace llvm { class LiveIntervals; class MachineLoopInfo; + /// normalizeSpillWeight - The spill weight of a live interval is computed as: + /// + /// (sum(use freq) + sum(def freq)) / (K + size) + /// + /// @param UseDefFreq Expected number of executed use and def instructions + /// per function call. Derived from block frequencies. + /// @param Size Size of live interval as returnexd by getSize() + /// + static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size) { + // The magic constant 200 corresponds to approx. 25 instructions since + // SlotIndexes allocate 8 slots per instruction. + // + // The constant is added to avoid depending too much on accidental SlotIndex + // gaps for small intervals. The effect is that small intervals have a spill + // weight that is mostly proportional to the number of uses, while large + // intervals get a spill weight that is closer to a use density. + // + return UseDefFreq / (Size + 200); + } + /// VirtRegAuxInfo - Calculate auxiliary information for a virtual /// register such as its spill weight and allocation hint. class VirtRegAuxInfo { @@ -48,7 +68,9 @@ namespace llvm { public: static char ID; - CalculateSpillWeights() : MachineFunctionPass(ID) {} + CalculateSpillWeights() : MachineFunctionPass(ID) { + initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); + } virtual void getAnalysisUsage(AnalysisUsage &au) const; diff --git a/include/llvm/CodeGen/CallingConvLower.h b/include/llvm/CodeGen/CallingConvLower.h index 6fb8436..2a9bbdf 100644 --- a/include/llvm/CodeGen/CallingConvLower.h +++ b/include/llvm/CodeGen/CallingConvLower.h @@ -57,14 +57,14 @@ private: LocInfo HTP : 6; /// ValVT - The type of the value being assigned. - EVT ValVT; + MVT ValVT; /// LocVT - The type of the location being assigned to. - EVT LocVT; + MVT LocVT; public: - static CCValAssign getReg(unsigned ValNo, EVT ValVT, - unsigned RegNo, EVT LocVT, + static CCValAssign getReg(unsigned ValNo, MVT ValVT, + unsigned RegNo, MVT LocVT, LocInfo HTP) { CCValAssign Ret; Ret.ValNo = ValNo; @@ -77,8 +77,8 @@ public: return Ret; } - static CCValAssign getCustomReg(unsigned ValNo, EVT ValVT, - unsigned RegNo, EVT LocVT, + static CCValAssign getCustomReg(unsigned ValNo, MVT ValVT, + unsigned RegNo, MVT LocVT, LocInfo HTP) { CCValAssign Ret; Ret = getReg(ValNo, ValVT, RegNo, LocVT, HTP); @@ -86,8 +86,8 @@ public: return Ret; } - static CCValAssign getMem(unsigned ValNo, EVT ValVT, - unsigned Offset, EVT LocVT, + static CCValAssign getMem(unsigned ValNo, MVT ValVT, + unsigned Offset, MVT LocVT, LocInfo HTP) { CCValAssign Ret; Ret.ValNo = ValNo; @@ -100,8 +100,8 @@ public: return Ret; } - static CCValAssign getCustomMem(unsigned ValNo, EVT ValVT, - unsigned Offset, EVT LocVT, + static CCValAssign getCustomMem(unsigned ValNo, MVT ValVT, + unsigned Offset, MVT LocVT, LocInfo HTP) { CCValAssign Ret; Ret = getMem(ValNo, ValVT, Offset, LocVT, HTP); @@ -110,7 +110,7 @@ public: } unsigned getValNo() const { return ValNo; } - EVT getValVT() const { return ValVT; } + MVT getValVT() const { return ValVT; } bool isRegLoc() const { return !isMem; } bool isMemLoc() const { return isMem; } @@ -119,7 +119,7 @@ public: unsigned getLocReg() const { assert(isRegLoc()); return Loc; } unsigned getLocMemOffset() const { assert(isMemLoc()); return Loc; } - EVT getLocVT() const { return LocVT; } + MVT getLocVT() const { return LocVT; } LocInfo getLocInfo() const { return HTP; } bool isExtInLoc() const { @@ -129,16 +129,16 @@ public: }; /// CCAssignFn - This function assigns a location for Val, updating State to -/// reflect the change. -typedef bool CCAssignFn(unsigned ValNo, EVT ValVT, - EVT LocVT, CCValAssign::LocInfo LocInfo, +/// reflect the change. It returns 'true' if it failed to handle Val. +typedef bool CCAssignFn(unsigned ValNo, MVT ValVT, + MVT LocVT, CCValAssign::LocInfo LocInfo, ISD::ArgFlagsTy ArgFlags, CCState &State); /// CCCustomFn - This function assigns a location for Val, possibly updating /// all args to reflect changes and indicates if it handled it. It must set /// isCustom if it handles the arg and returns true. -typedef bool CCCustomFn(unsigned &ValNo, EVT &ValVT, - EVT &LocVT, CCValAssign::LocInfo &LocInfo, +typedef bool CCCustomFn(unsigned &ValNo, MVT &ValVT, + MVT &LocVT, CCValAssign::LocInfo &LocInfo, ISD::ArgFlagsTy &ArgFlags, CCState &State); /// CCState - This class holds information needed while lowering arguments and @@ -198,7 +198,7 @@ public: /// AnalyzeCallOperands - Same as above except it takes vectors of types /// and argument flags. - void AnalyzeCallOperands(SmallVectorImpl<EVT> &ArgVTs, + void AnalyzeCallOperands(SmallVectorImpl<MVT> &ArgVTs, SmallVectorImpl<ISD::ArgFlagsTy> &Flags, CCAssignFn Fn); @@ -209,7 +209,7 @@ public: /// AnalyzeCallResult - Same as above except it's specialized for calls which /// produce a single value. - void AnalyzeCallResult(EVT VT, CCAssignFn Fn); + void AnalyzeCallResult(MVT VT, CCAssignFn Fn); /// getFirstUnallocated - Return the first unallocated register in the set, or /// NumRegs if they are all allocated. @@ -284,8 +284,8 @@ public: // HandleByVal - Allocate a stack slot large enough to pass an argument by // value. The size and alignment information of the argument is encoded in its // parameter attribute. - void HandleByVal(unsigned ValNo, EVT ValVT, - EVT LocVT, CCValAssign::LocInfo LocInfo, + void HandleByVal(unsigned ValNo, MVT ValVT, + MVT LocVT, CCValAssign::LocInfo LocInfo, int MinSize, int MinAlign, ISD::ArgFlagsTy ArgFlags); private: diff --git a/include/llvm/CodeGen/EdgeBundles.h b/include/llvm/CodeGen/EdgeBundles.h new file mode 100644 index 0000000..2c5215a --- /dev/null +++ b/include/llvm/CodeGen/EdgeBundles.h @@ -0,0 +1,61 @@ +//===-------- EdgeBundles.h - Bundles of CFG edges --------------*- c++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// The EdgeBundles analysis forms equivalence classes of CFG edges such that all +// edges leaving a machine basic block are in the same bundle, and all edges +// leaving a basic block are in the same bundle. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_EDGEBUNDLES_H +#define LLVM_CODEGEN_EDGEBUNDLES_H + +#include "llvm/ADT/IntEqClasses.h" +#include "llvm/CodeGen/MachineFunctionPass.h" + +namespace llvm { + +class EdgeBundles : public MachineFunctionPass { + const MachineFunction *MF; + + /// EC - Each edge bundle is an equivalence class. The keys are: + /// 2*BB->getNumber() -> Ingoing bundle. + /// 2*BB->getNumber()+1 -> Outgoing bundle. + IntEqClasses EC; + +public: + static char ID; + EdgeBundles() : MachineFunctionPass(ID) {} + + /// getBundle - Return the ingoing (Out = false) or outgoing (Out = true) + /// bundle number for basic block #N + unsigned getBundle(unsigned N, bool Out) const { return EC[2 * N + Out]; } + + /// getNumBundles - Return the total number of bundles in the CFG. + unsigned getNumBundles() const { return EC.getNumClasses(); } + + /// getMachineFunction - Return the last machine function computed. + const MachineFunction *getMachineFunction() const { return MF; } + + /// view - Visualize the annotated bipartite CFG with Graphviz. + void view() const; + +private: + virtual bool runOnMachineFunction(MachineFunction&); + virtual void getAnalysisUsage(AnalysisUsage&) const; +}; + +/// Specialize WriteGraph, the standard implementation won't work. +raw_ostream &WriteGraph(raw_ostream &O, const EdgeBundles &G, + bool ShortNames = false, + const std::string &Title = ""); + +} // end namespace llvm + +#endif diff --git a/include/llvm/CodeGen/FastISel.h b/include/llvm/CodeGen/FastISel.h index 79b1554..fbb1200 100644 --- a/include/llvm/CodeGen/FastISel.h +++ b/include/llvm/CodeGen/FastISel.h @@ -15,9 +15,6 @@ #define LLVM_CODEGEN_FASTISEL_H #include "llvm/ADT/DenseMap.h" -#ifndef NDEBUG -#include "llvm/ADT/SmallSet.h" -#endif #include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/MachineBasicBlock.h" @@ -39,6 +36,7 @@ class TargetLowering; class TargetMachine; class TargetRegisterClass; class TargetRegisterInfo; +class LoadInst; /// FastISel - This is a fast-path instruction selection class that /// generates poor code and doesn't support illegal types or non-trivial @@ -102,7 +100,16 @@ public: /// index value. std::pair<unsigned, bool> getRegForGEPIndex(const Value *V); - /// recomputeInsertPt - Reset InsertPt to prepare for insterting instructions + /// TryToFoldLoad - 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. + virtual bool TryToFoldLoad(MachineInstr * /*MI*/, unsigned /*OpNo*/, + const LoadInst * /*LI*/) { + return false; + } + + /// recomputeInsertPt - Reset InsertPt to prepare for inserting instructions /// into the current block. void recomputeInsertPt(); diff --git a/include/llvm/CodeGen/FunctionLoweringInfo.h b/include/llvm/CodeGen/FunctionLoweringInfo.h index f17fe5a..27631b7 100644 --- a/include/llvm/CodeGen/FunctionLoweringInfo.h +++ b/include/llvm/CodeGen/FunctionLoweringInfo.h @@ -19,6 +19,7 @@ #include "llvm/Instructions.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallVector.h" #ifndef NDEBUG #include "llvm/ADT/SmallSet.h" @@ -27,6 +28,7 @@ #include "llvm/CodeGen/ISDOpcodes.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/Support/CallSite.h" +#include "llvm/Target/TargetRegisterInfo.h" #include <vector> namespace llvm { @@ -104,9 +106,8 @@ public: LiveOutInfo() : NumSignBits(0), KnownOne(1, 0), KnownZero(1, 0) {} }; - /// LiveOutRegInfo - Information about live out vregs, indexed by their - /// register number offset by 'FirstVirtualRegister'. - std::vector<LiveOutInfo> LiveOutRegInfo; + /// LiveOutRegInfo - Information about live out vregs. + IndexedMap<LiveOutInfo, VirtReg2IndexFunctor> LiveOutRegInfo; /// PHINodesToUpdate - A list of phi instructions whose operand list will /// be updated after processing the current basic block. diff --git a/include/llvm/CodeGen/GCMetadata.h b/include/llvm/CodeGen/GCMetadata.h index b401068..45469ed 100644 --- a/include/llvm/CodeGen/GCMetadata.h +++ b/include/llvm/CodeGen/GCMetadata.h @@ -36,6 +36,7 @@ #include "llvm/Pass.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/StringMap.h" +#include "llvm/Support/DebugLoc.h" namespace llvm { class AsmPrinter; @@ -59,8 +60,10 @@ namespace llvm { struct GCPoint { GC::PointKind Kind; //< The kind of the safe point. MCSymbol *Label; //< A label. + DebugLoc Loc; - GCPoint(GC::PointKind K, MCSymbol *L) : Kind(K), Label(L) {} + GCPoint(GC::PointKind K, MCSymbol *L, DebugLoc DL) + : Kind(K), Label(L), Loc(DL) {} }; /// GCRoot - Metadata for a pointer to an object managed by the garbage @@ -121,8 +124,8 @@ namespace llvm { /// addSafePoint - Notes the existence of a safe point. Num is the ID of the /// label just prior to the safe point (if the code generator is using /// MachineModuleInfo). - void addSafePoint(GC::PointKind Kind, MCSymbol *Label) { - SafePoints.push_back(GCPoint(Kind, Label)); + void addSafePoint(GC::PointKind Kind, MCSymbol *Label, DebugLoc DL) { + SafePoints.push_back(GCPoint(Kind, Label, DL)); } /// getFrameSize/setFrameSize - Records the function's frame size. diff --git a/include/llvm/CodeGen/ISDOpcodes.h b/include/llvm/CodeGen/ISDOpcodes.h index 2e23f4e..3da11c4 100644 --- a/include/llvm/CodeGen/ISDOpcodes.h +++ b/include/llvm/CodeGen/ISDOpcodes.h @@ -107,6 +107,13 @@ namespace ISD { // and returns an outchain. EH_SJLJ_LONGJMP, + // OUTCHAIN = EH_SJLJ_DISPATCHSETUP(INCHAIN, context) + // This corresponds to the eh.sjlj.dispatchsetup intrinsic. It takes an + // input chain and a pointer to the sjlj function context as inputs and + // returns an outchain. By default, this does nothing. Targets can lower + // this to unwind setup code if needed. + EH_SJLJ_DISPATCHSETUP, + // TargetConstant* - Like Constant*, but the DAG does not do any folding, // simplification, or lowering of the constant. They are used for constants // which are known to fit in the immediate fields of their users, or for @@ -262,16 +269,24 @@ namespace ISD { /// lengths of the input vectors. CONCAT_VECTORS, + /// INSERT_SUBVECTOR(VECTOR1, VECTOR2, IDX) - Returns a vector + /// with VECTOR2 inserted into VECTOR1 at the (potentially + /// variable) element number IDX, which must be a multiple of the + /// VECTOR2 vector length. The elements of VECTOR1 starting at + /// IDX are overwritten with VECTOR2. Elements IDX through + /// vector_length(VECTOR2) must be valid VECTOR1 indices. + INSERT_SUBVECTOR, + /// EXTRACT_SUBVECTOR(VECTOR, IDX) - Returns a subvector from VECTOR (an - /// vector value) starting with the (potentially variable) element number - /// IDX, which must be a multiple of the result vector length. + /// vector value) starting with the element number IDX, which must be a + /// constant multiple of the result vector length. EXTRACT_SUBVECTOR, - /// VECTOR_SHUFFLE(VEC1, VEC2) - Returns a vector, of the same type as + /// VECTOR_SHUFFLE(VEC1, VEC2) - Returns a vector, of the same type as /// VEC1/VEC2. A VECTOR_SHUFFLE node also contains an array of constant int /// values that indicate which value (or undef) each result element will - /// get. These constant ints are accessible through the - /// ShuffleVectorSDNode class. This is quite similar to the Altivec + /// get. These constant ints are accessible through the + /// ShuffleVectorSDNode class. This is quite similar to the Altivec /// 'vperm' instruction, except that the indices must be constants and are /// in terms of the element size of VEC1/VEC2, not in terms of bytes. VECTOR_SHUFFLE, @@ -288,13 +303,21 @@ namespace ISD { // an unsigned/signed value of type i[2*N], then return the top part. MULHU, MULHS, - // Bitwise operators - logical and, logical or, logical xor, shift left, - // shift right algebraic (shift in sign bits), shift right logical (shift in - // zeroes), rotate left, rotate right, and byteswap. - AND, OR, XOR, SHL, SRA, SRL, ROTL, ROTR, BSWAP, + /// Bitwise operators - logical and, logical or, logical xor. + AND, OR, XOR, + + /// Shift and rotation operations. After legalization, the type of the + /// shift amount is known to be TLI.getShiftAmountTy(). Before legalization + /// the shift amount can be any type, but care must be taken to ensure it is + /// large enough. TLI.getShiftAmountTy() is i8 on some targets, but before + /// legalization, types like i1024 can occur and i8 doesn't have enough bits + /// to represent the shift amount. By convention, DAGCombine and + /// SelectionDAGBuilder forces these shift amounts to i32 for simplicity. + /// + SHL, SRA, SRL, ROTL, ROTR, - // Counting operators - CTTZ, CTLZ, CTPOP, + /// Byte Swap and Counting operators. + BSWAP, CTTZ, CTLZ, CTPOP, // Select(COND, TRUEVAL, FALSEVAL). If the type of the boolean COND is not // i1 then the high bits must conform to getBooleanContents. @@ -392,14 +415,14 @@ namespace ISD { /// X = FP_EXTEND(Y) - Extend a smaller FP type into a larger FP type. FP_EXTEND, - // BIT_CONVERT - This operator converts between integer, vector and FP + // BITCAST - This operator converts between integer, vector and FP // values, as if the value was stored to memory with one type and loaded // from the same address with the other type (or equivalently for vector // format conversions, etc). The source and result are required to have // the same bit size (e.g. f32 <-> i32). This can also be used for // int-to-int or fp-to-fp conversions, but that is a noop, deleted by // getNode(). - BIT_CONVERT, + BITCAST, // CONVERT_RNDSAT - This operator is used to support various conversions // between various types (float, signed, unsigned and vectors of those @@ -475,6 +498,7 @@ namespace ISD { // Operand #0 : Input chain. // Operand #1 : a ExternalSymbolSDNode with a pointer to the asm string. // Operand #2 : a MDNodeSDNode with the !srcloc metadata. + // Operand #3 : HasSideEffect, IsAlignStack bits. // After this, it is followed by a list of operands with this format: // ConstantSDNode: Flags that encode whether it is a mem or not, the // of operands that follow, etc. See InlineAsm.h. @@ -525,7 +549,7 @@ namespace ISD { // SRCVALUE - This is a node type that holds a Value* that is used to // make reference to a value in the LLVM IR. SRCVALUE, - + // MDNODE_SDNODE - This is a node that holdes an MDNode*, which is used to // reference metadata in the IR. MDNODE_SDNODE, diff --git a/include/llvm/CodeGen/IntrinsicLowering.h b/include/llvm/CodeGen/IntrinsicLowering.h index eefbc45..767b666 100644 --- a/include/llvm/CodeGen/IntrinsicLowering.h +++ b/include/llvm/CodeGen/IntrinsicLowering.h @@ -48,6 +48,11 @@ namespace llvm { /// be capable of handling this kind of change. /// void LowerIntrinsicCall(CallInst *CI); + + /// LowerToByteSwap - Replace a call instruction into a call to bswap + /// intrinsic. Return false if it has determined the call is not a + /// simple integer bswap. + static bool LowerToByteSwap(CallInst *CI); }; } diff --git a/include/llvm/CodeGen/JITCodeEmitter.h b/include/llvm/CodeGen/JITCodeEmitter.h index eb373fb..fea8523 100644 --- a/include/llvm/CodeGen/JITCodeEmitter.h +++ b/include/llvm/CodeGen/JITCodeEmitter.h @@ -18,7 +18,7 @@ #define LLVM_CODEGEN_JITCODEEMITTER_H #include <string> -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include "llvm/Support/MathExtras.h" #include "llvm/CodeGen/MachineCodeEmitter.h" #include "llvm/ADT/DenseMap.h" diff --git a/include/llvm/CodeGen/LatencyPriorityQueue.h b/include/llvm/CodeGen/LatencyPriorityQueue.h index 13cebea..1ed2547 100644 --- a/include/llvm/CodeGen/LatencyPriorityQueue.h +++ b/include/llvm/CodeGen/LatencyPriorityQueue.h @@ -20,25 +20,25 @@ namespace llvm { class LatencyPriorityQueue; - + /// Sorting functions for the Available queue. struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> { LatencyPriorityQueue *PQ; explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} - + bool operator()(const SUnit* left, const SUnit* right) const; }; class LatencyPriorityQueue : public SchedulingPriorityQueue { // SUnits - The SUnits for the current graph. std::vector<SUnit> *SUnits; - + /// NumNodesSolelyBlocking - This vector contains, for every node in the /// Queue, the number of nodes that the node is the sole unscheduled /// predecessor for. This is used as a tie-breaker heuristic for better /// mobility. std::vector<unsigned> NumNodesSolelyBlocking; - + /// Queue - The queue. std::vector<SUnit*> Queue; latency_sort Picker; @@ -47,6 +47,8 @@ namespace llvm { LatencyPriorityQueue() : Picker(this) { } + bool isBottomUp() const { return false; } + void initNodes(std::vector<SUnit> &sunits) { SUnits = &sunits; NumNodesSolelyBlocking.resize(SUnits->size(), 0); @@ -62,25 +64,27 @@ namespace llvm { void releaseState() { SUnits = 0; } - + unsigned getLatency(unsigned NodeNum) const { assert(NodeNum < (*SUnits).size()); return (*SUnits)[NodeNum].getHeight(); } - + unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { assert(NodeNum < NumNodesSolelyBlocking.size()); return NumNodesSolelyBlocking[NodeNum]; } - + bool empty() const { return Queue.empty(); } - + virtual void push(SUnit *U); - + virtual SUnit *pop(); virtual void remove(SUnit *SU); + virtual void dump(ScheduleDAG* DAG) const; + // ScheduledNode - As nodes are scheduled, we look to see if there are any // successor nodes that have a single unscheduled predecessor. If so, that // single predecessor has a higher priority, since scheduling it will make diff --git a/include/llvm/CodeGen/LinkAllCodegenComponents.h b/include/llvm/CodeGen/LinkAllCodegenComponents.h index cd8293d..c931261 100644 --- a/include/llvm/CodeGen/LinkAllCodegenComponents.h +++ b/include/llvm/CodeGen/LinkAllCodegenComponents.h @@ -34,8 +34,10 @@ namespace { (void) llvm::createDeadMachineInstructionElimPass(); (void) llvm::createFastRegisterAllocator(); + (void) llvm::createBasicRegisterAllocator(); (void) llvm::createLinearScanRegisterAllocator(); - (void) llvm::createPBQPRegisterAllocator(); + (void) llvm::createGreedyRegisterAllocator(); + (void) llvm::createDefaultPBQPRegisterAllocator(); (void) llvm::createSimpleRegisterCoalescer(); diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 29e689a..88131fb 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -21,7 +21,7 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_H #define LLVM_CODEGEN_LIVEINTERVAL_H -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/IntEqClasses.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/AlignOf.h" #include "llvm/CodeGen/SlotIndexes.h" @@ -39,32 +39,17 @@ namespace llvm { /// This class holds information about a machine level values, including /// definition and use points. /// - /// Care must be taken in interpreting the def index of the value. The - /// following rules apply: - /// - /// If the isDefAccurate() method returns false then def does not contain the - /// index of the defining MachineInstr, or even (necessarily) to a - /// MachineInstr at all. In general such a def index is not meaningful - /// and should not be used. The exception is that, for values originally - /// defined by PHI instructions, after PHI elimination def will contain the - /// index of the MBB in which the PHI originally existed. This can be used - /// to insert code (spills or copies) which deals with the value, which will - /// be live in to the block. class VNInfo { private: enum { HAS_PHI_KILL = 1, REDEF_BY_EC = 1 << 1, IS_PHI_DEF = 1 << 2, - IS_UNUSED = 1 << 3, - IS_DEF_ACCURATE = 1 << 4 + IS_UNUSED = 1 << 3 }; + MachineInstr *copy; unsigned char flags; - union { - MachineInstr *copy; - unsigned reg; - } cr; public: typedef BumpPtrAllocator Allocator; @@ -76,20 +61,19 @@ namespace llvm { SlotIndex def; /// VNInfo constructor. - /// d is presumed to point to the actual defining instr. If it doesn't - /// setIsDefAccurate(false) should be called after construction. VNInfo(unsigned i, SlotIndex d, MachineInstr *c) - : flags(IS_DEF_ACCURATE), id(i), def(d) { cr.copy = c; } + : copy(c), flags(0), id(i), def(d) + { } /// VNInfo construtor, copies values from orig, except for the value number. VNInfo(unsigned i, const VNInfo &orig) - : flags(orig.flags), cr(orig.cr), id(i), def(orig.def) + : copy(orig.copy), flags(orig.flags), id(i), def(orig.def) { } /// Copy from the parameter into this VNInfo. void copyFrom(VNInfo &src) { flags = src.flags; - cr = src.cr; + copy = src.copy; def = src.def; } @@ -97,23 +81,23 @@ namespace llvm { unsigned getFlags() const { return flags; } void setFlags(unsigned flags) { this->flags = flags; } + /// Merge flags from another VNInfo + void mergeFlags(const VNInfo *VNI) { + flags = (flags | VNI->flags) & ~IS_UNUSED; + } + /// For a register interval, if this VN was definied by a copy instr /// getCopy() returns a pointer to it, otherwise returns 0. /// For a stack interval the behaviour of this method is undefined. - MachineInstr* getCopy() const { return cr.copy; } + MachineInstr* getCopy() const { return copy; } /// For a register interval, set the copy member. /// This method should not be called on stack intervals as it may lead to /// undefined behavior. - void setCopy(MachineInstr *c) { cr.copy = c; } + void setCopy(MachineInstr *c) { copy = c; } - /// For a stack interval, returns the reg which this stack interval was - /// defined from. - /// For a register interval the behaviour of this method is undefined. - unsigned getReg() const { return cr.reg; } - /// For a stack interval, set the defining register. - /// This method should not be called on register intervals as it may lead - /// to undefined behaviour. - void setReg(unsigned reg) { cr.reg = reg; } + /// isDefByCopy - Return true when this value was defined by a copy-like + /// instruction as determined by MachineInstr::isCopyLike. + bool isDefByCopy() const { return copy != 0; } /// Returns true if one or more kills are PHI nodes. bool hasPHIKill() const { return flags & HAS_PHI_KILL; } @@ -156,16 +140,6 @@ namespace llvm { else flags &= ~IS_UNUSED; } - - /// Returns true if the def is accurate. - bool isDefAccurate() const { return flags & IS_DEF_ACCURATE; } - /// Set the "is def accurate" flag on this value. - void setIsDefAccurate(bool defAccurate) { - if (defAccurate) - flags |= IS_DEF_ACCURATE; - else - flags &= ~IS_DEF_ACCURATE; - } }; /// LiveRange structure - This represents a simple register range in the @@ -231,8 +205,7 @@ namespace llvm { typedef SmallVector<LiveRange,4> Ranges; typedef SmallVector<VNInfo*,4> VNInfoList; - unsigned reg; // the register or stack slot of this interval - // if the top bits is set, it represents a stack slot. + 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 @@ -248,11 +221,8 @@ namespace llvm { }; - LiveInterval(unsigned Reg, float Weight, bool IsSS = false) - : reg(Reg), weight(Weight) { - if (IsSS) - reg = reg | (1U << (sizeof(unsigned)*CHAR_BIT-1)); - } + LiveInterval(unsigned Reg, float Weight) + : reg(Reg), weight(Weight) {} typedef Ranges::iterator iterator; iterator begin() { return ranges.begin(); } @@ -276,28 +246,29 @@ namespace llvm { /// position is in a hole, this method returns an iterator pointing to the /// LiveRange immediately after the hole. iterator advanceTo(iterator I, SlotIndex Pos) { + assert(I != end()); if (Pos >= endIndex()) return end(); while (I->end <= Pos) ++I; return I; } - void clear() { - valnos.clear(); - ranges.clear(); - } - - /// isStackSlot - Return true if this is a stack slot interval. + /// find - Return an iterator pointing to the first range that ends after + /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster + /// when searching large intervals. /// - bool isStackSlot() const { - return reg & (1U << (sizeof(unsigned)*CHAR_BIT-1)); + /// 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 beyond endIndex, end() is returned. + iterator find(SlotIndex Pos); + + const_iterator find(SlotIndex Pos) const { + return const_cast<LiveInterval*>(this)->find(Pos); } - /// getStackSlotIndex - Return stack slot index if this is a stack slot - /// interval. - int getStackSlotIndex() const { - assert(isStackSlot() && "Interval is not a stack slot interval!"); - return reg & ~(1U << (sizeof(unsigned)*CHAR_BIT-1)); + void clear() { + valnos.clear(); + ranges.clear(); } bool hasAtLeastOneValue() const { return !valnos.empty(); } @@ -318,10 +289,9 @@ namespace llvm { /// getNextValue - Create a new value number and return it. MIIdx specifies /// the instruction that defines the value number. VNInfo *getNextValue(SlotIndex def, MachineInstr *CopyMI, - bool isDefAccurate, VNInfo::Allocator &VNInfoAllocator) { + VNInfo::Allocator &VNInfoAllocator) { VNInfo *VNI = new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def, CopyMI); - VNI->setIsDefAccurate(isDefAccurate); valnos.push_back(VNI); return VNI; } @@ -358,21 +328,6 @@ namespace llvm { /// cause merging of V1/V2 values numbers and compaction of the value space. VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); - /// MergeInClobberRanges - For any live ranges that are not defined in the - /// current interval, but are defined in the Clobbers interval, mark them - /// used with an unknown definition value. Caller must pass in reference to - /// VNInfoAllocator since it will create a new val#. - void MergeInClobberRanges(LiveIntervals &li_, - const LiveInterval &Clobbers, - VNInfo::Allocator &VNInfoAllocator); - - /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a - /// single LiveRange only. - void MergeInClobberRange(LiveIntervals &li_, - SlotIndex Start, - SlotIndex End, - VNInfo::Allocator &VNInfoAllocator); - /// 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 @@ -412,17 +367,18 @@ namespace llvm { return index >= endIndex(); } - bool liveAt(SlotIndex index) const; - - // liveBeforeAndAt - Check if the interval is live at the index and the - // index just before it. If index is liveAt, check if it starts a new live - // range.If it does, then check if the previous live range ends at index-1. - bool liveBeforeAndAt(SlotIndex index) const; + bool liveAt(SlotIndex index) const { + const_iterator r = find(index); + 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; + bool killedAt(SlotIndex index) const { + const_iterator r = find(index.getUseIndex()); + return r != end() && r->end == index; + } /// killedInRange - Return true if the interval has kills in [Start,End). /// Note that the kill point is considered the end of a live range, so it is @@ -452,20 +408,20 @@ namespace llvm { /// FindLiveRangeContaining - Return an iterator to the live range that /// contains the specified index, or end() if there is none. - const_iterator FindLiveRangeContaining(SlotIndex Idx) const; + iterator FindLiveRangeContaining(SlotIndex Idx) { + iterator I = find(Idx); + return I != end() && I->start <= Idx ? I : end(); + } - /// FindLiveRangeContaining - Return an iterator to the live range that - /// contains the specified index, or end() if there is none. - iterator FindLiveRangeContaining(SlotIndex Idx); + const_iterator FindLiveRangeContaining(SlotIndex Idx) const { + const_iterator I = find(Idx); + return I != end() && I->start <= Idx ? I : end(); + } /// findDefinedVNInfo - Find the by the specified /// index (register interval) or defined VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) const; - /// findDefinedVNInfo - Find the VNInfo that's defined by the specified - /// register (stack inteval only). - VNInfo *findDefinedVNInfoForStackInt(unsigned Reg) const; - /// overlaps - Return true if the intersection of the two live intervals is /// not empty. @@ -502,7 +458,10 @@ namespace llvm { /// isInOneLiveRange - Return true if the range specified is entirely in the /// a single LiveRange of the live interval. - bool isInOneLiveRange(SlotIndex Start, SlotIndex End); + bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const { + const_iterator r = find(Start); + return r != end() && r->containsRange(Start, End); + } /// removeRange - Remove the specified range from this interval. Note that /// the range must be a single LiveRange in its entirety. @@ -569,6 +528,46 @@ namespace llvm { LI.print(OS); return OS; } -} + /// 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 + /// multiple LiveIntervals. + /// + /// Given a LiveInterval that may have multiple connected components, run: + /// + /// unsigned numComps = ConEQ.Classify(LI); + /// if (numComps > 1) { + /// // allocate numComps-1 new LiveIntervals into LIS[1..] + /// ConEQ.Distribute(LIS); + /// } + + class ConnectedVNInfoEqClasses { + LiveIntervals &lis_; + IntEqClasses eqClass_; + + // Note that values a and b are connected. + void Connect(unsigned a, unsigned b); + + unsigned Renumber(); + + public: + explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : lis_(lis) {} + + /// Classify - Classify the values in LI into connected components. + /// Return the number of connected components. + unsigned Classify(const LiveInterval *LI); + + /// getEqClass - Classify creates equivalence classes numbered 0..N. Return + /// the equivalence class assigned the VNI. + unsigned getEqClass(const VNInfo *VNI) const { return eqClass_[VNI->id]; } + + /// Distribute - Distribute values in LIV[0] into a separate LiveInterval + /// for each connected component. LIV must have a LiveInterval for each + /// connected component. The LiveIntervals in Liv[1..] must be empty. + void Distribute(LiveInterval *LIV[]); + + }; + +} #endif diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 2918c3c2a..b09f8d1 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -68,19 +68,13 @@ namespace llvm { public: static char ID; // Pass identification, replacement for typeid - LiveIntervals() : MachineFunctionPass(ID) {} + LiveIntervals() : MachineFunctionPass(ID) { + initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); + } // Calculate the spill weight to assign to a single instruction. static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth); - // After summing the spill weights of all defs and uses, the final weight - // should be normalized, dividing the weight of the interval by its size. - // This encourages spilling of intervals that are large and have few uses, - // and discourages spilling of small intervals with many uses. - void normalizeSpillWeight(LiveInterval &li) { - li.weight /= getApproximateInstructionCount(li) + 25; - } - typedef Reg2IntervalMap::iterator iterator; typedef Reg2IntervalMap::const_iterator const_iterator; const_iterator begin() const { return r2iMap_.begin(); } @@ -161,6 +155,12 @@ namespace llvm { LiveRange addLiveRangeToEndOfBlock(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 + /// defs for new uses, and it doesn't remove dead defs. + /// Dead PHIDef values are marked as unused. + void shrinkToUses(LiveInterval *li); + // Interval removal void removeInterval(unsigned Reg) { @@ -169,6 +169,10 @@ namespace llvm { r2iMap_.erase(I); } + SlotIndexes *getSlotIndexes() const { + return indexes_; + } + SlotIndex getZeroIndex() const { return indexes_->getZeroIndex(); } @@ -227,10 +231,6 @@ namespace llvm { return indexes_->getMBBFromIndex(index); } - SlotIndex getMBBTerminatorGap(const MachineBasicBlock *mbb) { - return indexes_->getTerminatorGap(mbb); - } - SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { return indexes_->insertMachineInstrInMaps(MI); } @@ -272,7 +272,7 @@ namespace llvm { /// (if any is created) by reference. This is temporary. std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i, - SmallVectorImpl<LiveInterval*> &SpillIs, + const SmallVectorImpl<LiveInterval*> &SpillIs, const MachineLoopInfo *loopInfo, VirtRegMap& vrm); /// spillPhysRegAroundRegDefsUses - Spill the specified physical register @@ -285,7 +285,7 @@ namespace llvm { /// val# of the specified interval is re-materializable. Also returns true /// by reference if all of the defs are load instructions. bool isReMaterializable(const LiveInterval &li, - SmallVectorImpl<LiveInterval*> &SpillIs, + const SmallVectorImpl<LiveInterval*> &SpillIs, bool &isLoad); /// isReMaterializable - Returns true if the definition MI of the specified @@ -306,6 +306,16 @@ namespace llvm { /// within a single basic block. bool intervalIsInOneMBB(const LiveInterval &li) const; + /// getLastSplitPoint - Return the last possible insertion point in mbb for + /// spilling and splitting code. This is the first terminator, or the call + /// instruction if li is live into a landing pad successor. + MachineBasicBlock::iterator getLastSplitPoint(const LiveInterval &li, + MachineBasicBlock *mbb) const; + + /// addKillFlags - Add kill flags to any instruction that kills a virtual + /// register. + void addKillFlags(); + private: /// computeIntervals - Compute live intervals. void computeIntervals(); @@ -362,7 +372,7 @@ namespace llvm { /// by reference if the def is a load. bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, MachineInstr *MI, - SmallVectorImpl<LiveInterval*> &SpillIs, + const SmallVectorImpl<LiveInterval*> &SpillIs, bool &isLoad); /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from @@ -443,9 +453,6 @@ namespace llvm { DenseMap<unsigned,unsigned> &MBBVRegsMap, std::vector<LiveInterval*> &NewLIs); - // Normalize the spill weight of all the intervals in NewLIs. - void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs); - static LiveInterval* createInterval(unsigned Reg); void printInstrs(raw_ostream &O) const; diff --git a/include/llvm/CodeGen/LiveStackAnalysis.h b/include/llvm/CodeGen/LiveStackAnalysis.h index ad984db..8a8dcaf 100644 --- a/include/llvm/CodeGen/LiveStackAnalysis.h +++ b/include/llvm/CodeGen/LiveStackAnalysis.h @@ -39,7 +39,9 @@ namespace llvm { public: static char ID; // Pass identification, replacement for typeid - LiveStacks() : MachineFunctionPass(ID) {} + LiveStacks() : MachineFunctionPass(ID) { + initializeLiveStacksPass(*PassRegistry::getPassRegistry()); + } typedef SS2IntervalMap::iterator iterator; typedef SS2IntervalMap::const_iterator const_iterator; @@ -50,19 +52,7 @@ namespace llvm { unsigned getNumIntervals() const { return (unsigned)S2IMap.size(); } - LiveInterval &getOrCreateInterval(int Slot, const TargetRegisterClass *RC) { - assert(Slot >= 0 && "Spill slot indice must be >= 0"); - SS2IntervalMap::iterator I = S2IMap.find(Slot); - if (I == S2IMap.end()) { - I = S2IMap.insert(I,std::make_pair(Slot, LiveInterval(Slot,0.0F,true))); - S2RCMap.insert(std::make_pair(Slot, RC)); - } else { - // Use the largest common subclass register class. - const TargetRegisterClass *OldRC = S2RCMap[Slot]; - S2RCMap[Slot] = getCommonSubClass(OldRC, RC); - } - return I->second; - } + LiveInterval &getOrCreateInterval(int Slot, const TargetRegisterClass *RC); LiveInterval &getInterval(int Slot) { assert(Slot >= 0 && "Spill slot indice must be >= 0"); diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index c8182e0..f9b81b1 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -32,8 +32,10 @@ #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SparseBitVector.h" @@ -46,7 +48,9 @@ class TargetRegisterInfo; class LiveVariables : public MachineFunctionPass { public: static char ID; // Pass identification, replacement for typeid - LiveVariables() : MachineFunctionPass(ID) {} + LiveVariables() : MachineFunctionPass(ID) { + initializeLiveVariablesPass(*PassRegistry::getPassRegistry()); + } /// VarInfo - This represents the regions where a virtual register is live in /// the program. We represent this with three different pieces of @@ -119,10 +123,9 @@ public: private: /// VirtRegInfo - This list is a mapping from virtual register number to - /// variable information. FirstVirtualRegister is subtracted from the virtual - /// register number before indexing into this list. + /// variable information. /// - std::vector<VarInfo> VirtRegInfo; + IndexedMap<VarInfo, VirtReg2IndexFunctor> VirtRegInfo; /// PHIJoins - list of virtual registers that are PHI joins. These registers /// may have multiple definitions, and they require special handling when diff --git a/include/llvm/CodeGen/MachORelocation.h b/include/llvm/CodeGen/MachORelocation.h index 27306c6..21fe74f 100644 --- a/include/llvm/CodeGen/MachORelocation.h +++ b/include/llvm/CodeGen/MachORelocation.h @@ -15,7 +15,7 @@ #ifndef LLVM_CODEGEN_MACHO_RELOCATION_H #define LLVM_CODEGEN_MACHO_RELOCATION_H -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" namespace llvm { diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 3cfc47a..1785451 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -23,6 +23,7 @@ class Pass; class BasicBlock; class MachineFunction; class MCSymbol; +class SlotIndexes; class StringRef; class raw_ostream; @@ -223,6 +224,10 @@ public: /// this basic block is entered via an exception handler. void setIsLandingPad() { IsLandingPad = true; } + /// getLandingPadSuccessor - If this block has a successor that is a landing + /// pad, return it. Otherwise return NULL. + const MachineBasicBlock *getLandingPadSuccessor() const; + // Code Layout methods. /// moveBefore/moveAfter - move 'this' block before or after the specified @@ -289,11 +294,20 @@ public: /// Returns end() is there's no non-PHI instruction. iterator getFirstNonPHI(); + /// SkipPHIsAndLabels - Return the first instruction in MBB after I that is + /// not a PHI or a label. This is the correct point to insert copies at the + /// beginning of a basic block. + iterator SkipPHIsAndLabels(iterator I); + /// getFirstTerminator - returns an iterator to the first terminator /// instruction of this basic block. If a terminator does not exist, /// it returns end() iterator getFirstTerminator(); + /// getLastNonDebugInstr - returns an iterator to the last non-debug + /// instruction in the basic block, or end() + iterator getLastNonDebugInstr(); + /// SplitCriticalEdge - Split the critical edge from this block to the /// given successor block, and return the newly created block, or null /// if splitting is not possible. @@ -308,6 +322,9 @@ public: template<typename IT> void insert(iterator I, IT S, IT E) { Insts.insert(I, S, E); } iterator insert(iterator I, MachineInstr *M) { return Insts.insert(I, M); } + iterator insertAfter(iterator I, MachineInstr *M) { + return Insts.insertAfter(I, M); + } // erase - Remove the specified element or range from the instruction list. // These functions delete any instructions removed. @@ -358,7 +375,7 @@ public: // Debugging methods. void dump() const; - void print(raw_ostream &OS) const; + void print(raw_ostream &OS, SlotIndexes* = 0) const; /// getNumber - MachineBasicBlocks are uniquely numbered at the function /// level, unless they're not in a MachineFunction yet, in which case this diff --git a/include/llvm/CodeGen/MachineCodeEmitter.h b/include/llvm/CodeGen/MachineCodeEmitter.h index 7abb49a..8fc80ad 100644 --- a/include/llvm/CodeGen/MachineCodeEmitter.h +++ b/include/llvm/CodeGen/MachineCodeEmitter.h @@ -17,7 +17,7 @@ #ifndef LLVM_CODEGEN_MACHINECODEEMITTER_H #define LLVM_CODEGEN_MACHINECODEEMITTER_H -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include "llvm/Support/DebugLoc.h" namespace llvm { diff --git a/include/llvm/CodeGen/MachineCodeInfo.h b/include/llvm/CodeGen/MachineCodeInfo.h index a75c02a..c5c0c44 100644 --- a/include/llvm/CodeGen/MachineCodeInfo.h +++ b/include/llvm/CodeGen/MachineCodeInfo.h @@ -17,7 +17,7 @@ #ifndef EE_MACHINE_CODE_INFO_H #define EE_MACHINE_CODE_INFO_H -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" namespace llvm { diff --git a/include/llvm/CodeGen/MachineDominators.h b/include/llvm/CodeGen/MachineDominators.h index 48695d5..ab944a2 100644 --- a/include/llvm/CodeGen/MachineDominators.h +++ b/include/llvm/CodeGen/MachineDominators.h @@ -145,7 +145,7 @@ public: } /// eraseNode - Removes a node from the dominator tree. Block must not - /// domiante any other blocks. Removes node from its immediate dominator's + /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. inline void eraseNode(MachineBasicBlock *BB) { DT->eraseNode(BB); diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h index dca65ef..22a82a9 100644 --- a/include/llvm/CodeGen/MachineFrameInfo.h +++ b/include/llvm/CodeGen/MachineFrameInfo.h @@ -16,7 +16,7 @@ #include "llvm/ADT/SmallVector.h" //#include "llvm/ADT/IndexedMap.h" -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include <cassert> #include <vector> @@ -27,7 +27,7 @@ class TargetRegisterClass; class Type; class MachineFunction; class MachineBasicBlock; -class TargetFrameInfo; +class TargetFrameLowering; class BitVector; /// The CalleeSavedInfo class tracks the information need to locate where a @@ -192,13 +192,9 @@ class MachineFrameInfo { /// CSIValid - Has CSInfo been set yet? bool CSIValid; - /// SpillObjects - A vector indicating which frame indices refer to - /// spill slots. - SmallVector<bool, 8> SpillObjects; - - /// TargetFrameInfo - Target information about frame layout. + /// TargetFrameLowering - Target information about frame layout. /// - const TargetFrameInfo &TFI; + const TargetFrameLowering &TFI; /// LocalFrameObjects - References to frame indices which are mapped /// into the local frame allocation block. <FrameIdx, LocalOffset> @@ -217,7 +213,7 @@ class MachineFrameInfo { bool UseLocalStackAllocationBlock; public: - explicit MachineFrameInfo(const TargetFrameInfo &tfi) : TFI(tfi) { + explicit MachineFrameInfo(const TargetFrameLowering &tfi) : TFI(tfi) { StackSize = NumFixedObjects = OffsetAdjustment = MaxAlignment = 0; HasVarSizedObjects = false; FrameAddressTaken = false; diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h index 5bb453d..abeaa4f 100644 --- a/include/llvm/CodeGen/MachineFunction.h +++ b/include/llvm/CodeGen/MachineFunction.h @@ -28,6 +28,7 @@ namespace llvm { class Value; class Function; +class GCModuleInfo; class MachineRegisterInfo; class MachineFrameInfo; class MachineConstantPool; @@ -37,6 +38,7 @@ class MCContext; class Pass; class TargetMachine; class TargetRegisterClass; +struct MachinePointerInfo; template <> struct ilist_traits<MachineBasicBlock> @@ -74,6 +76,7 @@ class MachineFunction { const TargetMachine &Target; MCContext &Ctx; MachineModuleInfo &MMI; + GCModuleInfo *GMI; // RegInfo - Information about each register in use in the function. MachineRegisterInfo *RegInfo; @@ -126,10 +129,12 @@ class MachineFunction { void operator=(const MachineFunction&); // DO NOT IMPLEMENT public: MachineFunction(const Function *Fn, const TargetMachine &TM, - unsigned FunctionNum, MachineModuleInfo &MMI); + unsigned FunctionNum, MachineModuleInfo &MMI, + GCModuleInfo* GMI); ~MachineFunction(); MachineModuleInfo &getMMI() const { return MMI; } + GCModuleInfo *getGMI() const { return GMI; } MCContext &getContext() const { return Ctx; } /// getFunction - Return the LLVM function that this machine code represents @@ -243,7 +248,7 @@ public: /// print - Print out the MachineFunction in a format suitable for debugging /// to the specified stream. /// - void print(raw_ostream &OS) const; + void print(raw_ostream &OS, SlotIndexes* = 0) const; /// viewCFG - This function is meant for use from the debugger. You can just /// say 'call F->viewCFG()' and a ghostview window should pop up from the @@ -266,7 +271,7 @@ public: /// verify - Run the current MachineFunction through the machine code /// verifier, useful for debugger use. - void verify(Pass *p=NULL) const; + void verify(Pass *p = NULL, const char *Banner = NULL) const; // Provide accessors for the MachineBasicBlock list... typedef BasicBlockListType::iterator iterator; @@ -276,7 +281,7 @@ public: /// addLiveIn - Add the specified physical register as a live-in value and /// create a corresponding virtual register for it. - unsigned addLiveIn(unsigned PReg, const TargetRegisterClass *RC); + unsigned addLiveIn(unsigned PReg, const TargetRegisterClass *RC, DebugLoc DL); //===--------------------------------------------------------------------===// // BasicBlock accessor functions. @@ -368,10 +373,11 @@ public: /// getMachineMemOperand - Allocate a new MachineMemOperand. /// MachineMemOperands are owned by the MachineFunction and need not be /// explicitly deallocated. - MachineMemOperand *getMachineMemOperand(const Value *v, unsigned f, - int64_t o, uint64_t s, - unsigned base_alignment); - + MachineMemOperand *getMachineMemOperand(MachinePointerInfo PtrInfo, + unsigned f, uint64_t s, + unsigned base_alignment, + const MDNode *TBAAInfo = 0); + /// getMachineMemOperand - Allocate a new MachineMemOperand by copying /// an existing one, adjusting by an offset and using the given size. /// MachineMemOperands are owned by the MachineFunction and need not be @@ -406,6 +412,10 @@ public: /// normal 'L' label is returned. MCSymbol *getJTISymbol(unsigned JTI, MCContext &Ctx, bool isLinkerPrivate = false) const; + + /// getPICBaseSymbol - Return a function-local symbol to represent the PIC + /// base. + MCSymbol *getPICBaseSymbol() const; }; //===--------------------------------------------------------------------===// diff --git a/include/llvm/CodeGen/MachineFunctionAnalysis.h b/include/llvm/CodeGen/MachineFunctionAnalysis.h index 75dbaab..50676ad 100644 --- a/include/llvm/CodeGen/MachineFunctionAnalysis.h +++ b/include/llvm/CodeGen/MachineFunctionAnalysis.h @@ -37,6 +37,10 @@ public: MachineFunction &getMF() const { return *MF; } CodeGenOpt::Level getOptLevel() const { return OptLevel; } + + virtual const char* getPassName() const { + return "Machine Function Analysis"; + } private: virtual bool doInitialization(Module &M); diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index f843196..82c5332 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -127,6 +127,10 @@ public: /// unsigned short getAsmPrinterFlags() const { return AsmPrinterFlags; } + /// clearAsmPrinterFlags - clear the AsmPrinter bitvector + /// + void clearAsmPrinterFlags() { AsmPrinterFlags = 0; } + /// getAsmPrinterFlag - Return whether an AsmPrinter flag is set. /// bool getAsmPrinterFlag(CommentFlag Flag) const { @@ -138,6 +142,12 @@ public: void setAsmPrinterFlag(CommentFlag Flag) { AsmPrinterFlags |= (unsigned short)Flag; } + + /// clearAsmPrinterFlag - clear specific AsmPrinter flags + /// + void clearAsmPrinterFlag(CommentFlag Flag) { + AsmPrinterFlags &= ~Flag; + } /// getDebugLoc - Returns the debug location id of this MachineInstr. /// @@ -167,7 +177,17 @@ public: /// getNumExplicitOperands - Returns the number of non-implicit operands. /// unsigned getNumExplicitOperands() const; - + + /// iterator/begin/end - Iterate over all operands of a machine instruction. + typedef std::vector<MachineOperand>::iterator mop_iterator; + typedef std::vector<MachineOperand>::const_iterator const_mop_iterator; + + mop_iterator operands_begin() { return Operands.begin(); } + mop_iterator operands_end() { return Operands.end(); } + + const_mop_iterator operands_begin() const { return Operands.begin(); } + const_mop_iterator operands_end() const { return Operands.end(); } + /// Access to memory operands of the instruction mmo_iterator memoperands_begin() const { return MemRefs; } mmo_iterator memoperands_end() const { return MemRefsEnd; } @@ -217,6 +237,7 @@ public: bool isKill() const { return getOpcode() == TargetOpcode::KILL; } bool isImplicitDef() const { return getOpcode()==TargetOpcode::IMPLICIT_DEF; } bool isInlineAsm() const { return getOpcode() == TargetOpcode::INLINEASM; } + bool isStackAligningInlineAsm() const; bool isInsertSubreg() const { return getOpcode() == TargetOpcode::INSERT_SUBREG; } @@ -412,10 +433,23 @@ public: /// return 0. unsigned isConstantValuePHI() const; + /// hasUnmodeledSideEffects - Return true if this instruction has side + /// effects that are not modeled by mayLoad / mayStore, etc. + /// For all instructions, the property is encoded in TargetInstrDesc::Flags + /// (see TargetInstrDesc::hasUnmodeledSideEffects(). The only exception is + /// INLINEASM instruction, in which case the side effect property is encoded + /// in one of its operands (see InlineAsm::Extra_HasSideEffect). + /// + bool hasUnmodeledSideEffects() const; + /// allDefsAreDead - Return true if all the defs of this instruction are dead. /// bool allDefsAreDead() const; + /// copyImplicitOps - Copy implicit register operands from specified + /// instruction to this instruction. + void copyImplicitOps(const MachineInstr *MI); + // // Debugging support // diff --git a/include/llvm/CodeGen/MachineInstrBuilder.h b/include/llvm/CodeGen/MachineInstrBuilder.h index 37ac24c..1eb9735 100644 --- a/include/llvm/CodeGen/MachineInstrBuilder.h +++ b/include/llvm/CodeGen/MachineInstrBuilder.h @@ -18,6 +18,7 @@ #define LLVM_CODEGEN_MACHINEINSTRBUILDER_H #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/Support/ErrorHandling.h" namespace llvm { @@ -122,6 +123,13 @@ public: return *this; } + const MachineInstrBuilder &setMemRefs(MachineInstr::mmo_iterator b, + MachineInstr::mmo_iterator e) const { + MI->setMemRefs(b, e); + return *this; + } + + const MachineInstrBuilder &addOperand(const MachineOperand &MO) const { MI->addOperand(MO); return *this; @@ -136,6 +144,19 @@ public: MI->addOperand(MachineOperand::CreateMCSymbol(Sym)); return *this; } + + // Add a displacement from an existing MachineOperand with an added offset. + const MachineInstrBuilder &addDisp(const MachineOperand &Disp, + int64_t off) const { + switch (Disp.getType()) { + default: + llvm_unreachable("Unhandled operand type in addDisp()"); + case MachineOperand::MO_Immediate: + return addImm(Disp.getImm() + off); + case MachineOperand::MO_GlobalAddress: + return addGlobalAddress(Disp.getGlobal(), Disp.getOffset() + off); + } + } }; /// BuildMI - Builder interface. Specify how to create the initial instruction diff --git a/include/llvm/CodeGen/MachineLocation.h b/include/llvm/CodeGen/MachineLocation.h index a1fcb9f..21951b6 100644 --- a/include/llvm/CodeGen/MachineLocation.h +++ b/include/llvm/CodeGen/MachineLocation.h @@ -32,7 +32,7 @@ private: public: enum { // The target register number for an abstract frame pointer. The value is - // an arbitrary value greater than TargetRegisterInfo::FirstVirtualRegister. + // an arbitrary value that doesn't collide with any real target register. VirtualFP = ~0U }; MachineLocation() @@ -41,6 +41,11 @@ public: : IsRegister(true), Register(R), Offset(0) {} MachineLocation(unsigned R, int O) : IsRegister(false), Register(R), Offset(O) {} + + bool operator==(const MachineLocation &Other) const { + return IsRegister == Other.IsRegister && Register == Other.Register && + Offset == Other.Offset; + } // Accessors bool isReg() const { return IsRegister; } diff --git a/include/llvm/CodeGen/MachineLoopInfo.h b/include/llvm/CodeGen/MachineLoopInfo.h index 9760eba..6dd9440 100644 --- a/include/llvm/CodeGen/MachineLoopInfo.h +++ b/include/llvm/CodeGen/MachineLoopInfo.h @@ -67,7 +67,9 @@ class MachineLoopInfo : public MachineFunctionPass { public: static char ID; // Pass identification, replacement for typeid - MachineLoopInfo() : MachineFunctionPass(ID) {} + MachineLoopInfo() : MachineFunctionPass(ID) { + initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); + } LoopInfoBase<MachineBasicBlock, MachineLoop>& getBase() { return LI; } diff --git a/include/llvm/CodeGen/MachineLoopRanges.h b/include/llvm/CodeGen/MachineLoopRanges.h new file mode 100644 index 0000000..6a30e8b --- /dev/null +++ b/include/llvm/CodeGen/MachineLoopRanges.h @@ -0,0 +1,112 @@ +//===- MachineLoopRanges.h - Ranges of machine loops -----------*- c++ -*--===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface to the MachineLoopRanges analysis. +// +// Provide on-demand information about the ranges of machine instructions +// covered by a loop. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_MACHINELOOPRANGES_H +#define LLVM_CODEGEN_MACHINELOOPRANGES_H + +#include "llvm/ADT/IntervalMap.h" +#include "llvm/CodeGen/SlotIndexes.h" + +namespace llvm { + +class MachineLoop; +class MachineLoopInfo; +class raw_ostream; + +/// MachineLoopRange - Range information for a single loop. +class MachineLoopRange { + friend class MachineLoopRanges; + +public: + typedef IntervalMap<SlotIndex, unsigned, 4> Map; + typedef Map::Allocator Allocator; + +private: + /// The mapped loop. + const MachineLoop *const Loop; + + /// Map intervals to a bit mask. + /// Bit 0 = inside loop block. + Map Intervals; + + /// Loop area as measured by SlotIndex::distance. + unsigned Area; + + /// Create a MachineLoopRange, only accessible to MachineLoopRanges. + MachineLoopRange(const MachineLoop*, Allocator&, SlotIndexes&); + +public: + /// getLoop - Return the mapped machine loop. + const MachineLoop *getLoop() const { return Loop; } + + /// overlaps - Return true if this loop overlaps the given range of machine + /// inteructions. + bool overlaps(SlotIndex Start, SlotIndex Stop); + + /// getNumber - Return the loop number. This is the same as the number of the + /// header block. + unsigned getNumber() const; + + /// getArea - Return the loop area. This number is approximately proportional + /// to the number of instructions in the loop. + unsigned getArea() const { return Area; } + + /// getMap - Allow public read-only access for IntervalMapOverlaps. + const Map &getMap() { return Intervals; } + + /// print - Print loop ranges on OS. + void print(raw_ostream&) const; + + /// byNumber - Comparator for array_pod_sort that sorts a list of + /// MachineLoopRange pointers by number. + static int byNumber(const void*, const void*); + + /// byAreaDesc - Comparator for array_pod_sort that sorts a list of + /// MachineLoopRange pointers by descending area, then by number. + static int byAreaDesc(const void*, const void*); +}; + +raw_ostream &operator<<(raw_ostream&, const MachineLoopRange&); + +/// MachineLoopRanges - Analysis pass that provides on-demand per-loop range +/// information. +class MachineLoopRanges : public MachineFunctionPass { + typedef DenseMap<const MachineLoop*, MachineLoopRange*> CacheMap; + typedef MachineLoopRange::Allocator MapAllocator; + + MapAllocator Allocator; + SlotIndexes *Indexes; + CacheMap Cache; + +public: + static char ID; // Pass identification, replacement for typeid + + MachineLoopRanges() : MachineFunctionPass(ID), Indexes(0) {} + ~MachineLoopRanges() { releaseMemory(); } + + /// getLoopRange - Return the range of loop. + MachineLoopRange *getLoopRange(const MachineLoop *Loop); + +private: + virtual bool runOnMachineFunction(MachineFunction&); + virtual void releaseMemory(); + virtual void getAnalysisUsage(AnalysisUsage&) const; +}; + + +} // end namespace llvm + +#endif // LLVM_CODEGEN_MACHINELOOPRANGES_H diff --git a/include/llvm/CodeGen/MachineMemOperand.h b/include/llvm/CodeGen/MachineMemOperand.h index 7272aa5..768ce47 100644 --- a/include/llvm/CodeGen/MachineMemOperand.h +++ b/include/llvm/CodeGen/MachineMemOperand.h @@ -16,7 +16,7 @@ #ifndef LLVM_CODEGEN_MACHINEMEMOPERAND_H #define LLVM_CODEGEN_MACHINEMEMOPERAND_H -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" namespace llvm { @@ -24,6 +24,52 @@ class Value; class FoldingSetNodeID; class raw_ostream; +/// MachinePointerInfo - This class contains a discriminated union of +/// information about pointers in memory operands, relating them back to LLVM IR +/// or to virtual locations (such as frame indices) that are exposed during +/// codegen. +struct MachinePointerInfo { + /// V - This is the IR pointer value for the access, or it is null if unknown. + /// If this is null, then the access is to a pointer in the default address + /// space. + const Value *V; + + /// Offset - This is an offset from the base Value*. + int64_t Offset; + + explicit MachinePointerInfo(const Value *v = 0, int64_t offset = 0) + : V(v), Offset(offset) {} + + MachinePointerInfo getWithOffset(int64_t O) const { + if (V == 0) return MachinePointerInfo(0, 0); + return MachinePointerInfo(V, Offset+O); + } + + /// getAddrSpace - Return the LLVM IR address space number that this pointer + /// points into. + unsigned getAddrSpace() const; + + /// getConstantPool - Return a MachinePointerInfo record that refers to the + /// constant pool. + static MachinePointerInfo getConstantPool(); + + /// getFixedStack - Return a MachinePointerInfo record that refers to the + /// the specified FrameIndex. + static MachinePointerInfo getFixedStack(int FI, int64_t offset = 0); + + /// getJumpTable - Return a MachinePointerInfo record that refers to a + /// jump table entry. + static MachinePointerInfo getJumpTable(); + + /// getGOT - Return a MachinePointerInfo record that refers to a + /// GOT entry. + static MachinePointerInfo getGOT(); + + /// getStack - stack pointer relative access. + static MachinePointerInfo getStack(int64_t Offset); +}; + + //===----------------------------------------------------------------------===// /// MachineMemOperand - A description of a memory reference used in the backend. /// Instead of holding a StoreInst or LoadInst, this class holds the address @@ -33,10 +79,10 @@ class raw_ostream; /// that aren't explicit in the regular LLVM IR. /// class MachineMemOperand { - int64_t Offset; + MachinePointerInfo PtrInfo; uint64_t Size; - const Value *V; - unsigned int Flags; + unsigned Flags; + const MDNode *TBAAInfo; public: /// Flags values. These may be or'd together. @@ -54,10 +100,12 @@ public: }; /// MachineMemOperand - Construct an MachineMemOperand object with the - /// specified address Value, flags, offset, size, and base alignment. - MachineMemOperand(const Value *v, unsigned int f, int64_t o, uint64_t s, - unsigned int base_alignment); + /// specified PtrInfo, flags, size, and base alignment. + MachineMemOperand(MachinePointerInfo PtrInfo, unsigned flags, uint64_t s, + unsigned base_alignment, const MDNode *TBAAInfo = 0); + const MachinePointerInfo &getPointerInfo() const { return PtrInfo; } + /// getValue - Return the base address of the memory access. This may either /// be a normal LLVM IR Value, or one of the special values used in CodeGen. /// Special values are those obtained via @@ -65,7 +113,7 @@ public: /// other PseudoSourceValue member functions which return objects which stand /// for frame/stack pointer relative references and other special references /// which are not representable in the high-level IR. - const Value *getValue() const { return V; } + const Value *getValue() const { return PtrInfo.V; } /// getFlags - Return the raw flags of the source value, \see MemOperandFlags. unsigned int getFlags() const { return Flags & ((1 << MOMaxBits) - 1); } @@ -73,7 +121,7 @@ public: /// getOffset - For normal values, this is a byte offset added to the base /// address. For PseudoSourceValue::FPRel values, this is the FrameIndex /// number. - int64_t getOffset() const { return Offset; } + int64_t getOffset() const { return PtrInfo.Offset; } /// getSize - Return the size in bytes of the memory reference. uint64_t getSize() const { return Size; } @@ -86,6 +134,9 @@ public: /// base address, without the offset. uint64_t getBaseAlignment() const { return (1u << (Flags >> MOMaxBits)) >> 1; } + /// getTBAAInfo - Return the TBAA tag for the memory reference. + const MDNode *getTBAAInfo() const { return TBAAInfo; } + bool isLoad() const { return Flags & MOLoad; } bool isStore() const { return Flags & MOStore; } bool isVolatile() const { return Flags & MOVolatile; } @@ -99,7 +150,8 @@ public: /// setValue - Change the SourceValue for this MachineMemOperand. This /// should only be used when an object is being relocated and all references /// to it are being updated. - void setValue(const Value *NewSV) { V = NewSV; } + void setValue(const Value *NewSV) { PtrInfo.V = NewSV; } + void setOffset(int64_t NewOffset) { PtrInfo.Offset = NewOffset; } /// Profile - Gather unique data for the object. /// diff --git a/include/llvm/CodeGen/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h index 0e719c8..6bc80b0 100644 --- a/include/llvm/CodeGen/MachineModuleInfo.h +++ b/include/llvm/CodeGen/MachineModuleInfo.h @@ -39,7 +39,7 @@ #include "llvm/Support/Dwarf.h" #include "llvm/Support/DebugLoc.h" #include "llvm/Support/ValueHandle.h" -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" @@ -57,7 +57,7 @@ class MachineFunction; class Module; class PointerType; class StructType; - + /// MachineModuleInfoImpl - This class can be derived from and used by targets /// to hold private target-specific information for each Module. Objects of /// type are accessed/created with MMI::getInfo and destroyed when the @@ -70,8 +70,8 @@ public: protected: static SymbolListTy GetSortedStubs(const DenseMap<MCSymbol*, StubValueTy>&); }; - - + + //===----------------------------------------------------------------------===// /// LandingPadInfo - This structure is used to retain landing pad info for @@ -90,19 +90,19 @@ struct LandingPadInfo { }; class MMIAddrLabelMap; - + //===----------------------------------------------------------------------===// /// MachineModuleInfo - This class contains meta information specific to a -/// module. Queries can be made by different debugging and exception handling +/// module. Queries can be made by different debugging and exception handling /// schemes and reformated for specific use. /// class MachineModuleInfo : public ImmutablePass { /// Context - This is the MCContext used for the entire code generator. MCContext Context; - + /// TheModule - This is the LLVM Module being worked on. const Module *TheModule; - + /// ObjFileMMI - This is the object-file-format-specific implementation of /// MachineModuleInfoImpl, which lets targets accumulate whatever info they /// want. @@ -111,7 +111,7 @@ class MachineModuleInfo : public ImmutablePass { // 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; - + // LandingPads - List of LandingPadInfo describing the landing pad information // in the current function. std::vector<LandingPadInfo> LandingPads; @@ -145,18 +145,22 @@ class MachineModuleInfo : public ImmutablePass { /// llvm.compiler.used. SmallPtrSet<const Function *, 32> UsedFunctions; - + /// AddrLabelSymbols - This map keeps track of which symbol is being used for /// the specified basic block's address of label. MMIAddrLabelMap *AddrLabelSymbols; - + bool CallsEHReturn; bool CallsUnwindInit; - + /// DbgInfoAvailable - True if debugging information is available /// in this module. bool DbgInfoAvailable; + /// True if this module calls VarArg function with floating point arguments. + /// This is used to emit an undefined reference to fltused on Windows targets. + bool CallsExternalVAFunctionWithFloatingPointArguments; + public: static char ID; // Pass identification, replacement for typeid @@ -166,22 +170,23 @@ public: VariableDbgInfoMapTy VariableDbgInfo; MachineModuleInfo(); // DUMMY CONSTRUCTOR, DO NOT CALL. - MachineModuleInfo(const MCAsmInfo &MAI); // Real constructor. + // Real constructor. + MachineModuleInfo(const MCAsmInfo &MAI, const TargetAsmInfo *TAI); ~MachineModuleInfo(); - + bool doInitialization(); bool doFinalization(); /// EndFunction - Discard function meta information. /// void EndFunction(); - + const MCContext &getContext() const { return Context; } MCContext &getContext() { return Context; } void setModule(const Module *M) { TheModule = M; } const Module *getModule() const { return TheModule; } - + /// getInfo - Keep track of various per-function pieces of information for /// backends that would like to do so. /// @@ -191,32 +196,40 @@ public: ObjFileMMI = new Ty(*this); return *static_cast<Ty*>(ObjFileMMI); } - + template<typename Ty> const Ty &getObjFileInfo() const { return const_cast<MachineModuleInfo*>(this)->getObjFileInfo<Ty>(); } - + /// AnalyzeModule - Scan the module for global debug information. /// void AnalyzeModule(const Module &M); - + /// hasDebugInfo - Returns true if valid debug info is present. /// bool hasDebugInfo() const { return DbgInfoAvailable; } - void setDebugInfoAvailability(bool avail) { DbgInfoAvailable = true; } + void setDebugInfoAvailability(bool avail) { DbgInfoAvailable = avail; } bool callsEHReturn() const { return CallsEHReturn; } void setCallsEHReturn(bool b) { CallsEHReturn = b; } bool callsUnwindInit() const { return CallsUnwindInit; } void setCallsUnwindInit(bool b) { CallsUnwindInit = b; } - + + bool callsExternalVAFunctionWithFloatingPointArguments() const { + return CallsExternalVAFunctionWithFloatingPointArguments; + } + + void setCallsExternalVAFunctionWithFloatingPointArguments(bool b) { + CallsExternalVAFunctionWithFloatingPointArguments = b; + } + /// getFrameMoves - Returns a reference to a list of moves done in the current /// function's prologue. Used to construct frame maps for debug and exception /// handling comsumers. std::vector<MachineMove> &getFrameMoves() { return FrameMoves; } - + /// getAddrLabelSymbol - Return the symbol to be used for the specified basic /// block when its address is taken. This cannot be its normal LBB label /// because the block may be accessed outside its containing function. @@ -226,15 +239,15 @@ public: /// basic block when its address is taken. If other blocks were RAUW'd to /// this one, we may have to emit them as well, return the whole set. std::vector<MCSymbol*> getAddrLabelSymbolToEmit(const BasicBlock *BB); - + /// takeDeletedSymbolsForFunction - If the specified function has had any /// references to address-taken blocks generated, but the block got deleted, /// return the symbol now so we can emit it. This prevents emitting a /// reference to a symbol that has no definition. - void takeDeletedSymbolsForFunction(const Function *F, + void takeDeletedSymbolsForFunction(const Function *F, std::vector<MCSymbol*> &Result); - + //===- EH ---------------------------------------------------------------===// /// getOrCreateLandingPadInfo - Find or create an LandingPadInfo for the @@ -245,11 +258,11 @@ public: /// associate it with a try landing pad block. void addInvoke(MachineBasicBlock *LandingPad, MCSymbol *BeginLabel, MCSymbol *EndLabel); - - /// addLandingPad - Add a new panding pad. Returns the label ID for the + + /// addLandingPad - Add a new panding pad. Returns the label ID for the /// landing pad entry. MCSymbol *addLandingPad(MachineBasicBlock *LandingPad); - + /// addPersonality - Provide the personality function for the exception /// information. void addPersonality(MachineBasicBlock *LandingPad, @@ -285,7 +298,7 @@ public: /// void addCleanup(MachineBasicBlock *LandingPad); - /// getTypeIDFor - Return the type id for the specified typeinfo. This is + /// getTypeIDFor - Return the type id for the specified typeinfo. This is /// function wide. unsigned getTypeIDFor(const GlobalVariable *TI); @@ -296,7 +309,7 @@ public: /// TidyLandingPads - Remap landing pad labels and remove any deleted landing /// pads. void TidyLandingPads(DenseMap<MCSymbol*, uintptr_t> *LPMap = 0); - + /// getLandingPads - Return a reference to the landing pad info for the /// current function. const std::vector<LandingPadInfo> &getLandingPads() const { diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h index afa2c29..8acc949 100644 --- a/include/llvm/CodeGen/MachineOperand.h +++ b/include/llvm/CodeGen/MachineOperand.h @@ -14,11 +14,11 @@ #ifndef LLVM_CODEGEN_MACHINEOPERAND_H #define LLVM_CODEGEN_MACHINEOPERAND_H -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include <cassert> namespace llvm { - + class BlockAddress; class ConstantFP; class GlobalValue; @@ -30,7 +30,7 @@ class TargetMachine; class TargetRegisterInfo; class raw_ostream; class MCSymbol; - + /// MachineOperand class - Representation of each machine instruction operand. /// class MachineOperand { @@ -54,21 +54,21 @@ private: /// OpKind - Specify what kind of operand this is. This discriminates the /// union. unsigned char OpKind; // MachineOperandType - + /// SubReg - Subregister number, only valid for MO_Register. A value of 0 /// indicates the MO_Register has no subReg. unsigned char SubReg; - + /// TargetFlags - This is a set of target-specific operand flags. unsigned char TargetFlags; - + /// IsDef/IsImp/IsKill/IsDead flags - These are only valid for MO_Register /// operands. - + /// IsDef - True if this is a def, false if this is a use of the register. /// bool IsDef : 1; - + /// IsImp - True if this is an implicit def or use, false if it is explicit. /// bool IsImp : 1; @@ -94,7 +94,16 @@ private: /// not a real instruction. Such uses should be ignored during codegen. bool IsDebug : 1; - /// ParentMI - This is the instruction that this operand is embedded into. + /// SmallContents - Thisreally should be part of the Contents union, but lives + /// out here so we can get a better packed struct. + /// MO_Register: Register number. + /// OffsetedInfo: Low bits of offset. + union { + unsigned RegNo; // For MO_Register. + unsigned OffsetLo; // Matches Contents.OffsetedInfo.OffsetHi. + } SmallContents; + + /// ParentMI - This is the instruction that this operand is embedded into. /// This is valid for all operand types, when the operand is in an instr. MachineInstr *ParentMI; @@ -107,11 +116,11 @@ private: MCSymbol *Sym; // For MO_MCSymbol struct { // For MO_Register. - unsigned RegNo; + // Register number is in SmallContents.RegNo. MachineOperand **Prev; // Access list for register. MachineOperand *Next; } Reg; - + /// OffsetedInfo - This struct contains the offset and an object identifier. /// this represent the object as with an optional offset from it. struct { @@ -121,10 +130,11 @@ private: const GlobalValue *GV; // For MO_GlobalAddress. const BlockAddress *BA; // For MO_BlockAddress. } Val; - int64_t Offset; // An offset from the object. + // Low bits of offset are in SmallContents.OffsetLo. + int OffsetHi; // An offset from the object, high 32 bits. } OffsetedInfo; } Contents; - + explicit MachineOperand(MachineOperandType K) : OpKind(K), ParentMI(0) { TargetFlags = 0; } @@ -132,17 +142,27 @@ public: /// getType - Returns the MachineOperandType for this operand. /// MachineOperandType getType() const { return (MachineOperandType)OpKind; } - + unsigned char getTargetFlags() const { return TargetFlags; } void setTargetFlags(unsigned char F) { TargetFlags = F; } void addTargetFlag(unsigned char F) { TargetFlags |= F; } - + /// getParent - Return the instruction that this operand belongs to. /// MachineInstr *getParent() { return ParentMI; } const MachineInstr *getParent() const { return ParentMI; } - + + /// clearParent - Reset the parent pointer. + /// + /// The MachineOperand copy constructor also copies ParentMI, expecting the + /// original to be deleted. If a MachineOperand is ever stored outside a + /// MachineInstr, the parent pointer must be cleared. + /// + /// Never call clearParent() on an operand in a MachineInstr. + /// + void clearParent() { ParentMI = 0; } + void print(raw_ostream &os, const TargetMachine *TM = 0) const; //===--------------------------------------------------------------------===// @@ -180,44 +200,44 @@ public: /// getReg - Returns the register number. unsigned getReg() const { assert(isReg() && "This is not a register operand!"); - return Contents.Reg.RegNo; + return SmallContents.RegNo; } - + unsigned getSubReg() const { assert(isReg() && "Wrong MachineOperand accessor"); return (unsigned)SubReg; } - - bool isUse() const { + + bool isUse() const { assert(isReg() && "Wrong MachineOperand accessor"); return !IsDef; } - + bool isDef() const { assert(isReg() && "Wrong MachineOperand accessor"); return IsDef; } - - bool isImplicit() const { + + bool isImplicit() const { assert(isReg() && "Wrong MachineOperand accessor"); return IsImp; } - + bool isDead() const { assert(isReg() && "Wrong MachineOperand accessor"); return IsDead; } - + bool isKill() const { assert(isReg() && "Wrong MachineOperand accessor"); return IsKill; } - + bool isUndef() const { assert(isReg() && "Wrong MachineOperand accessor"); return IsUndef; } - + bool isEarlyClobber() const { assert(isReg() && "Wrong MachineOperand accessor"); return IsEarlyClobber; @@ -238,11 +258,11 @@ public: //===--------------------------------------------------------------------===// // Mutators for Register Operands //===--------------------------------------------------------------------===// - + /// Change the register this operand corresponds to. /// void setReg(unsigned Reg); - + void setSubReg(unsigned subReg) { assert(isReg() && "Wrong MachineOperand accessor"); SubReg = (unsigned char)subReg; @@ -266,14 +286,14 @@ public: assert((Val || !isDebug()) && "Marking a debug operation as def"); IsDef = !Val; } - + void setIsDef(bool Val = true) { assert(isReg() && "Wrong MachineOperand accessor"); assert((!Val || !isDebug()) && "Marking a debug operation as def"); IsDef = Val; } - void setImplicit(bool Val = true) { + void setImplicit(bool Val = true) { assert(isReg() && "Wrong MachineOperand accessor"); IsImp = Val; } @@ -283,7 +303,7 @@ public: assert((!Val || !isDebug()) && "Marking a debug operation as kill"); IsKill = Val; } - + void setIsDead(bool Val = true) { assert(isReg() && IsDef && "Wrong MachineOperand accessor"); IsDead = Val; @@ -293,7 +313,7 @@ public: assert(isReg() && "Wrong MachineOperand accessor"); IsUndef = Val; } - + void setIsEarlyClobber(bool Val = true) { assert(isReg() && IsDef && "Wrong MachineOperand accessor"); IsEarlyClobber = Val; @@ -307,17 +327,17 @@ public: //===--------------------------------------------------------------------===// // Accessors for various operand types. //===--------------------------------------------------------------------===// - + int64_t getImm() const { assert(isImm() && "Wrong MachineOperand accessor"); return Contents.ImmVal; } - + const ConstantFP *getFPImm() const { assert(isFPImm() && "Wrong MachineOperand accessor"); return Contents.CFP; } - + MachineBasicBlock *getMBB() const { assert(isMBB() && "Wrong MachineOperand accessor"); return Contents.MBB; @@ -328,7 +348,7 @@ public: "Wrong MachineOperand accessor"); return Contents.OffsetedInfo.Val.Index; } - + const GlobalValue *getGlobal() const { assert(isGlobal() && "Wrong MachineOperand accessor"); return Contents.OffsetedInfo.Val.GV; @@ -343,15 +363,16 @@ public: assert(isMCSymbol() && "Wrong MachineOperand accessor"); return Contents.Sym; } - + /// getOffset - Return the offset from the symbol in this operand. This always /// returns 0 for ExternalSymbol operands. int64_t getOffset() const { assert((isGlobal() || isSymbol() || isCPI() || isBlockAddress()) && "Wrong MachineOperand accessor"); - return Contents.OffsetedInfo.Offset; + return (int64_t(Contents.OffsetedInfo.OffsetHi) << 32) | + SmallContents.OffsetLo; } - + const char *getSymbolName() const { assert(isSymbol() && "Wrong MachineOperand accessor"); return Contents.OffsetedInfo.Val.SymbolName; @@ -361,11 +382,11 @@ public: assert(isMetadata() && "Wrong MachineOperand accessor"); return Contents.MD; } - + //===--------------------------------------------------------------------===// // Mutators for various operand types. //===--------------------------------------------------------------------===// - + void setImm(int64_t immVal) { assert(isImm() && "Wrong MachineOperand mutator"); Contents.ImmVal = immVal; @@ -374,56 +395,57 @@ public: void setOffset(int64_t Offset) { assert((isGlobal() || isSymbol() || isCPI() || isBlockAddress()) && "Wrong MachineOperand accessor"); - Contents.OffsetedInfo.Offset = Offset; + SmallContents.OffsetLo = unsigned(Offset); + Contents.OffsetedInfo.OffsetHi = int(Offset >> 32); } - + void setIndex(int Idx) { assert((isFI() || isCPI() || isJTI()) && "Wrong MachineOperand accessor"); Contents.OffsetedInfo.Val.Index = Idx; } - + void setMBB(MachineBasicBlock *MBB) { assert(isMBB() && "Wrong MachineOperand accessor"); Contents.MBB = MBB; } - + //===--------------------------------------------------------------------===// // Other methods. //===--------------------------------------------------------------------===// - + /// isIdenticalTo - Return true if this operand is identical to the specified /// operand. Note: This method ignores isKill and isDead properties. bool isIdenticalTo(const MachineOperand &Other) const; - + /// ChangeToImmediate - Replace this operand with a new immediate operand of /// the specified value. If an operand is known to be an immediate already, /// the setImm method should be used. void ChangeToImmediate(int64_t ImmVal); - + /// ChangeToRegister - Replace this operand with a new register operand of /// the specified value. If an operand is known to be an register already, /// the setReg method should be used. void ChangeToRegister(unsigned Reg, bool isDef, bool isImp = false, bool isKill = false, bool isDead = false, bool isUndef = false, bool isDebug = false); - + //===--------------------------------------------------------------------===// // Construction methods. //===--------------------------------------------------------------------===// - + static MachineOperand CreateImm(int64_t Val) { MachineOperand Op(MachineOperand::MO_Immediate); Op.setImm(Val); return Op; } - + static MachineOperand CreateFPImm(const ConstantFP *CFP) { MachineOperand Op(MachineOperand::MO_FPImmediate); Op.Contents.CFP = CFP; return Op; } - + static MachineOperand CreateReg(unsigned Reg, bool isDef, bool isImp = false, bool isKill = false, bool isDead = false, bool isUndef = false, @@ -438,7 +460,7 @@ public: Op.IsUndef = isUndef; Op.IsEarlyClobber = isEarlyClobber; Op.IsDebug = isDebug; - Op.Contents.Reg.RegNo = Reg; + Op.SmallContents.RegNo = Reg; Op.Contents.Reg.Prev = 0; Op.Contents.Reg.Next = 0; Op.SubReg = SubReg; @@ -506,7 +528,7 @@ public: Op.Contents.Sym = Sym; return Op; } - + friend class MachineInstr; friend class MachineRegisterInfo; private: @@ -521,7 +543,7 @@ private: assert(isReg() && "Can only add reg operand to use lists"); return Contents.Reg.Prev != 0; } - + /// AddRegOperandToRegInfo - Add this register operand to the specified /// MachineRegisterInfo. If it is null, then the next/prev fields should be /// explicitly nulled out. diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h index 066c91b..79ff714 100644 --- a/include/llvm/CodeGen/MachineRegisterInfo.h +++ b/include/llvm/CodeGen/MachineRegisterInfo.h @@ -16,6 +16,9 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/ADT/BitVector.h" +#include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/DebugLoc.h" #include <vector> namespace llvm { @@ -24,13 +27,12 @@ namespace llvm { /// registers, including vreg register classes, use/def chains for registers, /// etc. class MachineRegisterInfo { - /// VRegInfo - Information we keep for each virtual register. The entries in - /// this vector are actually converted to vreg numbers by adding the - /// TargetRegisterInfo::FirstVirtualRegister delta to their index. + /// VRegInfo - Information we keep for each virtual register. /// /// Each element in this list contains the register class of the vreg and the /// start of the use/def list for the register. - std::vector<std::pair<const TargetRegisterClass*, MachineOperand*> > VRegInfo; + IndexedMap<std::pair<const TargetRegisterClass*, MachineOperand*>, + VirtReg2IndexFunctor> VRegInfo; /// RegClassVRegMap - This vector acts as a map from TargetRegisterClass to /// virtual registers. For each target register class, it keeps a list of @@ -44,7 +46,7 @@ class MachineRegisterInfo { /// register for allocation. For example, if the hint is <0, 1024>, it means /// the allocator should prefer the physical register allocated to the virtual /// register of the hint. - std::vector<std::pair<unsigned, unsigned> > RegAllocHints; + IndexedMap<std::pair<unsigned, unsigned>, VirtReg2IndexFunctor> RegAllocHints; /// PhysRegUseDefLists - This is an array of the head of the use/def list for /// physical registers. @@ -64,7 +66,10 @@ class MachineRegisterInfo { /// stored in the second element. std::vector<std::pair<unsigned, unsigned> > LiveIns; std::vector<unsigned> LiveOuts; - + + /// LiveInLocs - Keep track of location livein registers. + DenseMap<unsigned, DebugLoc> LiveInLocs; + MachineRegisterInfo(const MachineRegisterInfo&); // DO NOT IMPLEMENT void operator=(const MachineRegisterInfo&); // DO NOT IMPLEMENT public: @@ -159,17 +164,15 @@ public: /// getRegUseDefListHead - Return the head pointer for the register use/def /// list for the specified virtual or physical register. MachineOperand *&getRegUseDefListHead(unsigned RegNo) { - if (RegNo < TargetRegisterInfo::FirstVirtualRegister) - return PhysRegUseDefLists[RegNo]; - RegNo -= TargetRegisterInfo::FirstVirtualRegister; - return VRegInfo[RegNo].second; + if (TargetRegisterInfo::isVirtualRegister(RegNo)) + return VRegInfo[RegNo].second; + return PhysRegUseDefLists[RegNo]; } MachineOperand *getRegUseDefListHead(unsigned RegNo) const { - if (RegNo < TargetRegisterInfo::FirstVirtualRegister) - return PhysRegUseDefLists[RegNo]; - RegNo -= TargetRegisterInfo::FirstVirtualRegister; - return VRegInfo[RegNo].second; + if (TargetRegisterInfo::isVirtualRegister(RegNo)) + return VRegInfo[RegNo].second; + return PhysRegUseDefLists[RegNo]; } /// getVRegDef - Return the machine instr that defines the specified virtual @@ -194,8 +197,6 @@ public: /// getRegClass - Return the register class of the specified virtual register. /// const TargetRegisterClass *getRegClass(unsigned Reg) const { - Reg -= TargetRegisterInfo::FirstVirtualRegister; - assert(Reg < VRegInfo.size() && "Invalid vreg!"); return VRegInfo[Reg].first; } @@ -203,16 +204,22 @@ public: /// void setRegClass(unsigned Reg, const TargetRegisterClass *RC); + /// constrainRegClass - Constrain the register class of the specified virtual + /// register to be a common subclass of RC and the current register class. + /// Return the new register class, or NULL if no such class exists. + /// This should only be used when the constraint is known to be trivial, like + /// GR32 -> GR32_NOSP. Beware of increasing register pressure. + const TargetRegisterClass *constrainRegClass(unsigned Reg, + const TargetRegisterClass *RC); + /// createVirtualRegister - Create and return a new virtual register in the /// function with the specified register class. /// unsigned createVirtualRegister(const TargetRegisterClass *RegClass); - /// getLastVirtReg - Return the highest currently assigned virtual register. + /// getNumVirtRegs - Return the number of virtual registers created. /// - unsigned getLastVirtReg() const { - return (unsigned)VRegInfo.size()+TargetRegisterInfo::FirstVirtualRegister-1; - } + unsigned getNumVirtRegs() const { return VRegInfo.size(); } /// getRegClassVirtRegs - Return the list of virtual registers of the given /// target register class. @@ -224,8 +231,6 @@ public: /// setRegAllocationHint - Specify a register allocation hint for the /// specified virtual register. void setRegAllocationHint(unsigned Reg, unsigned Type, unsigned PrefReg) { - Reg -= TargetRegisterInfo::FirstVirtualRegister; - assert(Reg < VRegInfo.size() && "Invalid vreg!"); RegAllocHints[Reg].first = Type; RegAllocHints[Reg].second = PrefReg; } @@ -234,8 +239,6 @@ public: /// specified virtual register. std::pair<unsigned, unsigned> getRegAllocationHint(unsigned Reg) const { - Reg -= TargetRegisterInfo::FirstVirtualRegister; - assert(Reg < VRegInfo.size() && "Invalid vreg!"); return RegAllocHints[Reg]; } @@ -273,7 +276,12 @@ public: LiveIns.push_back(std::make_pair(Reg, vreg)); } void addLiveOut(unsigned Reg) { LiveOuts.push_back(Reg); } - + + /// addLiveInLoc - Keep track of location info for live in reg. + void addLiveInLoc(unsigned VReg, DebugLoc DL) { + LiveInLocs[VReg] = DL; + } + // Iteration support for live in/out sets. These sets are kept in sorted // order by their register number. typedef std::vector<std::pair<unsigned,unsigned> >::const_iterator diff --git a/include/llvm/CodeGen/MachineRelocation.h b/include/llvm/CodeGen/MachineRelocation.h index c316785..244b466 100644 --- a/include/llvm/CodeGen/MachineRelocation.h +++ b/include/llvm/CodeGen/MachineRelocation.h @@ -14,7 +14,7 @@ #ifndef LLVM_CODEGEN_MACHINERELOCATION_H #define LLVM_CODEGEN_MACHINERELOCATION_H -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include <cassert> namespace llvm { diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h new file mode 100644 index 0000000..b2224cb --- /dev/null +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -0,0 +1,425 @@ +//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// PBQP Graph class. +// +//===----------------------------------------------------------------------===// + + +#ifndef LLVM_CODEGEN_PBQP_GRAPH_H +#define LLVM_CODEGEN_PBQP_GRAPH_H + +#include "Math.h" + +#include <list> +#include <vector> +#include <map> + +namespace PBQP { + + /// PBQP Graph class. + /// Instances of this class describe PBQP problems. + class Graph { + private: + + // ----- TYPEDEFS ----- + class NodeEntry; + class EdgeEntry; + + typedef std::list<NodeEntry> NodeList; + typedef std::list<EdgeEntry> EdgeList; + + public: + + typedef NodeList::iterator NodeItr; + typedef NodeList::const_iterator ConstNodeItr; + + typedef EdgeList::iterator EdgeItr; + typedef EdgeList::const_iterator ConstEdgeItr; + + private: + + typedef std::list<EdgeItr> AdjEdgeList; + + public: + + typedef AdjEdgeList::iterator AdjEdgeItr; + + private: + + class NodeEntry { + private: + Vector costs; + AdjEdgeList adjEdges; + unsigned degree; + void *data; + public: + NodeEntry(const Vector &costs) : costs(costs), degree(0) {} + Vector& getCosts() { return costs; } + const Vector& getCosts() const { return costs; } + unsigned getDegree() const { return degree; } + AdjEdgeItr edgesBegin() { return adjEdges.begin(); } + AdjEdgeItr edgesEnd() { return adjEdges.end(); } + AdjEdgeItr addEdge(EdgeItr e) { + ++degree; + 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 { + private: + NodeItr node1, node2; + Matrix costs; + AdjEdgeItr node1AEItr, node2AEItr; + void *data; + public: + EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs) + : node1(node1), node2(node2), costs(costs) {} + NodeItr getNode1() const { return node1; } + NodeItr getNode2() const { return node2; } + Matrix& getCosts() { return costs; } + const Matrix& getCosts() const { return costs; } + void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; } + AdjEdgeItr getNode1AEItr() { return node1AEItr; } + void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; } + AdjEdgeItr getNode2AEItr() { return node2AEItr; } + void setData(void *data) { this->data = data; } + void *getData() { return data; } + }; + + // ----- MEMBERS ----- + + NodeList nodes; + unsigned numNodes; + + EdgeList edges; + unsigned numEdges; + + // ----- 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); + } + + EdgeItr addConstructedEdge(const EdgeEntry &e) { + assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() && + "Attempt to add duplicate edge."); + ++numEdges; + EdgeItr edgeItr = edges.insert(edges.end(), e); + EdgeEntry &ne = getEdge(edgeItr); + 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; + } + + inline void copyFrom(const Graph &other); + public: + + /// \brief Construct an empty PBQP graph. + Graph() : numNodes(0), numEdges(0) {} + + /// \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); + } + + /// \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; + } + + /// \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) { + return addConstructedNode(NodeEntry(costs)); + } + + /// \brief Add an edge between the given nodes with the given costs. + /// @param n1Itr First node. + /// @param n2Itr 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() && + "Matrix dimensions mismatch."); + return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); + } + + /// \brief Get the number of nodes in the graph. + /// @return Number of nodes in the graph. + unsigned getNumNodes() const { return numNodes; } + + /// \brief Get the number of edges in the graph. + /// @return Number of edges in the graph. + unsigned getNumEdges() const { return numEdges; } + + /// \brief Get a node's cost vector. + /// @param nItr Node iterator. + /// @return Node cost vector. + Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); } + + /// \brief Get a node's cost vector (const version). + /// @param nItr Node iterator. + /// @return Node cost vector. + const Vector& getNodeCosts(ConstNodeItr nItr) const { + return getNode(nItr).getCosts(); + } + + /// \brief Set a node's data pointer. + /// @param nItr Node iterator. + /// @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); } + + /// \brief Get the node's data pointer. + /// @param nItr Node iterator. + /// @return Pointer to node data. + void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); } + + /// \brief Get an edge's cost matrix. + /// @param eItr Edge iterator. + /// @return Edge cost matrix. + Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); } + + /// \brief Get an edge's cost matrix (const version). + /// @param eItr Edge iterator. + /// @return Edge cost matrix. + const Matrix& getEdgeCosts(ConstEdgeItr eItr) const { + return getEdge(eItr).getCosts(); + } + + /// \brief Set an edge's data pointer. + /// @param eItr Edge iterator. + /// @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); } + + /// \brief Get an edge's data pointer. + /// @param eItr Edge iterator. + /// @return Pointer to edge data. + void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); } + + /// \brief Get a node's degree. + /// @param nItr Node iterator. + /// @return The degree of the node. + unsigned getNodeDegree(NodeItr nItr) const { + return getNode(nItr).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(); } + + /// \brief End iterator for node set. + NodeItr nodesEnd() { return nodes.end(); } + + /// \brief End const iterator for node set. + ConstNodeItr nodesEnd() const { return nodes.end(); } + + /// \brief Begin iterator for edge set. + EdgeItr edgesBegin() { return edges.begin(); } + + /// \brief End iterator for edge set. + EdgeItr edgesEnd() { return edges.end(); } + + /// \brief Get begin iterator for adjacent edge set. + /// @param nItr Node iterator. + /// @return Begin iterator for the set of edges connected to the given node. + AdjEdgeItr adjEdgesBegin(NodeItr nItr) { + return getNode(nItr).edgesBegin(); + } + + /// \brief Get end iterator for adjacent edge set. + /// @param nItr Node iterator. + /// @return End iterator for the set of edges connected to the given node. + AdjEdgeItr adjEdgesEnd(NodeItr nItr) { + return getNode(nItr).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(); + } + + /// \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(); + } + + /// \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) { + return e.getNode2(); + } // else + return e.getNode1(); + } + + /// \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); + aeItr != aeEnd; ++aeItr) { + if ((getEdgeNode1(*aeItr) == n2Itr) || + (getEdgeNode2(*aeItr) == n2Itr)) { + return *aeItr; + } + } + return edges.end(); + } + + /// \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); + } + nodes.erase(nItr); + --numNodes; + } + + /// \brief Remove an edge from the graph. + /// @param eItr Edge iterator. + void removeEdge(EdgeItr eItr) { + EdgeEntry &e = getEdge(eItr); + NodeEntry &n1 = getNode(e.getNode1()); + NodeEntry &n2 = getNode(e.getNode2()); + n1.removeEdge(e.getNode1AEItr()); + n2.removeEdge(e.getNode2AEItr()); + edges.erase(eItr); + --numEdges; + } + + /// \brief Remove all nodes and edges from the graph. + void clear() { + nodes.clear(); + edges.clear(); + numNodes = numEdges = 0; + } + + /// \brief Print a representation of this graph in DOT format. + /// @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"; + } + + os << " edge [ len=" << getNumNodes() << " ]\n"; + + for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); + edgeItr != edgeEnd; ++edgeItr) { + + os << " node" << getEdgeNode1(edgeItr) + << " -- node" << getEdgeNode2(edgeItr) + << " [ label=\""; + + const Matrix &edgeCosts = getEdgeCosts(edgeItr); + + for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { + os << edgeCosts.getRowAsVector(i) << "\\n"; + } + os << "\" ]\n"; + } + os << "}\n"; + } + + }; + + 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; + + for (Graph::ConstNodeItr nItr = other.nodesBegin(), + nEnd = other.nodesEnd(); + nItr != nEnd; ++nItr) { + nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); + } + + } + +} + +#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP diff --git a/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h new file mode 100644 index 0000000..791c227 --- /dev/null +++ b/include/llvm/CodeGen/PBQP/HeuristicBase.h @@ -0,0 +1,246 @@ +//===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PBQP_HEURISTICBASE_H +#define LLVM_CODEGEN_PBQP_HEURISTICBASE_H + +#include "HeuristicSolver.h" + +namespace PBQP { + + /// \brief Abstract base class for heuristic implementations. + /// + /// This class provides a handy base for heuristic implementations with common + /// solver behaviour implemented for a number of methods. + /// + /// To implement your own heuristic using this class as a base you'll have to + /// implement, as a minimum, the following methods: + /// <ul> + /// <li> void addToHeuristicList(Graph::NodeItr) : Add a node to the + /// heuristic reduction list. + /// <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 + /// costs on the given edge. + /// <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new + /// edge into the PBQP graph (by R2). + /// <li> void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the + /// disconnection of the given edge from the given node. + /// <li> A constructor for your derived class : to pass back a reference to + /// the solver which is using this heuristic. + /// </ul> + /// + /// 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. + /// + /// You'll also need to provide NodeData and EdgeData structs in your class. + /// These can be used to attach data relevant to your heuristic to each + /// node/edge in the PBQP graph. + + template <typename HImpl> + class HeuristicBase { + private: + + typedef std::list<Graph::NodeItr> OptimalList; + + HeuristicSolverImpl<HImpl> &s; + Graph &g; + OptimalList optimalList; + + // Return a reference to the derived heuristic. + 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); + } + + public: + + /// \brief Construct an instance with a reference to the given solver. + /// @param solver The solver which is using this heuristic instance. + HeuristicBase(HeuristicSolverImpl<HImpl> &solver) + : s(solver), g(s.getGraph()) { } + + /// \brief Get the solver which is using this heuristic instance. + /// @return The solver which is using this heuristic instance. + /// + /// You can use this method to get access to the solver in your derived + /// heuristic implementation. + HeuristicSolverImpl<HImpl>& getSolver() { return s; } + + /// \brief Get the graph representing the problem to be solved. + /// @return The graph representing the problem to be solved. + Graph& getGraph() { return g; } + + /// \brief Tell the solver to simplify the graph before the reduction phase. + /// @return Whether or not the solver should run a simplification phase + /// prior to the main setup and reduction. + /// + /// HeuristicBase returns true from this method as it's a sensible default, + /// however you can over-ride it in your derived class if you want different + /// behaviour. + bool solverRunSimplify() const { return true; } + + /// \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). + /// + /// HeuristicBase returns true for any node with degree less than 3. This is + /// sane and sensible for many situations, but not all. You can over-ride + /// this method in your derived class if you want a different selection + /// 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) + return true; + // else + return false; + } + + /// \brief Add the given node to the list of nodes to be optimally reduced. + /// @return nItr Node iterator 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); + } + + /// \brief Initialise the heuristic. + /// + /// HeuristicBase iterates over all nodes in the problem and adds them to + /// the appropriate list using addToOptimalReduceList or + /// addToHeuristicReduceList based on the result of shouldOptimallyReduce. + /// + /// This behaviour should be fine for most situations. + void setup() { + for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); + nItr != nEnd; ++nItr) { + if (impl().shouldOptimallyReduce(nItr)) { + addToOptimalReduceList(nItr); + } else { + impl().addToHeuristicReduceList(nItr); + } + } + } + + /// \brief Optimally reduce one of the nodes in the optimal reduce list. + /// @return True if a reduction takes place, false if the optimal reduce + /// list is empty. + /// + /// Selects a node from the optimal reduce list and removes it, applying + /// R0, R1 or R2 as appropriate based on the selected node's degree. + bool optimalReduce() { + if (optimalList.empty()) + return false; + + Graph::NodeItr nItr = 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; + default: assert(false && + "Optimal reductions of degree > 2 nodes is invalid."); + } + + return true; + } + + /// \brief Perform the PBQP reduction process. + /// + /// Reduces the problem to the empty graph by repeated application of the + /// reduction rules R0, R1, R2 and RN. + /// R0, R1 or R2 are always applied if possible before RN is used. + void reduce() { + bool finished = false; + + while (!finished) { + if (!optimalReduce()) { + if (impl().heuristicReduce()) { + getSolver().recordRN(); + } else { + finished = true; + } + } + } + } + + /// \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) { + assert(false && "Must be implemented in derived class."); + } + + /// \brief Heuristically reduce one of the nodes in the heuristic + /// reduce list. + /// @return True if a reduction takes place, false if the heuristic reduce + /// list is empty. + void heuristicReduce() { + assert(false && "Must be implemented in derived class."); + } + + /// \brief Prepare a change in the costs on the given edge. + /// @param eItr Edge iterator. + void preUpdateEdgeCosts(Graph::EdgeItr eItr) { + assert(false && "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) { + assert(false && "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) { + assert(false && "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. + /// + /// 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) { + assert(false && "Must be implemented in derived class."); + } + + /// \brief Clean up any structures used by HeuristicBase. + /// + /// At present this just performs a sanity check: that the optimal reduce + /// list is empty now that reduction has completed. + /// + /// If your derived class has more complex structures which need tearing + /// down you should over-ride this method but include a call back to this + /// implementation. + void cleanup() { + assert(optimalList.empty() && "Nodes left over in optimal reduce list?"); + } + + }; + +} + + +#endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H diff --git a/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h new file mode 100644 index 0000000..35514f9 --- /dev/null +++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h @@ -0,0 +1,616 @@ +//===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H +#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H + +#include "Graph.h" +#include "Solution.h" +#include <vector> +#include <limits> + +namespace PBQP { + + /// \brief Heuristic PBQP solver implementation. + /// + /// This class should usually be created (and destroyed) indirectly via a call + /// to HeuristicSolver<HImpl>::solve(Graph&). + /// See the comments for HeuristicSolver. + /// + /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules, + /// backpropagation phase, and maintains the internal copy of the graph on + /// which the reduction is carried out (the original being kept to facilitate + /// backpropagation). + template <typename HImpl> + class HeuristicSolverImpl { + private: + + typedef typename HImpl::NodeData HeuristicNodeData; + typedef typename HImpl::EdgeData HeuristicEdgeData; + + typedef std::list<Graph::EdgeItr> SolverEdges; + + public: + + /// \brief Iterator type for edges in the solver graph. + typedef SolverEdges::iterator SolverEdgeItr; + + private: + + class NodeData { + public: + NodeData() : solverDegree(0) {} + + HeuristicNodeData& getHeuristicData() { return hData; } + + SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) { + ++solverDegree; + return solverEdges.insert(solverEdges.end(), eItr); + } + + void removeSolverEdge(SolverEdgeItr seItr) { + --solverDegree; + solverEdges.erase(seItr); + } + + SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); } + SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); } + unsigned getSolverDegree() const { return solverDegree; } + void clearSolverEdges() { + solverDegree = 0; + solverEdges.clear(); + } + + private: + HeuristicNodeData hData; + unsigned solverDegree; + SolverEdges solverEdges; + }; + + class EdgeData { + public: + HeuristicEdgeData& getHeuristicData() { return hData; } + + void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) { + this->n1SolverEdgeItr = n1SolverEdgeItr; + } + + SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; } + + void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){ + this->n2SolverEdgeItr = n2SolverEdgeItr; + } + + SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; } + + private: + + HeuristicEdgeData hData; + SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr; + }; + + Graph &g; + HImpl h; + Solution s; + std::vector<Graph::NodeItr> stack; + + typedef std::list<NodeData> NodeDataList; + NodeDataList nodeDataList; + + typedef std::list<EdgeData> EdgeDataList; + EdgeDataList edgeDataList; + + public: + + /// \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) {} + + /// \brief Get the graph being solved by this solver. + /// @return The graph representing the problem instance being solved by this + /// solver. + Graph& getGraph() { return g; } + + /// \brief Get the heuristic data attached to the given node. + /// @param nItr Node iterator. + /// @return The heuristic data attached to the given node. + HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) { + return getSolverNodeData(nItr).getHeuristicData(); + } + + /// \brief Get the heuristic data attached to the given edge. + /// @param eItr Edge iterator. + /// @return The heuristic data attached to the given node. + HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { + return getSolverEdgeData(eItr).getHeuristicData(); + } + + /// \brief Begin iterator for the set of edges adjacent to the given node in + /// the solver graph. + /// @param nItr Node iterator. + /// @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(); + } + + /// \brief End iterator for the set of edges adjacent to the given node in + /// the solver graph. + /// @param nItr Node iterator. + /// @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(); + } + + /// \brief Remove a node from the solver graph. + /// @param eItr Edge iterator 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)); + + n1Data.removeSolverEdge(eData.getN1SolverEdgeItr()); + n2Data.removeSolverEdge(eData.getN2SolverEdgeItr()); + } + + /// \brief Compute a solution to the PBQP problem instance with which this + /// heuristic solver was constructed. + /// @return A solution to the PBQP problem. + /// + /// Performs the full PBQP heuristic solver algorithm, including setup, + /// calls to the heuristic (which will call back to the reduction rules in + /// this class), and cleanup. + Solution computeSolution() { + setup(); + h.setup(); + h.reduce(); + backpropagate(); + h.cleanup(); + cleanup(); + return s; + } + + /// \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); + } + + /// \brief Returns the solver degree of the given node. + /// @param nItr Node iterator 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(); + } + + /// \brief Set the solution of the given node. + /// @param nItr Node iterator to set solution for. + /// @param selection Selection for node. + void setSolution(const Graph::NodeItr &nItr, unsigned selection) { + s.setSelection(nItr, selection); + + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), + aeEnd = g.adjEdgesEnd(nItr); + aeItr != aeEnd; ++aeItr) { + Graph::EdgeItr eItr(*aeItr); + Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr)); + getSolverNodeData(anItr).addSolverEdge(eItr); + } + } + + /// \brief Apply rule R0. + /// @param nItr Node iterator 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 && + "R0 applied to node with degree != 0."); + + // Nothing to do. Just push the node onto the reduction stack. + pushToStack(nItr); + + s.recordR0(); + } + + /// \brief Apply rule R1. + /// @param xnItr Node iterator for node to apply R1 to. + /// + /// Node will be automatically pushed to the solver stack. + void applyR1(Graph::NodeItr xnItr) { + NodeData &nd = getSolverNodeData(xnItr); + assert(nd.getSolverDegree() == 1 && + "R1 applied to node with degree != 1."); + + Graph::EdgeItr eItr = *nd.solverEdgesBegin(); + + 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); + for (unsigned j = 0; j < yCosts.getLength(); ++j) { + PBQPNum min = eCosts[0][j] + xCosts[0]; + for (unsigned i = 1; i < xCosts.getLength(); ++i) { + PBQPNum c = eCosts[i][j] + xCosts[i]; + if (c < min) + min = c; + } + yCosts[j] += min; + } + h.handleRemoveEdge(eItr, ynItr); + } else { + Graph::NodeItr ynItr = g.getEdgeNode1(eItr); + Vector &yCosts = g.getNodeCosts(ynItr); + for (unsigned i = 0; i < yCosts.getLength(); ++i) { + PBQPNum min = eCosts[i][0] + xCosts[0]; + for (unsigned j = 1; j < xCosts.getLength(); ++j) { + PBQPNum c = eCosts[i][j] + xCosts[j]; + if (c < min) + min = c; + } + yCosts[i] += min; + } + h.handleRemoveEdge(eItr, ynItr); + } + removeSolverEdge(eItr); + assert(nd.getSolverDegree() == 0 && + "Degree 1 with edge removed should be 0."); + pushToStack(xnItr); + s.recordR1(); + } + + /// \brief Apply rule R2. + /// @param xnItr Node iterator 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 && + "R2 applied to node with degree != 2."); + + NodeData &nd = getSolverNodeData(xnItr); + const Vector &xCosts = g.getNodeCosts(xnItr); + + SolverEdgeItr aeItr = nd.solverEdgesBegin(); + Graph::EdgeItr yxeItr = *aeItr, + zxeItr = *(++aeItr); + + Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr), + znItr = g.getEdgeOtherNode(zxeItr, xnItr); + + bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr), + flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr); + + const Matrix *yxeCosts = flipEdge1 ? + new Matrix(g.getEdgeCosts(yxeItr).transpose()) : + &g.getEdgeCosts(yxeItr); + + const Matrix *zxeCosts = flipEdge2 ? + new Matrix(g.getEdgeCosts(zxeItr).transpose()) : + &g.getEdgeCosts(zxeItr); + + unsigned xLen = xCosts.getLength(), + yLen = yxeCosts->getRows(), + zLen = zxeCosts->getRows(); + + Matrix delta(yLen, zLen); + + for (unsigned i = 0; i < yLen; ++i) { + for (unsigned j = 0; j < zLen; ++j) { + PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0]; + for (unsigned k = 1; k < xLen; ++k) { + PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k]; + if (c < min) { + min = c; + } + } + delta[i][j] = min; + } + } + + if (flipEdge1) + delete yxeCosts; + + if (flipEdge2) + delete zxeCosts; + + Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr); + bool addedEdge = false; + + if (yzeItr == g.edgesEnd()) { + yzeItr = g.addEdge(ynItr, znItr, delta); + addedEdge = true; + } else { + Matrix &yzeCosts = g.getEdgeCosts(yzeItr); + h.preUpdateEdgeCosts(yzeItr); + if (ynItr == g.getEdgeNode1(yzeItr)) { + yzeCosts += delta; + } else { + yzeCosts += delta.transpose(); + } + } + + bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr); + + if (!addedEdge) { + // If we modified the edge costs let the heuristic know. + h.postUpdateEdgeCosts(yzeItr); + } + + 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); + } + g.removeEdge(yzeItr); + } 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); + } + + h.handleRemoveEdge(yxeItr, ynItr); + removeSolverEdge(yxeItr); + h.handleRemoveEdge(zxeItr, znItr); + removeSolverEdge(zxeItr); + + pushToStack(xnItr); + s.recordR2(); + } + + /// \brief Record an application of the RN rule. + /// + /// For use by the HeuristicBase. + void recordRN() { s.recordRN(); } + + private: + + NodeData& getSolverNodeData(Graph::NodeItr nItr) { + return *static_cast<NodeData*>(g.getNodeData(nItr)); + } + + EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) { + return *static_cast<EdgeData*>(g.getEdgeData(eItr)); + } + + void addSolverEdge(Graph::EdgeItr eItr) { + EdgeData &eData = getSolverEdgeData(eItr); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eItr)); + + eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr)); + eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr)); + } + + void setup() { + if (h.solverRunSimplify()) { + simplify(); + } + + // Create node data objects. + for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); + nItr != nEnd; ++nItr) { + nodeDataList.push_back(NodeData()); + 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); + } + } + + void simplify() { + disconnectTrivialNodes(); + eliminateIndependentEdges(); + } + + // Eliminate trivial nodes. + void disconnectTrivialNodes() { + unsigned numDisconnected = 0; + + for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); + nItr != nEnd; ++nItr) { + + if (g.getNodeCosts(nItr).getLength() == 1) { + + std::vector<Graph::EdgeItr> edgesToRemove; + + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr), + aeEnd = g.adjEdgesEnd(nItr); + aeItr != aeEnd; ++aeItr) { + + Graph::EdgeItr eItr = *aeItr; + + if (g.getEdgeNode1(eItr) == nItr) { + Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr); + g.getNodeCosts(otherNodeItr) += + g.getEdgeCosts(eItr).getRowAsVector(0); + } + else { + Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr); + g.getNodeCosts(otherNodeItr) += + g.getEdgeCosts(eItr).getColAsVector(0); + } + + edgesToRemove.push_back(eItr); + } + + if (!edgesToRemove.empty()) + ++numDisconnected; + + while (!edgesToRemove.empty()) { + g.removeEdge(edgesToRemove.back()); + edgesToRemove.pop_back(); + } + } + } + } + + void eliminateIndependentEdges() { + std::vector<Graph::EdgeItr> edgesToProcess; + unsigned numEliminated = 0; + + for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); + eItr != eEnd; ++eItr) { + edgesToProcess.push_back(eItr); + } + + while (!edgesToProcess.empty()) { + if (tryToEliminateEdge(edgesToProcess.back())) + ++numEliminated; + edgesToProcess.pop_back(); + } + } + + bool tryToEliminateEdge(Graph::EdgeItr eItr) { + if (tryNormaliseEdgeMatrix(eItr)) { + g.removeEdge(eItr); + return true; + } + return false; + } + + bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) { + + 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)); + + for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { + PBQPNum rowMin = infinity; + + for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { + if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin) + rowMin = edgeCosts[r][c]; + } + + uCosts[r] += rowMin; + + if (rowMin != infinity) { + edgeCosts.subFromRow(r, rowMin); + } + else { + edgeCosts.setRow(r, 0); + } + } + + for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { + PBQPNum colMin = infinity; + + for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { + if (uCosts[r] != infinity && edgeCosts[r][c] < colMin) + colMin = edgeCosts[r][c]; + } + + vCosts[c] += colMin; + + if (colMin != infinity) { + edgeCosts.subFromCol(c, colMin); + } + else { + edgeCosts.setCol(c, 0); + } + } + + return edgeCosts.isZero(); + } + + void backpropagate() { + while (!stack.empty()) { + computeSolution(stack.back()); + stack.pop_back(); + } + } + + void computeSolution(Graph::NodeItr nItr) { + + NodeData &nodeData = getSolverNodeData(nItr); + + Vector v(g.getNodeCosts(nItr)); + + // 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); + + if (nItr == g.getEdgeNode1(eItr)) { + Graph::NodeItr adjNode(g.getEdgeNode2(eItr)); + unsigned adjSolution = s.getSelection(adjNode); + v += edgeCosts.getColAsVector(adjSolution); + } + else { + Graph::NodeItr adjNode(g.getEdgeNode1(eItr)); + unsigned adjSolution = s.getSelection(adjNode); + v += edgeCosts.getRowAsVector(adjSolution); + } + + } + + setSolution(nItr, v.minIndex()); + } + + void cleanup() { + h.cleanup(); + nodeDataList.clear(); + edgeDataList.clear(); + } + }; + + /// \brief PBQP heuristic solver class. + /// + /// Given a PBQP Graph g representing a PBQP problem, you can find a solution + /// by calling + /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt> + /// + /// The choice of heuristic for the H parameter will affect both the solver + /// speed and solution quality. The heuristic should be chosen based on the + /// nature of the problem being solved. + /// Currently the only solver included with LLVM is the Briggs heuristic for + /// register allocation. + template <typename HImpl> + class HeuristicSolver { + public: + static Solution solve(Graph &g) { + HeuristicSolverImpl<HImpl> hs(g); + return hs.computeSolution(); + } + }; + +} + +#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h new file mode 100644 index 0000000..47a287c --- /dev/null +++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h @@ -0,0 +1,464 @@ +//===-- Briggs.h --- Briggs Heuristic for PBQP ------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This class implements the Briggs test for "allocability" of nodes in a +// PBQP graph representing a register allocation problem. Nodes which can be +// proven allocable (by a safe and relatively accurate test) are removed from +// the PBQP graph first. If no provably allocable node is present in the graph +// then the node with the minimal spill-cost to degree ratio is removed. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H +#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H + +#include "../HeuristicSolver.h" +#include "../HeuristicBase.h" + +#include <set> +#include <limits> + +namespace PBQP { + namespace Heuristics { + + /// \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 + /// corresponding node. Edge cost matrices are likewise assumed to represent + /// register constraints. + /// If one or more nodes can be proven allocable by this heuristic (by + /// inspection of their constraint matrices) then the allocable node of + /// highest degree is selected for the next reduction and pushed to the + /// 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. + 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)) + return true; + return false; + } + private: + HeuristicSolverImpl<Briggs> *s; + }; + + class SpillCostComparator { + 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); + + PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr); + PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr); + + if (cost1 < cost2) + return true; + return false; + } + + private: + HeuristicSolverImpl<Briggs> *s; + Graph *g; + }; + + typedef std::list<Graph::NodeItr> RNAllocableList; + typedef RNAllocableList::iterator RNAllocableListItr; + + typedef std::list<Graph::NodeItr> RNUnallocableList; + typedef RNUnallocableList::iterator RNUnallocableListItr; + + public: + + struct NodeData { + typedef std::vector<unsigned> UnsafeDegreesArray; + bool isHeuristic, isAllocable, isInitialized; + unsigned numDenied, numSafe; + UnsafeDegreesArray unsafeDegrees; + RNAllocableListItr rnaItr; + RNUnallocableListItr rnuItr; + + NodeData() + : isHeuristic(false), isAllocable(false), isInitialized(false), + numDenied(0), numSafe(0) { } + }; + + struct EdgeData { + typedef std::vector<unsigned> UnsafeArray; + unsigned worst, reverseWorst; + UnsafeArray unsafe, reverseUnsafe; + bool isUpToDate; + + EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {} + }; + + /// \brief Construct an instance of the Briggs heuristic. + /// @param solver A reference to the solver which is using this heuristic. + Briggs(HeuristicSolverImpl<Briggs> &solver) : + HeuristicBase<Briggs>(solver) {} + + /// \brief Determine whether a node should be reduced using optimal + /// reduction. + /// @param nItr Node iterator to be considered. + /// @return True if the given node should be optimally reduced, false + /// otherwise. + /// + /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one + /// exception. Nodes whose spill cost (element 0 of their cost vector) is + /// 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) { + return true; + } + // else + return false; + } + + /// \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); + nd.isHeuristic = true; + if (nd.isAllocable) { + nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); + } else { + nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr); + } + } + + /// \brief Heuristically reduce one of the nodes in the heuristic + /// reduce list. + /// @return True if a reduction takes place, false if the heuristic reduce + /// list is empty. + /// + /// If the list of allocable nodes is non-empty a node is selected + /// from it and pushed to the stack. Otherwise if the non-allocable list + /// is non-empty a node is selected from it and pushed to the stack. + /// If both lists are empty the method simply returns false with no action + /// taken. + bool heuristicReduce() { + if (!rnAllocableList.empty()) { + RNAllocableListItr rnaItr = + min_element(rnAllocableList.begin(), rnAllocableList.end(), + LinkDegreeComparator(getSolver())); + Graph::NodeItr nItr = *rnaItr; + rnAllocableList.erase(rnaItr); + handleRemoveNode(nItr); + getSolver().pushToStack(nItr); + return true; + } else if (!rnUnallocableList.empty()) { + RNUnallocableListItr rnuItr = + min_element(rnUnallocableList.begin(), rnUnallocableList.end(), + SpillCostComparator(getSolver())); + Graph::NodeItr nItr = *rnuItr; + rnUnallocableList.erase(rnuItr); + handleRemoveNode(nItr); + getSolver().pushToStack(nItr); + return true; + } + // else + return false; + } + + /// \brief Prepare a change in the costs on the given edge. + /// @param eItr Edge iterator. + void preUpdateEdgeCosts(Graph::EdgeItr eItr) { + Graph &g = getGraph(); + Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), + n2Itr = g.getEdgeNode2(eItr); + NodeData &n1 = getHeuristicNodeData(n1Itr), + &n2 = getHeuristicNodeData(n2Itr); + + if (n1.isHeuristic) + subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr)); + if (n2.isHeuristic) + subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr)); + + EdgeData &ed = getHeuristicEdgeData(eItr); + ed.isUpToDate = false; + } + + /// \brief Handle the change in the costs on the given edge. + /// @param eItr Edge iterator. + void postUpdateEdgeCosts(Graph::EdgeItr eItr) { + // This is effectively the same as adding a new edge now, since + // we've factored out the costs of the old one. + handleAddEdge(eItr); + } + + /// \brief Handle the addition of a new edge into the PBQP graph. + /// @param eItr Edge iterator 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) { + Graph &g = getGraph(); + Graph::NodeItr n1Itr = g.getEdgeNode1(eItr), + n2Itr = g.getEdgeNode2(eItr); + NodeData &n1 = getHeuristicNodeData(n1Itr), + &n2 = getHeuristicNodeData(n2Itr); + + // If neither node is managed by the heuristic there's nothing to be + // done. + if (!n1.isHeuristic && !n2.isHeuristic) + return; + + // Ok - we need to update at least one node. + computeEdgeContributions(eItr); + + // Update node 1 if it's managed by the heuristic. + if (n1.isHeuristic) { + bool n1WasAllocable = n1.isAllocable; + addEdgeContributions(eItr, n1Itr); + updateAllocability(n1Itr); + if (n1WasAllocable && !n1.isAllocable) { + rnAllocableList.erase(n1.rnaItr); + n1.rnuItr = + rnUnallocableList.insert(rnUnallocableList.end(), n1Itr); + } + } + + // Likewise for node 2. + if (n2.isHeuristic) { + bool n2WasAllocable = n2.isAllocable; + addEdgeContributions(eItr, n2Itr); + updateAllocability(n2Itr); + if (n2WasAllocable && !n2.isAllocable) { + rnAllocableList.erase(n2.rnaItr); + n2.rnuItr = + rnUnallocableList.insert(rnUnallocableList.end(), n2Itr); + } + } + } + + /// \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. + /// + /// 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); + + // If the node is not managed by the heuristic there's nothing to be + // done. + if (!nd.isHeuristic) + return; + + EdgeData &ed = getHeuristicEdgeData(eItr); + (void)ed; + assert(ed.isUpToDate && "Edge data is not up to date."); + + // Update node. + bool ndWasAllocable = nd.isAllocable; + subtractEdgeContributions(eItr, nItr); + updateAllocability(nItr); + + // If the node has gone optimal... + if (shouldOptimallyReduce(nItr)) { + nd.isHeuristic = false; + addToOptimalReduceList(nItr); + if (ndWasAllocable) { + rnAllocableList.erase(nd.rnaItr); + } else { + rnUnallocableList.erase(nd.rnuItr); + } + } else { + // Node didn't go optimal, but we might have to move it + // from "unallocable" to "allocable". + if (!ndWasAllocable && nd.isAllocable) { + rnUnallocableList.erase(nd.rnuItr); + nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr); + } + } + } + + private: + + NodeData& getHeuristicNodeData(Graph::NodeItr nItr) { + return getSolver().getHeuristicNodeData(nItr); + } + + EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) { + return getSolver().getHeuristicEdgeData(eItr); + } + + // 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); + + if (ed.isUpToDate) + return; // Edge data is already up to date. + + Matrix &eCosts = getGraph().getEdgeCosts(eItr); + + unsigned numRegs = eCosts.getRows() - 1, + numReverseRegs = eCosts.getCols() - 1; + + std::vector<unsigned> rowInfCounts(numRegs, 0), + colInfCounts(numReverseRegs, 0); + + ed.worst = 0; + ed.reverseWorst = 0; + ed.unsafe.clear(); + ed.unsafe.resize(numRegs, 0); + ed.reverseUnsafe.clear(); + ed.reverseUnsafe.resize(numReverseRegs, 0); + + for (unsigned i = 0; i < numRegs; ++i) { + for (unsigned j = 0; j < numReverseRegs; ++j) { + if (eCosts[i + 1][j + 1] == + std::numeric_limits<PBQPNum>::infinity()) { + ed.unsafe[i] = 1; + ed.reverseUnsafe[j] = 1; + ++rowInfCounts[i]; + ++colInfCounts[j]; + + if (colInfCounts[j] > ed.worst) { + ed.worst = colInfCounts[j]; + } + + if (rowInfCounts[i] > ed.reverseWorst) { + ed.reverseWorst = rowInfCounts[i]; + } + } + } + } + + ed.isUpToDate = true; + } + + // 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); + + 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); + 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 (nd.unsafeDegrees[r]==0) { + --nd.numSafe; + } + ++nd.unsafeDegrees[r]; + } + } + } + + // 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); + + 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); + 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 (nd.unsafeDegrees[r] == 1) { + ++nd.numSafe; + } + --nd.unsafeDegrees[r]; + } + } + } + + void updateAllocability(Graph::NodeItr nItr) { + NodeData &nd = getHeuristicNodeData(nItr); + unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; + nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0; + } + + void initializeNode(Graph::NodeItr nItr) { + NodeData &nd = getHeuristicNodeData(nItr); + + if (nd.isInitialized) + return; // Node data is already up to date. + + unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1; + + nd.numDenied = 0; + nd.numSafe = numRegs; + nd.unsafeDegrees.resize(numRegs, 0); + + typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; + + for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr), + aeEnd = getSolver().solverEdgesEnd(nItr); + aeItr != aeEnd; ++aeItr) { + + Graph::EdgeItr eItr = *aeItr; + computeEdgeContributions(eItr); + addEdgeContributions(eItr, nItr); + } + + updateAllocability(nItr); + nd.isInitialized = true; + } + + void handleRemoveNode(Graph::NodeItr xnItr) { + typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr; + std::vector<Graph::EdgeItr> edgesToRemove; + for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr), + aeEnd = getSolver().solverEdgesEnd(xnItr); + aeItr != aeEnd; ++aeItr) { + Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr); + handleRemoveEdge(*aeItr, ynItr); + edgesToRemove.push_back(*aeItr); + } + while (!edgesToRemove.empty()) { + getSolver().removeSolverEdge(edgesToRemove.back()); + edgesToRemove.pop_back(); + } + } + + RNAllocableList rnAllocableList; + RNUnallocableList rnUnallocableList; + }; + + } +} + + +#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H diff --git a/include/llvm/CodeGen/PBQP/Math.h b/include/llvm/CodeGen/PBQP/Math.h new file mode 100644 index 0000000..e7598bf --- /dev/null +++ b/include/llvm/CodeGen/PBQP/Math.h @@ -0,0 +1,288 @@ +//===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PBQP_MATH_H +#define LLVM_CODEGEN_PBQP_MATH_H + +#include <cassert> +#include <algorithm> +#include <functional> + +namespace PBQP { + +typedef float PBQPNum; + +/// \brief PBQP Vector class. +class Vector { + public: + + /// \brief Construct a PBQP vector of the given size. + explicit Vector(unsigned length) : + length(length), data(new PBQPNum[length]) { + } + + /// \brief Construct a PBQP vector with initializer. + Vector(unsigned length, PBQPNum initVal) : + length(length), data(new PBQPNum[length]) { + std::fill(data, data + length, initVal); + } + + /// \brief Copy construct a PBQP vector. + Vector(const Vector &v) : + length(v.length), data(new PBQPNum[length]) { + std::copy(v.data, v.data + length, data); + } + + /// \brief Destroy this vector, return its memory. + ~Vector() { delete[] data; } + + /// \brief Assignment operator. + Vector& operator=(const Vector &v) { + delete[] data; + length = v.length; + data = new PBQPNum[length]; + std::copy(v.data, v.data + length, data); + return *this; + } + + /// \brief Return the length of the vector + unsigned getLength() const { + return length; + } + + /// \brief Element access. + PBQPNum& operator[](unsigned index) { + assert(index < length && "Vector element access out of bounds."); + return data[index]; + } + + /// \brief Const element access. + const PBQPNum& operator[](unsigned index) const { + assert(index < length && "Vector element access out of bounds."); + return data[index]; + } + + /// \brief Add another vector to this one. + Vector& operator+=(const Vector &v) { + assert(length == v.length && "Vector length mismatch."); + std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); + return *this; + } + + /// \brief Subtract another vector from this one. + Vector& operator-=(const Vector &v) { + assert(length == v.length && "Vector length mismatch."); + std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); + return *this; + } + + /// \brief Returns the index of the minimum value in this vector + unsigned minIndex() const { + return std::min_element(data, data + length) - data; + } + + private: + unsigned length; + PBQPNum *data; +}; + +/// \brief Output a textual representation of the given vector on the given +/// output stream. +template <typename OStream> +OStream& operator<<(OStream &os, const Vector &v) { + assert((v.getLength() != 0) && "Zero-length vector badness."); + + os << "[ " << v[0]; + for (unsigned i = 1; i < v.getLength(); ++i) { + os << ", " << v[i]; + } + os << " ]"; + + return os; +} + + +/// \brief PBQP Matrix class +class Matrix { + public: + + /// \brief Construct a PBQP Matrix with the given dimensions. + Matrix(unsigned rows, unsigned cols) : + rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { + } + + /// \brief Construct a PBQP Matrix with the given dimensions and initial + /// value. + Matrix(unsigned rows, unsigned cols, PBQPNum initVal) : + rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { + std::fill(data, data + (rows * cols), initVal); + } + + /// \brief Copy construct a PBQP matrix. + Matrix(const Matrix &m) : + rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) { + std::copy(m.data, m.data + (rows * cols), data); + } + + /// \brief Destroy this matrix, return its memory. + ~Matrix() { delete[] data; } + + /// \brief Assignment operator. + Matrix& operator=(const Matrix &m) { + delete[] data; + rows = m.rows; cols = m.cols; + data = new PBQPNum[rows * cols]; + std::copy(m.data, m.data + (rows * cols), data); + return *this; + } + + /// \brief Return the number of rows in this matrix. + unsigned getRows() const { return rows; } + + /// \brief Return the number of cols in this matrix. + unsigned getCols() const { return cols; } + + /// \brief Matrix element access. + PBQPNum* operator[](unsigned r) { + assert(r < rows && "Row out of bounds."); + return data + (r * cols); + } + + /// \brief Matrix element access. + const PBQPNum* operator[](unsigned r) const { + assert(r < rows && "Row out of bounds."); + return data + (r * cols); + } + + /// \brief Returns the given row as a vector. + Vector getRowAsVector(unsigned r) const { + Vector v(cols); + for (unsigned c = 0; c < cols; ++c) + v[c] = (*this)[r][c]; + return v; + } + + /// \brief Returns the given column as a vector. + Vector getColAsVector(unsigned c) const { + Vector v(rows); + for (unsigned r = 0; r < rows; ++r) + v[r] = (*this)[r][c]; + return v; + } + + /// \brief Reset the matrix to the given value. + Matrix& reset(PBQPNum val = 0) { + std::fill(data, data + (rows * cols), val); + return *this; + } + + /// \brief Set a single row of this matrix to the given value. + Matrix& setRow(unsigned r, PBQPNum val) { + assert(r < rows && "Row out of bounds."); + std::fill(data + (r * cols), data + ((r + 1) * cols), val); + return *this; + } + + /// \brief Set a single column of this matrix to the given value. + Matrix& setCol(unsigned c, PBQPNum val) { + assert(c < cols && "Column out of bounds."); + for (unsigned r = 0; r < rows; ++r) + (*this)[r][c] = val; + return *this; + } + + /// \brief Matrix transpose. + Matrix transpose() const { + Matrix m(cols, rows); + for (unsigned r = 0; r < rows; ++r) + for (unsigned c = 0; c < cols; ++c) + m[c][r] = (*this)[r][c]; + return m; + } + + /// \brief Returns the diagonal of the matrix as a vector. + /// + /// Matrix must be square. + Vector diagonalize() const { + assert(rows == cols && "Attempt to diagonalize non-square matrix."); + + Vector v(rows); + for (unsigned r = 0; r < rows; ++r) + v[r] = (*this)[r][r]; + return v; + } + + /// \brief Add the given matrix to this one. + Matrix& operator+=(const Matrix &m) { + assert(rows == m.rows && cols == m.cols && + "Matrix dimensions mismatch."); + std::transform(data, data + (rows * cols), m.data, data, + std::plus<PBQPNum>()); + return *this; + } + + /// \brief Returns the minimum of the given row + PBQPNum getRowMin(unsigned r) const { + assert(r < rows && "Row out of bounds"); + return *std::min_element(data + (r * cols), data + ((r + 1) * cols)); + } + + /// \brief Returns the minimum of the given column + PBQPNum getColMin(unsigned c) const { + PBQPNum minElem = (*this)[0][c]; + for (unsigned r = 1; r < rows; ++r) + if ((*this)[r][c] < minElem) minElem = (*this)[r][c]; + return minElem; + } + + /// \brief Subtracts the given scalar from the elements of the given row. + Matrix& subFromRow(unsigned r, PBQPNum val) { + assert(r < rows && "Row out of bounds"); + std::transform(data + (r * cols), data + ((r + 1) * cols), + data + (r * cols), + std::bind2nd(std::minus<PBQPNum>(), val)); + return *this; + } + + /// \brief Subtracts the given scalar from the elements of the given column. + Matrix& subFromCol(unsigned c, PBQPNum val) { + for (unsigned r = 0; r < rows; ++r) + (*this)[r][c] -= val; + return *this; + } + + /// \brief Returns true if this is a zero matrix. + bool isZero() const { + return find_if(data, data + (rows * cols), + std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) == + data + (rows * cols); + } + + private: + unsigned rows, cols; + PBQPNum *data; +}; + +/// \brief Output a textual representation of the given matrix on the given +/// output stream. +template <typename OStream> +OStream& operator<<(OStream &os, const Matrix &m) { + + assert((m.getRows() != 0) && "Zero-row matrix badness."); + + for (unsigned i = 0; i < m.getRows(); ++i) { + os << m.getRowAsVector(i); + } + + return os; +} + +} + +#endif // LLVM_CODEGEN_PBQP_MATH_H diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h new file mode 100644 index 0000000..57d9b95 --- /dev/null +++ b/include/llvm/CodeGen/PBQP/Solution.h @@ -0,0 +1,94 @@ +//===-- Solution.h ------- PBQP Solution ------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// PBQP Solution class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PBQP_SOLUTION_H +#define LLVM_CODEGEN_PBQP_SOLUTION_H + +#include "Math.h" +#include "Graph.h" + +#include <map> + +namespace PBQP { + + /// \brief Represents a solution to a PBQP problem. + /// + /// To get the selection for each node in the problem use the getSelection method. + class Solution { + private: + + typedef std::map<Graph::ConstNodeItr, unsigned, + NodeItrComparator> SelectionsMap; + SelectionsMap selections; + + unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions; + + public: + + /// \brief Initialise an empty solution. + Solution() + : r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {} + + /// \brief Number of nodes for which selections have been made. + /// @return Number of nodes for which selections have been made. + unsigned numNodes() const { return selections.size(); } + + /// \brief Records a reduction via the R0 rule. Should be called from the + /// solver only. + void recordR0() { ++r0Reductions; } + + /// \brief Returns the number of R0 reductions applied to solve the problem. + unsigned numR0Reductions() const { return r0Reductions; } + + /// \brief Records a reduction via the R1 rule. Should be called from the + /// solver only. + void recordR1() { ++r1Reductions; } + + /// \brief Returns the number of R1 reductions applied to solve the problem. + unsigned numR1Reductions() const { return r1Reductions; } + + /// \brief Records a reduction via the R2 rule. Should be called from the + /// solver only. + void recordR2() { ++r2Reductions; } + + /// \brief Returns the number of R2 reductions applied to solve the problem. + unsigned numR2Reductions() const { return r2Reductions; } + + /// \brief Records a reduction via the RN rule. Should be called from the + /// solver only. + void recordRN() { ++ rNReductions; } + + /// \brief Returns the number of RN reductions applied to solve the problem. + 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; + } + + /// \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); + assert(sItr != selections.end() && "No selection for node."); + return sItr->second; + } + + }; + +} + +#endif // LLVM_CODEGEN_PBQP_SOLUTION_H diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index 4762a39..53aee7a 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -45,10 +45,19 @@ namespace llvm { /// extern char &MachineLoopInfoID; + /// MachineLoopRanges pass - This pass is an on-demand loop coverage + /// analysis pass. + /// + extern char &MachineLoopRangesID; + /// MachineDominators pass - This pass is a machine dominators analysis pass. /// extern char &MachineDominatorsID; + /// EdgeBundles analysis - Bundle machine CFG edges. + /// + extern char &EdgeBundlesID; + /// PHIElimination pass - 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 @@ -66,6 +75,9 @@ namespace llvm { extern char &PreAllocSplittingID; + /// LiveStacks pass. An analysis keeping track of the liveness of stack slots. + extern char &LiveStacksID; + /// SimpleRegisterCoalescing pass. Aggressively coalesces every register /// copy it can. /// @@ -76,6 +88,11 @@ namespace llvm { /// register allocators. extern char &TwoAddressInstructionPassID; + /// SpillPlacement analysis. Suggest optimal placement of spill code between + /// basic blocks. + /// + extern char &SpillPlacementID; + /// UnreachableMachineBlockElimination pass - This pass removes unreachable /// machine basic blocks. extern char &UnreachableMachineBlockElimID; @@ -95,6 +112,16 @@ namespace llvm { /// FunctionPass *createFastRegisterAllocator(); + /// BasicRegisterAllocation Pass - This pass implements a degenerate global + /// register allocator using the basic regalloc framework. + /// + FunctionPass *createBasicRegisterAllocator(); + + /// Greedy register allocation pass - This pass implements a global register + /// allocator for optimized builds. + /// + FunctionPass *createGreedyRegisterAllocator(); + /// LinearScanRegisterAllocation Pass - This pass implements the linear scan /// register allocation algorithm, a global register allocator. /// @@ -103,7 +130,7 @@ namespace llvm { /// PBQPRegisterAllocation Pass - This pass implements the Partitioned Boolean /// Quadratic Prograaming (PBQP) based register allocator. /// - FunctionPass *createPBQPRegisterAllocator(); + FunctionPass *createDefaultPBQPRegisterAllocator(); /// SimpleRegisterCoalescing Pass - Coalesce all copies possible. Can run /// independently of the register allocator. @@ -188,7 +215,7 @@ namespace llvm { /// createMachineVerifierPass - This pass verifies cenerated machine code /// instructions for correctness. - FunctionPass *createMachineVerifierPass(); + FunctionPass *createMachineVerifierPass(const char *Banner = 0); /// createDwarfEHPass - This pass mulches exception handling code into a form /// adapted to code generation. Required if using dwarf exception handling. @@ -205,6 +232,10 @@ namespace llvm { /// addressing. FunctionPass *createLocalStackSlotAllocationPass(); + /// createExpandISelPseudosPass - This pass expands pseudo-instructions. + /// + FunctionPass *createExpandISelPseudosPass(); + } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/PostRAHazardRecognizer.h b/include/llvm/CodeGen/PostRAHazardRecognizer.h deleted file mode 100644 index 24d73cb..0000000 --- a/include/llvm/CodeGen/PostRAHazardRecognizer.h +++ /dev/null @@ -1,94 +0,0 @@ -//=- llvm/CodeGen/PostRAHazardRecognizer.h - Scheduling Support -*- 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 the PostRAHazardRecognizer class, which -// implements hazard-avoidance heuristics for scheduling, based on the -// scheduling itineraries specified for the target. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_EXACTHAZARDRECOGNIZER_H -#define LLVM_CODEGEN_EXACTHAZARDRECOGNIZER_H - -#include "llvm/CodeGen/ScheduleHazardRecognizer.h" -#include "llvm/System/DataTypes.h" - -#include <cassert> -#include <cstring> -#include <string> - -namespace llvm { - -class InstrItineraryData; -class SUnit; - -class PostRAHazardRecognizer : public ScheduleHazardRecognizer { - // ScoreBoard to track function unit usage. ScoreBoard[0] is a - // mask of the FUs in use in the cycle currently being - // schedule. ScoreBoard[1] is a mask for the next cycle. The - // ScoreBoard is used as a circular buffer with the current cycle - // indicated by Head. - class ScoreBoard { - unsigned *Data; - - // The maximum number of cycles monitored by the Scoreboard. This - // value is determined based on the target itineraries to ensure - // that all hazards can be tracked. - size_t Depth; - // Indices into the Scoreboard that represent the current cycle. - size_t Head; - public: - ScoreBoard():Data(NULL), Depth(0), Head(0) { } - ~ScoreBoard() { - delete[] Data; - } - - size_t getDepth() const { return Depth; } - unsigned& operator[](size_t idx) const { - assert(Depth && "ScoreBoard was not initialized properly!"); - - return Data[(Head + idx) % Depth]; - } - - void reset(size_t d = 1) { - if (Data == NULL) { - Depth = d; - Data = new unsigned[Depth]; - } - - memset(Data, 0, Depth * sizeof(Data[0])); - Head = 0; - } - - void advance() { - Head = (Head + 1) % Depth; - } - - // Print the scoreboard. - void dump() const; - }; - - // Itinerary data for the target. - const InstrItineraryData &ItinData; - - ScoreBoard ReservedScoreboard; - ScoreBoard RequiredScoreboard; - -public: - PostRAHazardRecognizer(const InstrItineraryData &ItinData); - - virtual HazardType getHazardType(SUnit *SU); - virtual void Reset(); - virtual void EmitInstruction(SUnit *SU); - virtual void AdvanceCycle(); -}; - -} - -#endif diff --git a/include/llvm/CodeGen/ProcessImplicitDefs.h b/include/llvm/CodeGen/ProcessImplicitDefs.h index 1d743c1..e2ab899 100644 --- a/include/llvm/CodeGen/ProcessImplicitDefs.h +++ b/include/llvm/CodeGen/ProcessImplicitDefs.h @@ -31,7 +31,9 @@ namespace llvm { public: static char ID; - ProcessImplicitDefs() : MachineFunctionPass(ID) {} + ProcessImplicitDefs() : MachineFunctionPass(ID) { + initializeProcessImplicitDefsPass(*PassRegistry::getPassRegistry()); + } virtual void getAnalysisUsage(AnalysisUsage &au) const; diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h new file mode 100644 index 0000000..7e8745e --- /dev/null +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -0,0 +1,167 @@ +//===-- RegAllocPBQP.h ------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the PBQPBuilder interface, for classes which build PBQP +// instances to represent register allocation problems, and the RegAllocPBQP +// interface. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_REGALLOCPBQP_H +#define LLVM_CODEGEN_REGALLOCPBQP_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/PBQP/Graph.h" +#include "llvm/CodeGen/PBQP/Solution.h" + +#include <map> +#include <set> + +namespace llvm { + + class LiveIntervals; + class MachineFunction; + class MachineLoopInfo; + + /// This class wraps up a PBQP instance representing a register allocation + /// problem, plus the structures necessary to map back from the PBQP solution + /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map, + /// and the PBQP option <--> storage location map). + + class PBQPRAProblem { + public: + + typedef SmallVector<unsigned, 16> AllowedSet; + + PBQP::Graph& getGraph() { return graph; } + + const PBQP::Graph& getGraph() const { return graph; } + + /// Record the mapping between the given virtual register and PBQP node, + /// and the set of allowed pregs for the vreg. + /// + /// If you are extending + /// 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, + AllowedRegsItr arBegin, AllowedRegsItr arEnd) { + assert(node2VReg.find(node) == 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; + 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; + + /// Get the PBQP node corresponding to the given virtual register. + PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const; + + /// Returns true if the given PBQP option represents a physical register, + /// false otherwise. + bool isPRegOption(unsigned vreg, unsigned option) const { + // At present we only have spills or pregs, so anything that's not a + // spill is a preg. (This might be extended one day to support remat). + return !isSpillOption(vreg, option); + } + + /// Returns true if the given PBQP option represents spilling, false + /// otherwise. + bool isSpillOption(unsigned vreg, unsigned option) const { + // We hardcode option zero as the spill option. + return option == 0; + } + + /// Returns the allowed set for the given virtual register. + const AllowedSet& getAllowedSet(unsigned vreg) const; + + /// Get PReg for option. + unsigned getPRegForOption(unsigned vreg, unsigned option) const; + + private: + + typedef std::map<PBQP::Graph::ConstNodeItr, unsigned, + PBQP::NodeItrComparator> Node2VReg; + typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node; + typedef std::map<unsigned, AllowedSet> AllowedSetMap; + + PBQP::Graph graph; + Node2VReg node2VReg; + VReg2Node vreg2Node; + + AllowedSetMap allowedSets; + + }; + + /// Builds PBQP instances to represent register allocation problems. Includes + /// spill, interference and coalescing costs by default. You can extend this + /// class to support additional constraints for your architecture. + class PBQPBuilder { + private: + PBQPBuilder(const PBQPBuilder&) {} + void operator=(const PBQPBuilder&) {} + public: + + typedef std::set<unsigned> RegSet; + + /// Default constructor. + PBQPBuilder() {} + + /// Clean up a PBQPBuilder. + virtual ~PBQPBuilder() {} + + /// Build a PBQP instance to represent the register allocation problem for + /// the given MachineFunction. + virtual std::auto_ptr<PBQPRAProblem> build( + MachineFunction *mf, + const LiveIntervals *lis, + const MachineLoopInfo *loopInfo, + const RegSet &vregs); + private: + + void addSpillCosts(PBQP::Vector &costVec, PBQP::PBQPNum spillCost); + + void addInterferenceCosts(PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + const TargetRegisterInfo *tri); + }; + + /// Extended builder which adds coalescing constraints to a problem. + class PBQPBuilderWithCoalescing : public PBQPBuilder { + public: + + /// Build a PBQP instance to represent the register allocation problem for + /// the given MachineFunction. + virtual std::auto_ptr<PBQPRAProblem> build( + MachineFunction *mf, + const LiveIntervals *lis, + const MachineLoopInfo *loopInfo, + const RegSet &vregs); + + private: + + void addPhysRegCoalesce(PBQP::Vector &costVec, unsigned pregOption, + PBQP::PBQPNum benefit); + + void addVirtRegCoalesce(PBQP::Matrix &costMat, + const PBQPRAProblem::AllowedSet &vr1Allowed, + const PBQPRAProblem::AllowedSet &vr2Allowed, + PBQP::PBQPNum benefit); + }; + + FunctionPass* createPBQPRegisterAllocator(std::auto_ptr<PBQPBuilder> builder); +} + +#endif /* LLVM_CODEGEN_REGALLOCPBQP_H */ diff --git a/include/llvm/CodeGen/RegisterCoalescer.h b/include/llvm/CodeGen/RegisterCoalescer.h index 7644433..af0b394 100644 --- a/include/llvm/CodeGen/RegisterCoalescer.h +++ b/include/llvm/CodeGen/RegisterCoalescer.h @@ -12,7 +12,7 @@ // //===----------------------------------------------------------------------===// -#include "llvm/System/IncludeFile.h" +#include "llvm/Support/IncludeFile.h" #include "llvm/CodeGen/LiveInterval.h" #include "llvm/ADT/SmallPtrSet.h" diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 076268b..3864ffd 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -221,6 +221,9 @@ namespace llvm { } }; + template <> + struct isPodLike<SDep> { static const bool value = true; }; + /// SUnit - Scheduling unit. This is a node in the scheduling DAG. class SUnit { private: @@ -229,9 +232,8 @@ namespace llvm { public: SUnit *OrigNode; // If not this, the node from which // this node was cloned. - - // Preds/Succs - The SUnits before/after us in the graph. The boolean value - // is true if the edge is a token chain edge, false if it is a value edge. + + // Preds/Succs - The SUnits before/after us in the graph. SmallVector<SDep, 4> Preds; // All sunit predecessors. SmallVector<SDep, 4> Succs; // All sunit successors. @@ -242,11 +244,13 @@ namespace llvm { unsigned NodeNum; // Entry # of node in the node vector. unsigned NodeQueueId; // Queue id of node. - unsigned short Latency; // Node latency. unsigned NumPreds; // # of SDep::Data preds. unsigned NumSuccs; // # of SDep::Data sucss. unsigned NumPredsLeft; // # of preds not scheduled. unsigned NumSuccsLeft; // # of succs not scheduled. + unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. + unsigned short Latency; // Node latency. + bool isCall : 1; // Is a function call. bool isTwoAddress : 1; // Is a two-address instruction. bool isCommutable : 1; // Is a commutable instruction. bool hasPhysRegDefs : 1; // Has physreg defs that are being used. @@ -267,13 +271,14 @@ namespace llvm { public: const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. const TargetRegisterClass *CopySrcRC; - + /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent /// an SDNode and any nodes flagged to it. SUnit(SDNode *node, unsigned nodenum) : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), - NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), + NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), + NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), + isCall(false), isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isCloned(false), @@ -285,8 +290,9 @@ namespace llvm { /// a MachineInstr. SUnit(MachineInstr *instr, unsigned nodenum) : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), - NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), + NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), + NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), + isCall(false), isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isCloned(false), @@ -297,8 +303,9 @@ namespace llvm { /// SUnit - Construct a placeholder SUnit. SUnit() : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), - NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), + NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), + NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), + isCall(false), isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false), isAvailable(false), isScheduled(false), isScheduleHigh(false), isCloned(false), @@ -320,6 +327,10 @@ namespace llvm { return Node; } + /// isInstr - Return true if this SUnit refers to a machine instruction as + /// opposed to an SDNode. + bool isInstr() const { return Instr; } + /// setInstr - Assign the instruction for the SUnit. /// This may be used during post-regalloc scheduling. void setInstr(MachineInstr *MI) { @@ -337,7 +348,7 @@ namespace llvm { /// addPred - This adds the specified edge as a pred of the current node if /// not already. It also adds the current node as a successor of the /// specified node. - void addPred(const SDep &D); + bool addPred(const SDep &D); /// removePred - This removes the specified edge as a pred of the current /// node if it exists. It also removes the current node as a successor of @@ -347,7 +358,7 @@ namespace llvm { /// getDepth - Return the depth of this node, which is the length of the /// maximum path up to any node with has no predecessors. unsigned getDepth() const { - if (!isDepthCurrent) + if (!isDepthCurrent) const_cast<SUnit *>(this)->ComputeDepth(); return Depth; } @@ -355,7 +366,7 @@ namespace llvm { /// getHeight - Return the height of this node, which is the length of the /// maximum path down to any node with has no successors. unsigned getHeight() const { - if (!isHeightCurrent) + if (!isHeightCurrent) const_cast<SUnit *>(this)->ComputeHeight(); return Height; } @@ -387,7 +398,7 @@ namespace llvm { return true; return false; } - + /// isSucc - Test if node N is a successor of this node. bool isSucc(SUnit *N) { for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) @@ -408,25 +419,38 @@ namespace llvm { //===--------------------------------------------------------------------===// /// SchedulingPriorityQueue - This interface is used to plug different /// priorities computation algorithms into the list scheduler. It implements - /// the interface of a standard priority queue, where nodes are inserted in + /// the interface of a standard priority queue, where nodes are inserted in /// arbitrary order and returned in priority order. The computation of the /// priority and the representation of the queue are totally up to the /// implementation to decide. - /// + /// class SchedulingPriorityQueue { unsigned CurCycle; + bool HasReadyFilter; public: - SchedulingPriorityQueue() : CurCycle(0) {} + SchedulingPriorityQueue(bool rf = false): + CurCycle(0), HasReadyFilter(rf) {} virtual ~SchedulingPriorityQueue() {} - + + virtual bool isBottomUp() const = 0; + virtual void initNodes(std::vector<SUnit> &SUnits) = 0; virtual void addNode(const SUnit *SU) = 0; virtual void updateNode(const SUnit *SU) = 0; virtual void releaseState() = 0; virtual bool empty() const = 0; + + bool hasReadyFilter() const { return HasReadyFilter; } + + virtual bool tracksRegPressure() const { return false; } + + virtual bool isReady(SUnit *) const { + assert(!HasReadyFilter && "The ready filter must override isReady()"); + return true; + } virtual void push(SUnit *U) = 0; - + void push_all(const std::vector<SUnit *> &Nodes) { for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) @@ -437,6 +461,8 @@ namespace llvm { virtual void remove(SUnit *SU) = 0; + virtual void dump(ScheduleDAG *) const {} + /// ScheduledNode - As each node is scheduled, this method is invoked. This /// allows the priority function to adjust the priority of related /// unscheduled nodes, for example. @@ -451,7 +477,7 @@ namespace llvm { unsigned getCurCycle() const { return CurCycle; - } + } }; class ScheduleDAG { @@ -473,11 +499,18 @@ namespace llvm { virtual ~ScheduleDAG(); + /// getInstrDesc - Return the TargetInstrDesc of this SUnit. + /// Return NULL for SDNodes without a machine opcode. + const TargetInstrDesc *getInstrDesc(const SUnit *SU) const { + if (SU->isInstr()) return &SU->getInstr()->getDesc(); + return getNodeDesc(SU->getNode()); + } + /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered /// using 'dot'. /// void viewGraph(); - + /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock /// according to the order specified in Sequence. /// @@ -536,6 +569,10 @@ namespace llvm { void EmitNoop(); void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); + + private: + // Return the TargetInstrDesc of this SDNode or NULL. + const TargetInstrDesc *getNodeDesc(const SDNode *Node) const; }; class SUnitIterator : public std::iterator<std::forward_iterator_tag, @@ -627,7 +664,7 @@ namespace llvm { /// Visited - a set of nodes visited during a DFS traversal. BitVector Visited; - /// DFS - make a DFS traversal and mark all nodes affected by the + /// DFS - make a DFS traversal and mark all nodes affected by the /// edge insertion. These nodes will later get new topological indexes /// by means of the Shift method. void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); @@ -642,7 +679,7 @@ namespace llvm { public: explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits); - /// InitDAGTopologicalSorting - create the initial topological + /// InitDAGTopologicalSorting - create the initial topological /// ordering from the DAG to be scheduled. void InitDAGTopologicalSorting(); diff --git a/include/llvm/CodeGen/ScheduleHazardRecognizer.h b/include/llvm/CodeGen/ScheduleHazardRecognizer.h index 09e3e88..2f53baa 100644 --- a/include/llvm/CodeGen/ScheduleHazardRecognizer.h +++ b/include/llvm/CodeGen/ScheduleHazardRecognizer.h @@ -23,7 +23,15 @@ class SUnit; /// issued this cycle, and whether or not a noop needs to be inserted to handle /// the hazard. class ScheduleHazardRecognizer { +protected: + /// MaxLookAhead - Indicate the number of cycles in the scoreboard + /// state. Important to restore the state after backtracking. Additionally, + /// MaxLookAhead=0 identifies a fake recognizer, allowing the client to + /// bypass virtual calls. Currently the PostRA scheduler ignores it. + unsigned MaxLookAhead; + public: + ScheduleHazardRecognizer(): MaxLookAhead(0) {} virtual ~ScheduleHazardRecognizer(); enum HazardType { @@ -32,6 +40,14 @@ public: NoopHazard // This instruction can't be emitted, and needs noops. }; + unsigned getMaxLookAhead() const { return MaxLookAhead; } + + bool isEnabled() const { return MaxLookAhead != 0; } + + /// atIssueLimit - Return true if no more instructions may be issued in this + /// cycle. + virtual bool atIssueLimit() const { return false; } + /// getHazardType - Return the hazard type of emitting this node. There are /// three possible results. Either: /// * NoHazard: it is legal to issue this instruction on this cycle. @@ -39,7 +55,7 @@ public: /// other instruction is available, issue it first. /// * NoopHazard: issuing this instruction would break the program. If /// some other instruction can be issued, do so, otherwise issue a noop. - virtual HazardType getHazardType(SUnit *) { + virtual HazardType getHazardType(SUnit *m, int Stalls) { return NoHazard; } @@ -52,12 +68,18 @@ public: /// emitted, to advance the hazard state. virtual void EmitInstruction(SUnit *) {} - /// AdvanceCycle - This callback is invoked when no instructions can be - /// issued on this cycle without a hazard. This should increment the + /// AdvanceCycle - This callback is invoked whenever the next top-down + /// instruction to be scheduled cannot issue in the current cycle, either + /// because of latency or resource conflicts. This should increment the /// internal state of the hazard recognizer so that previously "Hazard" /// instructions will now not be hazards. virtual void AdvanceCycle() {} + /// RecedeCycle - This callback is invoked whenever the next bottom-up + /// instruction to be scheduled cannot issue in the current cycle, either + /// because of latency or resource conflicts. + virtual void RecedeCycle() {} + /// EmitNoop - This callback is invoked when a noop was added to the /// instruction stream. virtual void EmitNoop() { diff --git a/include/llvm/CodeGen/ScoreboardHazardRecognizer.h b/include/llvm/CodeGen/ScoreboardHazardRecognizer.h new file mode 100644 index 0000000..8850006 --- /dev/null +++ b/include/llvm/CodeGen/ScoreboardHazardRecognizer.h @@ -0,0 +1,129 @@ +//=- llvm/CodeGen/ScoreboardHazardRecognizer.h - Schedule Support -*- C++ -*-=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the ScoreboardHazardRecognizer class, which +// encapsulates hazard-avoidance heuristics for scheduling, based on the +// scheduling itineraries specified for the target. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_SCOREBOARDHAZARDRECOGNIZER_H +#define LLVM_CODEGEN_SCOREBOARDHAZARDRECOGNIZER_H + +#include "llvm/CodeGen/ScheduleHazardRecognizer.h" +#include "llvm/Support/DataTypes.h" + +#include <cassert> +#include <cstring> +#include <string> + +namespace llvm { + +class InstrItineraryData; +class TargetInstrDesc; +class ScheduleDAG; +class SUnit; + +class ScoreboardHazardRecognizer : public ScheduleHazardRecognizer { + // Scoreboard to track function unit usage. Scoreboard[0] is a + // mask of the FUs in use in the cycle currently being + // schedule. Scoreboard[1] is a mask for the next cycle. The + // Scoreboard is used as a circular buffer with the current cycle + // indicated by Head. + // + // Scoreboard always counts cycles in forward execution order. If used by a + // bottom-up scheduler, then the scoreboard cycles are the inverse of the + // scheduler's cycles. + class Scoreboard { + unsigned *Data; + + // The maximum number of cycles monitored by the Scoreboard. This + // value is determined based on the target itineraries to ensure + // that all hazards can be tracked. + size_t Depth; + // Indices into the Scoreboard that represent the current cycle. + size_t Head; + public: + Scoreboard():Data(NULL), Depth(0), Head(0) { } + ~Scoreboard() { + delete[] Data; + } + + size_t getDepth() const { return Depth; } + unsigned& operator[](size_t idx) const { + // Depth is expected to be a power-of-2. + assert(Depth && !(Depth & (Depth - 1)) && + "Scoreboard was not initialized properly!"); + + return Data[(Head + idx) & (Depth-1)]; + } + + void reset(size_t d = 1) { + if (Data == NULL) { + Depth = d; + Data = new unsigned[Depth]; + } + + memset(Data, 0, Depth * sizeof(Data[0])); + Head = 0; + } + + void advance() { + Head = (Head + 1) & (Depth-1); + } + + void recede() { + Head = (Head - 1) & (Depth-1); + } + + // Print the scoreboard. + void dump() const; + }; + +#ifndef NDEBUG + // Support for tracing ScoreboardHazardRecognizer as a component within + // another module. Follows the current thread-unsafe model of tracing. + static const char *DebugType; +#endif + + // Itinerary data for the target. + const InstrItineraryData *ItinData; + + const ScheduleDAG *DAG; + + /// IssueWidth - Max issue per cycle. 0=Unknown. + unsigned IssueWidth; + + /// IssueCount - Count instructions issued in this cycle. + unsigned IssueCount; + + Scoreboard ReservedScoreboard; + Scoreboard RequiredScoreboard; + +public: + ScoreboardHazardRecognizer(const InstrItineraryData *ItinData, + const ScheduleDAG *DAG, + const char *ParentDebugType = ""); + + /// atIssueLimit - Return true if no more instructions may be issued in this + /// cycle. + virtual bool atIssueLimit() const; + + // Stalls provides an cycle offset at which SU will be scheduled. It will be + // negative for bottom-up scheduling. + virtual HazardType getHazardType(SUnit *SU, int Stalls); + virtual void Reset(); + virtual void EmitInstruction(SUnit *SU); + virtual void AdvanceCycle(); + virtual void RecedeCycle(); +}; + +} + +#endif //!LLVM_CODEGEN_SCOREBOARDHAZARDRECOGNIZER_H diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 7723fa0..c9de95b 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -171,9 +171,6 @@ class SelectionDAG { /// DbgInfo - Tracks dbg_value information through SDISel. SDDbgInfo *DbgInfo; - /// VerifyNode - Sanity check the given node. Aborts if it is invalid. - void VerifyNode(SDNode *N); - /// setGraphColorHelper - Implementation of setSubgraphColor. /// Return whether we had to truncate the search. /// @@ -401,21 +398,21 @@ public: } // This version of the getCopyToReg method takes an extra operand, which - // indicates that there is potentially an incoming flag value (if Flag is not - // null) and that there should be a flag result. + // 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 Flag) { - SDVTList VTs = getVTList(MVT::Other, MVT::Flag); - SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; - return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3); + SDValue Glue) { + SDVTList VTs = getVTList(MVT::Other, MVT::Glue); + SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue }; + return getNode(ISD::CopyToReg, dl, VTs, Ops, Glue.getNode() ? 4 : 3); } // Similar to last getCopyToReg() except parameter Reg is a SDValue SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N, - SDValue Flag) { - SDVTList VTs = getVTList(MVT::Other, MVT::Flag); - SDValue Ops[] = { Chain, Reg, N, Flag }; - return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3); + 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) { @@ -425,13 +422,13 @@ public: } // This version of the getCopyFromReg method takes an extra operand, which - // indicates that there is potentially an incoming flag value (if Flag is not - // null) and that there should be a flag result. + // 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 Flag) { - SDVTList VTs = getVTList(VT, MVT::Other, MVT::Flag); - SDValue Ops[] = { Chain, getRegister(Reg, VT), Flag }; - return getNode(ISD::CopyFromReg, dl, VTs, Ops, Flag.getNode() ? 3 : 2); + SDValue Glue) { + SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue); + SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue }; + return getNode(ISD::CopyFromReg, dl, VTs, Ops, Glue.getNode() ? 3 : 2); } SDValue getCondCode(ISD::CondCode Cond); @@ -465,27 +462,27 @@ public: SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT); /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have - /// a flag result (to ensure it's not CSE'd). CALLSEQ_START does not have a + /// 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) { - SDVTList VTs = getVTList(MVT::Other, MVT::Flag); + SDVTList VTs = getVTList(MVT::Other, MVT::Glue); SDValue Ops[] = { Chain, Op }; return getNode(ISD::CALLSEQ_START, DebugLoc(), VTs, Ops, 2); } /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a - /// flag result (to ensure it's not CSE'd). CALLSEQ_END does not have + /// glue result (to ensure it's not CSE'd). CALLSEQ_END does not have /// a useful DebugLoc. SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2, - SDValue InFlag) { - SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag); + SDValue InGlue) { + 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(InFlag); + Ops.push_back(InGlue); return getNode(ISD::CALLSEQ_END, DebugLoc(), NodeTys, &Ops[0], - (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0)); + (unsigned)Ops.size() - (InGlue.getNode() == 0 ? 1 : 0)); } /// getUNDEF - Return an UNDEF node. UNDEF does not have a useful DebugLoc. @@ -542,17 +539,17 @@ public: SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, SDValue Size, unsigned Align, bool isVol, bool AlwaysInline, - const Value *DstSV, uint64_t DstSVOff, - const Value *SrcSV, uint64_t SrcSVOff); + MachinePointerInfo DstPtrInfo, + MachinePointerInfo SrcPtrInfo); SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, SDValue Size, unsigned Align, bool isVol, - const Value *DstSV, uint64_t DstOSVff, - const Value *SrcSV, uint64_t SrcSVOff); + MachinePointerInfo DstPtrInfo, + MachinePointerInfo SrcPtrInfo); SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src, SDValue Size, unsigned Align, bool isVol, - const Value *DstSV, uint64_t DstSVOff); + MachinePointerInfo DstPtrInfo); /// getSetCC - Helper function to make it easier to build SetCC's if you just /// have an ISD::CondCode instead of an SDValue. @@ -587,8 +584,8 @@ public: /// 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 Ptr, SDValue Cmp, SDValue Swp, const Value* PtrVal, - unsigned Alignment=0); + SDValue Ptr, SDValue Cmp, SDValue Swp, + MachinePointerInfo PtrInfo, unsigned Alignment=0); SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain, SDValue Ptr, SDValue Cmp, SDValue Swp, MachineMemOperand *MMO); @@ -609,13 +606,13 @@ public: SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, const EVT *VTs, unsigned NumVTs, const SDValue *Ops, unsigned NumOps, - EVT MemVT, const Value *srcValue, int SVOff, + EVT MemVT, MachinePointerInfo PtrInfo, unsigned Align = 0, bool Vol = false, bool ReadMem = true, bool WriteMem = true); SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, const SDValue *Ops, unsigned NumOps, - EVT MemVT, const Value *srcValue, int SVOff, + EVT MemVT, MachinePointerInfo PtrInfo, unsigned Align = 0, bool Vol = false, bool ReadMem = true, bool WriteMem = true); @@ -630,19 +627,22 @@ public: /// determined by their operands, and they produce a value AND a token chain. /// SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, - const Value *SV, int SVOffset, bool isVolatile, - bool isNonTemporal, unsigned Alignment); - SDValue getExtLoad(ISD::LoadExtType ExtType, EVT VT, DebugLoc dl, - SDValue Chain, SDValue Ptr, const Value *SV, - int SVOffset, EVT MemVT, bool isVolatile, - bool isNonTemporal, unsigned Alignment); + MachinePointerInfo PtrInfo, bool isVolatile, + bool isNonTemporal, unsigned Alignment, + const MDNode *TBAAInfo = 0); + SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc 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 Offset, ISD::MemIndexedMode AM); SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, SDValue Offset, - const Value *SV, int SVOffset, EVT MemVT, - bool isVolatile, bool isNonTemporal, unsigned Alignment); + MachinePointerInfo PtrInfo, EVT MemVT, + bool isVolatile, bool isNonTemporal, unsigned Alignment, + const MDNode *TBAAInfo = 0); SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr, SDValue Offset, @@ -651,14 +651,16 @@ public: /// getStore - Helper function to build ISD::STORE nodes. /// SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, - const Value *SV, int SVOffset, bool isVolatile, - bool isNonTemporal, unsigned Alignment); + MachinePointerInfo PtrInfo, bool isVolatile, + bool isNonTemporal, unsigned Alignment, + const MDNode *TBAAInfo = 0); SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, MachineMemOperand *MMO); SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, - const Value *SV, int SVOffset, EVT TVT, + MachinePointerInfo PtrInfo, EVT TVT, bool isNonTemporal, bool isVolatile, - unsigned Alignment); + unsigned Alignment, + const MDNode *TBAAInfo = 0); SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr, EVT TVT, MachineMemOperand *MMO); SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base, @@ -899,6 +901,9 @@ public: SmallVector<SDDbgValue*,2> &GetDbgValues(const SDNode* SD) { return DbgInfo->getSDDbgValues(SD); } + + /// TransferDbgValues - Transfer SDDbgValues. + void TransferDbgValues(SDValue From, SDValue To); /// hasDebugValues - Return true if there are any SDDbgValue nodes associated /// with this SelectionDAG. @@ -961,6 +966,13 @@ public: /// class to allow target nodes to be understood. unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const; + /// isBaseWithConstantOffset - Return true if the specified operand is an + /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an + /// ISD::OR with a ConstantSDNode that is guaranteed to have the same + /// semantics as an ADD. This handles the equivalence: + /// X|Cst == X+Cst iff X&Cst = 0. + bool isBaseWithConstantOffset(SDValue Op) const; + /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN. bool isKnownNeverNaN(SDValue Op) const; diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index 01d05dd..62358e7 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -34,7 +34,8 @@ namespace llvm { class ScheduleHazardRecognizer; class GCFunctionInfo; class ScheduleDAGSDNodes; - + class LoadInst; + /// SelectionDAGISel - This is the common base class used for SelectionDAG-based /// pattern-matching instruction selectors. class SelectionDAGISel : public MachineFunctionPass { @@ -54,7 +55,7 @@ public: explicit SelectionDAGISel(const TargetMachine &tm, CodeGenOpt::Level OL = CodeGenOpt::Default); virtual ~SelectionDAGISel(); - + const TargetLowering &getTargetLowering() { return TLI; } virtual void getAnalysisUsage(AnalysisUsage &AU) const; @@ -62,18 +63,18 @@ public: virtual bool runOnMachineFunction(MachineFunction &MF); virtual void EmitFunctionEntryCode() {} - + /// PreprocessISelDAG - This hook allows targets to hack on the graph before /// instruction selection starts. virtual void PreprocessISelDAG() {} - + /// PostprocessISelDAG() - This hook allows the target to hack on the graph /// right after selection. virtual void PostprocessISelDAG() {} - + /// Select - Main hook targets implement to select a node. virtual SDNode *Select(SDNode *N) = 0; - + /// SelectInlineAsmMemoryOperand - Select the specified address as a target /// addressing mode, according to the specified constraint code. If this does /// not match or is not implemented, return true. The resultant operands @@ -91,25 +92,20 @@ public: /// IsLegalToFold - Returns true if the specific operand node N of /// U can be folded during instruction selection that starts at Root. - /// FIXME: This is a static member function because the PIC16 target, - /// which uses it during lowering. + /// FIXME: This is a static member function because the MSP430/SystemZ/X86 + /// targets, which uses it during isel. This could become a proper member. static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, CodeGenOpt::Level OptLevel, bool IgnoreChains = false); - /// CreateTargetHazardRecognizer - Return a newly allocated hazard recognizer - /// to use for this target when scheduling the DAG. - virtual ScheduleHazardRecognizer *CreateTargetHazardRecognizer(); - - // Opcodes used by the DAG state machine: enum BuiltinOpcodes { OPC_Scope, OPC_RecordNode, - OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3, + OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3, OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7, OPC_RecordMemRef, - OPC_CaptureFlagInput, + OPC_CaptureGlueInput, OPC_MoveChild, OPC_MoveParent, OPC_CheckSame, @@ -128,7 +124,7 @@ public: OPC_CheckComplexPat, OPC_CheckAndImm, OPC_CheckOrImm, OPC_CheckFoldableChainNode, - + OPC_EmitInteger, OPC_EmitRegister, OPC_EmitConvertToTarget, @@ -139,15 +135,15 @@ public: OPC_EmitNodeXForm, OPC_EmitNode, OPC_MorphNodeTo, - OPC_MarkFlagResults, + OPC_MarkGlueResults, OPC_CompleteMatch }; - + enum { - OPFL_None = 0, // Node has no chain or flag input and isn't variadic. + OPFL_None = 0, // Node has no chain or glue input and isn't variadic. OPFL_Chain = 1, // Node has a chain input. - OPFL_FlagInput = 2, // Node has a flag input. - OPFL_FlagOutput = 4, // Node has a flag output. + OPFL_GlueInput = 2, // Node has a glue input. + OPFL_GlueOutput = 4, // Node has a glue output. OPFL_MemRefs = 8, // Node gets accumulated MemRefs. OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs. OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs. @@ -156,37 +152,37 @@ public: OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs. OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs. OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs. - + OPFL_VariadicInfo = OPFL_Variadic6 }; - + /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the /// number of fixed arity values that should be skipped when copying from the /// root. static inline int getNumFixedFromVariadicInfo(unsigned Flags) { return ((Flags&OPFL_VariadicInfo) >> 4)-1; } - - + + protected: /// DAGSize - Size of DAG being instruction selected. /// unsigned DAGSize; - + /// ISelPosition - Node iterator marking the current position of /// instruction selection as it procedes through the topologically-sorted /// node list. SelectionDAG::allnodes_iterator ISelPosition; - - /// ISelUpdater - helper class to handle updates of the + + /// ISelUpdater - helper class to handle updates of the /// instruction selection graph. class ISelUpdater : public SelectionDAG::DAGUpdateListener { SelectionDAG::allnodes_iterator &ISelPosition; public: explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp) : ISelPosition(isp) {} - + /// NodeDeleted - Handle nodes deleted from the graph. If the /// node being deleted is the current ISelPosition node, update /// ISelPosition. @@ -195,46 +191,46 @@ protected: if (ISelPosition == SelectionDAG::allnodes_iterator(N)) ++ISelPosition; } - + /// NodeUpdated - Ignore updates for now. virtual void NodeUpdated(SDNode *N) {} }; - + /// ReplaceUses - replace all uses of the old node F with the use /// of the new node T. void ReplaceUses(SDValue F, SDValue T) { ISelUpdater ISU(ISelPosition); CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU); } - + /// ReplaceUses - replace all uses of the old nodes F with the use /// of the new nodes T. void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) { ISelUpdater ISU(ISelPosition); CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU); } - + /// ReplaceUses - replace all uses of the old node F with the use /// of the new node T. void ReplaceUses(SDNode *F, SDNode *T) { ISelUpdater ISU(ISelPosition); CurDAG->ReplaceAllUsesWith(F, T, &ISU); } - + /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated /// by tblgen. Others should not call it. void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops); - + public: // Calls to these predicates are generated by tblgen. bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const; bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const; - - + + /// CheckPatternPredicate - This function is generated by tblgen in the /// target. It runs the specified pattern predicate and returns true if it /// succeeds or false if it fails. The number is a private implementation @@ -252,13 +248,14 @@ public: assert(0 && "Tblgen should generate the implementation of this!"); return 0; } - - virtual bool CheckComplexPattern(SDNode *Root, SDValue N, unsigned PatternNo, - SmallVectorImpl<SDValue> &Result) { + + virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N, + unsigned PatternNo, + SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) { assert(0 && "Tblgen should generate the implementation of this!"); return false; } - + virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) { assert(0 && "Tblgen shoudl generate this!"); return SDValue(); @@ -267,9 +264,9 @@ public: SDNode *SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, unsigned TableSize); - + private: - + // Calls to these functions are generated by tblgen. SDNode *Select_INLINEASM(SDNode *N); SDNode *Select_UNDEF(SDNode *N); @@ -279,9 +276,10 @@ private: void DoInstructionSelection(); SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTs, const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo); - + void PrepareEHLandingPad(); void SelectAllBasicBlocks(const Function &Fn); + bool TryToFoldFastISelLoad(const LoadInst *LI, FastISel *FastIS); void FinishBasicBlock(); void SelectBasicBlock(BasicBlock::const_iterator Begin, @@ -289,7 +287,7 @@ private: bool &HadTailCall); void CodeGenAndEmitDAG(); void LowerArguments(const BasicBlock *BB); - + void ComputeLiveOutVRegInfo(); /// Create the scheduler. If a specific scheduler was specified @@ -297,16 +295,16 @@ private: /// one preferred by the target. /// ScheduleDAGSDNodes *CreateScheduler(); - + /// OpcodeOffset - This is a cache used to dispatch efficiently into isel /// state machines that start with a OPC_SwitchOpcode node. std::vector<unsigned> OpcodeOffset; - - void UpdateChainsAndFlags(SDNode *NodeToMatch, SDValue InputChain, - const SmallVectorImpl<SDNode*> &ChainNodesMatched, - SDValue InputFlag,const SmallVectorImpl<SDNode*> &F, - bool isMorphNodeTo); - + + void UpdateChainsAndGlue(SDNode *NodeToMatch, SDValue InputChain, + const SmallVectorImpl<SDNode*> &ChainNodesMatched, + SDValue InputGlue, const SmallVectorImpl<SDNode*> &F, + bool isMorphNodeTo); + }; } diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 4cf6f36..6454639 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -29,7 +29,7 @@ #include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/Support/MathExtras.h" -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include "llvm/Support/DebugLoc.h" #include <cassert> @@ -524,24 +524,24 @@ public: return X; } - /// getFlaggedNode - If this node has a flag operand, return the node - /// to which the flag operand points. Otherwise return NULL. - SDNode *getFlaggedNode() const { + /// getGluedNode - If this node has a glue operand, return the node + /// to which the glue operand points. Otherwise return NULL. + SDNode *getGluedNode() const { if (getNumOperands() != 0 && - getOperand(getNumOperands()-1).getValueType().getSimpleVT() == MVT::Flag) + getOperand(getNumOperands()-1).getValueType() == MVT::Glue) return getOperand(getNumOperands()-1).getNode(); return 0; } // If this is a pseudo op, like copyfromreg, look to see if there is a - // real target node flagged to it. If so, return the target node. - const SDNode *getFlaggedMachineNode() const { + // real target node glued to it. If so, return the target node. + const SDNode *getGluedMachineNode() const { const SDNode *FoundNode = this; - // Climb up flag edges until a machine-opcode node is found, or the + // Climb up glue edges until a machine-opcode node is found, or the // end of the chain is reached. while (!FoundNode->isMachineOpcode()) { - const SDNode *N = FoundNode->getFlaggedNode(); + const SDNode *N = FoundNode->getGluedNode(); if (!N) break; FoundNode = N; } @@ -549,11 +549,11 @@ public: return FoundNode; } - /// getFlaggedUser - If this node has a flag value with a user, return + /// getGluedUser - If this node has a glue value with a user, return /// the user (there is at most one). Otherwise return NULL. - SDNode *getFlaggedUser() const { + SDNode *getGluedUser() const { for (use_iterator UI = use_begin(), UE = use_end(); UI != UE; ++UI) - if (UI.getUse().get().getValueType() == MVT::Flag) + if (UI.getUse().get().getValueType() == MVT::Glue) return *UI; return 0; } @@ -902,6 +902,9 @@ public: const Value *getSrcValue() const { return MMO->getValue(); } int64_t getSrcValueOffset() const { return MMO->getOffset(); } + /// Returns the TBAAInfo that describes the dereference. + const MDNode *getTBAAInfo() const { return MMO->getTBAAInfo(); } + /// getMemoryVT - Return the type of the in-memory value. EVT getMemoryVT() const { return MemoryVT; } @@ -909,6 +912,10 @@ public: /// reference performed by operation. MachineMemOperand *getMemOperand() const { return MMO; } + const MachinePointerInfo &getPointerInfo() const { + return MMO->getPointerInfo(); + } + /// refineAlignment - Update this MemSDNode's MachineMemOperand information /// to reflect the alignment of NewMMO, if it has a greater alignment. /// This must only be used when the new alignment applies to all users of @@ -929,6 +936,7 @@ public: // with either an intrinsic or a target opcode. return N->getOpcode() == ISD::LOAD || N->getOpcode() == ISD::STORE || + N->getOpcode() == ISD::PREFETCH || N->getOpcode() == ISD::ATOMIC_CMP_SWAP || N->getOpcode() == ISD::ATOMIC_SWAP || N->getOpcode() == ISD::ATOMIC_LOAD_ADD || @@ -1004,8 +1012,8 @@ public: /// MemIntrinsicSDNode - This SDNode is used for target intrinsics that touch /// memory and need an associated MachineMemOperand. Its opcode may be -/// INTRINSIC_VOID, INTRINSIC_W_CHAIN, or a target-specific opcode with a -/// value not less than FIRST_TARGET_MEMORY_OPCODE. +/// INTRINSIC_VOID, INTRINSIC_W_CHAIN, PREFETCH, or a target-specific opcode +/// with a value not less than FIRST_TARGET_MEMORY_OPCODE. class MemIntrinsicSDNode : public MemSDNode { public: MemIntrinsicSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, @@ -1021,6 +1029,7 @@ public: // early a node with a target opcode can be of this class return N->getOpcode() == ISD::INTRINSIC_W_CHAIN || N->getOpcode() == ISD::INTRINSIC_VOID || + N->getOpcode() == ISD::PREFETCH || N->isTargetMemoryOpcode(); } }; diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index 88044c7..1da1e91be 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -13,10 +13,7 @@ // // SlotIndex is mostly a proxy for entries of the SlotIndexList, a class which // is held is LiveIntervals and provides the real numbering. This allows -// LiveIntervals to perform largely transparent renumbering. The SlotIndex -// class does hold a PHI bit, which determines whether the index relates to a -// PHI use or def point, or an actual instruction. See the SlotIndex class -// description for futher information. +// LiveIntervals to perform largely transparent renumbering. //===----------------------------------------------------------------------===// #ifndef LLVM_CODEGEN_SLOTINDEXES_H @@ -130,12 +127,10 @@ namespace llvm { enum Slot { LOAD, USE, DEF, STORE, NUM }; - static const unsigned PHI_BIT = 1 << 2; + PointerIntPair<IndexListEntry*, 2, unsigned> lie; - PointerIntPair<IndexListEntry*, 3, unsigned> lie; - - SlotIndex(IndexListEntry *entry, unsigned phiAndSlot) - : lie(entry, phiAndSlot) { + SlotIndex(IndexListEntry *entry, unsigned slot) + : lie(entry, slot) { assert(entry != 0 && "Attempt to construct index with 0 pointer."); } @@ -149,7 +144,7 @@ namespace llvm { /// Returns the slot for this SlotIndex. Slot getSlot() const { - return static_cast<Slot>(lie.getInt() & ~PHI_BIT); + return static_cast<Slot>(lie.getInt()); } static inline unsigned getHashValue(const SlotIndex &v) { @@ -166,22 +161,13 @@ namespace llvm { static inline SlotIndex getTombstoneKey() { return SlotIndex(IndexListEntry::getTombstoneKeyEntry(), 0); } - + /// Construct an invalid index. SlotIndex() : lie(IndexListEntry::getEmptyKeyEntry(), 0) {} - // Construct a new slot index from the given one, set the phi flag on the - // new index to the value of the phi parameter. - SlotIndex(const SlotIndex &li, bool phi) - : lie(&li.entry(), phi ? PHI_BIT | li.getSlot() : (unsigned)li.getSlot()){ - assert(lie.getPointer() != 0 && - "Attempt to construct index with 0 pointer."); - } - - // Construct a new slot index from the given one, set the phi flag on the - // new index to the value of the phi parameter, and the slot to the new slot. - SlotIndex(const SlotIndex &li, bool phi, Slot s) - : lie(&li.entry(), phi ? PHI_BIT | s : (unsigned)s) { + // Construct a new slot index from the given one, and set the slot. + SlotIndex(const SlotIndex &li, Slot s) + : lie(&li.entry(), unsigned(s)) { assert(lie.getPointer() != 0 && "Attempt to construct index with 0 pointer."); } @@ -236,11 +222,6 @@ namespace llvm { return other.getIndex() - getIndex(); } - /// Returns the state of the PHI bit. - bool isPHI() const { - return lie.getInt() & PHI_BIT; - } - /// isLoad - Return true if this is a LOAD slot. bool isLoad() const { return getSlot() == LOAD; @@ -405,9 +386,6 @@ namespace llvm { /// and MBB id. std::vector<IdxMBBPair> idx2MBBMap; - typedef DenseMap<const MachineBasicBlock*, SlotIndex> TerminatorGapsMap; - TerminatorGapsMap terminatorGaps; - // IndexListEntry allocator. BumpPtrAllocator ileAllocator; @@ -415,7 +393,7 @@ namespace llvm { IndexListEntry *entry = static_cast<IndexListEntry*>( ileAllocator.Allocate(sizeof(IndexListEntry), - alignof<IndexListEntry>())); + alignOf<IndexListEntry>())); new (entry) IndexListEntry(mi, index); @@ -491,7 +469,9 @@ namespace llvm { public: static char ID; - SlotIndexes() : MachineFunctionPass(ID), indexListHead(0) {} + SlotIndexes() : MachineFunctionPass(ID), indexListHead(0) { + initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); + } virtual void getAnalysisUsage(AnalysisUsage &au) const; virtual void releaseMemory(); @@ -565,26 +545,22 @@ namespace llvm { return nextNonNull; } - /// Returns the first index in the given basic block. - SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { + /// Return the (start,end) range of the given basic block. + const std::pair<SlotIndex, SlotIndex> & + getMBBRange(const MachineBasicBlock *mbb) const { MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb); assert(itr != mbb2IdxMap.end() && "MBB not found in maps."); - return itr->second.first; + return itr->second; } - /// Returns the last index in the given basic block. - SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { - MBB2IdxMap::const_iterator itr = mbb2IdxMap.find(mbb); - assert(itr != mbb2IdxMap.end() && "MBB not found in maps."); - return itr->second.second; + /// Returns the first index in the given basic block. + SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { + return getMBBRange(mbb).first; } - /// Returns the terminator gap for the given index. - SlotIndex getTerminatorGap(const MachineBasicBlock *mbb) { - TerminatorGapsMap::iterator itr = terminatorGaps.find(mbb); - assert(itr != terminatorGaps.end() && - "All MBBs should have terminator gaps in their indexes."); - return itr->second; + /// Returns the last index in the given basic block. + SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { + return getMBBRange(mbb).second; } /// Returns the basic block which the given index falls in. @@ -618,29 +594,6 @@ namespace llvm { return resVal; } - /// Return a list of MBBs that can be reach via any branches or - /// fall-throughs. - bool findReachableMBBs(SlotIndex start, SlotIndex end, - SmallVectorImpl<MachineBasicBlock*> &mbbs) const { - std::vector<IdxMBBPair>::const_iterator itr = - std::lower_bound(idx2MBBMap.begin(), idx2MBBMap.end(), start); - - bool resVal = false; - while (itr != idx2MBBMap.end()) { - if (itr->first > end) - break; - MachineBasicBlock *mbb = itr->second; - if (getMBBEndIdx(mbb) > end) - break; - for (MachineBasicBlock::succ_iterator si = mbb->succ_begin(), - se = mbb->succ_end(); si != se; ++si) - mbbs.push_back(*si); - resVal = true; - ++itr; - } - return resVal; - } - /// Returns the MBB covering the given range, or null if the range covers /// more than one basic block. MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const { @@ -672,6 +625,9 @@ namespace llvm { SlotIndex insertMachineInstrInMaps(MachineInstr *mi, bool *deferredRenumber = 0) { assert(mi2iMap.find(mi) == mi2iMap.end() && "Instr already indexed."); + // Numbering DBG_VALUE instructions could cause code generation to be + // affected by debug information. + assert(!mi->isDebugValue() && "Cannot number DBG_VALUE instructions."); MachineBasicBlock *mbb = mi->getParent(); @@ -789,7 +745,7 @@ namespace llvm { MachineFunction::iterator nextMBB = llvm::next(MachineFunction::iterator(mbb)); IndexListEntry *startEntry = createEntry(0, 0); - IndexListEntry *terminatorEntry = createEntry(0, 0); + IndexListEntry *stopEntry = createEntry(0, 0); IndexListEntry *nextEntry = 0; if (nextMBB == mbb->getParent()->end()) { @@ -799,15 +755,11 @@ namespace llvm { } insert(nextEntry, startEntry); - insert(nextEntry, terminatorEntry); + insert(nextEntry, stopEntry); SlotIndex startIdx(startEntry, SlotIndex::LOAD); - SlotIndex terminatorIdx(terminatorEntry, SlotIndex::PHI_BIT); SlotIndex endIdx(nextEntry, SlotIndex::LOAD); - terminatorGaps.insert( - std::make_pair(mbb, terminatorIdx)); - mbb2IdxMap.insert( std::make_pair(mbb, std::make_pair(startIdx, endIdx))); @@ -828,6 +780,20 @@ namespace llvm { }; + // Specialize IntervalMapInfo for half-open slot index intervals. + template <typename> struct IntervalMapInfo; + template <> struct IntervalMapInfo<SlotIndex> { + static inline bool startLess(const SlotIndex &x, const SlotIndex &a) { + return x < a; + } + static inline bool stopLess(const SlotIndex &b, const SlotIndex &x) { + return b <= x; + } + static inline bool adjacent(const SlotIndex &a, const SlotIndex &b) { + return a == b; + } + }; + } #endif // LLVM_CODEGEN_LIVEINDEX_H diff --git a/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h b/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h index d8f0373..fba3e48 100644 --- a/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h +++ b/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h @@ -57,6 +57,8 @@ public: virtual void Initialize(MCContext &Ctx, const TargetMachine &TM); + virtual const MCSection *getEHFrameSection() const; + const MCSection *getDataRelSection() const { return DataRelSection; } /// getSectionForConstant - Given a constant with the SectionKind, return a @@ -121,6 +123,8 @@ public: virtual void Initialize(MCContext &Ctx, const TargetMachine &TM); + virtual const MCSection *getEHFrameSection() const; + virtual const MCSection * SelectSectionForGlobal(const GlobalValue *GV, SectionKind Kind, Mangler *Mang, const TargetMachine &TM) const; @@ -184,6 +188,8 @@ public: virtual void Initialize(MCContext &Ctx, const TargetMachine &TM); + virtual const MCSection *getEHFrameSection() const; + virtual const MCSection *getDrectveSection() const { return DrectveSection; } virtual const MCSection * diff --git a/include/llvm/CodeGen/ValueTypes.h b/include/llvm/CodeGen/ValueTypes.h index 51f324c..22d1622 100644 --- a/include/llvm/CodeGen/ValueTypes.h +++ b/include/llvm/CodeGen/ValueTypes.h @@ -18,7 +18,7 @@ #include <cassert> #include <string> -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include "llvm/Support/MathExtras.h" namespace llvm { @@ -26,7 +26,10 @@ namespace llvm { class LLVMContext; struct EVT; - class MVT { // MVT = Machine Value Type + /// 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. + class MVT { public: enum SimpleValueType { // If you change this numbering, you must change the values in @@ -74,14 +77,16 @@ namespace llvm { FIRST_VECTOR_VALUETYPE = v2i8, LAST_VECTOR_VALUETYPE = v4f64, - Flag = 33, // This glues nodes together during pre-RA sched + x86mmx = 33, // This is an X86 MMX value - isVoid = 34, // This has no value + Glue = 34, // This glues nodes together during pre-RA sched - LAST_VALUETYPE = 35, // This always remains at the end of the list. + isVoid = 35, // This has no value + + LAST_VALUETYPE = 36, // This always remains at the end of the list. // This is the current maximum for LAST_VALUETYPE. - // EVT::MAX_ALLOWED_VALUETYPE is used for asserts and to size bit vectors + // MVT::MAX_ALLOWED_VALUETYPE is used for asserts and to size bit vectors // This value must be a multiple of 32. MAX_ALLOWED_VALUETYPE = 64, @@ -124,13 +129,14 @@ namespace llvm { MVT() : SimpleTy((SimpleValueType)(INVALID_SIMPLE_VALUE_TYPE)) {} MVT(SimpleValueType SVT) : SimpleTy(SVT) { } - + bool operator>(const MVT& S) const { return SimpleTy > S.SimpleTy; } bool operator<(const MVT& S) const { return SimpleTy < S.SimpleTy; } bool operator==(const MVT& S) const { return SimpleTy == S.SimpleTy; } + bool operator!=(const MVT& S) const { return SimpleTy != S.SimpleTy; } bool operator>=(const MVT& S) const { return SimpleTy >= S.SimpleTy; } bool operator<=(const MVT& S) const { return SimpleTy <= S.SimpleTy; } - + /// isFloatingPoint - Return true if this is a FP, or a vector FP type. bool isFloatingPoint() const { return ((SimpleTy >= MVT::f32 && SimpleTy <= MVT::ppcf128) || @@ -149,14 +155,14 @@ namespace llvm { return (SimpleTy >= MVT::FIRST_VECTOR_VALUETYPE && SimpleTy <= MVT::LAST_VECTOR_VALUETYPE); } - + /// isPow2VectorType - Returns true if the given vector is a power of 2. bool isPow2VectorType() const { unsigned NElts = getVectorNumElements(); return !(NElts & (NElts - 1)); } - /// getPow2VectorType - Widens the length of the given vector EVT up to + /// getPow2VectorType - Widens the length of the given vector MVT up to /// the nearest power of 2 and returns that type. MVT getPow2VectorType() const { if (isPow2VectorType()) @@ -172,7 +178,7 @@ namespace llvm { MVT getScalarType() const { return isVector() ? getVectorElementType() : *this; } - + MVT getVectorElementType() const { switch (SimpleTy) { default: @@ -200,7 +206,7 @@ namespace llvm { case v4f64: return f64; } } - + unsigned getVectorNumElements() const { switch (SimpleTy) { default: @@ -228,7 +234,7 @@ namespace llvm { case v1i64: return 1; } } - + unsigned getSizeInBits() const { switch (SimpleTy) { case iPTR: @@ -247,6 +253,7 @@ namespace llvm { case i32 : case v4i8: case v2i16: return 32; + case x86mmx: case f64 : case i64 : case v8i8: @@ -273,7 +280,19 @@ namespace llvm { case v8i64: return 512; } } - + + /// getStoreSize - Return the number of bytes overwritten by a store + /// of the specified value type. + unsigned getStoreSize() const { + return (getSizeInBits() + 7) / 8; + } + + /// getStoreSizeInBits - Return the number of bits overwritten by a store + /// of the specified value type. + unsigned getStoreSizeInBits() const { + return getStoreSize() * 8; + } + static MVT getFloatingPointVT(unsigned BitWidth) { switch (BitWidth) { default: @@ -288,7 +307,7 @@ namespace llvm { return MVT::f128; } } - + static MVT getIntegerVT(unsigned BitWidth) { switch (BitWidth) { default: @@ -307,7 +326,7 @@ namespace llvm { return MVT::i128; } } - + static MVT getVectorVT(MVT VT, unsigned NumElements) { switch (VT.SimpleTy) { default: @@ -350,7 +369,11 @@ namespace llvm { } }; - struct EVT { // EVT = Extended Value Type + + /// EVT - Extended Value Type. Capable of holding value types which are not + /// native for any processor (such as the i12345 type), as well as the types + /// a MVT can represent. + struct EVT { private: MVT V; const Type *LLVMTy; @@ -527,7 +550,7 @@ namespace llvm { EVT getScalarType() const { return isVector() ? getVectorElementType() : *this; } - + /// getVectorElementType - Given a vector type, return the type of /// each element. EVT getVectorElementType() const { diff --git a/include/llvm/CodeGen/ValueTypes.td b/include/llvm/CodeGen/ValueTypes.td index 8151c0b..a1163f7 100644 --- a/include/llvm/CodeGen/ValueTypes.td +++ b/include/llvm/CodeGen/ValueTypes.td @@ -46,17 +46,18 @@ def v4i32 : ValueType<128, 22>; // 4 x i32 vector value def v8i32 : ValueType<256, 23>; // 8 x i32 vector value def v1i64 : ValueType<64 , 24>; // 1 x i64 vector value def v2i64 : ValueType<128, 25>; // 2 x i64 vector value -def v4i64 : ValueType<256, 26>; // 4 x f64 vector value -def v8i64 : ValueType<512, 27>; // 4 x f64 vector value +def v4i64 : ValueType<256, 26>; // 4 x i64 vector value +def v8i64 : ValueType<512, 27>; // 8 x i64 vector value -def v2f32 : ValueType<64, 28>; // 2 x f32 vector value +def v2f32 : ValueType<64 , 28>; // 2 x f32 vector value def v4f32 : ValueType<128, 29>; // 4 x f32 vector value def v8f32 : ValueType<256, 30>; // 8 x f32 vector value def v2f64 : ValueType<128, 31>; // 2 x f64 vector value def v4f64 : ValueType<256, 32>; // 4 x f64 vector value -def FlagVT : ValueType<0 , 33>; // Pre-RA sched glue -def isVoid : ValueType<0 , 34>; // Produces no value +def x86mmx : ValueType<64 , 33>; // X86 MMX value +def FlagVT : ValueType<0 , 34>; // Pre-RA sched glue +def isVoid : ValueType<0 , 35>; // Produces no value def MetadataVT: ValueType<0, 250>; // Metadata |
