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/CodeGen/MachineRegisterInfo.h"
26#include "llvm/Target/TargetMachine.h"
27
28namespace llvm {
29
30class AliasAnalysis;
31class LiveIntervals;
32class MachineBlockFrequencyInfo;
33class MachineLoopInfo;
34class VirtRegMap;
35
36class LiveRangeEdit : private MachineRegisterInfo::Delegate {
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<unsigned> &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
100  /// MachineRegisterInfo callback to notify when new virtual
101  /// registers are created.
102  void MRI_NoteNewVirtualRegister(unsigned VReg) override;
103
104public:
105  /// Create a LiveRangeEdit for breaking down parent into smaller pieces.
106  /// @param parent The register being spilled or split.
107  /// @param newRegs List to receive any new registers created. This needn't be
108  ///                empty initially, any existing registers are ignored.
109  /// @param MF The MachineFunction the live range edit is taking place in.
110  /// @param lis The collection of all live intervals in this function.
111  /// @param vrm Map of virtual registers to physical registers for this
112  ///            function.  If NULL, no virtual register map updates will
113  ///            be done.  This could be the case if called before Regalloc.
114  LiveRangeEdit(LiveInterval *parent,
115                SmallVectorImpl<unsigned> &newRegs,
116                MachineFunction &MF,
117                LiveIntervals &lis,
118                VirtRegMap *vrm,
119                Delegate *delegate = nullptr)
120    : Parent(parent), NewRegs(newRegs),
121      MRI(MF.getRegInfo()), LIS(lis), VRM(vrm),
122      TII(*MF.getTarget().getInstrInfo()),
123      TheDelegate(delegate),
124      FirstNew(newRegs.size()),
125      ScannedRemattable(false) { MRI.setDelegate(this); }
126
127  ~LiveRangeEdit() { MRI.resetDelegate(this); }
128
129  LiveInterval &getParent() const {
130   assert(Parent && "No parent LiveInterval");
131   return *Parent;
132  }
133  unsigned getReg() const { return getParent().reg; }
134
135  /// Iterator for accessing the new registers added by this edit.
136  typedef SmallVectorImpl<unsigned>::const_iterator iterator;
137  iterator begin() const { return NewRegs.begin()+FirstNew; }
138  iterator end() const { return NewRegs.end(); }
139  unsigned size() const { return NewRegs.size()-FirstNew; }
140  bool empty() const { return size() == 0; }
141  unsigned get(unsigned idx) const { return NewRegs[idx+FirstNew]; }
142
143  ArrayRef<unsigned> regs() const {
144    return makeArrayRef(NewRegs).slice(FirstNew);
145  }
146
147  /// createEmptyIntervalFrom - Create a new empty interval based on OldReg.
148  LiveInterval &createEmptyIntervalFrom(unsigned OldReg);
149
150  /// createFrom - Create a new virtual register based on OldReg.
151  unsigned createFrom(unsigned OldReg);
152
153  /// create - Create a new register with the same class and original slot as
154  /// parent.
155  LiveInterval &createEmptyInterval() {
156    return createEmptyIntervalFrom(getReg());
157  }
158
159  unsigned create() {
160    return createFrom(getReg());
161  }
162
163  /// anyRematerializable - Return true if any parent values may be
164  /// rematerializable.
165  /// This function must be called before any rematerialization is attempted.
166  bool anyRematerializable(AliasAnalysis*);
167
168  /// checkRematerializable - Manually add VNI to the list of rematerializable
169  /// values if DefMI may be rematerializable.
170  bool checkRematerializable(VNInfo *VNI, const MachineInstr *DefMI,
171                             AliasAnalysis*);
172
173  /// Remat - Information needed to rematerialize at a specific location.
174  struct Remat {
175    VNInfo *ParentVNI;      // parent_'s value at the remat location.
176    MachineInstr *OrigMI;   // Instruction defining ParentVNI.
177    explicit Remat(VNInfo *ParentVNI) : ParentVNI(ParentVNI), OrigMI(nullptr) {}
178  };
179
180  /// canRematerializeAt - Determine if ParentVNI can be rematerialized at
181  /// UseIdx. It is assumed that parent_.getVNINfoAt(UseIdx) == ParentVNI.
182  /// When cheapAsAMove is set, only cheap remats are allowed.
183  bool canRematerializeAt(Remat &RM,
184                          SlotIndex UseIdx,
185                          bool cheapAsAMove);
186
187  /// rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an
188  /// instruction into MBB before MI. The new instruction is mapped, but
189  /// liveness is not updated.
190  /// Return the SlotIndex of the new instruction.
191  SlotIndex rematerializeAt(MachineBasicBlock &MBB,
192                            MachineBasicBlock::iterator MI,
193                            unsigned DestReg,
194                            const Remat &RM,
195                            const TargetRegisterInfo&,
196                            bool Late = false);
197
198  /// markRematerialized - explicitly mark a value as rematerialized after doing
199  /// it manually.
200  void markRematerialized(const VNInfo *ParentVNI) {
201    Rematted.insert(ParentVNI);
202  }
203
204  /// didRematerialize - Return true if ParentVNI was rematerialized anywhere.
205  bool didRematerialize(const VNInfo *ParentVNI) const {
206    return Rematted.count(ParentVNI);
207  }
208
209  /// eraseVirtReg - Notify the delegate that Reg is no longer in use, and try
210  /// to erase it from LIS.
211  void eraseVirtReg(unsigned Reg);
212
213  /// eliminateDeadDefs - Try to delete machine instructions that are now dead
214  /// (allDefsAreDead returns true). This may cause live intervals to be trimmed
215  /// and further dead efs to be eliminated.
216  /// RegsBeingSpilled lists registers currently being spilled by the register
217  /// allocator.  These registers should not be split into new intervals
218  /// as currently those new intervals are not guaranteed to spill.
219  void eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
220                         ArrayRef<unsigned> RegsBeingSpilled = None);
221
222  /// calculateRegClassAndHint - Recompute register class and hint for each new
223  /// register.
224  void calculateRegClassAndHint(MachineFunction&,
225                                const MachineLoopInfo&,
226                                const MachineBlockFrequencyInfo&);
227};
228
229}
230
231#endif
232