[PBQP] Unique allowed-sets for nodes in the PBQP graph and use pairs of these
[oota-llvm.git] / lib / Target / AArch64 / AArch64PBQPRegAlloc.cpp
1 //===-- AArch64PBQPRegAlloc.cpp - AArch64 specific PBQP constraints -------===//
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 // This file contains the AArch64 / Cortex-A57 specific register allocation
10 // constraints for use by the PBQP register allocator.
11 //
12 // It is essentially a transcription of what is contained in
13 // AArch64A57FPLoadBalancing, which tries to use a balanced
14 // mix of odd and even D-registers when performing a critical sequence of
15 // independent, non-quadword FP/ASIMD floating-point multiply-accumulates.
16 //===----------------------------------------------------------------------===//
17
18 #define DEBUG_TYPE "aarch64-pbqp"
19
20 #include "AArch64.h"
21 #include "AArch64PBQPRegAlloc.h"
22 #include "AArch64RegisterInfo.h"
23 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
24 #include "llvm/CodeGen/MachineBasicBlock.h"
25 #include "llvm/CodeGen/MachineFunction.h"
26 #include "llvm/CodeGen/MachineRegisterInfo.h"
27 #include "llvm/CodeGen/RegAllocPBQP.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/ErrorHandling.h"
30 #include "llvm/Support/raw_ostream.h"
31
32 using namespace llvm;
33
34 namespace {
35
36 #ifndef NDEBUG
37 bool isFPReg(unsigned reg) {
38   return AArch64::FPR32RegClass.contains(reg) ||
39          AArch64::FPR64RegClass.contains(reg) ||
40          AArch64::FPR128RegClass.contains(reg);
41 }
42 #endif
43
44 bool isOdd(unsigned reg) {
45   switch (reg) {
46   default:
47     llvm_unreachable("Register is not from the expected class !");
48   case AArch64::S1:
49   case AArch64::S3:
50   case AArch64::S5:
51   case AArch64::S7:
52   case AArch64::S9:
53   case AArch64::S11:
54   case AArch64::S13:
55   case AArch64::S15:
56   case AArch64::S17:
57   case AArch64::S19:
58   case AArch64::S21:
59   case AArch64::S23:
60   case AArch64::S25:
61   case AArch64::S27:
62   case AArch64::S29:
63   case AArch64::S31:
64   case AArch64::D1:
65   case AArch64::D3:
66   case AArch64::D5:
67   case AArch64::D7:
68   case AArch64::D9:
69   case AArch64::D11:
70   case AArch64::D13:
71   case AArch64::D15:
72   case AArch64::D17:
73   case AArch64::D19:
74   case AArch64::D21:
75   case AArch64::D23:
76   case AArch64::D25:
77   case AArch64::D27:
78   case AArch64::D29:
79   case AArch64::D31:
80   case AArch64::Q1:
81   case AArch64::Q3:
82   case AArch64::Q5:
83   case AArch64::Q7:
84   case AArch64::Q9:
85   case AArch64::Q11:
86   case AArch64::Q13:
87   case AArch64::Q15:
88   case AArch64::Q17:
89   case AArch64::Q19:
90   case AArch64::Q21:
91   case AArch64::Q23:
92   case AArch64::Q25:
93   case AArch64::Q27:
94   case AArch64::Q29:
95   case AArch64::Q31:
96     return true;
97   case AArch64::S0:
98   case AArch64::S2:
99   case AArch64::S4:
100   case AArch64::S6:
101   case AArch64::S8:
102   case AArch64::S10:
103   case AArch64::S12:
104   case AArch64::S14:
105   case AArch64::S16:
106   case AArch64::S18:
107   case AArch64::S20:
108   case AArch64::S22:
109   case AArch64::S24:
110   case AArch64::S26:
111   case AArch64::S28:
112   case AArch64::S30:
113   case AArch64::D0:
114   case AArch64::D2:
115   case AArch64::D4:
116   case AArch64::D6:
117   case AArch64::D8:
118   case AArch64::D10:
119   case AArch64::D12:
120   case AArch64::D14:
121   case AArch64::D16:
122   case AArch64::D18:
123   case AArch64::D20:
124   case AArch64::D22:
125   case AArch64::D24:
126   case AArch64::D26:
127   case AArch64::D28:
128   case AArch64::D30:
129   case AArch64::Q0:
130   case AArch64::Q2:
131   case AArch64::Q4:
132   case AArch64::Q6:
133   case AArch64::Q8:
134   case AArch64::Q10:
135   case AArch64::Q12:
136   case AArch64::Q14:
137   case AArch64::Q16:
138   case AArch64::Q18:
139   case AArch64::Q20:
140   case AArch64::Q22:
141   case AArch64::Q24:
142   case AArch64::Q26:
143   case AArch64::Q28:
144   case AArch64::Q30:
145     return false;
146
147   }
148 }
149
150 bool haveSameParity(unsigned reg1, unsigned reg2) {
151   assert(isFPReg(reg1) && "Expecting an FP register for reg1");
152   assert(isFPReg(reg2) && "Expecting an FP register for reg2");
153
154   return isOdd(reg1) == isOdd(reg2);
155 }
156
157 }
158
159 bool A57ChainingConstraint::addIntraChainConstraint(PBQPRAGraph &G, unsigned Rd,
160                                                  unsigned Ra) {
161   if (Rd == Ra)
162     return false;
163
164   LiveIntervals &LIs = G.getMetadata().LIS;
165
166   if (TRI->isPhysicalRegister(Rd) || TRI->isPhysicalRegister(Ra)) {
167     DEBUG(dbgs() << "Rd is a physical reg:" << TRI->isPhysicalRegister(Rd)
168           << '\n');
169     DEBUG(dbgs() << "Ra is a physical reg:" << TRI->isPhysicalRegister(Ra)
170           << '\n');
171     return false;
172   }
173
174   PBQPRAGraph::NodeId node1 = G.getMetadata().getNodeIdForVReg(Rd);
175   PBQPRAGraph::NodeId node2 = G.getMetadata().getNodeIdForVReg(Ra);
176
177   const PBQPRAGraph::NodeMetadata::AllowedRegVector *vRdAllowed =
178     &G.getNodeMetadata(node1).getAllowedRegs();
179   const PBQPRAGraph::NodeMetadata::AllowedRegVector *vRaAllowed =
180     &G.getNodeMetadata(node2).getAllowedRegs();
181
182   PBQPRAGraph::EdgeId edge = G.findEdge(node1, node2);
183
184   // The edge does not exist. Create one with the appropriate interference
185   // costs.
186   if (edge == G.invalidEdgeId()) {
187     const LiveInterval &ld = LIs.getInterval(Rd);
188     const LiveInterval &la = LIs.getInterval(Ra);
189     bool livesOverlap = ld.overlaps(la);
190
191     PBQPRAGraph::RawMatrix costs(vRdAllowed->size() + 1,
192                                  vRaAllowed->size() + 1, 0);
193     for (unsigned i = 0, ie = vRdAllowed->size(); i != ie; ++i) {
194       unsigned pRd = (*vRdAllowed)[i];
195       for (unsigned j = 0, je = vRaAllowed->size(); j != je; ++j) {
196         unsigned pRa = (*vRaAllowed)[j];
197         if (livesOverlap && TRI->regsOverlap(pRd, pRa))
198           costs[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
199         else
200           costs[i + 1][j + 1] = haveSameParity(pRd, pRa) ? 0.0 : 1.0;
201       }
202     }
203     G.addEdge(node1, node2, std::move(costs));
204     return true;
205   }
206
207   if (G.getEdgeNode1Id(edge) == node2) {
208     std::swap(node1, node2);
209     std::swap(vRdAllowed, vRaAllowed);
210   }
211
212   // Enforce minCost(sameParity(RaClass)) > maxCost(otherParity(RdClass))
213   PBQPRAGraph::RawMatrix costs(G.getEdgeCosts(edge));
214   for (unsigned i = 0, ie = vRdAllowed->size(); i != ie; ++i) {
215     unsigned pRd = (*vRdAllowed)[i];
216
217     // Get the maximum cost (excluding unallocatable reg) for same parity
218     // registers
219     PBQP::PBQPNum sameParityMax = std::numeric_limits<PBQP::PBQPNum>::min();
220     for (unsigned j = 0, je = vRaAllowed->size(); j != je; ++j) {
221       unsigned pRa = (*vRaAllowed)[j];
222       if (haveSameParity(pRd, pRa))
223         if (costs[i + 1][j + 1] !=
224                 std::numeric_limits<PBQP::PBQPNum>::infinity() &&
225             costs[i + 1][j + 1] > sameParityMax)
226           sameParityMax = costs[i + 1][j + 1];
227     }
228
229     // Ensure all registers with a different parity have a higher cost
230     // than sameParityMax
231     for (unsigned j = 0, je = vRaAllowed->size(); j != je; ++j) {
232       unsigned pRa = (*vRaAllowed)[j];
233       if (!haveSameParity(pRd, pRa))
234         if (sameParityMax > costs[i + 1][j + 1])
235           costs[i + 1][j + 1] = sameParityMax + 1.0;
236     }
237   }
238   G.setEdgeCosts(edge, std::move(costs));
239
240   return true;
241 }
242
243 void A57ChainingConstraint::addInterChainConstraint(PBQPRAGraph &G, unsigned Rd,
244                                                  unsigned Ra) {
245   LiveIntervals &LIs = G.getMetadata().LIS;
246
247   // Do some Chain management
248   if (Chains.count(Ra)) {
249     if (Rd != Ra) {
250       DEBUG(dbgs() << "Moving acc chain from " << PrintReg(Ra, TRI) << " to "
251                    << PrintReg(Rd, TRI) << '\n';);
252       Chains.remove(Ra);
253       Chains.insert(Rd);
254     }
255   } else {
256     DEBUG(dbgs() << "Creating new acc chain for " << PrintReg(Rd, TRI)
257                  << '\n';);
258     Chains.insert(Rd);
259   }
260
261   PBQPRAGraph::NodeId node1 = G.getMetadata().getNodeIdForVReg(Rd);
262
263   const LiveInterval &ld = LIs.getInterval(Rd);
264   for (auto r : Chains) {
265     // Skip self
266     if (r == Rd)
267       continue;
268
269     const LiveInterval &lr = LIs.getInterval(r);
270     if (ld.overlaps(lr)) {
271       const PBQPRAGraph::NodeMetadata::AllowedRegVector *vRdAllowed =
272         &G.getNodeMetadata(node1).getAllowedRegs();
273
274       PBQPRAGraph::NodeId node2 = G.getMetadata().getNodeIdForVReg(r);
275       const PBQPRAGraph::NodeMetadata::AllowedRegVector *vRrAllowed =
276         &G.getNodeMetadata(node2).getAllowedRegs();
277
278       PBQPRAGraph::EdgeId edge = G.findEdge(node1, node2);
279       assert(edge != G.invalidEdgeId() &&
280              "PBQP error ! The edge should exist !");
281
282       DEBUG(dbgs() << "Refining constraint !\n";);
283
284       if (G.getEdgeNode1Id(edge) == node2) {
285         std::swap(node1, node2);
286         std::swap(vRdAllowed, vRrAllowed);
287       }
288
289       // Enforce that cost is higher with all other Chains of the same parity
290       PBQP::Matrix costs(G.getEdgeCosts(edge));
291       for (unsigned i = 0, ie = vRdAllowed->size(); i != ie; ++i) {
292         unsigned pRd = (*vRdAllowed)[i];
293
294         // Get the maximum cost (excluding unallocatable reg) for all other
295         // parity registers
296         PBQP::PBQPNum sameParityMax = std::numeric_limits<PBQP::PBQPNum>::min();
297         for (unsigned j = 0, je = vRrAllowed->size(); j != je; ++j) {
298           unsigned pRa = (*vRrAllowed)[j];
299           if (!haveSameParity(pRd, pRa))
300             if (costs[i + 1][j + 1] !=
301                     std::numeric_limits<PBQP::PBQPNum>::infinity() &&
302                 costs[i + 1][j + 1] > sameParityMax)
303               sameParityMax = costs[i + 1][j + 1];
304         }
305
306         // Ensure all registers with same parity have a higher cost
307         // than sameParityMax
308         for (unsigned j = 0, je = vRrAllowed->size(); j != je; ++j) {
309           unsigned pRa = (*vRrAllowed)[j];
310           if (haveSameParity(pRd, pRa))
311             if (sameParityMax > costs[i + 1][j + 1])
312               costs[i + 1][j + 1] = sameParityMax + 1.0;
313         }
314       }
315       G.setEdgeCosts(edge, std::move(costs));
316     }
317   }
318 }
319
320 static bool regJustKilledBefore(const LiveIntervals &LIs, unsigned reg,
321                                 const MachineInstr &MI) {
322   LiveInterval LI = LIs.getInterval(reg);
323   SlotIndex SI = LIs.getInstructionIndex(&MI);
324   return LI.expiredAt(SI);
325 }
326
327 void A57ChainingConstraint::apply(PBQPRAGraph &G) {
328   const MachineFunction &MF = G.getMetadata().MF;
329   LiveIntervals &LIs = G.getMetadata().LIS;
330
331   TRI = MF.getTarget().getSubtargetImpl()->getRegisterInfo();
332   DEBUG(MF.dump());
333
334   for (const auto &MBB: MF) {
335     Chains.clear(); // FIXME: really needed ? Could not work at MF level ?
336
337     for (const auto &MI: MBB) {
338
339       // Forget Chains which have expired
340       for (auto r : Chains) {
341         SmallVector<unsigned, 8> toDel;
342         if(regJustKilledBefore(LIs, r, MI)) {
343           DEBUG(dbgs() << "Killing chain " << PrintReg(r, TRI) << " at ";
344                 MI.print(dbgs()););
345           toDel.push_back(r);
346         }
347
348         while (!toDel.empty()) {
349           Chains.remove(toDel.back());
350           toDel.pop_back();
351         }
352       }
353
354       switch (MI.getOpcode()) {
355       case AArch64::FMSUBSrrr:
356       case AArch64::FMADDSrrr:
357       case AArch64::FNMSUBSrrr:
358       case AArch64::FNMADDSrrr:
359       case AArch64::FMSUBDrrr:
360       case AArch64::FMADDDrrr:
361       case AArch64::FNMSUBDrrr:
362       case AArch64::FNMADDDrrr: {
363         unsigned Rd = MI.getOperand(0).getReg();
364         unsigned Ra = MI.getOperand(3).getReg();
365
366         if (addIntraChainConstraint(G, Rd, Ra))
367           addInterChainConstraint(G, Rd, Ra);
368         break;
369       }
370
371       case AArch64::FMLAv2f32:
372       case AArch64::FMLSv2f32: {
373         unsigned Rd = MI.getOperand(0).getReg();
374         addInterChainConstraint(G, Rd, Rd);
375         break;
376       }
377
378       default:
379         break;
380       }
381     }
382   }
383 }