[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

6 files changed, 117 insertions, 2 deletions

diff --git a/polly/include/polly/Support/ISLTools.h b/polly/include/polly/Support/ISLTools.h
index fab0dae..eb57bf5 100644
--- a/polly/include/polly/Support/ISLTools.h
+++ b/polly/include/polly/Support/ISLTools.h
@@ -463,6 +463,21 @@ isl::union_map applyDomainRange(isl::union_map UMap, isl::union_map Func);
 /// @return { Domain[] -> Range[] }
 isl::map intersectRange(isl::map Map, isl::union_set Range);
 
+/// Subtract the parameter space @p Params from @p Map.
+/// This is akin to isl::map::intersect_params.
+///
+/// Example:
+///   subtractParams(
+///     { [i] -> [i] },
+///     [x] -> { : x < 0 }
+///   ) = [x] -> { [i] -> [i] : x >= 0 }
+///
+/// @param Map    Remove the conditions of @p Params from this map.
+/// @param Params Parameter set to subtract.
+///
+/// @param The map with the parameter conditions removed.
+isl::map subtractParams(isl::map Map, isl::set Params);
+
 /// If @p PwAff maps to a constant, return said constant. If @p Max/@p Min, it
 /// can also be a piecewise constant and it would return the minimum/maximum
 /// value. Otherwise, return NaN.
diff --git a/polly/lib/Support/ISLTools.cpp b/polly/lib/Support/ISLTools.cpp
index 2559262..08bb052 100644
--- a/polly/lib/Support/ISLTools.cpp
+++ b/polly/lib/Support/ISLTools.cpp
@@ -507,6 +507,12 @@ isl::map polly::intersectRange(isl::map Map, isl::union_set Range) {
   return Map.intersect_range(RangeSet);
 }
 
+isl::map polly::subtractParams(isl::map Map, isl::set Params) {
+  auto MapSpace = Map.get_space();
+  auto ParamsMap = isl::map::universe(MapSpace).intersect_params(Params);
+  return Map.subtract(ParamsMap);
+}
+
 isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) {
   assert(!Max || !Min); // Cannot return min and max at the same time.
   isl::val Result;
diff --git a/polly/lib/Transform/ZoneAlgo.cpp b/polly/lib/Transform/ZoneAlgo.cpp
index 6802615..0fd4ab6 100644
--- a/polly/lib/Transform/ZoneAlgo.cpp
+++ b/polly/lib/Transform/ZoneAlgo.cpp
@@ -563,6 +563,11 @@ isl::union_map ZoneAlgorithm::computePerPHI(const ScopArrayInfo *SAI) {
 
   // { DomainPHIRead[] -> Scatter[] }
   isl::map PHIWriteTimes = BeforeRead.intersect_range(WriteTimes);
+
+  // Remove instances outside the context.
+  PHIWriteTimes = PHIWriteTimes.intersect_params(S->getAssumedContext());
+  PHIWriteTimes = subtractParams(PHIWriteTimes, S->getInvalidContext());
+
   isl::map LastPerPHIWrites = PHIWriteTimes.lexmax();
 
   // { DomainPHIRead[] -> DomainPHIWrite[] }
diff --git a/polly/test/DeLICM/pr41656.ll b/polly/test/DeLICM/pr41656.ll
new file mode 100644
index 0000000..4af478e
--- /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 3a96ff6..47f4495 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 2ac6f7b..9d72bf0 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[] };