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