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