[LLVMdev] Live Intervals Question

Evan Cheng evan.cheng at apple.com
Tue Jun 26 19:08:12 PDT 2007


On Jun 26, 2007, at 12:57 PM, David Greene wrote:

> Evan, thanks for responding so quickly.
>
> On Tuesday 26 June 2007 14:11, Evan Cheng wrote:
>> On Jun 26, 2007, at 11:20 AM, David A. Greene wrote:
>>> 28	%AL<dead> = MOV8rr %reg1024<kill>, %EAX<imp-def>
>>> MOV8rr	%mreg(2)<d>	%reg1024	%mreg(17)<d>
>>> 32	CALL64pcrel32 <ga:printf>, %RDI<kill>, %RAX<imp-def>, %RCX<imp-
>>> def,dead>,
>>> %RDX<imp-def,dead>, %RSI<imp-def,dead>, %RDI<imp-def,dead>,
>>> %R8<imp-def,dead>, %R9<imp-def,dead>, %R10<imp-def,dead>, %R11<imp-
>>> def,dead>,
>>> %FP0<imp-def,dead>, %FP1<imp-def,dead>, %FP2<imp-def,dead>,
>>> %FP3<imp-def,dead>, %FP4<imp-def,dead>, %FP5<imp-def,dead>,
>>> %FP6<imp-def,dead>, %ST(0)<imp-def,dead>, %MM0<imp-def,dead>,
>>> %MM1<imp-def,dead>, %MM2<imp-def,dead>, %MM3<imp-def,dead>,
>>> %MM4<imp-def,dead>, %MM5<imp-def,dead>, %MM6<imp-def,dead>,
>>> %MM7<imp-def,dead>, %XMM0<imp-def,dead>, %XMM1<imp-def,dead>,
>>> %XMM2<imp-def,dead>, %XMM3<imp-def,dead>, %XMM4<imp-def,dead>,
>>> %XMM5<imp-def,dead>, %XMM6<imp-def,dead>, %XMM7<imp-def,dead>,
>>> %XMM8<imp-def,dead>, %XMM9<imp-def,dead>, %XMM10<imp-def,dead>,
>>> %XMM11<imp-def,dead>, %XMM12<imp-def,dead>, %XMM13<imp-def,dead>,
>>> %XMM14<imp-def,dead>, %XMM15<imp-def,dead>, %EAX<imp-def>
>>> CALL64pcrel32	<ga:printf>	%mreg(78)	%mreg(74)<d>	%mreg(77)<d>	%mreg
>>> (79)<d>
>>> %mreg(81)<d>	%mreg(78)<d>	%mreg(66)<d>	%mreg(70)<d>	%mreg(42)<d>	%
>>> mreg(46)<d>
>>> %mreg(26)<d>	%mreg(27)<d>	%mreg(28)<d>	%mreg(29)<d>	%mreg(30)<d>	%
>>> mreg(31)<d>
>>> %mreg(32)<d>	%mreg(87)<d>	%mreg(34)<d>	%mreg(35)<d>	%mreg(36)<d>	%
>>> mreg(37)<d>
>>> %mreg(38)<d>	%mreg(39)<d>	%mreg(40)<d>	%mreg(41)<d>	%mreg(95)<d>	%
>>> mreg(96)<d>
>>> %mreg(103)<d>	%mreg(104)<d>	%mreg(105)<d>	%mreg(106)<d>	%mreg(107) 
>>> <d>
>>> %mreg(108)<d>	%mreg(109)<d>	%mreg(110)<d>	%mreg(97)<d>	%mreg(98)<d>
>>> %mreg(99)<d>	%mreg(100)<d>	%mreg(101)<d>	%mreg(102)<d>	%mreg(17)<d>
>>>
>>>
>>> Some selected live interval information:
>>>
>>> ********** INTERVALS **********
>>> AH,inf = [30,42:0)[50,54:1)  0@? 1@?
>>> AL,inf = [30,31:0)[34,42:1)[50,54:2)  0 at 30 1@? 2@?
>>> AX,inf = [30,42:0)[50,54:1)  0@? 1@?
>>> EAX,inf = [30,31:0)[34,42:1)[50,54:2)  0 at 30 1@? 2 at 50
>>> RAX,inf = [34,50:0)[50,54:1)  0@? 1 at 50
>>> %reg1026,0 = [42,43:0)  0 at 42
>>> %reg1027,0 = [46,50:0)  0@?
>>>
>>> Here's where the non-understanding happens.  Why are the live
>>> ranges for the
>>> A machine registers so different?  AL is defined in slot 30, which
>>> is an
>>> implicit def of AX, EAX and RAX due to aliasing, right?  Only EAX
>>> is listed as
>>> an explicit def in that instruction, though everything except RAX
>>> is show to
>>> have a live interval starting at slot 30.
>>
>> EAX and its sub-registers are defined by the MOV8rr instruction
>>
>> implicitly:
>>> 28	%AL<dead> = MOV8rr %reg1024<kill>, %EAX<imp-def>
>>> MOV8rr	%mreg(2)<d>	%reg1024	%mreg(17)<d>
>>
>> So their live ranges start at 28+2.
>
> Yep, this makes sense to me.  But AL is a subregister of RAX too,
> so shouldn't it have a live interval that starts there as well?

Def of a register also defines its sub-registers. Not its super- 
registers. RAX is not available at this time since only part of it is  
defined.

>
>>> 2	CALL64pcrel32 <ga:printf>, %RDI<kill>, %RAX<imp-def>, %RCX<imp-
>>> def,dead>,
>>
>> RAX is implicitly defined by the CALL instruction. So it starts at  
>> 32+2.
>
> Yes, there is a live range that starts there, but as I said above,  
> there
> should be _another_ one that starts at 28+2.
>
> Or I'm really not understanding something, which is entirely possible.
>
>>> So two questions come up here: why isn't RAX included at the start
>>> of this
>>> live interval and why is AH included in this interval -- it's not
>>> defined at
>>> all!
>>
>> Sure it is. AH is a sub-register of EAX.
>
> But EAX is only _implicitly_ defined because AL is _explicitly_  
> defined.
> EAX aliases AL so there does have to be a def of EAX there.  But  
> there is no
> need to start a live range for AH.  Otherwise you're unnecessarily
> constraining the register allocator.

It's not clear to me where the implicit def of EAX comes from. Need  
to walk through the example. The def of AL should not introduce the  
implicit def. It could introduce a implicit-use and an implicit-def  
of EAX if EAX was already defined at that point (r/m/w of a super- 
reg). If you could walk through the LiveVariables to find out why imp- 
def of EAX is introduced, let me know. If it's a bug, please file it.

However, since there is a def of EAX, there is a def of AH.

>
> For example, say there as a char that lived over this instruction.   
> It could
> live in AH, but not if AH is defined here.
>
> I should think that a def would only apply to aliases of a  
> register, not to
> all subregisters of aliases of the register.  In other words, it's  
> not a
> transitive operation.
>
>>> Then we get to the call to printf.  This defines EAX as a return
>>> value.  So
>>> again we get another interval starting at slot 34.  This include
>>> AL, EAX
>>> and RAX.  Why not AX and AH?  I suppose because they have intervals
>>> that extend from slot 30 to slot 42.  That doesn't make any sense
>>> to me
>>> at all.
>>
>> I see this:
>>
>> ********** INTERVALS **********
>> AH,inf = [30,42:0)[50,54:1)  0@? 1@?
>> AL,inf = [30,31:0)[34,42:1)[50,54:2)  0 at 30 1@? 2@?
>> AX,inf = [30,42:0)[50,54:1)  0@? 1@?
>> EAX,inf = [30,31:0)[34,42:1)[50,54:2)  0 at 30 1@? 2 at 50
>> RAX,inf = [34,50:0)[50,54:1)  0@? 1 at 50
>>
>> AL is marked dead. So it makes sense there is a gap between [30:31)
>> and [34,42).
>
> Agreed.  Setting AL here is part of the ABI.
>
>> It looks like EAX implicit def should be marked dead as
>> well. So I think there is a bug there somewhere.
>
> Probably.  I'm not so familiar with how ABI issues are handled.  AL  
> is passed
> to printf as a hidden argument.  It's marked dead here:
>
> 28      %AL<dead> = MOV8rr %reg1024<kill>, %EAX<imp-def>
> MOV8rr  %mreg(2)<d>     %reg1024        %mreg(17)<d>
>
> But it's really dead at the point right after the call.  I think  
> the range
> [30,31) is correct, as far as I understand the slat numbering scheme.
> EAX has the same range, which seems correct.  I don't know what you
> mean when you say EAX should be marked dead.  It is, as far as live
> interval analysis is concerned, because it has the correct live range.
>
> Do you mean that it should be listed as dead in the printout of the  
> CALL
> instruction?   I don't know.  How should this be interacting with  
> the return
> value semantics?

If AL is passed to printf as a argument, then there is a bug with  
CALL64pcrel32. I don't see a implicit-use of AL. That's why AL is  
marked dead because there is no use. Please file a bug. Is this a  
Linux only ABI issue? I think it has something to do with vararg  
functions but my memory about it is fuzzy.


>
> What I was questioning was whether AX and RAX should also have
> the same range as EAX and AL, since they alias AL.  Again, AH  
> shouldn't
> be affected since there shouldn't be a range for AH in the first  
> place.
>
> They're all dead because printf redefines EAX with its return value.
>
> I would say the ranges for AX and RAX indicate a bug.  Do you agree?
>
>>> At slot 42 all of the A registers EXCEPT RAX die (last use).
>>> Again, what's
>>> the deal with RAX?  EAX is redefined just a few instructions later,
>>> which
>>> should kill RAX.  The [34,50:0)[50,54:1)  interval for RAX is just
>>> weird.  Why
>>> isn't it [34,54)?
>>
>> 48	%EAX = MOV32rr %reg1027<kill>, %RAX<imp-use,kill>, %RAX<imp-def>
>> MOV32rr	%mreg(17)<d>	%reg1027	%mreg(74)	%mreg(74)<d>
>>
>> Def of sub-register use and define its super-register(s).
>
> I can't quite parse that.

Definition of a sub-register implicitly read and write its super- 
registers.

>
>> So RAX's live range isn't broken here.
>
> How is there an implicit use of RAX here?  EAX is dead at slot 42.   
> RAX
> should be too.  I agree there's an implicit def.  That starts a new  
> live range
> for RAX.

CALL %RAX<imp-def>, %EAX<imp-def>...
reg1026 = MOV32rr %EAX<kill>
%EAX = MOV32rr %reg1027<kill>, %RAX<imp-use,kill>,%RAX<imp-def>

Ok, live variables is being overly conservative here. Nothing between  
CALL and the second MOV32rr read RAX so there is no reason to extend  
the live range beyond the first move. Bugzilla please. :-)

>
> I'm missing something fundamental here.  What is it?
>
>>> Finally, according to the above live interval information,
>>> registers 1026 and
>>> 1027 have live ranges that overlap RAX.  That's just totally bogus
>>> as can
>>> be seen simply by reading the machine instructions.  EAX and all  
>>> other
>>> A registers are last used at instruction 40 and EAX is not defined
>>> again
>>> until instruction 48, which is the last use of register 1027.  The
>>> move to
>>> register 1026 is entirely unnecessary -- why is it even there?
>>
>> Move to r1026 is marked dead. This is the artifact of translating
>> CopyFromReg (of the call result) of EAX. It's harmless.
>
> So it will get removed sometime later on?  It's worrisome that this  
> shows up
> during register allocate because it adds candidates to color that  
> don't have
> to be colored and it adds edges to the graph.  It's definitely not  
> harmless.

Copy coalescer should eliminate it.

>
>> EAX,inf = [30,31:0)[34,42:1)[50,54:2)  0 at 30 1@? 2 at 50
>> RAX,inf = [34,50:0)[50,54:1)  0@? 1 at 50
>> %reg1026,0 = [42,43:0)  0 at 42
>> %reg1027,0 = [46,50:0)  0@?
>>
>> 40	%reg1026<dead> = MOV32rr %EAX<kill>
>> MOV32rr	%reg1026<d>	%mreg(17)
>>
>> While EAX is marked kill here, RAX is still alive.
>
> How can this be when there's no further use of RAX later on?  There's
> an implicit use here:

Discussed earlier.

>
> 52      RET %EAX<imp-use,kill>, %RAX<imp-use,kill>
>
> But again, this value of EAX is the one defined by instruction 48:
>
> 48      %EAX = MOV32rr %reg1027<kill>, %RAX<imp-use,kill>, %RAX<imp- 
> def>
>
> (the implicit use of RAX makes no sense to me here)
>
> Any value RAX may have had was destroyed at this point.
>
>> Again, this is  because def of EAX r/m/w RAX.
>
> What does "r/m/w" mean?  "Read-modify-write?"

Right.

>
>> It does not terminate RAX live range.
>> The important thing here is reg1027 does not overlap EAX and the
>> magic of coalescer join them together.
>
> That's true, 1027 does not overlap EAX.  But there's an overlap  
> between 1027
> and RAX, which translates into an edge in a graph coloring register  
> allocator.
> That's kind of weird because they're in different register  
> classes.  I suppose
> I could check for this case and not add the edge but I would have  
> expected
> that the overlap wouldn't exist in the first place.

Again. Due to bug discussed earlier. In practice this does not hurt  
the linear scan allocator. But it may be an issue for other  
allocators so it should be fixed.

Evan

>
>                                                 -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev




More information about the llvm-dev mailing list