diff options
Diffstat (limited to 'include/llvm/CodeGen')
46 files changed, 886 insertions, 462 deletions
diff --git a/include/llvm/CodeGen/Analysis.h b/include/llvm/CodeGen/Analysis.h index a8292ea649..78bf9fc11a 100644 --- a/include/llvm/CodeGen/Analysis.h +++ b/include/llvm/CodeGen/Analysis.h @@ -23,8 +23,10 @@ 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 @@ -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 7eef9567a0..a071febb10 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/System/DataTypes.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. @@ -444,7 +445,8 @@ namespace llvm { /// EmitVisibility - This emits visibility information about symbol, if /// this is suported by the target. - void EmitVisibility(MCSymbol *Sym, unsigned Visibility) const; + void EmitVisibility(MCSymbol *Sym, unsigned Visibility, + bool IsDefinition = true) const; void EmitLinkage(unsigned Linkage, MCSymbol *GVSym) const; diff --git a/include/llvm/CodeGen/BinaryObject.h b/include/llvm/CodeGen/BinaryObject.h index 3ade7c9e47..8c1431ffbe 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 24264d7f97..1f5f088be7 100644 --- a/include/llvm/CodeGen/CalcSpillWeights.h +++ b/include/llvm/CodeGen/CalcSpillWeights.h @@ -11,7 +11,7 @@ #ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H #define LLVM_CODEGEN_CALCSPILLWEIGHTS_H -#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/ADT/DenseMap.h" namespace llvm { @@ -20,6 +20,23 @@ 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 constant 25 instructions 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 + 25*SlotIndex::InstrDist); + } + /// VirtRegAuxInfo - Calculate auxiliary information for a virtual /// register such as its spill weight and allocation hint. class VirtRegAuxInfo { diff --git a/include/llvm/CodeGen/EdgeBundles.h b/include/llvm/CodeGen/EdgeBundles.h new file mode 100644 index 0000000000..2c5215a792 --- /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/FunctionLoweringInfo.h b/include/llvm/CodeGen/FunctionLoweringInfo.h index f17fe5a146..4421cc02d1 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 { @@ -99,14 +101,16 @@ public: #endif struct LiveOutInfo { - unsigned NumSignBits; + unsigned NumSignBits : 31; + bool IsValid : 1; APInt KnownOne, KnownZero; - LiveOutInfo() : NumSignBits(0), KnownOne(1, 0), KnownZero(1, 0) {} + LiveOutInfo() : NumSignBits(0), IsValid(true), KnownOne(1, 0), + KnownZero(1, 0) {} }; - - /// LiveOutRegInfo - Information about live out vregs, indexed by their - /// register number offset by 'FirstVirtualRegister'. - std::vector<LiveOutInfo> LiveOutRegInfo; + + /// VisitedBBs - The set of basic blocks visited thus far by instruction + /// selection. + DenseSet<const BasicBlock*> VisitedBBs; /// PHINodesToUpdate - A list of phi instructions whose operand list will /// be updated after processing the current basic block. @@ -142,12 +146,67 @@ public: return R = CreateRegs(V->getType()); } + /// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the + /// register is a PHI destination and the PHI's LiveOutInfo is not valid. + const LiveOutInfo *GetLiveOutRegInfo(unsigned Reg) { + if (!LiveOutRegInfo.inBounds(Reg)) + return NULL; + + const LiveOutInfo *LOI = &LiveOutRegInfo[Reg]; + if (!LOI->IsValid) + return NULL; + + return LOI; + } + + /// GetLiveOutRegInfo - Gets LiveOutInfo for a register, returning NULL if the + /// register is a PHI destination and the PHI's LiveOutInfo is not valid. If + /// the register's LiveOutInfo is for a smaller bit width, it is extended to + /// the larger bit width by zero extension. The bit width must be no smaller + /// than the LiveOutInfo's existing bit width. + const LiveOutInfo *GetLiveOutRegInfo(unsigned Reg, unsigned BitWidth); + + /// AddLiveOutRegInfo - Adds LiveOutInfo for a register. + void AddLiveOutRegInfo(unsigned Reg, unsigned NumSignBits, + const APInt &KnownZero, const APInt &KnownOne) { + // Only install this information if it tells us something. + if (NumSignBits == 1 && KnownZero == 0 && KnownOne == 0) + return; + + LiveOutRegInfo.grow(Reg); + LiveOutInfo &LOI = LiveOutRegInfo[Reg]; + LOI.NumSignBits = NumSignBits; + LOI.KnownOne = KnownOne; + LOI.KnownZero = KnownZero; + } + + /// ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI's destination + /// register based on the LiveOutInfo of its operands. + void ComputePHILiveOutRegInfo(const PHINode*); + + /// InvalidatePHILiveOutRegInfo - Invalidates a PHI's LiveOutInfo, to be + /// called when a block is visited before all of its predecessors. + void InvalidatePHILiveOutRegInfo(const PHINode *PN) { + // PHIs with no uses have no ValueMap entry. + DenseMap<const Value*, unsigned>::const_iterator It = ValueMap.find(PN); + if (It == ValueMap.end()) + return; + + unsigned Reg = It->second; + LiveOutRegInfo.grow(Reg); + LiveOutRegInfo[Reg].IsValid = false; + } + /// setByValArgumentFrameIndex - Record frame index for the byval /// argument. void setByValArgumentFrameIndex(const Argument *A, int FI); /// getByValArgumentFrameIndex - Get frame index for the byval argument. int getByValArgumentFrameIndex(const Argument *A); + +private: + /// LiveOutRegInfo - Information about live out vregs. + IndexedMap<LiveOutInfo, VirtReg2IndexFunctor> LiveOutRegInfo; }; /// AddCatchInfo - Extract the personality and type infos from an eh.selector @@ -155,8 +214,9 @@ public: void AddCatchInfo(const CallInst &I, MachineModuleInfo *MMI, MachineBasicBlock *MBB); -/// CopyCatchInfo - Copy catch information from DestBB to SrcBB. -void CopyCatchInfo(const BasicBlock *SrcBB, const BasicBlock *DestBB, +/// CopyCatchInfo - Copy catch information from SuccBB (or one of its +/// successors) to LPad. +void CopyCatchInfo(const BasicBlock *SuccBB, const BasicBlock *LPad, MachineModuleInfo *MMI, FunctionLoweringInfo &FLI); } // end namespace llvm diff --git a/include/llvm/CodeGen/ISDOpcodes.h b/include/llvm/CodeGen/ISDOpcodes.h index 31da0211eb..3da11c4a0e 100644 --- a/include/llvm/CodeGen/ISDOpcodes.h +++ b/include/llvm/CodeGen/ISDOpcodes.h @@ -269,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, @@ -295,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. @@ -399,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 @@ -482,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. @@ -532,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 eefbc45cb2..767b666225 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 eb373fb145..fea8523051 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 13cebeaf42..1ed2547ca6 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 bc06d43b8f..c931261f63 100644 --- a/include/llvm/CodeGen/LinkAllCodegenComponents.h +++ b/include/llvm/CodeGen/LinkAllCodegenComponents.h @@ -36,6 +36,7 @@ namespace { (void) llvm::createFastRegisterAllocator(); (void) llvm::createBasicRegisterAllocator(); (void) llvm::createLinearScanRegisterAllocator(); + (void) llvm::createGreedyRegisterAllocator(); (void) llvm::createDefaultPBQPRegisterAllocator(); (void) llvm::createSimpleRegisterCoalescer(); diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index c21df28cdd..427af87960 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" @@ -205,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 @@ -222,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(); } @@ -250,6 +246,7 @@ 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; @@ -274,19 +271,6 @@ namespace llvm { ranges.clear(); } - /// isStackSlot - Return true if this is a stack slot interval. - /// - bool isStackSlot() const { - return reg & (1U << (sizeof(unsigned)*CHAR_BIT-1)); - } - - /// 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)); - } - bool hasAtLeastOneValue() const { return !valnos.empty(); } bool containsOneValue() const { return valnos.size() == 1; } @@ -463,6 +447,11 @@ namespace llvm { addRangeFrom(LR, ranges.begin()); } + /// extendInBlock - If this interval is live before UseIdx in the basic + /// block that starts at StartIdx, extend it to be live at UseIdx and return + /// the value. If there is no live range before UseIdx, return NULL. + VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex UseIdx); + /// join - Join two live intervals (this, and other) together. This applies /// mappings to the value numbers in the LHS/RHS intervals as specified. If /// the intervals are not joinable, this aborts. @@ -560,11 +549,7 @@ namespace llvm { class ConnectedVNInfoEqClasses { LiveIntervals &lis_; - - // Map each value number to its equivalence class. - // The invariant is that EqClass[x] <= x. - // Two values are connected iff EqClass[x] == EqClass[b]. - SmallVector<unsigned, 8> eqClass_; + IntEqClasses eqClass_; // Note that values a and b are connected. void Connect(unsigned a, unsigned b); @@ -580,7 +565,7 @@ namespace llvm { /// getEqClass - Classify creates equivalence classes numbered 0..N. Return /// the equivalence class assigned the VNI. - unsigned getEqClass(const VNInfo *VNI) { return eqClass_[VNI->id]; } + 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 diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 143a1a6836..b09f8d1110 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -75,14 +75,6 @@ namespace llvm { // 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(); } @@ -163,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) { @@ -171,6 +169,10 @@ namespace llvm { r2iMap_.erase(I); } + SlotIndexes *getSlotIndexes() const { + return indexes_; + } + SlotIndex getZeroIndex() const { return indexes_->getZeroIndex(); } @@ -304,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(); @@ -441,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 9310a30a4d..8a8dcaf572 100644 --- a/include/llvm/CodeGen/LiveStackAnalysis.h +++ b/include/llvm/CodeGen/LiveStackAnalysis.h @@ -52,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 ea32efaf0c..f9b81b1ea7 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" @@ -121,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 27306c62d8..21fe74f8e1 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 49daf5f4d3..1906093388 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -16,6 +16,7 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/ADT/GraphTraits.h" +#include <functional> namespace llvm { @@ -224,6 +225,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 @@ -300,6 +305,10 @@ public: /// 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. @@ -403,6 +412,14 @@ raw_ostream& operator<<(raw_ostream &OS, const MachineBasicBlock &MBB); void WriteAsOperand(raw_ostream &, const MachineBasicBlock*, bool t); +// This is useful when building IndexedMaps keyed on basic block pointers. +struct MBB2NumberFunctor : + public std::unary_function<const MachineBasicBlock*, unsigned> { + unsigned operator()(const MachineBasicBlock *MBB) const { + return MBB->getNumber(); + } +}; + //===--------------------------------------------------------------------===// // GraphTraits specializations for machine basic block graphs (machine-CFGs) //===--------------------------------------------------------------------===// diff --git a/include/llvm/CodeGen/MachineCodeEmitter.h b/include/llvm/CodeGen/MachineCodeEmitter.h index 7abb49a219..8fc80adf7f 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 a75c02a052..c5c0c44504 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/MachineConstantPool.h b/include/llvm/CodeGen/MachineConstantPool.h index 498f815b9b..5727321a0d 100644 --- a/include/llvm/CodeGen/MachineConstantPool.h +++ b/include/llvm/CodeGen/MachineConstantPool.h @@ -16,6 +16,7 @@ #ifndef LLVM_CODEGEN_MACHINECONSTANTPOOL_H #define LLVM_CODEGEN_MACHINECONSTANTPOOL_H +#include "llvm/ADT/DenseSet.h" #include <cassert> #include <climits> #include <vector> @@ -130,6 +131,8 @@ class MachineConstantPool { const TargetData *TD; ///< The machine's TargetData. unsigned PoolAlignment; ///< The alignment for the pool. std::vector<MachineConstantPoolEntry> Constants; ///< The pool of constants. + /// MachineConstantPoolValues that use an existing MachineConstantPoolEntry. + DenseSet<MachineConstantPoolValue*> MachineCPVsSharingEntries; public: /// @brief The only constructor. explicit MachineConstantPool(const TargetData *td) diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h index dca65ef6d4..22a82a9d6e 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 eeba1bbddf..f56c053e47 100644 --- a/include/llvm/CodeGen/MachineFunction.h +++ b/include/llvm/CodeGen/MachineFunction.h @@ -271,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; diff --git a/include/llvm/CodeGen/MachineFunctionAnalysis.h b/include/llvm/CodeGen/MachineFunctionAnalysis.h index 75dbaab973..50676ad4ad 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 d1f17d39db..0f69a7789c 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -50,13 +50,22 @@ public: enum CommentFlag { ReloadReuse = 0x1 }; - + + enum MIFlag { + NoFlags = 0, + FrameSetup = 1 << 0 // Instruction is used as a part of + // function frame setup code. + }; private: const TargetInstrDesc *TID; // Instruction descriptor. - unsigned short NumImplicitOps; // Number of implicit operands (which + uint16_t NumImplicitOps; // Number of implicit operands (which // are determined at construction time). - unsigned short AsmPrinterFlags; // Various bits of information used by + uint8_t Flags; // Various bits of additional + // information about machine + // instruction. + + uint8_t AsmPrinterFlags; // Various bits of information used by // the AsmPrinter to emit helpful // comments. This is *not* semantic // information. Do not use this for @@ -125,8 +134,12 @@ public: /// getAsmPrinterFlags - Return the asm printer flags bitvector. /// - unsigned short getAsmPrinterFlags() const { return AsmPrinterFlags; } + uint8_t 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 { @@ -136,13 +149,38 @@ public: /// setAsmPrinterFlag - Set a flag for the AsmPrinter. /// void setAsmPrinterFlag(CommentFlag Flag) { - AsmPrinterFlags |= (unsigned short)Flag; + AsmPrinterFlags |= (uint8_t)Flag; + } + + /// getFlags - Return the MI flags bitvector. + uint8_t getFlags() const { + return Flags; + } + + /// getFlag - Return whether an MI flag is set. + bool getFlag(MIFlag Flag) const { + return Flags & Flag; + } + + /// setFlag - Set a MI flag. + void setFlag(MIFlag Flag) { + Flags |= (uint8_t)Flag; + } + + void setFlags(unsigned flags) { + Flags = flags; + } + + /// clearAsmPrinterFlag - clear specific AsmPrinter flags + /// + void clearAsmPrinterFlag(CommentFlag Flag) { + AsmPrinterFlags &= ~Flag; } /// getDebugLoc - Returns the debug location id of this MachineInstr. /// DebugLoc getDebugLoc() const { return debugLoc; } - + /// getDesc - Returns the target instruction descriptor of this /// MachineInstr. const TargetInstrDesc &getDesc() const { return *TID; } @@ -227,6 +265,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; } @@ -422,6 +461,15 @@ 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; diff --git a/include/llvm/CodeGen/MachineInstrBuilder.h b/include/llvm/CodeGen/MachineInstrBuilder.h index 1eb9735308..f04dee2b4b 100644 --- a/include/llvm/CodeGen/MachineInstrBuilder.h +++ b/include/llvm/CodeGen/MachineInstrBuilder.h @@ -145,6 +145,16 @@ public: return *this; } + const MachineInstrBuilder &setMIFlags(unsigned Flags) const { + MI->setFlags(Flags); + return *this; + } + + const MachineInstrBuilder &setMIFlag(MachineInstr::MIFlag Flag) const { + MI->setFlag(Flag); + return *this; + } + // Add a displacement from an existing MachineOperand with an added offset. const MachineInstrBuilder &addDisp(const MachineOperand &Disp, int64_t off) const { diff --git a/include/llvm/CodeGen/MachineLocation.h b/include/llvm/CodeGen/MachineLocation.h index a1fcb9fe75..21951b6680 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/MachineLoopRanges.h b/include/llvm/CodeGen/MachineLoopRanges.h new file mode 100644 index 0000000000..6a30e8b53c --- /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 cabd129353..768ce47f8b 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 { diff --git a/include/llvm/CodeGen/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h index 43405c0937..6bc80b099f 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" @@ -170,7 +170,8 @@ 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(); @@ -208,7 +209,7 @@ public: /// 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; } diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h index aaf6a2fe4f..8acc9490d8 100644 --- a/include/llvm/CodeGen/MachineOperand.h +++ b/include/llvm/CodeGen/MachineOperand.h @@ -14,7 +14,7 @@ #ifndef LLVM_CODEGEN_MACHINEOPERAND_H #define LLVM_CODEGEN_MACHINEOPERAND_H -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include <cassert> namespace llvm { @@ -153,6 +153,16 @@ public: 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; //===--------------------------------------------------------------------===// diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h index ddba61bf18..74df8da20e 100644 --- a/include/llvm/CodeGen/MachineRegisterInfo.h +++ b/include/llvm/CodeGen/MachineRegisterInfo.h @@ -16,6 +16,7 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/ADT/BitVector.h" +#include "llvm/ADT/IndexedMap.h" #include <vector> namespace llvm { @@ -24,13 +25,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 +44,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. @@ -159,17 +159,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 +192,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; } @@ -216,11 +212,9 @@ public: /// 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. @@ -232,8 +226,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; } @@ -242,8 +234,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]; } diff --git a/include/llvm/CodeGen/MachineRelocation.h b/include/llvm/CodeGen/MachineRelocation.h index c316785dd1..244b466e17 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/Passes.h b/include/llvm/CodeGen/Passes.h index bbedabd407..53aee7a9c9 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 @@ -79,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; @@ -103,6 +117,11 @@ namespace llvm { /// 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. /// @@ -196,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. @@ -213,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 4160384f89..0000000000 --- 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/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index 008a7b3bf3..7e8745edde 100644 --- a/include/llvm/CodeGen/RegAllocPBQP.h +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -22,10 +22,11 @@ #include "llvm/CodeGen/PBQP/Solution.h" #include <map> +#include <set> namespace llvm { - class LiveInterval; + class LiveIntervals; class MachineFunction; class MachineLoopInfo; diff --git a/include/llvm/CodeGen/RegisterCoalescer.h b/include/llvm/CodeGen/RegisterCoalescer.h index 7644433a33..af0b394691 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/RegisterScavenging.h b/include/llvm/CodeGen/RegisterScavenging.h index 246831c034..26b6773c05 100644 --- a/include/llvm/CodeGen/RegisterScavenging.h +++ b/include/llvm/CodeGen/RegisterScavenging.h @@ -100,7 +100,7 @@ public: /// getRegsAvailable - Return all available registers in the register class /// in Mask. - void getRegsAvailable(const TargetRegisterClass *RC, BitVector &Mask); + BitVector getRegsAvailable(const TargetRegisterClass *RC); /// FindUnusedReg - Find a unused register of the specified register class. /// Return 0 if none is found. diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index a86ba83185..3864ffd50a 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,12 @@ 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. @@ -268,13 +271,13 @@ 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), + 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), @@ -287,8 +290,8 @@ 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), + 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), @@ -300,8 +303,8 @@ 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), + 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), @@ -324,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) { @@ -341,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 @@ -351,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; } @@ -359,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; } @@ -391,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) @@ -412,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) @@ -441,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. @@ -455,7 +477,7 @@ namespace llvm { unsigned getCurCycle() const { return CurCycle; - } + } }; class ScheduleDAG { @@ -477,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. /// @@ -540,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, @@ -631,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); @@ -646,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 09e3e88613..2f53baa1c7 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 0000000000..8850006df8 --- /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 4dfc3c6728..c9de95bebd 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. @@ -633,7 +630,7 @@ public: MachinePointerInfo PtrInfo, bool isVolatile, bool isNonTemporal, unsigned Alignment, const MDNode *TBAAInfo = 0); - SDValue getExtLoad(ISD::LoadExtType ExtType, EVT VT, DebugLoc dl, + SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT, SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT, bool isVolatile, bool isNonTemporal, unsigned Alignment, @@ -904,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. @@ -966,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 9601bbc2f9..54576794de 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -35,7 +35,7 @@ namespace llvm { 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 { @@ -55,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; @@ -63,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 @@ -98,19 +98,14 @@ public: 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, @@ -129,9 +124,10 @@ public: OPC_CheckComplexPat, OPC_CheckAndImm, OPC_CheckOrImm, OPC_CheckFoldableChainNode, - + OPC_EmitInteger, OPC_EmitRegister, + OPC_EmitRegister2, OPC_EmitConvertToTarget, OPC_EmitMergeInputChains, OPC_EmitMergeInputChains1_0, @@ -140,15 +136,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. @@ -157,37 +153,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. @@ -196,46 +192,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 @@ -253,14 +249,14 @@ public: assert(0 && "Tblgen should generate the implementation of this!"); return 0; } - + 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(); @@ -269,9 +265,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); @@ -281,7 +277,7 @@ 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); @@ -292,7 +288,7 @@ private: bool &HadTailCall); void CodeGenAndEmitDAG(); void LowerArguments(const BasicBlock *BB); - + void ComputeLiveOutVRegInfo(); /// Create the scheduler. If a specific scheduler was specified @@ -300,16 +296,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 8fa099ae39..64546394ce 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() == 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; } diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index c8f26544f0..0e2adb5897 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -34,77 +34,35 @@ namespace llvm { /// SlotIndex & SlotIndexes classes for the public interface to this /// information. class IndexListEntry { - static const unsigned EMPTY_KEY_INDEX = ~0U & ~3U, - TOMBSTONE_KEY_INDEX = ~0U & ~7U; - IndexListEntry *next, *prev; MachineInstr *mi; unsigned index; - protected: - - typedef enum { EMPTY_KEY, TOMBSTONE_KEY } ReservedEntryType; - - // This constructor is only to be used by getEmptyKeyEntry - // & getTombstoneKeyEntry. It sets index to the given - // value and mi to zero. - IndexListEntry(ReservedEntryType r) : mi(0) { - switch(r) { - case EMPTY_KEY: index = EMPTY_KEY_INDEX; break; - case TOMBSTONE_KEY: index = TOMBSTONE_KEY_INDEX; break; - default: assert(false && "Invalid value for constructor."); - } - next = this; - prev = this; - } - public: - IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) { - assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to create invalid index. " - "Available indexes may have been exhausted?."); - } - - bool isValid() const { - return (index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX); - } + IndexListEntry(MachineInstr *mi, unsigned index) : mi(mi), index(index) {} MachineInstr* getInstr() const { return mi; } void setInstr(MachineInstr *mi) { - assert(isValid() && "Attempt to modify reserved index."); this->mi = mi; } unsigned getIndex() const { return index; } void setIndex(unsigned index) { - assert(index != EMPTY_KEY_INDEX && index != TOMBSTONE_KEY_INDEX && - "Attempt to set index to invalid value."); - assert(isValid() && "Attempt to reset reserved index value."); this->index = index; } IndexListEntry* getNext() { return next; } const IndexListEntry* getNext() const { return next; } void setNext(IndexListEntry *next) { - assert(isValid() && "Attempt to modify reserved index."); this->next = next; } IndexListEntry* getPrev() { return prev; } const IndexListEntry* getPrev() const { return prev; } void setPrev(IndexListEntry *prev) { - assert(isValid() && "Attempt to modify reserved index."); this->prev = prev; } - - // This function returns the index list entry that is to be used for empty - // SlotIndex keys. - static IndexListEntry* getEmptyKeyEntry(); - - // This function returns the index list entry that is to be used for - // tombstone SlotIndex keys. - static IndexListEntry* getTombstoneKeyEntry(); }; // Specialize PointerLikeTypeTraits for IndexListEntry. @@ -130,11 +88,10 @@ namespace llvm { PointerIntPair<IndexListEntry*, 2, unsigned> lie; SlotIndex(IndexListEntry *entry, unsigned slot) - : lie(entry, slot) { - assert(entry != 0 && "Attempt to construct index with 0 pointer."); - } + : lie(entry, slot) {} IndexListEntry& entry() const { + assert(isValid() && "Attempt to compare reserved index."); return *lie.getPointer(); } @@ -148,22 +105,27 @@ namespace llvm { } static inline unsigned getHashValue(const SlotIndex &v) { - IndexListEntry *ptrVal = &v.entry(); - return (unsigned((intptr_t)ptrVal) >> 4) ^ - (unsigned((intptr_t)ptrVal) >> 9); + void *ptrVal = v.lie.getOpaqueValue(); + return (unsigned((intptr_t)ptrVal)) ^ (unsigned((intptr_t)ptrVal) >> 9); } public: + enum { + /// The default distance between instructions as returned by distance(). + /// This may vary as instructions are inserted and removed. + InstrDist = 4*NUM + }; + static inline SlotIndex getEmptyKey() { - return SlotIndex(IndexListEntry::getEmptyKeyEntry(), 0); + return SlotIndex(0, 1); } static inline SlotIndex getTombstoneKey() { - return SlotIndex(IndexListEntry::getTombstoneKeyEntry(), 0); + return SlotIndex(0, 2); } /// Construct an invalid index. - SlotIndex() : lie(IndexListEntry::getEmptyKeyEntry(), 0) {} + SlotIndex() : lie(0, 0) {} // Construct a new slot index from the given one, and set the slot. SlotIndex(const SlotIndex &li, Slot s) @@ -175,8 +137,7 @@ namespace llvm { /// Returns true if this is a valid index. Invalid indicies do /// not point into an index table, and cannot be compared. bool isValid() const { - IndexListEntry *entry = lie.getPointer(); - return ((entry!= 0) && (entry->isValid())); + return lie.getPointer(); } /// Print this index to the given raw_ostream. @@ -187,11 +148,11 @@ namespace llvm { /// Compare two SlotIndex objects for equality. bool operator==(SlotIndex other) const { - return getIndex() == other.getIndex(); + return lie == other.lie; } /// Compare two SlotIndex objects for inequality. bool operator!=(SlotIndex other) const { - return getIndex() != other.getIndex(); + return lie != other.lie; } /// Compare two SlotIndex objects. Return true if the first index @@ -466,6 +427,9 @@ namespace llvm { insert(getTail(), val); } + /// Renumber locally after inserting newEntry. + void renumberIndexes(IndexListEntry *newEntry); + public: static char ID; @@ -530,7 +494,7 @@ namespace llvm { /// Returns the instruction for the given index, or null if the given /// index has no instruction associated with it. MachineInstr* getInstructionFromIndex(SlotIndex index) const { - return index.entry().getInstr(); + return index.isValid() ? index.entry().getInstr() : 0; } /// Returns the next non-null index. @@ -545,18 +509,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 first index in the given basic block. + SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { + return getMBBRange(mbb).first; } /// 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; + return getMBBRange(mbb).second; } /// Returns the basic block which the given index falls in. @@ -618,9 +586,11 @@ namespace llvm { /// Insert the given machine instruction into the mapping. Returns the /// assigned index. - SlotIndex insertMachineInstrInMaps(MachineInstr *mi, - bool *deferredRenumber = 0) { + SlotIndex insertMachineInstrInMaps(MachineInstr *mi) { 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(); @@ -632,7 +602,6 @@ namespace llvm { "Instruction's parent MBB has not been added to SlotIndexes."); MachineBasicBlock::iterator miItr(mi); - bool needRenumber = false; IndexListEntry *newEntry; // Get previous index, considering that not all instructions are indexed. IndexListEntry *prevEntry; @@ -655,55 +624,22 @@ namespace llvm { // Get a number for the new instr, or 0 if there's no room currently. // In the latter case we'll force a renumber later. - unsigned dist = nextEntry->getIndex() - prevEntry->getIndex(); - unsigned newNumber = dist > SlotIndex::NUM ? - prevEntry->getIndex() + ((dist >> 1) & ~3U) : 0; - - if (newNumber == 0) { - needRenumber = true; - } + unsigned dist = ((nextEntry->getIndex() - prevEntry->getIndex())/2) & ~3u; + unsigned newNumber = prevEntry->getIndex() + dist; // Insert a new list entry for mi. newEntry = createEntry(mi, newNumber); insert(nextEntry, newEntry); - - SlotIndex newIndex(newEntry, SlotIndex::LOAD); - mi2iMap.insert(std::make_pair(mi, newIndex)); - if (miItr == mbb->end()) { - // If this is the last instr in the MBB then we need to fix up the bb - // range: - mbbRangeItr->second.second = SlotIndex(newEntry, SlotIndex::STORE); - } - - // Renumber if we need to. - if (needRenumber) { - if (deferredRenumber == 0) - renumberIndexes(); - else - *deferredRenumber = true; - } + // Renumber locally if we need to. + if (dist == 0) + renumberIndexes(newEntry); + SlotIndex newIndex(newEntry, SlotIndex::LOAD); + mi2iMap.insert(std::make_pair(mi, newIndex)); return newIndex; } - /// Add all instructions in the vector to the index list. This method will - /// defer renumbering until all instrs have been added, and should be - /// preferred when adding multiple instrs. - void insertMachineInstrsInMaps(SmallVectorImpl<MachineInstr*> &mis) { - bool renumber = false; - - for (SmallVectorImpl<MachineInstr*>::iterator - miItr = mis.begin(), miEnd = mis.end(); - miItr != miEnd; ++miItr) { - insertMachineInstrInMaps(*miItr, &renumber); - } - - if (renumber) - renumberIndexes(); - } - - /// Remove the given machine instruction from the mapping. void removeMachineInstrFromMaps(MachineInstr *mi) { // remove index -> MachineInstr and @@ -773,6 +709,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 d8f0373859..fba3e48c47 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 ae6729a205..22d1622207 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 { @@ -79,7 +79,7 @@ namespace llvm { x86mmx = 33, // This is an X86 MMX value - Flag = 34, // This glues nodes together during pre-RA sched + Glue = 34, // This glues nodes together during pre-RA sched isVoid = 35, // This has no value |