+/* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
+ that includes the value VAL. The search is restricted to the range
+ [START_IDX, n - 1] where n is the size of VEC.
+
+ If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
+ returned.
+
+ If there is no CASE_LABEL for VAL and the is one that is larger than VAL,
+ it is placed in IDX and false is returned.
+
+ If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
+ returned. */
+
+static bool
+find_case_label_index (gimple stmt, size_t start_idx, tree val, size_t *idx)
+{
+ size_t n = gimple_switch_num_labels (stmt);
+ size_t low, high;
+
+ /* Find case label for minimum of the value range or the next one.
+ At each iteration we are searching in [low, high - 1]. */
+
+ for (low = start_idx, high = n; high != low; )
+ {
+ tree t;
+ int cmp;
+ /* Note that i != high, so we never ask for n. */
+ size_t i = (high + low) / 2;
+ t = gimple_switch_label (stmt, i);
+
+ /* Cache the result of comparing CASE_LOW and val. */
+ cmp = tree_int_cst_compare (CASE_LOW (t), val);
+
+ if (cmp == 0)
+ {
+ /* Ranges cannot be empty. */
+ *idx = i;
+ return true;
+ }
+ else if (cmp > 0)
+ high = i;
+ else
+ {
+ low = i + 1;
+ if (CASE_HIGH (t) != NULL
+ && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
+ {
+ *idx = i;
+ return true;
+ }
+ }
+ }
+
+ *idx = high;
+ return false;
+}
+
+/* Searches the case label vector VEC for the range of CASE_LABELs that is used
+ for values between MIN and MAX. The first index is placed in MIN_IDX. The
+ last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
+ then MAX_IDX < MIN_IDX.
+ Returns true if the default label is not needed. */
+
+static bool
+find_case_label_range (gimple stmt, tree min, tree max, size_t *min_idx,
+ size_t *max_idx)
+{
+ size_t i, j;
+ bool min_take_default = !find_case_label_index (stmt, 1, min, &i);
+ bool max_take_default = !find_case_label_index (stmt, i, max, &j);
+
+ if (i == j
+ && min_take_default
+ && max_take_default)
+ {
+ /* Only the default case label reached.
+ Return an empty range. */
+ *min_idx = 1;
+ *max_idx = 0;
+ return false;
+ }
+ else
+ {
+ bool take_default = min_take_default || max_take_default;
+ tree low, high;
+ size_t k;
+
+ if (max_take_default)
+ j--;
+
+ /* If the case label range is continuous, we do not need
+ the default case label. Verify that. */
+ high = CASE_LOW (gimple_switch_label (stmt, i));
+ if (CASE_HIGH (gimple_switch_label (stmt, i)))
+ high = CASE_HIGH (gimple_switch_label (stmt, i));
+ for (k = i + 1; k <= j; ++k)
+ {
+ low = CASE_LOW (gimple_switch_label (stmt, k));
+ if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0)))
+ {
+ take_default = true;
+ break;
+ }
+ high = low;
+ if (CASE_HIGH (gimple_switch_label (stmt, k)))
+ high = CASE_HIGH (gimple_switch_label (stmt, k));
+ }
+
+ *min_idx = i;
+ *max_idx = j;
+ return !take_default;
+ }
+}
+
+/* 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 (gimple stmt, edge *taken_edge_p)
+{
+ tree op, val;
+ value_range_t *vr;
+ size_t i = 0, j = 0, n;
+ bool take_default;
+
+ *taken_edge_p = NULL;
+ op = gimple_switch_index (stmt);
+ 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. */
+ n = gimple_switch_num_labels (stmt);
+
+ take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
+
+ /* Check if the range spans no CASE_LABEL. If so, we only reach the default
+ label */
+ if (j < i)
+ {
+ gcc_assert (take_default);
+ val = gimple_switch_default_label (stmt);
+ }
+ else
+ {
+ /* Check if labels with index i to j and maybe the default label
+ are all reaching the same label. */
+
+ val = gimple_switch_label (stmt, i);
+ if (take_default
+ && CASE_LABEL (gimple_switch_default_label (stmt))
+ != 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 (gimple_switch_label (stmt, 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 (gimple_bb (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;
+}
+