Invalid alias info through crossjumping

[Andreas Krebbel <krebbel1 at de dot ibm dot com>]

Hello

The attached testcase produces wrong code due to corrupted alias data during crossjumping.

The crossjumping analysis wants to identify redundant code located before jumps to the same target. 

taken from i.26.postreload:

tail of basic block 1:

(insn 125 18 21 1 (set (reg:SI 3 %r3)
        (const_int 0 [0x0])) 56 {*movsi_esa} (nil)
    (nil))

(insn 21 125 116 1 (set (mem/f:SI (reg/f:SI 1 %r1 [44]) [0 p1+0 S4 A32])
        (reg:SI 3 %r3)) 56 {*movsi_esa} (insn_list 17 (insn_list:REG_DEP_ANTI 12 (insn_list:REG_DEP_AN
TI 18 (nil))))
    (nil))

(jump_insn 116 21 117 1 (set (pc)
        (label_ref 81)) 299 {jump} (insn_list 17 (insn_list:REG_DEP_ANTI 21 (insn_list 8 (insn_list:RE
G_DEP_ANTI 18 (insn_list 26 (insn_list 11 (insn_list:REG_DEP_ANTI 12 (nil))))))))
    (nil))



tail of basic block 7:

(insn 127 67 68 7 (set (reg:SI 3 %r3)
        (const_int 0 [0x0])) 56 {*movsi_esa} (nil)
    (nil))

(insn 68 127 120 7 (set (mem/f:SI (reg/f:SI 1 %r1 [59]) [0 p2+0 S4 A32])
        (reg:SI 3 %r3)) 56 {*movsi_esa} (insn_list 67 (insn_list:REG_DEP_ANTI 40 (insn_list:REG_DEP_AN
TI 12 (insn_list:REG_DEP_ANTI 32 (insn_list:REG_DEP_ANTI 61 (insn_list:REG_DEP_ANTI 118 (insn_list:REG
_DEP_ANTI 37 (nil))))))))
    (nil))

(jump_insn 120 68 121 7 (set (pc)
        (label_ref 81)) 299 {jump} (insn_list:REG_DEP_ANTI 12 (insn_list:REG_DEP_ANTI 32 (insn_list:RE
G_DEP_ANTI 58 (insn_list 67 (insn_list:REG_DEP_ANTI 68 (insn_list 60 (insn_list 37 (insn_list 8 (insn_
list 11 (insn_list:REG_DEP_ANTI 31 (insn_list 73 (insn_list 39 (insn_list 49 (insn_list:REG_DEP_ANTI 4
0 (insn_list:REG_DEP_ANTI 50 (insn_list 59 (insn_list 61 (insn_list 118 (nil)))))))))))))))))))
    (nil))



The code lines -1- and -2- (in the testcase listing) are recognized as redundant:


.27.flow2:

try_optimize_cfg iteration 1

Splitting bb 7 before 2 insns
Cross jumping from bb 1 to bb 7; 2 common insns

;; Start of basic block 1, registers live: 2 [%r2] 4 [%r4] 15 [%r15]
(note 87 12 17 1 [bb 1] NOTE_INSN_BASIC_BLOCK)

(insn 17 87 18 1 (set (reg/f:SI 1 %r1 [44])
        (mem/u/f:SI (symbol_ref/u:SI ("*.LC1") [flags 0x2]) [0 S4 A32])) 56 {*movsi_esa} (nil)
    (expr_list:REG_EQUIV (symbol_ref:SI ("p1") [flags 0x40] <var_decl 0x40221680 p1>)
        (nil)))

(insn 18 17 143 1 (set (mem/s/j:SI (reg/f:SI 4 %r4 [42]) [0 x.opval+0 S4 A32])
        (mem/f:SI (reg/f:SI 1 %r1 [44]) [0 p1+0 S4 A32])) 56 {*movsi_esa} (insn_list 17 (nil))
    (expr_list:REG_DEAD (reg/f:SI 4 %r4 [42])
        (nil)))

(jump_insn 143 18 144 1 (set (pc)
        (label_ref 142)) -1 (nil)
    (nil))
;; End of basic block 1, registers live:
 1 [%r1] 2 [%r2] 15 [%r15]

;; Start of basic block 7, registers live: 15 [%r15]
(code_label 65 61 94 7 4 "" [2 uses])

(note 94 65 73 7 [bb 7] NOTE_INSN_BASIC_BLOCK)

(insn 73 94 67 7 (set (reg:SI 2 %r2 [orig:40 <result> ] [40])
        (const_int 260 [0x104])) 56 {*movsi_esa} (nil)
    (nil))

(insn 67 73 142 7 (set (reg/f:SI 1 %r1 [59])
        (mem/u/f:SI (symbol_ref/u:SI ("*.LC3") [flags 0x2]) [0 S4 A32])) 56 {*movsi_esa} (nil)
    (expr_list:REG_EQUIV (symbol_ref:SI ("p2") [flags 0x40] <var_decl 0x40221780 p2>)
        (nil)))
;; End of basic block 7, registers live:
 1 [%r1] 2 [%r2] 15 [%r15]

;; Start of basic block 10, registers live: 1 [%r1] 2 [%r2] 15 [%r15]
(code_label 142 67 140 10 7 "" [1 uses])

(note 140 142 127 10 [bb 10] NOTE_INSN_BASIC_BLOCK)

(insn 127 140 68 10 (set (reg:SI 3 %r3)
        (const_int 0 [0x0])) 56 {*movsi_esa} (nil)
    (nil))

(insn 68 127 120 10 (set (mem/f:SI (reg/f:SI 1 %r1 [59]) [0 p2+0 S4 A32])
        (reg:SI 3 %r3)) 56 {*movsi_esa} (insn_list 127 (nil))
    (expr_list:REG_DEAD (reg:SI 3 %r3)
        (expr_list:REG_DEAD (reg/f:SI 1 %r1 [59])
            (nil))))

(jump_insn 120 68 121 10 (set (pc)
        (label_ref 81)) 299 {jump} (nil)
    (nil))
;; End of basic block 10, registers live:
 2 [%r2] 15 [%r15]


Unfortunately the crossjumping analysis didn't care much about the alias information and in this case the alias info of the former insn number 21 don't make it to the next round. But this wouldn't be a problem so far because the scheduler would never move an insn over a code label. The problem comes up when the basic block reordering step gets the great idea to duplicate code in order to avoid the jump-insn 143 and therefore undoes the crossjumping:

.31.bbro:

;; Start of basic block 3, registers live: 2 [%r2] 4 [%r4] 15 [%r15]
(code_label 160 139 87 3 9 "" [1 uses])

(note 87 160 17 3 [bb 3] NOTE_INSN_BASIC_BLOCK)

(insn 17 87 18 3 (set (reg/f:SI 1 %r1 [44])
        (mem/u/f:SI (symbol_ref/u:SI ("*.LC1") [flags 0x2]) [0 S4 A32])) 56 {*movsi_esa} (nil)
    (expr_list:REG_EQUIV (symbol_ref:SI ("p1") [flags 0x40] <var_decl 0x40221680 p1>)
        (nil)))

(insn 18 17 127 3 (set (mem/s/j:SI (reg/f:SI 4 %r4 [42]) [0 x.opval+0 S4 A32])
        (mem/f:SI (reg/f:SI 1 %r1 [44]) [0 p1+0 S4 A32])) 56 {*movsi_esa} (insn_list 17 (nil))
    (expr_list:REG_DEAD (reg/f:SI 4 %r4 [42])
        (nil)))

(insn 127 18 68 3 (set (reg:SI 3 %r3)
        (const_int 0 [0x0])) 56 {*movsi_esa} (nil)
    (nil))

(insn 68 127 162 3 (set (mem/f:SI (reg/f:SI 1 %r1 [59]) [0 p2+0 S4 A32])
        (reg:SI 3 %r3)) 56 {*movsi_esa} (insn_list 127 (nil))
    (expr_list:REG_DEAD (reg:SI 3 %r3)
        (expr_list:REG_DEAD (reg/f:SI 1 %r1 [59])
            (nil))))

(jump_insn 162 68 163 3 (set (pc)
        (label_ref 81)) -1 (nil)
    (nil))
;; End of basic block 3, registers live:
 2 [%r2] 15 [%r15]

;; Start of basic block 7, registers live: 1 [%r1] 2 [%r2] 15 [%r15]
(code_label 167 67 151 7 12 "" [2 uses])

(note 151 167 149 7 [bb 7] NOTE_INSN_BASIC_BLOCK)

(insn 149 151 150 7 (set (reg:SI 3 %r3)
        (const_int 0 [0x0])) 56 {*movsi_esa} (nil)
    (nil))

(insn 150 149 165 7 (set (mem/f:SI (reg/f:SI 1 %r1 [59]) [0 p2+0 S4 A32])
        (reg:SI 3 %r3)) 56 {*movsi_esa} (nil)
    (expr_list:REG_DEAD (reg/f:SI 1 %r1 [59])
        (expr_list:REG_DEAD (reg:SI 3 %r3)
            (nil))))

(jump_insn 165 150 166 7 (set (pc)
        (label_ref 81)) -1 (nil)
    (nil))
;; End of basic block 7, registers live:
 2 [%r2] 15 [%r15]


After a lot of optimization steps the only change is that the former insn 21 is replaced by the insn 68 with a modified alias information. The insn 68 in turn got a twin called insn 150 which now holds the old position of 68.

Now the scheduler wants to reorder the insns: 18 127 68 to 127 68 18 which seems to be a valid step: 

;;   ======================================================
;;   -- basic block 3 from 17 to 162 -- after reload
;;   ======================================================

;;        0--> 17   %r1=[`*.LC1']                      :(x-e1-st+x-mem),x-wr-st
;;        0--> 127  %r3=0x0                            :x-e1-st,x-wr-st
;;        4--> 68   [%r1]=%r3                          :(x-e1-st+x_store_tok),x-wr-st
;;        5--> 18   [%r4]=[%r1]                        :x-e1-np,x-wr-np
;;        6--> 162  pc=L81                             :x_e1_r,x_wr_r
;;      Ready list (final):
;;   total time = 6
;;   new head = 17
;;   new tail = 162

And the program is broken ...

As you can tell from the alias data the code was compiled with -fno-strict-aliasing and therefore every insn gets 0 as its alias group. Though the type based aliasing is turned off. But even this doesn't avoid the problem because the compiler assumes that two different symbol references never overlap. That's why the function "nonoverlapping_memrefs_p" returns false (in line 2025 of alias.c) when it is called with the two memory references: 

(mem/f:SI (reg/f:SI 1 %r1 [59]) [0 p2+0 S4 A32]) and
(mem/f:SI (reg/f:SI 1 %r1 [44]) [0 p1+0 S4 A32])

Hence no anti dependence between insns 18 and 68 is created and the scheduler thinks it does the right thing.

I could imagine two solutions to fix this:

1.) The insn comparison during crossjumping analysis should draw the alias information into. Two insns with different alias data should never be considered "mergable".

2.) If insns get merged during crossjumping the memory reference in the resulting insn must be marked with a general alias constraint.


Any suggestions?

Thanks

-Andreas-


Compiled with: gcc -O3 -mtune=z990 test.i -fno-strict-aliasing

gcc -v says:

Configured with: ../gcc/configure --prefix=/build/cvs/mygcc --mandir=/usr/share/man --infodir=/usr/share/info --enable-threads=posix --enable-shared --with-system-zlib --enable-__cxa_atexit --disable-multilib --enable-serial-configure --enable-languages=c,c++
Thread model: posix
gcc version 3.4.0 20040115 (experimental)

typedef struct {
  int a;
} R;

typedef struct s {
  void* any;
  int   flags;
} S;

typedef struct {
  char * pv;
  int    cur;
} T;

extern union {
  int ival;
  R *opval;
} x;

extern R * p1;
extern S * p2;

char* bar (S* sv, int* lp);

int
foo(void)
{
  int y = x.ival;

  if (y == 0) {
    x.opval = p1;         // mvc 
    p1 = (R*)((void *)0); // st     -1-
    return 260;
  }
  if (y == 5) {
    S *s;
 
    if ((s->flags & 0xff) == 5) {

      int l;
      char *p;

      p = (s->flags & 0x40000) ? ((l = ((T*) s->any)->cur), 
				  ((T*) s->any)->pv) : bar(s, &l);
    }

    p2 = (S*)((void *)0); //  -2-    
    return 260;
  }
}