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