Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 1 | //===---- LiveRangeCalc.cpp - Calculate live ranges -----------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // Implementation of the LiveRangeCalc class. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 14 | #include "LiveRangeCalc.h" |
| 15 | #include "llvm/CodeGen/MachineDominators.h" |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 16 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 17 | |
| 18 | using namespace llvm; |
| 19 | |
Chandler Carruth | 1b9dde0 | 2014-04-22 02:02:50 +0000 | [diff] [blame] | 20 | #define DEBUG_TYPE "regalloc" |
| 21 | |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 22 | void LiveRangeCalc::resetLiveOutMap() { |
| 23 | unsigned NumBlocks = MF->getNumBlockIDs(); |
| 24 | Seen.clear(); |
| 25 | Seen.resize(NumBlocks); |
| 26 | Map.resize(NumBlocks); |
| 27 | } |
| 28 | |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 29 | void LiveRangeCalc::reset(const MachineFunction *mf, |
Jakob Stoklund Olesen | 5ef0e0b2 | 2012-06-04 18:21:16 +0000 | [diff] [blame] | 30 | SlotIndexes *SI, |
| 31 | MachineDominatorTree *MDT, |
| 32 | VNInfo::Allocator *VNIA) { |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 33 | MF = mf; |
Jakob Stoklund Olesen | 5ef0e0b2 | 2012-06-04 18:21:16 +0000 | [diff] [blame] | 34 | MRI = &MF->getRegInfo(); |
| 35 | Indexes = SI; |
| 36 | DomTree = MDT; |
| 37 | Alloc = VNIA; |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 38 | resetLiveOutMap(); |
Matthias Braun | c3a72c2 | 2014-12-15 21:36:35 +0000 | [diff] [blame] | 39 | LiveIn.clear(); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 40 | } |
| 41 | |
| 42 | |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 43 | static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc, |
| 44 | LiveRange &LR, const MachineOperand &MO) { |
| 45 | const MachineInstr *MI = MO.getParent(); |
Matthias Braun | 876e717 | 2015-02-20 23:43:14 +0000 | [diff] [blame] | 46 | SlotIndex DefIdx = |
| 47 | Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber()); |
Matthias Braun | c3a72c2 | 2014-12-15 21:36:35 +0000 | [diff] [blame] | 48 | |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 49 | // Create the def in LR. This may find an existing def. |
| 50 | LR.createDeadDef(DefIdx, Alloc); |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 51 | } |
| 52 | |
Matthias Braun | a25e13a | 2015-03-19 00:21:58 +0000 | [diff] [blame] | 53 | void LiveRangeCalc::calculate(LiveInterval &LI, bool TrackSubRegs) { |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 54 | assert(MRI && Indexes && "call reset() first"); |
| 55 | |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 56 | // Step 1: Create minimal live segments for every definition of Reg. |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 57 | // Visit all def operands. If the same instruction has multiple defs of Reg, |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 58 | // createDeadDef() will deduplicate. |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 59 | const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); |
| 60 | unsigned Reg = LI.reg; |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 61 | for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { |
| 62 | if (!MO.isDef() && !MO.readsReg()) |
| 63 | continue; |
| 64 | |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 65 | unsigned SubReg = MO.getSubReg(); |
Matthias Braun | a25e13a | 2015-03-19 00:21:58 +0000 | [diff] [blame] | 66 | if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) { |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 67 | unsigned Mask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg) |
| 68 | : MRI->getMaxLaneMaskForVReg(Reg); |
| 69 | |
| 70 | // If this is the first time we see a subregister def, initialize |
| 71 | // subranges by creating a copy of the main range. |
| 72 | if (!LI.hasSubRanges() && !LI.empty()) { |
| 73 | unsigned ClassMask = MRI->getMaxLaneMaskForVReg(Reg); |
| 74 | LI.createSubRangeFrom(*Alloc, ClassMask, LI); |
| 75 | } |
| 76 | |
Matthias Braun | 09afa1e | 2014-12-11 00:59:06 +0000 | [diff] [blame] | 77 | for (LiveInterval::SubRange &S : LI.subranges()) { |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 78 | // A Mask for subregs common to the existing subrange and current def. |
Matthias Braun | 09afa1e | 2014-12-11 00:59:06 +0000 | [diff] [blame] | 79 | unsigned Common = S.LaneMask & Mask; |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 80 | if (Common == 0) |
| 81 | continue; |
| 82 | // A Mask for subregs covered by the subrange but not the current def. |
Matthias Braun | 09afa1e | 2014-12-11 00:59:06 +0000 | [diff] [blame] | 83 | unsigned LRest = S.LaneMask & ~Mask; |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 84 | LiveInterval::SubRange *CommonRange; |
| 85 | if (LRest != 0) { |
| 86 | // Split current subrange into Common and LRest ranges. |
Matthias Braun | 09afa1e | 2014-12-11 00:59:06 +0000 | [diff] [blame] | 87 | S.LaneMask = LRest; |
| 88 | CommonRange = LI.createSubRangeFrom(*Alloc, Common, S); |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 89 | } else { |
Matthias Braun | 09afa1e | 2014-12-11 00:59:06 +0000 | [diff] [blame] | 90 | assert(Common == S.LaneMask); |
| 91 | CommonRange = &S; |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 92 | } |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 93 | if (MO.isDef()) |
| 94 | createDeadDef(*Indexes, *Alloc, *CommonRange, MO); |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 95 | Mask &= ~Common; |
| 96 | } |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 97 | // Create a new SubRange for subregs we did not cover yet. |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 98 | if (Mask != 0) { |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 99 | LiveInterval::SubRange *NewRange = LI.createSubRange(*Alloc, Mask); |
| 100 | if (MO.isDef()) |
| 101 | createDeadDef(*Indexes, *Alloc, *NewRange, MO); |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 102 | } |
| 103 | } |
| 104 | |
Matthias Braun | dbcca0d | 2014-12-24 02:11:51 +0000 | [diff] [blame] | 105 | // Create the def in the main liverange. We do not have to do this if |
| 106 | // subranges are tracked as we recreate the main range later in this case. |
| 107 | if (MO.isDef() && !LI.hasSubRanges()) |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 108 | createDeadDef(*Indexes, *Alloc, LI, MO); |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 109 | } |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 110 | |
| 111 | // We may have created empty live ranges for partially undefined uses, we |
| 112 | // can't keep them because we won't find defs in them later. |
| 113 | LI.removeEmptySubRanges(); |
| 114 | |
| 115 | // Step 2: Extend live segments to all uses, constructing SSA form as |
| 116 | // necessary. |
Matthias Braun | dbcca0d | 2014-12-24 02:11:51 +0000 | [diff] [blame] | 117 | if (LI.hasSubRanges()) { |
| 118 | for (LiveInterval::SubRange &S : LI.subranges()) { |
| 119 | resetLiveOutMap(); |
| 120 | extendToUses(S, Reg, S.LaneMask); |
| 121 | } |
| 122 | LI.clear(); |
| 123 | LI.constructMainRangeFromSubranges(*Indexes, *Alloc); |
| 124 | } else { |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 125 | resetLiveOutMap(); |
Matthias Braun | dbcca0d | 2014-12-24 02:11:51 +0000 | [diff] [blame] | 126 | extendToUses(LI, Reg, ~0u); |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 127 | } |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 128 | } |
| 129 | |
| 130 | |
Matthias Braun | c3a72c2 | 2014-12-15 21:36:35 +0000 | [diff] [blame] | 131 | void LiveRangeCalc::createDeadDefs(LiveRange &LR, unsigned Reg) { |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 132 | assert(MRI && Indexes && "call reset() first"); |
| 133 | |
| 134 | // Visit all def operands. If the same instruction has multiple defs of Reg, |
Matthias Braun | 2d5c32b | 2013-10-10 21:28:57 +0000 | [diff] [blame] | 135 | // LR.createDeadDef() will deduplicate. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 136 | for (MachineOperand &MO : MRI->def_operands(Reg)) |
| 137 | createDeadDef(*Indexes, *Alloc, LR, MO); |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 138 | } |
| 139 | |
| 140 | |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 141 | void LiveRangeCalc::extendToUses(LiveRange &LR, unsigned Reg, unsigned Mask) { |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 142 | // Visit all operands that read Reg. This may include partial defs. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 143 | const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); |
Owen Anderson | b36376e | 2014-03-17 19:36:09 +0000 | [diff] [blame] | 144 | for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { |
Jakob Stoklund Olesen | 4aed470 | 2012-09-06 18:15:15 +0000 | [diff] [blame] | 145 | // Clear all kill flags. They will be reinserted after register allocation |
| 146 | // by LiveIntervalAnalysis::addKillFlags(). |
| 147 | if (MO.isUse()) |
| 148 | MO.setIsKill(false); |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 149 | else { |
| 150 | // We only care about uses, but on the main range (mask ~0u) this includes |
| 151 | // the "virtual" reads happening for subregister defs. |
| 152 | if (Mask != ~0u) |
| 153 | continue; |
| 154 | } |
| 155 | |
Matthias Braun | c3a72c2 | 2014-12-15 21:36:35 +0000 | [diff] [blame] | 156 | if (!MO.readsReg()) |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 157 | continue; |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 158 | unsigned SubReg = MO.getSubReg(); |
| 159 | if (SubReg != 0) { |
| 160 | unsigned SubRegMask = TRI.getSubRegIndexLaneMask(SubReg); |
| 161 | // Ignore uses not covering the current subrange. |
| 162 | if ((SubRegMask & Mask) == 0) |
| 163 | continue; |
| 164 | } |
| 165 | |
| 166 | // Determine the actual place of the use. |
| 167 | const MachineInstr *MI = MO.getParent(); |
| 168 | unsigned OpNo = (&MO - &MI->getOperand(0)); |
| 169 | SlotIndex UseIdx; |
| 170 | if (MI->isPHI()) { |
| 171 | assert(!MO.isDef() && "Cannot handle PHI def of partial register."); |
| 172 | // The actual place where a phi operand is used is the end of the pred |
| 173 | // MBB. PHI operands are paired: (Reg, PredMBB). |
| 174 | UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo+1).getMBB()); |
| 175 | } else { |
| 176 | // Check for early-clobber redefs. |
| 177 | bool isEarlyClobber = false; |
| 178 | unsigned DefIdx; |
| 179 | if (MO.isDef()) |
| 180 | isEarlyClobber = MO.isEarlyClobber(); |
| 181 | else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) { |
| 182 | // FIXME: This would be a lot easier if tied early-clobber uses also |
| 183 | // had an early-clobber flag. |
| 184 | isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber(); |
| 185 | } |
| 186 | UseIdx = Indexes->getInstructionIndex(MI).getRegSlot(isEarlyClobber); |
| 187 | } |
| 188 | |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 189 | // MI is reading Reg. We may have visited MI before if it happens to be |
| 190 | // reading Reg multiple times. That is OK, extend() is idempotent. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 191 | extend(LR, UseIdx, Reg); |
Jakob Stoklund Olesen | 989b3b1 | 2012-06-05 21:54:09 +0000 | [diff] [blame] | 192 | } |
| 193 | } |
| 194 | |
| 195 | |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 196 | void LiveRangeCalc::updateFromLiveIns() { |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 197 | LiveRangeUpdater Updater; |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 198 | for (const LiveInBlock &I : LiveIn) { |
| 199 | if (!I.DomNode) |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 200 | continue; |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 201 | MachineBasicBlock *MBB = I.DomNode->getBlock(); |
| 202 | assert(I.Value && "No live-in value found"); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 203 | SlotIndex Start, End; |
Benjamin Kramer | d6f1f84 | 2014-03-02 13:30:33 +0000 | [diff] [blame] | 204 | std::tie(Start, End) = Indexes->getMBBRange(MBB); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 205 | |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 206 | if (I.Kill.isValid()) |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 207 | // Value is killed inside this block. |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 208 | End = I.Kill; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 209 | else { |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 210 | // The value is live-through, update LiveOut as well. |
| 211 | // Defer the Domtree lookup until it is needed. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 212 | assert(Seen.test(MBB->getNumber())); |
| 213 | Map[MBB] = LiveOutPair(I.Value, nullptr); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 214 | } |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 215 | Updater.setDest(&I.LR); |
| 216 | Updater.add(Start, End, I.Value); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 217 | } |
| 218 | LiveIn.clear(); |
| 219 | } |
| 220 | |
| 221 | |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 222 | void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg) { |
| 223 | assert(Use.isValid() && "Invalid SlotIndex"); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 224 | assert(Indexes && "Missing SlotIndexes"); |
| 225 | assert(DomTree && "Missing dominator tree"); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 226 | |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 227 | MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot()); |
| 228 | assert(UseMBB && "No MBB at Use"); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 229 | |
| 230 | // Is there a def in the same MBB we can extend? |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 231 | if (LR.extendInBlock(Indexes->getMBBStartIdx(UseMBB), Use)) |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 232 | return; |
| 233 | |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 234 | // Find the single reaching def, or determine if Use is jointly dominated by |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 235 | // multiple values, and we may need to create even more phi-defs to preserve |
| 236 | // VNInfo SSA form. Perform a search for all predecessor blocks where we |
| 237 | // know the dominating VNInfo. |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 238 | if (findReachingDefs(LR, *UseMBB, Use, PhysReg)) |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 239 | return; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 240 | |
| 241 | // When there were multiple different values, we may need new PHIs. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 242 | calculateValues(); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 243 | } |
| 244 | |
| 245 | |
| 246 | // This function is called by a client after using the low-level API to add |
| 247 | // live-out and live-in blocks. The unique value optimization is not |
| 248 | // available, SplitEditor::transferValues handles that case directly anyway. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 249 | void LiveRangeCalc::calculateValues() { |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 250 | assert(Indexes && "Missing SlotIndexes"); |
| 251 | assert(DomTree && "Missing dominator tree"); |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 252 | updateSSA(); |
| 253 | updateFromLiveIns(); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 254 | } |
| 255 | |
| 256 | |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 257 | bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB, |
| 258 | SlotIndex Use, unsigned PhysReg) { |
| 259 | unsigned UseMBBNum = UseMBB.getNumber(); |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 260 | |
Matthias Braun | 2d5c32b | 2013-10-10 21:28:57 +0000 | [diff] [blame] | 261 | // Block numbers where LR should be live-in. |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 262 | SmallVector<unsigned, 16> WorkList(1, UseMBBNum); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 263 | |
| 264 | // Remember if we have seen more than one value. |
| 265 | bool UniqueVNI = true; |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 266 | VNInfo *TheVNI = nullptr; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 267 | |
| 268 | // Using Seen as a visited set, perform a BFS for all reaching defs. |
| 269 | for (unsigned i = 0; i != WorkList.size(); ++i) { |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 270 | MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]); |
Jakob Stoklund Olesen | 3d604ab | 2012-07-13 23:39:05 +0000 | [diff] [blame] | 271 | |
| 272 | #ifndef NDEBUG |
| 273 | if (MBB->pred_empty()) { |
| 274 | MBB->getParent()->verify(); |
Matthias Braun | 5391754 | 2015-05-11 18:47:47 +0000 | [diff] [blame^] | 275 | errs() << "Use of " << PrintReg(PhysReg) |
| 276 | << " does not have a corresponding definition on every path:\n"; |
| 277 | const MachineInstr *MI = Indexes->getInstructionFromIndex(Use); |
| 278 | if (MI != nullptr) |
| 279 | errs() << Use << " " << *MI; |
Jakob Stoklund Olesen | 3d604ab | 2012-07-13 23:39:05 +0000 | [diff] [blame] | 280 | llvm_unreachable("Use not jointly dominated by defs."); |
| 281 | } |
| 282 | |
| 283 | if (TargetRegisterInfo::isPhysicalRegister(PhysReg) && |
| 284 | !MBB->isLiveIn(PhysReg)) { |
| 285 | MBB->getParent()->verify(); |
Matthias Braun | 5391754 | 2015-05-11 18:47:47 +0000 | [diff] [blame^] | 286 | errs() << "The register " << PrintReg(PhysReg) |
| 287 | << " needs to be live in to BB#" << MBB->getNumber() |
Jakob Stoklund Olesen | 3d604ab | 2012-07-13 23:39:05 +0000 | [diff] [blame] | 288 | << ", but is missing from the live-in list.\n"; |
| 289 | llvm_unreachable("Invalid global physical register"); |
| 290 | } |
| 291 | #endif |
| 292 | |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 293 | for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), |
Matthias Braun | 2d5c32b | 2013-10-10 21:28:57 +0000 | [diff] [blame] | 294 | PE = MBB->pred_end(); PI != PE; ++PI) { |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 295 | MachineBasicBlock *Pred = *PI; |
| 296 | |
| 297 | // Is this a known live-out block? |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 298 | if (Seen.test(Pred->getNumber())) { |
| 299 | if (VNInfo *VNI = Map[Pred].first) { |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 300 | if (TheVNI && TheVNI != VNI) |
| 301 | UniqueVNI = false; |
| 302 | TheVNI = VNI; |
| 303 | } |
| 304 | continue; |
| 305 | } |
| 306 | |
| 307 | SlotIndex Start, End; |
Benjamin Kramer | d6f1f84 | 2014-03-02 13:30:33 +0000 | [diff] [blame] | 308 | std::tie(Start, End) = Indexes->getMBBRange(Pred); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 309 | |
| 310 | // First time we see Pred. Try to determine the live-out value, but set |
| 311 | // it as null if Pred is live-through with an unknown value. |
Matthias Braun | 2d5c32b | 2013-10-10 21:28:57 +0000 | [diff] [blame] | 312 | VNInfo *VNI = LR.extendInBlock(Start, End); |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 313 | setLiveOutValue(Pred, VNI); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 314 | if (VNI) { |
| 315 | if (TheVNI && TheVNI != VNI) |
| 316 | UniqueVNI = false; |
| 317 | TheVNI = VNI; |
| 318 | continue; |
| 319 | } |
| 320 | |
| 321 | // No, we need a live-in value for Pred as well |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 322 | if (Pred != &UseMBB) |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 323 | WorkList.push_back(Pred->getNumber()); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 324 | else |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 325 | // Loopback to UseMBB, so value is really live through. |
| 326 | Use = SlotIndex(); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 327 | } |
| 328 | } |
| 329 | |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 330 | LiveIn.clear(); |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 331 | |
| 332 | // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but |
| 333 | // neither require it. Skip the sorting overhead for small updates. |
| 334 | if (WorkList.size() > 4) |
| 335 | array_pod_sort(WorkList.begin(), WorkList.end()); |
| 336 | |
| 337 | // If a unique reaching def was found, blit in the live ranges immediately. |
| 338 | if (UniqueVNI) { |
Matthias Braun | 2d5c32b | 2013-10-10 21:28:57 +0000 | [diff] [blame] | 339 | LiveRangeUpdater Updater(&LR); |
| 340 | for (SmallVectorImpl<unsigned>::const_iterator I = WorkList.begin(), |
| 341 | E = WorkList.end(); I != E; ++I) { |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 342 | SlotIndex Start, End; |
Benjamin Kramer | d6f1f84 | 2014-03-02 13:30:33 +0000 | [diff] [blame] | 343 | std::tie(Start, End) = Indexes->getMBBRange(*I); |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 344 | // Trim the live range in UseMBB. |
| 345 | if (*I == UseMBBNum && Use.isValid()) |
| 346 | End = Use; |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 347 | else |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 348 | Map[MF->getBlockNumbered(*I)] = LiveOutPair(TheVNI, nullptr); |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 349 | Updater.add(Start, End, TheVNI); |
| 350 | } |
| 351 | return true; |
| 352 | } |
| 353 | |
| 354 | // Multiple values were found, so transfer the work list to the LiveIn array |
| 355 | // where UpdateSSA will use it as a work list. |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 356 | LiveIn.reserve(WorkList.size()); |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 357 | for (SmallVectorImpl<unsigned>::const_iterator |
| 358 | I = WorkList.begin(), E = WorkList.end(); I != E; ++I) { |
| 359 | MachineBasicBlock *MBB = MF->getBlockNumbered(*I); |
Matthias Braun | 2d5c32b | 2013-10-10 21:28:57 +0000 | [diff] [blame] | 360 | addLiveInBlock(LR, DomTree->getNode(MBB)); |
Matthias Braun | 11042c8 | 2015-02-18 01:50:52 +0000 | [diff] [blame] | 361 | if (MBB == &UseMBB) |
| 362 | LiveIn.back().Kill = Use; |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 363 | } |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 364 | |
Jakob Stoklund Olesen | b389271 | 2013-02-20 23:08:26 +0000 | [diff] [blame] | 365 | return false; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 366 | } |
| 367 | |
| 368 | |
| 369 | // This is essentially the same iterative algorithm that SSAUpdater uses, |
| 370 | // except we already have a dominator tree, so we don't have to recompute it. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 371 | void LiveRangeCalc::updateSSA() { |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 372 | assert(Indexes && "Missing SlotIndexes"); |
| 373 | assert(DomTree && "Missing dominator tree"); |
| 374 | |
| 375 | // Interate until convergence. |
| 376 | unsigned Changes; |
| 377 | do { |
| 378 | Changes = 0; |
| 379 | // Propagate live-out values down the dominator tree, inserting phi-defs |
| 380 | // when necessary. |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 381 | for (LiveInBlock &I : LiveIn) { |
| 382 | MachineDomTreeNode *Node = I.DomNode; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 383 | // Skip block if the live-in value has already been determined. |
| 384 | if (!Node) |
| 385 | continue; |
| 386 | MachineBasicBlock *MBB = Node->getBlock(); |
| 387 | MachineDomTreeNode *IDom = Node->getIDom(); |
| 388 | LiveOutPair IDomValue; |
| 389 | |
| 390 | // We need a live-in value to a block with no immediate dominator? |
| 391 | // This is probably an unreachable block that has survived somehow. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 392 | bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber()); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 393 | |
| 394 | // IDom dominates all of our predecessors, but it may not be their |
| 395 | // immediate dominator. Check if any of them have live-out values that are |
| 396 | // properly dominated by IDom. If so, we need a phi-def here. |
| 397 | if (!needPHI) { |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 398 | IDomValue = Map[IDom->getBlock()]; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 399 | |
| 400 | // Cache the DomTree node that defined the value. |
| 401 | if (IDomValue.first && !IDomValue.second) |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 402 | Map[IDom->getBlock()].second = IDomValue.second = |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 403 | DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def)); |
| 404 | |
| 405 | for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), |
| 406 | PE = MBB->pred_end(); PI != PE; ++PI) { |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 407 | LiveOutPair &Value = Map[*PI]; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 408 | if (!Value.first || Value.first == IDomValue.first) |
| 409 | continue; |
| 410 | |
| 411 | // Cache the DomTree node that defined the value. |
| 412 | if (!Value.second) |
| 413 | Value.second = |
| 414 | DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def)); |
| 415 | |
| 416 | // This predecessor is carrying something other than IDomValue. |
| 417 | // It could be because IDomValue hasn't propagated yet, or it could be |
| 418 | // because MBB is in the dominance frontier of that value. |
| 419 | if (DomTree->dominates(IDom, Value.second)) { |
| 420 | needPHI = true; |
| 421 | break; |
| 422 | } |
| 423 | } |
| 424 | } |
| 425 | |
| 426 | // The value may be live-through even if Kill is set, as can happen when |
| 427 | // we are called from extendRange. In that case LiveOutSeen is true, and |
| 428 | // LiveOut indicates a foreign or missing value. |
Matthias Braun | 1aed6ff | 2014-12-16 04:03:38 +0000 | [diff] [blame] | 429 | LiveOutPair &LOP = Map[MBB]; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 430 | |
| 431 | // Create a phi-def if required. |
| 432 | if (needPHI) { |
| 433 | ++Changes; |
| 434 | assert(Alloc && "Need VNInfo allocator to create PHI-defs"); |
| 435 | SlotIndex Start, End; |
Benjamin Kramer | d6f1f84 | 2014-03-02 13:30:33 +0000 | [diff] [blame] | 436 | std::tie(Start, End) = Indexes->getMBBRange(MBB); |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 437 | LiveRange &LR = I.LR; |
Matthias Braun | 2d5c32b | 2013-10-10 21:28:57 +0000 | [diff] [blame] | 438 | VNInfo *VNI = LR.getNextValue(Start, *Alloc); |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 439 | I.Value = VNI; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 440 | // This block is done, we know the final value. |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 441 | I.DomNode = nullptr; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 442 | |
Matthias Braun | 2f66232 | 2014-12-10 01:12:12 +0000 | [diff] [blame] | 443 | // Add liveness since updateFromLiveIns now skips this node. |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 444 | if (I.Kill.isValid()) |
| 445 | LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI)); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 446 | else { |
Matthias Braun | 2d5c32b | 2013-10-10 21:28:57 +0000 | [diff] [blame] | 447 | LR.addSegment(LiveInterval::Segment(Start, End, VNI)); |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 448 | LOP = LiveOutPair(VNI, Node); |
| 449 | } |
| 450 | } else if (IDomValue.first) { |
| 451 | // No phi-def here. Remember incoming value. |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 452 | I.Value = IDomValue.first; |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 453 | |
| 454 | // If the IDomValue is killed in the block, don't propagate through. |
Matthias Braun | 42fab34 | 2014-12-15 19:40:46 +0000 | [diff] [blame] | 455 | if (I.Kill.isValid()) |
Jakob Stoklund Olesen | 487f2a3 | 2011-09-13 01:34:21 +0000 | [diff] [blame] | 456 | continue; |
| 457 | |
| 458 | // Propagate IDomValue if it isn't killed: |
| 459 | // MBB is live-out and doesn't define its own value. |
| 460 | if (LOP.first == IDomValue.first) |
| 461 | continue; |
| 462 | ++Changes; |
| 463 | LOP = IDomValue; |
| 464 | } |
| 465 | } |
| 466 | } while (Changes); |
| 467 | } |