[SCEV] Do not insert if it is already in cache

[skatkov]

Summary

This is fix for the crash caused by ScalarEvolution::getTruncateExpr.

It expects that if it checked the condition that SCEV is not in UniqueSCEVs cache in
the beginning that it will not be there inside this method.

However during recursion and transformation/simplification for sub expression,
it is possible that these modifications will end up with the same SCEV as we started from.

So we must always check whether SCEV is in cache and do not insert item if it is already there.

[skatkov]

Test is simplified a bit, comment in test is provided to explain how we got a crash.

[mkazantsev]

Do you mind giving the blocks in test some reasonable names? E.g. outer_loop, inner_loop etc, just to make it clear what is going on.

test/Analysis/ScalarEvolution/truncate.ll

44

Nit: update -> updated

[skatkov]

Hi Sanjoy, could you please take a look into this as well?

[sanjoy]

LGTM!

lib/Analysis/ScalarEvolution.cpp

1272

Please add comments here and below about what's going on.

test/Analysis/ScalarEvolution/truncate.ll

23

Please run this through -metarenamer. The %1 etc. names aren't really names, and e.g. adding a new instruction to the test will change these (which will make the test difficult to update).

lib/Analysis/ScalarEvolution.cpp

if (const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Op)) {
     for (unsigned i = 0, e = SA->getNumOperands(); i != e && !hasTrunc; ++i) {
       const SCEV *S = getTruncateExpr(SA->getOperand(i), Ty);
       if (!isa<SCEVCastExpr>(SA->getOperand(i)))
         hasTrunc = isa<SCEVTruncateExpr>(S);
       Operands.push_back(S);
     }
     if (!hasTrunc)
       return getAddExpr(Operands);
-    UniqueSCEVs.FindNodeOrInsertPos(ID, IP);  // Mutates IP, returns NULL.
+    if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+      return S;
   }
 
   // trunc(x1*x2*...*xN) --> trunc(x1)*trunc(x2)*...*trunc(xN) if we can
   // eliminate all the truncates, or we replace other casts with truncates.
   if (const SCEVMulExpr *SM = dyn_cast<SCEVMulExpr>(Op)) {
     SmallVector<const SCEV *, 4> Operands;
     bool hasTrunc = false;
     for (unsigned i = 0, e = SM->getNumOperands(); i != e && !hasTrunc; ++i) {
       const SCEV *S = getTruncateExpr(SM->getOperand(i), Ty);
       if (!isa<SCEVCastExpr>(SM->getOperand(i)))
         hasTrunc = isa<SCEVTruncateExpr>(S);
       Operands.push_back(S);
     }
     if (!hasTrunc)
       return getMulExpr(Operands);
-    UniqueSCEVs.FindNodeOrInsertPos(ID, IP);  // Mutates IP, returns NULL.
+    if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+      return S;
   }
 
   // If the input value is a chrec scev, truncate the chrec's operands.
   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
     SmallVector<const SCEV *, 4> Operands;
     for (const SCEV *Op : AddRec->operands())
       Operands.push_back(getTruncateExpr(Op, Ty));
     return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);

test/Analysis/ScalarEvolution/truncate.ll

+; RUN: opt < %s -analyze -scalar-evolution
+; RUN: opt < %s -passes='print<scalar-evolution>'
+; Regression test for assert ScalarEvolution::getTruncateExpr.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test(i8*, i8 %p1, i64 %p2) {
+entry:
+  br label %label5
+
+label1.loopexit:                                  ; preds = %not_zero108.1
+  br i1 true, label %label2, label %label5
+
+label2:                                           ; preds = %label1.loopexit
+  br label %label4
+
+label3:                                           ; preds = %label4
+  ret void
+
+label4:                                           ; preds = %label4, %label2
+  %1 = phi i64 [ %15, %label2 ], [ %4, %label4 ]
+  %local_4_33 = phi i32 [ 3, %label2 ], [ %5, %label4 ]
+; The following steps led to crash
+; First it tries to get a SCEV for %2 instruction
+; As soon as it does not exists it tries to create SCEV
+; This is truncate so it invokes getTruncateExpr for SCEV for operand %1
+; It did not find it in a cache, and it is AddRec:
+; {(-1 + (sext i8 {(-2 + %p1),+,-2}<%label6> to i64) + (-1 * (sext i8 {(-1 + %p1),+,-2}<%label6> to i64)) + %6),+,-1}<%label4>
+; Takes the operand (-1 + (sext i8 {(-2 + %p1),+,-2}<%label6> to i64) + (-1 * (sext i8 {(-1 + %p1),+,-2}<%label6> to i64)) + %6)
+; and tries to getTruncateExpr of it.
+; It is Add expresion so traverse throuh its operands...
+; First operand is -1 and everything is ok.
+; Second operand is (sext i8 {(-2 + %p1),+,-2}<%label6> to i64)
+; So go to ScalarEvolution::getTruncateOrSignExtend with {(-2 + %p1),+,-2}<%label6>
+; It is sext so go to getSignExtendExpr.
+; It is AddRec and affine, so when we try to check isLoopBackedgeGuardedByCond,
+; recursevely it ends up with ScalarEvolution::getTruncateExpr for
+; Op = (-1 + (sext i8 {(-2 + %p1),+,-2}<%label6> to i64) + (-1 * (sext i8 {(-1 + %p1),+,-2}<%label6> to i64)) + %6)
+; which is exactly the same we had before.
+; Now we will build it and add to cache.
+; When we return back to the second invocation of getTruncateExpr,
+; it expects that SCEV is not in the cache but it was added in recursive invocations.
+; So SCEV is in cache, Insertion Point is not update (remains nullptr) and we
+; get a crash when we insert SCEV into cache.
+  %2 = trunc i64 %1 to i32
+  %3 = sdiv i32 %2, %local_4_33
+  %4 = add i64 %1, -1
+  %5 = add i32 %3, %local_4_33
+  br i1 true, label %label3, label %label4
+
+label5:                                           ; preds = %label1.loopexit, %entry
+  br label %label6
+
+label6:                                           ; preds = %not_zero108.1, %label5
+  %6 = phi i64 [ %p2, %label5 ], [ %15, %not_zero108.1 ]
+  %7 = phi i8 [ %p1, %label5 ], [ %13, %not_zero108.1 ]
+  %local_3_91 = phi i32 [ 1, %label5 ], [ %18, %not_zero108.1 ]
+  %8 = add i8 %7, -1
+  %9 = sext i8 %8 to i64
+  %.neg126 = sub i64 1, %6
+  %10 = add i64 %.neg126, %9
+  %11 = trunc i64 %10 to i32
+  %12 = icmp eq i32 %11, 0
+  br i1 %12, label %zero107.loopexit, label %not_zero108
+
+not_zero108:                                      ; preds = %label6
+  br i1 true, label %done111, label %general_case110
+
+general_case110:                                  ; preds = %not_zero108
+  br label %done111
+
+done111:                                          ; preds = %general_case110, %not_zero108
+  %13 = add i8 %7, -2
+  %14 = sext i8 %13 to i64
+  %15 = sub i64 %14, %10
+  %16 = trunc i64 %15 to i32
+  %17 = icmp eq i32 %16, 0
+  br i1 %17, label %zero107.split.loop.exit, label %not_zero108.1
+
+zero107.split.loop.exit:                          ; preds = %done111
+  br label %zero107
+
+zero107.loopexit:                                 ; preds = %label6
+  br label %zero107
+
+zero107:                                          ; preds = %zero107.loopexit, %zero107.split.loop.exit
+  unreachable
+
+not_zero108.1:                                    ; preds = %done111
+  %18 = add nuw nsw i32 %local_3_91, 2
+  %19 = icmp ugt i32 %local_3_91, 52
+  br i1 %19, label %label1.loopexit, label %label6
+}