diff options
Diffstat (limited to 'include/llvm/CodeGen')
54 files changed, 961 insertions, 367 deletions
diff --git a/include/llvm/CodeGen/Analysis.h b/include/llvm/CodeGen/Analysis.h index 0b609ed658..4ff0be758a 100644 --- a/include/llvm/CodeGen/Analysis.h +++ b/include/llvm/CodeGen/Analysis.h @@ -14,12 +14,12 @@ #ifndef LLVM_CODEGEN_ANALYSIS_H #define LLVM_CODEGEN_ANALYSIS_H -#include "llvm/Instructions.h" -#include "llvm/InlineAsm.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/ISDOpcodes.h" +#include "llvm/CodeGen/ValueTypes.h" +#include "llvm/InlineAsm.h" +#include "llvm/Instructions.h" #include "llvm/Support/CallSite.h" namespace llvm { diff --git a/include/llvm/CodeGen/CalcSpillWeights.h b/include/llvm/CodeGen/CalcSpillWeights.h index 2f76a6cc55..9cd2decfac 100644 --- a/include/llvm/CodeGen/CalcSpillWeights.h +++ b/include/llvm/CodeGen/CalcSpillWeights.h @@ -11,8 +11,8 @@ #ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H #define LLVM_CODEGEN_CALCSPILLWEIGHTS_H -#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/SlotIndexes.h" namespace llvm { diff --git a/include/llvm/CodeGen/CallingConvLower.h b/include/llvm/CodeGen/CallingConvLower.h index c1bc3aba5e..064a92ef36 100644 --- a/include/llvm/CodeGen/CallingConvLower.h +++ b/include/llvm/CodeGen/CallingConvLower.h @@ -16,11 +16,11 @@ #define LLVM_CODEGEN_CALLINGCONVLOWER_H #include "llvm/ADT/SmallVector.h" -#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CallingConv.h" #include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/ValueTypes.h" #include "llvm/Target/TargetCallingConv.h" -#include "llvm/CallingConv.h" namespace llvm { class TargetRegisterInfo; diff --git a/include/llvm/CodeGen/CommandFlags.h b/include/llvm/CodeGen/CommandFlags.h index 90ee234244..e7a654b423 100644 --- a/include/llvm/CodeGen/CommandFlags.h +++ b/include/llvm/CodeGen/CommandFlags.h @@ -16,10 +16,9 @@ #ifndef LLVM_CODEGEN_COMMAND_LINE_FLAGS_H #define LLVM_CODEGEN_COMMAND_LINE_FLAGS_H -#include "llvm/Support/CommandLine.h" #include "llvm/Support/CodeGen.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Target/TargetMachine.h" - #include <string> using namespace llvm; diff --git a/include/llvm/CodeGen/DFAPacketizer.h b/include/llvm/CodeGen/DFAPacketizer.h index e4386fc8e2..9d25fd377b 100644 --- a/include/llvm/CodeGen/DFAPacketizer.h +++ b/include/llvm/CodeGen/DFAPacketizer.h @@ -26,8 +26,8 @@ #ifndef LLVM_CODEGEN_DFAPACKETIZER_H #define LLVM_CODEGEN_DFAPACKETIZER_H -#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/MachineBasicBlock.h" #include <map> namespace llvm { diff --git a/include/llvm/CodeGen/FastISel.h b/include/llvm/CodeGen/FastISel.h index 7c24e36092..05619050a3 100644 --- a/include/llvm/CodeGen/FastISel.h +++ b/include/llvm/CodeGen/FastISel.h @@ -15,8 +15,8 @@ #define LLVM_CODEGEN_FASTISEL_H #include "llvm/ADT/DenseMap.h" -#include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/ValueTypes.h" namespace llvm { @@ -131,6 +131,10 @@ public: /// into the current block. void recomputeInsertPt(); + /// removeDeadCode - Remove all dead instructions between the I and E. + void removeDeadCode(MachineBasicBlock::iterator I, + MachineBasicBlock::iterator E); + struct SavePoint { MachineBasicBlock::iterator InsertPt; DebugLoc DL; @@ -395,10 +399,6 @@ private: /// hasTrivialKill - Test whether the given value has exactly one use. bool hasTrivialKill(const Value *V) const; - - /// removeDeadCode - Remove all dead instructions between the I and E. - void removeDeadCode(MachineBasicBlock::iterator I, - MachineBasicBlock::iterator E); }; } diff --git a/include/llvm/CodeGen/FunctionLoweringInfo.h b/include/llvm/CodeGen/FunctionLoweringInfo.h index 8cf22eca4f..789f77f26e 100644 --- a/include/llvm/CodeGen/FunctionLoweringInfo.h +++ b/include/llvm/CodeGen/FunctionLoweringInfo.h @@ -15,8 +15,6 @@ #ifndef LLVM_CODEGEN_FUNCTIONLOWERINGINFO_H #define LLVM_CODEGEN_FUNCTIONLOWERINGINFO_H -#include "llvm/InlineAsm.h" -#include "llvm/Instructions.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" @@ -24,9 +22,11 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/BranchProbabilityInfo.h" -#include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/ISDOpcodes.h" #include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/ValueTypes.h" +#include "llvm/InlineAsm.h" +#include "llvm/Instructions.h" #include "llvm/Support/CallSite.h" #include "llvm/Target/TargetRegisterInfo.h" #include <vector> diff --git a/include/llvm/CodeGen/GCMetadata.h b/include/llvm/CodeGen/GCMetadata.h index 076f6f39fe..fa40049dbd 100644 --- a/include/llvm/CodeGen/GCMetadata.h +++ b/include/llvm/CodeGen/GCMetadata.h @@ -33,9 +33,9 @@ #ifndef LLVM_CODEGEN_GCMETADATA_H #define LLVM_CODEGEN_GCMETADATA_H -#include "llvm/Pass.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/StringMap.h" +#include "llvm/Pass.h" #include "llvm/Support/DebugLoc.h" namespace llvm { diff --git a/include/llvm/CodeGen/JITCodeEmitter.h b/include/llvm/CodeGen/JITCodeEmitter.h index f95b8b6b84..e14d04e422 100644 --- a/include/llvm/CodeGen/JITCodeEmitter.h +++ b/include/llvm/CodeGen/JITCodeEmitter.h @@ -17,11 +17,11 @@ #ifndef LLVM_CODEGEN_JITCODEEMITTER_H #define LLVM_CODEGEN_JITCODEEMITTER_H -#include <string> +#include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/MachineCodeEmitter.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/MathExtras.h" -#include "llvm/CodeGen/MachineCodeEmitter.h" -#include "llvm/ADT/DenseMap.h" +#include <string> namespace llvm { diff --git a/include/llvm/CodeGen/LexicalScopes.h b/include/llvm/CodeGen/LexicalScopes.h index e1911cfd82..bb22cb74c5 100644 --- a/include/llvm/CodeGen/LexicalScopes.h +++ b/include/llvm/CodeGen/LexicalScopes.h @@ -17,11 +17,11 @@ #ifndef LLVM_CODEGEN_LEXICALSCOPES_H #define LLVM_CODEGEN_LEXICALSCOPES_H -#include "llvm/Metadata.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/Metadata.h" #include "llvm/Support/DebugLoc.h" #include "llvm/Support/ValueHandle.h" #include <utility> diff --git a/include/llvm/CodeGen/LinkAllCodegenComponents.h b/include/llvm/CodeGen/LinkAllCodegenComponents.h index 46dd004609..2145eb80bd 100644 --- a/include/llvm/CodeGen/LinkAllCodegenComponents.h +++ b/include/llvm/CodeGen/LinkAllCodegenComponents.h @@ -15,9 +15,9 @@ #ifndef LLVM_CODEGEN_LINKALLCODEGENCOMPONENTS_H #define LLVM_CODEGEN_LINKALLCODEGENCOMPONENTS_H +#include "llvm/CodeGen/GCs.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/SchedulerRegistry.h" -#include "llvm/CodeGen/GCs.h" #include "llvm/Target/TargetMachine.h" #include <cstdlib> diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 185e414ae2..95760758de 100644 --- a/include/llvm/CodeGen/LiveInterval.h +++ b/include/llvm/CodeGen/LiveInterval.h @@ -22,9 +22,9 @@ #define LLVM_CODEGEN_LIVEINTERVAL_H #include "llvm/ADT/IntEqClasses.h" -#include "llvm/Support/Allocator.h" -#include "llvm/Support/AlignOf.h" #include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/Support/AlignOf.h" +#include "llvm/Support/Allocator.h" #include <cassert> #include <climits> diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index b421753dd5..9e89519b28 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -20,16 +20,16 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/LiveInterval.h" -#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/Support/Allocator.h" +#include "llvm/Target/TargetRegisterInfo.h" #include <cmath> #include <iterator> @@ -347,6 +347,10 @@ namespace llvm { return RegUnitIntervals[Unit]; } + const LiveInterval *getCachedRegUnit(unsigned Unit) const { + return RegUnitIntervals[Unit]; + } + private: /// computeIntervals - Compute live intervals. void computeIntervals(); diff --git a/include/llvm/CodeGen/LiveIntervalUnion.h b/include/llvm/CodeGen/LiveIntervalUnion.h new file mode 100644 index 0000000000..6a61614df4 --- /dev/null +++ b/include/llvm/CodeGen/LiveIntervalUnion.h @@ -0,0 +1,205 @@ +//===-- LiveIntervalUnion.h - Live interval union data struct --*- C++ -*--===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// LiveIntervalUnion is a union of live segments across multiple live virtual +// registers. This may be used during coalescing to represent a congruence +// class, or during register allocation to model liveness of a physical +// register. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVEINTERVALUNION +#define LLVM_CODEGEN_LIVEINTERVALUNION + +#include "llvm/ADT/IntervalMap.h" +#include "llvm/CodeGen/LiveInterval.h" + +namespace llvm { + +class TargetRegisterInfo; + +#ifndef NDEBUG +// forward declaration +template <unsigned Element> class SparseBitVector; +typedef SparseBitVector<128> LiveVirtRegBitSet; +#endif + +/// Compare a live virtual register segment to a LiveIntervalUnion segment. +inline bool +overlap(const LiveRange &VRSeg, + const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) { + return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end; +} + +/// Union of live intervals that are strong candidates for coalescing into a +/// single register (either physical or virtual depending on the context). We +/// expect the constituent live intervals to be disjoint, although we may +/// eventually make exceptions to handle value-based interference. +class LiveIntervalUnion { + // A set of live virtual register segments that supports fast insertion, + // intersection, and removal. + // Mapping SlotIndex intervals to virtual register numbers. + typedef IntervalMap<SlotIndex, LiveInterval*> LiveSegments; + +public: + // SegmentIter can advance to the next segment ordered by starting position + // which may belong to a different live virtual register. We also must be able + // to reach the current segment's containing virtual register. + typedef LiveSegments::iterator SegmentIter; + + // LiveIntervalUnions share an external allocator. + typedef LiveSegments::Allocator Allocator; + + class Query; + +private: + unsigned Tag; // unique tag for current contents. + LiveSegments Segments; // union of virtual reg segments + +public: + explicit LiveIntervalUnion(Allocator &a) : Tag(0), Segments(a) {} + + // Iterate over all segments in the union of live virtual registers ordered + // by their starting position. + SegmentIter begin() { return Segments.begin(); } + SegmentIter end() { return Segments.end(); } + SegmentIter find(SlotIndex x) { return Segments.find(x); } + bool empty() const { return Segments.empty(); } + SlotIndex startIndex() const { return Segments.start(); } + + // Provide public access to the underlying map to allow overlap iteration. + typedef LiveSegments Map; + const Map &getMap() { return Segments; } + + /// getTag - Return an opaque tag representing the current state of the union. + unsigned getTag() const { return Tag; } + + /// changedSince - Return true if the union change since getTag returned tag. + bool changedSince(unsigned tag) const { return tag != Tag; } + + // Add a live virtual register to this union and merge its segments. + void unify(LiveInterval &VirtReg); + + // Remove a live virtual register's segments from this union. + void extract(LiveInterval &VirtReg); + + // Remove all inserted virtual registers. + void clear() { Segments.clear(); ++Tag; } + + // Print union, using TRI to translate register names + void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; + +#ifndef NDEBUG + // Verify the live intervals in this union and add them to the visited set. + void verify(LiveVirtRegBitSet& VisitedVRegs); +#endif + + /// Query interferences between a single live virtual register and a live + /// interval union. + class Query { + LiveIntervalUnion *LiveUnion; + LiveInterval *VirtReg; + LiveInterval::iterator VirtRegI; // current position in VirtReg + SegmentIter LiveUnionI; // current position in LiveUnion + SmallVector<LiveInterval*,4> InterferingVRegs; + bool CheckedFirstInterference; + bool SeenAllInterferences; + bool SeenUnspillableVReg; + unsigned Tag, UserTag; + + public: + Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {} + + Query(LiveInterval *VReg, LiveIntervalUnion *LIU): + LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false), + SeenAllInterferences(false), SeenUnspillableVReg(false) + {} + + void clear() { + LiveUnion = NULL; + VirtReg = NULL; + InterferingVRegs.clear(); + CheckedFirstInterference = false; + SeenAllInterferences = false; + SeenUnspillableVReg = false; + Tag = 0; + UserTag = 0; + } + + void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) { + assert(VReg && LIU && "Invalid arguments"); + if (UserTag == UTag && VirtReg == VReg && + LiveUnion == LIU && !LIU->changedSince(Tag)) { + // Retain cached results, e.g. firstInterference. + return; + } + clear(); + LiveUnion = LIU; + VirtReg = VReg; + Tag = LIU->getTag(); + UserTag = UTag; + } + + LiveInterval &virtReg() const { + assert(VirtReg && "uninitialized"); + return *VirtReg; + } + + // Does this live virtual register interfere with the union? + bool checkInterference() { return collectInterferingVRegs(1); } + + // Count the virtual registers in this union that interfere with this + // query's live virtual register, up to maxInterferingRegs. + unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX); + + // Was this virtual register visited during collectInterferingVRegs? + bool isSeenInterference(LiveInterval *VReg) const; + + // Did collectInterferingVRegs collect all interferences? + bool seenAllInterferences() const { return SeenAllInterferences; } + + // Did collectInterferingVRegs encounter an unspillable vreg? + bool seenUnspillableVReg() const { return SeenUnspillableVReg; } + + // Vector generated by collectInterferingVRegs. + const SmallVectorImpl<LiveInterval*> &interferingVRegs() const { + return InterferingVRegs; + } + + private: + Query(const Query&) LLVM_DELETED_FUNCTION; + void operator=(const Query&) LLVM_DELETED_FUNCTION; + }; + + // Array of LiveIntervalUnions. + class Array { + unsigned Size; + LiveIntervalUnion *LIUs; + public: + Array() : Size(0), LIUs(0) {} + ~Array() { clear(); } + + // Initialize the array to have Size entries. + // Reuse an existing allocation if the size matches. + void init(LiveIntervalUnion::Allocator&, unsigned Size); + + unsigned size() const { return Size; } + + void clear(); + + LiveIntervalUnion& operator[](unsigned idx) { + assert(idx < Size && "idx out of bounds"); + return LIUs[idx]; + } + }; +}; + +} // end namespace llvm + +#endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION) diff --git a/include/llvm/CodeGen/LiveRegMatrix.h b/include/llvm/CodeGen/LiveRegMatrix.h new file mode 100644 index 0000000000..7a3e9e8347 --- /dev/null +++ b/include/llvm/CodeGen/LiveRegMatrix.h @@ -0,0 +1,148 @@ +//===-- LiveRegMatrix.h - Track register interference ---------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// The LiveRegMatrix analysis pass keeps track of virtual register interference +// along two dimensions: Slot indexes and register units. The matrix is used by +// register allocators to ensure that no interfering virtual registers get +// assigned to overlapping physical registers. +// +// Register units are defined in MCRegisterInfo.h, they represent the smallest +// unit of interference when dealing with overlapping physical registers. The +// LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When +// a virtual register is assigned to a physical register, the live range for +// the virtual register is inserted into the LiveIntervalUnion for each regunit +// in the physreg. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVEREGMATRIX_H +#define LLVM_CODEGEN_LIVEREGMATRIX_H + +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/CodeGen/LiveIntervalUnion.h" +#include "llvm/CodeGen/MachineFunctionPass.h" + +namespace llvm { + +class LiveInterval; +class LiveIntervalAnalysis; +class MachineRegisterInfo; +class TargetRegisterInfo; +class VirtRegMap; + +class LiveRegMatrix : public MachineFunctionPass { + const TargetRegisterInfo *TRI; + MachineRegisterInfo *MRI; + LiveIntervals *LIS; + VirtRegMap *VRM; + + // UserTag changes whenever virtual registers have been modified. + unsigned UserTag; + + // The matrix is represented as a LiveIntervalUnion per register unit. + LiveIntervalUnion::Allocator LIUAlloc; + LiveIntervalUnion::Array Matrix; + + // Cached queries per register unit. + OwningArrayPtr<LiveIntervalUnion::Query> Queries; + + // Cached register mask interference info. + unsigned RegMaskTag; + unsigned RegMaskVirtReg; + BitVector RegMaskUsable; + + // MachineFunctionPass boilerplate. + virtual void getAnalysisUsage(AnalysisUsage&) const; + virtual bool runOnMachineFunction(MachineFunction&); + virtual void releaseMemory(); +public: + static char ID; + LiveRegMatrix(); + + //===--------------------------------------------------------------------===// + // High-level interface. + //===--------------------------------------------------------------------===// + // + // Check for interference before assigning virtual registers to physical + // registers. + // + + /// Invalidate cached interference queries after modifying virtual register + /// live ranges. Interference checks may return stale information unless + /// caches are invalidated. + void invalidateVirtRegs() { ++UserTag; } + + enum InterferenceKind { + /// No interference, go ahead and assign. + IK_Free = 0, + + /// Virtual register interference. There are interfering virtual registers + /// assigned to PhysReg or its aliases. This interference could be resolved + /// by unassigning those other virtual registers. + IK_VirtReg, + + /// Register unit interference. A fixed live range is in the way, typically |