reg_iterator Caveats

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

reg_iterator Caveats

dag-7
I'm forwarding this to llvmdev so it doesn't get lost in the sea of commits...

                                            -Dave

----------  Forwarded Message  ----------

Subject: Re: [llvm-commits] [llvm] r48521 - in /llvm/trunk:
include/llvm/CodeGen/LiveVariables.h lib/CodeGen/LiveVariables.cpp
test/CodeGen/PowerPC/2008-03-18-RegScavengerAssert.ll
test/CodeGen/X86/x86-64-ret0.ll
Date: Friday 28 March 2008 16:34
From: David Greene <[hidden email]>
To: [hidden email]
Cc: Chris Lattner <[hidden email]>

On Tuesday 18 March 2008 23:59, Chris Lattner wrote:

> How about using reg_iterators to do this?  I assume this only applies
> to vregs.  If you walk the use_iterator list for the register, you can
> very efficiently discard uses in other blocks (check User->getparent()
> == MBB).  Any uses within the same block are either a) in phi nodes,
> in which case they are above the instruction or b) users later in the
> block.
>
> If the representation is not in SSA form, you have to do some more
> checks, but this should be a lot faster than scanning the whole
> machine block.  MBB's can be very large after all :)

Ack.  I just started looking at using reg_iterators elsewhere but wasn't
aware of this non-SSA caveat.  Can you elaborate?

                                               -Dave

-------------------------------------------------------
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

Chris Lattner
On Mar 30, 2008, at 11:17 AM, David Greene wrote:
> I'm forwarding this to llvmdev so it doesn't get lost in the sea of  
> commits...

reg_iterators are independent of SSA or not.  The basic issue is that  
if you loop over uses or defs of a register, it will return *all* the  
uses/defs of that register in the current function.  If the value is  
SSA form, it is reasonable to say "give me the first def" and expect  
it to be the only def.  For multiply defined values like physregs,  
this is not true, because the reg can have multiple defs.

That said, ref_iterator and variants will always do what they are  
documented to, they just don't magically provide ssa-like properties  
for physregs.

-Chris

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

greened
On Sunday 30 March 2008 01:30:40 pm Chris Lattner wrote:

> On Mar 30, 2008, at 11:17 AM, David Greene wrote:
> > I'm forwarding this to llvmdev so it doesn't get lost in the sea of
> > commits...
>
> reg_iterators are independent of SSA or not.  The basic issue is that
> if you loop over uses or defs of a register, it will return *all* the
> uses/defs of that register in the current function.  If the value is
> SSA form, it is reasonable to say "give me the first def" and expect
> it to be the only def.  For multiply defined values like physregs,
> this is not true, because the reg can have multiple defs.

Gotcha.  This is exactly what I want.  Thanks for the explanation.

For non-SSA values, is there some indication of which defs reach which
uses?  I don't need this right now but I can imagine using it in the future.

                                        -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

Chris Lattner
On Mar 30, 2008, at 10:42 PM, David A. Greene wrote:
>> SSA form, it is reasonable to say "give me the first def" and expect
>> it to be the only def.  For multiply defined values like physregs,
>> this is not true, because the reg can have multiple defs.
>
> Gotcha.  This is exactly what I want.  Thanks for the explanation.
>
> For non-SSA values, is there some indication of which defs reach which
> uses?  I don't need this right now but I can imagine using it in the  
> future.

The reg def/kill/dead flags are all that there is.

-Chris
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

dag-7
On Monday 31 March 2008 00:57, Chris Lattner wrote:

> On Mar 30, 2008, at 10:42 PM, David A. Greene wrote:
> >> SSA form, it is reasonable to say "give me the first def" and expect
> >> it to be the only def.  For multiply defined values like physregs,
> >> this is not true, because the reg can have multiple defs.
> >
> > Gotcha.  This is exactly what I want.  Thanks for the explanation.
> >
> > For non-SSA values, is there some indication of which defs reach which
> > uses?  I don't need this right now but I can imagine using it in the
> > future.
>
> The reg def/kill/dead flags are all that there is.

I just discovered that def_itterator (and presumably, reg_iterator) doesn't
include implicit defs, for example at function calls for caller-save physical
registers.  Guh.  I'm not sure if it should or not, but it's certainly
necessary information in some cases.  Is this expected behavior, or an
oversight?

                                            -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

Evan Cheng-2

On Mar 31, 2008, at 2:53 PM, David Greene wrote:

> On Monday 31 March 2008 00:57, Chris Lattner wrote:
>> On Mar 30, 2008, at 10:42 PM, David A. Greene wrote:
>>>> SSA form, it is reasonable to say "give me the first def" and  
>>>> expect
>>>> it to be the only def.  For multiply defined values like physregs,
>>>> this is not true, because the reg can have multiple defs.
>>>
>>> Gotcha.  This is exactly what I want.  Thanks for the explanation.
>>>
>>> For non-SSA values, is there some indication of which defs reach  
>>> which
>>> uses?  I don't need this right now but I can imagine using it in the
>>> future.
>>
>> The reg def/kill/dead flags are all that there is.
>
> I just discovered that def_itterator (and presumably, reg_iterator)  
> doesn't
> include implicit defs, for example at function calls for caller-save  
> physical
> registers.  Guh.  I'm not sure if it should or not, but it's certainly
> necessary information in some cases.  Is this expected behavior, or an
> oversight?

MachineRegisterInfo tracks virtual register only.

I also wish it would track physical register defs and uses as well. It  
can be used to simplify a lot of code (in livevariable, etc.). Chris,  
do you think that's feasible?

Evan

>
>
>                                            -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

Chris Lattner
On Mon, 31 Mar 2008, Evan Cheng wrote:
>> I just discovered that def_itterator (and presumably, reg_iterator)
>> doesn't
>> include implicit defs, for example at function calls for caller-save
>> physical
>> registers.  Guh.  I'm not sure if it should or not, but it's certainly
>> necessary information in some cases.  Is this expected behavior, or an
>> oversight?

reg iterators will return everything that is in the function.  If the
implicit operands haven't been added to the machieninstrs yet, then they
won't be returned.

> MachineRegisterInfo tracks virtual register only.

It works for vregs and pregs today.

> I also wish it would track physical register defs and uses as well. It
> can be used to simplify a lot of code (in livevariable, etc.). Chris,
> do you think that's feasible?

Really really feasible :)

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

Evan Cheng-2

On Mar 31, 2008, at 4:55 PM, Chris Lattner wrote:

> On Mon, 31 Mar 2008, Evan Cheng wrote:
>>> I just discovered that def_itterator (and presumably, reg_iterator)
>>> doesn't
>>> include implicit defs, for example at function calls for caller-save
>>> physical
>>> registers.  Guh.  I'm not sure if it should or not, but it's  
>>> certainly
>>> necessary information in some cases.  Is this expected behavior,  
>>> or an
>>> oversight?
>
> reg iterators will return everything that is in the function.  If the
> implicit operands haven't been added to the machieninstrs yet, then  
> they
> won't be returned.
>
>> MachineRegisterInfo tracks virtual register only.
>
> It works for vregs and pregs today.

Ok! Fooled me with this comment:

/// MachineRegisterInfo - Keep track of information for each virtual  
register,
/// including its register class.

Evan

>
>
>> I also wish it would track physical register defs and uses as well.  
>> It
>> can be used to simplify a lot of code (in livevariable, etc.). Chris,
>> do you think that's feasible?
>
> Really really feasible :)
>
> -Chris
>
> --
> http://nondot.org/sabre/
> http://llvm.org/
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

Chris Lattner-2
On Mar 31, 2008, at 5:35 PM, Evan Cheng wrote:
>>> MachineRegisterInfo tracks virtual register only.
>>
>> It works for vregs and pregs today.
>
> Ok! Fooled me with this comment:
>
> /// MachineRegisterInfo - Keep track of information for each virtual  
> register,
> /// including its register class.

Hrm, my tree [now] says:

/// MachineRegisterInfo - Keep track of information for virtual and  
physical
/// registers, including vreg register classes, use/def chains for  
registers,
/// etc.

maybe you need to update :-P

-Chris
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

dag-7
In reply to this post by Chris Lattner
On Monday 31 March 2008 18:55, Chris Lattner wrote:

> On Mon, 31 Mar 2008, Evan Cheng wrote:
> >> I just discovered that def_itterator (and presumably, reg_iterator)
> >> doesn't
> >> include implicit defs, for example at function calls for caller-save
> >> physical
> >> registers.  Guh.  I'm not sure if it should or not, but it's certainly
> >> necessary information in some cases.  Is this expected behavior, or an
> >> oversight?
>
> reg iterators will return everything that is in the function.  If the
> implicit operands haven't been added to the machieninstrs yet, then they
> won't be returned.

Hmm...this is definitely NOT true in my copy.  During register allocation
these implicit defs are not returned.  By then the instructions are most
definitely fully constructed.  :)

We have a very old copy of llvm.  Is it possible they got added sometime
after reg_iterators were created?

Also, just as a point of information, where would I go to find out if a
physical register is a caller-save or callee-save register?  The closest
thing I can find is in the .td files but no interface is generated (as far
as I can tell) to categorize physical registers according to calling
convention.

                                               -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

dag-7
On Tuesday 01 April 2008 10:47, David Greene wrote:

> > reg iterators will return everything that is in the function.  If the
> > implicit operands haven't been added to the machieninstrs yet, then they
> > won't be returned.
>
> Hmm...this is definitely NOT true in my copy.  During register allocation
> these implicit defs are not returned.  By then the instructions are most
> definitely fully constructed.  :)

Urk.  It seems things are worse than that, even.

By the time things hit regalloc, the def/use lists seem to be completely
out of date.  Instructions that exist in the function are not reflected in the
def lists, for example.  Simple register-to-register copies are completely
missed.  So far I've only discovered this to be the case for physical
registers, though that doesn't mean virtual register information isn't also
out of date.

Who constructs this information?  I don't see any interfaces in
MachineRegisterInfo to keep the information up to date as instructions
are added or deleted.  Do I need to depend on some Pass?

What does coalescing do with this information?  Does it update it as
intervals are merged and instructions are changed?  I thought
MachineRegisterInfo::replaceRegWith might handle this but it doesn't
update MachineRegisterInfo::VRegInfo.

                                                   -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

Evan Cheng-2
In reply to this post by dag-7

On Apr 1, 2008, at 8:47 AM, David Greene wrote:

> On Monday 31 March 2008 18:55, Chris Lattner wrote:
>> On Mon, 31 Mar 2008, Evan Cheng wrote:
>>>> I just discovered that def_itterator (and presumably, reg_iterator)
>>>> doesn't
>>>> include implicit defs, for example at function calls for caller-
>>>> save
>>>> physical
>>>> registers.  Guh.  I'm not sure if it should or not, but it's  
>>>> certainly
>>>> necessary information in some cases.  Is this expected behavior,  
>>>> or an
>>>> oversight?
>>
>> reg iterators will return everything that is in the function.  If the
>> implicit operands haven't been added to the machieninstrs yet, then  
>> they
>> won't be returned.
>
> Hmm...this is definitely NOT true in my copy.  During register  
> allocation
> these implicit defs are not returned.  By then the instructions are  
> most
> definitely fully constructed.  :)
>
> We have a very old copy of llvm.  Is it possible they got added  
> sometime
> after reg_iterators were created?

Not sure.

>
>
> Also, just as a point of information, where would I go to find out  
> if a
> physical register is a caller-save or callee-save register?  The  
> closest
> thing I can find is in the .td files but no interface is generated  
> (as far
> as I can tell) to categorize physical registers according to calling
> convention.

See X86RegisterInfo::getCalleeSavedRegs() etc.

Evan
>
>
>                                               -Dave
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

Chris Lattner
In reply to this post by dag-7
On Tue, 1 Apr 2008, David Greene wrote:

> On Tuesday 01 April 2008 10:47, David Greene wrote:
>>> reg iterators will return everything that is in the function.  If the
>>> implicit operands haven't been added to the machieninstrs yet, then they
>>> won't be returned.
>>
>> Hmm...this is definitely NOT true in my copy.  During register allocation
>> these implicit defs are not returned.  By then the instructions are most
>> definitely fully constructed.  :)
>
> Urk.  It seems things are worse than that, even.

You should try updating to mainline.  I have no idea what snapshot you
have.

Barring a serious bug, the use/def chains cannot get out of date.  When a
machineinstr is inserted into a function or when an operand is added to
the instr, it is automatically added to the register list.  There is no
way that these can get out of date, by design.

> By the time things hit regalloc, the def/use lists seem to be completely
> out of date.  Instructions that exist in the function are not reflected in the
> def lists, for example.  Simple register-to-register copies are completely
> missed.  So far I've only discovered this to be the case for physical
> registers, though that doesn't mean virtual register information isn't also
> out of date.

You'd have to debug it.

> Who constructs this information?  I don't see any interfaces in
> MachineRegisterInfo to keep the information up to date as instructions
> are added or deleted.  Do I need to depend on some Pass?

It is implicitly always up to date.  Start looking at
MachineOperand::setReg for example to see what happens when you change the
register an operand refers to.

> What does coalescing do with this information?  Does it update it as
> intervals are merged and instructions are changed?  I thought
> MachineRegisterInfo::replaceRegWith might handle this but it doesn't
> update MachineRegisterInfo::VRegInfo.

No passes need to update this info explicitly.

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: reg_iterator Caveats

dag-7
On Tuesday 01 April 2008 12:35, Chris Lattner wrote:

> On Tue, 1 Apr 2008, David Greene wrote:
> > On Tuesday 01 April 2008 10:47, David Greene wrote:
> >>> reg iterators will return everything that is in the function.  If the
> >>> implicit operands haven't been added to the machieninstrs yet, then
> >>> they won't be returned.
> >>
> >> Hmm...this is definitely NOT true in my copy.  During register
> >> allocation these implicit defs are not returned.  By then the
> >> instructions are most definitely fully constructed.  :)
> >
> > Urk.  It seems things are worse than that, even.
>
> You should try updating to mainline.  I have no idea what snapshot you
> have.

Yep, it's on my TODO list.

> Barring a serious bug, the use/def chains cannot get out of date.  When a
> machineinstr is inserted into a function or when an operand is added to
> the instr, it is automatically added to the register list.  There is no
> way that these can get out of date, by design.

Ok, I see the code in MachineOperand to do this.  Strange.  I've hacked around
it for the time being.  I'll double-check when we update.

                                                    -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev