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 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 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 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 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 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