1 //===----- TypePromotion.cpp ----------------------------------------------===//
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 /// \file
10 /// This is an opcode based type promotion pass for small types that would
11 /// otherwise be promoted during legalisation. This works around the limitations
12 /// of selection dag for cyclic regions. The search begins from icmp
13 /// instructions operands where a tree, consisting of non-wrapping or safe
14 /// wrapping instructions, is built, checked and promoted if possible.
15 ///
16 //===----------------------------------------------------------------------===//
17
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/StringRef.h"
20 #include "llvm/Analysis/TargetTransformInfo.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/CodeGen/TargetLowering.h"
23 #include "llvm/CodeGen/TargetPassConfig.h"
24 #include "llvm/CodeGen/TargetSubtargetInfo.h"
25 #include "llvm/IR/Attributes.h"
26 #include "llvm/IR/BasicBlock.h"
27 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/IR/IntrinsicsARM.h"
36 #include "llvm/IR/Type.h"
37 #include "llvm/IR/Value.h"
38 #include "llvm/IR/Verifier.h"
39 #include "llvm/InitializePasses.h"
40 #include "llvm/Pass.h"
41 #include "llvm/Support/Casting.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Target/TargetMachine.h"
44
45 #define DEBUG_TYPE "type-promotion"
46 #define PASS_NAME "Type Promotion"
47
48 using namespace llvm;
49
50 static cl::opt<bool>
51 DisablePromotion("disable-type-promotion", cl::Hidden, cl::init(false),
52 cl::desc("Disable type promotion pass"));
53
54 // The goal of this pass is to enable more efficient code generation for
55 // operations on narrow types (i.e. types with < 32-bits) and this is a
56 // motivating IR code example:
57 //
58 // define hidden i32 @cmp(i8 zeroext) {
59 // %2 = add i8 %0, -49
60 // %3 = icmp ult i8 %2, 3
61 // ..
62 // }
63 //
64 // The issue here is that i8 is type-legalized to i32 because i8 is not a
65 // legal type. Thus, arithmetic is done in integer-precision, but then the
66 // byte value is masked out as follows:
67 //
68 // t19: i32 = add t4, Constant:i32<-49>
69 // t24: i32 = and t19, Constant:i32<255>
70 //
71 // Consequently, we generate code like this:
72 //
73 // subs r0, #49
74 // uxtb r1, r0
75 // cmp r1, #3
76 //
77 // This shows that masking out the byte value results in generation of
78 // the UXTB instruction. This is not optimal as r0 already contains the byte
79 // value we need, and so instead we can just generate:
80 //
81 // sub.w r1, r0, #49
82 // cmp r1, #3
83 //
84 // We achieve this by type promoting the IR to i32 like so for this example:
85 //
86 // define i32 @cmp(i8 zeroext %c) {
87 // %0 = zext i8 %c to i32
88 // %c.off = add i32 %0, -49
89 // %1 = icmp ult i32 %c.off, 3
90 // ..
91 // }
92 //
93 // For this to be valid and legal, we need to prove that the i32 add is
94 // producing the same value as the i8 addition, and that e.g. no overflow
95 // happens.
96 //
97 // A brief sketch of the algorithm and some terminology.
98 // We pattern match interesting IR patterns:
99 // - which have "sources": instructions producing narrow values (i8, i16), and
100 // - they have "sinks": instructions consuming these narrow values.
101 //
102 // We collect all instruction connecting sources and sinks in a worklist, so
103 // that we can mutate these instruction and perform type promotion when it is
104 // legal to do so.
105
106 namespace {
107 class IRPromoter {
108 LLVMContext &Ctx;
109 IntegerType *OrigTy = nullptr;
110 unsigned PromotedWidth = 0;
111 SetVector<Value*> &Visited;
112 SetVector<Value*> &Sources;
113 SetVector<Instruction*> &Sinks;
114 SmallVectorImpl<Instruction*> &SafeWrap;
115 IntegerType *ExtTy = nullptr;
116 SmallPtrSet<Value*, 8> NewInsts;
117 SmallPtrSet<Instruction*, 4> InstsToRemove;
118 DenseMap<Value*, SmallVector<Type*, 4>> TruncTysMap;
119 SmallPtrSet<Value*, 8> Promoted;
120
121 void ReplaceAllUsersOfWith(Value *From, Value *To);
122 void PrepareWrappingAdds(void);
123 void ExtendSources(void);
124 void ConvertTruncs(void);
125 void PromoteTree(void);
126 void TruncateSinks(void);
127 void Cleanup(void);
128
129 public:
IRPromoter(LLVMContext & C,IntegerType * Ty,unsigned Width,SetVector<Value * > & visited,SetVector<Value * > & sources,SetVector<Instruction * > & sinks,SmallVectorImpl<Instruction * > & wrap)130 IRPromoter(LLVMContext &C, IntegerType *Ty, unsigned Width,
131 SetVector<Value*> &visited, SetVector<Value*> &sources,
132 SetVector<Instruction*> &sinks,
133 SmallVectorImpl<Instruction*> &wrap) :
134 Ctx(C), OrigTy(Ty), PromotedWidth(Width), Visited(visited),
135 Sources(sources), Sinks(sinks), SafeWrap(wrap) {
136 ExtTy = IntegerType::get(Ctx, PromotedWidth);
137 assert(OrigTy->getPrimitiveSizeInBits().getFixedSize() <
138 ExtTy->getPrimitiveSizeInBits().getFixedSize() &&
139 "Original type not smaller than extended type");
140 }
141
142 void Mutate();
143 };
144
145 class TypePromotion : public FunctionPass {
146 unsigned TypeSize = 0;
147 LLVMContext *Ctx = nullptr;
148 unsigned RegisterBitWidth = 0;
149 SmallPtrSet<Value*, 16> AllVisited;
150 SmallPtrSet<Instruction*, 8> SafeToPromote;
151 SmallVector<Instruction*, 4> SafeWrap;
152
153 // Does V have the same size result type as TypeSize.
154 bool EqualTypeSize(Value *V);
155 // Does V have the same size, or narrower, result type as TypeSize.
156 bool LessOrEqualTypeSize(Value *V);
157 // Does V have a result type that is wider than TypeSize.
158 bool GreaterThanTypeSize(Value *V);
159 // Does V have a result type that is narrower than TypeSize.
160 bool LessThanTypeSize(Value *V);
161 // Should V be a leaf in the promote tree?
162 bool isSource(Value *V);
163 // Should V be a root in the promotion tree?
164 bool isSink(Value *V);
165 // Should we change the result type of V? It will result in the users of V
166 // being visited.
167 bool shouldPromote(Value *V);
168 // Is I an add or a sub, which isn't marked as nuw, but where a wrapping
169 // result won't affect the computation?
170 bool isSafeWrap(Instruction *I);
171 // Can V have its integer type promoted, or can the type be ignored.
172 bool isSupportedType(Value *V);
173 // Is V an instruction with a supported opcode or another value that we can
174 // handle, such as constants and basic blocks.
175 bool isSupportedValue(Value *V);
176 // Is V an instruction thats result can trivially promoted, or has safe
177 // wrapping.
178 bool isLegalToPromote(Value *V);
179 bool TryToPromote(Value *V, unsigned PromotedWidth);
180
181 public:
182 static char ID;
183
TypePromotion()184 TypePromotion() : FunctionPass(ID) {}
185
getAnalysisUsage(AnalysisUsage & AU) const186 void getAnalysisUsage(AnalysisUsage &AU) const override {
187 AU.addRequired<TargetTransformInfoWrapperPass>();
188 AU.addRequired<TargetPassConfig>();
189 }
190
getPassName() const191 StringRef getPassName() const override { return PASS_NAME; }
192
193 bool runOnFunction(Function &F) override;
194 };
195
196 }
197
GenerateSignBits(Value * V)198 static bool GenerateSignBits(Value *V) {
199 if (!isa<Instruction>(V))
200 return false;
201
202 unsigned Opc = cast<Instruction>(V)->getOpcode();
203 return Opc == Instruction::AShr || Opc == Instruction::SDiv ||
204 Opc == Instruction::SRem || Opc == Instruction::SExt;
205 }
206
EqualTypeSize(Value * V)207 bool TypePromotion::EqualTypeSize(Value *V) {
208 return V->getType()->getScalarSizeInBits() == TypeSize;
209 }
210
LessOrEqualTypeSize(Value * V)211 bool TypePromotion::LessOrEqualTypeSize(Value *V) {
212 return V->getType()->getScalarSizeInBits() <= TypeSize;
213 }
214
GreaterThanTypeSize(Value * V)215 bool TypePromotion::GreaterThanTypeSize(Value *V) {
216 return V->getType()->getScalarSizeInBits() > TypeSize;
217 }
218
LessThanTypeSize(Value * V)219 bool TypePromotion::LessThanTypeSize(Value *V) {
220 return V->getType()->getScalarSizeInBits() < TypeSize;
221 }
222
223 /// Return true if the given value is a source in the use-def chain, producing
224 /// a narrow 'TypeSize' value. These values will be zext to start the promotion
225 /// of the tree to i32. We guarantee that these won't populate the upper bits
226 /// of the register. ZExt on the loads will be free, and the same for call
227 /// return values because we only accept ones that guarantee a zeroext ret val.
228 /// Many arguments will have the zeroext attribute too, so those would be free
229 /// too.
isSource(Value * V)230 bool TypePromotion::isSource(Value *V) {
231 if (!isa<IntegerType>(V->getType()))
232 return false;
233
234 // TODO Allow zext to be sources.
235 if (isa<Argument>(V))
236 return true;
237 else if (isa<LoadInst>(V))
238 return true;
239 else if (isa<BitCastInst>(V))
240 return true;
241 else if (auto *Call = dyn_cast<CallInst>(V))
242 return Call->hasRetAttr(Attribute::AttrKind::ZExt);
243 else if (auto *Trunc = dyn_cast<TruncInst>(V))
244 return EqualTypeSize(Trunc);
245 return false;
246 }
247
248 /// Return true if V will require any promoted values to be truncated for the
249 /// the IR to remain valid. We can't mutate the value type of these
250 /// instructions.
isSink(Value * V)251 bool TypePromotion::isSink(Value *V) {
252 // TODO The truncate also isn't actually necessary because we would already
253 // proved that the data value is kept within the range of the original data
254 // type.
255
256 // Sinks are:
257 // - points where the value in the register is being observed, such as an
258 // icmp, switch or store.
259 // - points where value types have to match, such as calls and returns.
260 // - zext are included to ease the transformation and are generally removed
261 // later on.
262 if (auto *Store = dyn_cast<StoreInst>(V))
263 return LessOrEqualTypeSize(Store->getValueOperand());
264 if (auto *Return = dyn_cast<ReturnInst>(V))
265 return LessOrEqualTypeSize(Return->getReturnValue());
266 if (auto *ZExt = dyn_cast<ZExtInst>(V))
267 return GreaterThanTypeSize(ZExt);
268 if (auto *Switch = dyn_cast<SwitchInst>(V))
269 return LessThanTypeSize(Switch->getCondition());
270 if (auto *ICmp = dyn_cast<ICmpInst>(V))
271 return ICmp->isSigned() || LessThanTypeSize(ICmp->getOperand(0));
272
273 return isa<CallInst>(V);
274 }
275
276 /// Return whether this instruction can safely wrap.
isSafeWrap(Instruction * I)277 bool TypePromotion::isSafeWrap(Instruction *I) {
278 // We can support a, potentially, wrapping instruction (I) if:
279 // - It is only used by an unsigned icmp.
280 // - The icmp uses a constant.
281 // - The wrapping value (I) is decreasing, i.e would underflow - wrapping
282 // around zero to become a larger number than before.
283 // - The wrapping instruction (I) also uses a constant.
284 //
285 // We can then use the two constants to calculate whether the result would
286 // wrap in respect to itself in the original bitwidth. If it doesn't wrap,
287 // just underflows the range, the icmp would give the same result whether the
288 // result has been truncated or not. We calculate this by:
289 // - Zero extending both constants, if needed, to 32-bits.
290 // - Take the absolute value of I's constant, adding this to the icmp const.
291 // - Check that this value is not out of range for small type. If it is, it
292 // means that it has underflowed enough to wrap around the icmp constant.
293 //
294 // For example:
295 //
296 // %sub = sub i8 %a, 2
297 // %cmp = icmp ule i8 %sub, 254
298 //
299 // If %a = 0, %sub = -2 == FE == 254
300 // But if this is evalulated as a i32
301 // %sub = -2 == FF FF FF FE == 4294967294
302 // So the unsigned compares (i8 and i32) would not yield the same result.
303 //
304 // Another way to look at it is:
305 // %a - 2 <= 254
306 // %a + 2 <= 254 + 2
307 // %a <= 256
308 // And we can't represent 256 in the i8 format, so we don't support it.
309 //
310 // Whereas:
311 //
312 // %sub i8 %a, 1
313 // %cmp = icmp ule i8 %sub, 254
314 //
315 // If %a = 0, %sub = -1 == FF == 255
316 // As i32:
317 // %sub = -1 == FF FF FF FF == 4294967295
318 //
319 // In this case, the unsigned compare results would be the same and this
320 // would also be true for ult, uge and ugt:
321 // - (255 < 254) == (0xFFFFFFFF < 254) == false
322 // - (255 <= 254) == (0xFFFFFFFF <= 254) == false
323 // - (255 > 254) == (0xFFFFFFFF > 254) == true
324 // - (255 >= 254) == (0xFFFFFFFF >= 254) == true
325 //
326 // To demonstrate why we can't handle increasing values:
327 //
328 // %add = add i8 %a, 2
329 // %cmp = icmp ult i8 %add, 127
330 //
331 // If %a = 254, %add = 256 == (i8 1)
332 // As i32:
333 // %add = 256
334 //
335 // (1 < 127) != (256 < 127)
336
337 unsigned Opc = I->getOpcode();
338 if (Opc != Instruction::Add && Opc != Instruction::Sub)
339 return false;
340
341 if (!I->hasOneUse() ||
342 !isa<ICmpInst>(*I->user_begin()) ||
343 !isa<ConstantInt>(I->getOperand(1)))
344 return false;
345
346 ConstantInt *OverflowConst = cast<ConstantInt>(I->getOperand(1));
347 bool NegImm = OverflowConst->isNegative();
348 bool IsDecreasing = ((Opc == Instruction::Sub) && !NegImm) ||
349 ((Opc == Instruction::Add) && NegImm);
350 if (!IsDecreasing)
351 return false;
352
353 // Don't support an icmp that deals with sign bits.
354 auto *CI = cast<ICmpInst>(*I->user_begin());
355 if (CI->isSigned() || CI->isEquality())
356 return false;
357
358 ConstantInt *ICmpConst = nullptr;
359 if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(0)))
360 ICmpConst = Const;
361 else if (auto *Const = dyn_cast<ConstantInt>(CI->getOperand(1)))
362 ICmpConst = Const;
363 else
364 return false;
365
366 // Now check that the result can't wrap on itself.
367 APInt Total = ICmpConst->getValue().getBitWidth() < 32 ?
368 ICmpConst->getValue().zext(32) : ICmpConst->getValue();
369
370 Total += OverflowConst->getValue().getBitWidth() < 32 ?
371 OverflowConst->getValue().abs().zext(32) : OverflowConst->getValue().abs();
372
373 APInt Max = APInt::getAllOnesValue(TypePromotion::TypeSize);
374
375 if (Total.getBitWidth() > Max.getBitWidth()) {
376 if (Total.ugt(Max.zext(Total.getBitWidth())))
377 return false;
378 } else if (Max.getBitWidth() > Total.getBitWidth()) {
379 if (Total.zext(Max.getBitWidth()).ugt(Max))
380 return false;
381 } else if (Total.ugt(Max))
382 return false;
383
384 LLVM_DEBUG(dbgs() << "IR Promotion: Allowing safe overflow for "
385 << *I << "\n");
386 SafeWrap.push_back(I);
387 return true;
388 }
389
shouldPromote(Value * V)390 bool TypePromotion::shouldPromote(Value *V) {
391 if (!isa<IntegerType>(V->getType()) || isSink(V))
392 return false;
393
394 if (isSource(V))
395 return true;
396
397 auto *I = dyn_cast<Instruction>(V);
398 if (!I)
399 return false;
400
401 if (isa<ICmpInst>(I))
402 return false;
403
404 return true;
405 }
406
407 /// Return whether we can safely mutate V's type to ExtTy without having to be
408 /// concerned with zero extending or truncation.
isPromotedResultSafe(Value * V)409 static bool isPromotedResultSafe(Value *V) {
410 if (GenerateSignBits(V))
411 return false;
412
413 if (!isa<Instruction>(V))
414 return true;
415
416 if (!isa<OverflowingBinaryOperator>(V))
417 return true;
418
419 return cast<Instruction>(V)->hasNoUnsignedWrap();
420 }
421
ReplaceAllUsersOfWith(Value * From,Value * To)422 void IRPromoter::ReplaceAllUsersOfWith(Value *From, Value *To) {
423 SmallVector<Instruction*, 4> Users;
424 Instruction *InstTo = dyn_cast<Instruction>(To);
425 bool ReplacedAll = true;
426
427 LLVM_DEBUG(dbgs() << "IR Promotion: Replacing " << *From << " with " << *To
428 << "\n");
429
430 for (Use &U : From->uses()) {
431 auto *User = cast<Instruction>(U.getUser());
432 if (InstTo && User->isIdenticalTo(InstTo)) {
433 ReplacedAll = false;
434 continue;
435 }
436 Users.push_back(User);
437 }
438
439 for (auto *U : Users)
440 U->replaceUsesOfWith(From, To);
441
442 if (ReplacedAll)
443 if (auto *I = dyn_cast<Instruction>(From))
444 InstsToRemove.insert(I);
445 }
446
PrepareWrappingAdds()447 void IRPromoter::PrepareWrappingAdds() {
448 LLVM_DEBUG(dbgs() << "IR Promotion: Prepare wrapping adds.\n");
449 IRBuilder<> Builder{Ctx};
450
451 // For adds that safely wrap and use a negative immediate as operand 1, we
452 // create an equivalent instruction using a positive immediate.
453 // That positive immediate can then be zext along with all the other
454 // immediates later.
455 for (auto *I : SafeWrap) {
456 if (I->getOpcode() != Instruction::Add)
457 continue;
458
459 LLVM_DEBUG(dbgs() << "IR Promotion: Adjusting " << *I << "\n");
460 assert((isa<ConstantInt>(I->getOperand(1)) &&
461 cast<ConstantInt>(I->getOperand(1))->isNegative()) &&
462 "Wrapping should have a negative immediate as the second operand");
463
464 auto Const = cast<ConstantInt>(I->getOperand(1));
465 auto *NewConst = ConstantInt::get(Ctx, Const->getValue().abs());
466 Builder.SetInsertPoint(I);
467 Value *NewVal = Builder.CreateSub(I->getOperand(0), NewConst);
468 if (auto *NewInst = dyn_cast<Instruction>(NewVal)) {
469 NewInst->copyIRFlags(I);
470 NewInsts.insert(NewInst);
471 }
472 InstsToRemove.insert(I);
473 I->replaceAllUsesWith(NewVal);
474 LLVM_DEBUG(dbgs() << "IR Promotion: New equivalent: " << *NewVal << "\n");
475 }
476 for (auto *I : NewInsts)
477 Visited.insert(I);
478 }
479
ExtendSources()480 void IRPromoter::ExtendSources() {
481 IRBuilder<> Builder{Ctx};
482
483 auto InsertZExt = [&](Value *V, Instruction *InsertPt) {
484 assert(V->getType() != ExtTy && "zext already extends to i32");
485 LLVM_DEBUG(dbgs() << "IR Promotion: Inserting ZExt for " << *V << "\n");
486 Builder.SetInsertPoint(InsertPt);
487 if (auto *I = dyn_cast<Instruction>(V))
488 Builder.SetCurrentDebugLocation(I->getDebugLoc());
489
490 Value *ZExt = Builder.CreateZExt(V, ExtTy);
491 if (auto *I = dyn_cast<Instruction>(ZExt)) {
492 if (isa<Argument>(V))
493 I->moveBefore(InsertPt);
494 else
495 I->moveAfter(InsertPt);
496 NewInsts.insert(I);
497 }
498
499 ReplaceAllUsersOfWith(V, ZExt);
500 };
501
502 // Now, insert extending instructions between the sources and their users.
503 LLVM_DEBUG(dbgs() << "IR Promotion: Promoting sources:\n");
504 for (auto V : Sources) {
505 LLVM_DEBUG(dbgs() << " - " << *V << "\n");
506 if (auto *I = dyn_cast<Instruction>(V))
507 InsertZExt(I, I);
508 else if (auto *Arg = dyn_cast<Argument>(V)) {
509 BasicBlock &BB = Arg->getParent()->front();
510 InsertZExt(Arg, &*BB.getFirstInsertionPt());
511 } else {
512 llvm_unreachable("unhandled source that needs extending");
513 }
514 Promoted.insert(V);
515 }
516 }
517
PromoteTree()518 void IRPromoter::PromoteTree() {
519 LLVM_DEBUG(dbgs() << "IR Promotion: Mutating the tree..\n");
520
521 IRBuilder<> Builder{Ctx};
522
523 // Mutate the types of the instructions within the tree. Here we handle
524 // constant operands.
525 for (auto *V : Visited) {
526 if (Sources.count(V))
527 continue;
528
529 auto *I = cast<Instruction>(V);
530 if (Sinks.count(I))
531 continue;
532
533 for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
534 Value *Op = I->getOperand(i);
535 if ((Op->getType() == ExtTy) || !isa<IntegerType>(Op->getType()))
536 continue;
537
538 if (auto *Const = dyn_cast<ConstantInt>(Op)) {
539 Constant *NewConst = ConstantExpr::getZExt(Const, ExtTy);
540 I->setOperand(i, NewConst);
541 } else if (isa<UndefValue>(Op))
542 I->setOperand(i, UndefValue::get(ExtTy));
543 }
544
545 // Mutate the result type, unless this is an icmp.
546 if (!isa<ICmpInst>(I)) {
547 I->mutateType(ExtTy);
548 Promoted.insert(I);
549 }
550 }
551 }
552
TruncateSinks()553 void IRPromoter::TruncateSinks() {
554 LLVM_DEBUG(dbgs() << "IR Promotion: Fixing up the sinks:\n");
555
556 IRBuilder<> Builder{Ctx};
557
558 auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction* {
559 if (!isa<Instruction>(V) || !isa<IntegerType>(V->getType()))
560 return nullptr;
561
562 if ((!Promoted.count(V) && !NewInsts.count(V)) || Sources.count(V))
563 return nullptr;
564
565 LLVM_DEBUG(dbgs() << "IR Promotion: Creating " << *TruncTy << " Trunc for "
566 << *V << "\n");
567 Builder.SetInsertPoint(cast<Instruction>(V));
568 auto *Trunc = dyn_cast<Instruction>(Builder.CreateTrunc(V, TruncTy));
569 if (Trunc)
570 NewInsts.insert(Trunc);
571 return Trunc;
572 };
573
574 // Fix up any stores or returns that use the results of the promoted
575 // chain.
576 for (auto I : Sinks) {
577 LLVM_DEBUG(dbgs() << "IR Promotion: For Sink: " << *I << "\n");
578
579 // Handle calls separately as we need to iterate over arg operands.
580 if (auto *Call = dyn_cast<CallInst>(I)) {
581 for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
582 Value *Arg = Call->getArgOperand(i);
583 Type *Ty = TruncTysMap[Call][i];
584 if (Instruction *Trunc = InsertTrunc(Arg, Ty)) {
585 Trunc->moveBefore(Call);
586 Call->setArgOperand(i, Trunc);
587 }
588 }
589 continue;
590 }
591
592 // Special case switches because we need to truncate the condition.
593 if (auto *Switch = dyn_cast<SwitchInst>(I)) {
594 Type *Ty = TruncTysMap[Switch][0];
595 if (Instruction *Trunc = InsertTrunc(Switch->getCondition(), Ty)) {
596 Trunc->moveBefore(Switch);
597 Switch->setCondition(Trunc);
598 }
599 continue;
600 }
601
602 // Now handle the others.
603 for (unsigned i = 0; i < I->getNumOperands(); ++i) {
604 Type *Ty = TruncTysMap[I][i];
605 if (Instruction *Trunc = InsertTrunc(I->getOperand(i), Ty)) {
606 Trunc->moveBefore(I);
607 I->setOperand(i, Trunc);
608 }
609 }
610 }
611 }
612
Cleanup()613 void IRPromoter::Cleanup() {
614 LLVM_DEBUG(dbgs() << "IR Promotion: Cleanup..\n");
615 // Some zexts will now have become redundant, along with their trunc
616 // operands, so remove them
617 for (auto V : Visited) {
618 if (!isa<ZExtInst>(V))
619 continue;
620
621 auto ZExt = cast<ZExtInst>(V);
622 if (ZExt->getDestTy() != ExtTy)
623 continue;
624
625 Value *Src = ZExt->getOperand(0);
626 if (ZExt->getSrcTy() == ZExt->getDestTy()) {
627 LLVM_DEBUG(dbgs() << "IR Promotion: Removing unnecessary cast: " << *ZExt
628 << "\n");
629 ReplaceAllUsersOfWith(ZExt, Src);
630 continue;
631 }
632
633 // Unless they produce a value that is narrower than ExtTy, we can
634 // replace the result of the zext with the input of a newly inserted
635 // trunc.
636 if (NewInsts.count(Src) && isa<TruncInst>(Src) &&
637 Src->getType() == OrigTy) {
638 auto *Trunc = cast<TruncInst>(Src);
639 assert(Trunc->getOperand(0)->getType() == ExtTy &&
640 "expected inserted trunc to be operating on i32");
641 ReplaceAllUsersOfWith(ZExt, Trunc->getOperand(0));
642 }
643 }
644
645 for (auto *I : InstsToRemove) {
646 LLVM_DEBUG(dbgs() << "IR Promotion: Removing " << *I << "\n");
647 I->dropAllReferences();
648 I->eraseFromParent();
649 }
650 }
651
ConvertTruncs()652 void IRPromoter::ConvertTruncs() {
653 LLVM_DEBUG(dbgs() << "IR Promotion: Converting truncs..\n");
654 IRBuilder<> Builder{Ctx};
655
656 for (auto *V : Visited) {
657 if (!isa<TruncInst>(V) || Sources.count(V))
658 continue;
659
660 auto *Trunc = cast<TruncInst>(V);
661 Builder.SetInsertPoint(Trunc);
662 IntegerType *SrcTy = cast<IntegerType>(Trunc->getOperand(0)->getType());
663 IntegerType *DestTy = cast<IntegerType>(TruncTysMap[Trunc][0]);
664
665 unsigned NumBits = DestTy->getScalarSizeInBits();
666 ConstantInt *Mask =
667 ConstantInt::get(SrcTy, APInt::getMaxValue(NumBits).getZExtValue());
668 Value *Masked = Builder.CreateAnd(Trunc->getOperand(0), Mask);
669
670 if (auto *I = dyn_cast<Instruction>(Masked))
671 NewInsts.insert(I);
672
673 ReplaceAllUsersOfWith(Trunc, Masked);
674 }
675 }
676
Mutate()677 void IRPromoter::Mutate() {
678 LLVM_DEBUG(dbgs() << "IR Promotion: Promoting use-def chains from "
679 << OrigTy->getBitWidth() << " to " << PromotedWidth << "-bits\n");
680
681 // Cache original types of the values that will likely need truncating
682 for (auto *I : Sinks) {
683 if (auto *Call = dyn_cast<CallInst>(I)) {
684 for (unsigned i = 0; i < Call->getNumArgOperands(); ++i) {
685 Value *Arg = Call->getArgOperand(i);
686 TruncTysMap[Call].push_back(Arg->getType());
687 }
688 } else if (auto *Switch = dyn_cast<SwitchInst>(I))
689 TruncTysMap[I].push_back(Switch->getCondition()->getType());
690 else {
691 for (unsigned i = 0; i < I->getNumOperands(); ++i)
692 TruncTysMap[I].push_back(I->getOperand(i)->getType());
693 }
694 }
695 for (auto *V : Visited) {
696 if (!isa<TruncInst>(V) || Sources.count(V))
697 continue;
698 auto *Trunc = cast<TruncInst>(V);
699 TruncTysMap[Trunc].push_back(Trunc->getDestTy());
700 }
701
702 // Convert adds using negative immediates to equivalent instructions that use
703 // positive constants.
704 PrepareWrappingAdds();
705
706 // Insert zext instructions between sources and their users.
707 ExtendSources();
708
709 // Promote visited instructions, mutating their types in place.
710 PromoteTree();
711
712 // Convert any truncs, that aren't sources, into AND masks.
713 ConvertTruncs();
714
715 // Insert trunc instructions for use by calls, stores etc...
716 TruncateSinks();
717
718 // Finally, remove unecessary zexts and truncs, delete old instructions and
719 // clear the data structures.
720 Cleanup();
721
722 LLVM_DEBUG(dbgs() << "IR Promotion: Mutation complete\n");
723 }
724
725 /// We disallow booleans to make life easier when dealing with icmps but allow
726 /// any other integer that fits in a scalar register. Void types are accepted
727 /// so we can handle switches.
isSupportedType(Value * V)728 bool TypePromotion::isSupportedType(Value *V) {
729 Type *Ty = V->getType();
730
731 // Allow voids and pointers, these won't be promoted.
732 if (Ty->isVoidTy() || Ty->isPointerTy())
733 return true;
734
735 if (!isa<IntegerType>(Ty) ||
736 cast<IntegerType>(Ty)->getBitWidth() == 1 ||
737 cast<IntegerType>(Ty)->getBitWidth() > RegisterBitWidth)
738 return false;
739
740 return LessOrEqualTypeSize(V);
741 }
742
743 /// We accept most instructions, as well as Arguments and ConstantInsts. We
744 /// Disallow casts other than zext and truncs and only allow calls if their
745 /// return value is zeroext. We don't allow opcodes that can introduce sign
746 /// bits.
isSupportedValue(Value * V)747 bool TypePromotion::isSupportedValue(Value *V) {
748 if (auto *I = dyn_cast<Instruction>(V)) {
749 switch (I->getOpcode()) {
750 default:
751 return isa<BinaryOperator>(I) && isSupportedType(I) &&
752 !GenerateSignBits(I);
753 case Instruction::GetElementPtr:
754 case Instruction::Store:
755 case Instruction::Br:
756 case Instruction::Switch:
757 return true;
758 case Instruction::PHI:
759 case Instruction::Select:
760 case Instruction::Ret:
761 case Instruction::Load:
762 case Instruction::Trunc:
763 case Instruction::BitCast:
764 return isSupportedType(I);
765 case Instruction::ZExt:
766 return isSupportedType(I->getOperand(0));
767 case Instruction::ICmp:
768 // Now that we allow small types than TypeSize, only allow icmp of
769 // TypeSize because they will require a trunc to be legalised.
770 // TODO: Allow icmp of smaller types, and calculate at the end
771 // whether the transform would be beneficial.
772 if (isa<PointerType>(I->getOperand(0)->getType()))
773 return true;
774 return EqualTypeSize(I->getOperand(0));
775 case Instruction::Call: {
776 // Special cases for calls as we need to check for zeroext
777 // TODO We should accept calls even if they don't have zeroext, as they
778 // can still be sinks.
779 auto *Call = cast<CallInst>(I);
780 return isSupportedType(Call) &&
781 Call->hasRetAttr(Attribute::AttrKind::ZExt);
782 }
783 }
784 } else if (isa<Constant>(V) && !isa<ConstantExpr>(V)) {
785 return isSupportedType(V);
786 } else if (isa<Argument>(V))
787 return isSupportedType(V);
788
789 return isa<BasicBlock>(V);
790 }
791
792 /// Check that the type of V would be promoted and that the original type is
793 /// smaller than the targeted promoted type. Check that we're not trying to
794 /// promote something larger than our base 'TypeSize' type.
isLegalToPromote(Value * V)795 bool TypePromotion::isLegalToPromote(Value *V) {
796
797 auto *I = dyn_cast<Instruction>(V);
798 if (!I)
799 return true;
800
801 if (SafeToPromote.count(I))
802 return true;
803
804 if (isPromotedResultSafe(V) || isSafeWrap(I)) {
805 SafeToPromote.insert(I);
806 return true;
807 }
808 return false;
809 }
810
TryToPromote(Value * V,unsigned PromotedWidth)811 bool TypePromotion::TryToPromote(Value *V, unsigned PromotedWidth) {
812 Type *OrigTy = V->getType();
813 TypeSize = OrigTy->getPrimitiveSizeInBits().getFixedSize();
814 SafeToPromote.clear();
815 SafeWrap.clear();
816
817 if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
818 return false;
819
820 LLVM_DEBUG(dbgs() << "IR Promotion: TryToPromote: " << *V << ", from "
821 << TypeSize << " bits to " << PromotedWidth << "\n");
822
823 SetVector<Value*> WorkList;
824 SetVector<Value*> Sources;
825 SetVector<Instruction*> Sinks;
826 SetVector<Value*> CurrentVisited;
827 WorkList.insert(V);
828
829 // Return true if V was added to the worklist as a supported instruction,
830 // if it was already visited, or if we don't need to explore it (e.g.
831 // pointer values and GEPs), and false otherwise.
832 auto AddLegalInst = [&](Value *V) {
833 if (CurrentVisited.count(V))
834 return true;
835
836 // Ignore GEPs because they don't need promoting and the constant indices
837 // will prevent the transformation.
838 if (isa<GetElementPtrInst>(V))
839 return true;
840
841 if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {
842 LLVM_DEBUG(dbgs() << "IR Promotion: Can't handle: " << *V << "\n");
843 return false;
844 }
845
846 WorkList.insert(V);
847 return true;
848 };
849
850 // Iterate through, and add to, a tree of operands and users in the use-def.
851 while (!WorkList.empty()) {
852 Value *V = WorkList.pop_back_val();
853 if (CurrentVisited.count(V))
854 continue;
855
856 // Ignore non-instructions, other than arguments.
857 if (!isa<Instruction>(V) && !isSource(V))
858 continue;
859
860 // If we've already visited this value from somewhere, bail now because
861 // the tree has already been explored.
862 // TODO: This could limit the transform, ie if we try to promote something
863 // from an i8 and fail first, before trying an i16.
864 if (AllVisited.count(V))
865 return false;
866
867 CurrentVisited.insert(V);
868 AllVisited.insert(V);
869
870 // Calls can be both sources and sinks.
871 if (isSink(V))
872 Sinks.insert(cast<Instruction>(V));
873
874 if (isSource(V))
875 Sources.insert(V);
876
877 if (!isSink(V) && !isSource(V)) {
878 if (auto *I = dyn_cast<Instruction>(V)) {
879 // Visit operands of any instruction visited.
880 for (auto &U : I->operands()) {
881 if (!AddLegalInst(U))
882 return false;
883 }
884 }
885 }
886
887 // Don't visit users of a node which isn't going to be mutated unless its a
888 // source.
889 if (isSource(V) || shouldPromote(V)) {
890 for (Use &U : V->uses()) {
891 if (!AddLegalInst(U.getUser()))
892 return false;
893 }
894 }
895 }
896
897 LLVM_DEBUG(dbgs() << "IR Promotion: Visited nodes:\n";
898 for (auto *I : CurrentVisited)
899 I->dump();
900 );
901
902 unsigned ToPromote = 0;
903 unsigned NonFreeArgs = 0;
904 SmallPtrSet<BasicBlock*, 4> Blocks;
905 for (auto *V : CurrentVisited) {
906 if (auto *I = dyn_cast<Instruction>(V))
907 Blocks.insert(I->getParent());
908
909 if (Sources.count(V)) {
910 if (auto *Arg = dyn_cast<Argument>(V))
911 if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr())
912 ++NonFreeArgs;
913 continue;
914 }
915
916 if (Sinks.count(cast<Instruction>(V)))
917 continue;
918 ++ToPromote;
919 }
920
921 // DAG optimizations should be able to handle these cases better, especially
922 // for function arguments.
923 if (ToPromote < 2 || (Blocks.size() == 1 && (NonFreeArgs > SafeWrap.size())))
924 return false;
925
926 if (ToPromote < 2)
927 return false;
928
929 IRPromoter Promoter(*Ctx, cast<IntegerType>(OrigTy), PromotedWidth,
930 CurrentVisited, Sources, Sinks, SafeWrap);
931 Promoter.Mutate();
932 return true;
933 }
934
runOnFunction(Function & F)935 bool TypePromotion::runOnFunction(Function &F) {
936 if (skipFunction(F) || DisablePromotion)
937 return false;
938
939 LLVM_DEBUG(dbgs() << "IR Promotion: Running on " << F.getName() << "\n");
940
941 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
942 if (!TPC)
943 return false;
944
945 AllVisited.clear();
946 SafeToPromote.clear();
947 SafeWrap.clear();
948 bool MadeChange = false;
949 const DataLayout &DL = F.getParent()->getDataLayout();
950 const TargetMachine &TM = TPC->getTM<TargetMachine>();
951 const TargetSubtargetInfo *SubtargetInfo = TM.getSubtargetImpl(F);
952 const TargetLowering *TLI = SubtargetInfo->getTargetLowering();
953 const TargetTransformInfo &TII =
954 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
955 RegisterBitWidth = TII.getRegisterBitWidth(false);
956 Ctx = &F.getParent()->getContext();
957
958 // Search up from icmps to try to promote their operands.
959 for (BasicBlock &BB : F) {
960 for (auto &I : BB) {
961 if (AllVisited.count(&I))
962 continue;
963
964 if (!isa<ICmpInst>(&I))
965 continue;
966
967 auto *ICmp = cast<ICmpInst>(&I);
968 // Skip signed or pointer compares
969 if (ICmp->isSigned() ||
970 !isa<IntegerType>(ICmp->getOperand(0)->getType()))
971 continue;
972
973 LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n");
974
975 for (auto &Op : ICmp->operands()) {
976 if (auto *I = dyn_cast<Instruction>(Op)) {
977 EVT SrcVT = TLI->getValueType(DL, I->getType());
978 if (SrcVT.isSimple() && TLI->isTypeLegal(SrcVT.getSimpleVT()))
979 break;
980
981 if (TLI->getTypeAction(ICmp->getContext(), SrcVT) !=
982 TargetLowering::TypePromoteInteger)
983 break;
984 EVT PromotedVT = TLI->getTypeToTransformTo(ICmp->getContext(), SrcVT);
985 if (RegisterBitWidth < PromotedVT.getFixedSizeInBits()) {
986 LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target register "
987 << "for promoted type\n");
988 break;
989 }
990
991 MadeChange |= TryToPromote(I, PromotedVT.getFixedSizeInBits());
992 break;
993 }
994 }
995 }
996 LLVM_DEBUG(if (verifyFunction(F, &dbgs())) {
997 dbgs() << F;
998 report_fatal_error("Broken function after type promotion");
999 });
1000 }
1001 if (MadeChange)
1002 LLVM_DEBUG(dbgs() << "After TypePromotion: " << F << "\n");
1003
1004 AllVisited.clear();
1005 SafeToPromote.clear();
1006 SafeWrap.clear();
1007
1008 return MadeChange;
1009 }
1010
1011 INITIALIZE_PASS_BEGIN(TypePromotion, DEBUG_TYPE, PASS_NAME, false, false)
1012 INITIALIZE_PASS_END(TypePromotion, DEBUG_TYPE, PASS_NAME, false, false)
1013
1014 char TypePromotion::ID = 0;
1015
createTypePromotionPass()1016 FunctionPass *llvm::createTypePromotionPass() {
1017 return new TypePromotion();
1018 }
1019