[PATCH] Scalar evolution and hidden casts

[Eric Botcazou <ebotcazou at adacore dot com>]

Hi,

I've attached an Ada testcase that should totally collapse at -O -gnatp, i.e. 
generates only "A = A + 1000000000", but doesn't because scev is very picky 
about casts, even hidden casts (tree-chrec.c contains many type assertions).
The .lim dump file is entirely clean (attached, no casts) but .sccp shows that 
scev rematerializes some of them, yielding to scev_not_known:

Analyzing # of iterations of loop 2
  exit condition [2, + , 1] <= 1000000
  bounds on difference of bases: 999998 ... 999998
  result:
    # of iterations 999999, bounded by 999999
  (set_nb_iterations_in_loop = 999999))
(chrec_apply 
  (varying_loop = 2
)
  (chrec = {(integer) p__a_lsm.11_11, +, 1}_2)
  (x = 999999)
  (res = (integer) p__a_lsm.11_11 + 999999))
  (evolution_function = scev_not_known))


Teaching tree-chrec.c to disregard useless casts appears to be tricky, you 
very quickly run into one of the type assertions.  Another strategy, which 
works at least in this case, is to change the type of the chrec and use that 
of the SSA name.  Patch attached, tested on i586-suse-linux, OK for mainline?


2009-05-19  Eric Botcazou  <ebotcazou@adacore.com>

	* tree-scalar-evolution.c (follow_ssa_edge_expr) <PLUS_EXPR>: Propagate
	the type of the first operand.
	(follow_ssa_edge_in_rhs) <GIMPLE_BINARY_RHS>: Likewise.


-- 
Eric Botcazou

Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c	(revision 147612)
+++ tree-scalar-evolution.c	(working copy)
@@ -1181,6 +1181,7 @@ follow_ssa_edge_expr (struct loop *loop,
       /* This case is under the form "rhs0 +- rhs1".  */
       rhs0 = TREE_OPERAND (expr, 0);
       rhs1 = TREE_OPERAND (expr, 1);
+      type = TREE_TYPE (rhs0);
       STRIP_TYPE_NOPS (rhs0);
       STRIP_TYPE_NOPS (rhs1);
       return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
@@ -1215,16 +1216,17 @@ static t_bool
 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
 			gimple halting_phi, tree *evolution_of_loop, int limit)
 {
-  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
   enum tree_code code = gimple_assign_rhs_code (stmt);
 
   switch (get_gimple_rhs_class (code))
     {
     case GIMPLE_BINARY_RHS:
-      return follow_ssa_edge_binary (loop, stmt, type,
-				     gimple_assign_rhs1 (stmt), code,
-				     gimple_assign_rhs2 (stmt),
-				     halting_phi, evolution_of_loop, limit);
+      {
+	tree rhs1 = gimple_assign_rhs1 (stmt);
+	return follow_ssa_edge_binary (loop, stmt, TREE_TYPE (rhs1), rhs1,
+				       code, gimple_assign_rhs2 (stmt),
+				       halting_phi, evolution_of_loop, limit);
+      }
     case GIMPLE_SINGLE_RHS:
       return follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
 				   halting_phi, evolution_of_loop, limit);
@@ -1232,6 +1234,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
       if (code == NOP_EXPR)
 	{
 	  /* This assignment is under the form "a_1 = (cast) rhs.  */
+	  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
 	  t_bool res
 	    = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
 				    halting_phi, evolution_of_loop, limit);

package P is
  A : Integer := 0;
  procedure Main;
end P;

;; Function P.Main (p__main)



Symbols to be put in SSA form

{ .MEM p__a_lsm.11 }


Incremental SSA update started at block: 0

Number of blocks in CFG: 9
Number of blocks to update: 8 ( 89%)




SSA replacement table
N_i -> { O_1 ... O_j } means that N_i replaces O_1, ..., O_j

p__a_lsm.11_5 -> { p__a_lsm.11_9 }
p__a_lsm.11_10 -> { p__a_lsm.11_9 }

Number of virtual NEW -> OLD mappings:       0
Number of real NEW -> OLD mappings:          2
Number of total NEW -> OLD mappings:         2

Number of virtual symbols: 0


Incremental SSA update started at block: 3

Number of blocks in CFG: 9
Number of blocks to update: 6 ( 67%)



P.Main ()
{
  integer p__a_lsm.11;
  integer p__a.0;
  integer p__a.1;
  integer i;
  integer j;

<bb 2>:
  p__a_lsm.11_12 = p__a;

<bb 3>:
  # j_16 = PHI <j_4(7), 1(2)>
  # p__a_lsm.11_11 = PHI <p__a_lsm.11_10(7), p__a_lsm.11_12(2)>

<bb 4>:
  # i_19 = PHI <i_8(5), 1(3)>
  # p__a_lsm.11_21 = PHI <p__a_lsm.11_9(5), p__a_lsm.11_11(3)>
  p__a.0_6 = p__a_lsm.11_21;
  p__a.1_7 = p__a.0_6 + 1;
  p__a_lsm.11_9 = p__a.1_7;
  i_8 = i_19 + 1;
  if (i_8 <= 1000000)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  goto <bb 4>;

<bb 6>:
  # p__a_lsm.11_10 = PHI <p__a_lsm.11_9(4)>
  j_4 = j_16 + 1;
  if (j_4 <= 1000)
    goto <bb 7>;
  else
    goto <bb 8>;

<bb 7>:
  goto <bb 3>;

<bb 8>:
  # p__a_lsm.11_5 = PHI <p__a_lsm.11_10(6)>
  p__a = p__a_lsm.11_5;
  return;

}


package body P is
  procedure Foo is
  begin
    for I in 1 .. 1_000_000 loop
      A := A + 1;
    end loop;
  end Foo;

  procedure Bar is
  begin
    for J in 1 .. 1_000 loop
      Foo;
    end loop;
  end Bar;

  procedure Main is
  begin
    Bar;
  end;
end P;