GVN fails to fold constant expression

[kromanova]

Summary

This is a fix for PR 28418.

opt never finishes compiling test/Transforms/GVN/fold-const-expr.ll when -gvn option is passed.
I added fold-const-expr.ll to the llvm regression test suite.

The problem is caused by the fact that GVN fails to fold a constant expression.
That expression gets expanded multiple times and ends up as a huge, exponentially growing (relative to the number of instructions in the BB) constant expression. This expression is too big for GVN to analyze, so this optimization pass never finishes.

For more details, see the analysis in the PR 28418.
Here is concise version:

The expression (i32 trunc (i128 bitcast (<4 x i32> <i32 234567891, i32 345678912, i32 456789123, i32 0> to i128) to i32) is the result of a GVN expansion, when a previously stored constant vector is partially reloaded (note that the store size does not match the load size).

We have a store of a full <4 x i32> vector;

// (<4 x i32> <i32 234567891, i32 345678912, i32 456789123, i32 0> to i128

later on we reload the first element of the vector.
// i32 234567891

The lack of knowledge about constant expressions currently forces GVN to canonicalize a partial reload into a sequence of `trunc + bitcast`.
The aforementioned expression should be constant folded to i32 234567891 by GVN.

Special thanks to Andrea DiBiagio for his help with the analysis/fix and to Rafael for his help with reducing an immense reproducer.

[majnemer]

Seems OK to me. Danny, what do you think?

[• dberlin]

The only question I have is whether it should be folding as you go. This
looks like it calls constant fold on the huge materialized expression,
instead of folding as it is built by the coercion logic.

I expect the latter to be better both memory and time wise.

[kromanova]

Hi Daniel and David,
Thank you so much for your feedback. I think what Daniel is suggesting will be more efficient, however that patch might not look as simple and readable. I will work on the new patch and then we could discuss it again.
Katya.

[kromanova]

Hi Daniel,
I did folding earlier, allowing further folding of const expression as it's being built. It's taking care of the problem and we don't get huge meterialized expression. See the patch.

Andrea noticed that ‘CoerceAvailableValueToLoadType’ can still generate sub-optimal constant expressions, since this function may potentially insert bitcasts, shifts and truncates of the input value. To always simplify constant expressions, we should add some extra folding to simplify the StoredVal before it is returned from the function. I will send a patch for it in a minute.
Katya.

[kromanova]

This patch is better than the previous one, since it does extra folding to simplify the StoredVal before it is returned from the function ‘CoerceAvailableValueToLoadType’ can potentially insert bitcasts, shifts and truncates of the input value, creating though not huge, but still sub-optimal const expression.

[• dberlin]

LGTM.
Thank you so much!

lib/Transforms/Scalar/GVN.cpp

 ///
 /// If we can't do it, return null.
 static Value *CoerceAvailableValueToLoadType(Value *StoredVal, Type *LoadedTy,
                                              IRBuilder<> &IRB,
                                              const DataLayout &DL) {
   assert(CanCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL) &&
          "precondition violation - materialization can't fail");
 
+  if (auto *CExpr = dyn_cast<ConstantExpr>(StoredVal))
+    StoredVal = ConstantFoldConstantExpression(CExpr, DL);
+
   // If this is already the right type, just return it.
   Type *StoredValTy = StoredVal->getType();
 
   uint64_t StoredValSize = DL.getTypeSizeInBits(StoredValTy);
   uint64_t LoadedValSize = DL.getTypeSizeInBits(LoadedTy);
 
   // If the store and reload are the same size, we can always reuse it.
   if (StoredValSize == LoadedValSize) {
     // Pointer to Pointer -> use bitcast.
     if (StoredValTy->getScalarType()->isPointerTy() &&
-        LoadedTy->getScalarType()->isPointerTy())
-      return IRB.CreateBitCast(StoredVal, LoadedTy);
-
+        LoadedTy->getScalarType()->isPointerTy()) {
+      StoredVal = IRB.CreateBitCast(StoredVal, LoadedTy);
+    } else {
       // Convert source pointers to integers, which can be bitcast.
       if (StoredValTy->getScalarType()->isPointerTy()) {
         StoredValTy = DL.getIntPtrType(StoredValTy);
         StoredVal = IRB.CreatePtrToInt(StoredVal, StoredValTy);
       }
 
       Type *TypeToCastTo = LoadedTy;
       if (TypeToCastTo->getScalarType()->isPointerTy())
         TypeToCastTo = DL.getIntPtrType(TypeToCastTo);
 
       if (StoredValTy != TypeToCastTo)
         StoredVal = IRB.CreateBitCast(StoredVal, TypeToCastTo);
 
       // Cast to pointer if the load needs a pointer type.
       if (LoadedTy->getScalarType()->isPointerTy())
         StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy);
+    }
+
+    if (auto *CExpr = dyn_cast<ConstantExpr>(StoredVal))
+      StoredVal = ConstantFoldConstantExpression(CExpr, DL);
 
     return StoredVal;
   }
 
   // If the loaded value is smaller than the available value, then we can
   // extract out a piece from it.  If the available value is too small, then we
   // can't do anything.
   assert(StoredValSize >= LoadedValSize &&
uint64_t ShiftAmt = DL.getTypeStoreSizeInBits(StoredValTy) -
                         DL.getTypeStoreSizeInBits(LoadedTy);
     StoredVal = IRB.CreateLShr(StoredVal, ShiftAmt, "tmp");
   }
 
   // Truncate the integer to the right size now.
   Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadedValSize);
   StoredVal  = IRB.CreateTrunc(StoredVal, NewIntTy, "trunc");
 
-  if (LoadedTy == NewIntTy)
-    return StoredVal;
-
+  if (LoadedTy != NewIntTy) {
     // If the result is a pointer, inttoptr.
     if (LoadedTy->getScalarType()->isPointerTy())
-    return IRB.CreateIntToPtr(StoredVal, LoadedTy, "inttoptr");
-
+      StoredVal = IRB.CreateIntToPtr(StoredVal, LoadedTy, "inttoptr");
+    else
       // Otherwise, bitcast.
-  return IRB.CreateBitCast(StoredVal, LoadedTy, "bitcast");
+      StoredVal = IRB.CreateBitCast(StoredVal, LoadedTy, "bitcast");
+  }
+
+  if (auto *CExpr = dyn_cast<ConstantExpr>(StoredVal))
+    StoredVal = ConstantFoldConstantExpression(CExpr, DL);
+
+  return StoredVal;
 }
 
 /// This function is called when we have a
 /// memdep query of a load that ends up being a clobbering memory write (store,
 /// memset, memcpy, memmove).  This means that the write *may* provide bits used
 /// by the load but we can't be sure because the pointers don't mustalias.
 ///
 /// Check this case to see if there is anything more we can do before we give

test/Transforms/GVN/fold-const-expr.ll

+; GVN failed to do constant expression folding and expanded
+; them unfolded in many places, producing exponentially large const
+; expressions. As a result, the compilation never fisished.
+; This test checks that we are folding constant expression
+; PR 28418
+; RUN: opt -gvn -S < %s | FileCheck %s
+
+%2 = type { i32, i32, i32, i32, i32 }
+define i32 @_Z16vector3util_mainv(i32 %x, i32 %y)  {
+  %tmp1 = alloca %2, align 4
+  %tmp114 = getelementptr inbounds %2, %2* %tmp1, i64 0, i32 1
+  %tmp115 = bitcast i32* %tmp114 to <4 x i32>*
+  store <4 x i32> <i32 234567891, i32 345678912, i32 456789123, i32 0>, <4 x i32>* %tmp115, align 4
+  %tmp1683 = getelementptr inbounds %2, %2* %tmp1, i64 0, i32 1
+  %tmp1688 = load i32, i32* %tmp1683, align 4
+  %tmp1693 = shl i32 %tmp1688, 5
+  %tmp1694 = xor i32 %tmp1693, %tmp1688
+  %tmp1695 = lshr i32 %tmp1694, 7
+  %tmp1696 = xor i32 %tmp1695, %tmp1694
+  %tmp1697 = shl i32 %tmp1696, 22
+  %tmp1698 = xor i32 %tmp1697, %tmp1696
+  %tmp1707 = shl i32 %tmp1698, 5
+  %tmp1708 = xor i32 %tmp1707, %tmp1698
+  %tmp1709 = lshr i32 %tmp1708, 7
+  %tmp1710 = xor i32 %tmp1709, %tmp1708
+  %tmp1711 = shl i32 %tmp1710, 22
+  %tmp1712 = xor i32 %tmp1711, %tmp1710
+  %tmp1721 = shl i32 %tmp1712, 5
+  %tmp1722 = xor i32 %tmp1721, %tmp1712
+  %tmp1723 = lshr i32 %tmp1722, 7
+  %tmp1724 = xor i32 %tmp1723, %tmp1722
+  %tmp1725 = shl i32 %tmp1724, 22
+  %tmp1726 = xor i32 %tmp1725, %tmp1724
+  %tmp1735 = shl i32 %tmp1726, 5
+  %tmp1736 = xor i32 %tmp1735, %tmp1726
+  %tmp1737 = lshr i32 %tmp1736, 7
+  %tmp1738 = xor i32 %tmp1737, %tmp1736
+  %tmp1739 = shl i32 %tmp1738, 22
+  %tmp1740 = xor i32 %tmp1739, %tmp1738
+  store i32 %tmp1740, i32* %tmp1683, align 4
+; CHECK: store i32 310393545, i32* %tmp114, align 4
+  %tmp1756 = getelementptr inbounds %2, %2* %tmp1, i64 0, i32 1
+  %tmp1761 = load i32, i32* %tmp1756, align 4
+  %tmp1766 = shl i32 %tmp1761, 5
+  %tmp1767 = xor i32 %tmp1766, %tmp1761
+  %tmp1768 = lshr i32 %tmp1767, 7
+  %tmp1769 = xor i32 %tmp1768, %tmp1767
+  %tmp1770 = shl i32 %tmp1769, 22
+  %tmp1771 = xor i32 %tmp1770, %tmp1769
+  %tmp1780 = shl i32 %tmp1771, 5
+  %tmp1781 = xor i32 %tmp1780, %tmp1771
+  %tmp1782 = lshr i32 %tmp1781, 7
+  %tmp1783 = xor i32 %tmp1782, %tmp1781
+  %tmp1784 = shl i32 %tmp1783, 22
+  %tmp1785 = xor i32 %tmp1784, %tmp1783
+  %tmp1794 = shl i32 %tmp1785, 5
+  %tmp1795 = xor i32 %tmp1794, %tmp1785
+  %tmp1796 = lshr i32 %tmp1795, 7
+  %tmp1797 = xor i32 %tmp1796, %tmp1795
+  %tmp1798 = shl i32 %tmp1797, 22
+  %tmp1799 = xor i32 %tmp1798, %tmp1797
+  %tmp1808 = shl i32 %tmp1799, 5
+  %tmp1809 = xor i32 %tmp1808, %tmp1799
+  %tmp1810 = lshr i32 %tmp1809, 7
+  %tmp1811 = xor i32 %tmp1810, %tmp1809
+  %tmp1812 = shl i32 %tmp1811, 22
+  %tmp1813 = xor i32 %tmp1812, %tmp1811
+  store i32 %tmp1813, i32* %tmp1756, align 4
+; CHECK: store i32 -383584258, i32* %tmp114, align 4
+  %tmp2645 = getelementptr inbounds %2, %2* %tmp1, i64 0, i32 1
+  %tmp2650 = load i32, i32* %tmp2645, align 4
+  %tmp2655 = shl i32 %tmp2650, 5
+  %tmp2656 = xor i32 %tmp2655, %tmp2650
+  %tmp2657 = lshr i32 %tmp2656, 7
+  %tmp2658 = xor i32 %tmp2657, %tmp2656
+  %tmp2659 = shl i32 %tmp2658, 22
+  %tmp2660 = xor i32 %tmp2659, %tmp2658
+  %tmp2669 = shl i32 %tmp2660, 5
+  %tmp2670 = xor i32 %tmp2669, %tmp2660
+  %tmp2671 = lshr i32 %tmp2670, 7
+  %tmp2672 = xor i32 %tmp2671, %tmp2670
+  %tmp2673 = shl i32 %tmp2672, 22
+  %tmp2674 = xor i32 %tmp2673, %tmp2672
+  %tmp2683 = shl i32 %tmp2674, 5
+  %tmp2684 = xor i32 %tmp2683, %tmp2674
+  %tmp2685 = lshr i32 %tmp2684, 7
+  %tmp2686 = xor i32 %tmp2685, %tmp2684
+  %tmp2687 = shl i32 %tmp2686, 22
+  %tmp2688 = xor i32 %tmp2687, %tmp2686
+  %tmp2697 = shl i32 %tmp2688, 5
+  %tmp2698 = xor i32 %tmp2697, %tmp2688
+  %tmp2699 = lshr i32 %tmp2698, 7
+  %tmp2700 = xor i32 %tmp2699, %tmp2698
+  %tmp2701 = shl i32 %tmp2700, 22
+  %tmp2702 = xor i32 %tmp2701, %tmp2700
+  store i32 %tmp2702, i32* %tmp2645, align 4
+; CHECK: store i32 -57163022, i32* %tmp114, align 4
+  ret i32 0
+}