Bug 18178 - Missed opportunity for removing bounds checking
Summary: Missed opportunity for removing bounds checking
Status: RESOLVED DUPLICATE of bug 21855
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.0.0
: P2 enhancement
Target Milestone: 4.1.0
Assignee: Diego Novillo
URL:
Keywords: alias, missed-optimization
Depends on:
Blocks: 19659
  Show dependency treegraph
 
Reported: 2004-10-27 14:09 UTC by Andrew Pinski
Modified: 2005-06-04 17:00 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-04-13 18:06:49


Attachments
equivalent C++ test case with parameters (282 bytes, text/plain)
2005-02-08 20:40 UTC, Tom Tromey
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew Pinski 2004-10-27 14:09:45 UTC
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;
  }
}
Comment 1 Andrew Pinski 2004-10-27 14:15:41 UTC
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;

}
Comment 2 Andrew Pinski 2004-10-28 14:24:29 UTC
Confirmed.
Comment 3 Tom Tromey 2005-02-08 20:40:46 UTC
Created attachment 8144 [details]
equivalent C++ test case with parameters

This test case shows VRP both working and not working depending
on how it is compiled.
Right now it only works when THIRD is not defined and
WORK_WORK_WORK is defined.  In the other two cases it leaves
the dead 'throw' in.
Comment 4 Steven Bosscher 2005-02-08 21:07:01 UTC
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. 
 
Comment 5 CVS Commits 2005-02-18 21:29:03 UTC
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

Comment 6 Diego Novillo 2005-02-18 21:44:56 UTC
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.  
Comment 7 Paul Schlie 2005-02-18 21:57:44 UTC
(In reply to comment #6)
> Fix.  http://gcc.gnu.org/ml/gcc-patches/2005-02/msg01074.html.

For 4.0 ?

Comment 8 Andrew Pinski 2005-02-18 22:00:39 UTC
(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.
Comment 9 Andrew Pinski 2005-02-18 22:01:27 UTC
Suspending as fixed and moving the target milestone to 4.1.0 so we know to retest it when tcb gets 
merged in.
Comment 10 Andrew Pinski 2005-04-13 18:06:49 UTC
Now the problem is that we don't remove the extra load of a->length because of aliasing.
Comment 11 Diego Novillo 2005-06-04 17:00:33 UTC
21855 has some analysis.  Better use that one.

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