LLVM 19.0.0git
RegBankSelect.cpp
Go to the documentation of this file.
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
14#include "llvm/ADT/STLExtras.h"
32#include "llvm/Config/llvm-config.h"
33#include "llvm/IR/Function.h"
35#include "llvm/Pass.h"
39#include "llvm/Support/Debug.h"
42#include <algorithm>
43#include <cassert>
44#include <cstdint>
45#include <limits>
46#include <memory>
47#include <utility>
48
49#define DEBUG_TYPE "regbankselect"
50
51using namespace llvm;
52
54 cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional,
55 cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast",
56 "Run the Fast mode (default mapping)"),
57 clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy",
58 "Use the Greedy mode (best local mapping)")));
59
60char RegBankSelect::ID = 0;
61
63 "Assign register bank of generic virtual registers",
64 false, false);
69 "Assign register bank of generic virtual registers", false,
70 false)
71
72RegBankSelect::RegBankSelect(char &PassID, Mode RunningMode)
73 : MachineFunctionPass(PassID), OptMode(RunningMode) {
74 if (RegBankSelectMode.getNumOccurrences() != 0) {
75 OptMode = RegBankSelectMode;
76 if (RegBankSelectMode != RunningMode)
77 LLVM_DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n");
78 }
79}
80
83 assert(RBI && "Cannot work without RegisterBankInfo");
84 MRI = &MF.getRegInfo();
86 TPC = &getAnalysis<TargetPassConfig>();
87 if (OptMode != Mode::Fast) {
88 MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
89 MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
90 } else {
91 MBFI = nullptr;
92 MBPI = nullptr;
93 }
94 MIRBuilder.setMF(MF);
95 MORE = std::make_unique<MachineOptimizationRemarkEmitter>(MF, MBFI);
96}
97
99 if (OptMode != Mode::Fast) {
100 // We could preserve the information from these two analysis but
101 // the APIs do not allow to do so yet.
104 }
108}
109
111 Register Reg, const RegisterBankInfo::ValueMapping &ValMapping,
112 bool &OnlyAssign) const {
113 // By default we assume we will have to repair something.
114 OnlyAssign = false;
115 // Each part of a break down needs to end up in a different register.
116 // In other word, Reg assignment does not match.
117 if (ValMapping.NumBreakDowns != 1)
118 return false;
119
120 const RegisterBank *CurRegBank = RBI->getRegBank(Reg, *MRI, *TRI);
121 const RegisterBank *DesiredRegBank = ValMapping.BreakDown[0].RegBank;
122 // Reg is free of assignment, a simple assignment will make the
123 // register bank to match.
124 OnlyAssign = CurRegBank == nullptr;
125 LLVM_DEBUG(dbgs() << "Does assignment already match: ";
126 if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";
127 dbgs() << " against ";
128 assert(DesiredRegBank && "The mapping must be valid");
129 dbgs() << *DesiredRegBank << '\n';);
130 return CurRegBank == DesiredRegBank;
131}
132
134 MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping,
137
138 assert(ValMapping.NumBreakDowns == (unsigned)size(NewVRegs) &&
139 "need new vreg for each breakdown");
140
141 // An empty range of new register means no repairing.
142 assert(!NewVRegs.empty() && "We should not have to repair");
143
145 if (ValMapping.NumBreakDowns == 1) {
146 // Assume we are repairing a use and thus, the original reg will be
147 // the source of the repairing.
148 Register Src = MO.getReg();
149 Register Dst = *NewVRegs.begin();
150
151 // If we repair a definition, swap the source and destination for
152 // the repairing.
153 if (MO.isDef())
154 std::swap(Src, Dst);
155
156 assert((RepairPt.getNumInsertPoints() == 1 || Dst.isPhysical()) &&
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 MI = MIRBuilder.buildInstrNoInsert(TargetOpcode::COPY)
163 .addDef(Dst)
164 .addUse(Src);
165 LLVM_DEBUG(dbgs() << "Copy: " << printReg(Src) << ':'
166 << printRegClassOrBank(Src, *MRI, TRI)
167 << " to: " << printReg(Dst) << ':'
168 << printRegClassOrBank(Dst, *MRI, TRI) << '\n');
169 } else {
170 // TODO: Support with G_IMPLICIT_DEF + G_INSERT sequence or G_EXTRACT
171 // sequence.
172 assert(ValMapping.partsAllUniform() && "irregular breakdowns not supported");
173
174 LLT RegTy = MRI->getType(MO.getReg());
175 if (MO.isDef()) {
176 unsigned MergeOp;
177 if (RegTy.isVector()) {
178 if (ValMapping.NumBreakDowns == RegTy.getNumElements())
179 MergeOp = TargetOpcode::G_BUILD_VECTOR;
180 else {
181 assert(
182 (ValMapping.BreakDown[0].Length * ValMapping.NumBreakDowns ==
183 RegTy.getSizeInBits()) &&
184 (ValMapping.BreakDown[0].Length % RegTy.getScalarSizeInBits() ==
185 0) &&
186 "don't understand this value breakdown");
187
188 MergeOp = TargetOpcode::G_CONCAT_VECTORS;
189 }
190 } else
191 MergeOp = TargetOpcode::G_MERGE_VALUES;
192
193 auto MergeBuilder =
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
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
238 const MachineOperand &MO,
239 const RegisterBankInfo::ValueMapping &ValMapping) const {
240 assert(MO.isReg() && "We should only repair register operand");
241 assert(ValMapping.NumBreakDowns && "Nothing to map??");
242
243 bool IsSameNumOfValues = ValMapping.NumBreakDowns == 1;
244 const RegisterBank *CurRegBank = RBI->getRegBank(MO.getReg(), *MRI, *TRI);
245 // If MO does not have a register bank, we should have just been
246 // able to set one unless we have to break the value down.
247 assert(CurRegBank || MO.isDef());
248
249 // Def: Val <- NewDefs
250 // Same number of values: copy
251 // Different number: Val = build_sequence Defs1, Defs2, ...
252 // Use: NewSources <- Val.
253 // Same number of values: copy.
254 // Different number: Src1, Src2, ... =
255 // extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ...
256 // We should remember that this value is available somewhere else to
257 // coalesce the value.
258
259 if (ValMapping.NumBreakDowns != 1)
260 return RBI->getBreakDownCost(ValMapping, CurRegBank);
261
262 if (IsSameNumOfValues) {
263 const RegisterBank *DesiredRegBank = ValMapping.BreakDown[0].RegBank;
264 // If we repair a definition, swap the source and destination for
265 // the repairing.
266 if (MO.isDef())
267 std::swap(CurRegBank, DesiredRegBank);
268 // TODO: It may be possible to actually avoid the copy.
269 // If we repair something where the source is defined by a copy
270 // and the source of that copy is on the right bank, we can reuse
271 // it for free.
272 // E.g.,
273 // RegToRepair<BankA> = copy AlternativeSrc<BankB>
274 // = op RegToRepair<BankA>
275 // We can simply propagate AlternativeSrc instead of copying RegToRepair
276 // into a new virtual register.
277 // We would also need to propagate this information in the
278 // repairing placement.
279 unsigned Cost = RBI->copyCost(*DesiredRegBank, *CurRegBank,
280 RBI->getSizeInBits(MO.getReg(), *MRI, *TRI));
281 // TODO: use a dedicated constant for ImpossibleCost.
282 if (Cost != std::numeric_limits<unsigned>::max())
283 return Cost;
284 // Return the legalization cost of that repairing.
285 }
286 return std::numeric_limits<unsigned>::max();
287}
288
292 assert(!PossibleMappings.empty() &&
293 "Do not know how to map this instruction");
294
295 const RegisterBankInfo::InstructionMapping *BestMapping = nullptr;
298 for (const RegisterBankInfo::InstructionMapping *CurMapping :
299 PossibleMappings) {
300 MappingCost CurCost =
301 computeMapping(MI, *CurMapping, LocalRepairPts, &Cost);
302 if (CurCost < Cost) {
303 LLVM_DEBUG(dbgs() << "New best: " << CurCost << '\n');
304 Cost = CurCost;
305 BestMapping = CurMapping;
306 RepairPts.clear();
307 for (RepairingPlacement &RepairPt : LocalRepairPts)
308 RepairPts.emplace_back(std::move(RepairPt));
309 }
310 }
311 if (!BestMapping && !TPC->isGlobalISelAbortEnabled()) {
312 // If none of the mapping worked that means they are all impossible.
313 // Thus, pick the first one and set an impossible repairing point.
314 // It will trigger the failed isel mode.
315 BestMapping = *PossibleMappings.begin();
316 RepairPts.emplace_back(
318 } else
319 assert(BestMapping && "No suitable mapping for instruction");
320 return *BestMapping;
321}
322
325 const RegisterBankInfo::ValueMapping &ValMapping) const {
326 const MachineInstr &MI = *MO.getParent();
327 assert(RepairPt.hasSplit() && "We should not have to adjust for split");
328 // Splitting should only occur for PHIs or between terminators,
329 // because we only do local repairing.
330 assert((MI.isPHI() || MI.isTerminator()) && "Why do we split?");
331
332 assert(&MI.getOperand(RepairPt.getOpIdx()) == &MO &&
333 "Repairing placement does not match operand");
334
335 // If we need splitting for phis, that means it is because we
336 // could not find an insertion point before the terminators of
337 // the predecessor block for this argument. In other words,
338 // the input value is defined by one of the terminators.
339 assert((!MI.isPHI() || !MO.isDef()) && "Need split for phi def?");
340
341 // We split to repair the use of a phi or a terminator.
342 if (!MO.isDef()) {
343 if (MI.isTerminator()) {
344 assert(&MI != &(*MI.getParent()->getFirstTerminator()) &&
345 "Need to split for the first terminator?!");
346 } else {
347 // For the PHI case, the split may not be actually required.
348 // In the copy case, a phi is already a copy on the incoming edge,
349 // therefore there is no need to split.
350 if (ValMapping.NumBreakDowns == 1)
351 // This is a already a copy, there is nothing to do.
353 }
354 return;
355 }
356
357 // At this point, we need to repair a defintion of a terminator.
358
359 // Technically we need to fix the def of MI on all outgoing
360 // edges of MI to keep the repairing local. In other words, we
361 // will create several definitions of the same register. This
362 // does not work for SSA unless that definition is a physical
363 // register.
364 // However, there are other cases where we can get away with
365 // that while still keeping the repairing local.
366 assert(MI.isTerminator() && MO.isDef() &&
367 "This code is for the def of a terminator");
368
369 // Since we use RPO traversal, if we need to repair a definition
370 // this means this definition could be:
371 // 1. Used by PHIs (i.e., this VReg has been visited as part of the
372 // uses of a phi.), or
373 // 2. Part of a target specific instruction (i.e., the target applied
374 // some register class constraints when creating the instruction.)
375 // If the constraints come for #2, the target said that another mapping
376 // is supported so we may just drop them. Indeed, if we do not change
377 // the number of registers holding that value, the uses will get fixed
378 // when we get to them.
379 // Uses in PHIs may have already been proceeded though.
380 // If the constraints come for #1, then, those are weak constraints and
381 // no actual uses may rely on them. However, the problem remains mainly
382 // the same as for #2. If the value stays in one register, we could
383 // just switch the register bank of the definition, but we would need to
384 // account for a repairing cost for each phi we silently change.
385 //
386 // In any case, if the value needs to be broken down into several
387 // registers, the repairing is not local anymore as we need to patch
388 // every uses to rebuild the value in just one register.
389 //
390 // To summarize:
391 // - If the value is in a physical register, we can do the split and
392 // fix locally.
393 // Otherwise if the value is in a virtual register:
394 // - If the value remains in one register, we do not have to split
395 // just switching the register bank would do, but we need to account
396 // in the repairing cost all the phi we changed.
397 // - If the value spans several registers, then we cannot do a local
398 // repairing.
399
400 // Check if this is a physical or virtual register.
401 Register Reg = MO.getReg();
402 if (Reg.isPhysical()) {
403 // We are going to split every outgoing edges.
404 // Check that this is possible.
405 // FIXME: The machine representation is currently broken
406 // since it also several terminators in one basic block.
407 // Because of that we would technically need a way to get
408 // the targets of just one terminator to know which edges
409 // we have to split.
410 // Assert that we do not hit the ill-formed representation.
411
412 // If there are other terminators before that one, some of
413 // the outgoing edges may not be dominated by this definition.
414 assert(&MI == &(*MI.getParent()->getFirstTerminator()) &&
415 "Do not know which outgoing edges are relevant");
416 const MachineInstr *Next = MI.getNextNode();
417 assert((!Next || Next->isUnconditionalBranch()) &&
418 "Do not know where each terminator ends up");
419 if (Next)
420 // If the next terminator uses Reg, this means we have
421 // to split right after MI and thus we need a way to ask
422 // which outgoing edges are affected.
423 assert(!Next->readsRegister(Reg) && "Need to split between terminators");
424 // We will split all the edges and repair there.
425 } else {
426 // This is a virtual register defined by a terminator.
427 if (ValMapping.NumBreakDowns == 1) {
428 // There is nothing to repair, but we may actually lie on
429 // the repairing cost because of the PHIs already proceeded
430 // as already stated.
431 // Though the code will be correct.
432 assert(false && "Repairing cost may not be accurate");
433 } else {
434 // We need to do non-local repairing. Basically, patch all
435 // the uses (i.e., phis) that we already proceeded.
436 // For now, just say this mapping is not possible.
438 }
439 }
440}
441
445 const RegBankSelect::MappingCost *BestCost) {
446 assert((MBFI || !BestCost) && "Costs comparison require MBFI");
447
448 if (!InstrMapping.isValid())
450
451 // If mapped with InstrMapping, MI will have the recorded cost.
452 MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent())
453 : BlockFrequency(1));
454 bool Saturated = Cost.addLocalCost(InstrMapping.getCost());
455 assert(!Saturated && "Possible mapping saturated the cost");
456 LLVM_DEBUG(dbgs() << "Evaluating mapping cost for: " << MI);
457 LLVM_DEBUG(dbgs() << "With: " << InstrMapping << '\n');
458 RepairPts.clear();
459 if (BestCost && Cost > *BestCost) {
460 LLVM_DEBUG(dbgs() << "Mapping is too expensive from the start\n");
461 return Cost;
462 }
463 const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
464
465 // Moreover, to realize this mapping, the register bank of each operand must
466 // match this mapping. In other words, we may need to locally reassign the
467 // register banks. Account for that repairing cost as well.
468 // In this context, local means in the surrounding of MI.
469 for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();
470 OpIdx != EndOpIdx; ++OpIdx) {
471 const MachineOperand &MO = MI.getOperand(OpIdx);
472 if (!MO.isReg())
473 continue;
474 Register Reg = MO.getReg();
475 if (!Reg)
476 continue;
477 LLT Ty = MRI.getType(Reg);
478 if (!Ty.isValid())
479 continue;
480
481 LLVM_DEBUG(dbgs() << "Opd" << OpIdx << '\n');
482 const RegisterBankInfo::ValueMapping &ValMapping =
483 InstrMapping.getOperandMapping(OpIdx);
484 // If Reg is already properly mapped, this is free.
485 bool Assign;
486 if (assignmentMatch(Reg, ValMapping, Assign)) {
487 LLVM_DEBUG(dbgs() << "=> is free (match).\n");
488 continue;
489 }
490 if (Assign) {
491 LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n");
492 RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,
494 continue;
495 }
496
497 // Find the insertion point for the repairing code.
498 RepairPts.emplace_back(
500 RepairingPlacement &RepairPt = RepairPts.back();
501
502 // If we need to split a basic block to materialize this insertion point,
503 // we may give a higher cost to this mapping.
504 // Nevertheless, we may get away with the split, so try that first.
505 if (RepairPt.hasSplit())
506 tryAvoidingSplit(RepairPt, MO, ValMapping);
507
508 // Check that the materialization of the repairing is possible.
509 if (!RepairPt.canMaterialize()) {
510 LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n");
512 }
513
514 // Account for the split cost and repair cost.
515 // Unless the cost is already saturated or we do not care about the cost.
516 if (!BestCost || Saturated)
517 continue;
518
519 // To get accurate information we need MBFI and MBPI.
520 // Thus, if we end up here this information should be here.
521 assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI");
522
523 // FIXME: We will have to rework the repairing cost model.
524 // The repairing cost depends on the register bank that MO has.
525 // However, when we break down the value into different values,
526 // MO may not have a register bank while still needing repairing.
527 // For the fast mode, we don't compute the cost so that is fine,
528 // but still for the repairing code, we will have to make a choice.
529 // For the greedy mode, we should choose greedily what is the best
530 // choice based on the next use of MO.
531
532 // Sums up the repairing cost of MO at each insertion point.
533 uint64_t RepairCost = getRepairCost(MO, ValMapping);
534
535 // This is an impossible to repair cost.
536 if (RepairCost == std::numeric_limits<unsigned>::max())
538
539 // Bias used for splitting: 5%.
540 const uint64_t PercentageForBias = 5;
541 uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100;
542 // We should not need more than a couple of instructions to repair
543 // an assignment. In other words, the computation should not
544 // overflow because the repairing cost is free of basic block
545 // frequency.
546 assert(((RepairCost < RepairCost * PercentageForBias) &&
547 (RepairCost * PercentageForBias <
548 RepairCost * PercentageForBias + 99)) &&
549 "Repairing involves more than a billion of instructions?!");
550 for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
551 assert(InsertPt->canMaterialize() && "We should not have made it here");
552 // We will applied some basic block frequency and those uses uint64_t.
553 if (!InsertPt->isSplit())
554 Saturated = Cost.addLocalCost(RepairCost);
555 else {
556 uint64_t CostForInsertPt = RepairCost;
557 // Again we shouldn't overflow here givent that
558 // CostForInsertPt is frequency free at this point.
559 assert(CostForInsertPt + Bias > CostForInsertPt &&
560 "Repairing + split bias overflows");
561 CostForInsertPt += Bias;
562 uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt;
563 // Check if we just overflowed.
564 if ((Saturated = PtCost < CostForInsertPt))
565 Cost.saturate();
566 else
567 Saturated = Cost.addNonLocalCost(PtCost);
568 }
569
570 // Stop looking into what it takes to repair, this is already
571 // too expensive.
572 if (BestCost && Cost > *BestCost) {
573 LLVM_DEBUG(dbgs() << "Mapping is too expensive, stop processing\n");
574 return Cost;
575 }
576
577 // No need to accumulate more cost information.
578 // We need to still gather the repairing information though.
579 if (Saturated)
580 break;
581 }
582 }
583 LLVM_DEBUG(dbgs() << "Total cost is: " << Cost << "\n");
584 return Cost;
585}
586
590 // OpdMapper will hold all the information needed for the rewriting.
591 RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI);
592
593 // First, place the repairing code.
594 for (RepairingPlacement &RepairPt : RepairPts) {
595 if (!RepairPt.canMaterialize() ||
596 RepairPt.getKind() == RepairingPlacement::Impossible)
597 return false;
598 assert(RepairPt.getKind() != RepairingPlacement::None &&
599 "This should not make its way in the list");
600 unsigned OpIdx = RepairPt.getOpIdx();
601 MachineOperand &MO = MI.getOperand(OpIdx);
602 const RegisterBankInfo::ValueMapping &ValMapping =
603 InstrMapping.getOperandMapping(OpIdx);
604 Register Reg = MO.getReg();
605
606 switch (RepairPt.getKind()) {
608 assert(ValMapping.NumBreakDowns == 1 &&
609 "Reassignment should only be for simple mapping");
610 MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);
611 break;
613 // Don't insert additional instruction for debug instruction.
614 if (MI.isDebugInstr())
615 break;
616 OpdMapper.createVRegs(OpIdx);
617 if (!repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx)))
618 return false;
619 break;
620 default:
621 llvm_unreachable("Other kind should not happen");
622 }
623 }
624
625 // Second, rewrite the instruction.
626 LLVM_DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n');
627 RBI->applyMapping(MIRBuilder, OpdMapper);
628
629 return true;
630}
631
633 LLVM_DEBUG(dbgs() << "Assign: " << MI);
634
635 unsigned Opc = MI.getOpcode();
637 assert((Opc == TargetOpcode::G_ASSERT_ZEXT ||
638 Opc == TargetOpcode::G_ASSERT_SEXT ||
639 Opc == TargetOpcode::G_ASSERT_ALIGN) &&
640 "Unexpected hint opcode!");
641 // The only correct mapping for these is to always use the source register
642 // bank.
643 const RegisterBank *RB =
644 RBI->getRegBank(MI.getOperand(1).getReg(), *MRI, *TRI);
645 // We can assume every instruction above this one has a selected register
646 // bank.
647 assert(RB && "Expected source register to have a register bank?");
648 LLVM_DEBUG(dbgs() << "... Hint always uses source's register bank.\n");
649 MRI->setRegBank(MI.getOperand(0).getReg(), *RB);
650 return true;
651 }
652
653 // Remember the repairing placement for all the operands.
655
656 const RegisterBankInfo::InstructionMapping *BestMapping;
658 BestMapping = &RBI->getInstrMapping(MI);
659 MappingCost DefaultCost = computeMapping(MI, *BestMapping, RepairPts);
660 (void)DefaultCost;
661 if (DefaultCost == MappingCost::ImpossibleCost())
662 return false;
663 } else {
666 if (PossibleMappings.empty())
667 return false;
668 BestMapping = &findBestMapping(MI, PossibleMappings, RepairPts);
669 }
670 // Make sure the mapping is valid for MI.
671 assert(BestMapping->verify(MI) && "Invalid instruction mapping");
672
673 LLVM_DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n');
674
675 // After this call, MI may not be valid anymore.
676 // Do not use it.
677 return applyMapping(MI, *BestMapping, RepairPts);
678}
679
681 // Walk the function and assign register banks to all operands.
682 // Use a RPOT to make sure all registers are assigned before we choose
683 // the best mapping of the current instruction.
685 for (MachineBasicBlock *MBB : RPOT) {
686 // Set a sensible insertion point so that subsequent calls to
687 // MIRBuilder.
691
692 while (!WorkList.empty()) {
693 MachineInstr &MI = *WorkList.pop_back_val();
694
695 // Ignore target-specific post-isel instructions: they should use proper
696 // regclasses.
697 if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode())
698 continue;
699
700 // Ignore inline asm instructions: they should use physical
701 // registers/regclasses
702 if (MI.isInlineAsm())
703 continue;
704
705 // Ignore IMPLICIT_DEF which must have a regclass.
706 if (MI.isImplicitDef())
707 continue;
708
709 if (!assignInstr(MI)) {
710 reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
711 "unable to map instruction", MI);
712 return false;
713 }
714 }
715 }
716
717 return true;
718}
719
721#ifndef NDEBUG
723 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
724 reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
725 "instruction is not legal", *MI);
726 return false;
727 }
728 }
729#endif
730 return true;
731}
732
734 // If the ISel pipeline failed, do not bother running that pass.
735 if (MF.getProperties().hasProperty(
737 return false;
738
739 LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
740 const Function &F = MF.getFunction();
741 Mode SaveOptMode = OptMode;
742 if (F.hasOptNone())
744 init(MF);
745
746#ifndef NDEBUG
747 if (!checkFunctionIsLegal(MF))
748 return false;
749#endif
750
752
753 OptMode = SaveOptMode;
754 return false;
755}
756
757//------------------------------------------------------------------------------
758// Helper Classes Implementation
759//------------------------------------------------------------------------------
761 MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P,
763 // Default is, we are going to insert code to repair OpIdx.
764 : Kind(Kind), OpIdx(OpIdx),
765 CanMaterialize(Kind != RepairingKind::Impossible), P(P) {
766 const MachineOperand &MO = MI.getOperand(OpIdx);
767 assert(MO.isReg() && "Trying to repair a non-reg operand");
768
769 if (Kind != RepairingKind::Insert)
770 return;
771
772 // Repairings for definitions happen after MI, uses happen before.
773 bool Before = !MO.isDef();
774
775 // Check if we are done with MI.
776 if (!MI.isPHI() && !MI.isTerminator()) {
778 // We are done with the initialization.
779 return;
780 }
781
782 // Now, look for the special cases.
783 if (MI.isPHI()) {
784 // - PHI must be the first instructions:
785 // * Before, we have to split the related incoming edge.
786 // * After, move the insertion point past the last phi.
787 if (!Before) {
788 MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI();
789 if (It != MI.getParent()->end())
790 addInsertPoint(*It, /*Before*/ true);
791 else
792 addInsertPoint(*(--It), /*Before*/ false);
793 return;
794 }
795 // We repair a use of a phi, we may need to split the related edge.
796 MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB();
797 // Check if we can move the insertion point prior to the
798 // terminators of the predecessor.
799 Register Reg = MO.getReg();
801 for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It)
802 if (It->modifiesRegister(Reg, &TRI)) {
803 // We cannot hoist the repairing code in the predecessor.
804 // Split the edge.
805 addInsertPoint(Pred, *MI.getParent());
806 return;
807 }
808 // At this point, we can insert in Pred.
809
810 // - If It is invalid, Pred is empty and we can insert in Pred
811 // wherever we want.
812 // - If It is valid, It is the first non-terminator, insert after It.
813 if (It == Pred.end())
814 addInsertPoint(Pred, /*Beginning*/ false);
815 else
816 addInsertPoint(*It, /*Before*/ false);
817 } else {
818 // - Terminators must be the last instructions:
819 // * Before, move the insert point before the first terminator.
820 // * After, we have to split the outcoming edges.
821 if (Before) {
822 // Check whether Reg is defined by any terminator.
824 auto REnd = MI.getParent()->rend();
825
826 for (; It != REnd && It->isTerminator(); ++It) {
827 assert(!It->modifiesRegister(MO.getReg(), &TRI) &&
828 "copy insertion in middle of terminators not handled");
829 }
830
831 if (It == REnd) {
832 addInsertPoint(*MI.getParent()->begin(), true);
833 return;
834 }
835
836 // We are sure to be right before the first terminator.
837 addInsertPoint(*It, /*Before*/ false);
838 return;
839 }
840 // Make sure Reg is not redefined by other terminators, otherwise
841 // we do not know how to split.
842 for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();
843 ++It != End;)
844 // The machine verifier should reject this kind of code.
845 assert(It->modifiesRegister(MO.getReg(), &TRI) &&
846 "Do not know where to split");
847 // Split each outcoming edges.
848 MachineBasicBlock &Src = *MI.getParent();
849 for (auto &Succ : Src.successors())
850 addInsertPoint(Src, Succ);
851 }
852}
853
855 bool Before) {
856 addInsertPoint(*new InstrInsertPoint(MI, Before));
857}
858
860 bool Beginning) {
861 addInsertPoint(*new MBBInsertPoint(MBB, Beginning));
862}
863
865 MachineBasicBlock &Dst) {
866 addInsertPoint(*new EdgeInsertPoint(Src, Dst, P));
867}
868
871 CanMaterialize &= Point.canMaterialize();
872 HasSplit |= Point.isSplit();
873 InsertPoints.emplace_back(&Point);
874}
875
877 bool Before)
878 : Instr(Instr), Before(Before) {
879 // Since we do not support splitting, we do not need to update
880 // liveness and such, so do not do anything with P.
881 assert((!Before || !Instr.isPHI()) &&
882 "Splitting before phis requires more points");
883 assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&
884 "Splitting between phis does not make sense");
885}
886
887void RegBankSelect::InstrInsertPoint::materialize() {
888 if (isSplit()) {
889 // Slice and return the beginning of the new block.
890 // If we need to split between the terminators, we theoritically
891 // need to know where the first and second set of terminators end
892 // to update the successors properly.
893 // Now, in pratice, we should have a maximum of 2 branch
894 // instructions; one conditional and one unconditional. Therefore
895 // we know how to update the successor by looking at the target of
896 // the unconditional branch.
897 // If we end up splitting at some point, then, we should update
898 // the liveness information and such. I.e., we would need to
899 // access P here.
900 // The machine verifier should actually make sure such cases
901 // cannot happen.
902 llvm_unreachable("Not yet implemented");
903 }
904 // Otherwise the insertion point is just the current or next
905 // instruction depending on Before. I.e., there is nothing to do
906 // here.
907}
908
910 // If the insertion point is after a terminator, we need to split.
911 if (!Before)
912 return Instr.isTerminator();
913 // If we insert before an instruction that is after a terminator,
914 // we are still after a terminator.
915 return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator();
916}
917
919 // Even if we need to split, because we insert between terminators,
920 // this split has actually the same frequency as the instruction.
922 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
923 if (!MBFI)
924 return 1;
925 return MBFI->getBlockFreq(Instr.getParent()).getFrequency();
926}
927
930 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
931 if (!MBFI)
932 return 1;
933 return MBFI->getBlockFreq(&MBB).getFrequency();
934}
935
936void RegBankSelect::EdgeInsertPoint::materialize() {
937 // If we end up repairing twice at the same place before materializing the
938 // insertion point, we may think we have to split an edge twice.
939 // We should have a factory for the insert point such that identical points
940 // are the same instance.
941 assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&
942 "This point has already been split");
943 MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P);
944 assert(NewBB && "Invalid call to materialize");
945 // We reuse the destination block to hold the information of the new block.
946 DstOrSplit = NewBB;
947}
948
951 P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
952 if (!MBFI)
953 return 1;
954 if (WasMaterialized)
955 return MBFI->getBlockFreq(DstOrSplit).getFrequency();
956
958 P.getAnalysisIfAvailable<MachineBranchProbabilityInfo>();
959 if (!MBPI)
960 return 1;
961 // The basic block will be on the edge.
962 return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit))
963 .getFrequency();
964}
965
967 // If this is not a critical edge, we should not have used this insert
968 // point. Indeed, either the successor or the predecessor should
969 // have do.
970 assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&
971 "Edge is not critical");
972 return Src.canSplitCriticalEdge(DstOrSplit);
973}
974
975RegBankSelect::MappingCost::MappingCost(BlockFrequency LocalFreq)
976 : LocalFreq(LocalFreq.getFrequency()) {}
977
979 // Check if this overflows.
980 if (LocalCost + Cost < LocalCost) {
981 saturate();
982 return true;
983 }
984 LocalCost += Cost;
985 return isSaturated();
986}
987
989 // Check if this overflows.
990 if (NonLocalCost + Cost < NonLocalCost) {
991 saturate();
992 return true;
993 }
994 NonLocalCost += Cost;
995 return isSaturated();
996}
997
998bool RegBankSelect::MappingCost::isSaturated() const {
999 return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&
1000 LocalFreq == UINT64_MAX;
1001}
1002
1004 *this = ImpossibleCost();
1005 --LocalCost;
1006}
1007
1010}
1011
1013 // Sort out the easy cases.
1014 if (*this == Cost)
1015 return false;
1016 // If one is impossible to realize the other is cheaper unless it is
1017 // impossible as well.
1018 if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))
1019 return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());
1020 // If one is saturated the other is cheaper, unless it is saturated
1021 // as well.
1022 if (isSaturated() || Cost.isSaturated())
1023 return isSaturated() < Cost.isSaturated();
1024 // At this point we know both costs hold sensible values.
1025
1026 // If both values have a different base frequency, there is no much
1027 // we can do but to scale everything.
1028 // However, if they have the same base frequency we can avoid making
1029 // complicated computation.
1030 uint64_t ThisLocalAdjust;
1031 uint64_t OtherLocalAdjust;
1032 if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {
1033
1034 // At this point, we know the local costs are comparable.
1035 // Do the case that do not involve potential overflow first.
1036 if (NonLocalCost == Cost.NonLocalCost)
1037 // Since the non-local costs do not discriminate on the result,
1038 // just compare the local costs.
1039 return LocalCost < Cost.LocalCost;
1040
1041 // The base costs are comparable so we may only keep the relative
1042 // value to increase our chances of avoiding overflows.
1043 ThisLocalAdjust = 0;
1044 OtherLocalAdjust = 0;
1045 if (LocalCost < Cost.LocalCost)
1046 OtherLocalAdjust = Cost.LocalCost - LocalCost;
1047 else
1048 ThisLocalAdjust = LocalCost - Cost.LocalCost;
1049 } else {
1050 ThisLocalAdjust = LocalCost;
1051 OtherLocalAdjust = Cost.LocalCost;
1052 }
1053
1054 // The non-local costs are comparable, just keep the relative value.
1055 uint64_t ThisNonLocalAdjust = 0;
1056 uint64_t OtherNonLocalAdjust = 0;
1057 if (NonLocalCost < Cost.NonLocalCost)
1058 OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;
1059 else
1060 ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;
1061 // Scale everything to make them comparable.
1062 uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;
1063 // Check for overflow on that operation.
1064 bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||
1065 ThisScaledCost < LocalFreq);
1066 uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;
1067 // Check for overflow on the last operation.
1068 bool OtherOverflows =
1069 OtherLocalAdjust &&
1070 (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);
1071 // Add the non-local costs.
1072 ThisOverflows |= ThisNonLocalAdjust &&
1073 ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;
1074 ThisScaledCost += ThisNonLocalAdjust;
1075 OtherOverflows |= OtherNonLocalAdjust &&
1076 OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;
1077 OtherScaledCost += OtherNonLocalAdjust;
1078 // If both overflows, we cannot compare without additional
1079 // precision, e.g., APInt. Just give up on that case.
1080 if (ThisOverflows && OtherOverflows)
1081 return false;
1082 // If one overflows but not the other, we can still compare.
1083 if (ThisOverflows || OtherOverflows)
1084 return ThisOverflows < OtherOverflows;
1085 // Otherwise, just compare the values.
1086 return ThisScaledCost < OtherScaledCost;
1087}
1088
1090 return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&
1091 LocalFreq == Cost.LocalFreq;
1092}
1093
1094#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1096 print(dbgs());
1097 dbgs() << '\n';
1098}
1099#endif
1100
1102 if (*this == ImpossibleCost()) {
1103 OS << "impossible";
1104 return;
1105 }
1106 if (isSaturated()) {
1107 OS << "saturated";
1108 return;
1109 }
1110 OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost;
1111}
MachineBasicBlock & MBB
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:693
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:240
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:480
IRTranslator LLVM IR MI
Interface for Targets to specify which operations they can successfully select and how the others sho...
#define F(x, y, z)
Definition: MD5.cpp:55
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
unsigned const TargetRegisterInfo * TRI
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
static cl::opt< RegBankSelect::Mode > RegBankSelectMode(cl::desc("Mode of the RegBankSelect pass"), cl::Hidden, cl::Optional, cl::values(clEnumValN(RegBankSelect::Mode::Fast, "regbankselect-fast", "Run the Fast mode (default mapping)"), clEnumValN(RegBankSelect::Mode::Greedy, "regbankselect-greedy", "Use the Greedy mode (best local mapping)")))
#define DEBUG_TYPE
This file describes the interface of the MachineFunctionPass responsible for assigning the generic vi...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallVector class.
Target-Independent Code Generator Pass Configuration Options pass.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
constexpr unsigned getScalarSizeInBits() const
Definition: LowLevelType.h:267
constexpr bool isValid() const
Definition: LowLevelType.h:145
constexpr uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
Definition: LowLevelType.h:159
constexpr bool isVector() const
Definition: LowLevelType.h:148
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelType.h:193
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool hasProperty(Property P) const
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineFunctionProperties & getProperties() const
Get the function properties.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
MachineFunction & getMF()
Getter for the function we currently build.
void setMBB(MachineBasicBlock &MBB)
Set the insertion point to the end of MBB.
MachineInstrBuilder buildInstrNoInsert(unsigned Opcode)
Build but don't insert <empty> = Opcode <empty>.
void setMF(MachineFunction &MF)
const MachineInstrBuilder & addUse(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register use operand.
const MachineInstrBuilder & addDef(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register definition operand.
Representation of each machine instruction.
Definition: MachineInstr.h:69
void insert(mop_iterator InsertBefore, ArrayRef< MachineOperand > Ops)
Inserts Ops BEFORE It. Can untie/retie tied operands.
bool isUnconditionalBranch(QueryType Type=AnyInBundle) const
Return true if this is a branch which always transfers control flow to some other block.
Definition: MachineInstr.h:970
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
void setRegBank(Register Reg, const RegisterBank &RegBank)
Set the register bank to RegBank for Reg.
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
Insertion point on an edge.
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
bool canMaterialize() const override
Check whether this insertion point can be materialized.
Abstract class used to represent an insertion point in a CFG.
virtual bool canMaterialize() const
Check whether this insertion point can be materialized.
virtual bool isSplit() const
Does this point involve splitting an edge or block? As soon as getPoint is called and thus,...
Insertion point before or after an instruction.
InstrInsertPoint(MachineInstr &Instr, bool Before=true)
Create an insertion point before (Before=true) or after Instr.
bool isSplit() const override
Does this point involve splitting an edge or block? As soon as getPoint is called and thus,...
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
Insertion point at the beginning or end of a basic block.
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
Helper class used to represent the cost for mapping an instruction.
void saturate()
Saturate the cost to the maximal representable value.
bool operator==(const MappingCost &Cost) const
Check if this is equal to Cost.
bool addLocalCost(uint64_t Cost)
Add Cost to the local cost.
void dump() const
Print this on dbgs() stream.
static MappingCost ImpossibleCost()
Return an instance of MappingCost that represents an impossible mapping.
bool addNonLocalCost(uint64_t Cost)
Add Cost to the non-local cost.
bool operator<(const MappingCost &Cost) const
Check if this is less than Cost.
void print(raw_ostream &OS) const
Print this on OS;.
Struct used to represent the placement of a repairing point for a given operand.
RepairingPlacement(MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P, RepairingKind Kind=RepairingKind::Insert)
Create a repairing placement for the OpIdx-th operand of MI.
RepairingKind
Define the kind of action this repairing needs.
@ Insert
Reparing code needs to happen before InsertPoints.
@ None
Nothing to repair, just drop this action.
@ Reassign
(Re)assign the register bank of the operand.
@ Impossible
Mark this repairing placement as impossible.
void switchTo(RepairingKind NewKind)
Change the type of this repairing placement to NewKind.
void addInsertPoint(MachineBasicBlock &MBB, bool Beginning)
This pass implements the reg bank selector pass used in the GlobalISel pipeline.
Definition: RegBankSelect.h:91
Mode
List of the modes supported by the RegBankSelect pass.
Definition: RegBankSelect.h:96
@ Fast
Assign the register banks as fast as possible (default).
Definition: RegBankSelect.h:98
bool checkFunctionIsLegal(MachineFunction &MF) const
Check that our input is fully legal: we require the function to have the Legalized property,...
MachineIRBuilder MIRBuilder
Helper class used for every code morphing.
MachineBlockFrequencyInfo * MBFI
Get the frequency of blocks.
Mode OptMode
Optimization mode of the pass.
const RegisterBankInfo::InstructionMapping & findBestMapping(MachineInstr &MI, RegisterBankInfo::InstructionMappings &PossibleMappings, SmallVectorImpl< RepairingPlacement > &RepairPts)
Find the best mapping for MI from PossibleMappings.
bool assignInstr(MachineInstr &MI)
Assign the register bank of each operand of MI.
bool assignRegisterBanks(MachineFunction &MF)
Walk through MF and assign a register bank to every virtual register that are still mapped to nothing...
void init(MachineFunction &MF)
Initialize the field members using MF.
void tryAvoidingSplit(RegBankSelect::RepairingPlacement &RepairPt, const MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping) const
When RepairPt involves splitting to repair MO for the given ValMapping, try to change the way we repa...
const TargetRegisterInfo * TRI
Information on the register classes for the current function.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
MachineBranchProbabilityInfo * MBPI
Get the frequency of the edges.
bool assignmentMatch(Register Reg, const RegisterBankInfo::ValueMapping &ValMapping, bool &OnlyAssign) const
Check if Reg is already assigned what is described by ValMapping.
uint64_t getRepairCost(const MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping) const
Return the cost of the instruction needed to map MO to ValMapping.
MappingCost computeMapping(MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping, SmallVectorImpl< RepairingPlacement > &RepairPts, const MappingCost *BestCost=nullptr)
Compute the cost of mapping MI with InstrMapping and compute the repairing placement for such mapping...
bool repairReg(MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping, RegBankSelect::RepairingPlacement &RepairPt, const iterator_range< SmallVectorImpl< Register >::const_iterator > &NewVRegs)
Insert repairing code for Reg as specified by ValMapping.
MachineRegisterInfo * MRI
MRI contains all the register class/bank information that this pass uses and updates.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetPassConfig * TPC
Current target configuration. Controls how the pass handles errors.
const RegisterBankInfo * RBI
Interface to the target lowering info related to register banks.
std::unique_ptr< MachineOptimizationRemarkEmitter > MORE
Current optimization remark emitter. Used to report failures.
bool applyMapping(MachineInstr &MI, const RegisterBankInfo::InstructionMapping &InstrMapping, SmallVectorImpl< RepairingPlacement > &RepairPts)
Apply Mapping to MI.
Helper class that represents how the value of an instruction may be mapped and what is the related co...
unsigned getNumOperands() const
Get the number of operands.
unsigned getCost() const
Get the cost.
bool verify(const MachineInstr &MI) const
Verifiy that this mapping makes sense for MI.
bool isValid() const
Check whether this object is valid.
Helper class used to get/create the virtual registers that will be used to replace the MachineOperand...
void createVRegs(unsigned OpIdx)
Create as many new virtual registers as needed for the mapping of the OpIdx-th operand.
iterator_range< SmallVectorImpl< Register >::const_iterator > getVRegs(unsigned OpIdx, bool ForDebug=false) const
Get all the virtual registers required to map the OpIdx-th operand of the instruction.
void applyMapping(MachineIRBuilder &Builder, const OperandsMapper &OpdMapper) const
Apply OpdMapper.getInstrMapping() to OpdMapper.getMI().
virtual const InstructionMapping & getInstrMapping(const MachineInstr &MI) const
Get the mapping of the different operands of MI on the register bank.
const RegisterBank & getRegBank(unsigned ID)
Get the register bank identified by ID.
TypeSize getSizeInBits(Register Reg, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI) const
Get the size in bits of Reg.
InstructionMappings getInstrPossibleMappings(const MachineInstr &MI) const
Get the possible mapping for MI.
virtual unsigned copyCost(const RegisterBank &A, const RegisterBank &B, TypeSize Size) const
Get the cost of a copy from B to A, or put differently, get the cost of A = COPY B.
virtual unsigned getBreakDownCost(const ValueMapping &ValMapping, const RegisterBank *CurBank=nullptr) const
Get the cost of using ValMapping to decompose a register.
This class implements the register bank concept.
Definition: RegisterBank.h:28
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:591
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Target-Independent Code Generator Pass Configuration Options.
bool isGlobalISelAbortEnabled() const
Check whether or not GlobalISel should abort on error.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const RegisterBankInfo * getRegBankInfo() const
If the information for the register banks is available, return it.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define UINT64_MAX
Definition: DataTypes.h:77
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:718
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1689
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
bool isPreISelGenericOptimizationHint(unsigned Opcode)
Definition: TargetOpcodes.h:42
cl::opt< bool > DisableGISelLegalityCheck
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:428
void reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC, MachineOptimizationRemarkEmitter &MORE, MachineOptimizationRemarkMissed &R)
Report an ISel error as a missed optimization remark to the LLVMContext's diagnostic stream.
Definition: Utils.cpp:273
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:156
Printable printRegClassOrBank(Register Reg, const MachineRegisterInfo &RegInfo, const TargetRegisterInfo *TRI)
Create Printable object to print register classes or register banks on a raw_ostream.
const MachineInstr * machineFunctionIsIllegal(const MachineFunction &MF)
Checks that MIR is fully legal, returns an illegal instruction if it's not, nullptr otherwise.
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:1071
bool isTargetSpecificOpcode(unsigned Opcode)
Check whether the given Opcode is a target-specific opcode.
Definition: TargetOpcodes.h:36
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:363
InstructionCost Cost
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
const RegisterBank * RegBank
Register bank where the partial value lives.
unsigned Length
Length of this mapping in bits.
Helper struct that represents how a value is mapped through different register banks.
unsigned NumBreakDowns
Number of partial mapping to break down this value.
const PartialMapping * BreakDown
How the value is broken down between the different register banks.