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