Re: Unswitching

Re: Unswitching

[Michael Hayes]

Jeffrey A Law writes:

 > Anyway, given a loop condition like:
 > 
 > bar ? (i < 4) : (i < 8)
 > 
 > One of the easy ways to pull the "bar" test out of the loop is to create
 > two loops:
 > 
 > if (bar)
 >   loop using i < 4
 > else
 >   loop using i < 8
 > 
 > The code expansion is greater then reworking the condition into
 > i < (bar ? 4 : 8), then hoisting the (bar ? 4 : 8) out of the loop.

Yes, we emit twice the code.

 > But the net result is two loops with very simple conditions which can
 > easily be unrolled.  If they get completely unrolled it's likely cross
 > jumping would be able to eliminate the code expansion later by having the
 > i < 4 code jump into the middle of the i < 8 code.

I am more interested in determining the iteration count so that we can
use low overhead looping instructions or decrement and branch
instructions.

While loop unswitching is a very desirable optimisation, it is bit
like using a sledgehammer to crack this walnut.

I've had another think about that pesky transformation and I'm
convinced that it is sub-optimal, especially if the target has
conditional loads. 

Consider the following:

int cmp(int bar, int foo)
{
  return foo < (bar ? 2 : 4);
}

Without the transformation, I get for the c4x (look no branches!):

_cmp:
	cmpi3	0,ar2  ; bar in ar2
	ldiu	2,r0
	ldieq	4,r0
	cmpi3	r0,r2  ; foo in r2
	ldiu	0,r1
	ldilt	1,r1
	ldiu	r1,r0
	rets

The current state of play gives (one delayed branch):

_cmp:
	cmpi3	0,ar2
	beqd	L3
	ldiu	r2,r0
	cmpi3	3,r0
	nop
	; branch occurs here
	cmpi3	1,r0
	ldiu	0,r0
	ldile	1,r0
	rets
L3:
	ldiu	0,r0
	ldile	1,r0
	rets


Michael.

Re: Ternary operator in loop condition

[Jeffrey A Law]

  In message < 13976.30162.513083.611567@ongaonga.elec.canterbury.ac.nz >you writ
e:
  >  > I'd be much more interested in whether or not "bar ? 4 : 8" gets hoisted
  >  > out of the loop since it's a loop invariant
  > 
  > Even without the undesirable transformation, my limited knowledge of
  > the loop hoisting code indicates that this still will not be hoisted.
  > It appears to give up once it finds a conditional branch.
It may be something that could be caught by gcse/pre once alias analysis is
tied into that pass.

Basically gcse/pre would see that the expression can be computed multiple times
on certain paths (those which loop) and that its value doesn't change.  It's
supposed to hoist it out of the loop.

Note that while gcse/pre does loop invariant code motion, it is not as
powerful as the LICM performed by the loop optimizer -- the loop optimizer
knows how to reshape expressions (particularly address computations) to expose
additional loop invariants.

jeff

Re: Ternary operator in loop condition

[Michael Hayes]

Jeffrey A Law writes:
 >   > Looking at the unrolling problem pointed out by Richard Earnshaw I've
 >   > noticed that the C front end converts a loop termination condition
 >   > such as: 'i < (bar ? 4 : 8); i++)' into 'bar ? (i < 4) : (i < 8)'.
 >   > 
 >   > Is there any good reason for doing this? 
 > Probably.  You should track down the code which does this transformation. 

Yep, once I've found my way through a maze of twisty little passages,
all alike.

 >   > void foo(bar)
 >   >      int bar;
 >   > {
 >   >   int i;
 >   >   
 >   >   for (i = 0; i < (bar ? 4 : 8); i++)
 >   >     fred[i] = 0;
 >   > }

 > I'd be much more interested in whether or not "bar ? 4 : 8" gets hoisted
 > out of the loop since it's a loop invariant

Even without the undesirable transformation, my limited knowledge of
the loop hoisting code indicates that this still will not be hoisted.
It appears to give up once it finds a conditional branch.

Michael.

Re: Ternary operator in loop condition

[Michael Hayes]

Jeffrey A Law writes:

 > I wonder if our time would be better spent trying to hoist this puppy out
 > of the loop or on something completely different.  There's a little bird
 > telling me we're not worrying about the common case for when we want to
 > unroll loops :-)

Right, this would be the more general and my preferred solution.
However, it's also the much harder problem to solve ;-(

Currently we do a pitiful job of hoisting invariants out of the loop
termination testing instructions and it's easy to overlook that the
termination testing code is executed every iteration.  If the
iteration count is invariant and can be hoisted out we've got a lot to
gain.

Michael

cmov [Re: Unswitching]

[Richard Henderson]

On Thu, Jan 14, 1999 at 02:20:51AM -0700, Jeffrey A Law wrote:
> This is a failing in our conditional move support.  There's no technical
> reason why it can't handle both kinds of sequences and generate nonbranching
> code.  Basically our support for conditional moves is minimal at the moment.

For the record, here's one I came across the other day
that I wanted to fix.  It went something like

	if (prev)
		prev->next = node;
	else
		head = node;

where head was a global.  This could be transformed to

	if (prev)
		tmp = &prev->next;
	else
		tmp = &head;
	*tmp = node;

ie

	lda	$0,head
	lda	$1,8($9)
	cmoveq	$9,$0,$1
	stq	$2,0($1)


r~

Re: Unswitching

[Jeffrey A Law]

  In message < 13981.25914.187251.809584@ongaonga.elec.canterbury.ac.nz >you writ
  > I am more interested in determining the iteration count so that we can
  > use low overhead looping instructions or decrement and branch
  > instructions.
Yup.  You'd actually be able to do that if you unswitched them  :-)  Their
lifetimes could never overlap (as long as they were kept as loops and not
unrolled).


  > While loop unswitching is a very desirable optimisation, it is bit
  > like using a sledgehammer to crack this walnut.
Yes, but it is a sledgehammer that we want to build anyway.


  > I've had another think about that pesky transformation and I'm
  > convinced that it is sub-optimal, especially if the target has
  > conditional loads. 
  > 
  > Consider the following:
  > 
  > int cmp(int bar, int foo)
  > {
  >   return foo < (bar ? 2 : 4);
  > }
  > 
  > Without the transformation, I get for the c4x (look no branches!):
This is a failing in our conditional move support.  There's no technical
reason why it can't handle both kinds of sequences and generate nonbranching
code.  Basically our support for conditional moves is minimal at the moment.
jeff

Re: Ternary operator in loop condition

[Michael Hayes]

Jeffrey A Law writes:
 >   > build_binary_op in c-typeck.c seems to do the damage.   The next 
 >   > question concerns whether the transformation is useful in general 
 >   > and how it should be disabled without pessimizing other stuff.
 > Where precisely does this happen within build_binary_op?

The transformation (damage) is actually done by fold
(fold-const.c:4222) called from build_binary_op.

i < (a ? b : c) ==>  a ? (i < b) : (i < c)

Now under some circumstances I can see that this generates better code
but it sure makes it harder to determine a loop iteration count.

Michael.

Re: Ternary operator in loop condition

[Michael Hayes]

Michael Hayes writes:
 > Jeffrey A Law writes:
 >  >   > Looking at the unrolling problem pointed out by Richard Earnshaw I've
 >  >   > noticed that the C front end converts a loop termination condition
 >  >   > such as: 'i < (bar ? 4 : 8); i++)' into 'bar ? (i < 4) : (i < 8)'.
 >  >   > 
 >  >   > Is there any good reason for doing this? 
 >  > Probably.  You should track down the code which does this transformation. 
build_binary_op in c-typeck.c seems to do the damage.   The next 
question concerns whether the transformation is useful in general 
and how it should be disabled without pessimizing other stuff.

Michael.

Re: Ternary operator in loop condition

[Jeffrey A Law]

  In message < 13975.57349.465373.745785@ongaonga.elec.canterbury.ac.nz >you write:
  > 
  > Looking at the unrolling problem pointed out by Richard Earnshaw I've
  > noticed that the C front end converts a loop termination condition
  > such as: 'i < (bar ? 4 : 8); i++)' into 'bar ? (i < 4) : (i < 8)'.
  > 
  > Is there any good reason for doing this? 
Probably.  You should track down the code which does this transformation. 
There'll probably be some comments around it which may help understand why
the conditional is transformed.

  > The disadvantages I see are
  > that we generate two latch blocks for a loop with this termination
  > condition (which has been upsetting the loop unrolling code) and that
  > it makes it much harder to detect that the number of loop iterations
  > is loop invariant.
It's probably not a good thing to do for loop test conditions.  It probably
is a good thing to do in other circumstances.



  > For example, consider the following function.  We should be able to
  > determine that the loop iterates 4 or 8 times before we enter the
  > loop.
  > 
  > static char *fred;
  > 
  > void foo(bar)
  >      int bar;
  > {
  >   int i;
  >   
  >   for (i = 0; i < (bar ? 4 : 8); i++)
  >     fred[i] = 0;
  > }
Yea, but I doubt it's very important to be able to make that determination.
I'd be much more interested in whether or not "bar ? 4 : 8" gets hoisted
out of the loop since it's a loop invariant

jeff

Ternary operator in loop condition

[Michael Hayes]

Looking at the unrolling problem pointed out by Richard Earnshaw I've
noticed that the C front end converts a loop termination condition
such as: 'i < (bar ? 4 : 8); i++)' into 'bar ? (i < 4) : (i < 8)'.

Is there any good reason for doing this?  The disadvantages I see are
that we generate two latch blocks for a loop with this termination
condition (which has been upsetting the loop unrolling code) and that
it makes it much harder to detect that the number of loop iterations
is loop invariant.

For example, consider the following function.  We should be able to
determine that the loop iterates 4 or 8 times before we enter the
loop.

static char *fred;

void foo(bar)
     int bar;
{
  int i;
  
  for (i = 0; i < (bar ? 4 : 8); i++)
    fred[i] = 0;
}


Michael.

Unswitching [Was: Re: Ternary operator in loop condition]

[Jeffrey A Law]

  In message < 13980.29872.698277.543613@ongaonga.elec.canterbury.ac.nz >you writ
e:
  > Right, this would be the more general and my preferred solution.
  > However, it's also the much harder problem to solve ;-(
Maybe harder to solve.  But the benefits are probably greater than
having the unroller realize the loop iterates a multiple of 4 times and
optimizing the unrolled loop & precondition code accordingly.


Anyway, given a loop condition like:

bar ? (i < 4) : (i < 8)

One of the easy ways to pull the "bar" test out of the loop is to create
two loops:

if (bar)
  loop using i < 4
else
  loop using i < 8

The code expansion is greater then reworking the condition into
i < (bar ? 4 : 8), then hoisting the (bar ? 4 : 8) out of the loop.

But the net result is two loops with very simple conditions which can
easily be unrolled.  If they get completely unrolled it's likely cross
jumping would be able to eliminate the code expansion later by having the
i < 4 code jump into the middle of the i < 8 code.

Plus the work would be re-useable for implementing unswitching.  

Toon -- stop jumping up and down.  Calm down. I know you want this
optimization  ;-)



      do i = 1, n
         if (lcond) then
            <body1>
         else
            <body2>
         endif
      enddo

If lcond is a loop invariant it can be turned into:

      if (lcond) then
         do i = 1, n
            <body1>
         enddo
      else
         do i = 1, n
            <body2>
         enddo
      endif


It'd be awful cool.  And I don't think it's a horribly difficult problem
to solve.

  > Currently we do a pitiful job of hoisting invariants out of the loop
  > termination testing instructions and it's easy to overlook that the
  > termination testing code is executed every iteration.  If the
  > iteration count is invariant and can be hoisted out we've got a lot to
  > gain.
Yup.  No arguments.

jeff

Re: Ternary operator in loop condition

[Jeffrey A Law]

  In message < 13977.33688.460065.141289@ongaonga.elec.canterbury.ac.nz >you writ
e:
  >  > It may be something that could be caught by gcse/pre once alias analysis
  >  is
  >  > tied into that pass.
  > 
  > How about a case where there is no aliasing.  What mods are required
  > for the gcse/pre pass to hoist "(bar ? 4 : 8)" from the loop in the
  > following example?
  > 
  > static char fred[100];
  > 
  > void foo(bar)
  >      int bar;
  > {
  >   int i;
  >   
  >   for (i = 0; i < (bar ? 4 : 8); i++)
  >     fred[i] = 0;
  > }
The key is to extend the code which computes local properties to know more
precisely when a load is killed.  A load is killed by a store to memory
which might reference the same memory, a function call or anytime the address
expression for the load is killed.

Right now we consider a load killed by any store, function call or when the
address expression for the load is killed.




jeff

Re: Ternary operator in loop condition

[Jeffrey A Law]

  In message < 13977.11474.68617.538818@ongaonga.elec.canterbury.ac.nz >you write
:
  > Michael Hayes writes:
  >  > Jeffrey A Law writes:
  >  >  >   > Looking at the unrolling problem pointed out by Richard Earnshaw 
  > I've
  >  >  >   > noticed that the C front end converts a loop termination conditio
  > n
  >  >  >   > such as: 'i < (bar ? 4 : 8); i++)' into 'bar ? (i < 4) : (i < 8)'
  > .
  >  >  >   > 
  >  >  >   > Is there any good reason for doing this? 
  >  >  > Probably.  You should track down the code which does this transformat
  > ion. 
  > build_binary_op in c-typeck.c seems to do the damage.   The next 
  > question concerns whether the transformation is useful in general 
  > and how it should be disabled without pessimizing other stuff.
Where precisely does this happen within build_binary_op?

jeff

Re: Ternary operator in loop condition

[Michael Hayes]

 > It may be something that could be caught by gcse/pre once alias analysis is
 > tied into that pass.

How about a case where there is no aliasing.  What mods are required
for the gcse/pre pass to hoist "(bar ? 4 : 8)" from the loop in the
following example?

static char fred[100];

void foo(bar)
     int bar;
{
  int i;
  
  for (i = 0; i < (bar ? 4 : 8); i++)
    fred[i] = 0;
}

Michael.

Re: Ternary operator in loop condition

[Jeffrey A Law]

  In message < 13980.26939.10991.979841@ongaonga.elec.canterbury.ac.nz >you write
:
  > Jeffrey A Law writes:
  >  >   > build_binary_op in c-typeck.c seems to do the damage.   The next 
  >  >   > question concerns whether the transformation is useful in general 
  >  >   > and how it should be disabled without pessimizing other stuff.
  >  > Where precisely does this happen within build_binary_op?
  > 
  > The transformation (damage) is actually done by fold
  > (fold-const.c:4222) called from build_binary_op.
  > 
  > i < (a ? b : c) ==>  a ? (i < b) : (i < c)
  > 
  > Now under some circumstances I can see that this generates better code
  > but it sure makes it harder to determine a loop iteration count.
I wonder if our time would be better spent trying to hoist this puppy out
of the loop or on something completely different.  There's a little bird
telling me we're not worrying about the common case for when we want to
unroll loops :-)


jeff