ScheduleDAG.h revision a34b6f8713cd065306b07aafb1c978c30bc64947 
1//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Evan Cheng and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the ScheduleDAG class, which is used as the common
11// base class for SelectionDAG-based instruction scheduler.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CODEGEN_SCHEDULEDAG_H
16#define LLVM_CODEGEN_SCHEDULEDAG_H
17
18#include "llvm/CodeGen/SelectionDAG.h"
19
20namespace llvm {
21  struct InstrStage;
22  class MachineConstantPool;
23  class MachineDebugInfo;
24  class MachineInstr;
25  class MRegisterInfo;
26  class SelectionDAG;
27  class SSARegMap;
28  class TargetInstrInfo;
29  class TargetInstrDescriptor;
30  class TargetMachine;
31
32  /// HazardRecognizer - This determines whether or not an instruction can be
33  /// issued this cycle, and whether or not a noop needs to be inserted to handle
34  /// the hazard.
35  class HazardRecognizer {
36  public:
37    virtual ~HazardRecognizer();
38
39    enum HazardType {
40      NoHazard,      // This instruction can be emitted at this cycle.
41      Hazard,        // This instruction can't be emitted at this cycle.
42      NoopHazard,    // This instruction can't be emitted, and needs noops.
43    };
44
45    /// getHazardType - Return the hazard type of emitting this node.  There are
46    /// three possible results.  Either:
47    ///  * NoHazard: it is legal to issue this instruction on this cycle.
48    ///  * Hazard: issuing this instruction would stall the machine.  If some
49    ///     other instruction is available, issue it first.
50    ///  * NoopHazard: issuing this instruction would break the program.  If
51    ///     some other instruction can be issued, do so, otherwise issue a noop.
52    virtual HazardType getHazardType(SDNode *Node) {
53      return NoHazard;
54    }
55
56    /// EmitInstruction - This callback is invoked when an instruction is
57    /// emitted, to advance the hazard state.
58    virtual void EmitInstruction(SDNode *Node) {
59    }
60
61    /// AdvanceCycle - This callback is invoked when no instructions can be
62    /// issued on this cycle without a hazard.  This should increment the
63    /// internal state of the hazard recognizer so that previously "Hazard"
64    /// instructions will now not be hazards.
65    virtual void AdvanceCycle() {
66    }
67
68    /// EmitNoop - This callback is invoked when a noop was added to the
69    /// instruction stream.
70    virtual void EmitNoop() {
71    }
72  };
73
74  class ScheduleDAG {
75  public:
76    SelectionDAG &DAG;                    // DAG of the current basic block
77    MachineBasicBlock *BB;                // Current basic block
78    const TargetMachine &TM;              // Target processor
79    const TargetInstrInfo *TII;           // Target instruction information
80    const MRegisterInfo *MRI;             // Target processor register info
81    SSARegMap *RegMap;                    // Virtual/real register map
82    MachineConstantPool *ConstPool;       // Target constant pool
83
84    ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
85                const TargetMachine &tm)
86      : DAG(dag), BB(bb), TM(tm) {}
87
88    virtual ~ScheduleDAG() {}
89
90    /// Run - perform scheduling.
91    ///
92    MachineBasicBlock *Run();
93
94    /// isPassiveNode - Return true if the node is a non-scheduled leaf.
95    ///
96    static bool isPassiveNode(SDNode *Node) {
97      if (isa<ConstantSDNode>(Node))       return true;
98      if (isa<RegisterSDNode>(Node))       return true;
99      if (isa<GlobalAddressSDNode>(Node))  return true;
100      if (isa<BasicBlockSDNode>(Node))     return true;
101      if (isa<FrameIndexSDNode>(Node))     return true;
102      if (isa<ConstantPoolSDNode>(Node))   return true;
103      if (isa<ExternalSymbolSDNode>(Node)) return true;
104      return false;
105    }
106
107    /// EmitNode - Generate machine code for an node and needed dependencies.
108    /// VRBaseMap contains, for each already emitted node, the first virtual
109    /// register number for the results of the node.
110    ///
111    void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
112
113    /// EmitNoop - Emit a noop instruction.
114    ///
115    void EmitNoop();
116
117
118    /// Schedule - Order nodes according to selected style.
119    ///
120    virtual void Schedule() {}
121
122  private:
123    void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
124                    const TargetInstrDescriptor *II,
125                    std::map<SDNode*, unsigned> &VRBaseMap);
126  };
127
128  ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB);
129
130  /// createSimpleDAGScheduler - This creates a simple two pass instruction
131  /// scheduler.
132  ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG,
133                                        MachineBasicBlock *BB);
134
135  /// createBURRListDAGScheduler - This creates a bottom up register usage
136  /// reduction list scheduler.
137  ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
138                                          MachineBasicBlock *BB);
139
140  /// createTDListDAGScheduler - This creates a top-down list scheduler with
141  /// the specified hazard recognizer.  This takes ownership of the hazard
142  /// recognizer and deletes it when done.
143  ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
144                                        MachineBasicBlock *BB,
145                                        HazardRecognizer *HR);
146}
147
148#endif
149