  This work explores an unexpected application of Implicit Computational
Complexity (ICC) to parallelize loops in imperative programs. Thanks to a
lightweight dependency analysis, our algorithm allows splitting a loop into
multiple loops that can be run in parallel, resulting in gains in terms of
execution time similar to state-of-the-art automatic parallelization tools when
both are applicable. Our graph-based algorithm is intuitive, language-agnostic,
proven correct, and applicable to all types of loops, even if their loop
iteration space is unknown statically or at compile time, if they are not in
canonical form or if they contain loop-carried dependency. As contributions we
deliver the computational technique, proof of its preservation of semantic
correctness, and experimental results to quantify the expected performance
gains. Our benchmarks also show that the technique could be seamlessly
integrated into compiler passes or other automatic parallelization suites. We
assert that this original and automatable loop transformation method was
discovered thanks to the "orthogonal" approach offered by ICC.
