Talk:Loop-invariant code motion

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing ??? This article has not yet received a rating on the project's importance scale.

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

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

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.

"[...] 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

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