1 //===---------- AArch64CollectLOH.cpp - AArch64 collect LOH pass --*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
13 // To be useful for the linker, the LOH must be printed into the assembly file.
15 // A LOH describes a sequence of instructions that may be optimized by the
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
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:
33 // L3: ldr xC, [xB, #imm]
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
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
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
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.
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.
87 // The overall design for emitting the LOHs is:
88 // 1. AArch64CollectLOH (this pass) records the LOHs in the AArch64FunctionInfo.
89 // 2. AArch64AsmPrinter reads the LOHs from AArch64FunctionInfo 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 //===----------------------------------------------------------------------===//
102 #include "AArch64InstrInfo.h"
103 #include "AArch64MachineFunctionInfo.h"
104 #include "AArch64Subtarget.h"
105 #include "MCTargetDesc/AArch64AddressingModes.h"
106 #include "llvm/ADT/BitVector.h"
107 #include "llvm/ADT/DenseMap.h"
108 #include "llvm/ADT/MapVector.h"
109 #include "llvm/ADT/SetVector.h"
110 #include "llvm/ADT/SmallVector.h"
111 #include "llvm/ADT/Statistic.h"
112 #include "llvm/CodeGen/MachineBasicBlock.h"
113 #include "llvm/CodeGen/MachineDominators.h"
114 #include "llvm/CodeGen/MachineFunctionPass.h"
115 #include "llvm/CodeGen/MachineInstr.h"
116 #include "llvm/CodeGen/MachineInstrBuilder.h"
117 #include "llvm/Support/CommandLine.h"
118 #include "llvm/Support/Debug.h"
119 #include "llvm/Support/ErrorHandling.h"
120 #include "llvm/Support/raw_ostream.h"
121 #include "llvm/Target/TargetInstrInfo.h"
122 #include "llvm/Target/TargetMachine.h"
123 #include "llvm/Target/TargetRegisterInfo.h"
124 using namespace llvm;
126 #define DEBUG_TYPE "aarch64-collect-loh"
129 PreCollectRegister("aarch64-collect-loh-pre-collect-register", cl::Hidden,
130 cl::desc("Restrict analysis to registers invovled"
135 BasicBlockScopeOnly("aarch64-collect-loh-bb-only", cl::Hidden,
136 cl::desc("Restrict analysis at basic block scope"),
139 STATISTIC(NumADRPSimpleCandidate,
140 "Number of simplifiable ADRP dominate by another");
141 STATISTIC(NumADRPComplexCandidate2,
142 "Number of simplifiable ADRP reachable by 2 defs");
143 STATISTIC(NumADRPComplexCandidate3,
144 "Number of simplifiable ADRP reachable by 3 defs");
145 STATISTIC(NumADRPComplexCandidateOther,
146 "Number of simplifiable ADRP reachable by 4 or more defs");
147 STATISTIC(NumADDToSTRWithImm,
148 "Number of simplifiable STR with imm reachable by ADD");
149 STATISTIC(NumLDRToSTRWithImm,
150 "Number of simplifiable STR with imm reachable by LDR");
151 STATISTIC(NumADDToSTR, "Number of simplifiable STR reachable by ADD");
152 STATISTIC(NumLDRToSTR, "Number of simplifiable STR reachable by LDR");
153 STATISTIC(NumADDToLDRWithImm,
154 "Number of simplifiable LDR with imm reachable by ADD");
155 STATISTIC(NumLDRToLDRWithImm,
156 "Number of simplifiable LDR with imm reachable by LDR");
157 STATISTIC(NumADDToLDR, "Number of simplifiable LDR reachable by ADD");
158 STATISTIC(NumLDRToLDR, "Number of simplifiable LDR reachable by LDR");
159 STATISTIC(NumADRPToLDR, "Number of simplifiable LDR reachable by ADRP");
160 STATISTIC(NumCplxLvl1, "Number of complex case of level 1");
161 STATISTIC(NumTooCplxLvl1, "Number of too complex case of level 1");
162 STATISTIC(NumCplxLvl2, "Number of complex case of level 2");
163 STATISTIC(NumTooCplxLvl2, "Number of too complex case of level 2");
164 STATISTIC(NumADRSimpleCandidate, "Number of simplifiable ADRP + ADD");
165 STATISTIC(NumADRComplexCandidate, "Number of too complex ADRP + ADD");
168 void initializeAArch64CollectLOHPass(PassRegistry &);
172 struct AArch64CollectLOH : public MachineFunctionPass {
174 AArch64CollectLOH() : MachineFunctionPass(ID) {
175 initializeAArch64CollectLOHPass(*PassRegistry::getPassRegistry());
178 bool runOnMachineFunction(MachineFunction &MF) override;
180 const char *getPassName() const override {
181 return "AArch64 Collect Linker Optimization Hint (LOH)";
184 void getAnalysisUsage(AnalysisUsage &AU) const override {
185 AU.setPreservesAll();
186 MachineFunctionPass::getAnalysisUsage(AU);
187 AU.addRequired<MachineDominatorTree>();
193 /// A set of MachineInstruction.
194 typedef SetVector<const MachineInstr *> SetOfMachineInstr;
195 /// Map a basic block to a set of instructions per register.
196 /// This is used to represent the exposed uses of a basic block
198 typedef MapVector<const MachineBasicBlock *, SetOfMachineInstr *>
199 BlockToSetOfInstrsPerColor;
200 /// Map a basic block to an instruction per register.
201 /// This is used to represent the live-out definitions of a basic block
203 typedef MapVector<const MachineBasicBlock *, const MachineInstr **>
204 BlockToInstrPerColor;
205 /// Map an instruction to a set of instructions. Used to represent the
206 /// mapping def to reachable uses or use to definitions.
207 typedef MapVector<const MachineInstr *, SetOfMachineInstr> InstrToInstrs;
208 /// Map a basic block to a BitVector.
209 /// This is used to record the kill registers per basic block.
210 typedef MapVector<const MachineBasicBlock *, BitVector> BlockToRegSet;
212 /// Map a register to a dense id.
213 typedef DenseMap<unsigned, unsigned> MapRegToId;
214 /// Map a dense id to a register. Used for debug purposes.
215 typedef SmallVector<unsigned, 32> MapIdToReg;
216 } // end anonymous namespace.
218 char AArch64CollectLOH::ID = 0;
220 INITIALIZE_PASS_BEGIN(AArch64CollectLOH, "aarch64-collect-loh",
221 "AArch64 Collect Linker Optimization Hint (LOH)", false,
223 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
224 INITIALIZE_PASS_END(AArch64CollectLOH, "aarch64-collect-loh",
225 "AArch64 Collect Linker Optimization Hint (LOH)", false,
228 /// Given a couple (MBB, reg) get the corresponding set of instruction from
229 /// the given "sets".
230 /// If this couple does not reference any set, an empty set is added to "sets"
231 /// for this couple and returned.
232 /// \param nbRegs is used internally allocate some memory. It must be consistent
233 /// with the way sets is used.
234 static SetOfMachineInstr &getSet(BlockToSetOfInstrsPerColor &sets,
235 const MachineBasicBlock &MBB, unsigned reg,
237 SetOfMachineInstr *result;
238 BlockToSetOfInstrsPerColor::iterator it = sets.find(&MBB);
239 if (it != sets.end())
242 result = sets[&MBB] = new SetOfMachineInstr[nbRegs];
247 /// Given a couple (reg, MI) get the corresponding set of instructions from the
248 /// the given "sets".
249 /// This is used to get the uses record in sets of a definition identified by
250 /// MI and reg, i.e., MI defines reg.
251 /// If the couple does not reference anything, an empty set is added to
253 /// \pre set[reg] is valid.
254 static SetOfMachineInstr &getUses(InstrToInstrs *sets, unsigned reg,
255 const MachineInstr &MI) {
256 return sets[reg][&MI];
259 /// Same as getUses but does not modify the input map: sets.
260 /// \return NULL if the couple (reg, MI) is not in sets.
261 static const SetOfMachineInstr *getUses(const InstrToInstrs *sets, unsigned reg,
262 const MachineInstr &MI) {
263 InstrToInstrs::const_iterator Res = sets[reg].find(&MI);
264 if (Res != sets[reg].end())
265 return &(Res->second);
269 /// Initialize the reaching definition algorithm:
270 /// For each basic block BB in MF, record:
272 /// - its reachable uses (uses that are exposed to BB's predecessors).
273 /// - its the generated definitions.
274 /// \param DummyOp if not NULL, specifies a Dummy Operation to be added to
275 /// the list of uses of exposed defintions.
276 /// \param ADRPMode specifies to only consider ADRP instructions for generated
277 /// definition. It also consider definitions of ADRP instructions as uses and
278 /// ignore other uses. The ADRPMode is used to collect the information for LHO
279 /// that involve ADRP operation only.
280 static void initReachingDef(MachineFunction &MF,
281 InstrToInstrs *ColorOpToReachedUses,
282 BlockToInstrPerColor &Gen, BlockToRegSet &Kill,
283 BlockToSetOfInstrsPerColor &ReachableUses,
284 const MapRegToId &RegToId,
285 const MachineInstr *DummyOp, bool ADRPMode) {
286 const TargetMachine &TM = MF.getTarget();
287 const TargetRegisterInfo *TRI = TM.getSubtargetImpl()->getRegisterInfo();
289 unsigned NbReg = RegToId.size();
291 for (MachineBasicBlock &MBB : MF) {
292 const MachineInstr **&BBGen = Gen[&MBB];
293 BBGen = new const MachineInstr *[NbReg];
294 memset(BBGen, 0, sizeof(const MachineInstr *) * NbReg);
296 BitVector &BBKillSet = Kill[&MBB];
297 BBKillSet.resize(NbReg);
298 for (const MachineInstr &MI : MBB) {
299 bool IsADRP = MI.getOpcode() == AArch64::ADRP;
301 // Process uses first.
302 if (IsADRP || !ADRPMode)
303 for (const MachineOperand &MO : MI.operands()) {
304 // Treat ADRP def as use, as the goal of the analysis is to find
305 // ADRP defs reached by other ADRP defs.
306 if (!MO.isReg() || (!ADRPMode && !MO.isUse()) ||
307 (ADRPMode && (!IsADRP || !MO.isDef())))
309 unsigned CurReg = MO.getReg();
310 MapRegToId::const_iterator ItCurRegId = RegToId.find(CurReg);
311 if (ItCurRegId == RegToId.end())
313 CurReg = ItCurRegId->second;
315 // if CurReg has not been defined, this use is reachable.
316 if (!BBGen[CurReg] && !BBKillSet.test(CurReg))
317 getSet(ReachableUses, MBB, CurReg, NbReg).insert(&MI);
318 // current basic block definition for this color, if any, is in Gen.
320 getUses(ColorOpToReachedUses, CurReg, *BBGen[CurReg]).insert(&MI);
324 for (const MachineOperand &MO : MI.operands()) {
327 // Clobbers kill the related colors.
328 const uint32_t *PreservedRegs = MO.getRegMask();
330 // Set generated regs.
331 for (const auto Entry : RegToId) {
332 unsigned Reg = Entry.second;
333 // Use the global register ID when querying APIs external to this
335 if (MachineOperand::clobbersPhysReg(PreservedRegs, Entry.first)) {
336 // Do not register clobbered definition for no ADRP.
337 // This definition is not used anyway (otherwise register
338 // allocation is wrong).
339 BBGen[Reg] = ADRPMode ? &MI : nullptr;
345 // Process register defs.
346 for (const MachineOperand &MO : MI.operands()) {
347 if (!MO.isReg() || !MO.isDef())
349 unsigned CurReg = MO.getReg();
350 MapRegToId::const_iterator ItCurRegId = RegToId.find(CurReg);
351 if (ItCurRegId == RegToId.end())
354 for (MCRegAliasIterator AI(CurReg, TRI, true); AI.isValid(); ++AI) {
355 MapRegToId::const_iterator ItRegId = RegToId.find(*AI);
356 assert(ItRegId != RegToId.end() &&
357 "Sub-register of an "
358 "involved register, not recorded as involved!");
359 BBKillSet.set(ItRegId->second);
360 BBGen[ItRegId->second] = &MI;
362 BBGen[ItCurRegId->second] = &MI;
366 // If we restrict our analysis to basic block scope, conservatively add a
368 // use for each generated value.
369 if (!ADRPMode && DummyOp && !MBB.succ_empty())
370 for (unsigned CurReg = 0; CurReg < NbReg; ++CurReg)
372 getUses(ColorOpToReachedUses, CurReg, *BBGen[CurReg]).insert(DummyOp);
376 /// Reaching def core algorithm:
377 /// while an Out has changed
380 /// In[bb][color] = U Out[bb.predecessors][color]
381 /// insert reachableUses[bb][color] in each in[bb][color]
384 /// Out[bb] = Gen[bb] U (In[bb] - Kill[bb])
385 static void reachingDefAlgorithm(MachineFunction &MF,
386 InstrToInstrs *ColorOpToReachedUses,
387 BlockToSetOfInstrsPerColor &In,
388 BlockToSetOfInstrsPerColor &Out,
389 BlockToInstrPerColor &Gen, BlockToRegSet &Kill,
390 BlockToSetOfInstrsPerColor &ReachableUses,
395 for (MachineBasicBlock &MBB : MF) {
397 for (CurReg = 0; CurReg < NbReg; ++CurReg) {
398 SetOfMachineInstr &BBInSet = getSet(In, MBB, CurReg, NbReg);
399 SetOfMachineInstr &BBReachableUses =
400 getSet(ReachableUses, MBB, CurReg, NbReg);
401 SetOfMachineInstr &BBOutSet = getSet(Out, MBB, CurReg, NbReg);
402 unsigned Size = BBOutSet.size();
403 // In[bb][color] = U Out[bb.predecessors][color]
404 for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
405 SetOfMachineInstr &PredOutSet = getSet(Out, *PredMBB, CurReg, NbReg);
406 BBInSet.insert(PredOutSet.begin(), PredOutSet.end());
408 // insert reachableUses[bb][color] in each in[bb][color] op.reachedses
409 for (const MachineInstr *MI : BBInSet) {
410 SetOfMachineInstr &OpReachedUses =
411 getUses(ColorOpToReachedUses, CurReg, *MI);
412 OpReachedUses.insert(BBReachableUses.begin(), BBReachableUses.end());
414 // Out[bb] = Gen[bb] U (In[bb] - Kill[bb])
415 if (!Kill[&MBB].test(CurReg))
416 BBOutSet.insert(BBInSet.begin(), BBInSet.end());
417 if (Gen[&MBB][CurReg])
418 BBOutSet.insert(Gen[&MBB][CurReg]);
419 HasChanged |= BBOutSet.size() != Size;
422 } while (HasChanged);
425 /// Release all memory dynamically allocated during the reaching
426 /// definition algorithm.
427 static void finitReachingDef(BlockToSetOfInstrsPerColor &In,
428 BlockToSetOfInstrsPerColor &Out,
429 BlockToInstrPerColor &Gen,
430 BlockToSetOfInstrsPerColor &ReachableUses) {
435 for (auto &IT : ReachableUses)
441 /// Reaching definition algorithm.
442 /// \param MF function on which the algorithm will operate.
443 /// \param[out] ColorOpToReachedUses will contain the result of the reaching
445 /// \param ADRPMode specify whether the reaching def algorithm should be tuned
446 /// for ADRP optimization. \see initReachingDef for more details.
447 /// \param DummyOp if not NULL, the algorithm will work at
448 /// basic block scope and will set for every exposed definition a use to
450 /// \pre ColorOpToReachedUses is an array of at least number of registers of
452 static void reachingDef(MachineFunction &MF,
453 InstrToInstrs *ColorOpToReachedUses,
454 const MapRegToId &RegToId, bool ADRPMode = false,
455 const MachineInstr *DummyOp = nullptr) {
457 // For each basic block.
458 // Out: a set per color of definitions that reach the
459 // out boundary of this block.
460 // In: Same as Out but for in boundary.
461 // Gen: generated color in this block (one operation per color).
462 // Kill: register set of killed color in this block.
463 // ReachableUses: a set per color of uses (operation) reachable
464 // for "In" definitions.
465 BlockToSetOfInstrsPerColor Out, In, ReachableUses;
466 BlockToInstrPerColor Gen;
469 // Initialize Gen, kill and reachableUses.
470 initReachingDef(MF, ColorOpToReachedUses, Gen, Kill, ReachableUses, RegToId,
475 reachingDefAlgorithm(MF, ColorOpToReachedUses, In, Out, Gen, Kill,
476 ReachableUses, RegToId.size());
479 finitReachingDef(In, Out, Gen, ReachableUses);
483 /// print the result of the reaching definition algorithm.
484 static void printReachingDef(const InstrToInstrs *ColorOpToReachedUses,
485 unsigned NbReg, const TargetRegisterInfo *TRI,
486 const MapIdToReg &IdToReg) {
488 for (CurReg = 0; CurReg < NbReg; ++CurReg) {
489 if (ColorOpToReachedUses[CurReg].empty())
491 DEBUG(dbgs() << "*** Reg " << PrintReg(IdToReg[CurReg], TRI) << " ***\n");
493 for (const auto &DefsIt : ColorOpToReachedUses[CurReg]) {
494 DEBUG(dbgs() << "Def:\n");
495 DEBUG(DefsIt.first->print(dbgs()));
496 DEBUG(dbgs() << "Reachable uses:\n");
497 for (const MachineInstr *MI : DefsIt.second) {
498 DEBUG(MI->print(dbgs()));
505 /// Answer the following question: Can Def be one of the definition
506 /// involved in a part of a LOH?
507 static bool canDefBePartOfLOH(const MachineInstr *Def) {
508 unsigned Opc = Def->getOpcode();
509 // Accept ADRP, ADDLow and LOADGot.
515 case AArch64::ADDXri:
516 // Check immediate to see if the immediate is an address.
517 switch (Def->getOperand(2).getType()) {
520 case MachineOperand::MO_GlobalAddress:
521 case MachineOperand::MO_JumpTableIndex:
522 case MachineOperand::MO_ConstantPoolIndex:
523 case MachineOperand::MO_BlockAddress:
526 case AArch64::LDRXui:
527 // Check immediate to see if the immediate is an address.
528 switch (Def->getOperand(2).getType()) {
531 case MachineOperand::MO_GlobalAddress:
539 /// Check whether the given instruction can the end of a LOH chain involving a
541 static bool isCandidateStore(const MachineInstr *Instr) {
542 switch (Instr->getOpcode()) {
545 case AArch64::STRBui:
546 case AArch64::STRHui:
547 case AArch64::STRWui:
548 case AArch64::STRXui:
549 case AArch64::STRSui:
550 case AArch64::STRDui:
551 case AArch64::STRQui:
552 // In case we have str xA, [xA, #imm], this is two different uses
553 // of xA and we cannot fold, otherwise the xA stored may be wrong,
554 // even if #imm == 0.
555 if (Instr->getOperand(0).getReg() != Instr->getOperand(1).getReg())
561 /// Given the result of a reaching definition algorithm in ColorOpToReachedUses,
562 /// Build the Use to Defs information and filter out obvious non-LOH candidates.
563 /// In ADRPMode, non-LOH candidates are "uses" with non-ADRP definitions.
564 /// In non-ADRPMode, non-LOH candidates are "uses" with several definition,
565 /// i.e., no simple chain.
566 /// \param ADRPMode -- \see initReachingDef.
567 static void reachedUsesToDefs(InstrToInstrs &UseToReachingDefs,
568 const InstrToInstrs *ColorOpToReachedUses,
569 const MapRegToId &RegToId,
570 bool ADRPMode = false) {
572 SetOfMachineInstr NotCandidate;
573 unsigned NbReg = RegToId.size();
574 MapRegToId::const_iterator EndIt = RegToId.end();
575 for (unsigned CurReg = 0; CurReg < NbReg; ++CurReg) {
576 // If this color is never defined, continue.
577 if (ColorOpToReachedUses[CurReg].empty())
580 for (const auto &DefsIt : ColorOpToReachedUses[CurReg]) {
581 for (const MachineInstr *MI : DefsIt.second) {
582 const MachineInstr *Def = DefsIt.first;
583 MapRegToId::const_iterator It;
584 // if all the reaching defs are not adrp, this use will not be
586 if ((ADRPMode && Def->getOpcode() != AArch64::ADRP) ||
587 (!ADRPMode && !canDefBePartOfLOH(Def)) ||
588 (!ADRPMode && isCandidateStore(MI) &&
589 // store are LOH candidate iff the end of the chain is used as
591 ((It = RegToId.find((MI)->getOperand(1).getReg())) == EndIt ||
592 It->second != CurReg))) {
593 NotCandidate.insert(MI);
596 // Do not consider self reaching as a simplifiable case for ADRP.
597 if (!ADRPMode || MI != DefsIt.first) {
598 UseToReachingDefs[MI].insert(DefsIt.first);
599 // If UsesIt has several reaching definitions, it is not
600 // candidate for simplificaton in non-ADRPMode.
601 if (!ADRPMode && UseToReachingDefs[MI].size() > 1)
602 NotCandidate.insert(MI);
607 for (const MachineInstr *Elem : NotCandidate) {
608 DEBUG(dbgs() << "Too many reaching defs: " << *Elem << "\n");
609 // It would have been better if we could just remove the entry
610 // from the map. Because of that, we have to filter the garbage
611 // (second.empty) in the subsequence analysis.
612 UseToReachingDefs[Elem].clear();
616 /// Based on the use to defs information (in ADRPMode), compute the
617 /// opportunities of LOH ADRP-related.
618 static void computeADRP(const InstrToInstrs &UseToDefs,
619 AArch64FunctionInfo &AArch64FI,
620 const MachineDominatorTree *MDT) {
621 DEBUG(dbgs() << "*** Compute LOH for ADRP\n");
622 for (const auto &Entry : UseToDefs) {
623 unsigned Size = Entry.second.size();
627 const MachineInstr *L2 = *Entry.second.begin();
628 const MachineInstr *L1 = Entry.first;
629 if (!MDT->dominates(L2, L1)) {
630 DEBUG(dbgs() << "Dominance check failed:\n" << *L2 << '\n' << *L1
634 DEBUG(dbgs() << "Record AdrpAdrp:\n" << *L2 << '\n' << *L1 << '\n');
635 SmallVector<const MachineInstr *, 2> Args;
638 AArch64FI.addLOHDirective(MCLOH_AdrpAdrp, Args);
639 ++NumADRPSimpleCandidate;
643 ++NumADRPComplexCandidate2;
645 ++NumADRPComplexCandidate3;
647 ++NumADRPComplexCandidateOther;
649 // if Size < 1, the use should have been removed from the candidates
650 assert(Size >= 1 && "No reaching defs for that use!");
654 /// Check whether the given instruction can be the end of a LOH chain
655 /// involving a load.
656 static bool isCandidateLoad(const MachineInstr *Instr) {
657 switch (Instr->getOpcode()) {
660 case AArch64::LDRSBWui:
661 case AArch64::LDRSBXui:
662 case AArch64::LDRSHWui:
663 case AArch64::LDRSHXui:
664 case AArch64::LDRSWui:
665 case AArch64::LDRBui:
666 case AArch64::LDRHui:
667 case AArch64::LDRWui:
668 case AArch64::LDRXui:
669 case AArch64::LDRSui:
670 case AArch64::LDRDui:
671 case AArch64::LDRQui:
672 if (Instr->getOperand(2).getTargetFlags() & AArch64II::MO_GOT)
680 /// Check whether the given instruction can load a litteral.
681 static bool supportLoadFromLiteral(const MachineInstr *Instr) {
682 switch (Instr->getOpcode()) {
685 case AArch64::LDRSWui:
686 case AArch64::LDRWui:
687 case AArch64::LDRXui:
688 case AArch64::LDRSui:
689 case AArch64::LDRDui:
690 case AArch64::LDRQui:
697 /// Check whether the given instruction is a LOH candidate.
698 /// \param UseToDefs is used to check that Instr is at the end of LOH supported
700 /// \pre UseToDefs contains only on def per use, i.e., obvious non candidate are
701 /// already been filtered out.
702 static bool isCandidate(const MachineInstr *Instr,
703 const InstrToInstrs &UseToDefs,
704 const MachineDominatorTree *MDT) {
705 if (!isCandidateLoad(Instr) && !isCandidateStore(Instr))
708 const MachineInstr *Def = *UseToDefs.find(Instr)->second.begin();
709 if (Def->getOpcode() != AArch64::ADRP) {
710 // At this point, Def is ADDXri or LDRXui of the right type of
711 // symbol, because we filtered out the uses that were not defined
712 // by these kind of instructions (+ ADRP).
714 // Check if this forms a simple chain: each intermediate node must
715 // dominates the next one.
716 if (!MDT->dominates(Def, Instr))
718 // Move one node up in the simple chain.
719 if (UseToDefs.find(Def) ==
721 // The map may contain garbage we have to ignore.
723 UseToDefs.find(Def)->second.empty())
726 Def = *UseToDefs.find(Def)->second.begin();
728 // Check if we reached the top of the simple chain:
730 // - check the simple chain property: each intermediate node must
731 // dominates the next one.
732 if (Def->getOpcode() == AArch64::ADRP)
733 return MDT->dominates(Def, Instr);
737 static bool registerADRCandidate(const MachineInstr &Use,
738 const InstrToInstrs &UseToDefs,
739 const InstrToInstrs *DefsPerColorToUses,
740 AArch64FunctionInfo &AArch64FI,
741 SetOfMachineInstr *InvolvedInLOHs,
742 const MapRegToId &RegToId) {
743 // Look for opportunities to turn ADRP -> ADD or
744 // ADRP -> LDR GOTPAGEOFF into ADR.
745 // If ADRP has more than one use. Give up.
746 if (Use.getOpcode() != AArch64::ADDXri &&
747 (Use.getOpcode() != AArch64::LDRXui ||
748 !(Use.getOperand(2).getTargetFlags() & AArch64II::MO_GOT)))
750 InstrToInstrs::const_iterator It = UseToDefs.find(&Use);
751 // The map may contain garbage that we need to ignore.
752 if (It == UseToDefs.end() || It->second.empty())
754 const MachineInstr &Def = **It->second.begin();
755 if (Def.getOpcode() != AArch64::ADRP)
757 // Check the number of users of ADRP.
758 const SetOfMachineInstr *Users =
759 getUses(DefsPerColorToUses,
760 RegToId.find(Def.getOperand(0).getReg())->second, Def);
761 if (Users->size() > 1) {
762 ++NumADRComplexCandidate;
765 ++NumADRSimpleCandidate;
766 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(&Def)) &&
767 "ADRP already involved in LOH.");
768 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(&Use)) &&
769 "ADD already involved in LOH.");
770 DEBUG(dbgs() << "Record AdrpAdd\n" << Def << '\n' << Use << '\n');
772 SmallVector<const MachineInstr *, 2> Args;
773 Args.push_back(&Def);
774 Args.push_back(&Use);
776 AArch64FI.addLOHDirective(Use.getOpcode() == AArch64::ADDXri ? MCLOH_AdrpAdd
782 /// Based on the use to defs information (in non-ADRPMode), compute the
783 /// opportunities of LOH non-ADRP-related
784 static void computeOthers(const InstrToInstrs &UseToDefs,
785 const InstrToInstrs *DefsPerColorToUses,
786 AArch64FunctionInfo &AArch64FI, const MapRegToId &RegToId,
787 const MachineDominatorTree *MDT) {
788 SetOfMachineInstr *InvolvedInLOHs = nullptr;
790 SetOfMachineInstr InvolvedInLOHsStorage;
791 InvolvedInLOHs = &InvolvedInLOHsStorage;
793 DEBUG(dbgs() << "*** Compute LOH for Others\n");
794 // ADRP -> ADD/LDR -> LDR/STR pattern.
795 // Fall back to ADRP -> ADD pattern if we fail to catch the bigger pattern.
797 // FIXME: When the statistics are not important,
798 // This initial filtering loop can be merged into the next loop.
799 // Currently, we didn't do it to have the same code for both DEBUG and
800 // NDEBUG builds. Indeed, the iterator of the second loop would need
802 SetOfMachineInstr PotentialCandidates;
803 SetOfMachineInstr PotentialADROpportunities;
804 for (auto &Use : UseToDefs) {
805 // If no definition is available, this is a non candidate.
806 if (Use.second.empty())
808 // Keep only instructions that are load or store and at the end of
809 // a ADRP -> ADD/LDR/Nothing chain.
810 // We already filtered out the no-chain cases.
811 if (!isCandidate(Use.first, UseToDefs, MDT)) {
812 PotentialADROpportunities.insert(Use.first);
815 PotentialCandidates.insert(Use.first);
818 // Make the following distinctions for statistics as the linker does
819 // know how to decode instructions:
820 // - ADD/LDR/Nothing make there different patterns.
821 // - LDR/STR make two different patterns.
822 // Hence, 6 - 1 base patterns.
823 // (because ADRP-> Nothing -> STR is not simplifiable)
825 // The linker is only able to have a simple semantic, i.e., if pattern A
827 // However, we want to see the opportunity we may miss if we were able to
828 // catch more complex cases.
830 // PotentialCandidates are result of a chain ADRP -> ADD/LDR ->
831 // A potential candidate becomes a candidate, if its current immediate
832 // operand is zero and all nodes of the chain have respectively only one user
834 SetOfMachineInstr DefsOfPotentialCandidates;
836 for (const MachineInstr *Candidate : PotentialCandidates) {
837 // Get the definition of the candidate i.e., ADD or LDR.
838 const MachineInstr *Def = *UseToDefs.find(Candidate)->second.begin();
839 // Record the elements of the chain.
840 const MachineInstr *L1 = Def;
841 const MachineInstr *L2 = nullptr;
842 unsigned ImmediateDefOpc = Def->getOpcode();
843 if (Def->getOpcode() != AArch64::ADRP) {
844 // Check the number of users of this node.
845 const SetOfMachineInstr *Users =
846 getUses(DefsPerColorToUses,
847 RegToId.find(Def->getOperand(0).getReg())->second, *Def);
848 if (Users->size() > 1) {
850 // if all the uses of this def are in potential candidate, this is
851 // a complex candidate of level 2.
852 bool IsLevel2 = true;
853 for (const MachineInstr *MI : *Users) {
854 if (!PotentialCandidates.count(MI)) {
863 PotentialADROpportunities.insert(Def);
867 Def = *UseToDefs.find(Def)->second.begin();
869 } // else the element in the middle of the chain is nothing, thus
870 // Def already contains the first element of the chain.
872 // Check the number of users of the first node in the chain, i.e., ADRP
873 const SetOfMachineInstr *Users =
874 getUses(DefsPerColorToUses,
875 RegToId.find(Def->getOperand(0).getReg())->second, *Def);
876 if (Users->size() > 1) {
878 // if all the uses of this def are in the defs of the potential candidate,
879 // this is a complex candidate of level 1
880 if (DefsOfPotentialCandidates.empty()) {
882 DefsOfPotentialCandidates = PotentialCandidates;
883 for (const MachineInstr *Candidate : PotentialCandidates) {
884 if (!UseToDefs.find(Candidate)->second.empty())
885 DefsOfPotentialCandidates.insert(
886 *UseToDefs.find(Candidate)->second.begin());
890 for (auto &Use : *Users) {
891 if (!DefsOfPotentialCandidates.count(Use)) {
903 bool IsL2Add = (ImmediateDefOpc == AArch64::ADDXri);
904 // If the chain is three instructions long and ldr is the second element,
905 // then this ldr must load form GOT, otherwise this is not a correct chain.
906 if (L2 && !IsL2Add && L2->getOperand(2).getTargetFlags() != AArch64II::MO_GOT)
908 SmallVector<const MachineInstr *, 3> Args;
910 if (isCandidateLoad(Candidate)) {
912 // At this point, the candidate LOH indicates that the ldr instruction
913 // may use a direct access to the symbol. There is not such encoding
914 // for loads of byte and half.
915 if (!supportLoadFromLiteral(Candidate))
918 DEBUG(dbgs() << "Record AdrpLdr:\n" << *L1 << '\n' << *Candidate
920 Kind = MCLOH_AdrpLdr;
922 Args.push_back(Candidate);
923 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L1)) &&
924 "L1 already involved in LOH.");
925 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(Candidate)) &&
926 "Candidate already involved in LOH.");
929 DEBUG(dbgs() << "Record Adrp" << (IsL2Add ? "Add" : "LdrGot")
930 << "Ldr:\n" << *L1 << '\n' << *L2 << '\n' << *Candidate
933 Kind = IsL2Add ? MCLOH_AdrpAddLdr : MCLOH_AdrpLdrGotLdr;
936 Args.push_back(Candidate);
938 PotentialADROpportunities.remove(L2);
939 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L1)) &&
940 "L1 already involved in LOH.");
941 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L2)) &&
942 "L2 already involved in LOH.");
943 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(Candidate)) &&
944 "Candidate already involved in LOH.");
946 // get the immediate of the load
947 if (Candidate->getOperand(2).getImm() == 0)
948 if (ImmediateDefOpc == AArch64::ADDXri)
952 else if (ImmediateDefOpc == AArch64::ADDXri)
953 ++NumADDToLDRWithImm;
955 ++NumLDRToLDRWithImm;
959 if (ImmediateDefOpc == AArch64::ADRP)
963 DEBUG(dbgs() << "Record Adrp" << (IsL2Add ? "Add" : "LdrGot")
964 << "Str:\n" << *L1 << '\n' << *L2 << '\n' << *Candidate
967 Kind = IsL2Add ? MCLOH_AdrpAddStr : MCLOH_AdrpLdrGotStr;
970 Args.push_back(Candidate);
972 PotentialADROpportunities.remove(L2);
973 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L1)) &&
974 "L1 already involved in LOH.");
975 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(L2)) &&
976 "L2 already involved in LOH.");
977 assert((!InvolvedInLOHs || InvolvedInLOHs->insert(Candidate)) &&
978 "Candidate already involved in LOH.");
980 // get the immediate of the store
981 if (Candidate->getOperand(2).getImm() == 0)
982 if (ImmediateDefOpc == AArch64::ADDXri)
986 else if (ImmediateDefOpc == AArch64::ADDXri)
987 ++NumADDToSTRWithImm;
989 ++NumLDRToSTRWithImm;
993 AArch64FI.addLOHDirective(Kind, Args);
996 // Now, we grabbed all the big patterns, check ADR opportunities.
997 for (const MachineInstr *Candidate : PotentialADROpportunities)
998 registerADRCandidate(*Candidate, UseToDefs, DefsPerColorToUses, AArch64FI,
999 InvolvedInLOHs, RegToId);
1002 /// Look for every register defined by potential LOHs candidates.
1003 /// Map these registers with dense id in @p RegToId and vice-versa in
1004 /// @p IdToReg. @p IdToReg is populated only in DEBUG mode.
1005 static void collectInvolvedReg(MachineFunction &MF, MapRegToId &RegToId,
1006 MapIdToReg &IdToReg,
1007 const TargetRegisterInfo *TRI) {
1008 unsigned CurRegId = 0;
1009 if (!PreCollectRegister) {
1010 unsigned NbReg = TRI->getNumRegs();
1011 for (; CurRegId < NbReg; ++CurRegId) {
1012 RegToId[CurRegId] = CurRegId;
1013 DEBUG(IdToReg.push_back(CurRegId));
1014 DEBUG(assert(IdToReg[CurRegId] == CurRegId && "Reg index mismatches"));
1019 DEBUG(dbgs() << "** Collect Involved Register\n");
1020 for (const auto &MBB : MF) {
1021 for (const MachineInstr &MI : MBB) {
1022 if (!canDefBePartOfLOH(&MI))
1026 for (MachineInstr::const_mop_iterator IO = MI.operands_begin(),
1027 IOEnd = MI.operands_end();
1028 IO != IOEnd; ++IO) {
1029 if (!IO->isReg() || !IO->isDef())
1031 unsigned CurReg = IO->getReg();
1032 for (MCRegAliasIterator AI(CurReg, TRI, true); AI.isValid(); ++AI)
1033 if (RegToId.find(*AI) == RegToId.end()) {
1034 DEBUG(IdToReg.push_back(*AI);
1035 assert(IdToReg[CurRegId] == *AI &&
1036 "Reg index mismatches insertion index."));
1037 RegToId[*AI] = CurRegId++;
1038 DEBUG(dbgs() << "Register: " << PrintReg(*AI, TRI) << '\n');
1045 bool AArch64CollectLOH::runOnMachineFunction(MachineFunction &MF) {
1046 const TargetMachine &TM = MF.getTarget();
1047 const TargetRegisterInfo *TRI = TM.getSubtargetImpl()->getRegisterInfo();
1048 const MachineDominatorTree *MDT = &getAnalysis<MachineDominatorTree>();
1052 AArch64FunctionInfo *AArch64FI = MF.getInfo<AArch64FunctionInfo>();
1053 assert(AArch64FI && "No MachineFunctionInfo for this function!");
1055 DEBUG(dbgs() << "Looking for LOH in " << MF.getName() << '\n');
1057 collectInvolvedReg(MF, RegToId, IdToReg, TRI);
1058 if (RegToId.empty())
1061 MachineInstr *DummyOp = nullptr;
1062 if (BasicBlockScopeOnly) {
1063 const AArch64InstrInfo *TII = static_cast<const AArch64InstrInfo *>(
1064 TM.getSubtargetImpl()->getInstrInfo());
1065 // For local analysis, create a dummy operation to record uses that are not
1067 DummyOp = MF.CreateMachineInstr(TII->get(AArch64::COPY), DebugLoc());
1070 unsigned NbReg = RegToId.size();
1071 bool Modified = false;
1074 InstrToInstrs *ColorOpToReachedUses = new InstrToInstrs[NbReg];
1076 // Compute the reaching def in ADRP mode, meaning ADRP definitions
1077 // are first considered as uses.
1078 reachingDef(MF, ColorOpToReachedUses, RegToId, true, DummyOp);
1079 DEBUG(dbgs() << "ADRP reaching defs\n");
1080 DEBUG(printReachingDef(ColorOpToReachedUses, NbReg, TRI, IdToReg));
1082 // Translate the definition to uses map into a use to definitions map to ease
1083 // statistic computation.
1084 InstrToInstrs ADRPToReachingDefs;
1085 reachedUsesToDefs(ADRPToReachingDefs, ColorOpToReachedUses, RegToId, true);
1087 // Compute LOH for ADRP.
1088 computeADRP(ADRPToReachingDefs, *AArch64FI, MDT);
1089 delete[] ColorOpToReachedUses;
1091 // Continue with general ADRP -> ADD/LDR -> LDR/STR pattern.
1092 ColorOpToReachedUses = new InstrToInstrs[NbReg];
1094 // first perform a regular reaching def analysis.
1095 reachingDef(MF, ColorOpToReachedUses, RegToId, false, DummyOp);
1096 DEBUG(dbgs() << "All reaching defs\n");
1097 DEBUG(printReachingDef(ColorOpToReachedUses, NbReg, TRI, IdToReg));
1099 // Turn that into a use to defs to ease statistic computation.
1100 InstrToInstrs UsesToReachingDefs;
1101 reachedUsesToDefs(UsesToReachingDefs, ColorOpToReachedUses, RegToId, false);
1103 // Compute other than AdrpAdrp LOH.
1104 computeOthers(UsesToReachingDefs, ColorOpToReachedUses, *AArch64FI, RegToId,
1106 delete[] ColorOpToReachedUses;
1108 if (BasicBlockScopeOnly)
1109 MF.DeleteMachineInstr(DummyOp);
1114 /// createAArch64CollectLOHPass - returns an instance of the Statistic for
1115 /// linker optimization pass.
1116 FunctionPass *llvm::createAArch64CollectLOHPass() {
1117 return new AArch64CollectLOH();