diff options
Diffstat (limited to 'include/llvm/CodeGen')
68 files changed, 2683 insertions, 913 deletions
diff --git a/include/llvm/CodeGen/Analysis.h b/include/llvm/CodeGen/Analysis.h index 0b609ed..81e75d8 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,12 +86,9 @@ ISD::CondCode getICmpCondCode(ICmpInst::Predicate Pred); /// between it and the return. /// /// This function only tests target-independent requirements. -bool isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, +bool isInTailCallPosition(ImmutableCallSite CS, Attribute CalleeRetAttr, const TargetLowering &TLI); -bool isInTailCallPosition(SelectionDAG &DAG, SDNode *Node, - SDValue &Chain, const TargetLowering &TLI); - } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/AsmPrinter.h b/include/llvm/CodeGen/AsmPrinter.h index 2920675..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" @@ -48,7 +48,7 @@ namespace llvm { class DwarfException; class Mangler; class TargetLoweringObjectFile; - class TargetData; + class DataLayout; class TargetMachine; /// AsmPrinter - This class is intended to be used as a driving class for all @@ -131,8 +131,8 @@ namespace llvm { /// getObjFileLowering - Return information about object file lowering. const TargetLoweringObjectFile &getObjFileLowering() const; - /// getTargetData - Return information about data layout. - const TargetData &getTargetData() const; + /// getDataLayout - Return information about data layout. + const DataLayout &getDataLayout() const; /// getCurrentSection() - Return the current section we are emitting to. const MCSection *getCurrentSection() const; @@ -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 3afe309..c035e07 100644 --- a/include/llvm/CodeGen/CallingConvLower.h +++ b/include/llvm/CodeGen/CallingConvLower.h @@ -16,10 +16,11 @@ #define LLVM_CODEGEN_CALLINGCONVLOWER_H #include "llvm/ADT/SmallVector.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; @@ -49,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; @@ -288,6 +289,7 @@ public: StackOffset = ((StackOffset + Align-1) & ~(Align-1)); unsigned Result = StackOffset; StackOffset += Size; + MF.getFrameInfo()->ensureMaxAlignment(Align); return Result; } diff --git a/include/llvm/CodeGen/CommandFlags.h b/include/llvm/CodeGen/CommandFlags.h new file mode 100644 index 0000000..a66e05b --- /dev/null +++ b/include/llvm/CodeGen/CommandFlags.h @@ -0,0 +1,227 @@ +//===-- CommandFlags.h - Command Line Flags Interface -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains codegen-specific flags that are shared between different +// command line tools. The tools "llc" and "opt" both use this file to prevent +// flag duplication. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_COMMAND_LINE_FLAGS_H +#define LLVM_CODEGEN_COMMAND_LINE_FLAGS_H + +#include "llvm/Support/CodeGen.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Target/TargetMachine.h" +#include <string> +using namespace llvm; + +cl::opt<std::string> +MArch("march", cl::desc("Architecture to generate code for (see --version)")); + +cl::opt<std::string> +MCPU("mcpu", + cl::desc("Target a specific cpu type (-mcpu=help for details)"), + cl::value_desc("cpu-name"), + cl::init("")); + +cl::list<std::string> +MAttrs("mattr", + cl::CommaSeparated, + cl::desc("Target specific attributes (-mattr=help for details)"), + cl::value_desc("a1,+a2,-a3,...")); + +cl::opt<Reloc::Model> +RelocModel("relocation-model", + cl::desc("Choose relocation model"), + cl::init(Reloc::Default), + cl::values( + clEnumValN(Reloc::Default, "default", + "Target default relocation model"), + clEnumValN(Reloc::Static, "static", + "Non-relocatable code"), + clEnumValN(Reloc::PIC_, "pic", + "Fully relocatable, position independent code"), + clEnumValN(Reloc::DynamicNoPIC, "dynamic-no-pic", + "Relocatable external references, non-relocatable code"), + clEnumValEnd)); + +cl::opt<llvm::CodeModel::Model> +CMModel("code-model", + cl::desc("Choose code model"), + cl::init(CodeModel::Default), + cl::values(clEnumValN(CodeModel::Default, "default", + "Target default code model"), + clEnumValN(CodeModel::Small, "small", + "Small code model"), + clEnumValN(CodeModel::Kernel, "kernel", + "Kernel code model"), + clEnumValN(CodeModel::Medium, "medium", + "Medium code model"), + clEnumValN(CodeModel::Large, "large", + "Large code model"), + clEnumValEnd)); + +cl::opt<bool> +RelaxAll("mc-relax-all", + cl::desc("When used with filetype=obj, " + "relax all fixups in the emitted object file")); + +cl::opt<TargetMachine::CodeGenFileType> +FileType("filetype", cl::init(TargetMachine::CGFT_AssemblyFile), + cl::desc("Choose a file type (not all types are supported by all targets):"), + cl::values( + clEnumValN(TargetMachine::CGFT_AssemblyFile, "asm", + "Emit an assembly ('.s') file"), + clEnumValN(TargetMachine::CGFT_ObjectFile, "obj", + "Emit a native object ('.o') file"), + clEnumValN(TargetMachine::CGFT_Null, "null", + "Emit nothing, for performance testing"), + clEnumValEnd)); + +cl::opt<bool> DisableDotLoc("disable-dot-loc", cl::Hidden, + cl::desc("Do not use .loc entries")); + +cl::opt<bool> DisableCFI("disable-cfi", cl::Hidden, + cl::desc("Do not use .cfi_* directives")); + +cl::opt<bool> EnableDwarfDirectory("enable-dwarf-directory", cl::Hidden, + cl::desc("Use .file directives with an explicit directory.")); + +cl::opt<bool> +DisableRedZone("disable-red-zone", + cl::desc("Do not emit code that uses the red zone."), + cl::init(false)); + +cl::opt<bool> +EnableFPMAD("enable-fp-mad", + cl::desc("Enable less precise MAD instructions to be generated"), + cl::init(false)); + +cl::opt<bool> +DisableFPElim("disable-fp-elim", + cl::desc("Disable frame pointer elimination optimization"), + cl::init(false)); + +cl::opt<bool> +DisableFPElimNonLeaf("disable-non-leaf-fp-elim", + cl::desc("Disable frame pointer elimination optimization for non-leaf funcs"), + cl::init(false)); + +cl::opt<bool> +EnableUnsafeFPMath("enable-unsafe-fp-math", + cl::desc("Enable optimizations that may decrease FP precision"), + cl::init(false)); + +cl::opt<bool> +EnableNoInfsFPMath("enable-no-infs-fp-math", + cl::desc("Enable FP math optimizations that assume no +-Infs"), + cl::init(false)); + +cl::opt<bool> +EnableNoNaNsFPMath("enable-no-nans-fp-math", + cl::desc("Enable FP math optimizations that assume no NaNs"), + cl::init(false)); + +cl::opt<bool> +EnableHonorSignDependentRoundingFPMath("enable-sign-dependent-rounding-fp-math", + cl::Hidden, + cl::desc("Force codegen to assume rounding mode can change dynamically"), + cl::init(false)); + +cl::opt<bool> +GenerateSoftFloatCalls("soft-float", + cl::desc("Generate software floating point library calls"), + cl::init(false)); + +cl::opt<llvm::FloatABI::ABIType> +FloatABIForCalls("float-abi", + cl::desc("Choose float ABI type"), + cl::init(FloatABI::Default), + cl::values( + clEnumValN(FloatABI::Default, "default", + "Target default float ABI type"), + clEnumValN(FloatABI::Soft, "soft", + "Soft float ABI (implied by -soft-float)"), + clEnumValN(FloatABI::Hard, "hard", + "Hard float ABI (uses FP registers)"), + clEnumValEnd)); + +cl::opt<llvm::FPOpFusion::FPOpFusionMode> +FuseFPOps("fp-contract", + cl::desc("Enable aggresive formation of fused FP ops"), + cl::init(FPOpFusion::Standard), + cl::values( + clEnumValN(FPOpFusion::Fast, "fast", + "Fuse FP ops whenever profitable"), + clEnumValN(FPOpFusion::Standard, "on", + "Only fuse 'blessed' FP ops."), + clEnumValN(FPOpFusion::Strict, "off", + "Only fuse FP ops when the result won't be effected."), + clEnumValEnd)); + +cl::opt<bool> +DontPlaceZerosInBSS("nozero-initialized-in-bss", + cl::desc("Don't place zero-initialized symbols into bss section"), + cl::init(false)); + +cl::opt<bool> +EnableGuaranteedTailCallOpt("tailcallopt", + cl::desc("Turn fastcc calls into tail calls by (potentially) changing ABI."), + cl::init(false)); + +cl::opt<bool> +DisableTailCalls("disable-tail-calls", + cl::desc("Never emit tail calls"), + cl::init(false)); + +cl::opt<unsigned> +OverrideStackAlignment("stack-alignment", + cl::desc("Override default stack alignment"), + cl::init(0)); + +cl::opt<bool> +EnableRealignStack("realign-stack", + cl::desc("Realign stack if needed"), + cl::init(true)); + +cl::opt<std::string> +TrapFuncName("trap-func", cl::Hidden, + cl::desc("Emit a call to trap function rather than a trap instruction"), + cl::init("")); + +cl::opt<bool> +EnablePIE("enable-pie", + cl::desc("Assume the creation of a position independent executable."), + cl::init(false)); + +cl::opt<bool> +SegmentedStacks("segmented-stacks", + cl::desc("Use segmented stacks if possible."), + cl::init(false)); + +cl::opt<bool> +UseInitArray("use-init-array", + cl::desc("Use .init_array instead of .ctors."), + cl::init(false)); + +cl::opt<std::string> StopAfter("stop-after", + cl::desc("Stop compilation after a specific pass"), + cl::value_desc("pass-name"), + cl::init("")); +cl::opt<std::string> StartAfter("start-after", + cl::desc("Resume compilation after a specific pass"), + cl::value_desc("pass-name"), + cl::init("")); + +cl::opt<unsigned> +SSPBufferSize("stack-protector-buffer-size", cl::init(8), + cl::desc("Lower bound for a buffer to be considered for " + "stack protection")); +#endif diff --git a/include/llvm/CodeGen/DAGCombine.h b/include/llvm/CodeGen/DAGCombine.h new file mode 100644 index 0000000..8b59190 --- /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 7cb9695..0561905 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 { @@ -32,7 +32,7 @@ class MachineFunction; class MachineInstr; class MachineFrameInfo; class MachineRegisterInfo; -class TargetData; +class DataLayout; class TargetInstrInfo; class TargetLibraryInfo; class TargetLowering; @@ -54,7 +54,7 @@ protected: MachineConstantPool &MCP; DebugLoc DL; const TargetMachine &TM; - const TargetData &TD; + const DataLayout &TD; const TargetInstrInfo &TII; const TargetLowering &TLI; const TargetRegisterInfo &TRI; @@ -131,6 +131,10 @@ public: /// into the current block. void recomputeInsertPt(); + /// removeDeadCode - Remove all dead instructions between the I and E. + void removeDeadCode(MachineBasicBlock::iterator I, + MachineBasicBlock::iterator E); + struct SavePoint { MachineBasicBlock::iterator InsertPt; DebugLoc DL; @@ -395,10 +399,6 @@ private: /// hasTrivialKill - Test whether the given value has exactly one use. bool hasTrivialKill(const Value *V) const; - - /// removeDeadCode - Remove all dead instructions between the I and E. - void removeDeadCode(MachineBasicBlock::iterator I, - MachineBasicBlock::iterator E); }; } diff --git a/include/llvm/CodeGen/FunctionLoweringInfo.h b/include/llvm/CodeGen/FunctionLoweringInfo.h index 8cf22ec..72e0937 100644 --- a/include/llvm/CodeGen/FunctionLoweringInfo.h +++ b/include/llvm/CodeGen/FunctionLoweringInfo.h @@ -15,8 +15,6 @@ #ifndef LLVM_CODEGEN_FUNCTIONLOWERINGINFO_H #define LLVM_CODEGEN_FUNCTIONLOWERINGINFO_H -#include "llvm/InlineAsm.h" -#include "llvm/Instructions.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" @@ -24,9 +22,11 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/BranchProbabilityInfo.h" -#include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/ISDOpcodes.h" #include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/ValueTypes.h" +#include "llvm/IR/InlineAsm.h" +#include "llvm/IR/Instructions.h" #include "llvm/Support/CallSite.h" #include "llvm/Target/TargetRegisterInfo.h" #include <vector> @@ -136,7 +136,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 20e33f7..fa40049 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 { @@ -122,6 +122,11 @@ namespace llvm { Roots.push_back(GCRoot(Num, Metadata)); } + /// removeStackRoot - Removes a root. + roots_iterator removeStackRoot(roots_iterator position) { + return Roots.erase(position); + } + /// addSafePoint - Notes the existence of a safe point. Num is the ID of the /// label just prior to the safe point (if the code generator is using /// MachineModuleInfo). diff --git a/include/llvm/CodeGen/GCMetadataPrinter.h b/include/llvm/CodeGen/GCMetadataPrinter.h index 17a2653..4a6b5ac 100644 --- a/include/llvm/CodeGen/GCMetadataPrinter.h +++ b/include/llvm/CodeGen/GCMetadataPrinter.h @@ -48,9 +48,10 @@ namespace llvm { // May only be subclassed. GCMetadataPrinter(); - // Do not implement. - GCMetadataPrinter(const GCMetadataPrinter &); - GCMetadataPrinter &operator=(const GCMetadataPrinter &); + private: + GCMetadataPrinter(const GCMetadataPrinter &) LLVM_DELETED_FUNCTION; + GCMetadataPrinter & + operator=(const GCMetadataPrinter &) LLVM_DELETED_FUNCTION; public: GCStrategy &getStrategy() { return *S; } diff --git a/include/llvm/CodeGen/IntrinsicLowering.h b/include/llvm/CodeGen/IntrinsicLowering.h index 767b666..68389dd 100644 --- a/include/llvm/CodeGen/IntrinsicLowering.h +++ b/include/llvm/CodeGen/IntrinsicLowering.h @@ -16,20 +16,20 @@ #ifndef LLVM_CODEGEN_INTRINSICLOWERING_H #define LLVM_CODEGEN_INTRINSICLOWERING_H -#include "llvm/Intrinsics.h" +#include "llvm/IR/Intrinsics.h" namespace llvm { class CallInst; class Module; - class TargetData; + class DataLayout; class IntrinsicLowering { - const TargetData& TD; + const DataLayout& TD; bool Warned; public: - explicit IntrinsicLowering(const TargetData &td) : + explicit IntrinsicLowering(const DataLayout &td) : TD(td), Warned(false) {} /// AddPrototypes - This method, if called, causes all of the prototypes diff --git a/include/llvm/CodeGen/JITCodeEmitter.h b/include/llvm/CodeGen/JITCodeEmitter.h index 89f00e9..21a3f48 100644 --- a/include/llvm/CodeGen/JITCodeEmitter.h +++ b/include/llvm/CodeGen/JITCodeEmitter.h @@ -17,11 +17,11 @@ #ifndef LLVM_CODEGEN_JITCODEEMITTER_H #define LLVM_CODEGEN_JITCODEEMITTER_H -#include <string> +#include "llvm/ADT/DenseMap.h" +#include "llvm/CodeGen/MachineCodeEmitter.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/MathExtras.h" -#include "llvm/CodeGen/MachineCodeEmitter.h" -#include "llvm/ADT/DenseMap.h" +#include <string> namespace llvm { diff --git a/include/llvm/CodeGen/LexicalScopes.h b/include/llvm/CodeGen/LexicalScopes.h index 8414c64..3cb6b4d 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> diff --git a/include/llvm/CodeGen/LinkAllCodegenComponents.h b/include/llvm/CodeGen/LinkAllCodegenComponents.h index 46dd004..2145eb8 100644 --- a/include/llvm/CodeGen/LinkAllCodegenComponents.h +++ b/include/llvm/CodeGen/LinkAllCodegenComponents.h @@ -15,9 +15,9 @@ #ifndef LLVM_CODEGEN_LINKALLCODEGENCOMPONENTS_H #define LLVM_CODEGEN_LINKALLCODEGENCOMPONENTS_H +#include "llvm/CodeGen/GCs.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/SchedulerRegistry.h" -#include "llvm/CodeGen/GCs.h" #include "llvm/Target/TargetMachine.h" #include <cstdlib> diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h index 5aeb1a8..9576075 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> @@ -114,9 +114,6 @@ namespace llvm { void dump() const; void print(raw_ostream &os) const; - - private: - LiveRange(); // DO NOT IMPLEMENT }; template <> struct isPodLike<LiveRange> { static const bool value = true; }; @@ -276,11 +273,6 @@ namespace llvm { void MergeValueInAsValue(const LiveInterval &RHS, const VNInfo *RHSValNo, VNInfo *LHSValNo); - /// Copy - Copy the specified live interval. This copies all the fields - /// except for the register of the interval. - void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI, - VNInfo::Allocator &VNInfoAllocator); - bool empty() const { return ranges.empty(); } /// beginIndex - Return the lowest numbered slot covered by interval. @@ -313,12 +305,6 @@ namespace llvm { return r != end() && r->end == index; } - /// killedInRange - Return true if the interval has kills in [Start,End). - /// Note that the kill point is considered the end of a live range, so it is - /// not contained in the live range. If a live range ends at End, it won't - /// be counted as a kill by this method. - bool killedInRange(SlotIndex Start, SlotIndex End) const; - /// getLiveRangeContaining - Return the live range that contains the /// specified index, or null if there is none. const LiveRange *getLiveRangeContaining(SlotIndex Idx) const { @@ -478,7 +464,7 @@ namespace llvm { VNInfo *LHSValNo = 0, const VNInfo *RHSValNo = 0); - LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT + LiveInterval& operator=(const LiveInterval& rhs) LLVM_DELETED_FUNCTION; }; @@ -510,7 +496,9 @@ namespace llvm { if (I == E) return; // Is this an instruction live-in segment? - if (SlotIndex::isEarlierInstr(I->start, Idx)) { + // If Idx is the start index of a basic block, include live-in segments + // that start at Idx.getBaseIndex(). + if (I->start <= Idx.getBaseIndex()) { EarlyVal = I->valno; EndPoint = I->end; // Move to the potentially live-out segment. @@ -519,6 +507,12 @@ namespace llvm { if (++I == E) return; } + // Special case: A PHIDef value can have its def in the middle of a + // segment if the value happens to be live out of the layout + // predecessor. + // Such a value is not live-in. + if (EarlyVal->def == Idx.getBaseIndex()) + EarlyVal = 0; } // I now points to the segment that may be live-through, or defined by // this instr. Ignore segments starting after the current instr. diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index bf74690..9e89519 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -20,16 +20,16 @@ #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H -#include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/CodeGen/MachineBasicBlock.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/LiveInterval.h" -#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/SlotIndexes.h" #include "llvm/Support/Allocator.h" +#include "llvm/Target/TargetRegisterInfo.h" #include <cmath> #include <iterator> @@ -65,12 +65,6 @@ namespace llvm { /// Live interval pointers for all the virtual registers. IndexedMap<LiveInterval*, VirtReg2IndexFunctor> VirtRegIntervals; - /// AllocatableRegs - A bit vector of allocatable registers. - BitVector AllocatableRegs; - - /// ReservedRegs - A bit vector of reserved registers. - BitVector ReservedRegs; - /// RegMaskSlots - Sorted list of instructions with register mask operands. /// Always use the 'r' slot, RegMasks are normal clobbers, not early /// clobbers. @@ -123,18 +117,6 @@ namespace llvm { return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; } - /// isAllocatable - is the physical register reg allocatable in the current - /// function? - bool isAllocatable(unsigned reg) const { - return AllocatableRegs.test(reg); - } - - /// isReserved - is the physical register reg reserved in the current - /// function - bool isReserved(unsigned reg) const { - return ReservedRegs.test(reg); - } - // Interval creation. LiveInterval &getOrCreateInterval(unsigned Reg) { if (!hasInterval(Reg)) { @@ -165,6 +147,26 @@ namespace llvm { bool shrinkToUses(LiveInterval *li, SmallVectorImpl<MachineInstr*> *dead = 0); + /// extendToIndices - Extend the live range of LI to reach all points in + /// Indices. The points in the Indices array must be jointly dominated by + /// existing defs in LI. PHI-defs are added as needed to maintain SSA form. + /// + /// If a SlotIndex in Indices is the end index of a basic block, LI will be + /// extended to be live out of the basic block. + /// + /// See also LiveRangeCalc::extend(). + void extendToIndices(LiveInterval *LI, ArrayRef<SlotIndex> Indices); + + /// pruneValue - If an LI value is live at Kill, prune its live range by + /// removing any liveness reachable from Kill. Add live range end points to + /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the + /// value's live range. + /// + /// Calling pruneValue() and extendToIndices() can be used to reconstruct + /// SSA form after adding defs to a virtual register. + void pruneValue(LiveInterval *LI, SlotIndex Kill, + SmallVectorImpl<SlotIndex> *EndPoints); + SlotIndexes *getSlotIndexes() const { return Indexes; } @@ -258,15 +260,20 @@ namespace llvm { /// instruction 'mi' has been moved within a basic block. This will update /// the live intervals for all operands of mi. Moves between basic blocks /// are not supported. - void handleMove(MachineInstr* MI); + /// + /// \param UpdateFlags Update live intervals for nonallocatable physregs. + void handleMove(MachineInstr* MI, bool UpdateFlags = false); /// moveIntoBundle - Update intervals for operands of MI so that they /// begin/end on the SlotIndex for BundleStart. /// + /// \param UpdateFlags Update live intervals for nonallocatable physregs. + /// /// Requires MI and BundleStart to have SlotIndexes, and assumes /// existing liveness is accurate. BundleStart should be the first /// instruction in the Bundle. - void handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart); + void handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart, + bool UpdateFlags = false); // Register mask functions. // @@ -340,6 +347,10 @@ namespace llvm { return RegUnitIntervals[Unit]; } + const LiveInterval *getCachedRegUnit(unsigned Unit) const { + return RegUnitIntervals[Unit]; + } + private: /// computeIntervals - Compute live intervals. void computeIntervals(); diff --git a/include/llvm/CodeGen/LiveIntervalUnion.h b/include/llvm/CodeGen/LiveIntervalUnion.h new file mode 100644 index 0000000..6a61614 --- /dev/null +++ b/include/llvm/CodeGen/LiveIntervalUnion.h @@ -0,0 +1,205 @@ +//===-- LiveIntervalUnion.h - Live interval union data struct --*- C++ -*--===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// LiveIntervalUnion is a union of live segments across multiple live virtual +// registers. This may be used during coalescing to represent a congruence +// class, or during register allocation to model liveness of a physical +// register. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_LIVEINTERVALUNION +#define LLVM_CODEGEN_LIVEINTERVALUNION + +#include "llvm/ADT/IntervalMap.h" +#include "llvm/CodeGen/LiveInterval.h" + +namespace llvm { + +class TargetRegisterInfo; + +#ifndef NDEBUG +// forward declaration +template <unsigned Element> class SparseBitVector; +typedef SparseBitVector<128> LiveVirtRegBitSet; +#endif + +/// Compare a live virtual register segment to a LiveIntervalUnion segment. +inline bool +overlap(const LiveRange &VRSeg, + const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) { + return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end; +} + +/// Union of live intervals that are strong candidates for coalescing into a +/// single register (either physical or virtual depending on the context). We +/// expect the constituent live intervals to be disjoint, although we may +/// eventually make exceptions to handle value-based interference. +class LiveIntervalUnion { + // A set of live virtual register segments that supports fast insertion, + // intersection, and removal. + // Mapping SlotIndex intervals to virtual register numbers. + typedef IntervalMap<SlotIndex, LiveInterval*> LiveSegments; + +public: + // SegmentIter can advance to the next segment ordered by starting position + // which may belong to a different live virtual register. We also must be able + // to reach the current segment's containing virtual register. + typedef LiveSegments::iterator SegmentIter; + + // LiveIntervalUnions share an external allocator. + typedef LiveSegments::Allocator Allocator; + + class Query; + +private: + unsigned Tag; // unique tag for current contents. + LiveSegments Segments; // union of virtual reg segments + +public: + explicit LiveIntervalUnion(Allocator &a) : Tag(0), Segments(a) {} + + // Iterate over all segments in the union of live virtual registers ordered + // by their starting position. + SegmentIter begin() { return Segments.begin(); } + SegmentIter end() { return Segments.end(); } + SegmentIter find(SlotIndex x) { return Segments.find(x); } + bool empty() const { return Segments.empty(); } + SlotIndex startIndex() const { return Segments.start(); } + + // Provide public access to the underlying map to allow overlap iteration. + typedef LiveSegments Map; + const Map &getMap() { return Segments; } + + /// getTag - Return an opaque tag representing the current state of the union. + unsigned getTag() const { return Tag; } + + /// changedSince - Return true if the union change since getTag returned tag. + bool changedSince(unsigned tag) const { return tag != Tag; } + + // Add a live virtual register to this union and merge its segments. + void unify(LiveInterval &VirtReg); + + // Remove a live virtual register's segments from this union. + void extract(LiveInterval &VirtReg); + + // Remove all inserted virtual registers. + void clear() { Segments.clear(); ++Tag; } + + // Print union, using TRI to translate register names + void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const; + +#ifndef NDEBUG + // Verify the live intervals in this union and add them to the visited set. + void verify(LiveVirtRegBitSet& VisitedVRegs); +#endif + + /// Query interferences between a single live virtual register and a live + /// interval union. + class Query { + LiveIntervalUnion *LiveUnion; + LiveInterval *VirtReg; + LiveInterval::iterator VirtRegI; // current position in VirtReg + SegmentIter LiveUnionI; // current position in LiveUnion + SmallVector<LiveInterval*,4> InterferingVRegs; + bool CheckedFirstInterference; + bool SeenAllInterferences; + bool SeenUnspillableVReg; + unsigned Tag, UserTag; + + public: + Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {} + + Query(LiveInterval *VReg, LiveIntervalUnion *LIU): + LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false), + SeenAllInterferences(false), SeenUnspillableVReg(false) + {} + + void clear() { + LiveUnion = NULL; + VirtReg = NULL; + InterferingVRegs.clear(); + CheckedFirstInterference = false; + SeenAllInterferences = false; + SeenUnspillableVReg = false; + Tag = 0; + UserTag = 0; + } + + void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) { + assert(VReg && LIU && "Invalid arguments"); + if (UserTag == UTag && VirtReg == VReg && + LiveUnion == LIU && !LIU->changedSince(Tag)) { + // Retain cached results, e.g. firstInterference. + return; + } + clear(); + LiveUnion = LIU; + VirtReg = VReg; + Tag = LIU->getTag(); + UserTag = UTag; + } + + LiveInterval &virtReg() const { + assert(VirtReg && "uninitialized"); + return *VirtReg; + } + + // Does this live virtual register interfere with the union? + bool checkInterference() { return collectInterferingVRegs(1); } + + // Count the virtual registers in this union that interfere with this + // query's live virtual register, up to maxInterferingRegs. + unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX); + + // Was this virtual register visited during collectInterferingVRegs? + bool isSeenInterference(LiveInterval *VReg) const; + + // Did collectInterferingVRegs collect all interferences? + bool seenAllInterferences() const { return SeenAllInterferences; } + + // Did collectInterferingVRegs encounter an unspillable vreg? + bool seenUnspillableVReg() const { return SeenUnspillableVReg; } + + // Vector generated by collectInterferingVRegs. + const SmallVectorImpl<LiveInterval*> &interferingVRegs() const { + return InterferingVRegs; + } + + private: + Query(const Query&) LLVM_DELETED_FUNCTION; + void operator=(const Query&) LLVM_DELETED_FUNCTION; + }; + + // Array of LiveIntervalUnions. + class Array { + unsigned Size; + LiveIntervalUnion *LIUs; + public: + Array() : Size(0), LIUs(0) {} + ~Array() { clear(); } + + // Initialize the array to have Size entries. + // Reuse an existing allocation if the size matches. + void init(LiveIntervalUnion::Allocator&, unsigned Size); + + unsigned size() const { return Size; } + + void clear(); + + LiveIntervalUnion& operator[](unsigned idx) { + assert(idx < Size && "idx out of bounds"); + return LIUs[idx]; + } + }; +}; + +} // end namespace llvm + +#endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION) diff --git a/include/llvm/CodeGen/LiveRegMatrix.h b/include/llvm/CodeGen/LiveRegMatrix.h new file mode 100644 index 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..a3b1855 100644 --- a/include/llvm/CodeGen/LiveStackAnalysis.h +++ b/include/llvm/CodeGen/LiveStackAnalysis.h @@ -16,10 +16,10 @@ #ifndef LLVM_CODEGEN_LIVESTACK_ANALYSIS_H #define LLVM_CODEGEN_LIVESTACK_ANALYSIS_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 d4bb409..3c5ed92 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -29,16 +29,16 @@ #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/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/TargetRegisterInfo.h" namespace llvm { @@ -126,12 +126,6 @@ private: /// building live intervals. SparseBitVector<> PHIJoins; - /// ReservedRegisters - This vector keeps track of which registers - /// are reserved register which are not allocatable by the target machine. - /// We can not track liveness for values that are in this set. - /// - BitVector ReservedRegisters; - private: // Intermediate data structures MachineFunction *MF; diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index 77ea4d0..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 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 - 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 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()); } @@ -547,6 +574,28 @@ public: return findDebugLoc(MBBI.getInstrIterator()); } + /// Possible outcome of a register liveness query to computeRegisterLiveness() + enum LivenessQueryResult { + LQR_Live, ///< Register is known to be live. + LQR_OverlappingLive, ///< Register itself is not live, but some overlapping + ///< register is. + LQR_Dead, ///< Register is known to be dead. + LQR_Unknown ///< Register liveness not decidable from local + ///< neighborhood. + }; + + /// computeRegisterLiveness - Return whether (physical) register \c Reg + /// has been <def>ined and not <kill>ed as of just before \c MI. + /// + /// Search is localised to a neighborhood of + /// \c Neighborhood instructions before (searching for defs or kills) and + /// Neighborhood instructions after (searching just for defs) MI. + /// + /// \c Reg must be a physical register. + LivenessQueryResult computeRegisterLiveness(const TargetRegisterInfo *TRI, + unsigned Reg, MachineInstr *MI, + unsigned Neighborhood=10); + // Debugging methods. void dump() const; void print(raw_ostream &OS, SlotIndexes* = 0) const; diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h index 12189ce..1c9bdd9 100644 --- a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h +++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -15,8 +15,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/MachineConstantPool.h b/include/llvm/CodeGen/MachineConstantPool.h index d6d65a2..8ed215d 100644 --- a/include/llvm/CodeGen/MachineConstantPool.h +++ b/include/llvm/CodeGen/MachineConstantPool.h @@ -25,7 +25,7 @@ namespace llvm { class Constant; class FoldingSetNodeID; -class TargetData; +class DataLayout; class TargetMachine; class Type; class MachineConstantPool; @@ -132,14 +132,14 @@ public: /// address of the function constant pool values. /// @brief The machine constant pool. class MachineConstantPool { - const TargetData *TD; ///< The machine's TargetData. + const DataLayout *TD; ///< The machine's DataLayout. unsigned PoolAlignment; ///< The alignment for the pool. std::vector<MachineConstantPoolEntry> Constants; ///< The pool of constants. /// MachineConstantPoolValues that use an existing MachineConstantPoolEntry. DenseSet<MachineConstantPoolValue*> MachineCPVsSharingEntries; public: /// @brief The only constructor. - explicit MachineConstantPool(const TargetData *td) + explicit MachineConstantPool(const DataLayout *td) : TD(td), PoolAlignment(1) {} ~MachineConstantPool(); diff --git a/include/llvm/CodeGen/MachineDominators.h b/include/llvm/CodeGen/MachineDominators.h index 82a4ac8..40b2542 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 { diff --git a/include/llvm/CodeGen/MachineFrameInfo.h b/include/llvm/CodeGen/MachineFrameInfo.h index 3c07ceb..93d7728 100644 --- a/include/llvm/CodeGen/MachineFrameInfo.h +++ b/include/llvm/CodeGen/MachineFrameInfo.h @@ -21,7 +21,7 @@ namespace llvm { class raw_ostream; -class TargetData; +class DataLayout; class TargetRegisterClass; class Type; class MachineFunction; @@ -29,6 +29,7 @@ class MachineBasicBlock; class TargetFrameLowering; class BitVector; class Value; +class AllocaInst; /// The CalleeSavedInfo class tracks the information need to locate where a /// callee saved register is in the current frame. @@ -106,14 +107,14 @@ class MachineFrameInfo { /// Alloca - If this stack object is originated from an Alloca instruction /// this value saves the original IR allocation. Can be NULL. - const Value *Alloca; + const AllocaInst *Alloca; // PreAllocated - If true, the object was mapped into the local frame // block and doesn't need additional handling for allocation beyond that. bool PreAllocated; StackObject(uint64_t Sz, unsigned Al, int64_t SP, bool IM, - bool isSS, bool NSP, const Value *Val) + bool isSS, bool NSP, const AllocaInst *Val) : SPOffset(SP), Size(Sz), Alignment(Al), isImmutable(IM), isSpillSlot(isSS), MayNeedSP(NSP), Alloca(Val), PreAllocated(false) {} }; @@ -220,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; @@ -369,7 +373,7 @@ public: /// getObjectAllocation - Return the underlying Alloca of the specified /// stack object if it exists. Returns 0 if none exists. - const Value* getObjectAllocation(int ObjectIdx) const { + const AllocaInst* getObjectAllocation(int ObjectIdx) const { assert(unsigned(ObjectIdx+NumFixedObjects) < Objects.size() && "Invalid Object Idx!"); return Objects[ObjectIdx+NumFixedObjects].Alloca; @@ -431,9 +435,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 @@ -495,26 +497,13 @@ public: /// a nonnegative identifier to represent it. /// int CreateStackObject(uint64_t Size, unsigned Alignment, bool isSS, - bool MayNeedSP = false, const Value *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. /// @@ -528,12 +517,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 0eb9d0e..cd704c1 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,8 +131,8 @@ class MachineFunction { /// about the control flow of such functions. bool ExposesReturnsTwice; - MachineFunction(const MachineFunction &); // DO NOT IMPLEMENT - void operator=(const MachineFunction&); // DO NOT IMPLEMENT + MachineFunction(const MachineFunction &) LLVM_DELETED_FUNCTION; + void operator=(const MachineFunction&) LLVM_DELETED_FUNCTION; public: MachineFunction(const Function *Fn, const TargetMachine &TM, unsigned FunctionNum, MachineModuleInfo &MMI, @@ -394,6 +398,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/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h index 4e1533a..89521e8 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&); // DO NOT IMPLEMENT - void operator=(const MachineInstr&); // DO NOT IMPLEMENT + 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,37 +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(); - - // The next two constructors have DebugLoc and non-DebugLoc versions; - // over time, the non-DebugLoc versions should be phased out and eventually - // removed. - - /// MachineInstr ctor - This constructor creates a MachineInstr and adds the - /// implicit operands. It reserves space for the number of operands specified - /// by the MCInstrDesc. The version with a DebugLoc should be preferred. - explicit MachineInstr(const MCInstrDesc &MCID, 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. The version with a DebugLoc should be preferred. - MachineInstr(MachineBasicBlock *MBB, const MCInstrDesc &MCID); - /// 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. - explicit 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; @@ -175,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. @@ -220,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. /// @@ -259,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!"); @@ -275,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; } @@ -460,6 +463,11 @@ public: /// Instructions with this flag set are not necessarily simple load /// instructions, they may load a value and modify it, for example. bool mayLoad(QueryType Type = AnyInBundle) const { + if (isInlineAsm()) { + unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm(); + if (ExtraInfo & InlineAsm::Extra_MayLoad) + return true; + } return hasProperty(MCID::MayLoad, Type); } @@ -469,6 +477,11 @@ public: /// instructions, they may store a modified value based on their operands, or /// may not actually modify anything, for example. bool mayStore(QueryType Type = AnyInBundle) const { + if (isInlineAsm()) { + unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm(); + if (ExtraInfo & InlineAsm::Extra_MayStore) + return true; + } return hasProperty(MCID::MayStore, Type); } @@ -583,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 { @@ -826,13 +858,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, @@ -914,7 +939,7 @@ 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 @@ -925,10 +950,23 @@ public: //===--------------------------------------------------------------------===// // 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 @@ -955,7 +993,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: @@ -975,7 +1014,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 654361f..a2d3d63 100644 --- a/include/llvm/CodeGen/MachineInstrBuilder.h +++ b/include/llvm/CodeGen/MachineInstrBuilder.h @@ -42,10 +42,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 +64,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 +163,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; } @@ -176,17 +188,32 @@ public: } // Add a displacement from an existing MachineOperand with an added offset. - const MachineInstrBuilder &addDisp(const MachineOperand &Disp, - int64_t off) const { + const MachineInstrBuilder &addDisp(const MachineOperand &Disp, int64_t off, + unsigned char TargetFlags = 0) const { switch (Disp.getType()) { default: llvm_unreachable("Unhandled operand type in addDisp()"); case MachineOperand::MO_Immediate: return addImm(Disp.getImm() + off); - case MachineOperand::MO_GlobalAddress: - return addGlobalAddress(Disp.getGlobal(), Disp.getOffset() + off); + case MachineOperand::MO_GlobalAddress: { + // If caller specifies new TargetFlags then use it, otherwise the + // default behavior is to copy the target flags from the existing + // MachineOperand. This means if the caller wants to clear the + // target flags it needs to do so explicitly. + if (TargetFlags) + return addGlobalAddress(Disp.getGlobal(), Disp.getOffset() + off, + TargetFlags); + return addGlobalAddress(Disp.getGlobal(), Disp.getOffset() + off, + Disp.getTargetFlags()); + } } } + + /// 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 @@ -195,7 +222,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 @@ -205,7 +232,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); } @@ -218,9 +245,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, @@ -228,9 +256,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, @@ -255,18 +284,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, @@ -321,6 +352,98 @@ 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) { + MachineBasicBlock::iterator I = MI; + ++I; + End = I.getInstrIterator(); + } + + /// 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 dc5f9a6..3c60ad1 100644 --- a/include/llvm/CodeGen/MachineInstrBundle.h +++ b/include/llvm/CodeGen/MachineInstrBundle.h @@ -130,9 +130,9 @@ public: return OpI - InstrI->operands_begin(); } - /// RegInfo - Information about a virtual register used by a set of operands. + /// VirtRegInfo - Information about a virtual register used by a set of operands. /// - struct RegInfo { + struct VirtRegInfo { /// Reads - One of the operands read the virtual register. This does not /// include <undef> or <internal> use operands, see MO::readsReg(). bool Reads; @@ -146,6 +146,29 @@ public: bool Tied; }; + /// 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. + bool Clobbers; + + /// Defines - Reg or a super-register is defined. + bool Defines; + + /// Reads - Read or a super-register is read. + bool Reads; + + /// ReadsOverlap - Reg or an overlapping register is read. + bool ReadsOverlap; + + /// DefinesDead - All defs of a Reg or a super-register are dead. + bool DefinesDead; + + /// There is a kill of Reg or a super-register. + bool Kills; + }; + /// analyzeVirtReg - Analyze how the current instruction or bundle uses a /// virtual register. This function should not be called after operator++(), /// it expects a fresh iterator. @@ -154,8 +177,16 @@ public: /// @param Ops When set, this vector will receive an (MI, OpNum) entry for /// each operand referring to Reg. /// @returns A filled-in RegInfo struct. - RegInfo analyzeVirtReg(unsigned Reg, + VirtRegInfo analyzeVirtReg(unsigned Reg, SmallVectorImpl<std::pair<MachineInstr*, unsigned> > *Ops = 0); + + /// analyzePhysReg - Analyze how the current instruction or bundle uses a + /// physical register. This function should not be called after operator++(), + /// it expects a fresh iterator. + /// + /// @param Reg The physical register to analyze. + /// @returns A filled-in PhysRegInfo struct. + PhysRegInfo analyzePhysReg(unsigned Reg, const TargetRegisterInfo *TRI); }; /// MIOperands - Iterate over operands of a single instruction. diff --git a/include/llvm/CodeGen/MachineJumpTableInfo.h b/include/llvm/CodeGen/MachineJumpTableInfo.h index f7c4e86..adcd1d0 100644 --- a/include/llvm/CodeGen/MachineJumpTableInfo.h +++ b/include/llvm/CodeGen/MachineJumpTableInfo.h @@ -20,13 +20,13 @@ #ifndef LLVM_CODEGEN_MACHINEJUMPTABLEINFO_H #define LLVM_CODEGEN_MACHINEJUMPTABLEINFO_H -#include <vector> #include <cassert> +#include <vector> namespace llvm { class MachineBasicBlock; -class TargetData; +class DataLayout; class raw_ostream; /// MachineJumpTableEntry - One jump table in the jump table info. @@ -84,9 +84,9 @@ public: JTEntryKind getEntryKind() const { return EntryKind; } /// getEntrySize - Return the size of each entry in the jump table. - unsigned getEntrySize(const TargetData &TD) const; + unsigned getEntrySize(const DataLayout &TD) const; /// getEntryAlignment - Return the alignment of each entry in the jump table. - unsigned getEntryAlignment(const TargetData &TD) const; + unsigned getEntryAlignment(const DataLayout &TD) const; /// createJumpTableIndex - Create a new jump table. /// diff --git a/include/llvm/CodeGen/MachineLoopInfo.h b/include/llvm/CodeGen/MachineLoopInfo.h index 3e204be..99da6b2 100644 --- a/include/llvm/CodeGen/MachineLoopInfo.h +++ b/include/llvm/CodeGen/MachineLoopInfo.h @@ -30,8 +30,8 @@ #ifndef LLVM_CODEGEN_MACHINE_LOOP_INFO_H #define LLVM_CODEGEN_MACHINE_LOOP_INFO_H -#include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/CodeGen/MachineFunctionPass.h" namespace llvm { @@ -73,8 +73,8 @@ class MachineLoopInfo : public MachineFunctionPass { LoopInfoBase<MachineBasicBlock, MachineLoop> LI; friend class LoopBase<MachineBasicBlock, MachineLoop>; - void operator=(const MachineLoopInfo &); // do not implement - MachineLoopInfo(const MachineLoopInfo &); // do not implement + void operator=(const MachineLoopInfo &) LLVM_DELETED_FUNCTION; + MachineLoopInfo(const MachineLoopInfo &) LLVM_DELETED_FUNCTION; public: static char ID; // Pass identification, replacement for typeid 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..6194d05 100644 --- a/include/llvm/CodeGen/MachineModuleInfo.h +++ b/include/llvm/CodeGen/MachineModuleInfo.h @@ -31,19 +31,19 @@ #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/GlobalValue.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 +180,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. /// @@ -372,7 +373,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/MachineModuleInfoImpls.h b/include/llvm/CodeGen/MachineModuleInfoImpls.h index 9401ffd..7afc7eb 100644 --- a/include/llvm/CodeGen/MachineModuleInfoImpls.h +++ b/include/llvm/CodeGen/MachineModuleInfoImpls.h @@ -38,7 +38,7 @@ namespace llvm { /// this GV is external. DenseMap<MCSymbol*, StubValueTy> HiddenGVStubs; - virtual void Anchor(); // Out of line virtual method. + virtual void anchor(); // Out of line virtual method. public: MachineModuleInfoMachO(const MachineModuleInfo &) {} @@ -76,7 +76,7 @@ namespace llvm { /// mode. DenseMap<MCSymbol*, StubValueTy> GVStubs; - virtual void Anchor(); // Out of line virtual method. + virtual void anchor(); // Out of line virtual method. public: MachineModuleInfoELF(const MachineModuleInfo &) {} diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h index 0b9d67f..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, @@ -628,11 +631,11 @@ public: Op.setTargetFlags(TargetFlags); return Op; } - static MachineOperand CreateBA(const BlockAddress *BA, + static MachineOperand CreateBA(const BlockAddress *BA, int64_t Offset, unsigned char TargetFlags = 0) { MachineOperand Op(MachineOperand::MO_BlockAddress); Op.Contents.OffsetedInfo.Val.BA = BA; - Op.setOffset(0); // Offset is always 0. + Op.setOffset(Offset); Op.setTargetFlags(TargetFlags); return Op; } @@ -687,6 +690,9 @@ inline raw_ostream &operator<<(raw_ostream &OS, const MachineOperand& MO) { return OS; } + // See friend declaration above. This additional declaration is required in + // order to compile LLVM with IBM xlC compiler. + hash_code hash_value(const MachineOperand &MO); } // End llvm namespace #endif diff --git a/include/llvm/CodeGen/MachinePostDominators.h b/include/llvm/CodeGen/MachinePostDominators.h new file mode 100644 index 0000000..00a60cb --- /dev/null +++ b/include/llvm/CodeGen/MachinePostDominators.h @@ -0,0 +1,87 @@ +//=- llvm/CodeGen/MachineDominators.h ----------------------------*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file exposes interfaces to post dominance information for +// target-specific code. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_MACHINEPOSTDOMINATORS_H +#define LLVM_CODEGEN_MACHINEPOSTDOMINATORS_H + +#include "llvm/Analysis/DominatorInternals.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineFunctionPass.h" + +namespace llvm { + +/// +/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used +/// to compute the a post-dominator tree. +/// +struct MachinePostDominatorTree : public MachineFunctionPass { +private: + DominatorTreeBase<MachineBasicBlock> *DT; + +public: + static char ID; + + MachinePostDominatorTree(); + + ~MachinePostDominatorTree(); + + FunctionPass *createMachinePostDominatorTreePass(); + + const std::vector<MachineBasicBlock *> &getRoots() const { + return DT->getRoots(); + } + + MachineDomTreeNode *getRootNode() const { + return DT->getRootNode(); + } + + MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { + return DT->getNode(BB); + } + + MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { + return DT->getNode(BB); + } + + bool dominates(MachineDomTreeNode *A, MachineDomTreeNode *B) const { + return DT->dominates(A, B); + } + + bool dominates(MachineBasicBlock *A, MachineBasicBlock *B) const { + return DT->dominates(A, B); + } + + bool + properlyDominates(const MachineDomTreeNode *A, MachineDomTreeNode *B) const { + return DT->properlyDominates(A, B); + } + + bool + properlyDominates(MachineBasicBlock *A, MachineBasicBlock *B) const { + return DT->properlyDominates(A, B); + } + + MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, + MachineBasicBlock *B) { + return DT->findNearestCommonDominator(A, B); + } + + virtual bool runOnMachineFunction(MachineFunction &MF); + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void print(llvm::raw_ostream &OS, const Module *M = 0) const; +}; +} //end of namespace llvm + +#endif diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h index 42a8aa4..36427e9 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 { @@ -77,16 +77,20 @@ class MachineRegisterInfo { return MO->Contents.Reg.Next; } - /// UsedPhysRegs - This is a bit vector that is computed and set by the + /// UsedRegUnits - This is a bit vector that is computed and set by the /// register allocator, and must be kept up to date by passes that run after /// register allocation (though most don't modify this). This is used /// so that the code generator knows which callee save registers to save and /// for other target specific uses. - /// This vector only has bits set for registers explicitly used, not their - /// aliases. - BitVector UsedPhysRegs; - - /// UsedPhysRegMask - Additional used physregs, but including aliases. + /// This vector has bits set for register units that are modified in the + /// current function. It doesn't include registers clobbered by function + /// calls with register mask operands. + BitVector UsedRegUnits; + + /// UsedPhysRegMask - Additional used physregs including aliases. + /// This bit vector represents all the registers clobbered by function calls. + /// It can model things that UsedRegUnits can't, such as function calls that + /// clobber ymm7 but preserve the low half in xmm7. BitVector UsedPhysRegMask; /// ReservedRegs - This is a bit vector of reserved registers. The target @@ -95,9 +99,6 @@ class MachineRegisterInfo { /// started. BitVector ReservedRegs; - /// AllocatableRegs - From TRI->getAllocatableSet. - mutable BitVector AllocatableRegs; - /// 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. @@ -106,8 +107,8 @@ class MachineRegisterInfo { std::vector<std::pair<unsigned, unsigned> > LiveIns; std::vector<unsigned> LiveOuts; - MachineRegisterInfo(const MachineRegisterInfo&); // DO NOT IMPLEMENT - void operator=(const MachineRegisterInfo&); // DO NOT IMPLEMENT + MachineRegisterInfo(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION; + void operator=(const MachineRegisterInfo&) LLVM_DELETED_FUNCTION; public: explicit MachineRegisterInfo(const TargetRegisterInfo &TRI); ~MachineRegisterInfo(); @@ -155,6 +156,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. @@ -360,29 +364,27 @@ public: //===--------------------------------------------------------------------===// /// isPhysRegUsed - Return true if the specified register is used in this - /// function. This only works after register allocation. + /// function. Also check for clobbered aliases and registers clobbered by + /// function calls with register mask operands. + /// + /// This only works after register allocation. It is primarily used by + /// PrologEpilogInserter to determine which callee-saved registers need + /// spilling. bool isPhysRegUsed(unsigned Reg) const { - return UsedPhysRegs.test(Reg) || UsedPhysRegMask.test(Reg); - } - - /// isPhysRegOrOverlapUsed - Return true if Reg or any overlapping register - /// is used in this function. - bool isPhysRegOrOverlapUsed(unsigned Reg) const { if (UsedPhysRegMask.test(Reg)) return true; - for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) - if (UsedPhysRegs.test(*AI)) + for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) + if (UsedRegUnits.test(*Units)) return true; return false; } /// setPhysRegUsed - Mark the specified register used in this function. /// This should only be called during and after register allocation. - void setPhysRegUsed(unsigned Reg) { UsedPhysRegs.set(Reg); } - - /// addPhysRegsUsed - Mark the specified registers used in this function. - /// This should only be called during and after register allocation. - void addPhysRegsUsed(const BitVector &Regs) { UsedPhysRegs |= Regs; } + void setPhysRegUsed(unsigned Reg) { + for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) + UsedRegUnits.set(*Units); + } /// addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used. /// This corresponds to the bit mask attached to register mask operands. @@ -393,8 +395,9 @@ public: /// setPhysRegUnused - Mark the specified register unused in this function. /// This should only be called during and after register allocation. void setPhysRegUnused(unsigned Reg) { - UsedPhysRegs.reset(Reg); UsedPhysRegMask.reset(Reg); + for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) + UsedRegUnits.reset(*Units); } @@ -427,6 +430,34 @@ public: return !reservedRegsFrozen() || ReservedRegs.test(PhysReg); } + /// getReservedRegs - Returns a reference to the frozen set of reserved + /// registers. This method should always be preferred to calling + /// TRI::getReservedRegs() when possible. + const BitVector &getReservedRegs() const { + assert(reservedRegsFrozen() && + "Reserved registers haven't been frozen yet. " + "Use TRI::getReservedRegs()."); + return ReservedRegs; + } + + /// isReserved - Returns true when PhysReg is a reserved register. + /// + /// Reserved registers may belong to an allocatable register class, but the + /// target has explicitly requested that they are not used. + /// + bool isReserved(unsigned PhysReg) const { + return getReservedRegs().test(PhysReg); + } + + /// isAllocatable - Returns true when PhysReg belongs to an allocatable + /// register class and it hasn't been reserved. + /// + /// Allocatable registers may show up in the allocation order of some virtual + /// register, so a register allocator needs to track its liveness and + /// availability. + bool isAllocatable(unsigned PhysReg) const { + return TRI->isInAllocatableClass(PhysReg) && !isReserved(PhysReg); + } //===--------------------------------------------------------------------===// // LiveIn/LiveOut Management diff --git a/include/llvm/CodeGen/MachineSSAUpdater.h b/include/llvm/CodeGen/MachineSSAUpdater.h index cbb45a7..edf93d1 100644 --- a/include/llvm/CodeGen/MachineSSAUpdater.h +++ b/include/llvm/CodeGen/MachineSSAUpdater.h @@ -14,6 +14,8 @@ #ifndef LLVM_CODEGEN_MACHINESSAUPDATER_H #define LLVM_CODEGEN_MACHINESSAUPDATER_H +#include "llvm/Support/Compiler.h" + namespace llvm { class MachineBasicBlock; class MachineFunction; @@ -106,8 +108,8 @@ private: void ReplaceRegWith(unsigned OldReg, unsigned NewReg); unsigned GetValueAtEndOfBlockInternal(MachineBasicBlock *BB); - void operator=(const MachineSSAUpdater&); // DO NOT IMPLEMENT - MachineSSAUpdater(const MachineSSAUpdater&); // DO NOT IMPLEMENT + void operator=(const MachineSSAUpdater&) LLVM_DELETED_FUNCTION; + MachineSSAUpdater(const MachineSSAUpdater&) LLVM_DELETED_FUNCTION; }; } // End llvm namespace diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index 8da2045..88f347e 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -28,9 +28,15 @@ #define MACHINESCHEDULER_H #include "llvm/CodeGen/MachinePassRegistry.h" +#include "llvm/CodeGen/RegisterPressure.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/Target/TargetInstrInfo.h" namespace llvm { +extern cl::opt<bool> ForceTopDown; +extern cl::opt<bool> ForceBottomUp; + class AliasAnalysis; class LiveIntervals; class MachineDominatorTree; @@ -93,6 +99,260 @@ public: } }; +class ScheduleDAGMI; + +/// MachineSchedStrategy - Interface to the scheduling algorithm used by +/// ScheduleDAGMI. +class MachineSchedStrategy { +public: + virtual ~MachineSchedStrategy() {} + + /// Initialize the strategy after building the DAG for a new region. + virtual void initialize(ScheduleDAGMI *DAG) = 0; + + /// Notify this strategy that all roots have been released (including those + /// that depend on EntrySU or ExitSU). + virtual void registerRoots() {} + + /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to + /// schedule the node at the top of the unscheduled region. Otherwise it will + /// be scheduled at the bottom. + virtual SUnit *pickNode(bool &IsTopNode) = 0; + + /// 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; + + /// When all predecessor dependencies have been resolved, free this node for + /// top-down scheduling. + virtual void releaseTopNode(SUnit *SU) = 0; + /// When all successor dependencies have been resolved, free this node for + /// bottom-up scheduling. + virtual void releaseBottomNode(SUnit *SU) = 0; +}; + +/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience +/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified +/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. +/// +/// This is a convenience class that may be used by implementations of +/// MachineSchedStrategy. +class ReadyQueue { + unsigned ID; + std::string Name; + std::vector<SUnit*> Queue; + +public: + ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} + + unsigned getID() const { return ID; } + + StringRef getName() const { return Name; } + + // SU is in this queue if it's NodeQueueID is a superset of this ID. + bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } + + bool empty() const { return Queue.empty(); } + + void clear() { Queue.clear(); } + + unsigned size() const { return Queue.size(); } + + typedef std::vector<SUnit*>::iterator iterator; + + iterator begin() { return Queue.begin(); } + + iterator end() { return Queue.end(); } + + iterator find(SUnit *SU) { + return std::find(Queue.begin(), Queue.end(), SU); + } + + void push(SUnit *SU) { + Queue.push_back(SU); + SU->NodeQueueId |= ID; + } + + iterator remove(iterator I) { + (*I)->NodeQueueId &= ~ID; + *I = Queue.back(); + unsigned idx = I - Queue.begin(); + Queue.pop_back(); + return Queue.begin() + idx; + } + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + void dump(); +#endif +}; + +/// Mutate the DAG as a postpass after normal DAG building. +class ScheduleDAGMutation { +public: + virtual ~ScheduleDAGMutation() {} + + virtual void apply(ScheduleDAGMI *DAG) = 0; +}; + +/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules +/// machine instructions while updating LiveIntervals and tracking regpressure. +class ScheduleDAGMI : public ScheduleDAGInstrs { +protected: + AliasAnalysis *AA; + RegisterClassInfo *RegClassInfo; + MachineSchedStrategy *SchedImpl; + + /// 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; + + MachineBasicBlock::iterator LiveRegionEnd; + + /// Register pressure in this region computed by buildSchedGraph. + IntervalPressure RegPressure; + RegPressureTracker RPTracker; + + /// List of pressure sets that exceed the target's pressure limit before + /// scheduling, listed in increasing set ID order. Each pressure set is paired + /// with its max pressure in the currently scheduled regions. + std::vector<PressureElement> RegionCriticalPSets; + + /// The top of the unscheduled zone. + MachineBasicBlock::iterator CurrentTop; + IntervalPressure TopPressure; + RegPressureTracker TopRPTracker; + + /// The bottom of the unscheduled zone. + MachineBasicBlock::iterator CurrentBottom; + 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. + unsigned NumInstrsScheduled; +#endif + +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), + Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), + TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), + NextClusterPred(NULL), NextClusterSucc(NULL) { +#ifndef NDEBUG + NumInstrsScheduled = 0; +#endif + } + + virtual ~ScheduleDAGMI() { + DeleteContainerPointers(Mutations); + delete SchedImpl; + } + + /// 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; } + + /// Implement the ScheduleDAGInstrs interface for handling the next scheduling + /// region. This covers all instructions in a block, while schedule() may only + /// cover a subset. + void enterRegion(MachineBasicBlock *bb, + MachineBasicBlock::iterator begin, + MachineBasicBlock::iterator end, + unsigned endcount); + + + /// Implement ScheduleDAGInstrs interface for scheduling a sequence of + /// reorderable instructions. + virtual void schedule(); + + /// Get current register pressure for the top scheduled instructions. + const IntervalPressure &getTopPressure() const { return TopPressure; } + const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } + + /// Get current register pressure for the bottom scheduled instructions. + const IntervalPressure &getBotPressure() const { return BotPressure; } + const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } + + /// Get register pressure for the entire scheduling region before scheduling. + const IntervalPressure &getRegPressure() const { return RegPressure; } + + const std::vector<PressureElement> &getRegionCriticalPSets() const { + return RegionCriticalPSets; + } + + const SUnit *getNextClusterPred() const { return NextClusterPred; } + + const SUnit *getNextClusterSucc() const { return NextClusterSucc; } + +protected: + // Top-Level entry points for the schedule() driver... + + /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking + /// enabled. This sets up three trackers. RPTracker will cover the entire DAG + /// region, TopTracker and BottomTracker will be initialized to the top and + /// bottom of the DAG region without covereing any unscheduled instruction. + void buildDAGWithRegPressure(); + + /// Apply each ScheduleDAGMutation step in order. This allows different + /// instances of ScheduleDAGMI to perform custom DAG postprocessing. + void postprocessDAG(); + + /// Identify DAG roots and setup scheduler queues. + void initQueues(); + + /// Move an instruction and update register pressure. + void scheduleMI(SUnit *SU, bool IsTopNode); + + /// Update scheduler DAG and queues after scheduling an instruction. + void updateQueues(SUnit *SU, bool IsTopNode); + + /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. + void placeDebugValues(); + + /// \brief dump the scheduled Sequence. + void dumpSchedule() const; + + // Lesser helpers... + + void initRegPressure(); + + void updateScheduledPressure(std::vector<unsigned> NewMaxPressure); + + void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); + bool checkSchedLimit(); + + void releaseRoots(); + + void releaseSucc(SUnit *SU, SDep *SuccEdge); + void releaseSuccessors(SUnit *SU); + void releasePred(SUnit *SU, SDep *PredEdge); + void releasePredecessors(SUnit *SU); +}; + } // namespace llvm #endif diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index a5d8b0d..85bf511 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -16,7 +16,8 @@ #define LLVM_CODEGEN_PBQP_GRAPH_H #include "Math.h" - +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" #include <list> #include <map> @@ -31,16 +32,16 @@ namespace PBQP { class NodeEntry; class EdgeEntry; - typedef std::list<NodeEntry> NodeList; - typedef std::list<EdgeEntry> EdgeList; + typedef llvm::ilist<NodeEntry> NodeList; + typedef llvm::ilist<EdgeEntry> EdgeList; public: - typedef NodeList::iterator NodeItr; - typedef NodeList::const_iterator ConstNodeItr; + typedef NodeEntry* NodeItr; + typedef const NodeEntry* ConstNodeItr; - typedef EdgeList::iterator EdgeItr; - typedef EdgeList::const_iterator ConstEdgeItr; + typedef EdgeEntry* EdgeItr; + typedef const EdgeEntry* ConstEdgeItr; private: @@ -52,12 +53,14 @@ namespace PBQP { private: - class NodeEntry { + class NodeEntry : public llvm::ilist_node<NodeEntry> { + friend struct llvm::ilist_sentinel_traits<NodeEntry>; private: Vector costs; AdjEdgeList adjEdges; unsigned degree; void *data; + NodeEntry() : costs(0, 0) {} public: NodeEntry(const Vector &costs) : costs(costs), degree(0) {} Vector& getCosts() { return costs; } @@ -77,12 +80,14 @@ namespace PBQP { void* getData() { return data; } }; - class EdgeEntry { + class EdgeEntry : public llvm::ilist_node<EdgeEntry> { + friend struct llvm::ilist_sentinel_traits<EdgeEntry>; private: NodeItr node1, node2; Matrix costs; AdjEdgeItr node1AEItr, node2AEItr; void *data; + EdgeEntry() : costs(0, 0, 0) {} public: EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs) : node1(node1), node2(node2), costs(costs) {} 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..4e51913 100644 --- a/include/llvm/CodeGen/PBQP/Math.h +++ b/include/llvm/CodeGen/PBQP/Math.h @@ -10,8 +10,8 @@ #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..0d02700 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -141,6 +141,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(); @@ -237,6 +241,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 +280,12 @@ 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 TargetLowering *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 +303,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; diff --git a/include/llvm/CodeGen/PseudoSourceValue.h b/include/llvm/CodeGen/PseudoSourceValue.h index 7dab4f9..df74d088 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; @@ -50,7 +50,6 @@ namespace llvm { /// classof - Methods for support type inquiry through isa, cast, and /// dyn_cast: /// - static inline bool classof(const PseudoSourceValue *) { return true; } static inline bool classof(const Value *V) { return V->getValueID() == PseudoSourceValueVal || V->getValueID() == FixedStackPseudoSourceValueVal; @@ -90,9 +89,6 @@ namespace llvm { /// classof - Methods for support type inquiry through isa, cast, and /// dyn_cast: /// - static inline bool classof(const FixedStackPseudoSourceValue *) { - return true; - } static inline bool classof(const Value *V) { return V->getValueID() == FixedStackPseudoSourceValueVal; } diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index bce3ec7..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 @@ -109,8 +109,8 @@ namespace llvm { /// class to support additional constraints for your architecture. class PBQPBuilder { private: - PBQPBuilder(const PBQPBuilder&) {} - void operator=(const PBQPBuilder&) {} + PBQPBuilder(const PBQPBuilder&) LLVM_DELETED_FUNCTION; + void operator=(const PBQPBuilder&) LLVM_DELETED_FUNCTION; public: typedef std::set<unsigned> RegSet; diff --git a/include/llvm/CodeGen/RegisterClassInfo.h b/include/llvm/CodeGen/RegisterClassInfo.h index 400e1f4..12bd1c6 100644 --- a/include/llvm/CodeGen/RegisterClassInfo.h +++ b/include/llvm/CodeGen/RegisterClassInfo.h @@ -29,10 +29,10 @@ class RegisterClassInfo { unsigned Tag; unsigned NumRegs; bool ProperSubClass; - OwningArrayPtr<unsigned> Order; + OwningArrayPtr<MCPhysReg> Order; RCInfo() : Tag(0), NumRegs(0), ProperSubClass(false) {} - operator ArrayRef<unsigned>() const { + operator ArrayRef<MCPhysReg>() const { return makeArrayRef(Order.get(), NumRegs); } }; @@ -84,7 +84,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,25 +106,6 @@ public: return CalleeSaved[N-1]; return 0; } - - /// isReserved - Returns true when PhysReg is a reserved register. - /// - /// Reserved registers may belong to an allocatable register class, but the - /// target has explicitly requested that they are not used. - /// - bool isReserved(unsigned PhysReg) const { - return Reserved.test(PhysReg); - } - - /// isAllocatable - Returns true when PhysReg belongs to an allocatable - /// register class and it hasn't been reserved. - /// - /// Allocatable registers may show up in the allocation order of some virtual - /// register, so a register allocator needs to track its liveness and - /// availability. - bool isAllocatable(unsigned PhysReg) const { - return TRI->isInAllocatableClass(PhysReg) && !isReserved(PhysReg); - } }; } // end namespace llvm diff --git a/include/llvm/CodeGen/RegisterPressure.h b/include/llvm/CodeGen/RegisterPressure.h index 2043155..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,20 +31,26 @@ 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); + void dump(const TargetRegisterInfo *TRI) const; }; /// RegisterPressure computed within a region of instructions delimited by @@ -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(); @@ -197,16 +236,14 @@ public: /// This result is complete if either advance() or recede() has returned true, /// or if closeRegion() was explicitly invoked. RegisterPressure &getPressure() { return P; } + const RegisterPressure &getPressure() const { return P; } /// Get the register set pressure at the current position, which may be less /// 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; @@ -267,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 3986a8d..6604d4c 100644 --- a/include/llvm/CodeGen/RegisterScavenging.h +++ b/include/llvm/CodeGen/RegisterScavenging.h @@ -17,8 +17,9 @@ #ifndef LLVM_CODEGEN_REGISTER_SCAVENGING_H #define LLVM_CODEGEN_REGISTER_SCAVENGING_H -#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/ADT/BitVector.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" namespace llvm { @@ -59,10 +60,6 @@ class RegScavenger { /// BitVector CalleeSavedRegs; - /// ReservedRegs - A bitvector of reserved registers. - /// - BitVector ReservedRegs; - /// RegsAvailable - The current state of all the physical registers immediately /// before MBBI. One bit per physical register. If bit is set that means it's /// available, unset means the register is currently being used. @@ -130,12 +127,14 @@ public: void setUsed(unsigned Reg); private: /// isReserved - Returns true if a register is reserved. It is never "unused". - bool isReserved(unsigned Reg) const { return ReservedRegs.test(Reg); } + 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) || ReservedRegs.test(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? diff --git a/include/llvm/CodeGen/ResourcePriorityQueue.h b/include/llvm/CodeGen/ResourcePriorityQueue.h index 56b5855..66a6039 100644 --- a/include/llvm/CodeGen/ResourcePriorityQueue.h +++ b/include/llvm/CodeGen/ResourcePriorityQueue.h @@ -18,8 +18,8 @@ #define RESOURCE_PRIORITY_QUEUE_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..1a9dc1c 100644 --- a/include/llvm/CodeGen/RuntimeLibcalls.h +++ b/include/llvm/CodeGen/RuntimeLibcalls.h @@ -86,100 +86,126 @@ 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, 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 +220,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 +239,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 2567a65..aa91b03 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -16,13 +16,13 @@ #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/DenseMap.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/Target/TargetLowering.h" namespace llvm { class AliasAnalysis; @@ -31,6 +31,7 @@ namespace llvm { class MachineFunction; class MachineRegisterInfo; class MachineInstr; + struct MCSchedClassDesc; class TargetRegisterInfo; class ScheduleDAG; class SDNode; @@ -52,6 +53,14 @@ namespace llvm { Order ///< Any other ordering dependency. }; + 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). + Cluster ///< Weak DAG edge linking a chain of clustered instrs. + }; + private: /// Dep - A pointer to the depending/depended-on SUnit, and an enum /// indicating the kind of the dependency. @@ -65,20 +74,7 @@ namespace llvm { unsigned Reg; /// Order - Additional information about Order dependencies. - struct { - /// isNormalMemory - True if both sides of the dependence - /// access memory in non-volatile and fully modeled ways. - bool isNormalMemory : 1; - - /// isMustAlias - True if both sides of the dependence are known to - /// access the same memory. - bool isMustAlias : 1; - - /// isArtificial - True if this is an artificial dependency, meaning - /// it is not necessary for program correctness, and may be safely - /// deleted if necessary. - bool isArtificial : 1; - } Order; + unsigned OrdKind; // enum OrderKind } Contents; /// Latency - The time associated with this edge. Often this is just @@ -86,6 +82,9 @@ namespace llvm { /// models may provide additional information about specific edges. unsigned Latency; /// Record MinLatency seperately from "expected" Latency. + /// + /// FIXME: this field is not packed on LP64. Convert to 16-bit DAG edge + /// latency after introducing saturating truncation. unsigned MinLatency; public: @@ -95,28 +94,28 @@ namespace llvm { SDep() : Dep(0, Data) {} /// SDep - Construct an SDep with the specified values. - SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0, - bool isNormalMemory = false, bool isMustAlias = false, - bool isArtificial = false) - : Dep(S, kind), Contents(), Latency(latency), MinLatency(latency) { + SDep(SUnit *S, Kind kind, unsigned Reg) + : Dep(S, kind), Contents() { switch (kind) { + default: + llvm_unreachable("Reg given for non-register dependence!"); case Anti: case Output: assert(Reg != 0 && "SDep::Anti and SDep::Output must use a non-zero Reg!"); - // fall through - case Data: - assert(!isMustAlias && "isMustAlias only applies with SDep::Order!"); - assert(!isArtificial && "isArtificial only applies with SDep::Order!"); Contents.Reg = Reg; + Latency = 0; break; - case Order: - assert(Reg == 0 && "Reg given for non-register dependence!"); - Contents.Order.isNormalMemory = isNormalMemory; - Contents.Order.isMustAlias = isMustAlias; - Contents.Order.isArtificial = isArtificial; + case Data: + Contents.Reg = Reg; + Latency = 1; break; } + MinLatency = Latency; + } + SDep(SUnit *S, OrderKind kind) + : Dep(S, Order), Contents(), Latency(0), MinLatency(0) { + Contents.OrdKind = kind; } /// Return true if the specified SDep is equivalent except for latency. @@ -128,10 +127,7 @@ namespace llvm { case Output: return Contents.Reg == Other.Contents.Reg; case Order: - return Contents.Order.isNormalMemory == - Other.Contents.Order.isNormalMemory && - Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias && - Contents.Order.isArtificial == Other.Contents.Order.isArtificial; + return Contents.OrdKind == Other.Contents.OrdKind; } llvm_unreachable("Invalid dependency kind!"); } @@ -194,20 +190,35 @@ namespace llvm { /// memory accesses where both sides of the dependence access memory /// in non-volatile and fully modeled ways. bool isNormalMemory() const { - return getKind() == Order && Contents.Order.isNormalMemory; + return getKind() == Order && (Contents.OrdKind == MayAliasMem + || Contents.OrdKind == MustAliasMem); } /// isMustAlias - Test if this is an Order dependence that is marked /// as "must alias", meaning that the SUnits at either end of the edge /// have a memory dependence on a known memory location. bool isMustAlias() const { - return getKind() == Order && Contents.Order.isMustAlias; + 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 == Cluster; } /// 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.Order.isArtificial; + 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 @@ -254,6 +265,8 @@ namespace llvm { // this node was cloned. // (SD scheduling only) + const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass. + // Preds/Succs - The SUnits before/after us in the graph. SmallVector<SDep, 4> Preds; // All sunit predecessors. SmallVector<SDep, 4> Succs; // All sunit successors. @@ -269,6 +282,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,41 +316,41 @@ namespace llvm { /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent /// an SDNode and any nodes flagged to it. SUnit(SDNode *node, unsigned nodenum) - : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), + : 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) {} /// SUnit - Construct an SUnit for post-regalloc scheduling to represent /// a MachineInstr. SUnit(MachineInstr *instr, unsigned nodenum) - : Node(0), Instr(instr), OrigNode(0), NodeNum(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), NodeNum(~0u), + : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(~0u), 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) {} @@ -374,7 +389,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 @@ -570,16 +585,6 @@ namespace llvm { unsigned VerifyScheduledDAG(bool isBottomUp); #endif - protected: - /// ComputeLatency - Compute node latency. - /// - virtual void computeLatency(SUnit *SU) = 0; - - /// ForceUnitLatencies - Return true if all scheduling edges should be given - /// a latency value of one. The default is to return false; schedulers may - /// override this as needed. - virtual bool forceUnitLatencies() const { return false; } - private: // Return the MCInstrDesc of this SDNode or NULL. const MCInstrDesc *getNodeDesc(const SDNode *Node) const; @@ -666,6 +671,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; @@ -687,7 +693,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/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h index 8b52b5a..ffc442e 100644 --- a/include/llvm/CodeGen/ScheduleDAGInstrs.h +++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -15,13 +15,14 @@ #ifndef SCHEDULEDAGINSTRS_H #define SCHEDULEDAGINSTRS_H +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SparseSet.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineLoopInfo.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 { @@ -30,72 +31,6 @@ namespace llvm { class LiveIntervals; class RegPressureTracker; - /// LoopDependencies - This class analyzes loop-oriented register - /// dependencies, which are used to guide scheduling decisions. - /// For example, loop induction variable increments should be - /// scheduled as soon as possible after the variable's last use. - /// - class LoopDependencies { - const MachineDominatorTree &MDT; - - public: - typedef std::map<unsigned, std::pair<const MachineOperand *, unsigned> > - LoopDeps; - LoopDeps Deps; - - LoopDependencies(const MachineDominatorTree &mdt) : MDT(mdt) {} - - /// VisitLoop - Clear out any previous state and analyze the given loop. - /// - void VisitLoop(const MachineLoop *Loop) { - assert(Deps.empty() && "stale loop dependencies"); - - MachineBasicBlock *Header = Loop->getHeader(); - SmallSet<unsigned, 8> LoopLiveIns; - for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(), - LE = Header->livein_end(); LI != LE; ++LI) - LoopLiveIns.insert(*LI); - - const MachineDomTreeNode *Node = MDT.getNode(Header); - const MachineBasicBlock *MBB = Node->getBlock(); - assert(Loop->contains(MBB) && - "Loop does not contain header!"); - VisitRegion(Node, MBB, Loop, LoopLiveIns); - } - - private: - void VisitRegion(const MachineDomTreeNode *Node, - const MachineBasicBlock *MBB, - const MachineLoop *Loop, - const SmallSet<unsigned, 8> &LoopLiveIns) { - unsigned Count = 0; - for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I) { - const MachineInstr *MI = I; - if (MI->isDebugValue()) - continue; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isUse()) - continue; - unsigned MOReg = MO.getReg(); - if (LoopLiveIns.count(MOReg)) - Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count))); - } - ++Count; // Not every iteration due to dbg_value above. - } - - const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); - for (std::vector<MachineDomTreeNode*>::const_iterator I = - Children.begin(), E = Children.end(); I != E; ++I) { - const MachineDomTreeNode *ChildNode = *I; - MachineBasicBlock *ChildBlock = ChildNode->getBlock(); - if (Loop->contains(ChildBlock)) - VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns); - } - } - }; - /// An individual mapping from virtual register number to SUnit. struct VReg2SUnit { unsigned VirtReg; @@ -176,11 +111,13 @@ namespace llvm { const MachineLoopInfo &MLI; const MachineDominatorTree &MDT; const MachineFrameInfo *MFI; - const InstrItineraryData *InstrItins; /// Live Intervals provides reaching defs in preRA scheduling. LiveIntervals *LIS; + /// TargetSchedModel provides an interface to the machine model. + TargetSchedModel SchedModel; + /// isPostRA flag indicates vregs cannot be present. bool IsPostRA; @@ -232,10 +169,6 @@ namespace llvm { /// to minimize construction/destruction. std::vector<SUnit *> PendingLoads; - /// LoopRegs - Track which registers are used for loop-carried dependencies. - /// - LoopDependencies LoopRegs; - /// DbgValues - Remember instruction that precedes DBG_VALUE. /// These are generated by buildSchedGraph but persist so they can be /// referenced when emitting the final schedule. @@ -253,6 +186,16 @@ namespace llvm { virtual ~ScheduleDAGInstrs() {} + /// \brief Get the machine model for instruction scheduling. + const TargetSchedModel *getSchedModel() const { return &SchedModel; } + + /// \brief Resolve and cache a resolved scheduling class for an SUnit. + const MCSchedClassDesc *getSchedClass(SUnit *SU) const { + if (!SU->SchedClass) + SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr()); + return SU->SchedClass; + } + /// begin - Return an iterator to the top of the current scheduling region. MachineBasicBlock::iterator begin() const { return RegionBegin; } @@ -293,10 +236,6 @@ namespace llvm { /// used by instructions in the fallthrough block. void addSchedBarrierDeps(); - /// computeLatency - Compute node latency. - /// - virtual void computeLatency(SUnit *SU); - /// schedule - Order nodes according to selected style, filling /// in the Sequence member. /// diff --git a/include/llvm/CodeGen/ScheduleDFS.h b/include/llvm/CodeGen/ScheduleDFS.h new file mode 100644 index 0000000..fbbadd9 --- /dev/null +++ b/include/llvm/CodeGen/ScheduleDFS.h @@ -0,0 +1,152 @@ +//===- 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/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. +/// +/// 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. +/// +/// ILPValues summarize the DAG subtree rooted at each node up to +/// SubtreeLimit. ILPValues are also valid for interior nodes of a subtree, not +/// just the root. +class SchedDFSResult { + friend class SchedDFSImpl; + + /// \brief Per-SUnit data computed during DFS for various metrics. + struct NodeData { + unsigned InstrCount; + unsigned SubtreeID; + + NodeData(): InstrCount(0), SubtreeID(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> DFSData; + + // 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 Clear the results. + void clear() { + DFSData.clear(); + SubtreeConnections.clear(); + SubtreeConnectLevels.clear(); + } + + /// \brief Initialize the result data with the size of the DAG. + void resize(unsigned NumSUnits) { + DFSData.resize(NumSUnits); + } + + /// \brief Compute various metrics for the DAG with given roots. + void compute(ArrayRef<SUnit *> Roots); + + /// \brief Get the ILP value for a DAG node. + /// + /// A leaf node has an ILP of 1/1. + ILPValue getILP(const SUnit *SU) { + return ILPValue(DFSData[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. + unsigned getSubtreeID(const SUnit *SU) { + return DFSData[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) { + 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 a582b0c..836b73a 100644 --- a/include/llvm/CodeGen/SchedulerRegistry.h +++ b/include/llvm/CodeGen/SchedulerRegistry.h @@ -102,6 +102,11 @@ ScheduleDAGSDNodes *createVLIWDAGScheduler(SelectionDAGISel *IS, ScheduleDAGSDNodes *createDefaultScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel); +/// createDAGLinearizer - This creates a "no-scheduling" scheduler which +/// linearize the DAG using topological order. +ScheduleDAGSDNodes *createDAGLinearizer(SelectionDAGISel *IS, + CodeGenOpt::Level OptLevel); + } // end namespace llvm #endif 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 1ccfe54..c5cc8f5 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: @@ -73,8 +75,8 @@ class SDDbgInfo { SmallVector<SDDbgValue*, 32> ByvalParmDbgValues; DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMap; - void operator=(const SDDbgInfo&); // Do not implement. - SDDbgInfo(const SDDbgInfo&); // Do not implement. + void operator=(const SDDbgInfo&) LLVM_DELETED_FUNCTION; + SDDbgInfo(const SDDbgInfo&) LLVM_DELETED_FUNCTION; public: SDDbgInfo() {} @@ -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; @@ -222,8 +218,8 @@ private: DenseSet<SDNode *> &visited, int level, bool &printed); - void operator=(const SelectionDAG&); // Do not implement. - SelectionDAG(const SelectionDAG&); // Do not implement. + void operator=(const SelectionDAG&) LLVM_DELETED_FUNCTION; + SelectionDAG(const SelectionDAG&) LLVM_DELETED_FUNCTION; public: explicit SelectionDAG(const TargetMachine &TM, llvm::CodeGenOpt::Level); @@ -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'. @@ -437,7 +434,13 @@ public: SDValue getRegisterMask(const uint32_t *RegMask); SDValue getEHLabel(DebugLoc dl, SDValue Root, MCSymbol *Label); SDValue getBlockAddress(const BlockAddress *BA, EVT VT, - bool isTarget = false, unsigned char TargetFlags = 0); + int64_t Offset = 0, bool isTarget = false, + unsigned char TargetFlags = 0); + SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT, + int64_t Offset = 0, + unsigned char TargetFlags = 0) { + return getBlockAddress(BA, VT, Offset, true, TargetFlags); + } SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) { return getNode(ISD::CopyToReg, dl, MVT::Other, Chain, diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index c42f655..16aacc0 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -15,10 +15,10 @@ #ifndef LLVM_CODEGEN_SELECTIONDAG_ISEL_H #define LLVM_CODEGEN_SELECTIONDAG_ISEL_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; diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 3bea2de..2c34b4f 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 { @@ -216,8 +221,8 @@ class SDUse { /// this operand. SDUse **Prev, *Next; - SDUse(const SDUse &U); // Do not implement - void operator=(const SDUse &U); // Do not implement + SDUse(const SDUse &U) LLVM_DELETED_FUNCTION; + void operator=(const SDUse &U) LLVM_DELETED_FUNCTION; public: SDUse() : Val(), User(NULL), Prev(NULL), Next(NULL) {} @@ -525,7 +530,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 +600,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 { @@ -662,9 +673,6 @@ public: /// void dumprWithDepth(const SelectionDAG *G = 0, unsigned depth = 100) const; - - static bool classof(const SDNode *) { return true; } - /// Profile - Gather unique data for the node. /// void Profile(FoldingSetNodeID &ID) const; @@ -956,7 +964,12 @@ public: const MachinePointerInfo &getPointerInfo() const { return MMO->getPointerInfo(); } - + + /// getAddressSpace - Return the address space for the associated pointer + unsigned getAddressSpace() const { + return getPointerInfo().getAddrSpace(); + } + /// refineAlignment - Update this MemSDNode's MachineMemOperand information /// to reflect the alignment of NewMMO, if it has a greater alignment. /// This must only be used when the new alignment applies to all users of @@ -971,7 +984,6 @@ public: } // Methods to support isa and dyn_cast - static bool classof(const MemSDNode *) { return true; } static bool classof(const SDNode *N) { // For some targets, we lower some target intrinsics to a MemIntrinsicNode // with either an intrinsic or a target opcode. @@ -1056,7 +1068,6 @@ public: } // Methods to support isa and dyn_cast - static bool classof(const AtomicSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::ATOMIC_CMP_SWAP || N->getOpcode() == ISD::ATOMIC_SWAP || @@ -1088,7 +1099,6 @@ public: } // Methods to support isa and dyn_cast - static bool classof(const MemIntrinsicSDNode *) { return true; } static bool classof(const SDNode *N) { // We lower some target intrinsics to their target opcode // early a node with a target opcode can be of this class @@ -1143,7 +1153,6 @@ public: } static bool isSplatMask(const int *Mask, EVT VT); - static bool classof(const ShuffleVectorSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::VECTOR_SHUFFLE; } @@ -1167,7 +1176,6 @@ public: bool isNullValue() const { return Value->isNullValue(); } bool isAllOnesValue() const { return Value->isAllOnesValue(); } - static bool classof(const ConstantSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::Constant || N->getOpcode() == ISD::TargetConstant; @@ -1202,9 +1210,6 @@ public: /// have to duplicate its logic everywhere it's called. bool isExactlyValue(double V) const { bool ignored; - // convert is not supported on this type - if (&Value->getValueAPF().getSemantics() == &APFloat::PPCDoubleDouble) - return false; APFloat Tmp(V); Tmp.convert(Value->getValueAPF().getSemantics(), APFloat::rmNearestTiesToEven, &ignored); @@ -1214,7 +1219,6 @@ public: static bool isValueValidForType(EVT VT, const APFloat& Val); - static bool classof(const ConstantFPSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::ConstantFP || N->getOpcode() == ISD::TargetConstantFP; @@ -1236,7 +1240,6 @@ public: // Return the address space this GlobalAddress belongs to. unsigned getAddressSpace() const; - static bool classof(const GlobalAddressSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::GlobalAddress || N->getOpcode() == ISD::TargetGlobalAddress || @@ -1256,7 +1259,6 @@ public: int getIndex() const { return FI; } - static bool classof(const FrameIndexSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::FrameIndex || N->getOpcode() == ISD::TargetFrameIndex; @@ -1276,7 +1278,6 @@ public: int getIndex() const { return JTI; } unsigned char getTargetFlags() const { return TargetFlags; } - static bool classof(const JumpTableSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::JumpTable || N->getOpcode() == ISD::TargetJumpTable; @@ -1337,7 +1338,6 @@ public: Type *getType() const; - static bool classof(const ConstantPoolSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::ConstantPool || N->getOpcode() == ISD::TargetConstantPool; @@ -1361,7 +1361,6 @@ public: int getIndex() const { return Index; } int64_t getOffset() const { return Offset; } - static bool classof(const TargetIndexSDNode*) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::TargetIndex; } @@ -1380,7 +1379,6 @@ public: MachineBasicBlock *getBasicBlock() const { return MBB; } - static bool classof(const BasicBlockSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::BasicBlock; } @@ -1390,7 +1388,7 @@ public: /// BUILD_VECTORs. class BuildVectorSDNode : public SDNode { // These are constructed as SDNodes and then cast to BuildVectorSDNodes. - explicit BuildVectorSDNode(); // Do not implement + explicit BuildVectorSDNode() LLVM_DELETED_FUNCTION; public: /// isConstantSplat - Check if this is a constant splat, and if so, find the /// smallest element size that splats the vector. If MinSplatBits is @@ -1405,7 +1403,6 @@ public: unsigned &SplatBitSize, bool &HasAnyUndefs, unsigned MinSplatBits = 0, bool isBigEndian = false); - static inline bool classof(const BuildVectorSDNode *) { return true; } static inline bool classof(const SDNode *N) { return N->getOpcode() == ISD::BUILD_VECTOR; } @@ -1426,7 +1423,6 @@ public: /// getValue - return the contained Value. const Value *getValue() const { return V; } - static bool classof(const SrcValueSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::SRCVALUE; } @@ -1441,7 +1437,6 @@ public: const MDNode *getMD() const { return MD; } - static bool classof(const MDNodeSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::MDNODE_SDNODE; } @@ -1458,7 +1453,6 @@ public: unsigned getReg() const { return Reg; } - static bool classof(const RegisterSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::Register; } @@ -1475,7 +1469,6 @@ public: const uint32_t *getRegMask() const { return RegMask; } - static bool classof(const RegisterMaskSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::RegisterMask; } @@ -1483,18 +1476,19 @@ public: class BlockAddressSDNode : public SDNode { const BlockAddress *BA; + int64_t Offset; unsigned char TargetFlags; friend class SelectionDAG; BlockAddressSDNode(unsigned NodeTy, EVT VT, const BlockAddress *ba, - unsigned char Flags) + int64_t o, unsigned char Flags) : SDNode(NodeTy, DebugLoc(), getSDVTList(VT)), - BA(ba), TargetFlags(Flags) { + BA(ba), Offset(o), TargetFlags(Flags) { } public: const BlockAddress *getBlockAddress() const { return BA; } + int64_t getOffset() const { return Offset; } unsigned char getTargetFlags() const { return TargetFlags; } - static bool classof(const BlockAddressSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::BlockAddress || N->getOpcode() == ISD::TargetBlockAddress; @@ -1512,7 +1506,6 @@ class EHLabelSDNode : public SDNode { public: MCSymbol *getLabel() const { return Label; } - static bool classof(const EHLabelSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::EH_LABEL; } @@ -1532,7 +1525,6 @@ public: const char *getSymbol() const { return Symbol; } unsigned char getTargetFlags() const { return TargetFlags; } - static bool classof(const ExternalSymbolSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::ExternalSymbol || N->getOpcode() == ISD::TargetExternalSymbol; @@ -1550,7 +1542,6 @@ public: ISD::CondCode get() const { return Condition; } - static bool classof(const CondCodeSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::CONDCODE; } @@ -1570,7 +1561,6 @@ class CvtRndSatSDNode : public SDNode { public: ISD::CvtCode getCvtCode() const { return CvtCode; } - static bool classof(const CvtRndSatSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::CONVERT_RNDSAT; } @@ -1589,7 +1579,6 @@ public: EVT getVT() const { return ValueType; } - static bool classof(const VTSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::VALUETYPE; } @@ -1633,7 +1622,6 @@ public: /// isUnindexed - Return true if this is NOT a pre/post inc/dec load/store. bool isUnindexed() const { return getAddressingMode() == ISD::UNINDEXED; } - static bool classof(const LSBaseSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::LOAD || N->getOpcode() == ISD::STORE; @@ -1665,7 +1653,6 @@ public: const SDValue &getBasePtr() const { return getOperand(1); } const SDValue &getOffset() const { return getOperand(2); } - static bool classof(const LoadSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::LOAD; } @@ -1696,7 +1683,6 @@ public: const SDValue &getBasePtr() const { return getOperand(2); } const SDValue &getOffset() const { return getOperand(3); } - static bool classof(const StoreSDNode *) { return true; } static bool classof(const SDNode *N) { return N->getOpcode() == ISD::STORE; } @@ -1737,7 +1723,6 @@ public: MemRefsEnd = NewMemRefsEnd; } - static bool classof(const MachineSDNode *) { return true; } static bool classof(const SDNode *N) { return N->isMachineOpcode(); } diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index c52599b..b46d153 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 { @@ -631,17 +632,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 new file mode 100644 index 0000000..4c4a2a8 --- /dev/null +++ b/include/llvm/CodeGen/TargetSchedule.h @@ -0,0 +1,167 @@ +//===-- llvm/CodeGen/TargetSchedule.h - Sched Machine Model -----*- 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 a wrapper around MCSchedModel that allows the interface to +// benefit from information currently only available in TargetInstrInfo. +// Ideally, the scheduling interface would be fully defined in the MC layer. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TARGET_TARGETSCHEDMODEL_H +#define LLVM_TARGET_TARGETSCHEDMODEL_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/MC/MCInstrItineraries.h" +#include "llvm/MC/MCSchedule.h" +#include "llvm/Target/TargetSubtargetInfo.h" + +namespace llvm { + +class TargetRegisterInfo; +class TargetSubtargetInfo; +class TargetInstrInfo; +class MachineInstr; + +/// Provide an instruction scheduling machine model to CodeGen passes. +class TargetSchedModel { + // For efficiency, hold a copy of the statically defined MCSchedModel for this + // processor. + MCSchedModel SchedModel; + InstrItineraryData InstrItins; + const TargetSubtargetInfo *STI; + const TargetInstrInfo *TII; + + SmallVector<unsigned, 16> ResourceFactors; + unsigned MicroOpFactor; // Multiply to normalize microops to resource units. + unsigned ResourceLCM; // Resource units per cycle. Latency normalization factor. +public: + TargetSchedModel(): STI(0), TII(0) {} + + /// \brief Initialize the machine model for instruction scheduling. + /// + /// The machine model API keeps a copy of the top-level MCSchedModel table + /// indices and may query TargetSubtargetInfo and TargetInstrInfo to resolve + /// dynamic properties. + void init(const MCSchedModel &sm, const TargetSubtargetInfo *sti, + const TargetInstrInfo *tii); + + /// Return the MCSchedClassDesc for this instruction. + const MCSchedClassDesc *resolveSchedClass(const MachineInstr *MI) const; + + /// \brief TargetInstrInfo getter. + const TargetInstrInfo *getInstrInfo() const { return TII; } + + /// \brief Return true if this machine model includes an instruction-level + /// scheduling model. + /// + /// This is more detailed than the course grain IssueWidth and default + /// latency properties, but separate from the per-cycle itinerary data. + bool hasInstrSchedModel() const; + + const MCSchedModel *getMCSchedModel() const { return &SchedModel; } + + /// \brief Return true if this machine model includes cycle-to-cycle itinerary + /// data. + /// + /// This models scheduling at each stage in the processor pipeline. + bool hasInstrItineraries() const; + + const InstrItineraryData *getInstrItineraries() const { + if (hasInstrItineraries()) + return &InstrItins; + return 0; + } + + /// \brief Identify the processor corresponding to the current subtarget. + unsigned getProcessorID() const { return SchedModel.getProcessorID(); } + + /// \brief Maximum number of micro-ops that may be scheduled per cycle. + unsigned getIssueWidth() const { return SchedModel.IssueWidth; } + + /// \brief Return the number of issue slots required for this MI. + unsigned getNumMicroOps(const MachineInstr *MI, + const MCSchedClassDesc *SC = 0) const; + + /// \brief Get the number of kinds of resources for this target. + unsigned getNumProcResourceKinds() const { + return SchedModel.getNumProcResourceKinds(); + } + + /// \brief Get a processor resource by ID for convenience. + const MCProcResourceDesc *getProcResource(unsigned PIdx) const { + return SchedModel.getProcResource(PIdx); + } + + typedef const MCWriteProcResEntry *ProcResIter; + + // \brief Get an iterator into the processor resources consumed by this + // scheduling class. + ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const { + // The subtarget holds a single resource table for all processors. + return STI->getWriteProcResBegin(SC); + } + ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const { + return STI->getWriteProcResEnd(SC); + } + + /// \brief Multiply the number of units consumed for a resource by this factor + /// to normalize it relative to other resources. + unsigned getResourceFactor(unsigned ResIdx) const { + return ResourceFactors[ResIdx]; + } + + /// \brief Multiply number of micro-ops by this factor to normalize it + /// relative to other resources. + unsigned getMicroOpFactor() const { + return MicroOpFactor; + } + + /// \brief Multiply cycle count by this factor to normalize it relative to + /// other resources. This is the number of resource units per cycle. + unsigned getLatencyFactor() const { + return ResourceLCM; + } + + /// \brief Compute operand latency based on the available machine model. + /// + /// Computes and return the latency of the given data dependent def and use + /// when the operand indices are already known. UseMI may be NULL for an + /// unknown user. + /// + /// FindMin may be set to get the minimum vs. expected latency. Minimum + /// latency is used for scheduling groups, while expected latency is for + /// instruction cost and critical path. + unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, + const MachineInstr *UseMI, unsigned UseOperIdx, + bool FindMin) const; + + /// \brief Compute the instruction latency based on the available machine + /// model. + /// + /// Compute and return the expected latency of this instruction independent of + /// a particular use. computeOperandLatency is the prefered API, but this is + /// occasionally useful to help estimate instruction cost. + unsigned computeInstrLatency(const MachineInstr *MI) const; + + /// \brief Output dependency latency of a pair of defs of the same register. + /// + /// This is typically one cycle. + unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefIdx, + const MachineInstr *DepMI) const; + +private: + /// getDefLatency is a helper for computeOperandLatency. Return the + /// instruction's latency if operand lookup is not required. + /// Otherwise return -1. + int getDefLatency(const MachineInstr *DefMI, bool FindMin) const; +}; + +} // namespace llvm + +#endif diff --git a/include/llvm/CodeGen/ValueTypes.h b/include/llvm/CodeGen/ValueTypes.h index eb38cd3..f8a6503 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 @@ -56,50 +60,65 @@ namespace llvm { FIRST_FP_VALUETYPE = f16, LAST_FP_VALUETYPE = ppcf128, - v2i8 = 13, // 2 x i8 - v4i8 = 14, // 4 x i8 - v8i8 = 15, // 8 x i8 - v16i8 = 16, // 16 x i8 - v32i8 = 17, // 32 x i8 - v2i16 = 18, // 2 x i16 - v4i16 = 19, // 4 x i16 - v8i16 = 20, // 8 x i16 - v16i16 = 21, // 16 x i16 - v2i32 = 22, // 2 x i32 - v4i32 = 23, // 4 x i32 - v8i32 = 24, // 8 x i32 - v16i32 = 25, // 16 x i32 - v1i64 = 26, // 1 x i64 - v2i64 = 27, // 2 x i64 - v4i64 = 28, // 4 x i64 - v8i64 = 29, // 8 x i64 - v16i64 = 30, // 16 x i64 - - v2f16 = 31, // 2 x f16 - v2f32 = 32, // 2 x f32 - v4f32 = 33, // 4 x f32 - v8f32 = 34, // 8 x f32 - v2f64 = 35, // 2 x f64 - v4f64 = 36, // 4 x f64 - - FIRST_VECTOR_VALUETYPE = v2i8, - LAST_VECTOR_VALUETYPE = v4f64, - FIRST_INTEGER_VECTOR_VALUETYPE = v2i8, + v2i1 = 13, // 2 x i1 + v4i1 = 14, // 4 x i1 + v8i1 = 15, // 8 x i1 + v16i1 = 16, // 16 x i1 + 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_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 = 37, // This is an X86 MMX value + FIRST_VECTOR_VALUETYPE = v2i1, + LAST_VECTOR_VALUETYPE = v8f64, - Glue = 38, // This glues nodes together during pre-RA sched + x86mmx = 49, // This is an X86 MMX value - isVoid = 39, // This has no value + Glue = 50, // This glues nodes together during pre-RA sched - Untyped = 40, // This value takes a register, but has + isVoid = 51, // This has no value + + Untyped = 52, // This value takes a register, but has // unspecified type. The register class // will be determined by the opcode. - LAST_VALUETYPE = 41, // 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 @@ -131,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; @@ -175,6 +187,18 @@ namespace llvm { SimpleTy <= MVT::LAST_VECTOR_VALUETYPE); } + /// is16BitVector - Return true if this is a 16-bit vector type. + bool is16BitVector() const { + return (SimpleTy == MVT::v2i8 || SimpleTy == MVT::v1i16 || + SimpleTy == MVT::v16i1); + } + + /// is32BitVector - Return true if this is a 32-bit vector type. + bool is32BitVector() const { + return (SimpleTy == MVT::v4i8 || SimpleTy == MVT::v2i16 || + SimpleTy == MVT::v1i32); + } + /// is64BitVector - Return true if this is a 64-bit vector type. bool is64BitVector() const { return (SimpleTy == MVT::v8i8 || SimpleTy == MVT::v4i16 || @@ -198,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. @@ -233,15 +259,25 @@ namespace llvm { switch (SimpleTy) { default: llvm_unreachable("Not a vector MVT!"); + case v2i1 : + case v4i1 : + case v8i1 : + 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: case v8i32: @@ -254,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; } } @@ -264,22 +302,32 @@ 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 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: case v4i32: case v4i64: case v4f32: case v4f64: return 4; + case v2i1: case v2i8: case v2i16: case v2i32: @@ -287,6 +335,8 @@ namespace llvm { case v2f16: case v2f32: case v2f64: return 2; + case v1i16: + case v1i32: case v1i64: return 1; } } @@ -298,22 +348,33 @@ 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; - case i8 : return 8; + case v2i1: return 2; + case v4i1: return 4; + case i8 : + case v8i1: return 8; case i16 : case f16: - case v2i8: return 16; + case v16i1: + case v2i8: + case v1i16: return 16; case f32 : case i32 : + case v32i1: case v4i8: case v2i16: - case v2f16: return 32; + case v2f16: + case v1i32: return 32; case x86mmx: case f64 : case i64 : + case v64i1: case v8i8: case v4i16: case v2i32: @@ -335,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; } } @@ -353,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: @@ -393,20 +479,32 @@ namespace llvm { switch (VT.SimpleTy) { default: break; + case MVT::i1: + if (NumElements == 2) return MVT::v2i1; + 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; if (NumElements == 4) return MVT::v4i8; 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; if (NumElements == 2) return MVT::v2i16; 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; if (NumElements == 2) return MVT::v2i32; if (NumElements == 4) return MVT::v4i32; if (NumElements == 8) return MVT::v8i32; @@ -426,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); + }; @@ -457,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; } @@ -473,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); } @@ -482,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); } @@ -497,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; } @@ -505,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 @@ -529,6 +635,16 @@ namespace llvm { return isSimple() ? V.isVector() : isExtendedVector(); } + /// is16BitVector - Return true if this is a 16-bit vector type. + bool is16BitVector() const { + return isSimple() ? V.is16BitVector() : isExtended16BitVector(); + } + + /// is32BitVector - Return true if this is a 32-bit vector type. + bool is32BitVector() const { + return isSimple() ? V.is32BitVector() : isExtended32BitVector(); + } + /// is64BitVector - Return true if this is a 64-bit vector type. bool is64BitVector() const { return isSimple() ? V.is64BitVector() : isExtended64BitVector(); @@ -740,6 +856,8 @@ namespace llvm { bool isExtendedFloatingPoint() const; bool isExtendedInteger() const; bool isExtendedVector() const; + bool isExtended16BitVector() const; + bool isExtended32BitVector() const; bool isExtended64BitVector() const; bool isExtended128BitVector() const; bool isExtended256BitVector() const; diff --git a/include/llvm/CodeGen/ValueTypes.td b/include/llvm/CodeGen/ValueTypes.td index f4b75bd..76df6ac 100644 --- a/include/llvm/CodeGen/ValueTypes.td +++ b/include/llvm/CodeGen/ValueTypes.td @@ -33,37 +33,49 @@ def f80 : ValueType<80 , 10>; // 80-bit floating point value def f128 : ValueType<128, 11>; // 128-bit floating point value def ppcf128: ValueType<128, 12>; // PPC 128-bit floating point value -def v2i8 : ValueType<16 , 13>; // 2 x i8 vector value -def v4i8 : ValueType<32 , 14>; // 4 x i8 vector value -def v8i8 : ValueType<64 , 15>; // 8 x i8 vector value -def v16i8 : ValueType<128, 16>; // 16 x i8 vector value -def v32i8 : ValueType<256, 17>; // 32 x i8 vector value -def v2i16 : ValueType<32 , 18>; // 2 x i16 vector value -def v4i16 : ValueType<64 , 19>; // 4 x i16 vector value -def v8i16 : ValueType<128, 20>; // 8 x i16 vector value -def v16i16 : ValueType<256, 21>; // 16 x i16 vector value -def v2i32 : ValueType<64 , 22>; // 2 x i32 vector value -def v4i32 : ValueType<128, 23>; // 4 x i32 vector value -def v8i32 : ValueType<256, 24>; // 8 x i32 vector value -def v16i32 : ValueType<512, 25>; // 16 x i32 vector value -def v1i64 : ValueType<64 , 26>; // 1 x i64 vector value -def v2i64 : ValueType<128, 27>; // 2 x i64 vector value -def v4i64 : ValueType<256, 28>; // 4 x i64 vector value -def v8i64 : ValueType<512, 29>; // 8 x i64 vector value -def v16i64 : ValueType<1024,30>; // 16 x i64 vector value +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 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 , 31>; // 2 x f16 vector value -def v2f32 : ValueType<64 , 32>; // 2 x f32 vector value -def v4f32 : ValueType<128, 33>; // 4 x f32 vector value -def v8f32 : ValueType<256, 34>; // 8 x f32 vector value -def v2f64 : ValueType<128, 35>; // 2 x f64 vector value -def v4f64 : ValueType<256, 36>; // 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 , 37>; // X86 MMX value -def FlagVT : ValueType<0 , 38>; // Pre-RA sched glue -def isVoid : ValueType<0 , 39>; // Produces no value -def untyped: ValueType<8 , 40>; // 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 |