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