Index: llvm/trunk/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp
===================================================================
--- llvm/trunk/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp
+++ llvm/trunk/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp
@@ -317,6 +317,7 @@
       // 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;
       }
@@ -326,11 +327,18 @@
                                   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).
+      auto Entry = find(Worklist, I);
+      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:
Index: llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_const_expr.ll
===================================================================
--- llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_const_expr.ll
+++ llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_const_expr.ll
@@ -46,6 +46,37 @@
   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>)
Index: llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_multi_uses.ll
===================================================================
--- llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_multi_uses.ll
+++ llvm/trunk/test/Transforms/AggressiveInstCombine/trunc_multi_uses.ll
@@ -212,3 +212,59 @@
   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
+}