[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [language-experts] SSA like notation on a simple AST
|
From: |
Paulo César Pereira de Andrade |
|
Subject: |
Re: [language-experts] SSA like notation on a simple AST |
|
Date: |
Thu, 29 Mar 2012 14:11:11 -0300 |
Em 29 de março de 2012 06:33, Bruno Haible <address@hidden> escreveu:
> Hi Paulo,
Hi Bruno,
>> The SSA like notation should make it easy to picture what is being done,
>> and
>> make it easier to figure out if in a loop, if there is a jump, e.g. goto,
>> etc.
>>
>> A simple example could be represented as:
>>
>> void t(c#0) {
>> auto a#0, b#0;
>>
>> for (a#1 = b#1 = 0; a#2 < c#0; a#2++)
>> b#2 += a#2;
>>
>> print("%d\n", b#3);
>> }
>
> You mean this notation should be used by a programmer? Or do you only
> mean to indicate the internal representation of the compiler or
> interpreter?
This is as a representation of the internal structure, and also close
to the intended generic debug output.
For example, the above program in "very verbose mode" in the current
implementation:
-%<-
$ cat t.e
void t(c) {
auto a, b;
for (a = b = 0; a < c; a++)
b += a;
print("%d\n", b);
}
t(10);
$ ./econs -v2 t.e
nil()
L0: 0 ; void:void
enter 0 2 0 0 ; void:void
#note "t.e" 9 ; void:void
int 10 ; int8
pushv ; int8:int8
call t ; int8:dynamic
exit ; dynamic:dynamic
---------------
# t.e:9
0x7f20a829f122 xor %rdi,%rdi
0x7f20a829f125 mov $0x2,%esi
0x7f20a829f12a xor %rdx,%rdx
0x7f20a829f12d xor %rcx,%rcx
0x7f20a829f130 xor %r8,%r8
0x7f20a829f133 mov $0x478940,%eax
0x7f20a829f138 rex.W callq *%rax
0x7f20a829f13b mov $0xa,%r13d
0x7f20a829f141 mov 0x28(%rbx),%r10
0x7f20a829f145 lea 0x18(%r10),%rax
0x7f20a829f149 mov %rax,0x28(%rbx)
0x7f20a829f14d mov $0x1,%eax
0x7f20a829f152 mov %eax,(%r10)
0x7f20a829f155 mov %r13,0x8(%r10)
0x7f20a829f159 movabs $0x7f20a829f198,%r11
0x7f20a829f163 mov 0x28(%rbx),%r10
0x7f20a829f167 lea 0x30(%r10),%rax
0x7f20a829f16b mov %rax,0x28(%rbx)
0x7f20a829f16f xor %rax,%rax
0x7f20a829f172 mov %eax,0x18(%r10)
0x7f20a829f176 mov %eax,(%r10)
0x7f20a829f179 mov %r11,0x8(%r10)
0x7f20a829f17d mov 0x20(%rbx),%rax
0x7f20a829f181 mov %rax,0x20(%r10)
0x7f20a829f185 lea 0x18(%r10),%rax
0x7f20a829f189 mov %rax,0x20(%rbx)
0x7f20a829f18d jmpq 0x7f20a829f1b0 null:0
0x7f20a829f192 nopw 0x0(%rax,%rax,1)
0x7f20a829f198 movabs $0x486d80,%rax
0x7f20a829f1a2 rex.W callq *%rax
0x7f20a829f1a5 xor %rax,%rax
0x7f20a829f1a8 jmpq 0x7f20a829f670 null:0
0x7f20a829f1ad nopl (%rax)
t()
L0: 0
; use: 100
; c
; set: 111
; b
; a
; c
; dsts: L1 L2 ; void:void
enter 3 1 0 0 ; void:void
#note "t.e" 4 ; void:void
int 0 ; int8
sb b#1 ; int8:int8
sb a#1 ; int8:int8
push ; int8:int8
lb c#0 ; dynamic
lt ; int8/dynamic:uint8
jf L2 ; uint8:uint8
L1: 1
;-> a == 0
;-> a < c
;-> c > 0
; use: 111
; b
; a
; c
; set: 11
; b
; a
; phi: 11
; b
; a
; srcs: L0 L1
; dsts: L1 L2 ; uint8:void
#note "t.e" 5 ; void:void
lb b#2 ; dynamic
push ; dynamic:dynamic
lb a#2 ; dynamic
add ; dynamic/dynamic:dynamic
sb b#3 ; dynamic:dynamic
lb a#2 ; dynamic
inc ; dynamic:dynamic
sb a#3 ; dynamic:dynamic
push ; dynamic:dynamic
lb c#0 ; dynamic
lt ; dynamic/dynamic:uint8
jt L1 ; uint8:uint8
L2: 0
; use: 1
; b
; phi: 1
; b
; srcs: L0 L1 ; uint8:void
#note "t.e" 7 ; void:void
lb b#4 ; dynamic
push ; dynamic:dynamic
ll "%d\n" ; vector
push ; vector:vector
blt print 2 ; vector:dynamic
reti 2 ; dynamic:dynamic
---------------
# t.e:4
0x7f20a829f1b0 mov $0x3,%edi
0x7f20a829f1b5 mov $0x1,%esi
0x7f20a829f1ba xor %rdx,%rdx
0x7f20a829f1bd xor %rcx,%rcx
0x7f20a829f1c0 xor %r8,%r8
0x7f20a829f1c3 mov $0x478940,%eax
0x7f20a829f1c8 rex.W callq *%rax
0x7f20a829f1cb xor %r13,%r13
0x7f20a829f1ce mov 0x20(%rbx),%r10
0x7f20a829f1d2 mov $0x1,%eax
0x7f20a829f1d7 mov %eax,0x30(%r10)
0x7f20a829f1db mov %r13,0x38(%r10)
0x7f20a829f1df mov 0x20(%rbx),%r10
0x7f20a829f1e3 mov %eax,0x18(%r10)
0x7f20a829f1e7 mov %r13,0x20(%r10)
0x7f20a829f1eb mov 0x20(%rbx),%r10
0x7f20a829f1ef mov %eax,(%rbx)
0x7f20a829f1f1 mov %r13,0x8(%rbx)
0x7f20a829f1f5 movslq -0x30(%r10),%rax
0x7f20a829f1f9 cmp $0x1,%rax
0x7f20a829f1fd je 0x7f20a829f228 t.e:4
0x7f20a829f203 cmp $0x2,%rax
0x7f20a829f207 jne 0x7f20a829f240 t.e:4
0x7f20a829f20d movsd -0x28(%r10),%xmm9
0x7f20a829f213 cvtsi2sd %r13,%xmm8
0x7f20a829f218 ucomisd %xmm9,%xmm8
0x7f20a829f21d jae 0x7f20a829f5b0 t.e:7
0x7f20a829f223 jmpq 0x7f20a829f280 t.e:5
0x7f20a829f228 mov -0x28(%r10),%rax
0x7f20a829f22c cmp %rax,%r13
0x7f20a829f22f jge 0x7f20a829f5b0 t.e:7
0x7f20a829f235 jmpq 0x7f20a829f280 t.e:5
0x7f20a829f23a nopw 0x0(%rax,%rax,1)
0x7f20a829f240 movabs $0x479220,%rax
0x7f20a829f24a rex.W callq *%rax
0x7f20a829f24d movabs $0xfffffffffffffffe,%rdi
0x7f20a829f257 mov $0x4753d0,%eax
0x7f20a829f25c rex.W callq *%rax
0x7f20a829f25f movabs $0x47aa60,%r10
0x7f20a829f269 rex.WB callq *%r10
0x7f20a829f26c movslq 0x8(%rbx),%r13
0x7f20a829f270 test %r13,%r13
0x7f20a829f273 jne 0x7f20a829f5b0 t.e:7
0x7f20a829f279 nopl 0x0(%rax)
# t.e:5
0x7f20a829f280 mov 0x20(%rbx),%r10
0x7f20a829f284 movslq 0x30(%r10),%rax
0x7f20a829f288 cmp $0x1,%rax
0x7f20a829f28c jne 0x7f20a829f2f0 t.e:5
0x7f20a829f292 mov 0x38(%r10),%r13
0x7f20a829f296 movslq 0x18(%r10),%rax
0x7f20a829f29a cmp $0x1,%rax
0x7f20a829f29e je 0x7f20a829f2d0 t.e:5
0x7f20a829f2a4 cmp $0x2,%rax
0x7f20a829f2a8 jne 0x7f20a829f350 t.e:5
0x7f20a829f2ae movsd 0x20(%r10),%xmm9
0x7f20a829f2b4 cvtsi2sd %r13,%xmm8
0x7f20a829f2b9 addsd %xmm9,%xmm8
0x7f20a829f2be mov %eax,(%rbx)
0x7f20a829f2c0 movsd %xmm8,0x8(%rbx)
0x7f20a829f2c6 jmpq 0x7f20a829f3b0 t.e:5
0x7f20a829f2cb nopl 0x0(%rax,%rax,1)
0x7f20a829f2d0 mov 0x20(%r10),%rax
0x7f20a829f2d4 add %rax,%r13
0x7f20a829f2d7 jo 0x7f20a829f350 t.e:5
0x7f20a829f2dd mov $0x1,%eax
0x7f20a829f2e2 mov %eax,(%rbx)
0x7f20a829f2e4 mov %r13,0x8(%rbx)
0x7f20a829f2e8 jmpq 0x7f20a829f3b0 t.e:5
0x7f20a829f2ed nopl (%rax)
0x7f20a829f2f0 movslq 0x30(%r10),%rax
0x7f20a829f2f4 cmp $0x2,%rax
0x7f20a829f2f8 jne 0x7f20a829f350 t.e:5
0x7f20a829f2fe movsd 0x38(%r10),%xmm8
0x7f20a829f304 movslq 0x18(%r10),%rax
0x7f20a829f308 cmp $0x2,%rax
0x7f20a829f30c je 0x7f20a829f330 t.e:5
0x7f20a829f312 cmp $0x1,%rax
0x7f20a829f316 jne 0x7f20a829f350 t.e:5
0x7f20a829f31c mov 0x20(%r10),%rax
0x7f20a829f320 cvtsi2sd %rax,%xmm9
0x7f20a829f325 jmpq 0x7f20a829f338 t.e:5
0x7f20a829f32a nopw 0x0(%rax,%rax,1)
0x7f20a829f330 movsd 0x20(%r10),%xmm9
0x7f20a829f336 xchg %ax,%ax
0x7f20a829f338 addsd %xmm9,%xmm8
0x7f20a829f33d mov $0x2,%eax
0x7f20a829f342 mov %eax,(%rbx)
0x7f20a829f344 movsd %xmm8,0x8(%rbx)
0x7f20a829f34a jmpq 0x7f20a829f3b0 t.e:5
0x7f20a829f34f nop
0x7f20a829f350 mov $0x2,%edi
0x7f20a829f355 mov $0x4753d0,%eax
0x7f20a829f35a rex.W callq *%rax
0x7f20a829f35d movabs $0x479220,%r10
0x7f20a829f367 rex.WB callq *%r10
0x7f20a829f36a mov $0x1,%edi
0x7f20a829f36f mov $0x4753d0,%eax
0x7f20a829f374 rex.W callq *%rax
0x7f20a829f377 movabs $0x47af80,%r10
0x7f20a829f381 rex.WB callq *%r10
0x7f20a829f384 movslq (%rbx),%rax
0x7f20a829f387 cmp $0x1,%rax
0x7f20a829f38b jne 0x7f20a829f3a0 t.e:5
0x7f20a829f391 mov 0x8(%rbx),%r13
0x7f20a829f395 jmpq 0x7f20a829f3b0 t.e:5
0x7f20a829f39a nopw 0x0(%rax,%rax,1)
0x7f20a829f3a0 cmp $0x2,%rax
0x7f20a829f3a4 jne 0x7f20a829f3b0 t.e:5
0x7f20a829f3aa movsd 0x8(%rbx),%xmm8
0x7f20a829f3b0 mov 0x20(%rbx),%r10
0x7f20a829f3b4 movslq (%rbx),%rax
0x7f20a829f3b7 cmp $0x1,%rax
0x7f20a829f3bb jne 0x7f20a829f3d0 t.e:5
0x7f20a829f3c1 mov %eax,0x30(%r10)
0x7f20a829f3c5 mov %r13,0x38(%r10)
0x7f20a829f3c9 jmpq 0x7f20a829f400 t.e:5
0x7f20a829f3ce xchg %ax,%ax
0x7f20a829f3d0 cmp $0x2,%rax
0x7f20a829f3d4 jne 0x7f20a829f3f0 t.e:5
0x7f20a829f3da mov %eax,0x30(%r10)
0x7f20a829f3de movsd %xmm8,0x38(%r10)
0x7f20a829f3e4 jmpq 0x7f20a829f400 t.e:5
0x7f20a829f3e9 nopl 0x0(%rax)
0x7f20a829f3f0 add $0x30,%r10
0x7f20a829f3f4 mov %r10,%rdi
0x7f20a829f3f7 mov $0x476a10,%eax
0x7f20a829f3fc rex.W callq *%rax
0x7f20a829f3ff nop
0x7f20a829f400 mov 0x20(%rbx),%r10
0x7f20a829f404 movslq 0x18(%r10),%rax
0x7f20a829f408 cmp $0x1,%rax
0x7f20a829f40c jne 0x7f20a829f438 t.e:5
0x7f20a829f412 mov 0x20(%r10),%r13
0x7f20a829f416 add $0x1,%r13
0x7f20a829f41a jo 0x7f20a829f470 t.e:5
0x7f20a829f420 mov %r13,0x20(%r10)
0x7f20a829f424 mov $0x1,%eax
0x7f20a829f429 mov %eax,(%rbx)
0x7f20a829f42b mov %r13,0x8(%rbx)
0x7f20a829f42f jmpq 0x7f20a829f4b8 t.e:5
0x7f20a829f434 nopl 0x0(%rax)
0x7f20a829f438 cmp $0x2,%rax
0x7f20a829f43c jne 0x7f20a829f470 t.e:5
0x7f20a829f442 movsd 0x20(%r10),%xmm8
0x7f20a829f448 movabs $0x3ff0000000000000,%r11
0x7f20a829f452 movq %r11,%xmm10
0x7f20a829f457 addsd %xmm10,%xmm8
0x7f20a829f45c movsd %xmm8,0x20(%r10)
0x7f20a829f462 mov %eax,(%rbx)
0x7f20a829f464 movsd %xmm8,0x8(%rbx)
0x7f20a829f46a jmpq 0x7f20a829f4b8 t.e:5
0x7f20a829f46f nop
0x7f20a829f470 mov $0x1,%edi
0x7f20a829f475 mov $0x4753d0,%eax
0x7f20a829f47a rex.W callq *%rax
0x7f20a829f47d movabs $0x47b970,%r10
0x7f20a829f487 rex.WB callq *%r10
0x7f20a829f48a mov $0x1,%edi
0x7f20a829f48f mov $0x476cc0,%eax
0x7f20a829f494 rex.W callq *%rax
0x7f20a829f497 movslq (%rbx),%rax
0x7f20a829f49a cmp $0x1,%rax
0x7f20a829f49e jne 0x7f20a829f4a8 t.e:5
0x7f20a829f4a4 mov 0x8(%rbx),%r13
0x7f20a829f4a8 cmp $0x2,%rax
0x7f20a829f4ac jne 0x7f20a829f4b8 t.e:5
0x7f20a829f4b2 movsd 0x8(%rbx),%xmm8
0x7f20a829f4b8 mov 0x20(%rbx),%r10
0x7f20a829f4bc movslq (%rbx),%rax
0x7f20a829f4bf cmp $0x1,%rax
0x7f20a829f4c3 jne 0x7f20a829f518 t.e:5
0x7f20a829f4c9 mov 0x8(%rbx),%r13
0x7f20a829f4cd movslq -0x30(%r10),%rax
0x7f20a829f4d1 cmp $0x1,%rax
0x7f20a829f4d5 je 0x7f20a829f500 t.e:5
0x7f20a829f4db cmp $0x2,%rax
0x7f20a829f4df jne 0x7f20a829f570 t.e:5
0x7f20a829f4e5 movsd -0x28(%r10),%xmm9
0x7f20a829f4eb cvtsi2sd %r13,%xmm8
0x7f20a829f4f0 ucomisd %xmm8,%xmm9
0x7f20a829f4f5 ja 0x7f20a829f280 t.e:5
0x7f20a829f4fb jmpq 0x7f20a829f5b0 t.e:7
0x7f20a829f500 mov -0x28(%r10),%rax
0x7f20a829f504 cmp %rax,%r13
0x7f20a829f507 jl 0x7f20a829f280 t.e:5
0x7f20a829f50d jmpq 0x7f20a829f5b0 t.e:7
0x7f20a829f512 nopw 0x0(%rax,%rax,1)
0x7f20a829f518 movslq (%rbx),%rax
0x7f20a829f51b cmp $0x2,%rax
0x7f20a829f51f jne 0x7f20a829f570 t.e:5
0x7f20a829f525 movsd 0x8(%rbx),%xmm8
0x7f20a829f52b movslq -0x30(%r10),%rax
0x7f20a829f52f cmp $0x2,%rax
0x7f20a829f533 je 0x7f20a829f558 t.e:5
0x7f20a829f539 cmp $0x1,%rax
0x7f20a829f53d jne 0x7f20a829f570 t.e:5
0x7f20a829f543 mov -0x28(%r10),%rax
0x7f20a829f547 cvtsi2sd %rax,%xmm9
0x7f20a829f54c jmpq 0x7f20a829f560 t.e:5
0x7f20a829f551 nopl 0x0(%rax)
0x7f20a829f558 movsd -0x28(%r10),%xmm9
0x7f20a829f55e xchg %ax,%ax
0x7f20a829f560 ucomisd %xmm8,%xmm9
0x7f20a829f565 ja 0x7f20a829f280 t.e:5
0x7f20a829f56b jmpq 0x7f20a829f5b0 t.e:7
0x7f20a829f570 movabs $0x479220,%rax
0x7f20a829f57a rex.W callq *%rax
0x7f20a829f57d movabs $0xfffffffffffffffe,%rdi
0x7f20a829f587 mov $0x4753d0,%eax
0x7f20a829f58c rex.W callq *%rax
0x7f20a829f58f movabs $0x47a7f0,%r10
0x7f20a829f599 rex.WB callq *%r10
0x7f20a829f59c movslq 0x8(%rbx),%r13
0x7f20a829f5a0 test %r13,%r13
0x7f20a829f5a3 jne 0x7f20a829f280 t.e:5
0x7f20a829f5a9 nopl 0x0(%rax)
# t.e:7
0x7f20a829f5b0 mov 0x20(%rbx),%r10
0x7f20a829f5b4 mov 0x28(%rbx),%r11
0x7f20a829f5b8 lea 0x18(%r11),%rax
0x7f20a829f5bc mov %rax,0x28(%rbx)
0x7f20a829f5c0 movslq 0x30(%r10),%rax
0x7f20a829f5c4 cmp $0x1,%rax
0x7f20a829f5c8 jne 0x7f20a829f5e0 t.e:7
0x7f20a829f5ce mov 0x38(%r10),%r13
0x7f20a829f5d2 mov %eax,(%r11)
0x7f20a829f5d5 mov %r13,0x8(%r11)
0x7f20a829f5d9 jmpq 0x7f20a829f620 t.e:7
0x7f20a829f5de xchg %ax,%ax
0x7f20a829f5e0 cmp $0x2,%rax
0x7f20a829f5e4 jne 0x7f20a829f600 t.e:7
0x7f20a829f5ea movsd 0x38(%r10),%xmm8
0x7f20a829f5f0 mov %eax,(%r11)
0x7f20a829f5f3 movsd %xmm8,0x8(%r11)
0x7f20a829f5f9 jmpq 0x7f20a829f620 t.e:7
0x7f20a829f5fe xchg %ax,%ax
0x7f20a829f600 mov %r11,%r13
0x7f20a829f603 mov $0x2,%edi
0x7f20a829f608 mov $0x4753d0,%eax
0x7f20a829f60d rex.W callq *%rax
0x7f20a829f610 mov %r13,%rdi
0x7f20a829f613 mov $0x476e10,%eax
0x7f20a829f618 rex.W callq *%rax
0x7f20a829f61b nopl 0x0(%rax,%rax,1)
0x7f20a829f620 mov $0x60000014,%eax
0x7f20a829f625 mov %eax,(%rbx)
0x7f20a829f627 mov $0x134a7a0,%eax
0x7f20a829f62c mov %rax,0x8(%rbx)
0x7f20a829f630 mov 0x28(%rbx),%r10
0x7f20a829f634 lea 0x18(%r10),%rax
0x7f20a829f638 mov %rax,0x28(%rbx)
0x7f20a829f63c mov %r10,%rdi
0x7f20a829f63f mov $0x476e10,%eax
0x7f20a829f644 rex.W callq *%rax
0x7f20a829f647 mov $0x2c,%edi
0x7f20a829f64c mov $0x2,%esi
0x7f20a829f651 mov $0x479750,%eax
0x7f20a829f656 rex.W callq *%rax
0x7f20a829f659 mov $0x2,%edi
0x7f20a829f65e mov $0x479950,%eax
0x7f20a829f663 rex.W callq *%rax
0x7f20a829f666 rex.W jmpq *%rax
45
-%<-
It is not really slow. For several usages it runs at equivalent "gcc -O0"
C code, unless falling back too much to builtins, but it can be up to
10x faster and simpler, and that is my goal :-). If using statically typed
variables it generates simpler jit, but still has too much overhead.
> In any case, I don't see how an operator '++' can apply here. Don't you
> need to resolve operator '++' first? So that you get
> a#3 = a#2 + 1
Yes. It needs a transformation like you suggested (possibly hidden
transformation for the sake of debug output readability), or if the value
is not used, converted to prefix increment.
> SSA is helpful for register allocation, range propagation, and similar
> optimizations [1]. If your compiler is doing these kinds of optimizations,
> SSA can help.
As you can see above, the jit generates too much bloat when checking
types and inlining integer and float operations and fallback for other types.
Also only on simple sequential code it keeps values in registers. The new
implementation should from start be "jit friendly" and know about register
allocation.
> Bruno
>
> [1] http://en.wikipedia.org/wiki/Static_single_assignment_form
Thanks,
Paulo