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