[LLVMdev] Live Intervals Question

David Greene dag at cray.com
Tue Jun 26 12:57:22 PDT 2007


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?

> > 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.

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?

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.

> 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.

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.

> 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:

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?"

> 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.

                                                -Dave



More information about the llvm-dev mailing list