This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Value Range Propagation Pass Status
- To: gcc at gcc dot gnu dot org
- Subject: Value Range Propagation Pass Status
- From: John Wehle <john at feith dot com>
- Date: Thu, 3 Feb 2000 19:35:41 -0500 (EST)
I've been working on a pass (when time has allowed :-) to track
and make use of value ranges associated with pseudo registers.
I have reasonably solid code which bootstraps on alpha, i386,
powerpc, and sparc. Make check has been run on i386, powerpc,
and sparc with no regression. A slightly older version of the
code was bootstrapped on hppa and make check ran with no regressions.
Things to do before submitting:
1) Currently the code exists as a patch to gcse.c and runs as part of gcse.
It needs to exist on its own and be moved into a seperate file. Any
recommendations on when value range propagation should be done? I was
thinking of running it twice. Once before gcse and once after loop.
2) The code needs documentation.
3) Possibly handle some additional cases.
4) Some of the backend casesi patterns could use tweaking in order to
allow the value range pass to determine what cases will never be
reached.
Actually, items 3 and 4 can probably be done after submitting the current
code. If there's interest I can post the existing code so that people can
kick the tires and comment.
Some silly examples of what it can do:
int
func (int a)
{
int b;
int i;
int j;
b = 0;
for (i = a; i < 10; i++)
for (j = i; j < 10; j++)
b += i * j;
return b;
}
compiled with -O2 on the x86 produces:
Normal gcc With value range
------------------- ----------------
pushl %ebp pushl %ebp
movl %esp, %ebp movl %esp, %ebp
movl 8(%ebp), %ecx | movl 8(%ebp), %eax
pushl %ebx pushl %ebx
xorl %ebx, %ebx xorl %ebx, %ebx
cmpl $9, %ecx | cmpl $9, %eax
jg .L4 jg .L4
.align 4 .align 4
.L6: .L6:
cmpl $9, %ecx | movl %eax, %edx
movl %ecx, %eax | movl %eax, %ecx
jg .L5 <
movl %ecx, %edx <
imull %edx, %edx imull %edx, %edx
.align 4 .align 4
.L10: .L10:
incl %eax <
addl %edx, %ebx <
addl %ecx, %edx <
cmpl $9, %eax <
jle .L10 <
.L5: <
incl %ecx incl %ecx
> addl %edx, %ebx
> addl %eax, %edx
cmpl $9, %ecx cmpl $9, %ecx
> jle .L10
> incl %eax
> cmpl $9, %eax
jle .L6 jle .L6
.L4: .L4:
movl %ebx, %eax movl %ebx, %eax
popl %ebx popl %ebx
leave leave
ret ret
Notice that the compare and jump at the beginning of L6 has been eliminated.
int
func (int a)
{
int b;
b = a;
if (b < 0)
b = 0;
switch (b & 0x03)
{
case 0:
return 0;
case 1:
return 1;
case 2:
return 2;
case 3:
return 3;
case 4:
return 4;
case 5:
return 5;
case 6:
return 6;
case 7:
return 7;
default:
return -1;
}
}
compiled with -O2 on the x86 produces:
Normal gcc With value range
------------------- ----------------
func: func:
pushl %ebp pushl %ebp
movl %esp, %ebp movl %esp, %ebp
movl 8(%ebp), %edx movl 8(%ebp), %edx
movl %edx, %eax movl %edx, %eax
shrl $31, %eax shrl $31, %eax
decl %eax decl %eax
andl %edx, %eax andl %edx, %eax
andl $3, %eax andl $3, %eax
cmpl $7, %eax <
ja .L13 <
jmp *.L14(,%eax,4) jmp *.L14(,%eax,4)
.align 4 .align 4
.section .rodata .section .rodata
.align 4 .align 4
.align 4 .align 4
.L14: .L14:
.long .L5 .long .L5
.long .L6 .long .L6
.long .L7 .long .L7
.long .L8 .long .L8
.long .L9 <
.long .L10 <
.long .L11 <
.long .L12 <
.text .text
.align 4 .align 4
.L5: .L5:
xorl %eax, %eax xorl %eax, %eax
jmp .L15 jmp .L15
.align 4 .align 4
.L6: .L6:
movl $1, %eax movl $1, %eax
jmp .L15 jmp .L15
.align 4 .align 4
.L7: .L7:
movl $2, %eax movl $2, %eax
jmp .L15 jmp .L15
.align 4 .align 4
.L8: .L8:
movl $3, %eax movl $3, %eax
jmp .L15 <
.align 4 <
.L9: <
movl $4, %eax <
jmp .L15 <
.align 4 <
.L10: <
movl $5, %eax <
jmp .L15 <
.align 4 <
.L11: <
movl $6, %eax <
jmp .L15 <
.align 4 <
.L12: <
movl $7, %eax <
jmp .L15 <
.align 4 <
.L13: <
movl $-1, %eax <
.L15: .L15:
leave leave
ret ret
Notice that the out of range check has been eliminated in addition to
those cases which will never occur.
Feedback, questions, comments, etc. welcomed.
-- John
-------------------------------------------------------------------------
| Feith Systems | Voice: 1-215-646-8000 | Email: john@feith.com |
| John Wehle | Fax: 1-215-540-5495 | |
-------------------------------------------------------------------------