1 //===- LiveIntervalCalc.cpp - Calculate live interval --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Implementation of the LiveIntervalCalc class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/CodeGen/LiveIntervalCalc.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/SetVector.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/CodeGen/LiveInterval.h"
18 #include "llvm/CodeGen/MachineBasicBlock.h"
19 #include "llvm/CodeGen/MachineDominators.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/CodeGen/MachineOperand.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/CodeGen/SlotIndexes.h"
25 #include "llvm/CodeGen/TargetRegisterInfo.h"
26 #include "llvm/MC/LaneBitmask.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include <algorithm>
30 #include <cassert>
31 #include <iterator>
32 #include <tuple>
33 #include <utility>
34
35 using namespace llvm;
36
37 #define DEBUG_TYPE "regalloc"
38
39 // Reserve an address that indicates a value that is known to be "undef".
40 static VNInfo UndefVNI(0xbad, SlotIndex());
41
createDeadDef(SlotIndexes & Indexes,VNInfo::Allocator & Alloc,LiveRange & LR,const MachineOperand & MO)42 static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
43 LiveRange &LR, const MachineOperand &MO) {
44 const MachineInstr &MI = *MO.getParent();
45 SlotIndex DefIdx =
46 Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
47
48 // Create the def in LR. This may find an existing def.
49 LR.createDeadDef(DefIdx, Alloc);
50 }
51
calculate(LiveInterval & LI,bool TrackSubRegs)52 void LiveIntervalCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
53 const MachineRegisterInfo *MRI = getRegInfo();
54 SlotIndexes *Indexes = getIndexes();
55 VNInfo::Allocator *Alloc = getVNAlloc();
56
57 assert(MRI && Indexes && "call reset() first");
58
59 // Step 1: Create minimal live segments for every definition of Reg.
60 // Visit all def operands. If the same instruction has multiple defs of Reg,
61 // createDeadDef() will deduplicate.
62 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
63 unsigned Reg = LI.reg();
64 for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
65 if (!MO.isDef() && !MO.readsReg())
66 continue;
67
68 unsigned SubReg = MO.getSubReg();
69 if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
70 LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
71 : MRI->getMaxLaneMaskForVReg(Reg);
72 // If this is the first time we see a subregister def, initialize
73 // subranges by creating a copy of the main range.
74 if (!LI.hasSubRanges() && !LI.empty()) {
75 LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
76 LI.createSubRangeFrom(*Alloc, ClassMask, LI);
77 }
78
79 LI.refineSubRanges(
80 *Alloc, SubMask,
81 [&MO, Indexes, Alloc](LiveInterval::SubRange &SR) {
82 if (MO.isDef())
83 createDeadDef(*Indexes, *Alloc, SR, MO);
84 },
85 *Indexes, TRI);
86 }
87
88 // Create the def in the main liverange. We do not have to do this if
89 // subranges are tracked as we recreate the main range later in this case.
90 if (MO.isDef() && !LI.hasSubRanges())
91 createDeadDef(*Indexes, *Alloc, LI, MO);
92 }
93
94 // We may have created empty live ranges for partially undefined uses, we
95 // can't keep them because we won't find defs in them later.
96 LI.removeEmptySubRanges();
97
98 const MachineFunction *MF = getMachineFunction();
99 MachineDominatorTree *DomTree = getDomTree();
100 // Step 2: Extend live segments to all uses, constructing SSA form as
101 // necessary.
102 if (LI.hasSubRanges()) {
103 for (LiveInterval::SubRange &S : LI.subranges()) {
104 LiveIntervalCalc SubLIC;
105 SubLIC.reset(MF, Indexes, DomTree, Alloc);
106 SubLIC.extendToUses(S, Reg, S.LaneMask, &LI);
107 }
108 LI.clear();
109 constructMainRangeFromSubranges(LI);
110 } else {
111 resetLiveOutMap();
112 extendToUses(LI, Reg, LaneBitmask::getAll());
113 }
114 }
115
constructMainRangeFromSubranges(LiveInterval & LI)116 void LiveIntervalCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
117 // First create dead defs at all defs found in subranges.
118 LiveRange &MainRange = LI;
119 assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
120 "Expect empty main liverange");
121
122 VNInfo::Allocator *Alloc = getVNAlloc();
123 for (const LiveInterval::SubRange &SR : LI.subranges()) {
124 for (const VNInfo *VNI : SR.valnos) {
125 if (!VNI->isUnused() && !VNI->isPHIDef())
126 MainRange.createDeadDef(VNI->def, *Alloc);
127 }
128 }
129 resetLiveOutMap();
130 extendToUses(MainRange, LI.reg(), LaneBitmask::getAll(), &LI);
131 }
132
createDeadDefs(LiveRange & LR,Register Reg)133 void LiveIntervalCalc::createDeadDefs(LiveRange &LR, Register Reg) {
134 const MachineRegisterInfo *MRI = getRegInfo();
135 SlotIndexes *Indexes = getIndexes();
136 VNInfo::Allocator *Alloc = getVNAlloc();
137 assert(MRI && Indexes && "call reset() first");
138
139 // Visit all def operands. If the same instruction has multiple defs of Reg,
140 // LR.createDeadDef() will deduplicate.
141 for (MachineOperand &MO : MRI->def_operands(Reg))
142 createDeadDef(*Indexes, *Alloc, LR, MO);
143 }
144
extendToUses(LiveRange & LR,Register Reg,LaneBitmask Mask,LiveInterval * LI)145 void LiveIntervalCalc::extendToUses(LiveRange &LR, Register Reg,
146 LaneBitmask Mask, LiveInterval *LI) {
147 const MachineRegisterInfo *MRI = getRegInfo();
148 SlotIndexes *Indexes = getIndexes();
149 SmallVector<SlotIndex, 4> Undefs;
150 if (LI != nullptr)
151 LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
152
153 // Visit all operands that read Reg. This may include partial defs.
154 bool IsSubRange = !Mask.all();
155 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
156 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
157 // Clear all kill flags. They will be reinserted after register allocation
158 // by LiveIntervals::addKillFlags().
159 if (MO.isUse())
160 MO.setIsKill(false);
161 // MO::readsReg returns "true" for subregister defs. This is for keeping
162 // liveness of the entire register (i.e. for the main range of the live
163 // interval). For subranges, definitions of non-overlapping subregisters
164 // do not count as uses.
165 if (!MO.readsReg() || (IsSubRange && MO.isDef()))
166 continue;
167
168 unsigned SubReg = MO.getSubReg();
169 if (SubReg != 0) {
170 LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
171 if (MO.isDef())
172 SLM = ~SLM;
173 // Ignore uses not reading the current (sub)range.
174 if ((SLM & Mask).none())
175 continue;
176 }
177
178 // Determine the actual place of the use.
179 const MachineInstr *MI = MO.getParent();
180 unsigned OpNo = (&MO - &MI->getOperand(0));
181 SlotIndex UseIdx;
182 if (MI->isPHI()) {
183 assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
184 // The actual place where a phi operand is used is the end of the pred
185 // MBB. PHI operands are paired: (Reg, PredMBB).
186 UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo + 1).getMBB());
187 } else {
188 // Check for early-clobber redefs.
189 bool isEarlyClobber = false;
190 unsigned DefIdx;
191 if (MO.isDef())
192 isEarlyClobber = MO.isEarlyClobber();
193 else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
194 // FIXME: This would be a lot easier if tied early-clobber uses also
195 // had an early-clobber flag.
196 isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
197 }
198 UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
199 }
200
201 // MI is reading Reg. We may have visited MI before if it happens to be
202 // reading Reg multiple times. That is OK, extend() is idempotent.
203 extend(LR, UseIdx, Reg, Undefs);
204 }
205 }
206