Compilation crash after node replacement

[delena]

Summary

The bug is here: https://llvm.org/bugs/show_bug.cgi?id=31045

The problem occurs when we take a node N and analyze its predecessors (operands of operands). We start from N and recursively go up N = N->getOperand(0).
On some stage of the climbing, we decide to replace one of predecessors with ReplaceAllUsesWith(N, NewNode). The ReplaceAllUsesWith works recursively and at some stage kills parent node.
I added ReplaceOneUseWith() to prevent recursive deletion.
Please let me know if this solution looks reasonable. (I attached the original reproducer, I'll minimize it if the solution itself makes sense.)

[RKSimon]

Please can you add context to the diff?

[delena]

Added context to the diff.

[delena]

Ping.

[spatel]

I haven't looked at this level of the DAG very much, so I'm not the best reviewer for the patch.
But if it's valid to specialize the one-use case, then can we just add a 'hasOneUse()' check to the existing ReplaceAllUsesWith() instead of adding another function call? That way, all callers of ReplaceAllUsesWith() would benefit. Or is there some other difference that triggers the bug that we're trying to avoid?

[delena]

../lib/CodeGen/SelectionDAG/SelectionDAG.cpp

6371

The crash happens due to this line. RemoveNodeFromCSEMaps() - deletes node that is currently in-use.

[RKSimon]

Please reduce the test case as much as you can - remove the metadata and run it through bugpoint to isolate the issue.

I have a similar query to Sanjay: what is preventing you from having a 'hasOneUse' fast path inside SelectionDAG::ReplaceAllUsesWith - isn't a similar crash likely to occur in other cases?

[RKSimon]

Any movement on this?

[RKSimon]

@delena Abandon this? It doesn't look necessary any more

I've confirmed that PR31045 was fixed by D31286/rL298633, I've added a reduced version of 'addr-calc-crash.ll' at rL312786

[RKSimon]

@delena Abandon this?

../include/llvm/CodeGen/SelectionDAG.h

#endif
   /// these replacements are being performed, CSE may cause the From node
   /// to be given new uses. These new uses of From are left in place, and
   /// not automatically transferred to To.
   ///
   void ReplaceAllUsesWith(SDValue From, SDValue Op);
   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);
 
   /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
   /// This correctly handles the case where
   /// there is an overlap between the From values and the To values.
   void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,

../lib/CodeGen/SelectionDAG/SelectionDAG.cpp

void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
   // is replaced by To, we don't want to replace of all its users with To
   // too. See PR3018 for more info.
   SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
   RAUWUpdateListener Listener(*this, UI, UE);
   while (UI != UE) {
     SDNode *User = *UI;
 
     // This node is about to morph, remove its old self from the CSE maps.
     RemoveNodeFromCSEMaps(User);
 
     // A user can appear in a use list multiple times, and when this
     // happens the uses are usually next to each other in the list.
     // To help reduce the number of CSE recomputations, process all
     // the uses of this user that we can find this way.
     do {
       SDUse &Use = UI.getUse();
       ++UI;
       Use.set(To);
     } while (UI != UE && *UI == User);
 
     // Now that we have modified User, add it back to the CSE maps.  If it
     // already exists there, recursively merge the results together.
     AddModifiedNodeToCSEMaps(User);
   }
 
 
   // If we just RAUW'd the root, take note.
   if (FromN == getRoot())
     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.
 ///
 /// This version assumes that for each value of From, there is a
 /// corresponding value in To in the same position with the same type.
 ///
 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
 #ifndef NDEBUG

../lib/Target/X86/X86ISelDAGToDAG.cpp

static bool foldMaskedShiftToScaledMask(SelectionDAG &DAG, SDValue N,
   // Insert the new nodes into the topological ordering. We must do this in
   // a valid topological ordering as nothing is going to go back and re-sort
   // these nodes. We continually insert before 'N' in sequence as this is
   // essentially a pre-flattened and pre-sorted sequence of nodes. There is no
   // hierarchy left to express.
   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;
   return false;
 }
 
 // Implement some heroics to detect shifts of masked values where the mask can
 // be replaced by extending the shift and undoing that in the addressing mode

../test/CodeGen/X86/addr-calc-crash.ll

+; 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}