Data dependency algorithms under polyhedral model vs. normal algorithms

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
  1. I test (GCD test and Banerjee test): Only evaluates the ability to prove or disprove dependence between statements.
  2. 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.
  3. Polyhedral dependence: Give the right precision level ( Will tell which iteration of statements are in dependent).
• Triangle loops
  1. I test and Omega test: Can not handle.
  2. Polyhedral dependence: Can handle.
• conditionals with boolean expressions of affine inequalities
  1. I test and Omega test: Can not handle.
  2. Polyhedral dependence: Can handle.
• Cost
  1. I test: It cost less and is always preferred because they capture most dependency under a low computational cost.
  2. Omega test: Worst exponential complexities, but works good in practice.
  3. 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.  */