Currently, we give up on loop interchange if we encounter a flow dependency anywhere in the loop list. Worse yet, we don't even track output dependencies.
This patch updates the dependency matrix computation to flow and output dependencies in the same way anti dependencies are tracked.
This improve an internal workload by a 2.2x speedup. All correctness test pass including SPEC2000, SPEC2006, and the llvm test-suite.
Note the loop interchange pass is off by default. It can be enabled with '-mllvm -enable-loopinterchange'
Please take a look.