boolean loop optimisation

R

Roedy Green

If I wrote some code like this:


for ( int i=0; i<n; i++ )
{
if ( x )
{
a( i );
}
else
{
b( i );
}
}

A clever compiler might notice that x in invariant inside the loop,
and note really does not need to test x inside the loop. It can
replace that code with something like this:

if ( x ) for ( int i=0; i<n; i++ )
{
a( i );
}
else for ( int i=0; i<n; i++ )
{
b( i );
}

What is that called?
 
B

Brad BARCLAY

Roedy said:
If I wrote some code like this:


for ( int i=0; i<n; i++ )
{
if ( x )
{
a( i );
}
else
{
b( i );
}
}

A clever compiler might notice that x in invariant inside the loop,
and note really does not need to test x inside the loop. It can
replace that code with something like this:

<snip>

That depends, actually, on wether or not x can be modified by another
thread while the loop is running. If it's a volatile instance or class
variable, you won't be able to use this sort of optimization.

Brad BARCLAY
 
C

Chris Uppal

Roedy Green wrote:

[...]
A clever compiler might notice that x in invariant inside the loop,
and note really does not need to test x inside the loop. It can
replace that code with something like this: [...]
What is that called?

I think "code hoisting" is the common name.

-- chris
 
X

xarax

Chris Uppal said:
Roedy Green wrote:

[...]
A clever compiler might notice that x in invariant inside the loop,
and note really does not need to test x inside the loop. It can
replace that code with something like this: [...]
What is that called?

I think "code hoisting" is the common name.

-- chris

Yes, I think that's the term. A compiler writer would be
burned at the stack if he wrote a compiler that hoisted
that particular code sequence. There's no way to tell
whether a() or b() can modify x (it's not declared as
a local variable so it's likely a field).
 
R

Roedy Green

There's no way to tell
whether a() or b() can modify x (it's not declared as
a local variable so it's likely a field).

Since you don't see the declaration, you can't make any such
presumption. I should have declared it local and final in the example
to make it abundantly clear the optimisation would be safe.

It could even be safe if x were a field. It depends what a() and b()
potentially do. I think we underestimate just how much snooping about
today's global optimisers can do.
 
R

rkm

xarax said:
Yes, I think that's the term. A compiler writer would be
burned at the stack if he wrote a compiler that hoisted
that particular code sequence. There's no way to tell
whether a() or b() can modify x (it's not declared as
a local variable so it's likely a field).


No, it's called Loop-Invariant Code Motion.

From "Advanced Compiler Design and Implementation" - Steve
Muchnick:

pg 397
"Loop-invariant code motion recognizes computations in loops
that produce the same value on every iteration of the loop
and moves them out of the loop."

pg 417
"Code Hoisting (also called unification) finds expressions
that are always evaluated following some point in a program,
regardless of the execution path, and moves them to the
earliest point beyond which they would always be evaluated."

Rick
 
T

Thomas G. Marshall

Roedy Green said:
On 11 Sep 2003 06:35:23 -0700, (e-mail address removed) (xarax) wrote or quoted


Since you don't see the declaration, you can't make any such
presumption. I should have declared it local and final in the example
to make it abundantly clear the optimisation would be safe.

It could even be safe if x were a field. It depends what a() and b()
potentially do. I think we underestimate just how much snooping about
today's global optimisers can do.

It would not be safe if the field were publicly accessible.

The code you're talking about (say, in class A) could easily be used by
/other/ code (from class B) that modifies the daylights out of A.x in
another thread. The A code was compiled long before the B code was.

volatile.
 
C

Chris Uppal

rkm said:
pg 397
"Loop-invariant code motion recognizes computations in loops
that produce the same value on every iteration of the loop
and moves them out of the loop."

pg 417
"Code Hoisting (also called unification) finds expressions
that are always evaluated following some point in a program,
regardless of the execution path, and moves them to the
earliest point beyond which they would always be evaluated."

Thanks for the clarification.

Still, it seems to me that "Loop-invariant code motion" is a special case of
"Code Hoisting" and I doubt whether many people make that fine a distinction.
It depends, I suppose, on how much of a specialist (or pedant) you are.

-- chris (a pedant, and proud of it)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top