Index: ../lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
===================================================================
--- ../lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ ../lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -1074,10 +1074,11 @@
         SDValue SAO =
           DAG.getShiftAmountOperand(Node->getOperand(0).getValueType(),
                                     Node->getOperand(1));
-        HandleSDNode Handle(SAO);
-        LegalizeOp(SAO.getNode());
-        NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
-                                         Handle.getValue());
+        // The getShiftAmountOperand() may create a new operand node or
+        // return the existing one. If new operand is created we need
+        // to update the parent node.
+        if (SAO != Node->getOperand(1))
+          NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0), SAO);
       }
       break;
     case ISD::SRL_PARTS:
@@ -1089,11 +1090,12 @@
         SDValue SAO =
           DAG.getShiftAmountOperand(Node->getOperand(0).getValueType(),
                                     Node->getOperand(2));
-        HandleSDNode Handle(SAO);
-        LegalizeOp(SAO.getNode());
-        NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
-                                         Node->getOperand(1),
-                                         Handle.getValue());
+        // The getShiftAmountOperand() may create a new operand node or
+        // return the existing one. If new operand is created we need
+        // to update the parent node.
+        if (SAO != Node->getOperand(2))
+          NewNode = DAG.UpdateNodeOperands(Node, Node->getOperand(0),
+                                           Node->getOperand(1), SAO);
       }
       break;
     }
Index: ../test/CodeGen/X86/shl-crash-on-legalize.ll
===================================================================
--- ../test/CodeGen/X86/shl-crash-on-legalize.ll
+++ ../test/CodeGen/X86/shl-crash-on-legalize.ll
@@ -0,0 +1,34 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+;RUN: llc < %s | FileCheck %s
+
+; This test case failed on legalization of "shl" node. PR29058.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@_ZN8struct_210member_2_3E = external local_unnamed_addr global i64, align 8
+@var_366 = external local_unnamed_addr global i8, align 1
+
+; Function Attrs: norecurse nounwind uwtable
+define i32 @_Z3foov() local_unnamed_addr #0 {
+; CHECK-LABEL: _Z3foov:
+; CHECK:       # BB#0: # %entry
+; CHECK-NEXT:    movq %rax, {{.*}}(%rip)
+; CHECK-NEXT:    retq
+entry:
+  %tobool4 = icmp ne i8 undef, 0
+  %tobool172 = icmp eq i8 undef, 0
+  %0 = select i1 %tobool172, i32 2147483646, i32 undef
+  %or198 = select i1 %tobool4, i32 undef, i32 -1
+  %shl199 = shl i32 %0, %or198
+  %conv201 = zext i32 %shl199 to i64
+  store i64 %conv201, i64* @_ZN8struct_210member_2_3E, align 8
+  %.phitmp455 = select i1 %tobool172, i32 2147483646, i32 undef
+  %lnot407 = icmp eq i8 undef, 0
+  %or419 = select i1 %lnot407, i32 -1, i32 undef
+  %shl420 = shl i32 %.phitmp455, %or419
+  ret i32 %shl420
+}
+
+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" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+