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