[AggressiveInstCombine] Add `phi` nodes support to `TruncInstCombine`

[anton-afanasyev]

Summary

Expand TruncInstCombine to handle loops by adding phi nodes
to expression graph reduced.

[anton-afanasyev]

Ping.
Though this patch makes AIC more complicated (using general graph instead of expression DAG), it spreads AIC outside one BB. It impacts ~30 tests of test suite.

[RKSimon]

In D109817#3043432, @anton-afanasyev wrote:

Ping.
Though this patch makes AIC more complicated (using general graph instead of expression DAG), it spreads AIC outside one BB. It impacts ~30 tests of test suite.

Are there any notable diffs (codegen/perf) in those tests?

[RKSimon]

@anton-afanasyev reverse ping

[anton-afanasyev]

In D109817#3060903, @RKSimon wrote:

In D109817#3043432, @anton-afanasyev wrote:

Ping.
Though this patch makes AIC more complicated (using general graph instead of expression DAG), it spreads AIC outside one BB. It impacts ~30 tests of test suite.

Are there any notable diffs (codegen/perf) in those tests?

I don't think that such diffs could be called "notable", what I see is rather controversal impact in code size:

$ ~/llvm/test-suite/utils/compare.py -a --filter-short -m size..text result_base.json vs result_exp.json
Tests: 2889
Short Running: 465 (filtered out)
Remaining: 2424
Metric: size..text

Program                                        lhs        rhs        diff 
 test-suite.../Benchmarks/Ptrdist/bc/bc.test   46658.00   46722.00    0.1%
 test-suite...terchange/LoopInterchange.test   232802.00  232818.00   0.0%
 test-suite...eProcessing/Dilate/Dilate.test   236098.00  236114.00   0.0%
 test-suite...Filtering/BilateralFilter.test   236498.00  236514.00   0.0%
 test-suite...sion/AnisotropicDiffusion.test   237202.00  237218.00   0.0%
 test-suite.../Builtins/Int128/Builtins.test   237218.00  237234.00   0.0%
 test-suite...terpolation/Interpolation.test   237458.00  237474.00   0.0%
 test-suite...ImageProcessing/Blur/blur.test   239058.00  239074.00   0.0%
 test-suite...eProcessing/Dither/Dither.test   239842.00  239858.00   0.0%
 test-suite...oBenchmarks/harris/harris.test   241122.00  241138.00   0.0%
 test-suite...LPVectorizationBenchmarks.test   256626.00  256642.00   0.0%
 test-suite...opVectorizationBenchmarks.test   353330.00  353346.00   0.0%
 test-suite...MemFunctions/MemFunctions.test   371794.00  371810.00   0.0%
 test-suite...SubsetBRawLoops/lcalsBRaw.test   421026.00  421042.00   0.0%
 test-suite...BLambdaLoops/lcalsBLambda.test   421282.00  421298.00   0.0%
 test-suite...SubsetARawLoops/lcalsARaw.test   430978.00  430994.00   0.0%
 test-suite...ALambdaLoops/lcalsALambda.test   432050.00  432066.00   0.0%
 test-suite...CLambdaLoops/lcalsCLambda.test   434514.00  434530.00   0.0%
 test-suite...SubsetCRawLoops/lcalsCRaw.test   434690.00  434706.00   0.0%
 test-suite...ications/JM/lencod/lencod.test   756738.00  756754.00   0.0%
 test-suite...itcode/Regression/fft/fft.test   7425490.00 7425522.00  0.0%
 test-suite...ute/GCC-C-execute-loop-13.test   546.00     546.00      0.0%
...
 test-suite.../GCC-C-execute-20000403-1.test   450.00     450.00      0.0%
 test-suite...lications/ClamAV/clamscan.test   531321.00  531289.00  -0.0%
 test-suite...nsumer-lame/consumer-lame.test   175042.00  175026.00  -0.0%
 test-suite...nsumer-jpeg/consumer-jpeg.test   167186.00  167170.00  -0.0%
 test-suite...pplications/oggenc/oggenc.test   252210.00  252162.00  -0.0%
 test-suite...lications/sqlite3/sqlite3.test   496770.00  496530.00  -0.0%
 test-suite...ests/Vectorizer/gcc-loops.test   21330.00   21314.00   -0.1%
 test-suite...s/MallocBench/cfrac/cfrac.test   20754.00   20722.00   -0.2%
 test-suite...itBench/uudecode/uudecode.test   1538.00    1522.00    -1.0%
 Geomean difference                                                  -0.0%

Therefore I would abandon this change until we see a strict need of it.

[lebedev.ri]

I would recommend to proceed with this.

[RKSimon]

None of those size changes look like alarming - why do you want to stop work on this patch?

[anton-afanasyev]

In D109817#3184760, @lebedev.ri wrote:

I would recommend to proceed with this.

In D109817#3188058, @RKSimon wrote:

None of those size changes look like alarming - why do you want to stop work on this patch?

The patch changes previous logic without undoubted positive impact. I would expect no code size increase of any test for such change. But ok, I'm to investigate what is a real cause of it and proceed with this.

[RKSimon]

@anton-afanasyev Now that 14.x has been branched are you intending to revive this?

[anton-afanasyev]

Rebase

[anton-afanasyev]

I've investigated small regressions, caused by this patch. The sizes are actually increased at the backend level, while translating llvm to machine code, for instanse:

> ll symtab.c.*
13769 symtab.c.base.ll
13681 symtab.c.exp.ll
8280 symtab.c.base.s
8394 symtab.c.exp.s

For the tests from testsuite this mostly leads to just +16 bytes code size increase (see table at D109817#3184752), so I believe it's acceptable fluctuation.

[RKSimon]

In D109817#3184760, @lebedev.ri wrote:

I would recommend to proceed with this.

@lebedev.ri Are you still happy with this patch?

[lebedev.ri]

In D109817#3317534, @RKSimon wrote:

In D109817#3184760, @lebedev.ri wrote:

I would recommend to proceed with this.

@lebedev.ri Are you still happy with this patch?

Conceptually, yes.
Are there tests with switches, where the PHI node has multiple incoming edges from the same predecessor?

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

154

Stack should be a SetVector then.
Also, could use a comment.

[anton-afanasyev]

Are there tests with switches, where the PHI node has multiple incoming edges from the same predecessor?

What do you mean by "the same predecessor"? There is test with ordinary loop.

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

154

Stack is already used as stack, we need to push/pop from it.
Added comment.

[anton-afanasyev]

Add comment

[lebedev.ri]

In D109817#3319994, @anton-afanasyev wrote:

Are there tests with switches, where the PHI node has multiple incoming edges from the same predecessor?

What do you mean by "the same predecessor"? There is test with ordinary loop.

https://godbolt.org/z/MdsrzGnvq

[anton-afanasyev]

In D109817#3320059, @lebedev.ri wrote:

In D109817#3319994, @anton-afanasyev wrote:

Are there tests with switches, where the PHI node has multiple incoming edges from the same predecessor?

What do you mean by "the same predecessor"? There is test with ordinary loop.

https://godbolt.org/z/MdsrzGnvq

Oh, I see. Added test.

[anton-afanasyev]

Add test

[anton-afanasyev]

@lebedev.ri Ping. Is it ok now?

[lebedev.ri]

Sorry, meant to take another look and forgot.
Seems reasonable, let's see who complains :)

[anton-afanasyev]

Fix sanitizer breakage: erase phi-nodes from InstInfoMap before erasing themselves

[lebedev.ri]

In D109817#3344766, @anton-afanasyev wrote:

Fix sanitizer breakage: erase phi-nodes from InstInfoMap before erasing themselves

(If you believe that fixes the issue then feel free to recommit, no further feedback here expected)

[anton-afanasyev]

In D109817#3344942, @lebedev.ri wrote:

In D109817#3344766, @anton-afanasyev wrote:

Fix sanitizer breakage: erase phi-nodes from InstInfoMap before erasing themselves

(If you believe that fixes the issue then feel free to recommit, no further feedback here expected)

Sure, I've already recommited this with fix, updated here just to note about it.

[anton-afanasyev]

This is already closed, reopened accidentally.

[uabelho]

I wrote a ticket about a crash that started happening with this patch:
https://github.com/llvm/llvm-project/issues/58008

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombineInternal.h

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Support/KnownBits.h"
 
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
-// TruncInstCombine - looks for expression dags dominated by trunc instructions
-// and for each eligible dag, it will create a reduced bit-width expression and
-// replace the old expression with this new one and remove the old one.
-// Eligible expression dag is such that:
+// TruncInstCombine - looks for expression graphs dominated by trunc
+// instructions and for each eligible graph, it will create a reduced bit-width
+// expression and replace the old expression with this new one and remove the
+// old one. Eligible expression graph is such that:
 //   1. Contains only supported instructions.
 //   2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
 //   3. Can be evaluated into type with reduced legal bit-width (or Trunc type).
-//   4. All instructions in the dag must not have users outside the dag.
+//   4. All instructions in the graph must not have users outside the graph.
 //      Only exception is for {ZExt, SExt}Inst with operand type equal to the
 //      new reduced type chosen in (3).
 //
 // The motivation for this optimization is that evaluating and expression using
 // smaller bit-width is preferable, especially for vectorization where we can
 // fit more values in one vectorized instruction. In addition, this optimization
 // may decrease the number of cast instructions, but will not increase it.
 //===----------------------------------------------------------------------===//
class TruncInstCombine {
   const DominatorTree &DT;
 
   /// List of all TruncInst instructions to be processed.
   SmallVector<TruncInst *, 4> Worklist;
 
   /// Current processed TruncInst instruction.
   TruncInst *CurrentTruncInst;
 
-  /// Information per each instruction in the expression dag.
+  /// Information per each instruction in the expression graph.
   struct Info {
     /// Number of LSBs that are needed to generate a valid expression.
     unsigned ValidBitWidth = 0;
     /// Minimum number of LSBs needed to generate the ValidBitWidth.
     unsigned MinBitWidth = 0;
     /// The reduced value generated to replace the old instruction.
     Value *NewValue = nullptr;
   };
-  /// An ordered map representing expression dag post-dominated by current
-  /// processed TruncInst. It maps each instruction in the dag to its Info
+  /// An ordered map representing expression graph post-dominated by current
+  /// processed TruncInst. It maps each instruction in the graph to its Info
   /// structure. The map is ordered such that each instruction appears before
-  /// all other instructions in the dag that uses it.
+  /// all other instructions in the graph that uses it.
   MapVector<Instruction *, Info> InstInfoMap;
 
 public:
   TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI,
                    const DataLayout &DL, const DominatorTree &DT)
       : AC(AC), TLI(TLI), DL(DL), DT(DT), CurrentTruncInst(nullptr) {}
 
   /// Perform TruncInst pattern optimization on given function.
   bool run(Function &F);
 
 private:
-  /// Build expression dag dominated by the /p CurrentTruncInst and append it to
-  /// the InstInfoMap container.
+  /// Build expression graph dominated by the /p CurrentTruncInst and append it
+  /// to the InstInfoMap container.
   ///
-  /// \return true only if succeed to generate an eligible sub expression dag.
-  bool buildTruncExpressionDag();
+  /// \return true only if succeed to generate an eligible sub expression graph.
+  bool buildTruncExpressionGraph();
 
   /// Calculate the minimal allowed bit-width of the chain ending with the
   /// currently visited truncate's operand.
   ///
   /// \return minimum number of bits to which the chain ending with the
   /// truncate's operand can be shrunk to.
   unsigned getMinBitWidth();
 
-  /// Build an expression dag dominated by the current processed TruncInst and
+  /// Build an expression graph dominated by the current processed TruncInst and
   /// Check if it is eligible to be reduced to a smaller type.
   ///
   /// \return the scalar version of the new type to be used for the reduced
-  ///         expression dag, or nullptr if the expression dag is not eligible
-  ///         to be reduced.
+  ///         expression graph, or nullptr if the expression graph is not
+  ///         eligible to be reduced.
   Type *getBestTruncatedType();
 
   KnownBits computeKnownBits(const Value *V) const {
     return llvm::computeKnownBits(V, DL, /*Depth=*/0, &AC,
                                   /*CtxI=*/cast<Instruction>(CurrentTruncInst),
                                   &DT);
   }
 
   unsigned ComputeNumSignBits(const Value *V) const {
     return llvm::ComputeNumSignBits(
         V, DL, /*Depth=*/0, &AC, /*CtxI=*/cast<Instruction>(CurrentTruncInst),
         &DT);
   }
 
   /// Given a \p V value and a \p SclTy scalar type return the generated reduced
   /// value of \p V based on the type \p SclTy.
   ///
   /// \param V value to be reduced.
   /// \param SclTy scalar version of new type to reduce to.
   /// \return the new reduced value.
   Value *getReducedOperand(Value *V, Type *SclTy);
 
-  /// Create a new expression dag using the reduced /p SclTy type and replace
-  /// the old expression dag with it. Also erase all instructions in the old
-  /// dag, except those that are still needed outside the dag.
+  /// Create a new expression graph using the reduced /p SclTy type and replace
+  /// the old expression graph with it. Also erase all instructions in the old
+  /// graph, except those that are still needed outside the graph.
   ///
-  /// \param SclTy scalar version of new type to reduce expression dag into.
-  void ReduceExpressionDag(Type *SclTy);
+  /// \param SclTy scalar version of new type to reduce expression graph into.
+  void ReduceExpressionGraph(Type *SclTy);
 };
 } // end namespace llvm.
 
 #endif

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

 //===- TruncInstCombine.cpp -----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// TruncInstCombine - looks for expression dags post-dominated by TruncInst and
-// for each eligible dag, it will create a reduced bit-width expression, replace
-// the old expression with this new one and remove the old expression.
-// Eligible expression dag is such that:
+// TruncInstCombine - looks for expression graphs post-dominated by TruncInst
+// and for each eligible graph, it will create a reduced bit-width expression,
+// replace the old expression with this new one and remove the old expression.
+// Eligible expression graph is such that:
 //   1. Contains only supported instructions.
 //   2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
 //   3. Can be evaluated into type with reduced legal bit-width.
-//   4. All instructions in the dag must not have users outside the dag.
+//   4. All instructions in the graph must not have users outside the graph.
 //      The only exception is for {ZExt, SExt}Inst with operand type equal to
 //      the new reduced type evaluated in (3).
 //
 // The motivation for this optimization is that evaluating and expression using
 // smaller bit-width is preferable, especially for vectorization where we can
 // fit more values in one vectorized instruction. In addition, this optimization
 // may decrease the number of cast instructions, but will not increase it.
 //

 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/Support/KnownBits.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "aggressive-instcombine"
 
-STATISTIC(
-    NumDAGsReduced,
-    "Number of truncations eliminated by reducing bit width of expression DAG");
+STATISTIC(NumExprsReduced, "Number of truncations eliminated by reducing bit "
+                           "width of expression graph");
 STATISTIC(NumInstrsReduced,
           "Number of instructions whose bit width was reduced");
 
 /// Given an instruction and a container, it fills all the relevant operands of
-/// that instruction, with respect to the Trunc expression dag optimizaton.
+/// that instruction, with respect to the Trunc expression graph optimizaton.
 static void getRelevantOperands(Instruction *I, SmallVectorImpl<Value *> &Ops) {
   unsigned Opc = I->getOpcode();
   switch (Opc) {
   case Instruction::Trunc:
   case Instruction::ZExt:
   case Instruction::SExt:
     // These CastInst are considered leaves of the evaluated expression, thus,
     // their operands are not relevent.
static void getRelevantOperands(Instruction *I, SmallVectorImpl<Value *> &Ops) {
   case Instruction::URem:
     Ops.push_back(I->getOperand(0));
     Ops.push_back(I->getOperand(1));
     break;
   case Instruction::Select:
     Ops.push_back(I->getOperand(1));
     Ops.push_back(I->getOperand(2));
     break;
+  case Instruction::PHI:
+    for (Value *V : cast<PHINode>(I)->incoming_values())
+      Ops.push_back(V);
+    break;
   default:
     llvm_unreachable("Unreachable!");
   }
 }
 
-bool TruncInstCombine::buildTruncExpressionDag() {
+bool TruncInstCombine::buildTruncExpressionGraph() {
   SmallVector<Value *, 8> Worklist;
   SmallVector<Instruction *, 8> Stack;
-  // Clear old expression dag.
+  // Clear old instructions info.
   InstInfoMap.clear();
 
   Worklist.push_back(CurrentTruncInst->getOperand(0));
 
   while (!Worklist.empty()) {
     Value *Curr = Worklist.back();
 
     if (isa<Constant>(Curr)) {
while (!Worklist.empty()) {
     case Instruction::UDiv:
     case Instruction::URem:
     case Instruction::Select: {
       SmallVector<Value *, 2> Operands;
       getRelevantOperands(I, Operands);
       append_range(Worklist, Operands);
       break;
     }
+    case Instruction::PHI: {
+      SmallVector<Value *, 2> Operands;
+      getRelevantOperands(I, Operands);
+      for (auto *Op : Operands)
+        if (all_of(Stack, [Op](Value *V) { return Op != V; }))
+          Worklist.push_back(Op);
+      break;
+    }
     default:
       // TODO: Can handle more cases here:
       // 1. shufflevector, extractelement, insertelement
       // 2. sdiv, srem
-      // 3. phi node(and loop handling)
       // ...
       return false;
     }
   }
   return true;
 }
 
 unsigned TruncInstCombine::getMinBitWidth() {
if (MinBitWidth > TruncBitWidth) {
     bool ToLegal = MinBitWidth == 1 || DL.isLegalInteger(MinBitWidth);
     if (!DstTy->isVectorTy() && FromLegal && !ToLegal)
       return OrigBitWidth;
   }
   return MinBitWidth;
 }
 
 Type *TruncInstCombine::getBestTruncatedType() {
-  if (!buildTruncExpressionDag())
+  if (!buildTruncExpressionGraph())
     return nullptr;
 
   // We don't want to duplicate instructions, which isn't profitable. Thus, we
   // can't shrink something that has multiple users, unless all users are
   // post-dominated by the trunc instruction, i.e., were visited during the
   // expression evaluation.
   unsigned DesiredBitWidth = 0;
   for (auto Itr : InstInfoMap) {
Value *TruncInstCombine::getReducedOperand(Value *V, Type *SclTy) {
   }
 
   auto *I = cast<Instruction>(V);
   Info Entry = InstInfoMap.lookup(I);
   assert(Entry.NewValue);
   return Entry.NewValue;
 }
 
-void TruncInstCombine::ReduceExpressionDag(Type *SclTy) {
+void TruncInstCombine::ReduceExpressionGraph(Type *SclTy) {
   NumInstrsReduced += InstInfoMap.size();
+  // Pairs of old and new phi-nodes
+  SmallVector<std::pair<PHINode *, PHINode *>, 2> OldNewPHINodes;
   for (auto &Itr : InstInfoMap) { // Forward
     Instruction *I = Itr.first;
     TruncInstCombine::Info &NodeInfo = Itr.second;
 
     assert(!NodeInfo.NewValue && "Instruction has been evaluated");
 
     IRBuilder<> Builder(I);
     Value *Res = nullptr;
for (auto &Itr : InstInfoMap) { // Forward
     }
     case Instruction::Select: {
       Value *Op0 = I->getOperand(0);
       Value *LHS = getReducedOperand(I->getOperand(1), SclTy);
       Value *RHS = getReducedOperand(I->getOperand(2), SclTy);
       Res = Builder.CreateSelect(Op0, LHS, RHS);
       break;
     }
+    case Instruction::PHI: {
+      Res = Builder.CreatePHI(getReducedType(I, SclTy), I->getNumOperands());
+      OldNewPHINodes.push_back(
+          std::make_pair(cast<PHINode>(I), cast<PHINode>(Res)));
+      break;
+    }
     default:
       llvm_unreachable("Unhandled instruction");
     }
 
     NodeInfo.NewValue = Res;
     if (auto *ResI = dyn_cast<Instruction>(Res))
       ResI->takeName(I);
   }
 
+  for (auto &Node : OldNewPHINodes) {
+    PHINode *OldPN = Node.first;
+    PHINode *NewPN = Node.second;
+    for (auto Incoming : zip(OldPN->incoming_values(), OldPN->blocks()))
+      NewPN->addIncoming(getReducedOperand(std::get<0>(Incoming), SclTy),
+                         std::get<1>(Incoming));
+  }
+
   Value *Res = getReducedOperand(CurrentTruncInst->getOperand(0), SclTy);
   Type *DstTy = CurrentTruncInst->getType();
   if (Res->getType() != DstTy) {
     IRBuilder<> Builder(CurrentTruncInst);
     Res = Builder.CreateIntCast(Res, DstTy, false);
     if (auto *ResI = dyn_cast<Instruction>(Res))
       ResI->takeName(CurrentTruncInst);
   }
   CurrentTruncInst->replaceAllUsesWith(Res);
 
-  // Erase old expression dag, which was replaced by the reduced expression dag.
-  // We iterate backward, which means we visit the instruction before we visit
-  // any of its operands, this way, when we get to the operand, we already
-  // removed the instructions (from the expression dag) that uses it.
+  // Erase old expression graph, which was replaced by the reduced expression
+  // graph.
   CurrentTruncInst->eraseFromParent();
+  // First, erase old phi-nodes and its uses
+  for (auto &Node : OldNewPHINodes) {
+    PHINode *OldPN = Node.first;
+    OldPN->replaceAllUsesWith(PoisonValue::get(OldPN->getType()));
+    OldPN->eraseFromParent();
+  }
+  // Now we have expression graph turned into dag.
+  // We iterate backward, which means we visit the instruction before we
+  // visit any of its operands, this way, when we get to the operand, we already
+  // removed the instructions (from the expression dag) that uses it.
   for (auto I = InstInfoMap.rbegin(), E = InstInfoMap.rend(); I != E; ++I) {
+    // Skip phi-nodes since they were erased before
+    if (isa<PHINode>(I->first))
+      continue;
     // We still need to check that the instruction has no users before we erase
     // it, because {SExt, ZExt}Inst Instruction might have other users that was
     // not reduced, in such case, we need to keep that instruction.
     if (I->first->use_empty())
       I->first->eraseFromParent();
+    else
+      assert((isa<SExtInst>(I->first) || isa<ZExtInst>(I->first)) &&
+             "Only {SExt, ZExt}Inst might have unreduced users");
   }
 }
 
 bool TruncInstCombine::run(Function &F) {
   bool MadeIRChange = false;
 
   // Collect all TruncInst in the function into the Worklist for evaluating.
   for (auto &BB : F) {
     // Ignore unreachable basic block.
     if (!DT.isReachableFromEntry(&BB))
       continue;
     for (auto &I : BB)
       if (auto *CI = dyn_cast<TruncInst>(&I))
         Worklist.push_back(CI);
   }
 
   // Process all TruncInst in the Worklist, for each instruction:
-  //   1. Check if it dominates an eligible expression dag to be reduced.
-  //   2. Create a reduced expression dag and replace the old one with it.
+  //   1. Check if it dominates an eligible expression graph to be reduced.
+  //   2. Create a reduced expression graph and replace the old one with it.
   while (!Worklist.empty()) {
     CurrentTruncInst = Worklist.pop_back_val();
 
     if (Type *NewDstSclTy = getBestTruncatedType()) {
       LLVM_DEBUG(
-          dbgs() << "ICE: TruncInstCombine reducing type of expression dag "
+          dbgs() << "ICE: TruncInstCombine reducing type of expression graph "
                     "dominated by: "
                  << CurrentTruncInst << '\n');
-      ReduceExpressionDag(NewDstSclTy);
-      ++NumDAGsReduced;
+      ReduceExpressionGraph(NewDstSclTy);
+      ++NumExprsReduced;
       MadeIRChange = true;
     }
   }
 
   return MadeIRChange;
 }

llvm/test/Transforms/AggressiveInstCombine/trunc_phi.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -aggressive-instcombine -S | FileCheck %s
 
 define i16 @trunc_phi(i8 %x) {
 ; CHECK-LABEL: @trunc_phi(
 ; CHECK-NEXT:  LoopHeader:
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i16
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       Loop:
-; CHECK-NEXT:    [[ZEXT2:%.*]] = phi i32 [ [[ZEXT]], [[LOOPHEADER:%.*]] ], [ [[SHL:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[ZEXT2:%.*]] = phi i16 [ [[ZEXT]], [[LOOPHEADER:%.*]] ], [ [[SHL:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOPHEADER]] ], [ [[I:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[SHL]] = shl i32 [[ZEXT2]], 1
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[SHL]] to i16
+; CHECK-NEXT:    [[SHL]] = shl i16 [[ZEXT2]], 1
 ; CHECK-NEXT:    [[I]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOPEND:%.*]], label [[LOOP]]
 ; CHECK:       LoopEnd:
-; CHECK-NEXT:    ret i16 [[TRUNC]]
+; CHECK-NEXT:    ret i16 [[SHL]]
 ;
 LoopHeader:
   %zext = zext i8 %x to i32
   br label %Loop
 
 Loop:
   %zext2 = phi i32 [%zext, %LoopHeader], [%shl, %Loop]
   %j = phi i32 [0, %LoopHeader], [%i, %Loop]
   %shl = shl i32 %zext2, 1
   %trunc = trunc i32 %shl to i16
   %i = add i32 %j, 1
   %cmp = icmp eq i32 %i, 10
   br i1 %cmp, label %LoopEnd, label %Loop
 
 LoopEnd:
   ret i16 %trunc
 }
 
 define i16 @trunc_phi2(i8 %x) {
 ; CHECK-LABEL: @trunc_phi2(
 ; CHECK-NEXT:  LoopHeader:
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
+; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i16
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       Loop:
-; CHECK-NEXT:    [[ZEXT2:%.*]] = phi i32 [ [[ZEXT]], [[LOOPHEADER:%.*]] ], [ [[SHL:%.*]], [[LOOP]] ]
+; CHECK-NEXT:    [[ZEXT2:%.*]] = phi i16 [ [[ZEXT]], [[LOOPHEADER:%.*]] ], [ [[SHL:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOPHEADER]] ], [ [[I:%.*]], [[LOOP]] ]
-; CHECK-NEXT:    [[SHL]] = shl i32 [[ZEXT2]], 1
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[ZEXT2]] to i16
+; CHECK-NEXT:    [[SHL]] = shl i16 [[ZEXT2]], 1
 ; CHECK-NEXT:    [[I]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I]], 10
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LOOPEND:%.*]], label [[LOOP]]
 ; CHECK:       LoopEnd:
-; CHECK-NEXT:    ret i16 [[TRUNC]]
+; CHECK-NEXT:    ret i16 [[ZEXT2]]
 ;
 LoopHeader:
   %zext = zext i8 %x to i32
   br label %Loop
 
 Loop:
   %zext2 = phi i32 [%zext, %LoopHeader], [%shl, %Loop]
   %j = phi i32 [0, %LoopHeader], [%i, %Loop]