LLVM API Documentation
00001 //===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by Evan Cheng and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the ScheduleDAG class, which is used as the common 00011 // base class for SelectionDAG-based instruction scheduler. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H 00016 #define LLVM_CODEGEN_SCHEDULEDAG_H 00017 00018 #include "llvm/CodeGen/SelectionDAG.h" 00019 00020 namespace llvm { 00021 struct InstrStage; 00022 class MachineConstantPool; 00023 class MachineDebugInfo; 00024 class MachineInstr; 00025 class MRegisterInfo; 00026 class SelectionDAG; 00027 class SSARegMap; 00028 class TargetInstrInfo; 00029 class TargetInstrDescriptor; 00030 class TargetMachine; 00031 00032 /// HazardRecognizer - This determines whether or not an instruction can be 00033 /// issued this cycle, and whether or not a noop needs to be inserted to handle 00034 /// the hazard. 00035 class HazardRecognizer { 00036 public: 00037 virtual ~HazardRecognizer(); 00038 00039 enum HazardType { 00040 NoHazard, // This instruction can be emitted at this cycle. 00041 Hazard, // This instruction can't be emitted at this cycle. 00042 NoopHazard, // This instruction can't be emitted, and needs noops. 00043 }; 00044 00045 /// getHazardType - Return the hazard type of emitting this node. There are 00046 /// three possible results. Either: 00047 /// * NoHazard: it is legal to issue this instruction on this cycle. 00048 /// * Hazard: issuing this instruction would stall the machine. If some 00049 /// other instruction is available, issue it first. 00050 /// * NoopHazard: issuing this instruction would break the program. If 00051 /// some other instruction can be issued, do so, otherwise issue a noop. 00052 virtual HazardType getHazardType(SDNode *Node) { 00053 return NoHazard; 00054 } 00055 00056 /// EmitInstruction - This callback is invoked when an instruction is 00057 /// emitted, to advance the hazard state. 00058 virtual void EmitInstruction(SDNode *Node) { 00059 } 00060 00061 /// AdvanceCycle - This callback is invoked when no instructions can be 00062 /// issued on this cycle without a hazard. This should increment the 00063 /// internal state of the hazard recognizer so that previously "Hazard" 00064 /// instructions will now not be hazards. 00065 virtual void AdvanceCycle() { 00066 } 00067 00068 /// EmitNoop - This callback is invoked when a noop was added to the 00069 /// instruction stream. 00070 virtual void EmitNoop() { 00071 } 00072 }; 00073 00074 class ScheduleDAG { 00075 public: 00076 SelectionDAG &DAG; // DAG of the current basic block 00077 MachineBasicBlock *BB; // Current basic block 00078 const TargetMachine &TM; // Target processor 00079 const TargetInstrInfo *TII; // Target instruction information 00080 const MRegisterInfo *MRI; // Target processor register info 00081 SSARegMap *RegMap; // Virtual/real register map 00082 MachineConstantPool *ConstPool; // Target constant pool 00083 00084 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, 00085 const TargetMachine &tm) 00086 : DAG(dag), BB(bb), TM(tm) {} 00087 00088 virtual ~ScheduleDAG() {} 00089 00090 /// Run - perform scheduling. 00091 /// 00092 MachineBasicBlock *Run(); 00093 00094 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 00095 /// 00096 static bool isPassiveNode(SDNode *Node) { 00097 if (isa<ConstantSDNode>(Node)) return true; 00098 if (isa<RegisterSDNode>(Node)) return true; 00099 if (isa<GlobalAddressSDNode>(Node)) return true; 00100 if (isa<BasicBlockSDNode>(Node)) return true; 00101 if (isa<FrameIndexSDNode>(Node)) return true; 00102 if (isa<ConstantPoolSDNode>(Node)) return true; 00103 if (isa<ExternalSymbolSDNode>(Node)) return true; 00104 return false; 00105 } 00106 00107 /// EmitNode - Generate machine code for an node and needed dependencies. 00108 /// VRBaseMap contains, for each already emitted node, the first virtual 00109 /// register number for the results of the node. 00110 /// 00111 void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap); 00112 00113 /// EmitNoop - Emit a noop instruction. 00114 /// 00115 void EmitNoop(); 00116 00117 00118 /// Schedule - Order nodes according to selected style. 00119 /// 00120 virtual void Schedule() {} 00121 00122 private: 00123 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, 00124 const TargetInstrDescriptor *II, 00125 std::map<SDNode*, unsigned> &VRBaseMap); 00126 }; 00127 00128 ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB); 00129 00130 /// createSimpleDAGScheduler - This creates a simple two pass instruction 00131 /// scheduler. 00132 ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG, 00133 MachineBasicBlock *BB); 00134 00135 /// createBURRListDAGScheduler - This creates a bottom up register usage 00136 /// reduction list scheduler. 00137 ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG, 00138 MachineBasicBlock *BB); 00139 00140 /// createTDListDAGScheduler - This creates a top-down list scheduler with 00141 /// the specified hazard recognizer. This takes ownership of the hazard 00142 /// recognizer and deletes it when done. 00143 ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG, 00144 MachineBasicBlock *BB, 00145 HazardRecognizer *HR); 00146 } 00147 00148 #endif