Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -4378,6 +4378,12 @@
   if (!BEValueV || !StartValueV)
     return None;
 
+  // Make sure that the expression that updates the PHI is an Add
+  if (auto *Op = dyn_cast<BinaryOperator>(BEValueV)) {
+    if (Op->getOpcode() != Instruction::BinaryOps::Add)
+      return None;
+  }
+
   const SCEV *BEValue = getSCEV(BEValueV);
 
   // If the value coming around the backedge is an add with the symbolic
Index: test/Analysis/ScalarEvolution/loop-xor.ll
===================================================================
--- /dev/null
+++ test/Analysis/ScalarEvolution/loop-xor.ll
@@ -0,0 +1,34 @@
+; opt -S -loop-vectorize < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+; This test is here to make sure that the SCEV predicate rewriter
+; does not attempt to create a SCEVAddRec from a loop expression
+; that isn't actually an add. If it does try, then this test
+; will likely cause it to blow up.
+define void @foo() {
+; CHECK-LABEL: @foo
+
+; CHECK-LABEL: bb:
+; CHECK: br label %bb1
+bb:
+  br label %bb1
+
+; CHECK-LABEL: bb1:
+; CHECK:  %tmp = phi i64 [ -7, %bb ], [ %tmp4, %bb1 ]
+; CHECK:  %tmp2 = shl i64 %tmp, 32
+; CHECK:  %tmp3 = ashr exact i64 %tmp2, 32
+; CHECK:  %tmp4 = xor i64 %tmp3, -9223372036854775808
+; CHECK:  br
+bb1:
+  %tmp = phi i64 [ -7, %bb ], [ %tmp4, %bb1 ]
+  %tmp2 = shl i64 %tmp, 32
+  %tmp3 = ashr exact i64 %tmp2, 32
+  %tmp4 = xor i64 %tmp3, -9223372036854775808
+  br i1 undef, label %bb5, label %bb1
+
+; CHECK-LABEL: bb5:
+; CHECK: unreachable
+bb5:
+  unreachable
+}