diff options
Diffstat (limited to 'include/llvm/CodeGen')
76 files changed, 2534 insertions, 980 deletions
diff --git a/include/llvm/CodeGen/Analysis.h b/include/llvm/CodeGen/Analysis.h index 0b609ed..ce9ca0a 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/IR/InlineAsm.h" +#include "llvm/IR/Instructions.h" #include "llvm/Support/CallSite.h" namespace llvm { @@ -86,11 +86,7 @@ ISD::CondCode getICmpCondCode(ICmpInst::Predicate Pred); /// between it and the return. /// /// This function only tests target-independent requirements. -bool isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, - const TargetLowering &TLI); - -bool isInTailCallPosition(SelectionDAG &DAG, SDNode *Node, - SDValue &Chain, const TargetLowering &TLI); +bool isInTailCallPosition(ImmutableCallSite CS, const TargetLowering &TLI); } // End llvm namespace diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h index a92b859..e0a6e3f 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/InlineAsm.h" +#include "llvm/IR/InlineAsm.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/ErrorHandling.h" @@ -385,10 +385,8 @@ namespace llvm { /// GetSizeOfEncodedValue - Return the size of the encoding in bytes. unsigned GetSizeOfEncodedValue(unsigned Encoding) const; - /// EmitReference - Emit a reference to a label with a specified encoding. - /// - void EmitReference(const MCSymbol *Sym, unsigned Encoding) const; - void EmitReference(const GlobalValue *GV, unsigned Encoding) const; + /// EmitReference - Emit reference to a ttype global with a specified encoding. + void EmitTTypeReference(const GlobalValue *GV, unsigned Encoding) const; /// EmitSectionOffset - Emit the 4-byte offset of Label from the start of /// its section. This can be done with a special directive if the target diff --git a/include/llvm/CodeGen/CalcSpillWeights.h b/include/llvm/CodeGen/CalcSpillWeights.h index 2f76a6c..9cd2dec 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 436918b1..c035e07 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/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/ValueTypes.h" +#include "llvm/IR/CallingConv.h" #include "llvm/Target/TargetCallingConv.h" -#include "llvm/CallingConv.h" namespace llvm { class TargetRegisterInfo; @@ -50,10 +50,10 @@ private: unsigned Loc; /// isMem - True if this is a memory loc, false if it is a register loc. - bool isMem : 1; + unsigned isMem : 1; /// isCustom - True if this arg/retval requires special handling. - bool isCustom : 1; + unsigned isCustom : 1; /// Information about how the value is assigned. LocInfo HTP : 6; diff --git a/include/llvm/CodeGen/CommandFlags.h b/include/llvm/CodeGen/CommandFlags.h index 90ee234..9a27661 100644 --- a/include/llvm/CodeGen/CommandFlags.h +++ b/include/llvm/CodeGen/CommandFlags.h @@ -1,4 +1,4 @@ -//===-- CommandFlags.h - Register Coalescing Interface ----------*- C++ -*-===// +//===-- CommandFlags.h - Command Line Flags Interface -----------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -13,13 +13,12 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_COMMAND_LINE_FLAGS_H -#define LLVM_CODEGEN_COMMAND_LINE_FLAGS_H +#ifndef LLVM_CODEGEN_COMMANDFLAGS_H +#define LLVM_CODEGEN_COMMANDFLAGS_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/DAGCombine.h b/include/llvm/CodeGen/DAGCombine.h new file mode 100644 index 0000000..8b591900 --- /dev/null +++ b/include/llvm/CodeGen/DAGCombine.h @@ -0,0 +1,25 @@ +//===-- llvm/CodeGen/DAGCombine.h ------- SelectionDAG Nodes ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// + +#ifndef LLVM_CODEGEN_DAGCOMBINE_H +#define LLVM_CODEGEN_DAGCOMBINE_H + +namespace llvm { + +enum CombineLevel { + BeforeLegalizeTypes, + AfterLegalizeTypes, + AfterLegalizeVectorOps, + AfterLegalizeDAG +}; + +} // end llvm namespace + +#endif diff --git a/include/llvm/CodeGen/DFAPacketizer.h b/include/llvm/CodeGen/DFAPacketizer.h index 2d2db78..9d25fd3 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 { @@ -135,7 +135,7 @@ public: // initPacketizerState - perform initialization before packetizing // an instruction. This function is supposed to be overrided by // the target dependent packetizer. - virtual void initPacketizerState(void) { return; } + virtual void initPacketizerState() { return; } // ignorePseudoInstruction - Ignore bundling of pseudo instructions. virtual bool ignorePseudoInstruction(MachineInstr *I, diff --git a/include/llvm/CodeGen/FastISel.h b/include/llvm/CodeGen/FastISel.h index 7c24e36..705db7e 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 { @@ -90,6 +90,11 @@ public: /// getCurDebugLoc() - Return current debug location information. DebugLoc getCurDebugLoc() const { return DL; } + + /// LowerArguments - Do "fast" instruction selection for function arguments + /// and append machine instructions to the current block. Return true if + /// it is successful. + bool LowerArguments(); /// SelectInstruction - Do "fast" instruction selection for the given /// LLVM IR instruction, and append generated machine instructions to @@ -131,6 +136,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; @@ -156,6 +165,11 @@ protected: /// virtual bool TargetSelectInstruction(const Instruction *I) = 0; + + /// FastLowerArguments - This method is called by target-independent code to + /// do target specific argument lowering. It returns true if it was + /// successful. + virtual bool FastLowerArguments(); /// FastEmit_r - This method is called by target-independent code /// to request that an instruction with the given type and opcode @@ -395,10 +409,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 8cf22ec..ea6cb27 100644 --- a/include/llvm/CodeGen/FunctionLoweringInfo.h +++ b/include/llvm/CodeGen/FunctionLoweringInfo.h @@ -15,19 +15,15 @@ #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" #include "llvm/ADT/IndexedMap.h" #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/Support/CallSite.h" +#include "llvm/CodeGen/ValueTypes.h" +#include "llvm/IR/InlineAsm.h" +#include "llvm/IR/Instructions.h" #include "llvm/Target/TargetRegisterInfo.h" #include <vector> @@ -35,6 +31,7 @@ namespace llvm { class AllocaInst; class BasicBlock; +class BranchProbabilityInfo; class CallInst; class Function; class GlobalVariable; @@ -136,7 +133,7 @@ public: return ValueMap.count(V); } - unsigned CreateReg(EVT VT); + unsigned CreateReg(MVT VT); unsigned CreateRegs(Type *Ty); diff --git a/include/llvm/CodeGen/GCMetadata.h b/include/llvm/CodeGen/GCMetadata.h index 076f6f3..1070d29 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 { @@ -180,7 +180,8 @@ namespace llvm { GCModuleInfo(); ~GCModuleInfo(); - /// clear - Resets the pass. The metadata deleter pass calls this. + /// clear - Resets the pass. Any pass, which uses GCModuleInfo, should + /// call it in doFinalization(). /// void clear(); diff --git a/include/llvm/CodeGen/GCs.h b/include/llvm/CodeGen/GCs.h index c407b61..456d2dc 100644 --- a/include/llvm/CodeGen/GCs.h +++ b/include/llvm/CodeGen/GCs.h @@ -26,6 +26,12 @@ namespace llvm { /// Creates an ocaml-compatible metadata printer. void linkOcamlGCPrinter(); + + /// Creates an erlang-compatible garbage collector. + void linkErlangGC(); + + /// Creates an erlang-compatible metadata printer. + void linkErlangGCPrinter(); /// Creates a shadow stack garbage collector. This collector requires no code /// generator support. diff --git a/include/llvm/CodeGen/ISDOpcodes.h b/include/llvm/CodeGen/ISDOpcodes.h index 5d0a3b4..442729b 100644 --- a/include/llvm/CodeGen/ISDOpcodes.h +++ b/include/llvm/CodeGen/ISDOpcodes.h @@ -311,8 +311,10 @@ namespace ISD { /// 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. + /// to represent the shift amount. + /// When the 1st operand is a vector, the shift amount must be in the same + /// type. (TLI.getShiftAmountTy() will return the same type when the input + /// type is a vector.) SHL, SRA, SRL, ROTL, ROTR, /// Byte Swap and Counting operators. @@ -455,6 +457,9 @@ namespace ISD { FNEG, FABS, FSQRT, FSIN, FCOS, FPOWI, FPOW, FLOG, FLOG2, FLOG10, FEXP, FEXP2, FCEIL, FTRUNC, FRINT, FNEARBYINT, FFLOOR, + + /// FSINCOS - Compute both fsin and fcos as a single operation. + FSINCOS, /// LOAD and STORE have token chains as their first operand, then the same /// operands as an LLVM load/store instruction, then an offset node that diff --git a/include/llvm/CodeGen/IntrinsicLowering.h b/include/llvm/CodeGen/IntrinsicLowering.h index 5a3fb4b..68389dd 100644 --- a/include/llvm/CodeGen/IntrinsicLowering.h +++ b/include/llvm/CodeGen/IntrinsicLowering.h @@ -16,7 +16,7 @@ #ifndef LLVM_CODEGEN_INTRINSICLOWERING_H #define LLVM_CODEGEN_INTRINSICLOWERING_H -#include "llvm/Intrinsics.h" +#include "llvm/IR/Intrinsics.h" namespace llvm { class CallInst; diff --git a/include/llvm/CodeGen/JITCodeEmitter.h b/include/llvm/CodeGen/JITCodeEmitter.h index 89f00e9..9a73214 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 { @@ -207,8 +207,7 @@ public: /// emitString - This callback is invoked when a String needs to be /// written to the output stream. void emitString(const std::string &String) { - for (unsigned i = 0, N = static_cast<unsigned>(String.size()); - i < N; ++i) { + for (size_t i = 0, N = String.size(); i < N; ++i) { uint8_t C = String[i]; emitByte(C); } diff --git a/include/llvm/CodeGen/LatencyPriorityQueue.h b/include/llvm/CodeGen/LatencyPriorityQueue.h index 8fb31aa..d454347 100644 --- a/include/llvm/CodeGen/LatencyPriorityQueue.h +++ b/include/llvm/CodeGen/LatencyPriorityQueue.h @@ -13,8 +13,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LATENCY_PRIORITY_QUEUE_H -#define LATENCY_PRIORITY_QUEUE_H +#ifndef LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H +#define LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H #include "llvm/CodeGen/ScheduleDAG.h" diff --git a/include/llvm/CodeGen/LexicalScopes.h b/include/llvm/CodeGen/LexicalScopes.h index 8414c64..ff65db4 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/IR/Metadata.h" #include "llvm/Support/DebugLoc.h" #include "llvm/Support/ValueHandle.h" #include <utility> @@ -159,9 +159,6 @@ public: LexicalScope(LexicalScope *P, const MDNode *D, const MDNode *I, bool A) : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A), LastInsn(0), FirstInsn(0), DFSIn(0), DFSOut(0) { -#ifndef NDEBUG - IndentLevel = 0; -#endif if (Parent) Parent->addChild(this); } @@ -228,7 +225,7 @@ public: void setDFSIn(unsigned I) { DFSIn = I; } /// dump - print lexical scope. - void dump() const; + void dump(unsigned Indent = 0) const; private: LexicalScope *Parent; // Parent to this scope. @@ -244,9 +241,6 @@ private: const MachineInstr *FirstInsn; // First instruction of this scope. unsigned DFSIn, DFSOut; // In & Out Depth use to determine // scope nesting. -#ifndef NDEBUG - mutable unsigned IndentLevel; // Private state for dump() -#endif }; } // end llvm namespace diff --git a/include/llvm/CodeGen/LinkAllAsmWriterComponents.h b/include/llvm/CodeGen/LinkAllAsmWriterComponents.h index 7d1b1fe..c3046da 100644 --- a/include/llvm/CodeGen/LinkAllAsmWriterComponents.h +++ b/include/llvm/CodeGen/LinkAllAsmWriterComponents.h @@ -29,6 +29,7 @@ namespace { return; llvm::linkOcamlGCPrinter(); + llvm::linkErlangGCPrinter(); } } ForceAsmWriterLinking; // Force link by creating a global definition. diff --git a/include/llvm/CodeGen/LinkAllCodegenComponents.h b/include/llvm/CodeGen/LinkAllCodegenComponents.h index 46dd004..916c0f2 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> @@ -37,6 +37,7 @@ namespace { (void) llvm::createDefaultPBQPRegisterAllocator(); llvm::linkOcamlGC(); + llvm::linkErlangGC(); llvm::linkShadowStackGC(); (void) llvm::createBURRListDAGScheduler(NULL, llvm::CodeGenOpt::Default); diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 185e414..244be9c 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> @@ -86,9 +86,10 @@ namespace llvm { SlotIndex end; // End point of the interval (exclusive) VNInfo *valno; // identifier for the value contained in this interval. + LiveRange() : valno(0) {} + LiveRange(SlotIndex S, SlotIndex E, VNInfo *V) : start(S), end(E), valno(V) { - assert(S < E && "Cannot create empty or backwards range"); } @@ -373,8 +374,8 @@ namespace llvm { /// addRange - Add the specified LiveRange to this interval, merging /// intervals as appropriate. This returns an iterator to the inserted live /// range (which may have grown since it was inserted. - void addRange(LiveRange LR) { - addRangeFrom(LR, ranges.begin()); + iterator addRange(LiveRange LR) { + return addRangeFrom(LR, ranges.begin()); } /// extendInBlock - If this interval is live before Kill in the basic block @@ -460,9 +461,6 @@ namespace llvm { void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd); Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr); void markValNoForDeletion(VNInfo *V); - void mergeIntervalRanges(const LiveInterval &RHS, - VNInfo *LHSValNo = 0, - const VNInfo *RHSValNo = 0); LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION; @@ -473,6 +471,64 @@ namespace llvm { return OS; } + /// Helper class for performant LiveInterval bulk updates. + /// + /// Calling LiveInterval::addRange() repeatedly can be expensive on large + /// live ranges because segments after the insertion point may need to be + /// shifted. The LiveRangeUpdater class can defer the shifting when adding + /// many segments in order. + /// + /// The LiveInterval will be in an invalid state until flush() is called. + class LiveRangeUpdater { + LiveInterval *LI; + SlotIndex LastStart; + LiveInterval::iterator WriteI; + LiveInterval::iterator ReadI; + SmallVector<LiveRange, 16> Spills; + void mergeSpills(); + + public: + /// Create a LiveRangeUpdater for adding segments to LI. + /// LI will temporarily be in an invalid state until flush() is called. + LiveRangeUpdater(LiveInterval *li = 0) : LI(li) {} + + ~LiveRangeUpdater() { flush(); } + + /// Add a segment to LI and coalesce when possible, just like LI.addRange(). + /// Segments should be added in increasing start order for best performance. + void add(LiveRange); + + void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { + add(LiveRange(Start, End, VNI)); + } + + /// Return true if the LI is currently in an invalid state, and flush() + /// needs to be called. + bool isDirty() const { return LastStart.isValid(); } + + /// Flush the updater state to LI so it is valid and contains all added + /// segments. + void flush(); + + /// Select a different destination live range. + void setDest(LiveInterval *li) { + if (LI != li && isDirty()) + flush(); + LI = li; + } + + /// Get the current destination live range. + LiveInterval *getDest() const { return LI; } + + void dump() const; + void print(raw_ostream&) const; + }; + + inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) { + X.print(OS); + return OS; + } + /// LiveRangeQuery - Query information about a live range around a given /// instruction. This class hides the implementation details of live ranges, /// and it should be used as the primary interface for examining live ranges diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index b421753..7d72f37 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -20,22 +20,21 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/ADT/IndexedMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/LiveInterval.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/Support/Allocator.h" +#include "llvm/Target/TargetRegisterInfo.h" #include <cmath> #include <iterator> namespace llvm { class AliasAnalysis; + class BitVector; class LiveRangeCalc; class LiveVariables; class MachineDominatorTree; @@ -53,7 +52,6 @@ namespace llvm { const TargetRegisterInfo* TRI; const TargetInstrInfo* TII; AliasAnalysis *AA; - LiveVariables* LV; SlotIndexes* Indexes; MachineDominatorTree *DomTree; LiveRangeCalc *LRCalc; @@ -215,6 +213,13 @@ namespace llvm { return Indexes->getMBBFromIndex(index); } + void insertMBBInMaps(MachineBasicBlock *MBB) { + Indexes->insertMBBInMaps(MBB); + assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() && + "Blocks must be added in order."); + RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0)); + } + SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { return Indexes->insertMachineInstrInMaps(MI); } @@ -275,6 +280,21 @@ namespace llvm { void handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart, bool UpdateFlags = false); + /// repairIntervalsInRange - Update live intervals for instructions in a + /// range of iterators. It is intended for use after target hooks that may + /// insert or remove instructions, and is only efficient for a small number + /// of instructions. + /// + /// OrigRegs is a vector of registers that were originally used by the + /// instructions in the range between the two iterators. + /// + /// Currently, the only only changes that are supported are simple removal + /// and addition of uses. + void repairIntervalsInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + ArrayRef<unsigned> OrigRegs); + // Register mask functions. // // Machine instructions may use a register mask operand to indicate that a @@ -347,37 +367,17 @@ namespace llvm { return RegUnitIntervals[Unit]; } - private: - /// computeIntervals - Compute live intervals. - void computeIntervals(); + const LiveInterval *getCachedRegUnit(unsigned Unit) const { + return RegUnitIntervals[Unit]; + } + private: /// Compute live intervals for all virtual registers. void computeVirtRegs(); /// Compute RegMaskSlots and RegMaskBits. void computeRegMasks(); - /// handleRegisterDef - update intervals for a register def - /// (calls handleVirtualRegisterDef) - void handleRegisterDef(MachineBasicBlock *MBB, - MachineBasicBlock::iterator MI, - SlotIndex MIIdx, - MachineOperand& MO, unsigned MOIdx); - - /// isPartialRedef - Return true if the specified def at the specific index - /// is partially re-defining the specified live interval. A common case of - /// this is a definition of the sub-register. - bool isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, - LiveInterval &interval); - - /// handleVirtualRegisterDef - update intervals for a virtual - /// register def - void handleVirtualRegisterDef(MachineBasicBlock *MBB, - MachineBasicBlock::iterator MI, - SlotIndex MIIdx, MachineOperand& MO, - unsigned MOIdx, - LiveInterval& interval); - static LiveInterval* createInterval(unsigned Reg); void printInstrs(raw_ostream &O) const; diff --git a/include/llvm/CodeGen/LiveIntervalUnion.h b/include/llvm/CodeGen/LiveIntervalUnion.h new file mode 100644 index 0000000..615b339 --- /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_H +#define LLVM_CODEGEN_LIVEINTERVALUNION_H + +#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_H) diff --git a/include/llvm/CodeGen/LiveRangeEdit.h b/include/llvm/CodeGen/LiveRangeEdit.h index def7b00..8a32a3c 100644 --- a/include/llvm/CodeGen/LiveRangeEdit.h +++ b/include/llvm/CodeGen/LiveRangeEdit.h @@ -83,7 +83,7 @@ private: /// allUsesAvailableAt - Return true if all registers used by OrigMI at /// OrigIdx are also available with the same value at UseIdx. bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx, - SlotIndex UseIdx); + SlotIndex UseIdx) const; /// foldAsLoad - If LI has a single use and a single def that can be folded as /// a load, eliminate the register by folding the def into the use. diff --git a/include/llvm/CodeGen/LiveRegMatrix.h b/include/llvm/CodeGen/LiveRegMatrix.h new file mode 100644 index 0000000..7a3e9e8 --- /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 + /// argument registers for a call. This can't be resolved by unassigning + /// other virtual registers. + IK_RegUnit, + + /// RegMask interference. The live range is crossing an instruction with a + /// regmask operand that doesn't preserve PhysReg. This typically means + /// VirtReg is live across a call, and PhysReg isn't call-preserved. + IK_RegMask + }; + + /// Check for interference before assigning VirtReg to PhysReg. + /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg). + /// When there is more than one kind of interference, the InterferenceKind + /// with the highest enum value is returned. + InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg); + + /// Assign VirtReg to PhysReg. + /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and + /// update VirtRegMap. The live range is expected to be available in PhysReg. + void assign(LiveInterval &VirtReg, unsigned PhysReg); + + /// Unassign VirtReg from its PhysReg. + /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes + /// the assignment and updates VirtRegMap accordingly. + void unassign(LiveInterval &VirtReg); + + //===--------------------------------------------------------------------===// + // Low-level interface. + //===--------------------------------------------------------------------===// + // + // Provide access to the underlying LiveIntervalUnions. + // + + /// Check for regmask interference only. + /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg. + /// If PhysReg is null, check if VirtReg crosses any regmask operands. + bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0); + + /// Check for regunit interference only. + /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's + /// register units. + bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg); + + /// Query a line of the assigned virtual register matrix directly. + /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. + /// This returns a reference to an internal Query data structure that is only + /// valid until the next query() call. + LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned RegUnit); + + /// Directly access the live interval unions per regunit. + /// This returns an array indexed by the regunit number. + LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } +}; + +} // end namespace llvm + +#endif // LLVM_CODEGEN_LIVEREGMATRIX_H diff --git a/include/llvm/CodeGen/LiveStackAnalysis.h b/include/llvm/CodeGen/LiveStackAnalysis.h index 86c4d7c..92c35f7 100644 --- a/include/llvm/CodeGen/LiveStackAnalysis.h +++ b/include/llvm/CodeGen/LiveStackAnalysis.h @@ -13,13 +13,13 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_LIVESTACK_ANALYSIS_H -#define LLVM_CODEGEN_LIVESTACK_ANALYSIS_H +#ifndef LLVM_CODEGEN_LIVESTACKANALYSIS_H +#define LLVM_CODEGEN_LIVESTACKANALYSIS_H -#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/LiveInterval.h" -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/Support/Allocator.h" +#include "llvm/Target/TargetRegisterInfo.h" #include <map> namespace llvm { diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index 3bb134b..6628fd2 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -29,21 +29,19 @@ #ifndef LLVM_CODEGEN_LIVEVARIABLES_H #define LLVM_CODEGEN_LIVEVARIABLES_H -#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" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/TargetRegisterInfo.h" namespace llvm { +class MachineBasicBlock; class MachineRegisterInfo; -class TargetRegisterInfo; class LiveVariables : public MachineFunctionPass { public: diff --git a/include/llvm/CodeGen/MachORelocation.h b/include/llvm/CodeGen/MachORelocation.h index 21fe74f..8c9b7a8 100644 --- a/include/llvm/CodeGen/MachORelocation.h +++ b/include/llvm/CodeGen/MachORelocation.h @@ -12,8 +12,8 @@ //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_MACHO_RELOCATION_H -#define LLVM_CODEGEN_MACHO_RELOCATION_H +#ifndef LLVM_CODEGEN_MACHORELOCATION_H +#define LLVM_CODEGEN_MACHORELOCATION_H #include "llvm/Support/DataTypes.h" @@ -53,4 +53,4 @@ namespace llvm { } // end llvm namespace -#endif // LLVM_CODEGEN_MACHO_RELOCATION_H +#endif // LLVM_CODEGEN_MACHORELOCATION_H diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 97c3945..492a3ff 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -14,8 +14,8 @@ #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H #define LLVM_CODEGEN_MACHINEBASICBLOCK_H -#include "llvm/CodeGen/MachineInstr.h" #include "llvm/ADT/GraphTraits.h" +#include "llvm/CodeGen/MachineInstr.h" #include "llvm/Support/DataTypes.h" #include <functional> @@ -146,11 +146,11 @@ public: bundle_iterator(IterTy mii) : MII(mii) {} bundle_iterator(Ty &mi) : MII(mi) { - assert(!mi.isInsideBundle() && + assert(!mi.isBundledWithPred() && "It's not legal to initialize bundle_iterator with a bundled MI"); } bundle_iterator(Ty *mi) : MII(mi) { - assert((!mi || !mi->isInsideBundle()) && + assert((!mi || !mi->isBundledWithPred()) && "It's not legal to initialize bundle_iterator with a bundled MI"); } // Template allows conversion from const to nonconst. @@ -174,13 +174,13 @@ public: // Increment and decrement operators... bundle_iterator &operator--() { // predecrement - Back up do --MII; - while (MII->isInsideBundle()); + while (MII->isBundledWithPred()); return *this; } bundle_iterator &operator++() { // preincrement - Advance - IterTy E = MII->getParent()->instr_end(); - do ++MII; - while (MII != E && MII->isInsideBundle()); + while (MII->isBundledWithSucc()) + ++MII; + ++MII; return *this; } bundle_iterator operator--(int) { // postdecrement operators... @@ -441,80 +441,107 @@ public: void pop_back() { Insts.pop_back(); } void push_back(MachineInstr *MI) { Insts.push_back(MI); } - template<typename IT> - void insert(instr_iterator I, IT S, IT E) { - Insts.insert(I, S, E); - } - instr_iterator insert(instr_iterator I, MachineInstr *M) { - return Insts.insert(I, M); - } - instr_iterator insertAfter(instr_iterator I, MachineInstr *M) { - return Insts.insertAfter(I, M); - } + /// Insert MI into the instruction list before I, possibly inside a bundle. + /// + /// If the insertion point is inside a bundle, MI will be added to the bundle, + /// otherwise MI will not be added to any bundle. That means this function + /// alone can't be used to prepend or append instructions to bundles. See + /// MIBundleBuilder::insert() for a more reliable way of doing that. + instr_iterator insert(instr_iterator I, MachineInstr *M); + /// Insert a range of instructions into the instruction list before I. template<typename IT> void insert(iterator I, IT S, IT E) { Insts.insert(I.getInstrIterator(), S, E); } - iterator insert(iterator I, MachineInstr *M) { - return Insts.insert(I.getInstrIterator(), M); + + /// Insert MI into the instruction list before I. + iterator insert(iterator I, MachineInstr *MI) { + assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && + "Cannot insert instruction with bundle flags"); + return Insts.insert(I.getInstrIterator(), MI); } - iterator insertAfter(iterator I, MachineInstr *M) { - return Insts.insertAfter(I.getInstrIterator(), M); + + /// Insert MI into the instruction list after I. + iterator insertAfter(iterator I, MachineInstr *MI) { + assert(!MI->isBundledWithPred() && !MI->isBundledWithSucc() && + "Cannot insert instruction with bundle flags"); + return Insts.insertAfter(I.getInstrIterator(), MI); } - /// erase - Remove the specified element or range from the instruction list. - /// These functions delete any instructions removed. + /// Remove an instruction from the instruction list and delete it. /// - instr_iterator erase(instr_iterator I) { - return Insts.erase(I); - } - instr_iterator erase(instr_iterator I, instr_iterator E) { - return Insts.erase(I, E); - } + /// If the instruction is part of a bundle, the other instructions in the + /// bundle will still be bundled after removing the single instruction. + instr_iterator erase(instr_iterator I); + + /// Remove an instruction from the instruction list and delete it. + /// + /// If the instruction is part of a bundle, the other instructions in the + /// bundle will still be bundled after removing the single instruction. instr_iterator erase_instr(MachineInstr *I) { - instr_iterator MII(I); - return erase(MII); + return erase(instr_iterator(I)); } - iterator erase(iterator I); + /// Remove a range of instructions from the instruction list and delete them. iterator erase(iterator I, iterator E) { return Insts.erase(I.getInstrIterator(), E.getInstrIterator()); } + + /// Remove an instruction or bundle from the instruction list and delete it. + /// + /// If I points to a bundle of instructions, they are all erased. + iterator erase(iterator I) { + return erase(I, llvm::next(I)); + } + + /// Remove an instruction from the instruction list and delete it. + /// + /// If I is the head of a bundle of instructions, the whole bundle will be + /// erased. iterator erase(MachineInstr *I) { - iterator MII(I); - return erase(MII); + return erase(iterator(I)); } - /// remove - Remove the instruction from the instruction list. This function - /// does not delete the instruction. WARNING: Note, if the specified - /// instruction is a bundle this function will remove all the bundled - /// instructions as well. It is up to the caller to keep a list of the - /// bundled instructions and re-insert them if desired. This function is - /// *not recommended* for manipulating instructions with bundles. Use - /// splice instead. - MachineInstr *remove(MachineInstr *I); + /// Remove the unbundled instruction from the instruction list without + /// deleting it. + /// + /// This function can not be used to remove bundled instructions, use + /// remove_instr to remove individual instructions from a bundle. + MachineInstr *remove(MachineInstr *I) { + assert(!I->isBundled() && "Cannot remove bundled instructions"); + return Insts.remove(I); + } + + /// Remove the possibly bundled instruction from the instruction list + /// without deleting it. + /// + /// If the instruction is part of a bundle, the other instructions in the + /// bundle will still be bundled after removing the single instruction. + MachineInstr *remove_instr(MachineInstr *I); + void clear() { Insts.clear(); } - /// splice - Take an instruction from MBB 'Other' at the position From, - /// and insert it into this MBB right before 'where'. - void splice(instr_iterator where, MachineBasicBlock *Other, - instr_iterator From) { - Insts.splice(where, Other->Insts, From); + /// Take an instruction from MBB 'Other' at the position From, and insert it + /// into this MBB right before 'Where'. + /// + /// If From points to a bundle of instructions, the whole bundle is moved. + void splice(iterator Where, MachineBasicBlock *Other, iterator From) { + // The range splice() doesn't allow noop moves, but this one does. + if (Where != From) + splice(Where, Other, From, llvm::next(From)); } - void splice(iterator where, MachineBasicBlock *Other, iterator From); - /// splice - Take a block of instructions from MBB 'Other' in the range [From, - /// To), and insert them into this MBB right before 'where'. - void splice(instr_iterator where, MachineBasicBlock *Other, instr_iterator From, - instr_iterator To) { - Insts.splice(where, Other->Insts, From, To); - } - void splice(iterator where, MachineBasicBlock *Other, iterator From, - iterator To) { - Insts.splice(where.getInstrIterator(), Other->Insts, + /// Take a block of instructions from MBB 'Other' in the range [From, To), + /// and insert them into this MBB right before 'Where'. + /// + /// The instruction at 'Where' must not be included in the range of + /// instructions to move. + void splice(iterator Where, MachineBasicBlock *Other, + iterator From, iterator To) { + Insts.splice(Where.getInstrIterator(), Other->Insts, From.getInstrIterator(), To.getInstrIterator()); } diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h index 12189ce..98dd03b 100644 --- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -1,4 +1,3 @@ - //==- MachineBranchProbabilityInfo.h - Machine Branch Probability Analysis -==// // // The LLVM Compiler Infrastructure @@ -15,8 +14,8 @@ #ifndef LLVM_CODEGEN_MACHINEBRANCHPROBABILITYINFO_H #define LLVM_CODEGEN_MACHINEBRANCHPROBABILITYINFO_H -#include "llvm/Pass.h" #include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/Pass.h" #include "llvm/Support/BranchProbability.h" #include <climits> diff --git a/include/llvm/CodeGen/MachineCodeEmitter.h b/include/llvm/CodeGen/MachineCodeEmitter.h index 86e8f27..9e41e6e 100644 --- a/include/llvm/CodeGen/MachineCodeEmitter.h +++ b/include/llvm/CodeGen/MachineCodeEmitter.h @@ -19,7 +19,6 @@ #include "llvm/Support/DataTypes.h" #include "llvm/Support/DebugLoc.h" - #include <string> namespace llvm { diff --git a/include/llvm/CodeGen/MachineCodeInfo.h b/include/llvm/CodeGen/MachineCodeInfo.h index c5c0c44..ba9dfab 100644 --- a/include/llvm/CodeGen/MachineCodeInfo.h +++ b/include/llvm/CodeGen/MachineCodeInfo.h @@ -14,8 +14,8 @@ // //===----------------------------------------------------------------------===// -#ifndef EE_MACHINE_CODE_INFO_H -#define EE_MACHINE_CODE_INFO_H +#ifndef LLVM_CODEGEN_MACHINECODEINFO_H +#define LLVM_CODEGEN_MACHINECODEINFO_H #include "llvm/Support/DataTypes.h" diff --git a/include/llvm/CodeGen/MachineDominators.h b/include/llvm/CodeGen/MachineDominators.h index 82a4ac8..e41d206 100644 --- a/include/llvm/CodeGen/MachineDominators.h +++ b/include/llvm/CodeGen/MachineDominators.h @@ -15,11 +15,11 @@ #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H #define LLVM_CODEGEN_MACHINEDOMINATORS_H +#include "llvm/Analysis/DominatorInternals.h" +#include "llvm/Analysis/Dominators.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/DominatorInternals.h" namespace llvm { @@ -41,15 +41,15 @@ class MachineDominatorTree : public MachineFunctionPass { public: static char ID; // Pass ID, replacement for typeid DominatorTreeBase<MachineBasicBlock>* DT; - + MachineDominatorTree(); - + ~MachineDominatorTree(); - + DominatorTreeBase<MachineBasicBlock>& getBase() { return *DT; } - + virtual void getAnalysisUsage(AnalysisUsage &AU) const; - + /// getRoots - Return the root blocks of the current CFG. This may include /// multiple blocks if we are computing post dominators. For forward /// dominators, this will always be a single block (the entry node). @@ -57,33 +57,35 @@ public: inline const std::vector<MachineBasicBlock*> &getRoots() const { return DT->getRoots(); } - + inline MachineBasicBlock *getRoot() const { return DT->getRoot(); } - + inline MachineDomTreeNode *getRootNode() const { return DT->getRootNode(); } - + virtual bool runOnMachineFunction(MachineFunction &F); - - inline bool dominates(MachineDomTreeNode* A, MachineDomTreeNode* B) const { + + inline bool dominates(const MachineDomTreeNode* A, + const MachineDomTreeNode* B) const { return DT->dominates(A, B); } - - inline bool dominates(MachineBasicBlock* A, MachineBasicBlock* B) const { + + inline bool dominates(const MachineBasicBlock* A, + const MachineBasicBlock* B) const { return DT->dominates(A, B); } - + // dominates - Return true if A dominates B. This performs the // special checks necessary if A and B are in the same basic block. - bool dominates(MachineInstr *A, MachineInstr *B) const { - MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); + bool dominates(const MachineInstr *A, const MachineInstr *B) const { + const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); if (BBA != BBB) return DT->dominates(BBA, BBB); // Loop through the basic block until we find A or B. - MachineBasicBlock::iterator I = BBA->begin(); + MachineBasicBlock::const_iterator I = BBA->begin(); for (; &*I != A && &*I != B; ++I) /*empty*/ ; @@ -95,43 +97,43 @@ public: // return &*I == B; //} } - + inline bool properlyDominates(const MachineDomTreeNode* A, - MachineDomTreeNode* B) const { + const MachineDomTreeNode* B) const { return DT->properlyDominates(A, B); } - - inline bool properlyDominates(MachineBasicBlock* A, - MachineBasicBlock* B) const { + + inline bool properlyDominates(const MachineBasicBlock* A, + const MachineBasicBlock* B) const { return DT->properlyDominates(A, B); } - + /// findNearestCommonDominator - Find nearest common dominator basic block /// for basic block A and B. If there is no such block then return NULL. inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B) { return DT->findNearestCommonDominator(A, B); } - + inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { return DT->getNode(BB); } - + /// getNode - return the (Post)DominatorTree node for the specified basic /// block. This is the same as using operator[] on this class. /// inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { return DT->getNode(BB); } - + /// addNewBlock - Add a new node to the dominator tree information. This - /// creates a new node as a child of DomBB dominator node,linking it into + /// creates a new node as a child of DomBB dominator node,linking it into /// the children list of the immediate dominator. inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB) { return DT->addNewBlock(BB, DomBB); } - + /// changeImmediateDominator - This method is used to update the dominator /// tree information when a node's immediate dominator changes. /// @@ -139,19 +141,19 @@ public: MachineBasicBlock* NewIDom) { DT->changeImmediateDominator(N, NewIDom); } - + inline void changeImmediateDominator(MachineDomTreeNode *N, MachineDomTreeNode* NewIDom) { DT->changeImmediateDominator(N, NewIDom); } - + /// eraseNode - Removes a node from the dominator tree. Block must not /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. inline void eraseNode(MachineBasicBlock *BB) { DT->eraseNode(BB); } - + /// splitBlock - BB is split and now it has one successor. Update dominator /// tree to reflect this change. inline void splitBlock(MachineBasicBlock* NewBB) { @@ -160,12 +162,12 @@ public: /// isReachableFromEntry - Return true if A is dominated by the entry /// block of the function containing it. - bool isReachableFromEntry(MachineBasicBlock *A) { + bool isReachableFromEntry(const MachineBasicBlock *A) { return DT->isReachableFromEntry(A); } virtual void releaseMemory(); - + virtual void print(raw_ostream &OS, const Module*) const; }; @@ -179,7 +181,7 @@ template<class T> struct GraphTraits; template <> struct GraphTraits<MachineDomTreeNode *> { typedef MachineDomTreeNode NodeType; typedef NodeType::iterator ChildIteratorType; - + static NodeType *getEntryNode(NodeType *N) { return N; } diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h index 0e4e132..cdec7e6 100644 --- a/include/llvm/CodeGen/MachineFrameInfo.h +++ b/include/llvm/CodeGen/MachineFrameInfo.h @@ -221,8 +221,11 @@ class MachineFrameInfo { /// just allocate them normally. bool UseLocalStackAllocationBlock; + /// Whether the "realign-stack" option is on. + bool RealignOption; public: - explicit MachineFrameInfo(const TargetFrameLowering &tfi) : TFI(tfi) { + explicit MachineFrameInfo(const TargetFrameLowering &tfi, bool RealignOpt) + : TFI(tfi), RealignOption(RealignOpt) { StackSize = NumFixedObjects = OffsetAdjustment = MaxAlignment = 0; HasVarSizedObjects = false; FrameAddressTaken = false; @@ -416,6 +419,9 @@ public: /// void setStackSize(uint64_t Size) { StackSize = Size; } + /// Estimate and return the size of the stack frame. + unsigned estimateStackSize(const MachineFunction &MF) const; + /// getOffsetAdjustment - Return the correction for frame offsets. /// int getOffsetAdjustment() const { return OffsetAdjustment; } @@ -432,9 +438,7 @@ public: /// ensureMaxAlignment - Make sure the function is at least Align bytes /// aligned. - void ensureMaxAlignment(unsigned Align) { - if (MaxAlignment < Align) MaxAlignment = Align; - } + void ensureMaxAlignment(unsigned Align); /// AdjustsStack - Return true if this function adjusts the stack -- e.g., /// when calling another function. This is only valid during and after @@ -496,26 +500,13 @@ public: /// a nonnegative identifier to represent it. /// int CreateStackObject(uint64_t Size, unsigned Alignment, bool isSS, - bool MayNeedSP = false, const AllocaInst *Alloca = 0) { - assert(Size != 0 && "Cannot allocate zero size stack objects!"); - Objects.push_back(StackObject(Size, Alignment, 0, false, isSS, MayNeedSP, - Alloca)); - int Index = (int)Objects.size() - NumFixedObjects - 1; - assert(Index >= 0 && "Bad frame index!"); - ensureMaxAlignment(Alignment); - return Index; - } + bool MayNeedSP = false, const AllocaInst *Alloca = 0); /// CreateSpillStackObject - Create a new statically sized stack object that /// represents a spill slot, returning a nonnegative identifier to represent /// it. /// - int CreateSpillStackObject(uint64_t Size, unsigned Alignment) { - CreateStackObject(Size, Alignment, true, false); - int Index = (int)Objects.size() - NumFixedObjects - 1; - ensureMaxAlignment(Alignment); - return Index; - } + int CreateSpillStackObject(uint64_t Size, unsigned Alignment); /// RemoveStackObject - Remove or mark dead a statically sized stack object. /// @@ -529,12 +520,7 @@ public: /// variable sized object is created, whether or not the index returned is /// actually used. /// - int CreateVariableSizedObject(unsigned Alignment) { - HasVarSizedObjects = true; - Objects.push_back(StackObject(0, Alignment, 0, false, false, true, 0)); - ensureMaxAlignment(Alignment); - return (int)Objects.size()-NumFixedObjects-1; - } + int CreateVariableSizedObject(unsigned Alignment); /// getCalleeSavedInfo - Returns a reference to call saved info vector for the /// current function. diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h index 025e18a..82c4cd6 100644 --- a/include/llvm/CodeGen/MachineFunction.h +++ b/include/llvm/CodeGen/MachineFunction.h @@ -18,10 +18,11 @@ #ifndef LLVM_CODEGEN_MACHINEFUNCTION_H #define LLVM_CODEGEN_MACHINEFUNCTION_H -#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/ADT/ilist.h" -#include "llvm/Support/DebugLoc.h" +#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/ArrayRecycler.h" +#include "llvm/Support/DebugLoc.h" #include "llvm/Support/Recycler.h" namespace llvm { @@ -105,6 +106,9 @@ class MachineFunction { // Allocation management for instructions in function. Recycler<MachineInstr> InstructionRecycler; + // Allocation management for operand arrays on instructions. + ArrayRecycler<MachineOperand> OperandRecycler; + // Allocation management for basic blocks in function. Recycler<MachineBasicBlock> BasicBlockRecycler; @@ -127,6 +131,9 @@ class MachineFunction { /// about the control flow of such functions. bool ExposesReturnsTwice; + /// True if the function includes MS-style inline assembly. + bool HasMSInlineAsm; + MachineFunction(const MachineFunction &) LLVM_DELETED_FUNCTION; void operator=(const MachineFunction&) LLVM_DELETED_FUNCTION; public: @@ -210,6 +217,17 @@ public: void setExposesReturnsTwice(bool B) { ExposesReturnsTwice = B; } + + /// Returns true if the function contains any MS-style inline assembly. + bool hasMSInlineAsm() const { + return HasMSInlineAsm; + } + + /// Set a flag that indicates that the function contains MS-style inline + /// assembly. + void setHasMSInlineAsm(bool B) { + HasMSInlineAsm = B; + } /// getInfo - Keep track of various per-function pieces of information for /// backends that would like to do so. @@ -394,6 +412,21 @@ public: MachineMemOperand *getMachineMemOperand(const MachineMemOperand *MMO, int64_t Offset, uint64_t Size); + typedef ArrayRecycler<MachineOperand>::Capacity OperandCapacity; + + /// Allocate an array of MachineOperands. This is only intended for use by + /// internal MachineInstr functions. + MachineOperand *allocateOperandArray(OperandCapacity Cap) { + return OperandRecycler.allocate(Cap, Allocator); + } + + /// Dellocate an array of MachineOperands and recycle the memory. This is + /// only intended for use by internal MachineInstr functions. + /// Cap must be the same capacity that was used to allocate the array. + void deallocateOperandArray(OperandCapacity Cap, MachineOperand *Array) { + OperandRecycler.deallocate(Cap, Array); + } + /// allocateMemRefsArray - Allocate an array to hold MachineMemOperand /// pointers. This array is owned by the MachineFunction. MachineInstr::mmo_iterator allocateMemRefsArray(unsigned long Num); diff --git a/include/llvm/CodeGen/MachineFunctionAnalysis.h b/include/llvm/CodeGen/MachineFunctionAnalysis.h index 50ea206..112f07e 100644 --- a/include/llvm/CodeGen/MachineFunctionAnalysis.h +++ b/include/llvm/CodeGen/MachineFunctionAnalysis.h @@ -11,15 +11,15 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_MACHINE_FUNCTION_ANALYSIS_H -#define LLVM_CODEGEN_MACHINE_FUNCTION_ANALYSIS_H +#ifndef LLVM_CODEGEN_MACHINEFUNCTIONANALYSIS_H +#define LLVM_CODEGEN_MACHINEFUNCTIONANALYSIS_H #include "llvm/Pass.h" -#include "llvm/Target/TargetMachine.h" namespace llvm { class MachineFunction; +class TargetMachine; /// MachineFunctionAnalysis - This class is a Pass that manages a /// MachineFunction object. diff --git a/include/llvm/CodeGen/MachineFunctionPass.h b/include/llvm/CodeGen/MachineFunctionPass.h index b7bf0a3..04881e5 100644 --- a/include/llvm/CodeGen/MachineFunctionPass.h +++ b/include/llvm/CodeGen/MachineFunctionPass.h @@ -16,8 +16,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_MACHINE_FUNCTION_PASS_H -#define LLVM_CODEGEN_MACHINE_FUNCTION_PASS_H +#ifndef LLVM_CODEGEN_MACHINEFUNCTIONPASS_H +#define LLVM_CODEGEN_MACHINEFUNCTIONPASS_H #include "llvm/Pass.h" diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index 7eb03a9..195cce7 100644 --- a/include/llvm/CodeGen/MachineInstr.h +++ b/include/llvm/CodeGen/MachineInstr.h @@ -16,17 +16,18 @@ #ifndef LLVM_CODEGEN_MACHINEINSTR_H #define LLVM_CODEGEN_MACHINEINSTR_H -#include "llvm/CodeGen/MachineOperand.h" -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/Target/TargetOpcodes.h" #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/ilist.h" -#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/StringRef.h" -#include "llvm/ADT/DenseMapInfo.h" -#include "llvm/InlineAsm.h" +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/IR/InlineAsm.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/Support/ArrayRecycler.h" #include "llvm/Support/DebugLoc.h" +#include "llvm/Target/TargetOpcodes.h" #include <vector> namespace llvm { @@ -42,6 +43,10 @@ class MachineMemOperand; //===----------------------------------------------------------------------===// /// MachineInstr - Representation of each machine instruction. /// +/// This class isn't a POD type, but it must have a trivial destructor. When a +/// MachineFunction is deleted, all the contained MachineInstrs are deallocated +/// without having their destructor called. +/// class MachineInstr : public ilist_node<MachineInstr> { public: typedef MachineMemOperand **mmo_iterator; @@ -58,11 +63,18 @@ public: NoFlags = 0, FrameSetup = 1 << 0, // Instruction is used as a part of // function frame setup code. - InsideBundle = 1 << 1 // Instruction is inside a bundle (not - // the first MI in a bundle) + BundledPred = 1 << 1, // Instruction has bundled predecessors. + BundledSucc = 1 << 2 // Instruction has bundled successors. }; private: const MCInstrDesc *MCID; // Instruction descriptor. + MachineBasicBlock *Parent; // Pointer to the owning basic block. + + // Operands are allocated by an ArrayRecycler. + MachineOperand *Operands; // Pointer to the first operand. + unsigned NumOperands; // Number of operands on instruction. + typedef ArrayRecycler<MachineOperand>::Capacity OperandCapacity; + OperandCapacity CapOperands; // Capacity of the Operands array. uint8_t Flags; // Various bits of additional // information about machine @@ -75,15 +87,15 @@ private: // anything other than to convey comment // information to AsmPrinter. - uint16_t NumMemRefs; // information on memory references + uint8_t NumMemRefs; // Information on memory references. mmo_iterator MemRefs; - std::vector<MachineOperand> Operands; // the operands - MachineBasicBlock *Parent; // Pointer to the owning basic block. DebugLoc debugLoc; // Source line information. MachineInstr(const MachineInstr&) LLVM_DELETED_FUNCTION; void operator=(const MachineInstr&) LLVM_DELETED_FUNCTION; + // Use MachineFunction::DeleteMachineInstr() instead. + ~MachineInstr() LLVM_DELETED_FUNCTION; // Intrusive list support friend struct ilist_traits<MachineInstr>; @@ -94,22 +106,11 @@ private: /// MachineInstr in the given MachineFunction. MachineInstr(MachineFunction &, const MachineInstr &); - /// MachineInstr ctor - This constructor creates a dummy MachineInstr with - /// MCID NULL and no operands. - MachineInstr(); - /// MachineInstr ctor - This constructor create a MachineInstr and add the /// implicit operands. It reserves space for number of operands specified by /// MCInstrDesc. An explicit DebugLoc is supplied. - MachineInstr(const MCInstrDesc &MCID, const DebugLoc dl, bool NoImp = false); - - /// MachineInstr ctor - Work exactly the same as the ctor above, except that - /// the MachineInstr is created and added to the end of the specified basic - /// block. - MachineInstr(MachineBasicBlock *MBB, const DebugLoc dl, - const MCInstrDesc &MCID); - - ~MachineInstr(); + MachineInstr(MachineFunction&, const MCInstrDesc &MCID, + const DebugLoc dl, bool NoImp = false); // MachineInstrs are pool-allocated and owned by MachineFunction. friend class MachineFunction; @@ -160,7 +161,9 @@ public: } void setFlags(unsigned flags) { - Flags = flags; + // Filter out the automatically maintained flags. + unsigned Mask = BundledPred | BundledSucc; + Flags = (Flags & Mask) | (flags & ~Mask); } /// clearFlag - Clear a MI flag. @@ -205,21 +208,36 @@ public: /// The first instruction has the special opcode "BUNDLE". It's not "inside" /// a bundle, but the next three MIs are. bool isInsideBundle() const { - return getFlag(InsideBundle); - } - - /// setIsInsideBundle - Set InsideBundle bit. - /// - void setIsInsideBundle(bool Val = true) { - if (Val) - setFlag(InsideBundle); - else - clearFlag(InsideBundle); + return getFlag(BundledPred); } /// isBundled - Return true if this instruction part of a bundle. This is true /// if either itself or its following instruction is marked "InsideBundle". - bool isBundled() const; + bool isBundled() const { + return isBundledWithPred() || isBundledWithSucc(); + } + + /// Return true if this instruction is part of a bundle, and it is not the + /// first instruction in the bundle. + bool isBundledWithPred() const { return getFlag(BundledPred); } + + /// Return true if this instruction is part of a bundle, and it is not the + /// last instruction in the bundle. + bool isBundledWithSucc() const { return getFlag(BundledSucc); } + + /// Bundle this instruction with its predecessor. This can be an unbundled + /// instruction, or it can be the first instruction in a bundle. + void bundleWithPred(); + + /// Bundle this instruction with its successor. This can be an unbundled + /// instruction, or it can be the last instruction in a bundle. + void bundleWithSucc(); + + /// Break bundle above this instruction. + void unbundleFromPred(); + + /// Break bundle below this instruction. + void unbundleFromSucc(); /// getDebugLoc - Returns the debug location id of this MachineInstr. /// @@ -244,7 +262,7 @@ public: /// Access to explicit operands of the instruction. /// - unsigned getNumOperands() const { return (unsigned)Operands.size(); } + unsigned getNumOperands() const { return NumOperands; } const MachineOperand& getOperand(unsigned i) const { assert(i < getNumOperands() && "getOperand() out of range!"); @@ -260,14 +278,14 @@ public: unsigned getNumExplicitOperands() const; /// iterator/begin/end - Iterate over all operands of a machine instruction. - typedef std::vector<MachineOperand>::iterator mop_iterator; - typedef std::vector<MachineOperand>::const_iterator const_mop_iterator; + typedef MachineOperand *mop_iterator; + typedef const MachineOperand *const_mop_iterator; - mop_iterator operands_begin() { return Operands.begin(); } - mop_iterator operands_end() { return Operands.end(); } + mop_iterator operands_begin() { return Operands; } + mop_iterator operands_end() { return Operands + NumOperands; } - const_mop_iterator operands_begin() const { return Operands.begin(); } - const_mop_iterator operands_end() const { return Operands.end(); } + const_mop_iterator operands_begin() const { return Operands; } + const_mop_iterator operands_end() const { return Operands + NumOperands; } /// Access to memory operands of the instruction mmo_iterator memoperands_begin() const { return MemRefs; } @@ -295,11 +313,11 @@ public: /// The second argument indicates whether the query should look inside /// instruction bundles. bool hasProperty(unsigned MCFlag, QueryType Type = AnyInBundle) const { - // Inline the fast path. - if (Type == IgnoreBundle || !isBundle()) + // Inline the fast path for unbundled or bundle-internal instructions. + if (Type == IgnoreBundle || !isBundled() || isBundledWithPred()) return getDesc().getFlags() & (1 << MCFlag); - // If we have a bundle, take the slow path. + // If this is the first instruction in a bundle, take the slow path. return hasPropertyInBundle(1 << MCFlag, Type); } @@ -578,14 +596,33 @@ public: bool isIdenticalTo(const MachineInstr *Other, MICheckType Check = CheckDefs) const; - /// removeFromParent - This method unlinks 'this' from the containing basic - /// block, and returns it, but does not delete it. + /// Unlink 'this' from the containing basic block, and return it without + /// deleting it. + /// + /// This function can not be used on bundled instructions, use + /// removeFromBundle() to remove individual instructions from a bundle. MachineInstr *removeFromParent(); - /// eraseFromParent - This method unlinks 'this' from the containing basic - /// block and deletes it. + /// Unlink this instruction from its basic block and return it without + /// deleting it. + /// + /// If the instruction is part of a bundle, the other instructions in the + /// bundle remain bundled. + MachineInstr *removeFromBundle(); + + /// Unlink 'this' from the containing basic block and delete it. + /// + /// If this instruction is the header of a bundle, the whole bundle is erased. + /// This function can not be used for instructions inside a bundle, use + /// eraseFromBundle() to erase individual bundled instructions. void eraseFromParent(); + /// Unlink 'this' form its basic block and delete it. + /// + /// If the instruction is part of a bundle, the other instructions in the + /// bundle remain bundled. + void eraseFromBundle(); + /// isLabel - Returns true if the MachineInstr represents a label. /// bool isLabel() const { @@ -605,6 +642,9 @@ public: bool isKill() const { return getOpcode() == TargetOpcode::KILL; } bool isImplicitDef() const { return getOpcode()==TargetOpcode::IMPLICIT_DEF; } bool isInlineAsm() const { return getOpcode() == TargetOpcode::INLINEASM; } + bool isMSInlineAsm() const { + return getOpcode() == TargetOpcode::INLINEASM && getInlineAsmDialect(); + } bool isStackAligningInlineAsm() const; InlineAsm::AsmDialect getInlineAsmDialect() const; bool isInsertSubreg() const { @@ -662,7 +702,11 @@ public: } } - /// getBundleSize - Return the number of instructions inside the MI bundle. + /// Return the number of instructions inside the MI bundle, excluding the + /// bundle header. + /// + /// This is the number of instructions that MachineBasicBlock::iterator + /// skips, 0 for unbundled instructions. unsigned getBundleSize() const; /// readsRegister - Return true if the MachineInstr reads the specified @@ -821,13 +865,6 @@ public: /// void clearKillInfo(); - /// copyKillDeadInfo - Copies kill / dead operand properties from MI. - /// - void copyKillDeadInfo(const MachineInstr *MI); - - /// copyPredicates - Copies predicate operand(s) from MI. - void copyPredicates(const MachineInstr *MI); - /// substituteRegister - Replace all occurrences of FromReg with ToReg:SubIdx, /// properly composing subreg indices where necessary. void substituteRegister(unsigned FromReg, unsigned ToReg, unsigned SubIdx, @@ -909,21 +946,35 @@ public: /// copyImplicitOps - Copy implicit register operands from specified /// instruction to this instruction. - void copyImplicitOps(const MachineInstr *MI); + void copyImplicitOps(MachineFunction &MF, const MachineInstr *MI); // // Debugging support // - void print(raw_ostream &OS, const TargetMachine *TM = 0) const; + void print(raw_ostream &OS, const TargetMachine *TM = 0, + bool SkipOpers = false) const; void dump() const; //===--------------------------------------------------------------------===// // Accessors used to build up machine instructions. - /// addOperand - Add the specified operand to the instruction. If it is an - /// implicit operand, it is added to the end of the operand list. If it is - /// an explicit operand it is added at the end of the explicit operand list + /// Add the specified operand to the instruction. If it is an implicit + /// operand, it is added to the end of the operand list. If it is an + /// explicit operand it is added at the end of the explicit operand list /// (before the first implicit operand). + /// + /// MF must be the machine function that was used to allocate this + /// instruction. + /// + /// MachineInstrBuilder provides a more convenient interface for creating + /// instructions and adding operands. + void addOperand(MachineFunction &MF, const MachineOperand &Op); + + /// Add an operand without providing an MF reference. This only works for + /// instructions that are inserted in a basic block. + /// + /// MachineInstrBuilder and the two-argument addOperand(MF, MO) should be + /// preferred. void addOperand(const MachineOperand &Op); /// setDesc - Replace the instruction descriptor (thus opcode) of @@ -950,7 +1001,8 @@ public: /// list. This does not transfer ownership. void setMemRefs(mmo_iterator NewMemRefs, mmo_iterator NewMemRefsEnd) { MemRefs = NewMemRefs; - NumMemRefs = NewMemRefsEnd - NewMemRefs; + NumMemRefs = uint8_t(NewMemRefsEnd - NewMemRefs); + assert(NumMemRefs == NewMemRefsEnd - NewMemRefs && "Too many memrefs"); } private: @@ -970,7 +1022,7 @@ private: /// addImplicitDefUseOperands - Add all implicit def and use operands to /// this instruction. - void addImplicitDefUseOperands(); + void addImplicitDefUseOperands(MachineFunction &MF); /// RemoveRegOperandsFromUseLists - Unlink all of the register operands in /// this instruction from their respective use lists. This requires that the diff --git a/include/llvm/CodeGen/MachineInstrBuilder.h b/include/llvm/CodeGen/MachineInstrBuilder.h index 7706853..92c8da9 100644 --- a/include/llvm/CodeGen/MachineInstrBuilder.h +++ b/include/llvm/CodeGen/MachineInstrBuilder.h @@ -18,6 +18,7 @@ #define LLVM_CODEGEN_MACHINEINSTRBUILDER_H #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstrBundle.h" #include "llvm/Support/ErrorHandling.h" namespace llvm { @@ -42,10 +43,14 @@ namespace RegState { } class MachineInstrBuilder { + MachineFunction *MF; MachineInstr *MI; public: - MachineInstrBuilder() : MI(0) {} - explicit MachineInstrBuilder(MachineInstr *mi) : MI(mi) {} + MachineInstrBuilder() : MF(0), MI(0) {} + + /// Create a MachineInstrBuilder for manipulating an existing instruction. + /// F must be the machine function that was used to allocate I. + MachineInstrBuilder(MachineFunction &F, MachineInstr *I) : MF(&F), MI(I) {} /// Allow automatic conversion to the machine instruction we are working on. /// @@ -60,86 +65,94 @@ public: unsigned SubReg = 0) const { assert((flags & 0x1) == 0 && "Passing in 'true' to addReg is forbidden! Use enums instead."); - MI->addOperand(MachineOperand::CreateReg(RegNo, - flags & RegState::Define, - flags & RegState::Implicit, - flags & RegState::Kill, - flags & RegState::Dead, - flags & RegState::Undef, - flags & RegState::EarlyClobber, - SubReg, - flags & RegState::Debug, - flags & RegState::InternalRead)); + MI->addOperand(*MF, MachineOperand::CreateReg(RegNo, + flags & RegState::Define, + flags & RegState::Implicit, + flags & RegState::Kill, + flags & RegState::Dead, + flags & RegState::Undef, + flags & RegState::EarlyClobber, + SubReg, + flags & RegState::Debug, + flags & RegState::InternalRead)); return *this; } /// addImm - Add a new immediate operand. /// const MachineInstrBuilder &addImm(int64_t Val) const { - MI->addOperand(MachineOperand::CreateImm(Val)); + MI->addOperand(*MF, MachineOperand::CreateImm(Val)); return *this; } const MachineInstrBuilder &addCImm(const ConstantInt *Val) const { - MI->addOperand(MachineOperand::CreateCImm(Val)); + MI->addOperand(*MF, MachineOperand::CreateCImm(Val)); return *this; } const MachineInstrBuilder &addFPImm(const ConstantFP *Val) const { - MI->addOperand(MachineOperand::CreateFPImm(Val)); + MI->addOperand(*MF, MachineOperand::CreateFPImm(Val)); return *this; } const MachineInstrBuilder &addMBB(MachineBasicBlock *MBB, unsigned char TargetFlags = 0) const { - MI->addOperand(MachineOperand::CreateMBB(MBB, TargetFlags)); + MI->addOperand(*MF, MachineOperand::CreateMBB(MBB, TargetFlags)); return *this; } const MachineInstrBuilder &addFrameIndex(int Idx) const { - MI->addOperand(MachineOperand::CreateFI(Idx)); + MI->addOperand(*MF, MachineOperand::CreateFI(Idx)); return *this; } const MachineInstrBuilder &addConstantPoolIndex(unsigned Idx, int Offset = 0, unsigned char TargetFlags = 0) const { - MI->addOperand(MachineOperand::CreateCPI(Idx, Offset, TargetFlags)); + MI->addOperand(*MF, MachineOperand::CreateCPI(Idx, Offset, TargetFlags)); return *this; } const MachineInstrBuilder &addTargetIndex(unsigned Idx, int64_t Offset = 0, unsigned char TargetFlags = 0) const { - MI->addOperand(MachineOperand::CreateTargetIndex(Idx, Offset, TargetFlags)); + MI->addOperand(*MF, MachineOperand::CreateTargetIndex(Idx, Offset, + TargetFlags)); return *this; } const MachineInstrBuilder &addJumpTableIndex(unsigned Idx, unsigned char TargetFlags = 0) const { - MI->addOperand(MachineOperand::CreateJTI(Idx, TargetFlags)); + MI->addOperand(*MF, MachineOperand::CreateJTI(Idx, TargetFlags)); return *this; } const MachineInstrBuilder &addGlobalAddress(const GlobalValue *GV, int64_t Offset = 0, unsigned char TargetFlags = 0) const { - MI->addOperand(MachineOperand::CreateGA(GV, Offset, TargetFlags)); + MI->addOperand(*MF, MachineOperand::CreateGA(GV, Offset, TargetFlags)); return *this; } const MachineInstrBuilder &addExternalSymbol(const char *FnName, unsigned char TargetFlags = 0) const { - MI->addOperand(MachineOperand::CreateES(FnName, TargetFlags)); + MI->addOperand(*MF, MachineOperand::CreateES(FnName, TargetFlags)); + return *this; + } + + const MachineInstrBuilder &addBlockAddress(const BlockAddress *BA, + int64_t Offset = 0, + unsigned char TargetFlags = 0) const { + MI->addOperand(*MF, MachineOperand::CreateBA(BA, Offset, TargetFlags)); return *this; } const MachineInstrBuilder &addRegMask(const uint32_t *Mask) const { - MI->addOperand(MachineOperand::CreateRegMask(Mask)); + MI->addOperand(*MF, MachineOperand::CreateRegMask(Mask)); return *this; } const MachineInstrBuilder &addMemOperand(MachineMemOperand *MMO) const { - MI->addMemOperand(*MI->getParent()->getParent(), MMO); + MI->addMemOperand(*MF, MMO); return *this; } @@ -151,17 +164,17 @@ public: const MachineInstrBuilder &addOperand(const MachineOperand &MO) const { - MI->addOperand(MO); + MI->addOperand(*MF, MO); return *this; } const MachineInstrBuilder &addMetadata(const MDNode *MD) const { - MI->addOperand(MachineOperand::CreateMetadata(MD)); + MI->addOperand(*MF, MachineOperand::CreateMetadata(MD)); return *this; } const MachineInstrBuilder &addSym(MCSymbol *Sym) const { - MI->addOperand(MachineOperand::CreateMCSymbol(Sym)); + MI->addOperand(*MF, MachineOperand::CreateMCSymbol(Sym)); return *this; } @@ -196,6 +209,12 @@ public: } } } + + /// Copy all the implicit operands from OtherMI onto this one. + const MachineInstrBuilder ©ImplicitOps(const MachineInstr *OtherMI) { + MI->copyImplicitOps(*MF, OtherMI); + return *this; + } }; /// BuildMI - Builder interface. Specify how to create the initial instruction @@ -204,7 +223,7 @@ public: inline MachineInstrBuilder BuildMI(MachineFunction &MF, DebugLoc DL, const MCInstrDesc &MCID) { - return MachineInstrBuilder(MF.CreateMachineInstr(MCID, DL)); + return MachineInstrBuilder(MF, MF.CreateMachineInstr(MCID, DL)); } /// BuildMI - This version of the builder sets up the first operand as a @@ -214,7 +233,7 @@ inline MachineInstrBuilder BuildMI(MachineFunction &MF, DebugLoc DL, const MCInstrDesc &MCID, unsigned DestReg) { - return MachineInstrBuilder(MF.CreateMachineInstr(MCID, DL)) + return MachineInstrBuilder(MF, MF.CreateMachineInstr(MCID, DL)) .addReg(DestReg, RegState::Define); } @@ -227,9 +246,10 @@ inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB, DebugLoc DL, const MCInstrDesc &MCID, unsigned DestReg) { - MachineInstr *MI = BB.getParent()->CreateMachineInstr(MCID, DL); + MachineFunction &MF = *BB.getParent(); + MachineInstr *MI = MF.CreateMachineInstr(MCID, DL); BB.insert(I, MI); - return MachineInstrBuilder(MI).addReg(DestReg, RegState::Define); + return MachineInstrBuilder(MF, MI).addReg(DestReg, RegState::Define); } inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB, @@ -237,9 +257,10 @@ inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB, DebugLoc DL, const MCInstrDesc &MCID, unsigned DestReg) { - MachineInstr *MI = BB.getParent()->CreateMachineInstr(MCID, DL); + MachineFunction &MF = *BB.getParent(); + MachineInstr *MI = MF.CreateMachineInstr(MCID, DL); BB.insert(I, MI); - return MachineInstrBuilder(MI).addReg(DestReg, RegState::Define); + return MachineInstrBuilder(MF, MI).addReg(DestReg, RegState::Define); } inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB, @@ -264,18 +285,20 @@ inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB, MachineBasicBlock::iterator I, DebugLoc DL, const MCInstrDesc &MCID) { - MachineInstr *MI = BB.getParent()->CreateMachineInstr(MCID, DL); + MachineFunction &MF = *BB.getParent(); + MachineInstr *MI = MF.CreateMachineInstr(MCID, DL); BB.insert(I, MI); - return MachineInstrBuilder(MI); + return MachineInstrBuilder(MF, MI); } inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB, MachineBasicBlock::instr_iterator I, DebugLoc DL, const MCInstrDesc &MCID) { - MachineInstr *MI = BB.getParent()->CreateMachineInstr(MCID, DL); + MachineFunction &MF = *BB.getParent(); + MachineInstr *MI = MF.CreateMachineInstr(MCID, DL); BB.insert(I, MI); - return MachineInstrBuilder(MI); + return MachineInstrBuilder(MF, MI); } inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB, @@ -330,6 +353,94 @@ inline unsigned getUndefRegState(bool B) { inline unsigned getInternalReadRegState(bool B) { return B ? RegState::InternalRead : 0; } +inline unsigned getDebugRegState(bool B) { + return B ? RegState::Debug : 0; +} + + +/// Helper class for constructing bundles of MachineInstrs. +/// +/// MIBundleBuilder can create a bundle from scratch by inserting new +/// MachineInstrs one at a time, or it can create a bundle from a sequence of +/// existing MachineInstrs in a basic block. +class MIBundleBuilder { + MachineBasicBlock &MBB; + MachineBasicBlock::instr_iterator Begin; + MachineBasicBlock::instr_iterator End; + +public: + /// Create an MIBundleBuilder that inserts instructions into a new bundle in + /// BB above the bundle or instruction at Pos. + MIBundleBuilder(MachineBasicBlock &BB, + MachineBasicBlock::iterator Pos) + : MBB(BB), Begin(Pos.getInstrIterator()), End(Begin) {} + + /// Create a bundle from the sequence of instructions between B and E. + MIBundleBuilder(MachineBasicBlock &BB, + MachineBasicBlock::iterator B, + MachineBasicBlock::iterator E) + : MBB(BB), Begin(B.getInstrIterator()), End(E.getInstrIterator()) { + assert(B != E && "No instructions to bundle"); + ++B; + while (B != E) { + MachineInstr *MI = B; + ++B; + MI->bundleWithPred(); + } + } + + /// Create an MIBundleBuilder representing an existing instruction or bundle + /// that has MI as its head. + explicit MIBundleBuilder(MachineInstr *MI) + : MBB(*MI->getParent()), Begin(MI), End(getBundleEnd(MI)) {} + + /// Return a reference to the basic block containing this bundle. + MachineBasicBlock &getMBB() const { return MBB; } + + /// Return true if no instructions have been inserted in this bundle yet. + /// Empty bundles aren't representable in a MachineBasicBlock. + bool empty() const { return Begin == End; } + + /// Return an iterator to the first bundled instruction. + MachineBasicBlock::instr_iterator begin() const { return Begin; } + + /// Return an iterator beyond the last bundled instruction. + MachineBasicBlock::instr_iterator end() const { return End; } + + /// Insert MI into this bundle before I which must point to an instruction in + /// the bundle, or end(). + MIBundleBuilder &insert(MachineBasicBlock::instr_iterator I, + MachineInstr *MI) { + MBB.insert(I, MI); + if (I == Begin) { + if (!empty()) + MI->bundleWithSucc(); + Begin = MI; + return *this; + } + if (I == End) { + MI->bundleWithPred(); + return *this; + } + // MI was inserted in the middle of the bundle, so its neighbors' flags are + // already fine. Update MI's bundle flags manually. + MI->setFlag(MachineInstr::BundledPred); + MI->setFlag(MachineInstr::BundledSucc); + return *this; + } + + /// Insert MI into MBB by prepending it to the instructions in the bundle. + /// MI will become the first instruction in the bundle. + MIBundleBuilder &prepend(MachineInstr *MI) { + return insert(begin(), MI); + } + + /// Insert MI into MBB by appending it to the instructions in the bundle. + /// MI will become the last instruction in the bundle. + MIBundleBuilder &append(MachineInstr *MI) { + return insert(end(), MI); + } +}; } // End llvm namespace diff --git a/include/llvm/CodeGen/MachineInstrBundle.h b/include/llvm/CodeGen/MachineInstrBundle.h index 854ba06..9519edb 100644 --- a/include/llvm/CodeGen/MachineInstrBundle.h +++ b/include/llvm/CodeGen/MachineInstrBundle.h @@ -45,18 +45,36 @@ bool finalizeBundles(MachineFunction &MF); /// inline MachineInstr *getBundleStart(MachineInstr *MI) { MachineBasicBlock::instr_iterator I = MI; - while (I->isInsideBundle()) + while (I->isBundledWithPred()) --I; return I; } inline const MachineInstr *getBundleStart(const MachineInstr *MI) { MachineBasicBlock::const_instr_iterator I = MI; - while (I->isInsideBundle()) + while (I->isBundledWithPred()) --I; return I; } +/// Return an iterator pointing beyond the bundle containing MI. +inline MachineBasicBlock::instr_iterator +getBundleEnd(MachineInstr *MI) { + MachineBasicBlock::instr_iterator I = MI; + while (I->isBundledWithSucc()) + ++I; + return ++I; +} + +/// Return an iterator pointing beyond the bundle containing MI. +inline MachineBasicBlock::const_instr_iterator +getBundleEnd(const MachineInstr *MI) { + MachineBasicBlock::const_instr_iterator I = MI; + while (I->isBundledWithSucc()) + ++I; + return ++I; +} + //===----------------------------------------------------------------------===// // MachineOperand iterator // @@ -149,16 +167,13 @@ public: /// PhysRegInfo - Information about a physical register used by a set of /// operands. struct PhysRegInfo { - /// Clobbers - Reg or an overlapping register is defined, or a regmask + /// Clobbers - Reg or an overlapping register is defined, or a regmask /// clobbers Reg. bool Clobbers; /// Defines - Reg or a super-register is defined. bool Defines; - /// DefinesOverlap - Reg or an overlapping register is defined. - bool DefinesOverlap; - /// Reads - Read or a super-register is read. bool Reads; diff --git a/include/llvm/CodeGen/MachineJumpTableInfo.h b/include/llvm/CodeGen/MachineJumpTableInfo.h index 928145d..adcd1d0 100644 --- a/include/llvm/CodeGen/MachineJumpTableInfo.h +++ b/include/llvm/CodeGen/MachineJumpTableInfo.h @@ -20,8 +20,8 @@ #ifndef LLVM_CODEGEN_MACHINEJUMPTABLEINFO_H #define LLVM_CODEGEN_MACHINEJUMPTABLEINFO_H -#include <vector> #include <cassert> +#include <vector> namespace llvm { diff --git a/include/llvm/CodeGen/MachineLoopInfo.h b/include/llvm/CodeGen/MachineLoopInfo.h index d53f041..b058ecb 100644 --- a/include/llvm/CodeGen/MachineLoopInfo.h +++ b/include/llvm/CodeGen/MachineLoopInfo.h @@ -27,11 +27,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_MACHINE_LOOP_INFO_H -#define LLVM_CODEGEN_MACHINE_LOOP_INFO_H +#ifndef LLVM_CODEGEN_MACHINELOOPINFO_H +#define LLVM_CODEGEN_MACHINELOOPINFO_H -#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/CodeGen/MachineFunctionPass.h" namespace llvm { diff --git a/include/llvm/CodeGen/MachineLoopRanges.h b/include/llvm/CodeGen/MachineLoopRanges.h deleted file mode 100644 index 6a30e8b..0000000 --- a/include/llvm/CodeGen/MachineLoopRanges.h +++ /dev/null @@ -1,112 +0,0 @@ -//===- 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/MachineModuleInfo.h b/include/llvm/CodeGen/MachineModuleInfo.h index 6b88d4a..a3acec8 100644 --- a/include/llvm/CodeGen/MachineModuleInfo.h +++ b/include/llvm/CodeGen/MachineModuleInfo.h @@ -31,19 +31,18 @@ #ifndef LLVM_CODEGEN_MACHINEMODULEINFO_H #define LLVM_CODEGEN_MACHINEMODULEINFO_H -#include "llvm/Pass.h" -#include "llvm/GlobalValue.h" -#include "llvm/Metadata.h" -#include "llvm/MC/MachineLocation.h" -#include "llvm/MC/MCContext.h" -#include "llvm/Support/Dwarf.h" -#include "llvm/Support/DebugLoc.h" -#include "llvm/Support/ValueHandle.h" -#include "llvm/Support/DataTypes.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/IR/Metadata.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MachineLocation.h" +#include "llvm/Pass.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/DebugLoc.h" +#include "llvm/Support/Dwarf.h" +#include "llvm/Support/ValueHandle.h" namespace llvm { @@ -180,8 +179,9 @@ public: const MCObjectFileInfo *MOFI); ~MachineModuleInfo(); - bool doInitialization(); - bool doFinalization(); + // Initialization and Finalization + virtual bool doInitialization(Module &); + virtual bool doFinalization(Module &); /// EndFunction - Discard function meta information. /// @@ -295,7 +295,7 @@ public: /// isUsedFunction - Return true if the functions in the llvm.used list. This /// does not return true for things in llvm.compiler.used unless they are also /// in llvm.used. - bool isUsedFunction(const Function *F) { + bool isUsedFunction(const Function *F) const { return UsedFunctions.count(F); } @@ -372,7 +372,7 @@ public: /// getCurrentCallSite - Get the call site currently being processed, if any. /// return zero if none. - unsigned getCurrentCallSite(void) { return CurCallSite; } + unsigned getCurrentCallSite() { return CurCallSite; } /// getTypeInfos - Return a reference to the C++ typeinfo for the current /// function. diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h index 606833c..414770b 100644 --- a/include/llvm/CodeGen/MachineOperand.h +++ b/include/llvm/CodeGen/MachineOperand.h @@ -35,6 +35,11 @@ class MCSymbol; /// MachineOperand class - Representation of each machine instruction operand. /// +/// This class isn't a POD type because it has a private constructor, but its +/// destructor must be trivial. Functions like MachineInstr::addOperand(), +/// MachineRegisterInfo::moveOperands(), and MF::DeleteMachineInstr() depend on +/// not having to call the MachineOperand destructor. +/// class MachineOperand { public: enum MachineOperandType { @@ -60,15 +65,11 @@ private: /// union. unsigned char OpKind; // MachineOperandType - // This union is discriminated by OpKind. - union { - /// SubReg - Subregister number, only valid for MO_Register. A value of 0 - /// indicates the MO_Register has no subReg. - unsigned char SubReg; - - /// TargetFlags - This is a set of target-specific operand flags. - unsigned char TargetFlags; - }; + /// Subregister number for MO_Register. A value of 0 indicates the + /// MO_Register has no subReg. + /// + /// For all other kinds of operands, this field holds target-specific flags. + unsigned SubReg_TargetFlags : 12; /// TiedTo - Non-zero when this register operand is tied to another register /// operand. The encoding of this field is described in the block comment @@ -176,24 +177,25 @@ private: } OffsetedInfo; } Contents; - explicit MachineOperand(MachineOperandType K) : OpKind(K), ParentMI(0) { - TargetFlags = 0; - } + explicit MachineOperand(MachineOperandType K) + : OpKind(K), SubReg_TargetFlags(0), ParentMI(0) {} public: /// getType - Returns the MachineOperandType for this operand. /// MachineOperandType getType() const { return (MachineOperandType)OpKind; } - unsigned char getTargetFlags() const { - return isReg() ? 0 : TargetFlags; + unsigned getTargetFlags() const { + return isReg() ? 0 : SubReg_TargetFlags; } - void setTargetFlags(unsigned char F) { + void setTargetFlags(unsigned F) { assert(!isReg() && "Register operands can't have target flags"); - TargetFlags = F; + SubReg_TargetFlags = F; + assert(SubReg_TargetFlags == F && "Target flags out of range"); } - void addTargetFlag(unsigned char F) { + void addTargetFlag(unsigned F) { assert(!isReg() && "Register operands can't have target flags"); - TargetFlags |= F; + SubReg_TargetFlags |= F; + assert((SubReg_TargetFlags & F) && "Target flags out of range"); } @@ -261,7 +263,7 @@ public: unsigned getSubReg() const { assert(isReg() && "Wrong MachineOperand accessor"); - return (unsigned)SubReg; + return SubReg_TargetFlags; } bool isUse() const { @@ -336,7 +338,8 @@ public: void setSubReg(unsigned subReg) { assert(isReg() && "Wrong MachineOperand accessor"); - SubReg = (unsigned char)subReg; + SubReg_TargetFlags = subReg; + assert(SubReg_TargetFlags == subReg && "SubReg out of range"); } /// substVirtReg - Substitute the current register with the virtual @@ -574,7 +577,7 @@ public: Op.SmallContents.RegNo = Reg; Op.Contents.Reg.Prev = 0; Op.Contents.Reg.Next = 0; - Op.SubReg = SubReg; + Op.setSubReg(SubReg); return Op; } static MachineOperand CreateMBB(MachineBasicBlock *MBB, diff --git a/include/llvm/CodeGen/MachinePostDominators.h b/include/llvm/CodeGen/MachinePostDominators.h index a9fc843..ca09aef 100644 --- a/include/llvm/CodeGen/MachinePostDominators.h +++ b/include/llvm/CodeGen/MachinePostDominators.h @@ -15,10 +15,9 @@ #ifndef LLVM_CODEGEN_MACHINEPOSTDOMINATORS_H #define LLVM_CODEGEN_MACHINEPOSTDOMINATORS_H -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineDominators.h" #include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/DominatorInternals.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunctionPass.h" namespace llvm { @@ -55,26 +54,27 @@ public: return DT->getNode(BB); } - bool dominates(MachineDomTreeNode *A, MachineDomTreeNode *B) const { + bool dominates(const MachineDomTreeNode *A, + const MachineDomTreeNode *B) const { return DT->dominates(A, B); } - bool dominates(MachineBasicBlock *A, MachineBasicBlock *B) const { + bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const { return DT->dominates(A, B); } - bool - properlyDominates(const MachineDomTreeNode *A, MachineDomTreeNode *B) const { + bool properlyDominates(const MachineDomTreeNode *A, + const MachineDomTreeNode *B) const { return DT->properlyDominates(A, B); } - bool - properlyDominates(MachineBasicBlock *A, MachineBasicBlock *B) const { + bool properlyDominates(const MachineBasicBlock *A, + const MachineBasicBlock *B) const { return DT->properlyDominates(A, B); } MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, - MachineBasicBlock *B) { + MachineBasicBlock *B) { return DT->findNearestCommonDominator(A, B); } diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h index 4e86363..4b43cc1 100644 --- a/include/llvm/CodeGen/MachineRegisterInfo.h +++ b/include/llvm/CodeGen/MachineRegisterInfo.h @@ -14,10 +14,10 @@ #ifndef LLVM_CODEGEN_MACHINEREGISTERINFO_H #define LLVM_CODEGEN_MACHINEREGISTERINFO_H -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/CodeGen/MachineInstrBundle.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/IndexedMap.h" +#include "llvm/CodeGen/MachineInstrBundle.h" +#include "llvm/Target/TargetRegisterInfo.h" #include <vector> namespace llvm { @@ -99,13 +99,11 @@ class MachineRegisterInfo { /// started. BitVector ReservedRegs; - /// LiveIns/LiveOuts - Keep track of the physical registers that are - /// livein/liveout of the function. Live in values are typically arguments in - /// registers, live out values are typically return values in registers. - /// LiveIn values are allowed to have virtual registers associated with them, - /// stored in the second element. + /// Keep track of the physical registers that are live in to the function. + /// Live in values are typically arguments in registers. LiveIn values are + /// allowed to have virtual registers associated with them, stored in the + /// second element. std::vector<std::pair<unsigned, unsigned> > LiveIns; - std::vector<unsigned> LiveOuts; MachineRegisterInfo(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION; void operator=(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION; @@ -156,6 +154,9 @@ public: // Strictly for use by MachineInstr.cpp. void removeRegOperandFromUseList(MachineOperand *MO); + // Strictly for use by MachineInstr.cpp. + void moveOperands(MachineOperand *Dst, MachineOperand *Src, unsigned NumOps); + /// reg_begin/reg_end - Provide iteration support to walk over all definitions /// and uses of a register within the MachineFunction that corresponds to this /// MachineRegisterInfo object. @@ -376,6 +377,12 @@ public: return false; } + /// Mark the specified register unit as used in this function. + /// This should only be called during and after register allocation. + void setRegUnitUsed(unsigned RegUnit) { + UsedRegUnits.set(RegUnit); + } + /// setPhysRegUsed - Mark the specified register used in this function. /// This should only be called during and after register allocation. void setPhysRegUsed(unsigned Reg) { @@ -457,30 +464,24 @@ public: } //===--------------------------------------------------------------------===// - // LiveIn/LiveOut Management + // LiveIn Management //===--------------------------------------------------------------------===// - /// addLiveIn/Out - Add the specified register as a live in/out. Note that it + /// addLiveIn - Add the specified register as a live-in. Note that it /// is an error to add the same register to the same set more than once. void addLiveIn(unsigned Reg, unsigned vreg = 0) { LiveIns.push_back(std::make_pair(Reg, vreg)); } - void addLiveOut(unsigned Reg) { LiveOuts.push_back(Reg); } - // Iteration support for live in/out sets. These sets are kept in sorted - // order by their register number. + // Iteration support for the live-ins set. It's kept in sorted order + // by register number. typedef std::vector<std::pair<unsigned,unsigned> >::const_iterator livein_iterator; - typedef std::vector<unsigned>::const_iterator liveout_iterator; livein_iterator livein_begin() const { return LiveIns.begin(); } livein_iterator livein_end() const { return LiveIns.end(); } bool livein_empty() const { return LiveIns.empty(); } - liveout_iterator liveout_begin() const { return LiveOuts.begin(); } - liveout_iterator liveout_end() const { return LiveOuts.end(); } - bool liveout_empty() const { return LiveOuts.empty(); } bool isLiveIn(unsigned Reg) const; - bool isLiveOut(unsigned Reg) const; /// getLiveInPhysReg - If VReg is a live-in virtual register, return the /// corresponding live-in physical register. diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index 31bd606..57febe7 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -24,8 +24,8 @@ // //===----------------------------------------------------------------------===// -#ifndef MACHINESCHEDULER_H -#define MACHINESCHEDULER_H +#ifndef LLVM_CODEGEN_MACHINESCHEDULER_H +#define LLVM_CODEGEN_MACHINESCHEDULER_H #include "llvm/CodeGen/MachinePassRegistry.h" #include "llvm/CodeGen/RegisterPressure.h" @@ -43,6 +43,7 @@ class MachineDominatorTree; class MachineLoopInfo; class RegisterClassInfo; class ScheduleDAGInstrs; +class SchedDFSResult; /// MachineSchedContext provides enough context from the MachineScheduler pass /// for the target to instantiate a scheduler. @@ -119,6 +120,9 @@ public: /// be scheduled at the bottom. virtual SUnit *pickNode(bool &IsTopNode) = 0; + /// \brief Scheduler callback to notify that a new subtree is scheduled. + virtual void scheduleTree(unsigned SubtreeID) {} + /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an /// instruction and updated scheduled/remaining flags in the DAG nodes. virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; @@ -164,6 +168,8 @@ public: iterator end() { return Queue.end(); } + ArrayRef<SUnit*> elements() { return Queue; } + iterator find(SUnit *SU) { return std::find(Queue.begin(), Queue.end(), SU); } @@ -181,7 +187,7 @@ public: return Queue.begin() + idx; } -#ifndef NDEBUG +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void dump(); #endif }; @@ -202,6 +208,15 @@ protected: RegisterClassInfo *RegClassInfo; MachineSchedStrategy *SchedImpl; + /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees + /// will be empty. + SchedDFSResult *DFSResult; + BitVector ScheduledTrees; + + /// Topo - A topological ordering for SUnits which permits fast IsReachable + /// and similar queries. + ScheduleDAGTopologicalSort Topo; + /// Ordered list of DAG postprocessing steps. std::vector<ScheduleDAGMutation*> Mutations; @@ -226,6 +241,10 @@ protected: IntervalPressure BotPressure; RegPressureTracker BotRPTracker; + /// Record the next node in a scheduled cluster. + const SUnit *NextClusterPred; + const SUnit *NextClusterSucc; + #ifndef NDEBUG /// The number of instructions scheduled so far. Used to cut off the /// scheduler at the point determined by misched-cutoff. @@ -235,25 +254,33 @@ protected: public: ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), - AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), - RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), - CurrentBottom(), BotRPTracker(BotPressure) { + AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0), + Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), + TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), + NextClusterPred(NULL), NextClusterSucc(NULL) { #ifndef NDEBUG NumInstrsScheduled = 0; #endif } - virtual ~ScheduleDAGMI() { - delete SchedImpl; - } + virtual ~ScheduleDAGMI(); /// Add a postprocessing step to the DAG builder. /// Mutations are applied in the order that they are added after normal DAG /// building and before MachineSchedStrategy initialization. + /// + /// ScheduleDAGMI takes ownership of the Mutation object. void addMutation(ScheduleDAGMutation *Mutation) { Mutations.push_back(Mutation); } + /// \brief Add a DAG edge to the given SU with the given predecessor + /// dependence data. + /// + /// \returns true if the edge may be added without creating a cycle OR if an + /// equivalent edge already existed (false indicates failure). + bool addEdge(SUnit *SuccSU, const SDep &PredDep); + MachineBasicBlock::iterator top() const { return CurrentTop; } MachineBasicBlock::iterator bottom() const { return CurrentBottom; } @@ -285,6 +312,22 @@ public: return RegionCriticalPSets; } + const SUnit *getNextClusterPred() const { return NextClusterPred; } + + const SUnit *getNextClusterSucc() const { return NextClusterSucc; } + + /// Compute a DFSResult after DAG building is complete, and before any + /// queue comparisons. + void computeDFSResult(); + + /// Return a non-null DFS result if the scheduling strategy initialized it. + const SchedDFSResult *getDFSResult() const { return DFSResult; } + + BitVector &getScheduledTrees() { return ScheduledTrees; } + + void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE; + void viewGraph() LLVM_OVERRIDE; + protected: // Top-Level entry points for the schedule() driver... @@ -298,8 +341,8 @@ protected: /// instances of ScheduleDAGMI to perform custom DAG postprocessing. void postprocessDAG(); - /// Identify DAG roots and setup scheduler queues. - void initQueues(); + /// Release ExitSU predecessors and setup scheduler queues. + void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots); /// Move an instruction and update register pressure. void scheduleMI(SUnit *SU, bool IsTopNode); @@ -317,12 +360,13 @@ protected: void initRegPressure(); - void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); + void updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure); void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); bool checkSchedLimit(); - void releaseRoots(); + void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, + SmallVectorImpl<SUnit*> &BotRoots); void releaseSucc(SUnit *SU, SDep *SuccEdge); void releaseSuccessors(SUnit *SU); diff --git a/include/llvm/CodeGen/MachineTraceMetrics.h b/include/llvm/CodeGen/MachineTraceMetrics.h new file mode 100644 index 0000000..2775a04 --- /dev/null +++ b/include/llvm/CodeGen/MachineTraceMetrics.h @@ -0,0 +1,388 @@ +//===- lib/CodeGen/MachineTraceMetrics.h - Super-scalar metrics -*- 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 interface for the MachineTraceMetrics analysis pass +// that estimates CPU resource usage and critical data dependency paths through +// preferred traces. This is useful for super-scalar CPUs where execution speed +// can be limited both by data dependencies and by limited execution resources. +// +// Out-of-order CPUs will often be executing instructions from multiple basic +// blocks at the same time. This makes it difficult to estimate the resource +// usage accurately in a single basic block. Resources can be estimated better +// by looking at a trace through the current basic block. +// +// For every block, the MachineTraceMetrics pass will pick a preferred trace +// that passes through the block. The trace is chosen based on loop structure, +// branch probabilities, and resource usage. The intention is to pick likely +// traces that would be the most affected by code transformations. +// +// It is expensive to compute a full arbitrary trace for every block, so to +// save some computations, traces are chosen to be convergent. This means that +// if the traces through basic blocks A and B ever cross when moving away from +// A and B, they never diverge again. This applies in both directions - If the +// traces meet above A and B, they won't diverge when going further back. +// +// Traces tend to align with loops. The trace through a block in an inner loop +// will begin at the loop entry block and end at a back edge. If there are +// nested loops, the trace may begin and end at those instead. +// +// For each trace, we compute the critical path length, which is the number of +// cycles required to execute the trace when execution is limited by data +// dependencies only. We also compute the resource height, which is the number +// of cycles required to execute all instructions in the trace when ignoring +// data dependencies. +// +// Every instruction in the current block has a slack - the number of cycles +// execution of the instruction can be delayed without extending the critical +// path. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_MACHINE_TRACE_METRICS_H +#define LLVM_CODEGEN_MACHINE_TRACE_METRICS_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/TargetSchedule.h" + +namespace llvm { + +class InstrItineraryData; +class MachineBasicBlock; +class MachineInstr; +class MachineLoop; +class MachineLoopInfo; +class MachineRegisterInfo; +class TargetInstrInfo; +class TargetRegisterInfo; +class raw_ostream; + +class MachineTraceMetrics : public MachineFunctionPass { + const MachineFunction *MF; + const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; + const MachineRegisterInfo *MRI; + const MachineLoopInfo *Loops; + TargetSchedModel SchedModel; + +public: + class Ensemble; + class Trace; + static char ID; + MachineTraceMetrics(); + void getAnalysisUsage(AnalysisUsage&) const; + bool runOnMachineFunction(MachineFunction&); + void releaseMemory(); + void verifyAnalysis() const; + + friend class Ensemble; + friend class Trace; + + /// Per-basic block information that doesn't depend on the trace through the + /// block. + struct FixedBlockInfo { + /// The number of non-trivial instructions in the block. + /// Doesn't count PHI and COPY instructions that are likely to be removed. + unsigned InstrCount; + + /// True when the block contains calls. + bool HasCalls; + + FixedBlockInfo() : InstrCount(~0u), HasCalls(false) {} + + /// Returns true when resource information for this block has been computed. + bool hasResources() const { return InstrCount != ~0u; } + + /// Invalidate resource information. + void invalidate() { InstrCount = ~0u; } + }; + + /// Get the fixed resource information about MBB. Compute it on demand. + const FixedBlockInfo *getResources(const MachineBasicBlock*); + + /// Get the scaled number of cycles used per processor resource in MBB. + /// This is an array with SchedModel.getNumProcResourceKinds() entries. + /// The getResources() function above must have been called first. + /// + /// These numbers have already been scaled by SchedModel.getResourceFactor(). + ArrayRef<unsigned> getProcResourceCycles(unsigned MBBNum) const; + + /// A virtual register or regunit required by a basic block or its trace + /// successors. + struct LiveInReg { + /// The virtual register required, or a register unit. + unsigned Reg; + + /// For virtual registers: Minimum height of the defining instruction. + /// For regunits: Height of the highest user in the trace. + unsigned Height; + + LiveInReg(unsigned Reg, unsigned Height = 0) : Reg(Reg), Height(Height) {} + }; + + /// Per-basic block information that relates to a specific trace through the + /// block. Convergent traces means that only one of these is required per + /// block in a trace ensemble. + struct TraceBlockInfo { + /// Trace predecessor, or NULL for the first block in the trace. + /// Valid when hasValidDepth(). + const MachineBasicBlock *Pred; + + /// Trace successor, or NULL for the last block in the trace. + /// Valid when hasValidHeight(). + const MachineBasicBlock *Succ; + + /// The block number of the head of the trace. (When hasValidDepth()). + unsigned Head; + + /// The block number of the tail of the trace. (When hasValidHeight()). + unsigned Tail; + + /// Accumulated number of instructions in the trace above this block. + /// Does not include instructions in this block. + unsigned InstrDepth; + + /// Accumulated number of instructions in the trace below this block. + /// Includes instructions in this block. + unsigned InstrHeight; + + TraceBlockInfo() : + Pred(0), Succ(0), + InstrDepth(~0u), InstrHeight(~0u), + HasValidInstrDepths(false), HasValidInstrHeights(false) {} + + /// Returns true if the depth resources have been computed from the trace + /// above this block. + bool hasValidDepth() const { return InstrDepth != ~0u; } + + /// Returns true if the height resources have been computed from the trace + /// below this block. + bool hasValidHeight() const { return InstrHeight != ~0u; } + + /// Invalidate depth resources when some block above this one has changed. + void invalidateDepth() { InstrDepth = ~0u; HasValidInstrDepths = false; } + + /// Invalidate height resources when a block below this one has changed. + void invalidateHeight() { InstrHeight = ~0u; HasValidInstrHeights = false; } + + /// Assuming that this is a dominator of TBI, determine if it contains + /// useful instruction depths. A dominating block can be above the current + /// trace head, and any dependencies from such a far away dominator are not + /// expected to affect the critical path. + /// + /// Also returns true when TBI == this. + bool isUsefulDominator(const TraceBlockInfo &TBI) const { + // The trace for TBI may not even be calculated yet. + if (!hasValidDepth() || !TBI.hasValidDepth()) + return false; + // Instruction depths are only comparable if the traces share a head. + if (Head != TBI.Head) + return false; + // It is almost always the case that TBI belongs to the same trace as + // this block, but rare convoluted cases involving irreducible control + // flow, a dominator may share a trace head without actually being on the + // same trace as TBI. This is not a big problem as long as it doesn't + // increase the instruction depth. + return HasValidInstrDepths && InstrDepth <= TBI.InstrDepth; + } + + // Data-dependency-related information. Per-instruction depth and height + // are computed from data dependencies in the current trace, using + // itinerary data. + + /// Instruction depths have been computed. This implies hasValidDepth(). + bool HasValidInstrDepths; + + /// Instruction heights have been computed. This implies hasValidHeight(). + bool HasValidInstrHeights; + + /// Critical path length. This is the number of cycles in the longest data + /// dependency chain through the trace. This is only valid when both + /// HasValidInstrDepths and HasValidInstrHeights are set. + unsigned CriticalPath; + + /// Live-in registers. These registers are defined above the current block + /// and used by this block or a block below it. + /// This does not include PHI uses in the current block, but it does + /// include PHI uses in deeper blocks. + SmallVector<LiveInReg, 4> LiveIns; + + void print(raw_ostream&) const; + }; + + /// InstrCycles represents the cycle height and depth of an instruction in a + /// trace. + struct InstrCycles { + /// Earliest issue cycle as determined by data dependencies and instruction + /// latencies from the beginning of the trace. Data dependencies from + /// before the trace are not included. + unsigned Depth; + + /// Minimum number of cycles from this instruction is issued to the of the + /// trace, as determined by data dependencies and instruction latencies. + unsigned Height; + }; + + /// A trace represents a plausible sequence of executed basic blocks that + /// passes through the current basic block one. The Trace class serves as a + /// handle to internal cached data structures. + class Trace { + Ensemble &TE; + TraceBlockInfo &TBI; + + unsigned getBlockNum() const { return &TBI - &TE.BlockInfo[0]; } + + public: + explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {} + void print(raw_ostream&) const; + + /// Compute the total number of instructions in the trace. + unsigned getInstrCount() const { + return TBI.InstrDepth + TBI.InstrHeight; + } + + /// Return the resource depth of the top/bottom of the trace center block. + /// This is the number of cycles required to execute all instructions from + /// the trace head to the trace center block. The resource depth only + /// considers execution resources, it ignores data dependencies. + /// When Bottom is set, instructions in the trace center block are included. + unsigned getResourceDepth(bool Bottom) const; + + /// Return the resource length of the trace. This is the number of cycles + /// required to execute the instructions in the trace if they were all + /// independent, exposing the maximum instruction-level parallelism. + /// + /// Any blocks in Extrablocks are included as if they were part of the + /// trace. + unsigned getResourceLength(ArrayRef<const MachineBasicBlock*> Extrablocks = + ArrayRef<const MachineBasicBlock*>()) const; + + /// Return the length of the (data dependency) critical path through the + /// trace. + unsigned getCriticalPath() const { return TBI.CriticalPath; } + + /// Return the depth and height of MI. The depth is only valid for + /// instructions in or above the trace center block. The height is only + /// valid for instructions in or below the trace center block. + InstrCycles getInstrCycles(const MachineInstr *MI) const { + return TE.Cycles.lookup(MI); + } + + /// Return the slack of MI. This is the number of cycles MI can be delayed + /// before the critical path becomes longer. + /// MI must be an instruction in the trace center block. + unsigned getInstrSlack(const MachineInstr *MI) const; + + /// Return the Depth of a PHI instruction in a trace center block successor. + /// The PHI does not have to be part of the trace. + unsigned getPHIDepth(const MachineInstr *PHI) const; + }; + + /// A trace ensemble is a collection of traces selected using the same + /// strategy, for example 'minimum resource height'. There is one trace for + /// every block in the function. + class Ensemble { + SmallVector<TraceBlockInfo, 4> BlockInfo; + DenseMap<const MachineInstr*, InstrCycles> Cycles; + SmallVector<unsigned, 0> ProcResourceDepths; + SmallVector<unsigned, 0> ProcResourceHeights; + friend class Trace; + + void computeTrace(const MachineBasicBlock*); + void computeDepthResources(const MachineBasicBlock*); + void computeHeightResources(const MachineBasicBlock*); + unsigned computeCrossBlockCriticalPath(const TraceBlockInfo&); + void computeInstrDepths(const MachineBasicBlock*); + void computeInstrHeights(const MachineBasicBlock*); + void addLiveIns(const MachineInstr *DefMI, unsigned DefOp, + ArrayRef<const MachineBasicBlock*> Trace); + + protected: + MachineTraceMetrics &MTM; + virtual const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) =0; + virtual const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) =0; + explicit Ensemble(MachineTraceMetrics*); + const MachineLoop *getLoopFor(const MachineBasicBlock*) const; + const TraceBlockInfo *getDepthResources(const MachineBasicBlock*) const; + const TraceBlockInfo *getHeightResources(const MachineBasicBlock*) const; + ArrayRef<unsigned> getProcResourceDepths(unsigned MBBNum) const; + ArrayRef<unsigned> getProcResourceHeights(unsigned MBBNum) const; + + public: + virtual ~Ensemble(); + virtual const char *getName() const =0; + void print(raw_ostream&) const; + void invalidate(const MachineBasicBlock *MBB); + void verify() const; + + /// Get the trace that passes through MBB. + /// The trace is computed on demand. + Trace getTrace(const MachineBasicBlock *MBB); + }; + + /// Strategies for selecting traces. + enum Strategy { + /// Select the trace through a block that has the fewest instructions. + TS_MinInstrCount, + + TS_NumStrategies + }; + + /// Get the trace ensemble representing the given trace selection strategy. + /// The returned Ensemble object is owned by the MachineTraceMetrics analysis, + /// and valid for the lifetime of the analysis pass. + Ensemble *getEnsemble(Strategy); + + /// Invalidate cached information about MBB. This must be called *before* MBB + /// is erased, or the CFG is otherwise changed. + /// + /// This invalidates per-block information about resource usage for MBB only, + /// and it invalidates per-trace information for any trace that passes + /// through MBB. + /// + /// Call Ensemble::getTrace() again to update any trace handles. + void invalidate(const MachineBasicBlock *MBB); + +private: + // One entry per basic block, indexed by block number. + SmallVector<FixedBlockInfo, 4> BlockInfo; + + // Cycles consumed on each processor resource per block. + // The number of processor resource kinds is constant for a given subtarget, + // but it is not known at compile time. The number of cycles consumed by + // block B on processor resource R is at ProcResourceCycles[B*Kinds + R] + // where Kinds = SchedModel.getNumProcResourceKinds(). + SmallVector<unsigned, 0> ProcResourceCycles; + + // One ensemble per strategy. + Ensemble* Ensembles[TS_NumStrategies]; + + // Convert scaled resource usage to a cycle count that can be compared with + // latencies. + unsigned getCycles(unsigned Scaled) { + unsigned Factor = SchedModel.getLatencyFactor(); + return (Scaled + Factor - 1) / Factor; + } +}; + +inline raw_ostream &operator<<(raw_ostream &OS, + const MachineTraceMetrics::Trace &Tr) { + Tr.print(OS); + return OS; +} + +inline raw_ostream &operator<<(raw_ostream &OS, + const MachineTraceMetrics::Ensemble &En) { + En.print(OS); + return OS; +} +} // end namespace llvm + +#endif diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index 83c379b..85bf511 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -16,10 +16,10 @@ #define LLVM_CODEGEN_PBQP_GRAPH_H #include "Math.h" - +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" #include <list> #include <map> -#include <llvm/ADT/ilist.h> namespace PBQP { diff --git a/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h index 35514f9..47e15b2 100644 --- a/include/llvm/CodeGen/PBQP/HeuristicSolver.h +++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h @@ -18,8 +18,8 @@ #include "Graph.h" #include "Solution.h" -#include <vector> #include <limits> +#include <vector> namespace PBQP { diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h index a859e58..307d81e 100644 --- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h +++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h @@ -18,9 +18,8 @@ #ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H #define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H -#include "../HeuristicSolver.h" #include "../HeuristicBase.h" - +#include "../HeuristicSolver.h" #include <limits> namespace PBQP { diff --git a/include/llvm/CodeGen/PBQP/Math.h b/include/llvm/CodeGen/PBQP/Math.h index e7598bf..08f8b981a 100644 --- a/include/llvm/CodeGen/PBQP/Math.h +++ b/include/llvm/CodeGen/PBQP/Math.h @@ -7,11 +7,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_PBQP_MATH_H +#ifndef LLVM_CODEGEN_PBQP_MATH_H #define LLVM_CODEGEN_PBQP_MATH_H -#include <cassert> #include <algorithm> +#include <cassert> #include <functional> namespace PBQP { diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h index 57d9b95..b9f288b 100644 --- a/include/llvm/CodeGen/PBQP/Solution.h +++ b/include/llvm/CodeGen/PBQP/Solution.h @@ -14,9 +14,8 @@ #ifndef LLVM_CODEGEN_PBQP_SOLUTION_H #define LLVM_CODEGEN_PBQP_SOLUTION_H -#include "Math.h" #include "Graph.h" - +#include "Math.h" #include <map> namespace PBQP { diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index 7bd5764..fc8aa75 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -25,6 +25,7 @@ namespace llvm { class MachineFunctionPass; class PassInfo; class PassManagerBase; + class TargetLoweringBase; class TargetLowering; class TargetRegisterClass; class raw_ostream; @@ -141,6 +142,10 @@ public: /// Add passes to lower exception handling for the code generator. void addPassesToHandleExceptions(); + /// Add pass to prepare the LLVM IR for code generation. This should be done + /// before exception handling preparation passes. + virtual void addCodeGenPrepare(); + /// Add common passes that perform LLVM IR to IR transforms in preparation for /// instruction selection. virtual void addISelPrepare(); @@ -176,6 +181,16 @@ protected: /// instructions in SSA form. virtual void addMachineSSAOptimization(); + /// Add passes that optimize instruction level parallelism for out-of-order + /// targets. These passes are run while the machine code is still in SSA + /// form, so they can use MachineTraceMetrics to control their heuristics. + /// + /// All passes added here should preserve the MachineDominatorTree, + /// MachineLoopInfo, and MachineTraceMetrics analyses. + virtual bool addILPOpts() { + return false; + } + /// addPreRegAlloc - This method may be implemented by targets that want to /// run passes immediately before register allocation. This should return /// true if -print-machineinstrs should print after these passes. @@ -237,6 +252,11 @@ protected: return false; } + /// addGCPasses - Add late codegen passes that analyze code for garbage + /// collection. This should return true if GC info should be printed after + /// these passes. + virtual bool addGCPasses(); + /// Add standard basic block placement passes. virtual void addBlockPlacement(); @@ -271,6 +291,13 @@ protected: /// List of target independent CodeGen pass IDs. namespace llvm { + /// \brief Create a basic TargetTransformInfo analysis pass. + /// + /// This pass implements the target transform info analysis using the target + /// independent information available to the LLVM code generator. + ImmutablePass * + createBasicTargetTransformInfoPass(const TargetLoweringBase *TLI); + /// createUnreachableBlockEliminationPass - The LLVM code generator does not /// work well with unreachable basic blocks (what live ranges make sense for a /// block that cannot be reached?). As such, a code generator should either @@ -288,9 +315,6 @@ namespace llvm { /// MachineLoopInfo - This pass is a loop analysis pass. extern char &MachineLoopInfoID; - /// MachineLoopRanges - This pass is an on-demand loop coverage analysis. - extern char &MachineLoopRangesID; - /// MachineDominators - This pass is a machine dominators analysis pass. extern char &MachineDominatorsID; @@ -420,10 +444,6 @@ namespace llvm { /// information. extern char &MachineBlockPlacementStatsID; - /// Code Placement - This pass optimize code placement and aligns loop - /// headers to target specific alignment boundary. - extern char &CodePlacementOptID; - /// GCLowering Pass - Performs target-independent LLVM IR transformations for /// highly portable strategies. /// @@ -435,10 +455,6 @@ namespace llvm { /// branch folding). extern char &GCMachineCodeAnalysisID; - /// Deleter Pass - Releases GC metadata. - /// - FunctionPass *createGCInfoDeleter(); - /// Creates a pass to print GC metadata. /// FunctionPass *createGCInfoPrinter(raw_ostream &OS); @@ -469,7 +485,7 @@ namespace llvm { /// createStackProtectorPass - This pass adds stack protectors to functions. /// - FunctionPass *createStackProtectorPass(const TargetLowering *tli); + FunctionPass *createStackProtectorPass(const TargetLoweringBase *tli); /// createMachineVerifierPass - This pass verifies cenerated machine code /// instructions for correctness. @@ -483,7 +499,7 @@ namespace llvm { /// createSjLjEHPreparePass - This pass adapts exception handling code to use /// the GCC-style builtin setjmp/longjmp (sjlj) to handling EH control flow. /// - FunctionPass *createSjLjEHPreparePass(const TargetLowering *tli); + FunctionPass *createSjLjEHPreparePass(const TargetLoweringBase *tli); /// LocalStackSlotAllocation - This pass assigns local frame indices to stack /// slots relative to one another and allocates base registers to access them diff --git a/include/llvm/CodeGen/PseudoSourceValue.h b/include/llvm/CodeGen/PseudoSourceValue.h index 8f52d3b..df74d08 100644 --- a/include/llvm/CodeGen/PseudoSourceValue.h +++ b/include/llvm/CodeGen/PseudoSourceValue.h @@ -14,7 +14,7 @@ #ifndef LLVM_CODEGEN_PSEUDOSOURCEVALUE_H #define LLVM_CODEGEN_PSEUDOSOURCEVALUE_H -#include "llvm/Value.h" +#include "llvm/IR/Value.h" namespace llvm { class MachineFrameInfo; diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index acfc07d..b617c14 100644 --- a/include/llvm/CodeGen/RegAllocPBQP.h +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -20,7 +20,6 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/PBQP/Graph.h" #include "llvm/CodeGen/PBQP/Solution.h" - #include <map> #include <set> @@ -29,6 +28,7 @@ namespace llvm { class LiveIntervals; class MachineFunction; class MachineLoopInfo; + class TargetRegisterInfo; /// This class wraps up a PBQP instance representing a register allocation /// problem, plus the structures necessary to map back from the PBQP solution diff --git a/include/llvm/CodeGen/RegAllocRegistry.h b/include/llvm/CodeGen/RegAllocRegistry.h index 100e357..ca49577 100644 --- a/include/llvm/CodeGen/RegAllocRegistry.h +++ b/include/llvm/CodeGen/RegAllocRegistry.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGENREGALLOCREGISTRY_H -#define LLVM_CODEGENREGALLOCREGISTRY_H +#ifndef LLVM_CODEGEN_REGALLOCREGISTRY_H +#define LLVM_CODEGEN_REGALLOCREGISTRY_H #include "llvm/CodeGen/MachinePassRegistry.h" diff --git a/include/llvm/CodeGen/RegisterClassInfo.h b/include/llvm/CodeGen/RegisterClassInfo.h index 4467b62..3ad22e6 100644 --- a/include/llvm/CodeGen/RegisterClassInfo.h +++ b/include/llvm/CodeGen/RegisterClassInfo.h @@ -29,10 +29,15 @@ class RegisterClassInfo { unsigned Tag; unsigned NumRegs; bool ProperSubClass; - OwningArrayPtr<unsigned> Order; + uint8_t MinCost; + uint16_t LastCostChange; + OwningArrayPtr<MCPhysReg> Order; - RCInfo() : Tag(0), NumRegs(0), ProperSubClass(false) {} - operator ArrayRef<unsigned>() const { + RCInfo() + : Tag(0), NumRegs(0), ProperSubClass(false), MinCost(0), + LastCostChange(0) {} + + operator ArrayRef<MCPhysReg>() const { return makeArrayRef(Order.get(), NumRegs); } }; @@ -84,7 +89,7 @@ public: /// getOrder - Returns the preferred allocation order for RC. The order /// contains no reserved registers, and registers that alias callee saved /// registers come last. - ArrayRef<unsigned> getOrder(const TargetRegisterClass *RC) const { + ArrayRef<MCPhysReg> getOrder(const TargetRegisterClass *RC) const { return get(RC); } @@ -106,6 +111,21 @@ public: return CalleeSaved[N-1]; return 0; } + + /// Get the minimum register cost in RC's allocation order. + /// This is the smallest value returned by TRI->getCostPerUse(Reg) for all + /// the registers in getOrder(RC). + unsigned getMinCost(const TargetRegisterClass *RC) { + return get(RC).MinCost; + } + + /// Get the position of the last cost change in getOrder(RC). + /// + /// All registers in getOrder(RC).slice(getLastCostChange(RC)) will have the + /// same cost according to TRI->getCostPerUse(). + unsigned getLastCostChange(const TargetRegisterClass *RC) { + return get(RC).LastCostChange; + } }; } // end namespace llvm diff --git a/include/llvm/CodeGen/RegisterPressure.h b/include/llvm/CodeGen/RegisterPressure.h index 30326d0..2670180 100644 --- a/include/llvm/CodeGen/RegisterPressure.h +++ b/include/llvm/CodeGen/RegisterPressure.h @@ -15,13 +15,14 @@ #ifndef LLVM_CODEGEN_REGISTERPRESSURE_H #define LLVM_CODEGEN_REGISTERPRESSURE_H +#include "llvm/ADT/SparseSet.h" #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/ADT/SparseSet.h" namespace llvm { class LiveIntervals; +class LiveInterval; class RegisterClassInfo; class MachineInstr; @@ -30,18 +31,24 @@ struct RegisterPressure { /// Map of max reg pressure indexed by pressure set ID, not class ID. std::vector<unsigned> MaxSetPressure; - /// List of live in registers. + /// List of live in virtual registers or physical register units. SmallVector<unsigned,8> LiveInRegs; SmallVector<unsigned,8> LiveOutRegs; /// Increase register pressure for each pressure set impacted by this register /// class. Normally called by RegPressureTracker, but may be called manually /// to account for live through (global liveness). - void increase(const TargetRegisterClass *RC, const TargetRegisterInfo *TRI); + /// + /// \param Reg is either a virtual register number or register unit number. + void increase(unsigned Reg, const TargetRegisterInfo *TRI, + const MachineRegisterInfo *MRI); /// Decrease register pressure for each pressure set impacted by this register /// class. This is only useful to account for spilling or rematerialization. - void decrease(const TargetRegisterClass *RC, const TargetRegisterInfo *TRI); + /// + /// \param Reg is either a virtual register number or register unit number. + void decrease(unsigned Reg, const TargetRegisterInfo *TRI, + const MachineRegisterInfo *MRI); void dump(const TargetRegisterInfo *TRI) const; }; @@ -116,6 +123,33 @@ struct RegPressureDelta { RegPressureDelta() {} }; +/// \brief A set of live virtual registers and physical register units. +/// +/// Virtual and physical register numbers require separate sparse sets, but most +/// of the RegisterPressureTracker handles them uniformly. +struct LiveRegSet { + SparseSet<unsigned> PhysRegs; + SparseSet<unsigned, VirtReg2IndexFunctor> VirtRegs; + + bool contains(unsigned Reg) { + if (TargetRegisterInfo::isVirtualRegister(Reg)) + return VirtRegs.count(Reg); + return PhysRegs.count(Reg); + } + + bool insert(unsigned Reg) { + if (TargetRegisterInfo::isVirtualRegister(Reg)) + return VirtRegs.insert(Reg).second; + return PhysRegs.insert(Reg).second; + } + + bool erase(unsigned Reg) { + if (TargetRegisterInfo::isVirtualRegister(Reg)) + return VirtRegs.erase(Reg); + return PhysRegs.erase(Reg); + } +}; + /// Track the current register pressure at some position in the instruction /// stream, and remember the high water mark within the region traversed. This /// does not automatically consider live-through ranges. The client may @@ -150,15 +184,15 @@ class RegPressureTracker { bool RequireIntervals; /// Register pressure corresponds to liveness before this instruction - /// iterator. It may point to the end of the block rather than an instruction. + /// iterator. It may point to the end of the block or a DebugValue rather than + /// an instruction. MachineBasicBlock::const_iterator CurrPos; /// Pressure map indexed by pressure set ID, not class ID. std::vector<unsigned> CurrSetPressure; - /// List of live registers. - SparseSet<unsigned> LivePhysRegs; - SparseSet<unsigned, VirtReg2IndexFunctor> LiveVirtRegs; + /// Set of live registers. + LiveRegSet LiveRegs; public: RegPressureTracker(IntervalPressure &rp) : @@ -171,8 +205,9 @@ public: const LiveIntervals *lis, const MachineBasicBlock *mbb, MachineBasicBlock::const_iterator pos); - /// Force liveness of registers. Particularly useful to initialize the - /// livein/out state of the tracker before the first call to advance/recede. + /// Force liveness of virtual registers or physical register + /// units. Particularly useful to initialize the livein/out state of the + /// tracker before the first call to advance/recede. void addLiveRegs(ArrayRef<unsigned> Regs); /// Get the MI position corresponding to this register pressure. @@ -184,6 +219,10 @@ public: // position changes while pressure does not. void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; } + /// \brief Get the SlotIndex for the first nondebug instruction including or + /// after the current position. + SlotIndex getCurrSlot() const; + /// Recede across the previous instruction. bool recede(); @@ -203,11 +242,8 @@ public: /// than the pressure across the traversed region. std::vector<unsigned> &getRegSetPressureAtPos() { return CurrSetPressure; } - void discoverPhysLiveIn(unsigned Reg); - void discoverPhysLiveOut(unsigned Reg); - - void discoverVirtLiveIn(unsigned Reg); - void discoverVirtLiveOut(unsigned Reg); + void discoverLiveOut(unsigned Reg); + void discoverLiveIn(unsigned Reg); bool isTopClosed() const; bool isBottomClosed() const; @@ -268,12 +304,13 @@ public: return getDownwardPressure(MI, PressureResult, MaxPressureResult); } + void dump() const; + protected: - void increasePhysRegPressure(ArrayRef<unsigned> Regs); - void decreasePhysRegPressure(ArrayRef<unsigned> Regs); + const LiveInterval *getInterval(unsigned Reg) const; - void increaseVirtRegPressure(ArrayRef<unsigned> Regs); - void decreaseVirtRegPressure(ArrayRef<unsigned> Regs); + void increaseRegPressure(ArrayRef<unsigned> Regs); + void decreaseRegPressure(ArrayRef<unsigned> Regs); void bumpUpwardPressure(const MachineInstr *MI); void bumpDownwardPressure(const MachineInstr *MI); diff --git a/include/llvm/CodeGen/RegisterScavenging.h b/include/llvm/CodeGen/RegisterScavenging.h index 08d3169..95bf291 100644 --- a/include/llvm/CodeGen/RegisterScavenging.h +++ b/include/llvm/CodeGen/RegisterScavenging.h @@ -14,12 +14,12 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_REGISTER_SCAVENGING_H -#define LLVM_CODEGEN_REGISTER_SCAVENGING_H +#ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H +#define LLVM_CODEGEN_REGISTERSCAVENGING_H +#include "llvm/ADT/BitVector.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/ADT/BitVector.h" namespace llvm { @@ -40,21 +40,23 @@ class RegScavenger { /// registers. bool Tracking; - /// ScavengingFrameIndex - Special spill slot used for scavenging a register - /// post register allocation. - int ScavengingFrameIndex; + /// Information on scavenged registers (held in a spill slot). + struct ScavengedInfo { + ScavengedInfo(int FI = -1) : FrameIndex(FI), Reg(0), Restore(NULL) {} - /// ScavengedReg - If none zero, the specific register is currently being - /// scavenged. That is, it is spilled to the special scavenging stack slot. - unsigned ScavengedReg; + /// A spill slot used for scavenging a register post register allocation. + int FrameIndex; - /// ScavengedRC - Register class of the scavenged register. - /// - const TargetRegisterClass *ScavengedRC; + /// If non-zero, the specific register is currently being + /// scavenged. That is, it is spilled to this scavenging stack slot. + unsigned Reg; - /// ScavengeRestore - Instruction that restores the scavenged register from - /// stack. - const MachineInstr *ScavengeRestore; + /// The instruction that restores the scavenged register from stack. + const MachineInstr *Restore; + }; + + /// A vector of information on scavenged registers. + SmallVector<ScavengedInfo, 2> Scavenged; /// CalleeSavedrRegs - A bitvector of callee saved registers for the target. /// @@ -71,8 +73,7 @@ class RegScavenger { public: RegScavenger() - : MBB(NULL), NumPhysRegs(0), Tracking(false), - ScavengingFrameIndex(-1), ScavengedReg(0), ScavengedRC(NULL) {} + : MBB(NULL), NumPhysRegs(0), Tracking(false) {} /// enterBasicBlock - Start tracking liveness from the begin of the specific /// basic block. @@ -92,9 +93,25 @@ public: while (MBBI != I) forward(); } + /// Invert the behavior of forward() on the current instruction (undo the + /// changes to the available registers made by forward()). + void unprocess(); + + /// Unprocess instructions until you reach the provided iterator. + void unprocess(MachineBasicBlock::iterator I) { + while (MBBI != I) unprocess(); + } + /// skipTo - Move the internal MBB iterator but do not update register states. - /// - void skipTo(MachineBasicBlock::iterator I) { MBBI = I; } + void skipTo(MachineBasicBlock::iterator I) { + if (I == MachineBasicBlock::iterator(NULL)) + Tracking = false; + MBBI = I; + } + + MachineBasicBlock::iterator getCurrentPosition() const { + return MBBI; + } /// getRegsUsed - return all registers currently in use in used. void getRegsUsed(BitVector &used, bool includeReserved); @@ -107,10 +124,28 @@ public: /// Return 0 if none is found. unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const; - /// setScavengingFrameIndex / getScavengingFrameIndex - accessor and setter of - /// ScavengingFrameIndex. - void setScavengingFrameIndex(int FI) { ScavengingFrameIndex = FI; } - int getScavengingFrameIndex() const { return ScavengingFrameIndex; } + /// Add a scavenging frame index. + void addScavengingFrameIndex(int FI) { + Scavenged.push_back(ScavengedInfo(FI)); + } + + /// Query whether a frame index is a scavenging frame index. + bool isScavengingFrameIndex(int FI) const { + for (SmallVector<ScavengedInfo, 2>::const_iterator I = Scavenged.begin(), + IE = Scavenged.end(); I != IE; ++I) + if (I->FrameIndex == FI) + return true; + + return false; + } + + /// Get an array of scavenging frame indices. + void getScavengingFrameIndices(SmallVectorImpl<int> &A) const { + for (SmallVector<ScavengedInfo, 2>::const_iterator I = Scavenged.begin(), + IE = Scavenged.end(); I != IE; ++I) + if (I->FrameIndex >= 0) + A.push_back(I->FrameIndex); + } /// scavengeRegister - Make a register of the specific register class /// available and do the appropriate bookkeeping. SPAdj is the stack @@ -129,10 +164,12 @@ private: /// isReserved - Returns true if a register is reserved. It is never "unused". bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); } - /// isUsed / isUnused - Test if a register is currently being used. + /// isUsed - Test if a register is currently being used. When called by the + /// isAliasUsed function, we only check isReserved if this is the original + /// register, not an alias register. /// - bool isUsed(unsigned Reg) const { - return !RegsAvailable.test(Reg) || isReserved(Reg); + bool isUsed(unsigned Reg, bool CheckReserved = true) const { + return !RegsAvailable.test(Reg) || (CheckReserved && isReserved(Reg)); } /// isAliasUsed - Is Reg or an alias currently in use? @@ -147,6 +184,10 @@ private: RegsAvailable |= Regs; } + /// Processes the current instruction and fill the KillRegs and DefRegs bit + /// vectors. + void determineKillsAndDefs(); + /// Add Reg and all its sub-registers to BV. void addRegWithSubRegs(BitVector &BV, unsigned Reg); diff --git a/include/llvm/CodeGen/ResourcePriorityQueue.h b/include/llvm/CodeGen/ResourcePriorityQueue.h index 56b5855..f20a9fc 100644 --- a/include/llvm/CodeGen/ResourcePriorityQueue.h +++ b/include/llvm/CodeGen/ResourcePriorityQueue.h @@ -14,12 +14,12 @@ // //===----------------------------------------------------------------------===// -#ifndef RESOURCE_PRIORITY_QUEUE_H -#define RESOURCE_PRIORITY_QUEUE_H +#ifndef LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H +#define LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H #include "llvm/CodeGen/DFAPacketizer.h" -#include "llvm/CodeGen/SelectionDAGISel.h" #include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/SelectionDAGISel.h" #include "llvm/MC/MCInstrItineraries.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" diff --git a/include/llvm/CodeGen/RuntimeLibcalls.h b/include/llvm/CodeGen/RuntimeLibcalls.h index 4bfd4ab..41289a4 100644 --- a/include/llvm/CodeGen/RuntimeLibcalls.h +++ b/include/llvm/CodeGen/RuntimeLibcalls.h @@ -86,100 +86,131 @@ namespace RTLIB { ADD_F32, ADD_F64, ADD_F80, + ADD_F128, ADD_PPCF128, SUB_F32, SUB_F64, SUB_F80, + SUB_F128, SUB_PPCF128, MUL_F32, MUL_F64, MUL_F80, + MUL_F128, MUL_PPCF128, DIV_F32, DIV_F64, DIV_F80, + DIV_F128, DIV_PPCF128, REM_F32, REM_F64, REM_F80, + REM_F128, REM_PPCF128, FMA_F32, FMA_F64, FMA_F80, + FMA_F128, FMA_PPCF128, POWI_F32, POWI_F64, POWI_F80, + POWI_F128, POWI_PPCF128, SQRT_F32, SQRT_F64, SQRT_F80, + SQRT_F128, SQRT_PPCF128, LOG_F32, LOG_F64, LOG_F80, + LOG_F128, LOG_PPCF128, LOG2_F32, LOG2_F64, LOG2_F80, + LOG2_F128, LOG2_PPCF128, LOG10_F32, LOG10_F64, LOG10_F80, + LOG10_F128, LOG10_PPCF128, EXP_F32, EXP_F64, EXP_F80, + EXP_F128, EXP_PPCF128, EXP2_F32, EXP2_F64, EXP2_F80, + EXP2_F128, EXP2_PPCF128, SIN_F32, SIN_F64, SIN_F80, + SIN_F128, SIN_PPCF128, COS_F32, COS_F64, COS_F80, + COS_F128, COS_PPCF128, + SINCOS_F32, + SINCOS_F64, + SINCOS_F80, + SINCOS_F128, + SINCOS_PPCF128, POW_F32, POW_F64, POW_F80, + POW_F128, POW_PPCF128, CEIL_F32, CEIL_F64, CEIL_F80, + CEIL_F128, CEIL_PPCF128, TRUNC_F32, TRUNC_F64, TRUNC_F80, + TRUNC_F128, TRUNC_PPCF128, RINT_F32, RINT_F64, RINT_F80, + RINT_F128, RINT_PPCF128, NEARBYINT_F32, NEARBYINT_F64, NEARBYINT_F80, + NEARBYINT_F128, NEARBYINT_PPCF128, FLOOR_F32, FLOOR_F64, FLOOR_F80, + FLOOR_F128, FLOOR_PPCF128, COPYSIGN_F32, COPYSIGN_F64, COPYSIGN_F80, + COPYSIGN_F128, COPYSIGN_PPCF128, // CONVERSION + FPEXT_F64_F128, + FPEXT_F32_F128, FPEXT_F32_F64, FPEXT_F16_F32, FPROUND_F32_F16, FPROUND_F64_F32, FPROUND_F80_F32, + FPROUND_F128_F32, FPROUND_PPCF128_F32, FPROUND_F80_F64, + FPROUND_F128_F64, FPROUND_PPCF128_F64, FPTOSINT_F32_I8, FPTOSINT_F32_I16, @@ -194,6 +225,9 @@ namespace RTLIB { FPTOSINT_F80_I32, FPTOSINT_F80_I64, FPTOSINT_F80_I128, + FPTOSINT_F128_I32, + FPTOSINT_F128_I64, + FPTOSINT_F128_I128, FPTOSINT_PPCF128_I32, FPTOSINT_PPCF128_I64, FPTOSINT_PPCF128_I128, @@ -210,51 +244,68 @@ namespace RTLIB { FPTOUINT_F80_I32, FPTOUINT_F80_I64, FPTOUINT_F80_I128, + FPTOUINT_F128_I32, + FPTOUINT_F128_I64, + FPTOUINT_F128_I128, FPTOUINT_PPCF128_I32, FPTOUINT_PPCF128_I64, FPTOUINT_PPCF128_I128, SINTTOFP_I32_F32, SINTTOFP_I32_F64, SINTTOFP_I32_F80, + SINTTOFP_I32_F128, SINTTOFP_I32_PPCF128, SINTTOFP_I64_F32, SINTTOFP_I64_F64, SINTTOFP_I64_F80, + SINTTOFP_I64_F128, SINTTOFP_I64_PPCF128, SINTTOFP_I128_F32, SINTTOFP_I128_F64, SINTTOFP_I128_F80, + SINTTOFP_I128_F128, SINTTOFP_I128_PPCF128, UINTTOFP_I32_F32, UINTTOFP_I32_F64, UINTTOFP_I32_F80, + UINTTOFP_I32_F128, UINTTOFP_I32_PPCF128, UINTTOFP_I64_F32, UINTTOFP_I64_F64, UINTTOFP_I64_F80, + UINTTOFP_I64_F128, UINTTOFP_I64_PPCF128, UINTTOFP_I128_F32, UINTTOFP_I128_F64, UINTTOFP_I128_F80, + UINTTOFP_I128_F128, UINTTOFP_I128_PPCF128, // COMPARISON OEQ_F32, OEQ_F64, + OEQ_F128, UNE_F32, UNE_F64, + UNE_F128, OGE_F32, OGE_F64, + OGE_F128, OLT_F32, OLT_F64, + OLT_F128, OLE_F32, OLE_F64, + OLE_F128, OGT_F32, OGT_F64, + OGT_F128, UO_F32, UO_F64, + UO_F128, O_F32, O_F64, + O_F128, // MEMORY MEMCPY, diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 7e0ca14..8c959da 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -16,13 +16,12 @@ #ifndef LLVM_CODEGEN_SCHEDULEDAG_H #define LLVM_CODEGEN_SCHEDULEDAG_H -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/Target/TargetLowering.h" -#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/TargetLowering.h" namespace llvm { class AliasAnalysis; @@ -53,11 +52,22 @@ namespace llvm { Order ///< Any other ordering dependency. }; + // Strong dependencies must be respected by the scheduler. Artificial + // dependencies may be removed only if they are redundant with another + // strong depedence. + // + // Weak dependencies may be violated by the scheduling strategy, but only if + // the strategy can prove it is correct to do so. + // + // Strong OrderKinds must occur before "Weak". + // Weak OrderKinds must occur after "Weak". enum OrderKind { Barrier, ///< An unknown scheduling barrier. MayAliasMem, ///< Nonvolatile load/Store instructions that may alias. MustAliasMem, ///< Nonvolatile load/Store instructions that must alias. - Artificial ///< Arbitrary weak DAG edge (no actual dependence). + Artificial, ///< Arbitrary strong DAG edge (no real dependence). + Weak, ///< Arbitrary weak DAG edge. + Cluster ///< Weak DAG edge linking a chain of clustered instrs. }; private: @@ -200,12 +210,26 @@ namespace llvm { return getKind() == Order && Contents.OrdKind == MustAliasMem; } + /// isWeak - Test if this a weak dependence. Weak dependencies are + /// considered DAG edges for height computation and other heuristics, but do + /// not force ordering. Breaking a weak edge may require the scheduler to + /// compensate, for example by inserting a copy. + bool isWeak() const { + return getKind() == Order && Contents.OrdKind >= Weak; + } + /// isArtificial - Test if this is an Order dependence that is marked /// as "artificial", meaning it isn't necessary for correctness. bool isArtificial() const { return getKind() == Order && Contents.OrdKind == Artificial; } + /// isCluster - Test if this is an Order dependence that is marked + /// as "cluster", meaning it is artificial and wants to be adjacent. + bool isCluster() const { + return getKind() == Order && Contents.OrdKind == Cluster; + } + /// isAssignedRegDep - Test if this is a Data dependence that is /// associated with a register. bool isAssignedRegDep() const { @@ -243,6 +267,8 @@ namespace llvm { /// SUnit - Scheduling unit. This is a node in the scheduling DAG. class SUnit { private: + enum { BoundaryID = ~0u }; + SDNode *Node; // Representative node. MachineInstr *Instr; // Alternatively, a MachineInstr. public: @@ -267,6 +293,8 @@ namespace llvm { unsigned NumSuccs; // # of SDep::Data sucss. unsigned NumPredsLeft; // # of preds not scheduled. unsigned NumSuccsLeft; // # of succs not scheduled. + unsigned WeakPredsLeft; // # of weak preds not scheduled. + unsigned WeakSuccsLeft; // # of weak succs not scheduled. unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. unsigned short Latency; // Node latency. bool isVRegCycle : 1; // May use and def the same vreg. @@ -301,12 +329,12 @@ namespace llvm { SUnit(SDNode *node, unsigned nodenum) : Node(node), Instr(0), OrigNode(0), SchedClass(0), NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), - isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), - isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), - isPending(false), isAvailable(false), isScheduled(false), - isScheduleHigh(false), isScheduleLow(false), isCloned(false), - SchedulingPref(Sched::None), + NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), + Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), + isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), + hasPhysRegClobbers(false), isPending(false), isAvailable(false), + isScheduled(false), isScheduleHigh(false), isScheduleLow(false), + isCloned(false), SchedulingPref(Sched::None), isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} @@ -315,28 +343,37 @@ namespace llvm { SUnit(MachineInstr *instr, unsigned nodenum) : Node(0), Instr(instr), OrigNode(0), SchedClass(0), NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), - isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), - isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), - isPending(false), isAvailable(false), isScheduled(false), - isScheduleHigh(false), isScheduleLow(false), isCloned(false), - SchedulingPref(Sched::None), + NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), + Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), + isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), + hasPhysRegClobbers(false), isPending(false), isAvailable(false), + isScheduled(false), isScheduleHigh(false), isScheduleLow(false), + isCloned(false), SchedulingPref(Sched::None), isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} /// SUnit - Construct a placeholder SUnit. SUnit() - : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(~0u), + : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(BoundaryID), NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), - NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), - isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), - isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), - isPending(false), isAvailable(false), isScheduled(false), - isScheduleHigh(false), isScheduleLow(false), isCloned(false), - SchedulingPref(Sched::None), + NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), + Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), + isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), + hasPhysRegClobbers(false), isPending(false), isAvailable(false), + isScheduled(false), isScheduleHigh(false), isScheduleLow(false), + isCloned(false), SchedulingPref(Sched::None), isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} + /// \brief Boundary nodes are placeholders for the boundary of the + /// scheduling region. + /// + /// BoundaryNodes can have DAG edges, including Data edges, but they do not + /// correspond to schedulable entities (e.g. instructions) and do not have a + /// valid ID. Consequently, always check for boundary nodes before accessing + /// an assoicative data structure keyed on node ID. + bool isBoundaryNode() const { return NodeNum == BoundaryID; }; + /// setNode - Assign the representative SDNode for this SUnit. /// This may be used during pre-regalloc scheduling. void setNode(SDNode *N) { @@ -372,7 +409,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. - bool addPred(const SDep &D); + bool addPred(const SDep &D, bool Required = true); /// 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 @@ -438,6 +475,10 @@ namespace llvm { return NumSuccsLeft == 0; } + /// \brief Order this node's predecessor edges such that the critical path + /// edge occurs first. + void biasCriticalPath(); + void dump(const ScheduleDAG *G) const; void dumpAll(const ScheduleDAG *G) const; void print(raw_ostream &O, const ScheduleDAG *G) const; @@ -546,8 +587,8 @@ namespace llvm { /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered /// using 'dot'. /// - void viewGraph(const Twine &Name, const Twine &Title); - void viewGraph(); + virtual void viewGraph(const Twine &Name, const Twine &Title); + virtual void viewGraph(); virtual void dumpNode(const SUnit *SU) const = 0; @@ -654,6 +695,7 @@ namespace llvm { class ScheduleDAGTopologicalSort { /// SUnits - A reference to the ScheduleDAG's SUnits. std::vector<SUnit> &SUnits; + SUnit *ExitSU; /// Index2Node - Maps topological index to the node number. std::vector<int> Index2Node; @@ -675,7 +717,7 @@ namespace llvm { void Allocate(int n, int index); public: - explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits); + ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU); /// InitDAGTopologicalSorting - create the initial topological /// ordering from the DAG to be scheduled. diff --git a/include/llvm/CodeGen/ScheduleDAGILP.h b/include/llvm/CodeGen/ScheduleDAGILP.h deleted file mode 100644 index 1aa4058..0000000 --- a/include/llvm/CodeGen/ScheduleDAGILP.h +++ /dev/null @@ -1,86 +0,0 @@ -//===- ScheduleDAGILP.h - ILP metric for ScheduleDAGInstrs ------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Definition of an ILP metric for machine level instruction scheduling. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_SCHEDULEDAGILP_H -#define LLVM_CODEGEN_SCHEDULEDAGILP_H - -#include "llvm/Support/DataTypes.h" -#include <vector> - -namespace llvm { - -class raw_ostream; -class ScheduleDAGInstrs; -class SUnit; - -/// \brief Represent the ILP of the subDAG rooted at a DAG node. -struct ILPValue { - unsigned InstrCount; - unsigned Cycles; - - ILPValue(): InstrCount(0), Cycles(0) {} - - ILPValue(unsigned count, unsigned cycles): - InstrCount(count), Cycles(cycles) {} - - bool isValid() const { return Cycles > 0; } - - // Order by the ILP metric's value. - bool operator<(ILPValue RHS) const { - return (uint64_t)InstrCount * RHS.Cycles - < (uint64_t)Cycles * RHS.InstrCount; - } - bool operator>(ILPValue RHS) const { - return RHS < *this; - } - bool operator<=(ILPValue RHS) const { - return (uint64_t)InstrCount * RHS.Cycles - <= (uint64_t)Cycles * RHS.InstrCount; - } - bool operator>=(ILPValue RHS) const { - return RHS <= *this; - } - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - void print(raw_ostream &OS) const; - - void dump() const; -#endif -}; - -/// \brief Compute the values of each DAG node for an ILP metric. -/// -/// This metric assumes that the DAG is a forest of trees with roots at the -/// bottom of the schedule. -class ScheduleDAGILP { - bool IsBottomUp; - std::vector<ILPValue> ILPValues; - -public: - ScheduleDAGILP(bool IsBU): IsBottomUp(IsBU) {} - - /// \brief Initialize the result data with the size of the DAG. - void resize(unsigned NumSUnits); - - /// \brief Compute the ILP metric for the subDAG at this root. - void computeILP(const SUnit *Root); - - /// \brief Get the ILP value for a DAG node. - ILPValue getILP(const SUnit *SU); -}; - -raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val); - -} // namespace llvm - -#endif diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h index 4bcd35a..2219520 100644 --- a/include/llvm/CodeGen/ScheduleDAGInstrs.h +++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -12,20 +12,18 @@ // //===----------------------------------------------------------------------===// -#ifndef SCHEDULEDAGINSTRS_H -#define SCHEDULEDAGINSTRS_H +#ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H +#define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H -#include "llvm/CodeGen/MachineDominators.h" -#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/ADT/SparseSet.h" +#include "llvm/ADT/SparseMultiSet.h" #include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/CodeGen/TargetSchedule.h" #include "llvm/Support/Compiler.h" #include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/SparseSet.h" -#include <map> namespace llvm { + class MachineFrameInfo; class MachineLoopInfo; class MachineDominatorTree; class LiveIntervals; @@ -48,56 +46,18 @@ namespace llvm { struct PhysRegSUOper { SUnit *SU; int OpIdx; + unsigned Reg; - PhysRegSUOper(SUnit *su, int op): SU(su), OpIdx(op) {} - }; - - /// Combine a SparseSet with a 1x1 vector to track physical registers. - /// The SparseSet allows iterating over the (few) live registers for quickly - /// comparing against a regmask or clearing the set. - /// - /// Storage for the map is allocated once for the pass. The map can be - /// cleared between scheduling regions without freeing unused entries. - class Reg2SUnitsMap { - SparseSet<unsigned> PhysRegSet; - std::vector<std::vector<PhysRegSUOper> > SUnits; - public: - typedef SparseSet<unsigned>::const_iterator const_iterator; - - // Allow iteration over register numbers (keys) in the map. If needed, we - // can provide an iterator over SUnits (values) as well. - const_iterator reg_begin() const { return PhysRegSet.begin(); } - const_iterator reg_end() const { return PhysRegSet.end(); } - - /// Initialize the map with the number of registers. - /// If the map is already large enough, no allocation occurs. - /// For simplicity we expect the map to be empty(). - void setRegLimit(unsigned Limit); + PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {} - /// Returns true if the map is empty. - bool empty() const { return PhysRegSet.empty(); } - - /// Clear the map without deallocating storage. - void clear(); - - bool contains(unsigned Reg) const { return PhysRegSet.count(Reg); } - - /// If this register is mapped, return its existing SUnits vector. - /// Otherwise map the register and return an empty SUnits vector. - std::vector<PhysRegSUOper> &operator[](unsigned Reg) { - bool New = PhysRegSet.insert(Reg).second; - assert((!New || SUnits[Reg].empty()) && "stale SUnits vector"); - (void)New; - return SUnits[Reg]; - } - - /// Erase an existing element without freeing memory. - void erase(unsigned Reg) { - PhysRegSet.erase(Reg); - SUnits[Reg].clear(); - } + unsigned getSparseSetIndex() const { return Reg; } }; + /// Use a SparseMultiSet to track physical registers. Storage is only + /// allocated once for the pass. It can be cleared in constant time and reused + /// without any frees. + typedef SparseMultiSet<PhysRegSUOper, llvm::identity<unsigned>, uint16_t> Reg2SUnitsMap; + /// Use SparseSet as a SparseMap by relying on the fact that it never /// compares ValueT's, only unsigned keys. This allows the set to be cleared /// between scheduling regions in constant time as long as ValueT does not diff --git a/include/llvm/CodeGen/ScheduleDFS.h b/include/llvm/CodeGen/ScheduleDFS.h new file mode 100644 index 0000000..73ce99f --- /dev/null +++ b/include/llvm/CodeGen/ScheduleDFS.h @@ -0,0 +1,196 @@ +//===- ScheduleDAGILP.h - ILP metric for ScheduleDAGInstrs ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Definition of an ILP metric for machine level instruction scheduling. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_SCHEDULEDFS_H +#define LLVM_CODEGEN_SCHEDULEDFS_H + +#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/Support/DataTypes.h" +#include <vector> + +namespace llvm { + +class raw_ostream; +class IntEqClasses; +class ScheduleDAGInstrs; +class SUnit; + +/// \brief Represent the ILP of the subDAG rooted at a DAG node. +/// +/// ILPValues summarize the DAG subtree rooted at each node. ILPValues are +/// valid for all nodes regardless of their subtree membership. +/// +/// When computed using bottom-up DFS, this metric assumes that the DAG is a +/// forest of trees with roots at the bottom of the schedule branching upward. +struct ILPValue { + unsigned InstrCount; + /// Length may either correspond to depth or height, depending on direction, + /// and cycles or nodes depending on context. + unsigned Length; + + ILPValue(unsigned count, unsigned length): + InstrCount(count), Length(length) {} + + // Order by the ILP metric's value. + bool operator<(ILPValue RHS) const { + return (uint64_t)InstrCount * RHS.Length + < (uint64_t)Length * RHS.InstrCount; + } + bool operator>(ILPValue RHS) const { + return RHS < *this; + } + bool operator<=(ILPValue RHS) const { + return (uint64_t)InstrCount * RHS.Length + <= (uint64_t)Length * RHS.InstrCount; + } + bool operator>=(ILPValue RHS) const { + return RHS <= *this; + } + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + void print(raw_ostream &OS) const; + + void dump() const; +#endif +}; + +/// \brief Compute the values of each DAG node for various metrics during DFS. +class SchedDFSResult { + friend class SchedDFSImpl; + + static const unsigned InvalidSubtreeID = ~0u; + + /// \brief Per-SUnit data computed during DFS for various metrics. + /// + /// A node's SubtreeID is set to itself when it is visited to indicate that it + /// is the root of a subtree. Later it is set to its parent to indicate an + /// interior node. Finally, it is set to a representative subtree ID during + /// finalization. + struct NodeData { + unsigned InstrCount; + unsigned SubtreeID; + + NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {} + }; + + /// \brief Per-Subtree data computed during DFS. + struct TreeData { + unsigned ParentTreeID; + unsigned SubInstrCount; + + TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {} + }; + + /// \brief Record a connection between subtrees and the connection level. + struct Connection { + unsigned TreeID; + unsigned Level; + + Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {} + }; + + bool IsBottomUp; + unsigned SubtreeLimit; + /// DFS results for each SUnit in this DAG. + std::vector<NodeData> DFSNodeData; + + // Store per-tree data indexed on tree ID, + SmallVector<TreeData, 16> DFSTreeData; + + // For each subtree discovered during DFS, record its connections to other + // subtrees. + std::vector<SmallVector<Connection, 4> > SubtreeConnections; + + /// Cache the current connection level of each subtree. + /// This mutable array is updated during scheduling. + std::vector<unsigned> SubtreeConnectLevels; + +public: + SchedDFSResult(bool IsBU, unsigned lim) + : IsBottomUp(IsBU), SubtreeLimit(lim) {} + + /// \brief Get the node cutoff before subtrees are considered significant. + unsigned getSubtreeLimit() const { return SubtreeLimit; } + + /// \brief Return true if this DFSResult is uninitialized. + /// + /// resize() initializes DFSResult, while compute() populates it. + bool empty() const { return DFSNodeData.empty(); } + + /// \brief Clear the results. + void clear() { + DFSNodeData.clear(); + DFSTreeData.clear(); + SubtreeConnections.clear(); + SubtreeConnectLevels.clear(); + } + + /// \brief Initialize the result data with the size of the DAG. + void resize(unsigned NumSUnits) { + DFSNodeData.resize(NumSUnits); + } + + /// \brief Compute various metrics for the DAG with given roots. + void compute(ArrayRef<SUnit> SUnits); + + /// \brief Get the number of instructions in the given subtree and its + /// children. + unsigned getNumInstrs(const SUnit *SU) const { + return DFSNodeData[SU->NodeNum].InstrCount; + } + + /// \brief Get the number of instructions in the given subtree not including + /// children. + unsigned getNumSubInstrs(unsigned SubtreeID) const { + return DFSTreeData[SubtreeID].SubInstrCount; + } + + /// \brief Get the ILP value for a DAG node. + /// + /// A leaf node has an ILP of 1/1. + ILPValue getILP(const SUnit *SU) const { + return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth()); + } + + /// \brief The number of subtrees detected in this DAG. + unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); } + + /// \brief Get the ID of the subtree the given DAG node belongs to. + /// + /// For convenience, if DFSResults have not been computed yet, give everything + /// tree ID 0. + unsigned getSubtreeID(const SUnit *SU) const { + if (empty()) + return 0; + assert(SU->NodeNum < DFSNodeData.size() && "New Node"); + return DFSNodeData[SU->NodeNum].SubtreeID; + } + + /// \brief Get the connection level of a subtree. + /// + /// For bottom-up trees, the connection level is the latency depth (in cycles) + /// of the deepest connection to another subtree. + unsigned getSubtreeLevel(unsigned SubtreeID) const { + return SubtreeConnectLevels[SubtreeID]; + } + + /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is + /// initially scheduled. + void scheduleTree(unsigned SubtreeID); +}; + +raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val); + +} // namespace llvm + +#endif diff --git a/include/llvm/CodeGen/SchedulerRegistry.h b/include/llvm/CodeGen/SchedulerRegistry.h index 836b73a..51ac7f2 100644 --- a/include/llvm/CodeGen/SchedulerRegistry.h +++ b/include/llvm/CodeGen/SchedulerRegistry.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGENSCHEDULERREGISTRY_H -#define LLVM_CODEGENSCHEDULERREGISTRY_H +#ifndef LLVM_CODEGEN_SCHEDULERREGISTRY_H +#define LLVM_CODEGEN_SCHEDULERREGISTRY_H #include "llvm/CodeGen/MachinePassRegistry.h" #include "llvm/Target/TargetMachine.h" diff --git a/include/llvm/CodeGen/ScoreboardHazardRecognizer.h b/include/llvm/CodeGen/ScoreboardHazardRecognizer.h index 060e89a..c2103fb 100644 --- a/include/llvm/CodeGen/ScoreboardHazardRecognizer.h +++ b/include/llvm/CodeGen/ScoreboardHazardRecognizer.h @@ -18,7 +18,6 @@ #include "llvm/CodeGen/ScheduleHazardRecognizer.h" #include "llvm/Support/DataTypes.h" - #include <cassert> #include <cstring> diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h index 619ee69..e5adf67 100644 --- a/include/llvm/CodeGen/SelectionDAG.h +++ b/include/llvm/CodeGen/SelectionDAG.h @@ -15,16 +15,17 @@ #ifndef LLVM_CODEGEN_SELECTIONDAG_H #define LLVM_CODEGEN_SELECTIONDAG_H -#include "llvm/ADT/ilist.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/StringMap.h" +#include "llvm/ADT/ilist.h" +#include "llvm/CodeGen/DAGCombine.h" #include "llvm/CodeGen/SelectionDAGNodes.h" #include "llvm/Support/RecyclingAllocator.h" #include "llvm/Target/TargetMachine.h" #include <cassert> -#include <vector> #include <map> #include <string> +#include <vector> namespace llvm { @@ -36,6 +37,7 @@ class SDNodeOrdering; class SDDbgValue; class TargetLowering; class TargetSelectionDAGInfo; +class TargetTransformInfo; template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> { private: @@ -111,13 +113,6 @@ public: DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); } }; -enum CombineLevel { - BeforeLegalizeTypes, - AfterLegalizeTypes, - AfterLegalizeVectorOps, - AfterLegalizeDAG -}; - class SelectionDAG; void checkForCycles(const SDNode *N); void checkForCycles(const SelectionDAG *DAG); @@ -137,6 +132,7 @@ class SelectionDAG { const TargetMachine &TM; const TargetLowering &TLI; const TargetSelectionDAGInfo &TSI; + const TargetTransformInfo *TTI; MachineFunction *MF; LLVMContext *Context; CodeGenOpt::Level OptLevel; @@ -232,7 +228,7 @@ public: /// init - Prepare this SelectionDAG to process code in the given /// MachineFunction. /// - void init(MachineFunction &mf); + void init(MachineFunction &mf, const TargetTransformInfo *TTI); /// clear - Clear state and free memory necessary to make this /// SelectionDAG ready to process a new block. @@ -243,6 +239,7 @@ public: const TargetMachine &getTarget() const { return TM; } const TargetLowering &getTargetLoweringInfo() const { return TLI; } const TargetSelectionDAGInfo &getSelectionDAGInfo() const { return TSI; } + const TargetTransformInfo *getTargetTransformInfo() const { return TTI; } LLVMContext *getContext() const {return Context; } /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. @@ -570,7 +567,7 @@ public: SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, const SDValue *Ops, unsigned NumOps); SDValue getNode(unsigned Opcode, DebugLoc DL, - const std::vector<EVT> &ResultTys, + ArrayRef<EVT> ResultTys, const SDValue *Ops, unsigned NumOps); SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs, const SDValue *Ops, unsigned NumOps); @@ -834,7 +831,7 @@ public: MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps); MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, - const std::vector<EVT> &ResultTys, const SDValue *Ops, + ArrayRef<EVT> ResultTys, const SDValue *Ops, unsigned NumOps); MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs, const SDValue *Ops, unsigned NumOps); @@ -938,6 +935,20 @@ public: } } + /// Returns an APFloat semantics tag appropriate for the given type. If VT is + /// a vector type, the element semantics are returned. + static const fltSemantics &EVTToAPFloatSemantics(EVT VT) { + switch (VT.getScalarType().getSimpleVT().SimpleTy) { + default: llvm_unreachable("Unknown FP format"); + case MVT::f16: return APFloat::IEEEhalf; + case MVT::f32: return APFloat::IEEEsingle; + case MVT::f64: return APFloat::IEEEdouble; + case MVT::f80: return APFloat::x87DoubleExtended; + case MVT::f128: return APFloat::IEEEquad; + case MVT::ppcf128: return APFloat::PPCDoubleDouble; + } + } + /// AssignOrdering - Assign an order to the SDNode. void AssignOrdering(const SDNode *SD, unsigned Order); @@ -981,10 +992,8 @@ public: SDValue CreateStackTemporary(EVT VT1, EVT VT2); /// FoldConstantArithmetic - - SDValue FoldConstantArithmetic(unsigned Opcode, - EVT VT, - ConstantSDNode *Cst1, - ConstantSDNode *Cst2); + SDValue FoldConstantArithmetic(unsigned Opcode, EVT VT, + SDNode *Cst1, SDNode *Cst2); /// FoldSetCC - Constant fold a setcc to true or false. SDValue FoldSetCC(EVT VT, SDValue N1, diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index c42f655..5f503de 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -12,13 +12,13 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_SELECTIONDAG_ISEL_H -#define LLVM_CODEGEN_SELECTIONDAG_ISEL_H +#ifndef LLVM_CODEGEN_SELECTIONDAGISEL_H +#define LLVM_CODEGEN_SELECTIONDAGISEL_H -#include "llvm/BasicBlock.h" -#include "llvm/Pass.h" -#include "llvm/CodeGen/SelectionDAG.h" #include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/Pass.h" namespace llvm { class FastISel; @@ -31,6 +31,7 @@ namespace llvm { class TargetLowering; class TargetLibraryInfo; class TargetInstrInfo; + class TargetTransformInfo; class FunctionLoweringInfo; class ScheduleHazardRecognizer; class GCFunctionInfo; @@ -44,6 +45,7 @@ public: const TargetMachine &TM; const TargetLowering &TLI; const TargetLibraryInfo *LibInfo; + const TargetTransformInfo *TTI; FunctionLoweringInfo *FuncInfo; MachineFunction *MF; MachineRegisterInfo *RegInfo; @@ -247,16 +249,26 @@ private: const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo); void PrepareEHLandingPad(); + + /// \brief Perform instruction selection on all basic blocks in the function. void SelectAllBasicBlocks(const Function &Fn); - bool TryToFoldFastISelLoad(const LoadInst *LI, const Instruction *FoldInst, - FastISel *FastIS); - void FinishBasicBlock(); + /// \brief Perform instruction selection on a single basic block, for + /// instructions between \p Begin and \p End. \p HadTailCall will be set + /// to true if a call in the block was translated as a tail call. void SelectBasicBlock(BasicBlock::const_iterator Begin, BasicBlock::const_iterator End, bool &HadTailCall); + + bool TryToFoldFastISelLoad(const LoadInst *LI, const Instruction *FoldInst, + FastISel *FastIS); + void FinishBasicBlock(); + void CodeGenAndEmitDAG(); - void LowerArguments(const BasicBlock *BB); + + /// \brief Generate instructions for lowering the incoming arguments of the + /// given function. + void LowerArguments(const Function &F); void ComputeLiveOutVRegInfo(); @@ -279,4 +291,4 @@ private: } -#endif /* LLVM_CODEGEN_SELECTIONDAG_ISEL_H */ +#endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */ diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 362e9af..fef567f 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -19,20 +19,20 @@ #ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H #define LLVM_CODEGEN_SELECTIONDAGNODES_H -#include "llvm/Constants.h" -#include "llvm/Instructions.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/ilist_node.h" #include "llvm/CodeGen/ISDOpcodes.h" -#include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/MachineMemOperand.h" -#include "llvm/Support/MathExtras.h" +#include "llvm/CodeGen/ValueTypes.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Instructions.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/DebugLoc.h" +#include "llvm/Support/MathExtras.h" #include <cassert> namespace llvm { @@ -49,7 +49,7 @@ template <typename T> struct simplify_type; template <typename T> struct ilist_traits; void checkForCycles(const SDNode *N); - + /// SDVTList - This represents a list of ValueType's that has been intern'd by /// a SelectionDAG. Instances of this simple value class are returned by /// SelectionDAG::getVTList(...). @@ -108,7 +108,7 @@ public: void setNode(SDNode *N) { Node = N; } inline SDNode *operator->() const { return Node; } - + bool operator==(const SDValue &O) const { return Node == O.Node && ResNo == O.ResNo; } @@ -130,6 +130,11 @@ public: /// inline EVT getValueType() const; + /// Return the simple ValueType of the referenced return value. + MVT getSimpleValueType() const { + return getValueType().getSimpleVT(); + } + /// getValueSizeInBits - Returns the size of the value in bits. /// unsigned getValueSizeInBits() const { @@ -191,14 +196,14 @@ template <> struct isPodLike<SDValue> { static const bool value = true; }; /// SDValues as if they were SDNode*'s. template<> struct simplify_type<SDValue> { typedef SDNode* SimpleType; - static SimpleType getSimplifiedValue(const SDValue &Val) { - return static_cast<SimpleType>(Val.getNode()); + static SimpleType getSimplifiedValue(SDValue &Val) { + return Val.getNode(); } }; template<> struct simplify_type<const SDValue> { - typedef SDNode* SimpleType; + typedef /*const*/ SDNode* SimpleType; static SimpleType getSimplifiedValue(const SDValue &Val) { - return static_cast<SimpleType>(Val.getNode()); + return Val.getNode(); } }; @@ -290,14 +295,8 @@ private: /// SDValues as if they were SDNode*'s. template<> struct simplify_type<SDUse> { typedef SDNode* SimpleType; - static SimpleType getSimplifiedValue(const SDUse &Val) { - return static_cast<SimpleType>(Val.getNode()); - } -}; -template<> struct simplify_type<const SDUse> { - typedef SDNode* SimpleType; - static SimpleType getSimplifiedValue(const SDUse &Val) { - return static_cast<SimpleType>(Val.getNode()); + static SimpleType getSimplifiedValue(SDUse &Val) { + return Val.getNode(); } }; @@ -525,7 +524,7 @@ public: /// NOTE: This is still very expensive. Use carefully. bool hasPredecessorHelper(const SDNode *N, SmallPtrSet<const SDNode *, 32> &Visited, - SmallVector<const SDNode *, 16> &Worklist) const; + SmallVector<const SDNode *, 16> &Worklist) const; /// getNumOperands - Return the number of values used by this operation. /// @@ -595,6 +594,12 @@ public: return ValueList[ResNo]; } + /// Return the type of a specified result as a simple type. + /// + MVT getSimpleValueType(unsigned ResNo) const { + return getValueType(ResNo).getSimpleVT(); + } + /// getValueSizeInBits - Returns MVT::getSizeInBits(getValueType(ResNo)). /// unsigned getValueSizeInBits(unsigned ResNo) const { @@ -1287,7 +1292,7 @@ class ConstantPoolSDNode : public SDNode { : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) { - assert((int)Offset >= 0 && "Offset is too large"); + assert(Offset >= 0 && "Offset is too large"); Val.ConstVal = c; } ConstantPoolSDNode(bool isTarget, MachineConstantPoolValue *v, @@ -1295,7 +1300,7 @@ class ConstantPoolSDNode : public SDNode { : SDNode(isTarget ? ISD::TargetConstantPool : ISD::ConstantPool, DebugLoc(), getSDVTList(VT)), Offset(o), Alignment(Align), TargetFlags(TF) { - assert((int)Offset >= 0 && "Offset is too large"); + assert(Offset >= 0 && "Offset is too large"); Val.MachineCPVal = v; Offset |= 1 << (sizeof(unsigned)*CHAR_BIT-1); } @@ -1303,7 +1308,7 @@ public: bool isMachineConstantPoolEntry() const { - return (int)Offset < 0; + return Offset < 0; } const Constant *getConstVal() const { diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index c52599b..a277080 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -19,13 +19,14 @@ #ifndef LLVM_CODEGEN_SLOTINDEXES_H #define LLVM_CODEGEN_SLOTINDEXES_H -#include "llvm/CodeGen/MachineInstrBundle.h" -#include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IntervalMap.h" #include "llvm/ADT/PointerIntPair.h" -#include "llvm/ADT/ilist.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ilist.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstrBundle.h" #include "llvm/Support/Allocator.h" namespace llvm { @@ -111,7 +112,7 @@ namespace llvm { return lie.getPointer(); } - int getIndex() const { + unsigned getIndex() const { return listEntry()->getIndex() | getSlot(); } @@ -359,6 +360,11 @@ namespace llvm { /// Renumber the index list, providing space for new instructions. void renumberIndexes(); + /// Repair indexes after adding and removing instructions. + void repairIndexesInRange(MachineBasicBlock *MBB, + MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End); + /// Returns the zero index for this analysis. SlotIndex getZeroIndex() { assert(indexList.front().getIndex() == 0 && "First index is not 0?"); @@ -390,12 +396,16 @@ namespace llvm { return index.isValid() ? index.listEntry()->getInstr() : 0; } - /// Returns the next non-null index. - SlotIndex getNextNonNullIndex(SlotIndex index) { - IndexList::iterator itr(index.listEntry()); - ++itr; - while (itr != indexList.end() && itr->getInstr() == 0) { ++itr; } - return SlotIndex(itr, index.getSlot()); + /// Returns the next non-null index, if one exists. + /// Otherwise returns getLastIndex(). + SlotIndex getNextNonNullIndex(SlotIndex Index) { + IndexList::iterator I = Index.listEntry(); + IndexList::iterator E = indexList.end(); + while (++I != E) + if (I->getInstr()) + return SlotIndex(I, Index.getSlot()); + // We reached the end of the function. + return getLastIndex(); } /// getIndexBefore - Returns the index of the last indexed instruction @@ -601,29 +611,35 @@ namespace llvm { void insertMBBInMaps(MachineBasicBlock *mbb) { MachineFunction::iterator nextMBB = llvm::next(MachineFunction::iterator(mbb)); - IndexListEntry *startEntry = createEntry(0, 0); - IndexListEntry *stopEntry = createEntry(0, 0); - IndexListEntry *nextEntry = 0; + IndexListEntry *startEntry = 0; + IndexListEntry *endEntry = 0; + IndexList::iterator newItr; if (nextMBB == mbb->getParent()->end()) { - nextEntry = indexList.end(); + startEntry = &indexList.back(); + endEntry = createEntry(0, 0); + newItr = indexList.insertAfter(startEntry, endEntry); } else { - nextEntry = getMBBStartIdx(nextMBB).listEntry(); + startEntry = createEntry(0, 0); + endEntry = getMBBStartIdx(nextMBB).listEntry(); + newItr = indexList.insert(endEntry, startEntry); } - indexList.insert(nextEntry, startEntry); - indexList.insert(nextEntry, stopEntry); - SlotIndex startIdx(startEntry, SlotIndex::Slot_Block); - SlotIndex endIdx(nextEntry, SlotIndex::Slot_Block); + SlotIndex endIdx(endEntry, SlotIndex::Slot_Block); + + MachineFunction::iterator prevMBB(mbb); + assert(prevMBB != mbb->getParent()->end() && + "Can't insert a new block at the beginning of a function."); + --prevMBB; + MBBRanges[prevMBB->getNumber()].second = startIdx; assert(unsigned(mbb->getNumber()) == MBBRanges.size() && "Blocks must be added in order"); MBBRanges.push_back(std::make_pair(startIdx, endIdx)); - idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb)); - renumberIndexes(); + renumberIndexes(newItr); std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare()); } @@ -631,17 +647,8 @@ 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; - } + template <> + struct IntervalMapInfo<SlotIndex> : IntervalMapHalfOpenInfo<SlotIndex> { }; } diff --git a/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h b/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h index 9849e92..e7098e4 100644 --- a/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h +++ b/include/llvm/CodeGen/TargetLoweringObjectFileImpl.h @@ -15,9 +15,9 @@ #ifndef LLVM_CODEGEN_TARGETLOWERINGOBJECTFILEIMPL_H #define LLVM_CODEGEN_TARGETLOWERINGOBJECTFILEIMPL_H +#include "llvm/ADT/StringRef.h" #include "llvm/MC/SectionKind.h" #include "llvm/Target/TargetLoweringObjectFile.h" -#include "llvm/ADT/StringRef.h" namespace llvm { class MachineModuleInfo; @@ -55,13 +55,12 @@ public: SelectSectionForGlobal(const GlobalValue *GV, SectionKind Kind, Mangler *Mang, const TargetMachine &TM) const; - /// getExprForDwarfGlobalReference - Return an MCExpr to use for a reference - /// to the specified global variable from exception handling information. - /// + /// getTTypeGlobalReference - Return an MCExpr to use for a reference to the + /// specified type info global variable from exception handling information. virtual const MCExpr * - getExprForDwarfGlobalReference(const GlobalValue *GV, Mangler *Mang, - MachineModuleInfo *MMI, unsigned Encoding, - MCStreamer &Streamer) const; + getTTypeGlobalReference(const GlobalValue *GV, Mangler *Mang, + MachineModuleInfo *MMI, unsigned Encoding, + MCStreamer &Streamer) const; // getCFIPersonalitySymbol - The symbol that gets passed to .cfi_personality. virtual MCSymbol * @@ -103,12 +102,12 @@ public: virtual bool shouldEmitUsedDirectiveFor(const GlobalValue *GV, Mangler *) const; - /// getExprForDwarfGlobalReference - The mach-o version of this method + /// getTTypeGlobalReference - The mach-o version of this method /// defaults to returning a stub reference. virtual const MCExpr * - getExprForDwarfGlobalReference(const GlobalValue *GV, Mangler *Mang, - MachineModuleInfo *MMI, unsigned Encoding, - MCStreamer &Streamer) const; + getTTypeGlobalReference(const GlobalValue *GV, Mangler *Mang, + MachineModuleInfo *MMI, unsigned Encoding, + MCStreamer &Streamer) const; // getCFIPersonalitySymbol - The symbol that gets passed to .cfi_personality. virtual MCSymbol * diff --git a/include/llvm/CodeGen/TargetSchedule.h b/include/llvm/CodeGen/TargetSchedule.h index 88e6105..3e22252 100644 --- a/include/llvm/CodeGen/TargetSchedule.h +++ b/include/llvm/CodeGen/TargetSchedule.h @@ -13,13 +13,13 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_TARGET_TARGETSCHEDMODEL_H -#define LLVM_TARGET_TARGETSCHEDMODEL_H +#ifndef LLVM_CODEGEN_TARGETSCHEDULE_H +#define LLVM_CODEGEN_TARGETSCHEDULE_H -#include "llvm/Target/TargetSubtargetInfo.h" -#include "llvm/MC/MCSchedule.h" -#include "llvm/MC/MCInstrItineraries.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/MC/MCInstrItineraries.h" +#include "llvm/MC/MCSchedule.h" +#include "llvm/Target/TargetSubtargetInfo.h" namespace llvm { @@ -84,6 +84,9 @@ public: /// \brief Maximum number of micro-ops that may be scheduled per cycle. unsigned getIssueWidth() const { return SchedModel.IssueWidth; } + /// \brief Number of cycles the OOO processor is expected to hide. + unsigned getILPWindow() const { return SchedModel.ILPWindow; } + /// \brief Return the number of issue slots required for this MI. unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC = 0) const; diff --git a/include/llvm/CodeGen/ValueTypes.h b/include/llvm/CodeGen/ValueTypes.h index 2401992..ec48b67 100644 --- a/include/llvm/CodeGen/ValueTypes.h +++ b/include/llvm/CodeGen/ValueTypes.h @@ -33,6 +33,10 @@ namespace llvm { class MVT { public: enum SimpleValueType { + // INVALID_SIMPLE_VALUE_TYPE - Simple value types less than zero are + // considered extended value types. + INVALID_SIMPLE_VALUE_TYPE = -1, + // If you change this numbering, you must change the values in // ValueTypes.td as well! Other = 0, // This is a non-standard value @@ -60,52 +64,61 @@ namespace llvm { v4i1 = 14, // 4 x i1 v8i1 = 15, // 8 x i1 v16i1 = 16, // 16 x i1 - v2i8 = 17, // 2 x i8 - v4i8 = 18, // 4 x i8 - v8i8 = 19, // 8 x i8 - v16i8 = 20, // 16 x i8 - v32i8 = 21, // 32 x i8 - v1i16 = 22, // 1 x i16 - v2i16 = 23, // 2 x i16 - v4i16 = 24, // 4 x i16 - v8i16 = 25, // 8 x i16 - v16i16 = 26, // 16 x i16 - v1i32 = 27, // 1 x i32 - v2i32 = 28, // 2 x i32 - v4i32 = 29, // 4 x i32 - v8i32 = 30, // 8 x i32 - v16i32 = 31, // 16 x i32 - v1i64 = 32, // 1 x i64 - v2i64 = 33, // 2 x i64 - v4i64 = 34, // 4 x i64 - v8i64 = 35, // 8 x i64 - v16i64 = 36, // 16 x i64 - - v2f16 = 37, // 2 x f16 - v2f32 = 38, // 2 x f32 - v4f32 = 39, // 4 x f32 - v8f32 = 40, // 8 x f32 - v2f64 = 41, // 2 x f64 - v4f64 = 42, // 4 x f64 + v32i1 = 17, // 32 x i1 + v64i1 = 18, // 64 x i1 + + v2i8 = 19, // 2 x i8 + v4i8 = 20, // 4 x i8 + v8i8 = 21, // 8 x i8 + v16i8 = 22, // 16 x i8 + v32i8 = 23, // 32 x i8 + v64i8 = 24, // 64 x i8 + v1i16 = 25, // 1 x i16 + v2i16 = 26, // 2 x i16 + v4i16 = 27, // 4 x i16 + v8i16 = 28, // 8 x i16 + v16i16 = 29, // 16 x i16 + v32i16 = 30, // 32 x i16 + v1i32 = 31, // 1 x i32 + v2i32 = 32, // 2 x i32 + v4i32 = 33, // 4 x i32 + v8i32 = 34, // 8 x i32 + v16i32 = 35, // 16 x i32 + v1i64 = 36, // 1 x i64 + v2i64 = 37, // 2 x i64 + v4i64 = 38, // 4 x i64 + v8i64 = 39, // 8 x i64 + v16i64 = 40, // 16 x i64 - FIRST_VECTOR_VALUETYPE = v2i1, - LAST_VECTOR_VALUETYPE = v4f64, FIRST_INTEGER_VECTOR_VALUETYPE = v2i1, LAST_INTEGER_VECTOR_VALUETYPE = v16i64, + + v2f16 = 41, // 2 x f16 + v2f32 = 42, // 2 x f32 + v4f32 = 43, // 4 x f32 + v8f32 = 44, // 8 x f32 + v16f32 = 45, // 16 x f32 + v2f64 = 46, // 2 x f64 + v4f64 = 47, // 4 x f64 + v8f64 = 48, // 8 x f64 + FIRST_FP_VECTOR_VALUETYPE = v2f16, - LAST_FP_VECTOR_VALUETYPE = v4f64, + LAST_FP_VECTOR_VALUETYPE = v8f64, - x86mmx = 43, // This is an X86 MMX value + FIRST_VECTOR_VALUETYPE = v2i1, + LAST_VECTOR_VALUETYPE = v8f64, + + x86mmx = 49, // This is an X86 MMX value - Glue = 44, // This glues nodes together during pre-RA sched + Glue = 50, // This glues nodes together during pre-RA sched - isVoid = 45, // This has no value + isVoid = 51, // This has no value - Untyped = 46, // This value takes a register, but has + Untyped = 52, // This value takes a register, but has // unspecified type. The register class // will be determined by the opcode. - LAST_VALUETYPE = 47, // This always remains at the end of the list. + LAST_VALUETYPE = 53, // This always remains at the end of the list. // This is the current maximum for LAST_VALUETYPE. // MVT::MAX_ALLOWED_VALUETYPE is used for asserts and to size bit vectors @@ -137,14 +150,7 @@ namespace llvm { // iPTR - An int value the size of the pointer of the current // target. This should only be used internal to tblgen! - iPTR = 255, - - // LastSimpleValueType - The greatest valid SimpleValueType value. - LastSimpleValueType = 255, - - // INVALID_SIMPLE_VALUE_TYPE - Simple value types greater than or equal - // to this are considered extended value types. - INVALID_SIMPLE_VALUE_TYPE = LastSimpleValueType + 1 + iPTR = 255 }; SimpleValueType SimpleTy; @@ -216,7 +222,9 @@ namespace llvm { /// is512BitVector - Return true if this is a 512-bit vector type. bool is512BitVector() const { - return (SimpleTy == MVT::v8i64 || SimpleTy == MVT::v16i32); + return (SimpleTy == MVT::v8f64 || SimpleTy == MVT::v16f32 || + SimpleTy == MVT::v64i8 || SimpleTy == MVT::v32i16 || + SimpleTy == MVT::v8i64 || SimpleTy == MVT::v16i32); } /// is1024BitVector - Return true if this is a 1024-bit vector type. @@ -254,17 +262,21 @@ namespace llvm { case v2i1 : case v4i1 : case v8i1 : - case v16i1: return i1; + case v16i1 : + case v32i1 : + case v64i1: return i1; case v2i8 : case v4i8 : case v8i8 : case v16i8: - case v32i8: return i8; + case v32i8: + case v64i8: return i8; case v1i16: case v2i16: case v4i16: case v8i16: - case v16i16: return i16; + case v16i16: + case v32i16: return i16; case v1i32: case v2i32: case v4i32: @@ -278,9 +290,11 @@ namespace llvm { case v2f16: return f16; case v2f32: case v4f32: - case v8f32: return f32; + case v8f32: + case v16f32: return f32; case v2f64: - case v4f64: return f64; + case v4f64: + case v8f64: return f64; } } @@ -288,18 +302,24 @@ namespace llvm { switch (SimpleTy) { default: llvm_unreachable("Not a vector MVT!"); - case v32i8: return 32; + case v32i1: + case v32i8: + case v32i16: return 32; + case v64i1: + case v64i8: return 64; case v16i1: case v16i8: case v16i16: case v16i32: - case v16i64:return 16; - case v8i1: + case v16i64: + case v16f32: return 16; + case v8i1 : case v8i8 : case v8i16: case v8i32: case v8i64: - case v8f32: return 8; + case v8f32: + case v8f64: return 8; case v4i1: case v4i8: case v4i16: @@ -328,7 +348,10 @@ namespace llvm { case iPTRAny: case iAny: case fAny: + case vAny: llvm_unreachable("Value type is overloaded."); + case Metadata: + llvm_unreachable("Value type is metadata."); default: llvm_unreachable("getSizeInBits called on extended MVT."); case i1 : return 1; @@ -343,13 +366,15 @@ namespace llvm { case v1i16: return 16; case f32 : case i32 : + case v32i1: case v4i8: case v2i16: - case v2f16: + case v2f16: case v1i32: return 32; case x86mmx: case f64 : case i64 : + case v64i1: case v8i8: case v4i16: case v2i32: @@ -371,8 +396,12 @@ namespace llvm { case v4i64: case v8f32: case v4f64: return 256; + case v64i8: + case v32i16: case v16i32: - case v8i64: return 512; + case v8i64: + case v16f32: + case v8f64: return 512; case v16i64:return 1024; } } @@ -389,6 +418,27 @@ namespace llvm { return getStoreSize() * 8; } + /// Return true if this has more bits than VT. + bool bitsGT(MVT VT) const { + return getSizeInBits() > VT.getSizeInBits(); + } + + /// Return true if this has no less bits than VT. + bool bitsGE(MVT VT) const { + return getSizeInBits() >= VT.getSizeInBits(); + } + + /// Return true if this has less bits than VT. + bool bitsLT(MVT VT) const { + return getSizeInBits() < VT.getSizeInBits(); + } + + /// Return true if this has no more bits than VT. + bool bitsLE(MVT VT) const { + return getSizeInBits() <= VT.getSizeInBits(); + } + + static MVT getFloatingPointVT(unsigned BitWidth) { switch (BitWidth) { default: @@ -434,6 +484,8 @@ namespace llvm { if (NumElements == 4) return MVT::v4i1; if (NumElements == 8) return MVT::v8i1; if (NumElements == 16) return MVT::v16i1; + if (NumElements == 32) return MVT::v32i1; + if (NumElements == 64) return MVT::v64i1; break; case MVT::i8: if (NumElements == 2) return MVT::v2i8; @@ -441,6 +493,7 @@ namespace llvm { if (NumElements == 8) return MVT::v8i8; if (NumElements == 16) return MVT::v16i8; if (NumElements == 32) return MVT::v32i8; + if (NumElements == 64) return MVT::v64i8; break; case MVT::i16: if (NumElements == 1) return MVT::v1i16; @@ -448,6 +501,7 @@ namespace llvm { if (NumElements == 4) return MVT::v4i16; if (NumElements == 8) return MVT::v8i16; if (NumElements == 16) return MVT::v16i16; + if (NumElements == 32) return MVT::v32i16; break; case MVT::i32: if (NumElements == 1) return MVT::v1i32; @@ -470,14 +524,22 @@ namespace llvm { if (NumElements == 2) return MVT::v2f32; if (NumElements == 4) return MVT::v4f32; if (NumElements == 8) return MVT::v8f32; + if (NumElements == 16) return MVT::v16f32; break; case MVT::f64: if (NumElements == 2) return MVT::v2f64; if (NumElements == 4) return MVT::v4f64; + if (NumElements == 8) return MVT::v8f64; break; } return (MVT::SimpleValueType)(MVT::INVALID_SIMPLE_VALUE_TYPE); } + + /// Return the value type corresponding to the specified type. This returns + /// all pointers as iPTR. If HandleUnknown is true, unknown types are + /// returned as Other, otherwise they are invalid. + static MVT getVT(Type *Ty, bool HandleUnknown = false); + }; @@ -501,7 +563,7 @@ namespace llvm { bool operator!=(EVT VT) const { if (V.SimpleTy != VT.V.SimpleTy) return true; - if (V.SimpleTy == MVT::INVALID_SIMPLE_VALUE_TYPE) + if (V.SimpleTy < 0) return LLVMTy != VT.LLVMTy; return false; } @@ -517,7 +579,7 @@ namespace llvm { /// number of bits. static EVT getIntegerVT(LLVMContext &Context, unsigned BitWidth) { MVT M = MVT::getIntegerVT(BitWidth); - if (M.SimpleTy != MVT::INVALID_SIMPLE_VALUE_TYPE) + if (M.SimpleTy >= 0) return M; return getExtendedIntegerVT(Context, BitWidth); } @@ -526,7 +588,7 @@ namespace llvm { /// length, where each element is of type VT. static EVT getVectorVT(LLVMContext &Context, EVT VT, unsigned NumElements) { MVT M = MVT::getVectorVT(VT.V, NumElements); - if (M.SimpleTy != MVT::INVALID_SIMPLE_VALUE_TYPE) + if (M.SimpleTy >= 0) return M; return getExtendedVectorVT(Context, VT, NumElements); } @@ -541,7 +603,7 @@ namespace llvm { unsigned BitWidth = EltTy.getSizeInBits(); MVT IntTy = MVT::getIntegerVT(BitWidth); MVT VecTy = MVT::getVectorVT(IntTy, getVectorNumElements()); - assert(VecTy != MVT::INVALID_SIMPLE_VALUE_TYPE && + assert(VecTy.SimpleTy >= 0 && "Simple vector VT not representable by simple integer vector VT!"); return VecTy; } @@ -549,7 +611,7 @@ namespace llvm { /// isSimple - Test if the given EVT is simple (as opposed to being /// extended). bool isSimple() const { - return V.SimpleTy <= MVT::LastSimpleValueType; + return V.SimpleTy >= 0; } /// isExtended - Test if the given EVT is extended (as opposed to @@ -765,7 +827,7 @@ namespace llvm { /// types are returned as Other, otherwise they are invalid. static EVT getEVT(Type *Ty, bool HandleUnknown = false); - intptr_t getRawBits() { + intptr_t getRawBits() const { if (isSimple()) return V.SimpleTy; else diff --git a/include/llvm/CodeGen/ValueTypes.td b/include/llvm/CodeGen/ValueTypes.td index a707f88..76df6ac 100644 --- a/include/llvm/CodeGen/ValueTypes.td +++ b/include/llvm/CodeGen/ValueTypes.td @@ -37,39 +37,45 @@ def v2i1 : ValueType<2 , 13>; // 2 x i1 vector value def v4i1 : ValueType<4 , 14>; // 4 x i1 vector value def v8i1 : ValueType<8 , 15>; // 8 x i1 vector value def v16i1 : ValueType<16, 16>; // 16 x i1 vector value -def v2i8 : ValueType<16 , 17>; // 2 x i8 vector value -def v4i8 : ValueType<32 , 18>; // 4 x i8 vector value -def v8i8 : ValueType<64 , 19>; // 8 x i8 vector value -def v16i8 : ValueType<128, 20>; // 16 x i8 vector value -def v32i8 : ValueType<256, 21>; // 32 x i8 vector value -def v1i16 : ValueType<16 , 22>; // 1 x i16 vector value -def v2i16 : ValueType<32 , 23>; // 2 x i16 vector value -def v4i16 : ValueType<64 , 24>; // 4 x i16 vector value -def v8i16 : ValueType<128, 25>; // 8 x i16 vector value -def v16i16 : ValueType<256, 26>; // 16 x i16 vector value -def v1i32 : ValueType<32 , 27>; // 1 x i32 vector value -def v2i32 : ValueType<64 , 28>; // 2 x i32 vector value -def v4i32 : ValueType<128, 29>; // 4 x i32 vector value -def v8i32 : ValueType<256, 30>; // 8 x i32 vector value -def v16i32 : ValueType<512, 31>; // 16 x i32 vector value -def v1i64 : ValueType<64 , 32>; // 1 x i64 vector value -def v2i64 : ValueType<128, 33>; // 2 x i64 vector value -def v4i64 : ValueType<256, 34>; // 4 x i64 vector value -def v8i64 : ValueType<512, 35>; // 8 x i64 vector value -def v16i64 : ValueType<1024,36>; // 16 x i64 vector value +def v32i1 : ValueType<32 , 17>; // 32 x i1 vector value +def v64i1 : ValueType<64 , 18>; // 64 x i1 vector value +def v2i8 : ValueType<16 , 19>; // 2 x i8 vector value +def v4i8 : ValueType<32 , 20>; // 4 x i8 vector value +def v8i8 : ValueType<64 , 21>; // 8 x i8 vector value +def v16i8 : ValueType<128, 22>; // 16 x i8 vector value +def v32i8 : ValueType<256, 23>; // 32 x i8 vector value +def v64i8 : ValueType<256, 24>; // 64 x i8 vector value +def v1i16 : ValueType<16 , 25>; // 1 x i16 vector value +def v2i16 : ValueType<32 , 26>; // 2 x i16 vector value +def v4i16 : ValueType<64 , 27>; // 4 x i16 vector value +def v8i16 : ValueType<128, 28>; // 8 x i16 vector value +def v16i16 : ValueType<256, 29>; // 16 x i16 vector value +def v32i16 : ValueType<256, 30>; // 32 x i16 vector value +def v1i32 : ValueType<32 , 31>; // 1 x i32 vector value +def v2i32 : ValueType<64 , 32>; // 2 x i32 vector value +def v4i32 : ValueType<128, 33>; // 4 x i32 vector value +def v8i32 : ValueType<256, 34>; // 8 x i32 vector value +def v16i32 : ValueType<512, 35>; // 16 x i32 vector value +def v1i64 : ValueType<64 , 36>; // 1 x i64 vector value +def v2i64 : ValueType<128, 37>; // 2 x i64 vector value +def v4i64 : ValueType<256, 38>; // 4 x i64 vector value +def v8i64 : ValueType<512, 39>; // 8 x i64 vector value +def v16i64 : ValueType<1024,40>; // 16 x i64 vector value -def v2f16 : ValueType<32 , 37>; // 2 x f16 vector value -def v2f32 : ValueType<64 , 38>; // 2 x f32 vector value -def v4f32 : ValueType<128, 39>; // 4 x f32 vector value -def v8f32 : ValueType<256, 40>; // 8 x f32 vector value -def v2f64 : ValueType<128, 41>; // 2 x f64 vector value -def v4f64 : ValueType<256, 42>; // 4 x f64 vector value +def v2f16 : ValueType<32 , 41>; // 2 x f16 vector value +def v2f32 : ValueType<64 , 42>; // 2 x f32 vector value +def v4f32 : ValueType<128, 43>; // 4 x f32 vector value +def v8f32 : ValueType<256, 44>; // 8 x f32 vector value +def v16f32 : ValueType<512, 45>; // 16 x f32 vector value +def v2f64 : ValueType<128, 46>; // 2 x f64 vector value +def v4f64 : ValueType<256, 47>; // 4 x f64 vector value +def v8f64 : ValueType<512, 48>; // 8 x f64 vector value -def x86mmx : ValueType<64 , 43>; // X86 MMX value -def FlagVT : ValueType<0 , 44>; // Pre-RA sched glue -def isVoid : ValueType<0 , 45>; // Produces no value -def untyped: ValueType<8 , 46>; // Produces an untyped value +def x86mmx : ValueType<64 , 49>; // X86 MMX value +def FlagVT : ValueType<0 , 50>; // Pre-RA sched glue +def isVoid : ValueType<0 , 51>; // Produces no value +def untyped: ValueType<8 , 52>; // Produces an untyped value def MetadataVT: ValueType<0, 250>; // Metadata // Pseudo valuetype mapped to the current pointer size to any address space. diff --git a/include/llvm/CodeGen/VirtRegMap.h b/include/llvm/CodeGen/VirtRegMap.h new file mode 100644 index 0000000..3bc6ebd --- /dev/null +++ b/include/llvm/CodeGen/VirtRegMap.h @@ -0,0 +1,190 @@ +//===-- llvm/CodeGen/VirtRegMap.h - Virtual Register Map -*- C++ -*--------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a virtual register map. This maps virtual registers to +// physical registers and virtual registers to stack slots. It is created and +// updated by a register allocator and then used by a machine code rewriter that +// adds spill code and rewrites virtual into physical register references. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_VIRTREGMAP_H +#define LLVM_CODEGEN_VIRTREGMAP_H + +#include "llvm/ADT/IndexedMap.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/Target/TargetRegisterInfo.h" + +namespace llvm { + class MachineInstr; + class MachineFunction; + class MachineRegisterInfo; + class TargetInstrInfo; + class raw_ostream; + class SlotIndexes; + + class VirtRegMap : public MachineFunctionPass { + public: + enum { + NO_PHYS_REG = 0, + NO_STACK_SLOT = (1L << 30)-1, + MAX_STACK_SLOT = (1L << 18)-1 + }; + + private: + MachineRegisterInfo *MRI; + const TargetInstrInfo *TII; + const TargetRegisterInfo *TRI; + MachineFunction *MF; + + /// Virt2PhysMap - This is a virtual to physical register + /// mapping. Each virtual register is required to have an entry in + /// it; even spilled virtual registers (the register mapped to a + /// spilled register is the temporary used to load it from the + /// stack). + IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap; + + /// Virt2StackSlotMap - This is virtual register to stack slot + /// mapping. Each spilled virtual register has an entry in it + /// which corresponds to the stack slot this register is spilled + /// at. + IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap; + + /// Virt2SplitMap - This is virtual register to splitted virtual register + /// mapping. + IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2SplitMap; + + /// createSpillSlot - Allocate a spill slot for RC from MFI. + unsigned createSpillSlot(const TargetRegisterClass *RC); + + VirtRegMap(const VirtRegMap&) LLVM_DELETED_FUNCTION; + void operator=(const VirtRegMap&) LLVM_DELETED_FUNCTION; + + public: + static char ID; + VirtRegMap() : MachineFunctionPass(ID), Virt2PhysMap(NO_PHYS_REG), + Virt2StackSlotMap(NO_STACK_SLOT), Virt2SplitMap(0) { } + virtual bool runOnMachineFunction(MachineFunction &MF); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + MachineFunction &getMachineFunction() const { + assert(MF && "getMachineFunction called before runOnMachineFunction"); + return *MF; + } + + MachineRegisterInfo &getRegInfo() const { return *MRI; } + const TargetRegisterInfo &getTargetRegInfo() const { return *TRI; } + + void grow(); + + /// @brief returns true if the specified virtual register is + /// mapped to a physical register + bool hasPhys(unsigned virtReg) const { + return getPhys(virtReg) != NO_PHYS_REG; + } + + /// @brief returns the physical register mapped to the specified + /// virtual register + unsigned getPhys(unsigned virtReg) const { + assert(TargetRegisterInfo::isVirtualRegister(virtReg)); + return Virt2PhysMap[virtReg]; + } + + /// @brief creates a mapping for the specified virtual register to + /// the specified physical register + void assignVirt2Phys(unsigned virtReg, unsigned physReg) { + assert(TargetRegisterInfo::isVirtualRegister(virtReg) && + TargetRegisterInfo::isPhysicalRegister(physReg)); + assert(Virt2PhysMap[virtReg] == NO_PHYS_REG && + "attempt to assign physical register to already mapped " + "virtual register"); + Virt2PhysMap[virtReg] = physReg; + } + + /// @brief clears the specified virtual register's, physical + /// register mapping + void clearVirt(unsigned virtReg) { + assert(TargetRegisterInfo::isVirtualRegister(virtReg)); + assert(Virt2PhysMap[virtReg] != NO_PHYS_REG && + "attempt to clear a not assigned virtual register"); + Virt2PhysMap[virtReg] = NO_PHYS_REG; + } + + /// @brief clears all virtual to physical register mappings + void clearAllVirt() { + Virt2PhysMap.clear(); + grow(); + } + + /// @brief returns true if VirtReg is assigned to its preferred physreg. + bool hasPreferredPhys(unsigned VirtReg); + + /// @brief returns true if VirtReg has a known preferred register. + /// This returns false if VirtReg has a preference that is a virtual + /// register that hasn't been assigned yet. + bool hasKnownPreference(unsigned VirtReg); + + /// @brief records virtReg is a split live interval from SReg. + void setIsSplitFromReg(unsigned virtReg, unsigned SReg) { + Virt2SplitMap[virtReg] = SReg; + } + + /// @brief returns the live interval virtReg is split from. + unsigned getPreSplitReg(unsigned virtReg) const { + return Virt2SplitMap[virtReg]; + } + + /// getOriginal - Return the original virtual register that VirtReg descends + /// from through splitting. + /// A register that was not created by splitting is its own original. + /// This operation is idempotent. + unsigned getOriginal(unsigned VirtReg) const { + unsigned Orig = getPreSplitReg(VirtReg); + return Orig ? Orig : VirtReg; + } + + /// @brief returns true if the specified virtual register is not + /// mapped to a stack slot or rematerialized. + bool isAssignedReg(unsigned virtReg) const { + if (getStackSlot(virtReg) == NO_STACK_SLOT) + return true; + // Split register can be assigned a physical register as well as a + // stack slot or remat id. + return (Virt2SplitMap[virtReg] && Virt2PhysMap[virtReg] != NO_PHYS_REG); + } + + /// @brief returns the stack slot mapped to the specified virtual + /// register + int getStackSlot(unsigned virtReg) const { + assert(TargetRegisterInfo::isVirtualRegister(virtReg)); + return Virt2StackSlotMap[virtReg]; + } + + /// @brief create a mapping for the specifed virtual register to + /// the next available stack slot + int assignVirt2StackSlot(unsigned virtReg); + /// @brief create a mapping for the specified virtual register to + /// the specified stack slot + void assignVirt2StackSlot(unsigned virtReg, int frameIndex); + + void print(raw_ostream &OS, const Module* M = 0) const; + void dump() const; + }; + + inline raw_ostream &operator<<(raw_ostream &OS, const VirtRegMap &VRM) { + VRM.print(OS); + return OS; + } +} // End llvm namespace + +#endif |
