1//===- TruncInstCombine.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// TruncInstCombine - looks for expression graphs post-dominated by TruncInst
10// and for each eligible graph, it will create a reduced bit-width expression,
11// replace the old expression with this new one and remove the old expression.
12// Eligible expression graph is such that:
13// 1. Contains only supported instructions.
14// 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
15// 3. Can be evaluated into type with reduced legal bit-width.
16// 4. All instructions in the graph must not have users outside the graph.
17// The only exception is for {ZExt, SExt}Inst with operand type equal to
18// the new reduced type evaluated in (3).
19//
20// The motivation for this optimization is that evaluating and expression using
21// smaller bit-width is preferable, especially for vectorization where we can
22// fit more values in one vectorized instruction. In addition, this optimization
23// may decrease the number of cast instructions, but will not increase it.
24//
25//===----------------------------------------------------------------------===//
26
27#include "AggressiveInstCombineInternal.h"
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/Statistic.h"
30#include "llvm/Analysis/ConstantFolding.h"
31#include "llvm/IR/DataLayout.h"
32#include "llvm/IR/Dominators.h"
33#include "llvm/IR/IRBuilder.h"
34#include "llvm/IR/Instruction.h"
35#include "llvm/Support/KnownBits.h"
36
37using namespace llvm;
38
39#define DEBUG_TYPE "aggressive-instcombine"
40
41STATISTIC(NumExprsReduced, "Number of truncations eliminated by reducing bit "
42 "width of expression graph");
43STATISTIC(NumInstrsReduced,
44 "Number of instructions whose bit width was reduced");
45
46/// Return whether operand \p OpNo of \p I is reducible.
47static bool isRelevantOperand(const Instruction *I, unsigned OpNo) {
48 unsigned Opc = I->getOpcode();
49 switch (Opc) {
50 case Instruction::Trunc:
51 case Instruction::ZExt:
52 case Instruction::SExt:
53 // These CastInst are considered leaves of the evaluated expression, thus,
54 // their operands are not relevent.
55 return false;
56 case Instruction::Add:
57 case Instruction::Sub:
58 case Instruction::Mul:
59 case Instruction::And:
60 case Instruction::Or:
61 case Instruction::Xor:
62 case Instruction::Shl:
63 case Instruction::LShr:
64 case Instruction::AShr:
65 case Instruction::UDiv:
66 case Instruction::URem:
67 return true;
68 case Instruction::InsertElement:
69 return OpNo < 2;
70 case Instruction::ExtractElement:
71 return OpNo == 0;
72 case Instruction::Select:
73 return OpNo != 0;
74 case Instruction::PHI:
75 return true;
76 default:
77 llvm_unreachable("Unreachable!");
78 }
79}
80
81/// Given an instruction and a container, it fills all the relevant operands of
82/// that instruction, with respect to the Trunc expression graph optimizaton.
83static void getRelevantOperands(Instruction *I, SmallVectorImpl<Value *> &Ops) {
84 for (Use &Op : I->operands())
85 if (isRelevantOperand(I, OpNo: Op.getOperandNo()))
86 Ops.push_back(Elt: Op.get());
87}
88
89bool TruncInstCombine::buildTruncExpressionGraph() {
90 SmallVector<Value *, 8> Worklist;
91 SmallVector<Instruction *, 8> Stack;
92 // Clear old instructions info.
93 InstInfoMap.clear();
94
95 Worklist.push_back(Elt: CurrentTruncInst->getOperand(i_nocapture: 0));
96
97 while (!Worklist.empty()) {
98 Value *Curr = Worklist.back();
99
100 if (isa<Constant>(Val: Curr)) {
101 Worklist.pop_back();
102 continue;
103 }
104
105 auto *I = dyn_cast<Instruction>(Val: Curr);
106 if (!I)
107 return false;
108
109 if (!Stack.empty() && Stack.back() == I) {
110 // Already handled all instruction operands, can remove it from both the
111 // Worklist and the Stack, and add it to the instruction info map.
112 Worklist.pop_back();
113 Stack.pop_back();
114 // Insert I to the Info map.
115 InstInfoMap.try_emplace(Key: I);
116 continue;
117 }
118
119 if (InstInfoMap.count(Key: I)) {
120 Worklist.pop_back();
121 continue;
122 }
123
124 // Add the instruction to the stack before start handling its operands.
125 Stack.push_back(Elt: I);
126
127 unsigned Opc = I->getOpcode();
128 switch (Opc) {
129 case Instruction::Trunc:
130 case Instruction::ZExt:
131 case Instruction::SExt:
132 // trunc(trunc(x)) -> trunc(x)
133 // trunc(ext(x)) -> ext(x) if the source type is smaller than the new dest
134 // trunc(ext(x)) -> trunc(x) if the source type is larger than the new
135 // dest
136 break;
137 case Instruction::Add:
138 case Instruction::Sub:
139 case Instruction::Mul:
140 case Instruction::And:
141 case Instruction::Or:
142 case Instruction::Xor:
143 case Instruction::Shl:
144 case Instruction::LShr:
145 case Instruction::AShr:
146 case Instruction::UDiv:
147 case Instruction::URem:
148 case Instruction::InsertElement:
149 case Instruction::ExtractElement:
150 case Instruction::Select: {
151 SmallVector<Value *, 2> Operands;
152 getRelevantOperands(I, Ops&: Operands);
153 append_range(C&: Worklist, R&: Operands);
154 break;
155 }
156 case Instruction::PHI: {
157 SmallVector<Value *, 2> Operands;
158 getRelevantOperands(I, Ops&: Operands);
159 // Add only operands not in Stack to prevent cycle
160 for (auto *Op : Operands)
161 if (!llvm::is_contained(Range&: Stack, Element: Op))
162 Worklist.push_back(Elt: Op);
163 break;
164 }
165 default:
166 // TODO: Can handle more cases here:
167 // 1. shufflevector
168 // 2. sdiv, srem
169 // ...
170 return false;
171 }
172 }
173 return true;
174}
175
176unsigned TruncInstCombine::getMinBitWidth() {
177 SmallVector<Value *, 8> Worklist;
178 SmallVector<Instruction *, 8> Stack;
179
180 Value *Src = CurrentTruncInst->getOperand(i_nocapture: 0);
181 Type *DstTy = CurrentTruncInst->getType();
182 unsigned TruncBitWidth = DstTy->getScalarSizeInBits();
183 unsigned OrigBitWidth =
184 CurrentTruncInst->getOperand(i_nocapture: 0)->getType()->getScalarSizeInBits();
185
186 if (isa<Constant>(Val: Src))
187 return TruncBitWidth;
188
189 Worklist.push_back(Elt: Src);
190 InstInfoMap[cast<Instruction>(Val: Src)].ValidBitWidth = TruncBitWidth;
191
192 while (!Worklist.empty()) {
193 Value *Curr = Worklist.back();
194
195 if (isa<Constant>(Val: Curr)) {
196 Worklist.pop_back();
197 continue;
198 }
199
200 // Otherwise, it must be an instruction.
201 auto *I = cast<Instruction>(Val: Curr);
202
203 auto &Info = InstInfoMap[I];
204
205 SmallVector<Value *, 2> Operands;
206 getRelevantOperands(I, Ops&: Operands);
207
208 if (!Stack.empty() && Stack.back() == I) {
209 // Already handled all instruction operands, can remove it from both, the
210 // Worklist and the Stack, and update MinBitWidth.
211 Worklist.pop_back();
212 Stack.pop_back();
213 for (auto *Operand : Operands)
214 if (auto *IOp = dyn_cast<Instruction>(Val: Operand))
215 Info.MinBitWidth =
216 std::max(a: Info.MinBitWidth, b: InstInfoMap[IOp].MinBitWidth);
217 continue;
218 }
219
220 // Add the instruction to the stack before start handling its operands.
221 Stack.push_back(Elt: I);
222 unsigned ValidBitWidth = Info.ValidBitWidth;
223
224 // Update minimum bit-width before handling its operands. This is required
225 // when the instruction is part of a loop.
226 Info.MinBitWidth = std::max(a: Info.MinBitWidth, b: Info.ValidBitWidth);
227
228 for (auto *Operand : Operands)
229 if (auto *IOp = dyn_cast<Instruction>(Val: Operand)) {
230 // If we already calculated the minimum bit-width for this valid
231 // bit-width, or for a smaller valid bit-width, then just keep the
232 // answer we already calculated.
233 unsigned IOpBitwidth = InstInfoMap.lookup(Key: IOp).ValidBitWidth;
234 if (IOpBitwidth >= ValidBitWidth)
235 continue;
236 InstInfoMap[IOp].ValidBitWidth = ValidBitWidth;
237 Worklist.push_back(Elt: IOp);
238 }
239 }
240 unsigned MinBitWidth = InstInfoMap.lookup(Key: cast<Instruction>(Val: Src)).MinBitWidth;
241 assert(MinBitWidth >= TruncBitWidth);
242
243 if (MinBitWidth > TruncBitWidth) {
244 // In this case reducing expression with vector type might generate a new
245 // vector type, which is not preferable as it might result in generating
246 // sub-optimal code.
247 if (DstTy->isVectorTy())
248 return OrigBitWidth;
249 // Use the smallest integer type in the range [MinBitWidth, OrigBitWidth).
250 Type *Ty = DL.getSmallestLegalIntType(C&: DstTy->getContext(), Width: MinBitWidth);
251 // Update minimum bit-width with the new destination type bit-width if
252 // succeeded to find such, otherwise, with original bit-width.
253 MinBitWidth = Ty ? Ty->getScalarSizeInBits() : OrigBitWidth;
254 } else { // MinBitWidth == TruncBitWidth
255 // In this case the expression can be evaluated with the trunc instruction
256 // destination type, and trunc instruction can be omitted. However, we
257 // should not perform the evaluation if the original type is a legal scalar
258 // type and the target type is illegal.
259 bool FromLegal = MinBitWidth == 1 || DL.isLegalInteger(Width: OrigBitWidth);
260 bool ToLegal = MinBitWidth == 1 || DL.isLegalInteger(Width: MinBitWidth);
261 if (!DstTy->isVectorTy() && FromLegal && !ToLegal)
262 return OrigBitWidth;
263 }
264 return MinBitWidth;
265}
266
267Type *TruncInstCombine::getBestTruncatedType() {
268 if (!buildTruncExpressionGraph())
269 return nullptr;
270
271 // We don't want to duplicate instructions, which isn't profitable. Thus, we
272 // can't shrink something that has multiple uses, unless all uses can be
273 // reduced and all users are post-dominated by the trunc instruction,
274 // i.e., were visited during the expression evaluation.
275 unsigned DesiredBitWidth = 0;
276 for (auto Itr : InstInfoMap) {
277 Instruction *I = Itr.first;
278 if (I->hasOneUse())
279 continue;
280 bool IsExtInst = (isa<ZExtInst>(Val: I) || isa<SExtInst>(Val: I));
281 for (Use &U : I->uses())
282 if (auto *UI = dyn_cast<Instruction>(Val: U.getUser()))
283 if (UI != CurrentTruncInst &&
284 (!InstInfoMap.count(Key: UI) ||
285 !isRelevantOperand(I: UI, OpNo: U.getOperandNo()))) {
286 if (!IsExtInst)
287 return nullptr;
288 // If this is an extension from the dest type, we can eliminate it,
289 // even if it has multiple users. Thus, update the DesiredBitWidth and
290 // validate all extension instructions agrees on same DesiredBitWidth.
291 unsigned ExtInstBitWidth =
292 I->getOperand(i: 0)->getType()->getScalarSizeInBits();
293 if (DesiredBitWidth && DesiredBitWidth != ExtInstBitWidth)
294 return nullptr;
295 DesiredBitWidth = ExtInstBitWidth;
296 }
297 }
298
299 unsigned OrigBitWidth =
300 CurrentTruncInst->getOperand(i_nocapture: 0)->getType()->getScalarSizeInBits();
301
302 // Initialize MinBitWidth for shift instructions with the minimum number
303 // that is greater than shift amount (i.e. shift amount + 1).
304 // For `lshr` adjust MinBitWidth so that all potentially truncated
305 // bits of the value-to-be-shifted are zeros.
306 // For `ashr` adjust MinBitWidth so that all potentially truncated
307 // bits of the value-to-be-shifted are sign bits (all zeros or ones)
308 // and even one (first) untruncated bit is sign bit.
309 // Exit early if MinBitWidth is not less than original bitwidth.
310 for (auto &Itr : InstInfoMap) {
311 Instruction *I = Itr.first;
312 if (I->isShift()) {
313 KnownBits KnownRHS = computeKnownBits(V: I->getOperand(i: 1));
314 unsigned MinBitWidth = KnownRHS.getMaxValue()
315 .uadd_sat(RHS: APInt(OrigBitWidth, 1))
316 .getLimitedValue(Limit: OrigBitWidth);
317 if (MinBitWidth == OrigBitWidth)
318 return nullptr;
319 if (I->getOpcode() == Instruction::LShr) {
320 KnownBits KnownLHS = computeKnownBits(V: I->getOperand(i: 0));
321 MinBitWidth =
322 std::max(a: MinBitWidth, b: KnownLHS.getMaxValue().getActiveBits());
323 }
324 if (I->getOpcode() == Instruction::AShr) {
325 unsigned NumSignBits = ComputeNumSignBits(V: I->getOperand(i: 0));
326 MinBitWidth = std::max(a: MinBitWidth, b: OrigBitWidth - NumSignBits + 1);
327 }
328 if (MinBitWidth >= OrigBitWidth)
329 return nullptr;
330 Itr.second.MinBitWidth = MinBitWidth;
331 }
332 if (I->getOpcode() == Instruction::UDiv ||
333 I->getOpcode() == Instruction::URem) {
334 unsigned MinBitWidth = 0;
335 for (const auto &Op : I->operands()) {
336 KnownBits Known = computeKnownBits(V: Op);
337 MinBitWidth =
338 std::max(a: Known.getMaxValue().getActiveBits(), b: MinBitWidth);
339 if (MinBitWidth >= OrigBitWidth)
340 return nullptr;
341 }
342 Itr.second.MinBitWidth = MinBitWidth;
343 }
344 }
345
346 // Calculate minimum allowed bit-width allowed for shrinking the currently
347 // visited truncate's operand.
348 unsigned MinBitWidth = getMinBitWidth();
349
350 // Check that we can shrink to smaller bit-width than original one and that
351 // it is similar to the DesiredBitWidth is such exists.
352 if (MinBitWidth >= OrigBitWidth ||
353 (DesiredBitWidth && DesiredBitWidth != MinBitWidth))
354 return nullptr;
355
356 return IntegerType::get(C&: CurrentTruncInst->getContext(), NumBits: MinBitWidth);
357}
358
359/// Given a reduced scalar type \p Ty and a \p V value, return a reduced type
360/// for \p V, according to its type, if it vector type, return the vector
361/// version of \p Ty, otherwise return \p Ty.
362static Type *getReducedType(Value *V, Type *Ty) {
363 assert(Ty && !Ty->isVectorTy() && "Expect Scalar Type");
364 if (auto *VTy = dyn_cast<VectorType>(Val: V->getType()))
365 return VectorType::get(ElementType: Ty, EC: VTy->getElementCount());
366 return Ty;
367}
368
369Value *TruncInstCombine::getReducedOperand(Value *V, Type *SclTy) {
370 Type *Ty = getReducedType(V, Ty: SclTy);
371 if (auto *C = dyn_cast<Constant>(Val: V)) {
372 C = ConstantExpr::getTrunc(C, Ty);
373 // If we got a constantexpr back, try to simplify it with DL info.
374 return ConstantFoldConstant(C, DL, TLI: &TLI);
375 }
376
377 auto *I = cast<Instruction>(Val: V);
378 Info Entry = InstInfoMap.lookup(Key: I);
379 assert(Entry.NewValue);
380 return Entry.NewValue;
381}
382
383void TruncInstCombine::ReduceExpressionGraph(Type *SclTy) {
384 NumInstrsReduced += InstInfoMap.size();
385 // Pairs of old and new phi-nodes
386 SmallVector<std::pair<PHINode *, PHINode *>, 2> OldNewPHINodes;
387 for (auto &Itr : InstInfoMap) { // Forward
388 Instruction *I = Itr.first;
389 TruncInstCombine::Info &NodeInfo = Itr.second;
390
391 assert(!NodeInfo.NewValue && "Instruction has been evaluated");
392
393 IRBuilder<> Builder(I);
394 Value *Res = nullptr;
395 unsigned Opc = I->getOpcode();
396 switch (Opc) {
397 case Instruction::Trunc:
398 case Instruction::ZExt:
399 case Instruction::SExt: {
400 Type *Ty = getReducedType(V: I, Ty: SclTy);
401 // If the source type of the cast is the type we're trying for then we can
402 // just return the source. There's no need to insert it because it is not
403 // new.
404 if (I->getOperand(i: 0)->getType() == Ty) {
405 assert(!isa<TruncInst>(I) && "Cannot reach here with TruncInst");
406 NodeInfo.NewValue = I->getOperand(i: 0);
407 continue;
408 }
409 // Otherwise, must be the same type of cast, so just reinsert a new one.
410 // This also handles the case of zext(trunc(x)) -> zext(x).
411 Res = Builder.CreateIntCast(V: I->getOperand(i: 0), DestTy: Ty,
412 isSigned: Opc == Instruction::SExt);
413
414 // Update Worklist entries with new value if needed.
415 // There are three possible changes to the Worklist:
416 // 1. Update Old-TruncInst -> New-TruncInst.
417 // 2. Remove Old-TruncInst (if New node is not TruncInst).
418 // 3. Add New-TruncInst (if Old node was not TruncInst).
419 auto *Entry = find(Range&: Worklist, Val: I);
420 if (Entry != Worklist.end()) {
421 if (auto *NewCI = dyn_cast<TruncInst>(Val: Res))
422 *Entry = NewCI;
423 else
424 Worklist.erase(CI: Entry);
425 } else if (auto *NewCI = dyn_cast<TruncInst>(Val: Res))
426 Worklist.push_back(Elt: NewCI);
427 break;
428 }
429 case Instruction::Add:
430 case Instruction::Sub:
431 case Instruction::Mul:
432 case Instruction::And:
433 case Instruction::Or:
434 case Instruction::Xor:
435 case Instruction::Shl:
436 case Instruction::LShr:
437 case Instruction::AShr:
438 case Instruction::UDiv:
439 case Instruction::URem: {
440 Value *LHS = getReducedOperand(V: I->getOperand(i: 0), SclTy);
441 Value *RHS = getReducedOperand(V: I->getOperand(i: 1), SclTy);
442 Res = Builder.CreateBinOp(Opc: (Instruction::BinaryOps)Opc, LHS, RHS);
443 // Preserve `exact` flag since truncation doesn't change exactness
444 if (auto *PEO = dyn_cast<PossiblyExactOperator>(Val: I))
445 if (auto *ResI = dyn_cast<Instruction>(Val: Res))
446 ResI->setIsExact(PEO->isExact());
447 break;
448 }
449 case Instruction::ExtractElement: {
450 Value *Vec = getReducedOperand(V: I->getOperand(i: 0), SclTy);
451 Value *Idx = I->getOperand(i: 1);
452 Res = Builder.CreateExtractElement(Vec, Idx);
453 break;
454 }
455 case Instruction::InsertElement: {
456 Value *Vec = getReducedOperand(V: I->getOperand(i: 0), SclTy);
457 Value *NewElt = getReducedOperand(V: I->getOperand(i: 1), SclTy);
458 Value *Idx = I->getOperand(i: 2);
459 Res = Builder.CreateInsertElement(Vec, NewElt, Idx);
460 break;
461 }
462 case Instruction::Select: {
463 Value *Op0 = I->getOperand(i: 0);
464 Value *LHS = getReducedOperand(V: I->getOperand(i: 1), SclTy);
465 Value *RHS = getReducedOperand(V: I->getOperand(i: 2), SclTy);
466 Res = Builder.CreateSelect(C: Op0, True: LHS, False: RHS, Name: "", MDFrom: I);
467 break;
468 }
469 case Instruction::PHI: {
470 Res = Builder.CreatePHI(Ty: getReducedType(V: I, Ty: SclTy), NumReservedValues: I->getNumOperands());
471 OldNewPHINodes.push_back(
472 Elt: std::make_pair(x: cast<PHINode>(Val: I), y: cast<PHINode>(Val: Res)));
473 break;
474 }
475 default:
476 llvm_unreachable("Unhandled instruction");
477 }
478
479 NodeInfo.NewValue = Res;
480 if (auto *ResI = dyn_cast<Instruction>(Val: Res))
481 ResI->takeName(V: I);
482 }
483
484 for (auto &Node : OldNewPHINodes) {
485 PHINode *OldPN = Node.first;
486 PHINode *NewPN = Node.second;
487 for (auto Incoming : zip(t: OldPN->incoming_values(), u: OldPN->blocks()))
488 NewPN->addIncoming(V: getReducedOperand(V: std::get<0>(t&: Incoming), SclTy),
489 BB: std::get<1>(t&: Incoming));
490 }
491
492 Value *Res = getReducedOperand(V: CurrentTruncInst->getOperand(i_nocapture: 0), SclTy);
493 Type *DstTy = CurrentTruncInst->getType();
494 if (Res->getType() != DstTy) {
495 IRBuilder<> Builder(CurrentTruncInst);
496 Res = Builder.CreateIntCast(V: Res, DestTy: DstTy, isSigned: false);
497 if (auto *ResI = dyn_cast<Instruction>(Val: Res))
498 ResI->takeName(V: CurrentTruncInst);
499 }
500 CurrentTruncInst->replaceAllUsesWith(V: Res);
501
502 // Erase old expression graph, which was replaced by the reduced expression
503 // graph.
504 CurrentTruncInst->eraseFromParent();
505 // First, erase old phi-nodes and its uses
506 for (auto &Node : OldNewPHINodes) {
507 PHINode *OldPN = Node.first;
508 OldPN->replaceAllUsesWith(V: PoisonValue::get(T: OldPN->getType()));
509 InstInfoMap.erase(Key: OldPN);
510 OldPN->eraseFromParent();
511 }
512 // Now we have expression graph turned into dag.
513 // We iterate backward, which means we visit the instruction before we
514 // visit any of its operands, this way, when we get to the operand, we already
515 // removed the instructions (from the expression dag) that uses it.
516 for (auto &I : llvm::reverse(C&: InstInfoMap)) {
517 // We still need to check that the instruction has no users before we erase
518 // it, because {SExt, ZExt}Inst Instruction might have other users that was
519 // not reduced, in such case, we need to keep that instruction.
520 if (I.first->use_empty())
521 I.first->eraseFromParent();
522 else
523 assert((isa<SExtInst>(I.first) || isa<ZExtInst>(I.first)) &&
524 "Only {SExt, ZExt}Inst might have unreduced users");
525 }
526}
527
528bool TruncInstCombine::run(Function &F) {
529 bool MadeIRChange = false;
530
531 // Collect all TruncInst in the function into the Worklist for evaluating.
532 for (auto &BB : F) {
533 // Ignore unreachable basic block.
534 if (!DT.isReachableFromEntry(A: &BB))
535 continue;
536 for (auto &I : BB)
537 if (auto *CI = dyn_cast<TruncInst>(Val: &I))
538 Worklist.push_back(Elt: CI);
539 }
540
541 // Process all TruncInst in the Worklist, for each instruction:
542 // 1. Check if it dominates an eligible expression graph to be reduced.
543 // 2. Create a reduced expression graph and replace the old one with it.
544 while (!Worklist.empty()) {
545 CurrentTruncInst = Worklist.pop_back_val();
546
547 if (Type *NewDstSclTy = getBestTruncatedType()) {
548 LLVM_DEBUG(
549 dbgs() << "ICE: TruncInstCombine reducing type of expression graph "
550 "dominated by: "
551 << CurrentTruncInst << '\n');
552 ReduceExpressionGraph(SclTy: NewDstSclTy);
553 ++NumExprsReduced;
554 MadeIRChange = true;
555 }
556 }
557
558 return MadeIRChange;
559}
560