From d9b950dd440fe2029a111cda56add2c9e91123b9 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Mon, 6 Jun 2016 17:11:30 +0000 Subject: Selftest framework gcc/ChangeLog: * Makefile.in (OBJS): Add function-tests.o, hash-map-tests.o, hash-set-tests.o, rtl-tests.o, selftest-run-tests.o. (OBJS-libcommon): Add selftest.o. (OBJS-libcommon-target): Add selftest.o. (all.internal): Add "selftest". (all.cross): Likewise. (selftest): New phony target. (s-selftest): New target. (selftest-gdb): New phony target. (COLLECT2_OBJS): Add selftest.o. * bitmap.c: Include "selftest.h". (selftest::test_gc_alloc): New function. (selftest::test_set_range): New function. (selftest::test_clear_bit_in_middle): New function. (selftest::test_copying): New function. (selftest::test_bitmap_single_bit_set_p): New function. (selftest::bitmap_c_tests): New function. * common.opt (fself-test): New. * diagnostic-show-locus.c: Include "selftest.h". (make_range): New function. (test_range_contains_point_for_single_point): New function. (test_range_contains_point_for_single_line): New function. (test_range_contains_point_for_multiple_lines): New function. (assert_eq): New function. (test_get_line_width_without_trailing_whitespace): New function. (selftest::diagnostic_show_locus_c_tests): New function. * et-forest.c: Include "selftest.h". (selftest::test_single_node): New function. (selftest::test_simple_tree): New function. (selftest::test_disconnected_nodes): New function. (selftest::et_forest_c_tests): New function. * fold-const.c: Include "selftest.h". (selftest::assert_binop_folds_to_const): New function. (selftest::assert_binop_folds_to_nonlvalue): New function. (selftest::test_arithmetic_folding): New function. (selftest::fold_const_c_tests): New function. * function-tests.c: New file. * gimple.c: Include "selftest.h". Include "gimple-pretty-print.h". (selftest::verify_gimple_pp): New function. (selftest::test_assign_single): New function. (selftest::test_assign_binop): New function. (selftest::test_nop_stmt): New function. (selftest::test_return_stmt): New function. (selftest::test_return_without_value): New function. (selftest::gimple_c_tests): New function. * hash-map-tests.c: New file. * hash-set-tests.c: New file. * input.c: Include "selftest.h". (selftest::assert_loceq): New function. (selftest::test_accessing_ordinary_linemaps): New function. (selftest::test_unknown_location): New function. (selftest::test_builtins): New function. (selftest::test_reading_source_line): New function. (selftest::input_c_tests): New function. * rtl-tests.c: New file. * selftest-run-tests.c: New file. * selftest.c: New file. * selftest.h: New file. * spellcheck.c: Include "selftest.h". (selftest::levenshtein_distance_unit_test_oneway): New function, adapted from testsuite/gcc.dg/plugin/levenshtein_plugin.c. (selftest::levenshtein_distance_unit_test): Likewise. (selftest::spellcheck_c_tests): Likewise. * toplev.c: Include selftest.h. (toplev::run_self_tests): New. (toplev::main): Handle -fself-test. * toplev.h (toplev::run_self_tests): New. * tree.c: Include "selftest.h". (selftest::test_integer_constants): New function. (selftest::test_identifiers): New function. (selftest::test_labels): New function. (selftest::tree_c_tests): New function. * tree-cfg.c: Include "selftest.h". (selftest::push_fndecl): New function. (selftest::test_linear_chain): New function. (selftest::test_diamond): New function. (selftest::test_fully_connected): New function. (selftest::tree_cfg_c_tests): New function. * vec.c: Include "selftest.h". (selftest::safe_push_range): New function. (selftest::test_quick_push): New function. (selftest::test_safe_push): New function. (selftest::test_truncate): New function. (selftest::test_safe_grow_cleared): New function. (selftest::test_pop): New function. (selftest::test_safe_insert): New function. (selftest::test_ordered_remove): New function. (selftest::test_unordered_remove): New function. (selftest::test_block_remove): New function. (selftest::reverse_cmp): New function. (selftest::test_qsort): New function. (selftest::vec_c_tests): New function.c. * wide-int.cc: Include selftest.h and wide-int-print.h. (selftest::from_int ): New function. (selftest::from_int ): New function. (selftest::from_int ): New function. (selftest::assert_deceq): New function. (selftest::assert_hexeq): New function. (selftest::test_printing ): New function template. (selftest::test_ops ): New function template. (selftest::test_comparisons ): New function template. (selftest::run_all_wide_int_tests ): New function template. (selftest::wide_int_cc_tests): New function. gcc/testsuite/ChangeLog: * gcc.dg/plugin/levenshtein-test-1.c: Delete. * gcc.dg/plugin/levenshtein_plugin.c: Delete. * gcc.dg/plugin/plugin.exp (plugin_test_list): Remove the above. From-SVN: r237144 --- gcc/tree-cfg.c | 278 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 278 insertions(+) (limited to 'gcc/tree-cfg.c') diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index 7fc24ba..40e524b 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -58,6 +58,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-cfgcleanup.h" #include "gimplify.h" #include "attribs.h" +#include "selftest.h" /* This file contains functions for building the Control Flow Graph (CFG) for a function tree. */ @@ -9195,3 +9196,280 @@ gt_pch_nx (edge_def *e, gt_pointer_operator op, void *cookie) op (&(e->insns.r), cookie); op (&(block), cookie); } + +#if CHECKING_P + +namespace selftest { + +/* Helper function for CFG selftests: create a dummy function decl + and push it as cfun. */ + +static tree +push_fndecl (const char *name) +{ + tree fn_type = build_function_type_array (integer_type_node, 0, NULL); + /* FIXME: this uses input_location: */ + tree fndecl = build_fn_decl (name, fn_type); + tree retval = build_decl (UNKNOWN_LOCATION, RESULT_DECL, + NULL_TREE, integer_type_node); + DECL_RESULT (fndecl) = retval; + push_struct_function (fndecl); + function *fun = DECL_STRUCT_FUNCTION (fndecl); + ASSERT_TRUE (fun != NULL); + init_empty_tree_cfg_for_function (fun); + ASSERT_EQ (2, n_basic_blocks_for_fn (fun)); + ASSERT_EQ (0, n_edges_for_fn (fun)); + return fndecl; +} + +/* These tests directly create CFGs. + Compare with the static fns within tree-cfg.c: + - build_gimple_cfg + - make_blocks: calls create_basic_block (seq, bb); + - make_edges. */ + +/* Verify a simple cfg of the form: + ENTRY -> A -> B -> C -> EXIT. */ + +static void +test_linear_chain () +{ + gimple_register_cfg_hooks (); + + tree fndecl = push_fndecl ("cfg_test_linear_chain"); + function *fun = DECL_STRUCT_FUNCTION (fndecl); + + /* Create some empty blocks. */ + basic_block bb_a = create_empty_bb (ENTRY_BLOCK_PTR_FOR_FN (fun)); + basic_block bb_b = create_empty_bb (bb_a); + basic_block bb_c = create_empty_bb (bb_b); + + ASSERT_EQ (5, n_basic_blocks_for_fn (fun)); + ASSERT_EQ (0, n_edges_for_fn (fun)); + + /* Create some edges: a simple linear chain of BBs. */ + make_edge (ENTRY_BLOCK_PTR_FOR_FN (fun), bb_a, EDGE_FALLTHRU); + make_edge (bb_a, bb_b, 0); + make_edge (bb_b, bb_c, 0); + make_edge (bb_c, EXIT_BLOCK_PTR_FOR_FN (fun), 0); + + /* Verify the edges. */ + ASSERT_EQ (4, n_edges_for_fn (fun)); + ASSERT_EQ (NULL, ENTRY_BLOCK_PTR_FOR_FN (fun)->preds); + ASSERT_EQ (1, ENTRY_BLOCK_PTR_FOR_FN (fun)->succs->length ()); + ASSERT_EQ (1, bb_a->preds->length ()); + ASSERT_EQ (1, bb_a->succs->length ()); + ASSERT_EQ (1, bb_b->preds->length ()); + ASSERT_EQ (1, bb_b->succs->length ()); + ASSERT_EQ (1, bb_c->preds->length ()); + ASSERT_EQ (1, bb_c->succs->length ()); + ASSERT_EQ (1, EXIT_BLOCK_PTR_FOR_FN (fun)->preds->length ()); + ASSERT_EQ (NULL, EXIT_BLOCK_PTR_FOR_FN (fun)->succs); + + /* Verify the dominance information + Each BB in our simple chain should be dominated by the one before + it. */ + calculate_dominance_info (CDI_DOMINATORS); + ASSERT_EQ (bb_a, get_immediate_dominator (CDI_DOMINATORS, bb_b)); + ASSERT_EQ (bb_b, get_immediate_dominator (CDI_DOMINATORS, bb_c)); + vec dom_by_b = get_dominated_by (CDI_DOMINATORS, bb_b); + ASSERT_EQ (1, dom_by_b.length ()); + ASSERT_EQ (bb_c, dom_by_b[0]); + free_dominance_info (CDI_DOMINATORS); + + /* Similarly for post-dominance: each BB in our chain is post-dominated + by the one after it. */ + calculate_dominance_info (CDI_POST_DOMINATORS); + ASSERT_EQ (bb_b, get_immediate_dominator (CDI_POST_DOMINATORS, bb_a)); + ASSERT_EQ (bb_c, get_immediate_dominator (CDI_POST_DOMINATORS, bb_b)); + vec postdom_by_b = get_dominated_by (CDI_POST_DOMINATORS, bb_b); + ASSERT_EQ (1, postdom_by_b.length ()); + ASSERT_EQ (bb_a, postdom_by_b[0]); + free_dominance_info (CDI_POST_DOMINATORS); + + pop_cfun (); +} + +/* Verify a simple CFG of the form: + ENTRY + | + A + / \ + /t \f + B C + \ / + \ / + D + | + EXIT. */ + +static void +test_diamond () +{ + gimple_register_cfg_hooks (); + + tree fndecl = push_fndecl ("cfg_test_diamond"); + function *fun = DECL_STRUCT_FUNCTION (fndecl); + + /* Create some empty blocks. */ + basic_block bb_a = create_empty_bb (ENTRY_BLOCK_PTR_FOR_FN (fun)); + basic_block bb_b = create_empty_bb (bb_a); + basic_block bb_c = create_empty_bb (bb_a); + basic_block bb_d = create_empty_bb (bb_b); + + ASSERT_EQ (6, n_basic_blocks_for_fn (fun)); + ASSERT_EQ (0, n_edges_for_fn (fun)); + + /* Create the edges. */ + make_edge (ENTRY_BLOCK_PTR_FOR_FN (fun), bb_a, EDGE_FALLTHRU); + make_edge (bb_a, bb_b, EDGE_TRUE_VALUE); + make_edge (bb_a, bb_c, EDGE_FALSE_VALUE); + make_edge (bb_b, bb_d, 0); + make_edge (bb_c, bb_d, 0); + make_edge (bb_d, EXIT_BLOCK_PTR_FOR_FN (fun), 0); + + /* Verify the edges. */ + ASSERT_EQ (6, n_edges_for_fn (fun)); + ASSERT_EQ (1, bb_a->preds->length ()); + ASSERT_EQ (2, bb_a->succs->length ()); + ASSERT_EQ (1, bb_b->preds->length ()); + ASSERT_EQ (1, bb_b->succs->length ()); + ASSERT_EQ (1, bb_c->preds->length ()); + ASSERT_EQ (1, bb_c->succs->length ()); + ASSERT_EQ (2, bb_d->preds->length ()); + ASSERT_EQ (1, bb_d->succs->length ()); + + /* Verify the dominance information. */ + calculate_dominance_info (CDI_DOMINATORS); + ASSERT_EQ (bb_a, get_immediate_dominator (CDI_DOMINATORS, bb_b)); + ASSERT_EQ (bb_a, get_immediate_dominator (CDI_DOMINATORS, bb_c)); + ASSERT_EQ (bb_a, get_immediate_dominator (CDI_DOMINATORS, bb_d)); + vec dom_by_a = get_dominated_by (CDI_DOMINATORS, bb_a); + ASSERT_EQ (3, dom_by_a.length ()); /* B, C, D, in some order. */ + vec dom_by_b = get_dominated_by (CDI_DOMINATORS, bb_b); + ASSERT_EQ (0, dom_by_b.length ()); + free_dominance_info (CDI_DOMINATORS); + + /* Similarly for post-dominance. */ + calculate_dominance_info (CDI_POST_DOMINATORS); + ASSERT_EQ (bb_d, get_immediate_dominator (CDI_POST_DOMINATORS, bb_a)); + ASSERT_EQ (bb_d, get_immediate_dominator (CDI_POST_DOMINATORS, bb_b)); + ASSERT_EQ (bb_d, get_immediate_dominator (CDI_POST_DOMINATORS, bb_c)); + vec postdom_by_d = get_dominated_by (CDI_POST_DOMINATORS, bb_d); + ASSERT_EQ (3, postdom_by_d.length ()); /* A, B, C in some order. */ + vec postdom_by_b = get_dominated_by (CDI_POST_DOMINATORS, bb_b); + ASSERT_EQ (0, postdom_by_b.length ()); + free_dominance_info (CDI_POST_DOMINATORS); + + pop_cfun (); +} + +/* Verify that we can handle a CFG containing a "complete" aka + fully-connected subgraph (where A B C D below all have edges + pointing to each other node, also to themselves). + e.g.: + ENTRY EXIT + | ^ + | / + | / + | / + V/ + A<--->B + ^^ ^^ + | \ / | + | X | + | / \ | + VV VV + C<--->D +*/ + +static void +test_fully_connected () +{ + gimple_register_cfg_hooks (); + + tree fndecl = push_fndecl ("cfg_fully_connected"); + function *fun = DECL_STRUCT_FUNCTION (fndecl); + + const int n = 4; + + /* Create some empty blocks. */ + auto_vec subgraph_nodes; + for (int i = 0; i < n; i++) + subgraph_nodes.safe_push (create_empty_bb (ENTRY_BLOCK_PTR_FOR_FN (fun))); + + ASSERT_EQ (n + 2, n_basic_blocks_for_fn (fun)); + ASSERT_EQ (0, n_edges_for_fn (fun)); + + /* Create the edges. */ + make_edge (ENTRY_BLOCK_PTR_FOR_FN (fun), subgraph_nodes[0], EDGE_FALLTHRU); + make_edge (subgraph_nodes[0], EXIT_BLOCK_PTR_FOR_FN (fun), 0); + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + make_edge (subgraph_nodes[i], subgraph_nodes[j], 0); + + /* Verify the edges. */ + ASSERT_EQ (2 + (n * n), n_edges_for_fn (fun)); + /* The first one is linked to ENTRY/EXIT as well as itself and + everything else. */ + ASSERT_EQ (n + 1, subgraph_nodes[0]->preds->length ()); + ASSERT_EQ (n + 1, subgraph_nodes[0]->succs->length ()); + /* The other ones in the subgraph are linked to everything in + the subgraph (including themselves). */ + for (int i = 1; i < n; i++) + { + ASSERT_EQ (n, subgraph_nodes[i]->preds->length ()); + ASSERT_EQ (n, subgraph_nodes[i]->succs->length ()); + } + + /* Verify the dominance information. */ + calculate_dominance_info (CDI_DOMINATORS); + /* The initial block in the subgraph should be dominated by ENTRY. */ + ASSERT_EQ (ENTRY_BLOCK_PTR_FOR_FN (fun), + get_immediate_dominator (CDI_DOMINATORS, + subgraph_nodes[0])); + /* Every other block in the subgraph should be dominated by the + initial block. */ + for (int i = 1; i < n; i++) + ASSERT_EQ (subgraph_nodes[0], + get_immediate_dominator (CDI_DOMINATORS, + subgraph_nodes[i])); + free_dominance_info (CDI_DOMINATORS); + + /* Similarly for post-dominance. */ + calculate_dominance_info (CDI_POST_DOMINATORS); + /* The initial block in the subgraph should be postdominated by EXIT. */ + ASSERT_EQ (EXIT_BLOCK_PTR_FOR_FN (fun), + get_immediate_dominator (CDI_POST_DOMINATORS, + subgraph_nodes[0])); + /* Every other block in the subgraph should be postdominated by the + initial block, since that leads to EXIT. */ + for (int i = 1; i < n; i++) + ASSERT_EQ (subgraph_nodes[0], + get_immediate_dominator (CDI_POST_DOMINATORS, + subgraph_nodes[i])); + free_dominance_info (CDI_POST_DOMINATORS); + + pop_cfun (); +} + +/* Run all of the selftests within this file. */ + +void +tree_cfg_c_tests () +{ + test_linear_chain (); + test_diamond (); + test_fully_connected (); +} + +} // namespace selftest + +/* TODO: test the dominator/postdominator logic with various graphs/nodes: + - loop + - nested loops + - switch statement (a block with many out-edges) + - something that jumps to itself + - etc */ + +#endif /* CHECKING_P */ -- cgit v1.1