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