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