I've attached a patch that lets us interchange this.
It does two things:

1. It lets the chrec code consider variables invariant in the loop that 
matches the chrec variable (loop number) as constant for purposes for the 
chrec.

2. It informs the data dependence tester that chrecs that are equal 
(ie the same chrec) overlap on every iteration.

This is enough to get this loop to interchange.

Sebastian, unless you have a problem with this, then Dorit, i'd like to 
apply this to the autovect branch (Feel free to use 
evolution_function_is_invariant_p in the tests in the vectorizer. It 
should let you catch some more loops than the simple constant test, if 
you can transform them properly)

It includes Richard's testcase in order to make sure we don't regress here 
later on.

:)