1 //===- ExecutionDepsFix.cpp - Fix execution dependecy issues ----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains the execution dependency fix pass. 11 // 12 // Some X86 SSE instructions like mov, and, or, xor are available in different 13 // variants for different operand types. These variant instructions are 14 // equivalent, but on Nehalem and newer cpus there is extra latency 15 // transferring data between integer and floating point domains. ARM cores 16 // have similar issues when they are configured with both VFP and NEON 17 // pipelines. 18 // 19 // This pass changes the variant instructions to minimize domain crossings. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #include "llvm/CodeGen/Passes.h" 24 #include "llvm/ADT/PostOrderIterator.h" 25 #include "llvm/CodeGen/LivePhysRegs.h" 26 #include "llvm/CodeGen/MachineFunctionPass.h" 27 #include "llvm/CodeGen/MachineRegisterInfo.h" 28 #include "llvm/Support/Allocator.h" 29 #include "llvm/Support/Debug.h" 30 #include "llvm/Support/raw_ostream.h" 31 #include "llvm/Target/TargetInstrInfo.h" 32 #include "llvm/Target/TargetMachine.h" 33 using namespace llvm; 34 35 #define DEBUG_TYPE "execution-fix" 36 37 /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track 38 /// of execution domains. 39 /// 40 /// An open DomainValue represents a set of instructions that can still switch 41 /// execution domain. Multiple registers may refer to the same open 42 /// DomainValue - they will eventually be collapsed to the same execution 43 /// domain. 44 /// 45 /// A collapsed DomainValue represents a single register that has been forced 46 /// into one of more execution domains. There is a separate collapsed 47 /// DomainValue for each register, but it may contain multiple execution 48 /// domains. A register value is initially created in a single execution 49 /// domain, but if we were forced to pay the penalty of a domain crossing, we 50 /// keep track of the fact that the register is now available in multiple 51 /// domains. 52 namespace { 53 struct DomainValue { 54 // Basic reference counting. 55 unsigned Refs; 56 57 // Bitmask of available domains. For an open DomainValue, it is the still 58 // possible domains for collapsing. For a collapsed DomainValue it is the 59 // domains where the register is available for free. 60 unsigned AvailableDomains; 61 62 // Pointer to the next DomainValue in a chain. When two DomainValues are 63 // merged, Victim.Next is set to point to Victor, so old DomainValue 64 // references can be updated by following the chain. 65 DomainValue *Next; 66 67 // Twiddleable instructions using or defining these registers. 68 SmallVector<MachineInstr*, 8> Instrs; 69 70 // A collapsed DomainValue has no instructions to twiddle - it simply keeps 71 // track of the domains where the registers are already available. 72 bool isCollapsed() const { return Instrs.empty(); } 73 74 // Is domain available? 75 bool hasDomain(unsigned domain) const { 76 return AvailableDomains & (1u << domain); 77 } 78 79 // Mark domain as available. 80 void addDomain(unsigned domain) { 81 AvailableDomains |= 1u << domain; 82 } 83 84 // Restrict to a single domain available. 85 void setSingleDomain(unsigned domain) { 86 AvailableDomains = 1u << domain; 87 } 88 89 // Return bitmask of domains that are available and in mask. 90 unsigned getCommonDomains(unsigned mask) const { 91 return AvailableDomains & mask; 92 } 93 94 // First domain available. 95 unsigned getFirstDomain() const { 96 return countTrailingZeros(AvailableDomains); 97 } 98 99 DomainValue() : Refs(0) { clear(); } 100 101 // Clear this DomainValue and point to next which has all its data. 102 void clear() { 103 AvailableDomains = 0; 104 Next = nullptr; 105 Instrs.clear(); 106 } 107 }; 108 } 109 110 namespace { 111 /// LiveReg - Information about a live register. 112 struct LiveReg { 113 /// Value currently in this register, or NULL when no value is being tracked. 114 /// This counts as a DomainValue reference. 115 DomainValue *Value; 116 117 /// Instruction that defined this register, relative to the beginning of the 118 /// current basic block. When a LiveReg is used to represent a live-out 119 /// register, this value is relative to the end of the basic block, so it 120 /// will be a negative number. 121 int Def; 122 }; 123 } // anonynous namespace 124 125 namespace { 126 class ExeDepsFix : public MachineFunctionPass { 127 static char ID; 128 SpecificBumpPtrAllocator<DomainValue> Allocator; 129 SmallVector<DomainValue*,16> Avail; 130 131 const TargetRegisterClass *const RC; 132 MachineFunction *MF; 133 const TargetInstrInfo *TII; 134 const TargetRegisterInfo *TRI; 135 std::vector<int> AliasMap; 136 const unsigned NumRegs; 137 LiveReg *LiveRegs; 138 typedef DenseMap<MachineBasicBlock*, LiveReg*> LiveOutMap; 139 LiveOutMap LiveOuts; 140 141 /// List of undefined register reads in this block in forward order. 142 std::vector<std::pair<MachineInstr*, unsigned> > UndefReads; 143 144 /// Storage for register unit liveness. 145 LivePhysRegs LiveRegSet; 146 147 /// Current instruction number. 148 /// The first instruction in each basic block is 0. 149 int CurInstr; 150 151 /// True when the current block has a predecessor that hasn't been visited 152 /// yet. 153 bool SeenUnknownBackEdge; 154 155 public: 156 ExeDepsFix(const TargetRegisterClass *rc) 157 : MachineFunctionPass(ID), RC(rc), NumRegs(RC->getNumRegs()) {} 158 159 void getAnalysisUsage(AnalysisUsage &AU) const override { 160 AU.setPreservesAll(); 161 MachineFunctionPass::getAnalysisUsage(AU); 162 } 163 164 bool runOnMachineFunction(MachineFunction &MF) override; 165 166 const char *getPassName() const override { 167 return "Execution dependency fix"; 168 } 169 170 private: 171 // Register mapping. 172 int regIndex(unsigned Reg); 173 174 // DomainValue allocation. 175 DomainValue *alloc(int domain = -1); 176 DomainValue *retain(DomainValue *DV) { 177 if (DV) ++DV->Refs; 178 return DV; 179 } 180 void release(DomainValue*); 181 DomainValue *resolve(DomainValue*&); 182 183 // LiveRegs manipulations. 184 void setLiveReg(int rx, DomainValue *DV); 185 void kill(int rx); 186 void force(int rx, unsigned domain); 187 void collapse(DomainValue *dv, unsigned domain); 188 bool merge(DomainValue *A, DomainValue *B); 189 190 void enterBasicBlock(MachineBasicBlock*); 191 void leaveBasicBlock(MachineBasicBlock*); 192 void visitInstr(MachineInstr*); 193 void processDefs(MachineInstr*, bool Kill); 194 void visitSoftInstr(MachineInstr*, unsigned mask); 195 void visitHardInstr(MachineInstr*, unsigned domain); 196 bool shouldBreakDependence(MachineInstr*, unsigned OpIdx, unsigned Pref); 197 void processUndefReads(MachineBasicBlock*); 198 }; 199 } 200 201 char ExeDepsFix::ID = 0; 202 203 /// Translate TRI register number to an index into our smaller tables of 204 /// interesting registers. Return -1 for boring registers. 205 int ExeDepsFix::regIndex(unsigned Reg) { 206 assert(Reg < AliasMap.size() && "Invalid register"); 207 return AliasMap[Reg]; 208 } 209 210 DomainValue *ExeDepsFix::alloc(int domain) { 211 DomainValue *dv = Avail.empty() ? 212 new(Allocator.Allocate()) DomainValue : 213 Avail.pop_back_val(); 214 if (domain >= 0) 215 dv->addDomain(domain); 216 assert(dv->Refs == 0 && "Reference count wasn't cleared"); 217 assert(!dv->Next && "Chained DomainValue shouldn't have been recycled"); 218 return dv; 219 } 220 221 /// release - Release a reference to DV. When the last reference is released, 222 /// collapse if needed. 223 void ExeDepsFix::release(DomainValue *DV) { 224 while (DV) { 225 assert(DV->Refs && "Bad DomainValue"); 226 if (--DV->Refs) 227 return; 228 229 // There are no more DV references. Collapse any contained instructions. 230 if (DV->AvailableDomains && !DV->isCollapsed()) 231 collapse(DV, DV->getFirstDomain()); 232 233 DomainValue *Next = DV->Next; 234 DV->clear(); 235 Avail.push_back(DV); 236 // Also release the next DomainValue in the chain. 237 DV = Next; 238 } 239 } 240 241 /// resolve - Follow the chain of dead DomainValues until a live DomainValue is 242 /// reached. Update the referenced pointer when necessary. 243 DomainValue *ExeDepsFix::resolve(DomainValue *&DVRef) { 244 DomainValue *DV = DVRef; 245 if (!DV || !DV->Next) 246 return DV; 247 248 // DV has a chain. Find the end. 249 do DV = DV->Next; 250 while (DV->Next); 251 252 // Update DVRef to point to DV. 253 retain(DV); 254 release(DVRef); 255 DVRef = DV; 256 return DV; 257 } 258 259 /// Set LiveRegs[rx] = dv, updating reference counts. 260 void ExeDepsFix::setLiveReg(int rx, DomainValue *dv) { 261 assert(unsigned(rx) < NumRegs && "Invalid index"); 262 assert(LiveRegs && "Must enter basic block first."); 263 264 if (LiveRegs[rx].Value == dv) 265 return; 266 if (LiveRegs[rx].Value) 267 release(LiveRegs[rx].Value); 268 LiveRegs[rx].Value = retain(dv); 269 } 270 271 // Kill register rx, recycle or collapse any DomainValue. 272 void ExeDepsFix::kill(int rx) { 273 assert(unsigned(rx) < NumRegs && "Invalid index"); 274 assert(LiveRegs && "Must enter basic block first."); 275 if (!LiveRegs[rx].Value) 276 return; 277 278 release(LiveRegs[rx].Value); 279 LiveRegs[rx].Value = nullptr; 280 } 281 282 /// Force register rx into domain. 283 void ExeDepsFix::force(int rx, unsigned domain) { 284 assert(unsigned(rx) < NumRegs && "Invalid index"); 285 assert(LiveRegs && "Must enter basic block first."); 286 if (DomainValue *dv = LiveRegs[rx].Value) { 287 if (dv->isCollapsed()) 288 dv->addDomain(domain); 289 else if (dv->hasDomain(domain)) 290 collapse(dv, domain); 291 else { 292 // This is an incompatible open DomainValue. Collapse it to whatever and 293 // force the new value into domain. This costs a domain crossing. 294 collapse(dv, dv->getFirstDomain()); 295 assert(LiveRegs[rx].Value && "Not live after collapse?"); 296 LiveRegs[rx].Value->addDomain(domain); 297 } 298 } else { 299 // Set up basic collapsed DomainValue. 300 setLiveReg(rx, alloc(domain)); 301 } 302 } 303 304 /// Collapse open DomainValue into given domain. If there are multiple 305 /// registers using dv, they each get a unique collapsed DomainValue. 306 void ExeDepsFix::collapse(DomainValue *dv, unsigned domain) { 307 assert(dv->hasDomain(domain) && "Cannot collapse"); 308 309 // Collapse all the instructions. 310 while (!dv->Instrs.empty()) 311 TII->setExecutionDomain(dv->Instrs.pop_back_val(), domain); 312 dv->setSingleDomain(domain); 313 314 // If there are multiple users, give them new, unique DomainValues. 315 if (LiveRegs && dv->Refs > 1) 316 for (unsigned rx = 0; rx != NumRegs; ++rx) 317 if (LiveRegs[rx].Value == dv) 318 setLiveReg(rx, alloc(domain)); 319 } 320 321 /// Merge - All instructions and registers in B are moved to A, and B is 322 /// released. 323 bool ExeDepsFix::merge(DomainValue *A, DomainValue *B) { 324 assert(!A->isCollapsed() && "Cannot merge into collapsed"); 325 assert(!B->isCollapsed() && "Cannot merge from collapsed"); 326 if (A == B) 327 return true; 328 // Restrict to the domains that A and B have in common. 329 unsigned common = A->getCommonDomains(B->AvailableDomains); 330 if (!common) 331 return false; 332 A->AvailableDomains = common; 333 A->Instrs.append(B->Instrs.begin(), B->Instrs.end()); 334 335 // Clear the old DomainValue so we won't try to swizzle instructions twice. 336 B->clear(); 337 // All uses of B are referred to A. 338 B->Next = retain(A); 339 340 for (unsigned rx = 0; rx != NumRegs; ++rx) 341 if (LiveRegs[rx].Value == B) 342 setLiveReg(rx, A); 343 return true; 344 } 345 346 // enterBasicBlock - Set up LiveRegs by merging predecessor live-out values. 347 void ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) { 348 // Detect back-edges from predecessors we haven't processed yet. 349 SeenUnknownBackEdge = false; 350 351 // Reset instruction counter in each basic block. 352 CurInstr = 0; 353 354 // Set up UndefReads to track undefined register reads. 355 UndefReads.clear(); 356 LiveRegSet.clear(); 357 358 // Set up LiveRegs to represent registers entering MBB. 359 if (!LiveRegs) 360 LiveRegs = new LiveReg[NumRegs]; 361 362 // Default values are 'nothing happened a long time ago'. 363 for (unsigned rx = 0; rx != NumRegs; ++rx) { 364 LiveRegs[rx].Value = nullptr; 365 LiveRegs[rx].Def = -(1 << 20); 366 } 367 368 // This is the entry block. 369 if (MBB->pred_empty()) { 370 for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(), 371 e = MBB->livein_end(); i != e; ++i) { 372 int rx = regIndex(*i); 373 if (rx < 0) 374 continue; 375 // Treat function live-ins as if they were defined just before the first 376 // instruction. Usually, function arguments are set up immediately 377 // before the call. 378 LiveRegs[rx].Def = -1; 379 } 380 DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": entry\n"); 381 return; 382 } 383 384 // Try to coalesce live-out registers from predecessors. 385 for (MachineBasicBlock::const_pred_iterator pi = MBB->pred_begin(), 386 pe = MBB->pred_end(); pi != pe; ++pi) { 387 LiveOutMap::const_iterator fi = LiveOuts.find(*pi); 388 if (fi == LiveOuts.end()) { 389 SeenUnknownBackEdge = true; 390 continue; 391 } 392 assert(fi->second && "Can't have NULL entries"); 393 394 for (unsigned rx = 0; rx != NumRegs; ++rx) { 395 // Use the most recent predecessor def for each register. 396 LiveRegs[rx].Def = std::max(LiveRegs[rx].Def, fi->second[rx].Def); 397 398 DomainValue *pdv = resolve(fi->second[rx].Value); 399 if (!pdv) 400 continue; 401 if (!LiveRegs[rx].Value) { 402 setLiveReg(rx, pdv); 403 continue; 404 } 405 406 // We have a live DomainValue from more than one predecessor. 407 if (LiveRegs[rx].Value->isCollapsed()) { 408 // We are already collapsed, but predecessor is not. Force it. 409 unsigned Domain = LiveRegs[rx].Value->getFirstDomain(); 410 if (!pdv->isCollapsed() && pdv->hasDomain(Domain)) 411 collapse(pdv, Domain); 412 continue; 413 } 414 415 // Currently open, merge in predecessor. 416 if (!pdv->isCollapsed()) 417 merge(LiveRegs[rx].Value, pdv); 418 else 419 force(rx, pdv->getFirstDomain()); 420 } 421 } 422 DEBUG(dbgs() << "BB#" << MBB->getNumber() 423 << (SeenUnknownBackEdge ? ": incomplete\n" : ": all preds known\n")); 424 } 425 426 void ExeDepsFix::leaveBasicBlock(MachineBasicBlock *MBB) { 427 assert(LiveRegs && "Must enter basic block first."); 428 // Save live registers at end of MBB - used by enterBasicBlock(). 429 // Also use LiveOuts as a visited set to detect back-edges. 430 bool First = LiveOuts.insert(std::make_pair(MBB, LiveRegs)).second; 431 432 if (First) { 433 // LiveRegs was inserted in LiveOuts. Adjust all defs to be relative to 434 // the end of this block instead of the beginning. 435 for (unsigned i = 0, e = NumRegs; i != e; ++i) 436 LiveRegs[i].Def -= CurInstr; 437 } else { 438 // Insertion failed, this must be the second pass. 439 // Release all the DomainValues instead of keeping them. 440 for (unsigned i = 0, e = NumRegs; i != e; ++i) 441 release(LiveRegs[i].Value); 442 delete[] LiveRegs; 443 } 444 LiveRegs = nullptr; 445 } 446 447 void ExeDepsFix::visitInstr(MachineInstr *MI) { 448 if (MI->isDebugValue()) 449 return; 450 451 // Update instructions with explicit execution domains. 452 std::pair<uint16_t, uint16_t> DomP = TII->getExecutionDomain(MI); 453 if (DomP.first) { 454 if (DomP.second) 455 visitSoftInstr(MI, DomP.second); 456 else 457 visitHardInstr(MI, DomP.first); 458 } 459 460 // Process defs to track register ages, and kill values clobbered by generic 461 // instructions. 462 processDefs(MI, !DomP.first); 463 } 464 465 /// \brief Return true to if it makes sense to break dependence on a partial def 466 /// or undef use. 467 bool ExeDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx, 468 unsigned Pref) { 469 int rx = regIndex(MI->getOperand(OpIdx).getReg()); 470 if (rx < 0) 471 return false; 472 473 unsigned Clearance = CurInstr - LiveRegs[rx].Def; 474 DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref); 475 476 if (Pref > Clearance) { 477 DEBUG(dbgs() << ": Break dependency.\n"); 478 return true; 479 } 480 // The current clearance seems OK, but we may be ignoring a def from a 481 // back-edge. 482 if (!SeenUnknownBackEdge || Pref <= unsigned(CurInstr)) { 483 DEBUG(dbgs() << ": OK .\n"); 484 return false; 485 } 486 // A def from an unprocessed back-edge may make us break this dependency. 487 DEBUG(dbgs() << ": Wait for back-edge to resolve.\n"); 488 return false; 489 } 490 491 // Update def-ages for registers defined by MI. 492 // If Kill is set, also kill off DomainValues clobbered by the defs. 493 // 494 // Also break dependencies on partial defs and undef uses. 495 void ExeDepsFix::processDefs(MachineInstr *MI, bool Kill) { 496 assert(!MI->isDebugValue() && "Won't process debug values"); 497 498 // Break dependence on undef uses. Do this before updating LiveRegs below. 499 unsigned OpNum; 500 unsigned Pref = TII->getUndefRegClearance(MI, OpNum, TRI); 501 if (Pref) { 502 if (shouldBreakDependence(MI, OpNum, Pref)) 503 UndefReads.push_back(std::make_pair(MI, OpNum)); 504 } 505 const MCInstrDesc &MCID = MI->getDesc(); 506 for (unsigned i = 0, 507 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); 508 i != e; ++i) { 509 MachineOperand &MO = MI->getOperand(i); 510 if (!MO.isReg()) 511 continue; 512 if (MO.isImplicit()) 513 break; 514 if (MO.isUse()) 515 continue; 516 int rx = regIndex(MO.getReg()); 517 if (rx < 0) 518 continue; 519 520 // This instruction explicitly defines rx. 521 DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstr 522 << '\t' << *MI); 523 524 // Check clearance before partial register updates. 525 // Call breakDependence before setting LiveRegs[rx].Def. 526 unsigned Pref = TII->getPartialRegUpdateClearance(MI, i, TRI); 527 if (Pref && shouldBreakDependence(MI, i, Pref)) 528 TII->breakPartialRegDependency(MI, i, TRI); 529 530 // How many instructions since rx was last written? 531 LiveRegs[rx].Def = CurInstr; 532 533 // Kill off domains redefined by generic instructions. 534 if (Kill) 535 kill(rx); 536 } 537 ++CurInstr; 538 } 539 540 /// \break Break false dependencies on undefined register reads. 541 /// 542 /// Walk the block backward computing precise liveness. This is expensive, so we 543 /// only do it on demand. Note that the occurrence of undefined register reads 544 /// that should be broken is very rare, but when they occur we may have many in 545 /// a single block. 546 void ExeDepsFix::processUndefReads(MachineBasicBlock *MBB) { 547 if (UndefReads.empty()) 548 return; 549 550 // Collect this block's live out register units. 551 LiveRegSet.init(TRI); 552 LiveRegSet.addLiveOuts(MBB); 553 554 MachineInstr *UndefMI = UndefReads.back().first; 555 unsigned OpIdx = UndefReads.back().second; 556 557 for (MachineBasicBlock::reverse_iterator I = MBB->rbegin(), E = MBB->rend(); 558 I != E; ++I) { 559 // Update liveness, including the current instruction's defs. 560 LiveRegSet.stepBackward(*I); 561 562 if (UndefMI == &*I) { 563 if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg())) 564 TII->breakPartialRegDependency(UndefMI, OpIdx, TRI); 565 566 UndefReads.pop_back(); 567 if (UndefReads.empty()) 568 return; 569 570 UndefMI = UndefReads.back().first; 571 OpIdx = UndefReads.back().second; 572 } 573 } 574 } 575 576 // A hard instruction only works in one domain. All input registers will be 577 // forced into that domain. 578 void ExeDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) { 579 // Collapse all uses. 580 for (unsigned i = mi->getDesc().getNumDefs(), 581 e = mi->getDesc().getNumOperands(); i != e; ++i) { 582 MachineOperand &mo = mi->getOperand(i); 583 if (!mo.isReg()) continue; 584 int rx = regIndex(mo.getReg()); 585 if (rx < 0) continue; 586 force(rx, domain); 587 } 588 589 // Kill all defs and force them. 590 for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) { 591 MachineOperand &mo = mi->getOperand(i); 592 if (!mo.isReg()) continue; 593 int rx = regIndex(mo.getReg()); 594 if (rx < 0) continue; 595 kill(rx); 596 force(rx, domain); 597 } 598 } 599 600 // A soft instruction can be changed to work in other domains given by mask. 601 void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { 602 // Bitmask of available domains for this instruction after taking collapsed 603 // operands into account. 604 unsigned available = mask; 605 606 // Scan the explicit use operands for incoming domains. 607 SmallVector<int, 4> used; 608 if (LiveRegs) 609 for (unsigned i = mi->getDesc().getNumDefs(), 610 e = mi->getDesc().getNumOperands(); i != e; ++i) { 611 MachineOperand &mo = mi->getOperand(i); 612 if (!mo.isReg()) continue; 613 int rx = regIndex(mo.getReg()); 614 if (rx < 0) continue; 615 if (DomainValue *dv = LiveRegs[rx].Value) { 616 // Bitmask of domains that dv and available have in common. 617 unsigned common = dv->getCommonDomains(available); 618 // Is it possible to use this collapsed register for free? 619 if (dv->isCollapsed()) { 620 // Restrict available domains to the ones in common with the operand. 621 // If there are no common domains, we must pay the cross-domain 622 // penalty for this operand. 623 if (common) available = common; 624 } else if (common) 625 // Open DomainValue is compatible, save it for merging. 626 used.push_back(rx); 627 else 628 // Open DomainValue is not compatible with instruction. It is useless 629 // now. 630 kill(rx); 631 } 632 } 633 634 // If the collapsed operands force a single domain, propagate the collapse. 635 if (isPowerOf2_32(available)) { 636 unsigned domain = countTrailingZeros(available); 637 TII->setExecutionDomain(mi, domain); 638 visitHardInstr(mi, domain); 639 return; 640 } 641 642 // Kill off any remaining uses that don't match available, and build a list of 643 // incoming DomainValues that we want to merge. 644 SmallVector<LiveReg, 4> Regs; 645 for (SmallVectorImpl<int>::iterator i=used.begin(), e=used.end(); i!=e; ++i) { 646 int rx = *i; 647 const LiveReg &LR = LiveRegs[rx]; 648 // This useless DomainValue could have been missed above. 649 if (!LR.Value->getCommonDomains(available)) { 650 kill(rx); 651 continue; 652 } 653 // Sorted insertion. 654 bool Inserted = false; 655 for (SmallVectorImpl<LiveReg>::iterator i = Regs.begin(), e = Regs.end(); 656 i != e && !Inserted; ++i) { 657 if (LR.Def < i->Def) { 658 Inserted = true; 659 Regs.insert(i, LR); 660 } 661 } 662 if (!Inserted) 663 Regs.push_back(LR); 664 } 665 666 // doms are now sorted in order of appearance. Try to merge them all, giving 667 // priority to the latest ones. 668 DomainValue *dv = nullptr; 669 while (!Regs.empty()) { 670 if (!dv) { 671 dv = Regs.pop_back_val().Value; 672 // Force the first dv to match the current instruction. 673 dv->AvailableDomains = dv->getCommonDomains(available); 674 assert(dv->AvailableDomains && "Domain should have been filtered"); 675 continue; 676 } 677 678 DomainValue *Latest = Regs.pop_back_val().Value; 679 // Skip already merged values. 680 if (Latest == dv || Latest->Next) 681 continue; 682 if (merge(dv, Latest)) 683 continue; 684 685 // If latest didn't merge, it is useless now. Kill all registers using it. 686 for (SmallVectorImpl<int>::iterator i=used.begin(), e=used.end(); i!=e; ++i) 687 if (LiveRegs[*i].Value == Latest) 688 kill(*i); 689 } 690 691 // dv is the DomainValue we are going to use for this instruction. 692 if (!dv) { 693 dv = alloc(); 694 dv->AvailableDomains = available; 695 } 696 dv->Instrs.push_back(mi); 697 698 // Finally set all defs and non-collapsed uses to dv. We must iterate through 699 // all the operators, including imp-def ones. 700 for (MachineInstr::mop_iterator ii = mi->operands_begin(), 701 ee = mi->operands_end(); 702 ii != ee; ++ii) { 703 MachineOperand &mo = *ii; 704 if (!mo.isReg()) continue; 705 int rx = regIndex(mo.getReg()); 706 if (rx < 0) continue; 707 if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) { 708 kill(rx); 709 setLiveReg(rx, dv); 710 } 711 } 712 } 713 714 bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { 715 MF = &mf; 716 TII = MF->getTarget().getInstrInfo(); 717 TRI = MF->getTarget().getRegisterInfo(); 718 LiveRegs = nullptr; 719 assert(NumRegs == RC->getNumRegs() && "Bad regclass"); 720 721 DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: " 722 << RC->getName() << " **********\n"); 723 724 // If no relevant registers are used in the function, we can skip it 725 // completely. 726 bool anyregs = false; 727 for (TargetRegisterClass::const_iterator I = RC->begin(), E = RC->end(); 728 I != E; ++I) 729 if (MF->getRegInfo().isPhysRegUsed(*I)) { 730 anyregs = true; 731 break; 732 } 733 if (!anyregs) return false; 734 735 // Initialize the AliasMap on the first use. 736 if (AliasMap.empty()) { 737 // Given a PhysReg, AliasMap[PhysReg] is either the relevant index into RC, 738 // or -1. 739 AliasMap.resize(TRI->getNumRegs(), -1); 740 for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i) 741 for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); 742 AI.isValid(); ++AI) 743 AliasMap[*AI] = i; 744 } 745 746 MachineBasicBlock *Entry = MF->begin(); 747 ReversePostOrderTraversal<MachineBasicBlock*> RPOT(Entry); 748 SmallVector<MachineBasicBlock*, 16> Loops; 749 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator 750 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) { 751 MachineBasicBlock *MBB = *MBBI; 752 enterBasicBlock(MBB); 753 if (SeenUnknownBackEdge) 754 Loops.push_back(MBB); 755 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; 756 ++I) 757 visitInstr(I); 758 processUndefReads(MBB); 759 leaveBasicBlock(MBB); 760 } 761 762 // Visit all the loop blocks again in order to merge DomainValues from 763 // back-edges. 764 for (unsigned i = 0, e = Loops.size(); i != e; ++i) { 765 MachineBasicBlock *MBB = Loops[i]; 766 enterBasicBlock(MBB); 767 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; 768 ++I) 769 if (!I->isDebugValue()) 770 processDefs(I, false); 771 processUndefReads(MBB); 772 leaveBasicBlock(MBB); 773 } 774 775 // Clear the LiveOuts vectors and collapse any remaining DomainValues. 776 for (ReversePostOrderTraversal<MachineBasicBlock*>::rpo_iterator 777 MBBI = RPOT.begin(), MBBE = RPOT.end(); MBBI != MBBE; ++MBBI) { 778 LiveOutMap::const_iterator FI = LiveOuts.find(*MBBI); 779 if (FI == LiveOuts.end() || !FI->second) 780 continue; 781 for (unsigned i = 0, e = NumRegs; i != e; ++i) 782 if (FI->second[i].Value) 783 release(FI->second[i].Value); 784 delete[] FI->second; 785 } 786 LiveOuts.clear(); 787 UndefReads.clear(); 788 Avail.clear(); 789 Allocator.DestroyAll(); 790 791 return false; 792 } 793 794 FunctionPass * 795 llvm::createExecutionDependencyFixPass(const TargetRegisterClass *RC) { 796 return new ExeDepsFix(RC); 797 } 798