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