Differential D45066
[Polly] [ScopInfo] Remove bail out condition in buildMinMaxAccess() Authored by cs15btech11044 on Mar 29 2018, 3:00 PM.
Details This fix is a continuation of the discussion which happened here. It addresses the issue, with the help of suggestions from @Meinersbur. This patch tries to remove the premature max-disjuncts bail-out condition by using simple_hull() to reduce the computational overhead, instead of directly invalidating that SCoP. Instead of deciding for bail-out at compile time, we let the max-computations limit take care of it.
Diff Detail
Event TimelineComment Actions List of failing regression tests: Failing Tests (13):
Polly :: Isl/Ast/aliasing_parametric_simple_2.ll
Polly :: Isl/CodeGen/OpenMP/recomputed-srem.ll
Polly :: Isl/CodeGen/alias-check-multi-dim.ll
Polly :: Isl/CodeGen/aliasing_parametric_simple_2.ll
Polly :: Isl/CodeGen/exprModDiv.ll
Polly :: Isl/CodeGen/scev_expansion_in_nonaffine.ll
Polly :: Isl/CodeGen/test-invalid-operands-for-select-2.ll
Polly :: Isl/CodeGen/test-invalid-operands-for-select.ll
Polly :: ScopInfo/aliasing_many_parameters_not_all_involved.ll
Polly :: ScopInfo/invariant_load_zext_parameter-2.ll
Polly :: ScopInfo/long-compile-time-alias-analysis.ll
Polly :: ScopInfo/run-time-check-many-array-disjuncts.ll
Polly :: ScopInfo/run-time-check-many-parameters.ll
Expected Passes : 1030
Expected Failures : 13
Unsupported Tests : 73
Unexpected Failures: 13Each of these test cases fail at one single point: assert(MaxPMA.dim(isl::dim::out) && "Assumed at least one output dimension"); in ScopInfo.cpp:2345 Comment Actions We saw a similar assertion failure internally recently, but didn't get around to upstreaming the patch yet. I think you just need to move the "if (isl_ctx_last_error(Ctx.get()) == isl_error_quota)" after the call to "MaxPMA.coalesce()". Comment Actions Thanks your contribution! With the infos provided you should be able to fix the assertions.
Comment Actions Some more analysis from my side:
Comment Actions Implementing the changes suggested by @Meinersbur Failing Tests (10):
Polly :: Isl/Ast/aliasing_parametric_simple_2.ll
Polly :: Isl/CodeGen/OpenMP/recomputed-srem.ll
Polly :: Isl/CodeGen/alias-check-multi-dim.ll
Polly :: Isl/CodeGen/aliasing_parametric_simple_2.ll
Polly :: Isl/CodeGen/exprModDiv.ll
Polly :: Isl/CodeGen/scev_expansion_in_nonaffine.ll
Polly :: Isl/CodeGen/test-invalid-operands-for-select-2.ll
Polly :: Isl/CodeGen/test-invalid-operands-for-select.ll
Polly :: ScopInfo/aliasing_many_parameters_not_all_involved.ll
Polly :: ScopInfo/invariant_load_zext_parameter-2.ll
Expected Passes : 1033
Expected Failures : 13
Unsupported Tests : 73
Unexpected Failures: 10
Comment Actions Addressing the previous suggestions as well as incorporating some of mine. PS: None of the regression tests have failed in this case.
Comment Actions Changes made to this new patch:
Comment Actions Thanks for the update. I don't understand why you changed Set to a reference and introduced SimpleSet?
Comment Actions
Comment Actions Updates in this patch:
Comment Actions As discussed, here is a test-case. It was more difficult than I originally thought because ScalarEvolution does not support plain select (Array subscripts must be SCEVs). Using JScop-import also was no solution because Polly does not create new aliasing expressions after the import. I used smax expressions instead, which SCEVAffinator produces piecewise pw_affs. polly::simplify must also not coalesce these sets after remove_divs() and range() (it does still coalesces some of them), and I need at least 9 pieces. test/ScopInfo/piecewise_aliasing.ll ; RUN: opt %loadPolly -polly-scops -analyze < %s
;
define void @func(i64 %n, double* nonnull %A, double* nonnull %B, i64 %d) {
entry:
br label %for
for:
%j = phi i64 [0, %entry], [%j.inc, %inc]
%j.cmp = icmp slt i64 %j, %n
br i1 %j.cmp, label %body, label %exit
body:
%add.i.i = add nsw i64 1, %j
%sub.i.i = sub nsw i64 %add.i.i, 1
%cmp.i.i.i = icmp sgt i64 %sub.i.i, 0
%cond.i.i.i = select i1 %cmp.i.i.i, i64 %sub.i.i, i64 0
%mul.i.i = mul nsw i64 %cond.i.i.i, 7
%sub1.i.i = sub nsw i64 1, %j
%add2.i.i = add nsw i64 %sub1.i.i, 1
%cmp.i8.i.i = icmp sgt i64 %add2.i.i, 0
%cond.i11.i.i = select i1 %cmp.i8.i.i, i64 %add2.i.i, i64 0
%mul4.i.i = mul nsw i64 %cond.i11.i.i, 7
%add5.i.i = add nsw i64 %mul.i.i, %mul4.i.i
%add.i113.i = add nsw i64 1, %j
%sub.i114.i = sub nsw i64 %add.i113.i, 3
%cmp.i.i115.i = icmp sgt i64 %sub.i114.i, 0
%cond.i.i118.i = select i1 %cmp.i.i115.i, i64 %sub.i114.i, i64 0
%mul.i119.i = mul nsw i64 %cond.i.i118.i, 9
%sub1.i120.i = sub nsw i64 1, %j
%add2.i121.i = add nsw i64 %sub1.i120.i, 3
%cmp.i8.i122.i = icmp sgt i64 %add2.i121.i, 0
%cond.i11.i126.i = select i1 %cmp.i8.i122.i, i64 %add2.i121.i, i64 0
%mul4.i127.i = mul nsw i64 %cond.i11.i126.i, 9
%add5.i128.i = add nsw i64 %mul.i119.i, %mul4.i127.i
%add.i = add nsw i64 %add5.i.i, %add5.i128.i
%add.i89.i = add nsw i64 1, %j
%sub.i90.i = sub nsw i64 %add.i89.i, 4
%cmp.i.i91.i = icmp sgt i64 %sub.i90.i, 0
%cond.i.i94.i = select i1 %cmp.i.i91.i, i64 %sub.i90.i, i64 0
%mul.i95.i = mul nsw i64 %cond.i.i94.i, 11
%sub1.i96.i = sub nsw i64 1, %j
%add2.i97.i = add nsw i64 %sub1.i96.i, 4
%cmp.i8.i98.i = icmp sgt i64 %add2.i97.i, 0
%cond.i11.i102.i = select i1 %cmp.i8.i98.i, i64 %add2.i97.i, i64 0
%mul4.i103.i = mul nsw i64 %cond.i11.i102.i, 11
%add5.i104.i = add nsw i64 %mul.i95.i, %mul4.i103.i
%add3.i = add nsw i64 %add.i, %add5.i104.i
%add.i65.i = add nsw i64 1, %j
%sub.i66.i = sub nsw i64 %add.i65.i, 6
%cmp.i.i67.i = icmp sgt i64 %sub.i66.i, 0
%cond.i.i70.i = select i1 %cmp.i.i67.i, i64 %sub.i66.i, i64 0
%mul.i71.i = mul nsw i64 %cond.i.i70.i, 13
%sub1.i72.i = sub nsw i64 1, %j
%add2.i73.i = add nsw i64 %sub1.i72.i, 6
%cmp.i8.i74.i = icmp sgt i64 %add2.i73.i, 0
%cond.i11.i78.i = select i1 %cmp.i8.i74.i, i64 %add2.i73.i, i64 0
%mul4.i79.i = mul nsw i64 %cond.i11.i78.i, 13
%add5.i80.i = add nsw i64 %mul.i71.i, %mul4.i79.i
%add5.i = add nsw i64 %add3.i, %add5.i80.i
%add.i41.i = add nsw i64 1, %j
%sub.i42.i = sub nsw i64 %add.i41.i, 8
%cmp.i.i43.i = icmp sgt i64 %sub.i42.i, 0
%cond.i.i46.i = select i1 %cmp.i.i43.i, i64 %sub.i42.i, i64 0
%mul.i47.i = mul nsw i64 %cond.i.i46.i, 17
%sub1.i48.i = sub nsw i64 1, %j
%add2.i49.i = add nsw i64 %sub1.i48.i, 8
%cmp.i8.i50.i = icmp sgt i64 %add2.i49.i, 0
%cond.i11.i54.i = select i1 %cmp.i8.i50.i, i64 %add2.i49.i, i64 0
%mul4.i55.i = mul nsw i64 %cond.i11.i54.i, 17
%add5.i56.i = add nsw i64 %mul.i47.i, %mul4.i55.i
%add7.i = add nsw i64 %add5.i, %add5.i56.i
%add.i17.i = add nsw i64 1, %j
%sub.i18.i = sub nsw i64 %add.i17.i, 10
%cmp.i.i19.i = icmp sgt i64 %sub.i18.i, 0
%cond.i.i22.i = select i1 %cmp.i.i19.i, i64 %sub.i18.i, i64 0
%mul.i23.i = mul nsw i64 %cond.i.i22.i, 19
%sub1.i24.i = sub nsw i64 1, %j
%add2.i25.i = add nsw i64 %sub1.i24.i, 10
%cmp.i8.i26.i = icmp sgt i64 %add2.i25.i, 0
%cond.i11.i30.i = select i1 %cmp.i8.i26.i, i64 %add2.i25.i, i64 0
%mul4.i31.i = mul nsw i64 %cond.i11.i30.i, 19
%add5.i32.i = add nsw i64 %mul.i23.i, %mul4.i31.i
%idxprom = add nsw i64 %add7.i, %add5.i32.i
%A_idx = getelementptr inbounds double, double* %A, i64 %idxprom
%val = load double, double* %A_idx
%B_idx = getelementptr inbounds double, double* %B, i64 %j
store double %val, double* %B_idx
br label %inc
inc:
%j.inc = add nuw nsw i64 %j, 1
br label %for
exit:
br label %return
return:
ret void
}With the current Polly, ScopInfo bails out: NOTE: Run time checks for %for---%return could not be created as the number of parameters involved is too high. The SCoP will be dismissed. (yes, the debug message is still misleading) The set the example produces is: [n] -> {
MemRef_A[274] : n >= 8;
MemRef_A[283] : n >= 7;
MemRef_A[292] : n >= 6;
MemRef_A[295] : n >= 9;
MemRef_A[316] : n >= 10;
MemRef_A[325] : n >= 5;
MemRef_A[367] : n >= 4;
MemRef_A[373] : n >= 11;
MemRef_A[i0] : i0 >= 420 and 627 - 69n <= i0 <= 558;
MemRef_A[i0] : 430 <= i0 <= -482 + 76n
}(10 pieces) After simple_hull(), this should be the result: [n] -> {
MemRef_A[i0] : i0 >= 274 and 627 - 69n <= i0 <= 482 + 76n
}which is bounded for each n and simple enough for lexmin/-max to process. @cs15btech11044: Do you have everything to make a test-case for this patch out of it? Comment Actions I think the given test case is sufficient enough for this fix. When I tried to run this test case manually over opt, after applying Set.simple_hull(), it gave exactly the same reduced set as mentioned in the previous comment. I will format this test case with appropriate check statements to ensure correct output is obtained. Also, this diff needs to be updated since I have been working on a version of Polly which was cloned on March 30th. All these changes will be reflected in the next update. Comment Actions Updates in the new diff:
Comment Actions This patch has been quite inactive for some time. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||