Live Intervals Question

For the x86-64 target, I tried compiling a simple hello world. I don't
understand the live interval information.

Here's the machine instructions as dumped by LiveIntervalAnalysis:

********** MACHINEINSTRS **********
file hello.c line 3 b:
0 FNSTCW16m <fi#0>, 1, %NOREG, 0
FNSTCW16m <fi#0> 1 %mreg(0) 0
4 MOV8mi <fi#0>, 1, %NOREG, 1, 2
MOV8mi <fi#0> 1 %mreg(0) 1 2
8 FLDCW16m <fi#0>, 1, %NOREG, 0
FLDCW16m <fi#0> 1 %mreg(0) 0
12 ADJCALLSTACKDOWN 0, %ESP<imp-def>, %ESP<imp-use>
ADJCALLSTACKDOWN 0 %mreg(25)<d> %mreg(25)
16 %reg1024 = MOV8r0
MOV8r0 %reg1024<d>
20 %reg1025 = LEA64r %NOREG, 1, %NOREG,
<ga:initialized$$$CFE_id_cc092431_main>
LEA64r %reg1025<d> %mreg(0) 1 %mreg(0) <ga:initialized$$$CFE_id_cc092431_main>
24 %RDI = MOV64rr %reg1025<kill>
MOV64rr %mreg(78)<d> %reg1025
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>
36 ADJCALLSTACKUP 0, 0, %ESP<imp-def>, %ESP<imp-use>
ADJCALLSTACKUP 0 0 %mreg(25)<d> %mreg(25)
40 %reg1026<dead> = MOV32rr %EAX<kill>
MOV32rr %reg1026<d> %mreg(17)
44 %reg1027 = MOV32r0
MOV32r0 %reg1027<d>
48 %EAX = MOV32rr %reg1027<kill>, %RAX<imp-use,kill>, %RAX<imp-def>
MOV32rr %mreg(17)<d> %reg1027 %mreg(74) %mreg(74)<d>
52 RET %EAX<imp-use,kill>, %RAX<imp-use,kill>
RET %mreg(17) %mreg(74)

(The CFE_* stuff is from our frontend)

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@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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@50
%reg1026,0 = [42,43:0) 0@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.

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!

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.

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

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?

It's apparent that I don't understand the interaction between live intervals
and register aliases/sub registers, etc.

Help?

                                                   -Dave

28 %AL = MOV8rr %reg1024, %EAX
MOV8rr %mreg(2) %reg1024 %mreg(17)
32 CALL64pcrel32 ga:printf, %RDI, %RAX, %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
CALL64pcrel32 ga:printf %mreg(78) %mreg(74) %mreg(77) %mreg(79)
%mreg(81) %mreg(78) %mreg(66) %mreg(70) %mreg(42) %mreg(46)
%mreg(26) %mreg(27) %mreg(28) %mreg(29) %mreg(30) %mreg(31)
%mreg(32) %mreg(87) %mreg(34) %mreg(35) %mreg(36) %mreg(37)
%mreg(38) %mreg(39) %mreg(40) %mreg(41) %mreg(95) %mreg(96)
%mreg(103) %mreg(104) %mreg(105) %mreg(106) %mreg(107)
%mreg(108) %mreg(109) %mreg(110) %mreg(97) %mreg(98)
%mreg(99) %mreg(100) %mreg(101) %mreg(102) %mreg(17)

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@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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@50
%reg1026,0 = [42,43:0) 0@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 = MOV8rr %reg1024, %EAX
MOV8rr %mreg(2) %reg1024 %mreg(17)

So their live ranges start at 28+2.

2 CALL64pcrel32 ga:printf, %RDI, %RAX, %RCX<imp-def,dead>,

RAX is implicitly defined by the CALL instruction. So it starts at 32+2.

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.

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@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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@50

AL is marked dead. So it makes sense there is a gap between [30:31) and [34,42). It looks like EAX implicit def should be marked dead as well. So I think there is a bug there somewhere.

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, %RAX<imp-use,kill>, %RAX
MOV32rr %mreg(17) %reg1027 %mreg(74) %mreg(74)

Def of sub-register use and define its super-register(s). So RAX’s live range isn’t broken here.

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.

EAX,inf = [30,31:0)[34,42:1)[50,54:2) 0@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@50
%reg1026,0 = [42,43:0) 0@42
%reg1027,0 = [46,50:0) 0@?

40 %reg1026 = MOV32rr %EAX
MOV32rr %reg1026 %mreg(17)

While EAX is marked kill here, RAX is still alive. Again, this is because def of EAX r/m/w RAX. 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.

Evan

AH,inf = [30,42:0)[50,54:1) 0@? 1@?
AL,inf = [30,31:0)[34,42:1)[50,54:2) 0@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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@50

AL is marked dead. So it makes sense there is a gap between [30:31) and [34,42). It looks like EAX implicit def should be marked dead as well. So I think there is a bug there somewhere.

BTW, I am making some fixes to LiveIntervals so this may look different after my check-in. If it’s still buggy (I expect so), please file a bug. This doesn’t really affect codegen but it still should be examined.

Evan

Evan, thanks for responding so quickly.

> 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@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@30 1@? 2@50
> RAX,inf = [34,50:0)[50,54:1) 0@? 1@50
> %reg1026,0 = [42,43:0) 0@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@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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@50
%reg1026,0 = [42,43:0) 0@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

Once I get all this clarified in my head, I may or may not be doing some
fixes and other things in LiveIntervals myself. Any idea when your
changes will go in?

                                               -Dave

Ah, ah, ah. Ok, I think I see what you're getting at now. RAX is implicitly
used by the def of EAX because part of its value still exists after the
operation. So it's a read-modify-write of RAX. The final value in the
64 bit register is a combination of the upper bits of RAX and the new
value of EAX. So it's both an implicit use and an implicit def of RAX.

Is that the convention LiveIntervalAnalysis uses?

If it is, then why isn't there a similar implicit use of RAX and implicit def
of RAX at the def of AL? And similar implicit uses and defs of AX and
EAX (EAX is implicitly defined)?

No matter what the convention is, it strikes me that these two cases
(def of AL and def of EAX) should affect RAX in the same way. They
don't here and that seems wrong to me.

                                            -Dave

Evan, thanks for responding so quickly.

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@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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@50
%reg1026,0 = [42,43:0) 0@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@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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@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. :slight_smile:

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@30 1@? 2@50
RAX,inf = [34,50:0)[50,54:1) 0@? 1@50
%reg1026,0 = [42,43:0) 0@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->

(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

Some fixes are in. Once you file the bugs discussed earlier (and once I have some time), I'll fix the other issues.

Evan

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?

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.

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

Ah, ah, ah. Ok, I think I see what you're getting at now. RAX is implicitly
used by the def of EAX because part of its value still exists after the
operation. So it's a read-modify-write of RAX. The final value in the
64 bit register is a combination of the upper bits of RAX and the new
value of EAX. So it's both an implicit use and an implicit def of RAX.

Is that the convention LiveIntervalAnalysis uses?

Yes.

If it is, then why isn't there a similar implicit use of RAX and implicit def
of RAX at the def of AL? And similar implicit uses and defs of AX and
EAX (EAX is implicitly defined)?

This?
28 %AL<dead> = MOV8rr %reg1024<kill>, %EAX<imp-def>

I don't see imp-use and imp-def of RAX. The imp-def of EAX is not (at least it should not) be due to def of AL. There is something else going on here.

Evan

What was I smoking? :slight_smile: RAX isn't modified by the first MOV32rr. It's then r/m/w by the second MOV32rr. So it's perfectly correct for its live range to start at CALL and extend past both MOV32rr's. No bugzilla please. :slight_smile:

Evan