LLVM  14.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"
15 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/Config/llvm-config.h"
33 #include "llvm/IR/Attributes.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/InitializePasses.h"
36 #include "llvm/Pass.h"
39 #include "llvm/Support/Compiler.h"
40 #include "llvm/Support/Debug.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 
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 
64  "Assign register bank of generic virtual registers",
65  false, false);
70  "Assign register bank of generic virtual registers", false,
71  false)
72 
73 RegBankSelect::RegBankSelect(Mode RunningMode)
74  : MachineFunctionPass(ID), OptMode(RunningMode) {
75  if (RegBankSelectMode.getNumOccurrences() != 0) {
76  OptMode = RegBankSelectMode;
77  if (RegBankSelectMode != RunningMode)
78  LLVM_DEBUG(dbgs() << "RegBankSelect mode overrided by command line\n");
79  }
80 }
81 
82 void RegBankSelect::init(MachineFunction &MF) {
83  RBI = MF.getSubtarget().getRegBankInfo();
84  assert(RBI && "Cannot work without RegisterBankInfo");
85  MRI = &MF.getRegInfo();
86  TRI = MF.getSubtarget().getRegisterInfo();
87  TPC = &getAnalysis<TargetPassConfig>();
88  if (OptMode != Mode::Fast) {
89  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
90  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
91  } else {
92  MBFI = nullptr;
93  MBPI = nullptr;
94  }
95  MIRBuilder.setMF(MF);
96  MORE = std::make_unique<MachineOptimizationRemarkEmitter>(MF, MBFI);
97 }
98 
100  if (OptMode != Mode::Fast) {
101  // We could preserve the information from these two analysis but
102  // the APIs do not allow to do so yet.
105  }
109 }
110 
111 bool RegBankSelect::assignmentMatch(
112  Register Reg, const RegisterBankInfo::ValueMapping &ValMapping,
113  bool &OnlyAssign) const {
114  // By default we assume we will have to repair something.
115  OnlyAssign = false;
116  // Each part of a break down needs to end up in a different register.
117  // In other word, Reg assignment does not match.
118  if (ValMapping.NumBreakDowns != 1)
119  return false;
120 
121  const RegisterBank *CurRegBank = RBI->getRegBank(Reg, *MRI, *TRI);
122  const RegisterBank *DesiredRegBank = ValMapping.BreakDown[0].RegBank;
123  // Reg is free of assignment, a simple assignment will make the
124  // register bank to match.
125  OnlyAssign = CurRegBank == nullptr;
126  LLVM_DEBUG(dbgs() << "Does assignment already match: ";
127  if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";
128  dbgs() << " against ";
129  assert(DesiredRegBank && "The mapping must be valid");
130  dbgs() << *DesiredRegBank << '\n';);
131  return CurRegBank == DesiredRegBank;
132 }
133 
134 bool RegBankSelect::repairReg(
135  MachineOperand &MO, const RegisterBankInfo::ValueMapping &ValMapping,
138 
139  assert(ValMapping.NumBreakDowns == (unsigned)size(NewVRegs) &&
140  "need new vreg for each breakdown");
141 
142  // An empty range of new register means no repairing.
143  assert(!NewVRegs.empty() && "We should not have to repair");
144 
145  MachineInstr *MI;
146  if (ValMapping.NumBreakDowns == 1) {
147  // Assume we are repairing a use and thus, the original reg will be
148  // the source of the repairing.
149  Register Src = MO.getReg();
150  Register Dst = *NewVRegs.begin();
151 
152  // If we repair a definition, swap the source and destination for
153  // the repairing.
154  if (MO.isDef())
155  std::swap(Src, Dst);
156 
157  assert((RepairPt.getNumInsertPoints() == 1 ||
159  "We are about to create several defs for Dst");
160 
161  // Build the instruction used to repair, then clone it at the right
162  // places. Avoiding buildCopy bypasses the check that Src and Dst have the
163  // same types because the type is a placeholder when this function is called.
164  MI = MIRBuilder.buildInstrNoInsert(TargetOpcode::COPY)
165  .addDef(Dst)
166  .addUse(Src);
167  LLVM_DEBUG(dbgs() << "Copy: " << printReg(Src) << " to: " << printReg(Dst)
168  << '\n');
169  } else {
170  // TODO: Support with G_IMPLICIT_DEF + G_INSERT sequence or G_EXTRACT
171  // sequence.
172  assert(ValMapping.partsAllUniform() && "irregular breakdowns not supported");
173 
174  LLT RegTy = MRI->getType(MO.getReg());
175  if (MO.isDef()) {
176  unsigned MergeOp;
177  if (RegTy.isVector()) {
178  if (ValMapping.NumBreakDowns == RegTy.getNumElements())
179  MergeOp = TargetOpcode::G_BUILD_VECTOR;
180  else {
181  assert(
182  (ValMapping.BreakDown[0].Length * ValMapping.NumBreakDowns ==
183  RegTy.getSizeInBits()) &&
184  (ValMapping.BreakDown[0].Length % RegTy.getScalarSizeInBits() ==
185  0) &&
186  "don't understand this value breakdown");
187 
188  MergeOp = TargetOpcode::G_CONCAT_VECTORS;
189  }
190  } else
191  MergeOp = TargetOpcode::G_MERGE_VALUES;
192 
193  auto MergeBuilder =
194  MIRBuilder.buildInstrNoInsert(MergeOp)
195  .addDef(MO.getReg());
196 
197  for (Register SrcReg : NewVRegs)
198  MergeBuilder.addUse(SrcReg);
199 
200  MI = MergeBuilder;
201  } else {
202  MachineInstrBuilder UnMergeBuilder =
203  MIRBuilder.buildInstrNoInsert(TargetOpcode::G_UNMERGE_VALUES);
204  for (Register DefReg : NewVRegs)
205  UnMergeBuilder.addDef(DefReg);
206 
207  UnMergeBuilder.addUse(MO.getReg());
208  MI = UnMergeBuilder;
209  }
210  }
211 
212  if (RepairPt.getNumInsertPoints() != 1)
213  report_fatal_error("need testcase to support multiple insertion points");
214 
215  // TODO:
216  // Check if MI is legal. if not, we need to legalize all the
217  // instructions we are going to insert.
218  std::unique_ptr<MachineInstr *[]> NewInstrs(
219  new MachineInstr *[RepairPt.getNumInsertPoints()]);
220  bool IsFirst = true;
221  unsigned Idx = 0;
222  for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
223  MachineInstr *CurMI;
224  if (IsFirst)
225  CurMI = MI;
226  else
227  CurMI = MIRBuilder.getMF().CloneMachineInstr(MI);
228  InsertPt->insert(*CurMI);
229  NewInstrs[Idx++] = CurMI;
230  IsFirst = false;
231  }
232  // TODO:
233  // Legalize NewInstrs if need be.
234  return true;
235 }
236 
237 uint64_t RegBankSelect::getRepairCost(
238  const MachineOperand &MO,
239  const RegisterBankInfo::ValueMapping &ValMapping) const {
240  assert(MO.isReg() && "We should only repair register operand");
241  assert(ValMapping.NumBreakDowns && "Nothing to map??");
242 
243  bool IsSameNumOfValues = ValMapping.NumBreakDowns == 1;
244  const RegisterBank *CurRegBank = RBI->getRegBank(MO.getReg(), *MRI, *TRI);
245  // If MO does not have a register bank, we should have just been
246  // able to set one unless we have to break the value down.
247  assert(CurRegBank || MO.isDef());
248 
249  // Def: Val <- NewDefs
250  // Same number of values: copy
251  // Different number: Val = build_sequence Defs1, Defs2, ...
252  // Use: NewSources <- Val.
253  // Same number of values: copy.
254  // Different number: Src1, Src2, ... =
255  // extract_value Val, Src1Begin, Src1Len, Src2Begin, Src2Len, ...
256  // We should remember that this value is available somewhere else to
257  // coalesce the value.
258 
259  if (ValMapping.NumBreakDowns != 1)
260  return RBI->getBreakDownCost(ValMapping, CurRegBank);
261 
262  if (IsSameNumOfValues) {
263  const RegisterBank *DesiredRegBank = ValMapping.BreakDown[0].RegBank;
264  // If we repair a definition, swap the source and destination for
265  // the repairing.
266  if (MO.isDef())
267  std::swap(CurRegBank, DesiredRegBank);
268  // TODO: It may be possible to actually avoid the copy.
269  // If we repair something where the source is defined by a copy
270  // and the source of that copy is on the right bank, we can reuse
271  // it for free.
272  // E.g.,
273  // RegToRepair<BankA> = copy AlternativeSrc<BankB>
274  // = op RegToRepair<BankA>
275  // We can simply propagate AlternativeSrc instead of copying RegToRepair
276  // into a new virtual register.
277  // We would also need to propagate this information in the
278  // repairing placement.
279  unsigned Cost = RBI->copyCost(*DesiredRegBank, *CurRegBank,
280  RBI->getSizeInBits(MO.getReg(), *MRI, *TRI));
281  // TODO: use a dedicated constant for ImpossibleCost.
283  return Cost;
284  // Return the legalization cost of that repairing.
285  }
287 }
288 
289 const RegisterBankInfo::InstructionMapping &RegBankSelect::findBestMapping(
292  assert(!PossibleMappings.empty() &&
293  "Do not know how to map this instruction");
294 
295  const RegisterBankInfo::InstructionMapping *BestMapping = nullptr;
296  MappingCost Cost = MappingCost::ImpossibleCost();
297  SmallVector<RepairingPlacement, 4> LocalRepairPts;
298  for (const RegisterBankInfo::InstructionMapping *CurMapping :
299  PossibleMappings) {
300  MappingCost CurCost =
301  computeMapping(MI, *CurMapping, LocalRepairPts, &Cost);
302  if (CurCost < Cost) {
303  LLVM_DEBUG(dbgs() << "New best: " << CurCost << '\n');
304  Cost = CurCost;
305  BestMapping = CurMapping;
306  RepairPts.clear();
307  for (RepairingPlacement &RepairPt : LocalRepairPts)
308  RepairPts.emplace_back(std::move(RepairPt));
309  }
310  }
311  if (!BestMapping && !TPC->isGlobalISelAbortEnabled()) {
312  // If none of the mapping worked that means they are all impossible.
313  // Thus, pick the first one and set an impossible repairing point.
314  // It will trigger the failed isel mode.
315  BestMapping = *PossibleMappings.begin();
316  RepairPts.emplace_back(
317  RepairingPlacement(MI, 0, *TRI, *this, RepairingPlacement::Impossible));
318  } else
319  assert(BestMapping && "No suitable mapping for instruction");
320  return *BestMapping;
321 }
322 
323 void RegBankSelect::tryAvoidingSplit(
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();
403  // We are going to split every outgoing edges.
404  // Check that this is possible.
405  // FIXME: The machine representation is currently broken
406  // since it also several terminators in one basic block.
407  // Because of that we would technically need a way to get
408  // the targets of just one terminator to know which edges
409  // we have to split.
410  // Assert that we do not hit the ill-formed representation.
411 
412  // If there are other terminators before that one, some of
413  // the outgoing edges may not be dominated by this definition.
414  assert(&MI == &(*MI.getParent()->getFirstTerminator()) &&
415  "Do not know which outgoing edges are relevant");
416  const MachineInstr *Next = MI.getNextNode();
417  assert((!Next || Next->isUnconditionalBranch()) &&
418  "Do not know where each terminator ends up");
419  if (Next)
420  // If the next terminator uses Reg, this means we have
421  // to split right after MI and thus we need a way to ask
422  // which outgoing edges are affected.
423  assert(!Next->readsRegister(Reg) && "Need to split between terminators");
424  // We will split all the edges and repair there.
425  } else {
426  // This is a virtual register defined by a terminator.
427  if (ValMapping.NumBreakDowns == 1) {
428  // There is nothing to repair, but we may actually lie on
429  // the repairing cost because of the PHIs already proceeded
430  // as already stated.
431  // Though the code will be correct.
432  assert(false && "Repairing cost may not be accurate");
433  } else {
434  // We need to do non-local repairing. Basically, patch all
435  // the uses (i.e., phis) that we already proceeded.
436  // For now, just say this mapping is not possible.
437  RepairPt.switchTo(RepairingPlacement::RepairingKind::Impossible);
438  }
439  }
440 }
441 
442 RegBankSelect::MappingCost RegBankSelect::computeMapping(
445  const RegBankSelect::MappingCost *BestCost) {
446  assert((MBFI || !BestCost) && "Costs comparison require MBFI");
447 
448  if (!InstrMapping.isValid())
449  return MappingCost::ImpossibleCost();
450 
451  // If mapped with InstrMapping, MI will have the recorded cost.
452  MappingCost Cost(MBFI ? MBFI->getBlockFreq(MI.getParent()) : 1);
453  bool Saturated = Cost.addLocalCost(InstrMapping.getCost());
454  assert(!Saturated && "Possible mapping saturated the cost");
455  LLVM_DEBUG(dbgs() << "Evaluating mapping cost for: " << MI);
456  LLVM_DEBUG(dbgs() << "With: " << InstrMapping << '\n');
457  RepairPts.clear();
458  if (BestCost && Cost > *BestCost) {
459  LLVM_DEBUG(dbgs() << "Mapping is too expensive from the start\n");
460  return Cost;
461  }
462 
463  // Moreover, to realize this mapping, the register bank of each operand must
464  // match this mapping. In other words, we may need to locally reassign the
465  // register banks. Account for that repairing cost as well.
466  // In this context, local means in the surrounding of MI.
467  for (unsigned OpIdx = 0, EndOpIdx = InstrMapping.getNumOperands();
468  OpIdx != EndOpIdx; ++OpIdx) {
469  const MachineOperand &MO = MI.getOperand(OpIdx);
470  if (!MO.isReg())
471  continue;
472  Register Reg = MO.getReg();
473  if (!Reg)
474  continue;
475  LLVM_DEBUG(dbgs() << "Opd" << OpIdx << '\n');
476  const RegisterBankInfo::ValueMapping &ValMapping =
477  InstrMapping.getOperandMapping(OpIdx);
478  // If Reg is already properly mapped, this is free.
479  bool Assign;
480  if (assignmentMatch(Reg, ValMapping, Assign)) {
481  LLVM_DEBUG(dbgs() << "=> is free (match).\n");
482  continue;
483  }
484  if (Assign) {
485  LLVM_DEBUG(dbgs() << "=> is free (simple assignment).\n");
486  RepairPts.emplace_back(RepairingPlacement(MI, OpIdx, *TRI, *this,
488  continue;
489  }
490 
491  // Find the insertion point for the repairing code.
492  RepairPts.emplace_back(
493  RepairingPlacement(MI, OpIdx, *TRI, *this, RepairingPlacement::Insert));
494  RepairingPlacement &RepairPt = RepairPts.back();
495 
496  // If we need to split a basic block to materialize this insertion point,
497  // we may give a higher cost to this mapping.
498  // Nevertheless, we may get away with the split, so try that first.
499  if (RepairPt.hasSplit())
500  tryAvoidingSplit(RepairPt, MO, ValMapping);
501 
502  // Check that the materialization of the repairing is possible.
503  if (!RepairPt.canMaterialize()) {
504  LLVM_DEBUG(dbgs() << "Mapping involves impossible repairing\n");
505  return MappingCost::ImpossibleCost();
506  }
507 
508  // Account for the split cost and repair cost.
509  // Unless the cost is already saturated or we do not care about the cost.
510  if (!BestCost || Saturated)
511  continue;
512 
513  // To get accurate information we need MBFI and MBPI.
514  // Thus, if we end up here this information should be here.
515  assert(MBFI && MBPI && "Cost computation requires MBFI and MBPI");
516 
517  // FIXME: We will have to rework the repairing cost model.
518  // The repairing cost depends on the register bank that MO has.
519  // However, when we break down the value into different values,
520  // MO may not have a register bank while still needing repairing.
521  // For the fast mode, we don't compute the cost so that is fine,
522  // but still for the repairing code, we will have to make a choice.
523  // For the greedy mode, we should choose greedily what is the best
524  // choice based on the next use of MO.
525 
526  // Sums up the repairing cost of MO at each insertion point.
527  uint64_t RepairCost = getRepairCost(MO, ValMapping);
528 
529  // This is an impossible to repair cost.
530  if (RepairCost == std::numeric_limits<unsigned>::max())
531  return MappingCost::ImpossibleCost();
532 
533  // Bias used for splitting: 5%.
534  const uint64_t PercentageForBias = 5;
535  uint64_t Bias = (RepairCost * PercentageForBias + 99) / 100;
536  // We should not need more than a couple of instructions to repair
537  // an assignment. In other words, the computation should not
538  // overflow because the repairing cost is free of basic block
539  // frequency.
540  assert(((RepairCost < RepairCost * PercentageForBias) &&
541  (RepairCost * PercentageForBias <
542  RepairCost * PercentageForBias + 99)) &&
543  "Repairing involves more than a billion of instructions?!");
544  for (const std::unique_ptr<InsertPoint> &InsertPt : RepairPt) {
545  assert(InsertPt->canMaterialize() && "We should not have made it here");
546  // We will applied some basic block frequency and those uses uint64_t.
547  if (!InsertPt->isSplit())
548  Saturated = Cost.addLocalCost(RepairCost);
549  else {
550  uint64_t CostForInsertPt = RepairCost;
551  // Again we shouldn't overflow here givent that
552  // CostForInsertPt is frequency free at this point.
553  assert(CostForInsertPt + Bias > CostForInsertPt &&
554  "Repairing + split bias overflows");
555  CostForInsertPt += Bias;
556  uint64_t PtCost = InsertPt->frequency(*this) * CostForInsertPt;
557  // Check if we just overflowed.
558  if ((Saturated = PtCost < CostForInsertPt))
559  Cost.saturate();
560  else
561  Saturated = Cost.addNonLocalCost(PtCost);
562  }
563 
564  // Stop looking into what it takes to repair, this is already
565  // too expensive.
566  if (BestCost && Cost > *BestCost) {
567  LLVM_DEBUG(dbgs() << "Mapping is too expensive, stop processing\n");
568  return Cost;
569  }
570 
571  // No need to accumulate more cost information.
572  // We need to still gather the repairing information though.
573  if (Saturated)
574  break;
575  }
576  }
577  LLVM_DEBUG(dbgs() << "Total cost is: " << Cost << "\n");
578  return Cost;
579 }
580 
581 bool RegBankSelect::applyMapping(
584  // OpdMapper will hold all the information needed for the rewriting.
585  RegisterBankInfo::OperandsMapper OpdMapper(MI, InstrMapping, *MRI);
586 
587  // First, place the repairing code.
588  for (RepairingPlacement &RepairPt : RepairPts) {
589  if (!RepairPt.canMaterialize() ||
590  RepairPt.getKind() == RepairingPlacement::Impossible)
591  return false;
592  assert(RepairPt.getKind() != RepairingPlacement::None &&
593  "This should not make its way in the list");
594  unsigned OpIdx = RepairPt.getOpIdx();
595  MachineOperand &MO = MI.getOperand(OpIdx);
596  const RegisterBankInfo::ValueMapping &ValMapping =
597  InstrMapping.getOperandMapping(OpIdx);
598  Register Reg = MO.getReg();
599 
600  switch (RepairPt.getKind()) {
602  assert(ValMapping.NumBreakDowns == 1 &&
603  "Reassignment should only be for simple mapping");
604  MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);
605  break;
607  OpdMapper.createVRegs(OpIdx);
608  if (!repairReg(MO, ValMapping, RepairPt, OpdMapper.getVRegs(OpIdx)))
609  return false;
610  break;
611  default:
612  llvm_unreachable("Other kind should not happen");
613  }
614  }
615 
616  // Second, rewrite the instruction.
617  LLVM_DEBUG(dbgs() << "Actual mapping of the operands: " << OpdMapper << '\n');
618  RBI->applyMapping(OpdMapper);
619 
620  return true;
621 }
622 
623 bool RegBankSelect::assignInstr(MachineInstr &MI) {
624  LLVM_DEBUG(dbgs() << "Assign: " << MI);
625 
626  unsigned Opc = MI.getOpcode();
628  assert((Opc == TargetOpcode::G_ASSERT_ZEXT ||
629  Opc == TargetOpcode::G_ASSERT_SEXT) &&
630  "Unexpected hint opcode!");
631  // The only correct mapping for these is to always use the source register
632  // bank.
633  const RegisterBank *RB = MRI->getRegBankOrNull(MI.getOperand(1).getReg());
634  // We can assume every instruction above this one has a selected register
635  // bank.
636  assert(RB && "Expected source register to have a register bank?");
637  LLVM_DEBUG(dbgs() << "... Hint always uses source's register bank.\n");
638  MRI->setRegBank(MI.getOperand(0).getReg(), *RB);
639  return true;
640  }
641 
642  // Remember the repairing placement for all the operands.
644 
645  const RegisterBankInfo::InstructionMapping *BestMapping;
646  if (OptMode == RegBankSelect::Mode::Fast) {
647  BestMapping = &RBI->getInstrMapping(MI);
648  MappingCost DefaultCost = computeMapping(MI, *BestMapping, RepairPts);
649  (void)DefaultCost;
650  if (DefaultCost == MappingCost::ImpossibleCost())
651  return false;
652  } else {
653  RegisterBankInfo::InstructionMappings PossibleMappings =
655  if (PossibleMappings.empty())
656  return false;
657  BestMapping = &findBestMapping(MI, PossibleMappings, RepairPts);
658  }
659  // Make sure the mapping is valid for MI.
660  assert(BestMapping->verify(MI) && "Invalid instruction mapping");
661 
662  LLVM_DEBUG(dbgs() << "Best Mapping: " << *BestMapping << '\n');
663 
664  // After this call, MI may not be valid anymore.
665  // Do not use it.
666  return applyMapping(MI, *BestMapping, RepairPts);
667 }
668 
670  // If the ISel pipeline failed, do not bother running that pass.
671  if (MF.getProperties().hasProperty(
673  return false;
674 
675  LLVM_DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
676  const Function &F = MF.getFunction();
677  Mode SaveOptMode = OptMode;
678  if (F.hasOptNone())
679  OptMode = Mode::Fast;
680  init(MF);
681 
682 #ifndef NDEBUG
683  // Check that our input is fully legal: we require the function to have the
684  // Legalized property, so it should be.
685  // FIXME: This should be in the MachineVerifier.
687  if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
688  reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
689  "instruction is not legal", *MI);
690  return false;
691  }
692 #endif
693 
694  // Walk the function and assign register banks to all operands.
695  // Use a RPOT to make sure all registers are assigned before we choose
696  // the best mapping of the current instruction.
698  for (MachineBasicBlock *MBB : RPOT) {
699  // Set a sensible insertion point so that subsequent calls to
700  // MIRBuilder.
701  MIRBuilder.setMBB(*MBB);
702  for (MachineBasicBlock::iterator MII = MBB->begin(), End = MBB->end();
703  MII != End;) {
704  // MI might be invalidated by the assignment, so move the
705  // iterator before hand.
706  MachineInstr &MI = *MII++;
707 
708  // Ignore target-specific post-isel instructions: they should use proper
709  // regclasses.
710  if (isTargetSpecificOpcode(MI.getOpcode()) && !MI.isPreISelOpcode())
711  continue;
712 
713  // Ignore inline asm instructions: they should use physical
714  // registers/regclasses
715  if (MI.isInlineAsm())
716  continue;
717 
718  // Ignore debug info.
719  if (MI.isDebugInstr())
720  continue;
721 
722  // Ignore IMPLICIT_DEF which must have a regclass.
723  if (MI.isImplicitDef())
724  continue;
725 
726  if (!assignInstr(MI)) {
727  reportGISelFailure(MF, *TPC, *MORE, "gisel-regbankselect",
728  "unable to map instruction", MI);
729  return false;
730  }
731 
732  // It's possible the mapping changed control flow, and moved the following
733  // instruction to a new block, so figure out the new parent.
734  if (MII != End) {
735  MachineBasicBlock *NextInstBB = MII->getParent();
736  if (NextInstBB != MBB) {
737  LLVM_DEBUG(dbgs() << "Instruction mapping changed control flow\n");
738  MBB = NextInstBB;
739  MIRBuilder.setMBB(*MBB);
740  End = MBB->end();
741  }
742  }
743  }
744  }
745 
746  OptMode = SaveOptMode;
747  return false;
748 }
749 
750 //------------------------------------------------------------------------------
751 // Helper Classes Implementation
752 //------------------------------------------------------------------------------
754  MachineInstr &MI, unsigned OpIdx, const TargetRegisterInfo &TRI, Pass &P,
756  // Default is, we are going to insert code to repair OpIdx.
757  : Kind(Kind), OpIdx(OpIdx),
758  CanMaterialize(Kind != RepairingKind::Impossible), P(P) {
759  const MachineOperand &MO = MI.getOperand(OpIdx);
760  assert(MO.isReg() && "Trying to repair a non-reg operand");
761 
762  if (Kind != RepairingKind::Insert)
763  return;
764 
765  // Repairings for definitions happen after MI, uses happen before.
766  bool Before = !MO.isDef();
767 
768  // Check if we are done with MI.
769  if (!MI.isPHI() && !MI.isTerminator()) {
770  addInsertPoint(MI, Before);
771  // We are done with the initialization.
772  return;
773  }
774 
775  // Now, look for the special cases.
776  if (MI.isPHI()) {
777  // - PHI must be the first instructions:
778  // * Before, we have to split the related incoming edge.
779  // * After, move the insertion point past the last phi.
780  if (!Before) {
781  MachineBasicBlock::iterator It = MI.getParent()->getFirstNonPHI();
782  if (It != MI.getParent()->end())
783  addInsertPoint(*It, /*Before*/ true);
784  else
785  addInsertPoint(*(--It), /*Before*/ false);
786  return;
787  }
788  // We repair a use of a phi, we may need to split the related edge.
789  MachineBasicBlock &Pred = *MI.getOperand(OpIdx + 1).getMBB();
790  // Check if we can move the insertion point prior to the
791  // terminators of the predecessor.
792  Register Reg = MO.getReg();
794  for (auto Begin = Pred.begin(); It != Begin && It->isTerminator(); --It)
795  if (It->modifiesRegister(Reg, &TRI)) {
796  // We cannot hoist the repairing code in the predecessor.
797  // Split the edge.
798  addInsertPoint(Pred, *MI.getParent());
799  return;
800  }
801  // At this point, we can insert in Pred.
802 
803  // - If It is invalid, Pred is empty and we can insert in Pred
804  // wherever we want.
805  // - If It is valid, It is the first non-terminator, insert after It.
806  if (It == Pred.end())
807  addInsertPoint(Pred, /*Beginning*/ false);
808  else
809  addInsertPoint(*It, /*Before*/ false);
810  } else {
811  // - Terminators must be the last instructions:
812  // * Before, move the insert point before the first terminator.
813  // * After, we have to split the outcoming edges.
814  if (Before) {
815  // Check whether Reg is defined by any terminator.
817  auto REnd = MI.getParent()->rend();
818 
819  for (; It != REnd && It->isTerminator(); ++It) {
820  assert(!It->modifiesRegister(MO.getReg(), &TRI) &&
821  "copy insertion in middle of terminators not handled");
822  }
823 
824  if (It == REnd) {
825  addInsertPoint(*MI.getParent()->begin(), true);
826  return;
827  }
828 
829  // We are sure to be right before the first terminator.
830  addInsertPoint(*It, /*Before*/ false);
831  return;
832  }
833  // Make sure Reg is not redefined by other terminators, otherwise
834  // we do not know how to split.
835  for (MachineBasicBlock::iterator It = MI, End = MI.getParent()->end();
836  ++It != End;)
837  // The machine verifier should reject this kind of code.
838  assert(It->modifiesRegister(MO.getReg(), &TRI) &&
839  "Do not know where to split");
840  // Split each outcoming edges.
841  MachineBasicBlock &Src = *MI.getParent();
842  for (auto &Succ : Src.successors())
843  addInsertPoint(Src, Succ);
844  }
845 }
846 
848  bool Before) {
849  addInsertPoint(*new InstrInsertPoint(MI, Before));
850 }
851 
853  bool Beginning) {
854  addInsertPoint(*new MBBInsertPoint(MBB, Beginning));
855 }
856 
858  MachineBasicBlock &Dst) {
859  addInsertPoint(*new EdgeInsertPoint(Src, Dst, P));
860 }
861 
864  CanMaterialize &= Point.canMaterialize();
865  HasSplit |= Point.isSplit();
866  InsertPoints.emplace_back(&Point);
867 }
868 
870  bool Before)
871  : InsertPoint(), Instr(Instr), Before(Before) {
872  // Since we do not support splitting, we do not need to update
873  // liveness and such, so do not do anything with P.
874  assert((!Before || !Instr.isPHI()) &&
875  "Splitting before phis requires more points");
876  assert((!Before || !Instr.getNextNode() || !Instr.getNextNode()->isPHI()) &&
877  "Splitting between phis does not make sense");
878 }
879 
880 void RegBankSelect::InstrInsertPoint::materialize() {
881  if (isSplit()) {
882  // Slice and return the beginning of the new block.
883  // If we need to split between the terminators, we theoritically
884  // need to know where the first and second set of terminators end
885  // to update the successors properly.
886  // Now, in pratice, we should have a maximum of 2 branch
887  // instructions; one conditional and one unconditional. Therefore
888  // we know how to update the successor by looking at the target of
889  // the unconditional branch.
890  // If we end up splitting at some point, then, we should update
891  // the liveness information and such. I.e., we would need to
892  // access P here.
893  // The machine verifier should actually make sure such cases
894  // cannot happen.
895  llvm_unreachable("Not yet implemented");
896  }
897  // Otherwise the insertion point is just the current or next
898  // instruction depending on Before. I.e., there is nothing to do
899  // here.
900 }
901 
903  // If the insertion point is after a terminator, we need to split.
904  if (!Before)
905  return Instr.isTerminator();
906  // If we insert before an instruction that is after a terminator,
907  // we are still after a terminator.
908  return Instr.getPrevNode() && Instr.getPrevNode()->isTerminator();
909 }
910 
912  // Even if we need to split, because we insert between terminators,
913  // this split has actually the same frequency as the instruction.
914  const MachineBlockFrequencyInfo *MBFI =
915  P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
916  if (!MBFI)
917  return 1;
918  return MBFI->getBlockFreq(Instr.getParent()).getFrequency();
919 }
920 
922  const MachineBlockFrequencyInfo *MBFI =
923  P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
924  if (!MBFI)
925  return 1;
926  return MBFI->getBlockFreq(&MBB).getFrequency();
927 }
928 
929 void RegBankSelect::EdgeInsertPoint::materialize() {
930  // If we end up repairing twice at the same place before materializing the
931  // insertion point, we may think we have to split an edge twice.
932  // We should have a factory for the insert point such that identical points
933  // are the same instance.
934  assert(Src.isSuccessor(DstOrSplit) && DstOrSplit->isPredecessor(&Src) &&
935  "This point has already been split");
936  MachineBasicBlock *NewBB = Src.SplitCriticalEdge(DstOrSplit, P);
937  assert(NewBB && "Invalid call to materialize");
938  // We reuse the destination block to hold the information of the new block.
939  DstOrSplit = NewBB;
940 }
941 
943  const MachineBlockFrequencyInfo *MBFI =
944  P.getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
945  if (!MBFI)
946  return 1;
947  if (WasMaterialized)
948  return MBFI->getBlockFreq(DstOrSplit).getFrequency();
949 
950  const MachineBranchProbabilityInfo *MBPI =
951  P.getAnalysisIfAvailable<MachineBranchProbabilityInfo>();
952  if (!MBPI)
953  return 1;
954  // The basic block will be on the edge.
955  return (MBFI->getBlockFreq(&Src) * MBPI->getEdgeProbability(&Src, DstOrSplit))
956  .getFrequency();
957 }
958 
960  // If this is not a critical edge, we should not have used this insert
961  // point. Indeed, either the successor or the predecessor should
962  // have do.
963  assert(Src.succ_size() > 1 && DstOrSplit->pred_size() > 1 &&
964  "Edge is not critical");
965  return Src.canSplitCriticalEdge(DstOrSplit);
966 }
967 
968 RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq)
969  : LocalFreq(LocalFreq.getFrequency()) {}
970 
971 bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) {
972  // Check if this overflows.
973  if (LocalCost + Cost < LocalCost) {
974  saturate();
975  return true;
976  }
977  LocalCost += Cost;
978  return isSaturated();
979 }
980 
981 bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) {
982  // Check if this overflows.
983  if (NonLocalCost + Cost < NonLocalCost) {
984  saturate();
985  return true;
986  }
987  NonLocalCost += Cost;
988  return isSaturated();
989 }
990 
991 bool RegBankSelect::MappingCost::isSaturated() const {
992  return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&
993  LocalFreq == UINT64_MAX;
994 }
995 
996 void RegBankSelect::MappingCost::saturate() {
997  *this = ImpossibleCost();
998  --LocalCost;
999 }
1000 
1001 RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() {
1002  return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX);
1003 }
1004 
1005 bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const {
1006  // Sort out the easy cases.
1007  if (*this == Cost)
1008  return false;
1009  // If one is impossible to realize the other is cheaper unless it is
1010  // impossible as well.
1011  if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))
1012  return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());
1013  // If one is saturated the other is cheaper, unless it is saturated
1014  // as well.
1015  if (isSaturated() || Cost.isSaturated())
1016  return isSaturated() < Cost.isSaturated();
1017  // At this point we know both costs hold sensible values.
1018 
1019  // If both values have a different base frequency, there is no much
1020  // we can do but to scale everything.
1021  // However, if they have the same base frequency we can avoid making
1022  // complicated computation.
1023  uint64_t ThisLocalAdjust;
1024  uint64_t OtherLocalAdjust;
1025  if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {
1026 
1027  // At this point, we know the local costs are comparable.
1028  // Do the case that do not involve potential overflow first.
1029  if (NonLocalCost == Cost.NonLocalCost)
1030  // Since the non-local costs do not discriminate on the result,
1031  // just compare the local costs.
1032  return LocalCost < Cost.LocalCost;
1033 
1034  // The base costs are comparable so we may only keep the relative
1035  // value to increase our chances of avoiding overflows.
1036  ThisLocalAdjust = 0;
1037  OtherLocalAdjust = 0;
1038  if (LocalCost < Cost.LocalCost)
1039  OtherLocalAdjust = Cost.LocalCost - LocalCost;
1040  else
1041  ThisLocalAdjust = LocalCost - Cost.LocalCost;
1042  } else {
1043  ThisLocalAdjust = LocalCost;
1044  OtherLocalAdjust = Cost.LocalCost;
1045  }
1046 
1047  // The non-local costs are comparable, just keep the relative value.
1048  uint64_t ThisNonLocalAdjust = 0;
1049  uint64_t OtherNonLocalAdjust = 0;
1050  if (NonLocalCost < Cost.NonLocalCost)
1051  OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;
1052  else
1053  ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;
1054  // Scale everything to make them comparable.
1055  uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;
1056  // Check for overflow on that operation.
1057  bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||
1058  ThisScaledCost < LocalFreq);
1059  uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;
1060  // Check for overflow on the last operation.
1061  bool OtherOverflows =
1062  OtherLocalAdjust &&
1063  (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);
1064  // Add the non-local costs.
1065  ThisOverflows |= ThisNonLocalAdjust &&
1066  ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;
1067  ThisScaledCost += ThisNonLocalAdjust;
1068  OtherOverflows |= OtherNonLocalAdjust &&
1069  OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;
1070  OtherScaledCost += OtherNonLocalAdjust;
1071  // If both overflows, we cannot compare without additional
1072  // precision, e.g., APInt. Just give up on that case.
1073  if (ThisOverflows && OtherOverflows)
1074  return false;
1075  // If one overflows but not the other, we can still compare.
1076  if (ThisOverflows || OtherOverflows)
1077  return ThisOverflows < OtherOverflows;
1078  // Otherwise, just compare the values.
1079  return ThisScaledCost < OtherScaledCost;
1080 }
1081 
1082 bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const {
1083  return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&
1084  LocalFreq == Cost.LocalFreq;
1085 }
1086 
1087 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1089  print(dbgs());
1090  dbgs() << '\n';
1091 }
1092 #endif
1093 
1095  if (*this == ImpossibleCost()) {
1096  OS << "impossible";
1097  return;
1098  }
1099  if (isSaturated()) {
1100  OS << "saturated";
1101  return;
1102  }
1103  OS << LocalFreq << " * " << LocalCost << " + " << NonLocalCost;
1104 }
llvm::RegBankSelect::RepairingPlacement::RepairingPlacement
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.
Definition: RegBankSelect.cpp:753
llvm::MachineIRBuilder::setMF
void setMF(MachineFunction &MF)
Definition: MachineIRBuilder.cpp:26
llvm::RegBankSelect::RepairingPlacement::addInsertPoint
void addInsertPoint(MachineBasicBlock &MBB, bool Beginning)
Definition: RegBankSelect.cpp:852
llvm::RegBankSelect::InsertPoint
Abstract class used to represent an insertion point in a CFG.
Definition: RegBankSelect.h:111
llvm::MachineFunctionProperties::hasProperty
bool hasProperty(Property P) const
Definition: MachineFunction.h:169
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:506
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::LLT::getScalarSizeInBits
unsigned getScalarSizeInBits() const
Definition: LowLevelTypeImpl.h:213
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
Insert
Vector Rotate Left Mask Mask Insert
Definition: README_P9.txt:112
llvm::isPreISelGenericOptimizationHint
bool isPreISelGenericOptimizationHint(unsigned Opcode)
Definition: TargetOpcodes.h:42
llvm::Function
Definition: Function.h:62
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::RegBankSelect::InstrInsertPoint::InstrInsertPoint
InstrInsertPoint(MachineInstr &Instr, bool Before=true)
Create an insertion point before (Before=true) or after Instr.
Definition: RegBankSelect.cpp:869
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::RegisterBankInfo::InstructionMapping::verify
bool verify(const MachineInstr &MI) const
Verifiy that this mapping makes sense for MI.
Definition: RegisterBankInfo.cpp:595
llvm::RegisterBankInfo::getRegBank
RegisterBank & getRegBank(unsigned ID)
Get the register bank identified by ID.
Definition: RegisterBankInfo.h:432
ErrorHandling.h
RegisterBankInfo.h
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::DisableGISelLegalityCheck
cl::opt< bool > DisableGISelLegalityCheck
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:124
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
BlockFrequency.h
llvm::getSelectionDAGFallbackAnalysisUsage
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:863
llvm::MachineIRBuilder::buildInstrNoInsert
MachineInstrBuilder buildInstrNoInsert(unsigned Opcode)
Build but don't insert <empty> = Opcode <empty>.
Definition: MachineIRBuilder.cpp:40
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
STLExtras.h
llvm::RegisterBankInfo::InstructionMapping::isValid
bool isValid() const
Check whether this object is valid.
Definition: RegisterBankInfo.h:254
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:105
LegalizerInfo.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
llvm::RegBankSelect::RepairingPlacement::Insert
@ Insert
Reparing code needs to happen before InsertPoints.
Definition: RegBankSelect.h:321
llvm::RegBankSelect::MBBInsertPoint::frequency
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
Definition: RegBankSelect.cpp:921
llvm::MachineBlockFrequencyInfo::getBlockFreq
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
Definition: MachineBlockFrequencyInfo.cpp:230
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::RegisterBankInfo::ValueMapping::BreakDown
const PartialMapping * BreakDown
How the value is broken down between the different register banks.
Definition: RegisterBankInfo.h:147
llvm::RegisterBankInfo::ValueMapping::partsAllUniform
bool partsAllUniform() const
Definition: RegisterBankInfo.cpp:535
llvm::RegBankSelect::RepairingPlacement::hasSplit
bool hasSplit()
Definition: RegBankSelect.h:365
F
#define F(x, y, z)
Definition: MD5.cpp:56
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::RegBankSelect::InstrInsertPoint::frequency
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
Definition: RegBankSelect.cpp:911
llvm::RegisterBankInfo::getBreakDownCost
virtual unsigned getBreakDownCost(const ValueMapping &ValMapping, const RegisterBank *CurBank=nullptr) const
Get the cost of using ValMapping to decompose a register.
Definition: RegisterBankInfo.h:633
llvm::MachineInstr::isUnconditionalBranch
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:877
CommandLine.h
llvm::MachineInstrBuilder::addDef
const MachineInstrBuilder & addDef(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register definition operand.
Definition: MachineInstrBuilder.h:116
llvm::RegBankSelect::RepairingPlacement::RepairingKind
RepairingKind
Define the kind of action this repairing needs.
Definition: RegBankSelect.h:317
llvm::RegBankSelect::EdgeInsertPoint::frequency
uint64_t frequency(const Pass &P) const override
Frequency of the insertion point.
Definition: RegBankSelect.cpp:942
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:640
llvm::ms_demangle::IntrinsicFunctionKind::Assign
@ Assign
llvm::RegisterBank
This class implements the register bank concept.
Definition: RegisterBank.h:28
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:24
llvm::MachineIRBuilder::setMBB
void setMBB(MachineBasicBlock &MBB)
Set the insertion point to the end of MBB.
Definition: MachineIRBuilder.h:324
llvm::RegBankSelect::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
Walk through MF and assign a register bank to every virtual register that are still mapped to nothing...
Definition: RegBankSelect.cpp:669
llvm::LLT::getSizeInBits
TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelTypeImpl.h:153
llvm::RegisterBankInfo::applyMapping
void applyMapping(const OperandsMapper &OpdMapper) const
Apply OpdMapper.getInstrMapping() to OpdMapper.getMI().
Definition: RegisterBankInfo.h:715
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
Utils.h
llvm::MachineFunction::getProperties
const MachineFunctionProperties & getProperties() const
Get the function properties.
Definition: MachineFunction.h:721
UINT64_MAX
#define UINT64_MAX
Definition: DataTypes.h:77
llvm::RegisterBankInfo::getInstrPossibleMappings
InstructionMappings getInstrPossibleMappings(const MachineInstr &MI) const
Get the possible mapping for MI.
Definition: RegisterBankInfo.cpp:414
false
Definition: StackSlotColoring.cpp:142
TargetOpcodes.h
llvm::RegBankSelect::EdgeInsertPoint
Insertion point on an edge.
Definition: RegBankSelect.h:273
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::TargetPassConfig::isGlobalISelAbortEnabled
bool isGlobalISelAbortEnabled() const
Check whether or not GlobalISel should abort on error.
Definition: TargetPassConfig.cpp:1526
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false)
llvm::machineFunctionIsIllegal
const MachineInstr * machineFunctionIsIllegal(const MachineFunction &MF)
Checks that MIR is fully legal, returns an illegal instruction if it's not, nullptr otherwise.
Definition: LegalizerInfo.cpp:426
llvm::MachineIRBuilder::getMF
MachineFunction & getMF()
Getter for the function we currently build.
Definition: MachineIRBuilder.h:262
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::RegBankSelect::InstrInsertPoint
Insertion point before or after an instruction.
Definition: RegBankSelect.h:204
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::RegBankSelect::InsertPoint::canMaterialize
virtual bool canMaterialize() const
Check whether this insertion point can be materialized.
Definition: RegBankSelect.h:200
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:238
llvm::RegBankSelect::RepairingPlacement::Reassign
@ Reassign
(Re)assign the register bank of the operand.
Definition: RegBankSelect.h:323
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::RegisterBankInfo::getSizeInBits
unsigned getSizeInBits(Register Reg, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI) const
Get the size in bits of Reg.
Definition: RegisterBankInfo.cpp:493
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::Pass::print
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:125
llvm::RegisterBankInfo::OperandsMapper
Helper class used to get/create the virtual registers that will be used to replace the MachineOperand...
Definition: RegisterBankInfo.h:280
MachineOptimizationRemarkEmitter.h
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
llvm::TargetPassConfig
Target-Independent Code Generator Pass Configuration Options.
Definition: TargetPassConfig.h:84
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:630
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::BlockFrequency
Definition: BlockFrequency.h:24
llvm::cl::values
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:697
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:321
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineInstrBuilder
Definition: MachineInstrBuilder.h:69
uint64_t
llvm::MachineRegisterInfo::setRegBank
void setRegBank(Register Reg, const RegisterBank &RegBank)
Set the register bank to RegBank for Reg.
Definition: MachineRegisterInfo.cpp:63
llvm::RegisterBankInfo::InstructionMapping
Helper class that represents how the value of an instruction may be mapped and what is the related co...
Definition: RegisterBankInfo.h:189
llvm::MachineFunction::CloneMachineInstr
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Definition: MachineFunction.cpp:359
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::RegisterBankInfo::InstructionMapping::getNumOperands
unsigned getNumOperands() const
Get the number of operands.
Definition: RegisterBankInfo.h:234
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::RegBankSelect::InstrInsertPoint::isSplit
bool isSplit() const override
Does this point involve splitting an edge or block? As soon as ::getPoint is called and thus,...
Definition: RegBankSelect.cpp:902
llvm::BlockFrequency::getFrequency
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
Definition: BlockFrequency.h:35
llvm::LLT::isVector
bool isVector() const
Definition: LowLevelTypeImpl.h:123
llvm::LLT::getNumElements
uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
Definition: LowLevelTypeImpl.h:127
llvm::MachineBasicBlock::getLastNonDebugInstr
iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
Definition: MachineBasicBlock.cpp:267
TargetPassConfig.h
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:542
llvm::SmallVectorImpl::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:563
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBranchProbabilityInfo.h
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::RegisterBankInfo::InstructionMapping::getCost
unsigned getCost() const
Get the cost.
Definition: RegisterBankInfo.h:228
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
Mode
SI Whole Quad Mode
Definition: SIWholeQuadMode.cpp:262
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1255
llvm::MachineInstrBuilder::addUse
const MachineInstrBuilder & addUse(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register use operand.
Definition: MachineInstrBuilder.h:123
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::RegisterBankInfo::PartialMapping::RegBank
const RegisterBank * RegBank
Register bank where the partial value lives.
Definition: RegisterBankInfo.h:60
llvm::MachineBranchProbabilityInfo::getEdgeProbability
BranchProbability getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const
Definition: MachineBranchProbabilityInfo.cpp:58
register
should just be implemented with a CLZ instruction Since there are other e that share this it would be best to implement this in a target independent as zero is the default value for the binary encoder e add r0 add r5 Register operands should be distinct That when the encoding does not require two syntactical operands to refer to the same register
Definition: README.txt:726
llvm::MachineInstr::readsRegister
bool readsRegister(Register Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
Definition: MachineInstr.h:1368
llvm::TargetSubtargetInfo::getRegBankInfo
virtual const RegisterBankInfo * getRegBankInfo() const
If the information for the register banks is available, return it.
Definition: TargetSubtargetInfo.h:128
llvm::MachineFunction
Definition: MachineFunction.h:234
llvm::size
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:1532
llvm::RegisterBankInfo::ValueMapping
Helper struct that represents how a value is mapped through different register banks.
Definition: RegisterBankInfo.h:145
llvm::RegBankSelect::RepairingPlacement::None
@ None
Nothing to repair, just drop this action.
Definition: RegBankSelect.h:319
llvm::RegBankSelect::RepairingPlacement::getNumInsertPoints
unsigned getNumInsertPoints() const
Definition: RegBankSelect.h:389
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::RegBankSelect::RepairingPlacement
Struct used to represent the placement of a repairing point for a given operand.
Definition: RegBankSelect.h:314
Compiler.h
TargetSubtargetInfo.h
clEnumValN
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:672
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
llvm::RegisterBankInfo::PartialMapping::Length
unsigned Length
Length of this mapping in bits.
Definition: RegisterBankInfo.h:57
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::cl::Optional
@ Optional
Definition: CommandLine.h:119
llvm::RegBankSelect::EdgeInsertPoint::canMaterialize
bool canMaterialize() const override
Check whether this insertion point can be materialized.
Definition: RegBankSelect.cpp:959
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
Attributes.h
llvm::MachineFunctionProperties::Property::FailedISel
@ FailedISel
operator==
bool operator==(const StringView &LHS, const StringView &RHS)
Definition: StringView.h:112
Reassign
GCN NSA Reassign
Definition: GCNNSAReassign.cpp:98
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:596
operator<
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
llvm::isTargetSpecificOpcode
bool isTargetSpecificOpcode(unsigned Opcode)
Check whether the given Opcode is a target-specific opcode.
Definition: TargetOpcodes.h:36
llvm::RegBankSelect::InsertPoint::isSplit
virtual bool isSplit() const
Does this point involve splitting an edge or block? As soon as ::getPoint is called and thus,...
Definition: RegBankSelect.h:188
RegBankSelect.h
Function.h
llvm::MachineRegisterInfo::getRegBankOrNull
const RegisterBank * getRegBankOrNull(Register Reg) const
Return the register bank of Reg, or null if Reg has not been assigned a register bank or has been ass...
Definition: MachineRegisterInfo.h:660
llvm::RegisterBankInfo::copyCost
virtual unsigned copyCost(const RegisterBank &A, const RegisterBank &B, unsigned Size) const
Get the cost of a copy from B to A, or put differently, get the cost of A = COPY B.
Definition: RegisterBankInfo.h:614
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::RegisterBankInfo::getInstrMapping
virtual const InstructionMapping & getInstrMapping(const MachineInstr &MI) const
Get the mapping of the different operands of MI on the register bank.
Definition: RegisterBankInfo.cpp:406
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
llvm::reportGISelFailure
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:252
llvm::RegisterBankInfo::ValueMapping::NumBreakDowns
unsigned NumBreakDowns
Number of partial mapping to break down this value.
Definition: RegisterBankInfo.h:150
llvm::RegBankSelect::Mode
Mode
List of the modes supported by the RegBankSelect pass.
Definition: RegBankSelect.h:96
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
PostOrderIterator.h
llvm::RegBankSelect::RepairingPlacement::switchTo
void switchTo(RepairingKind NewKind)
Change the type of this repairing placement to NewKind.
Definition: RegBankSelect.h:399
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
llvm::MachineRegisterInfo::getType
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
Definition: MachineRegisterInfo.h:732
RegisterBank.h
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
LLVM_LIKELY
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:225
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::RegBankSelect::RepairingPlacement::getOpIdx
unsigned getOpIdx() const
Definition: RegBankSelect.h:363
MachineOperand.h
llvm::RegBankSelect::ID
static char ID
Definition: RegBankSelect.h:93
llvm::RegBankSelect
This pass implements the reg bank selector pass used in the GlobalISel pipeline.
Definition: RegBankSelect.h:91
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::RegBankSelect::MBBInsertPoint
Insertion point at the beginning or end of a basic block.
Definition: RegBankSelect.h:237
llvm::cl::desc
Definition: CommandLine.h:412
DEBUG_TYPE
#define DEBUG_TYPE
Definition: RegBankSelect.cpp:50
raw_ostream.h
MachineFunction.h
llvm::printReg
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.
Definition: TargetRegisterInfo.cpp:110
registers
Implement PPCInstrInfo::isLoadFromStackSlot isStoreToStackSlot for vector registers
Definition: README_ALTIVEC.txt:4
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
MachineBlockFrequencyInfo.h
llvm::RegBankSelect::RepairingPlacement::Impossible
@ Impossible
Mark this repairing placement as impossible.
Definition: RegBankSelect.h:325
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::RegBankSelect::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: RegBankSelect.cpp:99
of
Add support for conditional and other related patterns Instead of
Definition: README.txt:134
RegBankSelectMode
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)")))
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::LLT
Definition: LowLevelTypeImpl.h:40