**Theoretically**[1]:

Data dependency algorithms in trunk is mostly with I test and Omega test. Both of them are limited. Here is a comparison between them.

- Precise level
- I test (GCD test and Banerjee test): Only evaluates the ability to prove or disprove dependence between statements.
- Omega test: Can give a precise level (Tell which iteration of statements are in dependent), but less precise when there is one or more integer symbolic constant are present.
- Polyhedral dependence: Give the right precision level ( Will tell which iteration of statements are in dependent).

- Triangle loops
- I test and Omega test: Can not handle.
- Polyhedral dependence: Can handle.

- conditionals with boolean expressions of affine inequalities
- I test and Omega test: Can not handle.
- Polyhedral dependence: Can handle.

- Cost
- I test: It cost less and is always preferred because they capture most dependency under a low computational cost.
- Omega test: Worst exponential complexities, but works good in practice.
- Polyhedral dependence: High cost.

Reference: [1] Violated Dependence Analysis by Nicolas Vasilache, Albert Cohen, Cedric Bastoul, Sylvain Girbal.

**Practically (Implement in Graphite)**:

/* FIXME: Need to be added. */

## No comments:

Post a Comment