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