[ZoneAlgo] Fix PHI inconsistency in invalid contexts.

PHI nodes (reads) could point to multiple instances of predecessor
blocks (PHI writes) when in an invalid context. Fix by removing PHI
instances that are in an invalid or ouside assumed context.

This fixes llvm.org/PR41656.

llvm-svn: 360454

3 files changed, 91 insertions, 2 deletions

diff --git a/polly/test/DeLICM/pr41656.ll b/polly/test/DeLICM/pr41656.ll
new file mode 100644
index 00000000000..4af478e99bf
--- /dev/null
+++ b/polly/test/DeLICM/pr41656.ll
@@ -0,0 +1,89 @@
+; RUN: opt %loadPolly -polly-delicm -analyze < %s | FileCheck %s
+;
+; llvm.org/PR41656
+; 
+; This test case has an InvalidContext such that part of the predecessors
+; of for.body.us.i lie within the invalid context. This causes a
+; consistency check withing the invalid context of PR41656 to fail.
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define dso_local void @main() local_unnamed_addr #0 {
+entry:
+  %call24 = tail call i32 @av_get_channel_layout_nb_channels() #2
+  br label %if.end30
+
+if.end30:                                         ; preds = %entry
+  br i1 undef, label %if.then40, label %do.body.preheader
+
+do.body.preheader:                                ; preds = %if.end30
+  %idx.ext.i = sext i32 %call24 to i64
+  %wide.trip.count.i = zext i32 %call24 to i64
+  %0 = load double*, double** undef, align 8, !tbaa !1
+  br label %for.body.us.preheader.i
+
+if.then40:                                        ; preds = %if.end30
+  unreachable
+
+for.body.us.preheader.i:                          ; preds = %do.body.preheader
+  br i1 false, label %for.body.us.i.us, label %for.body.us.i
+
+for.body.us.i.us:                                 ; preds = %for.body.us.preheader.i
+  br label %fill_samples.exit
+
+for.body.us.i:                                    ; preds = %for.cond2.for.end_crit_edge.us.i, %for.body.us.preheader.i
+  %t.1 = phi double [ undef, %for.cond2.for.end_crit_edge.us.i ], [ 0.000000e+00, %for.body.us.preheader.i ]
+  %i.05.us.i = phi i32 [ %inc8.us.i, %for.cond2.for.end_crit_edge.us.i ], [ 0, %for.body.us.preheader.i ]
+  %dstp.03.us.i = phi double* [ %add.ptr.us.i, %for.cond2.for.end_crit_edge.us.i ], [ %0, %for.body.us.preheader.i ]
+  %mul.us.i = fmul nsz double %t.1, 0x40A59933FC6A96C1
+  %1 = call nsz double @llvm.sin.f64(double %mul.us.i) #2
+  store double %1, double* %dstp.03.us.i, align 8, !tbaa !5
+  %2 = bitcast double* %dstp.03.us.i to i64*
+  br label %for.body5.us.for.body5.us_crit_edge.i
+
+for.body5.us.for.body5.us_crit_edge.i:            ; preds = %for.body5.us.for.body5.us_crit_edge.i.for.body5.us.for.body5.us_crit_edge.i_crit_edge, %for.body.us.i
+  %indvars.iv.next.i66 = phi i64 [ 2, %for.body.us.i ], [ %indvars.iv.next.i, %for.body5.us.for.body5.us_crit_edge.i.for.body5.us.for.body5.us_crit_edge.i_crit_edge ]
+  %indvars.iv.next.i = add nuw nsw i64 %indvars.iv.next.i66, 1
+  %exitcond.i = icmp eq i64 %indvars.iv.next.i, %wide.trip.count.i
+  br i1 %exitcond.i, label %for.cond2.for.end_crit_edge.us.i, label %for.body5.us.for.body5.us_crit_edge.i.for.body5.us.for.body5.us_crit_edge.i_crit_edge
+
+for.body5.us.for.body5.us_crit_edge.i.for.body5.us.for.body5.us_crit_edge.i_crit_edge: ; preds = %for.body5.us.for.body5.us_crit_edge.i
+  %.pre10.i.pre = load i64, i64* %2, align 8, !tbaa !5
+  br label %for.body5.us.for.body5.us_crit_edge.i
+
+for.cond2.for.end_crit_edge.us.i:                 ; preds = %for.body5.us.for.body5.us_crit_edge.i
+  %add.ptr.us.i = getelementptr inbounds double, double* %dstp.03.us.i, i64 %idx.ext.i
+  %inc8.us.i = add nuw nsw i32 %i.05.us.i, 1
+  %exitcond7.i = icmp eq i32 %inc8.us.i, 1024
+  br i1 %exitcond7.i, label %fill_samples.exit, label %for.body.us.i
+
+fill_samples.exit:                                ; preds = %for.cond2.for.end_crit_edge.us.i, %for.body.us.i.us
+  ret void
+}
+
+declare dso_local i32 @av_get_channel_layout_nb_channels() local_unnamed_addr #0
+
+; Function Attrs: nounwind readnone speculatable
+declare double @llvm.sin.f64(double) #1
+
+attributes #0 = { "use-soft-float"="false" }
+attributes #1 = { nounwind readnone speculatable }
+attributes #2 = { nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 9.0.0 (https://github.com/llvm/llvm-project.git 2436237895b70ed44cf256f67eb2f74e147eb559)"}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"any pointer", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}
+!5 = !{!6, !6, i64 0}
+!6 = !{!"double", !3, i64 0}
+
+
+; Only write to scalar if call24 >= 3 (i.e. not in invalid context)
+; Since it should be never executed otherwise, the condition is not strictly necessary. 
+; CHECK:          Stmt_for_body_us_preheader_i
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 [call24] -> { Stmt_for_body_us_preheader_i[] -> MemRef_t_1__phi[] };
+; CHECK-NEXT:            new: [call24] -> { Stmt_for_body_us_preheader_i[] -> MemRef1[0, 0] : call24 >= 3 };
diff --git a/polly/test/DeLICM/reduction_looprotate_hoisted.ll b/polly/test/DeLICM/reduction_looprotate_hoisted.ll
index 3a96ff6138b..47f44956450 100644
--- a/polly/test/DeLICM/reduction_looprotate_hoisted.ll
+++ b/polly/test/DeLICM/reduction_looprotate_hoisted.ll
@@ -70,7 +70,7 @@ return:
 ; CHECK-NEXT:     Stmt_reduction_preheader
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
-; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : Start >= 2147483648 or Start <= 2147483646 };
 ; CHECK-NEXT:     Stmt_reduction_for
 ; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
diff --git a/polly/test/ScopInfo/stmt_with_read_but_without_sideffect.ll b/polly/test/ScopInfo/stmt_with_read_but_without_sideffect.ll
index 2ac6f7b61cd..9d72bf08765 100644
--- a/polly/test/ScopInfo/stmt_with_read_but_without_sideffect.ll
+++ b/polly/test/ScopInfo/stmt_with_read_but_without_sideffect.ll
@@ -86,7 +86,7 @@ for.inc.1:                                        ; preds = %if.then.1, %if.else
 ; CHECK-NEXT:     Stmt_if_else_1_last
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [p_0] -> { Stmt_if_else_1_last[i0] -> MemRef_min_1_1__phi[] };
-; CHECK-NEXT:            new: [p_0] -> { Stmt_if_else_1_last[i0] -> MemRef_ath[i0] };
+; CHECK-NEXT:            new: [p_0] -> { Stmt_if_else_1_last[i0] -> MemRef_ath[i0] : p_0 <= 576460752303423487 };
 ; CHECK-NEXT:     Stmt_for_inc_1
 ; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [p_0] -> { Stmt_for_inc_1[i0] -> MemRef_min_1_1__phi[] };