[AggressiveInstCombine] fixed PR36121

[aaboud]

Summary

Fixed the handle of trunc instruction as a leaf for expression pattern dominated by another trunc instruction.
In this case we need to update the work list of trunc instructions as follows:

1. Replace old-trunc instruction node with the new-trunc instruction, if we reduced trunc instruction to different trunc instruction.
2. Remove old-trunc instruction node from work-list, if we reduced trunc instruction to non-trunc instruction (e.g., to a constant expression).
3. Add new-trunc instruction node to work-list, if we reduced a non-trunc instruction (e.g., zext/sext) into trunc instruction.

This should solve PR36121.

[craig.topper]

lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

335 ↗

(On Diff #131706)

Could these just be isa instead of dyn_cast? Doesn't look like you need a TruncInst to do any of the worklist changes.

test/Transforms/AggressiveInstCombine/trunc_multi_uses.ll

223 ↗

(On Diff #131706)

patters->patterns

247 ↗

(On Diff #131706)

patters->patterns

[aaboud]

lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

335 ↗

(On Diff #131706)

/// List of all TruncInst instructions to be processed.
  SmallVector<TruncInst *, 4> Worklist;

Unless you are suggesting to change the definition of Worklist to be a list of Instructions, I am not sure I can get rid of the dyn_cast! (I will get a compilation error).

Saying that, I a prefer to keep Worklist as list of TruncInst, this way I can assume I always have a truncate instruction in this list without need to assert/check that explicitly!

[craig.topper]

LGTM

lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

335 ↗

(On Diff #131706)

Sorry I searched too quickly and saw the definition of one of the other worklists in this file that uses Value*.

llvm/trunk/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

for (auto &Itr : InstInfoMap) { // Forward
     case Instruction::Trunc:
     case Instruction::ZExt:
     case Instruction::SExt: {
       Type *Ty = getReducedType(I, SclTy);
       // If the source type of the cast is the type we're trying for then we can
       // just return the source.  There's no need to insert it because it is not
       // new.
       if (I->getOperand(0)->getType() == Ty) {
+        assert(!isa<TruncInst>(I) && "Cannot reach here with TruncInst");
         NodeInfo.NewValue = I->getOperand(0);
         continue;
       }
       // Otherwise, must be the same type of cast, so just reinsert a new one.
       // This also handles the case of zext(trunc(x)) -> zext(x).
       Res = Builder.CreateIntCast(I->getOperand(0), Ty,
                                   Opc == Instruction::SExt);
 
       // Update Worklist entries with new value if needed.
-      if (auto *NewCI = dyn_cast<TruncInst>(Res)) {
-        auto Entry = find(Worklist, I);
-        if (Entry != Worklist.end())
+      // There are three possible changes to the Worklist:
+      // 1. Update Old-TruncInst -> New-TruncInst.
+      // 2. Remove Old-TruncInst (if New node is not TruncInst).
+      // 3. Add New-TruncInst (if Old node was not TruncInst).
+      if (Entry != Worklist.end()) {
+        if (auto *NewCI = dyn_cast<TruncInst>(Res))
           *Entry = NewCI;
-      }
+        else
+          Worklist.erase(Entry);
+      } else if (auto *NewCI = dyn_cast<TruncInst>(Res))
+          Worklist.push_back(NewCI);
       break;
     }
     case Instruction::Add:
     case Instruction::Sub:
     case Instruction::Mul:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor: {

llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_const_expr.ll

 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use32(i32 44)
 ; CHECK-NEXT:    ret void
 ;
   %T = trunc i64 44 to i32
   call i32 @use32(i32 %T)
   ret void
 }
 
+; Check that we handle constant expression trunc instruction, when it is a leaf
+; of other trunc expression pattern:
+; 1. %T1 is the constant expression trunc instruction.
+; 2. %T2->%T1 is the trunc expression pattern we want to reduce.
+define void @const_expression_trunc_leaf() {
+; CHECK-LABEL: @const_expression_trunc_leaf(
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use32(i32 44)
+; CHECK-NEXT:    ret void
+;
+  %T1 = trunc i64 44 to i48
+  %T2 = trunc i48 %T1 to i32
+  call i32 @use32(i32 %T2)
+  ret void
+}
+
+; Check that we handle zext instruction, which turns into trunc instruction.
+; Notice that there are two expression patterns below:
+; 1. %T2->%T1
+; 2. %T1`->%A (where %T1` is the reduced node of %T1 into trunc instruction)
+define void @const_expression_zext_to_trunc() {
+; CHECK-LABEL: @const_expression_zext_to_trunc(
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use32(i32 44)
+; CHECK-NEXT:    ret void
+;
+  %A = add i64 11, 33
+  %T1 = zext i64 %A to i128
+  %T2 = trunc i128 %T1 to i32
+  call i32 @use32(i32 %T2)
+  ret void
+}
+
 define void @const_expression_mul_vec() {
 ; CHECK-LABEL: @const_expression_mul_vec(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @use32_vec(<2 x i32> <i32 24531, i32 24864>)
 ; CHECK-NEXT:    ret void
 ;
   %A = mul <2 x i64> <i64 111, i64 112>, <i64 221, i64 222>
   %T = trunc <2 x i64> %A to <2 x i32>
   call <2 x i32> @use32_vec(<2 x i32> %T)

llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_multi_uses.ll

;
   %C1 = mul <2 x i64> %B1, %B1
   %T1 = trunc <2 x i64> %C1 to <2 x i32>
   call <2 x i32> @use32_vec(<2 x i32> %T1)
   ; make sure zext have another use that is not post-dominated by the TruncInst.
   call <2 x i32> @use64_vec(<2 x i64> %A1)
   call <2 x i32> @use64_vec(<2 x i64> %A2)
   ret void
 }
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;; These tests check cases where expression dag post-dominated by TruncInst
+;; contains TruncInst leaf or ZEXT/SEXT leafs which turn into TruncInst leaves.
+;; Check that both expressions are reduced and no TruncInst remains or (was
+;; generated).
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+
+; Notice that there are two expression patterns below:
+; 1. %T2->%C2->(%B2->(%T1, 15), %B2->(%T1, 15))
+; 2. %T1`->%C1->(%B1->(%A1, 15), %B1->(%A1, 15))
+;    (where %T1` is the reduced node of %T1 into trunc instruction)
+define void @trunc_as_a_leaf(i32 %X) {
+; CHECK-LABEL: @trunc_as_a_leaf(
+; CHECK-NEXT:    [[B1:%.*]] = add i32 [[X:%.*]], 15
+; CHECK-NEXT:    [[C1:%.*]] = mul i32 [[B1]], [[B1]]
+; CHECK-NEXT:    [[B2:%.*]] = add i32 [[C1]], 15
+; CHECK-NEXT:    [[C2:%.*]] = mul i32 [[B2]], [[B2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use32(i32 [[C2]])
+; CHECK-NEXT:    ret void
+;
+  %A1 = zext i32 %X to i64
+  %B1 = add i64 %A1, 15
+  %C1 = mul i64 %B1, %B1
+  %T1 = trunc i64 %C1 to i48 ; leaf trunc
+  %B2 = add i48 %T1, 15
+  %C2 = mul i48 %B2, %B2
+  %T2 = trunc i48 %C2 to i32
+  call i32 @use32(i32 %T2)
+  ret void
+}
+
+; Notice that there are two expression patterns below:
+; 1. %T2->%C2->(%B2->(%T1, 15), %B2->(%T1, 15))
+; 2. %T1`->%C1->(%B1->(%A1, 15), %B1->(%A1, 15))
+;    (where %T1` is the reduced node of %T1 into trunc instruction)
+define void @zext_as_a_leaf(i16 %X) {
+; CHECK-LABEL: @zext_as_a_leaf(
+; CHECK-NEXT:    [[A1:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[B1:%.*]] = add i32 [[A1]], 15
+; CHECK-NEXT:    [[C1:%.*]] = mul i32 [[B1]], [[B1]]
+; CHECK-NEXT:    [[B2:%.*]] = add i32 [[C1]], 15
+; CHECK-NEXT:    [[C2:%.*]] = mul i32 [[B2]], [[B2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @use32(i32 [[C2]])
+; CHECK-NEXT:    ret void
+;
+  %A1 = zext i16 %X to i48
+  %B1 = add i48 %A1, 15
+  %C1 = mul i48 %B1, %B1
+  %T1 = zext i48 %C1 to i64 ; leaf zext, which will turn into trunc
+  %B2 = add i64 %T1, 15
+  %C2 = mul i64 %B2, %B2
+  %T2 = trunc i64 %C2 to i32
+  call i32 @use32(i32 %T2)
+  ret void
+}