X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FSelectionDAGISel.h;h=09be4fb5ebff9dbffab3ea8956837ee50c1c7383;hb=7b8c2f8587763e0a8ce48f9b7b67287930129c8d;hp=64c3b25591a807a2d59115fabfc33feff3a54447;hpb=f350b277f32d7d47f86c0e54f4aec4d470500618;p=oota-llvm.git diff --git a/include/llvm/CodeGen/SelectionDAGISel.h b/include/llvm/CodeGen/SelectionDAGISel.h index 64c3b25591a..09be4fb5ebf 100644 --- a/include/llvm/CodeGen/SelectionDAGISel.h +++ b/include/llvm/CodeGen/SelectionDAGISel.h @@ -17,54 +17,63 @@ #include "llvm/BasicBlock.h" #include "llvm/Pass.h" -#include "llvm/Constant.h" #include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/CodeGen/MachineFunctionPass.h" namespace llvm { - class SelectionDAGLowering; + class FastISel; + class SelectionDAGBuilder; class SDValue; class MachineRegisterInfo; class MachineBasicBlock; class MachineFunction; class MachineInstr; class TargetLowering; + class TargetInstrInfo; class FunctionLoweringInfo; - class HazardRecognizer; + class ScheduleHazardRecognizer; class GCFunctionInfo; - class ScheduleDAG; - + class ScheduleDAGSDNodes; + class LoadInst; + /// SelectionDAGISel - This is the common base class used for SelectionDAG-based /// pattern-matching instruction selectors. -class SelectionDAGISel : public FunctionPass { +class SelectionDAGISel : public MachineFunctionPass { public: - TargetLowering &TLI; + const TargetMachine &TM; + const TargetLowering &TLI; + FunctionLoweringInfo *FuncInfo; + MachineFunction *MF; MachineRegisterInfo *RegInfo; SelectionDAG *CurDAG; - MachineBasicBlock *BB; + SelectionDAGBuilder *SDB; AliasAnalysis *AA; GCFunctionInfo *GFI; - bool Fast; - std::vector TopOrder; + CodeGenOpt::Level OptLevel; static char ID; - explicit SelectionDAGISel(TargetLowering &tli, bool fast = false) : - FunctionPass((intptr_t)&ID), TLI(tli), GFI(), Fast(fast), DAGSize(0) {} - - TargetLowering &getTargetLowering() { return TLI; } + explicit SelectionDAGISel(const TargetMachine &tm, + CodeGenOpt::Level OL = CodeGenOpt::Default); + virtual ~SelectionDAGISel(); + + const TargetLowering &getTargetLowering() { return TLI; } virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual bool runOnFunction(Function &Fn); + virtual bool runOnMachineFunction(MachineFunction &MF); - unsigned MakeReg(MVT VT); + virtual void EmitFunctionEntryCode() {} - virtual void EmitFunctionEntryCode(Function &Fn, MachineFunction &MF) {} - virtual void InstructionSelect() = 0; - virtual void InstructionSelectPostProcessing() {} - - void SelectRootInit() { - DAGSize = CurDAG->AssignTopologicalOrder(TopOrder); - } + /// PreprocessISelDAG - This hook allows targets to hack on the graph before + /// instruction selection starts. + virtual void PreprocessISelDAG() {} + + /// PostprocessISelDAG() - This hook allows the target to hack on the graph + /// right after selection. + virtual void PostprocessISelDAG() {} + + /// Select - Main hook targets implement to select a node. + virtual SDNode *Select(SDNode *N) = 0; /// SelectInlineAsmMemoryOperand - Select the specified address as a target /// addressing mode, according to the specified constraint code. If this does @@ -77,140 +86,227 @@ public: return true; } - /// CanBeFoldedBy - Returns true if the specific operand node N of U can be - /// folded during instruction selection that starts at Root? - virtual bool CanBeFoldedBy(SDNode *N, SDNode *U, SDNode *Root) const { - return true; - } - - /// CreateTargetHazardRecognizer - Return a newly allocated hazard recognizer - /// to use for this target when scheduling the DAG. - virtual HazardRecognizer *CreateTargetHazardRecognizer(); - - /// CaseBlock - This structure is used to communicate between SDLowering and - /// SDISel for the code generation of additional basic blocks needed by multi- - /// case switch statements. - struct CaseBlock { - CaseBlock(ISD::CondCode cc, Value *cmplhs, Value *cmprhs, Value *cmpmiddle, - MachineBasicBlock *truebb, MachineBasicBlock *falsebb, - MachineBasicBlock *me) - : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), - TrueBB(truebb), FalseBB(falsebb), ThisBB(me) {} - // CC - the condition code to use for the case block's setcc node - ISD::CondCode CC; - // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit. - // Emit by default LHS op RHS. MHS is used for range comparisons: - // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). - Value *CmpLHS, *CmpMHS, *CmpRHS; - // TrueBB/FalseBB - the block to branch to if the setcc is true/false. - MachineBasicBlock *TrueBB, *FalseBB; - // ThisBB - the block into which to emit the code for the setcc and branches - MachineBasicBlock *ThisBB; - }; - struct JumpTable { - JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, - MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {} - - /// Reg - the virtual register containing the index of the jump table entry - //. to jump to. - unsigned Reg; - /// JTI - the JumpTableIndex for this jump table in the function. - unsigned JTI; - /// MBB - the MBB into which to emit the code for the indirect jump. - MachineBasicBlock *MBB; - /// Default - the MBB of the default bb, which is a successor of the range - /// check MBB. This is when updating PHI nodes in successors. - MachineBasicBlock *Default; - }; - struct JumpTableHeader { - JumpTableHeader(uint64_t F, uint64_t L, Value* SV, MachineBasicBlock* H, - bool E = false): - First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {} - uint64_t First; - uint64_t Last; - Value *SValue; - MachineBasicBlock *HeaderBB; - bool Emitted; - }; - typedef std::pair JumpTableBlock; - - struct BitTestCase { - BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr): - Mask(M), ThisBB(T), TargetBB(Tr) { } - uint64_t Mask; - MachineBasicBlock* ThisBB; - MachineBasicBlock* TargetBB; + /// IsProfitableToFold - Returns true if it's profitable to fold the specific + /// operand node N of U during instruction selection that starts at Root. + virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const; + + /// IsLegalToFold - Returns true if the specific operand node N of + /// U can be folded during instruction selection that starts at Root. + /// FIXME: This is a static member function because the MSP430/X86 + /// targets, which uses it during isel. This could become a proper member. + static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, + CodeGenOpt::Level OptLevel, + bool IgnoreChains = false); + + // Opcodes used by the DAG state machine: + enum BuiltinOpcodes { + OPC_Scope, + OPC_RecordNode, + OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3, + OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7, + OPC_RecordMemRef, + OPC_CaptureGlueInput, + OPC_MoveChild, + OPC_MoveParent, + OPC_CheckSame, + OPC_CheckPatternPredicate, + OPC_CheckPredicate, + OPC_CheckOpcode, + OPC_SwitchOpcode, + OPC_CheckType, + OPC_SwitchType, + OPC_CheckChild0Type, OPC_CheckChild1Type, OPC_CheckChild2Type, + OPC_CheckChild3Type, OPC_CheckChild4Type, OPC_CheckChild5Type, + OPC_CheckChild6Type, OPC_CheckChild7Type, + OPC_CheckInteger, + OPC_CheckCondCode, + OPC_CheckValueType, + OPC_CheckComplexPat, + OPC_CheckAndImm, OPC_CheckOrImm, + OPC_CheckFoldableChainNode, + + OPC_EmitInteger, + OPC_EmitRegister, + OPC_EmitRegister2, + OPC_EmitConvertToTarget, + OPC_EmitMergeInputChains, + OPC_EmitMergeInputChains1_0, + OPC_EmitMergeInputChains1_1, + OPC_EmitCopyToReg, + OPC_EmitNodeXForm, + OPC_EmitNode, + OPC_MorphNodeTo, + OPC_MarkGlueResults, + OPC_CompleteMatch }; - - typedef SmallVector BitTestInfo; - - struct BitTestBlock { - BitTestBlock(uint64_t F, uint64_t R, Value* SV, - unsigned Rg, bool E, - MachineBasicBlock* P, MachineBasicBlock* D, - const BitTestInfo& C): - First(F), Range(R), SValue(SV), Reg(Rg), Emitted(E), - Parent(P), Default(D), Cases(C) { } - uint64_t First; - uint64_t Range; - Value *SValue; - unsigned Reg; - bool Emitted; - MachineBasicBlock *Parent; - MachineBasicBlock *Default; - BitTestInfo Cases; + + enum { + OPFL_None = 0, // Node has no chain or glue input and isn't variadic. + OPFL_Chain = 1, // Node has a chain input. + OPFL_GlueInput = 2, // Node has a glue input. + OPFL_GlueOutput = 4, // Node has a glue output. + OPFL_MemRefs = 8, // Node gets accumulated MemRefs. + OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs. + OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs. + OPFL_Variadic2 = 3<<4, // Node is variadic, root has 2 fixed inputs. + OPFL_Variadic3 = 4<<4, // Node is variadic, root has 3 fixed inputs. + OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs. + OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs. + OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs. + + OPFL_VariadicInfo = OPFL_Variadic6 }; - + + /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the + /// number of fixed arity values that should be skipped when copying from the + /// root. + static inline int getNumFixedFromVariadicInfo(unsigned Flags) { + return ((Flags&OPFL_VariadicInfo) >> 4)-1; + } + + protected: /// DAGSize - Size of DAG being instruction selected. /// unsigned DAGSize; + /// ISelPosition - Node iterator marking the current position of + /// instruction selection as it procedes through the topologically-sorted + /// node list. + SelectionDAG::allnodes_iterator ISelPosition; + + + /// ISelUpdater - helper class to handle updates of the + /// instruction selection graph. + class ISelUpdater : public SelectionDAG::DAGUpdateListener { + SelectionDAG::allnodes_iterator &ISelPosition; + public: + explicit ISelUpdater(SelectionDAG::allnodes_iterator &isp) + : ISelPosition(isp) {} + + /// NodeDeleted - Handle nodes deleted from the graph. If the + /// node being deleted is the current ISelPosition node, update + /// ISelPosition. + /// + virtual void NodeDeleted(SDNode *N, SDNode *E) { + if (ISelPosition == SelectionDAG::allnodes_iterator(N)) + ++ISelPosition; + } + + /// NodeUpdated - Ignore updates for now. + virtual void NodeUpdated(SDNode *N) {} + }; + + /// ReplaceUses - replace all uses of the old node F with the use + /// of the new node T. + void ReplaceUses(SDValue F, SDValue T) { + ISelUpdater ISU(ISelPosition); + CurDAG->ReplaceAllUsesOfValueWith(F, T, &ISU); + } + + /// ReplaceUses - replace all uses of the old nodes F with the use + /// of the new nodes T. + void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) { + ISelUpdater ISU(ISelPosition); + CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num, &ISU); + } + + /// ReplaceUses - replace all uses of the old node F with the use + /// of the new node T. + void ReplaceUses(SDNode *F, SDNode *T) { + ISelUpdater ISU(ISelPosition); + CurDAG->ReplaceAllUsesWith(F, T, &ISU); + } + + /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated /// by tblgen. Others should not call it. void SelectInlineAsmMemoryOperands(std::vector &Ops); + +public: // Calls to these predicates are generated by tblgen. bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const; bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const; - + + + /// CheckPatternPredicate - This function is generated by tblgen in the + /// target. It runs the specified pattern predicate and returns true if it + /// succeeds or false if it fails. The number is a private implementation + /// detail to the code tblgen produces. + virtual bool CheckPatternPredicate(unsigned PredNo) const { + assert(0 && "Tblgen should generate the implementation of this!"); + return 0; + } + + /// CheckNodePredicate - This function is generated by tblgen in the target. + /// It runs node predicate number PredNo and returns true if it succeeds or + /// false if it fails. The number is a private implementation + /// detail to the code tblgen produces. + virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const { + assert(0 && "Tblgen should generate the implementation of this!"); + return 0; + } + + virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N, + unsigned PatternNo, + SmallVectorImpl > &Result) { + assert(0 && "Tblgen should generate the implementation of this!"); + return false; + } + + virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) { + assert(0 && "Tblgen should generate this!"); + return SDValue(); + } + + SDNode *SelectCodeCommon(SDNode *NodeToMatch, + const unsigned char *MatcherTable, + unsigned TableSize); + private: - void SelectAllBasicBlocks(Function &Fn, MachineFunction &MF, - FunctionLoweringInfo &FuncInfo); - void FinishBasicBlock(FunctionLoweringInfo &FuncInfo, - std::vector > &PHINodesToUpdate); - - void SelectBasicBlock(BasicBlock *LLVMBB, - BasicBlock::iterator Begin, - BasicBlock::iterator End, - bool DoArgs, - std::vector > &PHINodesToUpdate, - FunctionLoweringInfo &FuncInfo); + + // Calls to these functions are generated by tblgen. + SDNode *Select_INLINEASM(SDNode *N); + SDNode *Select_UNDEF(SDNode *N); + void CannotYetSelect(SDNode *N); + +private: + void DoInstructionSelection(); + SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTs, + const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo); + + void PrepareEHLandingPad(); + void SelectAllBasicBlocks(const Function &Fn); + bool TryToFoldFastISelLoad(const LoadInst *LI, const Instruction *FoldInst, + FastISel *FastIS); + void FinishBasicBlock(); + + void SelectBasicBlock(BasicBlock::const_iterator Begin, + BasicBlock::const_iterator End, + bool &HadTailCall); void CodeGenAndEmitDAG(); - void LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL); - - void ComputeLiveOutVRegInfo(); + void LowerArguments(const BasicBlock *BB); - void HandlePHINodesInSuccessorBlocks(BasicBlock *LLVMBB, - FunctionLoweringInfo &FuncInfo, - std::vector > &PHINodesToUpdate, - SelectionDAGLowering &SDL); + void ComputeLiveOutVRegInfo(); - /// Pick a safe ordering for instructions for each target node in the - /// graph. - ScheduleDAG *Schedule(); + /// Create the scheduler. If a specific scheduler was specified + /// via the SchedulerRegistry, use it, otherwise select the + /// one preferred by the target. + /// + ScheduleDAGSDNodes *CreateScheduler(); - /// SwitchCases - Vector of CaseBlock structures used to communicate - /// SwitchInst code generation information. - std::vector SwitchCases; + /// OpcodeOffset - This is a cache used to dispatch efficiently into isel + /// state machines that start with a OPC_SwitchOpcode node. + std::vector OpcodeOffset; - /// JTCases - Vector of JumpTable structures which holds necessary information - /// for emitting a jump tables during SwitchInst code generation. - std::vector JTCases; + void UpdateChainsAndGlue(SDNode *NodeToMatch, SDValue InputChain, + const SmallVectorImpl &ChainNodesMatched, + SDValue InputGlue, const SmallVectorImpl &F, + bool isMorphNodeTo); - std::vector BitTestCases; }; }