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