| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/GenericDomTree.h |
| Warning: | line 494, column 12 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- SplitKit.cpp - Toolkit for splitting 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-exception | |||
| 6 | // | |||
| 7 | //===----------------------------------------------------------------------===// | |||
| 8 | // | |||
| 9 | // This file contains the SplitAnalysis class as well as mutator functions for | |||
| 10 | // live range splitting. | |||
| 11 | // | |||
| 12 | //===----------------------------------------------------------------------===// | |||
| 13 | ||||
| 14 | #include "SplitKit.h" | |||
| 15 | #include "llvm/ADT/None.h" | |||
| 16 | #include "llvm/ADT/STLExtras.h" | |||
| 17 | #include "llvm/ADT/Statistic.h" | |||
| 18 | #include "llvm/Analysis/AliasAnalysis.h" | |||
| 19 | #include "llvm/CodeGen/LiveRangeEdit.h" | |||
| 20 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" | |||
| 21 | #include "llvm/CodeGen/MachineDominators.h" | |||
| 22 | #include "llvm/CodeGen/MachineInstr.h" | |||
| 23 | #include "llvm/CodeGen/MachineInstrBuilder.h" | |||
| 24 | #include "llvm/CodeGen/MachineLoopInfo.h" | |||
| 25 | #include "llvm/CodeGen/MachineOperand.h" | |||
| 26 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |||
| 27 | #include "llvm/CodeGen/TargetInstrInfo.h" | |||
| 28 | #include "llvm/CodeGen/TargetOpcodes.h" | |||
| 29 | #include "llvm/CodeGen/TargetRegisterInfo.h" | |||
| 30 | #include "llvm/CodeGen/TargetSubtargetInfo.h" | |||
| 31 | #include "llvm/CodeGen/VirtRegMap.h" | |||
| 32 | #include "llvm/Config/llvm-config.h" | |||
| 33 | #include "llvm/IR/DebugLoc.h" | |||
| 34 | #include "llvm/Support/Allocator.h" | |||
| 35 | #include "llvm/Support/BlockFrequency.h" | |||
| 36 | #include "llvm/Support/Debug.h" | |||
| 37 | #include "llvm/Support/ErrorHandling.h" | |||
| 38 | #include "llvm/Support/raw_ostream.h" | |||
| 39 | #include <algorithm> | |||
| 40 | #include <cassert> | |||
| 41 | #include <iterator> | |||
| 42 | #include <limits> | |||
| 43 | #include <tuple> | |||
| 44 | ||||
| 45 | using namespace llvm; | |||
| 46 | ||||
| 47 | #define DEBUG_TYPE"regalloc" "regalloc" | |||
| 48 | ||||
| 49 | STATISTIC(NumFinished, "Number of splits finished")static llvm::Statistic NumFinished = {"regalloc", "NumFinished" , "Number of splits finished"}; | |||
| 50 | STATISTIC(NumSimple, "Number of splits that were simple")static llvm::Statistic NumSimple = {"regalloc", "NumSimple", "Number of splits that were simple" }; | |||
| 51 | STATISTIC(NumCopies, "Number of copies inserted for splitting")static llvm::Statistic NumCopies = {"regalloc", "NumCopies", "Number of copies inserted for splitting" }; | |||
| 52 | STATISTIC(NumRemats, "Number of rematerialized defs for splitting")static llvm::Statistic NumRemats = {"regalloc", "NumRemats", "Number of rematerialized defs for splitting" }; | |||
| 53 | STATISTIC(NumRepairs, "Number of invalid live ranges repaired")static llvm::Statistic NumRepairs = {"regalloc", "NumRepairs" , "Number of invalid live ranges repaired"}; | |||
| 54 | ||||
| 55 | //===----------------------------------------------------------------------===// | |||
| 56 | // Last Insert Point Analysis | |||
| 57 | //===----------------------------------------------------------------------===// | |||
| 58 | ||||
| 59 | InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis, | |||
| 60 | unsigned BBNum) | |||
| 61 | : LIS(lis), LastInsertPoint(BBNum) {} | |||
| 62 | ||||
| 63 | SlotIndex | |||
| 64 | InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI, | |||
| 65 | const MachineBasicBlock &MBB) { | |||
| 66 | unsigned Num = MBB.getNumber(); | |||
| 67 | std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num]; | |||
| 68 | SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB); | |||
| 69 | ||||
| 70 | SmallVector<const MachineBasicBlock *, 1> ExceptionalSuccessors; | |||
| 71 | bool EHPadSuccessor = false; | |||
| 72 | for (const MachineBasicBlock *SMBB : MBB.successors()) { | |||
| 73 | if (SMBB->isEHPad()) { | |||
| 74 | ExceptionalSuccessors.push_back(SMBB); | |||
| 75 | EHPadSuccessor = true; | |||
| 76 | } else if (SMBB->isInlineAsmBrIndirectTarget()) | |||
| 77 | ExceptionalSuccessors.push_back(SMBB); | |||
| 78 | } | |||
| 79 | ||||
| 80 | // Compute insert points on the first call. The pair is independent of the | |||
| 81 | // current live interval. | |||
| 82 | if (!LIP.first.isValid()) { | |||
| 83 | MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator(); | |||
| 84 | if (FirstTerm == MBB.end()) | |||
| 85 | LIP.first = MBBEnd; | |||
| 86 | else | |||
| 87 | LIP.first = LIS.getInstructionIndex(*FirstTerm); | |||
| 88 | ||||
| 89 | // If there is a landing pad or inlineasm_br successor, also find the | |||
| 90 | // instruction. If there is no such instruction, we don't need to do | |||
| 91 | // anything special. We assume there cannot be multiple instructions that | |||
| 92 | // are Calls with EHPad successors or INLINEASM_BR in a block. Further, we | |||
| 93 | // assume that if there are any, they will be after any other call | |||
| 94 | // instructions in the block. | |||
| 95 | if (ExceptionalSuccessors.empty()) | |||
| 96 | return LIP.first; | |||
| 97 | for (const MachineInstr &MI : llvm::reverse(MBB)) { | |||
| 98 | if ((EHPadSuccessor && MI.isCall()) || | |||
| 99 | MI.getOpcode() == TargetOpcode::INLINEASM_BR) { | |||
| 100 | LIP.second = LIS.getInstructionIndex(MI); | |||
| 101 | break; | |||
| 102 | } | |||
| 103 | } | |||
| 104 | } | |||
| 105 | ||||
| 106 | // If CurLI is live into a landing pad successor, move the last insert point | |||
| 107 | // back to the call that may throw. | |||
| 108 | if (!LIP.second) | |||
| 109 | return LIP.first; | |||
| 110 | ||||
| 111 | if (none_of(ExceptionalSuccessors, [&](const MachineBasicBlock *EHPad) { | |||
| 112 | return LIS.isLiveInToMBB(CurLI, EHPad); | |||
| 113 | })) | |||
| 114 | return LIP.first; | |||
| 115 | ||||
| 116 | // Find the value leaving MBB. | |||
| 117 | const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd); | |||
| 118 | if (!VNI) | |||
| 119 | return LIP.first; | |||
| 120 | ||||
| 121 | // The def of statepoint instruction is a gc relocation and it should be alive | |||
| 122 | // in landing pad. So we cannot split interval after statepoint instruction. | |||
| 123 | if (SlotIndex::isSameInstr(VNI->def, LIP.second)) | |||
| 124 | if (auto *I = LIS.getInstructionFromIndex(LIP.second)) | |||
| 125 | if (I->getOpcode() == TargetOpcode::STATEPOINT) | |||
| 126 | return LIP.second; | |||
| 127 | ||||
| 128 | // If the value leaving MBB was defined after the call in MBB, it can't | |||
| 129 | // really be live-in to the landing pad. This can happen if the landing pad | |||
| 130 | // has a PHI, and this register is undef on the exceptional edge. | |||
| 131 | // <rdar://problem/10664933> | |||
| 132 | if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd) | |||
| 133 | return LIP.first; | |||
| 134 | ||||
| 135 | // Value is properly live-in to the landing pad. | |||
| 136 | // Only allow inserts before the call. | |||
| 137 | return LIP.second; | |||
| 138 | } | |||
| 139 | ||||
| 140 | MachineBasicBlock::iterator | |||
| 141 | InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI, | |||
| 142 | MachineBasicBlock &MBB) { | |||
| 143 | SlotIndex LIP = getLastInsertPoint(CurLI, MBB); | |||
| 144 | if (LIP == LIS.getMBBEndIdx(&MBB)) | |||
| 145 | return MBB.end(); | |||
| 146 | return LIS.getInstructionFromIndex(LIP); | |||
| 147 | } | |||
| 148 | ||||
| 149 | //===----------------------------------------------------------------------===// | |||
| 150 | // Split Analysis | |||
| 151 | //===----------------------------------------------------------------------===// | |||
| 152 | ||||
| 153 | SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, | |||
| 154 | const MachineLoopInfo &mli) | |||
| 155 | : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli), | |||
| 156 | TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {} | |||
| 157 | ||||
| 158 | void SplitAnalysis::clear() { | |||
| 159 | UseSlots.clear(); | |||
| 160 | UseBlocks.clear(); | |||
| 161 | ThroughBlocks.clear(); | |||
| 162 | CurLI = nullptr; | |||
| 163 | DidRepairRange = false; | |||
| 164 | } | |||
| 165 | ||||
| 166 | /// analyzeUses - Count instructions, basic blocks, and loops using CurLI. | |||
| 167 | void SplitAnalysis::analyzeUses() { | |||
| 168 | assert(UseSlots.empty() && "Call clear first")((void)0); | |||
| 169 | ||||
| 170 | // First get all the defs from the interval values. This provides the correct | |||
| 171 | // slots for early clobbers. | |||
| 172 | for (const VNInfo *VNI : CurLI->valnos) | |||
| 173 | if (!VNI->isPHIDef() && !VNI->isUnused()) | |||
| 174 | UseSlots.push_back(VNI->def); | |||
| 175 | ||||
| 176 | // Get use slots form the use-def chain. | |||
| 177 | const MachineRegisterInfo &MRI = MF.getRegInfo(); | |||
| 178 | for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg())) | |||
| 179 | if (!MO.isUndef()) | |||
| 180 | UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot()); | |||
| 181 | ||||
| 182 | array_pod_sort(UseSlots.begin(), UseSlots.end()); | |||
| 183 | ||||
| 184 | // Remove duplicates, keeping the smaller slot for each instruction. | |||
| 185 | // That is what we want for early clobbers. | |||
| 186 | UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(), | |||
| 187 | SlotIndex::isSameInstr), | |||
| 188 | UseSlots.end()); | |||
| 189 | ||||
| 190 | // Compute per-live block info. | |||
| 191 | if (!calcLiveBlockInfo()) { | |||
| 192 | // FIXME: calcLiveBlockInfo found inconsistencies in the live range. | |||
| 193 | // I am looking at you, RegisterCoalescer! | |||
| 194 | DidRepairRange = true; | |||
| 195 | ++NumRepairs; | |||
| 196 | LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n")do { } while (false); | |||
| 197 | const_cast<LiveIntervals&>(LIS) | |||
| 198 | .shrinkToUses(const_cast<LiveInterval*>(CurLI)); | |||
| 199 | UseBlocks.clear(); | |||
| 200 | ThroughBlocks.clear(); | |||
| 201 | bool fixed = calcLiveBlockInfo(); | |||
| 202 | (void)fixed; | |||
| 203 | assert(fixed && "Couldn't fix broken live interval")((void)0); | |||
| 204 | } | |||
| 205 | ||||
| 206 | LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "do { } while (false) | |||
| 207 | << UseBlocks.size() << " blocks, through "do { } while (false) | |||
| 208 | << NumThroughBlocks << " blocks.\n")do { } while (false); | |||
| 209 | } | |||
| 210 | ||||
| 211 | /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks | |||
| 212 | /// where CurLI is live. | |||
| 213 | bool SplitAnalysis::calcLiveBlockInfo() { | |||
| 214 | ThroughBlocks.resize(MF.getNumBlockIDs()); | |||
| 215 | NumThroughBlocks = NumGapBlocks = 0; | |||
| 216 | if (CurLI->empty()) | |||
| 217 | return true; | |||
| 218 | ||||
| 219 | LiveInterval::const_iterator LVI = CurLI->begin(); | |||
| 220 | LiveInterval::const_iterator LVE = CurLI->end(); | |||
| 221 | ||||
| 222 | SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE; | |||
| 223 | UseI = UseSlots.begin(); | |||
| 224 | UseE = UseSlots.end(); | |||
| 225 | ||||
| 226 | // Loop over basic blocks where CurLI is live. | |||
| 227 | MachineFunction::iterator MFI = | |||
| 228 | LIS.getMBBFromIndex(LVI->start)->getIterator(); | |||
| 229 | while (true) { | |||
| 230 | BlockInfo BI; | |||
| 231 | BI.MBB = &*MFI; | |||
| 232 | SlotIndex Start, Stop; | |||
| 233 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); | |||
| 234 | ||||
| 235 | // If the block contains no uses, the range must be live through. At one | |||
| 236 | // point, RegisterCoalescer could create dangling ranges that ended | |||
| 237 | // mid-block. | |||
| 238 | if (UseI == UseE || *UseI >= Stop) { | |||
| 239 | ++NumThroughBlocks; | |||
| 240 | ThroughBlocks.set(BI.MBB->getNumber()); | |||
| 241 | // The range shouldn't end mid-block if there are no uses. This shouldn't | |||
| 242 | // happen. | |||
| 243 | if (LVI->end < Stop) | |||
| 244 | return false; | |||
| 245 | } else { | |||
| 246 | // This block has uses. Find the first and last uses in the block. | |||
| 247 | BI.FirstInstr = *UseI; | |||
| 248 | assert(BI.FirstInstr >= Start)((void)0); | |||
| 249 | do ++UseI; | |||
| 250 | while (UseI != UseE && *UseI < Stop); | |||
| 251 | BI.LastInstr = UseI[-1]; | |||
| 252 | assert(BI.LastInstr < Stop)((void)0); | |||
| 253 | ||||
| 254 | // LVI is the first live segment overlapping MBB. | |||
| 255 | BI.LiveIn = LVI->start <= Start; | |||
| 256 | ||||
| 257 | // When not live in, the first use should be a def. | |||
| 258 | if (!BI.LiveIn) { | |||
| 259 | assert(LVI->start == LVI->valno->def && "Dangling Segment start")((void)0); | |||
| 260 | assert(LVI->start == BI.FirstInstr && "First instr should be a def")((void)0); | |||
| 261 | BI.FirstDef = BI.FirstInstr; | |||
| 262 | } | |||
| 263 | ||||
| 264 | // Look for gaps in the live range. | |||
| 265 | BI.LiveOut = true; | |||
| 266 | while (LVI->end < Stop) { | |||
| 267 | SlotIndex LastStop = LVI->end; | |||
| 268 | if (++LVI == LVE || LVI->start >= Stop) { | |||
| 269 | BI.LiveOut = false; | |||
| 270 | BI.LastInstr = LastStop; | |||
| 271 | break; | |||
| 272 | } | |||
| 273 | ||||
| 274 | if (LastStop < LVI->start) { | |||
| 275 | // There is a gap in the live range. Create duplicate entries for the | |||
| 276 | // live-in snippet and the live-out snippet. | |||
| 277 | ++NumGapBlocks; | |||
| 278 | ||||
| 279 | // Push the Live-in part. | |||
| 280 | BI.LiveOut = false; | |||
| 281 | UseBlocks.push_back(BI); | |||
| 282 | UseBlocks.back().LastInstr = LastStop; | |||
| 283 | ||||
| 284 | // Set up BI for the live-out part. | |||
| 285 | BI.LiveIn = false; | |||
| 286 | BI.LiveOut = true; | |||
| 287 | BI.FirstInstr = BI.FirstDef = LVI->start; | |||
| 288 | } | |||
| 289 | ||||
| 290 | // A Segment that starts in the middle of the block must be a def. | |||
| 291 | assert(LVI->start == LVI->valno->def && "Dangling Segment start")((void)0); | |||
| 292 | if (!BI.FirstDef) | |||
| 293 | BI.FirstDef = LVI->start; | |||
| 294 | } | |||
| 295 | ||||
| 296 | UseBlocks.push_back(BI); | |||
| 297 | ||||
| 298 | // LVI is now at LVE or LVI->end >= Stop. | |||
| 299 | if (LVI == LVE) | |||
| 300 | break; | |||
| 301 | } | |||
| 302 | ||||
| 303 | // Live segment ends exactly at Stop. Move to the next segment. | |||
| 304 | if (LVI->end == Stop && ++LVI == LVE) | |||
| 305 | break; | |||
| 306 | ||||
| 307 | // Pick the next basic block. | |||
| 308 | if (LVI->start < Stop) | |||
| 309 | ++MFI; | |||
| 310 | else | |||
| 311 | MFI = LIS.getMBBFromIndex(LVI->start)->getIterator(); | |||
| 312 | } | |||
| 313 | ||||
| 314 | assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count")((void)0); | |||
| 315 | return true; | |||
| 316 | } | |||
| 317 | ||||
| 318 | unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { | |||
| 319 | if (cli->empty()) | |||
| 320 | return 0; | |||
| 321 | LiveInterval *li = const_cast<LiveInterval*>(cli); | |||
| 322 | LiveInterval::iterator LVI = li->begin(); | |||
| 323 | LiveInterval::iterator LVE = li->end(); | |||
| 324 | unsigned Count = 0; | |||
| 325 | ||||
| 326 | // Loop over basic blocks where li is live. | |||
| 327 | MachineFunction::const_iterator MFI = | |||
| 328 | LIS.getMBBFromIndex(LVI->start)->getIterator(); | |||
| 329 | SlotIndex Stop = LIS.getMBBEndIdx(&*MFI); | |||
| 330 | while (true) { | |||
| 331 | ++Count; | |||
| 332 | LVI = li->advanceTo(LVI, Stop); | |||
| 333 | if (LVI == LVE) | |||
| 334 | return Count; | |||
| 335 | do { | |||
| 336 | ++MFI; | |||
| 337 | Stop = LIS.getMBBEndIdx(&*MFI); | |||
| 338 | } while (Stop <= LVI->start); | |||
| 339 | } | |||
| 340 | } | |||
| 341 | ||||
| 342 | bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const { | |||
| 343 | unsigned OrigReg = VRM.getOriginal(CurLI->reg()); | |||
| 344 | const LiveInterval &Orig = LIS.getInterval(OrigReg); | |||
| 345 | assert(!Orig.empty() && "Splitting empty interval?")((void)0); | |||
| 346 | LiveInterval::const_iterator I = Orig.find(Idx); | |||
| 347 | ||||
| 348 | // Range containing Idx should begin at Idx. | |||
| 349 | if (I != Orig.end() && I->start <= Idx) | |||
| 350 | return I->start == Idx; | |||
| 351 | ||||
| 352 | // Range does not contain Idx, previous must end at Idx. | |||
| 353 | return I != Orig.begin() && (--I)->end == Idx; | |||
| 354 | } | |||
| 355 | ||||
| 356 | void SplitAnalysis::analyze(const LiveInterval *li) { | |||
| 357 | clear(); | |||
| 358 | CurLI = li; | |||
| 359 | analyzeUses(); | |||
| 360 | } | |||
| 361 | ||||
| 362 | //===----------------------------------------------------------------------===// | |||
| 363 | // Split Editor | |||
| 364 | //===----------------------------------------------------------------------===// | |||
| 365 | ||||
| 366 | /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. | |||
| 367 | SplitEditor::SplitEditor(SplitAnalysis &SA, AliasAnalysis &AA, | |||
| 368 | LiveIntervals &LIS, VirtRegMap &VRM, | |||
| 369 | MachineDominatorTree &MDT, | |||
| 370 | MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI) | |||
| 371 | : SA(SA), AA(AA), LIS(LIS), VRM(VRM), | |||
| 372 | MRI(VRM.getMachineFunction().getRegInfo()), MDT(MDT), | |||
| 373 | TII(*VRM.getMachineFunction().getSubtarget().getInstrInfo()), | |||
| 374 | TRI(*VRM.getMachineFunction().getSubtarget().getRegisterInfo()), | |||
| 375 | MBFI(MBFI), VRAI(VRAI), RegAssign(Allocator) {} | |||
| 376 | ||||
| 377 | void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { | |||
| 378 | Edit = &LRE; | |||
| 379 | SpillMode = SM; | |||
| 380 | OpenIdx = 0; | |||
| 381 | RegAssign.clear(); | |||
| 382 | Values.clear(); | |||
| 383 | ||||
| 384 | // Reset the LiveIntervalCalc instances needed for this spill mode. | |||
| 385 | LICalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, | |||
| 386 | &LIS.getVNInfoAllocator()); | |||
| 387 | if (SpillMode) | |||
| 388 | LICalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, | |||
| 389 | &LIS.getVNInfoAllocator()); | |||
| 390 | ||||
| 391 | // We don't need an AliasAnalysis since we will only be performing | |||
| 392 | // cheap-as-a-copy remats anyway. | |||
| 393 | Edit->anyRematerializable(nullptr); | |||
| 394 | } | |||
| 395 | ||||
| 396 | #if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP) | |||
| 397 | LLVM_DUMP_METHOD__attribute__((noinline)) void SplitEditor::dump() const { | |||
| 398 | if (RegAssign.empty()) { | |||
| 399 | dbgs() << " empty\n"; | |||
| 400 | return; | |||
| 401 | } | |||
| 402 | ||||
| 403 | for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I) | |||
| 404 | dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); | |||
| 405 | dbgs() << '\n'; | |||
| 406 | } | |||
| 407 | #endif | |||
| 408 | ||||
| 409 | LiveInterval::SubRange &SplitEditor::getSubRangeForMaskExact(LaneBitmask LM, | |||
| 410 | LiveInterval &LI) { | |||
| 411 | for (LiveInterval::SubRange &S : LI.subranges()) | |||
| 412 | if (S.LaneMask == LM) | |||
| 413 | return S; | |||
| 414 | llvm_unreachable("SubRange for this mask not found")__builtin_unreachable(); | |||
| 415 | } | |||
| 416 | ||||
| 417 | LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM, | |||
| 418 | LiveInterval &LI) { | |||
| 419 | for (LiveInterval::SubRange &S : LI.subranges()) | |||
| 420 | if ((S.LaneMask & LM) == LM) | |||
| 421 | return S; | |||
| 422 | llvm_unreachable("SubRange for this mask not found")__builtin_unreachable(); | |||
| 423 | } | |||
| 424 | ||||
| 425 | void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) { | |||
| 426 | if (!LI.hasSubRanges()) { | |||
| 427 | LI.createDeadDef(VNI); | |||
| 428 | return; | |||
| 429 | } | |||
| 430 | ||||
| 431 | SlotIndex Def = VNI->def; | |||
| 432 | if (Original) { | |||
| 433 | // If we are transferring a def from the original interval, make sure | |||
| 434 | // to only update the subranges for which the original subranges had | |||
| 435 | // a def at this location. | |||
| 436 | for (LiveInterval::SubRange &S : LI.subranges()) { | |||
| 437 | auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent()); | |||
| 438 | VNInfo *PV = PS.getVNInfoAt(Def); | |||
| 439 | if (PV != nullptr && PV->def == Def) | |||
| 440 | S.createDeadDef(Def, LIS.getVNInfoAllocator()); | |||
| 441 | } | |||
| 442 | } else { | |||
| 443 | // This is a new def: either from rematerialization, or from an inserted | |||
| 444 | // copy. Since rematerialization can regenerate a definition of a sub- | |||
| 445 | // register, we need to check which subranges need to be updated. | |||
| 446 | const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def); | |||
| 447 | assert(DefMI != nullptr)((void)0); | |||
| 448 | LaneBitmask LM; | |||
| 449 | for (const MachineOperand &DefOp : DefMI->defs()) { | |||
| 450 | Register R = DefOp.getReg(); | |||
| 451 | if (R != LI.reg()) | |||
| 452 | continue; | |||
| 453 | if (unsigned SR = DefOp.getSubReg()) | |||
| 454 | LM |= TRI.getSubRegIndexLaneMask(SR); | |||
| 455 | else { | |||
| 456 | LM = MRI.getMaxLaneMaskForVReg(R); | |||
| 457 | break; | |||
| 458 | } | |||
| 459 | } | |||
| 460 | for (LiveInterval::SubRange &S : LI.subranges()) | |||
| 461 | if ((S.LaneMask & LM).any()) | |||
| 462 | S.createDeadDef(Def, LIS.getVNInfoAllocator()); | |||
| 463 | } | |||
| 464 | } | |||
| 465 | ||||
| 466 | VNInfo *SplitEditor::defValue(unsigned RegIdx, | |||
| 467 | const VNInfo *ParentVNI, | |||
| 468 | SlotIndex Idx, | |||
| 469 | bool Original) { | |||
| 470 | assert(ParentVNI && "Mapping NULL value")((void)0); | |||
| 471 | assert(Idx.isValid() && "Invalid SlotIndex")((void)0); | |||
| 472 | assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI")((void)0); | |||
| 473 | LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); | |||
| 474 | ||||
| 475 | // Create a new value. | |||
| 476 | VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); | |||
| 477 | ||||
| 478 | bool Force = LI->hasSubRanges(); | |||
| 479 | ValueForcePair FP(Force ? nullptr : VNI, Force); | |||
| 480 | // Use insert for lookup, so we can add missing values with a second lookup. | |||
| 481 | std::pair<ValueMap::iterator, bool> InsP = | |||
| 482 | Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP)); | |||
| 483 | ||||
| 484 | // This was the first time (RegIdx, ParentVNI) was mapped, and it is not | |||
| 485 | // forced. Keep it as a simple def without any liveness. | |||
| 486 | if (!Force && InsP.second) | |||
| 487 | return VNI; | |||
| 488 | ||||
| 489 | // If the previous value was a simple mapping, add liveness for it now. | |||
| 490 | if (VNInfo *OldVNI = InsP.first->second.getPointer()) { | |||
| 491 | addDeadDef(*LI, OldVNI, Original); | |||
| 492 | ||||
| 493 | // No longer a simple mapping. Switch to a complex mapping. If the | |||
| 494 | // interval has subranges, make it a forced mapping. | |||
| 495 | InsP.first->second = ValueForcePair(nullptr, Force); | |||
| 496 | } | |||
| 497 | ||||
| 498 | // This is a complex mapping, add liveness for VNI | |||
| 499 | addDeadDef(*LI, VNI, Original); | |||
| 500 | return VNI; | |||
| 501 | } | |||
| 502 | ||||
| 503 | void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI) { | |||
| 504 | ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI.id)]; | |||
| 505 | VNInfo *VNI = VFP.getPointer(); | |||
| 506 | ||||
| 507 | // ParentVNI was either unmapped or already complex mapped. Either way, just | |||
| 508 | // set the force bit. | |||
| 509 | if (!VNI) { | |||
| 510 | VFP.setInt(true); | |||
| 511 | return; | |||
| 512 | } | |||
| 513 | ||||
| 514 | // This was previously a single mapping. Make sure the old def is represented | |||
| 515 | // by a trivial live range. | |||
| 516 | addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false); | |||
| 517 | ||||
| 518 | // Mark as complex mapped, forced. | |||
| 519 | VFP = ValueForcePair(nullptr, true); | |||
| 520 | } | |||
| 521 | ||||
| 522 | SlotIndex SplitEditor::buildSingleSubRegCopy(Register FromReg, Register ToReg, | |||
| 523 | MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, | |||
| 524 | unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def) { | |||
| 525 | const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY); | |||
| 526 | bool FirstCopy = !Def.isValid(); | |||
| 527 | MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc) | |||
| 528 | .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy) | |||
| 529 | | getInternalReadRegState(!FirstCopy), SubIdx) | |||
| 530 | .addReg(FromReg, 0, SubIdx); | |||
| 531 | ||||
| 532 | BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); | |||
| 533 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
| 534 | if (FirstCopy) { | |||
| 535 | Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot(); | |||
| 536 | } else { | |||
| 537 | CopyMI->bundleWithPred(); | |||
| 538 | } | |||
| 539 | LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx); | |||
| 540 | DestLI.refineSubRanges(Allocator, LaneMask, | |||
| 541 | [Def, &Allocator](LiveInterval::SubRange &SR) { | |||
| 542 | SR.createDeadDef(Def, Allocator); | |||
| 543 | }, | |||
| 544 | Indexes, TRI); | |||
| 545 | return Def; | |||
| 546 | } | |||
| 547 | ||||
| 548 | SlotIndex SplitEditor::buildCopy(Register FromReg, Register ToReg, | |||
| 549 | LaneBitmask LaneMask, MachineBasicBlock &MBB, | |||
| 550 | MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) { | |||
| 551 | const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY); | |||
| 552 | if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) { | |||
| 553 | // The full vreg is copied. | |||
| 554 | MachineInstr *CopyMI = | |||
| 555 | BuildMI(MBB, InsertBefore, DebugLoc(), Desc, ToReg).addReg(FromReg); | |||
| 556 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
| 557 | return Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot(); | |||
| 558 | } | |||
| 559 | ||||
| 560 | // Only a subset of lanes needs to be copied. The following is a simple | |||
| 561 | // heuristic to construct a sequence of COPYs. We could add a target | |||
| 562 | // specific callback if this turns out to be suboptimal. | |||
| 563 | LiveInterval &DestLI = LIS.getInterval(Edit->get(RegIdx)); | |||
| 564 | ||||
| 565 | // First pass: Try to find a perfectly matching subregister index. If none | |||
| 566 | // exists find the one covering the most lanemask bits. | |||
| 567 | const TargetRegisterClass *RC = MRI.getRegClass(FromReg); | |||
| 568 | assert(RC == MRI.getRegClass(ToReg) && "Should have same reg class")((void)0); | |||
| 569 | ||||
| 570 | SmallVector<unsigned, 8> Indexes; | |||
| 571 | ||||
| 572 | // Abort if we cannot possibly implement the COPY with the given indexes. | |||
| 573 | if (!TRI.getCoveringSubRegIndexes(MRI, RC, LaneMask, Indexes)) | |||
| 574 | report_fatal_error("Impossible to implement partial COPY"); | |||
| 575 | ||||
| 576 | SlotIndex Def; | |||
| 577 | for (unsigned BestIdx : Indexes) { | |||
| 578 | Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx, | |||
| 579 | DestLI, Late, Def); | |||
| 580 | } | |||
| 581 | ||||
| 582 | return Def; | |||
| 583 | } | |||
| 584 | ||||
| 585 | VNInfo *SplitEditor::defFromParent(unsigned RegIdx, | |||
| 586 | VNInfo *ParentVNI, | |||
| 587 | SlotIndex UseIdx, | |||
| 588 | MachineBasicBlock &MBB, | |||
| 589 | MachineBasicBlock::iterator I) { | |||
| 590 | SlotIndex Def; | |||
| 591 | LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); | |||
| 592 | ||||
| 593 | // We may be trying to avoid interference that ends at a deleted instruction, | |||
| 594 | // so always begin RegIdx 0 early and all others late. | |||
| 595 | bool Late = RegIdx != 0; | |||
| 596 | ||||
| 597 | // Attempt cheap-as-a-copy rematerialization. | |||
| 598 | unsigned Original = VRM.getOriginal(Edit->get(RegIdx)); | |||
| 599 | LiveInterval &OrigLI = LIS.getInterval(Original); | |||
| 600 | VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx); | |||
| 601 | ||||
| 602 | Register Reg = LI->reg(); | |||
| 603 | bool DidRemat = false; | |||
| 604 | if (OrigVNI) { | |||
| 605 | LiveRangeEdit::Remat RM(ParentVNI); | |||
| 606 | RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def); | |||
| 607 | if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) { | |||
| 608 | Def = Edit->rematerializeAt(MBB, I, Reg, RM, TRI, Late); | |||
| 609 | ++NumRemats; | |||
| 610 | DidRemat = true; | |||
| 611 | } | |||
| 612 | } | |||
| 613 | if (!DidRemat) { | |||
| 614 | LaneBitmask LaneMask; | |||
| 615 | if (OrigLI.hasSubRanges()) { | |||
| 616 | LaneMask = LaneBitmask::getNone(); | |||
| 617 | for (LiveInterval::SubRange &S : OrigLI.subranges()) { | |||
| 618 | if (S.liveAt(UseIdx)) | |||
| 619 | LaneMask |= S.LaneMask; | |||
| 620 | } | |||
| 621 | } else { | |||
| 622 | LaneMask = LaneBitmask::getAll(); | |||
| 623 | } | |||
| 624 | ||||
| 625 | if (LaneMask.none()) { | |||
| 626 | const MCInstrDesc &Desc = TII.get(TargetOpcode::IMPLICIT_DEF); | |||
| 627 | MachineInstr *ImplicitDef = BuildMI(MBB, I, DebugLoc(), Desc, Reg); | |||
| 628 | SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
| 629 | Def = Indexes.insertMachineInstrInMaps(*ImplicitDef, Late).getRegSlot(); | |||
| 630 | } else { | |||
| 631 | ++NumCopies; | |||
| 632 | Def = buildCopy(Edit->getReg(), Reg, LaneMask, MBB, I, Late, RegIdx); | |||
| 633 | } | |||
| 634 | } | |||
| 635 | ||||
| 636 | // Define the value in Reg. | |||
| 637 | return defValue(RegIdx, ParentVNI, Def, false); | |||
| 638 | } | |||
| 639 | ||||
| 640 | /// Create a new virtual register and live interval. | |||
| 641 | unsigned SplitEditor::openIntv() { | |||
| 642 | // Create the complement as index 0. | |||
| 643 | if (Edit->empty()) | |||
| 644 | Edit->createEmptyInterval(); | |||
| 645 | ||||
| 646 | // Create the open interval. | |||
| 647 | OpenIdx = Edit->size(); | |||
| 648 | Edit->createEmptyInterval(); | |||
| 649 | return OpenIdx; | |||
| 650 | } | |||
| 651 | ||||
| 652 | void SplitEditor::selectIntv(unsigned Idx) { | |||
| 653 | assert(Idx != 0 && "Cannot select the complement interval")((void)0); | |||
| 654 | assert(Idx < Edit->size() && "Can only select previously opened interval")((void)0); | |||
| 655 | LLVM_DEBUG(dbgs() << " selectIntv " << OpenIdx << " -> " << Idx << '\n')do { } while (false); | |||
| 656 | OpenIdx = Idx; | |||
| 657 | } | |||
| 658 | ||||
| 659 | SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) { | |||
| 660 | assert(OpenIdx && "openIntv not called before enterIntvBefore")((void)0); | |||
| 661 | LLVM_DEBUG(dbgs() << " enterIntvBefore " << Idx)do { } while (false); | |||
| 662 | Idx = Idx.getBaseIndex(); | |||
| 663 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); | |||
| 664 | if (!ParentVNI) { | |||
| 665 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
| 666 | return Idx; | |||
| 667 | } | |||
| 668 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n')do { } while (false); | |||
| 669 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); | |||
| 670 | assert(MI && "enterIntvBefore called with invalid index")((void)0); | |||
| 671 | ||||
| 672 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI); | |||
| 673 | return VNI->def; | |||
| 674 | } | |||
| 675 | ||||
| 676 | SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { | |||
| 677 | assert(OpenIdx && "openIntv not called before enterIntvAfter")((void)0); | |||
| 678 | LLVM_DEBUG(dbgs() << " enterIntvAfter " << Idx)do { } while (false); | |||
| 679 | Idx = Idx.getBoundaryIndex(); | |||
| 680 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); | |||
| 681 | if (!ParentVNI) { | |||
| 682 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
| 683 | return Idx; | |||
| 684 | } | |||
| 685 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n')do { } while (false); | |||
| 686 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); | |||
| 687 | assert(MI && "enterIntvAfter called with invalid index")((void)0); | |||
| 688 | ||||
| 689 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), | |||
| 690 | std::next(MachineBasicBlock::iterator(MI))); | |||
| 691 | return VNI->def; | |||
| 692 | } | |||
| 693 | ||||
| 694 | SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { | |||
| 695 | assert(OpenIdx && "openIntv not called before enterIntvAtEnd")((void)0); | |||
| 696 | SlotIndex End = LIS.getMBBEndIdx(&MBB); | |||
| 697 | SlotIndex Last = End.getPrevSlot(); | |||
| 698 | LLVM_DEBUG(dbgs() << " enterIntvAtEnd " << printMBBReference(MBB) << ", "do { } while (false) | |||
| 699 | << Last)do { } while (false); | |||
| 700 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Last); | |||
| 701 | if (!ParentVNI) { | |||
| 702 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
| 703 | return End; | |||
| 704 | } | |||
| 705 | SlotIndex LSP = SA.getLastSplitPoint(&MBB); | |||
| 706 | if (LSP < Last) { | |||
| 707 | // It could be that the use after LSP is a def, and thus the ParentVNI | |||
| 708 | // just selected starts at that def. For this case to exist, the def | |||
| 709 | // must be part of a tied def/use pair (as otherwise we'd have split | |||
| 710 | // distinct live ranges into individual live intervals), and thus we | |||
| 711 | // can insert the def into the VNI of the use and the tied def/use | |||
| 712 | // pair can live in the resulting interval. | |||
| 713 | Last = LSP; | |||
| 714 | ParentVNI = Edit->getParent().getVNInfoAt(Last); | |||
| 715 | if (!ParentVNI) { | |||
| 716 | // undef use --> undef tied def | |||
| 717 | LLVM_DEBUG(dbgs() << ": tied use not live\n")do { } while (false); | |||
| 718 | return End; | |||
| 719 | } | |||
| 720 | } | |||
| 721 | ||||
| 722 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id)do { } while (false); | |||
| 723 | VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, | |||
| 724 | SA.getLastSplitPointIter(&MBB)); | |||
| 725 | RegAssign.insert(VNI->def, End, OpenIdx); | |||
| 726 | LLVM_DEBUG(dump())do { } while (false); | |||
| 727 | return VNI->def; | |||
| 728 | } | |||
| 729 | ||||
| 730 | /// useIntv - indicate that all instructions in MBB should use OpenLI. | |||
| 731 | void SplitEditor::useIntv(const MachineBasicBlock &MBB) { | |||
| 732 | useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB)); | |||
| 733 | } | |||
| 734 | ||||
| 735 | void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) { | |||
| 736 | assert(OpenIdx && "openIntv not called before useIntv")((void)0); | |||
| 737 | LLVM_DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):")do { } while (false); | |||
| 738 | RegAssign.insert(Start, End, OpenIdx); | |||
| 739 | LLVM_DEBUG(dump())do { } while (false); | |||
| 740 | } | |||
| 741 | ||||
| 742 | SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { | |||
| 743 | assert(OpenIdx && "openIntv not called before leaveIntvAfter")((void)0); | |||
| 744 | LLVM_DEBUG(dbgs() << " leaveIntvAfter " << Idx)do { } while (false); | |||
| 745 | ||||
| 746 | // The interval must be live beyond the instruction at Idx. | |||
| 747 | SlotIndex Boundary = Idx.getBoundaryIndex(); | |||
| 748 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); | |||
| 749 | if (!ParentVNI) { | |||
| 750 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
| 751 | return Boundary.getNextSlot(); | |||
| 752 | } | |||
| 753 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n')do { } while (false); | |||
| 754 | MachineInstr *MI = LIS.getInstructionFromIndex(Boundary); | |||
| 755 | assert(MI && "No instruction at index")((void)0); | |||
| 756 | ||||
| 757 | // In spill mode, make live ranges as short as possible by inserting the copy | |||
| 758 | // before MI. This is only possible if that instruction doesn't redefine the | |||
| 759 | // value. The inserted COPY is not a kill, and we don't need to recompute | |||
| 760 | // the source live range. The spiller also won't try to hoist this copy. | |||
| 761 | if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && | |||
| 762 | MI->readsVirtualRegister(Edit->getReg())) { | |||
| 763 | forceRecompute(0, *ParentVNI); | |||
| 764 | defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); | |||
| 765 | return Idx; | |||
| 766 | } | |||
| 767 | ||||
| 768 | VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), | |||
| 769 | std::next(MachineBasicBlock::iterator(MI))); | |||
| 770 | return VNI->def; | |||
| 771 | } | |||
| 772 | ||||
| 773 | SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) { | |||
| 774 | assert(OpenIdx && "openIntv not called before leaveIntvBefore")((void)0); | |||
| 775 | LLVM_DEBUG(dbgs() << " leaveIntvBefore " << Idx)do { } while (false); | |||
| 776 | ||||
| 777 | // The interval must be live into the instruction at Idx. | |||
| 778 | Idx = Idx.getBaseIndex(); | |||
| 779 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); | |||
| 780 | if (!ParentVNI) { | |||
| 781 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
| 782 | return Idx.getNextSlot(); | |||
| 783 | } | |||
| 784 | LLVM_DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n')do { } while (false); | |||
| 785 | ||||
| 786 | MachineInstr *MI = LIS.getInstructionFromIndex(Idx); | |||
| 787 | assert(MI && "No instruction at index")((void)0); | |||
| 788 | VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); | |||
| 789 | return VNI->def; | |||
| 790 | } | |||
| 791 | ||||
| 792 | SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { | |||
| 793 | assert(OpenIdx && "openIntv not called before leaveIntvAtTop")((void)0); | |||
| 794 | SlotIndex Start = LIS.getMBBStartIdx(&MBB); | |||
| 795 | LLVM_DEBUG(dbgs() << " leaveIntvAtTop " << printMBBReference(MBB) << ", "do { } while (false) | |||
| 796 | << Start)do { } while (false); | |||
| 797 | ||||
| 798 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); | |||
| 799 | if (!ParentVNI) { | |||
| 800 | LLVM_DEBUG(dbgs() << ": not live\n")do { } while (false); | |||
| 801 | return Start; | |||
| 802 | } | |||
| 803 | ||||
| 804 | VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB, | |||
| 805 | MBB.SkipPHIsLabelsAndDebug(MBB.begin())); | |||
| 806 | RegAssign.insert(Start, VNI->def, OpenIdx); | |||
| 807 | LLVM_DEBUG(dump())do { } while (false); | |||
| 808 | return VNI->def; | |||
| 809 | } | |||
| 810 | ||||
| 811 | static bool hasTiedUseOf(MachineInstr &MI, unsigned Reg) { | |||
| 812 | return any_of(MI.defs(), [Reg](const MachineOperand &MO) { | |||
| 813 | return MO.isReg() && MO.isTied() && MO.getReg() == Reg; | |||
| 814 | }); | |||
| 815 | } | |||
| 816 | ||||
| 817 | void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { | |||
| 818 | assert(OpenIdx && "openIntv not called before overlapIntv")((void)0); | |||
| 819 | const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); | |||
| 820 | assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) &&((void)0) | |||
| 821 | "Parent changes value in extended range")((void)0); | |||
| 822 | assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&((void)0) | |||
| 823 | "Range cannot span basic blocks")((void)0); | |||
| 824 | ||||
| 825 | // The complement interval will be extended as needed by LICalc.extend(). | |||
| 826 | if (ParentVNI) | |||
| 827 | forceRecompute(0, *ParentVNI); | |||
| 828 | ||||
| 829 | // If the last use is tied to a def, we can't mark it as live for the | |||
| 830 | // interval which includes only the use. That would cause the tied pair | |||
| 831 | // to end up in two different intervals. | |||
| 832 | if (auto *MI = LIS.getInstructionFromIndex(End)) | |||
| 833 | if (hasTiedUseOf(*MI, Edit->getReg())) { | |||
| 834 | LLVM_DEBUG(dbgs() << "skip overlap due to tied def at end\n")do { } while (false); | |||
| 835 | return; | |||
| 836 | } | |||
| 837 | ||||
| 838 | LLVM_DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):")do { } while (false); | |||
| 839 | RegAssign.insert(Start, End, OpenIdx); | |||
| 840 | LLVM_DEBUG(dump())do { } while (false); | |||
| 841 | } | |||
| 842 | ||||
| 843 | //===----------------------------------------------------------------------===// | |||
| 844 | // Spill modes | |||
| 845 | //===----------------------------------------------------------------------===// | |||
| 846 | ||||
| 847 | void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) { | |||
| 848 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); | |||
| 849 | LLVM_DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n")do { } while (false); | |||
| 850 | RegAssignMap::iterator AssignI; | |||
| 851 | AssignI.setMap(RegAssign); | |||
| 852 | ||||
| 853 | for (const VNInfo *C : Copies) { | |||
| 854 | SlotIndex Def = C->def; | |||
| 855 | MachineInstr *MI = LIS.getInstructionFromIndex(Def); | |||
| 856 | assert(MI && "No instruction for back-copy")((void)0); | |||
| 857 | ||||
| 858 | MachineBasicBlock *MBB = MI->getParent(); | |||
| 859 | MachineBasicBlock::iterator MBBI(MI); | |||
| 860 | bool AtBegin; | |||
| 861 | do AtBegin = MBBI == MBB->begin(); | |||
| 862 | while (!AtBegin && (--MBBI)->isDebugOrPseudoInstr()); | |||
| 863 | ||||
| 864 | LLVM_DEBUG(dbgs() << "Removing " << Def << '\t' << *MI)do { } while (false); | |||
| 865 | LIS.removeVRegDefAt(*LI, Def); | |||
| 866 | LIS.RemoveMachineInstrFromMaps(*MI); | |||
| 867 | MI->eraseFromParent(); | |||
| 868 | ||||
| 869 | // Adjust RegAssign if a register assignment is killed at Def. We want to | |||
| 870 | // avoid calculating the live range of the source register if possible. | |||
| 871 | AssignI.find(Def.getPrevSlot()); | |||
| 872 | if (!AssignI.valid() || AssignI.start() >= Def) | |||
| 873 | continue; | |||
| 874 | // If MI doesn't kill the assigned register, just leave it. | |||
| 875 | if (AssignI.stop() != Def) | |||
| 876 | continue; | |||
| 877 | unsigned RegIdx = AssignI.value(); | |||
| 878 | // We could hoist back-copy right after another back-copy. As a result | |||
| 879 | // MMBI points to copy instruction which is actually dead now. | |||
| 880 | // We cannot set its stop to MBBI which will be the same as start and | |||
| 881 | // interval does not support that. | |||
| 882 | SlotIndex Kill = | |||
| 883 | AtBegin ? SlotIndex() : LIS.getInstructionIndex(*MBBI).getRegSlot(); | |||
| 884 | if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg()) || | |||
| 885 | Kill <= AssignI.start()) { | |||
| 886 | LLVM_DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdxdo { } while (false) | |||
| 887 | << '\n')do { } while (false); | |||
| 888 | forceRecompute(RegIdx, *Edit->getParent().getVNInfoAt(Def)); | |||
| 889 | } else { | |||
| 890 | LLVM_DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI)do { } while (false); | |||
| 891 | AssignI.setStop(Kill); | |||
| 892 | } | |||
| 893 | } | |||
| 894 | } | |||
| 895 | ||||
| 896 | MachineBasicBlock* | |||
| 897 | SplitEditor::findShallowDominator(MachineBasicBlock *MBB, | |||
| 898 | MachineBasicBlock *DefMBB) { | |||
| 899 | if (MBB == DefMBB) | |||
| 900 | return MBB; | |||
| 901 | assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def.")((void)0); | |||
| 902 | ||||
| 903 | const MachineLoopInfo &Loops = SA.Loops; | |||
| 904 | const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB); | |||
| 905 | MachineDomTreeNode *DefDomNode = MDT[DefMBB]; | |||
| 906 | ||||
| 907 | // Best candidate so far. | |||
| 908 | MachineBasicBlock *BestMBB = MBB; | |||
| 909 | unsigned BestDepth = std::numeric_limits<unsigned>::max(); | |||
| 910 | ||||
| 911 | while (true) { | |||
| 912 | const MachineLoop *Loop = Loops.getLoopFor(MBB); | |||
| 913 | ||||
| 914 | // MBB isn't in a loop, it doesn't get any better. All dominators have a | |||
| 915 | // higher frequency by definition. | |||
| 916 | if (!Loop) { | |||
| 917 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)do { } while (false) | |||
| 918 | << " dominates " << printMBBReference(*MBB)do { } while (false) | |||
| 919 | << " at depth 0\n")do { } while (false); | |||
| 920 | return MBB; | |||
| 921 | } | |||
| 922 | ||||
| 923 | // We'll never be able to exit the DefLoop. | |||
| 924 | if (Loop == DefLoop) { | |||
| 925 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)do { } while (false) | |||
| 926 | << " dominates " << printMBBReference(*MBB)do { } while (false) | |||
| 927 | << " in the same loop\n")do { } while (false); | |||
| 928 | return MBB; | |||
| 929 | } | |||
| 930 | ||||
| 931 | // Least busy dominator seen so far. | |||
| 932 | unsigned Depth = Loop->getLoopDepth(); | |||
| 933 | if (Depth < BestDepth) { | |||
| 934 | BestMBB = MBB; | |||
| 935 | BestDepth = Depth; | |||
| 936 | LLVM_DEBUG(dbgs() << "Def in " << printMBBReference(*DefMBB)do { } while (false) | |||
| 937 | << " dominates " << printMBBReference(*MBB)do { } while (false) | |||
| 938 | << " at depth " << Depth << '\n')do { } while (false); | |||
| 939 | } | |||
| 940 | ||||
| 941 | // Leave loop by going to the immediate dominator of the loop header. | |||
| 942 | // This is a bigger stride than simply walking up the dominator tree. | |||
| 943 | MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); | |||
| 944 | ||||
| 945 | // Too far up the dominator tree? | |||
| 946 | if (!IDom || !MDT.dominates(DefDomNode, IDom)) | |||
| 947 | return BestMBB; | |||
| 948 | ||||
| 949 | MBB = IDom->getBlock(); | |||
| 950 | } | |||
| 951 | } | |||
| 952 | ||||
| 953 | void SplitEditor::computeRedundantBackCopies( | |||
| 954 | DenseSet<unsigned> &NotToHoistSet, SmallVectorImpl<VNInfo *> &BackCopies) { | |||
| 955 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); | |||
| 956 | LiveInterval *Parent = &Edit->getParent(); | |||
| 957 | SmallVector<SmallPtrSet<VNInfo *, 8>, 8> EqualVNs(Parent->getNumValNums()); | |||
| 958 | SmallPtrSet<VNInfo *, 8> DominatedVNIs; | |||
| 959 | ||||
| 960 | // Aggregate VNIs having the same value as ParentVNI. | |||
| 961 | for (VNInfo *VNI : LI->valnos) { | |||
| 962 | if (VNI->isUnused()) | |||
| 963 | continue; | |||
| 964 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); | |||
| 965 | EqualVNs[ParentVNI->id].insert(VNI); | |||
| 966 | } | |||
| 967 | ||||
| 968 | // For VNI aggregation of each ParentVNI, collect dominated, i.e., | |||
| 969 | // redundant VNIs to BackCopies. | |||
| 970 | for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { | |||
| 971 | VNInfo *ParentVNI = Parent->getValNumInfo(i); | |||
| 972 | if (!NotToHoistSet.count(ParentVNI->id)) | |||
| 973 | continue; | |||
| 974 | SmallPtrSetIterator<VNInfo *> It1 = EqualVNs[ParentVNI->id].begin(); | |||
| 975 | SmallPtrSetIterator<VNInfo *> It2 = It1; | |||
| 976 | for (; It1 != EqualVNs[ParentVNI->id].end(); ++It1) { | |||
| 977 | It2 = It1; | |||
| 978 | for (++It2; It2 != EqualVNs[ParentVNI->id].end(); ++It2) { | |||
| 979 | if (DominatedVNIs.count(*It1) || DominatedVNIs.count(*It2)) | |||
| 980 | continue; | |||
| 981 | ||||
| 982 | MachineBasicBlock *MBB1 = LIS.getMBBFromIndex((*It1)->def); | |||
| 983 | MachineBasicBlock *MBB2 = LIS.getMBBFromIndex((*It2)->def); | |||
| 984 | if (MBB1 == MBB2) { | |||
| 985 | DominatedVNIs.insert((*It1)->def < (*It2)->def ? (*It2) : (*It1)); | |||
| 986 | } else if (MDT.dominates(MBB1, MBB2)) { | |||
| 987 | DominatedVNIs.insert(*It2); | |||
| 988 | } else if (MDT.dominates(MBB2, MBB1)) { | |||
| 989 | DominatedVNIs.insert(*It1); | |||
| 990 | } | |||
| 991 | } | |||
| 992 | } | |||
| 993 | if (!DominatedVNIs.empty()) { | |||
| 994 | forceRecompute(0, *ParentVNI); | |||
| 995 | append_range(BackCopies, DominatedVNIs); | |||
| 996 | DominatedVNIs.clear(); | |||
| 997 | } | |||
| 998 | } | |||
| 999 | } | |||
| 1000 | ||||
| 1001 | /// For SM_Size mode, find a common dominator for all the back-copies for | |||
| 1002 | /// the same ParentVNI and hoist the backcopies to the dominator BB. | |||
| 1003 | /// For SM_Speed mode, if the common dominator is hot and it is not beneficial | |||
| 1004 | /// to do the hoisting, simply remove the dominated backcopies for the same | |||
| 1005 | /// ParentVNI. | |||
| 1006 | void SplitEditor::hoistCopies() { | |||
| 1007 | // Get the complement interval, always RegIdx 0. | |||
| 1008 | LiveInterval *LI = &LIS.getInterval(Edit->get(0)); | |||
| 1009 | LiveInterval *Parent = &Edit->getParent(); | |||
| 1010 | ||||
| 1011 | // Track the nearest common dominator for all back-copies for each ParentVNI, | |||
| 1012 | // indexed by ParentVNI->id. | |||
| 1013 | using DomPair = std::pair<MachineBasicBlock *, SlotIndex>; | |||
| 1014 | SmallVector<DomPair, 8> NearestDom(Parent->getNumValNums()); | |||
| 1015 | // The total cost of all the back-copies for each ParentVNI. | |||
| 1016 | SmallVector<BlockFrequency, 8> Costs(Parent->getNumValNums()); | |||
| 1017 | // The ParentVNI->id set for which hoisting back-copies are not beneficial | |||
| 1018 | // for Speed. | |||
| 1019 | DenseSet<unsigned> NotToHoistSet; | |||
| 1020 | ||||
| 1021 | // Find the nearest common dominator for parent values with multiple | |||
| 1022 | // back-copies. If a single back-copy dominates, put it in DomPair.second. | |||
| 1023 | for (VNInfo *VNI : LI->valnos) { | |||
| 1024 | if (VNI->isUnused()) | |||
| 1025 | continue; | |||
| 1026 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); | |||
| 1027 | assert(ParentVNI && "Parent not live at complement def")((void)0); | |||
| 1028 | ||||
| 1029 | // Don't hoist remats. The complement is probably going to disappear | |||
| 1030 | // completely anyway. | |||
| 1031 | if (Edit->didRematerialize(ParentVNI)) | |||
| 1032 | continue; | |||
| 1033 | ||||
| 1034 | MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); | |||
| 1035 | ||||
| 1036 | DomPair &Dom = NearestDom[ParentVNI->id]; | |||
| 1037 | ||||
| 1038 | // Keep directly defined parent values. This is either a PHI or an | |||
| 1039 | // instruction in the complement range. All other copies of ParentVNI | |||
| 1040 | // should be eliminated. | |||
| 1041 | if (VNI->def == ParentVNI->def) { | |||
| 1042 | LLVM_DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n')do { } while (false); | |||
| 1043 | Dom = DomPair(ValMBB, VNI->def); | |||
| 1044 | continue; | |||
| 1045 | } | |||
| 1046 | // Skip the singly mapped values. There is nothing to gain from hoisting a | |||
| 1047 | // single back-copy. | |||
| 1048 | if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { | |||
| 1049 | LLVM_DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n')do { } while (false); | |||
| 1050 | continue; | |||
| 1051 | } | |||
| 1052 | ||||
| 1053 | if (!Dom.first) { | |||
| 1054 | // First time we see ParentVNI. VNI dominates itself. | |||
| 1055 | Dom = DomPair(ValMBB, VNI->def); | |||
| 1056 | } else if (Dom.first == ValMBB) { | |||
| 1057 | // Two defs in the same block. Pick the earlier def. | |||
| 1058 | if (!Dom.second.isValid() || VNI->def < Dom.second) | |||
| 1059 | Dom.second = VNI->def; | |||
| 1060 | } else { | |||
| 1061 | // Different basic blocks. Check if one dominates. | |||
| 1062 | MachineBasicBlock *Near = | |||
| 1063 | MDT.findNearestCommonDominator(Dom.first, ValMBB); | |||
| 1064 | if (Near == ValMBB) | |||
| 1065 | // Def ValMBB dominates. | |||
| 1066 | Dom = DomPair(ValMBB, VNI->def); | |||
| 1067 | else if (Near != Dom.first) | |||
| 1068 | // None dominate. Hoist to common dominator, need new def. | |||
| 1069 | Dom = DomPair(Near, SlotIndex()); | |||
| 1070 | Costs[ParentVNI->id] += MBFI.getBlockFreq(ValMBB); | |||
| 1071 | } | |||
| 1072 | ||||
| 1073 | LLVM_DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@'do { } while (false) | |||
| 1074 | << VNI->def << " for parent " << ParentVNI->id << '@'do { } while (false) | |||
| 1075 | << ParentVNI->def << " hoist to "do { } while (false) | |||
| 1076 | << printMBBReference(*Dom.first) << ' ' << Dom.seconddo { } while (false) | |||
| 1077 | << '\n')do { } while (false); | |||
| 1078 | } | |||
| 1079 | ||||
| 1080 | // Insert the hoisted copies. | |||
| 1081 | for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { | |||
| 1082 | DomPair &Dom = NearestDom[i]; | |||
| 1083 | if (!Dom.first || Dom.second.isValid()) | |||
| 1084 | continue; | |||
| 1085 | // This value needs a hoisted copy inserted at the end of Dom.first. | |||
| 1086 | VNInfo *ParentVNI = Parent->getValNumInfo(i); | |||
| 1087 | MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); | |||
| 1088 | // Get a less loopy dominator than Dom.first. | |||
| 1089 | Dom.first = findShallowDominator(Dom.first, DefMBB); | |||
| 1090 | if (SpillMode == SM_Speed && | |||
| 1091 | MBFI.getBlockFreq(Dom.first) > Costs[ParentVNI->id]) { | |||
| 1092 | NotToHoistSet.insert(ParentVNI->id); | |||
| 1093 | continue; | |||
| 1094 | } | |||
| 1095 | SlotIndex LSP = SA.getLastSplitPoint(Dom.first); | |||
| 1096 | if (LSP <= ParentVNI->def) { | |||
| 1097 | NotToHoistSet.insert(ParentVNI->id); | |||
| 1098 | continue; | |||
| 1099 | } | |||
| 1100 | Dom.second = defFromParent(0, ParentVNI, LSP, *Dom.first, | |||
| 1101 | SA.getLastSplitPointIter(Dom.first))->def; | |||
| 1102 | } | |||
| 1103 | ||||
| 1104 | // Remove redundant back-copies that are now known to be dominated by another | |||
| 1105 | // def with the same value. | |||
| 1106 | SmallVector<VNInfo*, 8> BackCopies; | |||
| 1107 | for (VNInfo *VNI : LI->valnos) { | |||
| 1108 | if (VNI->isUnused()) | |||
| 1109 | continue; | |||
| 1110 | VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); | |||
| 1111 | const DomPair &Dom = NearestDom[ParentVNI->id]; | |||
| 1112 | if (!Dom.first || Dom.second == VNI->def || | |||
| 1113 | NotToHoistSet.count(ParentVNI->id)) | |||
| 1114 | continue; | |||
| 1115 | BackCopies.push_back(VNI); | |||
| 1116 | forceRecompute(0, *ParentVNI); | |||
| 1117 | } | |||
| 1118 | ||||
| 1119 | // If it is not beneficial to hoist all the BackCopies, simply remove | |||
| 1120 | // redundant BackCopies in speed mode. | |||
| 1121 | if (SpillMode == SM_Speed && !NotToHoistSet.empty()) | |||
| 1122 | computeRedundantBackCopies(NotToHoistSet, BackCopies); | |||
| 1123 | ||||
| 1124 | removeBackCopies(BackCopies); | |||
| 1125 | } | |||
| 1126 | ||||
| 1127 | /// transferValues - Transfer all possible values to the new live ranges. | |||
| 1128 | /// Values that were rematerialized are left alone, they need LICalc.extend(). | |||
| 1129 | bool SplitEditor::transferValues() { | |||
| 1130 | bool Skipped = false; | |||
| 1131 | RegAssignMap::const_iterator AssignI = RegAssign.begin(); | |||
| 1132 | for (const LiveRange::Segment &S : Edit->getParent()) { | |||
| 1133 | LLVM_DEBUG(dbgs() << " blit " << S << ':')do { } while (false); | |||
| 1134 | VNInfo *ParentVNI = S.valno; | |||
| 1135 | // RegAssign has holes where RegIdx 0 should be used. | |||
| 1136 | SlotIndex Start = S.start; | |||
| 1137 | AssignI.advanceTo(Start); | |||
| 1138 | do { | |||
| 1139 | unsigned RegIdx; | |||
| 1140 | SlotIndex End = S.end; | |||
| 1141 | if (!AssignI.valid()) { | |||
| 1142 | RegIdx = 0; | |||
| 1143 | } else if (AssignI.start() <= Start) { | |||
| 1144 | RegIdx = AssignI.value(); | |||
| 1145 | if (AssignI.stop() < End) { | |||
| 1146 | End = AssignI.stop(); | |||
| 1147 | ++AssignI; | |||
| 1148 | } | |||
| 1149 | } else { | |||
| 1150 | RegIdx = 0; | |||
| 1151 | End = std::min(End, AssignI.start()); | |||
| 1152 | } | |||
| 1153 | ||||
| 1154 | // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. | |||
| 1155 | LLVM_DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx << '('do { } while (false) | |||
| 1156 | << printReg(Edit->get(RegIdx)) << ')')do { } while (false); | |||
| 1157 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); | |||
| 1158 | ||||
| 1159 | // Check for a simply defined value that can be blitted directly. | |||
| 1160 | ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); | |||
| 1161 | if (VNInfo *VNI = VFP.getPointer()) { | |||
| 1162 | LLVM_DEBUG(dbgs() << ':' << VNI->id)do { } while (false); | |||
| 1163 | LI.addSegment(LiveInterval::Segment(Start, End, VNI)); | |||
| 1164 | Start = End; | |||
| 1165 | continue; | |||
| 1166 | } | |||
| 1167 | ||||
| 1168 | // Skip values with forced recomputation. | |||
| 1169 | if (VFP.getInt()) { | |||
| 1170 | LLVM_DEBUG(dbgs() << "(recalc)")do { } while (false); | |||
| 1171 | Skipped = true; | |||
| 1172 | Start = End; | |||
| 1173 | continue; | |||
| 1174 | } | |||
| 1175 | ||||
| 1176 | LiveIntervalCalc &LIC = getLICalc(RegIdx); | |||
| 1177 | ||||
| 1178 | // This value has multiple defs in RegIdx, but it wasn't rematerialized, | |||
| 1179 | // so the live range is accurate. Add live-in blocks in [Start;End) to the | |||
| 1180 | // LiveInBlocks. | |||
| 1181 | MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); | |||
| 1182 | SlotIndex BlockStart, BlockEnd; | |||
| 1183 | std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB); | |||
| 1184 | ||||
| 1185 | // The first block may be live-in, or it may have its own def. | |||
| 1186 | if (Start != BlockStart) { | |||
| 1187 | VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End)); | |||
| 1188 | assert(VNI && "Missing def for complex mapped value")((void)0); | |||
| 1189 | LLVM_DEBUG(dbgs() << ':' << VNI->id << "*" << printMBBReference(*MBB))do { } while (false); | |||
| 1190 | // MBB has its own def. Is it also live-out? | |||
| 1191 | if (BlockEnd <= End) | |||
| 1192 | LIC.setLiveOutValue(&*MBB, VNI); | |||
| 1193 | ||||
| 1194 | // Skip to the next block for live-in. | |||
| 1195 | ++MBB; | |||
| 1196 | BlockStart = BlockEnd; | |||
| 1197 | } | |||
| 1198 | ||||
| 1199 | // Handle the live-in blocks covered by [Start;End). | |||
| 1200 | assert(Start <= BlockStart && "Expected live-in block")((void)0); | |||
| 1201 | while (BlockStart < End) { | |||
| 1202 | LLVM_DEBUG(dbgs() << ">" << printMBBReference(*MBB))do { } while (false); | |||
| 1203 | BlockEnd = LIS.getMBBEndIdx(&*MBB); | |||
| 1204 | if (BlockStart == ParentVNI->def) { | |||
| 1205 | // This block has the def of a parent PHI, so it isn't live-in. | |||
| 1206 | assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?")((void)0); | |||
| 1207 | VNInfo *VNI = LI.extendInBlock(BlockStart, std::min(BlockEnd, End)); | |||
| 1208 | assert(VNI && "Missing def for complex mapped parent PHI")((void)0); | |||
| 1209 | if (End >= BlockEnd) | |||
| 1210 | LIC.setLiveOutValue(&*MBB, VNI); // Live-out as well. | |||
| 1211 | } else { | |||
| 1212 | // This block needs a live-in value. The last block covered may not | |||
| 1213 | // be live-out. | |||
| 1214 | if (End < BlockEnd) | |||
| 1215 | LIC.addLiveInBlock(LI, MDT[&*MBB], End); | |||
| 1216 | else { | |||
| 1217 | // Live-through, and we don't know the value. | |||
| 1218 | LIC.addLiveInBlock(LI, MDT[&*MBB]); | |||
| 1219 | LIC.setLiveOutValue(&*MBB, nullptr); | |||
| 1220 | } | |||
| 1221 | } | |||
| 1222 | BlockStart = BlockEnd; | |||
| 1223 | ++MBB; | |||
| 1224 | } | |||
| 1225 | Start = End; | |||
| 1226 | } while (Start != S.end); | |||
| 1227 | LLVM_DEBUG(dbgs() << '\n')do { } while (false); | |||
| 1228 | } | |||
| 1229 | ||||
| 1230 | LICalc[0].calculateValues(); | |||
| 1231 | if (SpillMode) | |||
| 1232 | LICalc[1].calculateValues(); | |||
| 1233 | ||||
| 1234 | return Skipped; | |||
| 1235 | } | |||
| 1236 | ||||
| 1237 | static bool removeDeadSegment(SlotIndex Def, LiveRange &LR) { | |||
| 1238 | const LiveRange::Segment *Seg = LR.getSegmentContaining(Def); | |||
| 1239 | if (Seg == nullptr) | |||
| 1240 | return true; | |||
| 1241 | if (Seg->end != Def.getDeadSlot()) | |||
| 1242 | return false; | |||
| 1243 | // This is a dead PHI. Remove it. | |||
| 1244 | LR.removeSegment(*Seg, true); | |||
| 1245 | return true; | |||
| 1246 | } | |||
| 1247 | ||||
| 1248 | void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC, | |||
| 1249 | LiveRange &LR, LaneBitmask LM, | |||
| 1250 | ArrayRef<SlotIndex> Undefs) { | |||
| 1251 | for (MachineBasicBlock *P : B.predecessors()) { | |||
| 1252 | SlotIndex End = LIS.getMBBEndIdx(P); | |||
| 1253 | SlotIndex LastUse = End.getPrevSlot(); | |||
| 1254 | // The predecessor may not have a live-out value. That is OK, like an | |||
| 1255 | // undef PHI operand. | |||
| 1256 | LiveInterval &PLI = Edit->getParent(); | |||
| 1257 | // Need the cast because the inputs to ?: would otherwise be deemed | |||
| 1258 | // "incompatible": SubRange vs LiveInterval. | |||
| 1259 | LiveRange &PSR = !LM.all() ? getSubRangeForMaskExact(LM, PLI) | |||
| 1260 | : static_cast<LiveRange &>(PLI); | |||
| 1261 | if (PSR.liveAt(LastUse)) | |||
| 1262 | LIC.extend(LR, End, /*PhysReg=*/0, Undefs); | |||
| 1263 | } | |||
| 1264 | } | |||
| 1265 | ||||
| 1266 | void SplitEditor::extendPHIKillRanges() { | |||
| 1267 | // Extend live ranges to be live-out for successor PHI values. | |||
| 1268 | ||||
| 1269 | // Visit each PHI def slot in the parent live interval. If the def is dead, | |||
| 1270 | // remove it. Otherwise, extend the live interval to reach the end indexes | |||
| 1271 | // of all predecessor blocks. | |||
| 1272 | ||||
| 1273 | LiveInterval &ParentLI = Edit->getParent(); | |||
| 1274 | for (const VNInfo *V : ParentLI.valnos) { | |||
| 1275 | if (V->isUnused() || !V->isPHIDef()) | |||
| 1276 | continue; | |||
| 1277 | ||||
| 1278 | unsigned RegIdx = RegAssign.lookup(V->def); | |||
| 1279 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); | |||
| 1280 | LiveIntervalCalc &LIC = getLICalc(RegIdx); | |||
| 1281 | MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); | |||
| 1282 | if (!removeDeadSegment(V->def, LI)) | |||
| 1283 | extendPHIRange(B, LIC, LI, LaneBitmask::getAll(), /*Undefs=*/{}); | |||
| 1284 | } | |||
| 1285 | ||||
| 1286 | SmallVector<SlotIndex, 4> Undefs; | |||
| 1287 | LiveIntervalCalc SubLIC; | |||
| 1288 | ||||
| 1289 | for (LiveInterval::SubRange &PS : ParentLI.subranges()) { | |||
| 1290 | for (const VNInfo *V : PS.valnos) { | |||
| 1291 | if (V->isUnused() || !V->isPHIDef()) | |||
| 1292 | continue; | |||
| 1293 | unsigned RegIdx = RegAssign.lookup(V->def); | |||
| 1294 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); | |||
| 1295 | LiveInterval::SubRange &S = getSubRangeForMaskExact(PS.LaneMask, LI); | |||
| 1296 | if (removeDeadSegment(V->def, S)) | |||
| 1297 | continue; | |||
| 1298 | ||||
| 1299 | MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def); | |||
| 1300 | SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, | |||
| 1301 | &LIS.getVNInfoAllocator()); | |||
| 1302 | Undefs.clear(); | |||
| 1303 | LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes()); | |||
| 1304 | extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs); | |||
| 1305 | } | |||
| 1306 | } | |||
| 1307 | } | |||
| 1308 | ||||
| 1309 | /// rewriteAssigned - Rewrite all uses of Edit->getReg(). | |||
| 1310 | void SplitEditor::rewriteAssigned(bool ExtendRanges) { | |||
| 1311 | struct ExtPoint { | |||
| 1312 | ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N) | |||
| 1313 | : MO(O), RegIdx(R), Next(N) {} | |||
| 1314 | ||||
| 1315 | MachineOperand MO; | |||
| 1316 | unsigned RegIdx; | |||
| 1317 | SlotIndex Next; | |||
| 1318 | }; | |||
| 1319 | ||||
| 1320 | SmallVector<ExtPoint,4> ExtPoints; | |||
| 1321 | ||||
| 1322 | for (MachineOperand &MO : | |||
| 1323 | llvm::make_early_inc_range(MRI.reg_operands(Edit->getReg()))) { | |||
| 1324 | MachineInstr *MI = MO.getParent(); | |||
| 1325 | // LiveDebugVariables should have handled all DBG_VALUE instructions. | |||
| 1326 | if (MI->isDebugValue()) { | |||
| 1327 | LLVM_DEBUG(dbgs() << "Zapping " << *MI)do { } while (false); | |||
| 1328 | MO.setReg(0); | |||
| 1329 | continue; | |||
| 1330 | } | |||
| 1331 | ||||
| 1332 | // <undef> operands don't really read the register, so it doesn't matter | |||
| 1333 | // which register we choose. When the use operand is tied to a def, we must | |||
| 1334 | // use the same register as the def, so just do that always. | |||
| 1335 | SlotIndex Idx = LIS.getInstructionIndex(*MI); | |||
| 1336 | if (MO.isDef() || MO.isUndef()) | |||
| 1337 | Idx = Idx.getRegSlot(MO.isEarlyClobber()); | |||
| 1338 | ||||
| 1339 | // Rewrite to the mapped register at Idx. | |||
| 1340 | unsigned RegIdx = RegAssign.lookup(Idx); | |||
| 1341 | LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx)); | |||
| 1342 | MO.setReg(LI.reg()); | |||
| 1343 | LLVM_DEBUG(dbgs() << " rewr " << printMBBReference(*MI->getParent())do { } while (false) | |||
| 1344 | << '\t' << Idx << ':' << RegIdx << '\t' << *MI)do { } while (false); | |||
| 1345 | ||||
| 1346 | // Extend liveness to Idx if the instruction reads reg. | |||
| 1347 | if (!ExtendRanges || MO.isUndef()) | |||
| 1348 | continue; | |||
| 1349 | ||||
| 1350 | // Skip instructions that don't read Reg. | |||
| 1351 | if (MO.isDef()) { | |||
| 1352 | if (!MO.getSubReg() && !MO.isEarlyClobber()) | |||
| 1353 | continue; | |||
| 1354 | // We may want to extend a live range for a partial redef, or for a use | |||
| 1355 | // tied to an early clobber. | |||
| 1356 | Idx = Idx.getPrevSlot(); | |||
| 1357 | if (!Edit->getParent().liveAt(Idx)) | |||
| 1358 | continue; | |||
| 1359 | } else | |||
| 1360 | Idx = Idx.getRegSlot(true); | |||
| 1361 | ||||
| 1362 | SlotIndex Next = Idx.getNextSlot(); | |||
| 1363 | if (LI.hasSubRanges()) { | |||
| 1364 | // We have to delay extending subranges until we have seen all operands | |||
| 1365 | // defining the register. This is because a <def,read-undef> operand | |||
| 1366 | // will create an "undef" point, and we cannot extend any subranges | |||
| 1367 | // until all of them have been accounted for. | |||
| 1368 | if (MO.isUse()) | |||
| 1369 | ExtPoints.push_back(ExtPoint(MO, RegIdx, Next)); | |||
| 1370 | } else { | |||
| 1371 | LiveIntervalCalc &LIC = getLICalc(RegIdx); | |||
| 1372 | LIC.extend(LI, Next, 0, ArrayRef<SlotIndex>()); | |||
| 1373 | } | |||
| 1374 | } | |||
| 1375 | ||||
| 1376 | for (ExtPoint &EP : ExtPoints) { | |||
| 1377 | LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx)); | |||
| 1378 | assert(LI.hasSubRanges())((void)0); | |||
| 1379 | ||||
| 1380 | LiveIntervalCalc SubLIC; | |||
| 1381 | Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg(); | |||
| 1382 | LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub) | |||
| 1383 | : MRI.getMaxLaneMaskForVReg(Reg); | |||
| 1384 | for (LiveInterval::SubRange &S : LI.subranges()) { | |||
| 1385 | if ((S.LaneMask & LM).none()) | |||
| 1386 | continue; | |||
| 1387 | // The problem here can be that the new register may have been created | |||
| 1388 | // for a partially defined original register. For example: | |||
| 1389 | // %0:subreg_hireg<def,read-undef> = ... | |||
| 1390 | // ... | |||
| 1391 | // %1 = COPY %0 | |||
| 1392 | if (S.empty()) | |||
| 1393 | continue; | |||
| 1394 | SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, | |||
| 1395 | &LIS.getVNInfoAllocator()); | |||
| 1396 | SmallVector<SlotIndex, 4> Undefs; | |||
| 1397 | LI.computeSubRangeUndefs(Undefs, S.LaneMask, MRI, *LIS.getSlotIndexes()); | |||
| 1398 | SubLIC.extend(S, EP.Next, 0, Undefs); | |||
| 1399 | } | |||
| 1400 | } | |||
| 1401 | ||||
| 1402 | for (Register R : *Edit) { | |||
| 1403 | LiveInterval &LI = LIS.getInterval(R); | |||
| 1404 | if (!LI.hasSubRanges()) | |||
| 1405 | continue; | |||
| 1406 | LI.clear(); | |||
| 1407 | LI.removeEmptySubRanges(); | |||
| 1408 | LIS.constructMainRangeFromSubranges(LI); | |||
| 1409 | } | |||
| 1410 | } | |||
| 1411 | ||||
| 1412 | void SplitEditor::deleteRematVictims() { | |||
| 1413 | SmallVector<MachineInstr*, 8> Dead; | |||
| 1414 | for (const Register &R : *Edit) { | |||
| 1415 | LiveInterval *LI = &LIS.getInterval(R); | |||
| 1416 | for (const LiveRange::Segment &S : LI->segments) { | |||
| 1417 | // Dead defs end at the dead slot. | |||
| 1418 | if (S.end != S.valno->def.getDeadSlot()) | |||
| 1419 | continue; | |||
| 1420 | if (S.valno->isPHIDef()) | |||
| 1421 | continue; | |||
| 1422 | MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def); | |||
| 1423 | assert(MI && "Missing instruction for dead def")((void)0); | |||
| 1424 | MI->addRegisterDead(LI->reg(), &TRI); | |||
| 1425 | ||||
| 1426 | if (!MI->allDefsAreDead()) | |||
| 1427 | continue; | |||
| 1428 | ||||
| 1429 | LLVM_DEBUG(dbgs() << "All defs dead: " << *MI)do { } while (false); | |||
| 1430 | Dead.push_back(MI); | |||
| 1431 | } | |||
| 1432 | } | |||
| 1433 | ||||
| 1434 | if (Dead.empty()) | |||
| 1435 | return; | |||
| 1436 | ||||
| 1437 | Edit->eliminateDeadDefs(Dead, None, &AA); | |||
| 1438 | } | |||
| 1439 | ||||
| 1440 | void SplitEditor::forceRecomputeVNI(const VNInfo &ParentVNI) { | |||
| 1441 | // Fast-path for common case. | |||
| 1442 | if (!ParentVNI.isPHIDef()) { | |||
| 1443 | for (unsigned I = 0, E = Edit->size(); I != E; ++I) | |||
| 1444 | forceRecompute(I, ParentVNI); | |||
| 1445 | return; | |||
| 1446 | } | |||
| 1447 | ||||
| 1448 | // Trace value through phis. | |||
| 1449 | SmallPtrSet<const VNInfo *, 8> Visited; ///< whether VNI was/is in worklist. | |||
| 1450 | SmallVector<const VNInfo *, 4> WorkList; | |||
| 1451 | Visited.insert(&ParentVNI); | |||
| 1452 | WorkList.push_back(&ParentVNI); | |||
| 1453 | ||||
| 1454 | const LiveInterval &ParentLI = Edit->getParent(); | |||
| 1455 | const SlotIndexes &Indexes = *LIS.getSlotIndexes(); | |||
| 1456 | do { | |||
| 1457 | const VNInfo &VNI = *WorkList.back(); | |||
| 1458 | WorkList.pop_back(); | |||
| 1459 | for (unsigned I = 0, E = Edit->size(); I != E; ++I) | |||
| 1460 | forceRecompute(I, VNI); | |||
| 1461 | if (!VNI.isPHIDef()) | |||
| 1462 | continue; | |||
| 1463 | ||||
| 1464 | MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(VNI.def); | |||
| 1465 | for (const MachineBasicBlock *Pred : MBB.predecessors()) { | |||
| 1466 | SlotIndex PredEnd = Indexes.getMBBEndIdx(Pred); | |||
| 1467 | VNInfo *PredVNI = ParentLI.getVNInfoBefore(PredEnd); | |||
| 1468 | assert(PredVNI && "Value available in PhiVNI predecessor")((void)0); | |||
| 1469 | if (Visited.insert(PredVNI).second) | |||
| 1470 | WorkList.push_back(PredVNI); | |||
| 1471 | } | |||
| 1472 | } while(!WorkList.empty()); | |||
| 1473 | } | |||
| 1474 | ||||
| 1475 | void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) { | |||
| 1476 | ++NumFinished; | |||
| 1477 | ||||
| 1478 | // At this point, the live intervals in Edit contain VNInfos corresponding to | |||
| 1479 | // the inserted copies. | |||
| 1480 | ||||
| 1481 | // Add the original defs from the parent interval. | |||
| 1482 | for (const VNInfo *ParentVNI : Edit->getParent().valnos) { | |||
| ||||
| 1483 | if (ParentVNI->isUnused()) | |||
| 1484 | continue; | |||
| 1485 | unsigned RegIdx = RegAssign.lookup(ParentVNI->def); | |||
| 1486 | defValue(RegIdx, ParentVNI, ParentVNI->def, true); | |||
| 1487 | ||||
| 1488 | // Force rematted values to be recomputed everywhere. | |||
| 1489 | // The new live ranges may be truncated. | |||
| 1490 | if (Edit->didRematerialize(ParentVNI)) | |||
| 1491 | forceRecomputeVNI(*ParentVNI); | |||
| 1492 | } | |||
| 1493 | ||||
| 1494 | // Hoist back-copies to the complement interval when in spill mode. | |||
| 1495 | switch (SpillMode) { | |||
| 1496 | case SM_Partition: | |||
| 1497 | // Leave all back-copies as is. | |||
| 1498 | break; | |||
| 1499 | case SM_Size: | |||
| 1500 | case SM_Speed: | |||
| 1501 | // hoistCopies will behave differently between size and speed. | |||
| 1502 | hoistCopies(); | |||
| 1503 | } | |||
| 1504 | ||||
| 1505 | // Transfer the simply mapped values, check if any are skipped. | |||
| 1506 | bool Skipped = transferValues(); | |||
| 1507 | ||||
| 1508 | // Rewrite virtual registers, possibly extending ranges. | |||
| 1509 | rewriteAssigned(Skipped); | |||
| 1510 | ||||
| 1511 | if (Skipped) | |||
| 1512 | extendPHIKillRanges(); | |||
| 1513 | else | |||
| 1514 | ++NumSimple; | |||
| 1515 | ||||
| 1516 | // Delete defs that were rematted everywhere. | |||
| 1517 | if (Skipped) | |||
| 1518 | deleteRematVictims(); | |||
| 1519 | ||||
| 1520 | // Get rid of unused values and set phi-kill flags. | |||
| 1521 | for (Register Reg : *Edit) { | |||
| 1522 | LiveInterval &LI = LIS.getInterval(Reg); | |||
| 1523 | LI.removeEmptySubRanges(); | |||
| 1524 | LI.RenumberValues(); | |||
| 1525 | } | |||
| 1526 | ||||
| 1527 | // Provide a reverse mapping from original indices to Edit ranges. | |||
| 1528 | if (LRMap) { | |||
| 1529 | LRMap->clear(); | |||
| 1530 | for (unsigned i = 0, e = Edit->size(); i != e; ++i) | |||
| 1531 | LRMap->push_back(i); | |||
| 1532 | } | |||
| 1533 | ||||
| 1534 | // Now check if any registers were separated into multiple components. | |||
| 1535 | ConnectedVNInfoEqClasses ConEQ(LIS); | |||
| 1536 | for (unsigned i = 0, e = Edit->size(); i != e; ++i) { | |||
| 1537 | // Don't use iterators, they are invalidated by create() below. | |||
| 1538 | Register VReg = Edit->get(i); | |||
| 1539 | LiveInterval &LI = LIS.getInterval(VReg); | |||
| 1540 | SmallVector<LiveInterval*, 8> SplitLIs; | |||
| 1541 | LIS.splitSeparateComponents(LI, SplitLIs); | |||
| 1542 | Register Original = VRM.getOriginal(VReg); | |||
| 1543 | for (LiveInterval *SplitLI : SplitLIs) | |||
| 1544 | VRM.setIsSplitFromReg(SplitLI->reg(), Original); | |||
| 1545 | ||||
| 1546 | // The new intervals all map back to i. | |||
| 1547 | if (LRMap) | |||
| 1548 | LRMap->resize(Edit->size(), i); | |||
| 1549 | } | |||
| 1550 | ||||
| 1551 | // Calculate spill weight and allocation hints for new intervals. | |||
| 1552 | Edit->calculateRegClassAndHint(VRM.getMachineFunction(), VRAI); | |||
| 1553 | ||||
| 1554 | assert(!LRMap || LRMap->size() == Edit->size())((void)0); | |||
| 1555 | } | |||
| 1556 | ||||
| 1557 | //===----------------------------------------------------------------------===// | |||
| 1558 | // Single Block Splitting | |||
| 1559 | //===----------------------------------------------------------------------===// | |||
| 1560 | ||||
| 1561 | bool SplitAnalysis::shouldSplitSingleBlock(const BlockInfo &BI, | |||
| 1562 | bool SingleInstrs) const { | |||
| 1563 | // Always split for multiple instructions. | |||
| 1564 | if (!BI.isOneInstr()) | |||
| 1565 | return true; | |||
| 1566 | // Don't split for single instructions unless explicitly requested. | |||
| 1567 | if (!SingleInstrs) | |||
| 1568 | return false; | |||
| 1569 | // Splitting a live-through range always makes progress. | |||
| 1570 | if (BI.LiveIn && BI.LiveOut) | |||
| 1571 | return true; | |||
| 1572 | // No point in isolating a copy. It has no register class constraints. | |||
| 1573 | if (LIS.getInstructionFromIndex(BI.FirstInstr)->isCopyLike()) | |||
| 1574 | return false; | |||
| 1575 | // Finally, don't isolate an end point that was created by earlier splits. | |||
| 1576 | return isOriginalEndpoint(BI.FirstInstr); | |||
| 1577 | } | |||
| 1578 | ||||
| 1579 | void SplitEditor::splitSingleBlock(const SplitAnalysis::BlockInfo &BI) { | |||
| 1580 | openIntv(); | |||
| 1581 | SlotIndex LastSplitPoint = SA.getLastSplitPoint(BI.MBB); | |||
| 1582 | SlotIndex SegStart = enterIntvBefore(std::min(BI.FirstInstr, | |||
| 1583 | LastSplitPoint)); | |||
| 1584 | if (!BI.LiveOut || BI.LastInstr < LastSplitPoint) { | |||
| 1585 | useIntv(SegStart, leaveIntvAfter(BI.LastInstr)); | |||
| 1586 | } else { | |||
| 1587 | // The last use is after the last valid split point. | |||
| 1588 | SlotIndex SegStop = leaveIntvBefore(LastSplitPoint); | |||
| 1589 | useIntv(SegStart, SegStop); | |||
| 1590 | overlapIntv(SegStop, BI.LastInstr); | |||
| 1591 | } | |||
| 1592 | } | |||
| 1593 | ||||
| 1594 | //===----------------------------------------------------------------------===// | |||
| 1595 | // Global Live Range Splitting Support | |||
| 1596 | //===----------------------------------------------------------------------===// | |||
| 1597 | ||||
| 1598 | // These methods support a method of global live range splitting that uses a | |||
| 1599 | // global algorithm to decide intervals for CFG edges. They will insert split | |||
| 1600 | // points and color intervals in basic blocks while avoiding interference. | |||
| 1601 | // | |||
| 1602 | // Note that splitSingleBlock is also useful for blocks where both CFG edges | |||
| 1603 | // are on the stack. | |||
| 1604 | ||||
| 1605 | void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, | |||
| 1606 | unsigned IntvIn, SlotIndex LeaveBefore, | |||
| 1607 | unsigned IntvOut, SlotIndex EnterAfter){ | |||
| 1608 | SlotIndex Start, Stop; | |||
| 1609 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); | |||
| 1610 | ||||
| 1611 | LLVM_DEBUG(dbgs() << "%bb." << MBBNum << " [" << Start << ';' << Stopdo { } while (false) | |||
| 1612 | << ") intf " << LeaveBefore << '-' << EnterAfterdo { } while (false) | |||
| 1613 | << ", live-through " << IntvIn << " -> " << IntvOut)do { } while (false); | |||
| 1614 | ||||
| 1615 | assert((IntvIn || IntvOut) && "Use splitSingleBlock for isolated blocks")((void)0); | |||
| 1616 | ||||
| 1617 | assert((!LeaveBefore || LeaveBefore < Stop) && "Interference after block")((void)0); | |||
| 1618 | assert((!IntvIn || !LeaveBefore || LeaveBefore > Start) && "Impossible intf")((void)0); | |||
| 1619 | assert((!EnterAfter || EnterAfter >= Start) && "Interference before block")((void)0); | |||
| 1620 | ||||
| 1621 | MachineBasicBlock *MBB = VRM.getMachineFunction().getBlockNumbered(MBBNum); | |||
| 1622 | ||||
| 1623 | if (!IntvOut) { | |||
| 1624 | LLVM_DEBUG(dbgs() << ", spill on entry.\n")do { } while (false); | |||
| 1625 | // | |||
| 1626 | // <<<<<<<<< Possible LeaveBefore interference. | |||
| 1627 | // |-----------| Live through. | |||
| 1628 | // -____________ Spill on entry. | |||
| 1629 | // | |||
| 1630 | selectIntv(IntvIn); | |||
| 1631 | SlotIndex Idx = leaveIntvAtTop(*MBB); | |||
| 1632 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
| 1633 | (void)Idx; | |||
| 1634 | return; | |||
| 1635 | } | |||
| 1636 | ||||
| 1637 | if (!IntvIn) { | |||
| 1638 | LLVM_DEBUG(dbgs() << ", reload on exit.\n")do { } while (false); | |||
| 1639 | // | |||
| 1640 | // >>>>>>> Possible EnterAfter interference. | |||
| 1641 | // |-----------| Live through. | |||
| 1642 | // ___________-- Reload on exit. | |||
| 1643 | // | |||
| 1644 | selectIntv(IntvOut); | |||
| 1645 | SlotIndex Idx = enterIntvAtEnd(*MBB); | |||
| 1646 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
| 1647 | (void)Idx; | |||
| 1648 | return; | |||
| 1649 | } | |||
| 1650 | ||||
| 1651 | if (IntvIn == IntvOut && !LeaveBefore && !EnterAfter) { | |||
| 1652 | LLVM_DEBUG(dbgs() << ", straight through.\n")do { } while (false); | |||
| 1653 | // | |||
| 1654 | // |-----------| Live through. | |||
| 1655 | // ------------- Straight through, same intv, no interference. | |||
| 1656 | // | |||
| 1657 | selectIntv(IntvOut); | |||
| 1658 | useIntv(Start, Stop); | |||
| 1659 | return; | |||
| 1660 | } | |||
| 1661 | ||||
| 1662 | // We cannot legally insert splits after LSP. | |||
| 1663 | SlotIndex LSP = SA.getLastSplitPoint(MBBNum); | |||
| 1664 | assert((!IntvOut || !EnterAfter || EnterAfter < LSP) && "Impossible intf")((void)0); | |||
| 1665 | ||||
| 1666 | if (IntvIn != IntvOut && (!LeaveBefore || !EnterAfter || | |||
| 1667 | LeaveBefore.getBaseIndex() > EnterAfter.getBoundaryIndex())) { | |||
| 1668 | LLVM_DEBUG(dbgs() << ", switch avoiding interference.\n")do { } while (false); | |||
| 1669 | // | |||
| 1670 | // >>>> <<<< Non-overlapping EnterAfter/LeaveBefore interference. | |||
| 1671 | // |-----------| Live through. | |||
| 1672 | // ------======= Switch intervals between interference. | |||
| 1673 | // | |||
| 1674 | selectIntv(IntvOut); | |||
| 1675 | SlotIndex Idx; | |||
| 1676 | if (LeaveBefore && LeaveBefore < LSP) { | |||
| 1677 | Idx = enterIntvBefore(LeaveBefore); | |||
| 1678 | useIntv(Idx, Stop); | |||
| 1679 | } else { | |||
| 1680 | Idx = enterIntvAtEnd(*MBB); | |||
| 1681 | } | |||
| 1682 | selectIntv(IntvIn); | |||
| 1683 | useIntv(Start, Idx); | |||
| 1684 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
| 1685 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
| 1686 | return; | |||
| 1687 | } | |||
| 1688 | ||||
| 1689 | LLVM_DEBUG(dbgs() << ", create local intv for interference.\n")do { } while (false); | |||
| 1690 | // | |||
| 1691 | // >>><><><><<<< Overlapping EnterAfter/LeaveBefore interference. | |||
| 1692 | // |-----------| Live through. | |||
| 1693 | // ==---------== Switch intervals before/after interference. | |||
| 1694 | // | |||
| 1695 | assert(LeaveBefore <= EnterAfter && "Missed case")((void)0); | |||
| 1696 | ||||
| 1697 | selectIntv(IntvOut); | |||
| 1698 | SlotIndex Idx = enterIntvAfter(EnterAfter); | |||
| 1699 | useIntv(Idx, Stop); | |||
| 1700 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
| 1701 | ||||
| 1702 | selectIntv(IntvIn); | |||
| 1703 | Idx = leaveIntvBefore(LeaveBefore); | |||
| 1704 | useIntv(Start, Idx); | |||
| 1705 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
| 1706 | } | |||
| 1707 | ||||
| 1708 | void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, | |||
| 1709 | unsigned IntvIn, SlotIndex LeaveBefore) { | |||
| 1710 | SlotIndex Start, Stop; | |||
| 1711 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); | |||
| 1712 | ||||
| 1713 | LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'do { } while (false) | |||
| 1714 | << Stop << "), uses " << BI.FirstInstr << '-'do { } while (false) | |||
| 1715 | << BI.LastInstr << ", reg-in " << IntvIndo { } while (false) | |||
| 1716 | << ", leave before " << LeaveBeforedo { } while (false) | |||
| 1717 | << (BI.LiveOut ? ", stack-out" : ", killed in block"))do { } while (false); | |||
| 1718 | ||||
| 1719 | assert(IntvIn && "Must have register in")((void)0); | |||
| 1720 | assert(BI.LiveIn && "Must be live-in")((void)0); | |||
| 1721 | assert((!LeaveBefore || LeaveBefore > Start) && "Bad interference")((void)0); | |||
| 1722 | ||||
| 1723 | if (!BI.LiveOut && (!LeaveBefore || LeaveBefore >= BI.LastInstr)) { | |||
| 1724 | LLVM_DEBUG(dbgs() << " before interference.\n")do { } while (false); | |||
| 1725 | // | |||
| 1726 | // <<< Interference after kill. | |||
| 1727 | // |---o---x | Killed in block. | |||
| 1728 | // ========= Use IntvIn everywhere. | |||
| 1729 | // | |||
| 1730 | selectIntv(IntvIn); | |||
| 1731 | useIntv(Start, BI.LastInstr); | |||
| 1732 | return; | |||
| 1733 | } | |||
| 1734 | ||||
| 1735 | SlotIndex LSP = SA.getLastSplitPoint(BI.MBB); | |||
| 1736 | ||||
| 1737 | if (!LeaveBefore || LeaveBefore > BI.LastInstr.getBoundaryIndex()) { | |||
| 1738 | // | |||
| 1739 | // <<< Possible interference after last use. | |||
| 1740 | // |---o---o---| Live-out on stack. | |||
| 1741 | // =========____ Leave IntvIn after last use. | |||
| 1742 | // | |||
| 1743 | // < Interference after last use. | |||
| 1744 | // |---o---o--o| Live-out on stack, late last use. | |||
| 1745 | // ============ Copy to stack after LSP, overlap IntvIn. | |||
| 1746 | // \_____ Stack interval is live-out. | |||
| 1747 | // | |||
| 1748 | if (BI.LastInstr < LSP) { | |||
| 1749 | LLVM_DEBUG(dbgs() << ", spill after last use before interference.\n")do { } while (false); | |||
| 1750 | selectIntv(IntvIn); | |||
| 1751 | SlotIndex Idx = leaveIntvAfter(BI.LastInstr); | |||
| 1752 | useIntv(Start, Idx); | |||
| 1753 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
| 1754 | } else { | |||
| 1755 | LLVM_DEBUG(dbgs() << ", spill before last split point.\n")do { } while (false); | |||
| 1756 | selectIntv(IntvIn); | |||
| 1757 | SlotIndex Idx = leaveIntvBefore(LSP); | |||
| 1758 | overlapIntv(Idx, BI.LastInstr); | |||
| 1759 | useIntv(Start, Idx); | |||
| 1760 | assert((!LeaveBefore || Idx <= LeaveBefore) && "Interference")((void)0); | |||
| 1761 | } | |||
| 1762 | return; | |||
| 1763 | } | |||
| 1764 | ||||
| 1765 | // The interference is overlapping somewhere we wanted to use IntvIn. That | |||
| 1766 | // means we need to create a local interval that can be allocated a | |||
| 1767 | // different register. | |||
| 1768 | unsigned LocalIntv = openIntv(); | |||
| 1769 | (void)LocalIntv; | |||
| 1770 | LLVM_DEBUG(dbgs() << ", creating local interval " << LocalIntv << ".\n")do { } while (false); | |||
| 1771 | ||||
| 1772 | if (!BI.LiveOut || BI.LastInstr < LSP) { | |||
| 1773 | // | |||
| 1774 | // <<<<<<< Interference overlapping uses. | |||
| 1775 | // |---o---o---| Live-out on stack. | |||
| 1776 | // =====----____ Leave IntvIn before interference, then spill. | |||
| 1777 | // | |||
| 1778 | SlotIndex To = leaveIntvAfter(BI.LastInstr); | |||
| 1779 | SlotIndex From = enterIntvBefore(LeaveBefore); | |||
| 1780 | useIntv(From, To); | |||
| 1781 | selectIntv(IntvIn); | |||
| 1782 | useIntv(Start, From); | |||
| 1783 | assert((!LeaveBefore || From <= LeaveBefore) && "Interference")((void)0); | |||
| 1784 | return; | |||
| 1785 | } | |||
| 1786 | ||||
| 1787 | // <<<<<<< Interference overlapping uses. | |||
| 1788 | // |---o---o--o| Live-out on stack, late last use. | |||
| 1789 | // =====------- Copy to stack before LSP, overlap LocalIntv. | |||
| 1790 | // \_____ Stack interval is live-out. | |||
| 1791 | // | |||
| 1792 | SlotIndex To = leaveIntvBefore(LSP); | |||
| 1793 | overlapIntv(To, BI.LastInstr); | |||
| 1794 | SlotIndex From = enterIntvBefore(std::min(To, LeaveBefore)); | |||
| 1795 | useIntv(From, To); | |||
| 1796 | selectIntv(IntvIn); | |||
| 1797 | useIntv(Start, From); | |||
| 1798 | assert((!LeaveBefore || From <= LeaveBefore) && "Interference")((void)0); | |||
| 1799 | } | |||
| 1800 | ||||
| 1801 | void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, | |||
| 1802 | unsigned IntvOut, SlotIndex EnterAfter) { | |||
| 1803 | SlotIndex Start, Stop; | |||
| 1804 | std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); | |||
| 1805 | ||||
| 1806 | LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " [" << Start << ';'do { } while (false) | |||
| 1807 | << Stop << "), uses " << BI.FirstInstr << '-'do { } while (false) | |||
| 1808 | << BI.LastInstr << ", reg-out " << IntvOutdo { } while (false) | |||
| 1809 | << ", enter after " << EnterAfterdo { } while (false) | |||
| 1810 | << (BI.LiveIn ? ", stack-in" : ", defined in block"))do { } while (false); | |||
| 1811 | ||||
| 1812 | SlotIndex LSP = SA.getLastSplitPoint(BI.MBB); | |||
| 1813 | ||||
| 1814 | assert(IntvOut && "Must have register out")((void)0); | |||
| 1815 | assert(BI.LiveOut && "Must be live-out")((void)0); | |||
| 1816 | assert((!EnterAfter || EnterAfter < LSP) && "Bad interference")((void)0); | |||
| 1817 | ||||
| 1818 | if (!BI.LiveIn && (!EnterAfter || EnterAfter <= BI.FirstInstr)) { | |||
| 1819 | LLVM_DEBUG(dbgs() << " after interference.\n")do { } while (false); | |||
| 1820 | // | |||
| 1821 | // >>>> Interference before def. | |||
| 1822 | // | o---o---| Defined in block. | |||
| 1823 | // ========= Use IntvOut everywhere. | |||
| 1824 | // | |||
| 1825 | selectIntv(IntvOut); | |||
| 1826 | useIntv(BI.FirstInstr, Stop); | |||
| 1827 | return; | |||
| 1828 | } | |||
| 1829 | ||||
| 1830 | if (!EnterAfter || EnterAfter < BI.FirstInstr.getBaseIndex()) { | |||
| 1831 | LLVM_DEBUG(dbgs() << ", reload after interference.\n")do { } while (false); | |||
| 1832 | // | |||
| 1833 | // >>>> Interference before def. | |||
| 1834 | // |---o---o---| Live-through, stack-in. | |||
| 1835 | // ____========= Enter IntvOut before first use. | |||
| 1836 | // | |||
| 1837 | selectIntv(IntvOut); | |||
| 1838 | SlotIndex Idx = enterIntvBefore(std::min(LSP, BI.FirstInstr)); | |||
| 1839 | useIntv(Idx, Stop); | |||
| 1840 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
| 1841 | return; | |||
| 1842 | } | |||
| 1843 | ||||
| 1844 | // The interference is overlapping somewhere we wanted to use IntvOut. That | |||
| 1845 | // means we need to create a local interval that can be allocated a | |||
| 1846 | // different register. | |||
| 1847 | LLVM_DEBUG(dbgs() << ", interference overlaps uses.\n")do { } while (false); | |||
| 1848 | // | |||
| 1849 | // >>>>>>> Interference overlapping uses. | |||
| 1850 | // |---o---o---| Live-through, stack-in. | |||
| 1851 | // ____---====== Create local interval for interference range. | |||
| 1852 | // | |||
| 1853 | selectIntv(IntvOut); | |||
| 1854 | SlotIndex Idx = enterIntvAfter(EnterAfter); | |||
| 1855 | useIntv(Idx, Stop); | |||
| 1856 | assert((!EnterAfter || Idx >= EnterAfter) && "Interference")((void)0); | |||
| 1857 | ||||
| 1858 | openIntv(); | |||
| 1859 | SlotIndex From = enterIntvBefore(std::min(Idx, BI.FirstInstr)); | |||
| 1860 | useIntv(From, Idx); | |||
| 1861 | } | |||
| 1862 | ||||
| 1863 | void SplitAnalysis::BlockInfo::print(raw_ostream &OS) const { | |||
| 1864 | OS << "{" << printMBBReference(*MBB) << ", " | |||
| 1865 | << "uses " << FirstInstr << " to " << LastInstr << ", " | |||
| 1866 | << "1st def " << FirstDef << ", " | |||
| 1867 | << (LiveIn ? "live in" : "dead in") << ", " | |||
| 1868 | << (LiveOut ? "live out" : "dead out") << "}"; | |||
| 1869 | } | |||
| 1870 | ||||
| 1871 | void SplitAnalysis::BlockInfo::dump() const { | |||
| 1872 | print(dbgs()); | |||
| 1873 | dbgs() << "\n"; | |||
| 1874 | } |
| 1 | //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==// |
| 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 | // This file defines classes mirroring those in llvm/Analysis/Dominators.h, |
| 10 | // but for target-specific code rather than target-independent IR. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H |
| 15 | #define LLVM_CODEGEN_MACHINEDOMINATORS_H |
| 16 | |
| 17 | #include "llvm/ADT/SmallSet.h" |
| 18 | #include "llvm/ADT/SmallVector.h" |
| 19 | #include "llvm/CodeGen/MachineBasicBlock.h" |
| 20 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 21 | #include "llvm/CodeGen/MachineInstr.h" |
| 22 | #include "llvm/Support/GenericDomTree.h" |
| 23 | #include "llvm/Support/GenericDomTreeConstruction.h" |
| 24 | #include <cassert> |
| 25 | #include <memory> |
| 26 | |
| 27 | namespace llvm { |
| 28 | |
| 29 | template <> |
| 30 | inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( |
| 31 | MachineBasicBlock *MBB) { |
| 32 | this->Roots.push_back(MBB); |
| 33 | } |
| 34 | |
| 35 | extern template class DomTreeNodeBase<MachineBasicBlock>; |
| 36 | extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree |
| 37 | extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree |
| 38 | |
| 39 | using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; |
| 40 | |
| 41 | //===------------------------------------- |
| 42 | /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to |
| 43 | /// compute a normal dominator tree. |
| 44 | /// |
| 45 | class MachineDominatorTree : public MachineFunctionPass { |
| 46 | using DomTreeT = DomTreeBase<MachineBasicBlock>; |
| 47 | |
| 48 | /// Helper structure used to hold all the basic blocks |
| 49 | /// involved in the split of a critical edge. |
| 50 | struct CriticalEdge { |
| 51 | MachineBasicBlock *FromBB; |
| 52 | MachineBasicBlock *ToBB; |
| 53 | MachineBasicBlock *NewBB; |
| 54 | }; |
| 55 | |
| 56 | /// Pile up all the critical edges to be split. |
| 57 | /// The splitting of a critical edge is local and thus, it is possible |
| 58 | /// to apply several of those changes at the same time. |
| 59 | mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit; |
| 60 | |
| 61 | /// Remember all the basic blocks that are inserted during |
| 62 | /// edge splitting. |
| 63 | /// Invariant: NewBBs == all the basic blocks contained in the NewBB |
| 64 | /// field of all the elements of CriticalEdgesToSplit. |
| 65 | /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs |
| 66 | /// such as BB == elt.NewBB. |
| 67 | mutable SmallSet<MachineBasicBlock *, 32> NewBBs; |
| 68 | |
| 69 | /// The DominatorTreeBase that is used to compute a normal dominator tree. |
| 70 | std::unique_ptr<DomTreeT> DT; |
| 71 | |
| 72 | /// Apply all the recorded critical edges to the DT. |
| 73 | /// This updates the underlying DT information in a way that uses |
| 74 | /// the fast query path of DT as much as possible. |
| 75 | /// |
| 76 | /// \post CriticalEdgesToSplit.empty(). |
| 77 | void applySplitCriticalEdges() const; |
| 78 | |
| 79 | public: |
| 80 | static char ID; // Pass ID, replacement for typeid |
| 81 | |
| 82 | MachineDominatorTree(); |
| 83 | explicit MachineDominatorTree(MachineFunction &MF) : MachineFunctionPass(ID) { |
| 84 | calculate(MF); |
| 85 | } |
| 86 | |
| 87 | DomTreeT &getBase() { |
| 88 | if (!DT) DT.reset(new DomTreeT()); |
| 89 | applySplitCriticalEdges(); |
| 90 | return *DT; |
| 91 | } |
| 92 | |
| 93 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
| 94 | |
| 95 | MachineBasicBlock *getRoot() const { |
| 96 | applySplitCriticalEdges(); |
| 97 | return DT->getRoot(); |
| 98 | } |
| 99 | |
| 100 | MachineDomTreeNode *getRootNode() const { |
| 101 | applySplitCriticalEdges(); |
| 102 | return DT->getRootNode(); |
| 103 | } |
| 104 | |
| 105 | bool runOnMachineFunction(MachineFunction &F) override; |
| 106 | |
| 107 | void calculate(MachineFunction &F); |
| 108 | |
| 109 | bool dominates(const MachineDomTreeNode *A, |
| 110 | const MachineDomTreeNode *B) const { |
| 111 | applySplitCriticalEdges(); |
| 112 | return DT->dominates(A, B); |
| 113 | } |
| 114 | |
| 115 | bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const { |
| 116 | applySplitCriticalEdges(); |
| 117 | return DT->dominates(A, B); |
| 118 | } |
| 119 | |
| 120 | // dominates - Return true if A dominates B. This performs the |
| 121 | // special checks necessary if A and B are in the same basic block. |
| 122 | bool dominates(const MachineInstr *A, const MachineInstr *B) const { |
| 123 | applySplitCriticalEdges(); |
| 124 | const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); |
| 125 | if (BBA != BBB) return DT->dominates(BBA, BBB); |
| 126 | |
| 127 | // Loop through the basic block until we find A or B. |
| 128 | MachineBasicBlock::const_iterator I = BBA->begin(); |
| 129 | for (; &*I != A && &*I != B; ++I) |
| 130 | /*empty*/ ; |
| 131 | |
| 132 | return &*I == A; |
| 133 | } |
| 134 | |
| 135 | bool properlyDominates(const MachineDomTreeNode *A, |
| 136 | const MachineDomTreeNode *B) const { |
| 137 | applySplitCriticalEdges(); |
| 138 | return DT->properlyDominates(A, B); |
| 139 | } |
| 140 | |
| 141 | bool properlyDominates(const MachineBasicBlock *A, |
| 142 | const MachineBasicBlock *B) const { |
| 143 | applySplitCriticalEdges(); |
| 144 | return DT->properlyDominates(A, B); |
| 145 | } |
| 146 | |
| 147 | /// findNearestCommonDominator - Find nearest common dominator basic block |
| 148 | /// for basic block A and B. If there is no such block then return NULL. |
| 149 | MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, |
| 150 | MachineBasicBlock *B) { |
| 151 | applySplitCriticalEdges(); |
| 152 | return DT->findNearestCommonDominator(A, B); |
| 153 | } |
| 154 | |
| 155 | MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { |
| 156 | applySplitCriticalEdges(); |
| 157 | return DT->getNode(BB); |
| 158 | } |
| 159 | |
| 160 | /// getNode - return the (Post)DominatorTree node for the specified basic |
| 161 | /// block. This is the same as using operator[] on this class. |
| 162 | /// |
| 163 | MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { |
| 164 | applySplitCriticalEdges(); |
| 165 | return DT->getNode(BB); |
| 166 | } |
| 167 | |
| 168 | /// addNewBlock - Add a new node to the dominator tree information. This |
| 169 | /// creates a new node as a child of DomBB dominator node,linking it into |
| 170 | /// the children list of the immediate dominator. |
| 171 | MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, |
| 172 | MachineBasicBlock *DomBB) { |
| 173 | applySplitCriticalEdges(); |
| 174 | return DT->addNewBlock(BB, DomBB); |
| 175 | } |
| 176 | |
| 177 | /// changeImmediateDominator - This method is used to update the dominator |
| 178 | /// tree information when a node's immediate dominator changes. |
| 179 | /// |
| 180 | void changeImmediateDominator(MachineBasicBlock *N, |
| 181 | MachineBasicBlock *NewIDom) { |
| 182 | applySplitCriticalEdges(); |
| 183 | DT->changeImmediateDominator(N, NewIDom); |
| 184 | } |
| 185 | |
| 186 | void changeImmediateDominator(MachineDomTreeNode *N, |
| 187 | MachineDomTreeNode *NewIDom) { |
| 188 | applySplitCriticalEdges(); |
| 189 | DT->changeImmediateDominator(N, NewIDom); |
| 190 | } |
| 191 | |
| 192 | /// eraseNode - Removes a node from the dominator tree. Block must not |
| 193 | /// dominate any other blocks. Removes node from its immediate dominator's |
| 194 | /// children list. Deletes dominator node associated with basic block BB. |
| 195 | void eraseNode(MachineBasicBlock *BB) { |
| 196 | applySplitCriticalEdges(); |
| 197 | DT->eraseNode(BB); |
| 198 | } |
| 199 | |
| 200 | /// splitBlock - BB is split and now it has one successor. Update dominator |
| 201 | /// tree to reflect this change. |
| 202 | void splitBlock(MachineBasicBlock* NewBB) { |
| 203 | applySplitCriticalEdges(); |
| 204 | DT->splitBlock(NewBB); |
| 205 | } |
| 206 | |
| 207 | /// isReachableFromEntry - Return true if A is dominated by the entry |
| 208 | /// block of the function containing it. |
| 209 | bool isReachableFromEntry(const MachineBasicBlock *A) { |
| 210 | applySplitCriticalEdges(); |
| 211 | return DT->isReachableFromEntry(A); |
| 212 | } |
| 213 | |
| 214 | void releaseMemory() override; |
| 215 | |
| 216 | void verifyAnalysis() const override; |
| 217 | |
| 218 | void print(raw_ostream &OS, const Module*) const override; |
| 219 | |
| 220 | /// Record that the critical edge (FromBB, ToBB) has been |
| 221 | /// split with NewBB. |
| 222 | /// This is best to use this method instead of directly update the |
| 223 | /// underlying information, because this helps mitigating the |
| 224 | /// number of time the DT information is invalidated. |
| 225 | /// |
| 226 | /// \note Do not use this method with regular edges. |
| 227 | /// |
| 228 | /// \note To benefit from the compile time improvement incurred by this |
| 229 | /// method, the users of this method have to limit the queries to the DT |
| 230 | /// interface between two edges splitting. In other words, they have to |
| 231 | /// pack the splitting of critical edges as much as possible. |
| 232 | void recordSplitCriticalEdge(MachineBasicBlock *FromBB, |
| 233 | MachineBasicBlock *ToBB, |
| 234 | MachineBasicBlock *NewBB) { |
| 235 | bool Inserted = NewBBs.insert(NewBB).second; |
| 236 | (void)Inserted; |
| 237 | assert(Inserted &&((void)0) |
| 238 | "A basic block inserted via edge splitting cannot appear twice")((void)0); |
| 239 | CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB}); |
| 240 | } |
| 241 | }; |
| 242 | |
| 243 | //===------------------------------------- |
| 244 | /// DominatorTree GraphTraits specialization so the DominatorTree can be |
| 245 | /// iterable by generic graph iterators. |
| 246 | /// |
| 247 | |
| 248 | template <class Node, class ChildIterator> |
| 249 | struct MachineDomTreeGraphTraitsBase { |
| 250 | using NodeRef = Node *; |
| 251 | using ChildIteratorType = ChildIterator; |
| 252 | |
| 253 | static NodeRef getEntryNode(NodeRef N) { return N; } |
| 254 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
| 255 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
| 256 | }; |
| 257 | |
| 258 | template <class T> struct GraphTraits; |
| 259 | |
| 260 | template <> |
| 261 | struct GraphTraits<MachineDomTreeNode *> |
| 262 | : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, |
| 263 | MachineDomTreeNode::const_iterator> { |
| 264 | }; |
| 265 | |
| 266 | template <> |
| 267 | struct GraphTraits<const MachineDomTreeNode *> |
| 268 | : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, |
| 269 | MachineDomTreeNode::const_iterator> { |
| 270 | }; |
| 271 | |
| 272 | template <> struct GraphTraits<MachineDominatorTree*> |
| 273 | : public GraphTraits<MachineDomTreeNode *> { |
| 274 | static NodeRef getEntryNode(MachineDominatorTree *DT) { |
| 275 | return DT->getRootNode(); |
| 276 | } |
| 277 | }; |
| 278 | |
| 279 | } // end namespace llvm |
| 280 | |
| 281 | #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H |
| 1 | //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===// | |||
| 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 | /// \file | |||
| 9 | /// | |||
| 10 | /// This file defines a set of templates that efficiently compute a dominator | |||
| 11 | /// tree over a generic graph. This is used typically in LLVM for fast | |||
| 12 | /// dominance queries on the CFG, but is fully generic w.r.t. the underlying | |||
| 13 | /// graph types. | |||
| 14 | /// | |||
| 15 | /// Unlike ADT/* graph algorithms, generic dominator tree has more requirements | |||
| 16 | /// on the graph's NodeRef. The NodeRef should be a pointer and, | |||
| 17 | /// NodeRef->getParent() must return the parent node that is also a pointer. | |||
| 18 | /// | |||
| 19 | /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits. | |||
| 20 | /// | |||
| 21 | //===----------------------------------------------------------------------===// | |||
| 22 | ||||
| 23 | #ifndef LLVM_SUPPORT_GENERICDOMTREE_H | |||
| 24 | #define LLVM_SUPPORT_GENERICDOMTREE_H | |||
| 25 | ||||
| 26 | #include "llvm/ADT/DenseMap.h" | |||
| 27 | #include "llvm/ADT/GraphTraits.h" | |||
| 28 | #include "llvm/ADT/STLExtras.h" | |||
| 29 | #include "llvm/ADT/SmallPtrSet.h" | |||
| 30 | #include "llvm/ADT/SmallVector.h" | |||
| 31 | #include "llvm/Support/CFGDiff.h" | |||
| 32 | #include "llvm/Support/CFGUpdate.h" | |||
| 33 | #include "llvm/Support/raw_ostream.h" | |||
| 34 | #include <algorithm> | |||
| 35 | #include <cassert> | |||
| 36 | #include <cstddef> | |||
| 37 | #include <iterator> | |||
| 38 | #include <memory> | |||
| 39 | #include <type_traits> | |||
| 40 | #include <utility> | |||
| 41 | ||||
| 42 | namespace llvm { | |||
| 43 | ||||
| 44 | template <typename NodeT, bool IsPostDom> | |||
| 45 | class DominatorTreeBase; | |||
| 46 | ||||
| 47 | namespace DomTreeBuilder { | |||
| 48 | template <typename DomTreeT> | |||
| 49 | struct SemiNCAInfo; | |||
| 50 | } // namespace DomTreeBuilder | |||
| 51 | ||||
| 52 | /// Base class for the actual dominator tree node. | |||
| 53 | template <class NodeT> class DomTreeNodeBase { | |||
| 54 | friend class PostDominatorTree; | |||
| 55 | friend class DominatorTreeBase<NodeT, false>; | |||
| 56 | friend class DominatorTreeBase<NodeT, true>; | |||
| 57 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>; | |||
| 58 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>; | |||
| 59 | ||||
| 60 | NodeT *TheBB; | |||
| 61 | DomTreeNodeBase *IDom; | |||
| 62 | unsigned Level; | |||
| 63 | SmallVector<DomTreeNodeBase *, 4> Children; | |||
| 64 | mutable unsigned DFSNumIn = ~0; | |||
| 65 | mutable unsigned DFSNumOut = ~0; | |||
| 66 | ||||
| 67 | public: | |||
| 68 | DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) | |||
| 69 | : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {} | |||
| 70 | ||||
| 71 | using iterator = typename SmallVector<DomTreeNodeBase *, 4>::iterator; | |||
| 72 | using const_iterator = | |||
| 73 | typename SmallVector<DomTreeNodeBase *, 4>::const_iterator; | |||
| 74 | ||||
| 75 | iterator begin() { return Children.begin(); } | |||
| 76 | iterator end() { return Children.end(); } | |||
| 77 | const_iterator begin() const { return Children.begin(); } | |||
| 78 | const_iterator end() const { return Children.end(); } | |||
| 79 | ||||
| 80 | DomTreeNodeBase *const &back() const { return Children.back(); } | |||
| 81 | DomTreeNodeBase *&back() { return Children.back(); } | |||
| 82 | ||||
| 83 | iterator_range<iterator> children() { return make_range(begin(), end()); } | |||
| 84 | iterator_range<const_iterator> children() const { | |||
| 85 | return make_range(begin(), end()); | |||
| 86 | } | |||
| 87 | ||||
| 88 | NodeT *getBlock() const { return TheBB; } | |||
| 89 | DomTreeNodeBase *getIDom() const { return IDom; } | |||
| 90 | unsigned getLevel() const { return Level; } | |||
| 91 | ||||
| 92 | std::unique_ptr<DomTreeNodeBase> addChild( | |||
| 93 | std::unique_ptr<DomTreeNodeBase> C) { | |||
| 94 | Children.push_back(C.get()); | |||
| 95 | return C; | |||
| 96 | } | |||
| 97 | ||||
| 98 | bool isLeaf() const { return Children.empty(); } | |||
| 99 | size_t getNumChildren() const { return Children.size(); } | |||
| 100 | ||||
| 101 | void clearAllChildren() { Children.clear(); } | |||
| 102 | ||||
| 103 | bool compare(const DomTreeNodeBase *Other) const { | |||
| 104 | if (getNumChildren() != Other->getNumChildren()) | |||
| 105 | return true; | |||
| 106 | ||||
| 107 | if (Level != Other->Level) return true; | |||
| 108 | ||||
| 109 | SmallPtrSet<const NodeT *, 4> OtherChildren; | |||
| 110 | for (const DomTreeNodeBase *I : *Other) { | |||
| 111 | const NodeT *Nd = I->getBlock(); | |||
| 112 | OtherChildren.insert(Nd); | |||
| 113 | } | |||
| 114 | ||||
| 115 | for (const DomTreeNodeBase *I : *this) { | |||
| 116 | const NodeT *N = I->getBlock(); | |||
| 117 | if (OtherChildren.count(N) == 0) | |||
| 118 | return true; | |||
| 119 | } | |||
| 120 | return false; | |||
| 121 | } | |||
| 122 | ||||
| 123 | void setIDom(DomTreeNodeBase *NewIDom) { | |||
| 124 | assert(IDom && "No immediate dominator?")((void)0); | |||
| 125 | if (IDom == NewIDom) return; | |||
| 126 | ||||
| 127 | auto I = find(IDom->Children, this); | |||
| 128 | assert(I != IDom->Children.end() &&((void)0) | |||
| 129 | "Not in immediate dominator children set!")((void)0); | |||
| 130 | // I am no longer your child... | |||
| 131 | IDom->Children.erase(I); | |||
| 132 | ||||
| 133 | // Switch to new dominator | |||
| 134 | IDom = NewIDom; | |||
| 135 | IDom->Children.push_back(this); | |||
| 136 | ||||
| 137 | UpdateLevel(); | |||
| 138 | } | |||
| 139 | ||||
| 140 | /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes | |||
| 141 | /// in the dominator tree. They are only guaranteed valid if | |||
| 142 | /// updateDFSNumbers() has been called. | |||
| 143 | unsigned getDFSNumIn() const { return DFSNumIn; } | |||
| 144 | unsigned getDFSNumOut() const { return DFSNumOut; } | |||
| 145 | ||||
| 146 | private: | |||
| 147 | // Return true if this node is dominated by other. Use this only if DFS info | |||
| 148 | // is valid. | |||
| 149 | bool DominatedBy(const DomTreeNodeBase *other) const { | |||
| 150 | return this->DFSNumIn >= other->DFSNumIn && | |||
| 151 | this->DFSNumOut <= other->DFSNumOut; | |||
| 152 | } | |||
| 153 | ||||
| 154 | void UpdateLevel() { | |||
| 155 | assert(IDom)((void)0); | |||
| 156 | if (Level == IDom->Level + 1) return; | |||
| 157 | ||||
| 158 | SmallVector<DomTreeNodeBase *, 64> WorkStack = {this}; | |||
| 159 | ||||
| 160 | while (!WorkStack.empty()) { | |||
| 161 | DomTreeNodeBase *Current = WorkStack.pop_back_val(); | |||
| 162 | Current->Level = Current->IDom->Level + 1; | |||
| 163 | ||||
| 164 | for (DomTreeNodeBase *C : *Current) { | |||
| 165 | assert(C->IDom)((void)0); | |||
| 166 | if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C); | |||
| 167 | } | |||
| 168 | } | |||
| 169 | } | |||
| 170 | }; | |||
| 171 | ||||
| 172 | template <class NodeT> | |||
| 173 | raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) { | |||
| 174 | if (Node->getBlock()) | |||
| 175 | Node->getBlock()->printAsOperand(O, false); | |||
| 176 | else | |||
| 177 | O << " <<exit node>>"; | |||
| 178 | ||||
| 179 | O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} [" | |||
| 180 | << Node->getLevel() << "]\n"; | |||
| 181 | ||||
| 182 | return O; | |||
| 183 | } | |||
| 184 | ||||
| 185 | template <class NodeT> | |||
| 186 | void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O, | |||
| 187 | unsigned Lev) { | |||
| 188 | O.indent(2 * Lev) << "[" << Lev << "] " << N; | |||
| 189 | for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), | |||
| 190 | E = N->end(); | |||
| 191 | I != E; ++I) | |||
| 192 | PrintDomTree<NodeT>(*I, O, Lev + 1); | |||
| 193 | } | |||
| 194 | ||||
| 195 | namespace DomTreeBuilder { | |||
| 196 | // The routines below are provided in a separate header but referenced here. | |||
| 197 | template <typename DomTreeT> | |||
| 198 | void Calculate(DomTreeT &DT); | |||
| 199 | ||||
| 200 | template <typename DomTreeT> | |||
| 201 | void CalculateWithUpdates(DomTreeT &DT, | |||
| 202 | ArrayRef<typename DomTreeT::UpdateType> Updates); | |||
| 203 | ||||
| 204 | template <typename DomTreeT> | |||
| 205 | void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, | |||
| 206 | typename DomTreeT::NodePtr To); | |||
| 207 | ||||
| 208 | template <typename DomTreeT> | |||
| 209 | void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, | |||
| 210 | typename DomTreeT::NodePtr To); | |||
| 211 | ||||
| 212 | template <typename DomTreeT> | |||
| 213 | void ApplyUpdates(DomTreeT &DT, | |||
| 214 | GraphDiff<typename DomTreeT::NodePtr, | |||
| 215 | DomTreeT::IsPostDominator> &PreViewCFG, | |||
| 216 | GraphDiff<typename DomTreeT::NodePtr, | |||
| 217 | DomTreeT::IsPostDominator> *PostViewCFG); | |||
| 218 | ||||
| 219 | template <typename DomTreeT> | |||
| 220 | bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL); | |||
| 221 | } // namespace DomTreeBuilder | |||
| 222 | ||||
| 223 | /// Core dominator tree base class. | |||
| 224 | /// | |||
| 225 | /// This class is a generic template over graph nodes. It is instantiated for | |||
| 226 | /// various graphs in the LLVM IR or in the code generator. | |||
| 227 | template <typename NodeT, bool IsPostDom> | |||
| 228 | class DominatorTreeBase { | |||
| 229 | public: | |||
| 230 | static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value, | |||
| 231 | "Currently DominatorTreeBase supports only pointer nodes"); | |||
| 232 | using NodeType = NodeT; | |||
| 233 | using NodePtr = NodeT *; | |||
| 234 | using ParentPtr = decltype(std::declval<NodeT *>()->getParent()); | |||
| 235 | static_assert(std::is_pointer<ParentPtr>::value, | |||
| 236 | "Currently NodeT's parent must be a pointer type"); | |||
| 237 | using ParentType = std::remove_pointer_t<ParentPtr>; | |||
| 238 | static constexpr bool IsPostDominator = IsPostDom; | |||
| 239 | ||||
| 240 | using UpdateType = cfg::Update<NodePtr>; | |||
| 241 | using UpdateKind = cfg::UpdateKind; | |||
| 242 | static constexpr UpdateKind Insert = UpdateKind::Insert; | |||
| 243 | static constexpr UpdateKind Delete = UpdateKind::Delete; | |||
| 244 | ||||
| 245 | enum class VerificationLevel { Fast, Basic, Full }; | |||
| 246 | ||||
| 247 | protected: | |||
| 248 | // Dominators always have a single root, postdominators can have more. | |||
| 249 | SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots; | |||
| 250 | ||||
| 251 | using DomTreeNodeMapType = | |||
| 252 | DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>; | |||
| 253 | DomTreeNodeMapType DomTreeNodes; | |||
| 254 | DomTreeNodeBase<NodeT> *RootNode = nullptr; | |||
| 255 | ParentPtr Parent = nullptr; | |||
| 256 | ||||
| 257 | mutable bool DFSInfoValid = false; | |||
| 258 | mutable unsigned int SlowQueries = 0; | |||
| 259 | ||||
| 260 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>; | |||
| 261 | ||||
| 262 | public: | |||
| 263 | DominatorTreeBase() {} | |||
| 264 | ||||
| 265 | DominatorTreeBase(DominatorTreeBase &&Arg) | |||
| 266 | : Roots(std::move(Arg.Roots)), | |||
| 267 | DomTreeNodes(std::move(Arg.DomTreeNodes)), | |||
| 268 | RootNode(Arg.RootNode), | |||
| 269 | Parent(Arg.Parent), | |||
| 270 | DFSInfoValid(Arg.DFSInfoValid), | |||
| 271 | SlowQueries(Arg.SlowQueries) { | |||
| 272 | Arg.wipe(); | |||
| 273 | } | |||
| 274 | ||||
| 275 | DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { | |||
| 276 | Roots = std::move(RHS.Roots); | |||
| 277 | DomTreeNodes = std::move(RHS.DomTreeNodes); | |||
| 278 | RootNode = RHS.RootNode; | |||
| 279 | Parent = RHS.Parent; | |||
| 280 | DFSInfoValid = RHS.DFSInfoValid; | |||
| 281 | SlowQueries = RHS.SlowQueries; | |||
| 282 | RHS.wipe(); | |||
| 283 | return *this; | |||
| 284 | } | |||
| 285 | ||||
| 286 | DominatorTreeBase(const DominatorTreeBase &) = delete; | |||
| 287 | DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; | |||
| 288 | ||||
| 289 | /// Iteration over roots. | |||
| 290 | /// | |||
| 291 | /// This may include multiple blocks if we are computing post dominators. | |||
| 292 | /// For forward dominators, this will always be a single block (the entry | |||
| 293 | /// block). | |||
| 294 | using root_iterator = typename SmallVectorImpl<NodeT *>::iterator; | |||
| 295 | using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator; | |||
| 296 | ||||
| 297 | root_iterator root_begin() { return Roots.begin(); } | |||
| 298 | const_root_iterator root_begin() const { return Roots.begin(); } | |||
| 299 | root_iterator root_end() { return Roots.end(); } | |||
| 300 | const_root_iterator root_end() const { return Roots.end(); } | |||
| 301 | ||||
| 302 | size_t root_size() const { return Roots.size(); } | |||
| 303 | ||||
| 304 | iterator_range<root_iterator> roots() { | |||
| 305 | return make_range(root_begin(), root_end()); | |||
| 306 | } | |||
| 307 | iterator_range<const_root_iterator> roots() const { | |||
| 308 | return make_range(root_begin(), root_end()); | |||
| 309 | } | |||
| 310 | ||||
| 311 | /// isPostDominator - Returns true if analysis based of postdoms | |||
| 312 | /// | |||
| 313 | bool isPostDominator() const { return IsPostDominator; } | |||
| 314 | ||||
| 315 | /// compare - Return false if the other dominator tree base matches this | |||
| 316 | /// dominator tree base. Otherwise return true. | |||
| 317 | bool compare(const DominatorTreeBase &Other) const { | |||
| 318 | if (Parent != Other.Parent) return true; | |||
| 319 | ||||
| 320 | if (Roots.size() != Other.Roots.size()) | |||
| 321 | return true; | |||
| 322 | ||||
| 323 | if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin())) | |||
| 324 | return true; | |||
| 325 | ||||
| 326 | const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; | |||
| 327 | if (DomTreeNodes.size() != OtherDomTreeNodes.size()) | |||
| 328 | return true; | |||
| 329 | ||||
| 330 | for (const auto &DomTreeNode : DomTreeNodes) { | |||
| 331 | NodeT *BB = DomTreeNode.first; | |||
| 332 | typename DomTreeNodeMapType::const_iterator OI = | |||
| 333 | OtherDomTreeNodes.find(BB); | |||
| 334 | if (OI == OtherDomTreeNodes.end()) | |||
| 335 | return true; | |||
| 336 | ||||
| 337 | DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second; | |||
| 338 | DomTreeNodeBase<NodeT> &OtherNd = *OI->second; | |||
| 339 | ||||
| 340 | if (MyNd.compare(&OtherNd)) | |||
| 341 | return true; | |||
| 342 | } | |||
| 343 | ||||
| 344 | return false; | |||
| 345 | } | |||
| 346 | ||||
| 347 | /// getNode - return the (Post)DominatorTree node for the specified basic | |||
| 348 | /// block. This is the same as using operator[] on this class. The result | |||
| 349 | /// may (but is not required to) be null for a forward (backwards) | |||
| 350 | /// statically unreachable block. | |||
| 351 | DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const { | |||
| 352 | auto I = DomTreeNodes.find(BB); | |||
| 353 | if (I != DomTreeNodes.end()) | |||
| 354 | return I->second.get(); | |||
| 355 | return nullptr; | |||
| 356 | } | |||
| 357 | ||||
| 358 | /// See getNode. | |||
| 359 | DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const { | |||
| 360 | return getNode(BB); | |||
| 361 | } | |||
| 362 | ||||
| 363 | /// getRootNode - This returns the entry node for the CFG of the function. If | |||
| 364 | /// this tree represents the post-dominance relations for a function, however, | |||
| 365 | /// this root may be a node with the block == NULL. This is the case when | |||
| 366 | /// there are multiple exit nodes from a particular function. Consumers of | |||
| 367 | /// post-dominance information must be capable of dealing with this | |||
| 368 | /// possibility. | |||
| 369 | /// | |||
| 370 | DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } | |||
| 371 | const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } | |||
| 372 | ||||
| 373 | /// Get all nodes dominated by R, including R itself. | |||
| 374 | void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { | |||
| 375 | Result.clear(); | |||
| 376 | const DomTreeNodeBase<NodeT> *RN = getNode(R); | |||
| 377 | if (!RN) | |||
| 378 | return; // If R is unreachable, it will not be present in the DOM tree. | |||
| 379 | SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; | |||
| 380 | WL.push_back(RN); | |||
| 381 | ||||
| 382 | while (!WL.empty()) { | |||
| 383 | const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); | |||
| 384 | Result.push_back(N->getBlock()); | |||
| 385 | WL.append(N->begin(), N->end()); | |||
| 386 | } | |||
| 387 | } | |||
| 388 | ||||
| 389 | /// properlyDominates - Returns true iff A dominates B and A != B. | |||
| 390 | /// Note that this is not a constant time operation! | |||
| 391 | /// | |||
| 392 | bool properlyDominates(const DomTreeNodeBase<NodeT> *A, | |||
| 393 | const DomTreeNodeBase<NodeT> *B) const { | |||
| 394 | if (!A || !B) | |||
| 395 | return false; | |||
| 396 | if (A == B) | |||
| 397 | return false; | |||
| 398 | return dominates(A, B); | |||
| 399 | } | |||
| 400 | ||||
| 401 | bool properlyDominates(const NodeT *A, const NodeT *B) const; | |||
| 402 | ||||
| 403 | /// isReachableFromEntry - Return true if A is dominated by the entry | |||
| 404 | /// block of the function containing it. | |||
| 405 | bool isReachableFromEntry(const NodeT *A) const { | |||
| 406 | assert(!this->isPostDominator() &&((void)0) | |||
| 407 | "This is not implemented for post dominators")((void)0); | |||
| 408 | return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); | |||
| 409 | } | |||
| 410 | ||||
| 411 | bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; } | |||
| 412 | ||||
| 413 | /// dominates - Returns true iff A dominates B. Note that this is not a | |||
| 414 | /// constant time operation! | |||
| 415 | /// | |||
| 416 | bool dominates(const DomTreeNodeBase<NodeT> *A, | |||
| 417 | const DomTreeNodeBase<NodeT> *B) const { | |||
| 418 | // A node trivially dominates itself. | |||
| 419 | if (B == A) | |||
| 420 | return true; | |||
| 421 | ||||
| 422 | // An unreachable node is dominated by anything. | |||
| 423 | if (!isReachableFromEntry(B)) | |||
| 424 | return true; | |||
| 425 | ||||
| 426 | // And dominates nothing. | |||
| 427 | if (!isReachableFromEntry(A)) | |||
| 428 | return false; | |||
| 429 | ||||
| 430 | if (B->getIDom() == A) return true; | |||
| 431 | ||||
| 432 | if (A->getIDom() == B) return false; | |||
| 433 | ||||
| 434 | // A can only dominate B if it is higher in the tree. | |||
| 435 | if (A->getLevel() >= B->getLevel()) return false; | |||
| 436 | ||||
| 437 | // Compare the result of the tree walk and the dfs numbers, if expensive | |||
| 438 | // checks are enabled. | |||
| 439 | #ifdef EXPENSIVE_CHECKS | |||
| 440 | assert((!DFSInfoValid ||((void)0) | |||
| 441 | (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&((void)0) | |||
| 442 | "Tree walk disagrees with dfs numbers!")((void)0); | |||
| 443 | #endif | |||
| 444 | ||||
| 445 | if (DFSInfoValid) | |||
| 446 | return B->DominatedBy(A); | |||
| 447 | ||||
| 448 | // If we end up with too many slow queries, just update the | |||
| 449 | // DFS numbers on the theory that we are going to keep querying. | |||
| 450 | SlowQueries++; | |||
| 451 | if (SlowQueries > 32) { | |||
| 452 | updateDFSNumbers(); | |||
| 453 | return B->DominatedBy(A); | |||
| 454 | } | |||
| 455 | ||||
| 456 | return dominatedBySlowTreeWalk(A, B); | |||
| 457 | } | |||
| 458 | ||||
| 459 | bool dominates(const NodeT *A, const NodeT *B) const; | |||
| 460 | ||||
| 461 | NodeT *getRoot() const { | |||
| 462 | assert(this->Roots.size() == 1 && "Should always have entry node!")((void)0); | |||
| 463 | return this->Roots[0]; | |||
| 464 | } | |||
| 465 | ||||
| 466 | /// Find nearest common dominator basic block for basic block A and B. A and B | |||
| 467 | /// must have tree nodes. | |||
| 468 | NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { | |||
| 469 | assert(A && B && "Pointers are not valid")((void)0); | |||
| 470 | assert(A->getParent() == B->getParent() &&((void)0) | |||
| 471 | "Two blocks are not in same function")((void)0); | |||
| 472 | ||||
| 473 | // If either A or B is a entry block then it is nearest common dominator | |||
| 474 | // (for forward-dominators). | |||
| 475 | if (!isPostDominator()) { | |||
| 476 | NodeT &Entry = A->getParent()->front(); | |||
| 477 | if (A == &Entry || B == &Entry) | |||
| 478 | return &Entry; | |||
| 479 | } | |||
| 480 | ||||
| 481 | DomTreeNodeBase<NodeT> *NodeA = getNode(A); | |||
| 482 | DomTreeNodeBase<NodeT> *NodeB = getNode(B); | |||
| 483 | assert(NodeA && "A must be in the tree")((void)0); | |||
| 484 | assert(NodeB && "B must be in the tree")((void)0); | |||
| 485 | ||||
| 486 | // Use level information to go up the tree until the levels match. Then | |||
| 487 | // continue going up til we arrive at the same node. | |||
| 488 | while (NodeA != NodeB) { | |||
| 489 | if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB); | |||
| 490 | ||||
| 491 | NodeA = NodeA->IDom; | |||
| 492 | } | |||
| 493 | ||||
| 494 | return NodeA->getBlock(); | |||
| ||||
| 495 | } | |||
| 496 | ||||
| 497 | const NodeT *findNearestCommonDominator(const NodeT *A, | |||
| 498 | const NodeT *B) const { | |||
| 499 | // Cast away the const qualifiers here. This is ok since | |||
| 500 | // const is re-introduced on the return type. | |||
| 501 | return findNearestCommonDominator(const_cast<NodeT *>(A), | |||
| 502 | const_cast<NodeT *>(B)); | |||
| 503 | } | |||
| 504 | ||||
| 505 | bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const { | |||
| 506 | return isPostDominator() && !A->getBlock(); | |||
| 507 | } | |||
| 508 | ||||
| 509 | //===--------------------------------------------------------------------===// | |||
| 510 | // API to update (Post)DominatorTree information based on modifications to | |||
| 511 | // the CFG... | |||
| 512 | ||||
| 513 | /// Inform the dominator tree about a sequence of CFG edge insertions and | |||
| 514 | /// deletions and perform a batch update on the tree. | |||
| 515 | /// | |||
| 516 | /// This function should be used when there were multiple CFG updates after | |||
| 517 | /// the last dominator tree update. It takes care of performing the updates | |||
| 518 | /// in sync with the CFG and optimizes away the redundant operations that | |||
| 519 | /// cancel each other. | |||
| 520 | /// The functions expects the sequence of updates to be balanced. Eg.: | |||
| 521 | /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because | |||
| 522 | /// logically it results in a single insertions. | |||
| 523 | /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make | |||
| 524 | /// sense to insert the same edge twice. | |||
| 525 | /// | |||
| 526 | /// What's more, the functions assumes that it's safe to ask every node in the | |||
| 527 | /// CFG about its children and inverse children. This implies that deletions | |||
| 528 | /// of CFG edges must not delete the CFG nodes before calling this function. | |||
| 529 | /// | |||
| 530 | /// The applyUpdates function can reorder the updates and remove redundant | |||
| 531 | /// ones internally. The batch updater is also able to detect sequences of | |||
| 532 | /// zero and exactly one update -- it's optimized to do less work in these | |||
| 533 | /// cases. | |||
| 534 | /// | |||
| 535 | /// Note that for postdominators it automatically takes care of applying | |||
| 536 | /// updates on reverse edges internally (so there's no need to swap the | |||
| 537 | /// From and To pointers when constructing DominatorTree::UpdateType). | |||
| 538 | /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T> | |||
| 539 | /// with the same template parameter T. | |||
| 540 | /// | |||
| 541 | /// \param Updates An unordered sequence of updates to perform. The current | |||
| 542 | /// CFG and the reverse of these updates provides the pre-view of the CFG. | |||
| 543 | /// | |||
| 544 | void applyUpdates(ArrayRef<UpdateType> Updates) { | |||
| 545 | GraphDiff<NodePtr, IsPostDominator> PreViewCFG( | |||
| 546 | Updates, /*ReverseApplyUpdates=*/true); | |||
| 547 | DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr); | |||
| 548 | } | |||
| 549 | ||||
| 550 | /// \param Updates An unordered sequence of updates to perform. The current | |||
| 551 | /// CFG and the reverse of these updates provides the pre-view of the CFG. | |||
| 552 | /// \param PostViewUpdates An unordered sequence of update to perform in order | |||
| 553 | /// to obtain a post-view of the CFG. The DT will be updated assuming the | |||
| 554 | /// obtained PostViewCFG is the desired end state. | |||
| 555 | void applyUpdates(ArrayRef<UpdateType> Updates, | |||
| 556 | ArrayRef<UpdateType> PostViewUpdates) { | |||
| 557 | if (Updates.empty()) { | |||
| 558 | GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates); | |||
| 559 | DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG); | |||
| 560 | } else { | |||
| 561 | // PreViewCFG needs to merge Updates and PostViewCFG. The updates in | |||
| 562 | // Updates need to be reversed, and match the direction in PostViewCFG. | |||
| 563 | // The PostViewCFG is created with updates reversed (equivalent to changes | |||
| 564 | // made to the CFG), so the PreViewCFG needs all the updates reverse | |||
| 565 | // applied. | |||
| 566 | SmallVector<UpdateType> AllUpdates(Updates.begin(), Updates.end()); | |||
| 567 | append_range(AllUpdates, PostViewUpdates); | |||
| 568 | GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates, | |||
| 569 | /*ReverseApplyUpdates=*/true); | |||
| 570 | GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates); | |||
| 571 | DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG); | |||
| 572 | } | |||
| 573 | } | |||
| 574 | ||||
| 575 | /// Inform the dominator tree about a CFG edge insertion and update the tree. | |||
| 576 | /// | |||
| 577 | /// This function has to be called just before or just after making the update | |||
| 578 | /// on the actual CFG. There cannot be any other updates that the dominator | |||
| 579 | /// tree doesn't know about. | |||
| 580 | /// | |||
| 581 | /// Note that for postdominators it automatically takes care of inserting | |||
| 582 | /// a reverse edge internally (so there's no need to swap the parameters). | |||
| 583 | /// | |||
| 584 | void insertEdge(NodeT *From, NodeT *To) { | |||
| 585 | assert(From)((void)0); | |||
| 586 | assert(To)((void)0); | |||
| 587 | assert(From->getParent() == Parent)((void)0); | |||
| 588 | assert(To->getParent() == Parent)((void)0); | |||
| 589 | DomTreeBuilder::InsertEdge(*this, From, To); | |||
| 590 | } | |||
| 591 | ||||
| 592 | /// Inform the dominator tree about a CFG edge deletion and update the tree. | |||
| 593 | /// | |||
| 594 | /// This function has to be called just after making the update on the actual | |||
| 595 | /// CFG. An internal functions checks if the edge doesn't exist in the CFG in | |||
| 596 | /// DEBUG mode. There cannot be any other updates that the | |||
| 597 | /// dominator tree doesn't know about. | |||
| 598 | /// | |||
| 599 | /// Note that for postdominators it automatically takes care of deleting | |||
| 600 | /// a reverse edge internally (so there's no need to swap the parameters). | |||
| 601 | /// | |||
| 602 | void deleteEdge(NodeT *From, NodeT *To) { | |||
| 603 | assert(From)((void)0); | |||
| 604 | assert(To)((void)0); | |||
| 605 | assert(From->getParent() == Parent)((void)0); | |||
| 606 | assert(To->getParent() == Parent)((void)0); | |||
| 607 | DomTreeBuilder::DeleteEdge(*this, From, To); | |||
| 608 | } | |||
| 609 | ||||
| 610 | /// Add a new node to the dominator tree information. | |||
| 611 | /// | |||
| 612 | /// This creates a new node as a child of DomBB dominator node, linking it | |||
| 613 | /// into the children list of the immediate dominator. | |||
| 614 | /// | |||
| 615 | /// \param BB New node in CFG. | |||
| 616 | /// \param DomBB CFG node that is dominator for BB. | |||
| 617 | /// \returns New dominator tree node that represents new CFG node. | |||
| 618 | /// | |||
| 619 | DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { | |||
| 620 | assert(getNode(BB) == nullptr && "Block already in dominator tree!")((void)0); | |||
| 621 | DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); | |||
| 622 | assert(IDomNode && "Not immediate dominator specified for block!")((void)0); | |||
| 623 | DFSInfoValid = false; | |||
| 624 | return createChild(BB, IDomNode); | |||
| 625 | } | |||
| 626 | ||||
| 627 | /// Add a new node to the forward dominator tree and make it a new root. | |||
| 628 | /// | |||
| 629 | /// \param BB New node in CFG. | |||
| 630 | /// \returns New dominator tree node that represents new CFG node. | |||
| 631 | /// | |||
| 632 | DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) { | |||
| 633 | assert(getNode(BB) == nullptr && "Block already in dominator tree!")((void)0); | |||
| 634 | assert(!this->isPostDominator() &&((void)0) | |||
| 635 | "Cannot change root of post-dominator tree")((void)0); | |||
| 636 | DFSInfoValid = false; | |||
| 637 | DomTreeNodeBase<NodeT> *NewNode = createNode(BB); | |||
| 638 | if (Roots.empty()) { | |||
| 639 | addRoot(BB); | |||
| 640 | } else { | |||
| 641 | assert(Roots.size() == 1)((void)0); | |||
| 642 | NodeT *OldRoot = Roots.front(); | |||
| 643 | auto &OldNode = DomTreeNodes[OldRoot]; | |||
| 644 | OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot])); | |||
| 645 | OldNode->IDom = NewNode; | |||
| 646 | OldNode->UpdateLevel(); | |||
| 647 | Roots[0] = BB; | |||
| 648 | } | |||
| 649 | return RootNode = NewNode; | |||
| 650 | } | |||
| 651 | ||||
| 652 | /// changeImmediateDominator - This method is used to update the dominator | |||
| 653 | /// tree information when a node's immediate dominator changes. | |||
| 654 | /// | |||
| 655 | void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, | |||
| 656 | DomTreeNodeBase<NodeT> *NewIDom) { | |||
| 657 | assert(N && NewIDom && "Cannot change null node pointers!")((void)0); | |||
| 658 | DFSInfoValid = false; | |||
| 659 | N->setIDom(NewIDom); | |||
| 660 | } | |||
| 661 | ||||
| 662 | void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { | |||
| 663 | changeImmediateDominator(getNode(BB), getNode(NewBB)); | |||
| 664 | } | |||
| 665 | ||||
| 666 | /// eraseNode - Removes a node from the dominator tree. Block must not | |||
| 667 | /// dominate any other blocks. Removes node from its immediate dominator's | |||
| 668 | /// children list. Deletes dominator node associated with basic block BB. | |||
| 669 | void eraseNode(NodeT *BB) { | |||
| 670 | DomTreeNodeBase<NodeT> *Node = getNode(BB); | |||
| 671 | assert(Node && "Removing node that isn't in dominator tree.")((void)0); | |||
| 672 | assert(Node->isLeaf() && "Node is not a leaf node.")((void)0); | |||
| 673 | ||||
| 674 | DFSInfoValid = false; | |||
| 675 | ||||
| 676 | // Remove node from immediate dominator's children list. | |||
| 677 | DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); | |||
| 678 | if (IDom) { | |||
| 679 | const auto I = find(IDom->Children, Node); | |||
| 680 | assert(I != IDom->Children.end() &&((void)0) | |||
| 681 | "Not in immediate dominator children set!")((void)0); | |||
| 682 | // I am no longer your child... | |||
| 683 | IDom->Children.erase(I); | |||
| 684 | } | |||
| 685 | ||||
| 686 | DomTreeNodes.erase(BB); | |||
| 687 | ||||
| 688 | if (!IsPostDom) return; | |||
| 689 | ||||
| 690 | // Remember to update PostDominatorTree roots. | |||
| 691 | auto RIt = llvm::find(Roots, BB); | |||
| 692 | if (RIt != Roots.end()) { | |||
| 693 | std::swap(*RIt, Roots.back()); | |||
| 694 | Roots.pop_back(); | |||
| 695 | } | |||
| 696 | } | |||
| 697 | ||||
| 698 | /// splitBlock - BB is split and now it has one successor. Update dominator | |||
| 699 | /// tree to reflect this change. | |||
| 700 | void splitBlock(NodeT *NewBB) { | |||
| 701 | if (IsPostDominator) | |||
| 702 | Split<Inverse<NodeT *>>(NewBB); | |||
| 703 | else | |||
| 704 | Split<NodeT *>(NewBB); | |||
| 705 | } | |||
| 706 | ||||
| 707 | /// print - Convert to human readable form | |||
| 708 | /// | |||
| 709 | void print(raw_ostream &O) const { | |||
| 710 | O << "=============================--------------------------------\n"; | |||
| 711 | if (IsPostDominator) | |||
| 712 | O << "Inorder PostDominator Tree: "; | |||
| 713 | else | |||
| 714 | O << "Inorder Dominator Tree: "; | |||
| 715 | if (!DFSInfoValid) | |||
| 716 | O << "DFSNumbers invalid: " << SlowQueries << " slow queries."; | |||
| 717 | O << "\n"; | |||
| 718 | ||||
| 719 | // The postdom tree can have a null root if there are no returns. | |||
| 720 | if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1); | |||
| 721 | O << "Roots: "; | |||
| 722 | for (const NodePtr Block : Roots) { | |||
| 723 | Block->printAsOperand(O, false); | |||
| 724 | O << " "; | |||
| 725 | } | |||
| 726 | O << "\n"; | |||
| 727 | } | |||
| 728 | ||||
| 729 | public: | |||
| 730 | /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking | |||
| 731 | /// dominator tree in dfs order. | |||
| 732 | void updateDFSNumbers() const { | |||
| 733 | if (DFSInfoValid) { | |||
| 734 | SlowQueries = 0; | |||
| 735 | return; | |||
| 736 | } | |||
| 737 | ||||
| 738 | SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, | |||
| 739 | typename DomTreeNodeBase<NodeT>::const_iterator>, | |||
| 740 | 32> WorkStack; | |||
| 741 | ||||
| 742 | const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); | |||
| 743 | assert((!Parent || ThisRoot) && "Empty constructed DomTree")((void)0); | |||
| 744 | if (!ThisRoot) | |||
| 745 | return; | |||
| 746 | ||||
| 747 | // Both dominators and postdominators have a single root node. In the case | |||
| 748 | // case of PostDominatorTree, this node is a virtual root. | |||
| 749 | WorkStack.push_back({ThisRoot, ThisRoot->begin()}); | |||
| 750 | ||||
| 751 | unsigned DFSNum = 0; | |||
| 752 | ThisRoot->DFSNumIn = DFSNum++; | |||
| 753 | ||||
| 754 | while (!WorkStack.empty()) { | |||
| 755 | const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; | |||
| 756 | const auto ChildIt = WorkStack.back().second; | |||
| 757 | ||||
| 758 | // If we visited all of the children of this node, "recurse" back up the | |||
| 759 | // stack setting the DFOutNum. | |||
| 760 | if (ChildIt == Node->end()) { | |||
| 761 | Node->DFSNumOut = DFSNum++; | |||
| 762 | WorkStack.pop_back(); | |||
| 763 | } else { | |||
| 764 | // Otherwise, recursively visit this child. | |||
| 765 | const DomTreeNodeBase<NodeT> *Child = *ChildIt; | |||
| 766 | ++WorkStack.back().second; | |||
| 767 | ||||
| 768 | WorkStack.push_back({Child, Child->begin()}); | |||
| 769 | Child->DFSNumIn = DFSNum++; | |||
| 770 | } | |||
| 771 | } | |||
| 772 | ||||
| 773 | SlowQueries = 0; | |||
| 774 | DFSInfoValid = true; | |||
| 775 | } | |||
| 776 | ||||
| 777 | /// recalculate - compute a dominator tree for the given function | |||
| 778 | void recalculate(ParentType &Func) { | |||
| 779 | Parent = &Func; | |||
| 780 | DomTreeBuilder::Calculate(*this); | |||
| 781 | } | |||
| 782 | ||||
| 783 | void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) { | |||
| 784 | Parent = &Func; | |||
| 785 | DomTreeBuilder::CalculateWithUpdates(*this, Updates); | |||
| 786 | } | |||
| 787 | ||||
| 788 | /// verify - checks if the tree is correct. There are 3 level of verification: | |||
| 789 | /// - Full -- verifies if the tree is correct by making sure all the | |||
| 790 | /// properties (including the parent and the sibling property) | |||
| 791 | /// hold. | |||
| 792 | /// Takes O(N^3) time. | |||
| 793 | /// | |||
| 794 | /// - Basic -- checks if the tree is correct, but compares it to a freshly | |||
| 795 | /// constructed tree instead of checking the sibling property. | |||
| 796 | /// Takes O(N^2) time. | |||
| 797 | /// | |||
| 798 | /// - Fast -- checks basic tree structure and compares it with a freshly | |||
| 799 | /// constructed tree. | |||
| 800 | /// Takes O(N^2) time worst case, but is faster in practise (same | |||
| 801 | /// as tree construction). | |||
| 802 | bool verify(VerificationLevel VL = VerificationLevel::Full) const { | |||
| 803 | return DomTreeBuilder::Verify(*this, VL); | |||
| 804 | } | |||
| 805 | ||||
| 806 | void reset() { | |||
| 807 | DomTreeNodes.clear(); | |||
| 808 | Roots.clear(); | |||
| 809 | RootNode = nullptr; | |||
| 810 | Parent = nullptr; | |||
| 811 | DFSInfoValid = false; | |||
| 812 | SlowQueries = 0; | |||
| 813 | } | |||
| 814 | ||||
| 815 | protected: | |||
| 816 | void addRoot(NodeT *BB) { this->Roots.push_back(BB); } | |||
| 817 | ||||
| 818 | DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) { | |||
| 819 | return (DomTreeNodes[BB] = IDom->addChild( | |||
| 820 | std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom))) | |||
| 821 | .get(); | |||
| 822 | } | |||
| 823 | ||||
| 824 | DomTreeNodeBase<NodeT> *createNode(NodeT *BB) { | |||
| 825 | return (DomTreeNodes[BB] = | |||
| 826 | std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)) | |||
| 827 | .get(); | |||
| 828 | } | |||
| 829 | ||||
| 830 | // NewBB is split and now it has one successor. Update dominator tree to | |||
| 831 | // reflect this change. | |||
| 832 | template <class N> | |||
| 833 | void Split(typename GraphTraits<N>::NodeRef NewBB) { | |||
| 834 | using GraphT = GraphTraits<N>; | |||
| 835 | using NodeRef = typename GraphT::NodeRef; | |||
| 836 | assert(std::distance(GraphT::child_begin(NewBB),((void)0) | |||
| 837 | GraphT::child_end(NewBB)) == 1 &&((void)0) | |||
| 838 | "NewBB should have a single successor!")((void)0); | |||
| 839 | NodeRef NewBBSucc = *GraphT::child_begin(NewBB); | |||
| 840 | ||||
| 841 | SmallVector<NodeRef, 4> PredBlocks(children<Inverse<N>>(NewBB)); | |||
| 842 | ||||
| 843 | assert(!PredBlocks.empty() && "No predblocks?")((void)0); | |||
| 844 | ||||
| 845 | bool NewBBDominatesNewBBSucc = true; | |||
| 846 | for (auto Pred : children<Inverse<N>>(NewBBSucc)) { | |||
| 847 | if (Pred != NewBB && !dominates(NewBBSucc, Pred) && | |||
| 848 | isReachableFromEntry(Pred)) { | |||
| 849 | NewBBDominatesNewBBSucc = false; | |||
| 850 | break; | |||
| 851 | } | |||
| 852 | } | |||
| 853 | ||||
| 854 | // Find NewBB's immediate dominator and create new dominator tree node for | |||
| 855 | // NewBB. | |||
| 856 | NodeT *NewBBIDom = nullptr; | |||
| 857 | unsigned i = 0; | |||
| 858 | for (i = 0; i < PredBlocks.size(); ++i) | |||
| 859 | if (isReachableFromEntry(PredBlocks[i])) { | |||
| 860 | NewBBIDom = PredBlocks[i]; | |||
| 861 | break; | |||
| 862 | } | |||
| 863 | ||||
| 864 | // It's possible that none of the predecessors of NewBB are reachable; | |||
| 865 | // in that case, NewBB itself is unreachable, so nothing needs to be | |||
| 866 | // changed. | |||
| 867 | if (!NewBBIDom) return; | |||
| 868 | ||||
| 869 | for (i = i + 1; i < PredBlocks.size(); ++i) { | |||
| 870 | if (isReachableFromEntry(PredBlocks[i])) | |||
| 871 | NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); | |||
| 872 | } | |||
| 873 | ||||
| 874 | // Create the new dominator tree node... and set the idom of NewBB. | |||
| 875 | DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom); | |||
| 876 | ||||
| 877 | // If NewBB strictly dominates other blocks, then it is now the immediate | |||
| 878 | // dominator of NewBBSucc. Update the dominator tree as appropriate. | |||
| 879 | if (NewBBDominatesNewBBSucc) { | |||
| 880 | DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc); | |||
| 881 | changeImmediateDominator(NewBBSuccNode, NewBBNode); | |||
| 882 | } | |||
| 883 | } | |||
| 884 | ||||
| 885 | private: | |||
| 886 | bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, | |||
| 887 | const DomTreeNodeBase<NodeT> *B) const { | |||
| 888 | assert(A != B)((void)0); | |||
| 889 | assert(isReachableFromEntry(B))((void)0); | |||
| 890 | assert(isReachableFromEntry(A))((void)0); | |||
| 891 | ||||
| 892 | const unsigned ALevel = A->getLevel(); | |||
| 893 | const DomTreeNodeBase<NodeT> *IDom; | |||
| 894 | ||||
| 895 | // Don't walk nodes above A's subtree. When we reach A's level, we must | |||
| 896 | // either find A or be in some other subtree not dominated by A. | |||
| 897 | while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) | |||
| 898 | B = IDom; // Walk up the tree | |||
| 899 | ||||
| 900 | return B == A; | |||
| 901 | } | |||
| 902 | ||||
| 903 | /// Wipe this tree's state without releasing any resources. | |||
| 904 | /// | |||
| 905 | /// This is essentially a post-move helper only. It leaves the object in an | |||
| 906 | /// assignable and destroyable state, but otherwise invalid. | |||
| 907 | void wipe() { | |||
| 908 | DomTreeNodes.clear(); | |||
| 909 | RootNode = nullptr; | |||
| 910 | Parent = nullptr; | |||
| 911 | } | |||
| 912 | }; | |||
| 913 | ||||
| 914 | template <typename T> | |||
| 915 | using DomTreeBase = DominatorTreeBase<T, false>; | |||
| 916 | ||||
| 917 | template <typename T> | |||
| 918 | using PostDomTreeBase = DominatorTreeBase<T, true>; | |||
| 919 | ||||
| 920 | // These two functions are declared out of line as a workaround for building | |||
| 921 | // with old (< r147295) versions of clang because of pr11642. | |||
| 922 | template <typename NodeT, bool IsPostDom> | |||
| 923 | bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A, | |||
| 924 | const NodeT *B) const { | |||
| 925 | if (A == B) | |||
| 926 | return true; | |||
| 927 | ||||
| 928 | // Cast away the const qualifiers here. This is ok since | |||
| 929 | // this function doesn't actually return the values returned | |||
| 930 | // from getNode. | |||
| 931 | return dominates(getNode(const_cast<NodeT *>(A)), | |||
| 932 | getNode(const_cast<NodeT *>(B))); | |||
| 933 | } | |||
| 934 | template <typename NodeT, bool IsPostDom> | |||
| 935 | bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates( | |||
| 936 | const NodeT *A, const NodeT *B) const { | |||
| 937 | if (A == B) | |||
| 938 | return false; | |||
| 939 | ||||
| 940 | // Cast away the const qualifiers here. This is ok since | |||
| 941 | // this function doesn't actually return the values returned | |||
| 942 | // from getNode. | |||
| 943 | return dominates(getNode(const_cast<NodeT *>(A)), | |||
| 944 | getNode(const_cast<NodeT *>(B))); | |||
| 945 | } | |||
| 946 | ||||
| 947 | } // end namespace llvm | |||
| 948 | ||||
| 949 | #endif // LLVM_SUPPORT_GENERICDOMTREE_H |
| 1 | //===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// |
| 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 | // This file defines the DenseMap class. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #ifndef LLVM_ADT_DENSEMAP_H |
| 14 | #define LLVM_ADT_DENSEMAP_H |
| 15 | |
| 16 | #include "llvm/ADT/DenseMapInfo.h" |
| 17 | #include "llvm/ADT/EpochTracker.h" |
| 18 | #include "llvm/Support/AlignOf.h" |
| 19 | #include "llvm/Support/Compiler.h" |
| 20 | #include "llvm/Support/MathExtras.h" |
| 21 | #include "llvm/Support/MemAlloc.h" |
| 22 | #include "llvm/Support/ReverseIteration.h" |
| 23 | #include "llvm/Support/type_traits.h" |
| 24 | #include <algorithm> |
| 25 | #include <cassert> |
| 26 | #include <cstddef> |
| 27 | #include <cstring> |
| 28 | #include <initializer_list> |
| 29 | #include <iterator> |
| 30 | #include <new> |
| 31 | #include <type_traits> |
| 32 | #include <utility> |
| 33 | |
| 34 | namespace llvm { |
| 35 | |
| 36 | namespace detail { |
| 37 | |
| 38 | // We extend a pair to allow users to override the bucket type with their own |
| 39 | // implementation without requiring two members. |
| 40 | template <typename KeyT, typename ValueT> |
| 41 | struct DenseMapPair : public std::pair<KeyT, ValueT> { |
| 42 | using std::pair<KeyT, ValueT>::pair; |
| 43 | |
| 44 | KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; } |
| 45 | const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; } |
| 46 | ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; } |
| 47 | const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; } |
| 48 | }; |
| 49 | |
| 50 | } // end namespace detail |
| 51 | |
| 52 | template <typename KeyT, typename ValueT, |
| 53 | typename KeyInfoT = DenseMapInfo<KeyT>, |
| 54 | typename Bucket = llvm::detail::DenseMapPair<KeyT, ValueT>, |
| 55 | bool IsConst = false> |
| 56 | class DenseMapIterator; |
| 57 | |
| 58 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
| 59 | typename BucketT> |
| 60 | class DenseMapBase : public DebugEpochBase { |
| 61 | template <typename T> |
| 62 | using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; |
| 63 | |
| 64 | public: |
| 65 | using size_type = unsigned; |
| 66 | using key_type = KeyT; |
| 67 | using mapped_type = ValueT; |
| 68 | using value_type = BucketT; |
| 69 | |
| 70 | using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>; |
| 71 | using const_iterator = |
| 72 | DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>; |
| 73 | |
| 74 | inline iterator begin() { |
| 75 | // When the map is empty, avoid the overhead of advancing/retreating past |
| 76 | // empty buckets. |
| 77 | if (empty()) |
| 78 | return end(); |
| 79 | if (shouldReverseIterate<KeyT>()) |
| 80 | return makeIterator(getBucketsEnd() - 1, getBuckets(), *this); |
| 81 | return makeIterator(getBuckets(), getBucketsEnd(), *this); |
| 82 | } |
| 83 | inline iterator end() { |
| 84 | return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true); |
| 85 | } |
| 86 | inline const_iterator begin() const { |
| 87 | if (empty()) |
| 88 | return end(); |
| 89 | if (shouldReverseIterate<KeyT>()) |
| 90 | return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this); |
| 91 | return makeConstIterator(getBuckets(), getBucketsEnd(), *this); |
| 92 | } |
| 93 | inline const_iterator end() const { |
| 94 | return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true); |
| 95 | } |
| 96 | |
| 97 | LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { |
| 98 | return getNumEntries() == 0; |
| 99 | } |
| 100 | unsigned size() const { return getNumEntries(); } |
| 101 | |
| 102 | /// Grow the densemap so that it can contain at least \p NumEntries items |
| 103 | /// before resizing again. |
| 104 | void reserve(size_type NumEntries) { |
| 105 | auto NumBuckets = getMinBucketToReserveForEntries(NumEntries); |
| 106 | incrementEpoch(); |
| 107 | if (NumBuckets > getNumBuckets()) |
| 108 | grow(NumBuckets); |
| 109 | } |
| 110 | |
| 111 | void clear() { |
| 112 | incrementEpoch(); |
| 113 | if (getNumEntries() == 0 && getNumTombstones() == 0) return; |
| 114 | |
| 115 | // If the capacity of the array is huge, and the # elements used is small, |
| 116 | // shrink the array. |
| 117 | if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { |
| 118 | shrink_and_clear(); |
| 119 | return; |
| 120 | } |
| 121 | |
| 122 | const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); |
| 123 | if (std::is_trivially_destructible<ValueT>::value) { |
| 124 | // Use a simpler loop when values don't need destruction. |
| 125 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) |
| 126 | P->getFirst() = EmptyKey; |
| 127 | } else { |
| 128 | unsigned NumEntries = getNumEntries(); |
| 129 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { |
| 130 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) { |
| 131 | if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { |
| 132 | P->getSecond().~ValueT(); |
| 133 | --NumEntries; |
| 134 | } |
| 135 | P->getFirst() = EmptyKey; |
| 136 | } |
| 137 | } |
| 138 | assert(NumEntries == 0 && "Node count imbalance!")((void)0); |
| 139 | } |
| 140 | setNumEntries(0); |
| 141 | setNumTombstones(0); |
| 142 | } |
| 143 | |
| 144 | /// Return 1 if the specified key is in the map, 0 otherwise. |
| 145 | size_type count(const_arg_type_t<KeyT> Val) const { |
| 146 | const BucketT *TheBucket; |
| 147 | return LookupBucketFor(Val, TheBucket) ? 1 : 0; |
| 148 | } |
| 149 | |
| 150 | iterator find(const_arg_type_t<KeyT> Val) { |
| 151 | BucketT *TheBucket; |
| 152 | if (LookupBucketFor(Val, TheBucket)) |
| 153 | return makeIterator(TheBucket, |
| 154 | shouldReverseIterate<KeyT>() ? getBuckets() |
| 155 | : getBucketsEnd(), |
| 156 | *this, true); |
| 157 | return end(); |
| 158 | } |
| 159 | const_iterator find(const_arg_type_t<KeyT> Val) const { |
| 160 | const BucketT *TheBucket; |
| 161 | if (LookupBucketFor(Val, TheBucket)) |
| 162 | return makeConstIterator(TheBucket, |
| 163 | shouldReverseIterate<KeyT>() ? getBuckets() |
| 164 | : getBucketsEnd(), |
| 165 | *this, true); |
| 166 | return end(); |
| 167 | } |
| 168 | |
| 169 | /// Alternate version of find() which allows a different, and possibly |
| 170 | /// less expensive, key type. |
| 171 | /// The DenseMapInfo is responsible for supplying methods |
| 172 | /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key |
| 173 | /// type used. |
| 174 | template<class LookupKeyT> |
| 175 | iterator find_as(const LookupKeyT &Val) { |
| 176 | BucketT *TheBucket; |
| 177 | if (LookupBucketFor(Val, TheBucket)) |
| 178 | return makeIterator(TheBucket, |
| 179 | shouldReverseIterate<KeyT>() ? getBuckets() |
| 180 | : getBucketsEnd(), |
| 181 | *this, true); |
| 182 | return end(); |
| 183 | } |
| 184 | template<class LookupKeyT> |
| 185 | const_iterator find_as(const LookupKeyT &Val) const { |
| 186 | const BucketT *TheBucket; |
| 187 | if (LookupBucketFor(Val, TheBucket)) |
| 188 | return makeConstIterator(TheBucket, |
| 189 | shouldReverseIterate<KeyT>() ? getBuckets() |
| 190 | : getBucketsEnd(), |
| 191 | *this, true); |
| 192 | return end(); |
| 193 | } |
| 194 | |
| 195 | /// lookup - Return the entry for the specified key, or a default |
| 196 | /// constructed value if no such entry exists. |
| 197 | ValueT lookup(const_arg_type_t<KeyT> Val) const { |
| 198 | const BucketT *TheBucket; |
| 199 | if (LookupBucketFor(Val, TheBucket)) |
| 200 | return TheBucket->getSecond(); |
| 201 | return ValueT(); |
| 202 | } |
| 203 | |
| 204 | // Inserts key,value pair into the map if the key isn't already in the map. |
| 205 | // If the key is already in the map, it returns false and doesn't update the |
| 206 | // value. |
| 207 | std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { |
| 208 | return try_emplace(KV.first, KV.second); |
| 209 | } |
| 210 | |
| 211 | // Inserts key,value pair into the map if the key isn't already in the map. |
| 212 | // If the key is already in the map, it returns false and doesn't update the |
| 213 | // value. |
| 214 | std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { |
| 215 | return try_emplace(std::move(KV.first), std::move(KV.second)); |
| 216 | } |
| 217 | |
| 218 | // Inserts key,value pair into the map if the key isn't already in the map. |
| 219 | // The value is constructed in-place if the key is not in the map, otherwise |
| 220 | // it is not moved. |
| 221 | template <typename... Ts> |
| 222 | std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) { |
| 223 | BucketT *TheBucket; |
| 224 | if (LookupBucketFor(Key, TheBucket)) |
| 225 | return std::make_pair(makeIterator(TheBucket, |
| 226 | shouldReverseIterate<KeyT>() |
| 227 | ? getBuckets() |
| 228 | : getBucketsEnd(), |
| 229 | *this, true), |
| 230 | false); // Already in map. |
| 231 | |
| 232 | // Otherwise, insert the new element. |
| 233 | TheBucket = |
| 234 | InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...); |
| 235 | return std::make_pair(makeIterator(TheBucket, |
| 236 | shouldReverseIterate<KeyT>() |
| 237 | ? getBuckets() |
| 238 | : getBucketsEnd(), |
| 239 | *this, true), |
| 240 | true); |
| 241 | } |
| 242 | |
| 243 | // Inserts key,value pair into the map if the key isn't already in the map. |
| 244 | // The value is constructed in-place if the key is not in the map, otherwise |
| 245 | // it is not moved. |
| 246 | template <typename... Ts> |
| 247 | std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) { |
| 248 | BucketT *TheBucket; |
| 249 | if (LookupBucketFor(Key, TheBucket)) |
| 250 | return std::make_pair(makeIterator(TheBucket, |
| 251 | shouldReverseIterate<KeyT>() |
| 252 | ? getBuckets() |
| 253 | : getBucketsEnd(), |
| 254 | *this, true), |
| 255 | false); // Already in map. |
| 256 | |
| 257 | // Otherwise, insert the new element. |
| 258 | TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...); |
| 259 | return std::make_pair(makeIterator(TheBucket, |
| 260 | shouldReverseIterate<KeyT>() |
| 261 | ? getBuckets() |
| 262 | : getBucketsEnd(), |
| 263 | *this, true), |
| 264 | true); |
| 265 | } |
| 266 | |
| 267 | /// Alternate version of insert() which allows a different, and possibly |
| 268 | /// less expensive, key type. |
| 269 | /// The DenseMapInfo is responsible for supplying methods |
| 270 | /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key |
| 271 | /// type used. |
| 272 | template <typename LookupKeyT> |
| 273 | std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV, |
| 274 | const LookupKeyT &Val) { |
| 275 | BucketT *TheBucket; |
| 276 | if (LookupBucketFor(Val, TheBucket)) |
| 277 | return std::make_pair(makeIterator(TheBucket, |
| 278 | shouldReverseIterate<KeyT>() |
| 279 | ? getBuckets() |
| 280 | : getBucketsEnd(), |
| 281 | *this, true), |
| 282 | false); // Already in map. |
| 283 | |
| 284 | // Otherwise, insert the new element. |
| 285 | TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first), |
| 286 | std::move(KV.second), Val); |
| 287 | return std::make_pair(makeIterator(TheBucket, |
| 288 | shouldReverseIterate<KeyT>() |
| 289 | ? getBuckets() |
| 290 | : getBucketsEnd(), |
| 291 | *this, true), |
| 292 | true); |
| 293 | } |
| 294 | |
| 295 | /// insert - Range insertion of pairs. |
| 296 | template<typename InputIt> |
| 297 | void insert(InputIt I, InputIt E) { |
| 298 | for (; I != E; ++I) |
| 299 | insert(*I); |
| 300 | } |
| 301 | |
| 302 | bool erase(const KeyT &Val) { |
| 303 | BucketT *TheBucket; |
| 304 | if (!LookupBucketFor(Val, TheBucket)) |
| 305 | return false; // not in map. |
| 306 | |
| 307 | TheBucket->getSecond().~ValueT(); |
| 308 | TheBucket->getFirst() = getTombstoneKey(); |
| 309 | decrementNumEntries(); |
| 310 | incrementNumTombstones(); |
| 311 | return true; |
| 312 | } |
| 313 | void erase(iterator I) { |
| 314 | BucketT *TheBucket = &*I; |
| 315 | TheBucket->getSecond().~ValueT(); |
| 316 | TheBucket->getFirst() = getTombstoneKey(); |
| 317 | decrementNumEntries(); |
| 318 | incrementNumTombstones(); |
| 319 | } |
| 320 | |
| 321 | value_type& FindAndConstruct(const KeyT &Key) { |
| 322 | BucketT *TheBucket; |
| 323 | if (LookupBucketFor(Key, TheBucket)) |
| 324 | return *TheBucket; |
| 325 | |
| 326 | return *InsertIntoBucket(TheBucket, Key); |
| 327 | } |
| 328 | |
| 329 | ValueT &operator[](const KeyT &Key) { |
| 330 | return FindAndConstruct(Key).second; |
| 331 | } |
| 332 | |
| 333 | value_type& FindAndConstruct(KeyT &&Key) { |
| 334 | BucketT *TheBucket; |
| 335 | if (LookupBucketFor(Key, TheBucket)) |
| 336 | return *TheBucket; |
| 337 | |
| 338 | return *InsertIntoBucket(TheBucket, std::move(Key)); |
| 339 | } |
| 340 | |
| 341 | ValueT &operator[](KeyT &&Key) { |
| 342 | return FindAndConstruct(std::move(Key)).second; |
| 343 | } |
| 344 | |
| 345 | /// isPointerIntoBucketsArray - Return true if the specified pointer points |
| 346 | /// somewhere into the DenseMap's array of buckets (i.e. either to a key or |
| 347 | /// value in the DenseMap). |
| 348 | bool isPointerIntoBucketsArray(const void *Ptr) const { |
| 349 | return Ptr >= getBuckets() && Ptr < getBucketsEnd(); |
| 350 | } |
| 351 | |
| 352 | /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets |
| 353 | /// array. In conjunction with the previous method, this can be used to |
| 354 | /// determine whether an insertion caused the DenseMap to reallocate. |
| 355 | const void *getPointerIntoBucketsArray() const { return getBuckets(); } |
| 356 | |
| 357 | protected: |
| 358 | DenseMapBase() = default; |
| 359 | |
| 360 | void destroyAll() { |
| 361 | if (getNumBuckets() == 0) // Nothing to do. |
| 362 | return; |
| 363 | |
| 364 | const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); |
| 365 | for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { |
| 366 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && |
| 367 | !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) |
| 368 | P->getSecond().~ValueT(); |
| 369 | P->getFirst().~KeyT(); |
| 370 | } |
| 371 | } |
| 372 | |
| 373 | void initEmpty() { |
| 374 | setNumEntries(0); |
| 375 | setNumTombstones(0); |
| 376 | |
| 377 | assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&((void)0) |
| 378 | "# initial buckets must be a power of two!")((void)0); |
| 379 | const KeyT EmptyKey = getEmptyKey(); |
| 380 | for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) |
| 381 | ::new (&B->getFirst()) KeyT(EmptyKey); |
| 382 | } |
| 383 | |
| 384 | /// Returns the number of buckets to allocate to ensure that the DenseMap can |
| 385 | /// accommodate \p NumEntries without need to grow(). |
| 386 | unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { |
| 387 | // Ensure that "NumEntries * 4 < NumBuckets * 3" |
| 388 | if (NumEntries == 0) |
| 389 | return 0; |
| 390 | // +1 is required because of the strict equality. |
| 391 | // For example if NumEntries is 48, we need to return 401. |
| 392 | return NextPowerOf2(NumEntries * 4 / 3 + 1); |
| 393 | } |
| 394 | |
| 395 | void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { |
| 396 | initEmpty(); |
| 397 | |
| 398 | // Insert all the old elements. |
| 399 | const KeyT EmptyKey = getEmptyKey(); |
| 400 | const KeyT TombstoneKey = getTombstoneKey(); |
| 401 | for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { |
| 402 | if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) && |
| 403 | !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) { |
| 404 | // Insert the key/value into the new table. |
| 405 | BucketT *DestBucket; |
| 406 | bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket); |
| 407 | (void)FoundVal; // silence warning. |
| 408 | assert(!FoundVal && "Key already in new map?")((void)0); |
| 409 | DestBucket->getFirst() = std::move(B->getFirst()); |
| 410 | ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond())); |
| 411 | incrementNumEntries(); |
| 412 | |
| 413 | // Free the value. |
| 414 | B->getSecond().~ValueT(); |
| 415 | } |
| 416 | B->getFirst().~KeyT(); |
| 417 | } |
| 418 | } |
| 419 | |
| 420 | template <typename OtherBaseT> |
| 421 | void copyFrom( |
| 422 | const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) { |
| 423 | assert(&other != this)((void)0); |
| 424 | assert(getNumBuckets() == other.getNumBuckets())((void)0); |
| 425 | |
| 426 | setNumEntries(other.getNumEntries()); |
| 427 | setNumTombstones(other.getNumTombstones()); |
| 428 | |
| 429 | if (std::is_trivially_copyable<KeyT>::value && |
| 430 | std::is_trivially_copyable<ValueT>::value) |
| 431 | memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(), |
| 432 | getNumBuckets() * sizeof(BucketT)); |
| 433 | else |
| 434 | for (size_t i = 0; i < getNumBuckets(); ++i) { |
| 435 | ::new (&getBuckets()[i].getFirst()) |
| 436 | KeyT(other.getBuckets()[i].getFirst()); |
| 437 | if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) && |
| 438 | !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey())) |
| 439 | ::new (&getBuckets()[i].getSecond()) |
| 440 | ValueT(other.getBuckets()[i].getSecond()); |
| 441 | } |
| 442 | } |
| 443 | |
| 444 | static unsigned getHashValue(const KeyT &Val) { |
| 445 | return KeyInfoT::getHashValue(Val); |
| 446 | } |
| 447 | |
| 448 | template<typename LookupKeyT> |
| 449 | static unsigned getHashValue(const LookupKeyT &Val) { |
| 450 | return KeyInfoT::getHashValue(Val); |
| 451 | } |
| 452 | |
| 453 | static const KeyT getEmptyKey() { |
| 454 | static_assert(std::is_base_of<DenseMapBase, DerivedT>::value, |
| 455 | "Must pass the derived type to this template!"); |
| 456 | return KeyInfoT::getEmptyKey(); |
| 457 | } |
| 458 | |
| 459 | static const KeyT getTombstoneKey() { |
| 460 | return KeyInfoT::getTombstoneKey(); |
| 461 | } |
| 462 | |
| 463 | private: |
| 464 | iterator makeIterator(BucketT *P, BucketT *E, |
| 465 | DebugEpochBase &Epoch, |
| 466 | bool NoAdvance=false) { |
| 467 | if (shouldReverseIterate<KeyT>()) { |
| 468 | BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1; |
| 469 | return iterator(B, E, Epoch, NoAdvance); |
| 470 | } |
| 471 | return iterator(P, E, Epoch, NoAdvance); |
| 472 | } |
| 473 | |
| 474 | const_iterator makeConstIterator(const BucketT *P, const BucketT *E, |
| 475 | const DebugEpochBase &Epoch, |
| 476 | const bool NoAdvance=false) const { |
| 477 | if (shouldReverseIterate<KeyT>()) { |
| 478 | const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1; |
| 479 | return const_iterator(B, E, Epoch, NoAdvance); |
| 480 | } |
| 481 | return const_iterator(P, E, Epoch, NoAdvance); |
| 482 | } |
| 483 | |
| 484 | unsigned getNumEntries() const { |
| 485 | return static_cast<const DerivedT *>(this)->getNumEntries(); |
| 486 | } |
| 487 | |
| 488 | void setNumEntries(unsigned Num) { |
| 489 | static_cast<DerivedT *>(this)->setNumEntries(Num); |
| 490 | } |
| 491 | |
| 492 | void incrementNumEntries() { |
| 493 | setNumEntries(getNumEntries() + 1); |
| 494 | } |
| 495 | |
| 496 | void decrementNumEntries() { |
| 497 | setNumEntries(getNumEntries() - 1); |
| 498 | } |
| 499 | |
| 500 | unsigned getNumTombstones() const { |
| 501 | return static_cast<const DerivedT *>(this)->getNumTombstones(); |
| 502 | } |
| 503 | |
| 504 | void setNumTombstones(unsigned Num) { |
| 505 | static_cast<DerivedT *>(this)->setNumTombstones(Num); |
| 506 | } |
| 507 | |
| 508 | void incrementNumTombstones() { |
| 509 | setNumTombstones(getNumTombstones() + 1); |
| 510 | } |
| 511 | |
| 512 | void decrementNumTombstones() { |
| 513 | setNumTombstones(getNumTombstones() - 1); |
| 514 | } |
| 515 | |
| 516 | const BucketT *getBuckets() const { |
| 517 | return static_cast<const DerivedT *>(this)->getBuckets(); |
| 518 | } |
| 519 | |
| 520 | BucketT *getBuckets() { |
| 521 | return static_cast<DerivedT *>(this)->getBuckets(); |
| 522 | } |
| 523 | |
| 524 | unsigned getNumBuckets() const { |
| 525 | return static_cast<const DerivedT *>(this)->getNumBuckets(); |
| 526 | } |
| 527 | |
| 528 | BucketT *getBucketsEnd() { |
| 529 | return getBuckets() + getNumBuckets(); |
| 530 | } |
| 531 | |
| 532 | const BucketT *getBucketsEnd() const { |
| 533 | return getBuckets() + getNumBuckets(); |
| 534 | } |
| 535 | |
| 536 | void grow(unsigned AtLeast) { |
| 537 | static_cast<DerivedT *>(this)->grow(AtLeast); |
| 538 | } |
| 539 | |
| 540 | void shrink_and_clear() { |
| 541 | static_cast<DerivedT *>(this)->shrink_and_clear(); |
| 542 | } |
| 543 | |
| 544 | template <typename KeyArg, typename... ValueArgs> |
| 545 | BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key, |
| 546 | ValueArgs &&... Values) { |
| 547 | TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket); |
| 548 | |
| 549 | TheBucket->getFirst() = std::forward<KeyArg>(Key); |
| 550 | ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...); |
| 551 | return TheBucket; |
| 552 | } |
| 553 | |
| 554 | template <typename LookupKeyT> |
| 555 | BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key, |
| 556 | ValueT &&Value, LookupKeyT &Lookup) { |
| 557 | TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket); |
| 558 | |
| 559 | TheBucket->getFirst() = std::move(Key); |
| 560 | ::new (&TheBucket->getSecond()) ValueT(std::move(Value)); |
| 561 | return TheBucket; |
| 562 | } |
| 563 | |
| 564 | template <typename LookupKeyT> |
| 565 | BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup, |
| 566 | BucketT *TheBucket) { |
| 567 | incrementEpoch(); |
| 568 | |
| 569 | // If the load of the hash table is more than 3/4, or if fewer than 1/8 of |
| 570 | // the buckets are empty (meaning that many are filled with tombstones), |
| 571 | // grow the table. |
| 572 | // |
| 573 | // The later case is tricky. For example, if we had one empty bucket with |
| 574 | // tons of tombstones, failing lookups (e.g. for insertion) would have to |
| 575 | // probe almost the entire table until it found the empty bucket. If the |
| 576 | // table completely filled with tombstones, no lookup would ever succeed, |
| 577 | // causing infinite loops in lookup. |
| 578 | unsigned NewNumEntries = getNumEntries() + 1; |
| 579 | unsigned NumBuckets = getNumBuckets(); |
| 580 | if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)__builtin_expect((bool)(NewNumEntries * 4 >= NumBuckets * 3 ), false)) { |
| 581 | this->grow(NumBuckets * 2); |
| 582 | LookupBucketFor(Lookup, TheBucket); |
| 583 | NumBuckets = getNumBuckets(); |
| 584 | } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones ()) <= NumBuckets/8), false) |
| 585 | NumBuckets/8)__builtin_expect((bool)(NumBuckets-(NewNumEntries+getNumTombstones ()) <= NumBuckets/8), false)) { |
| 586 | this->grow(NumBuckets); |
| 587 | LookupBucketFor(Lookup, TheBucket); |
| 588 | } |
| 589 | assert(TheBucket)((void)0); |
| 590 | |
| 591 | // Only update the state after we've grown our bucket space appropriately |
| 592 | // so that when growing buckets we have self-consistent entry count. |
| 593 | incrementNumEntries(); |
| 594 | |
| 595 | // If we are writing over a tombstone, remember this. |
| 596 | const KeyT EmptyKey = getEmptyKey(); |
| 597 | if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey)) |
| 598 | decrementNumTombstones(); |
| 599 | |
| 600 | return TheBucket; |
| 601 | } |
| 602 | |
| 603 | /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in |
| 604 | /// FoundBucket. If the bucket contains the key and a value, this returns |
| 605 | /// true, otherwise it returns a bucket with an empty marker or tombstone and |
| 606 | /// returns false. |
| 607 | template<typename LookupKeyT> |
| 608 | bool LookupBucketFor(const LookupKeyT &Val, |
| 609 | const BucketT *&FoundBucket) const { |
| 610 | const BucketT *BucketsPtr = getBuckets(); |
| 611 | const unsigned NumBuckets = getNumBuckets(); |
| 612 | |
| 613 | if (NumBuckets == 0) { |
| 614 | FoundBucket = nullptr; |
| 615 | return false; |
| 616 | } |
| 617 | |
| 618 | // FoundTombstone - Keep track of whether we find a tombstone while probing. |
| 619 | const BucketT *FoundTombstone = nullptr; |
| 620 | const KeyT EmptyKey = getEmptyKey(); |
| 621 | const KeyT TombstoneKey = getTombstoneKey(); |
| 622 | assert(!KeyInfoT::isEqual(Val, EmptyKey) &&((void)0) |
| 623 | !KeyInfoT::isEqual(Val, TombstoneKey) &&((void)0) |
| 624 | "Empty/Tombstone value shouldn't be inserted into map!")((void)0); |
| 625 | |
| 626 | unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); |
| 627 | unsigned ProbeAmt = 1; |
| 628 | while (true) { |
| 629 | const BucketT *ThisBucket = BucketsPtr + BucketNo; |
| 630 | // Found Val's bucket? If so, return it. |
| 631 | if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))__builtin_expect((bool)(KeyInfoT::isEqual(Val, ThisBucket-> getFirst())), true)) { |
| 632 | FoundBucket = ThisBucket; |
| 633 | return true; |
| 634 | } |
| 635 | |
| 636 | // If we found an empty bucket, the key doesn't exist in the set. |
| 637 | // Insert it and return the default value. |
| 638 | if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))__builtin_expect((bool)(KeyInfoT::isEqual(ThisBucket->getFirst (), EmptyKey)), true)) { |
| 639 | // If we've already seen a tombstone while probing, fill it in instead |
| 640 | // of the empty bucket we eventually probed to. |
| 641 | FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; |
| 642 | return false; |
| 643 | } |
| 644 | |
| 645 | // If this is a tombstone, remember it. If Val ends up not in the map, we |
| 646 | // prefer to return it than something that would require more probing. |
| 647 | if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) && |
| 648 | !FoundTombstone) |
| 649 | FoundTombstone = ThisBucket; // Remember the first tombstone found. |
| 650 | |
| 651 | // Otherwise, it's a hash collision or a tombstone, continue quadratic |
| 652 | // probing. |
| 653 | BucketNo += ProbeAmt++; |
| 654 | BucketNo &= (NumBuckets-1); |
| 655 | } |
| 656 | } |
| 657 | |
| 658 | template <typename LookupKeyT> |
| 659 | bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { |
| 660 | const BucketT *ConstFoundBucket; |
| 661 | bool Result = const_cast<const DenseMapBase *>(this) |
| 662 | ->LookupBucketFor(Val, ConstFoundBucket); |
| 663 | FoundBucket = const_cast<BucketT *>(ConstFoundBucket); |
| 664 | return Result; |
| 665 | } |
| 666 | |
| 667 | public: |
| 668 | /// Return the approximate size (in bytes) of the actual map. |
| 669 | /// This is just the raw memory used by DenseMap. |
| 670 | /// If entries are pointers to objects, the size of the referenced objects |
| 671 | /// are not included. |
| 672 | size_t getMemorySize() const { |
| 673 | return getNumBuckets() * sizeof(BucketT); |
| 674 | } |
| 675 | }; |
| 676 | |
| 677 | /// Equality comparison for DenseMap. |
| 678 | /// |
| 679 | /// Iterates over elements of LHS confirming that each (key, value) pair in LHS |
| 680 | /// is also in RHS, and that no additional pairs are in RHS. |
| 681 | /// Equivalent to N calls to RHS.find and N value comparisons. Amortized |
| 682 | /// complexity is linear, worst case is O(N^2) (if every hash collides). |
| 683 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
| 684 | typename BucketT> |
| 685 | bool operator==( |
| 686 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS, |
| 687 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) { |
| 688 | if (LHS.size() != RHS.size()) |
| 689 | return false; |
| 690 | |
| 691 | for (auto &KV : LHS) { |
| 692 | auto I = RHS.find(KV.first); |
| 693 | if (I == RHS.end() || I->second != KV.second) |
| 694 | return false; |
| 695 | } |
| 696 | |
| 697 | return true; |
| 698 | } |
| 699 | |
| 700 | /// Inequality comparison for DenseMap. |
| 701 | /// |
| 702 | /// Equivalent to !(LHS == RHS). See operator== for performance notes. |
| 703 | template <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT, |
| 704 | typename BucketT> |
| 705 | bool operator!=( |
| 706 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS, |
| 707 | const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) { |
| 708 | return !(LHS == RHS); |
| 709 | } |
| 710 | |
| 711 | template <typename KeyT, typename ValueT, |
| 712 | typename KeyInfoT = DenseMapInfo<KeyT>, |
| 713 | typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>> |
| 714 | class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>, |
| 715 | KeyT, ValueT, KeyInfoT, BucketT> { |
| 716 | friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
| 717 | |
| 718 | // Lift some types from the dependent base class into this class for |
| 719 | // simplicity of referring to them. |
| 720 | using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
| 721 | |
| 722 | BucketT *Buckets; |
| 723 | unsigned NumEntries; |
| 724 | unsigned NumTombstones; |
| 725 | unsigned NumBuckets; |
| 726 | |
| 727 | public: |
| 728 | /// Create a DenseMap with an optional \p InitialReserve that guarantee that |
| 729 | /// this number of elements can be inserted in the map without grow() |
| 730 | explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); } |
| 731 | |
| 732 | DenseMap(const DenseMap &other) : BaseT() { |
| 733 | init(0); |
| 734 | copyFrom(other); |
| 735 | } |
| 736 | |
| 737 | DenseMap(DenseMap &&other) : BaseT() { |
| 738 | init(0); |
| 739 | swap(other); |
| 740 | } |
| 741 | |
| 742 | template<typename InputIt> |
| 743 | DenseMap(const InputIt &I, const InputIt &E) { |
| 744 | init(std::distance(I, E)); |
| 745 | this->insert(I, E); |
| 746 | } |
| 747 | |
| 748 | DenseMap(std::initializer_list<typename BaseT::value_type> Vals) { |
| 749 | init(Vals.size()); |
| 750 | this->insert(Vals.begin(), Vals.end()); |
| 751 | } |
| 752 | |
| 753 | ~DenseMap() { |
| 754 | this->destroyAll(); |
| 755 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
| 756 | } |
| 757 | |
| 758 | void swap(DenseMap& RHS) { |
| 759 | this->incrementEpoch(); |
| 760 | RHS.incrementEpoch(); |
| 761 | std::swap(Buckets, RHS.Buckets); |
| 762 | std::swap(NumEntries, RHS.NumEntries); |
| 763 | std::swap(NumTombstones, RHS.NumTombstones); |
| 764 | std::swap(NumBuckets, RHS.NumBuckets); |
| 765 | } |
| 766 | |
| 767 | DenseMap& operator=(const DenseMap& other) { |
| 768 | if (&other != this) |
| 769 | copyFrom(other); |
| 770 | return *this; |
| 771 | } |
| 772 | |
| 773 | DenseMap& operator=(DenseMap &&other) { |
| 774 | this->destroyAll(); |
| 775 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
| 776 | init(0); |
| 777 | swap(other); |
| 778 | return *this; |
| 779 | } |
| 780 | |
| 781 | void copyFrom(const DenseMap& other) { |
| 782 | this->destroyAll(); |
| 783 | deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); |
| 784 | if (allocateBuckets(other.NumBuckets)) { |
| 785 | this->BaseT::copyFrom(other); |
| 786 | } else { |
| 787 | NumEntries = 0; |
| 788 | NumTombstones = 0; |
| 789 | } |
| 790 | } |
| 791 | |
| 792 | void init(unsigned InitNumEntries) { |
| 793 | auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries); |
| 794 | if (allocateBuckets(InitBuckets)) { |
| 795 | this->BaseT::initEmpty(); |
| 796 | } else { |
| 797 | NumEntries = 0; |
| 798 | NumTombstones = 0; |
| 799 | } |
| 800 | } |
| 801 | |
| 802 | void grow(unsigned AtLeast) { |
| 803 | unsigned OldNumBuckets = NumBuckets; |
| 804 | BucketT *OldBuckets = Buckets; |
| 805 | |
| 806 | allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1)))); |
| 807 | assert(Buckets)((void)0); |
| 808 | if (!OldBuckets) { |
| 809 | this->BaseT::initEmpty(); |
| 810 | return; |
| 811 | } |
| 812 | |
| 813 | this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); |
| 814 | |
| 815 | // Free the old table. |
| 816 | deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets, |
| 817 | alignof(BucketT)); |
| 818 | } |
| 819 | |
| 820 | void shrink_and_clear() { |
| 821 | unsigned OldNumBuckets = NumBuckets; |
| 822 | unsigned OldNumEntries = NumEntries; |
| 823 | this->destroyAll(); |
| 824 | |
| 825 | // Reduce the number of buckets. |
| 826 | unsigned NewNumBuckets = 0; |
| 827 | if (OldNumEntries) |
| 828 | NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); |
| 829 | if (NewNumBuckets == NumBuckets) { |
| 830 | this->BaseT::initEmpty(); |
| 831 | return; |
| 832 | } |
| 833 | |
| 834 | deallocate_buffer(Buckets, sizeof(BucketT) * OldNumBuckets, |
| 835 | alignof(BucketT)); |
| 836 | init(NewNumBuckets); |
| 837 | } |
| 838 | |
| 839 | private: |
| 840 | unsigned getNumEntries() const { |
| 841 | return NumEntries; |
| 842 | } |
| 843 | |
| 844 | void setNumEntries(unsigned Num) { |
| 845 | NumEntries = Num; |
| 846 | } |
| 847 | |
| 848 | unsigned getNumTombstones() const { |
| 849 | return NumTombstones; |
| 850 | } |
| 851 | |
| 852 | void setNumTombstones(unsigned Num) { |
| 853 | NumTombstones = Num; |
| 854 | } |
| 855 | |
| 856 | BucketT *getBuckets() const { |
| 857 | return Buckets; |
| 858 | } |
| 859 | |
| 860 | unsigned getNumBuckets() const { |
| 861 | return NumBuckets; |
| 862 | } |
| 863 | |
| 864 | bool allocateBuckets(unsigned Num) { |
| 865 | NumBuckets = Num; |
| 866 | if (NumBuckets == 0) { |
| 867 | Buckets = nullptr; |
| 868 | return false; |
| 869 | } |
| 870 | |
| 871 | Buckets = static_cast<BucketT *>( |
| 872 | allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT))); |
| 873 | return true; |
| 874 | } |
| 875 | }; |
| 876 | |
| 877 | template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4, |
| 878 | typename KeyInfoT = DenseMapInfo<KeyT>, |
| 879 | typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>> |
| 880 | class SmallDenseMap |
| 881 | : public DenseMapBase< |
| 882 | SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT, |
| 883 | ValueT, KeyInfoT, BucketT> { |
| 884 | friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
| 885 | |
| 886 | // Lift some types from the dependent base class into this class for |
| 887 | // simplicity of referring to them. |
| 888 | using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>; |
| 889 | |
| 890 | static_assert(isPowerOf2_64(InlineBuckets), |
| 891 | "InlineBuckets must be a power of 2."); |
| 892 | |
| 893 | unsigned Small : 1; |
| 894 | unsigned NumEntries : 31; |
| 895 | unsigned NumTombstones; |
| 896 | |
| 897 | struct LargeRep { |
| 898 | BucketT *Buckets; |
| 899 | unsigned NumBuckets; |
| 900 | }; |
| 901 | |
| 902 | /// A "union" of an inline bucket array and the struct representing |
| 903 | /// a large bucket. This union will be discriminated by the 'Small' bit. |
| 904 | AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; |
| 905 | |
| 906 | public: |
| 907 | explicit SmallDenseMap(unsigned NumInitBuckets = 0) { |
| 908 | init(NumInitBuckets); |
| 909 | } |
| 910 | |
| 911 | SmallDenseMap(const SmallDenseMap &other) : BaseT() { |
| 912 | init(0); |
| 913 | copyFrom(other); |
| 914 | } |
| 915 | |
| 916 | SmallDenseMap(SmallDenseMap &&other) : BaseT() { |
| 917 | init(0); |
| 918 | swap(other); |
| 919 | } |
| 920 | |
| 921 | template<typename InputIt> |
| 922 | SmallDenseMap(const InputIt &I, const InputIt &E) { |
| 923 | init(NextPowerOf2(std::distance(I, E))); |
| 924 | this->insert(I, E); |
| 925 | } |
| 926 | |
| 927 | SmallDenseMap(std::initializer_list<typename BaseT::value_type> Vals) |
| 928 | : SmallDenseMap(Vals.begin(), Vals.end()) {} |
| 929 | |
| 930 | ~SmallDenseMap() { |
| 931 | this->destroyAll(); |
| 932 | deallocateBuckets(); |
| 933 | } |
| 934 | |
| 935 | void swap(SmallDenseMap& RHS) { |
| 936 | unsigned TmpNumEntries = RHS.NumEntries; |
| 937 | RHS.NumEntries = NumEntries; |
| 938 | NumEntries = TmpNumEntries; |
| 939 | std::swap(NumTombstones, RHS.NumTombstones); |
| 940 | |
| 941 | const KeyT EmptyKey = this->getEmptyKey(); |
| 942 | const KeyT TombstoneKey = this->getTombstoneKey(); |
| 943 | if (Small && RHS.Small) { |
| 944 | // If we're swapping inline bucket arrays, we have to cope with some of |
| 945 | // the tricky bits of DenseMap's storage system: the buckets are not |
| 946 | // fully initialized. Thus we swap every key, but we may have |
| 947 | // a one-directional move of the value. |
| 948 | for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { |
| 949 | BucketT *LHSB = &getInlineBuckets()[i], |
| 950 | *RHSB = &RHS.getInlineBuckets()[i]; |
| 951 | bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) && |
| 952 | !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey)); |
| 953 | bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) && |
| 954 | !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey)); |
| 955 | if (hasLHSValue && hasRHSValue) { |
| 956 | // Swap together if we can... |
| 957 | std::swap(*LHSB, *RHSB); |
| 958 | continue; |
| 959 | } |
| 960 | // Swap separately and handle any asymmetry. |
| 961 | std::swap(LHSB->getFirst(), RHSB->getFirst()); |
| 962 | if (hasLHSValue) { |
| 963 | ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond())); |
| 964 | LHSB->getSecond().~ValueT(); |
| 965 | } else if (hasRHSValue) { |
| 966 | ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond())); |
| 967 | RHSB->getSecond().~ValueT(); |
| 968 | } |
| 969 | } |
| 970 | return; |
| 971 | } |
| 972 | if (!Small && !RHS.Small) { |
| 973 | std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); |
| 974 | std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); |
| 975 | return; |
| 976 | } |
| 977 | |
| 978 | SmallDenseMap &SmallSide = Small ? *this : RHS; |
| 979 | SmallDenseMap &LargeSide = Small ? RHS : *this; |
| 980 | |
| 981 | // First stash the large side's rep and move the small side across. |
| 982 | LargeRep TmpRep = std::move(*LargeSide.getLargeRep()); |
| 983 | LargeSide.getLargeRep()->~LargeRep(); |
| 984 | LargeSide.Small = true; |
| 985 | // This is similar to the standard move-from-old-buckets, but the bucket |
| 986 | // count hasn't actually rotated in this case. So we have to carefully |
| 987 | // move construct the keys and values into their new locations, but there |
| 988 | // is no need to re-hash things. |
| 989 | for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { |
| 990 | BucketT *NewB = &LargeSide.getInlineBuckets()[i], |
| 991 | *OldB = &SmallSide.getInlineBuckets()[i]; |
| 992 | ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst())); |
| 993 | OldB->getFirst().~KeyT(); |
| 994 | if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) && |
| 995 | !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) { |
| 996 | ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond())); |
| 997 | OldB->getSecond().~ValueT(); |
| 998 | } |
| 999 | } |
| 1000 | |
| 1001 | // The hard part of moving the small buckets across is done, just move |
| 1002 | // the TmpRep into its new home. |
| 1003 | SmallSide.Small = false; |
| 1004 | new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep)); |
| 1005 | } |
| 1006 | |
| 1007 | SmallDenseMap& operator=(const SmallDenseMap& other) { |
| 1008 | if (&other != this) |
| 1009 | copyFrom(other); |
| 1010 | return *this; |
| 1011 | } |
| 1012 | |
| 1013 | SmallDenseMap& operator=(SmallDenseMap &&other) { |
| 1014 | this->destroyAll(); |
| 1015 | deallocateBuckets(); |
| 1016 | init(0); |
| 1017 | swap(other); |
| 1018 | return *this; |
| 1019 | } |
| 1020 | |
| 1021 | void copyFrom(const SmallDenseMap& other) { |
| 1022 | this->destroyAll(); |
| 1023 | deallocateBuckets(); |
| 1024 | Small = true; |
| 1025 | if (other.getNumBuckets() > InlineBuckets) { |
| 1026 | Small = false; |
| 1027 | new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets())); |
| 1028 | } |
| 1029 | this->BaseT::copyFrom(other); |
| 1030 | } |
| 1031 | |
| 1032 | void init(unsigned InitBuckets) { |
| 1033 | Small = true; |
| 1034 | if (InitBuckets > InlineBuckets) { |
| 1035 | Small = false; |
| 1036 | new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); |
| 1037 | } |
| 1038 | this->BaseT::initEmpty(); |
| 1039 | } |
| 1040 | |
| 1041 | void grow(unsigned AtLeast) { |
| 1042 | if (AtLeast > InlineBuckets) |
| 1043 | AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); |
| 1044 | |
| 1045 | if (Small) { |
| 1046 | // First move the inline buckets into a temporary storage. |
| 1047 | AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; |
| 1048 | BucketT *TmpBegin = reinterpret_cast<BucketT *>(&TmpStorage); |
| 1049 | BucketT *TmpEnd = TmpBegin; |
| 1050 | |
| 1051 | // Loop over the buckets, moving non-empty, non-tombstones into the |
| 1052 | // temporary storage. Have the loop move the TmpEnd forward as it goes. |
| 1053 | const KeyT EmptyKey = this->getEmptyKey(); |
| 1054 | const KeyT TombstoneKey = this->getTombstoneKey(); |
| 1055 | for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { |
| 1056 | if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) && |
| 1057 | !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { |
| 1058 | assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&((void)0) |
| 1059 | "Too many inline buckets!")((void)0); |
| 1060 | ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst())); |
| 1061 | ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond())); |
| 1062 | ++TmpEnd; |
| 1063 | P->getSecond().~ValueT(); |
| 1064 | } |
| 1065 | P->getFirst().~KeyT(); |
| 1066 | } |
| 1067 | |
| 1068 | // AtLeast == InlineBuckets can happen if there are many tombstones, |
| 1069 | // and grow() is used to remove them. Usually we always switch to the |
| 1070 | // large rep here. |
| 1071 | if (AtLeast > InlineBuckets) { |
| 1072 | Small = false; |
| 1073 | new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); |
| 1074 | } |
| 1075 | this->moveFromOldBuckets(TmpBegin, TmpEnd); |
| 1076 | return; |
| 1077 | } |
| 1078 | |
| 1079 | LargeRep OldRep = std::move(*getLargeRep()); |
| 1080 | getLargeRep()->~LargeRep(); |
| 1081 | if (AtLeast <= InlineBuckets) { |
| 1082 | Small = true; |
| 1083 | } else { |
| 1084 | new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); |
| 1085 | } |
| 1086 | |
| 1087 | this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); |
| 1088 | |
| 1089 | // Free the old table. |
| 1090 | deallocate_buffer(OldRep.Buckets, sizeof(BucketT) * OldRep.NumBuckets, |
| 1091 | alignof(BucketT)); |
| 1092 | } |
| 1093 | |
| 1094 | void shrink_and_clear() { |
| 1095 | unsigned OldSize = this->size(); |
| 1096 | this->destroyAll(); |
| 1097 | |
| 1098 | // Reduce the number of buckets. |
| 1099 | unsigned NewNumBuckets = 0; |
| 1100 | if (OldSize) { |
| 1101 | NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); |
| 1102 | if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) |
| 1103 | NewNumBuckets = 64; |
| 1104 | } |
| 1105 | if ((Small && NewNumBuckets <= InlineBuckets) || |
| 1106 | (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { |
| 1107 | this->BaseT::initEmpty(); |
| 1108 | return; |
| 1109 | } |
| 1110 | |
| 1111 | deallocateBuckets(); |
| 1112 | init(NewNumBuckets); |
| 1113 | } |
| 1114 | |
| 1115 | private: |
| 1116 | unsigned getNumEntries() const { |
| 1117 | return NumEntries; |
| 1118 | } |
| 1119 | |
| 1120 | void setNumEntries(unsigned Num) { |
| 1121 | // NumEntries is hardcoded to be 31 bits wide. |
| 1122 | assert(Num < (1U << 31) && "Cannot support more than 1<<31 entries")((void)0); |
| 1123 | NumEntries = Num; |
| 1124 | } |
| 1125 | |
| 1126 | unsigned getNumTombstones() const { |
| 1127 | return NumTombstones; |
| 1128 | } |
| 1129 | |
| 1130 | void setNumTombstones(unsigned Num) { |
| 1131 | NumTombstones = Num; |
| 1132 | } |
| 1133 | |
| 1134 | const BucketT *getInlineBuckets() const { |
| 1135 | assert(Small)((void)0); |
| 1136 | // Note that this cast does not violate aliasing rules as we assert that |
| 1137 | // the memory's dynamic type is the small, inline bucket buffer, and the |
| 1138 | // 'storage' is a POD containing a char buffer. |
| 1139 | return reinterpret_cast<const BucketT *>(&storage); |
| 1140 | } |
| 1141 | |
| 1142 | BucketT *getInlineBuckets() { |
| 1143 | return const_cast<BucketT *>( |
| 1144 | const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); |
| 1145 | } |
| 1146 | |
| 1147 | const LargeRep *getLargeRep() const { |
| 1148 | assert(!Small)((void)0); |
| 1149 | // Note, same rule about aliasing as with getInlineBuckets. |
| 1150 | return reinterpret_cast<const LargeRep *>(&storage); |
| 1151 | } |
| 1152 | |
| 1153 | LargeRep *getLargeRep() { |
| 1154 | return const_cast<LargeRep *>( |
| 1155 | const_cast<const SmallDenseMap *>(this)->getLargeRep()); |
| 1156 | } |
| 1157 | |
| 1158 | const BucketT *getBuckets() const { |
| 1159 | return Small ? getInlineBuckets() : getLargeRep()->Buckets; |
| 1160 | } |
| 1161 | |
| 1162 | BucketT *getBuckets() { |
| 1163 | return const_cast<BucketT *>( |
| 1164 | const_cast<const SmallDenseMap *>(this)->getBuckets()); |
| 1165 | } |
| 1166 | |
| 1167 | unsigned getNumBuckets() const { |
| 1168 | return Small ? InlineBuckets : getLargeRep()->NumBuckets; |
| 1169 | } |
| 1170 | |
| 1171 | void deallocateBuckets() { |
| 1172 | if (Small) |
| 1173 | return; |
| 1174 | |
| 1175 | deallocate_buffer(getLargeRep()->Buckets, |
| 1176 | sizeof(BucketT) * getLargeRep()->NumBuckets, |
| 1177 | alignof(BucketT)); |
| 1178 | getLargeRep()->~LargeRep(); |
| 1179 | } |
| 1180 | |
| 1181 | LargeRep allocateBuckets(unsigned Num) { |
| 1182 | assert(Num > InlineBuckets && "Must allocate more buckets than are inline")((void)0); |
| 1183 | LargeRep Rep = {static_cast<BucketT *>(allocate_buffer( |
| 1184 | sizeof(BucketT) * Num, alignof(BucketT))), |
| 1185 | Num}; |
| 1186 | return Rep; |
| 1187 | } |
| 1188 | }; |
| 1189 | |
| 1190 | template <typename KeyT, typename ValueT, typename KeyInfoT, typename Bucket, |
| 1191 | bool IsConst> |
| 1192 | class DenseMapIterator : DebugEpochBase::HandleBase { |
| 1193 | friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, true>; |
| 1194 | friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, false>; |
| 1195 | |
| 1196 | public: |
| 1197 | using difference_type = ptrdiff_t; |
| 1198 | using value_type = |
| 1199 | typename std::conditional<IsConst, const Bucket, Bucket>::type; |
| 1200 | using pointer = value_type *; |
| 1201 | using reference = value_type &; |
| 1202 | using iterator_category = std::forward_iterator_tag; |
| 1203 | |
| 1204 | private: |
| 1205 | pointer Ptr = nullptr; |
| 1206 | pointer End = nullptr; |
| 1207 | |
| 1208 | public: |
| 1209 | DenseMapIterator() = default; |
| 1210 | |
| 1211 | DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, |
| 1212 | bool NoAdvance = false) |
| 1213 | : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { |
| 1214 | assert(isHandleInSync() && "invalid construction!")((void)0); |
| 1215 | |
| 1216 | if (NoAdvance) return; |
| 1217 | if (shouldReverseIterate<KeyT>()) { |
| 1218 | RetreatPastEmptyBuckets(); |
| 1219 | return; |
| 1220 | } |
| 1221 | AdvancePastEmptyBuckets(); |
| 1222 | } |
| 1223 | |
| 1224 | // Converting ctor from non-const iterators to const iterators. SFINAE'd out |
| 1225 | // for const iterator destinations so it doesn't end up as a user defined copy |
| 1226 | // constructor. |
| 1227 | template <bool IsConstSrc, |
| 1228 | typename = std::enable_if_t<!IsConstSrc && IsConst>> |
| 1229 | DenseMapIterator( |
| 1230 | const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I) |
| 1231 | : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {} |
| 1232 | |
| 1233 | reference operator*() const { |
| 1234 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
| 1235 | assert(Ptr != End && "dereferencing end() iterator")((void)0); |
| 1236 | if (shouldReverseIterate<KeyT>()) |
| 1237 | return Ptr[-1]; |
| 1238 | return *Ptr; |
| 1239 | } |
| 1240 | pointer operator->() const { |
| 1241 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
| 1242 | assert(Ptr != End && "dereferencing end() iterator")((void)0); |
| 1243 | if (shouldReverseIterate<KeyT>()) |
| 1244 | return &(Ptr[-1]); |
| 1245 | return Ptr; |
| 1246 | } |
| 1247 | |
| 1248 | friend bool operator==(const DenseMapIterator &LHS, |
| 1249 | const DenseMapIterator &RHS) { |
| 1250 | assert((!LHS.Ptr || LHS.isHandleInSync()) && "handle not in sync!")((void)0); |
| 1251 | assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!")((void)0); |
| 1252 | assert(LHS.getEpochAddress() == RHS.getEpochAddress() &&((void)0) |
| 1253 | "comparing incomparable iterators!")((void)0); |
| 1254 | return LHS.Ptr == RHS.Ptr; |
| 1255 | } |
| 1256 | |
| 1257 | friend bool operator!=(const DenseMapIterator &LHS, |
| 1258 | const DenseMapIterator &RHS) { |
| 1259 | return !(LHS == RHS); |
| 1260 | } |
| 1261 | |
| 1262 | inline DenseMapIterator& operator++() { // Preincrement |
| 1263 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
| 1264 | assert(Ptr != End && "incrementing end() iterator")((void)0); |
| 1265 | if (shouldReverseIterate<KeyT>()) { |
| 1266 | --Ptr; |
| 1267 | RetreatPastEmptyBuckets(); |
| 1268 | return *this; |
| 1269 | } |
| 1270 | ++Ptr; |
| 1271 | AdvancePastEmptyBuckets(); |
| 1272 | return *this; |
| 1273 | } |
| 1274 | DenseMapIterator operator++(int) { // Postincrement |
| 1275 | assert(isHandleInSync() && "invalid iterator access!")((void)0); |
| 1276 | DenseMapIterator tmp = *this; ++*this; return tmp; |
| 1277 | } |
| 1278 | |
| 1279 | private: |
| 1280 | void AdvancePastEmptyBuckets() { |
| 1281 | assert(Ptr <= End)((void)0); |
| 1282 | const KeyT Empty = KeyInfoT::getEmptyKey(); |
| 1283 | const KeyT Tombstone = KeyInfoT::getTombstoneKey(); |
| 1284 | |
| 1285 | while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) || |
| 1286 | KeyInfoT::isEqual(Ptr->getFirst(), Tombstone))) |
| 1287 | ++Ptr; |
| 1288 | } |
| 1289 | |
| 1290 | void RetreatPastEmptyBuckets() { |
| 1291 | assert(Ptr >= End)((void)0); |
| 1292 | const KeyT Empty = KeyInfoT::getEmptyKey(); |
| 1293 | const KeyT Tombstone = KeyInfoT::getTombstoneKey(); |
| 1294 | |
| 1295 | while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) || |
| 1296 | KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone))) |
| 1297 | --Ptr; |
| 1298 | } |
| 1299 | }; |
| 1300 | |
| 1301 | template <typename KeyT, typename ValueT, typename KeyInfoT> |
| 1302 | inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { |
| 1303 | return X.getMemorySize(); |
| 1304 | } |
| 1305 | |
| 1306 | } // end namespace llvm |
| 1307 | |
| 1308 | #endif // LLVM_ADT_DENSEMAP_H |