contrib/llvm/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp

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