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

source code of llvm/lib/CodeGen/TypePromotion.cpp