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