periscop/candl

Data Dependence Analyzer in the Polyhedral Model

candl's Issues

Candl implicitly depends on beta-vector structure, and does it wrong.

candl_statement_usr structure is used to identify loops using internal contiguous indexing. Its construction depends on beta-vectors, and does it wrong.

To compute these indexes, it silently assumes that each even 0-based output dimension is a beta and looks at the constant factor of the corresponding line to compute the index. This results in unexpected, wrong loop indexing for SCoPs that do not have full betas, e.g. those coming from Pluto.

Worse, when the dimension is a beta, it assumes statements in the SCoP appear in a lexicographical order of their beta-vectors. It changes the loop index if certain values of beta-vector grow, but not if they decrease. This is a problem for many SCoPs coming from Clay.

For example, a SCoP with two statements having beta-vectors [0,0] and [1,0] is handled fine. The same SCoP with swapped beta-vectors, [1,0] and [0,0], is considered to have only one loop with two statements inside.

I discovered this problem when invoking candl_dependence_is_loop_carried that expects a loop index. As a result, several loops may be "joined" together and wrongfully carry a dependence while other loops may be ignored. Indexes are also used in candl_dependence_build_system, but I did not evaluate which problems it may raise. Clearly, the indexing system is broken.

Now, I don't see an easy solution. While I could rewrite so that it does not expect lexicographically sorted betas, it would still depend on SCoPs having beta-structure, which makes it much less general. Furthermore, beta-functions are a part of Clay, that depends on Candl, so we cannot introduce the inverse dependence.

Moving beta-functionality to osl as suggested in periscop/openscop#25, may be a part of the solution. We also need functionality that would recover betas from the SCoP that does not have them. My current implementation of such functionality is in Chlore, written in C++ and depending on CLooG, making it hard to extract...

ISS with glpk test fails (pluto+)

test/multi-stmt-2d-periodic.c test/multi-stmt-2d-periodic.c:6:15: error: CHECK-DAG: expected string not found in input
// CHECK-DAG: T(S{{[0-9]+}}): (t, t+i, t+j)
^
:26:1: note: scanning from here
[pluto] Affine transformations [<iter coeff's> ]
^
:31:1: note: possible intended match here
T(S2): (t, t+j, t+i)
^
[Failed] test/multi-stmt-2d-periodic.c!

This could be due to the recent change to objective -- t+j is being preferred over t+i.

Outdated inline documentation

In multiple places the doxygen documentation dates back to the date when the dependence analysis was moved from CLooG, including references to CloogViolation and company.

One can use clang's -Wdocumentation option to see the list of most notable problems. I propose to update this documentation, grepping by cloog should suffice + clang should suffice and update the documentation style a little bit. The heading candl_function_name function: in each comment takes space and risks heavily to become outdated if the function is renamed. But the old name remains in the file, which is confusing for both Doxygen and someone who processes the file.

Candl should rely on isl_val instead of isl_int

configure not checking for makeinfo

Candl's configure isn't checking for texinfo, and as a result, there's a build time failure when texinfo isn't present.

...
MAKEINFO candl.info
/home/uday/git/pluto/candl/autoconf/missing: line 81: makeinfo: command not found
WARNING: 'makeinfo' is missing on your system.
You should only need it if you modified a '.texi' file, or
any other file indirectly affecting the aspect of the manual.
You might want to install the Texinfo package:
https://www.gnu.org/software/texinfo/
The spurious makeinfo call might also be the consequence of
using a buggy 'make' (AIX, DU, IRIX), in which case you might
want to install GNU make:
https://www.gnu.org/software/make/
make[4]: *** [Makefile:489: candl.info] Error 127
make[4]: Leaving directory '/home/uday/git/pluto/candl/doc'
make[3]: *** [Makefile:628: all-recursive] Error 1
make[3]: Leaving directory '/home/uday/git/pluto/candl/doc'
make[2]: *** [Makefile:905: all-recursive] Error 1
make[2]: Leaving directory '/home/uday/git/pluto/candl'
make[1]: *** [Makefile:519: all-recursive] Error 1
make[1]: Leaving directory '/home/uday/git/pluto'
make: *** [Makefile:391: all] Error 2
[uday@localhost pluto]$ sudo dnf -y install makeinfo
Last metadata expiration check: 0:54:47 ago on Thu 02 May 2019 11:56:24 PM IST.
No match for argument: makeinfo
Error: Unable to find a match

Candl types not found

Hi there,

I have one code developed using Candl that uses CandlOptions, CandlOptions, CandlDependence.
I could not find these types on my installation using the latest of this repo.
Have I installed the wrong version?

Thanks,

Candl is getting array refs the wrong way

candl_dependence_get_array_refs_in_dep suppose some form of relation to extract the array id (used to be OK with scoplib, but not OK anymore), it should rely on osl_relation_get_array_id.