LLVM API Documentation

ScheduleDAG.h

Go to the documentation of this file.
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