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.  */

Testing result of run-time after loop-parallelization

It's unlucky that blogger is unavailable  now in China that I could only
using gladder to get access. But it's lucky that blogger has a email
post functionality, so, it's fine.

I have tested some simple loops which parallelized by autopar
to see how much promotion we can got. This test results now
is available in gcc wiki:
http://gcc.gnu.org/wiki/AutoparRelated.
Mainly include:

1. One nested loop, number of threads vs. run-time, with
   not all the code parallel.
2. One nested loop, number of threads vs. run-time, almost
   all code got parallel.
3. Two nested loops, with innermost parallel, number of threads
    vs. run-time. (It got worse after parallel.)
4. Two nested loops, with outer loop parallel, number of threads
    vs. run-time. (It's better).

The 4 figures include comparing of:
 - Runtime of openmp directive inserted c code.
 - Runtime of Graphite autoparallel c code.
 - Runtime of non-parallel c code.

For this week, I'm planning to do some work with
the already-done data dependency work. Maybe firstly write
some test cases for the data dependency checking to see what
kinds of loops we could/want parallelize.

Tips for reading code

Using cscope instead of grep

In gcc code base, the definition of a function is always writen like:

int
some_func(int *)
{
...
}

So that when you wanner find a certain definition, you can use something like:

grep *.c ^some_func

This is not always convenient especially when you want to find definition in a code based not styled like gcc style. With cscope, you can do more...

• Find global definition
• Find functions calling a function
• Find egrep pattern (I like this, it's super nice)
• More...

Sometimes it doesn't work when using cscope finding definition in gcc.
Yes, this happens when you trying to find the definition of struct which marked by GTY(()), which is related to a sophisticated memory management techniques. But whenever their is a question, there is always a solution just not far away. We can simply find these definitions with cscope's finding egrep pattern method, then you can find patterns like struct GTY ((chain_next ("%h.next"))) loop. It's easy, hmm :)
Cscope supported emacs and it's integrated in a kind interface. But I think it'll be better if it can do something like etags works in emacs -- Go back as farther from where I start the find command as it can do... I like this very much, you may want to go back to your place after you read the definition's definition's definition...

Sometimes we need to use find+grep

Sometimes it's more convenient to using unix's super good cmd tool like find grep etc. to search the code base.
If you want to find in gcc/testsuite 's expect file (*.exp) a certain pattern, say DEFAULT_CFLAGS. You can simply use:
find . -iname "*.exp" -exec grep DEFAULT_CFLAGS {} \;

^L :)

write testsuites for autopar's code generation part

After triggering autopar's code generation part after Graphite, I write some testcases for judging whether this part works correctly. Now the simple tests is located at testsuites/gcc.dg/graphite/graphite_autopar. These test cases will PASS all the 9 checkings (3 checkings per test). Unfortunately, the reduction tests (I didn't include in the testsuites) will fail when collecting reduction information. I'll work with Razya to findout why.

Basic plans:

• Regression test for the patch(split autopar) for trunk.
• Try to merge/update Graphite's autopar code generation part with trunk (This part need some time, maybe I'll try to findout if we can do this appropriately first).
  
• Testsuites of autopar in trunk didn't actually run (just compile and analysis dump file), so maybe I'll submit a patch for that.