[Polly][WIP]JSCoP Importer: support for multi-valued schedules

[Mike_Jongen]

Summary

This patch adds support for multi-valued schedules when using the JSCoP-Importer.

Before, when non-single valued schedules are imported, Polly would crash.
This prevented the use of recomputation/recalculation in a schedule, which could be beneficial for improving data locality.

This patch adjusts the Scops and the imported schedules of schedules which perform certain statements multiple times.
This is done by copying the statements which are executed multiple times, and adjusting the schedule accordingly.
The new schedule is again single valued, and can be used by Polly.

This patch is work in progress.
Known bugs/errors:
isValidSchedule does not recognize the schedule as valid

[Meinersbur]

Thanks for the patch. The lexmin/subtract cycle look ok. Could you add a test case which I can try out and see what kind of input you generate and what you expect as output?

I added some remarks including some about the coding style we use.

include/polly/ScopInfo.h

1115

We usually add dots add the end of comments/sentences.

2092

LLVM coding style says variables, including function parameters, should start with a capital letter.

lib/Analysis/ScopInfo.cpp

1579

Cast (std::string) is unnecessary.

1581

You must also change the user part of the isl_id.

4454

Maybe call it copyScopStmt?

lib/Exchange/JSONExporter.cpp

304

In LLVM's coding style, function names start with a lower case letter.

348

There is an overloaded operator<<, you can push it directly to OS.

364

isl_union_map_lexmin can fail if the input is not lower-bounded. Could you add a check/assertion?

It might be easier to iterate over the Stmts first such that we get a isl_map and call isl_map_lexmin/isl_map_subtract on it. An advantage is that one Stmt is handles at a time, helping to diagnose which of those is causes a problem.

367–371

Could you consider using isl::union_map::foreach_map? This allows using C++11-style closures with less boilerplate code.

374

Sequential lexmin+subtract is not guaranteed to eventually end up in an empty set. Could you add a cut-off maximum number of iterations?

382

Consider using assert for such checks.

398

There is isl_union_map_dump(ScheduleData.NewUmap).

424

Does this function properly handle non-right-unique schedules?

442

Don't print errors during normal operation. Use

DEBUG(dbgs() << "JScop file contains a schedule that is not single valued\n");

for messages that helps you during development.

[Mike_Jongen]

In D33362#760795, @Meinersbur wrote:

Thanks for the patch. The lexmin/subtract cycle look ok. Could you add a test case which I can try out and see what kind of input you generate and what you expect as output?

I added some remarks including some about the coding style we use.

Thank you for the comments. I fixed most remarks.
I found an error in the new schedule. After I fix this I will add a test case.

Comment at: lib/Exchange/JSONExporter.cpp:364

isl_union_map_lexmin can fail if the input is not lower-bounded. Could you add a check/assertion?

Not sure if I understand. How can I check this, is there a function for this?

It might be easier to iterate over the Stmts first such that we get a isl_map and call isl_map_lexmin/isl_map_subtract on it. An advantage is that one Stmt is handles at a time, helping to diagnose which of those is causes a problem.

Good Idea, I will have a look at it.

Comment at: lib/Exchange/JSONExporter.cpp:367-371

Could you consider using isl::union_map::foreach_map? This allows using C++11-style closures with less boilerplate code.

I will have a look at it. I used foreach_set because this was also used by the function which checks if a map is single valued, but foreach_map might be better here indeed.

Comment at: lib/Exchange/JSONExporter.cpp:433

Does this function properly handle non-right-unique schedules?

It does not at the moment. I use disable-legality to go pass this check, I will have a look at it later.

[Mike_Jongen]

Rewritten most of the code using ideas from @Meinersbur.
Fixed the new schedule.
Copied Scops now have the correct data accesses

[Meinersbur]

In D33362#761968, @Mike_Jongen wrote:

In D33362#760795, @Meinersbur wrote:

Comment at: lib/Exchange/JSONExporter.cpp:364

isl_union_map_lexmin can fail if the input is not lower-bounded. Could you add a check/assertion?

Not sure if I understand. How can I check this, is there a function for this?

Depending on the on_error setting, isl_union_map_lexmin prints a warning, abort()s, and/or returns nullptr. You can e.g. assert on that the result value is not null.

You can check in advance using isl_basic_map_image_is_bounded. However, recently there was a discussion in isl-dev that this is not a sufficient condition. It should still suffice for us because if the map is not bounded, the lexmin/subtract cycle will loop endlessly, so such an assert would warn about this.

Run ninja/make polly-update-format to get the whitespace correct.

Looking forward to see a test case. One for verifying the behavior when passing an unbounded map (e.g. { Stmt[i] -> [j] : j >= i }) would be great as well.

[Mike_Jongen]

-Added detection for unbounded maps. These unbounded maps are now not adjusted by this patch, as this would require infinite copies of statements.

-Added 2 tests, one to test if the schedule is adjusted correctly and the correct scops are copied, and one to test if unbounded maps are detected and not adjusted by this patch.

[Mike_Jongen]

changed the order of importAccesses and importSchedule. Performing importSchedule before importAccesses gives an error, as importAccesses tries to import the accesses of scops which are not defined in the Jscop file. By changing the order this problem is avoided. I could not detect any problem with changing this order, but if there is a reason why the order was different, i can look for another (more complex) solution.

I also changed the domain of the newly created scops. These are not always the same as the old scops.

There is a problem with setting the schedule of the new scops. When using getschedule on a new schedule (after the schedule is set), no schedule is found. The problem is caused by:

Schedule = isl_union_map_intersect_domain(Schedule, isl_union_set_from_set(isl_set_copy(Domain)));

Schedule is empty when this is used on a copied statement (but not when used on a not copied statement). if we print the domain and the schedule, we can see that the domain is present is the schedule:

Domain:
{ Stmt_for_end_copy_no_2[i0] : 2 <= i0 <= 93 }

Schedule:
{ Stmt_for_inc29[i0, i1] -> [i0, 1, 0, 1, i1]; Stmt_for_cond1_preheader_copy_no_1[i0] -> [-1 + i0, 0, i0, 0, 0] : 2 <= i0 <= 94; Stmt_for_cond1_preheader_copy_no_1[i0 = 1] -> [1, 0, 1, 0, 0]; Stmt_for_cond17_preheader[i0] -> [i0, 1, 0, 0, 0]; Stmt_for_cond1_preheader_copy_no_2[i0] -> [i0, 0, i0, 0, 0] : 2 <= i0 <= 93; Stmt_for_inc[i0, i1] -> [0, 0, i0, 1, i1] : 0 <= i0 <= 1; Stmt_for_inc[i0, i1] -> [-2 + i0, 0, i0, 1, i1] : 2 <= i0 <= 95; Stmt_for_inc_copy_no_1[i0, i1] -> [-1 + i0, 0, i0, 1, i1] : 2 <= i0 <= 94; Stmt_for_inc_copy_no_1[i0 = 1, i1] -> [1, 0, 1, 1, i1]; Stmt_for_end31[i0] -> [i0, 1, 0, 2, 0]; Stmt_for_end_copy_no_1[i0] -> [-1 + i0, 0, i0, 2, 0] : 2 <= i0 <= 94; Stmt_for_end_copy_no_1[i0 = 1] -> [1, 0, 1, 2, 0]; Stmt_for_inc_copy_no_2[i0, i1] -> [i0, 0, i0, 1, i1] : 2 <= i0 <= 93; Stmt_for_end[i0] -> [0, 0, i0, 2, 0] : 0 <= i0 <= 1; Stmt_for_end[i0] -> [-2 + i0, 0, i0, 2, 0] : 2 <= i0 <= 95; Stmt_for_cond1_preheader[i0] -> [0, 0, i0, 0, 0] : 0 <= i0 <= 1; Stmt_for_cond1_preheader[i0] -> [-2 + i0, 0, i0, 0, 0] : 2 <= i0 <= 95; Stmt_for_end_copy_no_2[i0] -> [i0, 0, i0, 2, 0] : 2 <= i0 <= 93 }

Is there another variable in the domain or schedule that might be not set or incorrectly set, such that it can cause the intersect to fail? Or is there a way to check why the intersect fails?

[Meinersbur]

I currently cannot apply you diff, I get errors:

$ arc patch D33362
Checking patch test/ScopDetect/recomputation_unbound.ll...
error: test/ScopDetect/recomputation_unbound.ll: does not exist in index
Checking patch test/ScopDetect/recomputation.ll...
error: test/ScopDetect/recomputation.ll: does not exist in index
Checking patch test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.recompute...
error: test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.recompute: does not exist in index
Checking patch test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.notbound...
error: test/ScopDetect/double_convolution___%for.cond1.preheader---%for.end37.jscop.notbound: does not exist in index
Checking patch lib/Exchange/JSONExporter.cpp...
Hunk #3 succeeded at 326 (offset 37 lines).
Hunk #4 succeeded at 521 (offset 71 lines).
Hunk #5 succeeded at 875 (offset 139 lines).
Checking patch lib/Analysis/ScopInfo.cpp...
Hunk #1 succeeded at 1643 (offset 70 lines).
error: while searching for:
  return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
}

void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop) {
  assert(BB && "Unexpected nullptr!");
  Stmts.emplace_back(*this, *BB, SurroundingLoop);

error: patch failed: lib/Analysis/ScopInfo.cpp:4441
Checking patch include/polly/ScopInfo.h...
error: while searching for:
  ScopStmt(const ScopStmt &) = delete;
  const ScopStmt &operator=(const ScopStmt &) = delete;

  /// Create the ScopStmt from a BasicBlock.
  ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop);


error: patch failed: include/polly/ScopInfo.h:1112
Hunk #2 succeeded at 2196 (offset 108 lines).
Applied patch lib/Exchange/JSONExporter.cpp cleanly.
Applying patch lib/Analysis/ScopInfo.cpp with 1 reject...
Hunk #1 applied cleanly.
Rejected hunk #2.
Applying patch include/polly/ScopInfo.h with 1 reject...
Rejected hunk #1.
Hunk #2 applied cleanly.

Can you update the patch? It also seems your new files are not marked as being created. What are you using to create the diff?

In D33362#770414, @Mike_Jongen wrote:

There is a problem with setting the schedule of the new scops. When using getschedule on a new schedule (after the schedule is set), no schedule is found. The problem is caused by:

Schedule = isl_union_map_intersect_domain(Schedule, isl_union_set_from_set(isl_set_copy(Domain)));

Schedule is empty when this is used on a copied statement (but not when used on a not copied statement). if we print the domain and the schedule, we can see that the domain is present is the schedule:

This could mean that Domain is something different than you expect. What should it be? The domain of the original statement or new one?

Domain:
{ Stmt_for_end_copy_no_2[i0] : 2 <= i0 <= 93 }

Schedule:
{ Stmt_for_inc29[i0, i1] -> [i0, 1, 0, 1, i1]; Stmt_for_cond1_preheader_copy_no_1[i0] -> [-1 + i0, 0, i0, 0, 0] : 2 <= i0 <= 94; Stmt_for_cond1_preheader_copy_no_1[i0 = 1] -> [1, 0, 1, 0, 0]; Stmt_for_cond17_preheader[i0] -> [i0, 1, 0, 0, 0]; Stmt_for_cond1_preheader_copy_no_2[i0] -> [i0, 0, i0, 0, 0] : 2 <= i0 <= 93; Stmt_for_inc[i0, i1] -> [0, 0, i0, 1, i1] : 0 <= i0 <= 1; Stmt_for_inc[i0, i1] -> [-2 + i0, 0, i0, 1, i1] : 2 <= i0 <= 95; Stmt_for_inc_copy_no_1[i0, i1] -> [-1 + i0, 0, i0, 1, i1] : 2 <= i0 <= 94; Stmt_for_inc_copy_no_1[i0 = 1, i1] -> [1, 0, 1, 1, i1]; Stmt_for_end31[i0] -> [i0, 1, 0, 2, 0]; Stmt_for_end_copy_no_1[i0] -> [-1 + i0, 0, i0, 2, 0] : 2 <= i0 <= 94; Stmt_for_end_copy_no_1[i0 = 1] -> [1, 0, 1, 2, 0]; Stmt_for_inc_copy_no_2[i0, i1] -> [i0, 0, i0, 1, i1] : 2 <= i0 <= 93; Stmt_for_end[i0] -> [0, 0, i0, 2, 0] : 0 <= i0 <= 1; Stmt_for_end[i0] -> [-2 + i0, 0, i0, 2, 0] : 2 <= i0 <= 95; Stmt_for_cond1_preheader[i0] -> [0, 0, i0, 0, 0] : 0 <= i0 <= 1; Stmt_for_cond1_preheader[i0] -> [-2 + i0, 0, i0, 0, 0] : 2 <= i0 <= 95; Stmt_for_end_copy_no_2[i0] -> [i0, 0, i0, 2, 0] : 2 <= i0 <= 93 }

Is there another variable in the domain or schedule that might be not set or incorrectly set, such that it can cause the intersect to fail? Or is there a way to check why the intersect fails?

That looks like isl_union_map_intersect_domain should return something non-empty. There is the possibility that the user-pointer of an isl_id is different in Domain and Schedule (E.g. having the new name, but the user-pointer referring to the original polly::ScopStmt instance).

I would like to debug this, but as mentionend I cannot apply the patch.

test/ScopDetect/recomputation_unbound.ll

1 ↗

(On Diff #101055)

Try to avoid checking lines in stdout (-analyze) and stderr (-debug) in the same output, their interleaving order is undefined.

[Mike_Jongen]

Can you update the patch? It also seems your new files are not marked as being created. What are you using to create the diff?

I use "git diff" for the creation of the diff. I used "git add -N" for adding the new files.

Also, I will update to the current version of polly for the next version, I hope that will solve the errors.

[Mike_Jongen]

I have some difficulty updating the patch to the current version of polly (see this)
This version works for the polly version of the 24th of May:
llvm: commit 133fa95ca7019682c74d1c40f93d68014827a943
clang: commit 03e95d2ffb90719219513cabb351bbd88b2ee6d2
Polly: commit 577440293cadb977f910690b8ae0eb73372cde0a

The error was indeed the isl_id of the schedule. This is now fixed (the schedule and domain of the scop now have the same id).

[Mike_Jongen]

Updated to the current version of Polly.
Please let me know if there are still problems applying the patch

[Mike_Jongen]

When generating an AST of the new scop, I get an "unbounded optimum" error.

This is the error I get:

/home/s113026/llvm/tools/polly/lib/External/isl/isl_tab_pip.c:706: unbounded optimum
#0 0x00007f642f3a810d llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/s113026/llvm/lib/Support/Unix/Signals.inc:398:0
#1 0x00007f642f3a819e PrintStackTraceSignalHandler(void*) /home/s113026/llvm/lib/Support/Unix/Signals.inc:462:0
#2 0x00007f642f3a65e4 llvm::sys::RunSignalHandlers() /home/s113026/llvm/lib/Support/Signals.cpp:49:0
#3 0x00007f642f3a7aa5 SignalHandler(int) /home/s113026/llvm/lib/Support/Unix/Signals.inc:252:0
#4 0x00007f642d6a2cb0 (/lib/x86_64-linux-gnu/libc.so.6+0x36cb0)
#5 0x00007f642d6a2c37 gsignal /build/eglibc-SvCtMH/eglibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#6 0x00007f642d6a6028 abort /build/eglibc-SvCtMH/eglibc-2.19/stdlib/abort.c:91:0
#7 0x00007f642aff0980 isl_handle_error /home/s113026/llvm/tools/polly/lib/External/isl/isl_ctx.c:101:0
#8 0x00007f642b0b846d sol_add /home/s113026/llvm/tools/polly/lib/External/isl/isl_tab_pip.c:705:0
#9 0x00007f642b0c0c5f find_solutions /home/s113026/llvm/tools/polly/lib/External/isl/isl_tab_pip.c:4114:0
#10 0x00007f642b0c100f find_solutions_main /home/s113026/llvm/tools/polly/lib/External/isl/isl_tab_pip.c:4216:0
#11 0x00007f642b0c150f basic_map_partial_lexopt_base_sol /home/s113026/llvm/tools/polly/lib/External/isl/isl_tab_pip.c:4349:0
#12 0x00007f642b0c4363 basic_map_partial_lexopt_base_pw_multi_aff /home/s113026/llvm/tools/polly/lib/External/isl/isl_tab_pip.c:5580:0
#13 0x00007f642b0c5083 basic_map_partial_lexopt_pw_multi_aff /home/s113026/llvm/tools/polly/lib/External/isl/isl_tab_lexopt_templ.c:159:0
#14 0x00007f642b0c5216 isl_tab_basic_map_partial_lexopt_pw_multi_aff /home/s113026/llvm/tools/polly/lib/External/isl/isl_tab_lexopt_templ.c:225:0
#15 0x00007f642b02b43a isl_basic_map_partial_lexopt_pw_multi_aff /home/s113026/llvm/tools/polly/lib/External/isl/isl_map_lexopt_templ.c:37:0
#16 0x00007f642b02b538 basic_map_partial_lexopt_pw_multi_aff /home/s113026/llvm/tools/polly/lib/External/isl/isl_map_lexopt_templ.c:95:0
#17 0x00007f642b02b9e0 isl_map_partial_lexopt_aligned_pw_multi_aff /home/s113026/llvm/tools/polly/lib/External/isl/isl_map.c:6644:0
#18 0x00007f642b02b8b5 isl_map_lexopt_pw_multi_aff /home/s113026/llvm/tools/polly/lib/External/isl/isl_map_lexopt_templ.c:209:0
#19 0x00007f642b02b8d4 isl_map_lexmin_pw_multi_aff /home/s113026/llvm/tools/polly/lib/External/isl/isl_map_lexopt_templ.c:214:0
#20 0x00007f642afca960 exact_bound /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:475:0
#21 0x00007f642afcabc6 lower_bounds /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:588:0
#22 0x00007f642afcb9b1 refine_generic_bounds /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1179:0
#23 0x00007f642afcbcb8 refine_generic_split /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1288:0
#24 0x00007f642afcbd16 refine_generic /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1313:0
#25 0x00007f642afcc1ef create_node_scaled /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1521:0
#26 0x00007f642afcc4e8 create_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1677:0
#27 0x00007f642afcc9ae add_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1812:0
#28 0x00007f642afcd083 generate_sorted_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2039:0
#29 0x00007f642afcd2d9 generate_parallel_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2153:0
#30 0x00007f642afcef0c generate_shifted_component_tree_base /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3330:0
#31 0x00007f642afcf45b generate_shifted_component_tree /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3552:0
#32 0x00007f642afcf81c generate_shifted_component /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3616:0
#33 0x00007f642afd14cc generate_next_level /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4763:0
#34 0x00007f642afcc07f create_node_scaled /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1495:0
#35 0x00007f642afcc4e8 create_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1677:0
#36 0x00007f642afcc9ae add_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1812:0
#37 0x00007f642afcd083 generate_sorted_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2039:0
#38 0x00007f642afcd2d9 generate_parallel_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2153:0
#39 0x00007f642afcef0c generate_shifted_component_tree_base /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3330:0
#40 0x00007f642afcf45b generate_shifted_component_tree /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3552:0
#41 0x00007f642afcf81c generate_shifted_component /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3616:0
#42 0x00007f642afd14cc generate_next_level /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4763:0
#43 0x00007f642afcc07f create_node_scaled /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1495:0
#44 0x00007f642afcc4e8 create_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1677:0
#45 0x00007f642afcc9ae add_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1812:0
#46 0x00007f642afcd083 generate_sorted_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2039:0
#47 0x00007f642afcd2d9 generate_parallel_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2153:0
#48 0x00007f642afcef0c generate_shifted_component_tree_base /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3330:0
#49 0x00007f642afcf45b generate_shifted_component_tree /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3552:0
#50 0x00007f642afcf81c generate_shifted_component /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3616:0
#51 0x00007f642afd14cc generate_next_level /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4763:0
#52 0x00007f642afcc07f create_node_scaled /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1495:0
#53 0x00007f642afcc4e8 create_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1677:0
#54 0x00007f642afcc9ae add_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1812:0
#55 0x00007f642afcd083 generate_sorted_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2039:0
#56 0x00007f642afcd2d9 generate_parallel_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2153:0
#57 0x00007f642afcef0c generate_shifted_component_tree_base /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3330:0
#58 0x00007f642afcf45b generate_shifted_component_tree /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3552:0
#59 0x00007f642afcf81c generate_shifted_component /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3616:0
#60 0x00007f642afcf928 generate_shifted_component_from_list /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3662:0
#61 0x00007f642afd0282 generate_component /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4116:0
#62 0x00007f642afd132d generate_components /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4707:0
#63 0x00007f642afd14e1 generate_next_level /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4765:0
#64 0x00007f642afcc07f create_node_scaled /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1495:0
#65 0x00007f642afcc4e8 create_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1677:0
#66 0x00007f642afcc9ae add_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:1812:0
#67 0x00007f642afcd083 generate_sorted_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2039:0
#68 0x00007f642afcd2d9 generate_parallel_domains /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:2153:0
#69 0x00007f642afcef0c generate_shifted_component_tree_base /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3330:0
#70 0x00007f642afcf45b generate_shifted_component_tree /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3552:0
#71 0x00007f642afcf81c generate_shifted_component /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3616:0
#72 0x00007f642afcf928 generate_shifted_component_from_list /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:3662:0
#73 0x00007f642afd059d generate_component /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4174:0
#74 0x00007f642afd132d generate_components /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4707:0
#75 0x00007f642afd14e1 generate_next_level /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:4765:0
#76 0x00007f642afd1c68 build_ast_from_band /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:5111:0
#77 0x00007f642afd29a4 build_ast_from_schedule_node /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:5604:0
#78 0x00007f642afd2b34 build_ast_from_child /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:5651:0
#79 0x00007f642afd2c92 build_ast_from_domain /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:5705:0
#80 0x00007f642afd2dae isl_ast_build_node_from_schedule /home/s113026/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:5746:0
#81 0x00007f6432866611 polly::IslAst::init(polly::Dependences const&) /home/s113026/llvm/tools/polly/lib/CodeGen/IslAst.cpp:446:0
#82 0x00007f6432866662 polly::IslAst::create(polly::Scop&, polly::Dependences const&) /home/s113026/llvm/tools/polly/lib/CodeGen/IslAst.cpp:454:0
#83 0x00007f64328675e0 polly::IslAstInfo::IslAstInfo(polly::Scop&, polly::Dependences const&) /home/s113026/llvm/tools/polly/include/polly/CodeGen/IslAst.h:125:0
#84 0x00007f6432866f2a polly::IslAstInfoWrapperPass::runOnScop(polly::Scop&) /home/s113026/llvm/tools/polly/lib/CodeGen/IslAst.cpp:630:0
#85 0x00007f643283effe polly::ScopPass::runOnRegion(llvm::Region*, llvm::RGPassManager&) /home/s113026/llvm/tools/polly/lib/Analysis/ScopPass.cpp:29:0
#86 0x00007f6431ebb9c2 llvm::RGPassManager::runOnFunction(llvm::Function&) /home/s113026/llvm/lib/Analysis/RegionPass.cpp:98:0
#87 0x00007f6431337f10 llvm::FPPassManager::runOnFunction(llvm::Function&) /home/s113026/llvm/lib/IR/LegacyPassManager.cpp:1519:0
#88 0x00007f64313380a3 llvm::FPPassManager::runOnModule(llvm::Module&) /home/s113026/llvm/lib/IR/LegacyPassManager.cpp:1540:0
#89 0x00007f643133843e (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/s113026/llvm/lib/IR/LegacyPassManager.cpp:1596:0
#90 0x00007f6431338b8e llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/s113026/llvm/lib/IR/LegacyPassManager.cpp:1699:0
#91 0x00007f6431338dcf llvm::legacy::PassManager::run(llvm::Module&) /home/s113026/llvm/lib/IR/LegacyPassManager.cpp:1731:0
#92 0x0000000000484f1c (opt+0x484f1c)
#93 0x00007f642d68df45 __libc_start_main /build/eglibc-SvCtMH/eglibc-2.19/csu/libc-start.c:321:0
#94 0x00000000004688d9 (opt+0x4688d9)
Stack dump:
0. Program arguments: opt double_convolution_1d_fixed.preopt.ll -basicaa -polly-import-jscop -polly-import-jscop-postfix=fused2 -polly-ast -analyze -disable-polly-legality -polly-process-unprofitable

1. Running pass 'Function Pass Manager' on module 'double_convolution_1d_fixed.preopt.ll'.
2. Running pass 'Region Pass Manager' on function '@double_convolution'
3. Running pass 'Polly - Generate an AST from the SCoP (isl)' on basic block '%for.cond1.preheader'

Aborted

I am not sure what exactly causes this error. Are there some limitations on the schedule that might not hold for the new schedule, which might cause this error? Or are there other common mistakes that can cause this error?

The error can be reproduced by using the tests and adding -polly-process-unprofitable.

[Mike_Jongen]

Complete working version.
tested with commit 91e4e0e117198cfcb5fc0cb218cf381c20e13e78 (Mon Jun 19 17:44:02 2017).
I will soon check if the patch still works with the current version.

-fixed the memory accesses of the copied statements
-fixed the domain of the copied statements
-after the scop is adjusted, the dependences are recomputed
-changed the test cases, now they are more easily understandable and the related Jscop files perform the correct transformations

[Meinersbur]

Sorry for my absence, I was too busy with other stuff. If you don't get a response within a week or so, you can write a new comment "ping" so we don't forget.

In D33362#775904, @Mike_Jongen wrote:

Can you update the patch? It also seems your new files are not marked as being created. What are you using to create the diff?

I use "git diff" for the creation of the diff. I used "git add -N" for adding the new files.

With git add -N, make sure that the diff is against a revision before you executed that command. For instance, git diff HEAD.

I'll wait to do a more thorough review when you rebased to the latest Polly trunk. E.g. getAccessRelation() changed to an C++ object. Use getAccessRelation().release() to get the C struct as before or use the C++ object itself (e.g. NewAccessRel.set_tuple_id(...))

lib/Analysis/ScopInfo.cpp

1590–1591

Setting the tuple id will overwrite the change of the tuple name the line before.

isl_map_set_tuple_name is nothing more than isl_map_set_tuple_id with an isl_id of that name.

lib/Exchange/JSONExporter.cpp

416

This function can be static

[Mike_Jongen]

Updated to current polly version.

Changed the setup slightly. No longer is a copy added for every execution time.
Now it adds a dimension to the scopstmt, and uses this dimension for the extra executions.
Works simular to the previous version, but makes the scops much clearer.

The scops also perform a collectSurroundingLoops. The code generator would generate an error without this.

After code generation, some memory accesses use the wrong iterator, and use the new dimension as variable.

for example we have a statement with an access:
Stmt1[i0] -> MemRef0[i0]
if the statement is executed multiple times, the access changes to
Stmt1[i0, i1] -> MemRef0[i0]
How does the code generator decide to which variable i0 of MemRef0 refers to?
The logical answer would be i0, but I have seen generated code where it used i1.
How does the code generator link these variables?

[Mike_Jongen]

Fixed the issue of the memory accesses by using -polly-codegen-generate-expressions
I would like to include the functionality of this option to the patch, but I am not yet sure how to do this.

It now does generate the correct working code, as long as -polly-codegen-generate-expressions is used when generating code.

[Meinersbur]

Did you add files with git add -N? I cannot apply the patch. Please make the diff against origin/master (or use arcanist).

In D33362#834967, @Mike_Jongen wrote:

Fixed the issue of the memory accesses by using -polly-codegen-generate-expressions
I would like to include the functionality of this option to the patch, but I am not yet sure how to do this.

It now does generate the correct working code, as long as -polly-codegen-generate-expressions is used when generating code.

Codegen decides based on hasNewAccessRelation() whether to generate new index expressions, otherwise it tries to reuse the old one (by copying the instruction from the original code).
If it is necessary for this situation to always generate new expression, try calling (setNewAccessRelation(getLatestAccessRelation())).

However, it would be preferable if reusing old instructions would be possible, since it is the only way to handle accesses with non-affine indices.

I will have a look when I can apply the patch.

lib/Exchange/JSONExporter.cpp

292

[Style] Can you use doxygen-style comments (triple slash ///)?

293

[Style] Can you make the function (and the following if possible) static?

312

[Suggestion] Could you add a doxygen-style describing the function?

316

[Serious] Asserts are removed from NDEBUG builds. Try

isl::map LexMin= MapToAdd.lexmin();
assert(LexMin && "Map is not lower-bounded!");

341

[Serious] See above.

include/polly/ScopInfo.h

 ///
 /// It is further described by its iteration domain, its schedule and its data
 /// accesses.
 /// At the moment every statement represents a single basic block of LLVM-IR.
 class ScopStmt {
 public:
   ScopStmt(const ScopStmt &) = delete;
   const ScopStmt &operator=(const ScopStmt &) = delete;
   
+  /// Create the ScopStmt from another ScopStmt.
+  ScopStmt(ScopStmt *Original, int CopyNo);
+
   /// Create the ScopStmt from a BasicBlock.
   ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop);
 
   /// Create an overapproximating ScopStmt for the region @p R.
   ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop);
 
   /// Create a copy statement.
   ///

 public:
   ~Scop();
 
   /// Get the count of copy statements added to this Scop.
   ///
   /// @return The count of copy statements added to this Scop.
   unsigned getCopyStmtsNum() { return CopyStmtsNum; }
 
+  /// Create a new SCoP statement for @p ScopStmt.
+  void copyScopStmt(ScopStmt *NewStmt, int CopyNo);
+    
   /// Create a new copy statement.
   ///
   /// A new statement will be created and added to the statement vector.
   ///
   /// @param Stmt       The parent statement.
   /// @param SourceRel  The source location.
   /// @param TargetRel  The target location.
   /// @param Domain     The original domain under which copy statement whould

lib/Analysis/ScopInfo.cpp

 void ScopStmt::collectSurroundingLoops() {
   for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) {
     isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u);
     NestLoops.push_back(static_cast<Loop *>(isl_id_get_user(DimId)));
     isl_id_free(DimId);
   }
 }
 
+ScopStmt::ScopStmt(ScopStmt *Original, int CopyNo)
+  : Parent(*(Original->getParent())), InvalidDomain(nullptr), Domain(nullptr), BB(Original->getBasicBlock()), 
+  R(Original->getRegion()), Build(nullptr), SurroundingLoop(Original->getSurroundingLoop()){
+  BaseName = getIslCompatibleName(Original->getBaseName(), "_copy_no_", std::to_string(CopyNo));
+  Domain = Original->getDomain();
+  Domain = isl_set_set_tuple_name(Domain, BaseName.c_str());
+  isl_id *Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
+  Domain = isl_set_set_tuple_id(Domain, Id);
+}
+
 ScopStmt::ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(nullptr),
       R(&R), Build(nullptr), SurroundingLoop(SurroundingLoop) {
 
   BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), "");
 }
 
 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
       R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop) {
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
 }
 
mapToDimension(__isl_take isl_union_set *USet, int N) {
   (void)Res;
 
   assert(Res == isl_stat_ok);
 
   isl_union_set_free(USet);
   return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
 }
 
+void Scop::copyScopStmt(ScopStmt *NewStmt, int CopyNo) {
+  assert(NewStmt && "Unexpected nullptr!");
+  Stmts.emplace_back(NewStmt, CopyNo);
+}
+
 void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop) {
   assert(BB && "Unexpected nullptr!");
   Stmts.emplace_back(*this, *BB, SurroundingLoop);
   auto *Stmt = &Stmts.back();
   StmtMap[BB] = Stmt;
 }
 
 void Scop::addScopStmt(Region *R, Loop *SurroundingLoop) {

lib/Exchange/JSONExporter.cpp

 //===----------------------------------------------------------------------===//
 
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
 #include "polly/Support/ScopLocation.h"
+#include "polly/Support/GICHelper.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Support/raw_ostream.h"
 #include "isl/constraint.h"
 #include "isl/map.h"
 #include "isl/printer.h"
 #include "isl/set.h"
 #include "isl/union_map.h"
+#include "isl/union_set.h"
 #include "json/reader.h"
 #include "json/writer.h"
 #include <memory>
 #include <string>
 #include <system_error>
 
 using namespace llvm;
 using namespace polly;
for (unsigned i = 0; i < isl_set_dim(OldContext, isl_dim_param); i++) {
     NewContext = isl_set_set_dim_id(NewContext, isl_dim_param, i, Id);
   }
 
   isl_set_free(OldContext);
   S.setContext(NewContext);
   return true;
 }
 
+struct schedule_info{
+  isl_union_map *OriginalUmap;
+  isl_union_map *NewUmap;
+  int CopyNo;
+};
+
+struct print_info {
+  Scop *S;
+  int CopyNo;
+};
+
+// Adds a copy of the map corresponding to the set to the user->NewMap.
+static isl_stat copyScheduleStatements(__isl_take isl_set *set, void *user){
+  struct schedule_info *data = (schedule_info*) user;
+  isl_union_map *umap;
+  isl_set *range, *domain;
+  isl_map *NewMap;
+  std::string name;
+
+  umap = isl_union_map_copy(data->OriginalUmap);
+  umap = isl_union_map_intersect_domain(umap,
+          isl_union_set_from_set(isl_set_copy(set)));
+
+  range = isl_set_from_union_set(isl_union_map_range(umap));
+  name = getIslCompatibleName((std::string) isl_set_get_tuple_name(set), "_copy_no_", std::to_string(data->CopyNo));
+  domain = isl_set_set_tuple_name(set, name.c_str());
+  NewMap = isl_map_from_domain_and_range(domain, range);
+  data->NewUmap = isl_union_map_add_map(data->NewUmap, NewMap);
+  return isl_stat_ok;
+}
+
+// adds a copy to the SCoP for every ScopStmt corresponding to the set.
+static isl_stat copyScopStatements(__isl_take isl_set *set, void *user){
+  struct print_info *data = (print_info*) user;
+  isl_set *scopset;
+  ScopStmt *NewStmt;
+
+  for(ScopStmt &Stmt : *(data->S)) {
+  scopset = isl_map_domain(Stmt.getSchedule());
+  if(isl_set_is_equal(scopset, set)){
+    NewStmt = &Stmt;
+    isl_set_free(scopset);
+    break;
+  }
+  isl_set_free(scopset);
+  }
+  data->S->copyScopStmt(NewStmt, data->CopyNo);
+
+  isl_set_free(set);
+  return isl_stat_ok;
+}
+
+isl_union_map *makeScheduleSingleValued(isl_union_map *ScheduleMap, Scop &S){
+  //create a printer for the printing of isl types.
+  isl_printer *P = isl_printer_to_str(S.getIslCtx());
+  P = isl_printer_set_output_format(P, ISL_FORMAT_ISL);
+  P = isl_printer_flush(P);
+
+  isl_union_map *universe, *ScheduleDup, *FinalSchedule;
+  isl_union_map *NewSchedule;
+  isl_union_set *domain;
+
+  //create a schedule containing only duplicate elements.
+  FinalSchedule = isl_union_map_lexmin(isl_union_map_copy(ScheduleMap));
+  ScheduleDup = isl_union_map_subtract(isl_union_map_copy(ScheduleMap), isl_union_map_copy(FinalSchedule));
+
+  // create struct to be used by the isl_union_set_foreach_set functions.
+  struct print_info ScopData = {&S};
+  struct schedule_info ScheduleData;
+  ScheduleData.OriginalUmap = isl_union_map_copy(FinalSchedule);
+  ScheduleData.NewUmap = isl_union_map_copy(FinalSchedule);
+  int i = 1;
+
+  while(!isl_union_map_is_empty(ScheduleDup)){
+    assert(i < 11 && "More than 10 copies required!");
+    
+    universe = isl_union_map_universe(isl_union_map_copy(ScheduleDup));
+    domain = isl_union_map_domain(universe);
+
+    //fix the Scop by duplicating statements which are executed multiple times.
+    ScopData.CopyNo = i;
+    assert(isl_union_set_foreach_set(domain, &copyScopStatements, &ScopData) >= 0 &&
+        "error during foreach for copyScopStatements!");
+
+    // fix the schedule
+    ScheduleData.CopyNo = i;
+    if (isl_union_set_foreach_set(domain, &copyScheduleStatements, &ScheduleData) >= 0 &&
+        "error during foreach for copyScheduleStatements!");
+
+    NewSchedule = isl_union_map_lexmin(isl_union_map_copy(ScheduleDup));
+    isl_union_map_free(ScheduleData.OriginalUmap);
+    ScheduleData.OriginalUmap = isl_union_map_copy(NewSchedule);
+    ScheduleDup = isl_union_map_subtract(ScheduleDup, NewSchedule);
+    isl_union_set_free(domain);
+    i++;
+  }
+  
+  errs() << "\nNew Map:\n" << ScheduleData.NewUmap << "\n";
+
+  isl_printer_free(P);
+  isl_union_map_free(ScheduleMap);
+  isl_union_map_free(ScheduleDup);
+  isl_union_map_free(ScheduleData.OriginalUmap);
+  isl_union_map_free(ScheduleData.NewUmap);
+  return FinalSchedule;
+}
+
 bool JSONImporter::importSchedule(Scop &S, Json::Value &JScop,
                                   const Dependences &D) {
   StatementToIslMapTy NewSchedule;
 
   int Index = 0;
   for (ScopStmt &Stmt : S) {
     Json::Value Schedule = JScop["statements"][Index]["schedule"];
     assert(!Schedule.asString().empty() &&
            "Schedules that contain extension nodes require special handling.");
     isl_map *Map = isl_map_read_from_str(S.getIslCtx(), Schedule.asCString());
     isl_space *Space = Stmt.getDomainSpace();
 
     // Copy the old tuple id. This is necessary to retain the user pointer,
     // that stores the reference to the ScopStmt this schedule belongs to.
     Map = isl_map_set_tuple_id(Map, isl_dim_in,
                                isl_space_get_tuple_id(Space, isl_dim_set));
     for (unsigned i = 0; i < isl_space_dim(Space, isl_dim_param); i++) {
       isl_id *Id = isl_space_get_dim_id(Space, isl_dim_param, i);
       Map = isl_map_set_dim_id(Map, isl_dim_param, i, Id);
     }
     isl_space_free(Space);
     NewSchedule[&Stmt] = Map;
     Index++;
   }
 
   if (!D.isValidSchedule(S, &NewSchedule)) {
     errs() << "JScop file contains a schedule that changes the "
            << "dependences. Use -disable-polly-legality to continue anyways\n";
     for (auto Element : NewSchedule)
       isl_map_free(Element.second);
     return false;
   }
 
   auto ScheduleMap = isl_union_map_empty(S.getParamSpace());
   for (ScopStmt &Stmt : S) {
     if (NewSchedule.find(&Stmt) != NewSchedule.end())
       ScheduleMap = isl_union_map_add_map(ScheduleMap, NewSchedule[&Stmt]);
     else
       ScheduleMap = isl_union_map_add_map(ScheduleMap, Stmt.getSchedule());
   }
 
+  // Check if the map is single valued.
+  if(!isl_union_map_is_single_valued(ScheduleMap)){
+  DEBUG(dbgs() << "JScop file contains a schedule that is not single valued\n");
+
+  // Not Yet Finished, when ScheduleMap can be fixed by makeScheduleSingleValued, the new ScheduleMap will be passed.
+  ScheduleMap = makeScheduleSingleValued(ScheduleMap, S);
+  isl_union_map_free(ScheduleMap);
+  return false;
+  }
+
   S.setSchedule(ScheduleMap);
 
   return true;
 }
 
 bool JSONImporter::importAccesses(Scop &S, Json::Value &JScop,
                                   const DataLayout &DL) {
   int StatementIdx = 0;