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