Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -1268,7 +1268,8 @@
     }
     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
@@ -1284,7 +1285,8 @@
     }
     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.
Index: test/Analysis/ScalarEvolution/truncate.ll
===================================================================
--- /dev/null
+++ test/Analysis/ScalarEvolution/truncate.ll
@@ -0,0 +1,94 @@
+; 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 %header_outer
+
+backedge_outer:                                  ; preds = %backedge_inner
+  br i1 true, label %preheder_second, label %header_outer
+
+preheder_second:                                           ; preds = %backedge_outer
+  br label %loop_second
+
+exit:                                           ; preds = %loop_second
+  ret void
+
+loop_second:                                           ; preds = %loop_second, %preheder_second
+  %1 = phi i64 [ %15, %preheder_second ], [ %4, %loop_second ]
+  %local_4_33 = phi i32 [ 3, %preheder_second ], [ %5, %loop_second ]
+; 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}<%header_inner> to i64) + (-1 * (sext i8 {(-1 + %p1),+,-2}<%header_inner> to i64)) + %6),+,-1}<%loop_second>
+; Takes the operand (-1 + (sext i8 {(-2 + %p1),+,-2}<%header_inner> to i64) + (-1 * (sext i8 {(-1 + %p1),+,-2}<%header_inner> 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}<%header_inner> to i64)
+; So go to ScalarEvolution::getTruncateOrSignExtend with {(-2 + %p1),+,-2}<%header_inner>
+; 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}<%header_inner> to i64) + (-1 * (sext i8 {(-1 + %p1),+,-2}<%header_inner> 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 updated (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 %exit, label %loop_second
+
+header_outer:                                           ; preds = %backedge_outer, %entry
+  br label %header_inner
+
+header_inner:                                           ; preds = %backedge_inner, %header_outer
+  %6 = phi i64 [ %p2, %header_outer ], [ %15, %backedge_inner ]
+  %7 = phi i8 [ %p1, %header_outer ], [ %13, %backedge_inner ]
+  %local_3_91 = phi i32 [ 1, %header_outer ], [ %18, %backedge_inner ]
+  %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 = %header_inner
+  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 %backedge_inner
+
+zero107.split.loop.exit:                          ; preds = %done111
+  br label %zero107
+
+zero107.loopexit:                                 ; preds = %header_inner
+  br label %zero107
+
+zero107:                                          ; preds = %zero107.loopexit, %zero107.split.loop.exit
+  unreachable
+
+backedge_inner:                                    ; preds = %done111
+  %18 = add nuw nsw i32 %local_3_91, 2
+  %19 = icmp ugt i32 %local_3_91, 52
+  br i1 %19, label %backedge_outer, label %header_inner
+}