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 // The operands are zero extended (or have wrapped constants), so their
551 // sign bits no longer match those of the original narrow values.
552 if (auto *ICmp = dyn_cast<ICmpInst>(Val: I))
553 ICmp->setSameSign(false);
554
555 // Mutate the result type, unless this is an icmp or switch.
556 if (!isa<ICmpInst>(Val: I) && !isa<SwitchInst>(Val: I)) {
557 I->mutateType(Ty: ExtTy);
558 Promoted.insert(Ptr: I);
559 }
560 }
561}
562
563void IRPromoter::TruncateSinks() {
564 LLVM_DEBUG(dbgs() << "IR Promotion: Fixing up the sinks:\n");
565
566 IRBuilder<> Builder(M);
567
568 auto InsertTrunc = [&](Value *V, Type *TruncTy) -> Instruction * {
569 if (!isa<Instruction>(Val: V) || !isa<IntegerType>(Val: V->getType()))
570 return nullptr;
571
572 if ((!Promoted.count(Ptr: V) && !NewInsts.count(Ptr: V)) || Sources.count(key: V))
573 return nullptr;
574
575 LLVM_DEBUG(dbgs() << "IR Promotion: Creating " << *TruncTy << " Trunc for "
576 << *V << "\n");
577 Builder.SetInsertPoint(cast<Instruction>(Val: V));
578 auto *Trunc = dyn_cast<Instruction>(Val: Builder.CreateTrunc(V, DestTy: TruncTy));
579 if (Trunc)
580 NewInsts.insert(Ptr: Trunc);
581 return Trunc;
582 };
583
584 // Fix up any stores or returns that use the results of the promoted
585 // chain.
586 for (auto *I : Sinks) {
587 LLVM_DEBUG(dbgs() << "IR Promotion: For Sink: " << *I << "\n");
588
589 // Handle calls separately as we need to iterate over arg operands.
590 if (auto *Call = dyn_cast<CallInst>(Val: I)) {
591 for (unsigned i = 0; i < Call->arg_size(); ++i) {
592 Value *Arg = Call->getArgOperand(i);
593 Type *Ty = TruncTysMap[Call][i];
594 if (Instruction *Trunc = InsertTrunc(Arg, Ty)) {
595 Trunc->moveBefore(InsertPos: Call->getIterator());
596 Call->setArgOperand(i, v: Trunc);
597 }
598 }
599 continue;
600 }
601
602 // Special case switches because we need to truncate the condition.
603 if (auto *Switch = dyn_cast<SwitchInst>(Val: I)) {
604 Type *Ty = TruncTysMap[Switch][0];
605 if (Instruction *Trunc = InsertTrunc(Switch->getCondition(), Ty)) {
606 Trunc->moveBefore(InsertPos: Switch->getIterator());
607 Switch->setCondition(Trunc);
608 }
609 continue;
610 }
611
612 // Don't insert a trunc for a zext which can still legally promote.
613 // Nor insert a trunc when the input value to that trunc has the same width
614 // as the zext we are inserting it for. When this happens the input operand
615 // for the zext will be promoted to the same width as the zext's return type
616 // rendering that zext unnecessary. This zext gets removed before the end
617 // of the pass.
618 if (auto ZExt = dyn_cast<ZExtInst>(Val: I))
619 if (ZExt->getType()->getScalarSizeInBits() >= PromotedWidth)
620 continue;
621
622 // Now handle the others.
623 for (unsigned i = 0; i < I->getNumOperands(); ++i) {
624 Type *Ty = TruncTysMap[I][i];
625 if (Instruction *Trunc = InsertTrunc(I->getOperand(i), Ty)) {
626 Trunc->moveBefore(InsertPos: I->getIterator());
627 I->setOperand(i, Val: Trunc);
628 }
629 }
630 }
631}
632
633void IRPromoter::Cleanup() {
634 LLVM_DEBUG(dbgs() << "IR Promotion: Cleanup..\n");
635 // Some zexts will now have become redundant, along with their trunc
636 // operands, so remove them.
637 for (auto *V : Visited) {
638 if (!isa<ZExtInst>(Val: V))
639 continue;
640
641 auto ZExt = cast<ZExtInst>(Val: V);
642 if (ZExt->getDestTy() != ExtTy)
643 continue;
644
645 Value *Src = ZExt->getOperand(i_nocapture: 0);
646 if (ZExt->getSrcTy() == ZExt->getDestTy()) {
647 LLVM_DEBUG(dbgs() << "IR Promotion: Removing unnecessary cast: " << *ZExt
648 << "\n");
649 ReplaceAllUsersOfWith(From: ZExt, To: Src);
650 continue;
651 }
652
653 // We've inserted a trunc for a zext sink, but we already know that the
654 // input is in range, negating the need for the trunc.
655 if (NewInsts.count(Ptr: Src) && isa<TruncInst>(Val: Src)) {
656 auto *Trunc = cast<TruncInst>(Val: Src);
657 assert(Trunc->getOperand(0)->getType() == ExtTy &&
658 "expected inserted trunc to be operating on i32");
659 ReplaceAllUsersOfWith(From: ZExt, To: Trunc->getOperand(i_nocapture: 0));
660 }
661 }
662
663 for (auto *I : InstsToRemove) {
664 LLVM_DEBUG(dbgs() << "IR Promotion: Removing " << *I << "\n");
665 I->dropAllReferences();
666 }
667}
668
669void IRPromoter::ConvertTruncs() {
670 LLVM_DEBUG(dbgs() << "IR Promotion: Converting truncs..\n");
671 IRBuilder<> Builder(M);
672
673 for (auto *V : Visited) {
674 if (!isa<TruncInst>(Val: V) || isTruncToI1(V) || Sources.count(key: V))
675 continue;
676
677 auto *Trunc = cast<TruncInst>(Val: V);
678 Builder.SetInsertPoint(Trunc);
679 IntegerType *SrcTy = cast<IntegerType>(Val: Trunc->getOperand(i_nocapture: 0)->getType());
680 IntegerType *DestTy = cast<IntegerType>(Val: TruncTysMap[Trunc][0]);
681
682 unsigned NumBits = DestTy->getScalarSizeInBits();
683 ConstantInt *Mask =
684 ConstantInt::get(Ty: SrcTy, V: APInt::getMaxValue(numBits: NumBits).getZExtValue());
685 Value *Masked = Builder.CreateAnd(LHS: Trunc->getOperand(i_nocapture: 0), RHS: Mask);
686 if (SrcTy->getBitWidth() > ExtTy->getBitWidth())
687 Masked = Builder.CreateTrunc(V: Masked, DestTy: ExtTy);
688
689 if (auto *I = dyn_cast<Instruction>(Val: Masked))
690 NewInsts.insert(Ptr: I);
691
692 ReplaceAllUsersOfWith(From: Trunc, To: Masked);
693 }
694}
695
696void IRPromoter::Mutate() {
697 LLVM_DEBUG(dbgs() << "IR Promotion: Promoting use-def chains to "
698 << PromotedWidth << "-bits\n");
699
700 // Cache original types of the values that will likely need truncating
701 for (auto *I : Sinks) {
702 if (auto *Call = dyn_cast<CallInst>(Val: I)) {
703 for (Value *Arg : Call->args())
704 TruncTysMap[Call].push_back(Elt: Arg->getType());
705 } else if (auto *Switch = dyn_cast<SwitchInst>(Val: I))
706 TruncTysMap[I].push_back(Elt: Switch->getCondition()->getType());
707 else {
708 for (const Value *Op : I->operands())
709 TruncTysMap[I].push_back(Elt: Op->getType());
710 }
711 }
712 for (auto *V : Visited) {
713 if (!isa<TruncInst>(Val: V) || isTruncToI1(V) || Sources.count(key: V))
714 continue;
715 auto *Trunc = cast<TruncInst>(Val: V);
716 TruncTysMap[Trunc].push_back(Elt: Trunc->getDestTy());
717 }
718
719 // Insert zext instructions between sources and their users.
720 ExtendSources();
721
722 // Promote visited instructions, mutating their types in place.
723 PromoteTree();
724
725 // Convert any truncs, that aren't sources, into AND masks.
726 ConvertTruncs();
727
728 // Insert trunc instructions for use by calls, stores etc...
729 TruncateSinks();
730
731 // Finally, remove unecessary zexts and truncs, delete old instructions and
732 // clear the data structures.
733 Cleanup();
734
735 LLVM_DEBUG(dbgs() << "IR Promotion: Mutation complete\n");
736}
737
738/// We disallow booleans to make life easier when dealing with icmps but allow
739/// any other integer that fits in a scalar register. Void types are accepted
740/// so we can handle switches.
741bool TypePromotionImpl::isSupportedType(Value *V) {
742 Type *Ty = V->getType();
743
744 // Allow voids and pointers, these won't be promoted.
745 if (Ty->isVoidTy() || Ty->isPointerTy())
746 return true;
747
748 if (!isa<IntegerType>(Val: Ty) || cast<IntegerType>(Val: Ty)->getBitWidth() == 1 ||
749 cast<IntegerType>(Val: Ty)->getBitWidth() > RegisterBitWidth)
750 return false;
751
752 return LessOrEqualTypeSize(V);
753}
754
755/// We accept most instructions, as well as Arguments and ConstantInsts. We
756/// Disallow casts other than zext and truncs and only allow calls if their
757/// return value is zeroext. We don't allow opcodes that can introduce sign
758/// bits.
759bool TypePromotionImpl::isSupportedValue(Value *V) {
760 if (auto *I = dyn_cast<Instruction>(Val: V)) {
761 switch (I->getOpcode()) {
762 default:
763 return isa<BinaryOperator>(Val: I) && isSupportedType(V: I) &&
764 !GenerateSignBits(I);
765 case Instruction::GetElementPtr:
766 case Instruction::Store:
767 case Instruction::CondBr:
768 case Instruction::Switch:
769 return true;
770 case Instruction::PHI:
771 case Instruction::Select:
772 case Instruction::Ret:
773 case Instruction::Load:
774 return isSupportedType(V: I);
775 case Instruction::Trunc:
776 return isSupportedTruncToI1(V: I) || isSupportedType(V: I);
777 case Instruction::BitCast:
778 return I->getOperand(i: 0)->getType() == I->getType();
779 case Instruction::ZExt:
780 return isSupportedType(V: I->getOperand(i: 0));
781 case Instruction::ICmp:
782 // Now that we allow small types than TypeSize, only allow icmp of
783 // TypeSize because they will require a trunc to be legalised.
784 // TODO: Allow icmp of smaller types, and calculate at the end
785 // whether the transform would be beneficial.
786 if (isa<PointerType>(Val: I->getOperand(i: 0)->getType()))
787 return true;
788 return EqualTypeSize(V: I->getOperand(i: 0));
789 case Instruction::Call: {
790 // Special cases for calls as we need to check for zeroext
791 // TODO We should accept calls even if they don't have zeroext, as they
792 // can still be sinks.
793 auto *Call = cast<CallInst>(Val: I);
794 return isSupportedType(V: Call) &&
795 Call->hasRetAttr(Kind: Attribute::AttrKind::ZExt);
796 }
797 }
798 } else if (isa<Constant>(Val: V) && !isa<ConstantExpr>(Val: V)) {
799 return isSupportedType(V);
800 } else if (isa<Argument>(Val: V))
801 return isSupportedType(V);
802
803 return isa<BasicBlock>(Val: V);
804}
805
806/// Check that the type of V would be promoted and that the original type is
807/// smaller than the targeted promoted type. Check that we're not trying to
808/// promote something larger than our base 'TypeSize' type.
809bool TypePromotionImpl::isLegalToPromote(Value *V) {
810 auto *I = dyn_cast<Instruction>(Val: V);
811 if (!I)
812 return true;
813
814 if (SafeToPromote.count(Ptr: I))
815 return true;
816
817 if (isPromotedResultSafe(I) || isSafeWrap(I)) {
818 SafeToPromote.insert(Ptr: I);
819 return true;
820 }
821 return false;
822}
823
824bool TypePromotionImpl::TryToPromote(Value *V, unsigned PromotedWidth,
825 const LoopInfo &LI) {
826 Type *OrigTy = V->getType();
827 TypeSize = OrigTy->getPrimitiveSizeInBits().getFixedValue();
828 SafeToPromote.clear();
829 SafeWrap.clear();
830
831 if (!isSupportedValue(V) || !shouldPromote(V) || !isLegalToPromote(V))
832 return false;
833
834 LLVM_DEBUG(dbgs() << "IR Promotion: TryToPromote: " << *V << ", from "
835 << TypeSize << " bits to " << PromotedWidth << "\n");
836
837 SetVector<Value *> WorkList;
838 SetVector<Value *> Sources;
839 SetVector<Instruction *> Sinks;
840 SetVector<Value *> CurrentVisited;
841 WorkList.insert(X: V);
842
843 // Return true if V was added to the worklist as a supported instruction,
844 // if it was already visited, or if we don't need to explore it (e.g.
845 // pointer values and GEPs), and false otherwise.
846 auto AddLegalInst = [&](Value *V) {
847 if (CurrentVisited.count(key: V))
848 return true;
849
850 // Skip promoting GEPs as their indices should have already been
851 // canonicalized to pointer width.
852 if (isa<GetElementPtrInst>(Val: V))
853 return false;
854
855 if (!isSupportedValue(V) || (shouldPromote(V) && !isLegalToPromote(V))) {
856 LLVM_DEBUG(dbgs() << "IR Promotion: Can't handle: " << *V << "\n");
857 return false;
858 }
859
860 WorkList.insert(X: V);
861 return true;
862 };
863
864 // Iterate through, and add to, a tree of operands and users in the use-def.
865 while (!WorkList.empty()) {
866 Value *V = WorkList.pop_back_val();
867 if (CurrentVisited.count(key: V))
868 continue;
869
870 // Ignore non-instructions, other than arguments.
871 if (!isa<Instruction>(Val: V) && !isSource(V))
872 continue;
873
874 // If we've already visited this value from somewhere, bail now because
875 // the tree has already been explored.
876 // TODO: This could limit the transform, ie if we try to promote something
877 // from an i8 and fail first, before trying an i16.
878 if (!AllVisited.insert(Ptr: V).second)
879 return false;
880
881 CurrentVisited.insert(X: V);
882
883 // Calls can be both sources and sinks.
884 if (isSink(V))
885 Sinks.insert(X: cast<Instruction>(Val: V));
886
887 if (isSource(V))
888 Sources.insert(X: V);
889
890 if (!isSink(V) && !isSource(V)) {
891 if (auto *I = dyn_cast<Instruction>(Val: V)) {
892 // Visit operands of any instruction visited.
893 for (auto &U : I->operands()) {
894 // Skip condition of selects.
895 if (isa<SelectInst>(Val: I) && U.getOperandNo() == 0)
896 continue;
897 if (!AddLegalInst(U))
898 return false;
899 }
900 }
901 }
902
903 // Don't visit users of a node which isn't going to be mutated unless its a
904 // source.
905 if (isSource(V) || shouldPromote(V)) {
906 for (Use &U : V->uses()) {
907 if (!AddLegalInst(U.getUser()))
908 return false;
909 }
910 }
911 }
912
913 LLVM_DEBUG({
914 dbgs() << "IR Promotion: Visited nodes:\n";
915 for (auto *I : CurrentVisited)
916 I->dump();
917 });
918
919 unsigned ToPromote = 0;
920 unsigned NonFreeArgs = 0;
921 unsigned NonLoopSources = 0, LoopSinks = 0;
922 SmallPtrSet<BasicBlock *, 4> Blocks;
923 for (auto *CV : CurrentVisited) {
924 if (auto *I = dyn_cast<Instruction>(Val: CV))
925 Blocks.insert(Ptr: I->getParent());
926
927 if (Sources.count(key: CV)) {
928 if (auto *Arg = dyn_cast<Argument>(Val: CV))
929 if (!Arg->hasZExtAttr() && !Arg->hasSExtAttr())
930 ++NonFreeArgs;
931 if (!isa<Instruction>(Val: CV) ||
932 !LI.getLoopFor(BB: cast<Instruction>(Val: CV)->getParent()))
933 ++NonLoopSources;
934 continue;
935 }
936
937 if (isa<PHINode>(Val: CV))
938 continue;
939 if (LI.getLoopFor(BB: cast<Instruction>(Val: CV)->getParent()))
940 ++LoopSinks;
941 if (Sinks.count(key: cast<Instruction>(Val: CV)))
942 continue;
943 ++ToPromote;
944 }
945
946 // DAG optimizations should be able to handle these cases better, especially
947 // for function arguments.
948 if (!isa<PHINode>(Val: V) && !(LoopSinks && NonLoopSources) &&
949 (ToPromote < 2 || (Blocks.size() == 1 && NonFreeArgs > SafeWrap.size())))
950 return false;
951
952 IRPromoter Promoter(*M, PromotedWidth, CurrentVisited, Sources, Sinks,
953 SafeWrap, InstsToRemove);
954 Promoter.Mutate();
955 return true;
956}
957
958bool TypePromotionImpl::run(Function &F, const TargetMachine *TM,
959 const TargetTransformInfo &TTI,
960 const LoopInfo &LI) {
961 if (DisablePromotion)
962 return false;
963
964 LLVM_DEBUG(dbgs() << "IR Promotion: Running on " << F.getName() << "\n");
965
966 AllVisited.clear();
967 SafeToPromote.clear();
968 SafeWrap.clear();
969 bool MadeChange = false;
970 const DataLayout &DL = F.getDataLayout();
971 const TargetSubtargetInfo *SubtargetInfo = TM->getSubtargetImpl(F);
972 TLI = SubtargetInfo->getTargetLowering();
973 RegisterBitWidth =
974 TTI.getRegisterBitWidth(K: TargetTransformInfo::RGK_Scalar).getFixedValue();
975 M = F.getParent();
976 Ctx = &F.getContext();
977
978 // Return the preferred integer width of the instruction, or zero if we
979 // shouldn't try.
980 auto GetPromoteWidth = [&](Instruction *I) -> uint32_t {
981 if (!isa<IntegerType>(Val: I->getType()))
982 return 0;
983
984 EVT SrcVT = TLI->getValueType(DL, Ty: I->getType());
985 if (SrcVT.isSimple() && TLI->isTypeLegal(VT: SrcVT.getSimpleVT()))
986 return 0;
987
988 if (TLI->getTypeAction(Context&: *Ctx, VT: SrcVT) != TargetLowering::TypePromoteInteger)
989 return 0;
990
991 EVT PromotedVT = TLI->getTypeToTransformTo(Context&: *Ctx, VT: SrcVT);
992 if (TLI->isSExtCheaperThanZExt(FromTy: SrcVT, ToTy: PromotedVT))
993 return 0;
994 if (RegisterBitWidth < PromotedVT.getFixedSizeInBits()) {
995 LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target register "
996 << "for promoted type\n");
997 return 0;
998 }
999
1000 // TODO: Should we prefer to use RegisterBitWidth instead?
1001 return PromotedVT.getFixedSizeInBits();
1002 };
1003
1004 auto BBIsInLoop = [&](BasicBlock *BB) -> bool {
1005 for (auto *L : LI)
1006 if (L->contains(BB))
1007 return true;
1008 return false;
1009 };
1010
1011 for (BasicBlock &BB : F) {
1012 for (Instruction &I : BB) {
1013 if (AllVisited.count(Ptr: &I))
1014 continue;
1015
1016 if (isa<ZExtInst>(Val: &I) && isa<PHINode>(Val: I.getOperand(i: 0)) &&
1017 isa<IntegerType>(Val: I.getType()) && BBIsInLoop(&BB)) {
1018 LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: "
1019 << *I.getOperand(0) << "\n");
1020 EVT ZExtVT = TLI->getValueType(DL, Ty: I.getType());
1021 Instruction *Phi = static_cast<Instruction *>(I.getOperand(i: 0));
1022 auto PromoteWidth = ZExtVT.getFixedSizeInBits();
1023 if (RegisterBitWidth < PromoteWidth) {
1024 LLVM_DEBUG(dbgs() << "IR Promotion: Couldn't find target "
1025 << "register for ZExt type\n");
1026 continue;
1027 }
1028 MadeChange |= TryToPromote(V: Phi, PromotedWidth: PromoteWidth, LI);
1029 } else if (auto *ICmp = dyn_cast<ICmpInst>(Val: &I)) {
1030 // Search up from icmps to try to promote their operands.
1031 // Skip signed or pointer compares
1032 if (ICmp->isSigned())
1033 continue;
1034
1035 LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *ICmp << "\n");
1036
1037 for (auto &Op : ICmp->operands()) {
1038 if (auto *OpI = dyn_cast<Instruction>(Val&: Op)) {
1039 if (auto PromotedWidth = GetPromoteWidth(OpI)) {
1040 MadeChange |= TryToPromote(V: OpI, PromotedWidth, LI);
1041 break;
1042 }
1043 }
1044 }
1045 } else if (isTruncToI1(V: &I)) {
1046 // Like an unsigned icmp, a scalar trunc to i1 is a boolean boundary.
1047 auto *Trunc = cast<TruncInst>(Val: &I);
1048 LLVM_DEBUG(dbgs() << "IR Promotion: Searching from: " << *Trunc
1049 << "\n");
1050
1051 if (auto *OpI = dyn_cast<Instruction>(Val: Trunc->getOperand(i_nocapture: 0))) {
1052 if (auto PromotedWidth = GetPromoteWidth(OpI))
1053 MadeChange |= TryToPromote(V: OpI, PromotedWidth, LI);
1054 }
1055 }
1056 }
1057 if (!InstsToRemove.empty()) {
1058 for (auto *I : InstsToRemove)
1059 I->eraseFromParent();
1060 InstsToRemove.clear();
1061 }
1062 }
1063
1064 AllVisited.clear();
1065 SafeToPromote.clear();
1066 SafeWrap.clear();
1067
1068 return MadeChange;
1069}
1070
1071INITIALIZE_PASS_BEGIN(TypePromotionLegacy, DEBUG_TYPE, PASS_NAME, false, false)
1072INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1073INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
1074INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1075INITIALIZE_PASS_END(TypePromotionLegacy, DEBUG_TYPE, PASS_NAME, false, false)
1076
1077char TypePromotionLegacy::ID = 0;
1078
1079bool TypePromotionLegacy::runOnFunction(Function &F) {
1080 if (skipFunction(F))
1081 return false;
1082
1083 auto &TPC = getAnalysis<TargetPassConfig>();
1084 auto *TM = &TPC.getTM<TargetMachine>();
1085 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1086 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1087
1088 TypePromotionImpl TP;
1089 return TP.run(F, TM, TTI, LI);
1090}
1091
1092FunctionPass *llvm::createTypePromotionLegacyPass() {
1093 return new TypePromotionLegacy();
1094}
1095
1096PreservedAnalyses TypePromotionPass::run(Function &F,
1097 FunctionAnalysisManager &AM) {
1098 auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
1099 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
1100 TypePromotionImpl TP;
1101
1102 bool Changed = TP.run(F, TM, TTI, LI);
1103 if (!Changed)
1104 return PreservedAnalyses::all();
1105
1106 PreservedAnalyses PA;
1107 PA.preserveSet<CFGAnalyses>();
1108 return PA;
1109}
1110