1 //=- AArch64PromoteConstant.cpp --- Promote constant to global for AArch64 -==//
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 implements the AArch64PromoteConstant pass which promotes constants
11 // to global variables when this is likely to be more efficient. Currently only
12 // types related to constant vector (i.e., constant vector, array of constant
13 // vectors, constant structure with a constant vector field, etc.) are promoted
14 // to global variables. Constant vectors are likely to be lowered in target
15 // constant pool during instruction selection already; therefore, the access
16 // will remain the same (memory load), but the structure types are not split
17 // into different constant pool accesses for each field. A bonus side effect is
18 // that created globals may be merged by the global merge pass.
20 // FIXME: This pass may be useful for other targets too.
21 //===----------------------------------------------------------------------===//
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/ADT/Statistic.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/Function.h"
31 #include "llvm/IR/GlobalVariable.h"
32 #include "llvm/IR/IRBuilder.h"
33 #include "llvm/IR/InlineAsm.h"
34 #include "llvm/IR/InstIterator.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/IntrinsicInst.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
44 #define DEBUG_TYPE "aarch64-promote-const"
46 // Stress testing mode - disable heuristics.
47 static cl::opt<bool> Stress("aarch64-stress-promote-const", cl::Hidden,
48 cl::desc("Promote all vector constants"));
50 STATISTIC(NumPromoted, "Number of promoted constants");
51 STATISTIC(NumPromotedUses, "Number of promoted constants uses");
53 //===----------------------------------------------------------------------===//
54 // AArch64PromoteConstant
55 //===----------------------------------------------------------------------===//
58 /// Promotes interesting constant into global variables.
59 /// The motivating example is:
60 /// static const uint16_t TableA[32] = {
61 /// 41944, 40330, 38837, 37450, 36158, 34953, 33826, 32768,
62 /// 31776, 30841, 29960, 29128, 28340, 27595, 26887, 26215,
63 /// 25576, 24967, 24386, 23832, 23302, 22796, 22311, 21846,
64 /// 21400, 20972, 20561, 20165, 19785, 19419, 19066, 18725,
67 /// uint8x16x4_t LoadStatic(void) {
69 /// ret.val[0] = vld1q_u16(TableA + 0);
70 /// ret.val[1] = vld1q_u16(TableA + 8);
71 /// ret.val[2] = vld1q_u16(TableA + 16);
72 /// ret.val[3] = vld1q_u16(TableA + 24);
76 /// The constants in this example are folded into the uses. Thus, 4 different
77 /// constants are created.
79 /// As their type is vector the cheapest way to create them is to load them
82 /// Therefore the final assembly final has 4 different loads. With this pass
83 /// enabled, only one load is issued for the constants.
84 class AArch64PromoteConstant : public ModulePass {
88 AArch64PromoteConstant() : ModulePass(ID) {}
90 const char *getPassName() const override { return "AArch64 Promote Constant"; }
92 /// Iterate over the functions and promote the interesting constants into
93 /// global variables with module scope.
94 bool runOnModule(Module &M) override {
95 DEBUG(dbgs() << getPassName() << '\n');
98 Changed |= runOnFunction(MF);
104 /// Look for interesting constants used within the given function.
105 /// Promote them into global variables, load these global variables within
106 /// the related function, so that the number of inserted load is minimal.
107 bool runOnFunction(Function &F);
109 // This transformation requires dominator info
110 void getAnalysisUsage(AnalysisUsage &AU) const override {
111 AU.setPreservesCFG();
112 AU.addRequired<DominatorTreeWrapperPass>();
113 AU.addPreserved<DominatorTreeWrapperPass>();
116 /// Type to store a list of Uses.
117 typedef SmallVector<Use *, 4> Uses;
118 /// Map an insertion point to all the uses it dominates.
119 typedef DenseMap<Instruction *, Uses> InsertionPoints;
120 /// Map a function to the required insertion point of load for a
122 typedef DenseMap<Function *, InsertionPoints> InsertionPointsPerFunc;
124 /// Find the closest point that dominates the given Use.
125 Instruction *findInsertionPoint(Use &Use);
127 /// Check if the given insertion point is dominated by an existing
129 /// If true, the given use is added to the list of dominated uses for
130 /// the related existing point.
131 /// \param NewPt the insertion point to be checked
132 /// \param Use the use to be added into the list of dominated uses
133 /// \param InsertPts existing insertion points
134 /// \pre NewPt and all instruction in InsertPts belong to the same function
135 /// \return true if one of the insertion point in InsertPts dominates NewPt,
137 bool isDominated(Instruction *NewPt, Use &Use, InsertionPoints &InsertPts);
139 /// Check if the given insertion point can be merged with an existing
140 /// insertion point in a common dominator.
141 /// If true, the given use is added to the list of the created insertion
143 /// \param NewPt the insertion point to be checked
144 /// \param Use the use to be added into the list of dominated uses
145 /// \param InsertPts existing insertion points
146 /// \pre NewPt and all instruction in InsertPts belong to the same function
147 /// \pre isDominated returns false for the exact same parameters.
148 /// \return true if it exists an insertion point in InsertPts that could
149 /// have been merged with NewPt in a common dominator,
151 bool tryAndMerge(Instruction *NewPt, Use &Use, InsertionPoints &InsertPts);
153 /// Compute the minimal insertion points to dominates all the interesting
155 /// Insertion points are group per function and each insertion point
156 /// contains a list of all the uses it dominates within the related function
157 /// \param Val constant to be examined
158 /// \param[out] InsPtsPerFunc output storage of the analysis
159 void computeInsertionPoints(Constant *Val,
160 InsertionPointsPerFunc &InsPtsPerFunc);
162 /// Insert a definition of a new global variable at each point contained in
163 /// InsPtsPerFunc and update the related uses (also contained in
165 bool insertDefinitions(Constant *Cst, InsertionPointsPerFunc &InsPtsPerFunc);
167 /// Compute the minimal insertion points to dominate all the interesting
168 /// uses of Val and insert a definition of a new global variable
170 /// Also update the uses of Val accordingly.
171 /// Currently a use of Val is considered interesting if:
172 /// - Val is not UndefValue
173 /// - Val is not zeroinitialized
174 /// - Replacing Val per a load of a global variable is valid.
175 /// \see shouldConvert for more details
176 bool computeAndInsertDefinitions(Constant *Val);
178 /// Promote the given constant into a global variable if it is expected to
180 /// \return true if Cst has been promoted
181 bool promoteConstant(Constant *Cst);
183 /// Transfer the list of dominated uses of IPI to NewPt in InsertPts.
184 /// Append Use to this list and delete the entry of IPI in InsertPts.
185 static void appendAndTransferDominatedUses(Instruction *NewPt, Use &Use,
186 InsertionPoints::iterator &IPI,
187 InsertionPoints &InsertPts) {
188 // Record the dominated use.
189 IPI->second.push_back(&Use);
190 // Transfer the dominated uses of IPI to NewPt
191 // Inserting into the DenseMap may invalidate existing iterator.
192 // Keep a copy of the key to find the iterator to erase.
193 Instruction *OldInstr = IPI->first;
194 InsertPts[NewPt] = std::move(IPI->second);
196 InsertPts.erase(OldInstr);
199 } // end anonymous namespace
201 char AArch64PromoteConstant::ID = 0;
204 void initializeAArch64PromoteConstantPass(PassRegistry &);
207 INITIALIZE_PASS_BEGIN(AArch64PromoteConstant, "aarch64-promote-const",
208 "AArch64 Promote Constant Pass", false, false)
209 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
210 INITIALIZE_PASS_END(AArch64PromoteConstant, "aarch64-promote-const",
211 "AArch64 Promote Constant Pass", false, false)
213 ModulePass *llvm::createAArch64PromoteConstantPass() {
214 return new AArch64PromoteConstant();
217 /// Check if the given type uses a vector type.
218 static bool isConstantUsingVectorTy(const Type *CstTy) {
219 if (CstTy->isVectorTy())
221 if (CstTy->isStructTy()) {
222 for (unsigned EltIdx = 0, EndEltIdx = CstTy->getStructNumElements();
223 EltIdx < EndEltIdx; ++EltIdx)
224 if (isConstantUsingVectorTy(CstTy->getStructElementType(EltIdx)))
226 } else if (CstTy->isArrayTy())
227 return isConstantUsingVectorTy(CstTy->getArrayElementType());
231 /// Check if the given use (Instruction + OpIdx) of Cst should be converted into
232 /// a load of a global variable initialized with Cst.
233 /// A use should be converted if it is legal to do so.
234 /// For instance, it is not legal to turn the mask operand of a shuffle vector
235 /// into a load of a global variable.
236 static bool shouldConvertUse(const Constant *Cst, const Instruction *Instr,
238 // shufflevector instruction expects a const for the mask argument, i.e., the
239 // third argument. Do not promote this use in that case.
240 if (isa<const ShuffleVectorInst>(Instr) && OpIdx == 2)
243 // extractvalue instruction expects a const idx.
244 if (isa<const ExtractValueInst>(Instr) && OpIdx > 0)
247 // extractvalue instruction expects a const idx.
248 if (isa<const InsertValueInst>(Instr) && OpIdx > 1)
251 if (isa<const AllocaInst>(Instr) && OpIdx > 0)
254 // Alignment argument must be constant.
255 if (isa<const LoadInst>(Instr) && OpIdx > 0)
258 // Alignment argument must be constant.
259 if (isa<const StoreInst>(Instr) && OpIdx > 1)
262 // Index must be constant.
263 if (isa<const GetElementPtrInst>(Instr) && OpIdx > 0)
266 // Personality function and filters must be constant.
267 // Give up on that instruction.
268 if (isa<const LandingPadInst>(Instr))
271 // Switch instruction expects constants to compare to.
272 if (isa<const SwitchInst>(Instr))
275 // Expected address must be a constant.
276 if (isa<const IndirectBrInst>(Instr))
279 // Do not mess with intrinsics.
280 if (isa<const IntrinsicInst>(Instr))
283 // Do not mess with inline asm.
284 const CallInst *CI = dyn_cast<const CallInst>(Instr);
285 if (CI && isa<const InlineAsm>(CI->getCalledValue()))
291 /// Check if the given Cst should be converted into
292 /// a load of a global variable initialized with Cst.
293 /// A constant should be converted if it is likely that the materialization of
294 /// the constant will be tricky. Thus, we give up on zero or undef values.
296 /// \todo Currently, accept only vector related types.
297 /// Also we give up on all simple vector type to keep the existing
298 /// behavior. Otherwise, we should push here all the check of the lowering of
299 /// BUILD_VECTOR. By giving up, we lose the potential benefit of merging
300 /// constant via global merge and the fact that the same constant is stored
301 /// only once with this method (versus, as many function that uses the constant
302 /// for the regular approach, even for float).
303 /// Again, the simplest solution would be to promote every
304 /// constant and rematerialize them when they are actually cheap to create.
305 static bool shouldConvert(const Constant *Cst) {
306 if (isa<const UndefValue>(Cst))
309 // FIXME: In some cases, it may be interesting to promote in memory
310 // a zero initialized constant.
311 // E.g., when the type of Cst require more instructions than the
312 // adrp/add/load sequence or when this sequence can be shared by several
314 // Ideally, we could promote this into a global and rematerialize the constant
315 // when it was a bad idea.
316 if (Cst->isZeroValue())
322 // FIXME: see function \todo
323 if (Cst->getType()->isVectorTy())
325 return isConstantUsingVectorTy(Cst->getType());
328 Instruction *AArch64PromoteConstant::findInsertionPoint(Use &Use) {
329 Instruction *User = cast<Instruction>(Use.getUser());
331 // If this user is a phi, the insertion point is in the related
332 // incoming basic block.
333 if (PHINode *PhiInst = dyn_cast<PHINode>(User))
334 return PhiInst->getIncomingBlock(Use.getOperandNo())->getTerminator();
339 bool AArch64PromoteConstant::isDominated(Instruction *NewPt, Use &Use,
340 InsertionPoints &InsertPts) {
342 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(
343 *NewPt->getParent()->getParent()).getDomTree();
345 // Traverse all the existing insertion points and check if one is dominating
346 // NewPt. If it is, remember that.
347 for (auto &IPI : InsertPts) {
348 if (NewPt == IPI.first || DT.dominates(IPI.first, NewPt) ||
349 // When IPI.first is a terminator instruction, DT may think that
350 // the result is defined on the edge.
351 // Here we are testing the insertion point, not the definition.
352 (IPI.first->getParent() != NewPt->getParent() &&
353 DT.dominates(IPI.first->getParent(), NewPt->getParent()))) {
354 // No need to insert this point. Just record the dominated use.
355 DEBUG(dbgs() << "Insertion point dominated by:\n");
356 DEBUG(IPI.first->print(dbgs()));
357 DEBUG(dbgs() << '\n');
358 IPI.second.push_back(&Use);
365 bool AArch64PromoteConstant::tryAndMerge(Instruction *NewPt, Use &Use,
366 InsertionPoints &InsertPts) {
367 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(
368 *NewPt->getParent()->getParent()).getDomTree();
369 BasicBlock *NewBB = NewPt->getParent();
371 // Traverse all the existing insertion point and check if one is dominated by
372 // NewPt and thus useless or can be combined with NewPt into a common
374 for (InsertionPoints::iterator IPI = InsertPts.begin(),
375 EndIPI = InsertPts.end();
376 IPI != EndIPI; ++IPI) {
377 BasicBlock *CurBB = IPI->first->getParent();
378 if (NewBB == CurBB) {
379 // Instructions are in the same block.
380 // By construction, NewPt is dominating the other.
381 // Indeed, isDominated returned false with the exact same arguments.
382 DEBUG(dbgs() << "Merge insertion point with:\n");
383 DEBUG(IPI->first->print(dbgs()));
384 DEBUG(dbgs() << "\nat considered insertion point.\n");
385 appendAndTransferDominatedUses(NewPt, Use, IPI, InsertPts);
389 // Look for a common dominator
390 BasicBlock *CommonDominator = DT.findNearestCommonDominator(NewBB, CurBB);
391 // If none exists, we cannot merge these two points.
392 if (!CommonDominator)
395 if (CommonDominator != NewBB) {
396 // By construction, the CommonDominator cannot be CurBB.
397 assert(CommonDominator != CurBB &&
398 "Instruction has not been rejected during isDominated check!");
399 // Take the last instruction of the CommonDominator as insertion point
400 NewPt = CommonDominator->getTerminator();
402 // else, CommonDominator is the block of NewBB, hence NewBB is the last
403 // possible insertion point in that block.
404 DEBUG(dbgs() << "Merge insertion point with:\n");
405 DEBUG(IPI->first->print(dbgs()));
406 DEBUG(dbgs() << '\n');
407 DEBUG(NewPt->print(dbgs()));
408 DEBUG(dbgs() << '\n');
409 appendAndTransferDominatedUses(NewPt, Use, IPI, InsertPts);
415 void AArch64PromoteConstant::computeInsertionPoints(
416 Constant *Val, InsertionPointsPerFunc &InsPtsPerFunc) {
417 DEBUG(dbgs() << "** Compute insertion points **\n");
418 for (Use &Use : Val->uses()) {
419 Instruction *User = dyn_cast<Instruction>(Use.getUser());
421 // If the user is not an Instruction, we cannot modify it.
425 // Filter out uses that should not be converted.
426 if (!shouldConvertUse(Val, User, Use.getOperandNo()))
429 DEBUG(dbgs() << "Considered use, opidx " << Use.getOperandNo() << ":\n");
430 DEBUG(User->print(dbgs()));
431 DEBUG(dbgs() << '\n');
433 Instruction *InsertionPoint = findInsertionPoint(Use);
435 DEBUG(dbgs() << "Considered insertion point:\n");
436 DEBUG(InsertionPoint->print(dbgs()));
437 DEBUG(dbgs() << '\n');
439 // Check if the current insertion point is useless, i.e., it is dominated
441 InsertionPoints &InsertPts =
442 InsPtsPerFunc[InsertionPoint->getParent()->getParent()];
443 if (isDominated(InsertionPoint, Use, InsertPts))
445 // This insertion point is useful, check if we can merge some insertion
446 // point in a common dominator or if NewPt dominates an existing one.
447 if (tryAndMerge(InsertionPoint, Use, InsertPts))
450 DEBUG(dbgs() << "Keep considered insertion point\n");
452 // It is definitely useful by its own
453 InsertPts[InsertionPoint].push_back(&Use);
457 bool AArch64PromoteConstant::insertDefinitions(
458 Constant *Cst, InsertionPointsPerFunc &InsPtsPerFunc) {
459 // We will create one global variable per Module.
460 DenseMap<Module *, GlobalVariable *> ModuleToMergedGV;
461 bool HasChanged = false;
463 // Traverse all insertion points in all the function.
464 for (const auto &FctToInstPtsIt : InsPtsPerFunc) {
465 const InsertionPoints &InsertPts = FctToInstPtsIt.second;
466 // Do more checking for debug purposes.
468 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(
469 *FctToInstPtsIt.first).getDomTree();
471 assert(!InsertPts.empty() && "Empty uses does not need a definition");
473 Module *M = FctToInstPtsIt.first->getParent();
474 GlobalVariable *&PromotedGV = ModuleToMergedGV[M];
476 PromotedGV = new GlobalVariable(
477 *M, Cst->getType(), true, GlobalValue::InternalLinkage, nullptr,
478 "_PromotedConst", nullptr, GlobalVariable::NotThreadLocal);
479 PromotedGV->setInitializer(Cst);
480 DEBUG(dbgs() << "Global replacement: ");
481 DEBUG(PromotedGV->print(dbgs()));
482 DEBUG(dbgs() << '\n');
487 for (const auto &IPI : InsertPts) {
488 // Create the load of the global variable.
489 IRBuilder<> Builder(IPI.first->getParent(), IPI.first);
490 LoadInst *LoadedCst = Builder.CreateLoad(PromotedGV);
491 DEBUG(dbgs() << "**********\n");
492 DEBUG(dbgs() << "New def: ");
493 DEBUG(LoadedCst->print(dbgs()));
494 DEBUG(dbgs() << '\n');
496 // Update the dominated uses.
497 for (Use *Use : IPI.second) {
499 assert(DT.dominates(LoadedCst, findInsertionPoint(*Use)) &&
500 "Inserted definition does not dominate all its uses!");
502 DEBUG(dbgs() << "Use to update " << Use->getOperandNo() << ":");
503 DEBUG(Use->getUser()->print(dbgs()));
504 DEBUG(dbgs() << '\n');
513 bool AArch64PromoteConstant::computeAndInsertDefinitions(Constant *Val) {
514 InsertionPointsPerFunc InsertPtsPerFunc;
515 computeInsertionPoints(Val, InsertPtsPerFunc);
516 return insertDefinitions(Val, InsertPtsPerFunc);
519 bool AArch64PromoteConstant::promoteConstant(Constant *Cst) {
520 assert(Cst && "Given variable is not a valid constant.");
522 if (!shouldConvert(Cst))
525 DEBUG(dbgs() << "******************************\n");
526 DEBUG(dbgs() << "Candidate constant: ");
527 DEBUG(Cst->print(dbgs()));
528 DEBUG(dbgs() << '\n');
530 return computeAndInsertDefinitions(Cst);
533 bool AArch64PromoteConstant::runOnFunction(Function &F) {
534 // Look for instructions using constant vector. Promote that constant to a
535 // global variable. Create as few loads of this variable as possible and
536 // update the uses accordingly.
537 bool LocalChange = false;
538 SmallPtrSet<Constant *, 8> AlreadyChecked;
540 for (Instruction &I : inst_range(&F)) {
541 // Traverse the operand, looking for constant vectors. Replace them by a
542 // load of a global variable of constant vector type.
543 for (Value *Op : I.operand_values()) {
544 Constant *Cst = dyn_cast<Constant>(Op);
545 // There is no point in promoting global values as they are already
546 // global. Do not promote constant expressions either, as they may
547 // require some code expansion.
548 if (Cst && !isa<GlobalValue>(Cst) && !isa<ConstantExpr>(Cst) &&
549 AlreadyChecked.insert(Cst).second)
550 LocalChange |= promoteConstant(Cst);