Line data Source code
1 : //===-- AArch64AddressTypePromotion.cpp --- Promote type for addr accesses -==//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This pass tries to promote the computations use to obtained a sign extended
11 : // value used into memory accesses.
12 : // E.g.
13 : // a = add nsw i32 b, 3
14 : // d = sext i32 a to i64
15 : // e = getelementptr ..., i64 d
16 : //
17 : // =>
18 : // f = sext i32 b to i64
19 : // a = add nsw i64 f, 3
20 : // e = getelementptr ..., i64 a
21 : //
22 : // This is legal to do if the computations are marked with either nsw or nuw
23 : // markers. Moreover, the current heuristic is simple: it does not create new
24 : // sext operations, i.e., it gives up when a sext would have forked (e.g., if a
25 : // = add i32 b, c, two sexts are required to promote the computation).
26 : //
27 : // FIXME: This pass may be useful for other targets too.
28 : // ===---------------------------------------------------------------------===//
29 :
30 : #include "AArch64.h"
31 : #include "llvm/ADT/DenseMap.h"
32 : #include "llvm/ADT/SmallPtrSet.h"
33 : #include "llvm/ADT/SmallVector.h"
34 : #include "llvm/ADT/StringRef.h"
35 : #include "llvm/IR/Constants.h"
36 : #include "llvm/IR/Dominators.h"
37 : #include "llvm/IR/Function.h"
38 : #include "llvm/IR/InstrTypes.h"
39 : #include "llvm/IR/Instruction.h"
40 : #include "llvm/IR/Instructions.h"
41 : #include "llvm/IR/Operator.h"
42 : #include "llvm/IR/Type.h"
43 : #include "llvm/IR/Use.h"
44 : #include "llvm/IR/User.h"
45 : #include "llvm/Pass.h"
46 : #include "llvm/Support/Casting.h"
47 : #include "llvm/Support/CommandLine.h"
48 : #include "llvm/Support/Debug.h"
49 : #include "llvm/Support/raw_ostream.h"
50 : #include <cassert>
51 :
52 : using namespace llvm;
53 :
54 : #define DEBUG_TYPE "aarch64-type-promotion"
55 :
56 : static cl::opt<bool>
57 131740 : EnableMerge("aarch64-type-promotion-merge", cl::Hidden,
58 197610 : cl::desc("Enable merging of redundant sexts when one is dominating"
59 : " the other."),
60 329350 : cl::init(true));
61 :
62 : #define AARCH64_TYPE_PROMO_NAME "AArch64 Address Type Promotion"
63 :
64 : //===----------------------------------------------------------------------===//
65 : // AArch64AddressTypePromotion
66 : //===----------------------------------------------------------------------===//
67 :
68 : namespace {
69 :
70 0 : class AArch64AddressTypePromotion : public FunctionPass {
71 : public:
72 : static char ID;
73 :
74 0 : AArch64AddressTypePromotion() : FunctionPass(ID) {
75 0 : initializeAArch64AddressTypePromotionPass(*PassRegistry::getPassRegistry());
76 0 : }
77 :
78 0 : StringRef getPassName() const override { return AARCH64_TYPE_PROMO_NAME; }
79 :
80 : /// Iterate over the functions and promote the computation of interesting
81 : // sext instructions.
82 : bool runOnFunction(Function &F) override;
83 :
84 : private:
85 : /// The current function.
86 : Function *Func = nullptr;
87 :
88 : /// Filter out all sexts that does not have this type.
89 : /// Currently initialized with Int64Ty.
90 : Type *ConsideredSExtType = nullptr;
91 :
92 : // This transformation requires dominator info.
93 0 : void getAnalysisUsage(AnalysisUsage &AU) const override {
94 0 : AU.setPreservesCFG();
95 0 : AU.addRequired<DominatorTreeWrapperPass>();
96 0 : AU.addPreserved<DominatorTreeWrapperPass>();
97 0 : FunctionPass::getAnalysisUsage(AU);
98 0 : }
99 :
100 : typedef SmallPtrSet<Instruction *, 32> SetOfInstructions;
101 : typedef SmallVector<Instruction *, 16> Instructions;
102 : typedef DenseMap<Value *, Instructions> ValueToInsts;
103 :
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);
110 :
111 : /// Check if it is possible and legal to move a sext through this
112 : /// instruction.
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);
118 :
119 : /// Move sext operations through safe to sext instructions.
120 : bool propagateSignExtension(Instructions &SExtInsts);
121 :
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;
126 :
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
133 : // operands.
134 : void analyzeSExtension(Instructions &SExtInsts);
135 :
136 : /// Merge redundant sign extension operations in common dominator.
137 : void mergeSExts(ValueToInsts &ValToSExtendedUses,
138 : SetOfInstructions &ToRemove);
139 : };
140 :
141 : } // end anonymous namespace
142 :
143 : char AArch64AddressTypePromotion::ID = 0;
144 :
145 48292 : INITIALIZE_PASS_BEGIN(AArch64AddressTypePromotion, "aarch64-type-promotion",
146 : AARCH64_TYPE_PROMO_NAME, false, false)
147 48292 : INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
148 286868 : INITIALIZE_PASS_END(AArch64AddressTypePromotion, "aarch64-type-promotion",
149 : AARCH64_TYPE_PROMO_NAME, false, false)
150 :
151 0 : FunctionPass *llvm::createAArch64AddressTypePromotionPass() {
152 0 : return new AArch64AddressTypePromotion();
153 : }
154 :
155 0 : bool AArch64AddressTypePromotion::canGetThrough(const Instruction *Inst) {
156 0 : if (isa<SExtInst>(Inst))
157 : return true;
158 :
159 0 : const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
160 0 : if (BinOp && isa<OverflowingBinaryOperator>(BinOp) &&
161 0 : (BinOp->hasNoUnsignedWrap() || BinOp->hasNoSignedWrap()))
162 : return true;
163 :
164 : // sext(trunc(sext)) --> sext
165 0 : if (isa<TruncInst>(Inst) && isa<SExtInst>(Inst->getOperand(0))) {
166 0 : const Instruction *Opnd = cast<Instruction>(Inst->getOperand(0));
167 : // Check that the truncate just drop sign extended bits.
168 0 : if (Inst->getType()->getIntegerBitWidth() >=
169 0 : Opnd->getOperand(0)->getType()->getIntegerBitWidth() &&
170 0 : Inst->getOperand(0)->getType()->getIntegerBitWidth() <=
171 0 : ConsideredSExtType->getIntegerBitWidth())
172 : return true;
173 : }
174 :
175 : return false;
176 : }
177 :
178 0 : bool AArch64AddressTypePromotion::shouldGetThrough(const Instruction *Inst) {
179 : // If the type of the sext is the same as the considered one, this sext
180 : // will become useless.
181 : // Otherwise, we will have to do something to preserve the original value,
182 : // unless it is used once.
183 0 : if (isa<SExtInst>(Inst) &&
184 0 : (Inst->getType() == ConsideredSExtType || Inst->hasOneUse()))
185 : return true;
186 :
187 : // If the Inst is used more that once, we may need to insert truncate
188 : // operations and we don't do that at the moment.
189 0 : if (!Inst->hasOneUse())
190 : return false;
191 :
192 : // This truncate is used only once, thus if we can get thourgh, it will become
193 : // useless.
194 0 : if (isa<TruncInst>(Inst))
195 : return true;
196 :
197 : // If both operands are not constant, a new sext will be created here.
198 : // Current heuristic is: each step should be profitable.
199 : // Therefore we don't allow to increase the number of sext even if it may
200 : // be profitable later on.
201 0 : if (isa<BinaryOperator>(Inst) && isa<ConstantInt>(Inst->getOperand(1)))
202 : return true;
203 :
204 : return false;
205 : }
206 :
207 : static bool shouldSExtOperand(const Instruction *Inst, int OpIdx) {
208 0 : return !(isa<SelectInst>(Inst) && OpIdx == 0);
209 : }
210 :
211 : bool
212 0 : AArch64AddressTypePromotion::shouldConsiderSExt(const Instruction *SExt) const {
213 0 : if (SExt->getType() != ConsideredSExtType)
214 : return false;
215 :
216 0 : for (const User *U : SExt->users()) {
217 0 : if (isa<GetElementPtrInst>(U))
218 : return true;
219 : }
220 :
221 : return false;
222 : }
223 :
224 : // Input:
225 : // - SExtInsts contains all the sext instructions that are used directly in
226 : // GetElementPtrInst, i.e., access to memory.
227 : // Algorithm:
228 : // - For each sext operation in SExtInsts:
229 : // Let var be the operand of sext.
230 : // while it is profitable (see shouldGetThrough), legal, and safe
231 : // (see canGetThrough) to move sext through var's definition:
232 : // * promote the type of var's definition.
233 : // * fold var into sext uses.
234 : // * move sext above var's definition.
235 : // * update sext operand to use the operand of var that should be sign
236 : // extended (by construction there is only one).
237 : //
238 : // E.g.,
239 : // a = ... i32 c, 3
240 : // b = sext i32 a to i64 <- is it legal/safe/profitable to get through 'a'
241 : // ...
242 : // = b
243 : // => Yes, update the code
244 : // b = sext i32 c to i64
245 : // a = ... i64 b, 3
246 : // ...
247 : // = a
248 : // Iterate on 'c'.
249 : bool
250 0 : AArch64AddressTypePromotion::propagateSignExtension(Instructions &SExtInsts) {
251 : DEBUG(dbgs() << "*** Propagate Sign Extension ***\n");
252 :
253 0 : bool LocalChange = false;
254 0 : SetOfInstructions ToRemove;
255 0 : ValueToInsts ValToSExtendedUses;
256 0 : while (!SExtInsts.empty()) {
257 : // Get through simple chain.
258 0 : Instruction *SExt = SExtInsts.pop_back_val();
259 :
260 : DEBUG(dbgs() << "Consider:\n" << *SExt << '\n');
261 :
262 : // If this SExt has already been merged continue.
263 0 : if (SExt->use_empty() && ToRemove.count(SExt)) {
264 : DEBUG(dbgs() << "No uses => marked as delete\n");
265 0 : continue;
266 : }
267 :
268 : // Now try to get through the chain of definitions.
269 0 : while (auto *Inst = dyn_cast<Instruction>(SExt->getOperand(0))) {
270 : DEBUG(dbgs() << "Try to get through:\n" << *Inst << '\n');
271 0 : if (!canGetThrough(Inst) || !shouldGetThrough(Inst)) {
272 : // We cannot get through something that is not an Instruction
273 : // or not safe to SExt.
274 : DEBUG(dbgs() << "Cannot get through\n");
275 : break;
276 : }
277 :
278 0 : LocalChange = true;
279 : // If this is a sign extend, it becomes useless.
280 0 : if (isa<SExtInst>(Inst) || isa<TruncInst>(Inst)) {
281 : DEBUG(dbgs() << "SExt or trunc, mark it as to remove\n");
282 : // We cannot use replaceAllUsesWith here because we may trigger some
283 : // assertion on the type as all involved sext operation may have not
284 : // been moved yet.
285 0 : while (!Inst->use_empty()) {
286 0 : Use &U = *Inst->use_begin();
287 0 : Instruction *User = dyn_cast<Instruction>(U.getUser());
288 : assert(User && "User of sext is not an Instruction!");
289 0 : User->setOperand(U.getOperandNo(), SExt);
290 : }
291 0 : ToRemove.insert(Inst);
292 0 : SExt->setOperand(0, Inst->getOperand(0));
293 0 : SExt->moveBefore(Inst);
294 0 : continue;
295 : }
296 :
297 : // Get through the Instruction:
298 : // 1. Update its type.
299 : // 2. Replace the uses of SExt by Inst.
300 : // 3. Sign extend each operand that needs to be sign extended.
301 :
302 : // Step #1.
303 0 : Inst->mutateType(SExt->getType());
304 : // Step #2.
305 0 : SExt->replaceAllUsesWith(Inst);
306 : // Step #3.
307 0 : Instruction *SExtForOpnd = SExt;
308 :
309 : DEBUG(dbgs() << "Propagate SExt to operands\n");
310 0 : for (int OpIdx = 0, EndOpIdx = Inst->getNumOperands(); OpIdx != EndOpIdx;
311 : ++OpIdx) {
312 : DEBUG(dbgs() << "Operand:\n" << *(Inst->getOperand(OpIdx)) << '\n');
313 0 : if (Inst->getOperand(OpIdx)->getType() == SExt->getType() ||
314 0 : !shouldSExtOperand(Inst, OpIdx)) {
315 : DEBUG(dbgs() << "No need to propagate\n");
316 : continue;
317 : }
318 : // Check if we can statically sign extend the operand.
319 0 : Value *Opnd = Inst->getOperand(OpIdx);
320 0 : if (const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
321 : DEBUG(dbgs() << "Statically sign extend\n");
322 0 : Inst->setOperand(OpIdx, ConstantInt::getSigned(SExt->getType(),
323 0 : Cst->getSExtValue()));
324 0 : continue;
325 : }
326 : // UndefValue are typed, so we have to statically sign extend them.
327 0 : if (isa<UndefValue>(Opnd)) {
328 : DEBUG(dbgs() << "Statically sign extend\n");
329 0 : Inst->setOperand(OpIdx, UndefValue::get(SExt->getType()));
330 0 : continue;
331 : }
332 :
333 : // Otherwise we have to explicity sign extend it.
334 : assert(SExtForOpnd &&
335 : "Only one operand should have been sign extended");
336 :
337 0 : SExtForOpnd->setOperand(0, Opnd);
338 :
339 : DEBUG(dbgs() << "Move before:\n" << *Inst << "\nSign extend\n");
340 : // Move the sign extension before the insertion point.
341 0 : SExtForOpnd->moveBefore(Inst);
342 0 : Inst->setOperand(OpIdx, SExtForOpnd);
343 : // If more sext are required, new instructions will have to be created.
344 0 : SExtForOpnd = nullptr;
345 : }
346 0 : if (SExtForOpnd == SExt) {
347 : DEBUG(dbgs() << "Sign extension is useless now\n");
348 0 : ToRemove.insert(SExt);
349 0 : break;
350 : }
351 : }
352 :
353 : // If the use is already of the right type, connect its uses to its argument
354 : // and delete it.
355 : // This can happen for an Instruction all uses of which are sign extended.
356 0 : if (!ToRemove.count(SExt) &&
357 0 : SExt->getType() == SExt->getOperand(0)->getType()) {
358 : DEBUG(dbgs() << "Sign extension is useless, attach its use to "
359 : "its argument\n");
360 0 : SExt->replaceAllUsesWith(SExt->getOperand(0));
361 0 : ToRemove.insert(SExt);
362 : } else
363 0 : ValToSExtendedUses[SExt->getOperand(0)].push_back(SExt);
364 : }
365 :
366 0 : if (EnableMerge)
367 0 : mergeSExts(ValToSExtendedUses, ToRemove);
368 :
369 : // Remove all instructions marked as ToRemove.
370 0 : for (Instruction *I: ToRemove)
371 0 : I->eraseFromParent();
372 0 : return LocalChange;
373 : }
374 :
375 0 : void AArch64AddressTypePromotion::mergeSExts(ValueToInsts &ValToSExtendedUses,
376 : SetOfInstructions &ToRemove) {
377 0 : DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
378 :
379 0 : for (auto &Entry : ValToSExtendedUses) {
380 0 : Instructions &Insts = Entry.second;
381 0 : Instructions CurPts;
382 0 : for (Instruction *Inst : Insts) {
383 0 : if (ToRemove.count(Inst))
384 : continue;
385 0 : bool inserted = false;
386 0 : for (auto &Pt : CurPts) {
387 0 : if (DT.dominates(Inst, Pt)) {
388 : DEBUG(dbgs() << "Replace all uses of:\n" << *Pt << "\nwith:\n"
389 : << *Inst << '\n');
390 0 : Pt->replaceAllUsesWith(Inst);
391 0 : ToRemove.insert(Pt);
392 0 : Pt = Inst;
393 0 : inserted = true;
394 0 : break;
395 : }
396 0 : if (!DT.dominates(Pt, Inst))
397 : // Give up if we need to merge in a common dominator as the
398 : // expermients show it is not profitable.
399 : continue;
400 :
401 : DEBUG(dbgs() << "Replace all uses of:\n" << *Inst << "\nwith:\n"
402 : << *Pt << '\n');
403 0 : Inst->replaceAllUsesWith(Pt);
404 0 : ToRemove.insert(Inst);
405 0 : inserted = true;
406 0 : break;
407 : }
408 0 : if (!inserted)
409 0 : CurPts.push_back(Inst);
410 : }
411 : }
412 0 : }
413 :
414 0 : void AArch64AddressTypePromotion::analyzeSExtension(Instructions &SExtInsts) {
415 : DEBUG(dbgs() << "*** Analyze Sign Extensions ***\n");
416 :
417 0 : DenseMap<Value *, Instruction *> SeenChains;
418 :
419 0 : for (auto &BB : *Func) {
420 0 : for (auto &II : BB) {
421 0 : Instruction *SExt = &II;
422 :
423 : // Collect all sext operation per type.
424 0 : if (!isa<SExtInst>(SExt) || !shouldConsiderSExt(SExt))
425 0 : continue;
426 :
427 : DEBUG(dbgs() << "Found:\n" << (*SExt) << '\n');
428 :
429 : // Cases where we actually perform the optimization:
430 : // 1. SExt is used in a getelementptr with more than 2 operand =>
431 : // likely we can merge some computation if they are done on 64 bits.
432 : // 2. The beginning of the SExt chain is SExt several time. =>
433 : // code sharing is possible.
434 :
435 0 : bool insert = false;
436 : // #1.
437 0 : for (const User *U : SExt->users()) {
438 0 : const Instruction *Inst = dyn_cast<GetElementPtrInst>(U);
439 0 : if (Inst && Inst->getNumOperands() > 2) {
440 : DEBUG(dbgs() << "Interesting use in GetElementPtrInst\n" << *Inst
441 : << '\n');
442 : insert = true;
443 : break;
444 : }
445 : }
446 :
447 : // #2.
448 : // Check the head of the chain.
449 0 : Instruction *Inst = SExt;
450 : Value *Last;
451 0 : do {
452 0 : int OpdIdx = 0;
453 0 : const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst);
454 0 : if (BinOp && isa<ConstantInt>(BinOp->getOperand(0)))
455 0 : OpdIdx = 1;
456 0 : Last = Inst->getOperand(OpdIdx);
457 0 : Inst = dyn_cast<Instruction>(Last);
458 0 : } while (Inst && canGetThrough(Inst) && shouldGetThrough(Inst));
459 :
460 : DEBUG(dbgs() << "Head of the chain:\n" << *Last << '\n');
461 : DenseMap<Value *, Instruction *>::iterator AlreadySeen =
462 0 : SeenChains.find(Last);
463 0 : if (insert || AlreadySeen != SeenChains.end()) {
464 : DEBUG(dbgs() << "Insert\n");
465 0 : SExtInsts.push_back(SExt);
466 0 : if (AlreadySeen != SeenChains.end() && AlreadySeen->second != nullptr) {
467 : DEBUG(dbgs() << "Insert chain member\n");
468 0 : SExtInsts.push_back(AlreadySeen->second);
469 0 : SeenChains[Last] = nullptr;
470 : }
471 : } else {
472 : DEBUG(dbgs() << "Record its chain membership\n");
473 0 : SeenChains[Last] = SExt;
474 : }
475 : }
476 : }
477 0 : }
478 :
479 0 : bool AArch64AddressTypePromotion::runOnFunction(Function &F) {
480 0 : if (skipFunction(F))
481 : return false;
482 :
483 0 : if (F.isDeclaration())
484 : return false;
485 0 : Func = &F;
486 0 : ConsideredSExtType = Type::getInt64Ty(Func->getContext());
487 :
488 : DEBUG(dbgs() << "*** " << getPassName() << ": " << Func->getName() << '\n');
489 :
490 0 : Instructions SExtInsts;
491 0 : analyzeSExtension(SExtInsts);
492 0 : return propagateSignExtension(SExtInsts);
493 197610 : }
|
