Re: An alias bug

[hjl at lucon dot org (H.J. Lu)]

> 
>   In message <m0yv7b6-000266C@ocean.lucon.org>you write:
>   > I will continue working on it. IMHO, it is not just a libg++ issue.
> That depends on what we find.  The new alias code has exposed several
> bugs in user/library code.  We won't know if it's a bug in the libg++
> code or in the alias analysis code until we can look more closely at the
> problem.
> 
> I consider this an important issue, but there's little I can do right
> now to solve it.  I have to depend on you to provide me the information
> I'm going to need to evaluate the problem and take appropriate action.
> 

Here is a C testcase from Richard. The binary aborts when compiled with
-O2. I have another 500 line C++ testcase which results in an infinite
loop when compiled with -O2. The problems with loop and alias are

1. We may have

	set (reg 57) ((reg 26) + 10)
	...
	LOOP_BEG
	...
	set MEM((reg 26) + 10) (x)
	...
	set (y) MEM(reg 57)
	...
	LOOP_END

2. We may have

	set (reg 57) ((reg 26) + 10)
	...
	LOOP_BEG
	...
	set MEM(reg 57) (x)
	...
	set (y) MEM((reg 26) + 10)
	...
	LOOP_END

3. We may have

	LOOP_BEG
	...
	set (reg 57) ((reg 26) + 10)
	...
	set MEM((reg 26) + 10) (x)
	...
	set (y) MEM(reg 57)
	...
	LOOP_END

4. We may have

	LOOP_BEG
	...
	set (reg 57) ((reg 26) + 10)
	...
	set MEM(reg 57) (x)
	...
	set (y) MEM((reg 26) + 10)
	...
	LOOP_END

5. We may have

	LOOP_BEG
	...
	set MEM((reg 26) + 10) (x)
	...
	set (reg 57) ((reg 26) + 10)
	...
	set (y) MEM(reg 57)
	...
	LOOP_END

Since we only record 

	set MEM(addr1) (x)

in "loop_store_mems", we miss the dependency in

	set (y) MEM(addr2)

where MEM(addr2) is never set explicitly, but (addr1) == (addr2).

In case of the testcase enclosed here, we have

(insn 37 9 12 (set (mem:DI (addressof:SI (reg:DI 30) 22))
        (reg:DI 31)) 85 {movdi+1} (nil)
    (nil))
...
(note 13 113 19 "" NOTE_INSN_LOOP_BEG)
...
(insn 40 34 43 (set (mem:DI (addressof:SI (reg:DI 30) 22))
        (reg:DI 32)) 85 {movdi+1} (nil)
    (nil))
...
(insn 43 40 45 (set (reg:SI 33)
        (addressof:SI (reg:DI 30) 22)) 54 {movsi+2} (nil)
    (nil))
...
(insn 50 46 52 (set (reg:SI 37)
        (mem/s:SI (plus:SI (reg:SI 33)
                (const_int 4)))) 54 {movsi+2} (nil)
    (nil))
...
(insn 66 64 74 (set (mem:DI (addressof:SI (reg:DI 30) 22))
        (reg:DI 45)) 85 {movdi+1} (nil)
    (nil))
...
(note 87 16 93 "" NOTE_INSN_LOOP_END)

The alias code doesn't know (reg:SI 33) == (addressof:SI (reg:DI 30))
It knows 

(mem:DI (addressof:SI (reg:DI 30) 22))

is set. But it has no idea about

(mem/s:SI (plus:SI (reg:SI 33) (const_int 4)))

since (mem:DI (reg:SI 33)) is not in "loop_store_mems".

Those alias problems I have found so far all use pointers. In case of
C++, all my testcases use void * as position pointer. They are straight
C++, nothing fancy. C++ compiler has to use THIS poiner to access those
virtual functions as well as data members. As the result, the addressing
is kind of complicated. Here is an example from my testcase. Before
sched2:

(insn:HI 418 414 882 (set (reg:SI 4 %esi)
        (plus:SI (reg:SI 6 %ebp)
            (const_int -68))) 143 {addsi3+1} (nil)
    (nil))          

(insn 882 418 851 (set (mem:SI (plus:SI (reg:SI 6 %ebp)
                (const_int -96)))
        (reg:SI 4 %esi)) 54 {movsi+2} (nil)
    (nil))
  
(insn:HI 851 882 419 (set (mem:SI (plus:SI (reg:SI 6 %ebp)
                (const_int -88)))
        (reg:SI 4 %esi)) 54 {movsi+2} (insn_list 418 (nil))
    (expr_list:REG_EQUAL (plus:SI (reg:SI 6 %ebp)
            (const_int -68))
        (nil)))
......

(insn/i:HI 430 429 885 (set (reg:SI 4 %esi)
        (mem/s:SI (plus:SI (reg/v:SI 1 %edx)
                (const_int 4)))) 54 {movsi+2} (insn_list 424 (nil))
    (nil))

......


;; End of basic block 25

;; Insn is not within a basic block
(insn 894 460 461 (set (reg:SI 4 %esi)
        (mem:SI (plus:SI (reg:SI 6 %ebp)
                (const_int -88)))) 54 {movsi+2} (nil)
    (nil))

;; Start of basic block 26, registers live: 6 [bp] 7 [sp] 31 36 40 48 88 186 188
(insn/i:HI 461 894 462 (set (reg:SI 0 %eax)
        (mem/s:SI (reg:SI 4 %esi))) 54 {movsi+2} (nil)
    (expr_list:REG_EQUIV (mem/s:SI (reg:SI 4 %esi))
        (nil)))

(insn/i:QI 462 461 897 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
        (reg:SI 0 %eax)) 50 {movsi-2} (insn_list 461 (nil))
    (expr_list:REG_DEAD (reg:SI 0 %eax)
        (nil)))

(insn 897 462 463 (set (reg:SI 4 %esi)
        (mem:SI (plus:SI (reg:SI 6 %ebp)
                (const_int -92)))) 54 {movsi+2} (nil)
    (nil))

(insn/i:QI 463 897 464 (set (mem:SI (pre_dec:SI (reg:SI 7 %esp)))
        (reg:SI 4 %esi)) 50 {movsi-2} (nil)
    (nil))

(call_insn/i 464 463 465 (set (reg:SI 0 %eax)
        (call (mem:QI (symbol_ref:SI ("dosucc__C8intXPlexPCi")))
            (const_int 8))) 333 {call_value+1} (nil)
    (nil)
    (nil))
;; End of basic block 26

;; Start of basic block 27, registers live: 0 [ax] 6 [bp] 7 [sp] 31 36 40 48 88 186 188
(insn/i:QI 465 464 466 (set (reg:SI 7 %esp)
        (plus:SI (reg:SI 7 %esp)
            (const_int 8))) 143 {addsi3+1} (nil)
    (nil))

(note/i 466 465 467 "" NOTE_INSN_DELETED)
;; End of basic block 27

;; Start of basic block 28, registers live: 6 [bp] 7 [sp] 31 36 40 48 88 108 186 188
(code_label/i 467 466 900 968 "")

(insn 900 467 468 (set (reg:SI 4 %esi)
        (mem:SI (plus:SI (reg:SI 6 %ebp)
                (const_int -88)))) 54 {movsi+2} (nil)
    (nil))

(insn/i:HI 468 900 469 (set (mem/s:SI (reg:SI 4 %esi))
        (reg:SI 0 %eax)) 54 {movsi+2} (nil)
    (expr_list:REG_DEAD (reg:SI 0 %eax)
        (expr_list:REG_DEAD (mem:SI (plus:SI (reg:SI 6 %ebp)
                    (const_int -88)))
            (nil))))

(note/i 469 468 471 0 NOTE_INSN_BLOCK_END)

(note/i 471 469 472 0 NOTE_INSN_BLOCK_END)

(note/i 472 471 474 0 NOTE_INSN_BLOCK_END)

(note 474 472 823 0 NOTE_INSN_BLOCK_END)

(insn 823 474 849 (set (reg:SI 1 %edx)
        (mem:SI (plus:SI (reg:SI 6 %ebp)
                (const_int -68)))) 54 {movsi+2} (nil)
    (nil))

As you can see insn 894 restores (reg:SI 4 %esi) to

(plus:SI (reg:SI 6 %ebp) (const_int -68))

But this information is not available to alias code. As the result,
sched2 moves insn 823 before insn 468. That happens very often in C++
code. We have to track what is stored in each memory location to make
alias more reliable. If it is the right way to do it, I can give it
a try. "mem_last_sets" may be modeled after "reg_last_sets". It has
to be a list, like, "pending_write_mems", instead of array.


H.J.
-- 
H.J. Lu (hjl@gnu.org)
----
long A [2] = {0};
long B [2] = {2, 0};

typedef union
{
  long long ll;
  long l[2];
} long_long_type;

main ()
{
  unsigned int i;
  long long u = -1;
  for (i = 0; i < 2; i+=2)
  {
    u = A [i] + B [i];
    u = ((long_long_type *) &u)->l [1] + A [i+1] + B [i+1];
    A [i+1] = (long) u;
  }
  if (A [1] != 0)
    abort ();
  return 0;
}