1 //===--- LiveRangeEdit.cpp - Basic tools for editing a register live range --===//
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 
14 #include "LiveRangeEdit.h"
15 #include "VirtRegMap.h"
16 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/Target/TargetInstrInfo.h"
19 
20 using namespace llvm;
21 
22 LiveInterval &LiveRangeEdit::create(MachineRegisterInfo &mri,
23                                     LiveIntervals &lis,
24                                     VirtRegMap &vrm) {
25   const TargetRegisterClass *RC = mri.getRegClass(getReg());
26   unsigned VReg = mri.createVirtualRegister(RC);
27   vrm.grow();
28   vrm.setIsSplitFromReg(VReg, vrm.getOriginal(getReg()));
29   LiveInterval &li = lis.getOrCreateInterval(VReg);
30   newRegs_.push_back(&li);
31   return li;
32 }
33 
34 void LiveRangeEdit::scanRemattable(LiveIntervals &lis,
35                                    const TargetInstrInfo &tii,
36                                    AliasAnalysis *aa) {
37   for (LiveInterval::vni_iterator I = parent_.vni_begin(),
38        E = parent_.vni_end(); I != E; ++I) {
39     VNInfo *VNI = *I;
40     if (VNI->isUnused())
41       continue;
42     MachineInstr *DefMI = lis.getInstructionFromIndex(VNI->def);
43     if (!DefMI)
44       continue;
45     if (tii.isTriviallyReMaterializable(DefMI, aa))
46       remattable_.insert(VNI);
47   }
48   scannedRemattable_ = true;
49 }
50 
51 bool LiveRangeEdit::anyRematerializable(LiveIntervals &lis,
52                                         const TargetInstrInfo &tii,
53                                         AliasAnalysis *aa) {
54   if (!scannedRemattable_)
55     scanRemattable(lis, tii, aa);
56   return !remattable_.empty();
57 }
58 
59 /// allUsesAvailableAt - Return true if all registers used by OrigMI at
60 /// OrigIdx are also available with the same value at UseIdx.
61 bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
62                                        SlotIndex OrigIdx,
63                                        SlotIndex UseIdx,
64                                        LiveIntervals &lis) {
65   OrigIdx = OrigIdx.getUseIndex();
66   UseIdx = UseIdx.getUseIndex();
67   for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
68     const MachineOperand &MO = OrigMI->getOperand(i);
69     if (!MO.isReg() || !MO.getReg() || MO.getReg() == getReg())
70       continue;
71     // Reserved registers are OK.
72     if (MO.isUndef() || !lis.hasInterval(MO.getReg()))
73       continue;
74     // We don't want to move any defs.
75     if (MO.isDef())
76       return false;
77     // We cannot depend on virtual registers in uselessRegs_.
78     for (unsigned ui = 0, ue = uselessRegs_.size(); ui != ue; ++ui)
79       if (uselessRegs_[ui]->reg == MO.getReg())
80         return false;
81 
82     LiveInterval &li = lis.getInterval(MO.getReg());
83     const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
84     if (!OVNI)
85       continue;
86     if (OVNI != li.getVNInfoAt(UseIdx))
87       return false;
88   }
89   return true;
90 }
91 
92 bool LiveRangeEdit::canRematerializeAt(Remat &RM,
93                                        SlotIndex UseIdx,
94                                        bool cheapAsAMove,
95                                        LiveIntervals &lis) {
96   assert(scannedRemattable_ && "Call anyRematerializable first");
97 
98   // Use scanRemattable info.
99   if (!remattable_.count(RM.ParentVNI))
100     return false;
101 
102   // No defining instruction.
103   RM.OrigMI = lis.getInstructionFromIndex(RM.ParentVNI->def);
104   assert(RM.OrigMI && "Defining instruction for remattable value disappeared");
105 
106   // If only cheap remats were requested, bail out early.
107   if (cheapAsAMove && !RM.OrigMI->getDesc().isAsCheapAsAMove())
108     return false;
109 
110   // Verify that all used registers are available with the same values.
111   if (!allUsesAvailableAt(RM.OrigMI, RM.ParentVNI->def, UseIdx, lis))
112     return false;
113 
114   return true;
115 }
116 
117 SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
118                                          MachineBasicBlock::iterator MI,
119                                          unsigned DestReg,
120                                          const Remat &RM,
121                                          LiveIntervals &lis,
122                                          const TargetInstrInfo &tii,
123                                          const TargetRegisterInfo &tri) {
124   assert(RM.OrigMI && "Invalid remat");
125   tii.reMaterialize(MBB, MI, DestReg, 0, RM.OrigMI, tri);
126   rematted_.insert(RM.ParentVNI);
127   return lis.InsertMachineInstrInMaps(--MI).getDefIndex();
128 }
129 
130