Optimizing g++ when indexing an array with an injective function

Question

I have a for loop where each step i, it processes an array element p[f(i)], where f(i) is an injective (one-to-one) map from 1...n to 1...m (m > n). So there is no data coupling in the loop and all compiler optimization techniques such as pipelining can be used. But how can I inform g++ of the injectivity of f(i)? Or do I even need to (can g++ figure that out)?

Answer 1

Assuming that f doesn't rely on any global state and produces no side effects, you can tag it with the const attribute:

int f(int i) __attribute__((const));

If f does rely on global state but still has the property that it's a pure function of its inputs and global state (and produces no side effects), you can use the the slightly weaker pure attribute.

These attributes let gcc make more optimizations than it otherwise could, although I don't know if these will be helpful in your case. Take a look at the generated assembly code and see if they help.

Answer 2

You could also try processing the loop with a temporary storage array, i.e.:

temp[i]= process(p[f(i)]);

then copy the results back:

p[f(i)]= temp[i];

Assuming you declared p and temp to be restricted pointers, the compiler has enough information to optimize a little more aggressively.

Answer 3

If the definition of f() is in scope and is inlineable most any good compiler should first inline it into the function, then the next optimization passes should be able to rewrite the code as if the function call wasn't there.