1 //===- llvm/CodeGen/GlobalISel/RegBankSelect.cpp - RegBankSelect -*- C++ -*-==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 /// This file implements the RegBankSelect class.
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/ADT/PostOrderIterator.h"
14 #include "llvm/CodeGen/GlobalISel/RegBankSelect.h"
15 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
16 #include "llvm/CodeGen/MachineRegisterInfo.h"
17 #include "llvm/Support/Debug.h"
18 #include "llvm/Target/TargetSubtargetInfo.h"
19 
20 #define DEBUG_TYPE "regbankselect"
21 
22 using namespace llvm;
23 
24 char RegBankSelect::ID = 0;
25 INITIALIZE_PASS(RegBankSelect, "regbankselect",
26                 "Assign register bank of generic virtual registers",
27                 false, false);
28 
29 RegBankSelect::RegBankSelect()
30     : MachineFunctionPass(ID), RBI(nullptr), MRI(nullptr) {
31   initializeRegBankSelectPass(*PassRegistry::getPassRegistry());
32 }
33 
34 void RegBankSelect::init(MachineFunction &MF) {
35   RBI = MF.getSubtarget().getRegBankInfo();
36   assert(RBI && "Cannot work without RegisterBankInfo");
37   MRI = &MF.getRegInfo();
38   TRI = MF.getSubtarget().getRegisterInfo();
39   MIRBuilder.setMF(MF);
40 }
41 
42 bool RegBankSelect::assignmentMatch(
43     unsigned Reg, const RegisterBankInfo::ValueMapping &ValMapping) const {
44   // Each part of a break down needs to end up in a different register.
45   // In other word, Reg assignement does not match.
46   if (ValMapping.BreakDown.size() > 1)
47     return false;
48 
49   const RegisterBank *CurRegBank = RBI->getRegBank(Reg, *MRI, *TRI);
50   const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank;
51   DEBUG(dbgs() << "Does assignment already match: ";
52         if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";
53         dbgs() << " against ";
54         assert(DesiredRegBrank && "The mapping must be valid");
55         dbgs() << *DesiredRegBrank << '\n';);
56   return CurRegBank == DesiredRegBrank;
57 }
58 
59 unsigned
60 RegBankSelect::repairReg(unsigned Reg,
61                          const RegisterBankInfo::ValueMapping &ValMapping) {
62   assert(ValMapping.BreakDown.size() == 1 &&
63          "Support for complex break down not supported yet");
64   const RegisterBankInfo::PartialMapping &PartialMap = ValMapping.BreakDown[0];
65   assert(PartialMap.Mask.getBitWidth() == MRI->getSize(Reg) &&
66          "Repairing other than copy not implemented yet");
67   unsigned NewReg =
68       MRI->createGenericVirtualRegister(PartialMap.Mask.getBitWidth());
69   (void)MIRBuilder.buildInstr(TargetOpcode::COPY, NewReg, Reg);
70   DEBUG(dbgs() << "Repair: " << PrintReg(Reg) << " with: "
71         << PrintReg(NewReg) << '\n');
72   return NewReg;
73 }
74 
75 void RegBankSelect::assignInstr(MachineInstr &MI) {
76   DEBUG(dbgs() << "Assign: " << MI);
77   const RegisterBankInfo::InstructionMapping DefaultMapping =
78       RBI->getInstrMapping(MI);
79   // Make sure the mapping is valid for MI.
80   DefaultMapping.verify(MI);
81 
82   DEBUG(dbgs() << "Mapping: " << DefaultMapping << '\n');
83 
84   // Set the insertion point before MI.
85   // This is where we are going to insert the repairing code if any.
86   MIRBuilder.setInstr(MI, /*Before*/ true);
87 
88   // For now, do not look for alternative mappings.
89   // Alternative mapping may require to rewrite MI and we do not support
90   // that yet.
91   // Walk the operands and assign then to the chosen mapping, possibly with
92   // the insertion of repair code for uses.
93   for (unsigned OpIdx = 0, EndIdx = MI.getNumOperands(); OpIdx != EndIdx;
94        ++OpIdx) {
95     MachineOperand &MO = MI.getOperand(OpIdx);
96     // Nothing to be done for non-register operands.
97     if (!MO.isReg())
98       continue;
99     unsigned Reg = MO.getReg();
100     if (!Reg)
101       continue;
102 
103     const RegisterBankInfo::ValueMapping &ValMapping =
104         DefaultMapping.getOperandMapping(OpIdx);
105     // If Reg is already properly mapped, move on.
106     if (assignmentMatch(Reg, ValMapping))
107       continue;
108 
109     // For uses, we may need to create a new temporary.
110     // Indeed, if Reg is already assigned a register bank, at this
111     // point, we know it is different from the one defined by the
112     // chosen mapping, we need to adjust for that.
113     assert(ValMapping.BreakDown.size() == 1 &&
114            "Support for complex break down not supported yet");
115     if (!MO.isDef() && MRI->getRegClassOrRegBank(Reg)) {
116       // For phis, we need to change the insertion point to the end of
117       // the related predecessor block.
118       assert(!MI.isPHI() && "PHI support not implemented yet");
119       Reg = repairReg(Reg, ValMapping);
120     }
121     // If we end up here, MO should be free of encoding constraints,
122     // i.e., we do not have to constrained the RegBank of Reg to
123     // the requirement of the operands.
124     // If that is not the case, this means the code was broken before
125     // hands because we should have found that the assignment match.
126     // This will not hold when we will consider alternative mappings.
127     DEBUG(dbgs() << "Assign: " << *ValMapping.BreakDown[0].RegBank << " to "
128                  << PrintReg(Reg) << '\n');
129     // For a definition, we may be changing the register bank silently
130     // for all the uses here.
131     // Although this will be correct when we do a RPO traversal of the
132     // basic block, because the only uses that could be affected are
133     // PHIs (i.e., copies), this may not be the best solution
134     // according to the cost model.
135     MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);
136     MO.setReg(Reg);
137   }
138   DEBUG(dbgs() << "Assigned: " << MI);
139 }
140 
141 bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) {
142   DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
143   init(MF);
144   // Walk the function and assign register banks to all operands.
145   // Use a RPOT to make sure all registers are assigned before we choose
146   // the best mapping of the current instruction.
147   ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);
148   for (MachineBasicBlock *MBB : RPOT)
149     for (MachineInstr &MI : *MBB)
150       assignInstr(MI);
151   return false;
152 }
153