Handle cast instructions in complete loop unroll heuristic.

[mzolotukhin]

Summary

Cast instructions are important to handle since induction variables are often extended to 64-bits.
This patch is intended to be applied after D10205 (though it could be applied independently with minor changes).

[mzolotukhin]

• Don't try to const-prop casts if the simplified value is just an offset from a base pointer.

[chandlerc]

No test case here? Is this covered by the tests in D10208?

lib/Transforms/Scalar/LoopUnrollPass.cpp

430–434 ↗

(On Diff #27091)

I think the need for this will go away when offsets aren't (incorrectly) marked as needed in SimplifiedValues. See my comments is D10205.

436 ↗

(On Diff #27091)

This doesn't seem to be specific to ptrtoint. =]

[mzolotukhin]

• Fallback to Base visitor if failed to constant fold (and only then call simplifyInstWithSCEV).
• Add TODO to visitCast.

[mzolotukhin]

No test case here? Is this covered by the tests in D10208?

Yes, all tests are in D10208.

[mzolotukhin]

Ping!

[mzolotukhin]

Ping!

[mzolotukhin]

Ping!

[chandlerc]

This patch looks fine, but I'd like to have a test case that specifically exercises it. Is that possible given the current state, or does that come in a subsequent patch?

lib/Transforms/Scalar/LoopUnrollPass.cpp

444 ↗

(On Diff #27261)

This comment still seems stale (referring to ptrtoint).

[chandlerc]

Just as a note, this LGTM provided a minimal test change is included when it is committed.

[mzolotukhin]

Thanks!

I added a new test here and committed the patch (with comment fixed too) in r242257.

llvm/trunk/lib/Transforms/Scalar/LoopUnrollPass.cpp

bool visitLoad(LoadInst &I) {
     }
 
     Constant *CV = CDS->getElementAsConstant(Index);
     assert(CV && "Constant expected.");
     SimplifiedValues[&I] = CV;
 
     return true;
   }
+
+  bool visitCastInst(CastInst &I) {
+    // Propagate constants through casts.
+    Constant *COp = dyn_cast<Constant>(I.getOperand(0));
+    if (!COp)
+      COp = SimplifiedValues.lookup(I.getOperand(0));
+    if (COp)
+      if (Constant *C =
+              ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
+        SimplifiedValues[&I] = C;
+        return true;
+      }
+
+    return Base::visitCastInst(I);
+  }
 };
 } // namespace
 
 
 namespace {
 struct EstimatedUnrollCost {
   /// \brief The estimated cost after unrolling.
   unsigned UnrolledCost;

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-heuristics-cast.ll

+; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-dynamic-cost-savings-discount=1000 -unroll-threshold=10 -unroll-percent-dynamic-cost-saved-threshold=50 | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+@known_constant = internal unnamed_addr constant [10 x i32] [i32 0, i32 1, i32 0, i32 1, i32 0, i32 1, i32 0, i32 1, i32 0, i32 1], align 16
+
+; We should be able to propagate constant data thru different types of casts.
+; For example, in this test we have a load, which becomes constant after
+; unrolling, which then is truncated to i8. Obviously, truncated value is also a
+; constant, which can be used in the further simplifications.
+;
+; We expect this loop to be unrolled, because in this case load would become
+; constant, which is 0 in many cases, and which, in its turn, helps to simplify
+; following multiplication and addition. In total, unrolling should help to
+; optimize  ~60% of all instructions in this case.
+;
+; CHECK-LABEL: @const_load_trunc
+; CHECK-NOT: br i1 %exitcond86.i, label %loop.end, label %loop
+define i8 @const_load_trunc(i32* noalias nocapture readonly %src) {
+entry:
+  br label %loop
+
+loop:                                                ; preds = %loop, %entry
+  %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]
+  %r  = phi i8 [ 0, %entry ], [ %add, %loop ]
+  %arrayidx = getelementptr inbounds i32, i32* %src, i64 %iv
+  %src_element = load i32, i32* %arrayidx, align 4
+  %array_const_idx = getelementptr inbounds [10 x i32], [10 x i32]* @known_constant, i64 0, i64 %iv
+  %const_array_element = load i32, i32* %array_const_idx, align 4
+  %x = trunc i32 %src_element to i8
+  %y = trunc i32 %const_array_element to i8
+  %mul = mul nsw i8 %x, %y
+  %add = add nsw i8 %mul, %r
+  %inc = add nuw nsw i64 %iv, 1
+  %exitcond86.i = icmp eq i64 %inc, 10
+  br i1 %exitcond86.i, label %loop.end, label %loop
+
+loop.end:                                            ; preds = %loop
+  %r.lcssa = phi i8 [ %r, %loop ]
+  ret i8 %r.lcssa
+}
+
+; The same test as before, but with ZEXT instead of TRUNC.
+; CHECK-LABEL: @const_load_zext
+; CHECK-NOT: br i1 %exitcond86.i, label %loop.end, label %loop
+define i64 @const_load_zext(i32* noalias nocapture readonly %src) {
+entry:
+  br label %loop
+
+loop:                                                ; preds = %loop, %entry
+  %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]
+  %r  = phi i64 [ 0, %entry ], [ %add, %loop ]
+  %arrayidx = getelementptr inbounds i32, i32* %src, i64 %iv
+  %src_element = load i32, i32* %arrayidx, align 4
+  %array_const_idx = getelementptr inbounds [10 x i32], [10 x i32]* @known_constant, i64 0, i64 %iv
+  %const_array_element = load i32, i32* %array_const_idx, align 4
+  %x = zext i32 %src_element to i64
+  %y = zext i32 %const_array_element to i64
+  %mul = mul nsw i64 %x, %y
+  %add = add nsw i64 %mul, %r
+  %inc = add nuw nsw i64 %iv, 1
+  %exitcond86.i = icmp eq i64 %inc, 10
+  br i1 %exitcond86.i, label %loop.end, label %loop
+
+loop.end:                                            ; preds = %loop
+  %r.lcssa = phi i64 [ %r, %loop ]
+  ret i64 %r.lcssa
+}
+
+; The same test as the first one, but with SEXT instead of TRUNC.
+; CHECK-LABEL: @const_load_sext
+; CHECK-NOT: br i1 %exitcond86.i, label %loop.end, label %loop
+define i64 @const_load_sext(i32* noalias nocapture readonly %src) {
+entry:
+  br label %loop
+
+loop:                                                ; preds = %loop, %entry
+  %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]
+  %r  = phi i64 [ 0, %entry ], [ %add, %loop ]
+  %arrayidx = getelementptr inbounds i32, i32* %src, i64 %iv
+  %src_element = load i32, i32* %arrayidx, align 4
+  %array_const_idx = getelementptr inbounds [10 x i32], [10 x i32]* @known_constant, i64 0, i64 %iv
+  %const_array_element = load i32, i32* %array_const_idx, align 4
+  %x = sext i32 %src_element to i64
+  %y = sext i32 %const_array_element to i64
+  %mul = mul nsw i64 %x, %y
+  %add = add nsw i64 %mul, %r
+  %inc = add nuw nsw i64 %iv, 1
+  %exitcond86.i = icmp eq i64 %inc, 10
+  br i1 %exitcond86.i, label %loop.end, label %loop
+
+loop.end:                                            ; preds = %loop
+  %r.lcssa = phi i64 [ %r, %loop ]
+  ret i64 %r.lcssa
+}