lib/Target/ARM64/ARM64CollectLOH.cpp

   1 //===-------------- ARM64CollectLOH.cpp - ARM64 collect LOH pass --*- C++ -*-=//
   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 //
  10 // This file contains a pass that collect the Linker Optimization Hint (LOH).
  11 // This pass should be run at the very end of the compilation flow, just before
  12 // assembly printer.
  13 // To be useful for the linker, the LOH must be printed into the assembly file.
  14 //
  15 // A LOH describes a sequence of instructions that may be optimized by the
  16 // linker.
  17 // This same sequence cannot be optimized by the compiler because some of
  18 // the information will be known at link time.
  19 // For instance, consider the following sequence:
  20 //     L1: adrp xA, sym@PAGE
  21 //     L2: add xB, xA, sym@PAGEOFF
  22 //     L3: ldr xC, [xB, #imm]
  23 // This sequence can be turned into:
  24 // A literal load if sym@PAGE + sym@PAGEOFF + #imm - address(L3) is < 1MB:
  25 //     L3: ldr xC, sym+#imm
  26 // It may also be turned into either the following more efficient
  27 // code sequences:
  28 // - If sym@PAGEOFF + #imm fits the encoding space of L3.
  29 //     L1: adrp xA, sym@PAGE
  30 //     L3: ldr xC, [xB, sym@PAGEOFF + #imm]
  31 // - If sym@PAGE + sym@PAGEOFF - address(L1) < 1MB:
  32 //     L1: adr xA, sym
  33 //     L3: ldr xC, [xB, #imm]
  34 //
  35 // To be valid a LOH must meet all the requirements needed by all the related
  36 // possible linker transformations.
  37 // For instance, using the running example, the constraints to emit
  38 // ".loh AdrpAddLdr" are:
  39 // - L1, L2, and L3 instructions are of the expected type, i.e.,
  40 //   respectively ADRP, ADD (immediate), and LD.
  41 // - The result of L1 is used only by L2.
  42 // - The register argument (xA) used in the ADD instruction is defined
  43 //   only by L1.
  44 // - The result of L2 is used only by L3.
  45 // - The base address (xB) in L3 is defined only L2.
  46 // - The ADRP in L1 and the ADD in L2 must reference the same symbol using
  47 //   @PAGE/@PAGEOFF with no additional constants
  48 //
  49 // Currently supported LOHs are:
  50 // * So called non-ADRP-related:
  51 //   - .loh AdrpAddLdr L1, L2, L3:
  52 //     L1: adrp xA, sym@PAGE
  53 //     L2: add xB, xA, sym@PAGEOFF
  54 //     L3: ldr xC, [xB, #imm]
  55 //   - .loh AdrpLdrGotLdr L1, L2, L3:
  56 //     L1: adrp xA, sym@GOTPAGE
  57 //     L2: ldr xB, [xA, sym@GOTPAGEOFF]
  58 //     L3: ldr xC, [xB, #imm]
  59 //   - .loh AdrpLdr L1, L3:
  60 //     L1: adrp xA, sym@PAGE
  61 //     L3: ldr xC, [xA, sym@PAGEOFF]
  62 //   - .loh AdrpAddStr L1, L2, L3:
  63 //     L1: adrp xA, sym@PAGE
  64 //     L2: add xB, xA, sym@PAGEOFF
  65 //     L3: str xC, [xB, #imm]
  66 //   - .loh AdrpLdrGotStr L1, L2, L3:
  67 //     L1: adrp xA, sym@GOTPAGE
  68 //     L2: ldr xB, [xA, sym@GOTPAGEOFF]
  69 //     L3: str xC, [xB, #imm]
  70 //   - .loh AdrpAdd L1, L2:
  71 //     L1: adrp xA, sym@PAGE
  72 //     L2: add xB, xA, sym@PAGEOFF
  73 //   For all these LOHs, L1, L2, L3 form a simple chain:
  74 //   L1 result is used only by L2 and L2 result by L3.
  75 //   L3 LOH-related argument is defined only by L2 and L2 LOH-related argument
  76 //   by L1.
  77 // All these LOHs aim at using more efficient load/store patterns by folding
  78 // some instructions used to compute the address directly into the load/store.
  79 //
  80 // * So called ADRP-related:
  81 //  - .loh AdrpAdrp L2, L1:
  82 //    L2: ADRP xA, sym1@PAGE
  83 //    L1: ADRP xA, sym2@PAGE
  84 //    L2 dominates L1 and xA is not redifined between L2 and L1
  85 // This LOH aims at getting rid of redundant ADRP instructions.
  86 //
  87 // The overall design for emitting the LOHs is:
  88 // 1. ARM64CollectLOH (this pass) records the LOHs in the ARM64FunctionInfo.
  89 // 2. ARM64AsmPrinter reads the LOHs from ARM64FunctionInfo and it:
  90 //     1. Associates them a label.
  91 //     2. Emits them in a MCStreamer (EmitLOHDirective).
  92 //         - The MCMachOStreamer records them into the MCAssembler.
  93 //         - The MCAsmStreamer prints them.
  94 //         - Other MCStreamers ignore them.
  95 //     3. Closes the MCStreamer:
  96 //         - The MachObjectWriter gets them from the MCAssembler and writes
  97 //           them in the object file.
  98 //         - Other ObjectWriters ignore them.
  99 //
 100 // More information are available in the design document attached to
 101 // rdar://11956674
 102 //===----------------------------------------------------------------------===//
 103
 104 #define DEBUG_TYPE "arm64-collect-loh"
 105 #include "ARM64.h"
 106 #include "ARM64InstrInfo.h"
 107 #include "ARM64MachineFunctionInfo.h"
 108 #include "MCTargetDesc/ARM64AddressingModes.h"
 109 #include "llvm/ADT/BitVector.h"
 110 #include "llvm/ADT/DenseMap.h"
 111 #include "llvm/ADT/MapVector.h"
 112 #include "llvm/ADT/SetVector.h"
 113 #include "llvm/ADT/SmallVector.h"
 114 #include "llvm/CodeGen/MachineBasicBlock.h"
 115 #include "llvm/CodeGen/MachineDominators.h"
 116 #include "llvm/CodeGen/MachineFunctionPass.h"
 117 #include "llvm/CodeGen/MachineInstr.h"
 118 #include "llvm/CodeGen/MachineInstrBuilder.h"
 119 #include "llvm/Target/TargetInstrInfo.h"
 120 #include "llvm/Target/TargetMachine.h"
 121 #include "llvm/Target/TargetRegisterInfo.h"
 122 #include "llvm/Support/CommandLine.h"
 123 #include "llvm/Support/Debug.h"
 124 #include "llvm/Support/ErrorHandling.h"
 125 #include "llvm/Support/raw_ostream.h"
 126 #include "llvm/ADT/Statistic.h"
 127 using namespace llvm;
 128
 129 static cl::opt<bool>
 130 PreCollectRegister("arm64-collect-loh-pre-collect-register", cl::Hidden,
 131                    cl::desc("Restrict analysis to registers invovled"
 132                             " in LOHs"),
 133                    cl::init(true));
 134
 135 static cl::opt<bool>
 136 BasicBlockScopeOnly("arm64-collect-loh-bb-only", cl::Hidden,
 137                     cl::desc("Restrict analysis at basic block scope"),
 138                     cl::init(true));
 139
 140 STATISTIC(NumADRPSimpleCandidate,
 141           "Number of simplifiable ADRP dominate by another");
 142 STATISTIC(NumADRPComplexCandidate2,
 143           "Number of simplifiable ADRP reachable by 2 defs");
 144 STATISTIC(NumADRPComplexCandidate3,
 145           "Number of simplifiable ADRP reachable by 3 defs");
 146 STATISTIC(NumADRPComplexCandidateOther,
 147           "Number of simplifiable ADRP reachable by 4 or more defs");
 148 STATISTIC(NumADDToSTRWithImm,
 149           "Number of simplifiable STR with imm reachable by ADD");
 150 STATISTIC(NumLDRToSTRWithImm,
 151           "Number of simplifiable STR with imm reachable by LDR");
 152 STATISTIC(NumADDToSTR, "Number of simplifiable STR reachable by ADD");
 153 STATISTIC(NumLDRToSTR, "Number of simplifiable STR reachable by LDR");
 154 STATISTIC(NumADDToLDRWithImm,
 155           "Number of simplifiable LDR with imm reachable by ADD");
 156 STATISTIC(NumLDRToLDRWithImm,
 157           "Number of simplifiable LDR with imm reachable by LDR");
 158 STATISTIC(NumADDToLDR, "Number of simplifiable LDR reachable by ADD");
 159 STATISTIC(NumLDRToLDR, "Number of simplifiable LDR reachable by LDR");
 160 STATISTIC(NumADRPToLDR, "Number of simplifiable LDR reachable by ADRP");
 161 STATISTIC(NumCplxLvl1, "Number of complex case of level 1");
 162 STATISTIC(NumTooCplxLvl1, "Number of too complex case of level 1");
 163 STATISTIC(NumCplxLvl2, "Number of complex case of level 2");
 164 STATISTIC(NumTooCplxLvl2, "Number of too complex case of level 2");
 165 STATISTIC(NumADRSimpleCandidate, "Number of simplifiable ADRP + ADD");
 166 STATISTIC(NumADRComplexCandidate, "Number of too complex ADRP + ADD");
 167
 168 namespace llvm {
 169 void initializeARM64CollectLOHPass(PassRegistry &);
 170 }
 171
 172 namespace {
 173 struct ARM64CollectLOH : public MachineFunctionPass {
 174   static char ID;
 175   ARM64CollectLOH() : MachineFunctionPass(ID) {
 176     initializeARM64CollectLOHPass(*PassRegistry::getPassRegistry());
 177   }
 178
 179   virtual bool runOnMachineFunction(MachineFunction &Fn);
 180
 181   virtual const char *getPassName() const {
 182     return "ARM64 Collect Linker Optimization Hint (LOH)";
 183   }
 184
 185   void getAnalysisUsage(AnalysisUsage &AU) const {
 186     AU.setPreservesAll();
 187     MachineFunctionPass::getAnalysisUsage(AU);
 188     AU.addRequired<MachineDominatorTree>();
 189   }
 190
 191 private:
 192 };
 193
 194 /// A set of MachineInstruction.
 195 typedef SetVector<const MachineInstr *> SetOfMachineInstr;
 196 /// Map a basic block to a set of instructions per register.
 197 /// This is used to represent the exposed uses of a basic block
 198 /// per register.
 199 typedef MapVector<const MachineBasicBlock *, SetOfMachineInstr *>
 200 BlockToSetOfInstrsPerColor;
 201 /// Map a basic block to an instruction per register.
 202 /// This is used to represent the live-out definitions of a basic block
 203 /// per register.
 204 typedef MapVector<const MachineBasicBlock *, const MachineInstr **>
 205 BlockToInstrPerColor;
 206 /// Map an instruction to a set of instructions. Used to represent the
 207 /// mapping def to reachable uses or use to definitions.
 208 typedef MapVector<const MachineInstr *, SetOfMachineInstr> InstrToInstrs;
 209 /// Map a basic block to a BitVector.
 210 /// This is used to record the kill registers per basic block.
 211 typedef MapVector<const MachineBasicBlock *, BitVector> BlockToRegSet;
 212
 213 /// Map a register to a dense id.
 214 typedef DenseMap<unsigned, unsigned> MapRegToId;
 215 /// Map a dense id to a register. Used for debug purposes.
 216 typedef SmallVector<unsigned, 32> MapIdToReg;
 217 } // end anonymous namespace.
 218
 219 char ARM64CollectLOH::ID = 0;
 220
 221 INITIALIZE_PASS_BEGIN(ARM64CollectLOH, "arm64-collect-loh",
 222                       "ARM64 Collect Linker Optimization Hint (LOH)", false,
 223                       false)
 224 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 225 INITIALIZE_PASS_END(ARM64CollectLOH, "arm64-collect-loh",
 226                     "ARM64 Collect Linker Optimization Hint (LOH)", false,
 227                     false)
 228
 229 /// Given a couple (MBB, reg) get the corresponding set of instruction from
 230 /// the given "sets".
 231 /// If this couple does not reference any set, an empty set is added to "sets"
 232 /// for this couple and returned.
 233 /// \param nbRegs is used internally allocate some memory. It must be consistent
 234 /// with the way sets is used.
 235 static SetOfMachineInstr &getSet(BlockToSetOfInstrsPerColor &sets,
 236                                  const MachineBasicBlock *MBB, unsigned reg,
 237                                  unsigned nbRegs) {
 238   SetOfMachineInstr *result;
 239   BlockToSetOfInstrsPerColor::iterator it = sets.find(MBB);
 240   if (it != sets.end()) {
 241     result = it->second;
 242   } else {
 243     result = sets[MBB] = new SetOfMachineInstr[nbRegs];
 244   }
 245
 246   return result[reg];
 247 }
 248
 249 /// Given a couple (reg, MI) get the corresponding set of instructions from the
 250 /// the given "sets".
 251 /// This is used to get the uses record in sets of a definition identified by
 252 /// MI and reg, i.e., MI defines reg.
 253 /// If the couple does not reference anything, an empty set is added to
 254 /// "sets[reg]".
 255 /// \pre set[reg] is valid.
 256 static SetOfMachineInstr &getUses(InstrToInstrs *sets, unsigned reg,
 257                                   const MachineInstr *MI) {
 258   return sets[reg][MI];
 259 }
 260
 261 /// Same as getUses but does not modify the input map: sets.
 262 /// \return NULL if the couple (reg, MI) is not in sets.
 263 static const SetOfMachineInstr *getUses(const InstrToInstrs *sets, unsigned reg,
 264                                         const MachineInstr *MI) {
 265   InstrToInstrs::const_iterator Res = sets[reg].find(MI);
 266   if (Res != sets[reg].end())
 267     return &(Res->second);
 268   return NULL;
 269 }
 270
 271 /// Initialize the reaching definition algorithm:
 272 /// For each basic block BB in MF, record:
 273 /// - its kill set.
 274 /// - its reachable uses (uses that are exposed to BB's predecessors).
 275 /// - its the generated definitions.
 276 /// \param DummyOp if not NULL, specifies a Dummy Operation to be added to
 277 /// the list of uses of exposed defintions.
 278 /// \param ADRPMode specifies to only consider ADRP instructions for generated
 279 /// definition. It also consider definitions of ADRP instructions as uses and
 280 /// ignore other uses. The ADRPMode is used to collect the information for LHO
 281 /// that involve ADRP operation only.
 282 static void initReachingDef(MachineFunction *MF,
 283                             InstrToInstrs *ColorOpToReachedUses,
 284                             BlockToInstrPerColor &Gen, BlockToRegSet &Kill,
 285                             BlockToSetOfInstrsPerColor &ReachableUses,
 286                             const MapRegToId &RegToId,
 287                             const MachineInstr *DummyOp, bool ADRPMode) {
 288   const TargetMachine &TM = MF->getTarget();
 289   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
 290
 291   unsigned NbReg = RegToId.size();
 292
 293   for (MachineFunction::const_iterator IMBB = MF->begin(), IMBBEnd = MF->end();
 294        IMBB != IMBBEnd; ++IMBB) {
 295     const MachineBasicBlock *MBB = &(*IMBB);
 296     const MachineInstr **&BBGen = Gen[MBB];
 297     BBGen = new const MachineInstr *[NbReg];
 298     memset(BBGen, 0, sizeof(const MachineInstr *) * NbReg);
 299
 300     BitVector &BBKillSet = Kill[MBB];
 301     BBKillSet.resize(NbReg);
 302     for (MachineBasicBlock::const_iterator II = MBB->begin(), IEnd = MBB->end();
 303          II != IEnd; ++II) {
 304       bool IsADRP = II->getOpcode() == ARM64::ADRP;
 305
 306       // Process uses first.
 307       if (IsADRP || !ADRPMode)
 308         for (MachineInstr::const_mop_iterator IO = II->operands_begin(),
 309                                               IOEnd = II->operands_end();
 310              IO != IOEnd; ++IO) {
 311           // Treat ADRP def as use, as the goal of the analysis is to find
 312           // ADRP defs reached by other ADRP defs.
 313           if (!IO->isReg() || (!ADRPMode && !IO->isUse()) ||
 314               (ADRPMode && (!IsADRP || !IO->isDef())))
 315             continue;
 316           unsigned CurReg = IO->getReg();
 317           MapRegToId::const_iterator ItCurRegId = RegToId.find(CurReg);
 318           if (ItCurRegId == RegToId.end())
 319             continue;
 320           CurReg = ItCurRegId->second;
 321
 322           // if CurReg has not been defined, this use is reachable.
 323           if (!BBGen[CurReg] && !BBKillSet.test(CurReg))
 324             getSet(ReachableUses, MBB, CurReg, NbReg).insert(&(*II));
 325           // current basic block definition for this color, if any, is in Gen.
 326           if (BBGen[CurReg])
 327             getUses(ColorOpToReachedUses, CurReg, BBGen[CurReg]).insert(&(*II));
 328         }
 329
 330       // Process clobbers.
 331       for (MachineInstr::const_mop_iterator IO = II->operands_begin(),
 332                                             IOEnd = II->operands_end();
 333            IO != IOEnd; ++IO) {
 334         if (!IO->isRegMask())
 335           continue;
 336         // Clobbers kill the related colors.
 337         const uint32_t *PreservedRegs = IO->getRegMask();
 338
 339         // Set generated regs.
 340         for (MapRegToId::const_iterator ItRegId = RegToId.begin(),
 341                                         EndIt = RegToId.end();
 342              ItRegId != EndIt; ++ItRegId) {
 343           unsigned Reg = ItRegId->second;
 344           // Use the global register ID when querying APIs external to this
 345           // pass.
 346           if (MachineOperand::clobbersPhysReg(PreservedRegs, ItRegId->first)) {
 347             // Do not register clobbered definition for no ADRP.
 348             // This definition is not used anyway (otherwise register
 349             // allocation is wrong).
 350             BBGen[Reg] = ADRPMode ? II : NULL;
 351             BBKillSet.set(Reg);
 352           }
 353         }
 354       }
 355
 356       // Process defs
 357       for (MachineInstr::const_mop_iterator IO = II->operands_begin(),
 358                                             IOEnd = II->operands_end();
 359            IO != IOEnd; ++IO) {
 360         if (!IO->isReg() || !IO->isDef())
 361           continue;
 362         unsigned CurReg = IO->getReg();
 363         MapRegToId::const_iterator ItCurRegId = RegToId.find(CurReg);
 364         if (ItCurRegId == RegToId.end())
 365           continue;
 366
 367         for (MCRegAliasIterator AI(CurReg, TRI, true); AI.isValid(); ++AI) {
 368           MapRegToId::const_iterator ItRegId = RegToId.find(*AI);
 369           assert(ItRegId != RegToId.end() &&
 370                  "Sub-register of an "
 371                  "involved register, not recorded as involved!");
 372           BBKillSet.set(ItRegId->second);
 373           BBGen[ItRegId->second] = &(*II);
 374         }
 375         BBGen[ItCurRegId->second] = &(*II);
 376       }
 377     }
 378
 379     // If we restrict our analysis to basic block scope, conservatively add a
 380     // dummy
 381     // use for each generated value.
 382     if (!ADRPMode && DummyOp && !MBB->succ_empty())
 383       for (unsigned CurReg = 0; CurReg < NbReg; ++CurReg)
 384         if (BBGen[CurReg])
 385           getUses(ColorOpToReachedUses, CurReg, BBGen[CurReg]).insert(DummyOp);
 386   }
 387 }
 388
 389 /// Reaching def core algorithm:
 390 /// while an Out has changed
 391 ///    for each bb
 392 ///       for each color
 393 ///           In[bb][color] = U Out[bb.predecessors][color]
 394 ///           insert reachableUses[bb][color] in each in[bb][color]
 395 ///                 op.reachedUses
 396 ///
 397 ///           Out[bb] = Gen[bb] U (In[bb] - Kill[bb])
 398 static void reachingDefAlgorithm(MachineFunction *MF,
 399                                  InstrToInstrs *ColorOpToReachedUses,
 400                                  BlockToSetOfInstrsPerColor &In,
 401                                  BlockToSetOfInstrsPerColor &Out,
 402                                  BlockToInstrPerColor &Gen, BlockToRegSet &Kill,
 403                                  BlockToSetOfInstrsPerColor &ReachableUses,
 404                                  unsigned NbReg) {
 405   bool HasChanged;
 406   do {
 407     HasChanged = false;
 408     for (MachineFunction::const_iterator IMBB = MF->begin(),
 409                                          IMBBEnd = MF->end();
 410          IMBB != IMBBEnd; ++IMBB) {
 411       const MachineBasicBlock *MBB = &(*IMBB);
 412       unsigned CurReg;
 413       for (CurReg = 0; CurReg < NbReg; ++CurReg) {
 414         SetOfMachineInstr &BBInSet = getSet(In, MBB, CurReg, NbReg);
 415         SetOfMachineInstr &BBReachableUses =
 416             getSet(ReachableUses, MBB, CurReg, NbReg);
 417         SetOfMachineInstr &BBOutSet = getSet(Out, MBB, CurReg, NbReg);
 418         unsigned Size = BBOutSet.size();
 419         //   In[bb][color] = U Out[bb.predecessors][color]
 420         for (MachineBasicBlock::const_pred_iterator
 421                  PredMBB = MBB->pred_begin(),
 422                  EndPredMBB = MBB->pred_end();
 423              PredMBB != EndPredMBB; ++PredMBB) {
 424           SetOfMachineInstr &PredOutSet = getSet(Out, *PredMBB, CurReg, NbReg);
 425           BBInSet.insert(PredOutSet.begin(), PredOutSet.end());
 426         }
 427         //   insert reachableUses[bb][color] in each in[bb][color] op.reachedses
 428         for (SetOfMachineInstr::const_iterator InstrIt = BBInSet.begin(),
 429                                                EndInstrIt = BBInSet.end();
 430              InstrIt != EndInstrIt; ++InstrIt) {
 431           SetOfMachineInstr &OpReachedUses =
 432               getUses(ColorOpToReachedUses, CurReg, *InstrIt);
 433           OpReachedUses.insert(BBReachableUses.begin(), BBReachableUses.end());
 434         }
 435         //           Out[bb] = Gen[bb] U (In[bb] - Kill[bb])
 436         if (!Kill[MBB].test(CurReg))
 437           BBOutSet.insert(BBInSet.begin(), BBInSet.end());
 438         if (Gen[MBB][CurReg])
 439           BBOutSet.insert(Gen[MBB][CurReg]);
 440         HasChanged |= BBOutSet.size() != Size;
 441       }
 442     }
 443   } while (HasChanged);
 444 }
 445
 446 /// Release all memory dynamically allocated during the reaching
 447 /// definition algorithm.
 448 static void finitReachingDef(BlockToSetOfInstrsPerColor &In,
 449                              BlockToSetOfInstrsPerColor &Out,
 450                              BlockToInstrPerColor &Gen,
 451                              BlockToSetOfInstrsPerColor &ReachableUses) {
 452   for (BlockToSetOfInstrsPerColor::const_iterator IT = Out.begin(),
 453                                                   End = Out.end();
 454        IT != End; ++IT)
 455     delete[] IT->second;
 456   for (BlockToSetOfInstrsPerColor::const_iterator IT = In.begin(),
 457                                                   End = In.end();
 458        IT != End; ++IT)
 459     delete[] IT->second;
 460   for (BlockToSetOfInstrsPerColor::const_iterator IT = ReachableUses.begin(),
 461                                                   End = ReachableUses.end();
 462        IT != End; ++IT)
 463     delete[] IT->second;
 464   for (BlockToInstrPerColor::const_iterator IT = Gen.begin(), End = Gen.end();
 465        IT != End; ++IT)
 466     delete[] IT->second;
 467 }
 468
 469 /// Reaching definiton algorithm.
 470 /// \param MF function on which the algorithm will operate.
 471 /// \param[out] ColorOpToReachedUses will contain the result of the reaching
 472 /// def algorithm.
 473 /// \param ADRPMode specify whether the reaching def algorithm should be tuned
 474 /// for ADRP optimization. \see initReachingDef for more details.
 475 /// \param DummyOp if not NULL, the algorithm will work at
 476 /// basic block scope and will set for every exposed defintion a use to
 477 /// @p DummyOp.
 478 /// \pre ColorOpToReachedUses is an array of at least number of registers of
 479 /// InstrToInstrs.
 480 static void reachingDef(MachineFunction *MF,
 481                         InstrToInstrs *ColorOpToReachedUses,
 482                         const MapRegToId &RegToId, bool ADRPMode = false,
 483                         const MachineInstr *DummyOp = NULL) {
 484   // structures:
 485   // For each basic block.
 486   // Out: a set per color of definitions that reach the
 487   //      out boundary of this block.
 488   // In: Same as Out but for in boundary.
 489   // Gen: generated color in this block (one operation per color).
 490   // Kill: register set of killed color in this block.
 491   // ReachableUses: a set per color of uses (operation) reachable
 492   //                for "In" definitions.
 493   BlockToSetOfInstrsPerColor Out, In, ReachableUses;
 494   BlockToInstrPerColor Gen;
 495   BlockToRegSet Kill;
 496
 497   // Initialize Gen, kill and reachableUses.
 498   initReachingDef(MF, ColorOpToReachedUses, Gen, Kill, ReachableUses, RegToId,
 499                   DummyOp, ADRPMode);
 500
 501   // Algo.
 502   if (!DummyOp)
 503     reachingDefAlgorithm(MF, ColorOpToReachedUses, In, Out, Gen, Kill,
 504                          ReachableUses, RegToId.size());
 505
 506   // finit.
 507   finitReachingDef(In, Out, Gen, ReachableUses);
 508 }
 509
 510 #ifndef NDEBUG
 511 /// print the result of the reaching definition algorithm.
 512 static void printReachingDef(const InstrToInstrs *ColorOpToReachedUses,
 513                              unsigned NbReg, const TargetRegisterInfo *TRI,
 514                              const MapIdToReg &IdToReg) {
 515   unsigned CurReg;
 516   for (CurReg = 0; CurReg < NbReg; ++CurReg) {
 517     if (ColorOpToReachedUses[CurReg].empty())
 518       continue;
 519     DEBUG(dbgs() << "*** Reg " << PrintReg(IdToReg[CurReg], TRI) << " ***\n");
 520
 521     InstrToInstrs::const_iterator DefsIt = ColorOpToReachedUses[CurReg].begin();
 522     InstrToInstrs::const_iterator DefsItEnd =
 523         ColorOpToReachedUses[CurReg].end();
 524     for (; DefsIt != DefsItEnd; ++DefsIt) {
 525       DEBUG(dbgs() << "Def:\n");
 526       DEBUG(DefsIt->first->print(dbgs()));
 527       DEBUG(dbgs() << "Reachable uses:\n");
 528       for (SetOfMachineInstr::const_iterator UsesIt = DefsIt->second.begin(),
 529                                              UsesItEnd = DefsIt->second.end();
 530            UsesIt != UsesItEnd; ++UsesIt) {
 531         DEBUG((*UsesIt)->print(dbgs()));
 532       }
 533     }
 534   }
 535 }
 536 #endif // NDEBUG
 537
 538 /// Answer the following question: Can Def be one of the definition
 539 /// involved in a part of a LOH?
 540 static bool canDefBePartOfLOH(const MachineInstr *Def) {
 541   unsigned Opc = Def->getOpcode();
 542   // Accept ADRP, ADDLow and LOADGot.
 543   switch (Opc) {
 544   default:
 545     return false;
 546   case ARM64::ADRP:
 547     return true;
 548   case ARM64::ADDXri:
 549     // Check immediate to see if the immediate is an address.
 550     switch (Def->getOperand(2).getType()) {
 551     default:
 552       return false;
 553     case MachineOperand::MO_GlobalAddress:
 554     case MachineOperand::MO_JumpTableIndex:
 555     case MachineOperand::MO_ConstantPoolIndex:
 556     case MachineOperand::MO_BlockAddress:
 557       return true;
 558     }
 559   case ARM64::LDRXui:
 560     // Check immediate to see if the immediate is an address.
 561     switch (Def->getOperand(2).getType()) {
 562     default:
 563       return false;
 564     case MachineOperand::MO_GlobalAddress:
 565       return true;
 566     }
 567   }
 568   // Unreachable.
 569   return false;
 570 }
 571
 572 /// Check whether the given instruction can the end of a LOH chain involving a
 573 /// store.
 574 static bool isCandidateStore(const MachineInstr *Instr) {
 575   switch (Instr->getOpcode()) {
 576   default:
 577     return false;
 578   case ARM64::STRBui:
 579   case ARM64::STRHui:
 580   case ARM64::STRWui:
 581   case ARM64::STRXui:
 582   case ARM64::STRSui:
 583   case ARM64::STRDui:
 584   case ARM64::STRQui:
 585     // In case we have str xA, [xA, #imm], this is two different uses
 586     // of xA and we cannot fold, otherwise the xA stored may be wrong,
 587     // even if #imm == 0.
 588     if (Instr->getOperand(0).getReg() != Instr->getOperand(1).getReg())
 589       return true;
 590   }
 591   return false;
 592 }
 593
 594 /// Given the result of a reaching defintion algorithm in ColorOpToReachedUses,
 595 /// Build the Use to Defs information and filter out obvious non-LOH candidates.
 596 /// In ADRPMode, non-LOH candidates are "uses" with non-ADRP definitions.
 597 /// In non-ADRPMode, non-LOH candidates are "uses" with several definition,
 598 /// i.e., no simple chain.
 599 /// \param ADRPMode -- \see initReachingDef.
 600 static void reachedUsesToDefs(InstrToInstrs &UseToReachingDefs,
 601                               const InstrToInstrs *ColorOpToReachedUses,
 602                               const MapRegToId &RegToId,
 603                               bool ADRPMode = false) {
 604
 605   SetOfMachineInstr NotCandidate;
 606   unsigned NbReg = RegToId.size();
 607   MapRegToId::const_iterator EndIt = RegToId.end();
 608   for (unsigned CurReg = 0; CurReg < NbReg; ++CurReg) {
 609     // If this color is never defined, continue.
 610     if (ColorOpToReachedUses[CurReg].empty())
 611       continue;
 612
 613     InstrToInstrs::const_iterator DefsIt = ColorOpToReachedUses[CurReg].begin();
 614     InstrToInstrs::const_iterator DefsItEnd =
 615         ColorOpToReachedUses[CurReg].end();
 616     for (; DefsIt != DefsItEnd; ++DefsIt) {
 617       for (SetOfMachineInstr::const_iterator UsesIt = DefsIt->second.begin(),
 618                                              UsesItEnd = DefsIt->second.end();
 619            UsesIt != UsesItEnd; ++UsesIt) {
 620         const MachineInstr *Def = DefsIt->first;
 621         MapRegToId::const_iterator It;
 622         // if all the reaching defs are not adrp, this use will not be
 623         // simplifiable.
 624         if ((ADRPMode && Def->getOpcode() != ARM64::ADRP) ||
 625             (!ADRPMode && !canDefBePartOfLOH(Def)) ||
 626             (!ADRPMode && isCandidateStore(*UsesIt) &&
 627              // store are LOH candidate iff the end of the chain is used as
 628              // base.
 629              ((It = RegToId.find((*UsesIt)->getOperand(1).getReg())) == EndIt ||
 630               It->second != CurReg))) {
 631           NotCandidate.insert(*UsesIt);
 632           continue;
 633         }
 634         // Do not consider self reaching as a simplifiable case for ADRP.
 635         if (!ADRPMode || *UsesIt != DefsIt->first) {
 636           UseToReachingDefs[*UsesIt].insert(DefsIt->first);
 637           // If UsesIt has several reaching definitions, it is not
 638           // candidate for simplificaton in non-ADRPMode.
 639           if (!ADRPMode && UseToReachingDefs[*UsesIt].size() > 1)
 640             NotCandidate.insert(*UsesIt);
 641         }
 642       }
 643     }
 644   }
 645   for (SetOfMachineInstr::const_iterator NotCandidateIt = NotCandidate.begin(),
 646                                          NotCandidateItEnd = NotCandidate.end();
 647        NotCandidateIt != NotCandidateItEnd; ++NotCandidateIt) {
 648     DEBUG(dbgs() << "Too many reaching defs: " << **NotCandidateIt << "\n");
 649     // It would have been better if we could just remove the entry
 650     // from the map.  Because of that, we have to filter the garbage
 651     // (second.empty) in the subsequence analysis.
 652     UseToReachingDefs[*NotCandidateIt].clear();
 653   }
 654 }
 655
 656 /// Based on the use to defs information (in ADRPMode), compute the
 657 /// opportunities of LOH ADRP-related.
 658 static void computeADRP(const InstrToInstrs &UseToDefs,
 659                         ARM64FunctionInfo &ARM64FI,
 660                         const MachineDominatorTree *MDT) {
 661   DEBUG(dbgs() << "*** Compute LOH for ADRP\n");
 662   for (InstrToInstrs::const_iterator UseIt = UseToDefs.begin(),
 663                                      EndUseIt = UseToDefs.end();
 664        UseIt != EndUseIt; ++UseIt) {
 665     unsigned Size = UseIt->second.size();
 666     if (Size == 0)
 667       continue;
 668     if (Size == 1) {
 669       const MachineInstr *L2 = *UseIt->second.begin();
 670       const MachineInstr *L1 = UseIt->first;
 671       if (!MDT->dominates(L2, L1)) {
 672         DEBUG(dbgs() << "Dominance check failed:\n" << *L2 << '\n' << *L1
 673                      << '\n');
 674         continue;
 675       }
 676       DEBUG(dbgs() << "Record AdrpAdrp:\n" << *L2 << '\n' << *L1 << '\n');
 677       SmallVector<const MachineInstr *, 2> Args;
 678       Args.push_back(L2);
 679       Args.push_back(L1);
 680       ARM64FI.addLOHDirective(MCLOH_AdrpAdrp, Args);
 681       ++NumADRPSimpleCandidate;
 682     }
 683 #ifdef DEBUG
 684     else if (Size == 2)
 685       ++NumADRPComplexCandidate2;
 686     else if (Size == 3)
 687       ++NumADRPComplexCandidate3;
 688     else
 689       ++NumADRPComplexCandidateOther;
 690 #endif
 691     // if Size < 1, the use should have been removed from the candidates
 692     assert(Size >= 1 && "No reaching defs for that use!");
 693   }
 694 }
 695
 696 /// Check whether the given instruction can be the end of a LOH chain
 697 /// involving a load.
 698 static bool isCandidateLoad(const MachineInstr *Instr) {
 699   switch (Instr->getOpcode()) {
 700   default:
 701     return false;
 702   case ARM64::LDRSBWui:
 703   case ARM64::LDRSBXui:
 704   case ARM64::LDRSHWui:
 705   case ARM64::LDRSHXui:
 706   case ARM64::LDRSWui:
 707   case ARM64::LDRBui:
 708   case ARM64::LDRHui:
 709   case ARM64::LDRWui:
 710   case ARM64::LDRXui:
 711   case ARM64::LDRSui:
 712   case ARM64::LDRDui:
 713   case ARM64::LDRQui:
 714     if (Instr->getOperand(2).getTargetFlags() & ARM64II::MO_GOT)
 715       return false;
 716     return true;
 717   }
 718   // Unreachable.
 719   return false;
 720 }
 721
 722 /// Check whether the given instruction can load a litteral.
 723 static bool supportLoadFromLiteral(const MachineInstr *Instr) {
 724   switch (Instr->getOpcode()) {
 725   default:
 726     return false;
 727   case ARM64::LDRSWui:
 728   case ARM64::LDRWui:
 729   case ARM64::LDRXui:
 730   case ARM64::LDRSui:
 731   case ARM64::LDRDui:
 732   case ARM64::LDRQui:
 733     return true;
 734   }
 735   // Unreachable.
 736   return false;
 737 }
 738
 739 /// Check whether the given instruction is a LOH candidate.
 740 /// \param UseToDefs is used to check that Instr is at the end of LOH supported
 741 /// chain.
 742 /// \pre UseToDefs contains only on def per use, i.e., obvious non candidate are
 743 /// already been filtered out.
 744 static bool isCandidate(const MachineInstr *Instr,
 745                         const InstrToInstrs &UseToDefs,
 746                         const MachineDominatorTree *MDT) {
 747   if (!isCandidateLoad(Instr) && !isCandidateStore(Instr))
 748     return false;
 749
 750   const MachineInstr *Def = *UseToDefs.find(Instr)->second.begin();
 751   if (Def->getOpcode() != ARM64::ADRP) {
 752     // At this point, Def is ADDXri or LDRXui of the right type of
 753     // symbol, because we filtered out the uses that were not defined
 754     // by these kind of instructions (+ ADRP).
 755
 756     // Check if this forms a simple chain: each intermediate node must
 757     // dominates the next one.
 758     if (!MDT->dominates(Def, Instr))
 759       return false;
 760     // Move one node up in the simple chain.
 761     if (UseToDefs.find(Def) == UseToDefs.end()
 762                                // The map may contain garbage we have to ignore.
 763         ||
 764         UseToDefs.find(Def)->second.empty())
 765       return false;
 766     Instr = Def;
 767     Def = *UseToDefs.find(Def)->second.begin();
 768   }
 769   // Check if we reached the top of the simple chain:
 770   // - top is ADRP.
 771   // - check the simple chain property: each intermediate node must
 772   // dominates the next one.
 773   if (Def->getOpcode() == ARM64::ADRP)
 774     return MDT->dominates(Def, Instr);
 775   return false;
 776 }
 777
 778 static bool registerADRCandidate(const MachineInstr *Use,
 779                                  const InstrToInstrs &UseToDefs,
 780                                  const InstrToInstrs *DefsPerColorToUses,
 781                                  ARM64FunctionInfo &ARM64FI,
 782                                  SetOfMachineInstr *InvolvedInLOHs,
 783                                  const MapRegToId &RegToId) {
 784   // Look for opportunities to turn ADRP -> ADD or
 785   // ADRP -> LDR GOTPAGEOFF into ADR.
 786   // If ADRP has more than one use. Give up.
 787   if (Use->getOpcode() != ARM64::ADDXri &&
 788       (Use->getOpcode() != ARM64::LDRXui ||
 789        !(Use->getOperand(2).getTargetFlags() & ARM64II::MO_GOT)))
 790     return false;
 791   InstrToInstrs::const_iterator It = UseToDefs.find(Use);
 792   // The map may contain garbage that we need to ignore.
 793   if (It == UseToDefs.end() || It->second.empty())
 794     return false;
 795   const MachineInstr *Def = *It->second.begin();
 796   if (Def->getOpcode() != ARM64::ADRP)
 797     return false;
 798   // Check the number of users of ADRP.
 799   const SetOfMachineInstr *Users =
 800       getUses(DefsPerColorToUses,
 801               RegToId.find(Def->getOperand(0).getReg())->second, Def);
 802   if (Users->size() > 1) {
 803     ++NumADRComplexCandidate;
 804     return false;
 805   }
 806   ++NumADRSimpleCandidate;
 807   assert((!InvolvedInLOHs || InvolvedInLOHs->insert(Def)) &&
 808          "ADRP already involved in LOH.");
 809   assert((!InvolvedInLOHs || InvolvedInLOHs->insert(Use)) &&
 810          "ADD already involved in LOH.");
 811   DEBUG(dbgs() << "Record AdrpAdd\n" << *Def << '\n' << *Use << '\n');
 812
 813   SmallVector<const MachineInstr *, 2> Args;
 814   Args.push_back(Def);
 815   Args.push_back(Use);
 816
 817   ARM64FI.addLOHDirective(Use->getOpcode() == ARM64::ADDXri ? MCLOH_AdrpAdd
 818                                                             : MCLOH_AdrpLdrGot,
 819                           Args);
 820   return true;
 821 }
 822
 823 /// Based on the use to defs information (in non-ADRPMode), compute the
 824 /// opportunities of LOH non-ADRP-related
 825 static void computeOthers(const InstrToInstrs &UseToDefs,
 826                           const InstrToInstrs *DefsPerColorToUses,
 827                           ARM64FunctionInfo &ARM64FI, const MapRegToId &RegToId,
 828                           const MachineDominatorTree *MDT) {
 829   SetOfMachineInstr *InvolvedInLOHs = NULL;
 830 #ifdef DEBUG
 831   SetOfMachineInstr InvolvedInLOHsStorage;
 832   InvolvedInLOHs = &InvolvedInLOHsStorage;
 833 #endif // DEBUG
 834   DEBUG(dbgs() << "*** Compute LOH for Others\n");
 835   // ADRP -> ADD/LDR -> LDR/STR pattern.
 836   // Fall back to ADRP -> ADD pattern if we fail to catch the bigger pattern.
 837
 838   // FIXME: When the statistics are not important,
 839   // This initial filtering loop can be merged into the next loop.
 840   // Currently, we didn't do it to have the same code for both DEBUG and
 841   // NDEBUG builds. Indeed, the iterator of the second loop would need
 842   // to be changed.
 843   SetOfMachineInstr PotentialCandidates;
 844   SetOfMachineInstr PotentialADROpportunities;
 845   for (InstrToInstrs::const_iterator UseIt = UseToDefs.begin(),
 846                                      EndUseIt = UseToDefs.end();
 847        UseIt != EndUseIt; ++UseIt) {
 848     // If no definition is available, this is a non candidate.
 849     if (UseIt->second.empty())
 850       continue;
 851     // Keep only instructions that are load or store and at the end of
 852     // a ADRP -> ADD/LDR/Nothing chain.
 853     // We already filtered out the no-chain cases.
 854     if (!isCandidate(UseIt->first, UseToDefs, MDT)) {
 855       PotentialADROpportunities.insert(UseIt->first);
 856       continue;
 857     }
 858     PotentialCandidates.insert(UseIt->first);
 859   }
 860
 861   // Make the following distinctions for statistics as the linker does
 862   // know how to decode instructions:
 863   // - ADD/LDR/Nothing make there different patterns.
 864   // - LDR/STR make two different patterns.
 865   // Hence, 6 - 1 base patterns.
 866   // (because ADRP-> Nothing -> STR is not simplifiable)
 867
 868   // The linker is only able to have a simple semantic, i.e., if pattern A
 869   // do B.
 870   // However, we want to see the opportunity we may miss if we were able to
 871   // catch more complex cases.
 872
 873   // PotentialCandidates are result of a chain ADRP -> ADD/LDR ->
 874   // A potential candidate becomes a candidate, if its current immediate
 875   // operand is zero and all nodes of the chain have respectively only one user
 876   SetOfMachineInstr::const_iterator CandidateIt, EndCandidateIt;
 877 #ifdef DEBUG
 878   SetOfMachineInstr DefsOfPotentialCandidates;
 879 #endif
 880   for (CandidateIt = PotentialCandidates.begin(),
 881       EndCandidateIt = PotentialCandidates.end();
 882        CandidateIt != EndCandidateIt; ++CandidateIt) {
 883     const MachineInstr *Candidate = *CandidateIt;
 884     // Get the definition of the candidate i.e., ADD or LDR.
 885     const MachineInstr *Def = *UseToDefs.find(Candidate)->second.begin();
 886     // Record the elements of the chain.
 887     const MachineInstr *L1 = Def;
 888     const MachineInstr *L2 = NULL;
 889     unsigned ImmediateDefOpc = Def->getOpcode();
 890     if (Def->getOpcode() != ARM64::ADRP) {
 891       // Check the number of users of this node.
 892       const SetOfMachineInstr *Users =
 893           getUses(DefsPerColorToUses,
 894                   RegToId.find(Def->getOperand(0).getReg())->second, Def);
 895       if (Users->size() > 1) {
 896 #ifdef DEBUG
 897         // if all the uses of this def are in potential candidate, this is
 898         // a complex candidate of level 2.
 899         SetOfMachineInstr::const_iterator UseIt = Users->begin();
 900         SetOfMachineInstr::const_iterator EndUseIt = Users->end();
 901         for (; UseIt != EndUseIt; ++UseIt) {
 902           if (!PotentialCandidates.count(*UseIt)) {
 903             ++NumTooCplxLvl2;
 904             break;
 905           }
 906         }
 907         if (UseIt == EndUseIt)
 908           ++NumCplxLvl2;
 909 #endif // DEBUG
 910         PotentialADROpportunities.insert(Def);
 911         continue;
 912       }
 913       L2 = Def;
 914       Def = *UseToDefs.find(Def)->second.begin();
 915       L1 = Def;
 916     } // else the element in the middle of the chain is nothing, thus
 917       // Def already contains the first element of the chain.
 918
 919     // Check the number of users of the first node in the chain, i.e., ADRP
 920     const SetOfMachineInstr *Users =
 921         getUses(DefsPerColorToUses,
 922                 RegToId.find(Def->getOperand(0).getReg())->second, Def);
 923     if (Users->size() > 1) {
 924 #ifdef DEBUG
 925       // if all the uses of this def are in the defs of the potential candidate,
 926       // this is a complex candidate of level 1
 927       if (DefsOfPotentialCandidates.empty()) {
 928         // lazy init
 929         DefsOfPotentialCandidates = PotentialCandidates;
 930         for (SetOfMachineInstr::const_iterator
 931                  It = PotentialCandidates.begin(),
 932                  EndIt = PotentialCandidates.end();
 933              It != EndIt; ++It)
 934           if (!UseToDefs.find(Candidate)->second.empty())
 935             DefsOfPotentialCandidates.insert(
 936                 *UseToDefs.find(Candidate)->second.begin());
 937       }
 938       SetOfMachineInstr::const_iterator UseIt = Users->begin();
 939       SetOfMachineInstr::const_iterator EndUseIt = Users->end();
 940       for (; UseIt != EndUseIt; ++UseIt) {
 941         if (!DefsOfPotentialCandidates.count(*UseIt)) {
 942           ++NumTooCplxLvl1;
 943           break;
 944         }
 945       }
 946       if (UseIt == EndUseIt)
 947         ++NumCplxLvl1;
 948 #endif // DEBUG
 949       continue;
 950     }
 951
 952     bool IsL2Add = (ImmediateDefOpc == ARM64::ADDXri);
 953     // If the chain is three instructions long and ldr is the second element,
 954     // then this ldr must load form GOT, otherwise this is not a correct chain.
 955     if (L2 && !IsL2Add && L2->getOperand(2).getTargetFlags() != ARM64II::MO_GOT)
 956       continue;
 957     SmallVector<const MachineInstr *, 3> Args;
 958     MCLOHType Kind;
 959     if (isCandidateLoad(Candidate)) {
 960       if (L2 == NULL) {
 961         // At this point, the candidate LOH indicates that the ldr instruction
 962         // may use a direct access to the symbol. There is not such encoding
 963         // for loads of byte and half.
 964         if (!supportLoadFromLiteral(Candidate))
 965           continue;
 966
 967         DEBUG(dbgs() << "Record AdrpLdr:\n" << *L1 << '\n' << *Candidate
 968                      << '\n');
 969         Kind = MCLOH_AdrpLdr;
 970         Args.push_back(L1);
 971         Args.push_back(Candidate);
 972         assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L1)) &&
 973                "L1 already involved in LOH.");
 974         assert((!InvolvedInLOHs || InvolvedInLOHs->insert(Candidate)) &&
 975                "Candidate already involved in LOH.");
 976         ++NumADRPToLDR;
 977       } else {
 978         DEBUG(dbgs() << "Record Adrp" << (IsL2Add ? "Add" : "LdrGot")
 979                      << "Ldr:\n" << *L1 << '\n' << *L2 << '\n' << *Candidate
 980                      << '\n');
 981
 982         Kind = IsL2Add ? MCLOH_AdrpAddLdr : MCLOH_AdrpLdrGotLdr;
 983         Args.push_back(L1);
 984         Args.push_back(L2);
 985         Args.push_back(Candidate);
 986
 987         PotentialADROpportunities.remove(L2);
 988         assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L1)) &&
 989                "L1 already involved in LOH.");
 990         assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L2)) &&
 991                "L2 already involved in LOH.");
 992         assert((!InvolvedInLOHs || InvolvedInLOHs->insert(Candidate)) &&
 993                "Candidate already involved in LOH.");
 994 #ifdef DEBUG
 995         // get the immediate of the load
 996         if (Candidate->getOperand(2).getImm() == 0)
 997           if (ImmediateDefOpc == ARM64::ADDXri)
 998             ++NumADDToLDR;
 999           else
1000             ++NumLDRToLDR;
1001         else if (ImmediateDefOpc == ARM64::ADDXri)
1002           ++NumADDToLDRWithImm;
1003         else
1004           ++NumLDRToLDRWithImm;
1005 #endif // DEBUG
1006       }
1007     } else {
1008       if (ImmediateDefOpc == ARM64::ADRP)
1009         continue;
1010       else {
1011
1012         DEBUG(dbgs() << "Record Adrp" << (IsL2Add ? "Add" : "LdrGot")
1013                      << "Str:\n" << *L1 << '\n' << *L2 << '\n' << *Candidate
1014                      << '\n');
1015
1016         Kind = IsL2Add ? MCLOH_AdrpAddStr : MCLOH_AdrpLdrGotStr;
1017         Args.push_back(L1);
1018         Args.push_back(L2);
1019         Args.push_back(Candidate);
1020
1021         PotentialADROpportunities.remove(L2);
1022         assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L1)) &&
1023                "L1 already involved in LOH.");
1024         assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L2)) &&
1025                "L2 already involved in LOH.");
1026         assert((!InvolvedInLOHs || InvolvedInLOHs->insert(Candidate)) &&
1027                "Candidate already involved in LOH.");
1028 #ifdef DEBUG
1029         // get the immediate of the store
1030         if (Candidate->getOperand(2).getImm() == 0)
1031           if (ImmediateDefOpc == ARM64::ADDXri)
1032             ++NumADDToSTR;
1033           else
1034             ++NumLDRToSTR;
1035         else if (ImmediateDefOpc == ARM64::ADDXri)
1036           ++NumADDToSTRWithImm;
1037         else
1038           ++NumLDRToSTRWithImm;
1039 #endif // DEBUG
1040       }
1041     }
1042     ARM64FI.addLOHDirective(Kind, Args);
1043   }
1044
1045   // Now, we grabbed all the big patterns, check ADR opportunities.
1046   for (SetOfMachineInstr::const_iterator
1047            CandidateIt = PotentialADROpportunities.begin(),
1048            EndCandidateIt = PotentialADROpportunities.end();
1049        CandidateIt != EndCandidateIt; ++CandidateIt)
1050     registerADRCandidate(*CandidateIt, UseToDefs, DefsPerColorToUses, ARM64FI,
1051                          InvolvedInLOHs, RegToId);
1052 }
1053
1054 /// Look for every register defined by potential LOHs candidates.
1055 /// Map these registers with dense id in @p RegToId and vice-versa in
1056 /// @p IdToReg. @p IdToReg is populated only in DEBUG mode.
1057 static void collectInvolvedReg(MachineFunction &MF, MapRegToId &RegToId,
1058                                MapIdToReg &IdToReg,
1059                                const TargetRegisterInfo *TRI) {
1060   unsigned CurRegId = 0;
1061   if (!PreCollectRegister) {
1062     unsigned NbReg = TRI->getNumRegs();
1063     for (; CurRegId < NbReg; ++CurRegId) {
1064       RegToId[CurRegId] = CurRegId;
1065       DEBUG(IdToReg.push_back(CurRegId));
1066       DEBUG(assert(IdToReg[CurRegId] == CurRegId && "Reg index mismatches"));
1067     }
1068     return;
1069   }
1070
1071   DEBUG(dbgs() << "** Collect Involved Register\n");
1072   for (MachineFunction::const_iterator IMBB = MF.begin(), IMBBEnd = MF.end();
1073        IMBB != IMBBEnd; ++IMBB)
1074     for (MachineBasicBlock::const_iterator II = IMBB->begin(),
1075                                            IEnd = IMBB->end();
1076          II != IEnd; ++II) {
1077
1078       if (!canDefBePartOfLOH(II))
1079         continue;
1080
1081       // Process defs
1082       for (MachineInstr::const_mop_iterator IO = II->operands_begin(),
1083                                             IOEnd = II->operands_end();
1084            IO != IOEnd; ++IO) {
1085         if (!IO->isReg() || !IO->isDef())
1086           continue;
1087         unsigned CurReg = IO->getReg();
1088         for (MCRegAliasIterator AI(CurReg, TRI, true); AI.isValid(); ++AI)
1089           if (RegToId.find(*AI) == RegToId.end()) {
1090             DEBUG(IdToReg.push_back(*AI);
1091                   assert(IdToReg[CurRegId] == *AI &&
1092                          "Reg index mismatches insertion index."));
1093             RegToId[*AI] = CurRegId++;
1094             DEBUG(dbgs() << "Register: " << PrintReg(*AI, TRI) << '\n');
1095           }
1096       }
1097     }
1098 }
1099
1100 bool ARM64CollectLOH::runOnMachineFunction(MachineFunction &Fn) {
1101   const TargetMachine &TM = Fn.getTarget();
1102   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
1103   const MachineDominatorTree *MDT = &getAnalysis<MachineDominatorTree>();
1104
1105   MapRegToId RegToId;
1106   MapIdToReg IdToReg;
1107   ARM64FunctionInfo *ARM64FI = Fn.getInfo<ARM64FunctionInfo>();
1108   assert(ARM64FI && "No MachineFunctionInfo for this function!");
1109
1110   DEBUG(dbgs() << "Looking for LOH in " << Fn.getName() << '\n');
1111
1112   collectInvolvedReg(Fn, RegToId, IdToReg, TRI);
1113   if (RegToId.empty())
1114     return false;
1115
1116   MachineInstr *DummyOp = NULL;
1117   if (BasicBlockScopeOnly) {
1118     const ARM64InstrInfo *TII =
1119         static_cast<const ARM64InstrInfo *>(TM.getInstrInfo());
1120     // For local analysis, create a dummy operation to record uses that are not
1121     // local.
1122     DummyOp = Fn.CreateMachineInstr(TII->get(ARM64::COPY), DebugLoc());
1123   }
1124
1125   unsigned NbReg = RegToId.size();
1126   bool Modified = false;
1127
1128   // Start with ADRP.
1129   InstrToInstrs *ColorOpToReachedUses = new InstrToInstrs[NbReg];
1130
1131   // Compute the reaching def in ADRP mode, meaning ADRP definitions
1132   // are first considered as uses.
1133   reachingDef(&Fn, ColorOpToReachedUses, RegToId, true, DummyOp);
1134   DEBUG(dbgs() << "ADRP reaching defs\n");
1135   DEBUG(printReachingDef(ColorOpToReachedUses, NbReg, TRI, IdToReg));
1136
1137   // Translate the definition to uses map into a use to definitions map to ease
1138   // statistic computation.
1139   InstrToInstrs ADRPToReachingDefs;
1140   reachedUsesToDefs(ADRPToReachingDefs, ColorOpToReachedUses, RegToId, true);
1141
1142   // Compute LOH for ADRP.
1143   computeADRP(ADRPToReachingDefs, *ARM64FI, MDT);
1144   delete[] ColorOpToReachedUses;
1145
1146   // Continue with general ADRP -> ADD/LDR -> LDR/STR pattern.
1147   ColorOpToReachedUses = new InstrToInstrs[NbReg];
1148
1149   // first perform a regular reaching def analysis.
1150   reachingDef(&Fn, ColorOpToReachedUses, RegToId, false, DummyOp);
1151   DEBUG(dbgs() << "All reaching defs\n");
1152   DEBUG(printReachingDef(ColorOpToReachedUses, NbReg, TRI, IdToReg));
1153
1154   // Turn that into a use to defs to ease statistic computation.
1155   InstrToInstrs UsesToReachingDefs;
1156   reachedUsesToDefs(UsesToReachingDefs, ColorOpToReachedUses, RegToId, false);
1157
1158   // Compute other than AdrpAdrp LOH.
1159   computeOthers(UsesToReachingDefs, ColorOpToReachedUses, *ARM64FI, RegToId,
1160                 MDT);
1161   delete[] ColorOpToReachedUses;
1162
1163   if (BasicBlockScopeOnly)
1164     Fn.DeleteMachineInstr(DummyOp);
1165
1166   return Modified;
1167 }
1168
1169 /// createARM64CollectLOHPass - returns an instance of the Statistic for
1170 /// linker optimization pass.
1171 FunctionPass *llvm::createARM64CollectLOHPass() {
1172   return new ARM64CollectLOH();
1173 }