[Bug tree-optimization/29789] Missed invariant out of the loop with conditionals and shifts

[rguenth at gcc dot gnu dot org]

--- Comment #8 from rguenth at gcc dot gnu dot org  2007-04-22 12:27 ---
Subject: Bug 29789

Author: rguenth
Date: Sun Apr 22 12:26:49 2007
New Revision: 124042

URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=124042
Log:
2007-04-22  Richard Guenther  [EMAIL PROTECTED]

PR tree-optimization/29789
* tree-ssa-loop-im.c (stmt_cost): Adjust cost of shifts.
(rewrite_reciprocal): New helper split out from
determine_invariantness_stmt.
(rewrite_bittest): Likewise.
(determine_invariantness_stmt): Rewrite (A  B)  1 to
A  (1  B) if (1  B) is loop invariant but (A  B)
is not.

* gcc.dg/tree-ssa/ssa-lim-1.c: New testcase.
* gcc.dg/tree-ssa/ssa-lim-2.c: Likewise.

Added:
trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-1.c
trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-2.c
Modified:
trunk/gcc/ChangeLog
trunk/gcc/testsuite/ChangeLog
trunk/gcc/tree-ssa-loop-im.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29789

[Bug tree-optimization/29789] Missed invariant out of the loop with conditionals and shifts

[rguenth at gcc dot gnu dot org]

--- Comment #9 from rguenth at gcc dot gnu dot org  2007-04-22 12:35 ---
Fixed.  The combining the bit-test issue is split to PR31657.


-- 

rguenth at gcc dot gnu dot org changed:

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution||FIXED
   Target Milestone|--- |4.3.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29789

[Bug tree-optimization/29789] Missed invariant out of the loop with conditionals and shifts

[rguenth at gcc dot gnu dot org]

--- Comment #5 from rguenth at gcc dot gnu dot org  2007-04-20 15:33 ---
Note that this does fix the loop invariant motion only in the case of two
ifs can be merged (because that re-instantiates the A  (1  B) form).  The
following parts are still not resolved:

void quantum_cnot(int control, int target, unsigned long *state, int size)
{
  int i;

  for(i=0; isize; i++)
{
  if (state[i]  ((unsigned long) 1  control))
state[i] ^= ((unsigned long) 1  target);
}
}

(and more similar loops in libquantum).  It would be nice if rtl loop-invariant
motion could detect this form:

(insn 23 22 24 4 (parallel [
(set (reg:DI 67)
(lshiftrt:DI (reg:DI 62 [ D.1992 ])
(subreg:QI (reg/v:SI 63 [ control ]) 0)))
(clobber (reg:CC 17 flags))
]) 470 {*lshrdi3_1_rex64} (nil)
(nil))

(insn 24 23 25 4 (parallel [
(set (reg:SI 68)
(and:SI (subreg:SI (reg:DI 67) 0)
(const_int 1 [0x1])))
(clobber (reg:CC 17 flags))
]) 301 {*andsi_1} (nil)
(nil))

and move the invariant (1  control).  It does move the (1  target) which
looks like

(insn 30 28 31 5 (set (reg:DI 70)
(const_int 1 [0x1])) 82 {*movdi_1_rex64} (nil)
(nil))

(insn 31 30 32 5 (parallel [
(set (reg:DI 69)
(ashift:DI (reg:DI 70)
(subreg:QI (reg/v:SI 64 [ target ]) 0)))
(clobber (reg:CC 17 flags))
]) 411 {*ashldi3_1_rex64} (nil)
(expr_list:REG_EQUAL (ashift:DI (const_int 1 [0x1])
(subreg:QI (reg/v:SI 64 [ target ]) 0))
(nil)))


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29789

[Bug tree-optimization/29789] Missed invariant out of the loop with conditionals and shifts

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

--- Comment #6 from rakdver at atrey dot karlin dot mff dot cuni dot cz  
2007-04-20 16:09 ---
Subject: Re:  Missed invariant out of the loop with conditionals and shifts

 void quantum_cnot(int control, int target, unsigned long *state, int size)
 {
   int i;
 
   for(i=0; isize; i++)
 {
   if (state[i]  ((unsigned long) 1  control))
 state[i] ^= ((unsigned long) 1  target);
 }
 }
 
 (and more similar loops in libquantum).  It would be nice if rtl 
 loop-invariant
 motion could detect this form:
 
 (insn 23 22 24 4 (parallel [
 (set (reg:DI 67)
 (lshiftrt:DI (reg:DI 62 [ D.1992 ])
 (subreg:QI (reg/v:SI 63 [ control ]) 0)))
 (clobber (reg:CC 17 flags))
 ]) 470 {*lshrdi3_1_rex64} (nil)
 (nil))
 
 (insn 24 23 25 4 (parallel [
 (set (reg:SI 68)
 (and:SI (subreg:SI (reg:DI 67) 0)
 (const_int 1 [0x1])))
 (clobber (reg:CC 17 flags))
 ]) 301 {*andsi_1} (nil)
 (nil))
 
 and move the invariant (1  control).

how exactly do you imagine this transformation should work?  The insns
you show essentially are

tmp = x  control;
z = tmp  1;

I do not see how to transform just this pattern profitably (without also
seeing that z is only used in condition).

I could hack something in, however handling just this single pattern
specially seems a bit weird to me.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29789

[Bug tree-optimization/29789] Missed invariant out of the loop with conditionals and shifts

[rguenth at gcc dot gnu dot org]

--- Comment #4 from rguenth at gcc dot gnu dot org  2007-04-20 13:51 ---
Mine.  I have a tree if-conversion patch that produces

L0:;
  D.1993 = MEM[base: state, index: ivtmp.32, step: 8];
  if (pretmp.25 == (pretmp.25  D.1993)) goto L1; else goto L3;

L1:;
  MEM[base: state, index: ivtmp.32, step: 8] = 1  target ^ D.1993;

L3:;
  ivtmp.32 = ivtmp.32 + 1;
  if (size  (int) ivtmp.32) goto L0; else goto L6;

and finally

.L4:
movq(%r11,%r9,8), %rdi
movq%rsi, %rax
andq%rdi, %rax
cmpq%rax, %rsi
jne .L5
xorq%rdx, %rdi
movq%rdi, (%r11,%r9,8)
.L5:
addq$1, %r9
cmpl%r9d, %r8d
jg  .L4

for the inner loop.


-- 

rguenth at gcc dot gnu dot org changed:

   What|Removed |Added

 AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
   |dot org |org
 Status|NEW |ASSIGNED
   Last reconfirmed|2006-11-10 01:55:58 |2007-04-20 13:51:52
   date||


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29789

[Bug tree-optimization/29789] Missed invariant out of the loop with conditionals and shifts

[rguenth at gcc dot gnu dot org]

--- Comment #7 from rguenth at gcc dot gnu dot org  2007-04-20 16:59 ---
I posted a patch for the tree level im instead to handle this special case
right
after the reciprocal special case.  I agree it's a special case, but as it
happens
in spec 2k6...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29789