analyzer: rewrite of switch handling

analyzer: rewrite of switch handling

When investigating false positives on the Linux kernel from
-Wanalyzer-use-of-uninitialized-value, I noticed that the existing
implementation of switch statements in the analyzer is broken.

Specifically, the existing implementation assumes a 1:1 association
between CFG out-edges from the basic block and case labels in the
gimple switch statement.  This happened to be the case in the
examples I had tested, but there is no such association in general.
In particular, in the motivating example:
  arch/x86/kernel/cpu/mtrr/if.c: mtrr_ioctl
the switch statement has 3 blocks, each covering multiple ranges of
ioctl command IDs for which different local variables are initialized,
which the existing implementation gets badly wrong. [1]

This patch reimplements switch handling in the analyzer to eliminate
this false assumption - instead, for each out-edge we gather the set
of case labels for that out-edge, and use that to determine the
set of value ranges for the edge.  Avoiding false positives for the
above example requires that we accurately track value ranges for
symbolic values, so the patch extends constraint_manager with a new
bounded_ranges_constraint, adding just enough information to capture the
ranges for switch statements whilst retaining combatility with the
existing constraint-handling (ultimately I'd prefer to simply throw
all of this into a SAT solver and let it track things).

Doing so fixes the false positives seen on the Linux kernel and an
existing xfail in the test suite.

The patch also fixes a long-standing bug in
constraint_manager::add_unknown_constraint when updating constraints
due to combining equivalence classes, spotted when debugging the
same logic for the new kind of constraints.

[1] a reduced version of this code is captured in this patch, in
gcc.dg/analyzer/torture/switch-3.c

gcc/analyzer/ChangeLog:
	* analyzer.h (struct rejected_constraint): Convert to...
	(class rejected_constraint): ...this.
	(class bounded_ranges): New forward decl.
	(class bounded_ranges_manager): New forward decl.
	* constraint-manager.cc: Include "analyzer/analyzer-logging.h" and
	"tree-pretty-print.h".
	(can_plus_one_p): New.
	(plus_one): New.
	(can_minus_one_p): New.
	(minus_one): New.
	(bounded_range::bounded_range): New.
	(dump_cst): New.
	(bounded_range::dump_to_pp): New.
	(bounded_range::dump): New.
	(bounded_range::to_json): New.
	(bounded_range::set_json_attr): New.
	(bounded_range::contains_p): New.
	(bounded_range::intersects_p): New.
	(bounded_range::operator==): New.
	(bounded_range::cmp): New.
	(bounded_ranges::bounded_ranges): New.
	(bounded_ranges::bounded_ranges): New.
	(bounded_ranges::bounded_ranges): New.
	(bounded_ranges::canonicalize): New.
	(bounded_ranges::validate): New.
	(bounded_ranges::operator==): New.
	(bounded_ranges::dump_to_pp): New.
	(bounded_ranges::dump): New.
	(bounded_ranges::to_json): New.
	(bounded_ranges::eval_condition): New.
	(bounded_ranges::contain_p): New.
	(bounded_ranges::cmp): New.
	(bounded_ranges_manager::~bounded_ranges_manager): New.
	(bounded_ranges_manager::get_or_create_empty): New.
	(bounded_ranges_manager::get_or_create_point): New.
	(bounded_ranges_manager::get_or_create_range): New.
	(bounded_ranges_manager::get_or_create_union): New.
	(bounded_ranges_manager::get_or_create_intersection): New.
	(bounded_ranges_manager::get_or_create_inverse): New.
	(bounded_ranges_manager::consolidate): New.
	(bounded_ranges_manager::get_or_create_ranges_for_switch): New.
	(bounded_ranges_manager::create_ranges_for_switch): New.
	(bounded_ranges_manager::make_case_label_ranges): New.
	(bounded_ranges_manager::log_stats): New.
	(bounded_ranges_constraint::print): New.
	(bounded_ranges_constraint::to_json): New.
	(bounded_ranges_constraint::operator==): New.
	(bounded_ranges_constraint::add_to_hash): New.
	(constraint_manager::constraint_manager): Update for new field
	m_bounded_ranges_constraints.
	(constraint_manager::operator=): Likewise.
	(constraint_manager::hash): Likewise.
	(constraint_manager::operator==): Likewise.
	(constraint_manager::print): Likewise.
	(constraint_manager::dump_to_pp): Likewise.
	(constraint_manager::to_json): Likewise.
	(constraint_manager::add_unknown_constraint): Update the lhs_ec_id
	if necessary in existing constraints when combining equivalence
	classes.  Add similar code for handling
	m_bounded_ranges_constraints.
	(constraint_manager::add_constraint_internal): Add comment.
	(constraint_manager::add_bounded_ranges): New.
	(constraint_manager::eval_condition): Use new field
	m_bounded_ranges_constraints.
	(constraint_manager::purge): Update bounded_ranges_constraint
	instances.
	(constraint_manager::canonicalize): Update for new field.
	(merger_fact_visitor::on_ranges): New.
	(constraint_manager::for_each_fact): Use new field
	m_bounded_ranges_constraints.
	(constraint_manager::validate):  Fix off-by-one error needed due
	to bug fixed above in add_unknown_constraint.  Validate the EC IDs
	in m_bounded_ranges_constraints.
	(constraint_manager::get_range_manager): New.
	(selftest::assert_dump_bounded_range_eq): New.
	(ASSERT_DUMP_BOUNDED_RANGE_EQ): New.
	(selftest::test_bounded_range): New.
	(selftest::assert_dump_bounded_ranges_eq): New.
	(ASSERT_DUMP_BOUNDED_RANGES_EQ): New.
	(selftest::test_bounded_ranges): New.
	(selftest::run_constraint_manager_tests): Call the new selftests.
	* constraint-manager.h (struct bounded_range): New.
	(struct bounded_ranges): New.
	(template <> struct default_hash_traits<bounded_ranges::key_t>): New.
	(class bounded_ranges_manager): New.
	(fact_visitor::on_ranges): New pure virtual function.
	(class bounded_ranges_constraint): New.
	(constraint_manager::add_bounded_ranges): New decl.
	(constraint_manager::get_range_manager): New decl.
	(constraint_manager::m_bounded_ranges_constraints): New field.
	* diagnostic-manager.cc (epath_finder::process_worklist_item):
	Transfer ownership of rc to add_feasibility_problem.
	* engine.cc (feasibility_problem::dump_to_pp): Use get_model.
	* feasible-graph.cc (infeasible_node::dump_dot): Update for
	conversion of m_rc to a pointer.
	(feasible_graph::add_feasibility_problem): Pass RC by pointer and
	take ownership.
	* feasible-graph.h (infeasible_node::infeasible_node): Pass RC by
	pointer and take ownership.
	(infeasible_node::~infeasible_node): New.
	(infeasible_node::m_rc): Convert to a pointer.
	(feasible_graph::add_feasibility_problem): Pass RC by pointer and
	take ownership.
	* region-model-manager.cc: Include
	"analyzer/constraint-manager.h".
	(region_model_manager::region_model_manager): Initializer new
	field m_range_mgr.
	(region_model_manager::~region_model_manager): Delete it.
	(region_model_manager::log_stats): Call log_stats on it.
	* region-model.cc (region_model::add_constraint): Use new subclass
	rejected_op_constraint.
	(region_model::apply_constraints_for_gswitch): Reimplement using
	bounded_ranges_manager.
	(rejected_constraint::dump_to_pp): Convert to...
	(rejected_op_constraint::dump_to_pp): ...this.
	(rejected_ranges_constraint::dump_to_pp): New.
	* region-model.h (struct purge_stats): Add field
	m_num_bounded_ranges_constraints.
	(region_model_manager::get_range_manager): New.
	(region_model_manager::m_range_mgr): New.
	(region_model::get_range_manager): New.
	(struct rejected_constraint): Split into...
	(class rejected_constraint):...this new abstract base class,
	and...
	(class rejected_op_constraint): ...this new concrete subclass.
	(class rejected_ranges_constraint): New.
	* supergraph.cc: Include "tree-cfg.h".
	(supergraph::supergraph): Drop idx param from add_cfg_edge.
	(supergraph::add_cfg_edge): Drop idx param.
	(switch_cfg_superedge::switch_cfg_superedge): Move here from
	header.  Populate m_case_labels with all cases which go to DST.
	(switch_cfg_superedge::dump_label_to_pp): Reimplement to use
	m_case_labels.
	(switch_cfg_superedge::get_case_label): Delete.
	* supergraph.h (supergraphadd_cfg_edge): Drop "idx" param.
	(switch_cfg_superedge::switch_cfg_superedge): Drop idx param and
	move implementation to supergraph.cc.
	(switch_cfg_superedge::get_case_label): Delete.
	(switch_cfg_superedge::get_case_labels): New.
	(switch_cfg_superedge::m_idx): Delete.
	(switch_cfg_superedge::m_case_labels): New field.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/switch.c: Remove xfail.  Add various tests.
	* gcc.dg/analyzer/torture/switch-2.c: New test.
	* gcc.dg/analyzer/torture/switch-3.c: New test.
	* gcc.dg/analyzer/torture/switch-4.c: New test.
	* gcc.dg/analyzer/torture/switch-5.c: New test.