1//===- llvm/CodeGen/GlobalISel/RegBankSelect.cpp - RegBankSelect -*- 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/// \file 10/// This file implements the RegBankSelect class. 11//===----------------------------------------------------------------------===// 12 13#include "llvm/CodeGen/GlobalISel/RegBankSelect.h" 14#include "llvm/ADT/PostOrderIterator.h" 15#include "llvm/CodeGen/GlobalISel/RegisterBank.h" 16#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 17#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 18#include "llvm/CodeGen/MachineRegisterInfo.h" 19#include "llvm/IR/Function.h" 20#include "llvm/Support/BlockFrequency.h" 21#include "llvm/Support/CommandLine.h" 22#include "llvm/Support/Debug.h" 23#include "llvm/Target/TargetSubtargetInfo.h" 24 25#define DEBUG_TYPE "regbankselect" 26 27using namespace llvm; 28 29static cl::opt<RegBankSelect::Mode> RegBankSelectMode( 30 cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional, 31 cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast", 32 "Run the Fast mode (default mapping)"), 33 clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy", 34 "Use the Greedy mode (best local mapping)"), 35 clEnumValEnd)); 36 37char RegBankSelect::ID = 0; 38INITIALIZE_PASS_BEGIN(RegBankSelect, "regbankselect", 39 "Assign register bank of generic virtual registers", 40 false, false); 41INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) 42INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 43INITIALIZE_PASS_END(RegBankSelect, "regbankselect", 44 "Assign register bank of generic virtual registers", false, 45 false); 46 47RegBankSelect::RegBankSelect(Mode RunningMode) 48 : MachineFunctionPass(ID), RBI(nullptr), MRI(nullptr), TRI(nullptr), 49 MBFI(nullptr), MBPI(nullptr), OptMode(RunningMode) { 50 initializeRegBankSelectPass(*PassRegistry::getPassRegistry()); 51 if (RegBankSelectMode.getNumOccurrences() != 0) { 52 OptMode = RegBankSelectMode; 53 if (RegBankSelectMode != RunningMode) 54 DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n"); 55 } 56} 57 58void RegBankSelect::init(MachineFunction &MF) { 59 RBI = MF.getSubtarget().getRegBankInfo(); 60 assert(RBI && "Cannot work without RegisterBankInfo"); 61 MRI = &MF.getRegInfo(); 62 TRI = MF.getSubtarget().getRegisterInfo(); 63 if (OptMode != Mode::Fast) { 64 MBFI = &getAnalysis<MachineBlockFrequencyInfo>(); 65 MBPI = &getAnalysis<MachineBranchProbabilityInfo>(); 66 } else { 67 MBFI = nullptr; 68 MBPI = nullptr; 69 } 70 MIRBuilder.setMF(MF); 71} 72 73void RegBankSelect::getAnalysisUsage(AnalysisUsage &AU) const { 74 if (OptMode != Mode::Fast) { 75 // We could preserve the information from these two analysis but 76 // the APIs do not allow to do so yet. 77 AU.addRequired<MachineBlockFrequencyInfo>(); 78 AU.addRequired<MachineBranchProbabilityInfo>(); 79 } 80 MachineFunctionPass::getAnalysisUsage(AU); 81} 82 83bool RegBankSelect::assignmentMatch( 84 unsigned Reg, const RegisterBankInfo::ValueMapping &ValMapping, 85 bool &OnlyAssign) const { 86 // By default we assume we will have to repair something. 87 OnlyAssign = false; 88 // Each part of a break down needs to end up in a different register. 89 // In other word, Reg assignement does not match. 90 if (ValMapping.BreakDown.size() > 1) 91 return false; 92 93 const RegisterBank *CurRegBank = RBI->getRegBank(Reg, *MRI, *TRI); 94 const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank; 95 // Reg is free of assignment, a simple assignment will make the 96 // register bank to match. 97 OnlyAssign = CurRegBank == nullptr; 98 DEBUG(dbgs() << "Does assignment already match: "; 99 if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none"; 100 dbgs() << " against "; 101 assert(DesiredRegBrank && "The mapping must be valid"); 102 dbgs() << *DesiredRegBrank << '\n';); 103 return CurRegBank == DesiredRegBrank; 104} 105 106void RegBankSelect::repairReg( 107 MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping, 108 RegBankSelect::RepairingPlacement &RepairPt, 109 const iterator_range<SmallVectorImpl<unsigned>::const_iterator> &NewVRegs) { 110 assert(ValMapping.BreakDown.size() == 1 && "Not yet implemented"); 111 // An empty range of new register means no repairing. 112 assert(NewVRegs.begin() != NewVRegs.end() && "We should not have to repair"); 113 114 // Assume we are repairing a use and thus, the original reg will be 115 // the source of the repairing. 116 unsigned Src = MO.getReg(); 117 unsigned Dst = *NewVRegs.begin(); 118 119 // If we repair a definition, swap the source and destination for 120 // the repairing. 121 if (MO.isDef()) 122 std::swap(Src, Dst); 123 124 assert((RepairPt.getNumInsertPoints() == 1 || 125 TargetRegisterInfo::isPhysicalRegister(Dst)) && 126 "We are about to create several defs for Dst"); 127 128 // Build the instruction used to repair, then clone it at the right places. 129 MachineInstr *MI = MIRBuilder.buildInstr(TargetOpcode::COPY, Dst, Src); 130 MI->removeFromParent(); 131 DEBUG(dbgs() << "Copy: " << PrintReg(Src) << " to: " << PrintReg(Dst) 132 << '\n'); 133 // TODO: 134 // Check if MI is legal. if not, we need to legalize all the 135 // instructions we are going to insert. 136 std::unique_ptr<MachineInstr *[]> NewInstrs( 137 new MachineInstr *[RepairPt.getNumInsertPoints()]); 138 bool IsFirst = true; 139 unsigned Idx = 0; 140 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) { 141 MachineInstr *CurMI; 142 if (IsFirst) 143 CurMI = MI; 144 else 145 CurMI = MIRBuilder.getMF().CloneMachineInstr(MI); 146 InsertPt->insert(*CurMI); 147 NewInstrs[Idx++] = CurMI; 148 IsFirst = false; 149 } 150 // TODO: 151 // Legalize NewInstrs if need be. 152} 153 154uint64_t RegBankSelect::getRepairCost( 155 const MachineOperand &MO, 156 const RegisterBankInfo::ValueMapping &ValMapping) const { 157 assert(MO.isReg() && "We should only repair register operand"); 158 assert(!ValMapping.BreakDown.empty() && "Nothing to map??"); 159 160 bool IsSameNumOfValues = ValMapping.BreakDown.size() == 1; 161 const RegisterBank *CurRegBank = RBI->getRegBank(MO.getReg(), *MRI, *TRI); 162 // If MO does not have a register bank, we should have just been 163 // able to set one unless we have to break the value down. 164 assert((!IsSameNumOfValues || CurRegBank) && "We should not have to repair"); 165 // Def: Val <- NewDefs 166 // Same number of values: copy 167 // Different number: Val = build_sequence Defs1, Defs2, ... 168 // Use: NewSources <- Val. 169 // Same number of values: copy. 170 // Different number: Src1, Src2, ... = 171 // extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ... 172 // We should remember that this value is available somewhere else to 173 // coalesce the value. 174 175 if (IsSameNumOfValues) { 176 const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank; 177 // If we repair a definition, swap the source and destination for 178 // the repairing. 179 if (MO.isDef()) 180 std::swap(CurRegBank, DesiredRegBrank); 181 // TODO: It may be possible to actually avoid the copy. 182 // If we repair something where the source is defined by a copy 183 // and the source of that copy is on the right bank, we can reuse 184 // it for free. 185 // E.g., 186 // RegToRepair<BankA> = copy AlternativeSrc<BankB> 187 // = op RegToRepair<BankA> 188 // We can simply propagate AlternativeSrc instead of copying RegToRepair 189 // into a new virtual register. 190 // We would also need to propagate this information in the 191 // repairing placement. 192 unsigned Cost = 193 RBI->copyCost(*DesiredRegBrank, *CurRegBank, 194 RegisterBankInfo::getSizeInBits(MO.getReg(), *MRI, *TRI)); 195 // TODO: use a dedicated constant for ImpossibleCost. 196 if (Cost != UINT_MAX) 197 return Cost; 198 assert(false && "Legalization not available yet"); 199 // Return the legalization cost of that repairing. 200 } 201 assert(false && "Complex repairing not implemented yet"); 202 return 1; 203} 204 205RegisterBankInfo::InstructionMapping &RegBankSelect::findBestMapping( 206 MachineInstr &MI, RegisterBankInfo::InstructionMappings &PossibleMappings, 207 SmallVectorImpl<RepairingPlacement> &RepairPts) { 208 209 RegisterBankInfo::InstructionMapping *BestMapping = nullptr; 210 MappingCost Cost = MappingCost::ImpossibleCost(); 211 SmallVector<RepairingPlacement, 4> LocalRepairPts; 212 for (RegisterBankInfo::InstructionMapping &CurMapping : PossibleMappings) { 213 MappingCost CurCost = computeMapping(MI, CurMapping, LocalRepairPts, &Cost); 214 if (CurCost < Cost) { 215 Cost = CurCost; 216 BestMapping = &CurMapping; 217 RepairPts.clear(); 218 for (RepairingPlacement &RepairPt : LocalRepairPts) 219 RepairPts.emplace_back(std::move(RepairPt)); 220 } 221 } 222 assert(BestMapping && "No suitable mapping for instruction"); 223 return *BestMapping; 224} 225 226void RegBankSelect::tryAvoidingSplit( 227 RegBankSelect::RepairingPlacement &RepairPt, const MachineOperand &MO, 228 const RegisterBankInfo::ValueMapping &ValMapping) const { 229 const MachineInstr &MI = *MO.getParent(); 230 assert(RepairPt.hasSplit() && "We should not have to adjust for split"); 231 // Splitting should only occur for PHIs or between terminators, 232 // because we only do local repairing. 233 assert((MI.isPHI() || MI.isTerminator()) && "Why do we split?"); 234 235 assert(&MI.getOperand(RepairPt.getOpIdx()) == &MO && 236 "Repairing placement does not match operand"); 237 238 // If we need splitting for phis, that means it is because we 239 // could not find an insertion point before the terminators of 240 // the predecessor block for this argument. In other words, 241 // the input value is defined by one of the terminators. 242 assert((!MI.isPHI() || !MO.isDef()) && "Need split for phi def?"); 243 244 // We split to repair the use of a phi or a terminator. 245 if (!MO.isDef()) { 246 if (MI.isTerminator()) { 247 assert(&MI != &(*MI.getParent()->getFirstTerminator()) && 248 "Need to split for the first terminator?!"); 249 } else { 250 // For the PHI case, the split may not be actually required. 251 // In the copy case, a phi is already a copy on the incoming edge, 252 // therefore there is no need to split. 253 if (ValMapping.BreakDown.size() == 1) 254 // This is a already a copy, there is nothing to do. 255 RepairPt.switchTo(RepairingPlacement::RepairingKind::Reassign); 256 } 257 return; 258 } 259 260 // At this point, we need to repair a defintion of a terminator. 261 262 // Technically we need to fix the def of MI on all outgoing 263 // edges of MI to keep the repairing local. In other words, we 264 // will create several definitions of the same register. This 265 // does not work for SSA unless that definition is a physical 266 // register. 267 // However, there are other cases where we can get away with 268 // that while still keeping the repairing local. 269 assert(MI.isTerminator() && MO.isDef() && 270 "This code is for the def of a terminator"); 271 272 // Since we use RPO traversal, if we need to repair a definition 273 // this means this definition could be: 274 // 1. Used by PHIs (i.e., this VReg has been visited as part of the 275 // uses of a phi.), or 276 // 2. Part of a target specific instruction (i.e., the target applied 277 // some register class constraints when creating the instruction.) 278 // If the constraints come for #2, the target said that another mapping 279 // is supported so we may just drop them. Indeed, if we do not change 280 // the number of registers holding that value, the uses will get fixed 281 // when we get to them. 282 // Uses in PHIs may have already been proceeded though. 283 // If the constraints come for #1, then, those are weak constraints and 284 // no actual uses may rely on them. However, the problem remains mainly 285 // the same as for #2. If the value stays in one register, we could 286 // just switch the register bank of the definition, but we would need to 287 // account for a repairing cost for each phi we silently change. 288 // 289 // In any case, if the value needs to be broken down into several 290 // registers, the repairing is not local anymore as we need to patch 291 // every uses to rebuild the value in just one register. 292 // 293 // To summarize: 294 // - If the value is in a physical register, we can do the split and 295 // fix locally. 296 // Otherwise if the value is in a virtual register: 297 // - If the value remains in one register, we do not have to split 298 // just switching the register bank would do, but we need to account 299 // in the repairing cost all the phi we changed. 300 // - If the value spans several registers, then we cannot do a local 301 // repairing. 302 303 // Check if this is a physical or virtual register. 304 unsigned Reg = MO.getReg(); 305 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 306 // We are going to split every outgoing edges. 307 // Check that this is possible. 308 // FIXME: The machine representation is currently broken 309 // since it also several terminators in one basic block. 310 // Because of that we would technically need a way to get 311 // the targets of just one terminator to know which edges 312 // we have to split. 313 // Assert that we do not hit the ill-formed representation. 314 315 // If there are other terminators before that one, some of 316 // the outgoing edges may not be dominated by this definition. 317 assert(&MI == &(*MI.getParent()->getFirstTerminator()) && 318 "Do not know which outgoing edges are relevant"); 319 const MachineInstr *Next = MI.getNextNode(); 320 assert((!Next || Next->isUnconditionalBranch()) && 321 "Do not know where each terminator ends up"); 322 if (Next) 323 // If the next terminator uses Reg, this means we have 324 // to split right after MI and thus we need a way to ask 325 // which outgoing edges are affected. 326 assert(!Next->readsRegister(Reg) && "Need to split between terminators"); 327 // We will split all the edges and repair there. 328 } else { 329 // This is a virtual register defined by a terminator. 330 if (ValMapping.BreakDown.size() == 1) { 331 // There is nothing to repair, but we may actually lie on 332 // the repairing cost because of the PHIs already proceeded 333 // as already stated. 334 // Though the code will be correct. 335 assert(0 && "Repairing cost may not be accurate"); 336 } else { 337 // We need to do non-local repairing. Basically, patch all 338 // the uses (i.e., phis) that we already proceeded. 339 // For now, just say this mapping is not possible. 340 RepairPt.switchTo(RepairingPlacement::RepairingKind::Impossible); 341 } 342 } 343} 344 345RegBankSelect::MappingCost RegBankSelect::computeMapping( 346 MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping, 347 SmallVectorImpl<RepairingPlacement> &RepairPts, 348 const RegBankSelect::MappingCost *BestCost) { 349 assert((MBFI || !BestCost) && "Costs comparison require MBFI"); 350 351 // If mapped with InstrMapping, MI will have the recorded cost. 352 MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent()) : 1); 353 bool Saturated = Cost.addLocalCost(InstrMapping.getCost()); 354 assert(!Saturated && "Possible mapping saturated the cost"); 355 DEBUG(dbgs() << "Evaluating mapping cost for: " << MI); 356 DEBUG(dbgs() << "With: " << InstrMapping << '\n'); 357 RepairPts.clear(); 358 if (BestCost && Cost > *BestCost) 359 return Cost; 360 361 // Moreover, to realize this mapping, the register bank of each operand must 362 // match this mapping. In other words, we may need to locally reassign the 363 // register banks. Account for that repairing cost as well. 364 // In this context, local means in the surrounding of MI. 365 for (unsigned OpIdx = 0, EndOpIdx = MI.getNumOperands(); OpIdx != EndOpIdx; 366 ++OpIdx) { 367 const MachineOperand &MO = MI.getOperand(OpIdx); 368 if (!MO.isReg()) 369 continue; 370 unsigned Reg = MO.getReg(); 371 if (!Reg) 372 continue; 373 DEBUG(dbgs() << "Opd" << OpIdx); 374 const RegisterBankInfo::ValueMapping &ValMapping = 375 InstrMapping.getOperandMapping(OpIdx); 376 // If Reg is already properly mapped, this is free. 377 bool Assign; 378 if (assignmentMatch(Reg, ValMapping, Assign)) { 379 DEBUG(dbgs() << " is free (match).\n"); 380 continue; 381 } 382 if (Assign) { 383 DEBUG(dbgs() << " is free (simple assignment).\n"); 384 RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this, 385 RepairingPlacement::Reassign)); 386 continue; 387 } 388 389 // Find the insertion point for the repairing code. 390 RepairPts.emplace_back( 391 RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert)); 392 RepairingPlacement &RepairPt = RepairPts.back(); 393 394 // If we need to split a basic block to materialize this insertion point, 395 // we may give a higher cost to this mapping. 396 // Nevertheless, we may get away with the split, so try that first. 397 if (RepairPt.hasSplit()) 398 tryAvoidingSplit(RepairPt, MO, ValMapping); 399 400 // Check that the materialization of the repairing is possible. 401 if (!RepairPt.canMaterialize()) 402 return MappingCost::ImpossibleCost(); 403 404 // Account for the split cost and repair cost. 405 // Unless the cost is already saturated or we do not care about the cost. 406 if (!BestCost || Saturated) 407 continue; 408 409 // To get accurate information we need MBFI and MBPI. 410 // Thus, if we end up here this information should be here. 411 assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI"); 412 413 // FIXME: We will have to rework the repairing cost model. 414 // The repairing cost depends on the register bank that MO has. 415 // However, when we break down the value into different values, 416 // MO may not have a register bank while still needing repairing. 417 // For the fast mode, we don't compute the cost so that is fine, 418 // but still for the repairing code, we will have to make a choice. 419 // For the greedy mode, we should choose greedily what is the best 420 // choice based on the next use of MO. 421 422 // Sums up the repairing cost of MO at each insertion point. 423 uint64_t RepairCost = getRepairCost(MO, ValMapping); 424 // Bias used for splitting: 5%. 425 const uint64_t PercentageForBias = 5; 426 uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100; 427 // We should not need more than a couple of instructions to repair 428 // an assignment. In other words, the computation should not 429 // overflow because the repairing cost is free of basic block 430 // frequency. 431 assert(((RepairCost < RepairCost * PercentageForBias) && 432 (RepairCost * PercentageForBias < 433 RepairCost * PercentageForBias + 99)) && 434 "Repairing involves more than a billion of instructions?!"); 435 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) { 436 assert(InsertPt->canMaterialize() && "We should not have made it here"); 437 // We will applied some basic block frequency and those uses uint64_t. 438 if (!InsertPt->isSplit()) 439 Saturated = Cost.addLocalCost(RepairCost); 440 else { 441 uint64_t CostForInsertPt = RepairCost; 442 // Again we shouldn't overflow here givent that 443 // CostForInsertPt is frequency free at this point. 444 assert(CostForInsertPt + Bias > CostForInsertPt && 445 "Repairing + split bias overflows"); 446 CostForInsertPt += Bias; 447 uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt; 448 // Check if we just overflowed. 449 if ((Saturated = PtCost < CostForInsertPt)) 450 Cost.saturate(); 451 else 452 Saturated = Cost.addNonLocalCost(PtCost); 453 } 454 455 // Stop looking into what it takes to repair, this is already 456 // too expensive. 457 if (BestCost && Cost > *BestCost) 458 return Cost; 459 460 // No need to accumulate more cost information. 461 // We need to still gather the repairing information though. 462 if (Saturated) 463 break; 464 } 465 } 466 return Cost; 467} 468 469void RegBankSelect::applyMapping( 470 MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping, 471 SmallVectorImpl<RegBankSelect::RepairingPlacement> &RepairPts) { 472 // OpdMapper will hold all the information needed for the rewritting. 473 RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI); 474 475 // First, place the repairing code. 476 for (RepairingPlacement &RepairPt : RepairPts) { 477 assert(RepairPt.canMaterialize() && 478 RepairPt.getKind() != RepairingPlacement::Impossible && 479 "This mapping is impossible"); 480 assert(RepairPt.getKind() != RepairingPlacement::None && 481 "This should not make its way in the list"); 482 unsigned OpIdx = RepairPt.getOpIdx(); 483 MachineOperand &MO = MI.getOperand(OpIdx); 484 const RegisterBankInfo::ValueMapping &ValMapping = 485 InstrMapping.getOperandMapping(OpIdx); 486 unsigned BreakDownSize = ValMapping.BreakDown.size(); 487 (void)BreakDownSize; 488 unsigned Reg = MO.getReg(); 489 490 switch (RepairPt.getKind()) { 491 case RepairingPlacement::Reassign: 492 assert(BreakDownSize == 1 && 493 "Reassignment should only be for simple mapping"); 494 MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank); 495 break; 496 case RepairingPlacement::Insert: 497 OpdMapper.createVRegs(OpIdx); 498 repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx)); 499 break; 500 default: 501 llvm_unreachable("Other kind should not happen"); 502 } 503 } 504 // Second, rewrite the instruction. 505 DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n'); 506 RBI->applyMapping(OpdMapper); 507} 508 509void RegBankSelect::assignInstr(MachineInstr &MI) { 510 DEBUG(dbgs() << "Assign: " << MI); 511 // Remember the repairing placement for all the operands. 512 SmallVector<RepairingPlacement, 4> RepairPts; 513 514 RegisterBankInfo::InstructionMapping BestMapping; 515 if (OptMode == RegBankSelect::Mode::Fast) { 516 BestMapping = RBI->getInstrMapping(MI); 517 MappingCost DefaultCost = computeMapping(MI, BestMapping, RepairPts); 518 (void)DefaultCost; 519 assert(DefaultCost != MappingCost::ImpossibleCost() && 520 "Default mapping is not suited"); 521 } else { 522 RegisterBankInfo::InstructionMappings PossibleMappings = 523 RBI->getInstrPossibleMappings(MI); 524 assert(!PossibleMappings.empty() && 525 "Do not know how to map this instruction"); 526 BestMapping = std::move(findBestMapping(MI, PossibleMappings, RepairPts)); 527 } 528 // Make sure the mapping is valid for MI. 529 assert(BestMapping.verify(MI) && "Invalid instruction mapping"); 530 531 DEBUG(dbgs() << "Mapping: " << BestMapping << '\n'); 532 533 // After this call, MI may not be valid anymore. 534 // Do not use it. 535 applyMapping(MI, BestMapping, RepairPts); 536} 537 538bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) { 539 DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n'); 540 const Function *F = MF.getFunction(); 541 Mode SaveOptMode = OptMode; 542 if (F->hasFnAttribute(Attribute::OptimizeNone)) 543 OptMode = Mode::Fast; 544 init(MF); 545 // Walk the function and assign register banks to all operands. 546 // Use a RPOT to make sure all registers are assigned before we choose 547 // the best mapping of the current instruction. 548 ReversePostOrderTraversal<MachineFunction*> RPOT(&MF); 549 for (MachineBasicBlock *MBB : RPOT) { 550 // Set a sensible insertion point so that subsequent calls to 551 // MIRBuilder. 552 MIRBuilder.setMBB(*MBB); 553 for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end(); 554 MII != End;) { 555 // MI might be invalidated by the assignment, so move the 556 // iterator before hand. 557 assignInstr(*MII++); 558 } 559 } 560 OptMode = SaveOptMode; 561 return false; 562} 563 564//------------------------------------------------------------------------------ 565// Helper Classes Implementation 566//------------------------------------------------------------------------------ 567RegBankSelect::RepairingPlacement::RepairingPlacement( 568 MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P, 569 RepairingPlacement::RepairingKind Kind) 570 // Default is, we are going to insert code to repair OpIdx. 571 : Kind(Kind), 572 OpIdx(OpIdx), 573 CanMaterialize(Kind != RepairingKind::Impossible), 574 HasSplit(false), 575 P(P) { 576 const MachineOperand &MO = MI.getOperand(OpIdx); 577 assert(MO.isReg() && "Trying to repair a non-reg operand"); 578 579 if (Kind != RepairingKind::Insert) 580 return; 581 582 // Repairings for definitions happen after MI, uses happen before. 583 bool Before = !MO.isDef(); 584 585 // Check if we are done with MI. 586 if (!MI.isPHI() && !MI.isTerminator()) { 587 addInsertPoint(MI, Before); 588 // We are done with the initialization. 589 return; 590 } 591 592 // Now, look for the special cases. 593 if (MI.isPHI()) { 594 // - PHI must be the first instructions: 595 // * Before, we have to split the related incoming edge. 596 // * After, move the insertion point past the last phi. 597 if (!Before) { 598 MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI(); 599 if (It != MI.getParent()->end()) 600 addInsertPoint(*It, /*Before*/ true); 601 else 602 addInsertPoint(*(--It), /*Before*/ false); 603 return; 604 } 605 // We repair a use of a phi, we may need to split the related edge. 606 MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB(); 607 // Check if we can move the insertion point prior to the 608 // terminators of the predecessor. 609 unsigned Reg = MO.getReg(); 610 MachineBasicBlock::iterator It = Pred.getLastNonDebugInstr(); 611 for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It) 612 if (It->modifiesRegister(Reg, &TRI)) { 613 // We cannot hoist the repairing code in the predecessor. 614 // Split the edge. 615 addInsertPoint(Pred, *MI.getParent()); 616 return; 617 } 618 // At this point, we can insert in Pred. 619 620 // - If It is invalid, Pred is empty and we can insert in Pred 621 // wherever we want. 622 // - If It is valid, It is the first non-terminator, insert after It. 623 if (It == Pred.end()) 624 addInsertPoint(Pred, /*Beginning*/ false); 625 else 626 addInsertPoint(*It, /*Before*/ false); 627 } else { 628 // - Terminators must be the last instructions: 629 // * Before, move the insert point before the first terminator. 630 // * After, we have to split the outcoming edges. 631 unsigned Reg = MO.getReg(); 632 if (Before) { 633 // Check whether Reg is defined by any terminator. 634 MachineBasicBlock::iterator It = MI; 635 for (auto Begin = MI.getParent()->begin(); 636 --It != Begin && It->isTerminator();) 637 if (It->modifiesRegister(Reg, &TRI)) { 638 // Insert the repairing code right after the definition. 639 addInsertPoint(*It, /*Before*/ false); 640 return; 641 } 642 addInsertPoint(*It, /*Before*/ true); 643 return; 644 } 645 // Make sure Reg is not redefined by other terminators, otherwise 646 // we do not know how to split. 647 for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end(); 648 ++It != End;) 649 // The machine verifier should reject this kind of code. 650 assert(It->modifiesRegister(Reg, &TRI) && "Do not know where to split"); 651 // Split each outcoming edges. 652 MachineBasicBlock &Src = *MI.getParent(); 653 for (auto &Succ : Src.successors()) 654 addInsertPoint(Src, Succ); 655 } 656} 657 658void RegBankSelect::RepairingPlacement::addInsertPoint(MachineInstr &MI, 659 bool Before) { 660 addInsertPoint(*new InstrInsertPoint(MI, Before)); 661} 662 663void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &MBB, 664 bool Beginning) { 665 addInsertPoint(*new MBBInsertPoint(MBB, Beginning)); 666} 667 668void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &Src, 669 MachineBasicBlock &Dst) { 670 addInsertPoint(*new EdgeInsertPoint(Src, Dst, P)); 671} 672 673void RegBankSelect::RepairingPlacement::addInsertPoint( 674 RegBankSelect::InsertPoint &Point) { 675 CanMaterialize &= Point.canMaterialize(); 676 HasSplit |= Point.isSplit(); 677 InsertPoints.emplace_back(&Point); 678} 679 680RegBankSelect::InstrInsertPoint::InstrInsertPoint(MachineInstr &Instr, 681 bool Before) 682 : InsertPoint(), Instr(Instr), Before(Before) { 683 // Since we do not support splitting, we do not need to update 684 // liveness and such, so do not do anything with P. 685 assert((!Before || !Instr.isPHI()) && 686 "Splitting before phis requires more points"); 687 assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) && 688 "Splitting between phis does not make sense"); 689} 690 691void RegBankSelect::InstrInsertPoint::materialize() { 692 if (isSplit()) { 693 // Slice and return the beginning of the new block. 694 // If we need to split between the terminators, we theoritically 695 // need to know where the first and second set of terminators end 696 // to update the successors properly. 697 // Now, in pratice, we should have a maximum of 2 branch 698 // instructions; one conditional and one unconditional. Therefore 699 // we know how to update the successor by looking at the target of 700 // the unconditional branch. 701 // If we end up splitting at some point, then, we should update 702 // the liveness information and such. I.e., we would need to 703 // access P here. 704 // The machine verifier should actually make sure such cases 705 // cannot happen. 706 llvm_unreachable("Not yet implemented"); 707 } 708 // Otherwise the insertion point is just the current or next 709 // instruction depending on Before. I.e., there is nothing to do 710 // here. 711} 712 713bool RegBankSelect::InstrInsertPoint::isSplit() const { 714 // If the insertion point is after a terminator, we need to split. 715 if (!Before) 716 return Instr.isTerminator(); 717 // If we insert before an instruction that is after a terminator, 718 // we are still after a terminator. 719 return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator(); 720} 721 722uint64_t RegBankSelect::InstrInsertPoint::frequency(const Pass &P) const { 723 // Even if we need to split, because we insert between terminators, 724 // this split has actually the same frequency as the instruction. 725 const MachineBlockFrequencyInfo *MBFI = 726 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); 727 if (!MBFI) 728 return 1; 729 return MBFI->getBlockFreq(Instr.getParent()).getFrequency(); 730} 731 732uint64_t RegBankSelect::MBBInsertPoint::frequency(const Pass &P) const { 733 const MachineBlockFrequencyInfo *MBFI = 734 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); 735 if (!MBFI) 736 return 1; 737 return MBFI->getBlockFreq(&MBB).getFrequency(); 738} 739 740void RegBankSelect::EdgeInsertPoint::materialize() { 741 // If we end up repairing twice at the same place before materializing the 742 // insertion point, we may think we have to split an edge twice. 743 // We should have a factory for the insert point such that identical points 744 // are the same instance. 745 assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) && 746 "This point has already been split"); 747 MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P); 748 assert(NewBB && "Invalid call to materialize"); 749 // We reuse the destination block to hold the information of the new block. 750 DstOrSplit = NewBB; 751} 752 753uint64_t RegBankSelect::EdgeInsertPoint::frequency(const Pass &P) const { 754 const MachineBlockFrequencyInfo *MBFI = 755 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); 756 if (!MBFI) 757 return 1; 758 if (WasMaterialized) 759 return MBFI->getBlockFreq(DstOrSplit).getFrequency(); 760 761 const MachineBranchProbabilityInfo *MBPI = 762 P.getAnalysisIfAvailable<MachineBranchProbabilityInfo>(); 763 if (!MBPI) 764 return 1; 765 // The basic block will be on the edge. 766 return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit)) 767 .getFrequency(); 768} 769 770bool RegBankSelect::EdgeInsertPoint::canMaterialize() const { 771 // If this is not a critical edge, we should not have used this insert 772 // point. Indeed, either the successor or the predecessor should 773 // have do. 774 assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 && 775 "Edge is not critical"); 776 return Src.canSplitCriticalEdge(DstOrSplit); 777} 778 779RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq) 780 : LocalCost(0), NonLocalCost(0), LocalFreq(LocalFreq.getFrequency()) {} 781 782bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) { 783 // Check if this overflows. 784 if (LocalCost + Cost < LocalCost) { 785 saturate(); 786 return true; 787 } 788 LocalCost += Cost; 789 return isSaturated(); 790} 791 792bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) { 793 // Check if this overflows. 794 if (NonLocalCost + Cost < NonLocalCost) { 795 saturate(); 796 return true; 797 } 798 NonLocalCost += Cost; 799 return isSaturated(); 800} 801 802bool RegBankSelect::MappingCost::isSaturated() const { 803 return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX && 804 LocalFreq == UINT64_MAX; 805} 806 807void RegBankSelect::MappingCost::saturate() { 808 *this = ImpossibleCost(); 809 --LocalCost; 810} 811 812RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() { 813 return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX); 814} 815 816bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const { 817 // Sort out the easy cases. 818 if (*this == Cost) 819 return false; 820 // If one is impossible to realize the other is cheaper unless it is 821 // impossible as well. 822 if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost())) 823 return (*this == ImpossibleCost()) < (Cost == ImpossibleCost()); 824 // If one is saturated the other is cheaper, unless it is saturated 825 // as well. 826 if (isSaturated() || Cost.isSaturated()) 827 return isSaturated() < Cost.isSaturated(); 828 // At this point we know both costs hold sensible values. 829 830 // If both values have a different base frequency, there is no much 831 // we can do but to scale everything. 832 // However, if they have the same base frequency we can avoid making 833 // complicated computation. 834 uint64_t ThisLocalAdjust; 835 uint64_t OtherLocalAdjust; 836 if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) { 837 838 // At this point, we know the local costs are comparable. 839 // Do the case that do not involve potential overflow first. 840 if (NonLocalCost == Cost.NonLocalCost) 841 // Since the non-local costs do not discriminate on the result, 842 // just compare the local costs. 843 return LocalCost < Cost.LocalCost; 844 845 // The base costs are comparable so we may only keep the relative 846 // value to increase our chances of avoiding overflows. 847 ThisLocalAdjust = 0; 848 OtherLocalAdjust = 0; 849 if (LocalCost < Cost.LocalCost) 850 OtherLocalAdjust = Cost.LocalCost - LocalCost; 851 else 852 ThisLocalAdjust = LocalCost - Cost.LocalCost; 853 854 } else { 855 ThisLocalAdjust = LocalCost; 856 OtherLocalAdjust = Cost.LocalCost; 857 } 858 859 // The non-local costs are comparable, just keep the relative value. 860 uint64_t ThisNonLocalAdjust = 0; 861 uint64_t OtherNonLocalAdjust = 0; 862 if (NonLocalCost < Cost.NonLocalCost) 863 OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost; 864 else 865 ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost; 866 // Scale everything to make them comparable. 867 uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq; 868 // Check for overflow on that operation. 869 bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust || 870 ThisScaledCost < LocalFreq); 871 uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq; 872 // Check for overflow on the last operation. 873 bool OtherOverflows = 874 OtherLocalAdjust && 875 (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq); 876 // Add the non-local costs. 877 ThisOverflows |= ThisNonLocalAdjust && 878 ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust; 879 ThisScaledCost += ThisNonLocalAdjust; 880 OtherOverflows |= OtherNonLocalAdjust && 881 OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust; 882 OtherScaledCost += OtherNonLocalAdjust; 883 // If both overflows, we cannot compare without additional 884 // precision, e.g., APInt. Just give up on that case. 885 if (ThisOverflows && OtherOverflows) 886 return false; 887 // If one overflows but not the other, we can still compare. 888 if (ThisOverflows || OtherOverflows) 889 return ThisOverflows < OtherOverflows; 890 // Otherwise, just compare the values. 891 return ThisScaledCost < OtherScaledCost; 892} 893 894bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const { 895 return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost && 896 LocalFreq == Cost.LocalFreq; 897} 898