2 //===-- ARM64PromoteConstant.cpp --- Promote constant to global for ARM64 -===//
4 // The LLVM Compiler Infrastructure
6 // This file is distributed under the University of Illinois Open Source
7 // License. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 // This file implements the ARM64PromoteConstant pass which promotes constants
12 // to global variables when this is likely to be more efficient. Currently only
13 // types related to constant vector (i.e., constant vector, array of constant
14 // vectors, constant structure with a constant vector field, etc.) are promoted
15 // to global variables. Constant vectors are likely to be lowered in target
16 // constant pool during instruction selection already; therefore, the access
17 // will remain the same (memory load), but the structure types are not split
18 // into different constant pool accesses for each field. A bonus side effect is
19 // that created globals may be merged by the global merge pass.
21 // FIXME: This pass may be useful for other targets too.
22 //===----------------------------------------------------------------------===//
24 #define DEBUG_TYPE "arm64-promote-const"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/IR/Constants.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/InlineAsm.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/IntrinsicInst.h"
37 #include "llvm/IR/IRBuilder.h"
38 #include "llvm/IR/Module.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
45 // Stress testing mode - disable heuristics.
46 static cl::opt<bool> Stress("arm64-stress-promote-const", cl::Hidden,
47 cl::desc("Promote all vector constants"));
49 STATISTIC(NumPromoted, "Number of promoted constants");
50 STATISTIC(NumPromotedUses, "Number of promoted constants uses");
52 //===----------------------------------------------------------------------===//
53 // ARM64PromoteConstant
54 //===----------------------------------------------------------------------===//
57 /// Promotes interesting constant into global variables.
58 /// The motivating example is:
59 /// static const uint16_t TableA[32] = {
60 /// 41944, 40330, 38837, 37450, 36158, 34953, 33826, 32768,
61 /// 31776, 30841, 29960, 29128, 28340, 27595, 26887, 26215,
62 /// 25576, 24967, 24386, 23832, 23302, 22796, 22311, 21846,
63 /// 21400, 20972, 20561, 20165, 19785, 19419, 19066, 18725,
66 /// uint8x16x4_t LoadStatic(void) {
68 /// ret.val[0] = vld1q_u16(TableA + 0);
69 /// ret.val[1] = vld1q_u16(TableA + 8);
70 /// ret.val[2] = vld1q_u16(TableA + 16);
71 /// ret.val[3] = vld1q_u16(TableA + 24);
75 /// The constants in this example are folded into the uses. Thus, 4 different
76 /// constants are created.
78 /// As their type is vector the cheapest way to create them is to load them
81 /// Therefore the final assembly final has 4 different loads. With this pass
82 /// enabled, only one load is issued for the constants.
83 class ARM64PromoteConstant : public ModulePass {
87 ARM64PromoteConstant() : ModulePass(ID) {}
89 virtual const char *getPassName() const { return "ARM64 Promote Constant"; }
91 /// Iterate over the functions and promote the interesting constants into
92 /// global variables with module scope.
93 bool runOnModule(Module &M) {
94 DEBUG(dbgs() << getPassName() << '\n');
97 Changed |= runOnFunction(MF);
103 /// Look for interesting constants used within the given function.
104 /// Promote them into global variables, load these global variables within
105 /// the related function, so that the number of inserted load is minimal.
106 bool runOnFunction(Function &F);
108 // This transformation requires dominator info
109 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
110 AU.setPreservesCFG();
111 AU.addRequired<DominatorTreeWrapperPass>();
112 AU.addPreserved<DominatorTreeWrapperPass>();
115 /// Type to store a list of User.
116 typedef SmallVector<Value::user_iterator, 4> Users;
117 /// Map an insertion point to all the uses it dominates.
118 typedef DenseMap<Instruction *, Users> InsertionPoints;
119 /// Map a function to the required insertion point of load for a
121 typedef DenseMap<Function *, InsertionPoints> InsertionPointsPerFunc;
123 /// Find the closest point that dominates the given Use.
124 Instruction *findInsertionPoint(Value::user_iterator &Use);
126 /// Check if the given insertion point is dominated by an existing
128 /// If true, the given use is added to the list of dominated uses for
129 /// the related existing point.
130 /// \param NewPt the insertion point to be checked
131 /// \param UseIt the use to be added into the list of dominated uses
132 /// \param InsertPts existing insertion points
133 /// \pre NewPt and all instruction in InsertPts belong to the same function
134 /// \return true if one of the insertion point in InsertPts dominates NewPt,
136 bool isDominated(Instruction *NewPt, Value::user_iterator &UseIt,
137 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 UseIt 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, Value::user_iterator &UseIt,
152 InsertionPoints &InsertPts);
154 /// Compute the minimal insertion points to dominates all the interesting
156 /// Insertion points are group per function and each insertion point
157 /// contains a list of all the uses it dominates within the related function
158 /// \param Val constant to be examined
159 /// \param[out] InsPtsPerFunc output storage of the analysis
160 void computeInsertionPoints(Constant *Val,
161 InsertionPointsPerFunc &InsPtsPerFunc);
163 /// Insert a definition of a new global variable at each point contained in
164 /// InsPtsPerFunc and update the related uses (also contained in
166 bool insertDefinitions(Constant *Cst, InsertionPointsPerFunc &InsPtsPerFunc);
168 /// Compute the minimal insertion points to dominate all the interesting
169 /// uses of Val and insert a definition of a new global variable
171 /// Also update the uses of Val accordingly.
172 /// Currently a use of Val is considered interesting if:
173 /// - Val is not UndefValue
174 /// - Val is not zeroinitialized
175 /// - Replacing Val per a load of a global variable is valid.
176 /// \see shouldConvert for more details
177 bool computeAndInsertDefinitions(Constant *Val);
179 /// Promote the given constant into a global variable if it is expected to
181 /// \return true if Cst has been promoted
182 bool promoteConstant(Constant *Cst);
184 /// Transfer the list of dominated uses of IPI to NewPt in InsertPts.
185 /// Append UseIt to this list and delete the entry of IPI in InsertPts.
186 static void appendAndTransferDominatedUses(Instruction *NewPt,
187 Value::user_iterator &UseIt,
188 InsertionPoints::iterator &IPI,
189 InsertionPoints &InsertPts) {
190 // Record the dominated use.
191 IPI->second.push_back(UseIt);
192 // Transfer the dominated uses of IPI to NewPt
193 // Inserting into the DenseMap may invalidate existing iterator.
194 // Keep a copy of the key to find the iterator to erase.
195 Instruction *OldInstr = IPI->first;
196 InsertPts.insert(InsertionPoints::value_type(NewPt, IPI->second));
198 IPI = InsertPts.find(OldInstr);
199 InsertPts.erase(IPI);
202 } // end anonymous namespace
204 char ARM64PromoteConstant::ID = 0;
207 void initializeARM64PromoteConstantPass(PassRegistry &);
210 INITIALIZE_PASS_BEGIN(ARM64PromoteConstant, "arm64-promote-const",
211 "ARM64 Promote Constant Pass", false, false)
212 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
213 INITIALIZE_PASS_END(ARM64PromoteConstant, "arm64-promote-const",
214 "ARM64 Promote Constant Pass", false, false)
216 ModulePass *llvm::createARM64PromoteConstantPass() {
217 return new ARM64PromoteConstant();
220 /// Check if the given type uses a vector type.
221 static bool isConstantUsingVectorTy(const Type *CstTy) {
222 if (CstTy->isVectorTy())
224 if (CstTy->isStructTy()) {
225 for (unsigned EltIdx = 0, EndEltIdx = CstTy->getStructNumElements();
226 EltIdx < EndEltIdx; ++EltIdx)
227 if (isConstantUsingVectorTy(CstTy->getStructElementType(EltIdx)))
229 } else if (CstTy->isArrayTy())
230 return isConstantUsingVectorTy(CstTy->getArrayElementType());
234 /// Check if the given use (Instruction + OpIdx) of Cst should be converted into
235 /// a load of a global variable initialized with Cst.
236 /// A use should be converted if it is legal to do so.
237 /// For instance, it is not legal to turn the mask operand of a shuffle vector
238 /// into a load of a global variable.
239 static bool shouldConvertUse(const Constant *Cst, const Instruction *Instr,
241 // shufflevector instruction expects a const for the mask argument, i.e., the
242 // third argument. Do not promote this use in that case.
243 if (isa<const ShuffleVectorInst>(Instr) && OpIdx == 2)
246 // extractvalue instruction expects a const idx.
247 if (isa<const ExtractValueInst>(Instr) && OpIdx > 0)
250 // extractvalue instruction expects a const idx.
251 if (isa<const InsertValueInst>(Instr) && OpIdx > 1)
254 if (isa<const AllocaInst>(Instr) && OpIdx > 0)
257 // Alignment argument must be constant.
258 if (isa<const LoadInst>(Instr) && OpIdx > 0)
261 // Alignment argument must be constant.
262 if (isa<const StoreInst>(Instr) && OpIdx > 1)
265 // Index must be constant.
266 if (isa<const GetElementPtrInst>(Instr) && OpIdx > 0)
269 // Personality function and filters must be constant.
270 // Give up on that instruction.
271 if (isa<const LandingPadInst>(Instr))
274 // Switch instruction expects constants to compare to.
275 if (isa<const SwitchInst>(Instr))
278 // Expected address must be a constant.
279 if (isa<const IndirectBrInst>(Instr))
282 // Do not mess with intrinsics.
283 if (isa<const IntrinsicInst>(Instr))
286 // Do not mess with inline asm.
287 const CallInst *CI = dyn_cast<const CallInst>(Instr);
288 if (CI && isa<const InlineAsm>(CI->getCalledValue()))
294 /// Check if the given Cst should be converted into
295 /// a load of a global variable initialized with Cst.
296 /// A constant should be converted if it is likely that the materialization of
297 /// the constant will be tricky. Thus, we give up on zero or undef values.
299 /// \todo Currently, accept only vector related types.
300 /// Also we give up on all simple vector type to keep the existing
301 /// behavior. Otherwise, we should push here all the check of the lowering of
302 /// BUILD_VECTOR. By giving up, we lose the potential benefit of merging
303 /// constant via global merge and the fact that the same constant is stored
304 /// only once with this method (versus, as many function that uses the constant
305 /// for the regular approach, even for float).
306 /// Again, the simplest solution would be to promote every
307 /// constant and rematerialize them when they are actually cheap to create.
308 static bool shouldConvert(const Constant *Cst) {
309 if (isa<const UndefValue>(Cst))
312 // FIXME: In some cases, it may be interesting to promote in memory
313 // a zero initialized constant.
314 // E.g., when the type of Cst require more instructions than the
315 // adrp/add/load sequence or when this sequence can be shared by several
317 // Ideally, we could promote this into a global and rematerialize the constant
318 // when it was a bad idea.
319 if (Cst->isZeroValue())
325 // FIXME: see function \todo
326 if (Cst->getType()->isVectorTy())
328 return isConstantUsingVectorTy(Cst->getType());
332 ARM64PromoteConstant::findInsertionPoint(Value::user_iterator &Use) {
333 // If this user is a phi, the insertion point is in the related
334 // incoming basic block.
335 PHINode *PhiInst = dyn_cast<PHINode>(*Use);
336 Instruction *InsertionPoint;
339 PhiInst->getIncomingBlock(Use.getOperandNo())->getTerminator();
341 InsertionPoint = dyn_cast<Instruction>(*Use);
342 assert(InsertionPoint && "User is not an instruction!");
343 return InsertionPoint;
346 bool ARM64PromoteConstant::isDominated(Instruction *NewPt,
347 Value::user_iterator &UseIt,
348 InsertionPoints &InsertPts) {
350 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(
351 *NewPt->getParent()->getParent()).getDomTree();
353 // Traverse all the existing insertion points and check if one is dominating
354 // NewPt. If it is, remember that.
355 for (auto &IPI : InsertPts) {
356 if (NewPt == IPI.first || DT.dominates(IPI.first, NewPt) ||
357 // When IPI.first is a terminator instruction, DT may think that
358 // the result is defined on the edge.
359 // Here we are testing the insertion point, not the definition.
360 (IPI.first->getParent() != NewPt->getParent() &&
361 DT.dominates(IPI.first->getParent(), NewPt->getParent()))) {
362 // No need to insert this point. Just record the dominated use.
363 DEBUG(dbgs() << "Insertion point dominated by:\n");
364 DEBUG(IPI.first->print(dbgs()));
365 DEBUG(dbgs() << '\n');
366 IPI.second.push_back(UseIt);
373 bool ARM64PromoteConstant::tryAndMerge(Instruction *NewPt,
374 Value::user_iterator &UseIt,
375 InsertionPoints &InsertPts) {
376 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(
377 *NewPt->getParent()->getParent()).getDomTree();
378 BasicBlock *NewBB = NewPt->getParent();
380 // Traverse all the existing insertion point and check if one is dominated by
381 // NewPt and thus useless or can be combined with NewPt into a common
383 for (InsertionPoints::iterator IPI = InsertPts.begin(),
384 EndIPI = InsertPts.end();
385 IPI != EndIPI; ++IPI) {
386 BasicBlock *CurBB = IPI->first->getParent();
387 if (NewBB == CurBB) {
388 // Instructions are in the same block.
389 // By construction, NewPt is dominating the other.
390 // Indeed, isDominated returned false with the exact same arguments.
391 DEBUG(dbgs() << "Merge insertion point with:\n");
392 DEBUG(IPI->first->print(dbgs()));
393 DEBUG(dbgs() << "\nat considered insertion point.\n");
394 appendAndTransferDominatedUses(NewPt, UseIt, IPI, InsertPts);
398 // Look for a common dominator
399 BasicBlock *CommonDominator = DT.findNearestCommonDominator(NewBB, CurBB);
400 // If none exists, we cannot merge these two points.
401 if (!CommonDominator)
404 if (CommonDominator != NewBB) {
405 // By construction, the CommonDominator cannot be CurBB.
406 assert(CommonDominator != CurBB &&
407 "Instruction has not been rejected during isDominated check!");
408 // Take the last instruction of the CommonDominator as insertion point
409 NewPt = CommonDominator->getTerminator();
411 // else, CommonDominator is the block of NewBB, hence NewBB is the last
412 // possible insertion point in that block.
413 DEBUG(dbgs() << "Merge insertion point with:\n");
414 DEBUG(IPI->first->print(dbgs()));
415 DEBUG(dbgs() << '\n');
416 DEBUG(NewPt->print(dbgs()));
417 DEBUG(dbgs() << '\n');
418 appendAndTransferDominatedUses(NewPt, UseIt, IPI, InsertPts);
424 void ARM64PromoteConstant::computeInsertionPoints(
425 Constant *Val, InsertionPointsPerFunc &InsPtsPerFunc) {
426 DEBUG(dbgs() << "** Compute insertion points **\n");
427 for (Value::user_iterator UseIt = Val->user_begin(),
428 EndUseIt = Val->user_end();
429 UseIt != EndUseIt; ++UseIt) {
430 // If the user is not an Instruction, we cannot modify it.
431 if (!isa<Instruction>(*UseIt))
434 // Filter out uses that should not be converted.
435 if (!shouldConvertUse(Val, cast<Instruction>(*UseIt), UseIt.getOperandNo()))
438 DEBUG(dbgs() << "Considered use, opidx " << UseIt.getOperandNo() << ":\n");
439 DEBUG((*UseIt)->print(dbgs()));
440 DEBUG(dbgs() << '\n');
442 Instruction *InsertionPoint = findInsertionPoint(UseIt);
444 DEBUG(dbgs() << "Considered insertion point:\n");
445 DEBUG(InsertionPoint->print(dbgs()));
446 DEBUG(dbgs() << '\n');
448 // Check if the current insertion point is useless, i.e., it is dominated
450 InsertionPoints &InsertPts =
451 InsPtsPerFunc[InsertionPoint->getParent()->getParent()];
452 if (isDominated(InsertionPoint, UseIt, InsertPts))
454 // This insertion point is useful, check if we can merge some insertion
455 // point in a common dominator or if NewPt dominates an existing one.
456 if (tryAndMerge(InsertionPoint, UseIt, InsertPts))
459 DEBUG(dbgs() << "Keep considered insertion point\n");
461 // It is definitely useful by its own
462 InsertPts[InsertionPoint].push_back(UseIt);
467 ARM64PromoteConstant::insertDefinitions(Constant *Cst,
468 InsertionPointsPerFunc &InsPtsPerFunc) {
469 // We will create one global variable per Module.
470 DenseMap<Module *, GlobalVariable *> ModuleToMergedGV;
471 bool HasChanged = false;
473 // Traverse all insertion points in all the function.
474 for (InsertionPointsPerFunc::iterator FctToInstPtsIt = InsPtsPerFunc.begin(),
475 EndIt = InsPtsPerFunc.end();
476 FctToInstPtsIt != EndIt; ++FctToInstPtsIt) {
477 InsertionPoints &InsertPts = FctToInstPtsIt->second;
478 // Do more checking for debug purposes.
480 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>(
481 *FctToInstPtsIt->first).getDomTree();
483 GlobalVariable *PromotedGV;
484 assert(!InsertPts.empty() && "Empty uses does not need a definition");
486 Module *M = FctToInstPtsIt->first->getParent();
487 DenseMap<Module *, GlobalVariable *>::iterator MapIt =
488 ModuleToMergedGV.find(M);
489 if (MapIt == ModuleToMergedGV.end()) {
490 PromotedGV = new GlobalVariable(
491 *M, Cst->getType(), true, GlobalValue::InternalLinkage, 0,
492 "_PromotedConst", 0, GlobalVariable::NotThreadLocal);
493 PromotedGV->setInitializer(Cst);
494 ModuleToMergedGV[M] = PromotedGV;
495 DEBUG(dbgs() << "Global replacement: ");
496 DEBUG(PromotedGV->print(dbgs()));
497 DEBUG(dbgs() << '\n');
501 PromotedGV = MapIt->second;
504 for (InsertionPoints::iterator IPI = InsertPts.begin(),
505 EndIPI = InsertPts.end();
506 IPI != EndIPI; ++IPI) {
507 // Create the load of the global variable.
508 IRBuilder<> Builder(IPI->first->getParent(), IPI->first);
509 LoadInst *LoadedCst = Builder.CreateLoad(PromotedGV);
510 DEBUG(dbgs() << "**********\n");
511 DEBUG(dbgs() << "New def: ");
512 DEBUG(LoadedCst->print(dbgs()));
513 DEBUG(dbgs() << '\n');
515 // Update the dominated uses.
516 Users &DominatedUsers = IPI->second;
517 for (Users::iterator UseIt = DominatedUsers.begin(),
518 EndIt = DominatedUsers.end();
519 UseIt != EndIt; ++UseIt) {
521 assert((DT.dominates(LoadedCst, cast<Instruction>(**UseIt)) ||
522 (isa<PHINode>(**UseIt) &&
523 DT.dominates(LoadedCst, findInsertionPoint(*UseIt)))) &&
524 "Inserted definition does not dominate all its uses!");
526 DEBUG(dbgs() << "Use to update " << UseIt->getOperandNo() << ":");
527 DEBUG((*UseIt)->print(dbgs()));
528 DEBUG(dbgs() << '\n');
529 (*UseIt)->setOperand(UseIt->getOperandNo(), LoadedCst);
537 bool ARM64PromoteConstant::computeAndInsertDefinitions(Constant *Val) {
538 InsertionPointsPerFunc InsertPtsPerFunc;
539 computeInsertionPoints(Val, InsertPtsPerFunc);
540 return insertDefinitions(Val, InsertPtsPerFunc);
543 bool ARM64PromoteConstant::promoteConstant(Constant *Cst) {
544 assert(Cst && "Given variable is not a valid constant.");
546 if (!shouldConvert(Cst))
549 DEBUG(dbgs() << "******************************\n");
550 DEBUG(dbgs() << "Candidate constant: ");
551 DEBUG(Cst->print(dbgs()));
552 DEBUG(dbgs() << '\n');
554 return computeAndInsertDefinitions(Cst);
557 bool ARM64PromoteConstant::runOnFunction(Function &F) {
558 // Look for instructions using constant vector. Promote that constant to a
559 // global variable. Create as few loads of this variable as possible and
560 // update the uses accordingly.
561 bool LocalChange = false;
562 SmallSet<Constant *, 8> AlreadyChecked;
564 for (auto &MBB : F) {
565 for (auto &MI : MBB) {
566 // Traverse the operand, looking for constant vectors. Replace them by a
567 // load of a global variable of constant vector type.
568 for (unsigned OpIdx = 0, EndOpIdx = MI.getNumOperands();
569 OpIdx != EndOpIdx; ++OpIdx) {
570 Constant *Cst = dyn_cast<Constant>(MI.getOperand(OpIdx));
571 // There is no point in promoting global values as they are already
572 // global. Do not promote constant expressions either, as they may
573 // require some code expansion.
574 if (Cst && !isa<GlobalValue>(Cst) && !isa<ConstantExpr>(Cst) &&
575 AlreadyChecked.insert(Cst))
576 LocalChange |= promoteConstant(Cst);