Index: ../include/llvm/CodeGen/SelectionDAG.h
===================================================================
--- ../include/llvm/CodeGen/SelectionDAG.h
+++ ../include/llvm/CodeGen/SelectionDAG.h
@@ -1120,6 +1120,11 @@
   void ReplaceAllUsesWith(SDNode *From, SDNode *To);
   void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
 
+  /// Modify one node using 'From' to use 'To' instead.
+  /// This function is not recursive and may be used if 'From'
+  /// has only one use. Node 'From' is not deleted.
+  void ReplaceOneUseWith(SDValue From, SDValue Op);
+
   /// Replace any uses of From with To, leaving
   /// uses of other values produced by From.Val alone.
   void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
Index: ../lib/CodeGen/SelectionDAG/SelectionDAG.cpp
===================================================================
--- ../lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ ../lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -6391,6 +6391,25 @@
     setRoot(To);
 }
 
+void SelectionDAG::ReplaceOneUseWith(SDValue FromN, SDValue To) {
+  SDNode *From = FromN.getNode();
+  assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
+         "Cannot replace with this method!");
+  assert(From != To.getNode() && "Cannot replace uses of with self");
+
+  // Preserve Debug Values
+  TransferDbgValues(FromN, To);
+
+  assert(From->hasOneUse() && "The replaced node should have one use only");
+  SDNode::use_iterator UI = From->use_begin();
+  SDUse &Use = UI.getUse();
+  Use.set(To);
+
+  // If we just RAUW'd the root, take note.
+  if (FromN == getRoot())
+    setRoot(To);
+}
+
 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
 /// This can cause recursive merging of nodes in the DAG.
 ///
Index: ../lib/Target/X86/X86ISelDAGToDAG.cpp
===================================================================
--- ../lib/Target/X86/X86ISelDAGToDAG.cpp
+++ ../lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -990,7 +990,7 @@
   insertDAGNode(DAG, N, NewMask);
   insertDAGNode(DAG, N, NewAnd);
   insertDAGNode(DAG, N, NewShift);
-  DAG.ReplaceAllUsesWith(N, NewShift);
+  DAG.ReplaceOneUseWith(N, NewShift);
 
   AM.Scale = 1 << ShiftAmt;
   AM.IndexReg = NewAnd;
Index: ../test/CodeGen/X86/addr-calc-crash.ll
===================================================================
--- ../test/CodeGen/X86/addr-calc-crash.ll
+++ ../test/CodeGen/X86/addr-calc-crash.ll
@@ -0,0 +1,139 @@
+; RUN: llc < %s -o /dev/null
+
+; This test case originally crashed on recursive 
+; address calculation
+; https://llvm.org/bugs/show_bug.cgi?id=31045
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.b = type { %struct.a, %struct.a, i8 }
+%struct.a = type <{ i8, i16 }>
+%struct.c = type { i8, %struct.b, i24, i24 }
+%struct.d = type <{ %struct.c, %struct.c, i8, i8 }>
+
+@var_4 = local_unnamed_addr global i8 0, align 1
+@var_12 = local_unnamed_addr global i8 0, align 1
+@var_14 = local_unnamed_addr global i8 0, align 1
+@var_40 = local_unnamed_addr global i8 0, align 1
+@var_46 = local_unnamed_addr global i8 0, align 1
+@var_57 = local_unnamed_addr global i8 0, align 1
+@var_58 = local_unnamed_addr global i8 0, align 1
+@var_44 = local_unnamed_addr global i8 0, align 1
+@var_163 = local_unnamed_addr global i8 0, align 1
+@struct_obj_2 = local_unnamed_addr global %struct.b zeroinitializer, align 1
+@struct_obj_12 = local_unnamed_addr global %struct.c zeroinitializer, align 2
+@struct_obj_1 = local_unnamed_addr global %struct.d zeroinitializer, align 2
+@struct_obj_3 = local_unnamed_addr global %struct.d zeroinitializer, align 2
+@struct_obj_5 = local_unnamed_addr global %struct.d zeroinitializer, align 2
+@struct_obj_8 = local_unnamed_addr global %struct.d zeroinitializer, align 2
+@var_49 = external local_unnamed_addr constant i8, align 1
+
+; Function Attrs: norecurse nounwind uwtable
+define void @_Z1av() local_unnamed_addr #0 {
+entry:
+  %bf.load = load i32, i32* bitcast (i24* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_3, i64 0, i32 0, i32 2) to i32*), align 2
+  %0 = load i8, i8* @var_46, align 1, !tbaa !1
+  %conv1 = sext i8 %0 to i32
+  %1 = load i8, i8* @var_49, align 1, !tbaa !4, !range !6
+  %2 = zext i8 %1 to i32
+  %3 = load i8, i8* @var_57, align 1, !tbaa !1
+  %conv9 = sext i8 %3 to i32
+  %4 = shl i32 %bf.load, 1
+  %factor = and i32 %4, 2
+  %sub = sub nsw i32 %factor, %conv1
+  %sub8 = sub nsw i32 %sub, %2
+  %add = add nsw i32 %sub8, %conv9
+  %5 = load i8, i8* @var_58, align 1, !tbaa !1
+  %conv1098 = zext i8 %5 to i32
+  %6 = load i8, i8* @var_44, align 1, !tbaa !4, !range !6
+  %7 = zext i8 %6 to i32
+  %sum = add nuw nsw i32 %7, %conv1098
+  %sub14 = sub nsw i32 0, %sum
+  %bf.load15 = load i8, i8* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_8, i64 0, i32 0, i32 1, i32 2), align 1
+  %8 = and i8 %bf.load15, 1
+  %9 = zext i8 %8 to i32
+  %and = and i32 %9, %sub14
+  %10 = load i8, i8* @var_40, align 1, !tbaa !1
+  %conv19103 = zext i8 %10 to i32
+  %xor = xor i32 %add, 255
+  %xor20 = xor i32 %xor, %conv19103
+  %neg = xor i32 %xor20, %and
+  %bf.load21 = load i32, i32* bitcast (i24* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_5, i64 0, i32 0, i32 3) to i32*), align 2
+  %11 = load i8, i8* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_1, i64 0, i32 2), align 2, !tbaa !7, !range !6
+  %12 = zext i8 %11 to i32
+  %and26 = and i32 %12, %bf.load21
+  %13 = load i8, i8* @var_12, align 1, !tbaa !1
+  %bf.load30 = load i8, i8* getelementptr inbounds (%struct.b, %struct.b* @struct_obj_2, i64 0, i32 2), align 1
+  %bf.load35 = load i8, i8* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_8, i64 0, i32 0, i32 0), align 2
+  %bf.shl36 = shl i8 %bf.load35, 1
+  %bf.ashr37 = ashr exact i8 %bf.shl36, 1
+  %14 = and i8 %13, 1
+  %and34102 = and i8 %14, %bf.load30
+  %and39106 = and i8 %and34102, %bf.ashr37
+  %and39 = zext i8 %and39106 to i32
+  %xor40 = xor i32 %and39, %and26
+  %or = or i32 %xor40, %neg
+  %bf.load41 = load i8, i8* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_5, i64 0, i32 1, i32 1, i32 2), align 1
+  %15 = and i8 %bf.load41, 1
+  %16 = zext i8 %15 to i32
+  %17 = load i8, i8* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_5, i64 0, i32 1, i32 1, i32 0, i32 0), align 1, !tbaa !12, !range !6
+  %18 = zext i8 %17 to i32
+  %bf.load47 = load i32, i32* bitcast (i24* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_5, i64 0, i32 1, i32 2) to i32*), align 2
+  %19 = and i32 %bf.load47, 1
+  %add51 = add nuw nsw i32 %19, %18
+  %20 = load i8, i8* @var_4, align 1, !tbaa !1
+  %conv52 = sext i8 %20 to i32
+  %sub53 = sub nsw i32 %add51, %conv52
+  %cmp = icmp eq i32 %16, %sub53
+  %conv54 = zext i1 %cmp to i32
+  %or55 = or i32 %or, %conv54
+  %conv56 = trunc i32 %or55 to i16
+  %bf.load57 = load i16, i16* getelementptr inbounds (%struct.c, %struct.c* @struct_obj_12, i64 0, i32 1, i32 1, i32 1), align 1
+  %bf.value = and i16 %conv56, 255
+  %bf.clear58 = and i16 %bf.load57, -2048
+  %bf.set = or i16 %bf.value, %bf.clear58
+  store i16 %bf.set, i16* getelementptr inbounds (%struct.c, %struct.c* @struct_obj_12, i64 0, i32 1, i32 1, i32 1), align 1
+  %21 = load i8, i8* @var_14, align 1, !tbaa !1
+  %lnot = icmp eq i8 %21, 0
+  %bf.load61 = load i8, i8* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_3, i64 0, i32 0, i32 1, i32 2), align 1
+  %22 = and i8 %bf.load61, 1
+  %23 = zext i8 %22 to i32
+  %bf.load65 = load i32, i32* bitcast (i24* getelementptr inbounds (%struct.d, %struct.d* @struct_obj_8, i64 0, i32 0, i32 2) to i32*), align 2
+  %24 = and i32 %bf.load65, 1
+  %.op = sub nsw i32 0, %23
+  %25 = select i1 %lnot, i32 %.op, i32 0
+  %mul69 = and i32 %24, %25
+  %26 = sub nsw i32 0, %mul69
+  %mul75 = and i32 %7, %26
+  %27 = and i32 %bf.load, 1
+  %28 = sub nsw i32 0, %mul75
+  %mul80 = and i32 %27, %28
+  %factor109 = shl nuw nsw i32 %27, 1
+  %sub86 = sub nsw i32 %factor109, %conv1
+  %sub94 = sub nsw i32 %sub86, %2
+  %29 = sub nsw i32 0, %mul80
+  %mul95 = and i32 %sub94, %29
+  %tobool96 = icmp ne i32 %mul95, 0
+  %frombool = zext i1 %tobool96 to i8
+  store i8 %frombool, i8* @var_163, align 1, !tbaa !4
+  ret void
+}
+
+attributes #0 = { norecurse nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 4.0.0 (trunk 285685)"}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"omnipotent char", !3, i64 0}
+!3 = !{!"Simple C++ TBAA"}
+!4 = !{!5, !5, i64 0}
+!5 = !{!"bool", !2, i64 0}
+!6 = !{i8 0, i8 2}
+!7 = !{!8, !5, i64 32}
+!8 = !{!"_ZTS1d", !9, i64 0, !9, i64 16, !5, i64 32}
+!9 = !{!"_ZTS1c", !2, i64 0, !10, i64 1, !5, i64 8, !2, i64 12}
+!10 = !{!"_ZTS1b", !11, i64 0, !11, i64 3, !5, i64 6}
+!11 = !{!"_ZTS1a", !5, i64 0, !2, i64 1}
+!12 = !{!8, !5, i64 17}