| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/GlobalISel/RegBankSelect.cpp |
| Warning: | line 320, column 3 Returning null reference |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 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" "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",llvm::cl::OptionEnumValue { "regbankselect-fast", int(RegBankSelect ::Mode::Fast), "Run the Fast mode (default mapping)" } | |||
| 57 | "Run the Fast mode (default mapping)")llvm::cl::OptionEnumValue { "regbankselect-fast", int(RegBankSelect ::Mode::Fast), "Run the Fast mode (default mapping)" }, | |||
| 58 | clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy",llvm::cl::OptionEnumValue { "regbankselect-greedy", int(RegBankSelect ::Mode::Greedy), "Use the Greedy mode (best local mapping)" } | |||
| 59 | "Use the Greedy mode (best local mapping)")llvm::cl::OptionEnumValue { "regbankselect-greedy", int(RegBankSelect ::Mode::Greedy), "Use the Greedy mode (best local mapping)" })); | |||
| 60 | ||||
| 61 | char RegBankSelect::ID = 0; | |||
| 62 | ||||
| 63 | INITIALIZE_PASS_BEGIN(RegBankSelect, DEBUG_TYPE,static void *initializeRegBankSelectPassOnce(PassRegistry & Registry) { | |||
| 64 | "Assign register bank of generic virtual registers",static void *initializeRegBankSelectPassOnce(PassRegistry & Registry) { | |||
| 65 | false, false)static void *initializeRegBankSelectPassOnce(PassRegistry & Registry) {; | |||
| 66 | INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)initializeMachineBlockFrequencyInfoPass(Registry); | |||
| 67 | INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)initializeMachineBranchProbabilityInfoPass(Registry); | |||
| 68 | INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)initializeTargetPassConfigPass(Registry); | |||
| 69 | INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE,PassInfo *PI = new PassInfo( "Assign register bank of generic virtual registers" , "regbankselect", &RegBankSelect::ID, PassInfo::NormalCtor_t (callDefaultCtor<RegBankSelect>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeRegBankSelectPassFlag; void llvm::initializeRegBankSelectPass (PassRegistry &Registry) { llvm::call_once(InitializeRegBankSelectPassFlag , initializeRegBankSelectPassOnce, std::ref(Registry)); } | |||
| 70 | "Assign register bank of generic virtual registers", false,PassInfo *PI = new PassInfo( "Assign register bank of generic virtual registers" , "regbankselect", &RegBankSelect::ID, PassInfo::NormalCtor_t (callDefaultCtor<RegBankSelect>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeRegBankSelectPassFlag; void llvm::initializeRegBankSelectPass (PassRegistry &Registry) { llvm::call_once(InitializeRegBankSelectPassFlag , initializeRegBankSelectPassOnce, std::ref(Registry)); } | |||
| 71 | false)PassInfo *PI = new PassInfo( "Assign register bank of generic virtual registers" , "regbankselect", &RegBankSelect::ID, PassInfo::NormalCtor_t (callDefaultCtor<RegBankSelect>), false, false); Registry .registerPass(*PI, true); return PI; } static llvm::once_flag InitializeRegBankSelectPassFlag; void llvm::initializeRegBankSelectPass (PassRegistry &Registry) { llvm::call_once(InitializeRegBankSelectPassFlag , initializeRegBankSelectPassOnce, std::ref(Registry)); } | |||
| 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")do { } while (false); | |||
| 79 | } | |||
| 80 | } | |||
| 81 | ||||
| 82 | void RegBankSelect::init(MachineFunction &MF) { | |||
| 83 | RBI = MF.getSubtarget().getRegBankInfo(); | |||
| 84 | assert(RBI && "Cannot work without RegisterBankInfo")((void)0); | |||
| 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: ";do { } while (false) | |||
| 127 | if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";do { } while (false) | |||
| 128 | dbgs() << " against ";do { } while (false) | |||
| 129 | assert(DesiredRegBank && "The mapping must be valid");do { } while (false) | |||
| 130 | dbgs() << *DesiredRegBank << '\n';)do { } while (false); | |||
| 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) &&((void)0) | |||
| 140 | "need new vreg for each breakdown")((void)0); | |||
| 141 | ||||
| 142 | // An empty range of new register means no repairing. | |||
| 143 | assert(!NewVRegs.empty() && "We should not have to repair")((void)0); | |||
| 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 ||((void)0) | |||
| 158 | Register::isPhysicalRegister(Dst)) &&((void)0) | |||
| 159 | "We are about to create several defs for Dst")((void)0); | |||
| 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)do { } while (false) | |||
| 168 | << '\n')do { } while (false); | |||
| 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")((void)0); | |||
| 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(((void)0) | |||
| 182 | (ValMapping.BreakDown[0].Length * ValMapping.NumBreakDowns ==((void)0) | |||
| 183 | RegTy.getSizeInBits()) &&((void)0) | |||
| 184 | (ValMapping.BreakDown[0].Length % RegTy.getScalarSizeInBits() ==((void)0) | |||
| 185 | 0) &&((void)0) | |||
| 186 | "don't understand this value breakdown")((void)0); | |||
| 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")((void)0); | |||
| 241 | assert(ValMapping.NumBreakDowns && "Nothing to map??")((void)0); | |||
| 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())((void)0); | |||
| 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() &&((void)0) | |||
| 293 | "Do not know how to map this instruction")((void)0); | |||
| 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')do { } while (false); | |||
| 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
| |||
| 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")((void)0); | |||
| 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")((void)0); | |||
| 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?")((void)0); | |||
| 331 | ||||
| 332 | assert(&MI.getOperand(RepairPt.getOpIdx()) == &MO &&((void)0) | |||
| 333 | "Repairing placement does not match operand")((void)0); | |||
| 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?")((void)0); | |||
| 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()) &&((void)0) | |||
| 345 | "Need to split for the first terminator?!")((void)0); | |||
| 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() &&((void)0) | |||
| 367 | "This code is for the def of a terminator")((void)0); | |||
| 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()) &&((void)0) | |||
| 415 | "Do not know which outgoing edges are relevant")((void)0); | |||
| 416 | const MachineInstr *Next = MI.getNextNode(); | |||
| 417 | assert((!Next || Next->isUnconditionalBranch()) &&((void)0) | |||
| 418 | "Do not know where each terminator ends up")((void)0); | |||
| 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")((void)0); | |||
| 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")((void)0); | |||
| 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")((void)0); | |||
| 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")((void)0); | |||
| 455 | LLVM_DEBUG(dbgs() << "Evaluating mapping cost for: " << MI)do { } while (false); | |||
| 456 | LLVM_DEBUG(dbgs() << "With: " << InstrMapping << '\n')do { } while (false); | |||
| 457 | RepairPts.clear(); | |||
| 458 | if (BestCost && Cost > *BestCost) { | |||
| 459 | LLVM_DEBUG(dbgs() << "Mapping is too expensive from the start\n")do { } while (false); | |||
| 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')do { } while (false); | |||
| 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")do { } while (false); | |||
| 482 | continue; | |||
| 483 | } | |||
| 484 | if (Assign) { | |||
| 485 | LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n")do { } while (false); | |||
| 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")do { } while (false); | |||
| 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")((void)0); | |||
| 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) &&((void)0) | |||
| 541 | (RepairCost * PercentageForBias <((void)0) | |||
| 542 | RepairCost * PercentageForBias + 99)) &&((void)0) | |||
| 543 | "Repairing involves more than a billion of instructions?!")((void)0); | |||
| 544 | for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) { | |||
| 545 | assert(InsertPt->canMaterialize() && "We should not have made it here")((void)0); | |||
| 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 &&((void)0) | |||
| 554 | "Repairing + split bias overflows")((void)0); | |||
| 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")do { } while (false); | |||
| 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")do { } while (false); | |||
| 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 &&((void)0) | |||
| 593 | "This should not make its way in the list")((void)0); | |||
| 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 &&((void)0) | |||
| 603 | "Reassignment should only be for simple mapping")((void)0); | |||
| 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")__builtin_unreachable(); | |||
| 613 | } | |||
| 614 | } | |||
| 615 | ||||
| 616 | // Second, rewrite the instruction. | |||
| 617 | LLVM_DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n')do { } while (false); | |||
| 618 | RBI->applyMapping(OpdMapper); | |||
| 619 | ||||
| 620 | return true; | |||
| 621 | } | |||
| 622 | ||||
| 623 | bool RegBankSelect::assignInstr(MachineInstr &MI) { | |||
| 624 | LLVM_DEBUG(dbgs() << "Assign: " << MI)do { } while (false); | |||
| 625 | ||||
| 626 | unsigned Opc = MI.getOpcode(); | |||
| 627 | if (isPreISelGenericOptimizationHint(Opc)) { | |||
| 628 | assert((Opc == TargetOpcode::G_ASSERT_ZEXT ||((void)0) | |||
| 629 | Opc == TargetOpcode::G_ASSERT_SEXT) &&((void)0) | |||
| 630 | "Unexpected hint opcode!")((void)0); | |||
| 631 | // The only correct mapping for these is to always use the source register | |||
| 632 | // bank. | |||
| 633 | const RegisterBank *RB = MRI->getRegBankOrNull(MI.getOperand(1).getReg()); | |||
| 634 | // We can assume every instruction above this one has a selected register | |||
| 635 | // bank. | |||
| 636 | assert(RB && "Expected source register to have a register bank?")((void)0); | |||
| 637 | LLVM_DEBUG(dbgs() << "... Hint always uses source's register bank.\n")do { } while (false); | |||
| 638 | MRI->setRegBank(MI.getOperand(0).getReg(), *RB); | |||
| 639 | return true; | |||
| 640 | } | |||
| 641 | ||||
| 642 | // Remember the repairing placement for all the operands. | |||
| 643 | SmallVector<RepairingPlacement, 4> RepairPts; | |||
| 644 | ||||
| 645 | const RegisterBankInfo::InstructionMapping *BestMapping; | |||
| 646 | if (OptMode == RegBankSelect::Mode::Fast) { | |||
| 647 | BestMapping = &RBI->getInstrMapping(MI); | |||
| 648 | MappingCost DefaultCost = computeMapping(MI, *BestMapping, RepairPts); | |||
| 649 | (void)DefaultCost; | |||
| 650 | if (DefaultCost == MappingCost::ImpossibleCost()) | |||
| 651 | return false; | |||
| 652 | } else { | |||
| 653 | RegisterBankInfo::InstructionMappings PossibleMappings = | |||
| 654 | RBI->getInstrPossibleMappings(MI); | |||
| 655 | if (PossibleMappings.empty()) | |||
| 656 | return false; | |||
| 657 | BestMapping = &findBestMapping(MI, PossibleMappings, RepairPts); | |||
| 658 | } | |||
| 659 | // Make sure the mapping is valid for MI. | |||
| 660 | assert(BestMapping->verify(MI) && "Invalid instruction mapping")((void)0); | |||
| 661 | ||||
| 662 | LLVM_DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n')do { } while (false); | |||
| 663 | ||||
| 664 | // After this call, MI may not be valid anymore. | |||
| 665 | // Do not use it. | |||
| 666 | return applyMapping(MI, *BestMapping, RepairPts); | |||
| 667 | } | |||
| 668 | ||||
| 669 | bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) { | |||
| 670 | // If the ISel pipeline failed, do not bother running that pass. | |||
| 671 | if (MF.getProperties().hasProperty( | |||
| ||||
| 672 | MachineFunctionProperties::Property::FailedISel)) | |||
| 673 | return false; | |||
| 674 | ||||
| 675 | LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n')do { } while (false); | |||
| 676 | const Function &F = MF.getFunction(); | |||
| 677 | Mode SaveOptMode = OptMode; | |||
| 678 | if (F.hasOptNone()) | |||
| 679 | OptMode = Mode::Fast; | |||
| 680 | init(MF); | |||
| 681 | ||||
| 682 | #ifndef NDEBUG1 | |||
| 683 | // Check that our input is fully legal: we require the function to have the | |||
| 684 | // Legalized property, so it should be. | |||
| 685 | // FIXME: This should be in the MachineVerifier. | |||
| 686 | if (!DisableGISelLegalityCheck) | |||
| 687 | if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) { | |||
| 688 | reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", | |||
| 689 | "instruction is not legal", *MI); | |||
| 690 | return false; | |||
| 691 | } | |||
| 692 | #endif | |||
| 693 | ||||
| 694 | // Walk the function and assign register banks to all operands. | |||
| 695 | // Use a RPOT to make sure all registers are assigned before we choose | |||
| 696 | // the best mapping of the current instruction. | |||
| 697 | ReversePostOrderTraversal<MachineFunction*> RPOT(&MF); | |||
| 698 | for (MachineBasicBlock *MBB : RPOT) { | |||
| 699 | // Set a sensible insertion point so that subsequent calls to | |||
| 700 | // MIRBuilder. | |||
| 701 | MIRBuilder.setMBB(*MBB); | |||
| 702 | for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end(); | |||
| 703 | MII != End;) { | |||
| 704 | // MI might be invalidated by the assignment, so move the | |||
| 705 | // iterator before hand. | |||
| 706 | MachineInstr &MI = *MII++; | |||
| 707 | ||||
| 708 | // Ignore target-specific post-isel instructions: they should use proper | |||
| 709 | // regclasses. | |||
| 710 | if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode()) | |||
| 711 | continue; | |||
| 712 | ||||
| 713 | // Ignore inline asm instructions: they should use physical | |||
| 714 | // registers/regclasses | |||
| 715 | if (MI.isInlineAsm()) | |||
| 716 | continue; | |||
| 717 | ||||
| 718 | // Ignore debug info. | |||
| 719 | if (MI.isDebugInstr()) | |||
| 720 | continue; | |||
| 721 | ||||
| 722 | // Ignore IMPLICIT_DEF which must have a regclass. | |||
| 723 | if (MI.isImplicitDef()) | |||
| 724 | continue; | |||
| 725 | ||||
| 726 | if (!assignInstr(MI)) { | |||
| 727 | reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect", | |||
| 728 | "unable to map instruction", MI); | |||
| 729 | return false; | |||
| 730 | } | |||
| 731 | ||||
| 732 | // It's possible the mapping changed control flow, and moved the following | |||
| 733 | // instruction to a new block, so figure out the new parent. | |||
| 734 | if (MII != End) { | |||
| 735 | MachineBasicBlock *NextInstBB = MII->getParent(); | |||
| 736 | if (NextInstBB != MBB) { | |||
| 737 | LLVM_DEBUG(dbgs() << "Instruction mapping changed control flow\n")do { } while (false); | |||
| 738 | MBB = NextInstBB; | |||
| 739 | MIRBuilder.setMBB(*MBB); | |||
| 740 | End = MBB->end(); | |||
| 741 | } | |||
| 742 | } | |||
| 743 | } | |||
| 744 | } | |||
| 745 | ||||
| 746 | OptMode = SaveOptMode; | |||
| 747 | return false; | |||
| 748 | } | |||
| 749 | ||||
| 750 | //------------------------------------------------------------------------------ | |||
| 751 | // Helper Classes Implementation | |||
| 752 | //------------------------------------------------------------------------------ | |||
| 753 | RegBankSelect::RepairingPlacement::RepairingPlacement( | |||
| 754 | MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P, | |||
| 755 | RepairingPlacement::RepairingKind Kind) | |||
| 756 | // Default is, we are going to insert code to repair OpIdx. | |||
| 757 | : Kind(Kind), OpIdx(OpIdx), | |||
| 758 | CanMaterialize(Kind != RepairingKind::Impossible), P(P) { | |||
| 759 | const MachineOperand &MO = MI.getOperand(OpIdx); | |||
| 760 | assert(MO.isReg() && "Trying to repair a non-reg operand")((void)0); | |||
| 761 | ||||
| 762 | if (Kind != RepairingKind::Insert) | |||
| 763 | return; | |||
| 764 | ||||
| 765 | // Repairings for definitions happen after MI, uses happen before. | |||
| 766 | bool Before = !MO.isDef(); | |||
| 767 | ||||
| 768 | // Check if we are done with MI. | |||
| 769 | if (!MI.isPHI() && !MI.isTerminator()) { | |||
| 770 | addInsertPoint(MI, Before); | |||
| 771 | // We are done with the initialization. | |||
| 772 | return; | |||
| 773 | } | |||
| 774 | ||||
| 775 | // Now, look for the special cases. | |||
| 776 | if (MI.isPHI()) { | |||
| 777 | // - PHI must be the first instructions: | |||
| 778 | // * Before, we have to split the related incoming edge. | |||
| 779 | // * After, move the insertion point past the last phi. | |||
| 780 | if (!Before) { | |||
| 781 | MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI(); | |||
| 782 | if (It != MI.getParent()->end()) | |||
| 783 | addInsertPoint(*It, /*Before*/ true); | |||
| 784 | else | |||
| 785 | addInsertPoint(*(--It), /*Before*/ false); | |||
| 786 | return; | |||
| 787 | } | |||
| 788 | // We repair a use of a phi, we may need to split the related edge. | |||
| 789 | MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB(); | |||
| 790 | // Check if we can move the insertion point prior to the | |||
| 791 | // terminators of the predecessor. | |||
| 792 | Register Reg = MO.getReg(); | |||
| 793 | MachineBasicBlock::iterator It = Pred.getLastNonDebugInstr(); | |||
| 794 | for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It) | |||
| 795 | if (It->modifiesRegister(Reg, &TRI)) { | |||
| 796 | // We cannot hoist the repairing code in the predecessor. | |||
| 797 | // Split the edge. | |||
| 798 | addInsertPoint(Pred, *MI.getParent()); | |||
| 799 | return; | |||
| 800 | } | |||
| 801 | // At this point, we can insert in Pred. | |||
| 802 | ||||
| 803 | // - If It is invalid, Pred is empty and we can insert in Pred | |||
| 804 | // wherever we want. | |||
| 805 | // - If It is valid, It is the first non-terminator, insert after It. | |||
| 806 | if (It == Pred.end()) | |||
| 807 | addInsertPoint(Pred, /*Beginning*/ false); | |||
| 808 | else | |||
| 809 | addInsertPoint(*It, /*Before*/ false); | |||
| 810 | } else { | |||
| 811 | // - Terminators must be the last instructions: | |||
| 812 | // * Before, move the insert point before the first terminator. | |||
| 813 | // * After, we have to split the outcoming edges. | |||
| 814 | if (Before) { | |||
| 815 | // Check whether Reg is defined by any terminator. | |||
| 816 | MachineBasicBlock::reverse_iterator It = MI; | |||
| 817 | auto REnd = MI.getParent()->rend(); | |||
| 818 | ||||
| 819 | for (; It != REnd && It->isTerminator(); ++It) { | |||
| 820 | assert(!It->modifiesRegister(MO.getReg(), &TRI) &&((void)0) | |||
| 821 | "copy insertion in middle of terminators not handled")((void)0); | |||
| 822 | } | |||
| 823 | ||||
| 824 | if (It == REnd) { | |||
| 825 | addInsertPoint(*MI.getParent()->begin(), true); | |||
| 826 | return; | |||
| 827 | } | |||
| 828 | ||||
| 829 | // We are sure to be right before the first terminator. | |||
| 830 | addInsertPoint(*It, /*Before*/ false); | |||
| 831 | return; | |||
| 832 | } | |||
| 833 | // Make sure Reg is not redefined by other terminators, otherwise | |||
| 834 | // we do not know how to split. | |||
| 835 | for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end(); | |||
| 836 | ++It != End;) | |||
| 837 | // The machine verifier should reject this kind of code. | |||
| 838 | assert(It->modifiesRegister(MO.getReg(), &TRI) &&((void)0) | |||
| 839 | "Do not know where to split")((void)0); | |||
| 840 | // Split each outcoming edges. | |||
| 841 | MachineBasicBlock &Src = *MI.getParent(); | |||
| 842 | for (auto &Succ : Src.successors()) | |||
| 843 | addInsertPoint(Src, Succ); | |||
| 844 | } | |||
| 845 | } | |||
| 846 | ||||
| 847 | void RegBankSelect::RepairingPlacement::addInsertPoint(MachineInstr &MI, | |||
| 848 | bool Before) { | |||
| 849 | addInsertPoint(*new InstrInsertPoint(MI, Before)); | |||
| 850 | } | |||
| 851 | ||||
| 852 | void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &MBB, | |||
| 853 | bool Beginning) { | |||
| 854 | addInsertPoint(*new MBBInsertPoint(MBB, Beginning)); | |||
| 855 | } | |||
| 856 | ||||
| 857 | void RegBankSelect::RepairingPlacement::addInsertPoint(MachineBasicBlock &Src, | |||
| 858 | MachineBasicBlock &Dst) { | |||
| 859 | addInsertPoint(*new EdgeInsertPoint(Src, Dst, P)); | |||
| 860 | } | |||
| 861 | ||||
| 862 | void RegBankSelect::RepairingPlacement::addInsertPoint( | |||
| 863 | RegBankSelect::InsertPoint &Point) { | |||
| 864 | CanMaterialize &= Point.canMaterialize(); | |||
| 865 | HasSplit |= Point.isSplit(); | |||
| 866 | InsertPoints.emplace_back(&Point); | |||
| 867 | } | |||
| 868 | ||||
| 869 | RegBankSelect::InstrInsertPoint::InstrInsertPoint(MachineInstr &Instr, | |||
| 870 | bool Before) | |||
| 871 | : InsertPoint(), Instr(Instr), Before(Before) { | |||
| 872 | // Since we do not support splitting, we do not need to update | |||
| 873 | // liveness and such, so do not do anything with P. | |||
| 874 | assert((!Before || !Instr.isPHI()) &&((void)0) | |||
| 875 | "Splitting before phis requires more points")((void)0); | |||
| 876 | assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&((void)0) | |||
| 877 | "Splitting between phis does not make sense")((void)0); | |||
| 878 | } | |||
| 879 | ||||
| 880 | void RegBankSelect::InstrInsertPoint::materialize() { | |||
| 881 | if (isSplit()) { | |||
| 882 | // Slice and return the beginning of the new block. | |||
| 883 | // If we need to split between the terminators, we theoritically | |||
| 884 | // need to know where the first and second set of terminators end | |||
| 885 | // to update the successors properly. | |||
| 886 | // Now, in pratice, we should have a maximum of 2 branch | |||
| 887 | // instructions; one conditional and one unconditional. Therefore | |||
| 888 | // we know how to update the successor by looking at the target of | |||
| 889 | // the unconditional branch. | |||
| 890 | // If we end up splitting at some point, then, we should update | |||
| 891 | // the liveness information and such. I.e., we would need to | |||
| 892 | // access P here. | |||
| 893 | // The machine verifier should actually make sure such cases | |||
| 894 | // cannot happen. | |||
| 895 | llvm_unreachable("Not yet implemented")__builtin_unreachable(); | |||
| 896 | } | |||
| 897 | // Otherwise the insertion point is just the current or next | |||
| 898 | // instruction depending on Before. I.e., there is nothing to do | |||
| 899 | // here. | |||
| 900 | } | |||
| 901 | ||||
| 902 | bool RegBankSelect::InstrInsertPoint::isSplit() const { | |||
| 903 | // If the insertion point is after a terminator, we need to split. | |||
| 904 | if (!Before) | |||
| 905 | return Instr.isTerminator(); | |||
| 906 | // If we insert before an instruction that is after a terminator, | |||
| 907 | // we are still after a terminator. | |||
| 908 | return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator(); | |||
| 909 | } | |||
| 910 | ||||
| 911 | uint64_t RegBankSelect::InstrInsertPoint::frequency(const Pass &P) const { | |||
| 912 | // Even if we need to split, because we insert between terminators, | |||
| 913 | // this split has actually the same frequency as the instruction. | |||
| 914 | const MachineBlockFrequencyInfo *MBFI = | |||
| 915 | P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); | |||
| 916 | if (!MBFI) | |||
| 917 | return 1; | |||
| 918 | return MBFI->getBlockFreq(Instr.getParent()).getFrequency(); | |||
| 919 | } | |||
| 920 | ||||
| 921 | uint64_t RegBankSelect::MBBInsertPoint::frequency(const Pass &P) const { | |||
| 922 | const MachineBlockFrequencyInfo *MBFI = | |||
| 923 | P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); | |||
| 924 | if (!MBFI) | |||
| 925 | return 1; | |||
| 926 | return MBFI->getBlockFreq(&MBB).getFrequency(); | |||
| 927 | } | |||
| 928 | ||||
| 929 | void RegBankSelect::EdgeInsertPoint::materialize() { | |||
| 930 | // If we end up repairing twice at the same place before materializing the | |||
| 931 | // insertion point, we may think we have to split an edge twice. | |||
| 932 | // We should have a factory for the insert point such that identical points | |||
| 933 | // are the same instance. | |||
| 934 | assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&((void)0) | |||
| 935 | "This point has already been split")((void)0); | |||
| 936 | MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P); | |||
| 937 | assert(NewBB && "Invalid call to materialize")((void)0); | |||
| 938 | // We reuse the destination block to hold the information of the new block. | |||
| 939 | DstOrSplit = NewBB; | |||
| 940 | } | |||
| 941 | ||||
| 942 | uint64_t RegBankSelect::EdgeInsertPoint::frequency(const Pass &P) const { | |||
| 943 | const MachineBlockFrequencyInfo *MBFI = | |||
| 944 | P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>(); | |||
| 945 | if (!MBFI) | |||
| 946 | return 1; | |||
| 947 | if (WasMaterialized) | |||
| 948 | return MBFI->getBlockFreq(DstOrSplit).getFrequency(); | |||
| 949 | ||||
| 950 | const MachineBranchProbabilityInfo *MBPI = | |||
| 951 | P.getAnalysisIfAvailable<MachineBranchProbabilityInfo>(); | |||
| 952 | if (!MBPI) | |||
| 953 | return 1; | |||
| 954 | // The basic block will be on the edge. | |||
| 955 | return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit)) | |||
| 956 | .getFrequency(); | |||
| 957 | } | |||
| 958 | ||||
| 959 | bool RegBankSelect::EdgeInsertPoint::canMaterialize() const { | |||
| 960 | // If this is not a critical edge, we should not have used this insert | |||
| 961 | // point. Indeed, either the successor or the predecessor should | |||
| 962 | // have do. | |||
| 963 | assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&((void)0) | |||
| 964 | "Edge is not critical")((void)0); | |||
| 965 | return Src.canSplitCriticalEdge(DstOrSplit); | |||
| 966 | } | |||
| 967 | ||||
| 968 | RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq) | |||
| 969 | : LocalFreq(LocalFreq.getFrequency()) {} | |||
| 970 | ||||
| 971 | bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) { | |||
| 972 | // Check if this overflows. | |||
| 973 | if (LocalCost + Cost < LocalCost) { | |||
| 974 | saturate(); | |||
| 975 | return true; | |||
| 976 | } | |||
| 977 | LocalCost += Cost; | |||
| 978 | return isSaturated(); | |||
| 979 | } | |||
| 980 | ||||
| 981 | bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) { | |||
| 982 | // Check if this overflows. | |||
| 983 | if (NonLocalCost + Cost < NonLocalCost) { | |||
| 984 | saturate(); | |||
| 985 | return true; | |||
| 986 | } | |||
| 987 | NonLocalCost += Cost; | |||
| 988 | return isSaturated(); | |||
| 989 | } | |||
| 990 | ||||
| 991 | bool RegBankSelect::MappingCost::isSaturated() const { | |||
| 992 | return LocalCost == UINT64_MAX0xffffffffffffffffULL - 1 && NonLocalCost == UINT64_MAX0xffffffffffffffffULL && | |||
| 993 | LocalFreq == UINT64_MAX0xffffffffffffffffULL; | |||
| 994 | } | |||
| 995 | ||||
| 996 | void RegBankSelect::MappingCost::saturate() { | |||
| 997 | *this = ImpossibleCost(); | |||
| 998 | --LocalCost; | |||
| 999 | } | |||
| 1000 | ||||
| 1001 | RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() { | |||
| 1002 | return MappingCost(UINT64_MAX0xffffffffffffffffULL, UINT64_MAX0xffffffffffffffffULL, UINT64_MAX0xffffffffffffffffULL); | |||
| 1003 | } | |||
| 1004 | ||||
| 1005 | bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const { | |||
| 1006 | // Sort out the easy cases. | |||
| 1007 | if (*this == Cost) | |||
| 1008 | return false; | |||
| 1009 | // If one is impossible to realize the other is cheaper unless it is | |||
| 1010 | // impossible as well. | |||
| 1011 | if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost())) | |||
| 1012 | return (*this == ImpossibleCost()) < (Cost == ImpossibleCost()); | |||
| 1013 | // If one is saturated the other is cheaper, unless it is saturated | |||
| 1014 | // as well. | |||
| 1015 | if (isSaturated() || Cost.isSaturated()) | |||
| 1016 | return isSaturated() < Cost.isSaturated(); | |||
| 1017 | // At this point we know both costs hold sensible values. | |||
| 1018 | ||||
| 1019 | // If both values have a different base frequency, there is no much | |||
| 1020 | // we can do but to scale everything. | |||
| 1021 | // However, if they have the same base frequency we can avoid making | |||
| 1022 | // complicated computation. | |||
| 1023 | uint64_t ThisLocalAdjust; | |||
| 1024 | uint64_t OtherLocalAdjust; | |||
| 1025 | if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)__builtin_expect((bool)(LocalFreq == Cost.LocalFreq), true)) { | |||
| 1026 | ||||
| 1027 | // At this point, we know the local costs are comparable. | |||
| 1028 | // Do the case that do not involve potential overflow first. | |||
| 1029 | if (NonLocalCost == Cost.NonLocalCost) | |||
| 1030 | // Since the non-local costs do not discriminate on the result, | |||
| 1031 | // just compare the local costs. | |||
| 1032 | return LocalCost < Cost.LocalCost; | |||
| 1033 | ||||
| 1034 | // The base costs are comparable so we may only keep the relative | |||
| 1035 | // value to increase our chances of avoiding overflows. | |||
| 1036 | ThisLocalAdjust = 0; | |||
| 1037 | OtherLocalAdjust = 0; | |||
| 1038 | if (LocalCost < Cost.LocalCost) | |||
| 1039 | OtherLocalAdjust = Cost.LocalCost - LocalCost; | |||
| 1040 | else | |||
| 1041 | ThisLocalAdjust = LocalCost - Cost.LocalCost; | |||
| 1042 | } else { | |||
| 1043 | ThisLocalAdjust = LocalCost; | |||
| 1044 | OtherLocalAdjust = Cost.LocalCost; | |||
| 1045 | } | |||
| 1046 | ||||
| 1047 | // The non-local costs are comparable, just keep the relative value. | |||
| 1048 | uint64_t ThisNonLocalAdjust = 0; | |||
| 1049 | uint64_t OtherNonLocalAdjust = 0; | |||
| 1050 | if (NonLocalCost < Cost.NonLocalCost) | |||
| 1051 | OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost; | |||
| 1052 | else | |||
| 1053 | ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost; | |||
| 1054 | // Scale everything to make them comparable. | |||
| 1055 | uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq; | |||
| 1056 | // Check for overflow on that operation. | |||
| 1057 | bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust || | |||
| 1058 | ThisScaledCost < LocalFreq); | |||
| 1059 | uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq; | |||
| 1060 | // Check for overflow on the last operation. | |||
| 1061 | bool OtherOverflows = | |||
| 1062 | OtherLocalAdjust && | |||
| 1063 | (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq); | |||
| 1064 | // Add the non-local costs. | |||
| 1065 | ThisOverflows |= ThisNonLocalAdjust && | |||
| 1066 | ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust; | |||
| 1067 | ThisScaledCost += ThisNonLocalAdjust; | |||
| 1068 | OtherOverflows |= OtherNonLocalAdjust && | |||
| 1069 | OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust; | |||
| 1070 | OtherScaledCost += OtherNonLocalAdjust; | |||
| 1071 | // If both overflows, we cannot compare without additional | |||
| 1072 | // precision, e.g., APInt. Just give up on that case. | |||
| 1073 | if (ThisOverflows && OtherOverflows) | |||
| 1074 | return false; | |||
| 1075 | // If one overflows but not the other, we can still compare. | |||
| 1076 | if (ThisOverflows || OtherOverflows) | |||
| 1077 | return ThisOverflows < OtherOverflows; | |||
| 1078 | // Otherwise, just compare the values. | |||
| 1079 | return ThisScaledCost < OtherScaledCost; | |||
| 1080 | } | |||
| 1081 | ||||
| 1082 | bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const { | |||
| 1083 | return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost && | |||
| 1084 | LocalFreq == Cost.LocalFreq; | |||
| 1085 | } | |||
| 1086 | ||||
| 1087 | #if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP) | |||
| 1088 | LLVM_DUMP_METHOD__attribute__((noinline)) void RegBankSelect::MappingCost::dump() const { | |||
| 1089 | print(dbgs()); | |||
| 1090 | dbgs() << '\n'; | |||
| 1091 | } | |||
| 1092 | #endif | |||
| 1093 | ||||
| 1094 | void RegBankSelect::MappingCost::print(raw_ostream &OS) const { | |||
| 1095 | if (*this == ImpossibleCost()) { | |||
| 1096 | OS << "impossible"; | |||
| 1097 | return; | |||
| 1098 | } | |||
| 1099 | if (isSaturated()) { | |||
| 1100 | OS << "saturated"; | |||
| 1101 | return; | |||
| 1102 | } | |||
| 1103 | OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost; | |||
| 1104 | } |