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