LiveIntervalAnalysis.h revision 826cbac2a0cef418fd8949813761c2ed975f3df1 
1//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- 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 LiveInterval analysis pass.  Given some numbering of
11// each the machine instructions (in this implemention depth-first order) an
12// interval [i, j) is said to be a live interval for register v if there is no
13// instruction with number j' > j such that v is live at j' and there is no
14// instruction with number i' < i such that v is live at i'. In this
15// implementation intervals can have holes, i.e. an interval might look like
16// [1,20), [50,65), [1000,1001).
17//
18//===----------------------------------------------------------------------===//
19
20#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
21#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
22
23#include "llvm/CodeGen/MachineBasicBlock.h"
24#include "llvm/CodeGen/MachineFunctionPass.h"
25#include "llvm/CodeGen/LiveInterval.h"
26#include "llvm/CodeGen/SlotIndexes.h"
27#include "llvm/ADT/BitVector.h"
28#include "llvm/ADT/DenseMap.h"
29#include "llvm/ADT/SmallPtrSet.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/Support/Allocator.h"
32#include <cmath>
33#include <iterator>
34
35namespace llvm {
36
37  class AliasAnalysis;
38  class LiveVariables;
39  class MachineLoopInfo;
40  class TargetRegisterInfo;
41  class MachineRegisterInfo;
42  class TargetInstrInfo;
43  class TargetRegisterClass;
44  class VirtRegMap;
45
46  class LiveIntervals : public MachineFunctionPass {
47    MachineFunction* mf_;
48    MachineRegisterInfo* mri_;
49    const TargetMachine* tm_;
50    const TargetRegisterInfo* tri_;
51    const TargetInstrInfo* tii_;
52    AliasAnalysis *aa_;
53    LiveVariables* lv_;
54    SlotIndexes* indexes_;
55
56    /// Special pool allocator for VNInfo's (LiveInterval val#).
57    ///
58    BumpPtrAllocator VNInfoAllocator;
59
60    typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
61    Reg2IntervalMap r2iMap_;
62
63    /// allocatableRegs_ - A bit vector of allocatable registers.
64    BitVector allocatableRegs_;
65
66    /// CloneMIs - A list of clones as result of re-materialization.
67    std::vector<MachineInstr*> CloneMIs;
68
69  public:
70    static char ID; // Pass identification, replacement for typeid
71    LiveIntervals() : MachineFunctionPass(&ID) {}
72
73    // Calculate the spill weight to assign to a single instruction.
74    static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth);
75
76    // After summing the spill weights of all defs and uses, the final weight
77    // should be normalized, dividing the weight of the interval by its size.
78    // This encourages spilling of intervals that are large and have few uses,
79    // and discourages spilling of small intervals with many uses.
80    void normalizeSpillWeight(LiveInterval &li) {
81      li.weight /= getApproximateInstructionCount(li) + 25;
82    }
83
84    typedef Reg2IntervalMap::iterator iterator;
85    typedef Reg2IntervalMap::const_iterator const_iterator;
86    const_iterator begin() const { return r2iMap_.begin(); }
87    const_iterator end() const { return r2iMap_.end(); }
88    iterator begin() { return r2iMap_.begin(); }
89    iterator end() { return r2iMap_.end(); }
90    unsigned getNumIntervals() const { return (unsigned)r2iMap_.size(); }
91
92    LiveInterval &getInterval(unsigned reg) {
93      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
94      assert(I != r2iMap_.end() && "Interval does not exist for register");
95      return *I->second;
96    }
97
98    const LiveInterval &getInterval(unsigned reg) const {
99      Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
100      assert(I != r2iMap_.end() && "Interval does not exist for register");
101      return *I->second;
102    }
103
104    bool hasInterval(unsigned reg) const {
105      return r2iMap_.count(reg);
106    }
107
108    /// getScaledIntervalSize - get the size of an interval in "units,"
109    /// where every function is composed of one thousand units.  This
110    /// measure scales properly with empty index slots in the function.
111    double getScaledIntervalSize(LiveInterval& I) {
112      return (1000.0 * I.getSize()) / indexes_->getIndexesLength();
113    }
114
115    /// getApproximateInstructionCount - computes an estimate of the number
116    /// of instructions in a given LiveInterval.
117    unsigned getApproximateInstructionCount(LiveInterval& I) {
118      double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
119      return (unsigned)(IntervalPercentage * indexes_->getFunctionSize());
120    }
121
122    /// conflictsWithPhysReg - Returns true if the specified register is used or
123    /// defined during the duration of the specified interval. Copies to and
124    /// from li.reg are allowed. This method is only able to analyze simple
125    /// ranges that stay within a single basic block. Anything else is
126    /// considered a conflict.
127    bool conflictsWithPhysReg(const LiveInterval &li, VirtRegMap &vrm,
128                              unsigned reg);
129
130    /// conflictsWithSubPhysRegRef - Similar to conflictsWithPhysRegRef except
131    /// it checks for sub-register reference and it can check use as well.
132    bool conflictsWithSubPhysRegRef(LiveInterval &li, unsigned Reg,
133                                    bool CheckUse,
134                                   SmallPtrSet<MachineInstr*,32> &JoinedCopies);
135
136    // Interval creation
137    LiveInterval &getOrCreateInterval(unsigned reg) {
138      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
139      if (I == r2iMap_.end())
140        I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first;
141      return *I->second;
142    }
143
144    /// dupInterval - Duplicate a live interval. The caller is responsible for
145    /// managing the allocated memory.
146    LiveInterval *dupInterval(LiveInterval *li);
147
148    /// addLiveRangeToEndOfBlock - Given a register and an instruction,
149    /// adds a live range from that instruction to the end of its MBB.
150    LiveRange addLiveRangeToEndOfBlock(unsigned reg,
151                                       MachineInstr* startInst);
152
153    // Interval removal
154
155    void removeInterval(unsigned Reg) {
156      DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg);
157      delete I->second;
158      r2iMap_.erase(I);
159    }
160
161    SlotIndex getZeroIndex() const {
162      return indexes_->getZeroIndex();
163    }
164
165    SlotIndex getInvalidIndex() const {
166      return indexes_->getInvalidIndex();
167    }
168
169    /// isNotInMIMap - returns true if the specified machine instr has been
170    /// removed or was never entered in the map.
171    bool isNotInMIMap(const MachineInstr* Instr) const {
172      return !indexes_->hasIndex(Instr);
173    }
174
175    /// Returns the base index of the given instruction.
176    SlotIndex getInstructionIndex(const MachineInstr *instr) const {
177      return indexes_->getInstructionIndex(instr);
178    }
179
180    /// Returns the instruction associated with the given index.
181    MachineInstr* getInstructionFromIndex(SlotIndex index) const {
182      return indexes_->getInstructionFromIndex(index);
183    }
184
185    /// Return the first index in the given basic block.
186    SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const {
187      return indexes_->getMBBStartIdx(mbb);
188    }
189
190    /// Return the last index in the given basic block.
191    SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const {
192      return indexes_->getMBBEndIdx(mbb);
193    }
194
195    MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
196      return indexes_->getMBBFromIndex(index);
197    }
198
199    SlotIndex getMBBTerminatorGap(const MachineBasicBlock *mbb) {
200      return indexes_->getTerminatorGap(mbb);
201    }
202
203    SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) {
204      return indexes_->insertMachineInstrInMaps(MI);
205    }
206
207    void RemoveMachineInstrFromMaps(MachineInstr *MI) {
208      indexes_->removeMachineInstrFromMaps(MI);
209    }
210
211    void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) {
212      indexes_->replaceMachineInstrInMaps(MI, NewMI);
213    }
214
215    bool findLiveInMBBs(SlotIndex Start, SlotIndex End,
216                        SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
217      return indexes_->findLiveInMBBs(Start, End, MBBs);
218    }
219
220    void renumber() {
221      indexes_->renumberIndexes();
222    }
223
224    BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; }
225
226    /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
227    /// copy field and returns the source register that defines it.
228    unsigned getVNInfoSourceReg(const VNInfo *VNI) const;
229
230    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
231    virtual void releaseMemory();
232
233    /// runOnMachineFunction - pass entry point
234    virtual bool runOnMachineFunction(MachineFunction&);
235
236    /// print - Implement the dump method.
237    virtual void print(raw_ostream &O, const Module* = 0) const;
238
239    /// addIntervalsForSpills - Create new intervals for spilled defs / uses of
240    /// the given interval. FIXME: It also returns the weight of the spill slot
241    /// (if any is created) by reference. This is temporary.
242    std::vector<LiveInterval*>
243    addIntervalsForSpills(const LiveInterval& i,
244                          SmallVectorImpl<LiveInterval*> &SpillIs,
245                          const MachineLoopInfo *loopInfo, VirtRegMap& vrm);
246
247    /// addIntervalsForSpillsFast - Quickly create new intervals for spilled
248    /// defs / uses without remat or splitting.
249    std::vector<LiveInterval*>
250    addIntervalsForSpillsFast(const LiveInterval &li,
251                              const MachineLoopInfo *loopInfo, VirtRegMap &vrm);
252
253    /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
254    /// around all defs and uses of the specified interval. Return true if it
255    /// was able to cut its interval.
256    bool spillPhysRegAroundRegDefsUses(const LiveInterval &li,
257                                       unsigned PhysReg, VirtRegMap &vrm);
258
259    /// isReMaterializable - Returns true if every definition of MI of every
260    /// val# of the specified interval is re-materializable. Also returns true
261    /// by reference if all of the defs are load instructions.
262    bool isReMaterializable(const LiveInterval &li,
263                            SmallVectorImpl<LiveInterval*> &SpillIs,
264                            bool &isLoad);
265
266    /// isReMaterializable - Returns true if the definition MI of the specified
267    /// val# of the specified interval is re-materializable.
268    bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
269                            MachineInstr *MI);
270
271    /// getRepresentativeReg - Find the largest super register of the specified
272    /// physical register.
273    unsigned getRepresentativeReg(unsigned Reg) const;
274
275    /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
276    /// specified interval that conflicts with the specified physical register.
277    unsigned getNumConflictsWithPhysReg(const LiveInterval &li,
278                                        unsigned PhysReg) const;
279
280    /// processImplicitDefs - Process IMPLICIT_DEF instructions. Add isUndef
281    /// marker to implicit_def defs and their uses.
282    void processImplicitDefs();
283
284    /// intervalIsInOneMBB - Returns true if the specified interval is entirely
285    /// within a single basic block.
286    bool intervalIsInOneMBB(const LiveInterval &li) const;
287
288  private:
289    /// computeIntervals - Compute live intervals.
290    void computeIntervals();
291
292    /// handleRegisterDef - update intervals for a register def
293    /// (calls handlePhysicalRegisterDef and
294    /// handleVirtualRegisterDef)
295    void handleRegisterDef(MachineBasicBlock *MBB,
296                           MachineBasicBlock::iterator MI,
297                           SlotIndex MIIdx,
298                           MachineOperand& MO, unsigned MOIdx);
299
300    /// handleVirtualRegisterDef - update intervals for a virtual
301    /// register def
302    void handleVirtualRegisterDef(MachineBasicBlock *MBB,
303                                  MachineBasicBlock::iterator MI,
304                                  SlotIndex MIIdx, MachineOperand& MO,
305                                  unsigned MOIdx,
306                                  LiveInterval& interval);
307
308    /// handlePhysicalRegisterDef - update intervals for a physical register
309    /// def.
310    void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
311                                   MachineBasicBlock::iterator mi,
312                                   SlotIndex MIIdx, MachineOperand& MO,
313                                   LiveInterval &interval,
314                                   MachineInstr *CopyMI);
315
316    /// handleLiveInRegister - Create interval for a livein register.
317    void handleLiveInRegister(MachineBasicBlock* mbb,
318                              SlotIndex MIIdx,
319                              LiveInterval &interval, bool isAlias = false);
320
321    /// getReMatImplicitUse - If the remat definition MI has one (for now, we
322    /// only allow one) virtual register operand, then its uses are implicitly
323    /// using the register. Returns the virtual register.
324    unsigned getReMatImplicitUse(const LiveInterval &li,
325                                 MachineInstr *MI) const;
326
327    /// isValNoAvailableAt - Return true if the val# of the specified interval
328    /// which reaches the given instruction also reaches the specified use
329    /// index.
330    bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
331                            SlotIndex UseIdx) const;
332
333    /// isReMaterializable - Returns true if the definition MI of the specified
334    /// val# of the specified interval is re-materializable. Also returns true
335    /// by reference if the def is a load.
336    bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo,
337                            MachineInstr *MI,
338                            SmallVectorImpl<LiveInterval*> &SpillIs,
339                            bool &isLoad);
340
341    /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
342    /// slot / to reg or any rematerialized load into ith operand of specified
343    /// MI. If it is successul, MI is updated with the newly created MI and
344    /// returns true.
345    bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
346                              MachineInstr *DefMI, SlotIndex InstrIdx,
347                              SmallVector<unsigned, 2> &Ops,
348                              bool isSS, int FrameIndex, unsigned Reg);
349
350    /// canFoldMemoryOperand - Return true if the specified load / store
351    /// folding is possible.
352    bool canFoldMemoryOperand(MachineInstr *MI,
353                              SmallVector<unsigned, 2> &Ops,
354                              bool ReMatLoadSS) const;
355
356    /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified
357    /// VNInfo that's after the specified index but is within the basic block.
358    bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI,
359                              MachineBasicBlock *MBB,
360                              SlotIndex Idx) const;
361
362    /// hasAllocatableSuperReg - Return true if the specified physical register
363    /// has any super register that's allocatable.
364    bool hasAllocatableSuperReg(unsigned Reg) const;
365
366    /// SRInfo - Spill / restore info.
367    struct SRInfo {
368      SlotIndex index;
369      unsigned vreg;
370      bool canFold;
371      SRInfo(SlotIndex i, unsigned vr, bool f)
372        : index(i), vreg(vr), canFold(f) {}
373    };
374
375    bool alsoFoldARestore(int Id, SlotIndex index, unsigned vr,
376                          BitVector &RestoreMBBs,
377                          DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
378    void eraseRestoreInfo(int Id, SlotIndex index, unsigned vr,
379                          BitVector &RestoreMBBs,
380                          DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes);
381
382    /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
383    /// spilled and create empty intervals for their uses.
384    void handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
385                              const TargetRegisterClass* rc,
386                              std::vector<LiveInterval*> &NewLIs);
387
388    /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
389    /// interval on to-be re-materialized operands of MI) with new register.
390    void rewriteImplicitOps(const LiveInterval &li,
391                           MachineInstr *MI, unsigned NewVReg, VirtRegMap &vrm);
392
393    /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper
394    /// functions for addIntervalsForSpills to rewrite uses / defs for the given
395    /// live range.
396    bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
397        bool TrySplit, SlotIndex index, SlotIndex end,
398        MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI,
399        unsigned Slot, int LdSlot,
400        bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
401        VirtRegMap &vrm, const TargetRegisterClass* rc,
402        SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
403        unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
404        DenseMap<unsigned,unsigned> &MBBVRegsMap,
405        std::vector<LiveInterval*> &NewLIs);
406    void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
407        LiveInterval::Ranges::const_iterator &I,
408        MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot,
409        bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
410        VirtRegMap &vrm, const TargetRegisterClass* rc,
411        SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo,
412        BitVector &SpillMBBs,
413        DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes,
414        BitVector &RestoreMBBs,
415        DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes,
416        DenseMap<unsigned,unsigned> &MBBVRegsMap,
417        std::vector<LiveInterval*> &NewLIs);
418
419    // Normalize the spill weight of all the intervals in NewLIs.
420    void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs);
421
422    static LiveInterval* createInterval(unsigned Reg);
423
424    void printInstrs(raw_ostream &O) const;
425    void dumpInstrs() const;
426  };
427} // End llvm namespace
428
429#endif
430