AArch64PromoteConstant.cpp revision 360784 
1//==- AArch64PromoteConstant.cpp - Promote constant to global for AArch64 --==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the AArch64PromoteConstant pass which promotes constants
10// to global variables when this is likely to be more efficient. Currently only
11// types related to constant vector (i.e., constant vector, array of constant
12// vectors, constant structure with a constant vector field, etc.) are promoted
13// to global variables. Constant vectors are likely to be lowered in target
14// constant pool during instruction selection already; therefore, the access
15// will remain the same (memory load), but the structure types are not split
16// into different constant pool accesses for each field. A bonus side effect is
17// that created globals may be merged by the global merge pass.
18//
19// FIXME: This pass may be useful for other targets too.
20//===----------------------------------------------------------------------===//
21
22#include "AArch64.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/IR/BasicBlock.h"
27#include "llvm/IR/Constant.h"
28#include "llvm/IR/Constants.h"
29#include "llvm/IR/Dominators.h"
30#include "llvm/IR/Function.h"
31#include "llvm/IR/GlobalValue.h"
32#include "llvm/IR/GlobalVariable.h"
33#include "llvm/IR/IRBuilder.h"
34#include "llvm/IR/InlineAsm.h"
35#include "llvm/IR/InstIterator.h"
36#include "llvm/IR/Instruction.h"
37#include "llvm/IR/Instructions.h"
38#include "llvm/IR/IntrinsicInst.h"
39#include "llvm/IR/Module.h"
40#include "llvm/IR/Type.h"
41#include "llvm/InitializePasses.h"
42#include "llvm/Pass.h"
43#include "llvm/Support/Casting.h"
44#include "llvm/Support/CommandLine.h"
45#include "llvm/Support/Debug.h"
46#include "llvm/Support/raw_ostream.h"
47#include <algorithm>
48#include <cassert>
49#include <utility>
50
51using namespace llvm;
52
53#define DEBUG_TYPE "aarch64-promote-const"
54
55// Stress testing mode - disable heuristics.
56static cl::opt<bool> Stress("aarch64-stress-promote-const", cl::Hidden,
57                            cl::desc("Promote all vector constants"));
58
59STATISTIC(NumPromoted, "Number of promoted constants");
60STATISTIC(NumPromotedUses, "Number of promoted constants uses");
61
62//===----------------------------------------------------------------------===//
63//                       AArch64PromoteConstant
64//===----------------------------------------------------------------------===//
65
66namespace {
67
68/// Promotes interesting constant into global variables.
69/// The motivating example is:
70/// static const uint16_t TableA[32] = {
71///   41944, 40330, 38837, 37450, 36158, 34953, 33826, 32768,
72///   31776, 30841, 29960, 29128, 28340, 27595, 26887, 26215,
73///   25576, 24967, 24386, 23832, 23302, 22796, 22311, 21846,
74///   21400, 20972, 20561, 20165, 19785, 19419, 19066, 18725,
75/// };
76///
77/// uint8x16x4_t LoadStatic(void) {
78///   uint8x16x4_t ret;
79///   ret.val[0] = vld1q_u16(TableA +  0);
80///   ret.val[1] = vld1q_u16(TableA +  8);
81///   ret.val[2] = vld1q_u16(TableA + 16);
82///   ret.val[3] = vld1q_u16(TableA + 24);
83///   return ret;
84/// }
85///
86/// The constants in this example are folded into the uses. Thus, 4 different
87/// constants are created.
88///
89/// As their type is vector the cheapest way to create them is to load them
90/// for the memory.
91///
92/// Therefore the final assembly final has 4 different loads. With this pass
93/// enabled, only one load is issued for the constants.
94class AArch64PromoteConstant : public ModulePass {
95public:
96  struct PromotedConstant {
97    bool ShouldConvert = false;
98    GlobalVariable *GV = nullptr;
99  };
100  using PromotionCacheTy = SmallDenseMap<Constant *, PromotedConstant, 16>;
101
102  struct UpdateRecord {
103    Constant *C;
104    Instruction *User;
105    unsigned Op;
106
107    UpdateRecord(Constant *C, Instruction *User, unsigned Op)
108        : C(C), User(User), Op(Op) {}
109  };
110
111  static char ID;
112
113  AArch64PromoteConstant() : ModulePass(ID) {
114    initializeAArch64PromoteConstantPass(*PassRegistry::getPassRegistry());
115  }
116
117  StringRef getPassName() const override { return "AArch64 Promote Constant"; }
118
119  /// Iterate over the functions and promote the interesting constants into
120  /// global variables with module scope.
121  bool runOnModule(Module &M) override {
122    LLVM_DEBUG(dbgs() << getPassName() << '\n');
123    if (skipModule(M))
124      return false;
125    bool Changed = false;
126    PromotionCacheTy PromotionCache;
127    for (auto &MF : M) {
128      Changed |= runOnFunction(MF, PromotionCache);
129    }
130    return Changed;
131  }
132
133private:
134  /// Look for interesting constants used within the given function.
135  /// Promote them into global variables, load these global variables within
136  /// the related function, so that the number of inserted load is minimal.
137  bool runOnFunction(Function &F, PromotionCacheTy &PromotionCache);
138
139  // This transformation requires dominator info
140  void getAnalysisUsage(AnalysisUsage &AU) const override {
141    AU.setPreservesCFG();
142    AU.addRequired<DominatorTreeWrapperPass>();
143    AU.addPreserved<DominatorTreeWrapperPass>();
144  }
145
146  /// Type to store a list of Uses.
147  using Uses = SmallVector<std::pair<Instruction *, unsigned>, 4>;
148  /// Map an insertion point to all the uses it dominates.
149  using InsertionPoints = DenseMap<Instruction *, Uses>;
150
151  /// Find the closest point that dominates the given Use.
152  Instruction *findInsertionPoint(Instruction &User, unsigned OpNo);
153
154  /// Check if the given insertion point is dominated by an existing
155  /// insertion point.
156  /// If true, the given use is added to the list of dominated uses for
157  /// the related existing point.
158  /// \param NewPt the insertion point to be checked
159  /// \param User the user of the constant
160  /// \param OpNo the operand number of the use
161  /// \param InsertPts existing insertion points
162  /// \pre NewPt and all instruction in InsertPts belong to the same function
163  /// \return true if one of the insertion point in InsertPts dominates NewPt,
164  ///         false otherwise
165  bool isDominated(Instruction *NewPt, Instruction *User, unsigned OpNo,
166                   InsertionPoints &InsertPts);
167
168  /// Check if the given insertion point can be merged with an existing
169  /// insertion point in a common dominator.
170  /// If true, the given use is added to the list of the created insertion
171  /// point.
172  /// \param NewPt the insertion point to be checked
173  /// \param User the user of the constant
174  /// \param OpNo the operand number of the use
175  /// \param InsertPts existing insertion points
176  /// \pre NewPt and all instruction in InsertPts belong to the same function
177  /// \pre isDominated returns false for the exact same parameters.
178  /// \return true if it exists an insertion point in InsertPts that could
179  ///         have been merged with NewPt in a common dominator,
180  ///         false otherwise
181  bool tryAndMerge(Instruction *NewPt, Instruction *User, unsigned OpNo,
182                   InsertionPoints &InsertPts);
183
184  /// Compute the minimal insertion points to dominates all the interesting
185  /// uses of value.
186  /// Insertion points are group per function and each insertion point
187  /// contains a list of all the uses it dominates within the related function
188  /// \param User the user of the constant
189  /// \param OpNo the operand number of the constant
190  /// \param[out] InsertPts output storage of the analysis
191  void computeInsertionPoint(Instruction *User, unsigned OpNo,
192                             InsertionPoints &InsertPts);
193
194  /// Insert a definition of a new global variable at each point contained in
195  /// InsPtsPerFunc and update the related uses (also contained in
196  /// InsPtsPerFunc).
197  void insertDefinitions(Function &F, GlobalVariable &GV,
198                         InsertionPoints &InsertPts);
199
200  /// Do the constant promotion indicated by the Updates records, keeping track
201  /// of globals in PromotionCache.
202  void promoteConstants(Function &F, SmallVectorImpl<UpdateRecord> &Updates,
203                        PromotionCacheTy &PromotionCache);
204
205  /// Transfer the list of dominated uses of IPI to NewPt in InsertPts.
206  /// Append Use to this list and delete the entry of IPI in InsertPts.
207  static void appendAndTransferDominatedUses(Instruction *NewPt,
208                                             Instruction *User, unsigned OpNo,
209                                             InsertionPoints::iterator &IPI,
210                                             InsertionPoints &InsertPts) {
211    // Record the dominated use.
212    IPI->second.emplace_back(User, OpNo);
213    // Transfer the dominated uses of IPI to NewPt
214    // Inserting into the DenseMap may invalidate existing iterator.
215    // Keep a copy of the key to find the iterator to erase.  Keep a copy of the
216    // value so that we don't have to dereference IPI->second.
217    Instruction *OldInstr = IPI->first;
218    Uses OldUses = std::move(IPI->second);
219    InsertPts[NewPt] = std::move(OldUses);
220    // Erase IPI.
221    InsertPts.erase(OldInstr);
222  }
223};
224
225} // end anonymous namespace
226
227char AArch64PromoteConstant::ID = 0;
228
229INITIALIZE_PASS_BEGIN(AArch64PromoteConstant, "aarch64-promote-const",
230                      "AArch64 Promote Constant Pass", false, false)
231INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
232INITIALIZE_PASS_END(AArch64PromoteConstant, "aarch64-promote-const",
233                    "AArch64 Promote Constant Pass", false, false)
234
235ModulePass *llvm::createAArch64PromoteConstantPass() {
236  return new AArch64PromoteConstant();
237}
238
239/// Check if the given type uses a vector type.
240static bool isConstantUsingVectorTy(const Type *CstTy) {
241  if (CstTy->isVectorTy())
242    return true;
243  if (CstTy->isStructTy()) {
244    for (unsigned EltIdx = 0, EndEltIdx = CstTy->getStructNumElements();
245         EltIdx < EndEltIdx; ++EltIdx)
246      if (isConstantUsingVectorTy(CstTy->getStructElementType(EltIdx)))
247        return true;
248  } else if (CstTy->isArrayTy())
249    return isConstantUsingVectorTy(CstTy->getArrayElementType());
250  return false;
251}
252
253/// Check if the given use (Instruction + OpIdx) of Cst should be converted into
254/// a load of a global variable initialized with Cst.
255/// A use should be converted if it is legal to do so.
256/// For instance, it is not legal to turn the mask operand of a shuffle vector
257/// into a load of a global variable.
258static bool shouldConvertUse(const Constant *Cst, const Instruction *Instr,
259                             unsigned OpIdx) {
260  // shufflevector instruction expects a const for the mask argument, i.e., the
261  // third argument. Do not promote this use in that case.
262  if (isa<const ShuffleVectorInst>(Instr) && OpIdx == 2)
263    return false;
264
265  // extractvalue instruction expects a const idx.
266  if (isa<const ExtractValueInst>(Instr) && OpIdx > 0)
267    return false;
268
269  // extractvalue instruction expects a const idx.
270  if (isa<const InsertValueInst>(Instr) && OpIdx > 1)
271    return false;
272
273  if (isa<const AllocaInst>(Instr) && OpIdx > 0)
274    return false;
275
276  // Alignment argument must be constant.
277  if (isa<const LoadInst>(Instr) && OpIdx > 0)
278    return false;
279
280  // Alignment argument must be constant.
281  if (isa<const StoreInst>(Instr) && OpIdx > 1)
282    return false;
283
284  // Index must be constant.
285  if (isa<const GetElementPtrInst>(Instr) && OpIdx > 0)
286    return false;
287
288  // Personality function and filters must be constant.
289  // Give up on that instruction.
290  if (isa<const LandingPadInst>(Instr))
291    return false;
292
293  // Switch instruction expects constants to compare to.
294  if (isa<const SwitchInst>(Instr))
295    return false;
296
297  // Expected address must be a constant.
298  if (isa<const IndirectBrInst>(Instr))
299    return false;
300
301  // Do not mess with intrinsics.
302  if (isa<const IntrinsicInst>(Instr))
303    return false;
304
305  // Do not mess with inline asm.
306  const CallInst *CI = dyn_cast<const CallInst>(Instr);
307  return !(CI && isa<const InlineAsm>(CI->getCalledValue()));
308}
309
310/// Check if the given Cst should be converted into
311/// a load of a global variable initialized with Cst.
312/// A constant should be converted if it is likely that the materialization of
313/// the constant will be tricky. Thus, we give up on zero or undef values.
314///
315/// \todo Currently, accept only vector related types.
316/// Also we give up on all simple vector type to keep the existing
317/// behavior. Otherwise, we should push here all the check of the lowering of
318/// BUILD_VECTOR. By giving up, we lose the potential benefit of merging
319/// constant via global merge and the fact that the same constant is stored
320/// only once with this method (versus, as many function that uses the constant
321/// for the regular approach, even for float).
322/// Again, the simplest solution would be to promote every
323/// constant and rematerialize them when they are actually cheap to create.
324static bool shouldConvertImpl(const Constant *Cst) {
325  if (isa<const UndefValue>(Cst))
326    return false;
327
328  // FIXME: In some cases, it may be interesting to promote in memory
329  // a zero initialized constant.
330  // E.g., when the type of Cst require more instructions than the
331  // adrp/add/load sequence or when this sequence can be shared by several
332  // instances of Cst.
333  // Ideally, we could promote this into a global and rematerialize the constant
334  // when it was a bad idea.
335  if (Cst->isZeroValue())
336    return false;
337
338  if (Stress)
339    return true;
340
341  // FIXME: see function \todo
342  if (Cst->getType()->isVectorTy())
343    return false;
344  return isConstantUsingVectorTy(Cst->getType());
345}
346
347static bool
348shouldConvert(Constant &C,
349              AArch64PromoteConstant::PromotionCacheTy &PromotionCache) {
350  auto Converted = PromotionCache.insert(
351      std::make_pair(&C, AArch64PromoteConstant::PromotedConstant()));
352  if (Converted.second)
353    Converted.first->second.ShouldConvert = shouldConvertImpl(&C);
354  return Converted.first->second.ShouldConvert;
355}
356
357Instruction *AArch64PromoteConstant::findInsertionPoint(Instruction &User,
358                                                        unsigned OpNo) {
359  // If this user is a phi, the insertion point is in the related
360  // incoming basic block.
361  if (PHINode *PhiInst = dyn_cast<PHINode>(&User))
362    return PhiInst->getIncomingBlock(OpNo)->getTerminator();
363
364  return &User;
365}
366
367bool AArch64PromoteConstant::isDominated(Instruction *NewPt, Instruction *User,
368                                         unsigned OpNo,
369                                         InsertionPoints &InsertPts) {
370  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(
371      *NewPt->getParent()->getParent()).getDomTree();
372
373  // Traverse all the existing insertion points and check if one is dominating
374  // NewPt. If it is, remember that.
375  for (auto &IPI : InsertPts) {
376    if (NewPt == IPI.first || DT.dominates(IPI.first, NewPt) ||
377        // When IPI.first is a terminator instruction, DT may think that
378        // the result is defined on the edge.
379        // Here we are testing the insertion point, not the definition.
380        (IPI.first->getParent() != NewPt->getParent() &&
381         DT.dominates(IPI.first->getParent(), NewPt->getParent()))) {
382      // No need to insert this point. Just record the dominated use.
383      LLVM_DEBUG(dbgs() << "Insertion point dominated by:\n");
384      LLVM_DEBUG(IPI.first->print(dbgs()));
385      LLVM_DEBUG(dbgs() << '\n');
386      IPI.second.emplace_back(User, OpNo);
387      return true;
388    }
389  }
390  return false;
391}
392
393bool AArch64PromoteConstant::tryAndMerge(Instruction *NewPt, Instruction *User,
394                                         unsigned OpNo,
395                                         InsertionPoints &InsertPts) {
396  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(
397      *NewPt->getParent()->getParent()).getDomTree();
398  BasicBlock *NewBB = NewPt->getParent();
399
400  // Traverse all the existing insertion point and check if one is dominated by
401  // NewPt and thus useless or can be combined with NewPt into a common
402  // dominator.
403  for (InsertionPoints::iterator IPI = InsertPts.begin(),
404                                 EndIPI = InsertPts.end();
405       IPI != EndIPI; ++IPI) {
406    BasicBlock *CurBB = IPI->first->getParent();
407    if (NewBB == CurBB) {
408      // Instructions are in the same block.
409      // By construction, NewPt is dominating the other.
410      // Indeed, isDominated returned false with the exact same arguments.
411      LLVM_DEBUG(dbgs() << "Merge insertion point with:\n");
412      LLVM_DEBUG(IPI->first->print(dbgs()));
413      LLVM_DEBUG(dbgs() << "\nat considered insertion point.\n");
414      appendAndTransferDominatedUses(NewPt, User, OpNo, IPI, InsertPts);
415      return true;
416    }
417
418    // Look for a common dominator
419    BasicBlock *CommonDominator = DT.findNearestCommonDominator(NewBB, CurBB);
420    // If none exists, we cannot merge these two points.
421    if (!CommonDominator)
422      continue;
423
424    if (CommonDominator != NewBB) {
425      // By construction, the CommonDominator cannot be CurBB.
426      assert(CommonDominator != CurBB &&
427             "Instruction has not been rejected during isDominated check!");
428      // Take the last instruction of the CommonDominator as insertion point
429      NewPt = CommonDominator->getTerminator();
430    }
431    // else, CommonDominator is the block of NewBB, hence NewBB is the last
432    // possible insertion point in that block.
433    LLVM_DEBUG(dbgs() << "Merge insertion point with:\n");
434    LLVM_DEBUG(IPI->first->print(dbgs()));
435    LLVM_DEBUG(dbgs() << '\n');
436    LLVM_DEBUG(NewPt->print(dbgs()));
437    LLVM_DEBUG(dbgs() << '\n');
438    appendAndTransferDominatedUses(NewPt, User, OpNo, IPI, InsertPts);
439    return true;
440  }
441  return false;
442}
443
444void AArch64PromoteConstant::computeInsertionPoint(
445    Instruction *User, unsigned OpNo, InsertionPoints &InsertPts) {
446  LLVM_DEBUG(dbgs() << "Considered use, opidx " << OpNo << ":\n");
447  LLVM_DEBUG(User->print(dbgs()));
448  LLVM_DEBUG(dbgs() << '\n');
449
450  Instruction *InsertionPoint = findInsertionPoint(*User, OpNo);
451
452  LLVM_DEBUG(dbgs() << "Considered insertion point:\n");
453  LLVM_DEBUG(InsertionPoint->print(dbgs()));
454  LLVM_DEBUG(dbgs() << '\n');
455
456  if (isDominated(InsertionPoint, User, OpNo, InsertPts))
457    return;
458  // This insertion point is useful, check if we can merge some insertion
459  // point in a common dominator or if NewPt dominates an existing one.
460  if (tryAndMerge(InsertionPoint, User, OpNo, InsertPts))
461    return;
462
463  LLVM_DEBUG(dbgs() << "Keep considered insertion point\n");
464
465  // It is definitely useful by its own
466  InsertPts[InsertionPoint].emplace_back(User, OpNo);
467}
468
469static void ensurePromotedGV(Function &F, Constant &C,
470                             AArch64PromoteConstant::PromotedConstant &PC) {
471  assert(PC.ShouldConvert &&
472         "Expected that we should convert this to a global");
473  if (PC.GV)
474    return;
475  PC.GV = new GlobalVariable(
476      *F.getParent(), C.getType(), true, GlobalValue::InternalLinkage, nullptr,
477      "_PromotedConst", nullptr, GlobalVariable::NotThreadLocal);
478  PC.GV->setInitializer(&C);
479  LLVM_DEBUG(dbgs() << "Global replacement: ");
480  LLVM_DEBUG(PC.GV->print(dbgs()));
481  LLVM_DEBUG(dbgs() << '\n');
482  ++NumPromoted;
483}
484
485void AArch64PromoteConstant::insertDefinitions(Function &F,
486                                               GlobalVariable &PromotedGV,
487                                               InsertionPoints &InsertPts) {
488#ifndef NDEBUG
489  // Do more checking for debug purposes.
490  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
491#endif
492  assert(!InsertPts.empty() && "Empty uses does not need a definition");
493
494  for (const auto &IPI : InsertPts) {
495    // Create the load of the global variable.
496    IRBuilder<> Builder(IPI.first);
497    LoadInst *LoadedCst =
498        Builder.CreateLoad(PromotedGV.getValueType(), &PromotedGV);
499    LLVM_DEBUG(dbgs() << "**********\n");
500    LLVM_DEBUG(dbgs() << "New def: ");
501    LLVM_DEBUG(LoadedCst->print(dbgs()));
502    LLVM_DEBUG(dbgs() << '\n');
503
504    // Update the dominated uses.
505    for (auto Use : IPI.second) {
506#ifndef NDEBUG
507      assert(DT.dominates(LoadedCst,
508                          findInsertionPoint(*Use.first, Use.second)) &&
509             "Inserted definition does not dominate all its uses!");
510#endif
511      LLVM_DEBUG({
512        dbgs() << "Use to update " << Use.second << ":";
513        Use.first->print(dbgs());
514        dbgs() << '\n';
515      });
516      Use.first->setOperand(Use.second, LoadedCst);
517      ++NumPromotedUses;
518    }
519  }
520}
521
522void AArch64PromoteConstant::promoteConstants(
523    Function &F, SmallVectorImpl<UpdateRecord> &Updates,
524    PromotionCacheTy &PromotionCache) {
525  // Promote the constants.
526  for (auto U = Updates.begin(), E = Updates.end(); U != E;) {
527    LLVM_DEBUG(dbgs() << "** Compute insertion points **\n");
528    auto First = U;
529    Constant *C = First->C;
530    InsertionPoints InsertPts;
531    do {
532      computeInsertionPoint(U->User, U->Op, InsertPts);
533    } while (++U != E && U->C == C);
534
535    auto &Promotion = PromotionCache[C];
536    ensurePromotedGV(F, *C, Promotion);
537    insertDefinitions(F, *Promotion.GV, InsertPts);
538  }
539}
540
541bool AArch64PromoteConstant::runOnFunction(Function &F,
542                                           PromotionCacheTy &PromotionCache) {
543  // Look for instructions using constant vector. Promote that constant to a
544  // global variable. Create as few loads of this variable as possible and
545  // update the uses accordingly.
546  SmallVector<UpdateRecord, 64> Updates;
547  for (Instruction &I : instructions(&F)) {
548    // Traverse the operand, looking for constant vectors. Replace them by a
549    // load of a global variable of constant vector type.
550    for (Use &U : I.operands()) {
551      Constant *Cst = dyn_cast<Constant>(U);
552      // There is no point in promoting global values as they are already
553      // global. Do not promote constant expressions either, as they may
554      // require some code expansion.
555      if (!Cst || isa<GlobalValue>(Cst) || isa<ConstantExpr>(Cst))
556        continue;
557
558      // Check if this constant is worth promoting.
559      if (!shouldConvert(*Cst, PromotionCache))
560        continue;
561
562      // Check if this use should be promoted.
563      unsigned OpNo = &U - I.op_begin();
564      if (!shouldConvertUse(Cst, &I, OpNo))
565        continue;
566
567      Updates.emplace_back(Cst, &I, OpNo);
568    }
569  }
570
571  if (Updates.empty())
572    return false;
573
574  promoteConstants(F, Updates, PromotionCache);
575  return true;
576}
577