Talk:Loop-invariant code motion

The page originally had the following:

This can then be further optimized, leading to less overall executed code for larger values of maxval and/or smaller values of calcval.

int calcval = (4+array[k])*pi+5;
j = j + integer_part((maximum - 1 - j) / calcval) * calcval;

However, that transformation is not "loop-invariant code motion". In any case it is not obviously correct when maximum is near overflow (well, OK, maybe it's undefined behaviour then, but suppose that j was unsigned). --DavidHopwood 01:16, 29 January 2007 (UTC)[reply]

Exactly, it's undefined. If you're going to allow undefined behaviour to limit your optimizations by making it "defined" then even simple optimizations like loop unrolling greatly suffer. Themania (talk) 05:04, 26 July 2008 (UTC)[reply]

As of 10 Apr 2007, this article has:

while (j < maximum - 1)
{
     j = j + ( 4 + array[ k ] ) * pi + 5; 
}
The calculation of maximum - 1 and (4+array[k])*pi+5 can be moved outside the loop.

This makes an assumption that the program in question is not threaded. Otherwise, what would be the guarantee that no other thread would modify the value of maximum while this thread was executing that loop? (As for the pre-calculation?)

--Kevin

The only way another thread could modify maximum (legally) would be via having it's address taken at some point and stored in a variable the other thread can access. And even then, assuming the above is c code, maximum would have to be marked as volatile. The example gives no impression that either is true. And even if it isn't c code, alias analysis is likely to be performed before loop invariant code motion which would reveal that another thread cannot access maximum. Themania (talk) 05:04, 26 July 2008 (UTC)[reply]

Non-compiler use[edit]

This sort of optimization is frequently seen in JavaScript, where iterating over an array or a list of DOM nodes can often be sped up by precalculating the length of the array or node list either outside the loop or (more commonly) in the initialization of the loop variables (e.g., for(var i=0, max=someList.length; i < max; i++) instead of for(var i=0; i<someList.length; i++), avoiding the repetitive computation -- in some JavaScript implementations -- of someList.length). If anyone thinks this would be a useful addition to the article, I'll dig up some references and put it in. Ubernostrum 08:43, 5 July 2007 (UTC)[reply]

Somethign wrong here in the example[edit]

There is no need for this loop at all. Just multiply the sodding thing up by calcval and then round off the end. Something is wrong here.

SimonTrew (talk) 21:56, 9 March 2009 (UTC)[reply]

I've replaced the (slightly weird) example with another, hopefully better, example. Alksentrs (talk) 01:33, 10 March 2009 (UTC)[reply]

OK great. I am gonna check it over with my subbing eye. I hope you don't mind, I am sure it is fine, Wikipedia is great and I love it a lot and everyone who puts into it, but if something is wrong you have to say so.

a[i] is a multiplication[edit]

"[...] strength reduction could remove the two multiplications inside the loop (6*i and a[i]) [...]"

Via C syntax and pointer arithmetic, a[i] can also be interpreted as *(a + i). Can someone tell where the hidden multiplication is taking place? --Abdull (talk) 12:56, 29 October 2010 (UTC)[reply]

When doing pointer arithmetic, the index needs to be scaled by the pointer target's size: if a has type int*, then *(a + i) is equal to *(int*) (((char*) a) + (i * sizeof(int))). Alksentrs (talk) 16:44, 29 October 2010 (UTC)[reply]

Code motion[edit]

Should code motion link here? 70.247.173.255 (talk) 00:46, 20 May 2012 (UTC)[reply]