blob: 2bd1534d722f7274ef9f4ae404f51d952af98a64 [file] [log] [blame]
Quentin Colombet8e8e85c2016-04-05 19:06:01 +00001//===- llvm/CodeGen/GlobalISel/RegBankSelect.cpp - RegBankSelect -*- C++ -*-==//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9/// \file
10/// This file implements the RegBankSelect class.
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/GlobalISel/RegBankSelect.h"
Quentin Colombetcfd97b92016-05-20 00:35:26 +000014#include "llvm/ADT/PostOrderIterator.h"
Quentin Colombet40ad5732016-04-07 18:19:27 +000015#include "llvm/CodeGen/GlobalISel/RegisterBank.h"
16#include "llvm/CodeGen/MachineRegisterInfo.h"
Quentin Colombetcfd97b92016-05-20 00:35:26 +000017#include "llvm/Support/BlockFrequency.h"
Quentin Colombete16f5612016-04-07 23:53:55 +000018#include "llvm/Support/Debug.h"
Quentin Colombet40ad5732016-04-07 18:19:27 +000019#include "llvm/Target/TargetSubtargetInfo.h"
Quentin Colombet8e8e85c2016-04-05 19:06:01 +000020
21#define DEBUG_TYPE "regbankselect"
22
23using namespace llvm;
24
25char RegBankSelect::ID = 0;
26INITIALIZE_PASS(RegBankSelect, "regbankselect",
27 "Assign register bank of generic virtual registers",
28 false, false);
29
Quentin Colombet40ad5732016-04-07 18:19:27 +000030RegBankSelect::RegBankSelect()
31 : MachineFunctionPass(ID), RBI(nullptr), MRI(nullptr) {
Quentin Colombet8e8e85c2016-04-05 19:06:01 +000032 initializeRegBankSelectPass(*PassRegistry::getPassRegistry());
33}
34
Quentin Colombet40ad5732016-04-07 18:19:27 +000035void RegBankSelect::init(MachineFunction &MF) {
36 RBI = MF.getSubtarget().getRegBankInfo();
37 assert(RBI && "Cannot work without RegisterBankInfo");
38 MRI = &MF.getRegInfo();
Quentin Colombetaac71a42016-04-07 21:32:23 +000039 TRI = MF.getSubtarget().getRegisterInfo();
Quentin Colombet40ad5732016-04-07 18:19:27 +000040 MIRBuilder.setMF(MF);
41}
42
43bool RegBankSelect::assignmentMatch(
44 unsigned Reg, const RegisterBankInfo::ValueMapping &ValMapping) const {
45 // Each part of a break down needs to end up in a different register.
46 // In other word, Reg assignement does not match.
47 if (ValMapping.BreakDown.size() > 1)
48 return false;
49
Quentin Colombet6d6d6af2016-04-08 16:48:16 +000050 const RegisterBank *CurRegBank = RBI->getRegBank(Reg, *MRI, *TRI);
51 const RegisterBank *DesiredRegBrank = ValMapping.BreakDown[0].RegBank;
52 DEBUG(dbgs() << "Does assignment already match: ";
53 if (CurRegBank) dbgs() << *CurRegBank; else dbgs() << "none";
54 dbgs() << " against ";
55 assert(DesiredRegBrank && "The mapping must be valid");
56 dbgs() << *DesiredRegBrank << '\n';);
57 return CurRegBank == DesiredRegBrank;
Quentin Colombet40ad5732016-04-07 18:19:27 +000058}
59
60unsigned
61RegBankSelect::repairReg(unsigned Reg,
Quentin Colombet904a2c72016-04-12 00:12:59 +000062 const RegisterBankInfo::ValueMapping &ValMapping,
63 MachineInstr &DefUseMI, bool IsDef) {
Quentin Colombet40ad5732016-04-07 18:19:27 +000064 assert(ValMapping.BreakDown.size() == 1 &&
65 "Support for complex break down not supported yet");
66 const RegisterBankInfo::PartialMapping &PartialMap = ValMapping.BreakDown[0];
Quentin Colombet0e5ff582016-04-21 18:09:34 +000067 assert(PartialMap.Length ==
Quentin Colombet777a7712016-04-12 00:38:51 +000068 (TargetRegisterInfo::isPhysicalRegister(Reg)
69 ? TRI->getMinimalPhysRegClass(Reg)->getSize() * 8
70 : MRI->getSize(Reg)) &&
Quentin Colombet40ad5732016-04-07 18:19:27 +000071 "Repairing other than copy not implemented yet");
Quentin Colombet904a2c72016-04-12 00:12:59 +000072 // If the MIRBuilder is configured to insert somewhere else than
73 // DefUseMI, we may not use this function like was it first
74 // internded (local repairing), so make sure we pay attention before
75 // we remove the assert.
76 // In particular, it is likely that we will have to properly save
77 // the insertion point of the MIRBuilder and restore it at the end
78 // of this method.
79 assert(&DefUseMI == &(*MIRBuilder.getInsertPt()) &&
80 "Need to save and restore the insertion point");
81 // For use, we will add a copy just in front of the instruction.
82 // For def, we will add a copy just after the instruction.
83 // In either case, the insertion point must be valid. In particular,
84 // make sure we do not insert in the middle of terminators or phis.
85 bool Before = !IsDef;
86 setSafeInsertionPoint(DefUseMI, Before);
87 if (DefUseMI.isTerminator() && Before) {
88 // Check that the insertion point does not happen
89 // before the definition of Reg.
90 // This can happen if Reg is defined by a terminator
91 // and used by another one.
92 // In that case the repairing code is actually more involved
93 // because we have to split the block.
94
95 // Assert that this is not a physical register.
96 // The target independent code does not insert physical registers
97 // on terminators, so if we end up in this situation, this is
98 // likely a bug in the target.
99 assert(!TargetRegisterInfo::isPhysicalRegister(Reg) &&
100 "Check for physical register not implemented");
101 const MachineInstr *RegDef = MRI->getVRegDef(Reg);
102 assert(RegDef && "Reg has more than one definition?");
103 // Assert to make the code more readable; Reg is used by DefUseMI, i.e.,
104 // (Before == !IsDef == true), so DefUseMI != RegDef otherwise we have
105 // a use (that is not a PHI) that is not dominated by its def.
106 assert(&DefUseMI != RegDef && "Def does not dominate all of its uses");
107 if (RegDef->isTerminator() && RegDef->getParent() == DefUseMI.getParent())
108 // By construction, the repairing should happen between two
109 // terminators: RegDef and DefUseMI.
110 // This is not implemented.
111 report_fatal_error("Repairing between terminators not implemented yet");
112 }
113
114 // Create a new temporary to hold the repaired value.
Quentin Colombet0e5ff582016-04-21 18:09:34 +0000115 unsigned NewReg = MRI->createGenericVirtualRegister(PartialMap.Length);
Quentin Colombet904a2c72016-04-12 00:12:59 +0000116 // Set the registers for the source and destination of the copy.
117 unsigned Src = Reg, Dst = NewReg;
118 // If this is a definition that we repair, the copy will be
119 // inverted.
120 if (IsDef)
121 std::swap(Src, Dst);
122 (void)MIRBuilder.buildInstr(TargetOpcode::COPY, Dst, Src);
123
Quentin Colombete16f5612016-04-07 23:53:55 +0000124 DEBUG(dbgs() << "Repair: " << PrintReg(Reg) << " with: "
125 << PrintReg(NewReg) << '\n');
Quentin Colombet904a2c72016-04-12 00:12:59 +0000126
127 // Restore the insertion point of the MIRBuilder.
128 MIRBuilder.setInstr(DefUseMI, Before);
Quentin Colombet40ad5732016-04-07 18:19:27 +0000129 return NewReg;
130}
131
Quentin Colombet904a2c72016-04-12 00:12:59 +0000132void RegBankSelect::setSafeInsertionPoint(MachineInstr &InsertPt, bool Before) {
133 // Check that we are not looking to insert before a phi.
134 // Indeed, we would need more information on what to do.
135 // By default that should be all the predecessors, but this is
136 // probably not what we want in general.
137 assert((!Before || !InsertPt.isPHI()) &&
138 "Insertion before phis not implemented");
139 // The same kind of observation hold for terminators if we try to
140 // insert after them.
141 assert((Before || !InsertPt.isTerminator()) &&
142 "Insertion after terminatos not implemented");
143 if (InsertPt.isPHI()) {
144 assert(!Before && "Not supported!!");
145 MachineBasicBlock *MBB = InsertPt.getParent();
146 assert(MBB && "Insertion point is not in a basic block");
147 MachineBasicBlock::iterator FirstNonPHIPt = MBB->getFirstNonPHI();
148 if (FirstNonPHIPt == MBB->end()) {
149 // If there is not any non-phi instruction, insert at the end of MBB.
150 MIRBuilder.setMBB(*MBB, /*Beginning*/ false);
151 return;
152 }
153 // The insertion point before the first non-phi instruction.
154 MIRBuilder.setInstr(*FirstNonPHIPt, /*Before*/ true);
155 return;
156 }
157 if (InsertPt.isTerminator()) {
158 MachineBasicBlock *MBB = InsertPt.getParent();
159 assert(MBB && "Insertion point is not in a basic block");
160 MIRBuilder.setInstr(*MBB->getFirstTerminator(), /*Before*/ true);
161 return;
162 }
163 MIRBuilder.setInstr(InsertPt, /*Before*/ Before);
164}
165
Quentin Colombet40ad5732016-04-07 18:19:27 +0000166void RegBankSelect::assignInstr(MachineInstr &MI) {
Quentin Colombete16f5612016-04-07 23:53:55 +0000167 DEBUG(dbgs() << "Assign: " << MI);
Quentin Colombet40ad5732016-04-07 18:19:27 +0000168 const RegisterBankInfo::InstructionMapping DefaultMapping =
169 RBI->getInstrMapping(MI);
170 // Make sure the mapping is valid for MI.
Quentin Colombetc320fb42016-04-21 18:34:43 +0000171 assert(DefaultMapping.verify(MI) && "Invalid instruction mapping");
Quentin Colombete16f5612016-04-07 23:53:55 +0000172
173 DEBUG(dbgs() << "Mapping: " << DefaultMapping << '\n');
174
Quentin Colombet40ad5732016-04-07 18:19:27 +0000175 // Set the insertion point before MI.
176 // This is where we are going to insert the repairing code if any.
177 MIRBuilder.setInstr(MI, /*Before*/ true);
178
179 // For now, do not look for alternative mappings.
180 // Alternative mapping may require to rewrite MI and we do not support
181 // that yet.
182 // Walk the operands and assign then to the chosen mapping, possibly with
183 // the insertion of repair code for uses.
184 for (unsigned OpIdx = 0, EndIdx = MI.getNumOperands(); OpIdx != EndIdx;
185 ++OpIdx) {
186 MachineOperand &MO = MI.getOperand(OpIdx);
187 // Nothing to be done for non-register operands.
188 if (!MO.isReg())
189 continue;
190 unsigned Reg = MO.getReg();
191 if (!Reg)
192 continue;
193
194 const RegisterBankInfo::ValueMapping &ValMapping =
195 DefaultMapping.getOperandMapping(OpIdx);
196 // If Reg is already properly mapped, move on.
197 if (assignmentMatch(Reg, ValMapping))
198 continue;
199
200 // For uses, we may need to create a new temporary.
201 // Indeed, if Reg is already assigned a register bank, at this
202 // point, we know it is different from the one defined by the
203 // chosen mapping, we need to adjust for that.
Quentin Colombet904a2c72016-04-12 00:12:59 +0000204 // For definitions, changing the register bank will affect all
205 // its uses, and in particular the ones we already visited.
206 // Although this is correct, since with the RPO traversal of the
207 // basic blocks the only uses that we already visisted for this
208 // definition are PHIs (i.e., copies), this may not be the best
209 // solution according to the cost model.
210 // Therefore, create a new temporary for Reg.
Quentin Colombet40ad5732016-04-07 18:19:27 +0000211 assert(ValMapping.BreakDown.size() == 1 &&
212 "Support for complex break down not supported yet");
Quentin Colombet777a7712016-04-12 00:38:51 +0000213 if (TargetRegisterInfo::isPhysicalRegister(Reg) ||
214 MRI->getRegClassOrRegBank(Reg)) {
Quentin Colombet904a2c72016-04-12 00:12:59 +0000215 if (!MO.isDef() && MI.isPHI()) {
216 // Phis are already copies, so there is nothing to repair.
217 // Note: This will not hold when we support break downs with
218 // more than one segment.
219 DEBUG(dbgs() << "Skip PHI use\n");
220 continue;
221 }
222 // If MO is a definition, since repairing after a terminator is
223 // painful, do not repair. Indeed, this is probably not worse
224 // saving the move in the PHIs that will get reassigned.
225 if (!MO.isDef() || !MI.isTerminator())
226 Reg = repairReg(Reg, ValMapping, MI, MO.isDef());
Quentin Colombet40ad5732016-04-07 18:19:27 +0000227 }
Quentin Colombet904a2c72016-04-12 00:12:59 +0000228
Quentin Colombet40ad5732016-04-07 18:19:27 +0000229 // If we end up here, MO should be free of encoding constraints,
230 // i.e., we do not have to constrained the RegBank of Reg to
231 // the requirement of the operands.
232 // If that is not the case, this means the code was broken before
233 // hands because we should have found that the assignment match.
234 // This will not hold when we will consider alternative mappings.
Quentin Colombet6d6d6af2016-04-08 16:48:16 +0000235 DEBUG(dbgs() << "Assign: " << *ValMapping.BreakDown[0].RegBank << " to "
236 << PrintReg(Reg) << '\n');
Quentin Colombet904a2c72016-04-12 00:12:59 +0000237
Quentin Colombet40ad5732016-04-07 18:19:27 +0000238 MRI->setRegBank(Reg, *ValMapping.BreakDown[0].RegBank);
239 MO.setReg(Reg);
240 }
Quentin Colombete16f5612016-04-07 23:53:55 +0000241 DEBUG(dbgs() << "Assigned: " << MI);
Quentin Colombet40ad5732016-04-07 18:19:27 +0000242}
243
Quentin Colombet8e8e85c2016-04-05 19:06:01 +0000244bool RegBankSelect::runOnMachineFunction(MachineFunction &MF) {
Quentin Colombete16f5612016-04-07 23:53:55 +0000245 DEBUG(dbgs() << "Assign register banks for: " << MF.getName() << '\n');
Quentin Colombet40ad5732016-04-07 18:19:27 +0000246 init(MF);
247 // Walk the function and assign register banks to all operands.
Quentin Colombetab8c21f2016-04-08 17:19:10 +0000248 // Use a RPOT to make sure all registers are assigned before we choose
249 // the best mapping of the current instruction.
250 ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);
251 for (MachineBasicBlock *MBB : RPOT)
252 for (MachineInstr &MI : *MBB)
Quentin Colombet40ad5732016-04-07 18:19:27 +0000253 assignInstr(MI);
Quentin Colombet8e8e85c2016-04-05 19:06:01 +0000254 return false;
255}
Quentin Colombetcfd97b92016-05-20 00:35:26 +0000256
257//------------------------------------------------------------------------------
258// Helper Class Implementation
259//------------------------------------------------------------------------------
260RegBankSelect::MappingCost::MappingCost(const BlockFrequency &LocalFreq)
261 : LocalCost(0), NonLocalCost(0), LocalFreq(LocalFreq.getFrequency()) {}
262
263bool RegBankSelect::MappingCost::addLocalCost(uint64_t Cost) {
264 // Check if this overflows.
265 if (LocalCost + Cost < LocalCost) {
266 saturate();
267 return true;
268 }
269 LocalCost += Cost;
270 return isSaturated();
271}
272
273bool RegBankSelect::MappingCost::addNonLocalCost(uint64_t Cost) {
274 // Check if this overflows.
275 if (NonLocalCost + Cost < NonLocalCost) {
276 saturate();
277 return true;
278 }
279 NonLocalCost += Cost;
280 return isSaturated();
281}
282
283bool RegBankSelect::MappingCost::isSaturated() const {
284 return LocalCost == UINT64_MAX - 1 && NonLocalCost == UINT64_MAX &&
285 LocalFreq == UINT64_MAX;
286}
287
288void RegBankSelect::MappingCost::saturate() {
289 *this = ImpossibleCost();
290 --LocalCost;
291}
292
293RegBankSelect::MappingCost RegBankSelect::MappingCost::ImpossibleCost() {
294 return MappingCost(UINT64_MAX, UINT64_MAX, UINT64_MAX);
295}
296
297bool RegBankSelect::MappingCost::operator<(const MappingCost &Cost) const {
298 // Sort out the easy cases.
299 if (*this == Cost)
300 return false;
301 // If one is impossible to realize the other is cheaper unless it is
302 // impossible as well.
303 if ((*this == ImpossibleCost()) || (Cost == ImpossibleCost()))
304 return (*this == ImpossibleCost()) < (Cost == ImpossibleCost());
305 // If one is saturated the other is cheaper, unless it is saturated
306 // as well.
307 if (isSaturated() || Cost.isSaturated())
308 return isSaturated() < Cost.isSaturated();
309 // At this point we know both costs hold sensible values.
310
311 // If both values have a different base frequency, there is no much
312 // we can do but to scale everything.
313 // However, if they have the same base frequency we can avoid making
314 // complicated computation.
315 uint64_t ThisLocalAdjust;
316 uint64_t OtherLocalAdjust;
317 if (LLVM_LIKELY(LocalFreq == Cost.LocalFreq)) {
318
319 // At this point, we know the local costs are comparable.
320 // Do the case that do not involve potential overflow first.
321 if (NonLocalCost == Cost.NonLocalCost)
322 // Since the non-local costs do not discriminate on the result,
323 // just compare the local costs.
324 return LocalCost < Cost.LocalCost;
325
326 // The base costs are comparable so we may only keep the relative
327 // value to increase our chances of avoiding overflows.
328 ThisLocalAdjust = 0;
329 OtherLocalAdjust = 0;
330 if (LocalCost < Cost.LocalCost)
331 OtherLocalAdjust = Cost.LocalCost - LocalCost;
332 else
333 ThisLocalAdjust = LocalCost - Cost.LocalCost;
334
335 } else {
336 ThisLocalAdjust = LocalCost;
337 OtherLocalAdjust = Cost.LocalCost;
338 }
339
340 // The non-local costs are comparable, just keep the relative value.
341 uint64_t ThisNonLocalAdjust = 0;
342 uint64_t OtherNonLocalAdjust = 0;
343 if (NonLocalCost < Cost.NonLocalCost)
344 OtherNonLocalAdjust = Cost.NonLocalCost - NonLocalCost;
345 else
346 ThisNonLocalAdjust = NonLocalCost - Cost.NonLocalCost;
347 // Scale everything to make them comparable.
348 uint64_t ThisScaledCost = ThisLocalAdjust * LocalFreq;
349 // Check for overflow on that operation.
350 bool ThisOverflows = ThisLocalAdjust && (ThisScaledCost < ThisLocalAdjust ||
351 ThisScaledCost < LocalFreq);
352 uint64_t OtherScaledCost = OtherLocalAdjust * Cost.LocalFreq;
353 // Check for overflow on the last operation.
354 bool OtherOverflows =
355 OtherLocalAdjust &&
356 (OtherScaledCost < OtherLocalAdjust || OtherScaledCost < Cost.LocalFreq);
357 // Add the non-local costs.
358 ThisOverflows |= ThisNonLocalAdjust &&
359 ThisScaledCost + ThisNonLocalAdjust < ThisNonLocalAdjust;
360 ThisScaledCost += ThisNonLocalAdjust;
361 OtherOverflows |= OtherNonLocalAdjust &&
362 OtherScaledCost + OtherNonLocalAdjust < OtherNonLocalAdjust;
363 OtherScaledCost += OtherNonLocalAdjust;
364 // If both overflows, we cannot compare without additional
365 // precision, e.g., APInt. Just give up on that case.
366 if (ThisOverflows && OtherOverflows)
367 return false;
368 // If one overflows but not the other, we can still compare.
369 if (ThisOverflows || OtherOverflows)
370 return ThisOverflows < OtherOverflows;
371 // Otherwise, just compare the values.
372 return ThisScaledCost < OtherScaledCost;
373}
374
375bool RegBankSelect::MappingCost::operator==(const MappingCost &Cost) const {
376 return LocalCost == Cost.LocalCost && NonLocalCost == Cost.NonLocalCost &&
377 LocalFreq == Cost.LocalFreq;
378}