1//===-- AArch64A57FPLoadBalancing.cpp - Balance FP ops statically on A57---===//
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// For best-case performance on Cortex-A57, we should try to use a balanced
9// mix of odd and even D-registers when performing a critical sequence of
10// independent, non-quadword FP/ASIMD floating-point multiply or
11// multiply-accumulate operations.
12//
13// This pass attempts to detect situations where the register allocation may
14// adversely affect this load balancing and to change the registers used so as
15// to better utilize the CPU.
16//
17// Ideally we'd just take each multiply or multiply-accumulate in turn and
18// allocate it alternating even or odd registers. However, multiply-accumulates
19// are most efficiently performed in the same functional unit as their
20// accumulation operand. Therefore this pass tries to find maximal sequences
21// ("Chains") of multiply-accumulates linked via their accumulation operand,
22// and assign them all the same "color" (oddness/evenness).
23//
24// This optimization affects S-register and D-register floating point
25// multiplies and FMADD/FMAs, as well as vector (floating point only) muls and
26// FMADD/FMA. Q register instructions (and 128-bit vector instructions) are
27// not affected.
28//===----------------------------------------------------------------------===//
29
30#include "AArch64.h"
31#include "AArch64InstrInfo.h"
32#include "AArch64Subtarget.h"
33#include "llvm/ADT/EquivalenceClasses.h"
34#include "llvm/CodeGen/MachineFunction.h"
35#include "llvm/CodeGen/MachineFunctionPass.h"
36#include "llvm/CodeGen/MachineInstr.h"
37#include "llvm/CodeGen/MachineInstrBuilder.h"
38#include "llvm/CodeGen/MachineRegisterInfo.h"
39#include "llvm/CodeGen/RegisterClassInfo.h"
40#include "llvm/CodeGen/RegisterScavenging.h"
41#include "llvm/InitializePasses.h"
42#include "llvm/Support/CommandLine.h"
43#include "llvm/Support/Debug.h"
44#include "llvm/Support/raw_ostream.h"
45using namespace llvm;
46
47#define DEBUG_TYPE "aarch64-a57-fp-load-balancing"
48
49// Enforce the algorithm to use the scavenged register even when the original
50// destination register is the correct color. Used for testing.
51static cl::opt<bool>
52TransformAll("aarch64-a57-fp-load-balancing-force-all",
53 cl::desc("Always modify dest registers regardless of color"),
54 cl::init(Val: false), cl::Hidden);
55
56// Never use the balance information obtained from chains - return a specific
57// color always. Used for testing.
58static cl::opt<unsigned>
59OverrideBalance("aarch64-a57-fp-load-balancing-override",
60 cl::desc("Ignore balance information, always return "
61 "(1: Even, 2: Odd)."),
62 cl::init(Val: 0), cl::Hidden);
63
64//===----------------------------------------------------------------------===//
65// Helper functions
66
67// Is the instruction a type of multiply on 64-bit (or 32-bit) FPRs?
68static bool isMul(MachineInstr *MI) {
69 switch (MI->getOpcode()) {
70 case AArch64::FMULSrr:
71 case AArch64::FNMULSrr:
72 case AArch64::FMULDrr:
73 case AArch64::FNMULDrr:
74 return true;
75 default:
76 return false;
77 }
78}
79
80// Is the instruction a type of FP multiply-accumulate on 64-bit (or 32-bit) FPRs?
81static bool isMla(MachineInstr *MI) {
82 switch (MI->getOpcode()) {
83 case AArch64::FMSUBSrrr:
84 case AArch64::FMADDSrrr:
85 case AArch64::FNMSUBSrrr:
86 case AArch64::FNMADDSrrr:
87 case AArch64::FMSUBDrrr:
88 case AArch64::FMADDDrrr:
89 case AArch64::FNMSUBDrrr:
90 case AArch64::FNMADDDrrr:
91 return true;
92 default:
93 return false;
94 }
95}
96
97//===----------------------------------------------------------------------===//
98
99namespace {
100/// A "color", which is either even or odd. Yes, these aren't really colors
101/// but the algorithm is conceptually doing two-color graph coloring.
102enum class Color { Even, Odd };
103#ifndef NDEBUG
104static const char *ColorNames[2] = { "Even", "Odd" };
105#endif
106
107class Chain;
108
109class AArch64A57FPLoadBalancingImpl {
110public:
111 explicit AArch64A57FPLoadBalancingImpl(RegisterClassInfo *RCI) : RCI(RCI) {}
112
113 bool run(MachineFunction &MF);
114
115private:
116 MachineRegisterInfo *MRI;
117 const TargetRegisterInfo *TRI;
118 RegisterClassInfo *RCI = nullptr;
119
120 bool runOnBasicBlock(MachineBasicBlock &MBB);
121 bool colorChainSet(std::vector<Chain *> GV, MachineBasicBlock &MBB,
122 int &Balance);
123 bool colorChain(Chain *G, Color C, MachineBasicBlock &MBB);
124 int scavengeRegister(Chain *G, Color C, MachineBasicBlock &MBB);
125 void scanInstruction(MachineInstr *MI, unsigned Idx,
126 std::map<unsigned, Chain *> &Active,
127 std::vector<std::unique_ptr<Chain>> &AllChains);
128 void maybeKillChain(MachineOperand &MO, unsigned Idx,
129 std::map<unsigned, Chain *> &RegChains);
130 Color getColor(unsigned Register);
131 Chain *getAndEraseNext(Color PreferredColor, std::vector<Chain *> &L);
132};
133
134class AArch64A57FPLoadBalancingLegacy : public MachineFunctionPass {
135public:
136 static char ID;
137 explicit AArch64A57FPLoadBalancingLegacy() : MachineFunctionPass(ID) {}
138
139 bool runOnMachineFunction(MachineFunction &MF) override;
140
141 MachineFunctionProperties getRequiredProperties() const override {
142 return MachineFunctionProperties().setNoVRegs();
143 }
144
145 StringRef getPassName() const override {
146 return "A57 FP Anti-dependency breaker";
147 }
148
149 void getAnalysisUsage(AnalysisUsage &AU) const override {
150 AU.setPreservesCFG();
151 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
152 MachineFunctionPass::getAnalysisUsage(AU);
153 }
154};
155}
156
157char AArch64A57FPLoadBalancingLegacy::ID = 0;
158
159INITIALIZE_PASS_BEGIN(AArch64A57FPLoadBalancingLegacy, DEBUG_TYPE,
160 "AArch64 A57 FP Load-Balancing", false, false)
161INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
162INITIALIZE_PASS_END(AArch64A57FPLoadBalancingLegacy, DEBUG_TYPE,
163 "AArch64 A57 FP Load-Balancing", false, false)
164
165namespace {
166/// A Chain is a sequence of instructions that are linked together by
167/// an accumulation operand. For example:
168///
169/// fmul def d0, ?
170/// fmla def d1, ?, ?, killed d0
171/// fmla def d2, ?, ?, killed d1
172///
173/// There may be other instructions interleaved in the sequence that
174/// do not belong to the chain. These other instructions must not use
175/// the "chain" register at any point.
176///
177/// We currently only support chains where the "chain" operand is killed
178/// at each link in the chain for simplicity.
179/// A chain has three important instructions - Start, Last and Kill.
180/// * The start instruction is the first instruction in the chain.
181/// * Last is the final instruction in the chain.
182/// * Kill may or may not be defined. If defined, Kill is the instruction
183/// where the outgoing value of the Last instruction is killed.
184/// This information is important as if we know the outgoing value is
185/// killed with no intervening uses, we can safely change its register.
186///
187/// Without a kill instruction, we must assume the outgoing value escapes
188/// beyond our model and either must not change its register or must
189/// create a fixup FMOV to keep the old register value consistent.
190///
191class Chain {
192public:
193 /// The important (marker) instructions.
194 MachineInstr *StartInst, *LastInst, *KillInst;
195 /// The index, from the start of the basic block, that each marker
196 /// appears. These are stored so we can do quick interval tests.
197 unsigned StartInstIdx, LastInstIdx, KillInstIdx;
198 /// All instructions in the chain.
199 std::set<MachineInstr*> Insts;
200 /// True if KillInst cannot be modified. If this is true,
201 /// we cannot change LastInst's outgoing register.
202 /// This will be true for tied values and regmasks.
203 bool KillIsImmutable;
204 /// The "color" of LastInst. This will be the preferred chain color,
205 /// as changing intermediate nodes is easy but changing the last
206 /// instruction can be more tricky.
207 Color LastColor;
208
209 Chain(MachineInstr *MI, unsigned Idx, Color C)
210 : StartInst(MI), LastInst(MI), KillInst(nullptr),
211 StartInstIdx(Idx), LastInstIdx(Idx), KillInstIdx(0),
212 LastColor(C) {
213 Insts.insert(x: MI);
214 }
215
216 /// Add a new instruction into the chain. The instruction's dest operand
217 /// has the given color.
218 void add(MachineInstr *MI, unsigned Idx, Color C) {
219 LastInst = MI;
220 LastInstIdx = Idx;
221 LastColor = C;
222 assert((KillInstIdx == 0 || LastInstIdx < KillInstIdx) &&
223 "Chain: broken invariant. A Chain can only be killed after its last "
224 "def");
225
226 Insts.insert(x: MI);
227 }
228
229 /// Return true if MI is a member of the chain.
230 bool contains(MachineInstr &MI) { return Insts.count(x: &MI) > 0; }
231
232 /// Return the number of instructions in the chain.
233 unsigned size() const {
234 return Insts.size();
235 }
236
237 /// Inform the chain that its last active register (the dest register of
238 /// LastInst) is killed by MI with no intervening uses or defs.
239 void setKill(MachineInstr *MI, unsigned Idx, bool Immutable) {
240 KillInst = MI;
241 KillInstIdx = Idx;
242 KillIsImmutable = Immutable;
243 assert((KillInstIdx == 0 || LastInstIdx < KillInstIdx) &&
244 "Chain: broken invariant. A Chain can only be killed after its last "
245 "def");
246 }
247
248 /// Return the first instruction in the chain.
249 MachineInstr *getStart() const { return StartInst; }
250 /// Return the last instruction in the chain.
251 MachineInstr *getLast() const { return LastInst; }
252 /// Return the "kill" instruction (as set with setKill()) or NULL.
253 MachineInstr *getKill() const { return KillInst; }
254 /// Return an instruction that can be used as an iterator for the end
255 /// of the chain. This is the maximum of KillInst (if set) and LastInst.
256 MachineBasicBlock::iterator end() const {
257 return ++MachineBasicBlock::iterator(KillInst ? KillInst : LastInst);
258 }
259 MachineBasicBlock::iterator begin() const { return getStart(); }
260
261 /// Can the Kill instruction (assuming one exists) be modified?
262 bool isKillImmutable() const { return KillIsImmutable; }
263
264 /// Return the preferred color of this chain.
265 Color getPreferredColor() {
266 if (OverrideBalance != 0)
267 return OverrideBalance == 1 ? Color::Even : Color::Odd;
268 return LastColor;
269 }
270
271 /// Return true if this chain (StartInst..KillInst) overlaps with Other.
272 bool rangeOverlapsWith(const Chain &Other) const {
273 unsigned End = KillInst ? KillInstIdx : LastInstIdx;
274 unsigned OtherEnd = Other.KillInst ?
275 Other.KillInstIdx : Other.LastInstIdx;
276
277 return StartInstIdx <= OtherEnd && Other.StartInstIdx <= End;
278 }
279
280 /// Return true if this chain starts before Other.
281 bool startsBefore(const Chain *Other) const {
282 return StartInstIdx < Other->StartInstIdx;
283 }
284
285 /// Return true if the group will require a fixup MOV at the end.
286 bool requiresFixup() const {
287 return (getKill() && isKillImmutable()) || !getKill();
288 }
289
290 /// Return a simple string representation of the chain.
291 std::string str() const {
292 std::string S;
293 raw_string_ostream OS(S);
294
295 OS << "{";
296 StartInst->print(OS, /* SkipOpers= */IsStandalone: true);
297 OS << " -> ";
298 LastInst->print(OS, /* SkipOpers= */IsStandalone: true);
299 if (KillInst) {
300 OS << " (kill @ ";
301 KillInst->print(OS, /* SkipOpers= */IsStandalone: true);
302 OS << ")";
303 }
304 OS << "}";
305
306 return OS.str();
307 }
308
309};
310
311} // end anonymous namespace
312
313//===----------------------------------------------------------------------===//
314
315bool AArch64A57FPLoadBalancingImpl::run(MachineFunction &MF) {
316 if (!MF.getSubtarget<AArch64Subtarget>().balanceFPOps())
317 return false;
318
319 bool Changed = false;
320 LLVM_DEBUG(dbgs() << "***** AArch64A57FPLoadBalancing *****\n");
321
322 MRI = &MF.getRegInfo();
323 TRI = MF.getRegInfo().getTargetRegisterInfo();
324
325 for (auto &MBB : MF) {
326 Changed |= runOnBasicBlock(MBB);
327 }
328
329 return Changed;
330}
331
332bool AArch64A57FPLoadBalancingLegacy::runOnMachineFunction(
333 MachineFunction &MF) {
334 if (skipFunction(F: MF.getFunction()))
335 return false;
336 RegisterClassInfo *RCI =
337 &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
338 return AArch64A57FPLoadBalancingImpl(RCI).run(MF);
339}
340
341PreservedAnalyses
342AArch64A57FPLoadBalancingPass::run(MachineFunction &MF,
343 MachineFunctionAnalysisManager &MFAM) {
344 RegisterClassInfo *RCI = &MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
345 if (AArch64A57FPLoadBalancingImpl(RCI).run(MF)) {
346 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
347 PA.preserveSet<CFGAnalyses>();
348 return PA;
349 }
350 return PreservedAnalyses::all();
351}
352
353bool AArch64A57FPLoadBalancingImpl::runOnBasicBlock(MachineBasicBlock &MBB) {
354 bool Changed = false;
355 LLVM_DEBUG(dbgs() << "Running on MBB: " << MBB
356 << " - scanning instructions...\n");
357
358 // First, scan the basic block producing a set of chains.
359
360 // The currently "active" chains - chains that can be added to and haven't
361 // been killed yet. This is keyed by register - all chains can only have one
362 // "link" register between each inst in the chain.
363 std::map<unsigned, Chain*> ActiveChains;
364 std::vector<std::unique_ptr<Chain>> AllChains;
365 unsigned Idx = 0;
366 for (auto &MI : MBB)
367 scanInstruction(MI: &MI, Idx: Idx++, Active&: ActiveChains, AllChains);
368
369 LLVM_DEBUG(dbgs() << "Scan complete, " << AllChains.size()
370 << " chains created.\n");
371
372 // Group the chains into disjoint sets based on their liveness range. This is
373 // a poor-man's version of graph coloring. Ideally we'd create an interference
374 // graph and perform full-on graph coloring on that, but;
375 // (a) That's rather heavyweight for only two colors.
376 // (b) We expect multiple disjoint interference regions - in practice the live
377 // range of chains is quite small and they are clustered between loads
378 // and stores.
379 EquivalenceClasses<Chain*> EC;
380 for (auto &I : AllChains)
381 EC.insert(Data: I.get());
382
383 for (auto &I : AllChains)
384 for (auto &J : AllChains)
385 if (I != J && I->rangeOverlapsWith(Other: *J))
386 EC.unionSets(V1: I.get(), V2: J.get());
387 LLVM_DEBUG(dbgs() << "Created " << EC.getNumClasses() << " disjoint sets.\n");
388
389 // Now we assume that every member of an equivalence class interferes
390 // with every other member of that class, and with no members of other classes.
391
392 // Convert the EquivalenceClasses to a simpler set of sets.
393 std::vector<std::vector<Chain*> > V;
394 for (const auto &E : EC) {
395 if (!E->isLeader())
396 continue;
397 std::vector<Chain *> Cs(EC.member_begin(ECV: *E), EC.member_end());
398 if (Cs.empty()) continue;
399 V.push_back(x: std::move(Cs));
400 }
401
402 // Now we have a set of sets, order them by start address so
403 // we can iterate over them sequentially.
404 llvm::sort(C&: V,
405 Comp: [](const std::vector<Chain *> &A, const std::vector<Chain *> &B) {
406 return A.front()->startsBefore(Other: B.front());
407 });
408
409 // As we only have two colors, we can track the global (BB-level) balance of
410 // odds versus evens. We aim to keep this near zero to keep both execution
411 // units fed.
412 // Positive means we're even-heavy, negative we're odd-heavy.
413 //
414 // FIXME: If chains have interdependencies, for example:
415 // mul r0, r1, r2
416 // mul r3, r0, r1
417 // We do not model this and may color each one differently, assuming we'll
418 // get ILP when we obviously can't. This hasn't been seen to be a problem
419 // in practice so far, so we simplify the algorithm by ignoring it.
420 int Parity = 0;
421
422 for (auto &I : V)
423 Changed |= colorChainSet(GV: std::move(I), MBB, Balance&: Parity);
424
425 return Changed;
426}
427
428Chain *AArch64A57FPLoadBalancingImpl::getAndEraseNext(Color PreferredColor,
429 std::vector<Chain *> &L) {
430 if (L.empty())
431 return nullptr;
432
433 // We try and get the best candidate from L to color next, given that our
434 // preferred color is "PreferredColor". L is ordered from larger to smaller
435 // chains. It is beneficial to color the large chains before the small chains,
436 // but if we can't find a chain of the maximum length with the preferred color,
437 // we fuzz the size and look for slightly smaller chains before giving up and
438 // returning a chain that must be recolored.
439
440 // FIXME: Does this need to be configurable?
441 const unsigned SizeFuzz = 1;
442 unsigned MinSize = L.front()->size() - SizeFuzz;
443 for (auto I = L.begin(), E = L.end(); I != E; ++I) {
444 if ((*I)->size() <= MinSize) {
445 // We've gone past the size limit. Return the previous item.
446 Chain *Ch = *--I;
447 L.erase(position: I);
448 return Ch;
449 }
450
451 if ((*I)->getPreferredColor() == PreferredColor) {
452 Chain *Ch = *I;
453 L.erase(position: I);
454 return Ch;
455 }
456 }
457
458 // Bailout case - just return the first item.
459 Chain *Ch = L.front();
460 L.erase(position: L.begin());
461 return Ch;
462}
463
464bool AArch64A57FPLoadBalancingImpl::colorChainSet(std::vector<Chain *> GV,
465 MachineBasicBlock &MBB,
466 int &Parity) {
467 bool Changed = false;
468 LLVM_DEBUG(dbgs() << "colorChainSet(): #sets=" << GV.size() << "\n");
469
470 // Sort by descending size order so that we allocate the most important
471 // sets first.
472 // Tie-break equivalent sizes by sorting chains requiring fixups before
473 // those without fixups. The logic here is that we should look at the
474 // chains that we cannot change before we look at those we can,
475 // so the parity counter is updated and we know what color we should
476 // change them to!
477 // Final tie-break with instruction order so pass output is stable (i.e. not
478 // dependent on malloc'd pointer values).
479 llvm::sort(C&: GV, Comp: [](const Chain *G1, const Chain *G2) {
480 if (G1->size() != G2->size())
481 return G1->size() > G2->size();
482 if (G1->requiresFixup() != G2->requiresFixup())
483 return G1->requiresFixup() > G2->requiresFixup();
484 // Make sure startsBefore() produces a stable final order.
485 assert((G1 == G2 || (G1->startsBefore(G2) ^ G2->startsBefore(G1))) &&
486 "Starts before not total order!");
487 return G1->startsBefore(Other: G2);
488 });
489
490 Color PreferredColor = Parity < 0 ? Color::Even : Color::Odd;
491 while (Chain *G = getAndEraseNext(PreferredColor, L&: GV)) {
492 // Start off by assuming we'll color to our own preferred color.
493 Color C = PreferredColor;
494 if (Parity == 0)
495 // But if we really don't care, use the chain's preferred color.
496 C = G->getPreferredColor();
497
498 LLVM_DEBUG(dbgs() << " - Parity=" << Parity
499 << ", Color=" << ColorNames[(int)C] << "\n");
500
501 // If we'll need a fixup FMOV, don't bother. Testing has shown that this
502 // happens infrequently and when it does it has at least a 50% chance of
503 // slowing code down instead of speeding it up.
504 if (G->requiresFixup() && C != G->getPreferredColor()) {
505 C = G->getPreferredColor();
506 LLVM_DEBUG(dbgs() << " - " << G->str()
507 << " - not worthwhile changing; "
508 "color remains "
509 << ColorNames[(int)C] << "\n");
510 }
511
512 Changed |= colorChain(G, C, MBB);
513
514 Parity += (C == Color::Even) ? G->size() : -G->size();
515 PreferredColor = Parity < 0 ? Color::Even : Color::Odd;
516 }
517
518 return Changed;
519}
520
521int AArch64A57FPLoadBalancingImpl::scavengeRegister(Chain *G, Color C,
522 MachineBasicBlock &MBB) {
523 // Can we find an appropriate register that is available throughout the life
524 // of the chain? Simulate liveness backwards until the end of the chain.
525 LiveRegUnits Units(*TRI);
526 Units.addLiveOuts(MBB);
527 MachineBasicBlock::iterator I = MBB.end();
528 MachineBasicBlock::iterator ChainEnd = G->end();
529 while (I != ChainEnd) {
530 --I;
531 if (!I->isDebugInstr())
532 Units.stepBackward(MI: *I);
533 }
534
535 // Check which register units are alive throughout the chain.
536 MachineBasicBlock::iterator ChainBegin = G->begin();
537 assert(ChainBegin != ChainEnd && "Chain should contain instructions");
538 do {
539 --I;
540 Units.accumulate(MI: *I);
541 } while (I != ChainBegin);
542
543 // Make sure we allocate in-order, to get the cheapest registers first.
544 unsigned RegClassID = ChainBegin->getDesc().operands()[0].RegClass;
545 auto Ord = RCI->getOrder(RC: TRI->getRegClass(i: RegClassID));
546 for (auto Reg : Ord) {
547 if (!Units.available(Reg))
548 continue;
549 if (C == getColor(Register: Reg))
550 return Reg;
551 }
552
553 return -1;
554}
555
556bool AArch64A57FPLoadBalancingImpl::colorChain(Chain *G, Color C,
557 MachineBasicBlock &MBB) {
558 bool Changed = false;
559 LLVM_DEBUG(dbgs() << " - colorChain(" << G->str() << ", "
560 << ColorNames[(int)C] << ")\n");
561
562 // Try and obtain a free register of the right class. Without a register
563 // to play with we cannot continue.
564 int Reg = scavengeRegister(G, C, MBB);
565 if (Reg == -1) {
566 LLVM_DEBUG(dbgs() << "Scavenging (thus coloring) failed!\n");
567 return false;
568 }
569 LLVM_DEBUG(dbgs() << " - Scavenged register: " << printReg(Reg, TRI) << "\n");
570
571 std::map<unsigned, unsigned> Substs;
572 for (MachineInstr &I : *G) {
573 if (!G->contains(MI&: I) && (&I != G->getKill() || G->isKillImmutable()))
574 continue;
575
576 // I is a member of G, or I is a mutable instruction that kills G.
577
578 std::vector<unsigned> ToErase;
579 for (auto &U : I.operands()) {
580 if (U.isReg() && U.isUse() && Substs.find(x: U.getReg()) != Substs.end()) {
581 Register OrigReg = U.getReg();
582 U.setReg(Substs[OrigReg]);
583 if (U.isKill())
584 // Don't erase straight away, because there may be other operands
585 // that also reference this substitution!
586 ToErase.push_back(x: OrigReg);
587 } else if (U.isRegMask()) {
588 for (auto J : Substs) {
589 if (U.clobbersPhysReg(PhysReg: J.first))
590 ToErase.push_back(x: J.first);
591 }
592 }
593 }
594 // Now it's safe to remove the substs identified earlier.
595 for (auto J : ToErase)
596 Substs.erase(x: J);
597
598 // Only change the def if this isn't the last instruction.
599 if (&I != G->getKill()) {
600 MachineOperand &MO = I.getOperand(i: 0);
601
602 bool Change = TransformAll || getColor(Register: MO.getReg()) != C;
603 if (G->requiresFixup() && &I == G->getLast())
604 Change = false;
605
606 if (Change) {
607 Substs[MO.getReg()] = Reg;
608 MO.setReg(Reg);
609
610 Changed = true;
611 }
612 }
613 }
614 assert(Substs.size() == 0 && "No substitutions should be left active!");
615
616 if (G->getKill()) {
617 LLVM_DEBUG(dbgs() << " - Kill instruction seen.\n");
618 } else {
619 // We didn't have a kill instruction, but we didn't seem to need to change
620 // the destination register anyway.
621 LLVM_DEBUG(dbgs() << " - Destination register not changed.\n");
622 }
623 return Changed;
624}
625
626void AArch64A57FPLoadBalancingImpl::scanInstruction(
627 MachineInstr *MI, unsigned Idx, std::map<unsigned, Chain *> &ActiveChains,
628 std::vector<std::unique_ptr<Chain>> &AllChains) {
629 // Inspect "MI", updating ActiveChains and AllChains.
630
631 if (isMul(MI)) {
632
633 for (auto &I : MI->uses())
634 maybeKillChain(MO&: I, Idx, RegChains&: ActiveChains);
635 for (auto &I : MI->defs())
636 maybeKillChain(MO&: I, Idx, RegChains&: ActiveChains);
637
638 // Create a new chain. Multiplies don't require forwarding so can go on any
639 // unit.
640 Register DestReg = MI->getOperand(i: 0).getReg();
641
642 LLVM_DEBUG(dbgs() << "New chain started for register "
643 << printReg(DestReg, TRI) << " at " << *MI);
644
645 auto G = std::make_unique<Chain>(args&: MI, args&: Idx, args: getColor(Register: DestReg));
646 ActiveChains[DestReg] = G.get();
647 AllChains.push_back(x: std::move(G));
648
649 } else if (isMla(MI)) {
650
651 // It is beneficial to keep MLAs on the same functional unit as their
652 // accumulator operand.
653 Register DestReg = MI->getOperand(i: 0).getReg();
654 Register AccumReg = MI->getOperand(i: 3).getReg();
655
656 maybeKillChain(MO&: MI->getOperand(i: 1), Idx, RegChains&: ActiveChains);
657 maybeKillChain(MO&: MI->getOperand(i: 2), Idx, RegChains&: ActiveChains);
658 if (DestReg != AccumReg)
659 maybeKillChain(MO&: MI->getOperand(i: 0), Idx, RegChains&: ActiveChains);
660
661 if (ActiveChains.find(x: AccumReg) != ActiveChains.end()) {
662 LLVM_DEBUG(dbgs() << "Chain found for accumulator register "
663 << printReg(AccumReg, TRI) << " in MI " << *MI);
664
665 // For simplicity we only chain together sequences of MULs/MLAs where the
666 // accumulator register is killed on each instruction. This means we don't
667 // need to track other uses of the registers we want to rewrite.
668 //
669 // FIXME: We could extend to handle the non-kill cases for more coverage.
670 if (MI->getOperand(i: 3).isKill()) {
671 // Add to chain.
672 LLVM_DEBUG(dbgs() << "Instruction was successfully added to chain.\n");
673 ActiveChains[AccumReg]->add(MI, Idx, C: getColor(Register: DestReg));
674 // Handle cases where the destination is not the same as the accumulator.
675 if (DestReg != AccumReg) {
676 ActiveChains[DestReg] = ActiveChains[AccumReg];
677 ActiveChains.erase(x: AccumReg);
678 }
679 return;
680 }
681
682 LLVM_DEBUG(
683 dbgs() << "Cannot add to chain because accumulator operand wasn't "
684 << "marked <kill>!\n");
685 maybeKillChain(MO&: MI->getOperand(i: 3), Idx, RegChains&: ActiveChains);
686 }
687
688 LLVM_DEBUG(dbgs() << "Creating new chain for dest register "
689 << printReg(DestReg, TRI) << "\n");
690 auto G = std::make_unique<Chain>(args&: MI, args&: Idx, args: getColor(Register: DestReg));
691 ActiveChains[DestReg] = G.get();
692 AllChains.push_back(x: std::move(G));
693
694 } else {
695
696 // Non-MUL or MLA instruction. Invalidate any chain in the uses or defs
697 // lists.
698 for (auto &I : MI->uses())
699 maybeKillChain(MO&: I, Idx, RegChains&: ActiveChains);
700 for (auto &I : MI->defs())
701 maybeKillChain(MO&: I, Idx, RegChains&: ActiveChains);
702
703 }
704}
705
706void AArch64A57FPLoadBalancingImpl::maybeKillChain(
707 MachineOperand &MO, unsigned Idx,
708 std::map<unsigned, Chain *> &ActiveChains) {
709 // Given an operand and the set of active chains (keyed by register),
710 // determine if a chain should be ended and remove from ActiveChains.
711 MachineInstr *MI = MO.getParent();
712
713 if (MO.isReg()) {
714
715 // If this is a KILL of a current chain, record it.
716 if (MO.isKill() && ActiveChains.find(x: MO.getReg()) != ActiveChains.end()) {
717 LLVM_DEBUG(dbgs() << "Kill seen for chain " << printReg(MO.getReg(), TRI)
718 << "\n");
719 ActiveChains[MO.getReg()]->setKill(MI, Idx, /*Immutable=*/MO.isTied());
720 }
721 ActiveChains.erase(x: MO.getReg());
722
723 } else if (MO.isRegMask()) {
724
725 for (auto I = ActiveChains.begin(), E = ActiveChains.end();
726 I != E;) {
727 if (MO.clobbersPhysReg(PhysReg: I->first)) {
728 LLVM_DEBUG(dbgs() << "Kill (regmask) seen for chain "
729 << printReg(I->first, TRI) << "\n");
730 I->second->setKill(MI, Idx, /*Immutable=*/true);
731 ActiveChains.erase(position: I++);
732 } else
733 ++I;
734 }
735
736 }
737}
738
739Color AArch64A57FPLoadBalancingImpl::getColor(unsigned Reg) {
740 if ((TRI->getEncodingValue(Reg) % 2) == 0)
741 return Color::Even;
742 else
743 return Color::Odd;
744}
745
746// Factory function used by AArch64TargetMachine to add the pass to the passmanager.
747FunctionPass *llvm::createAArch64A57FPLoadBalancingLegacyPass() {
748 return new AArch64A57FPLoadBalancingLegacy();
749}
750