[Bug tree-optimization/18178] New: Missed opportunity for removing bounds checking

[Bug tree-optimization/18178] New: Missed opportunity for removing bounds checking

[pinskia at gcc dot gnu dot org]

We miss an opportunity to remove the bounds checking code in the following case (this shows up a 
huge amount in libjava and other code):
class t
{
  void f(int a[])
  {
     for(int i=0;i<a.length;i++)
       a[i] = 0;
  }
}

-- 
           Summary: Missed opportunity for removing bounds checking
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-10-27 14:15 -------
The tree level looks like after optimization:
t.f(int[]) (this, a)
{
  int i;
  int D.385;
  unsigned int i.3;
  int D.376;

<bb 0>:
  D.376 = a->length;
  if (D.376 <= 0) goto <L8>; else goto <L17>;

<L17>:;
  i = 0;

<L1>:;
  i.3 = (unsigned int) i;
  if ((unsigned int) D.376 > i.3) goto <L5>; else goto <L2>;

<L2>:;
  D.385 = _Jv_ThrowBadArrayIndex (i);

<L5>:;
  *(&a->data[0] + (int *) i.3 * 4B) = 0;

;
  i = (int) (i.3 + 1);
  D.376 = a->length;
  if (i >= D.376) goto <L8>; else goto <L1>;

<L8>:;
  return;

}

-- 


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[tromey at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tromey at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-10-28 14:24 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-10-28 14:24:30
               date|                            |


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[dnovillo at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |dnovillo at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-01-13 02:03:16         |2005-02-08 19:15:05
               date|                            |


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-08 21:07 -------
We have this hunk in the .vrp dump: 
 
  # BLOCK 1 
  # PRED: 4 (true,exec) 
<L0>:; 
  iD.1901_30 = iD.1901_1; 
  D.1909_31 = D.1909_4; 
  i.0D.1911_5 = (unsigned intD.6) iD.1901_30; 
  D.1909_6 = D.1909_31; 
  D.1912_7 = (unsigned intD.6) D.1909_6; 
  if (i.0D.1911_5 >= D.1912_7) goto <L1>; else goto <L2>; 
  # SUCC: 2 (true,exec) 3 (false,exec) 
 
  # BLOCK 2 
  # PRED: 1 (true,exec) 
<L1>:; 
  #   TMT.3D.1926_25 = V_MAY_DEF <TMT.3D.1926_20>; 
  #   TMT.2D.1925_26 = V_MAY_DEF <TMT.2D.1925_19>; 
  #   VUSE <_ZTIiD.1905_14>; 
  D.1904_16 = __cxa_allocate_exception (4); 
  D.1914_18 = (intD.2 *) D.1904_16; 
  #   TMT.3D.1926_27 = V_MAY_DEF <TMT.3D.1926_25>; 
  *D.1914_18 = 5; 
  D.1914_2 = D.1914_18; 
  #   VUSE <_ZTIiD.1905_14>; 
  #   VUSE <TMT.3D.1926_27>; 
  #   VUSE <TMT.2D.1925_26>; 
  __cxa_throw (D.1904_16, &_ZTIiD.1905, 0B); 
  # SUCC: 
 
  # BLOCK 3 
  # PRED: 1 (false,exec) 
<L2>:; 
 
and: 
i.0_5: VARYING 
D.1909_6: [-2147483648, i_30 - 1] 
D.1912_7: VARYING 
 
 
If WORK_WORK_WORK is defined, we have: 
  # BLOCK 1 
  # PRED: 4 (true,exec) 
<L0>:; 
  iD.1901_30 = iD.1901_1; 
  D.1909_31 = D.1909_4; 
  D.1909_5 = D.1909_31; 
  if (iD.1901_30 >= D.1909_5) goto <L1>; else goto <L2>; 
  # SUCC: 2 (true,exec) 3 (false,exec) 
 
  # BLOCK 2 
  # PRED: 1 (true,exec) 
<L1>:; 
  #   TMT.2D.1925_24 = V_MAY_DEF <TMT.2D.1925_19>; 
  #   TMT.1D.1924_25 = V_MAY_DEF <TMT.1D.1924_18>; 
  #   VUSE <_ZTIiD.1905_13>; 
  D.1904_15 = __cxa_allocate_exception (4); 
  D.1912_17 = (intD.2 *) D.1904_15; 
  #   TMT.2D.1925_26 = V_MAY_DEF <TMT.2D.1925_24>; 
  *D.1912_17 = 5; 
  D.1912_2 = D.1912_17; 
  #   VUSE <_ZTIiD.1905_13>; 
  #   VUSE <TMT.2D.1925_26>; 
  #   VUSE <TMT.1D.1924_25>; 
  __cxa_throw (D.1904_15, &_ZTIiD.1905, 0B); 
  # SUCC: 
 
  # BLOCK 3 
  # PRED: 1 (false,exec) 
<L2>:; 
 
and 
i_30: [0, D.1909_4 - 1] 
D.1909_5: [0, i_30 - 1] 
 
Note that even though (i_30 >= D.1909_5), VRP does not clean this up. 
The exception stays there until DOM1. 
 

-- 


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-02-18 21:29 -------
Subject: Bug 18178

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	tree-cleanup-branch
Changes by:	dnovillo@gcc.gnu.org	2005-02-18 21:28:58

Modified files:
	gcc            : ChangeLog.tcb Makefile.in tree-into-ssa.c 
	                 tree-vrp.c 
	gcc/testsuite  : ChangeLog.tcb 
	gcc/testsuite/gcc.dg/tree-ssa: ssa-pre-2.c ssa-pre-3.c 
	                               ssa-pre-4.c ssa-pre-5.c 
	                               ssa-pre-6.c 
Added files:
	gcc/testsuite/g++.dg/tree-ssa: pr18178.C 

Log message:
	PR tree-optimization/18178
	* Makefile.in (tree-vrp.o): Depend on CFGLOOP_H,
	tree-scalar-evolution.h and tree-chrec.h.
	* tree-into-ssa.c (prepare_block_for_update): Also rewrite
	operands of statements that define new names.
	* tree-vrp.c: Include cfgloop.h, tree-scalar-evolution.h and
	tree-chrec.h.
	(cfg_loops): New local variable.
	(compare_values): Forward declare.
	(copy_value_range): Remove.
	(set_value_range): Add range integrity checks.
	Decay to VR_VARYING ranges that take all possible values in
	the type domain.
	(compare_values): Do some symbolic comparisons.
	(value_inside_range): Move earlier in the file.
	(value_ranges_intersect_p): Likewise.
	(extract_range_from_assert): If the ASSERT_EXPR conditional
	and the variable have intersecting ranges, use the
	intersection to derive a narrower range.
	(extract_range_from_ssa_name): New function.
	(extract_range_from_binary_expr): Re-arrange to always call
	set_value_range to set the newly computed range.
	(extract_range_from_unary_expr): Likewise.
	Do not special case ABS_EXPR.
	If a type cast operation changes to a type of different size,
	set the resulting range to VR_VARYING.
	If the new range has the limits swapped around, set the result
	to VR_VARYING.
	(extract_range_from_expr): Call extract_range_from_ssa_name.
	(compare_ranges): Allow symbolic ranges.
	Fix calls to compare_values to always check for specific
	return values.
	(compare_range_with_value): Likewise.
	(adjust_range_with_scev): New function.
	(vrp_visit_assignment): Call it if the statement is inside a
	loop.
	(vrp_meet): Always call set_value_range to set the newly
	computed range.
	(vrp_visit_phi_node): Remove FIXME regarding derivation.
	(execute_vrp): Call loop_optimizer_init, scev_initialize,
	scev_finalize and loop_optimizer_finalize.
	
	testsuite/ChangeLog.tcb:
	
	* testsuite/gcc.dg/tree-ssa/ssa-pre-2.c: Adjust expected pattern.
	* testsuite/gcc.dg/tree-ssa/ssa-pre-3.c: Likewise.
	* testsuite/gcc.dg/tree-ssa/ssa-pre-4.c: Likewise.
	* testsuite/gcc.dg/tree-ssa/ssa-pre-5.c: Likewise.
	* testsuite/gcc.dg/tree-ssa/ssa-pre-6.c: Likewise.
	
	PR tree-optimization/18178
	* testsuite/g++.dg/tree-ssa/pr18178.C: New test.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.tcb.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.1.2.23&r2=1.1.2.24
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/Makefile.in.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.1396.2.18&r2=1.1396.2.19
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-into-ssa.c.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=2.21.2.12&r2=2.21.2.13
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-vrp.c.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.1.2.4&r2=1.1.2.5
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.tcb.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.1.2.6&r2=1.1.2.7
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/g++.dg/tree-ssa/pr18178.C.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=NONE&r2=1.1.2.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-2.c.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.3&r2=1.3.10.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-3.c.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.1.10.1&r2=1.1.10.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-4.c.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.1.2.1&r2=1.1.2.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-5.c.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.1.2.1&r2=1.1.2.2
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-6.c.diff?cvsroot=gcc&only_with_tag=tree-cleanup-branch&r1=1.1.2.1&r2=1.1.2.2



-- 


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-02-18 21:44 -------

Fix.  http://gcc.gnu.org/ml/gcc-patches/2005-02/msg01074.html.

The patch allows VRP to eliminate 42% more conditionals on cc1-i-files and 173%
more conditionals on DLV.  But produces little difference in MICO and TRAMP3D.  

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[schlie at comcast dot net]

------- Additional Comments From schlie at comcast dot net  2005-02-18 21:57 -------
(In reply to comment #6)
> Fix.  http://gcc.gnu.org/ml/gcc-patches/2005-02/msg01074.html.

For 4.0 ?



-- 


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-18 22:00 -------
(In reply to comment #7)
> (In reply to comment #6)
> > Fix.  http://gcc.gnu.org/ml/gcc-patches/2005-02/msg01074.html.
> 
> For 4.0 ?

No, but for 4.1, reopening as there is no 4.1 right now.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-18 22:01 -------
Suspending as fixed and moving the target milestone to 4.1.0 so we know to retest it when tcb gets 
merged in.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |SUSPENDED
   Target Milestone|---                         |4.1.0


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-04-13 18:06 -------
Now the problem is that we don't remove the extra load of a->length because of aliasing.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|SUSPENDED                   |NEW
           Keywords|                            |alias
   Last reconfirmed|2005-02-08 19:15:05         |2005-04-13 18:06:49
               date|                            |


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

[Bug tree-optimization/18178] Missed opportunity for removing bounds checking

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-06-04 17:00 -------

21855 has some analysis.  Better use that one.

*** This bug has been marked as a duplicate of 21855 ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |DUPLICATE


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