1//===---- LiveRangeEdit.h - Basic tools for split and spill -----*- 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// The LiveRangeEdit class represents changes done to a virtual register when it
11// is spilled or split.
12//
13// The parent register is never changed. Instead, a number of new virtual
14// registers are created and added to the newRegs vector.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_CODEGEN_LIVERANGEEDIT_H
19#define LLVM_CODEGEN_LIVERANGEEDIT_H
20
21#include "llvm/ADT/ArrayRef.h"
22#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/SmallPtrSet.h"
24#include "llvm/CodeGen/LiveInterval.h"
25#include "llvm/Target/TargetMachine.h"
26
27namespace llvm {
28
29class AliasAnalysis;
30class LiveIntervals;
31class MachineBlockFrequencyInfo;
32class MachineLoopInfo;
33class MachineRegisterInfo;
34class VirtRegMap;
35
36class LiveRangeEdit {
37public:
38  /// Callback methods for LiveRangeEdit owners.
39  class Delegate {
40    virtual void anchor();
41  public:
42    /// Called immediately before erasing a dead machine instruction.
43    virtual void LRE_WillEraseInstruction(MachineInstr *MI) {}
44
45    /// Called when a virtual register is no longer used. Return false to defer
46    /// its deletion from LiveIntervals.
47    virtual bool LRE_CanEraseVirtReg(unsigned) { return true; }
48
49    /// Called before shrinking the live range of a virtual register.
50    virtual void LRE_WillShrinkVirtReg(unsigned) {}
51
52    /// Called after cloning a virtual register.
53    /// This is used for new registers representing connected components of Old.
54    virtual void LRE_DidCloneVirtReg(unsigned New, unsigned Old) {}
55
56    virtual ~Delegate() {}
57  };
58
59private:
60  LiveInterval *Parent;
61  SmallVectorImpl<LiveInterval*> &NewRegs;
62  MachineRegisterInfo &MRI;
63  LiveIntervals &LIS;
64  VirtRegMap *VRM;
65  const TargetInstrInfo &TII;
66  Delegate *const TheDelegate;
67
68  /// FirstNew - Index of the first register added to NewRegs.
69  const unsigned FirstNew;
70
71  /// ScannedRemattable - true when remattable values have been identified.
72  bool ScannedRemattable;
73
74  /// Remattable - Values defined by remattable instructions as identified by
75  /// tii.isTriviallyReMaterializable().
76  SmallPtrSet<const VNInfo*,4> Remattable;
77
78  /// Rematted - Values that were actually rematted, and so need to have their
79  /// live range trimmed or entirely removed.
80  SmallPtrSet<const VNInfo*,4> Rematted;
81
82  /// scanRemattable - Identify the Parent values that may rematerialize.
83  void scanRemattable(AliasAnalysis *aa);
84
85  /// allUsesAvailableAt - Return true if all registers used by OrigMI at
86  /// OrigIdx are also available with the same value at UseIdx.
87  bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx,
88                          SlotIndex UseIdx) const;
89
90  /// foldAsLoad - If LI has a single use and a single def that can be folded as
91  /// a load, eliminate the register by folding the def into the use.
92  bool foldAsLoad(LiveInterval *LI, SmallVectorImpl<MachineInstr*> &Dead);
93
94  typedef SetVector<LiveInterval*,
95                    SmallVector<LiveInterval*, 8>,
96                    SmallPtrSet<LiveInterval*, 8> > ToShrinkSet;
97  /// Helper for eliminateDeadDefs.
98  void eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink);
99
100public:
101  /// Create a LiveRangeEdit for breaking down parent into smaller pieces.
102  /// @param parent The register being spilled or split.
103  /// @param newRegs List to receive any new registers created. This needn't be
104  ///                empty initially, any existing registers are ignored.
105  /// @param MF The MachineFunction the live range edit is taking place in.
106  /// @param lis The collection of all live intervals in this function.
107  /// @param vrm Map of virtual registers to physical registers for this
108  ///            function.  If NULL, no virtual register map updates will
109  ///            be done.  This could be the case if called before Regalloc.
110  LiveRangeEdit(LiveInterval *parent,
111                SmallVectorImpl<LiveInterval*> &newRegs,
112                MachineFunction &MF,
113                LiveIntervals &lis,
114                VirtRegMap *vrm,
115                Delegate *delegate = 0)
116    : Parent(parent), NewRegs(newRegs),
117      MRI(MF.getRegInfo()), LIS(lis), VRM(vrm),
118      TII(*MF.getTarget().getInstrInfo()),
119      TheDelegate(delegate),
120      FirstNew(newRegs.size()),
121      ScannedRemattable(false) {}
122
123  LiveInterval &getParent() const {
124   assert(Parent && "No parent LiveInterval");
125   return *Parent;
126  }
127  unsigned getReg() const { return getParent().reg; }
128
129  /// Iterator for accessing the new registers added by this edit.
130  typedef SmallVectorImpl<LiveInterval*>::const_iterator iterator;
131  iterator begin() const { return NewRegs.begin()+FirstNew; }
132  iterator end() const { return NewRegs.end(); }
133  unsigned size() const { return NewRegs.size()-FirstNew; }
134  bool empty() const { return size() == 0; }
135  LiveInterval *get(unsigned idx) const { return NewRegs[idx+FirstNew]; }
136
137  ArrayRef<LiveInterval*> regs() const {
138    return makeArrayRef(NewRegs).slice(FirstNew);
139  }
140
141  /// createFrom - Create a new virtual register based on OldReg.
142  LiveInterval &createFrom(unsigned OldReg);
143
144  /// create - Create a new register with the same class and original slot as
145  /// parent.
146  LiveInterval &create() {
147    return createFrom(getReg());
148  }
149
150  /// anyRematerializable - Return true if any parent values may be
151  /// rematerializable.
152  /// This function must be called before any rematerialization is attempted.
153  bool anyRematerializable(AliasAnalysis*);
154
155  /// checkRematerializable - Manually add VNI to the list of rematerializable
156  /// values if DefMI may be rematerializable.
157  bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI,
158                             AliasAnalysis*);
159
160  /// Remat - Information needed to rematerialize at a specific location.
161  struct Remat {
162    VNInfo *ParentVNI;      // parent_'s value at the remat location.
163    MachineInstr *OrigMI;   // Instruction defining ParentVNI.
164    explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI), OrigMI(0) {}
165  };
166
167  /// canRematerializeAt - Determine if ParentVNI can be rematerialized at
168  /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI.
169  /// When cheapAsAMove is set, only cheap remats are allowed.
170  bool canRematerializeAt(Remat &RM,
171                          SlotIndex UseIdx,
172                          bool cheapAsAMove);
173
174  /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an
175  /// instruction into MBB before MI. The new instruction is mapped, but
176  /// liveness is not updated.
177  /// Return the SlotIndex of the new instruction.
178  SlotIndex rematerializeAt(MachineBasicBlock &MBB,
179                            MachineBasicBlock::iterator MI,
180                            unsigned DestReg,
181                            const Remat &RM,
182                            const TargetRegisterInfo&,
183                            bool Late = false);
184
185  /// markRematerialized - explicitly mark a value as rematerialized after doing
186  /// it manually.
187  void markRematerialized(const VNInfo *ParentVNI) {
188    Rematted.insert(ParentVNI);
189  }
190
191  /// didRematerialize - Return true if ParentVNI was rematerialized anywhere.
192  bool didRematerialize(const VNInfo *ParentVNI) const {
193    return Rematted.count(ParentVNI);
194  }
195
196  /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try
197  /// to erase it from LIS.
198  void eraseVirtReg(unsigned Reg);
199
200  /// eliminateDeadDefs - Try to delete machine instructions that are now dead
201  /// (allDefsAreDead returns true). This may cause live intervals to be trimmed
202  /// and further dead efs to be eliminated.
203  /// RegsBeingSpilled lists registers currently being spilled by the register
204  /// allocator.  These registers should not be split into new intervals
205  /// as currently those new intervals are not guaranteed to spill.
206  void eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
207                         ArrayRef<unsigned> RegsBeingSpilled = None);
208
209  /// calculateRegClassAndHint - Recompute register class and hint for each new
210  /// register.
211  void calculateRegClassAndHint(MachineFunction&,
212                                const MachineLoopInfo&,
213                                const MachineBlockFrequencyInfo&);
214};
215
216}
217
218#endif
219