2 //===-- ARM64AddressTypePromotion.cpp --- Promote type for addr accesses -===//
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 pass tries to promote the computations use to obtained a sign extended
12 // value used into memory accesses.
14 // a = add nsw i32 b, 3
15 // d = sext i32 a to i64
16 // e = getelementptr ..., i64 d
19 // f = sext i32 b to i64
20 // a = add nsw i64 f, 3
21 // e = getelementptr ..., i64 a
23 // This is legal to do so if the computations are markers with either nsw or nuw
25 // Moreover, the current heuristic is simple: it does not create new sext
26 // operations, i.e., it gives up when a sext would have forked (e.g., if
27 // a = add i32 b, c, two sexts are required to promote the computation).
29 // FIXME: This pass may be useful for other targets too.
30 // ===---------------------------------------------------------------------===//
32 #define DEBUG_TYPE "arm64-type-promotion"
34 #include "llvm/ADT/DenseMap.h"
35 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/ADT/SmallVector.h"
37 #include "llvm/IR/Constants.h"
38 #include "llvm/IR/Dominators.h"
39 #include "llvm/IR/Function.h"
40 #include "llvm/IR/Instructions.h"
41 #include "llvm/IR/Module.h"
42 #include "llvm/IR/Operator.h"
43 #include "llvm/Pass.h"
44 #include "llvm/Support/CommandLine.h"
45 #include "llvm/Support/Debug.h"
50 EnableAddressTypePromotion("arm64-type-promotion", cl::Hidden,
51 cl::desc("Enable the type promotion pass"),
54 EnableMerge("arm64-type-promotion-merge", cl::Hidden,
55 cl::desc("Enable merging of redundant sexts when one is dominating"
59 //===----------------------------------------------------------------------===//
60 // ARM64AddressTypePromotion
61 //===----------------------------------------------------------------------===//
64 void initializeARM64AddressTypePromotionPass(PassRegistry &);
68 class ARM64AddressTypePromotion : public FunctionPass {
72 ARM64AddressTypePromotion()
73 : FunctionPass(ID), Func(NULL), ConsideredSExtType(NULL) {
74 initializeARM64AddressTypePromotionPass(*PassRegistry::getPassRegistry());
77 virtual const char *getPassName() const {
78 return "ARM64 Address Type Promotion";
81 /// Iterate over the functions and promote the computation of interesting
83 bool runOnFunction(Function &F);
86 /// The current function.
88 /// Filter out all sexts that does not have this type.
89 /// Currently initialized with Int64Ty.
90 Type *ConsideredSExtType;
92 // This transformation requires dominator info.
93 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
95 AU.addRequired<DominatorTreeWrapperPass>();
96 AU.addPreserved<DominatorTreeWrapperPass>();
97 FunctionPass::getAnalysisUsage(AU);
100 typedef SmallPtrSet<Instruction *, 32> SetOfInstructions;
101 typedef SmallVector<Instruction *, 16> Instructions;
102 typedef DenseMap<Value *, Instructions> ValueToInsts;
104 /// Check if it is profitable to move a sext through this instruction.
105 /// Currently, we consider it is profitable if:
106 /// - Inst is used only once (no need to insert truncate).
107 /// - Inst has only one operand that will require a sext operation (we do
108 /// do not create new sext operation).
109 bool shouldGetThrough(const Instruction *Inst);
111 /// Check if it is possible and legal to move a sext through this
113 /// Current heuristic considers that we can get through:
114 /// - Arithmetic operation marked with the nsw or nuw flag.
115 /// - Other sext operation.
116 /// - Truncate operation if it was just dropping sign extended bits.
117 bool canGetThrough(const Instruction *Inst);
119 /// Move sext operations through safe to sext instructions.
120 bool propagateSignExtension(Instructions &SExtInsts);
122 /// Is this sext should be considered for code motion.
123 /// We look for sext with ConsideredSExtType and uses in at least one
124 // GetElementPtrInst.
125 bool shouldConsiderSExt(const Instruction *SExt) const;
127 /// Collect all interesting sext operations, i.e., the ones with the right
128 /// type and used in memory accesses.
129 /// More precisely, a sext instruction is considered as interesting if it
130 /// is used in a "complex" getelementptr or it exits at least another
131 /// sext instruction that sign extended the same initial value.
132 /// A getelementptr is considered as "complex" if it has more than 2
134 void analyzeSExtension(Instructions &SExtInsts);
136 /// Merge redundant sign extension operations in common dominator.
137 void mergeSExts(ValueToInsts &ValToSExtendedUses,
138 SetOfInstructions &ToRemove);
140 } // end anonymous namespace.
142 char ARM64AddressTypePromotion::ID = 0;
144 INITIALIZE_PASS_BEGIN(ARM64AddressTypePromotion, "arm64-type-promotion",
145 "ARM64 Type Promotion Pass", false, false)
146 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
147 INITIALIZE_PASS_END(ARM64AddressTypePromotion, "arm64-type-promotion",
148 "ARM64 Type Promotion Pass", false, false)
150 FunctionPass *llvm::createARM64AddressTypePromotionPass() {
151 return new ARM64AddressTypePromotion();
154 bool ARM64AddressTypePromotion::canGetThrough(const Instruction *Inst) {
155 if (isa<SExtInst>(Inst))
158 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
159 if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
160 (BinOp->hasNoUnsignedWrap() || BinOp->hasNoSignedWrap()))
163 // sext(trunc(sext)) --> sext
164 if (isa<TruncInst>(Inst) && isa<SExtInst>(Inst->getOperand(0))) {
165 const Instruction *Opnd = cast<Instruction>(Inst->getOperand(0));
166 // Check that the truncate just drop sign extended bits.
167 if (Inst->getType()->getIntegerBitWidth() >=
168 Opnd->getOperand(0)->getType()->getIntegerBitWidth() &&
169 Inst->getOperand(0)->getType()->getIntegerBitWidth() <=
170 ConsideredSExtType->getIntegerBitWidth())
177 bool ARM64AddressTypePromotion::shouldGetThrough(const Instruction *Inst) {
178 // If the type of the sext is the same as the considered one, this sext
179 // will become useless.
180 // Otherwise, we will have to do something to preserve the original value,
181 // unless it is used once.
182 if (isa<SExtInst>(Inst) &&
183 (Inst->getType() == ConsideredSExtType || Inst->hasOneUse()))
186 // If the Inst is used more that once, we may need to insert truncate
187 // operations and we don't do that at the moment.
188 if (!Inst->hasOneUse())
191 // This truncate is used only once, thus if we can get thourgh, it will become
193 if (isa<TruncInst>(Inst))
196 // If both operands are not constant, a new sext will be created here.
197 // Current heuristic is: each step should be profitable.
198 // Therefore we don't allow to increase the number of sext even if it may
199 // be profitable later on.
200 if (isa<BinaryOperator>(Inst) && isa<ConstantInt>(Inst->getOperand(1)))
206 static bool shouldSExtOperand(const Instruction *Inst, int OpIdx) {
207 if (isa<SelectInst>(Inst) && OpIdx == 0)
213 ARM64AddressTypePromotion::shouldConsiderSExt(const Instruction *SExt) const {
214 if (SExt->getType() != ConsideredSExtType)
217 for (Value::const_use_iterator UseIt = SExt->use_begin(),
218 EndUseIt = SExt->use_end();
219 UseIt != EndUseIt; ++UseIt) {
220 if (isa<GetElementPtrInst>(*UseIt))
228 // - SExtInsts contains all the sext instructions that are use direclty in
229 // GetElementPtrInst, i.e., access to memory.
231 // - For each sext operation in SExtInsts:
232 // Let var be the operand of sext.
233 // while it is profitable (see shouldGetThrough), legal, and safe
234 // (see canGetThrough) to move sext through var's definition:
235 // * promote the type of var's definition.
236 // * fold var into sext uses.
237 // * move sext above var's definition.
238 // * update sext operand to use the operand of var that should be sign
239 // extended (by construction there is only one).
243 // b = sext i32 a to i64 <- is it legal/safe/profitable to get through 'a'
246 // => Yes, update the code
247 // b = sext i32 c to i64
253 ARM64AddressTypePromotion::propagateSignExtension(Instructions &SExtInsts) {
254 DEBUG(dbgs() << "*** Propagate Sign Extension ***\n");
256 bool LocalChange = false;
257 SetOfInstructions ToRemove;
258 ValueToInsts ValToSExtendedUses;
259 while (!SExtInsts.empty()) {
260 // Get through simple chain.
261 Instruction *SExt = SExtInsts.pop_back_val();
263 DEBUG(dbgs() << "Consider:\n" << *SExt << '\n');
265 // If this SExt has already been merged continue.
266 if (SExt->use_empty() && ToRemove.count(SExt)) {
267 DEBUG(dbgs() << "No uses => marked as delete\n");
271 // Now try to get through the chain of definitions.
272 while (isa<Instruction>(SExt->getOperand(0))) {
273 Instruction *Inst = dyn_cast<Instruction>(SExt->getOperand(0));
274 DEBUG(dbgs() << "Try to get through:\n" << *Inst << '\n');
275 if (!canGetThrough(Inst) || !shouldGetThrough(Inst)) {
276 // We cannot get through something that is not an Instruction
277 // or not safe to SExt.
278 DEBUG(dbgs() << "Cannot get through\n");
283 // If this is a sign extend, it becomes useless.
284 if (isa<SExtInst>(Inst) || isa<TruncInst>(Inst)) {
285 DEBUG(dbgs() << "SExt or trunc, mark it as to remove\n");
286 // We cannot use replaceAllUsesWith here because we may trigger some
287 // assertion on the type as all involved sext operation may have not
289 while (!Inst->use_empty()) {
290 Value::use_iterator UseIt = Inst->use_begin();
291 Instruction *UseInst = dyn_cast<Instruction>(*UseIt);
292 assert(UseInst && "Use of sext is not an Instruction!");
293 UseInst->setOperand(UseIt->getOperandNo(), SExt);
295 ToRemove.insert(Inst);
296 SExt->setOperand(0, Inst->getOperand(0));
297 SExt->moveBefore(Inst);
301 // Get through the Instruction:
302 // 1. Update its type.
303 // 2. Replace the uses of SExt by Inst.
304 // 3. Sign extend each operand that needs to be sign extended.
307 Inst->mutateType(SExt->getType());
309 SExt->replaceAllUsesWith(Inst);
311 Instruction *SExtForOpnd = SExt;
313 DEBUG(dbgs() << "Propagate SExt to operands\n");
314 for (int OpIdx = 0, EndOpIdx = Inst->getNumOperands(); OpIdx != EndOpIdx;
316 DEBUG(dbgs() << "Operand:\n" << *(Inst->getOperand(OpIdx)) << '\n');
317 if (Inst->getOperand(OpIdx)->getType() == SExt->getType() ||
318 !shouldSExtOperand(Inst, OpIdx)) {
319 DEBUG(dbgs() << "No need to propagate\n");
322 // Check if we can statically sign extend the operand.
323 Value *Opnd = Inst->getOperand(OpIdx);
324 if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
325 DEBUG(dbgs() << "Statically sign extend\n");
326 Inst->setOperand(OpIdx, ConstantInt::getSigned(SExt->getType(),
327 Cst->getSExtValue()));
330 // UndefValue are typed, so we have to statically sign extend them.
331 if (isa<UndefValue>(Opnd)) {
332 DEBUG(dbgs() << "Statically sign extend\n");
333 Inst->setOperand(OpIdx, UndefValue::get(SExt->getType()));
337 // Otherwise we have to explicity sign extend it.
338 assert(SExtForOpnd &&
339 "Only one operand should have been sign extended");
341 SExtForOpnd->setOperand(0, Opnd);
343 DEBUG(dbgs() << "Move before:\n" << *Inst << "\nSign extend\n");
344 // Move the sign extension before the insertion point.
345 SExtForOpnd->moveBefore(Inst);
346 Inst->setOperand(OpIdx, SExtForOpnd);
347 // If more sext are required, new instructions will have to be created.
350 if (SExtForOpnd == SExt) {
351 DEBUG(dbgs() << "Sign extension is useless now\n");
352 ToRemove.insert(SExt);
357 // If the use is already of the right type, connect its uses to its argument
359 // This can happen for an Instruction which all uses are sign extended.
360 if (!ToRemove.count(SExt) &&
361 SExt->getType() == SExt->getOperand(0)->getType()) {
362 DEBUG(dbgs() << "Sign extension is useless, attach its use to "
364 SExt->replaceAllUsesWith(SExt->getOperand(0));
365 ToRemove.insert(SExt);
367 ValToSExtendedUses[SExt->getOperand(0)].push_back(SExt);
371 mergeSExts(ValToSExtendedUses, ToRemove);
373 // Remove all instructions marked as ToRemove.
374 for (Instruction *I: ToRemove)
375 I->eraseFromParent();
379 void ARM64AddressTypePromotion::mergeSExts(ValueToInsts &ValToSExtendedUses,
380 SetOfInstructions &ToRemove) {
381 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
383 for (auto &Entry: ValToSExtendedUses) {
384 Instructions &Insts = Entry.second;
386 for (Instruction *Inst : Insts) {
387 if (ToRemove.count(Inst))
389 bool inserted = false;
390 for (auto Pt : CurPts) {
391 if (DT.dominates(Inst, Pt)) {
392 DEBUG(dbgs() << "Replace all uses of:\n" << *Pt << "\nwith:\n"
394 (Pt)->replaceAllUsesWith(Inst);
400 if (!DT.dominates(Pt, Inst))
401 // Give up if we need to merge in a common dominator as the
402 // expermients show it is not profitable.
405 DEBUG(dbgs() << "Replace all uses of:\n" << *Inst << "\nwith:\n"
407 Inst->replaceAllUsesWith(Pt);
408 ToRemove.insert(Inst);
413 CurPts.push_back(Inst);
418 void ARM64AddressTypePromotion::analyzeSExtension(Instructions &SExtInsts) {
419 DEBUG(dbgs() << "*** Analyze Sign Extensions ***\n");
421 DenseMap<Value *, Instruction *> SeenChains;
423 for (auto &BB : *Func) {
425 Instruction *SExt = &II;
427 // Collect all sext operation per type.
428 if (!isa<SExtInst>(SExt) || !shouldConsiderSExt(SExt))
431 DEBUG(dbgs() << "Found:\n" << (*SExt) << '\n');
433 // Cases where we actually perform the optimization:
434 // 1. SExt is used in a getelementptr with more than 2 operand =>
435 // likely we can merge some computation if they are done on 64 bits.
436 // 2. The beginning of the SExt chain is SExt several time. =>
437 // code sharing is possible.
441 for (Value::use_iterator UseIt = SExt->use_begin(),
442 EndUseIt = SExt->use_end();
443 UseIt != EndUseIt; ++UseIt) {
444 const Instruction *Inst = dyn_cast<GetElementPtrInst>(*UseIt);
445 if (Inst && Inst->getNumOperands() > 2) {
446 DEBUG(dbgs() << "Interesting use in GetElementPtrInst\n" << *Inst
454 // Check the head of the chain.
455 Instruction *Inst = SExt;
459 const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
460 if (BinOp && isa<ConstantInt>(BinOp->getOperand(0)))
462 Last = Inst->getOperand(OpdIdx);
463 Inst = dyn_cast<Instruction>(Last);
464 } while (Inst && canGetThrough(Inst) && shouldGetThrough(Inst));
466 DEBUG(dbgs() << "Head of the chain:\n" << *Last << '\n');
467 DenseMap<Value *, Instruction *>::iterator AlreadySeen =
468 SeenChains.find(Last);
469 if (insert || AlreadySeen != SeenChains.end()) {
470 DEBUG(dbgs() << "Insert\n");
471 SExtInsts.push_back(SExt);
472 if (AlreadySeen != SeenChains.end() && AlreadySeen->second != NULL) {
473 DEBUG(dbgs() << "Insert chain member\n");
474 SExtInsts.push_back(AlreadySeen->second);
475 SeenChains[Last] = NULL;
478 DEBUG(dbgs() << "Record its chain membership\n");
479 SeenChains[Last] = SExt;
485 bool ARM64AddressTypePromotion::runOnFunction(Function &F) {
486 if (!EnableAddressTypePromotion || F.isDeclaration())
489 ConsideredSExtType = Type::getInt64Ty(Func->getContext());
491 DEBUG(dbgs() << "*** " << getPassName() << ": " << Func->getName() << '\n');
493 Instructions SExtInsts;
494 analyzeSExtension(SExtInsts);
495 return propagateSignExtension(SExtInsts);