This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tcb] Add range assertion expressions to GIMPLE
- From: Diego Novillo <dnovillo at redhat dot com>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 14 Dec 2004 22:08:18 -0500
- Subject: [tcb] Add range assertion expressions to GIMPLE
- Organization: Red Hat Canada
This patch is the initial step to VRP (Value Range Propagation). It is
still experimental and at the moment it is not even clear whether this
strategy is good or not.
The basic idea is to insert in the IL stream expressions that assert
that some predicate involving one or two SSA names is always true.
These assertion expressions take the form:
ASSERT_EXPR <X, X OP Y>
This means that given the object X, the predicate X OP Y has the boolean
value 'true'. The result of an ASSERT_EXPR is its first operand (X) and
they can only appear on the RHS of an assignment.
So, from the point of view of an optimizer the following assignment
X_1 = ASSERT_EXPR <X_3, X_3 > Y_9>
means two things: (a) X_1 is a copy of X_3, and, (b) X_3 is greater than
Y_9. This information is very similar to what we currently capture
during dominator optimizations, but since it's explicitly inserted in
the IL stream it can be used outside of DOM as well. For instance, given
foo (x)
{
if (x == 3) goto <L0>; else goto <L1>;
<L0>:;
D.1119 = x + 2;
goto <bb 3> (<L2>);
<L1>:;
D.1119 = x > 0;
<L2>:;
return D.1119;
}
After range assertion expressions are inserted, we get
foo (x)
{
if (x == 3) goto <L0>; else goto <L1>;
<L0>:;
x = ASSERT_EXPR <x, x == 3>;
D.1119 = x + 2;
goto <bb 3> (<L2>);
<L1>:;
x = ASSERT_EXPR <x, x != 3>;
D.1119 = x > 0;
<L2>:;
return D.1119;
}
which is then renamed into SSA as:
foo (x)
{
if (x_2 == 3) goto <L0>; else goto <L1>;
<L0>:;
x_6 = ASSERT_EXPR <x_2, x_2 == 3>;
D.1119_7 = x_6 + 2;
goto <bb 3> (<L2>);
<L1>:;
x_4 = ASSERT_EXPR <x_2, x_2 != 3>;
D.1119_5 = x_4 > 0;
# D.1119_1 = PHI <D.1119_7(1), D.1119_5(2)>;
<L2>:;
return D.1119_1;
}
So, now CCP can easily assume that x_6 is 3 (this functionality is not
included in this patch, though).
This patch only adds the ASSERT_EXPRs and does very little with the
information. Just the basic handling needed to make the optimizers
aware of it and mostly ignore it. Not surprisingly, this adds some
compile time overhead of .5 to 2% in the mix of applications I've got
(DLV, tramp3d, MICO, cc1-i-files, rt.ii and cpgram.ii).
I will now start to add the specific VRP bits and also making the other
optimizers understand ASSERT_EXPR. This should allow us to move
everything DOM used to do into their respective passes.
I had to add -Wno-warn to collect2.o because we are confusing the
warning that checks for arguments clobbered by 'fork' and 'longjmp'.
I'll file a PR against the branch and add the test case after this patch
goes in.
Bootstrapped and tested on x86, x86-64, alpha, ppc and ia64.
Diego.
2004-12-14 Diego Novillo <dnovillo@redhat.com>
Add expression assertions to GIMPLE.
* tree-vrp.c: New file.
* tree.def (ASSERT_EXPR): Define.
* Makefile.in (collect2.o): Compile with -Wno-error.
(tree-vrp.o): New rule.
(OBJS-common): Add tree-vrp.o.
* timevar.def (TV_TREE_INSERT_ASSERT): Define.
* fold-const.c (fold): Handle ASSERT_EXPR.
* tree-cfg.c (verify_expr): Likewise.
* tree-gimple.c (is_gimple_formal_tmp_rhs): Likewise.
* tree-inline.c (estimate_num_insns_): Likewise.
* tree-pretty-print.c (dump_generic_node): Likewise.
* tree-scalar-evolution.c (follow_ssa_edge_in_rhs): Likewise.
(interpret_rhs_modify_expr): Likewise.
* tree-ssa-dom.c (record_equivalences_from_stmt): Likewise.
* tree-ssa-operands.c (get_expr_operands): Likewise.
* tree-ssa-ccp.c (likely_value): Likewise.
(pass_ccp): Add TODO_cleanup_cfg to todo_flags_finish.
* tree-optimize.c (init_tree_optimization_passes): Schedule
pass_insert_range_assertions and pass_remove_range_assertions.
* tree-pass.h (pass_insert_range_assertions): Declare.
(pass_remove_range_assertions): Declare.
* tree-ssa-copy.c (stmt_may_generate_copy): Remove unnecessary
checks for aliased loads and aliased stores.
testsuite/ChangeLog.tcb:
* gcc.dg/tree-ssa/cfgcleanup-1.c: Expect output at DCE2.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1396.2.10
diff -d -c -p -u -r1.1396.2.10 Makefile.in
--- Makefile.in 11 Dec 2004 01:52:15 -0000 1.1396.2.10
+++ Makefile.in 15 Dec 2004 02:14:17 -0000
@@ -203,6 +203,7 @@ SYSCALLS.c.X-warn = -Wno-strict-prototyp
# recognizing that the loop will always be executed at least once. We need
# a new loop optimizer.
reload1.o-warn = -Wno-error
+collect2.o-warn = -Wno-error
# All warnings have to be shut off in stage1 if the compiler used then
# isn't gcc; configure determines that. WARN_CFLAGS will be either
@@ -929,7 +930,7 @@ OBJS-common = \
varasm.o varray.o vec.o version.o vmsdbgout.o xcoffout.o alloc-pool.o \
et-forest.o cfghooks.o bt-load.o pretty-print.o $(GGC) web.o passes.o \
rtl-profile.o tree-profile.o rtlhooks.o cfgexpand.o lambda-mat.o \
- lambda-trans.o lambda-code.o tree-loop-linear.o
+ lambda-trans.o lambda-code.o tree-loop-linear.o tree-vrp.o
OBJS-md = $(out_object_file)
OBJS-archive = $(EXTRA_OBJS) $(host_hook_obj) tree-inline.o \
@@ -1669,6 +1670,9 @@ tree-ssa-pre.o : tree-ssa-pre.c $(TREE_F
tree-vn.o : tree-vn.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(GGC_H) \
$(TREE_H) $(TREE_FLOW_H) $(HASHTAB_H) langhooks.h tree-pass.h \
$(TREE_DUMP_H) diagnostic.h
+tree-vrp.o : tree-vrp.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
+ $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) diagnostic.h $(GGC_H) \
+ $(BASIC_BLOCK_H)
tree-cfg.o : tree-cfg.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) $(FLAGS_H) output.h \
diagnostic.h errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h \
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.461.2.7
diff -d -c -p -u -r1.461.2.7 fold-const.c
--- fold-const.c 11 Dec 2004 01:52:35 -0000 1.461.2.7
+++ fold-const.c 15 Dec 2004 02:14:22 -0000
@@ -9268,6 +9268,21 @@ fold (tree expr)
}
return t;
+ case ASSERT_EXPR:
+ {
+ /* Given ASSERT_EXPR <Y, COND>, return Y if COND can be folded
+ to boolean_true_node. If COND folds to boolean_false_node,
+ return ASSERT_EXPR <Y, 0>. Otherwise, return the original
+ expression. */
+ tree c = fold (arg1);
+ if (c == boolean_true_node)
+ return arg0;
+ else if (c == boolean_false_node)
+ return build (ASSERT_EXPR, TREE_TYPE (t), arg0, c);
+ else
+ return t;
+ }
+
default:
return t;
} /* switch (code) */
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.36.2.6
diff -d -c -p -u -r1.36.2.6 timevar.def
--- timevar.def 6 Dec 2004 01:03:45 -0000 1.36.2.6
+++ timevar.def 15 Dec 2004 02:14:22 -0000
@@ -64,6 +64,7 @@ DEFTIMEVAR (TV_TREE_GIMPLIFY , "tre
DEFTIMEVAR (TV_TREE_EH , "tree eh")
DEFTIMEVAR (TV_TREE_CFG , "tree CFG construction")
DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanup")
+DEFTIMEVAR (TV_TREE_INSERT_ASSERT , "tree insert assertions")
DEFTIMEVAR (TV_TREE_COPY_PROP , "tree copy propagation")
DEFTIMEVAR (TV_TREE_STORE_COPY_PROP , "tree store copy propagation")
DEFTIMEVAR (TV_FIND_REFERENCED_VARS , "tree find referenced vars")
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.55.2.11
diff -d -c -p -u -r2.55.2.11 tree-cfg.c
--- tree-cfg.c 11 Dec 2004 01:52:47 -0000 2.55.2.11
+++ tree-cfg.c 15 Dec 2004 02:14:27 -0000
@@ -3264,6 +3264,15 @@ verify_expr (tree *tp, int *walk_subtree
}
break;
+ case ASSERT_EXPR:
+ x = fold (TREE_OPERAND (t, 1));
+ if (x == boolean_false_node)
+ {
+ error ("ASSERT_EXPR with an always false condition");
+ return *tp;
+ }
+ break;
+
case MODIFY_EXPR:
x = TREE_OPERAND (t, 0);
if (TREE_CODE (x) == BIT_FIELD_REF
Index: tree-gimple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-gimple.c,v
retrieving revision 2.24.2.6
diff -d -c -p -u -r2.24.2.6 tree-gimple.c
--- tree-gimple.c 11 Dec 2004 01:52:50 -0000 2.24.2.6
+++ tree-gimple.c 15 Dec 2004 02:14:28 -0000
@@ -73,6 +73,7 @@ is_gimple_formal_tmp_rhs (tree t)
case COMPLEX_CST:
case VECTOR_CST:
case OBJ_TYPE_REF:
+ case ASSERT_EXPR:
return true;
default:
Index: tree-inline.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.c,v
retrieving revision 1.142.2.7
diff -d -c -p -u -r1.142.2.7 tree-inline.c
--- tree-inline.c 11 Dec 2004 01:52:50 -0000 1.142.2.7
+++ tree-inline.c 15 Dec 2004 02:14:29 -0000
@@ -1223,6 +1223,7 @@ estimate_num_insns_1 (tree *tp, int *wal
x = TREE_OPERAND (x, 0);
/* FALLTHRU */
case TARGET_EXPR:
+ case ASSERT_EXPR:
case CONSTRUCTOR:
{
HOST_WIDE_INT size;
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.47.2.11
diff -d -c -p -u -r2.47.2.11 tree-optimize.c
--- tree-optimize.c 6 Dec 2004 01:03:47 -0000 2.47.2.11
+++ tree-optimize.c 15 Dec 2004 02:14:29 -0000
@@ -344,6 +344,7 @@ init_tree_optimization_passes (void)
*p = NULL;
p = &pass_all_optimizations.sub;
+ NEXT_PASS (pass_insert_range_assertions);
NEXT_PASS (pass_referenced_vars);
NEXT_PASS (pass_maybe_create_global_var);
NEXT_PASS (pass_build_ssa);
@@ -394,6 +395,7 @@ init_tree_optimization_passes (void)
NEXT_PASS (pass_tail_calls);
NEXT_PASS (pass_rename_ssa_copies);
NEXT_PASS (pass_late_warn_uninitialized);
+ NEXT_PASS (pass_remove_range_assertions);
NEXT_PASS (pass_del_ssa);
NEXT_PASS (pass_nrv);
NEXT_PASS (pass_remove_useless_vars);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.15.2.8
diff -d -c -p -u -r2.15.2.8 tree-pass.h
--- tree-pass.h 6 Dec 2004 01:03:48 -0000 2.15.2.8
+++ tree-pass.h 15 Dec 2004 02:14:29 -0000
@@ -162,6 +162,8 @@ extern struct tree_opt_pass pass_remove_
extern struct tree_opt_pass pass_rename_ssa_copies;
extern struct tree_opt_pass pass_expand;
extern struct tree_opt_pass pass_rest_of_compilation;
+extern struct tree_opt_pass pass_insert_range_assertions;
+extern struct tree_opt_pass pass_remove_range_assertions;
extern struct tree_opt_pass pass_fre;
extern struct tree_opt_pass pass_linear_transform;
extern struct tree_opt_pass pass_maybe_create_global_var;
Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pretty-print.c,v
retrieving revision 2.38.2.5
diff -d -c -p -u -r2.38.2.5 tree-pretty-print.c
--- tree-pretty-print.c 11 Dec 2004 01:52:51 -0000 2.38.2.5
+++ tree-pretty-print.c 15 Dec 2004 02:14:29 -0000
@@ -1431,6 +1431,14 @@ dump_generic_node (pretty_printer *buffe
pp_printf (buffer, "VH.%d", VALUE_HANDLE_ID (node));
break;
+ case ASSERT_EXPR:
+ pp_string (buffer, "ASSERT_EXPR <");
+ dump_generic_node (buffer, TREE_OPERAND (node, 0), spc, flags, false);
+ pp_string (buffer, ", ");
+ dump_generic_node (buffer, TREE_OPERAND (node, 1), spc, flags, false);
+ pp_string (buffer, ">");
+ break;
+
case SCEV_KNOWN:
pp_string (buffer, "scev_known");
break;
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.7.2.3
diff -d -c -p -u -r2.7.2.3 tree-scalar-evolution.c
--- tree-scalar-evolution.c 18 Nov 2004 03:12:54 -0000 2.7.2.3
+++ tree-scalar-evolution.c 15 Dec 2004 02:14:30 -0000
@@ -1065,8 +1065,8 @@ follow_ssa_edge_in_rhs (struct loop *loo
- an INTEGER_CST,
- a PLUS_EXPR,
- a MINUS_EXPR,
- - other cases are not yet handled.
- */
+ - an ASSERT_EXPR,
+ - other cases are not yet handled. */
switch (TREE_CODE (rhs))
{
case NOP_EXPR:
@@ -1247,6 +1247,20 @@ follow_ssa_edge_in_rhs (struct loop *loo
break;
+ case ASSERT_EXPR:
+ {
+ /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
+ It must be handled as a copy assignment of the form a_1 = a_2. */
+ tree op0 = TREE_OPERAND (rhs, 0);
+ if (TREE_CODE (op0) == SSA_NAME)
+ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
+ halting_phi, evolution_of_loop);
+ else
+ res = false;
+ break;
+ }
+
+
default:
res = false;
break;
@@ -1701,6 +1715,11 @@ interpret_rhs_modify_expr (struct loop *
case SSA_NAME:
res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
break;
+
+ case ASSERT_EXPR:
+ opnd10 = TREE_OPERAND (opnd1, 0);
+ res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10));
+ break;
case NOP_EXPR:
case CONVERT_EXPR:
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-ccp.c,v
retrieving revision 2.41.2.9
diff -d -c -p -u -r2.41.2.9 tree-ssa-ccp.c
--- tree-ssa-ccp.c 6 Dec 2004 01:03:49 -0000 2.41.2.9
+++ tree-ssa-ccp.c 15 Dec 2004 02:14:32 -0000
@@ -473,6 +473,11 @@ likely_value (tree stmt)
&& TREE_CODE (stmt) != SWITCH_EXPR)
return VARYING;
+ /* FIXME, ASSERT_EXPRs can convey useful constants. */
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
+ return VARYING;
+
get_stmt_operands (stmt);
found_constant = false;
@@ -1604,7 +1609,7 @@ struct tree_opt_pass pass_ccp =
{
"ccp", /* name */
gate_ccp, /* gate */
- do_ssa_ccp, /* execute */
+ do_ssa_ccp, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
@@ -1652,6 +1657,7 @@ struct tree_opt_pass pass_store_ccp =
0, /* todo_flags_start */
TODO_dump_func | TODO_rename_vars
| TODO_ggc_collect | TODO_verify_ssa
+ | TODO_cleanup_cfg
| TODO_verify_stmts, /* todo_flags_finish */
0 /* letter */
};
Index: tree-ssa-copy.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-copy.c,v
retrieving revision 2.15.2.10
diff -d -c -p -u -r2.15.2.10 tree-ssa-copy.c
--- tree-ssa-copy.c 6 Dec 2004 01:03:49 -0000 2.15.2.10
+++ tree-ssa-copy.c 15 Dec 2004 02:14:32 -0000
@@ -175,6 +175,7 @@ merge_alias_info (tree orig, tree new)
gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig)));
gcc_assert (POINTER_TYPE_P (TREE_TYPE (new)));
+
#if defined ENABLE_CHECKING
gcc_assert (lang_hooks.types_compatible_p (TREE_TYPE (orig),
TREE_TYPE (new)));
@@ -366,9 +367,7 @@ stmt_may_generate_copy (tree stmt)
/* If we are not doing store copy-prop, statements with loads and/or
stores will never generate a useful copy. */
if (!do_store_copy_prop
- && (ann->makes_aliased_loads
- || ann->makes_aliased_stores
- || NUM_VUSES (VUSE_OPS (ann)) > 0
+ && (NUM_VUSES (VUSE_OPS (ann)) > 0
|| NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0
|| NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0))
return false;
@@ -531,7 +530,6 @@ copy_prop_visit_assignment (tree stmt, t
return SSA_PROP_VARYING;
*result_p = lhs;
-
if (set_copy_of_val (*result_p, rhs, NULL_TREE))
return SSA_PROP_INTERESTING;
else
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.44.2.9
diff -d -c -p -u -r2.44.2.9 tree-ssa-dom.c
--- tree-ssa-dom.c 11 Dec 2004 01:52:51 -0000 2.44.2.9
+++ tree-ssa-dom.c 15 Dec 2004 02:14:32 -0000
@@ -2682,6 +2682,20 @@ record_equivalences_from_stmt (tree stmt
|| is_gimple_min_invariant (rhs)))
SSA_NAME_VALUE (lhs) = rhs;
+ /* If the RHS is ASSERT_EXPR <X, COND>, record the conditional
+ COND as being true. */
+ if (may_optimize_p && TREE_CODE (rhs) == ASSERT_EXPR)
+ {
+ tree op = TREE_OPERAND (rhs, 0);
+ tree cond = fold (TREE_OPERAND (rhs, 1));
+ /* If STMT is inside a basic block that will never be
+ executed, the predicate of this ASSERT_EXPR will be
+ false. We need to handle this contradiction gracefully
+ because the CFG is not cleaned up while DOM runs. */
+ if (cond != boolean_false_node)
+ record_const_or_copy (lhs, op);
+ }
+
/* alloca never returns zero and the address of a non-weak symbol
is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
stripped as they do not affect this equivalence. */
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.44.2.8
diff -d -c -p -u -r2.44.2.8 tree-ssa-operands.c
--- tree-ssa-operands.c 11 Dec 2004 01:52:52 -0000 2.44.2.8
+++ tree-ssa-operands.c 15 Dec 2004 02:14:33 -0000
@@ -1202,6 +1202,7 @@ get_expr_operands (tree stmt, tree *expr
case TRUTH_XOR_EXPR:
case COMPOUND_EXPR:
case OBJ_TYPE_REF:
+ case ASSERT_EXPR:
do_binary:
{
tree op0 = TREE_OPERAND (expr, 0);
Index: tree-vrp.c
===================================================================
RCS file: tree-vrp.c
diff -N tree-vrp.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tree-vrp.c 15 Dec 2004 02:14:33 -0000
@@ -0,0 +1,340 @@
+/* Support routines for Value Range Propagation (VRP).
+ Contributed by Diego Novillo <dnovillo@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING. If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "tree.h"
+#include "basic-block.h"
+#include "tree-flow.h"
+#include "tree-pass.h"
+#include "timevar.h"
+#include "diagnostic.h"
+
+/* Given a comparison code, return its opposite. Note that this is *not*
+ the same as inverting its truth value (invert_tree_comparison). Here we
+ just want to literally flip the comparison around.
+
+ So, '<' gets '>', '<=' gets '>='. Both '==' and '!=' are returned
+ unchanged. */
+
+static enum tree_code
+opposite_comparison (enum tree_code code)
+{
+ switch (code)
+ {
+ case EQ_EXPR:
+ case NE_EXPR:
+ case ORDERED_EXPR:
+ case UNORDERED_EXPR:
+ case LTGT_EXPR:
+ case UNEQ_EXPR:
+ return code;
+ case GT_EXPR:
+ return LT_EXPR;
+ case GE_EXPR:
+ return LE_EXPR;
+ case LT_EXPR:
+ return GT_EXPR;
+ case LE_EXPR:
+ return GE_EXPR;
+ case UNGT_EXPR:
+ return UNLT_EXPR;
+ case UNGE_EXPR:
+ return UNLE_EXPR;
+ case UNLT_EXPR:
+ return UNGT_EXPR;
+ case UNLE_EXPR:
+ return UNGE_EXPR;
+ default:
+ gcc_unreachable ();
+ }
+}
+
+
+/* Given a COND_EXPR node E of the form 'V OP W', return a list of
+ assignments to ASSERT_EXPRs that mimic the comparison operand OP.
+ For instance, given 'V <= W', this function returns the assignments:
+
+ V = ASSERT_EXPR <V, V <= W>
+ W = ASSERT_EXPR <W, W >= V> */
+
+static tree
+build_assert_exprs (tree cond)
+{
+ tree list = NULL_TREE;
+ tree a1 = NULL_TREE;
+ tree a2 = NULL_TREE;
+
+ if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
+ {
+ /* Given X OP Y, build the assignments
+
+ X = ASSERT_EXPR <X, X OP Y>
+ Y = ASSERT_EXPR <Y, Y opposite<OP> X>
+
+ Make sure that either X or Y are a renameable _DECL,
+ otherwise we won't be able to create the assignments. */
+ tree op0 = TREE_OPERAND (cond, 0);
+ tree op1 = TREE_OPERAND (cond, 1);
+
+ cond = unshare_expr (cond);
+
+ if (DECL_P (op0))
+ {
+ a1 = build (MODIFY_EXPR, TREE_TYPE (op0), op0,
+ build (ASSERT_EXPR, TREE_TYPE (op0), op0, cond));
+ }
+
+ if (DECL_P (op1))
+ {
+ /* Switch the operands around and use the opposite comparison. */
+ cond = build (opposite_comparison (TREE_CODE (cond)),
+ TREE_TYPE (cond), op1, op0);
+ a2 = build (MODIFY_EXPR, TREE_TYPE (op1), op1,
+ build (ASSERT_EXPR, TREE_TYPE (op1), op1, cond));
+ }
+ }
+ else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
+ {
+ /* Given !X, build the assignment X = false. */
+ tree op0 = TREE_OPERAND (cond, 0);
+ if (DECL_P (op0))
+ a1 = build (MODIFY_EXPR, TREE_TYPE (op0), op0, boolean_false_node);
+ }
+ else if (DECL_P (cond))
+ {
+ /* Given X, build the assignment X = true. */
+ a1 = build (MODIFY_EXPR, TREE_TYPE (cond), cond, boolean_true_node);
+ }
+ else
+ gcc_unreachable ();
+
+ if (a1)
+ {
+ list = alloc_stmt_list ();
+ append_to_statement_list (a1, &list);
+ if (a2) append_to_statement_list (a2, &list);
+ }
+
+ return list;
+}
+
+
+/* Given a list L of assertion assignments, build another list with the
+ inverted version of each assertion. Assertions are inverted by
+ calling invert_truthvalue(). */
+
+static tree
+negate_assert_exprs (tree l)
+{
+ tree_stmt_iterator i;
+ tree neg_l;
+
+ neg_l = alloc_stmt_list ();
+
+ for (i = tsi_start (l); !tsi_end_p (i); tsi_next (&i))
+ {
+ tree rhs, a, neg_a;
+
+ a = tsi_stmt (i);
+
+ gcc_assert (TREE_CODE (a) == MODIFY_EXPR);
+
+ neg_a = unshare_expr (a);
+ rhs = TREE_OPERAND (neg_a, 1);
+
+ if (TREE_CODE (rhs) == ASSERT_EXPR)
+ {
+ tree op1 = TREE_OPERAND (rhs, 1);
+ TREE_OPERAND (rhs, 1) = invert_truthvalue (op1);
+
+ /* The inverted conditional must be GIMPLE, otherwise we lose
+ the ability to relate the variable on the LHS of the
+ assignment of an ASSERT_EXPR. */
+ gcc_assert (is_gimple_condexpr (TREE_OPERAND (rhs, 1)));
+ }
+ else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR)
+ {
+ tree op0 = TREE_OPERAND (rhs, 0);
+ TREE_OPERAND (rhs, 0) = invert_truthvalue (op0);
+ }
+ else if (rhs == boolean_true_node
+ || rhs == boolean_false_node)
+ {
+ TREE_OPERAND (neg_a, 1) = invert_truthvalue (rhs);
+ }
+ else
+ gcc_unreachable ();
+
+ append_to_statement_list (neg_a, &neg_l);
+ }
+
+ return neg_l;
+}
+
+
+/* Return false if EXPR is a predicate expression involving floating
+ point values. */
+
+static inline bool
+fp_predicate (tree expr)
+{
+ return TREE_CODE_CLASS (TREE_CODE (expr)) == tcc_comparison
+ && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0)));
+}
+
+
+/* Traverse the flowgraph looking for conditional jumps to insert range
+ expressions. These range expressions are meant to provide information
+ to optimizations that need to reason in terms of value ranges. They
+ will not be expanded into RTL. For instance, given:
+
+ x = ...
+ y = ...
+ if (x < y)
+ y = x - 2;
+ else
+ x = y + 3;
+
+ this pass will transform the code into:
+
+ x = ...
+ y = ...
+ if (x < y)
+ {
+ x = ASSERT_EXPR <x, x < y>
+ y = ASSERT_EXPR <y, y > x>
+ y = x - 2
+ }
+ else
+ {
+ x = ASSERT_EXPR <x, x >= y>
+ y = ASSERT_EXPR <y, y <= x>
+ x = y + 3
+ }
+
+ The idea is that once copy and constant propagation have run, other
+ optimizations will be able to determine what ranges of values can 'x'
+ take in different paths of the code, simply by checking the reaching
+ definition of 'x'. */
+
+static void
+execute_insert_range_assertions (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB (bb)
+ {
+ tree stmt = last_stmt (bb);
+
+ /* The last statement of the block must be an integer
+ comparison involving at least one renameable _DECL. */
+ if (stmt
+ && TREE_CODE (stmt) == COND_EXPR
+ && !fp_predicate (TREE_OPERAND (stmt, 0)))
+ {
+ edge e;
+ edge_iterator ei;
+ tree assertions, neg_assertions;
+
+ assertions = build_assert_exprs (TREE_OPERAND (stmt, 0));
+ if (assertions)
+ neg_assertions = negate_assert_exprs (assertions);
+
+ if (assertions)
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (e->flags & EDGE_TRUE_VALUE)
+ bsi_insert_on_edge (e, assertions);
+ else if ((e->flags & EDGE_FALSE_VALUE)
+ && neg_assertions)
+ bsi_insert_on_edge (e, neg_assertions);
+ else
+ gcc_unreachable ();
+ }
+ }
+ }
+
+ bsi_commit_edge_inserts ();
+}
+
+struct tree_opt_pass pass_insert_range_assertions =
+{
+ "add_assert", /* name */
+ NULL, /* gate */
+ execute_insert_range_assertions, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_INSERT_ASSERT, /* tv_id */
+ PROP_cfg | PROP_gimple_leh, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ TODO_cleanup_cfg, /* todo_flags_start */
+ TODO_dump_func | TODO_ggc_collect, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+
+/* Convert range assertion expressions into copies. FIXME, explain why. */
+
+static void
+execute_remove_range_assertions (void)
+{
+ basic_block bb;
+ block_stmt_iterator si;
+
+ FOR_EACH_BB (bb)
+ for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ {
+ tree stmt = bsi_stmt (si);
+
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
+ {
+ tree rhs = TREE_OPERAND (stmt, 1);
+ tree cond = fold (TREE_OPERAND (rhs, 1));
+ gcc_assert (cond != boolean_false_node);
+ TREE_OPERAND (stmt, 1) = TREE_OPERAND (rhs, 0);
+ modify_stmt (stmt);
+ }
+ }
+}
+
+
+struct tree_opt_pass pass_remove_range_assertions =
+{
+ "remove_assert", /* name */
+ NULL, /* gate */
+ execute_remove_range_assertions, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func | TODO_ggc_collect, /* todo_flags_finish */
+ 0 /* letter */
+};
Index: tree.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.def,v
retrieving revision 1.100.2.4
diff -d -c -p -u -r1.100.2.4 tree.def
--- tree.def 11 Dec 2004 01:52:56 -0000 1.100.2.4
+++ tree.def 15 Dec 2004 02:14:34 -0000
@@ -864,6 +864,20 @@ DEFTREECODE (STATEMENT_LIST, "statement_
the same value, they will be assigned the same value handle. */
DEFTREECODE (VALUE_HANDLE, "value_handle", tcc_exceptional, 0)
+/* Predicate assertion. Artificial expression generated by the optimizers
+ to keep track of predicate values. This expression may only appear on
+ the RHS of assignments.
+
+ Given X = ASSERT_EXPR <Y, EXPR>, the optimizers can infer
+ two things:
+
+ 1- X is a copy of Y.
+ 2- EXPR is a GIMPLE conditional expression (as defined by
+ is_gimple_condexpr) and is known to be true.
+
+ The type of the expression is the same as Y. */
+DEFTREECODE (ASSERT_EXPR, "assert_expr", tcc_expression, 2)
+
/* Base class information. Holds information about a class as a
baseclass of itself or another class. */
DEFTREECODE (TREE_BINFO, "tree_binfo", tcc_exceptional, 0)
Index: testsuite/gcc.dg/tree-ssa/cfgcleanup-1.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/cfgcleanup-1.c,v
retrieving revision 1.2
diff -d -c -p -u -r1.2 cfgcleanup-1.c
--- testsuite/gcc.dg/tree-ssa/cfgcleanup-1.c 13 May 2004 06:40:52 -0000 1.2
+++ testsuite/gcc.dg/tree-ssa/cfgcleanup-1.c 15 Dec 2004 02:14:38 -0000
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-dce1" } */
+/* { dg-options "-O2 -fdump-tree-dce2" } */
void
cleanup (int a, int b)
{
@@ -15,4 +15,4 @@ cleanup (int a, int b)
return;
}
/* Dce should get rid of the initializers and cfgcleanup should elliminate ifs */
-/* { dg-final { scan-tree-dump-times "if " 0 "dce1"} } */
+/* { dg-final { scan-tree-dump-times "if " 0 "dce2"} } */