[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

1172

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

2357

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

lib/Analysis/ScopInfo.cpp

1705

Cast (std::string) is unnecessary.

1707

You must also change the user part of the isl_id.

4845

Maybe call it copyScopStmt?

lib/Exchange/JSONExporter.cpp

341

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

385

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

401

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.

404–408

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

411

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

419

Consider using assert for such checks.

435

There is isl_union_map_dump(ScheduleData.NewUmap).

517

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

536

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

2

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

1716–1717

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

453

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

329

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

330

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

349

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

353

[Serious] Asserts are removed from NDEBUG builds. Try

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

378

[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 a BasicBlock.
   ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
            std::vector<Instruction *> Instructions);
 
   /// Create an overapproximating ScopStmt for the region @p R.
   ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop);
 
   /// Create a copy statement.
   ///
   /// @param Stmt       The parent statement.
   /// @param SourceRel  The source location.
   /// @param TargetRel  The target location.
   /// @param Domain     The original domain under which the copy statement would
   ///                   be executed.
   ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,
            isl::set Domain);
 
   /// Initialize members after all MemoryAccesses have been added.
   void init(LoopInfo &LI);
 
+  void updateAccesDomain();
+
 private:
   /// Polyhedral description
   //@{
 
   /// The Scop containing this ScopStmt.
   Scop &Parent;
 
   /// The domain under which this statement is not modeled precisely.
public:
   isl::set getInvalidDomain() const { return InvalidDomain; }
 
   /// Get the invalid context for this statement.
   isl::set getInvalidContext() const { return getInvalidDomain().params(); }
 
   /// Set the invalid context for this statement to @p ID.
   void setInvalidDomain(isl::set ID);
 
+  void setDomain(isl::set ID);
+
   /// Get the BasicBlock represented by this ScopStmt (if any).
   ///
   /// @return The BasicBlock represented by this ScopStmt, or null if the
   ///         statement represents a region.
   BasicBlock *getBasicBlock() const { return BB; }
 
   /// Return true if this statement represents a single basic block.
   bool isBlockStmt() const { return BB != nullptr; }
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 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 the copy statement would
   ///                   be executed.
   ScopStmt *addScopStmt(isl::map SourceRel, isl::map TargetRel,

lib/Analysis/ScopInfo.cpp

for (unsigned u = 0, e = Domain.dim(isl::dim::set); u < e; u++) {
     isl::id DimId = Domain.get_dim_id(isl::dim::set, u);
     NestLoops.push_back(static_cast<Loop *>(DimId.get_user()));
   }
 }
 
 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(), parent.getNextStmtIdx(), "", UseInstructionNames);
 }
 
 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
                    std::vector<Instruction *> Instructions)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
       R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop),
       Instructions(Instructions) {
 
   BaseName = getIslCompatibleName("Stmt", &bb, parent.getNextStmtIdx(), "",
                                   UseInstructionNames);
 }
 
 ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,
                    isl::set NewDomain)
     : Parent(parent), InvalidDomain(nullptr), Domain(NewDomain), BB(nullptr),
       R(nullptr), Build(nullptr) {
   BaseName = getIslCompatibleName("CopyStmt_", "",
                                   std::to_string(parent.getCopyStmtsNum()));
void ScopStmt::init(LoopInfo &LI) {
   buildDomain();
   collectSurroundingLoops();
   buildAccessRelations();
 
   if (DetectReductions)
     checkForReductions();
 }
 
+void ScopStmt::updateAccesDomain() {
+  for (MemoryAccess *MA : MemAccs) {
+    isl::map AccessRel = MA->getAccessRelation();
+    isl::id Id = AccessRel.get_tuple_id(isl::dim::in);
+    AccessRel = AccessRel.add_dims(isl::dim::in, 1);
+    AccessRel = AccessRel.set_tuple_id(isl::dim::in, Id);
+    MA->setAccessRelation(AccessRel);
+  }
+}
+
 /// Collect loads which might form a reduction chain with @p StoreMA.
 ///
 /// Check if the stored value for @p StoreMA is a binary operator with one or
 /// two loads as operands. If the binary operand is commutative & associative,
 /// used only once (by @p StoreMA) and its load operands are also used only
 /// once, we have found a possible reduction chain. It starts at an operand
 /// load and includes the binary operator and @p StoreMA.
 ///
if (!S)
     return "";
   auto Str = stringFromIslObj(S);
   isl_map_free(S);
   return Str;
 }
 
 void ScopStmt::setInvalidDomain(isl::set ID) { InvalidDomain = ID; }
 
+void ScopStmt::setDomain(isl::set ID) {
+  collectSurroundingLoops();
+  Domain = ID;
+}
+
 BasicBlock *ScopStmt::getEntryBlock() const {
   if (isBlockStmt())
     return getBasicBlock();
   return getRegion()->getEntry();
 }
 
 unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
 
static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) {
   isl::stat Res = USet.foreach_set(Lambda);
   (void)Res;
 
   assert(Res == isl::stat::ok);
 
   return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
 }
 
 void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
                        std::vector<Instruction *> Instructions) {
   assert(BB && "Unexpected nullptr!");
   Stmts.emplace_back(*this, *BB, SurroundingLoop, Instructions);
   auto *Stmt = &Stmts.back();
   StmtMap[BB].push_back(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/GICHelper.h"
 #include "polly/Support/ScopLocation.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 < OldContextDim; i++) {
     NewContext = isl_set_set_dim_id(NewContext, isl_dim_param, i, Id);
   }
 
   isl_set_free(OldContext);
   S.setContext(NewContext);
   return true;
 }
 
+// finds the ScopStmt corresponding to Map.
+ScopStmt *findStmtFromMap(Scop &S, isl::map Map) {
+  isl::map Universe;
+  isl::set StmtDomain, MapDomain;
+  ScopStmt *CurrentStmt;
+
+  Universe = isl::map::universe(Map.get_space());
+  MapDomain = Universe.domain();
+
+  for (ScopStmt &Stmt : S) {
+    StmtDomain = Stmt.getSchedule().domain();
+    if (StmtDomain.is_equal(MapDomain)) {
+      CurrentStmt = &Stmt;
+      break;
+    }
+  }
+
+  return CurrentStmt;
+}
+
+isl::stat makeStmtSingleValued(Scop &S, isl::union_map *NewSchedule,
+                               isl::map MapToAdd) {
+  isl::map LexMin;
+
+  assert((LexMin = MapToAdd.lexmin()) && "Map is not lower-bounded!");
+  if (!MapToAdd.is_equal(LexMin)) {
+    // non-singular valued map
+    int i = 0;
+    ScopStmt *CurrentStmt;
+    int dim = MapToAdd.dim(isl::dim::in);
+
+    // schedule for dim = 0
+    isl::map CurMap = LexMin.add_dims(isl::dim::in, 1);
+    isl::id Id = LexMin.get_tuple_id(isl::dim::in);
+    isl::set Domain;
+    isl::local_space LS = isl::local_space(CurMap.get_space());
+    isl::constraint C = isl::constraint::alloc_equality(LS);
+    C = C.set_constant_val(isl::val(MapToAdd.get_ctx(), -i));
+    C = C.set_coefficient_si(isl::dim::in, dim, 1);
+    i++;
+
+    CurMap = CurMap.add_constraint(C);
+    CurMap = CurMap.set_tuple_id(isl::dim::in, Id);
+    Domain = CurMap.domain();
+    *NewSchedule = NewSchedule->add_map(CurMap);
+
+    MapToAdd = MapToAdd.subtract(LexMin);
+    // schedule for dim > 0
+    while (!MapToAdd.is_empty()) {
+      assert((LexMin = MapToAdd.lexmin()) && "Map is not lower-bounded!");
+      MapToAdd = MapToAdd.subtract(LexMin);
+
+      CurMap = LexMin.add_dims(isl::dim::in, 1);
+      C = C.set_constant_val(isl::val(MapToAdd.get_ctx(), -i));
+      CurMap = CurMap.add_constraint(C);
+      CurMap = CurMap.set_tuple_id(isl::dim::in, Id);
+
+      *NewSchedule = NewSchedule->add_map(CurMap);
+      i++;
+
+      Domain = Domain.unite(CurMap.domain());
+    }
+
+    // Find the new domain
+    CurrentStmt = findStmtFromMap(S, MapToAdd);
+    isl::set OrigDomain = CurrentStmt->getDomain();
+    OrigDomain = OrigDomain.add_dims(isl::dim::set, 1);
+    OrigDomain = OrigDomain.set_tuple_id(Id);
+    Domain = Domain.intersect(OrigDomain);
+
+    // Adjust the Scop
+    CurrentStmt->setDomain(Domain);
+    CurrentStmt->updateAccesDomain();
+
+  } else {
+    // singular valued map
+    *NewSchedule = NewSchedule->add_map(MapToAdd);
+  }
+
+  return isl::stat::ok;
+}
+
+/// Makes a single-valued schedule and adds the required ScopStmts to the
+/// Scop.
+///
+/// @param OldSchedule The non-single-valued schedule to be made single-valued.
+///
+/// @param S The Scop where the new ScopStmts need to be added.
+///
+/// @returns isl_union_map the new single valued schedule.
+isl::union_map makeScheduleSingleValued(isl::union_map OldSchedule, Scop &S) {
+  isl::union_map NewSchedule;
+  NewSchedule = NewSchedule.empty(OldSchedule.get_space());
+
+  assert(OldSchedule.foreach_map([&S, &NewSchedule](isl::map Map) -> isl::stat {
+    return makeStmtSingleValued(S, &NewSchedule, Map);
+  }) == isl::stat::ok &&
+         "error during fixing schedule!");
+
+  DEBUG(dbgs() << "\nNew Map:\n"; NewSchedule.dump(); dbgs() << "\n\n");
+
+  return NewSchedule;
+}
+
+static isl_stat basicMapIsBounded(__isl_take isl_basic_map *Map, void *User) {
+  if (isl_basic_map_image_is_bounded(Map)) {
+    isl_basic_map_free(Map);
+    return isl_stat_ok;
+  }
+  isl_basic_map_free(Map);
+  return isl_stat_error;
+}
+
+static isl_stat mapIsBounded(__isl_take isl_map *Map, void *User) {
+  if (isl_map_foreach_basic_map(Map, basicMapIsBounded, NULL) == isl_stat_ok) {
+    isl_map_free(Map);
+    return isl_stat_ok;
+  }
+  isl_map_free(Map);
+  return isl_stat_error;
+}
+
+static bool unionMapIsBounded(isl_union_map *Map) {
+  if (isl_union_map_foreach_map(Map, &mapIsBounded, NULL) == isl_stat_ok) {
+    return true;
+  }
+  return false;
+}
+
 bool JSONImporter::importSchedule(Scop &S, Json::Value &JScop,
                                   const Dependences &D) {
   StatementToIslMapTy NewSchedule;
 
   // Check if key 'statements' is present.
   if (!JScop.isMember("statements")) {
     errs() << "JScop file has no key name 'statements'.\n";
     return false;
for (unsigned i = 0; i < isl_space_dim(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++;
   }
 
   // Check whether the new schedule is valid or not.
   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().release());
   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().release());
   }
 
+  // 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.
+    if (!unionMapIsBounded(ScheduleMap)) {
+      DEBUG(dbgs() << "JScop file contains a schedule that is not bounded\n");
+      isl_union_map_free(ScheduleMap);
+      return false;
+    }
+
+    ScheduleMap =
+        makeScheduleSingleValued(isl::manage(ScheduleMap), S).release();
+
     S.setSchedule(ScheduleMap);
 
+    const Dependences &NewD =
+        getAnalysis<DependenceInfo>().recomputeDependences(
+            Dependences::AL_Statement);
+    DEBUG(dbgs() << "\nNew dependences:\n"; NewD.dump(););
+  } else {
+    S.setSchedule(ScheduleMap);
+  }
+
   return true;
 }
 
 bool JSONImporter::importAccesses(Scop &S, Json::Value &JScop,
                                   const DataLayout &DL) {
   int StatementIdx = 0;
 
   // Check if key 'statements' is present.
if (!parsingSuccessful) {
     return false;
   }
 
   bool Success = importContext(S, jscop);
 
   if (!Success)
     return false;
 
-  Success = importSchedule(S, jscop, D);
+  Success = importArrays(S, jscop);
 
   if (!Success)
     return false;
 
-  Success = importArrays(S, jscop);
+  Success = importAccesses(S, jscop, DL);
 
   if (!Success)
     return false;
 
-  Success = importAccesses(S, jscop, DL);
+  Success = importSchedule(S, jscop, D);
 
   if (!Success)
     return false;
 
   return false;
 }
 
 void JSONImporter::getAnalysisUsage(AnalysisUsage &AU) const {

test/ScopDetect/double_convolution___%for.body---%for.end50.jscop.recompute

+{
+   "arrays" : [
+      {
+         "name" : "MemRef0",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      },
+      {
+         "name" : "MemRef1",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      },
+      {
+         "name" : "MemRef2",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      },
+      {
+         "name" : "MemRef3",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      },
+      {
+         "name" : "MemRef4",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      }
+   ],
+   "context" : "{  :  }",
+   "name" : "%for.body---%for.end50",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt0[i0] -> MemRef0[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt0[i0] : 0 <= i0 <= 49 }",
+         "name" : "Stmt0",
+         "schedule" : "{ Stmt0[i0] -> [0, i0, 0, 0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0] -> MemRef1[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt2[i0] : 0 <= i0 <= 47 }",
+         "name" : "Stmt2",
+         "schedule" : "{ Stmt2[i0] -> [1, t, 0, i0, 0]: 0 <= t < 6 }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt5[i0, i1] -> MemRef2[i0 + i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt5[i0, i1] -> MemRef3[i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt5[i0, i1] -> MemRef0[i0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt5[i0, i1] -> MemRef0[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt5[i0, i1] : 0 <= i0 <= 49 and 0 <= i1 <= 2 }",
+         "name" : "Stmt5",
+         "schedule" : "{ Stmt5[i0, i1] -> [2, t0, 0, t1, i1]: 0 <= t0 < 6 and 0 <= t1 < 10 and i0 = t0 * 8 + t1  }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt9[i0, i1] -> MemRef0[i0 + i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt9[i0, i1] -> MemRef4[i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt9[i0, i1] -> MemRef1[i0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt9[i0, i1] -> MemRef1[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt9[i0, i1] : 0 <= i0 <= 47 and 0 <= i1 <= 2 }",
+         "name" : "Stmt9",
+         "schedule" : "{ Stmt9[i0, i1] -> [2, t0, 1, t1, i1]: 0 <= t0 < 6 and 0 <= t1 < 8 and i0 = t0 * 8 + t1 }"
+      }
+   ]
+}

test/ScopDetect/double_convolution___%for.body---%for.end50.jscop.unbound

+{
+   "arrays" : [
+      {
+         "name" : "MemRef0",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      },
+      {
+         "name" : "MemRef1",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      },
+      {
+         "name" : "MemRef2",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      },
+      {
+         "name" : "MemRef3",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      },
+      {
+         "name" : "MemRef4",
+         "sizes" : [ "*" ],
+         "type" : "i32"
+      }
+   ],
+   "context" : "{  :  }",
+   "name" : "%for.body---%for.end50",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt0[i0] -> MemRef0[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt0[i0] : 0 <= i0 <= 49 }",
+         "name" : "Stmt0",
+         "schedule" : "{ Stmt0[i0] -> [0, i0, 0, 0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt2[i0] -> MemRef1[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt2[i0] : 0 <= i0 <= 47 }",
+         "name" : "Stmt2",
+         "schedule" : "{ Stmt2[i0] -> [1, t, 0, i0, 0]: 0 <= t }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt5[i0, i1] -> MemRef2[i0 + i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt5[i0, i1] -> MemRef3[i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt5[i0, i1] -> MemRef0[i0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt5[i0, i1] -> MemRef0[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt5[i0, i1] : 0 <= i0 <= 49 and 0 <= i1 <= 2 }",
+         "name" : "Stmt5",
+         "schedule" : "{ Stmt5[i0, i1] -> [2, t0, 0, t1, i1]: 0 <= t0 < 6 and 0 <= t1 < 10 and i0 = t0 * 8 + t1  }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt9[i0, i1] -> MemRef0[i0 + i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt9[i0, i1] -> MemRef4[i1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt9[i0, i1] -> MemRef1[i0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt9[i0, i1] -> MemRef1[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt9[i0, i1] : 0 <= i0 <= 47 and 0 <= i1 <= 2 }",
+         "name" : "Stmt9",
+         "schedule" : "{ Stmt9[i0, i1] -> [2, t0, 1, t1, i1]: 0 <= t0 < 6 and 0 <= t1 < 8 and i0 = t0 * 8 + t1 }"
+      }
+   ]
+}

test/ScopDetect/recomputation.ll

+; RUN: opt -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=recompute -polly-ast -debug -polly-process-unprofitable -disable-polly-legality < %s 2>&1 | FileCheck %s
+
+;void double_convolution(int* restrict Input, int* restrict Kernel1, int* restrict Intermediate,
+;     int* restrict Kernel2, int* restrict Output){
+;
+; for (int m1 = 0; m1 < 50; m1++){
+;   Intermediate[m1] = 0;
+; }
+;
+; for (int m1 = 0; m1 < 48; m1++){
+;   Output[m1] = 0;
+; }
+; 
+; for (int m1 = 0; m1 < 50; m1++){
+;   for(int k1 = 0; k1 < 3; k1++){
+;     Intermediate[m1] += Input[ m1 + k1 ] * Kernel1[k1];
+;   }
+; }
+;
+; for (int m2 = 0; m2 < 48; m2++){
+;   for(int k2 = 0; k2 < 3; k2++){
+;     Output[m2] += Intermediate[ m2 + k2 ] * Kernel2[k2];
+;   }
+; }
+;}
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @double_convolution(i32* noalias %Input, i32* noalias %Kernel1, i32* noalias %Intermediate, i32* noalias %Kernel2, i32* noalias %Output) #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.body
+  %indvars.iv21 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next22, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %Intermediate, i64 %indvars.iv21
+  store i32 0, i32* %arrayidx, align 4
+  %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1
+  %exitcond23 = icmp ne i64 %indvars.iv.next22, 50
+  br i1 %exitcond23, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  br label %for.body4
+
+for.body4:                                        ; preds = %for.end, %for.body4
+  %indvars.iv18 = phi i64 [ 0, %for.end ], [ %indvars.iv.next19, %for.body4 ]
+  %arrayidx6 = getelementptr inbounds i32, i32* %Output, i64 %indvars.iv18
+  store i32 0, i32* %arrayidx6, align 4
+  %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1
+  %exitcond20 = icmp ne i64 %indvars.iv.next19, 48
+  br i1 %exitcond20, label %for.body4, label %for.end9
+
+for.end9:                                         ; preds = %for.body4
+  br label %for.body13
+
+for.body13:                                       ; preds = %for.end9, %for.inc27
+  %indvars.iv15 = phi i64 [ 0, %for.end9 ], [ %indvars.iv.next16, %for.inc27 ]
+  br label %for.body16
+
+for.body16:                                       ; preds = %for.body13, %for.body16
+  %indvars.iv11 = phi i64 [ 0, %for.body13 ], [ %indvars.iv.next12, %for.body16 ]
+  %0 = add nuw nsw i64 %indvars.iv11, %indvars.iv15
+  %arrayidx18 = getelementptr inbounds i32, i32* %Input, i64 %0
+  %1 = load i32, i32* %arrayidx18, align 4
+  %arrayidx20 = getelementptr inbounds i32, i32* %Kernel1, i64 %indvars.iv11
+  %2 = load i32, i32* %arrayidx20, align 4
+  %mul = mul nsw i32 %2, %1
+  %arrayidx22 = getelementptr inbounds i32, i32* %Intermediate, i64 %indvars.iv15
+  %3 = load i32, i32* %arrayidx22, align 4
+  %add23 = add nsw i32 %3, %mul
+  store i32 %add23, i32* %arrayidx22, align 4
+  %indvars.iv.next12 = add nuw nsw i64 %indvars.iv11, 1
+  %exitcond14 = icmp ne i64 %indvars.iv.next12, 3
+  br i1 %exitcond14, label %for.body16, label %for.inc27
+
+for.inc27:                                        ; preds = %for.body16
+  %indvars.iv.next16 = add nuw nsw i64 %indvars.iv15, 1
+  %exitcond17 = icmp ne i64 %indvars.iv.next16, 50
+  br i1 %exitcond17, label %for.body13, label %for.end29
+
+for.end29:                                        ; preds = %for.inc27
+  br label %for.body32
+
+for.body32:                                       ; preds = %for.end29, %for.inc48
+  %indvars.iv8 = phi i64 [ 0, %for.end29 ], [ %indvars.iv.next9, %for.inc48 ]
+  br label %for.body35
+
+for.body35:                                       ; preds = %for.body32, %for.body35
+  %indvars.iv = phi i64 [ 0, %for.body32 ], [ %indvars.iv.next, %for.body35 ]
+  %4 = add nuw nsw i64 %indvars.iv, %indvars.iv8
+  %arrayidx38 = getelementptr inbounds i32, i32* %Intermediate, i64 %4
+  %5 = load i32, i32* %arrayidx38, align 4
+  %arrayidx40 = getelementptr inbounds i32, i32* %Kernel2, i64 %indvars.iv
+  %6 = load i32, i32* %arrayidx40, align 4
+  %mul41 = mul nsw i32 %6, %5
+  %arrayidx43 = getelementptr inbounds i32, i32* %Output, i64 %indvars.iv8
+  %7 = load i32, i32* %arrayidx43, align 4
+  %add44 = add nsw i32 %7, %mul41
+  store i32 %add44, i32* %arrayidx43, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 3
+  br i1 %exitcond, label %for.body35, label %for.inc48
+
+for.inc48:                                        ; preds = %for.body35
+  %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1
+  %exitcond10 = icmp ne i64 %indvars.iv.next9, 48
+  br i1 %exitcond10, label %for.body32, label %for.end50
+
+for.end50:                                        ; preds = %for.inc48
+  ret void
+}
+
+; CHECK: JScop file contains a schedule that is not single valued
+; CHECK-NOT: JScop file contains a schedule that is not bounded

test/ScopDetect/recomputation_unbound.ll

+; RUN: opt -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=unbound -polly-ast -debug -polly-process-unprofitable -disable-polly-legality < %s 2>&1 | FileCheck %s
+
+;void double_convolution(int* restrict Input, int* restrict Kernel1, int* restrict Intermediate,
+;     int* restrict Kernel2, int* restrict Output){
+;
+; for (int m1 = 0; m1 < 50; m1++){
+;   Intermediate[m1] = 0;
+; }
+;
+; for (int m1 = 0; m1 < 48; m1++){
+;   Output[m1] = 0;
+; }
+; 
+; for (int m1 = 0; m1 < 50; m1++){
+;   for(int k1 = 0; k1 < 3; k1++){
+;     Intermediate[m1] += Input[ m1 + k1 ] * Kernel1[k1];
+;   }
+; }
+;
+; for (int m2 = 0; m2 < 48; m2++){
+;   for(int k2 = 0; k2 < 3; k2++){
+;     Output[m2] += Intermediate[ m2 + k2 ] * Kernel2[k2];
+;   }
+; }
+;}
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @double_convolution(i32* noalias %Input, i32* noalias %Kernel1, i32* noalias %Intermediate, i32* noalias %Kernel2, i32* noalias %Output) #0 {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %entry.split, %for.body
+  %indvars.iv21 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next22, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %Intermediate, i64 %indvars.iv21
+  store i32 0, i32* %arrayidx, align 4
+  %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1
+  %exitcond23 = icmp ne i64 %indvars.iv.next22, 50
+  br i1 %exitcond23, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body
+  br label %for.body4
+
+for.body4:                                        ; preds = %for.end, %for.body4
+  %indvars.iv18 = phi i64 [ 0, %for.end ], [ %indvars.iv.next19, %for.body4 ]
+  %arrayidx6 = getelementptr inbounds i32, i32* %Output, i64 %indvars.iv18
+  store i32 0, i32* %arrayidx6, align 4
+  %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1
+  %exitcond20 = icmp ne i64 %indvars.iv.next19, 48
+  br i1 %exitcond20, label %for.body4, label %for.end9
+
+for.end9:                                         ; preds = %for.body4
+  br label %for.body13
+
+for.body13:                                       ; preds = %for.end9, %for.inc27
+  %indvars.iv15 = phi i64 [ 0, %for.end9 ], [ %indvars.iv.next16, %for.inc27 ]
+  br label %for.body16
+
+for.body16:                                       ; preds = %for.body13, %for.body16
+  %indvars.iv11 = phi i64 [ 0, %for.body13 ], [ %indvars.iv.next12, %for.body16 ]
+  %0 = add nuw nsw i64 %indvars.iv11, %indvars.iv15
+  %arrayidx18 = getelementptr inbounds i32, i32* %Input, i64 %0
+  %1 = load i32, i32* %arrayidx18, align 4
+  %arrayidx20 = getelementptr inbounds i32, i32* %Kernel1, i64 %indvars.iv11
+  %2 = load i32, i32* %arrayidx20, align 4
+  %mul = mul nsw i32 %2, %1
+  %arrayidx22 = getelementptr inbounds i32, i32* %Intermediate, i64 %indvars.iv15
+  %3 = load i32, i32* %arrayidx22, align 4
+  %add23 = add nsw i32 %3, %mul
+  store i32 %add23, i32* %arrayidx22, align 4
+  %indvars.iv.next12 = add nuw nsw i64 %indvars.iv11, 1
+  %exitcond14 = icmp ne i64 %indvars.iv.next12, 3
+  br i1 %exitcond14, label %for.body16, label %for.inc27
+
+for.inc27:                                        ; preds = %for.body16
+  %indvars.iv.next16 = add nuw nsw i64 %indvars.iv15, 1
+  %exitcond17 = icmp ne i64 %indvars.iv.next16, 50
+  br i1 %exitcond17, label %for.body13, label %for.end29
+
+for.end29:                                        ; preds = %for.inc27
+  br label %for.body32
+
+for.body32:                                       ; preds = %for.end29, %for.inc48
+  %indvars.iv8 = phi i64 [ 0, %for.end29 ], [ %indvars.iv.next9, %for.inc48 ]
+  br label %for.body35
+
+for.body35:                                       ; preds = %for.body32, %for.body35
+  %indvars.iv = phi i64 [ 0, %for.body32 ], [ %indvars.iv.next, %for.body35 ]
+  %4 = add nuw nsw i64 %indvars.iv, %indvars.iv8
+  %arrayidx38 = getelementptr inbounds i32, i32* %Intermediate, i64 %4
+  %5 = load i32, i32* %arrayidx38, align 4
+  %arrayidx40 = getelementptr inbounds i32, i32* %Kernel2, i64 %indvars.iv
+  %6 = load i32, i32* %arrayidx40, align 4
+  %mul41 = mul nsw i32 %6, %5
+  %arrayidx43 = getelementptr inbounds i32, i32* %Output, i64 %indvars.iv8
+  %7 = load i32, i32* %arrayidx43, align 4
+  %add44 = add nsw i32 %7, %mul41
+  store i32 %add44, i32* %arrayidx43, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 3
+  br i1 %exitcond, label %for.body35, label %for.inc48
+
+for.inc48:                                        ; preds = %for.body35
+  %indvars.iv.next9 = add nuw nsw i64 %indvars.iv8, 1
+  %exitcond10 = icmp ne i64 %indvars.iv.next9, 48
+  br i1 %exitcond10, label %for.body32, label %for.end50
+
+for.end50:                                        ; preds = %for.inc48
+  ret void
+}
+
+; CHECK: JScop file contains a schedule that is not single valued
+; CHECK: JScop file contains a schedule that is not bounded