461 lines · cpp
1//===- LiveRangeCalc.cpp - Calculate live ranges -------------------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// Implementation of the LiveRangeCalc class.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/CodeGen/LiveRangeCalc.h"14#include "llvm/ADT/BitVector.h"15#include "llvm/ADT/STLExtras.h"16#include "llvm/ADT/SetVector.h"17#include "llvm/ADT/SmallVector.h"18#include "llvm/CodeGen/LiveInterval.h"19#include "llvm/CodeGen/MachineBasicBlock.h"20#include "llvm/CodeGen/MachineDominators.h"21#include "llvm/CodeGen/MachineFunction.h"22#include "llvm/CodeGen/MachineInstr.h"23#include "llvm/CodeGen/MachineRegisterInfo.h"24#include "llvm/CodeGen/SlotIndexes.h"25#include "llvm/CodeGen/TargetRegisterInfo.h"26#include "llvm/Support/ErrorHandling.h"27#include "llvm/Support/raw_ostream.h"28#include <cassert>29#include <iterator>30#include <tuple>31 32using namespace llvm;33 34#define DEBUG_TYPE "regalloc"35 36// Reserve an address that indicates a value that is known to be "undef".37static VNInfo UndefVNI(0xbad, SlotIndex());38 39void LiveRangeCalc::resetLiveOutMap() {40 unsigned NumBlocks = MF->getNumBlockIDs();41 Seen.clear();42 Seen.resize(NumBlocks);43 EntryInfos.clear();44 Map.resize(NumBlocks);45}46 47void LiveRangeCalc::reset(const MachineFunction *mf,48 SlotIndexes *SI,49 MachineDominatorTree *MDT,50 VNInfo::Allocator *VNIA) {51 MF = mf;52 MRI = &MF->getRegInfo();53 Indexes = SI;54 DomTree = MDT;55 Alloc = VNIA;56 resetLiveOutMap();57 LiveIn.clear();58}59 60void LiveRangeCalc::updateFromLiveIns() {61 LiveRangeUpdater Updater;62 for (const LiveInBlock &I : LiveIn) {63 if (!I.DomNode)64 continue;65 MachineBasicBlock *MBB = I.DomNode->getBlock();66 assert(I.Value && "No live-in value found");67 SlotIndex Start, End;68 std::tie(Start, End) = Indexes->getMBBRange(MBB);69 70 if (I.Kill.isValid())71 // Value is killed inside this block.72 End = I.Kill;73 else {74 // The value is live-through, update LiveOut as well.75 // Defer the Domtree lookup until it is needed.76 assert(Seen.test(MBB->getNumber()));77 Map[MBB] = LiveOutPair(I.Value, nullptr);78 }79 Updater.setDest(&I.LR);80 Updater.add(Start, End, I.Value);81 }82 LiveIn.clear();83}84 85void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, Register PhysReg,86 ArrayRef<SlotIndex> Undefs) {87 assert(Use.isValid() && "Invalid SlotIndex");88 assert(Indexes && "Missing SlotIndexes");89 assert(DomTree && "Missing dominator tree");90 91 MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());92 assert(UseMBB && "No MBB at Use");93 94 // Is there a def in the same MBB we can extend?95 auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);96 if (EP.first != nullptr || EP.second)97 return;98 99 // Find the single reaching def, or determine if Use is jointly dominated by100 // multiple values, and we may need to create even more phi-defs to preserve101 // VNInfo SSA form. Perform a search for all predecessor blocks where we102 // know the dominating VNInfo.103 if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))104 return;105 106 // When there were multiple different values, we may need new PHIs.107 calculateValues();108}109 110// This function is called by a client after using the low-level API to add111// live-out and live-in blocks. The unique value optimization is not112// available, SplitEditor::transferValues handles that case directly anyway.113void LiveRangeCalc::calculateValues() {114 assert(Indexes && "Missing SlotIndexes");115 assert(DomTree && "Missing dominator tree");116 updateSSA();117 updateFromLiveIns();118}119 120bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,121 MachineBasicBlock &MBB, BitVector &DefOnEntry,122 BitVector &UndefOnEntry) {123 unsigned BN = MBB.getNumber();124 if (DefOnEntry[BN])125 return true;126 if (UndefOnEntry[BN])127 return false;128 129 auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {130 for (MachineBasicBlock *S : B.successors())131 DefOnEntry[S->getNumber()] = true;132 DefOnEntry[BN] = true;133 return true;134 };135 136 SetVector<unsigned> WorkList;137 // Checking if the entry of MBB is reached by some def: add all predecessors138 // that are potentially defined-on-exit to the work list.139 for (MachineBasicBlock *P : MBB.predecessors())140 WorkList.insert(P->getNumber());141 142 for (unsigned i = 0; i != WorkList.size(); ++i) {143 // Determine if the exit from the block is reached by some def.144 unsigned N = WorkList[i];145 MachineBasicBlock &B = *MF->getBlockNumbered(N);146 if (Seen[N]) {147 const LiveOutPair &LOB = Map[&B];148 if (LOB.first != nullptr && LOB.first != &UndefVNI)149 return MarkDefined(B);150 }151 SlotIndex Begin, End;152 std::tie(Begin, End) = Indexes->getMBBRange(&B);153 // Treat End as not belonging to B.154 // If LR has a segment S that starts at the next block, i.e. [End, ...),155 // std::upper_bound will return the segment following S. Instead,156 // S should be treated as the first segment that does not overlap B.157 LiveRange::iterator UB = upper_bound(LR, End.getPrevSlot());158 if (UB != LR.begin()) {159 LiveRange::Segment &Seg = *std::prev(UB);160 if (Seg.end > Begin) {161 // There is a segment that overlaps B. If the range is not explicitly162 // undefined between the end of the segment and the end of the block,163 // treat the block as defined on exit. If it is, go to the next block164 // on the work list.165 if (LR.isUndefIn(Undefs, Seg.end, End))166 continue;167 return MarkDefined(B);168 }169 }170 171 // No segment overlaps with this block. If this block is not defined on172 // entry, or it undefines the range, do not process its predecessors.173 if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {174 UndefOnEntry[N] = true;175 continue;176 }177 if (DefOnEntry[N])178 return MarkDefined(B);179 180 // Still don't know: add all predecessors to the work list.181 for (MachineBasicBlock *P : B.predecessors())182 WorkList.insert(P->getNumber());183 }184 185 UndefOnEntry[BN] = true;186 return false;187}188 189bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,190 SlotIndex Use, Register PhysReg,191 ArrayRef<SlotIndex> Undefs) {192 unsigned UseMBBNum = UseMBB.getNumber();193 194 // Block numbers where LR should be live-in.195 SmallVector<unsigned, 16> WorkList(1, UseMBBNum);196 197 // Remember if we have seen more than one value.198 bool UniqueVNI = true;199 VNInfo *TheVNI = nullptr;200 201 bool FoundUndef = false;202 203 // Using Seen as a visited set, perform a BFS for all reaching defs.204 for (unsigned i = 0; i != WorkList.size(); ++i) {205 MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);206 207#ifndef NDEBUG208 if (MBB->pred_empty()) {209 MBB->getParent()->verify(nullptr, nullptr, &errs());210 errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())211 << " does not have a corresponding definition on every path:\n";212 const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);213 if (MI != nullptr)214 errs() << Use << " " << *MI;215 report_fatal_error("Use not jointly dominated by defs.");216 }217 218 if (PhysReg.isPhysical()) {219 const TargetRegisterInfo *TRI = MRI->getTargetRegisterInfo();220 bool IsLiveIn = MBB->isLiveIn(PhysReg);221 for (MCRegAliasIterator Alias(PhysReg, TRI, false); !IsLiveIn && Alias.isValid(); ++Alias)222 IsLiveIn = MBB->isLiveIn(*Alias);223 if (!IsLiveIn) {224 MBB->getParent()->verify(nullptr, nullptr, &errs());225 errs() << "The register " << printReg(PhysReg, TRI)226 << " needs to be live in to " << printMBBReference(*MBB)227 << ", but is missing from the live-in list.\n";228 report_fatal_error("Invalid global physical register");229 }230 }231#endif232 FoundUndef |= MBB->pred_empty();233 234 for (MachineBasicBlock *Pred : MBB->predecessors()) {235 // Is this a known live-out block?236 if (Seen.test(Pred->getNumber())) {237 if (VNInfo *VNI = Map[Pred].first) {238 if (TheVNI && TheVNI != VNI)239 UniqueVNI = false;240 TheVNI = VNI;241 }242 continue;243 }244 245 SlotIndex Start, End;246 std::tie(Start, End) = Indexes->getMBBRange(Pred);247 248 // First time we see Pred. Try to determine the live-out value, but set249 // it as null if Pred is live-through with an unknown value.250 auto EP = LR.extendInBlock(Undefs, Start, End);251 VNInfo *VNI = EP.first;252 FoundUndef |= EP.second;253 setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);254 if (VNI) {255 if (TheVNI && TheVNI != VNI)256 UniqueVNI = false;257 TheVNI = VNI;258 }259 if (VNI || EP.second)260 continue;261 262 // No, we need a live-in value for Pred as well263 if (Pred != &UseMBB)264 WorkList.push_back(Pred->getNumber());265 else266 // Loopback to UseMBB, so value is really live through.267 Use = SlotIndex();268 }269 }270 271 LiveIn.clear();272 FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);273 if (!Undefs.empty() && FoundUndef)274 UniqueVNI = false;275 276 // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but277 // neither require it. Skip the sorting overhead for small updates.278 if (WorkList.size() > 4)279 array_pod_sort(WorkList.begin(), WorkList.end());280 281 // If a unique reaching def was found, blit in the live ranges immediately.282 if (UniqueVNI) {283 assert(TheVNI != nullptr && TheVNI != &UndefVNI);284 LiveRangeUpdater Updater(&LR);285 for (unsigned BN : WorkList) {286 SlotIndex Start, End;287 std::tie(Start, End) = Indexes->getMBBRange(BN);288 // Trim the live range in UseMBB.289 if (BN == UseMBBNum && Use.isValid())290 End = Use;291 else292 Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);293 Updater.add(Start, End, TheVNI);294 }295 return true;296 }297 298 // Prepare the defined/undefined bit vectors.299 EntryInfoMap::iterator Entry;300 bool DidInsert;301 std::tie(Entry, DidInsert) = EntryInfos.insert(302 std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));303 if (DidInsert) {304 // Initialize newly inserted entries.305 unsigned N = MF->getNumBlockIDs();306 Entry->second.first.resize(N);307 Entry->second.second.resize(N);308 }309 BitVector &DefOnEntry = Entry->second.first;310 BitVector &UndefOnEntry = Entry->second.second;311 312 // Multiple values were found, so transfer the work list to the LiveIn array313 // where UpdateSSA will use it as a work list.314 LiveIn.reserve(WorkList.size());315 for (unsigned BN : WorkList) {316 MachineBasicBlock *MBB = MF->getBlockNumbered(BN);317 if (!Undefs.empty() &&318 !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))319 continue;320 addLiveInBlock(LR, DomTree->getNode(MBB));321 if (MBB == &UseMBB)322 LiveIn.back().Kill = Use;323 }324 325 return false;326}327 328// This is essentially the same iterative algorithm that SSAUpdater uses,329// except we already have a dominator tree, so we don't have to recompute it.330void LiveRangeCalc::updateSSA() {331 assert(Indexes && "Missing SlotIndexes");332 assert(DomTree && "Missing dominator tree");333 334 // Interate until convergence.335 bool Changed;336 do {337 Changed = false;338 // Propagate live-out values down the dominator tree, inserting phi-defs339 // when necessary.340 for (LiveInBlock &I : LiveIn) {341 MachineDomTreeNode *Node = I.DomNode;342 // Skip block if the live-in value has already been determined.343 if (!Node)344 continue;345 MachineBasicBlock *MBB = Node->getBlock();346 MachineDomTreeNode *IDom = Node->getIDom();347 LiveOutPair IDomValue;348 349 // We need a live-in value to a block with no immediate dominator?350 // This is probably an unreachable block that has survived somehow.351 bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());352 353 // IDom dominates all of our predecessors, but it may not be their354 // immediate dominator. Check if any of them have live-out values that are355 // properly dominated by IDom. If so, we need a phi-def here.356 if (!needPHI) {357 IDomValue = Map[IDom->getBlock()];358 359 // Cache the DomTree node that defined the value.360 if (IDomValue.first && IDomValue.first != &UndefVNI &&361 !IDomValue.second) {362 Map[IDom->getBlock()].second = IDomValue.second =363 DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));364 }365 366 for (MachineBasicBlock *Pred : MBB->predecessors()) {367 LiveOutPair &Value = Map[Pred];368 if (!Value.first || Value.first == IDomValue.first)369 continue;370 if (Value.first == &UndefVNI) {371 needPHI = true;372 break;373 }374 375 // Cache the DomTree node that defined the value.376 if (!Value.second)377 Value.second =378 DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));379 380 // This predecessor is carrying something other than IDomValue.381 // It could be because IDomValue hasn't propagated yet, or it could be382 // because MBB is in the dominance frontier of that value.383 if (DomTree->dominates(IDom, Value.second)) {384 needPHI = true;385 break;386 }387 }388 }389 390 // The value may be live-through even if Kill is set, as can happen when391 // we are called from extendRange. In that case LiveOutSeen is true, and392 // LiveOut indicates a foreign or missing value.393 LiveOutPair &LOP = Map[MBB];394 395 // Create a phi-def if required.396 if (needPHI) {397 Changed = true;398 assert(Alloc && "Need VNInfo allocator to create PHI-defs");399 SlotIndex Start, End;400 std::tie(Start, End) = Indexes->getMBBRange(MBB);401 LiveRange &LR = I.LR;402 VNInfo *VNI = LR.getNextValue(Start, *Alloc);403 I.Value = VNI;404 // This block is done, we know the final value.405 I.DomNode = nullptr;406 407 // Add liveness since updateFromLiveIns now skips this node.408 if (I.Kill.isValid()) {409 if (VNI)410 LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));411 } else {412 if (VNI)413 LR.addSegment(LiveInterval::Segment(Start, End, VNI));414 LOP = LiveOutPair(VNI, Node);415 }416 } else if (IDomValue.first && IDomValue.first != &UndefVNI) {417 // No phi-def here. Remember incoming value.418 I.Value = IDomValue.first;419 420 // If the IDomValue is killed in the block, don't propagate through.421 if (I.Kill.isValid())422 continue;423 424 // Propagate IDomValue if it isn't killed:425 // MBB is live-out and doesn't define its own value.426 if (LOP.first == IDomValue.first)427 continue;428 Changed = true;429 LOP = IDomValue;430 }431 }432 } while (Changed);433}434 435bool LiveRangeCalc::isJointlyDominated(const MachineBasicBlock *MBB,436 ArrayRef<SlotIndex> Defs,437 const SlotIndexes &Indexes) {438 const MachineFunction &MF = *MBB->getParent();439 BitVector DefBlocks(MF.getNumBlockIDs());440 for (SlotIndex I : Defs)441 DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());442 443 unsigned EntryNum = MF.front().getNumber();444 SetVector<unsigned> PredQueue;445 PredQueue.insert(MBB->getNumber());446 for (unsigned i = 0; i != PredQueue.size(); ++i) {447 unsigned BN = PredQueue[i];448 if (DefBlocks[BN])449 continue;450 if (BN == EntryNum) {451 // We found a path from MBB back to the entry block without hitting any of452 // the def blocks.453 return false;454 }455 const MachineBasicBlock *B = MF.getBlockNumbered(BN);456 for (const MachineBasicBlock *P : B->predecessors())457 PredQueue.insert(P->getNumber());458 }459 return true;460}461