Infinite loop in init_alias_analysis

Infinite loop in init_alias_analysis

[Christian Iseli]

Hi there,

I got an infinite loop while compiling sone test code here.  I think I have 
tracked down the
problem to the new (as of snapshot 971031) code in alias.c, in the 
init_alias_analysis routine,
in the while (changed) loop.

Things happen in the following way:
- During the first iteration of the loop, new_reg_base_value[24] is set to 
(address (reg:HI 1 %r3)),
  (reg 1 is a FUNCTION_ARG_REGNO_P) while copying_arguments is true.
- Later in the function, new_reg_base_value[1] is set to (reg/v:HI 24)

- Now the first iteration terminates and the values from new_reg_base_value 
are copied into
  reg_base_value.
- In the next loop iteration, find_base_value is called and promptly returns 
the values it finds
  in reg_base_value, which yields to new_reg_base_value[24] => (reg/v:HI 24) 
and
  new_reg_base_value[1] => (address (reg:HI 1 %r3))
- And so on...

I'm not sure what's the best fix...
  - set reg_seen of the argument register when it is copied to the pseudo ?
  - avoid the part before NOTE_INSN_FUNCTION_BEG in subsequent loop iterations 
?
  - do some clever testing of new_reg_base_value and reg_base_value ?
  - reverse the if statements in the REG case in find_base_value ?

What do you think?

					Christian

Re: Infinite loop in init_alias_analysis

[Jeffrey A Law]

  In message < 199711041226.NAA07119@Rivendell.MiddleEarth.net >you write:
  > Hi there,
  > 
  > I got an infinite loop while compiling sone test code here.  I think I have
  >  
  > tracked down the
  > problem to the new (as of snapshot 971031) code in alias.c, in the 
  > init_alias_analysis routine,
  > in the while (changed) loop.
Sorry, I really can't follow your problem description.

Typically, when the alias code looped, that indicated that some register
that could hold a pointer at function entry wasn't put into the
new_reg_base_value array -- for example the static chain, or structure
value address tweaked this problem when I was working on the code.

  > Things happen in the following way:
  > - During the first iteration of the loop, new_reg_base_value[24] is set to 
  > (address (reg:HI 1 %r3)),
OK.

  >   (reg 1 is a FUNCTION_ARG_REGNO_P) while copying_arguments is true.
  > - Later in the function, new_reg_base_value[1] is set to (reg/v:HI 24)
OK.

  > - Now the first iteration terminates and the values from new_reg_base_value
OK.

  >  
  > are copied into
  >   reg_base_value.
  > - In the next loop iteration, find_base_value is called and promptly
  > returns the values it finds in reg_base_value, which yields to
  > new_reg_base_value[24] => (reg/v:HI 24> ) 
  > and
  >   new_reg_base_value[1] => (address (reg:HI 1 %r3))
  > - And so on...
Sorry, this is where you lost me.  Can you describe this better?

What are the arguments for the relavent calls to find_base_value?  What
does find_base_value return for those calls?

How does this set up a condition where we always think something changed?

Can you describe exactly what registers have pointer values in them at
function start?  An RTL dump of the function in question might be useful
too.


  > I'm not sure what's the best fix...
  >   - set reg_seen of the argument register when it is copied to the pseudo ?
I don't think this is right -- reg_seen tracks which registers have been
set, not the registers that were used as sources of sets.

  >   - avoid the part before NOTE_INSN_FUNCTION_BEG in subsequent loop
  > iterations 
No, I think this is wrong too -- seems to me that you have to be consistent
in how you handle argument copying each time through the loop.

  >   - do some clever testing of new_reg_base_value and reg_base_value ?
Such as?

  >   - reverse the if statements in the REG case in find_base_value ?
Hmmm, I don't think this is right either.

  > What do you think?
I think we need more information :-)

The one thing I'd considered was setting new_reg_base_value from reg_base_value
at the bottom of the loop.  I couldn't ever come up with a compelling
reason why it would be needed, but maybe you have.  I'd need more information
to make that decision though.

jeff

Re: Infinite loop in init_alias_analysis

[Christian Iseli]

law@hurl.cygnus.com said:
>  > Things happen in the following way: - During the first iteration 
>  > of the loop, new_reg_base_value[24] is set to  (address (reg:HI 1 %r3))
> OK.

>   >   (reg 1 is a FUNCTION_ARG_REGNO_P) while copying_arguments is 
>   > true. - Later in the function, new_reg_base_value[1] is set to (reg/v:HI 24)
> OK.

>   > - Now the first iteration terminates and the values from 
>   >   new_reg_base_value
> OK.

>   >   are copied into   reg_base_value. - In the next loop iteration, 
>   > find_base_value is called and promptly returns the values it finds in 
>   > reg_base_value, which yields to new_reg_base_value[24] => (reg/v:HI 
>   > 24> )  and   new_reg_base_value[1] => (address (reg:HI 1 %r3)) - And 
>   > so on...
> Sorry, this is where you lost me.  Can you describe this better? 

I'll try :-)

We seem to agree on the state of things after the first iteration through the 
loop;
we have:
  reg_base_value[1]  == (reg/v:HI 24)
  ...
  reg_base_value[24] == (address (reg:HI 1 %r3))
which were copied from new_reg_base_value.

Now we start a new iteration.  find_base_value is called (line 269 of alias.c) 
with
(reg:HI 1 %r3) and, since reg_base_value[1]  contains (reg/v:HI 24), returns 
(reg/v:HI 24).
Thus new_reg_base_value[24] is set to (reg/v:HI 24).
Later, find_base_value is called with (reg/v:HI 24) and, since 
reg_base_value[24]  contains
(address (reg:HI 1 %r3)), returns (address (reg:HI 1 %r3)).
Thus new_reg_base_value[1] is set to (address (reg:HI 1 %r3)).
At the end of the while loop, things are copied from new_reg_base_value to 
reg_base_value
and so, at the end of the second iteration we have:
  reg_base_value[1]  == (address (reg:HI 1 %r3))
  ...
  reg_base_value[24] == (reg/v:HI 24)
i.e., 1 and 24 were swapped.

So we start the 3rd iteration. find_base_value is called with (reg:HI 1 %r3) 
and, since
reg_base_value[1]  contains (address (reg:HI 1 %r3)), returns (address (reg:HI 
1 %r3)).
Thus new_reg_base_value[24] is set to (address (reg:HI 1 %r3)).
Later, find_base_value is called with (reg/v:HI 24) and, since 
reg_base_value[24]  contains
(reg/v:HI 24), returns (reg/v:HI 24).
Thus new_reg_base_value[1] is set to (reg/v:HI 24).
At the end of the while loop, things are copied from new_reg_base_value to 
reg_base_value
and so, at the end of the third iteration we have:
  reg_base_value[1]  == (reg/v:HI 24)
  ...
  reg_base_value[24] == (address (reg:HI 1 %r3))
i.e., 1 and 24 were swapped again.

So we have an endless loop.

The C routine that causes a problem looks like
  char *foo(char *str, const char *p, int n)
  {
    some loop doing *str++ = something;
    *str = '\0';
    return str;
  }
str is passed in (reg:HI 1 %r3) and copied into (reg/v:HI 24).
The first setting of (reg:HI 1 %r3) occurs for the return statement.

>   > I'm not sure what's the best fix...
>   >   - do some clever testing of new_reg_base_value and reg_base_value ?
> Such as?

Not allowing to return reg_base_value when it is the same as the argument of 
find_base_value...

At the moment, the following patch is my preferred proposition.

I hope I was more clear this time.

Let me know what you think.
					Christian


*** alias.c~	Tue Nov  4 10:52:17 1997
--- alias.c	Tue Nov  4 14:04:27 1997
*************** find_base_value (src)
*** 95,110 ****
        return src;
  
      case REG:
-       /* If this REG is related to a known base value, return it.  */
-       if (reg_base_value[REGNO (src)])
- 	return reg_base_value[REGNO (src)];
- 
        /* At the start of a function argument registers have known base
  	 values which may be lost later.  Returning an ADDRESS
  	 expression here allows optimization based on argument values
  	 even when the argument registers are used for other purposes.  */
        if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
  	return new_reg_base_value[REGNO (src)];
        return src;
  
      case MEM:
--- 95,110 ----
        return src;
  
      case REG:
        /* At the start of a function argument registers have known base
  	 values which may be lost later.  Returning an ADDRESS
  	 expression here allows optimization based on argument values
  	 even when the argument registers are used for other purposes.  */
        if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
  	return new_reg_base_value[REGNO (src)];
+ 
+       /* If this REG is related to a known base value, return it.  */
+       if (reg_base_value[REGNO (src)])
+ 	return reg_base_value[REGNO (src)];
        return src;
  
      case MEM:

Re: Infinite loop in init_alias_analysis

[Jeffrey A Law]

  In message < 199711042032.VAA16414@Rivendell.MiddleEarth.net >you write:
  > I'll try :-)
Thanks.

  > We seem to agree on the state of things after the first iteration
  > through the loop;
Yup.  Having HJ's alpha failure to look at was a big help too.  This
is a case where an RTL dump from the pass before the alias code hung
would have been quite useful since I can't just build your target
and look at it under the debugger :-)


  > we have:
  >   reg_base_value[1]  == (reg/v:HI 24)
  >   ...
  >   reg_base_value[24] == (address (reg:HI 1 %r3))
  > which were copied from new_reg_base_value.
Right.  Just to be sure.  I assume you've got something like this
in your RTL dump:

(set (reg 24) (reg 1)
NOTE_INSN_FUNCTION_BEGIN
...
(set (reg 1) (reg 24))
...


HJ's alpha example is actually one copy deeper, but the same
basic problem:

(set (reg 68) (reg 16))
NOTE_INSN_FUNCTION_BEGIN
...
(set (reg 69) (reg 68))
...
(set (reg 16) (reg 69))

After the first iteration we have:

reg_base_value[16] = (reg 69)
               68  = (address (reg 16))
               69  = (reg 68)

Which sets up up for the same kind of loop that I think you're
running into (the three values just keep rotating around in the
values arrays).

For some reason I didn't run into this on the PA, or sparc when
I bootstrapped them, though I don't know why since it seems like
it's a pretty generic problem.  The x86 didn't exhibit this failure
because it doesn't pass args in registers.

  > Now we start a new iteration.  find_base_value is called (line 269 of alias.c) 
  > with (reg:HI 1 %r3) and, since reg_base_value[1]  contains (reg/v:HI 24), returns 
  > (reg/v:HI 24).
Right.  I think my confusion was your register number/names didn't
mentally make sense to me -- (reg:HI 1 %r3) (register #1, name %r3),
I kept thinking that should refer to reg_base_value[3].

I see it now :-)

  > Not allowing to return reg_base_value when it is the same as the
  > argument of find_base_value...
Now that I've had a chance to look at the code, I suspect either
your solution or mine will work.  Mine converges quicker, but I'm
somewhat leery that for some weird example the quicker convergence
might be to the wrong state :(

  > I hope I was more clear this time.
Yup.  I'm going to add a comment or two and use your solution.

jeff

Re: Infinite loop in init_alias_analysis

[Jeffrey A Law]

  In message < 199711051230.NAA01044@lslsun17.epfl.ch >you write:
  > > HJ's alpha example is actually one copy deeper, but the same
  > > basic problem:
  > 
  > I was wondering if longer cycles were likely to happen.  Now I know :-)
Oh yes :-)    The reason behind the reorganization of the alias.c
code was do deal with more longer, more complicated set chains better. 
They can get much longer than 3 sets and aren't always nice and
simple like (set (regx) (regy)) 

  > > Now that I've had a chance to look at the code, I suspect either
  > > your solution or mine will work.  Mine converges quicker, but I'm
  > > somewhat leery that for some weird example the quicker convergence
  > > might be to the wrong state :(
  > 
  > What's your solution?
Instead of wiping new_reg_base_value clean at the start of the loop,
you copy entries from reg_base_value to it.   Problem is I can't
convince myself this is the right thing to do, but I can convince
myself that your solution is the right thing to do.

jeff

Re: Infinite loop in init_alias_analysis

[Christian Iseli]

>   > What's your solution?
> Instead of wiping new_reg_base_value clean at the start of the loop,
> you copy entries from reg_base_value to it.   Problem is I can't
> convince myself this is the right thing to do, but I can convince
> myself that your solution is the right thing to do.

I'll let you be the judge on this one :)

					Christian

Re: Infinite loop in init_alias_analysis

[Christian Iseli]

> Yup.  Having HJ's alpha failure to look at was a big help too.  This
> is a case where an RTL dump from the pass before the alias code hung
> would have been quite useful since I can't just build your target
> and look at it under the debugger :-)

Right.  I'll keep that in mind...

> Just to be sure.  I assume you've got something like this
> in your RTL dump:
> 
> (set (reg 24) (reg 1)
> NOTE_INSN_FUNCTION_BEGIN
> ...
> (set (reg 1) (reg 24))
> ...

Yup, exactly.

> HJ's alpha example is actually one copy deeper, but the same
> basic problem:

I was wondering if longer cycles were likely to happen.  Now I know :-)

> Now that I've had a chance to look at the code, I suspect either
> your solution or mine will work.  Mine converges quicker, but I'm
> somewhat leery that for some weird example the quicker convergence
> might be to the wrong state :(

What's your solution?

>   > I hope I was more clear this time.
> Yup.  I'm going to add a comment or two and use your solution.

Ok, thanks.  Waiting for the next snapshot... ;-)

					Christian