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