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