From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16265 invoked by alias); 28 Mar 2008 14:52:28 -0000 Received: (qmail 16246 invoked by uid 22791); 28 Mar 2008 14:52:27 -0000 X-Spam-Check-By: sourceware.org Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.31) with ESMTP; Fri, 28 Mar 2008 14:52:04 +0000 Received: from Relay2.suse.de (relay-ext.suse.de [195.135.221.8]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mx2.suse.de (Postfix) with ESMTP id 8B6844419E; Fri, 28 Mar 2008 15:52:01 +0100 (CET) Date: Fri, 28 Mar 2008 18:53:00 -0000 From: Richard Guenther To: gcc-patches@gcc.gnu.org Cc: Diego Novillo Subject: [PATCH] Fix PR14495 (1/2) Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2008-03/txt/msg01811.txt.bz2 This patch from last year fixes one part of PR14495 (VRP cannot simulate a switch stmt properly). Namely it teaches VRP the case of a single executable edge in a switch stmt. I believe this it likely to happen (only) with C++ and inlining after exposing constant propagation opportunities. It also introduces the find_case_label_index helper which will be needed in (2/2). Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for mainline? Thanks, Richard. 2008-03-28 Richard Guenther PR tree-optimization/14495 * tree-vrp.c (vrp_visit_cond_stmt): Do not handle SWITCH_EXPR here ... (vrp_visit_switch_stmt): ... but here (new function). (find_case_label_index): New helper function. (vrp_visit_stmt): Dispatch to vrp_visit_switch_stmt. * gcc.dg/tree-ssa/vrp38.c: New testcase. Index: gcc/tree-vrp.c =================================================================== *** gcc/tree-vrp.c.orig 2008-03-20 14:51:35.000000000 +0100 --- gcc/tree-vrp.c 2008-03-20 14:56:22.000000000 +0100 *************** vrp_visit_cond_stmt (tree stmt, edge *ta *** 5300,5310 **** bool sop; *taken_edge_p = NULL; - - /* FIXME. Handle SWITCH_EXPRs. */ - if (TREE_CODE (stmt) == SWITCH_EXPR) - return SSA_PROP_VARYING; - cond = COND_EXPR_COND (stmt); if (dump_file && (dump_flags & TDF_DETAILS)) --- 5300,5305 ---- *************** vrp_visit_cond_stmt (tree stmt, edge *ta *** 5398,5403 **** --- 5393,5539 ---- } + /* Searches the case label vector VEC for the index *IDX the CASE_LABEL + includes the value VAL. The search starts at index START_IDX and + true is returned if *IDX corresponds to such an index. False is + returned in case VAL hits the default case label and *IDX in this + case is the next higher or the next lower case label index. */ + + static bool + find_case_label_index (tree vec, size_t start_idx, tree val, size_t *idx) + { + size_t n = TREE_VEC_LENGTH (vec); + size_t low, high, i = start_idx; + + /* Find case label for minimum of the value range or the next one. */ + for (low = start_idx - 1, high = n - 1; high - low > 1; ) + { + tree t; + int cmp; + i = (high + low) / 2; + t = TREE_VEC_ELT (vec, i); + + /* Cache the result of comparing CASE_LOW and val. */ + cmp = tree_int_cst_compare (CASE_LOW (t), val); + + if (cmp > 0) + high = i; + else + low = i; + + if (CASE_HIGH (t) == NULL) + { + /* A singe-valued case label. */ + if (cmp == 0) + { + *idx = i; + return true; + } + } + else + { + /* A case range. We can only handle integer ranges. */ + if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0) + { + *idx = i; + return true; + } + } + } + + *idx = i; + return false; + } + + /* Visit switch statement STMT. If we can determine which edge + will be taken out of STMT's basic block, record it in + *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return + SSA_PROP_VARYING. */ + + static enum ssa_prop_result + vrp_visit_switch_stmt (tree stmt, edge *taken_edge_p) + { + tree op, val; + value_range_t *vr; + size_t i = 0, j = 0, n; + tree vec; + bool min_take_default, max_take_default; + + *taken_edge_p = NULL; + op = TREE_OPERAND (stmt, 0); + if (TREE_CODE (op) != SSA_NAME) + return SSA_PROP_VARYING; + + vr = get_value_range (op); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nVisiting switch expression with operand "); + print_generic_expr (dump_file, op, 0); + fprintf (dump_file, " with known range "); + dump_value_range (dump_file, vr); + fprintf (dump_file, "\n"); + } + + if (vr->type != VR_RANGE + || symbolic_range_p (vr)) + return SSA_PROP_VARYING; + + /* Find the single edge that is taken from the switch expression. */ + vec = SWITCH_LABELS (stmt); + n = TREE_VEC_LENGTH (vec); + + /* Find case label for minimum of the value range or the next one. */ + min_take_default = !find_case_label_index (vec, 0, vr->min, &i); + + /* Find case label for maximum of the value range or the previous one. */ + max_take_default = !find_case_label_index (vec, i, vr->max, &j); + + /* Check if we reach the default label only. */ + if (j < i) + val = TREE_VEC_ELT (vec, n - 1); + /* Check if we reach exactly one label and not the default label. */ + else if (i == j + && !min_take_default + && !max_take_default) + val = TREE_VEC_ELT (vec, i); + else + { + /* Check if labels with index i to j are all reaching the same label. + If we don't hit a single case label only, the default case also has + to branch to the same label. */ + val = TREE_VEC_ELT (vec, i); + if (CASE_LABEL (TREE_VEC_ELT (vec, n - 1)) != CASE_LABEL (val)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " not a single destination for this " + "range\n"); + return SSA_PROP_VARYING; + } + for (++i; i <= j; ++i) + { + if (CASE_LABEL (TREE_VEC_ELT (vec, i)) != CASE_LABEL (val)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " not a single destination for this " + "range\n"); + return SSA_PROP_VARYING; + } + } + } + + *taken_edge_p = find_edge (bb_for_stmt (stmt), + label_to_block (CASE_LABEL (val))); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " will take edge to "); + print_generic_stmt (dump_file, CASE_LABEL (val), 0); + } + + return SSA_PROP_INTERESTING; + } + + /* Evaluate statement STMT. If the statement produces a useful range, return SSA_PROP_INTERESTING and record the SSA name with the interesting range into *OUTPUT_P. *************** vrp_visit_stmt (tree stmt, edge *taken_e *** 5436,5443 **** || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) return vrp_visit_assignment (stmt, output_p); } ! else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) return vrp_visit_cond_stmt (stmt, taken_edge_p); /* All other statements produce nothing of interest for VRP, so mark their outputs varying and prevent further simulation. */ --- 5572,5581 ---- || ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) return vrp_visit_assignment (stmt, output_p); } ! else if (TREE_CODE (stmt) == COND_EXPR) return vrp_visit_cond_stmt (stmt, taken_edge_p); + else if (TREE_CODE (stmt) == SWITCH_EXPR) + return vrp_visit_switch_stmt (stmt, taken_edge_p); /* All other statements produce nothing of interest for VRP, so mark their outputs varying and prevent further simulation. */ Index: gcc/testsuite/gcc.dg/tree-ssa/vrp38.c =================================================================== *** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/testsuite/gcc.dg/tree-ssa/vrp38.c 2008-03-20 14:56:22.000000000 +0100 *************** *** 0 **** --- 1,18 ---- + /* { dg-do compile } */ + /* { dg-options "-O2 -fdump-tree-vrp1" } */ + + int f(int a) { + switch (a & 1) { + case 0: + case 1: return 3; + case 2: return 5; + case 3: return 7; + case 4: return 11; + case 5: return 13; + case 6: return 17; + case 7: return 19; + } + } + + /* { dg-final { scan-tree-dump "return 3;" "vrp1" } } */ + /* { dg-final { cleanup-tree-dump "vrp1" } } */