thr3ads.net - llvm dev - [LLVMdev] Linearscan allocator bug? [Jun 2004]

If this information is useful, please help other people find it:
Share via:

Vladimir Prus

2004-Jun-22 09:03 UTC

[LLVMdev] Linearscan allocator bug?

Folks, 
I'm running into something which looks like a bug in linearscan allocator.
Of
course I can't be 100% sure it's not some unobvious mistake on my part,
so
I'd like to hear your opinion.

First, I attach two files -- LLVM asm and the asm for my target. The problem 
with assembler is: on line 171 it uses register gr2, which is copied from gr6 
above, on line 161. The only predecessor of this basic block is jump on line 
90. The problem is that gr6 is not initialized in the interval from the 
function entry till the jump.

I also attach the debug dumps from my backend. 

The basic block in question is shortcirc_done.1 (line 198 in the log). It 
starts with:

    %reg1060 = phi %reg1032, mbb<shortcirc_next.0.selectcont.selectcont,

The predecessor is at line 155 and the register 1032 is assigned a value on 
line 140 (in shortcirc_next.0.selectcont): 

    %reg1032 = move %reg103

After register allocation the code in shortcirc_done.1 is (line 334):

    %gr2 = move %gr6

the predecessor in at line 285 and the code in shortcirc_next.0.selectcont is
(line 268)

    %gr4 = move %gr2

while I'd expect destination register should be gr6.

In fact, gr6 is first used here (line 289):

        if <>0 goto %disp(label shortcirc_done.1)
	%gr2 = move %gr4
	%gr5 = move %gr1
	%gr6 = move %gr4
	%gr1 = move %gr1

So, it's possible that jump goes to shortcirc_done.1 which then uses gr6 and
gets back results. 

Any ideas?

- Volodya
-------------- next part --------------
target endian = little
target pointersize = 32
%.str_1 = internal constant [32 x sbyte] c"Boolean Not: %d %d %d %d %d
%d\0A\00"		; <[32 x sbyte]*> [#uses=1]

implementation   ; Functions:

declare int %printf(sbyte*, ...)

void %testBooleanNot(int %A, int %B, int %C, int %D) {
entry:
	%tmp.3 = setlt int %A, 1		; <bool> [#uses=2]
	%tmp.4 = cast bool %tmp.3 to int		; <int> [#uses=2]
;	br bool %tmp.3, label %shortcirc_done.0, label %shortcirc_next.0
        br label %shortcirc_next.0

shortcirc_next.0:		; preds = %entry
	%tmp.9 = setlt int %C, 1		; <bool> [#uses=2]
	%tmp.111 = cast bool %tmp.9 to int		; <int> [#uses=2]
	%tmp.132 = setlt int %B, 1		; <bool> [#uses=1]
	%tmp.143 = cast bool %tmp.132 to int		; <int> [#uses=2]
	br bool %tmp.9, label %shortcirc_done.1, label %shortcirc_next.1

;shortcirc_done.0:		; preds = %entry
;	%tmp.13 = setlt int %B, 1		; <bool> [#uses=1]
;	%tmp.14 = cast bool %tmp.13 to int		; <int> [#uses=2]
;	%tmp.16 = setlt int %C, 1		; <bool> [#uses=1]
;	br bool %tmp.16, label %shortcirc_done.1, label %shortcirc_next.1

shortcirc_next.1:		; preds = %shortcirc_next.0, %shortcirc_done.0
	%tmp.11.0 = phi int [ %tmp.111, %shortcirc_next.0 ]		; <int> [#uses=1]
	%tmp.14.0 = phi int [ %tmp.143, %shortcirc_next.0 ]		; <int> [#uses=1]
	%tmp.19 = setlt int %D, 1		; <bool> [#uses=1]
	%tmp.215 = cast bool %tmp.19 to int		; <int> [#uses=1]
	%tmp.08 = call int (sbyte*, ...)* %printf( sbyte* getelementptr ([32 x sbyte]* 
%.str_1, long 0, long 0), int %tmp.4, int %tmp.11.0, int 0, int %tmp.14.0, int
0, int %tmp.215 )		; <int> [#uses=0]
	ret void

shortcirc_done.1:		; preds = %shortcirc_next.0, %shortcirc_done.0
	%tmp.11.1 = phi int [ %tmp.111, %shortcirc_next.0 ]		; <int> [#uses=1]
	%tmp.14.1 = phi int [ %tmp.143, %shortcirc_next.0 ]		; <int> [#uses=1]
	%tmp.0 = call int (sbyte*, ...)* %printf( sbyte* getelementptr ([32 x sbyte]* 
%.str_1, long 0, long 0), int %tmp.4, int %tmp.11.1, int 0, int %tmp.14.1, int
0, int 1 )		; <int> [#uses=0]
	ret void
}

int %main() {
entry:
	call void %__main( )
	call void %testBooleanNot( int 1, int 2, int -3, int 5 )
	ret int 0
}

declare void %__main()
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.s
Type: text/x-c++src
Size: 4117 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20040622/7a1c9d23/attachment.c>
-------------- next part --------------
target endian = little
target pointersize = 32
%.str_1 = internal constant [32 x sbyte] c"Boolean Not: %d %d %d %d %d
%d\0A\00"		; <[32 x sbyte]*> [#uses=3]

implementation   ; Functions:

declare int %printf(sbyte*, ...)

void %testBooleanNot(int %A, int %B, int %C, int %D) {
entry:
	%tmp.3 = setlt int %A, 1		; <bool> [#uses=1]
	br bool %tmp.3, label %entry.selecttrue, label %entry.selectcont

entry.selecttrue:		; preds = %entry
	br label %entry.selectcont

entry.selectcont:		; preds = %entry.selecttrue, %entry
	phi bool [ true, %entry.selecttrue ], [ false, %entry ]		; <bool>:0
[#uses=1]
	%tmp.4 = cast bool %0 to int		; <int> [#uses=2]
	br label %shortcirc_next.0

shortcirc_next.0:		; preds = %entry.selectcont
	%tmp.9 = setlt int %C, 1		; <bool> [#uses=1]
	br bool %tmp.9, label %shortcirc_next.0.selecttrue, label
%shortcirc_next.0.selectcont

shortcirc_next.0.selecttrue:		; preds = %shortcirc_next.0
	br label %shortcirc_next.0.selectcont

shortcirc_next.0.selectcont:		; preds = %shortcirc_next.0.selecttrue,
%shortcirc_next.0
	phi bool [ true, %shortcirc_next.0.selecttrue ], [ false, %shortcirc_next.0 ]	
; <bool>:1 [#uses=2]
	%tmp.111 = cast bool %1 to int		; <int> [#uses=2]
	%tmp.132 = setlt int %B, 1		; <bool> [#uses=1]
	br bool %tmp.132, label %shortcirc_next.0.selectcont.selecttrue, label
%shortcirc_next.0.selectcont.selectcont

shortcirc_next.0.selectcont.selecttrue:		; preds = %shortcirc_next.0.selectcont
	br label %shortcirc_next.0.selectcont.selectcont

shortcirc_next.0.selectcont.selectcont:		; preds =
%shortcirc_next.0.selectcont.selecttrue, %shortcirc_next.0.selectcont
	phi bool [ true, %shortcirc_next.0.selectcont.selecttrue ], [ false,
%shortcirc_next.0.selectcont ]		; <bool>:2 [#uses=1]
	%tmp.143 = cast bool %2 to int		; <int> [#uses=2]
	br bool %1, label %shortcirc_done.1, label %shortcirc_next.1

shortcirc_next.1:		; preds = %shortcirc_next.0.selectcont.selectcont
	%tmp.11.0 = phi int [ %tmp.111, %shortcirc_next.0.selectcont.selectcont ]		;
<int> [#uses=1]
	%tmp.14.0 = phi int [ %tmp.143, %shortcirc_next.0.selectcont.selectcont ]		;
<int> [#uses=1]
	%tmp.19 = setlt int %D, 1		; <bool> [#uses=1]
	br bool %tmp.19, label %shortcirc_next.1.selecttrue, label
%shortcirc_next.1.selectcont

shortcirc_next.1.selecttrue:		; preds = %shortcirc_next.1
	br label %shortcirc_next.1.selectcont

shortcirc_next.1.selectcont:		; preds = %shortcirc_next.1.selecttrue,
%shortcirc_next.1
	phi bool [ true, %shortcirc_next.1.selecttrue ], [ false, %shortcirc_next.1 ]	
; <bool>:3 [#uses=1]
	%tmp.215 = cast bool %3 to int		; <int> [#uses=1]
	cast [32 x sbyte]* %.str_1 to sbyte*		; <sbyte*>:0 [#uses=1]
	%tmp.08 = call int (sbyte*, ...)* %printf( sbyte* %0, int %tmp.4, int
%tmp.11.0, int 0, int %tmp.14.0, int 0, int %tmp.215 )		; <int> [#uses=0]
	ret void

shortcirc_done.1:		; preds = %shortcirc_next.0.selectcont.selectcont
	%tmp.11.1 = phi int [ %tmp.111, %shortcirc_next.0.selectcont.selectcont ]		;
<int> [#uses=1]
	%tmp.14.1 = phi int [ %tmp.143, %shortcirc_next.0.selectcont.selectcont ]		;
<int> [#uses=1]
	cast [32 x sbyte]* %.str_1 to sbyte*		; <sbyte*>:1 [#uses=1]
	%tmp.0 = call int (sbyte*, ...)* %printf( sbyte* %1, int %tmp.4, int %tmp.11.1,
int 0, int %tmp.14.1, int 0, int 1 )		; <int> [#uses=0]
	ret void
}

int %main() {
entry:
	call void %__main( )
	call void %testBooleanNot( int 1, int 2, int -3, int 5 )
	ret int 0
}

declare void %__main()
Instruction: 	phi bool [ true, %entry.selecttrue ], [ false, %entry ]		;
<bool>:0 [#uses=1]
Instruction: 	phi bool [ true, %shortcirc_next.0.selecttrue ], [ false,
%shortcirc_next.0 ]		; <bool>:1 [#uses=2]
Instruction: 	phi bool [ true, %shortcirc_next.0.selectcont.selecttrue ], [
false, %shortcirc_next.0.selectcont ]		; <bool>:2 [#uses=1]
Instruction: 	%tmp.11.0 = phi int [ %tmp.111,
%shortcirc_next.0.selectcont.selectcont ]		; <int> [#uses=1]
Instruction: 	%tmp.14.0 = phi int [ %tmp.143,
%shortcirc_next.0.selectcont.selectcont ]		; <int> [#uses=1]
Instruction: 	phi bool [ true, %shortcirc_next.1.selecttrue ], [ false,
%shortcirc_next.1 ]		; <bool>:3 [#uses=1]
Instruction: 	%tmp.11.1 = phi int [ %tmp.111,
%shortcirc_next.0.selectcont.selectcont ]		; <int> [#uses=1]
Instruction: 	%tmp.14.1 = phi int [ %tmp.143,
%shortcirc_next.0.selectcont.selectcont ]		; <int> [#uses=1]
Processing 	br bool %tmp.3, label %entry.selecttrue, label %entry.selectcont

Processing 	br label %entry.selectcont

Processing 	br label %shortcirc_next.0

Processing 	br bool %tmp.9, label %shortcirc_next.0.selecttrue, label
%shortcirc_next.0.selectcont

Processing 	br label %shortcirc_next.0.selectcont

Processing 	br bool %tmp.132, label %shortcirc_next.0.selectcont.selecttrue,
label %shortcirc_next.0.selectcont.selectcont

Processing 	br label %shortcirc_next.0.selectcont.selectcont

Processing 	br bool %1, label %shortcirc_done.1, label %shortcirc_next.1

Processing 	br bool %tmp.19, label %shortcirc_next.1.selecttrue, label
%shortcirc_next.1.selectcont

Processing 	br label %shortcirc_next.1.selectcont

Code after instruction selection
# Machine code for testBooleanNot():
  <fi #-4> is 4 bytes fixed at location [SP-80]
  <fi #-3> is 4 bytes fixed at location [SP-76]
  <fi #-2> is 4 bytes fixed at location [SP-72]
  <fi #-1> is 4 bytes fixed at location [SP-68]

entry (0x8065970, LLVM BB @0x805fde8):
	%reg1024 = load <fi#-1>
	%reg1025 = load <fi#-2>
	%reg1026 = load <fi#-3>
	%reg1027 = load <fi#-4>
	%reg1028 = move 1
	setcc %reg1024, %reg1028
	if v< goto %disp(label entry.selecttrue)
	%reg1071 = move 0
	goto %disp(label entry.selectcont)

entry.selecttrue (0x80659d0, LLVM BB @0x80639b0):
	%reg1070 = move 1

entry.selectcont (0x8065a30, LLVM BB @0x80638b0):
	%reg1030 = phi %reg1070, mbb<entry.selecttrue,0x80659d0>, %reg1071,
mbb<entry,0x8065970>
	%reg1029 = move %reg1030

shortcirc_next.0 (0x8065a90, LLVM BB @0x805ffc8):
	%reg1031 = move 1
	setcc %reg1026, %reg1031
	if v< goto %disp(label shortcirc_next.0.selecttrue)
	%reg1073 = move 0
	goto %disp(label shortcirc_next.0.selectcont)

shortcirc_next.0.selecttrue (0x8065af0, LLVM BB @0x8063bb0):
	%reg1072 = move 1

shortcirc_next.0.selectcont (0x8065b50, LLVM BB @0x8063b08):
	%reg1033 = phi %reg1072, mbb<shortcirc_next.0.selecttrue,0x8065af0>,
%reg1073, mbb<shortcirc_next.0,0x8065a90>
	%reg1032 = move %reg1033
	%reg1034 = move 1
	setcc %reg1025, %reg1034
	if v< goto %disp(label shortcirc_next.0.selectcont.selecttrue)
	%reg1075 = move 0
	goto %disp(label shortcirc_next.0.selectcont.selectcont)

shortcirc_next.0.selectcont.selecttrue (0x8065bb0, LLVM BB @0x8063db0):
	%reg1074 = move 1

shortcirc_next.0.selectcont.selectcont (0x8065c10, LLVM BB @0x8063d08):
	%reg1036 = phi %reg1074,
mbb<shortcirc_next.0.selectcont.selecttrue,0x8065bb0>, %reg1075,
mbb<shortcirc_next.0.selectcont,0x8065b50>
	%reg1035 = move %reg1036
	%reg1037 = move 0
	setcc %reg1033, %reg1037
	if <>0 goto %disp(label shortcirc_done.1)
	goto %disp(label shortcirc_next.1)

shortcirc_next.1 (0x8065c70, LLVM BB @0x8060278):
	%reg1046 = phi %reg1032,
mbb<shortcirc_next.0.selectcont.selectcont,0x8065c10>
	%reg1050 = phi %reg1035,
mbb<shortcirc_next.0.selectcont.selectcont,0x8065c10>
	%reg1038 = move 1
	setcc %reg1027, %reg1038
	if v< goto %disp(label shortcirc_next.1.selecttrue)
	%reg1077 = move 0
	goto %disp(label shortcirc_next.1.selectcont)

shortcirc_next.1.selecttrue (0x8065cd0, LLVM BB @0x8063fb0):
	%reg1076 = move 1

shortcirc_next.1.selectcont (0x8065d30, LLVM BB @0x8063f08):
	%reg1040 = phi %reg1076, mbb<shortcirc_next.1.selecttrue,0x8065cd0>,
%reg1077, mbb<shortcirc_next.1,0x8065c70>
	%reg1039 = move %reg1040
	%reg1042 = move <ga:.str_1>
	%reg1041 = move %reg1042
	%ar7 = + %ar7, 8
	%reg1043 = - %ar7, 1
	store %reg1043, %reg1041
	%reg1044 = - %ar7, 2
	store %reg1044, %reg1029
	%reg1045 = - %ar7, 3
	store %reg1045, %reg1046
	%reg1047 = - %ar7, 4
	%reg1048 = move 0
	store %reg1047, %reg1048
	%reg1049 = - %ar7, 5
	store %reg1049, %reg1050
	%reg1051 = - %ar7, 6
	%reg1052 = move 0
	store %reg1051, %reg1052
	%reg1053 = - %ar7, 7
	store %reg1053, %reg1039
	call <ga:printf>
	%ar7 = - %ar7, 8
	%reg1054 = move %gr7
	return

shortcirc_done.1 (0x8065d90, LLVM BB @0x8060320):
	%reg1060 = phi %reg1032,
mbb<shortcirc_next.0.selectcont.selectcont,0x8065c10>
	%reg1064 = phi %reg1035,
mbb<shortcirc_next.0.selectcont.selectcont,0x8065c10>
	%reg1056 = move <ga:.str_1>
	%reg1055 = move %reg1056
	%ar7 = + %ar7, 8
	%reg1057 = - %ar7, 1
	store %reg1057, %reg1055
	%reg1058 = - %ar7, 2
	store %reg1058, %reg1029
	%reg1059 = - %ar7, 3
	store %reg1059, %reg1060
	%reg1061 = - %ar7, 4
	%reg1062 = move 0
	store %reg1061, %reg1062
	%reg1063 = - %ar7, 5
	store %reg1063, %reg1064
	%reg1065 = - %ar7, 6
	%reg1066 = move 0
	store %reg1065, %reg1066
	%reg1067 = - %ar7, 7
	%reg1068 = move 1
	store %reg1067, %reg1068
	call <ga:printf>
	%ar7 = - %ar7, 8
	%reg1069 = move %gr7
	return

# End machine code for testBooleanNot().

Code after register allocation
# Machine code for testBooleanNot():
  <fi #-4> is 4 bytes fixed at location [SP-80]
  <fi #-3> is 4 bytes fixed at location [SP-76]
  <fi #-2> is 4 bytes fixed at location [SP-72]
  <fi #-1> is 4 bytes fixed at location [SP-68]

entry (0x8065970, LLVM BB @0x805fde8):
	%gr0 = load <fi#-1>
	%gr1 = load <fi#-2>
	%gr2 = load <fi#-3>
	%gr3 = load <fi#-4>
	%gr4 = move 1
	setcc %gr0, %gr4
	if v< goto %disp(label entry.selecttrue)
	%gr0 = move 0
	%gr0 = move %gr0
	goto %disp(label entry.selectcont)

entry.selecttrue (0x80659d0, LLVM BB @0x80639b0):
	%gr0 = move 1
	%gr0 = move %gr0

entry.selectcont (0x8065a30, LLVM BB @0x80638b0):
	%gr0 = move %gr0
	%gr0 = move %gr0

shortcirc_next.0 (0x8065a90, LLVM BB @0x805ffc8):
	%gr4 = move 1
	setcc %gr2, %gr4
	if v< goto %disp(label shortcirc_next.0.selecttrue)
	%gr2 = move 0
	%gr2 = move %gr2
	goto %disp(label shortcirc_next.0.selectcont)

shortcirc_next.0.selecttrue (0x8065af0, LLVM BB @0x8063bb0):
	%gr2 = move 1
	%gr2 = move %gr2

shortcirc_next.0.selectcont (0x8065b50, LLVM BB @0x8063b08):
	%gr2 = move %gr2
	%gr4 = move %gr2
	%gr5 = move 1
	setcc %gr1, %gr5
	if v< goto %disp(label shortcirc_next.0.selectcont.selecttrue)
	%gr1 = move 0
	%gr1 = move %gr1
	goto %disp(label shortcirc_next.0.selectcont.selectcont)

shortcirc_next.0.selectcont.selecttrue (0x8065bb0, LLVM BB @0x8063db0):
	%gr1 = move 1
	%gr1 = move %gr1

shortcirc_next.0.selectcont.selectcont (0x8065c10, LLVM BB @0x8063d08):
	%gr1 = move %gr1
	%gr1 = move %gr1
	%gr5 = move 0
	setcc %gr2, %gr5
	if <>0 goto %disp(label shortcirc_done.1)
	%gr2 = move %gr4
	%gr5 = move %gr1
	%gr6 = move %gr4
	%gr1 = move %gr1
	goto %disp(label shortcirc_next.1)

shortcirc_next.1 (0x8065c70, LLVM BB @0x8060278):
	%gr1 = move %gr2
	%gr2 = move %gr5
	%gr4 = move 1
	setcc %gr3, %gr4
	if v< goto %disp(label shortcirc_next.1.selecttrue)
	%gr3 = move 0
	%gr3 = move %gr3
	goto %disp(label shortcirc_next.1.selectcont)

shortcirc_next.1.selecttrue (0x8065cd0, LLVM BB @0x8063fb0):
	%gr3 = move 1
	%gr3 = move %gr3

shortcirc_next.1.selectcont (0x8065d30, LLVM BB @0x8063f08):
	%gr3 = move %gr3
	%gr3 = move %gr3
	%gr4 = move <ga:.str_1>
	%gr4 = move %gr4
	%ar7 = + %ar7, 8
	%ar4 = - %ar7, 1
	store %ar4, %gr4
	%ar4 = - %ar7, 2
	store %ar4, %gr0
	%ar4 = - %ar7, 3
	store %ar4, %gr1
	%ar4 = - %ar7, 4
	%gr0 = move 0
	store %ar4, %gr0
	%ar4 = - %ar7, 5
	store %ar4, %gr2
	%ar4 = - %ar7, 6
	%gr0 = move 0
	store %ar4, %gr0
	%ar4 = - %ar7, 7
	store %ar4, %gr3
	call <ga:printf>
	%ar7 = - %ar7, 8
	%gr0 = move %gr7
	return

shortcirc_done.1 (0x8065d90, LLVM BB @0x8060320):
	%gr2 = move %gr6
	%gr1 = move %gr1
	%gr3 = move <ga:.str_1>
	%gr3 = move %gr3
	%ar7 = + %ar7, 8
	%ar4 = - %ar7, 1
	store %ar4, %gr3
	%ar4 = - %ar7, 2
	store %ar4, %gr0
	%ar4 = - %ar7, 3
	store %ar4, %gr2
	%ar4 = - %ar7, 4
	%gr0 = move 0
	store %ar4, %gr0
	%ar4 = - %ar7, 5
	store %ar4, %gr1
	%ar4 = - %ar7, 6
	%gr0 = move 0
	store %ar4, %gr0
	%ar4 = - %ar7, 7
	%gr0 = move 1
	store %ar4, %gr0
	call <ga:printf>
	%ar7 = - %ar7, 8
	%gr0 = move %gr7
	return

# End machine code for testBooleanNot().

Here
Here
Code after prolog/epilog generation
# Machine code for testBooleanNot():
  <fi #-4> is 4 bytes fixed at location [SP-80]
  <fi #-3> is 4 bytes fixed at location [SP-76]
  <fi #-2> is 4 bytes fixed at location [SP-72]
  <fi #-1> is 4 bytes fixed at location [SP-68]
  <fi #0> is 4 bytes at location [SP]
  <fi #1> is 4 bytes at location [SP+4]
  <fi #2> is 4 bytes at location [SP+8]
  <fi #3> is 4 bytes at location [SP+12]
  <fi #4> is 4 bytes at location [SP+16]
  <fi #5> is 4 bytes at location [SP+20]
  <fi #6> is 4 bytes at location [SP+24]
  <fi #7> is 4 bytes at location [SP+28]

entry (0x8065970, LLVM BB @0x805fde8):
	push %ar6, %gr6
	%ar6 = move %ar7
	%ar7 = + %ar7, 2
	%ar6 = + %ar6, 12
	store %ar6, %gr0
	%ar6 = - %ar6, 12
	%ar6 = + %ar6, 13
	store %ar6, %gr1
	%ar6 = - %ar6, 13
	%ar6 = + %ar6, 14
	store %ar6, %gr2
	%ar6 = - %ar6, 14
	%ar6 = + %ar6, 15
	store %ar6, %gr3
	%ar6 = - %ar6, 15
	%ar6 = + %ar6, 16
	store %ar6, %gr4
	%ar6 = - %ar6, 16
	%ar6 = + %ar6, 17
	store %ar6, %gr5
	%ar6 = - %ar6, 17
	%ar6 = + %ar6, 18
	store %ar6, %gr6
	%ar6 = - %ar6, 18
	%ar6 = + %ar6, 19
	store %ar6, %ar4
	%ar6 = - %ar6, 19
	%ar6 = + %ar6, -5
	%gr0 = load %ar6
	%ar6 = - %ar6, -5
	%ar6 = + %ar6, -6
	%gr1 = load %ar6
	%ar6 = - %ar6, -6
	%ar6 = + %ar6, -7
	%gr2 = load %ar6
	%ar6 = - %ar6, -7
	%ar6 = + %ar6, -8
	%gr3 = load %ar6
	%ar6 = - %ar6, -8
	%gr4 = move 1
	setcc %gr0, %gr4
	if v< goto %disp(label entry.selecttrue)
	%gr0 = move 0
	%gr0 = move %gr0
	goto %disp(label entry.selectcont)

entry.selecttrue (0x80659d0, LLVM BB @0x80639b0):
	%gr0 = move 1
	%gr0 = move %gr0

entry.selectcont (0x8065a30, LLVM BB @0x80638b0):
	%gr0 = move %gr0
	%gr0 = move %gr0

shortcirc_next.0 (0x8065a90, LLVM BB @0x805ffc8):
	%gr4 = move 1
	setcc %gr2, %gr4
	if v< goto %disp(label shortcirc_next.0.selecttrue)
	%gr2 = move 0
	%gr2 = move %gr2
	goto %disp(label shortcirc_next.0.selectcont)

shortcirc_next.0.selecttrue (0x8065af0, LLVM BB @0x8063bb0):
	%gr2 = move 1
	%gr2 = move %gr2

shortcirc_next.0.selectcont (0x8065b50, LLVM BB @0x8063b08):
	%gr2 = move %gr2
	%gr4 = move %gr2
	%gr5 = move 1
	setcc %gr1, %gr5
	if v< goto %disp(label shortcirc_next.0.selectcont.selecttrue)
	%gr1 = move 0
	%gr1 = move %gr1
	goto %disp(label shortcirc_next.0.selectcont.selectcont)

shortcirc_next.0.selectcont.selecttrue (0x8065bb0, LLVM BB @0x8063db0):
	%gr1 = move 1
	%gr1 = move %gr1

shortcirc_next.0.selectcont.selectcont (0x8065c10, LLVM BB @0x8063d08):
	%gr1 = move %gr1
	%gr1 = move %gr1
	%gr5 = move 0
	setcc %gr2, %gr5
	if <>0 goto %disp(label shortcirc_done.1)
	%gr2 = move %gr4
	%gr5 = move %gr1
	%gr6 = move %gr4
	%gr1 = move %gr1
	goto %disp(label shortcirc_next.1)

shortcirc_next.1 (0x8065c70, LLVM BB @0x8060278):
	%gr1 = move %gr2
	%gr2 = move %gr5
	%gr4 = move 1
	setcc %gr3, %gr4
	if v< goto %disp(label shortcirc_next.1.selecttrue)
	%gr3 = move 0
	%gr3 = move %gr3
	goto %disp(label shortcirc_next.1.selectcont)

shortcirc_next.1.selecttrue (0x8065cd0, LLVM BB @0x8063fb0):
	%gr3 = move 1
	%gr3 = move %gr3

shortcirc_next.1.selectcont (0x8065d30, LLVM BB @0x8063f08):
	%gr3 = move %gr3
	%gr3 = move %gr3
	%gr4 = move <ga:.str_1>
	%gr4 = move %gr4
	%ar7 = + %ar7, 8
	%ar4 = - %ar7, 1
	store %ar4, %gr4
	%ar4 = - %ar7, 2
	store %ar4, %gr0
	%ar4 = - %ar7, 3
	store %ar4, %gr1
	%ar4 = - %ar7, 4
	%gr0 = move 0
	store %ar4, %gr0
	%ar4 = - %ar7, 5
	store %ar4, %gr2
	%ar4 = - %ar7, 6
	%gr0 = move 0
	store %ar4, %gr0
	%ar4 = - %ar7, 7
	store %ar4, %gr3
	call <ga:printf>
	%ar7 = - %ar7, 8
	%gr0 = move %gr7
	%ar6 = + %ar6, 19
	%ar4 = load %ar6
	%ar6 = - %ar6, 19
	%ar6 = + %ar6, 18
	%gr6 = load %ar6
	%ar6 = - %ar6, 18
	%ar6 = + %ar6, 17
	%gr5 = load %ar6
	%ar6 = - %ar6, 17
	%ar6 = + %ar6, 16
	%gr4 = load %ar6
	%ar6 = - %ar6, 16
	%ar6 = + %ar6, 15
	%gr3 = load %ar6
	%ar6 = - %ar6, 15
	%ar6 = + %ar6, 14
	%gr2 = load %ar6
	%ar6 = - %ar6, 14
	%ar6 = + %ar6, 13
	%gr1 = load %ar6
	%ar6 = - %ar6, 13
	%ar6 = + %ar6, 12
	%gr0 = load %ar6
	%ar6 = - %ar6, 12
	%ar7 = - %ar7, 2
	pop %ar6, %gr6
	return

shortcirc_done.1 (0x8065d90, LLVM BB @0x8060320):
	%gr2 = move %gr6
	%gr1 = move %gr1
	%gr3 = move <ga:.str_1>
	%gr3 = move %gr3
	%ar7 = + %ar7, 8
	%ar4 = - %ar7, 1
	store %ar4, %gr3
	%ar4 = - %ar7, 2
	store %ar4, %gr0
	%ar4 = - %ar7, 3
	store %ar4, %gr2
	%ar4 = - %ar7, 4
	%gr0 = move 0
	store %ar4, %gr0
	%ar4 = - %ar7, 5
	store %ar4, %gr1
	%ar4 = - %ar7, 6
	%gr0 = move 0
	store %ar4, %gr0
	%ar4 = - %ar7, 7
	%gr0 = move 1
	store %ar4, %gr0
	call <ga:printf>
	%ar7 = - %ar7, 8
	%gr0 = move %gr7
	%ar6 = + %ar6, 19
	%ar4 = load %ar6
	%ar6 = - %ar6, 19
	%ar6 = + %ar6, 18
	%gr6 = load %ar6
	%ar6 = - %ar6, 18
	%ar6 = + %ar6, 17
	%gr5 = load %ar6
	%ar6 = - %ar6, 17
	%ar6 = + %ar6, 16
	%gr4 = load %ar6
	%ar6 = - %ar6, 16
	%ar6 = + %ar6, 15
	%gr3 = load %ar6
	%ar6 = - %ar6, 15
	%ar6 = + %ar6, 14
	%gr2 = load %ar6
	%ar6 = - %ar6, 14
	%ar6 = + %ar6, 13
	%gr1 = load %ar6
	%ar6 = - %ar6, 13
	%ar6 = + %ar6, 12
	%gr0 = load %ar6
	%ar6 = - %ar6, 12
	%ar7 = - %ar7, 2
	pop %ar6, %gr6
	return

# End machine code for testBooleanNot().

Code after instruction selection
# Machine code for main():

entry (0x806e928, LLVM BB @0x8060490):
	%ar7 = + %ar7, 0
	call <ga:__main>
	%ar7 = - %ar7, 0
	%ar7 = + %ar7, 4
	%reg1024 = - %ar7, 1
	%reg1025 = move 1
	store %reg1024, %reg1025
	%reg1026 = - %ar7, 2
	%reg1027 = move 2
	store %reg1026, %reg1027
	%reg1028 = - %ar7, 3
	%reg1029 = move -3
	store %reg1028, %reg1029
	%reg1030 = - %ar7, 4
	%reg1031 = move 5
	store %reg1030, %reg1031
	call <ga:testBooleanNot>
	%ar7 = - %ar7, 4
	%reg1032 = move 0
	%gr7 = move %reg1032
	return

# End machine code for main().

Code after register allocation
# Machine code for main():

entry (0x806e928, LLVM BB @0x8060490):
	%ar7 = + %ar7, 0
	call <ga:__main>
	%ar7 = - %ar7, 0
	%ar7 = + %ar7, 4
	%ar4 = - %ar7, 1
	%gr0 = move 1
	store %ar4, %gr0
	%ar4 = - %ar7, 2
	%gr0 = move 2
	store %ar4, %gr0
	%ar4 = - %ar7, 3
	%gr0 = move -3
	store %ar4, %gr0
	%ar4 = - %ar7, 4
	%gr0 = move 5
	store %ar4, %gr0
	call <ga:testBooleanNot>
	%ar7 = - %ar7, 4
	%gr0 = move 0
	%gr7 = move %gr0
	return

# End machine code for main().

Here
Code after prolog/epilog generation
# Machine code for main():
  <fi #0> is 4 bytes at location [SP]
  <fi #1> is 4 bytes at location [SP+4]

entry (0x806e928, LLVM BB @0x8060490):
	push %ar6, %gr6
	%ar6 = move %ar7
	%ar7 = + %ar7, 2
	%ar6 = + %ar6, 12
	store %ar6, %gr0
	%ar6 = - %ar6, 12
	%ar6 = + %ar6, 13
	store %ar6, %ar4
	%ar6 = - %ar6, 13
	%ar7 = + %ar7, 0
	call <ga:__main>
	%ar7 = - %ar7, 0
	%ar7 = + %ar7, 4
	%ar4 = - %ar7, 1
	%gr0 = move 1
	store %ar4, %gr0
	%ar4 = - %ar7, 2
	%gr0 = move 2
	store %ar4, %gr0
	%ar4 = - %ar7, 3
	%gr0 = move -3
	store %ar4, %gr0
	%ar4 = - %ar7, 4
	%gr0 = move 5
	store %ar4, %gr0
	call <ga:testBooleanNot>
	%ar7 = - %ar7, 4
	%gr0 = move 0
	%gr7 = move %gr0
	%ar6 = + %ar6, 13
	%ar4 = load %ar6
	%ar6 = - %ar6, 13
	%ar6 = + %ar6, 12
	%gr0 = load %ar6
	%ar6 = - %ar6, 12
	%ar7 = - %ar7, 2
	pop %ar6, %gr6
	return

# End machine code for main().

Reid Spencer

2004-Jun-22 10:10 UTC

head link

[LLVMdev] Linearscan allocator bug?

Hi Vladimir.

On Tue, 2004-06-22 at 07:01, Vladimir Prus wrote:> Folks, 
> I'm running into something which looks like a bug in linearscan
allocator. Of
> course I can't be 100% sure it's not some unobvious mistake on my
part, so
> I'd like to hear your opinion.
Yes, there's a known bug in the linear scan allocator. It causes a few
of the nightly tests to fail.

I'll defer to the experts on your analysis below, but if you're close to
finding this problem, you might want to talk to Alkis who wrote linear
scan (I think).

Reid.
> 
> First, I attach two files -- LLVM asm and the asm for my target. The
problem
> with assembler is: on line 171 it uses register gr2, which is copied from
gr6
> above, on line 161. The only predecessor of this basic block is jump on
line
> 90. The problem is that gr6 is not initialized in the interval from the 
> function entry till the jump.
> 
> I also attach the debug dumps from my backend. 
> 
> The basic block in question is shortcirc_done.1 (line 198 in the log). It 
> starts with:
> 
>     %reg1060 = phi %reg1032, mbb<shortcirc_next.0.selectcont.selectcont,
> 
> The predecessor is at line 155 and the register 1032 is assigned a value on
> line 140 (in shortcirc_next.0.selectcont): 
> 
>     %reg1032 = move %reg103
> 
> After register allocation the code in shortcirc_done.1 is (line 334):
> 
>     %gr2 = move %gr6
> 
> the predecessor in at line 285 and the code in shortcirc_next.0.selectcont
is
> (line 268)
> 
>     %gr4 = move %gr2
> 
> while I'd expect destination register should be gr6.
> 
> In fact, gr6 is first used here (line 289):
> 
>         if <>0 goto %disp(label shortcirc_done.1)
> 	%gr2 = move %gr4
> 	%gr5 = move %gr1
> 	%gr6 = move %gr4
> 	%gr1 = move %gr1
> 
> So, it's possible that jump goes to shortcirc_done.1 which then uses
gr6 and
> gets back results. 
> 
> Any ideas?
> 
> - Volodya-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20040622/7d5e8cd7/attachment.sig>

Chris Lattner

2004-Jun-22 22:35 UTC

head link

[LLVMdev] Linearscan allocator bug?

On Tue, 22 Jun 2004, Vladimir Prus wrote:
> First, I attach two files -- LLVM asm and the asm for my target. The
problem
> with assembler is: on line 171 it uses register gr2, which is copied from
gr6
> above, on line 161. The only predecessor of this basic block is jump on
line
> 90. The problem is that gr6 is not initialized in the interval from the
> function entry till the jump.
Okay, I see the problem.  You need to tell the compiler that the
conditional branches are terminators.  You're getting code that looks like
this:

<LBB7> // // shortcirc_next.0.selectcont.selectcont
        gr1 = gr1;
        gr1 = gr1;
        gr5 = 0;
        gr2 - gr5;
        if <>0 goto LBB11;
*       gr2 = gr4;
*       gr5 = gr1;
*       gr6 = gr4;
*       gr1 = gr1;
        goto LBB8;

I'm guessing that those copies are inserted by the register allocator, and
in particular, that is probably where gr6 is supposed to get it's value.
If you set the isTerminator flag on your 'if <>0 goto LBB11;'
things will
probably magically start working for you, as the copies will be inserted
BEFORE the branch instead of after it.

Also, if you haven't already, you might want to teach TargetInstrInfo
that '=' is a move instruction (implement isMoveInstr), so instructinos
like 'gr1 = gr1' will go away and you'll get coallescing.  :)

-Chris
> I also attach the debug dumps from my backend.
>
> The basic block in question is shortcirc_done.1 (line 198 in the log). It
> starts with:
>
>     %reg1060 = phi %reg1032, mbb<shortcirc_next.0.selectcont.selectcont,
>
> The predecessor is at line 155 and the register 1032 is assigned a value on
> line 140 (in shortcirc_next.0.selectcont):
>
>     %reg1032 = move %reg103
>
> After register allocation the code in shortcirc_done.1 is (line 334):
>
>     %gr2 = move %gr6
>
> the predecessor in at line 285 and the code in shortcirc_next.0.selectcont
is
> (line 268)
>
>     %gr4 = move %gr2
>
> while I'd expect destination register should be gr6.
>
> In fact, gr6 is first used here (line 289):
>
>         if <>0 goto %disp(label shortcirc_done.1)
> 	%gr2 = move %gr4
> 	%gr5 = move %gr1
> 	%gr6 = move %gr4
> 	%gr1 = move %gr1
>
> So, it's possible that jump goes to shortcirc_done.1 which then uses
gr6 and
> gets back results.
>
> Any ideas?
>
> - Volodya
>
-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Vladimir Prus

2004-Jun-23 01:00 UTC

head link

[LLVMdev] Linearscan allocator bug?

Chris Lattner wrote:> On Tue, 22 Jun 2004, Vladimir Prus wrote:
> > First, I attach two files -- LLVM asm and the asm for my target. The
> > problem with assembler is: on line 171 it uses register gr2, which is
> > copied from gr6 above, on line 161. The only predecessor of this basic
> > block is jump on line 90. The problem is that gr6 is not initialized
in
> > the interval from the function entry till the jump.
>
> Okay, I see the problem.  You need to tell the compiler that the
> conditional branches are terminators.  You're getting code that looks
like
> this:
>
> <LBB7> // // shortcirc_next.0.selectcont.selectcont
>         gr1 = gr1;
>         gr1 = gr1;
>         gr5 = 0;
>         gr2 - gr5;
>         if <>0 goto LBB11;
> *       gr2 = gr4;
> *       gr5 = gr1;
> *       gr6 = gr4;
> *       gr1 = gr1;
>         goto LBB8;
>
> I'm guessing that those copies are inserted by the register allocator,
and
> in particular, that is probably where gr6 is supposed to get it's
value.
> If you set the isTerminator flag on your 'if <>0 goto LBB11;'
things will
> probably magically start working for you, as the copies will be inserted
> BEFORE the branch instead of after it.
Hmm.. this is what I have in td file already:

let isTerminator = 1 in
    def GOTO : Unknown<"goto">;
    def IFEQ : Unknown<"if =0 goto">;
    def IFNEQ : Unknown<"if <>0 goto">;
    .....

Should this work?
> Also, if you haven't already, you might want to teach TargetInstrInfo
> that '=' is a move instruction (implement isMoveInstr), so
instructinos
> like 'gr1 = gr1' will go away and you'll get coallescing.  :)
BTW, is it possible to set some instruction flag, instead of overriding a 
function? Something like:

let isMove = 1 in
      def MOVE :.....

?

- Volodya

Seemingly Similar Threads

Search for more seemingly similar threads

llvm dev - Jun 2004 - [LLVMdev] Linearscan allocator bug?

[LLVMdev] Linearscan allocator bug?

[LLVMdev] Linearscan allocator bug?

[LLVMdev] Linearscan allocator bug?

[LLVMdev] Linearscan allocator bug?

Seemingly Similar Threads