This is an archive of the discontinued LLVM Phabricator instance.

[Polly] [ScopInfo] Remove bail out condition in buildMinMaxAccess()
ClosedPublic

Authored by cs15btech11044 on Mar 29 2018, 3:00 PM.

Details

Summary

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

Repository
rL LLVM

Event Timeline

cs15btech11044 created this revision.Mar 29 2018, 3:00 PM

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: 13

Each 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

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()".

Thanks your contribution!

With the infos provided you should be able to fix the assertions.

lib/Analysis/ScopInfo.cpp
2304 ↗(On Diff #140338)

Did you try with affine_hull as well?

2335–2345 ↗(On Diff #140338)

As Eli already mentioned, these lines are indeed the issue. I assume commit r303404 meant to protect the assertion by checking for an error before, but coalescing can already max-out the quote.

I think it is safer to use
assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) && "Assumed at least one output dimension"); instead since even add_constant_si below can trigger the quota. That we'll need to check for the error anyway (And do, at the end of IslMaxOperationsGuard scope)

2377 ↗(On Diff #140338)

The detect_equalities should also have become unnecessary.

3195 ↗(On Diff #140338)

[different issue] buildAliasGroup can also return false if the complexity limit is hit, but only if it passes through we actually invalidate the SCoP?!?

cs15btech11044 marked an inline comment as done.Apr 1 2018, 2:28 AM
cs15btech11044 added inline comments.
lib/Analysis/ScopInfo.cpp
2304 ↗(On Diff #140338)

Yes, I had tried the same patch with simple_hull replaced by affine_hull. But it fails on a larger set of regression tests.
List of failed regression tests:

Failing Tests (149):
    Polly :: CodeGen/OpenMP/floord-as-argument-to-subfunction.ll
    Polly :: CodeGen/stride_detection.ll
    Polly :: DependenceInfo/fine_grain_dep_0.ll
    Polly :: DependenceInfo/generate_may_write_dependence_info.ll
    Polly :: ForwardOpTree/atax.ll
    Polly :: Isl/Ast/alias_simple_1.ll
    Polly :: Isl/Ast/alias_simple_2.ll
    Polly :: Isl/Ast/alias_simple_3.ll
    Polly :: Isl/Ast/aliasing_arrays_with_identical_base.ll
    Polly :: Isl/Ast/aliasing_multiple_alias_groups.ll
    Polly :: Isl/Ast/aliasing_parametric_simple_1.ll
    Polly :: Isl/Ast/aliasing_parametric_simple_2.ll
    Polly :: Isl/CodeGen/MemAccess/create_arrays.ll
    Polly :: Isl/CodeGen/MemAccess/create_arrays_heap.ll
    Polly :: Isl/CodeGen/MemAccess/different_types.ll
    Polly :: Isl/CodeGen/MemAccess/multiple_types.ll
    Polly :: Isl/CodeGen/OpenMP/alias-metadata.ll
    Polly :: Isl/CodeGen/OpenMP/invariant_base_pointer_preloaded_pass_only_needed.ll
    Polly :: Isl/CodeGen/OpenMP/mapped-phi-access.ll
    Polly :: Isl/CodeGen/OpenMP/recomputed-srem.ll
    Polly :: Isl/CodeGen/alias-check-multi-dim.ll
    Polly :: Isl/CodeGen/aliasing_different_base_and_access_type.ll
    Polly :: Isl/CodeGen/aliasing_different_pointer_types.ll
    Polly :: Isl/CodeGen/aliasing_multidimensional_access.ll
    Polly :: Isl/CodeGen/aliasing_parametric_simple_1.ll
    Polly :: Isl/CodeGen/aliasing_parametric_simple_2.ll
    Polly :: Isl/CodeGen/aliasing_struct_element.ll
    Polly :: Isl/CodeGen/annotated_alias_scopes.ll
    Polly :: Isl/CodeGen/exprModDiv.ll
    Polly :: Isl/CodeGen/fortran_array_runtime_size_generation.ll
    Polly :: Isl/CodeGen/inner_scev_sdiv_in_rtc.ll
    Polly :: Isl/CodeGen/inv-load-lnt-crash-wrong-order-3.ll
    Polly :: Isl/CodeGen/invariant_load_base_pointer_conditional_2.ll
    Polly :: Isl/CodeGen/invariant_load_condition.ll
    Polly :: Isl/CodeGen/invariant_load_escaping.ll
    Polly :: Isl/CodeGen/invariant_load_escaping_second_scop.ll
    Polly :: Isl/CodeGen/invariant_load_loop_ub.ll
    Polly :: Isl/CodeGen/invariant_load_scalar_escape_alloca_sharing.ll
    Polly :: Isl/CodeGen/invariant_loads_from_struct_with_different_types_1.ll
    Polly :: Isl/CodeGen/multidim_alias_check.ll
    Polly :: Isl/CodeGen/multiple-types-invariant-load.ll
    Polly :: Isl/CodeGen/no-overflow-tracking.ll
    Polly :: Isl/CodeGen/non-affine-subregion-dominance-reuse.ll
    Polly :: Isl/CodeGen/non-affine-update.ll
    Polly :: Isl/CodeGen/partial_write_in_region.ll
    Polly :: Isl/CodeGen/scev_expansion_in_nonaffine.ll
    Polly :: Isl/CodeGen/stack-overflow-in-load-hoisting.ll
    Polly :: Isl/CodeGen/stmt_split_no_dependence.ll
    Polly :: Isl/CodeGen/test-invalid-operands-for-select-2.ll
    Polly :: Isl/CodeGen/test-invalid-operands-for-select.ll
    Polly :: JSONExporter/ImportArrays/ImportArrays-Mispelled-type.ll
    Polly :: JSONExporter/ImportArrays/ImportArrays-Negative-size.ll
    Polly :: JSONExporter/ImportArrays/ImportArrays-No-name.ll
    Polly :: JSONExporter/ImportArrays/ImportArrays-No-sizes-key.ll
    Polly :: JSONExporter/ImportArrays/ImportArrays-No-type-key.ll
    Polly :: MaximalStaticExpansion/load_after_store_same_statement.ll
    Polly :: MaximalStaticExpansion/read_from_original.ll
    Polly :: MaximalStaticExpansion/too_many_writes.ll
    Polly :: MaximalStaticExpansion/working_deps_between_inners.ll
    Polly :: MaximalStaticExpansion/working_deps_between_inners_phi.ll
    Polly :: MaximalStaticExpansion/working_expansion.ll
    Polly :: MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll
    Polly :: MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll
    Polly :: MaximalStaticExpansion/working_value_expansion.ll
    Polly :: ScheduleOptimizer/ensure-correct-tile-sizes.ll
    Polly :: ScheduleOptimizer/full_partial_tile_separation.ll
    Polly :: ScheduleOptimizer/mat_mul_pattern_data_layout.ll
    Polly :: ScheduleOptimizer/mat_mul_pattern_data_layout_2.ll
    Polly :: ScheduleOptimizer/one-dimensional-band.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts-after-delicm.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_10.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_11.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_12.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_13.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_14.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_2.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_3.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_4.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_5.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_6.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_7.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_8.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_9.ll
    Polly :: ScheduleOptimizer/tile_after_fusion.ll
    Polly :: ScopDetect/indvars.ll
    Polly :: ScopInfo/Alias-0.ll
    Polly :: ScopInfo/Alias-1.ll
    Polly :: ScopInfo/Alias-2.ll
    Polly :: ScopInfo/Alias-3.ll
    Polly :: ScopInfo/Alias-4.ll
    Polly :: ScopInfo/NonAffine/invariant_loads_dependent_in_non_affine_region.ll
    Polly :: ScopInfo/NonAffine/non_affine_loop_condition.ll
    Polly :: ScopInfo/NonAffine/non_affine_region_guaranteed_non-entry.ll
    Polly :: ScopInfo/aliasing_conditional_alias_groups_2.ll
    Polly :: ScopInfo/aliasing_many_arrays_to_compare.ll
    Polly :: ScopInfo/aliasing_many_parameters_not_all_involved.ll
    Polly :: ScopInfo/aliasing_many_read_only_acesses.ll
    Polly :: ScopInfo/aliasing_multiple_alias_groups.ll
    Polly :: ScopInfo/aliasing_with_non_affine_access.ll
    Polly :: ScopInfo/complex-expression.ll
    Polly :: ScopInfo/complex-successor-structure-2.ll
    Polly :: ScopInfo/const_srem_sdiv.ll
    Polly :: ScopInfo/constant_functions_multi_dim.ll
    Polly :: ScopInfo/invariant-loads-leave-read-only-statements.ll
    Polly :: ScopInfo/invariant_load_access_classes_different_base_type.ll
    Polly :: ScopInfo/invariant_load_access_classes_different_base_type_escaping.ll
    Polly :: ScopInfo/invariant_load_access_classes_different_base_type_same_pointer.ll
    Polly :: ScopInfo/invariant_load_access_classes_different_base_type_same_pointer_escaping.ll
    Polly :: ScopInfo/invariant_load_canonicalize_array_baseptrs_4.ll
    Polly :: ScopInfo/invariant_load_canonicalize_array_baseptrs_4b.ll
    Polly :: ScopInfo/invariant_load_canonicalize_array_baseptrs_5.ll
    Polly :: ScopInfo/invariant_load_condition.ll
    Polly :: ScopInfo/invariant_load_dereferenceable.ll
    Polly :: ScopInfo/invariant_load_distinct_parameter_valuations.ll
    Polly :: ScopInfo/invariant_load_loop_ub.ll
    Polly :: ScopInfo/invariant_load_zext_parameter-2.ll
    Polly :: ScopInfo/invariant_load_zext_parameter.ll
    Polly :: ScopInfo/long-compile-time-alias-analysis.ll
    Polly :: ScopInfo/long-sequence-of-error-blocks.ll
    Polly :: ScopInfo/mismatching-array-dimensions.ll
    Polly :: ScopInfo/multidim_fixedsize_different_dimensionality.ll
    Polly :: ScopInfo/multidim_parameter_addrec_product.ll
    Polly :: ScopInfo/multidim_with_bitcast.ll
    Polly :: ScopInfo/multiple-types-access-offset-not-dividable-by-element-size.ll
    Polly :: ScopInfo/multiple-types.ll
    Polly :: ScopInfo/non-precise-inv-load-1.ll
    Polly :: ScopInfo/non-precise-inv-load-2.ll
    Polly :: ScopInfo/non-precise-inv-load-3.ll
    Polly :: ScopInfo/non-precise-inv-load-4.ll
    Polly :: ScopInfo/non-precise-inv-load-6.ll
    Polly :: ScopInfo/non-pure-function-calls-causes-dead-blocks.ll
    Polly :: ScopInfo/non-pure-function-calls.ll
    Polly :: ScopInfo/parameter-constant-division.ll
    Polly :: ScopInfo/partially_invariant_load_2.ll
    Polly :: ScopInfo/remarks.ll
    Polly :: ScopInfo/run-time-check-many-array-disjuncts.ll
    Polly :: ScopInfo/run-time-check-many-parameters.ll
    Polly :: ScopInfo/run-time-check-read-only-arrays.ll
    Polly :: ScopInfo/stmt_split_exit_of_region_stmt.ll
    Polly :: ScopInfo/stmt_split_no_dependence.ll
    Polly :: ScopInfo/stmt_split_on_store.ll
    Polly :: ScopInfo/stmt_split_on_synthesizable.ll
    Polly :: ScopInfo/stmt_split_phi_in_beginning_bb.ll
    Polly :: ScopInfo/stmt_split_phi_in_stmt.ll
    Polly :: ScopInfo/stmt_split_scalar_dependence.ll
    Polly :: ScopInfo/stmt_split_within_loop.ll
    Polly :: ScopInfo/unnamed_stmts.ll
    Polly :: Simplify/gemm.ll

  Expected Passes: 894
  Expected Failures: 13
  Unsupported Tests: 73
  Unexpected Failures: 149

All of them fail on the same assertion statement i.e ScopInfo.cpp:2345

Some more analysis from my side:

  1. Due to the approximation of the of the hull, Set.lexmin_pw_multi_aff() can fail not only because if a quota exceeds, but because the set is unbounded: isl_error_invalid
  1. Code assumes that because there is no isl_error_quota, the code thinks is succeeds, but results in a NULL entry which later code does not expects.
  1. the additional error with affine_hull also occur with simple_hull, just a lot less often.
  1. Some other errors occur, but only leed to the output: IMPLEMENTATION ERROR: Unhandled error state. This phenomenon has already been reported by Eli.
cs15btech11044 added inline comments.Apr 5 2018, 11:30 PM
lib/Analysis/ScopInfo.cpp
2377 ↗(On Diff #140338)

Sure Sir, this will be reflected in the next patch which will be sent soon enough.

Implementing the changes suggested by @Meinersbur
List of failing regression tests:

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
cs15btech11044 added inline comments.Apr 5 2018, 11:48 PM
lib/Analysis/ScopInfo.cpp
2304 ↗(On Diff #141283)

On some analysis of this particular line, it turns out that on the application of simple hull, a bounded set results in its unbounded approximation, which is likely the cause of MinPMA and MaxPMA sets computed as null values. Almost all of the failed regression tests are indirectly caused by this unexpected behaviour.

Meinersbur added inline comments.Apr 6 2018, 12:55 PM
lib/Analysis/ScopInfo.cpp
2304 ↗(On Diff #141283)

Do you have an example for this behavior? If this happens too often or in too important cases, we may need to look for another solution. I would have hoped that this happens less often, or not at all, with affine_hull.

2336–2340 ↗(On Diff #141283)

These are redundant.

2359 ↗(On Diff #141283)

[Nit] unnecessary change

2363 ↗(On Diff #141283)

There should be a

if (!MinPMA || !MaxPMA)
  return isl::stat::error;

here. If any of the two is null, there will be another fail later, so it must never be added to MinMaxAccesses.

(And even MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff) can fail, with the result of nullptr assigned to MaxPMA).

3199–3211 ↗(On Diff #141283)

There are some inconsistencies in how things are handled here, true, but IMHO we can leave it alone for this patch (this is what I meant with "different issue" -- sorry for the confusion)

cs15btech11044 added inline comments.Apr 9 2018, 3:06 AM
lib/Analysis/ScopInfo.cpp
2304 ↗(On Diff #141283)

Yes, there are some examples for this behavior.

For example, in the regression test ScopInfo/invariant_load_zext_parameter-2.ll before applying simple_hull in Line 2304 of ScopInfo.cpp, the set was [p_0, p_1, p_2, p_3, p_4] -> { MemRef_I1[p_2] : p_1 > -p_0; MemRef_I1[p_3 + p_4] : p_1 > -p_0; MemRef_I1[0] } , but after applying the hull operation, it got changed to [p_0, p_1, p_2, p_3, p_4] -> { MemRef_I1[i0] } , whereby the variable i0 does not have any bounds/conditions to it.

Meinersbur added inline comments.Apr 9 2018, 6:49 PM
lib/Analysis/ScopInfo.cpp
2304 ↗(On Diff #141283)

and with affine_hull?

I'd rate all of the test cases as important cases. We should not regress that much. However, we can still improve on the previous mechanism. E.g.

  1. call remove_divs (which overapproximates without changing boundaries)
  2. call polly::simplify (this should coalesce disjuncts, and unlike how it is in trunk, should be done after remove_divs)
  3. check for too many disjuncts. We either abort or try with affine/simple_hull.
cs15btech11044 added inline comments.Apr 10 2018, 4:27 AM
lib/Analysis/ScopInfo.cpp
2306–2308 ↗(On Diff #141283)

I would like to have an opinion on this part of codebase here.

Since the operation of simple_hull tries to reduce the number of disjuncts present in the set. Can we conditionally call simple_hull only when MaxDisjunctsInDomain is triggered?
In other words, I am proposing to replace

if (isl_set_n_basic_set(Set.get()) >= MaxDisjunctsInDomain)
    return isl::stat::error;

with

if (isl_set_n_basic_set(Set.get()) >= MaxDisjunctsInDomain)
    Set = Set.simple_hull();
if (isl_set_n_basic_set(Set.get()) >= MaxDisjunctsInDomain)
    return isl::stat::error;
Meinersbur added inline comments.Apr 11 2018, 1:15 PM
lib/Analysis/ScopInfo.cpp
2306–2308 ↗(On Diff #141283)

This resembles example 3. from by last comment, correct? Sounds like a good idea. Could you update this patch?

The error processing in the remainder of this function still has to updated:

  1. Must handle an error that would otherwise trigger an assertion at line 2355.
  2. Must never add nullptr values to MinMaxAccesses.

Do you know how to do this?

cs15btech11044 set the repository for this revision to rPLO Polly.

Addressing the previous suggestions as well as incorporating some of mine.

PS: None of the regression tests have failed in this case.

Meinersbur added inline comments.Apr 11 2018, 3:07 PM
lib/Analysis/ScopInfo.cpp
2305 ↗(On Diff #142073)

Why an r-value reference?
"simple_set" does not adhere the LLVM policy on naming local variables.
You could also just keep using Set as the code before.

2308 ↗(On Diff #142073)

Consider using RunTimeChecksMaxAccessDisjuncts which the current trunk uses.

2351–2352 ↗(On Diff #142073)

You should decide between one of the following (not a mix of both):

  1. Check for an error and return before reaching the assert
  2. Let the assertion pass in case of MaxPMA being NULL.

Please tell me if you are unsure what to do.

2361–2362 ↗(On Diff #142073)

Thanks.

cs15btech11044 added inline comments.Apr 12 2018, 1:42 AM
lib/Analysis/ScopInfo.cpp
2308 ↗(On Diff #142073)

I do not quite understand why RunTimeChecksMaxAccessDisjuncts needs to be used here.

If I remember correctly, the point of this patch was to remove max-disjuncts bailout in MinMaxAccess so that the computation limit will decide whether the memory access needs to be considered or not.
Then why is it being reintroduced here?

Meinersbur added inline comments.
lib/Analysis/ScopInfo.cpp
2308 ↗(On Diff #142073)

The idea was to remove a reason for a bail-out to happen (which occurred in a hot loop in a SPEC benchmark), if we can avoid it. Part of the reason it triggered was that the code does not coalesce() after remove_divs(). Instead of bailing-out we can apply a rougher approximation than remove_divs(): simple_hull() in this case.

remove max-disjuncts bailout in MinMaxAccess so that the computation limit will decide whether the memory access needs to be considered or not.

This was my idea for it, but according to @grosser we should avoid the additional computation time in lexmin_pw_multi_aff() to wait for the computation limit to trigger when currently we have a bail-out before that computational overhead.

How would you handle the situation?

cs15btech11044 marked an inline comment as done.Apr 13 2018, 10:09 AM
cs15btech11044 added inline comments.
lib/Analysis/ScopInfo.cpp
2351–2352 ↗(On Diff #142073)

I am a bit unsure about how to proceed.

I am thinking of checking MaxPMA and MinPMA before assertion and returning error if either of them are NULL, along with removing these checks from the assertion.

Would that be suitable?

Meinersbur added inline comments.Apr 13 2018, 12:35 PM
lib/Analysis/ScopInfo.cpp
2351–2352 ↗(On Diff #142073)

This is the first suggestion (which is what I think you just described):

MinPMA = Set.lexmin_pw_multi_aff();
MaxPMA = Set.lexmax_pw_multi_aff();

MinPMA = MinPMA.coalesce();
MaxPMA = MaxPMA.coalesce();

// Adjust the last dimension of the maximal access by one as we want to
// enclose the accessed memory region by MinPMA and MaxPMA. The pointer
// we test during code generation might now point after the end of the
// allocated array but we will never dereference it anyway.
if (!MinPMA || !MaxPMA)
  return isl::stat::error;
assert(MaxPMA.dim(isl::dim::out) && "Assumed at least one output dimension");
Pos = MaxPMA.dim(isl::dim::out) - 1;
LastDimAff = MaxPMA.get_pw_aff(Pos);
OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
OneAff = OneAff.add_constant_si(1);
LastDimAff = LastDimAff.add(OneAff);
MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);

if (!MinPMA || !MaxPMA)
  return isl::stat::error;
MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));

return isl::stat::ok;

(Also checking MinPMA before the assertion is not strictly necessary)

This is the second suggestion:

MinPMA = Set.lexmin_pw_multi_aff();
MaxPMA = Set.lexmax_pw_multi_aff();

MinPMA = MinPMA.coalesce();
MaxPMA = MaxPMA.coalesce();

// Adjust the last dimension of the maximal access by one as we want to
// enclose the accessed memory region by MinPMA and MaxPMA. The pointer
// we test during code generation might now point after the end of the
// allocated array but we will never dereference it anyway.
assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) && "Assumed at least one output dimension");
Pos = MaxPMA.dim(isl::dim::out) - 1;
LastDimAff = MaxPMA.get_pw_aff(Pos);
OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
OneAff = OneAff.add_constant_si(1);
LastDimAff = LastDimAff.add(OneAff);
MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);

if (!MinPMA || !MaxPMA)
  return isl::stat::error;
MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));

return isl::stat::ok;

Changes made to this new patch:

  1. Modified variable names according to LLVM coding standards.
  2. Used RunTimeChecksMaxAccessDisjuncts for the initial check.
  3. Modified the assertion according to @Meinersbur's second suggestion.

Thanks for the update. I don't understand why you changed Set to a reference and introduced SimpleSet?

lib/Analysis/ScopInfo.cpp
2303 ↗(On Diff #142522)

Is there a reason to change Set to by-reference?

2312 ↗(On Diff #142522)

Calling remove_divs before simplify could still be useful. It should not affect the ranges we need to check for aliasing.

2317–2318 ↗(On Diff #142522)

IMHO this condition can be removed.

2393 ↗(On Diff #142522)

Why introducing an alias for Set?

lib/Analysis/ScopInfo.cpp
2312 ↗(On Diff #142522)

Okay, I understand. This will be added in the next patch.

cs15btech11044 added inline comments.Apr 16 2018, 1:21 AM
lib/Analysis/ScopInfo.cpp
2303 ↗(On Diff #142522)

As mentioned in another comment, I had some confusion before regarding function arguments as references and as actual values. It's all cleared up now.

I think that this change is unnecessary. Changes will be reflected in the next patch.

2317–2318 ↗(On Diff #142522)

Okay, I agree with this point.

Changes will be reflected in the next patch.

2393 ↗(On Diff #142522)

I had some confusion before regarding function arguments as references and as actual values. It's all cleared up now.

I agree that this introduction of an alias is unnecessary. Changes will be reflected in the next patch.

Updates in this patch:

  1. Removed the unnecessary alias reference of Set in calculateMinMaxAccess
  2. Function signature of buildMinMaxAccess has been changed, removing reference to a set.
  3. Removing MaxDisjunctsInDomain condition
  4. Calling remove_divs() on Set before polly::simplify()

LGTM.

Adding @grosser as reviewer to confirm whether this satisfies his concerns in D41694.

Usually we add a test-case to behaviour-changing commits. However, IMHO this is more a cleanup-up and a test-case difficult to produce.

Meinersbur accepted this revision.Apr 16 2018, 2:43 PM
This revision is now accepted and ready to land.Apr 16 2018, 2:43 PM
cs15btech11044 set the repository for this revision to rPLO Polly.Apr 17 2018, 10:58 AM

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?

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.

cs15btech11044 edited the summary of this revision. (Show Details)

Updates in the new diff:

  1. Attached a test case run-time-check-many-piecewise-aliasing.ll with appropriate checks.
  2. Incorporating these changes on the latest version of Polly present, thereby updating the diff.
  3. Summary of the changes in this patch

This patch has been quite inactive for some time.
Are there any issues with this diff which are preventing it from getting committed to Polly codebase?

I'm waiting for the ok from Tobias.

grosser accepted this revision.May 9 2018, 2:25 AM

That's fine with me.

@cs15btech11044 is it ok if I commit this on your behalf?

Yes, it is fine.

This revision was automatically updated to reflect the committed changes.

Congratulations for your first contribution!