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