ScheduleDAGInstrs.h revision bfdf7f38523bd38ae0538861a2bfd8bdc46e5c33 
1//==- ScheduleDAGInstrs.h - MachineInstr Scheduling --------------*- C++ -*-==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the ScheduleDAGInstrs class, which implements
11// scheduling for a MachineInstr-based dependency graph.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef SCHEDULEDAGINSTRS_H
16#define SCHEDULEDAGINSTRS_H
17
18#include "llvm/CodeGen/MachineDominators.h"
19#include "llvm/CodeGen/MachineLoopInfo.h"
20#include "llvm/CodeGen/ScheduleDAG.h"
21#include "llvm/Support/Compiler.h"
22#include "llvm/Target/TargetRegisterInfo.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/SmallSet.h"
25#include <map>
26
27namespace llvm {
28  class MachineLoopInfo;
29  class MachineDominatorTree;
30
31  /// LoopDependencies - This class analyzes loop-oriented register
32  /// dependencies, which are used to guide scheduling decisions.
33  /// For example, loop induction variable increments should be
34  /// scheduled as soon as possible after the variable's last use.
35  ///
36  class VISIBILITY_HIDDEN LoopDependencies {
37    const MachineLoopInfo &MLI;
38    const MachineDominatorTree &MDT;
39
40  public:
41    typedef std::map<unsigned, std::pair<const MachineOperand *, unsigned> >
42      LoopDeps;
43    LoopDeps Deps;
44
45    LoopDependencies(const MachineLoopInfo &mli,
46                     const MachineDominatorTree &mdt) :
47      MLI(mli), MDT(mdt) {}
48
49    /// VisitLoop - Clear out any previous state and analyze the given loop.
50    ///
51    void VisitLoop(const MachineLoop *Loop) {
52      Deps.clear();
53      MachineBasicBlock *Header = Loop->getHeader();
54      SmallSet<unsigned, 8> LoopLiveIns;
55      for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(),
56           LE = Header->livein_end(); LI != LE; ++LI)
57        LoopLiveIns.insert(*LI);
58
59      const MachineDomTreeNode *Node = MDT.getNode(Header);
60      const MachineBasicBlock *MBB = Node->getBlock();
61      assert(Loop->contains(MBB) &&
62             "Loop does not contain header!");
63      VisitRegion(Node, MBB, Loop, LoopLiveIns);
64    }
65
66  private:
67    void VisitRegion(const MachineDomTreeNode *Node,
68                     const MachineBasicBlock *MBB,
69                     const MachineLoop *Loop,
70                     const SmallSet<unsigned, 8> &LoopLiveIns) {
71      unsigned Count = 0;
72      for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
73           I != E; ++I, ++Count) {
74        const MachineInstr *MI = I;
75        for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
76          const MachineOperand &MO = MI->getOperand(i);
77          if (!MO.isReg() || !MO.isUse())
78            continue;
79          unsigned MOReg = MO.getReg();
80          if (LoopLiveIns.count(MOReg))
81            Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count)));
82        }
83      }
84
85      const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
86      for (std::vector<MachineDomTreeNode*>::const_iterator I =
87           Children.begin(), E = Children.end(); I != E; ++I) {
88        const MachineDomTreeNode *ChildNode = *I;
89        MachineBasicBlock *ChildBlock = ChildNode->getBlock();
90        if (Loop->contains(ChildBlock))
91          VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns);
92      }
93    }
94  };
95
96  /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of
97  /// MachineInstrs.
98  class VISIBILITY_HIDDEN ScheduleDAGInstrs : public ScheduleDAG {
99    const MachineLoopInfo &MLI;
100    const MachineDominatorTree &MDT;
101    const MachineFrameInfo *MFI;
102
103    /// Defs, Uses - Remember where defs and uses of each physical register
104    /// are as we iterate upward through the instructions. This is allocated
105    /// here instead of inside BuildSchedGraph to avoid the need for it to be
106    /// initialized and destructed for each block.
107    std::vector<SUnit *> Defs[TargetRegisterInfo::FirstVirtualRegister];
108    std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister];
109
110    /// DbgValueVec - Remember DBG_VALUEs that refer to a particular
111    /// register.
112    std::vector<MachineInstr *>DbgValueVec;
113
114    /// PendingLoads - Remember where unknown loads are after the most recent
115    /// unknown store, as we iterate. As with Defs and Uses, this is here
116    /// to minimize construction/destruction.
117    std::vector<SUnit *> PendingLoads;
118
119    /// LoopRegs - Track which registers are used for loop-carried dependencies.
120    ///
121    LoopDependencies LoopRegs;
122
123    /// LoopLiveInRegs - Track which regs are live into a loop, to help guide
124    /// back-edge-aware scheduling.
125    ///
126    SmallSet<unsigned, 8> LoopLiveInRegs;
127
128  public:
129    MachineBasicBlock::iterator Begin;    // The beginning of the range to
130                                          // be scheduled. The range extends
131                                          // to InsertPos.
132    unsigned InsertPosIndex;              // The index in BB of InsertPos.
133
134    explicit ScheduleDAGInstrs(MachineFunction &mf,
135                               const MachineLoopInfo &mli,
136                               const MachineDominatorTree &mdt);
137
138    virtual ~ScheduleDAGInstrs() {}
139
140    /// NewSUnit - Creates a new SUnit and return a ptr to it.
141    ///
142    SUnit *NewSUnit(MachineInstr *MI) {
143#ifndef NDEBUG
144      const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0];
145#endif
146      SUnits.push_back(SUnit(MI, (unsigned)SUnits.size()));
147      assert((Addr == 0 || Addr == &SUnits[0]) &&
148             "SUnits std::vector reallocated on the fly!");
149      SUnits.back().OrigNode = &SUnits.back();
150      return &SUnits.back();
151    }
152
153    /// Run - perform scheduling.
154    ///
155    void Run(MachineBasicBlock *bb,
156             MachineBasicBlock::iterator begin,
157             MachineBasicBlock::iterator end,
158             unsigned endindex);
159
160    /// BuildSchedGraph - Build SUnits from the MachineBasicBlock that we are
161    /// input.
162    virtual void BuildSchedGraph(AliasAnalysis *AA);
163
164    /// ComputeLatency - Compute node latency.
165    ///
166    virtual void ComputeLatency(SUnit *SU);
167
168    /// ComputeOperandLatency - Override dependence edge latency using
169    /// operand use/def information
170    ///
171    virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use,
172                                       SDep& dep) const;
173
174    virtual MachineBasicBlock*
175    EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*>*);
176
177    /// StartBlock - Prepare to perform scheduling in the given block.
178    ///
179    virtual void StartBlock(MachineBasicBlock *BB);
180
181    /// Schedule - Order nodes according to selected style, filling
182    /// in the Sequence member.
183    ///
184    virtual void Schedule() = 0;
185
186    /// FinishBlock - Clean up after scheduling in the given block.
187    ///
188    virtual void FinishBlock();
189
190    virtual void dumpNode(const SUnit *SU) const;
191
192    virtual std::string getGraphNodeLabel(const SUnit *SU) const;
193  };
194}
195
196#endif
197