Lines Matching refs:graph
479 static constraint_graph_t graph; variable
497 gcc_assert (node < graph->size); in find()
498 if (graph->rep[node] != node) in find()
499 return graph->rep[node] = find (graph->rep[node]); in find()
511 gcc_assert (to < graph->size && from < graph->size); in unite()
512 if (to != from && graph->rep[from] != to) in unite()
514 graph->rep[from] = to; in unite()
781 insert_into_complex (constraint_graph_t graph, in insert_into_complex() argument
784 VEC (constraint_t, heap) *complex = graph->complex[var]; in insert_into_complex()
791 VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c); in insert_into_complex()
799 merge_node_constraints (constraint_graph_t graph, unsigned int to, in merge_node_constraints() argument
808 for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++) in merge_node_constraints()
821 constraint_set_union (&graph->complex[to], &graph->complex[from]); in merge_node_constraints()
822 VEC_free (constraint_t, heap, graph->complex[from]); in merge_node_constraints()
823 graph->complex[from] = NULL; in merge_node_constraints()
830 clear_edges_for_node (constraint_graph_t graph, unsigned int node) in clear_edges_for_node() argument
832 if (graph->succs[node]) in clear_edges_for_node()
833 BITMAP_FREE (graph->succs[node]); in clear_edges_for_node()
839 merge_graph_nodes (constraint_graph_t graph, unsigned int to, in merge_graph_nodes() argument
842 if (graph->indirect_cycles[from] != -1) in merge_graph_nodes()
850 if (graph->indirect_cycles[to] == -1) in merge_graph_nodes()
852 graph->indirect_cycles[to] = graph->indirect_cycles[from]; in merge_graph_nodes()
856 unsigned int tonode = find (graph->indirect_cycles[to]); in merge_graph_nodes()
857 unsigned int fromnode = find (graph->indirect_cycles[from]); in merge_graph_nodes()
860 unify_nodes (graph, tonode, fromnode, true); in merge_graph_nodes()
865 if (graph->succs[from]) in merge_graph_nodes()
867 if (!graph->succs[to]) in merge_graph_nodes()
868 graph->succs[to] = BITMAP_ALLOC (&pta_obstack); in merge_graph_nodes()
869 bitmap_ior_into (graph->succs[to], in merge_graph_nodes()
870 graph->succs[from]); in merge_graph_nodes()
873 clear_edges_for_node (graph, from); in merge_graph_nodes()
881 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to, in add_implicit_graph_edge() argument
887 if (!graph->implicit_preds[to]) in add_implicit_graph_edge()
888 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); in add_implicit_graph_edge()
890 if (!bitmap_bit_p (graph->implicit_preds[to], from)) in add_implicit_graph_edge()
893 bitmap_set_bit (graph->implicit_preds[to], from); in add_implicit_graph_edge()
902 add_pred_graph_edge (constraint_graph_t graph, unsigned int to, in add_pred_graph_edge() argument
905 if (!graph->preds[to]) in add_pred_graph_edge()
906 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack); in add_pred_graph_edge()
907 if (!bitmap_bit_p (graph->preds[to], from)) in add_pred_graph_edge()
908 bitmap_set_bit (graph->preds[to], from); in add_pred_graph_edge()
916 add_graph_edge (constraint_graph_t graph, unsigned int to, in add_graph_edge() argument
927 if (!graph->succs[from]) in add_graph_edge()
928 graph->succs[from] = BITMAP_ALLOC (&pta_obstack); in add_graph_edge()
929 if (!bitmap_bit_p (graph->succs[from], to)) in add_graph_edge()
934 bitmap_set_bit (graph->succs[from], to); in add_graph_edge()
944 valid_graph_edge (constraint_graph_t graph, unsigned int src, in valid_graph_edge() argument
947 return (graph->succs[dest] in valid_graph_edge()
948 && bitmap_bit_p (graph->succs[dest], src)); in valid_graph_edge()
960 graph = XNEW (struct constraint_graph); in build_pred_graph()
961 graph->size = (VEC_length (varinfo_t, varmap)) * 3; in build_pred_graph()
962 graph->succs = XCNEWVEC (bitmap, graph->size); in build_pred_graph()
963 graph->implicit_preds = XCNEWVEC (bitmap, graph->size); in build_pred_graph()
964 graph->preds = XCNEWVEC (bitmap, graph->size); in build_pred_graph()
965 graph->indirect_cycles = XNEWVEC (int, VEC_length (varinfo_t, varmap)); in build_pred_graph()
966 graph->label = XCNEWVEC (unsigned int, graph->size); in build_pred_graph()
967 graph->rep = XNEWVEC (unsigned int, graph->size); in build_pred_graph()
968 graph->eq_rep = XNEWVEC (int, graph->size); in build_pred_graph()
969 graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, in build_pred_graph()
971 graph->direct_nodes = sbitmap_alloc (graph->size); in build_pred_graph()
972 sbitmap_zero (graph->direct_nodes); in build_pred_graph()
977 SET_BIT (graph->direct_nodes, j); in build_pred_graph()
980 for (j = 0; j < graph->size; j++) in build_pred_graph()
982 graph->rep[j] = j; in build_pred_graph()
983 graph->eq_rep[j] = -1; in build_pred_graph()
987 graph->indirect_cycles[j] = -1; in build_pred_graph()
1000 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); in build_pred_graph()
1002 RESET_BIT (graph->direct_nodes, rhsvar); in build_pred_graph()
1008 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); in build_pred_graph()
1010 RESET_BIT (graph->direct_nodes, lhsvar); in build_pred_graph()
1015 add_pred_graph_edge (graph, lhsvar, FIRST_ADDR_NODE + rhsvar); in build_pred_graph()
1017 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); in build_pred_graph()
1019 RESET_BIT (graph->direct_nodes, rhsvar); in build_pred_graph()
1025 add_pred_graph_edge (graph, lhsvar, rhsvar); in build_pred_graph()
1027 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, in build_pred_graph()
1033 RESET_BIT (graph->direct_nodes, lhs.var); in build_pred_graph()
1035 RESET_BIT (graph->direct_nodes, rhs.var); in build_pred_graph()
1066 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); in build_succ_graph()
1071 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); in build_succ_graph()
1083 add_graph_edge (graph, lhsvar, rhsvar); in build_succ_graph()
1122 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) in scc_visit() argument
1133 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi) in scc_visit()
1145 scc_visit (graph, si, w); in scc_visit()
1187 unify_nodes (graph, lowest_node, i, false); in scc_visit()
1192 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node; in scc_visit()
1206 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, in unify_nodes() argument
1221 merge_graph_nodes (graph, to, from); in unify_nodes()
1222 merge_node_constraints (graph, to, from); in unify_nodes()
1257 if (valid_graph_edge (graph, to, to)) in unify_nodes()
1259 if (graph->succs[to]) in unify_nodes()
1260 bitmap_clear_bit (graph->succs[to], to); in unify_nodes()
1304 topo_visit (constraint_graph_t graph, struct topo_info *ti, in topo_visit() argument
1312 if (graph->succs[n]) in topo_visit()
1313 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) in topo_visit()
1316 topo_visit (graph, ti, j); in topo_visit()
1345 do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED, in do_da_constraint()
1389 do_sd_constraint (constraint_graph_t graph, constraint_t c, in do_sd_constraint() argument
1425 else if (add_graph_edge (graph, lhs, t)) in do_sd_constraint()
1524 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) in do_complex_constraint() argument
1531 do_da_constraint (graph, c, delta); in do_complex_constraint()
1543 do_sd_constraint (graph, c, delta); in do_complex_constraint()
1617 find_indirect_cycles (constraint_graph_t graph) in find_indirect_cycles() argument
1620 unsigned int size = graph->size; in find_indirect_cycles()
1625 scc_visit (graph, si, i); in find_indirect_cycles()
1634 compute_topo_order (constraint_graph_t graph, in compute_topo_order() argument
1642 topo_visit (graph, ti, i); in compute_topo_order()
1693 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) in label_visit() argument
1705 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) in label_visit()
1713 label_visit (graph, si, w); in label_visit()
1725 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) in label_visit()
1733 label_visit (graph, si, w); in label_visit()
1753 if (!TEST_BIT (graph->direct_nodes, w)) in label_visit()
1754 RESET_BIT (graph->direct_nodes, n); in label_visit()
1758 if (!TEST_BIT (graph->direct_nodes, n)) in label_visit()
1760 graph->label[n] = equivalence_class++; in label_visit()
1767 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) in label_visit()
1771 if (j == n || graph->label[j] == 0) in label_visit()
1776 firstlabel = graph->label[j]; in label_visit()
1779 else if (graph->label[j] != firstlabel) in label_visit()
1784 graph->label[n] = 0; in label_visit()
1786 graph->label[n] = firstlabel; in label_visit()
1788 graph->label[n] = equivalence_class++; in label_visit()
1799 perform_var_substitution (constraint_graph_t graph) in perform_var_substitution() argument
1802 unsigned int size = graph->size; in perform_var_substitution()
1813 label_visit (graph, si, si->node_mapping[i]); in perform_var_substitution()
1818 bool direct_node = TEST_BIT (graph->direct_nodes, i); in perform_var_substitution()
1823 graph->label[si->node_mapping[i]]); in perform_var_substitution()
1832 if (graph->label[node] == 0 && TEST_BIT (graph->direct_nodes, node)) in perform_var_substitution()
1839 clear_edges_for_node (graph, node); in perform_var_substitution()
1852 free (graph->label); in free_var_substitution_info()
1853 free (graph->eq_rep); in free_var_substitution_info()
1854 sbitmap_free (graph->direct_nodes); in free_var_substitution_info()
1862 find_equivalent_node (constraint_graph_t graph, in find_equivalent_node() argument
1870 if (graph->label[FIRST_ADDR_NODE + node] == 0) in find_equivalent_node()
1872 gcc_assert (label < graph->size); in find_equivalent_node()
1874 if (graph->eq_rep[label] != -1) in find_equivalent_node()
1877 if (unite (graph->eq_rep[label], node)) in find_equivalent_node()
1878 unify_nodes (graph, graph->eq_rep[label], node, false); in find_equivalent_node()
1879 return graph->eq_rep[label]; in find_equivalent_node()
1883 graph->eq_rep[label] = node; in find_equivalent_node()
1895 move_complex_constraints (constraint_graph_t graph, in move_complex_constraints() argument
1902 for (j = 0; j < graph->size; j++) in move_complex_constraints()
1916 lhslabel = graph->label[lhsnode]; in move_complex_constraints()
1917 rhslabel = graph->label[rhsnode]; in move_complex_constraints()
1923 if (!TEST_BIT (graph->direct_nodes, lhsnode)) in move_complex_constraints()
1924 lhslabel = graph->label[lhsnode] = equivalence_class++; in move_complex_constraints()
1942 if (!TEST_BIT (graph->direct_nodes, rhsnode)) in move_complex_constraints()
1943 rhslabel = graph->label[rhsnode] = equivalence_class++; in move_complex_constraints()
1959 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); in move_complex_constraints()
1960 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); in move_complex_constraints()
1967 insert_into_complex (graph, lhsvar, c); in move_complex_constraints()
1972 insert_into_complex (graph, rhsvar, c); in move_complex_constraints()
1977 insert_into_complex (graph, rhsvar, c); in move_complex_constraints()
1989 if (graph->indirect_cycles[node] != -1 in eliminate_indirect_cycles()
1995 unsigned int to = find (graph->indirect_cycles[node]); in eliminate_indirect_cycles()
2015 unify_nodes (graph, to, i, true); in eliminate_indirect_cycles()
2031 solve_graph (constraint_graph_t graph) in solve_graph() argument
2046 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) in solve_graph()
2047 || VEC_length (constraint_t, graph->complex[i]) > 0)) in solve_graph()
2065 compute_topo_order (graph, ti); in solve_graph()
2088 VEC(constraint_t,heap) *complex = graph->complex[i]; in solve_graph()
2114 do_complex_constraint (graph, c, pts); in solve_graph()
2124 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], in solve_graph()
4884 remove_preds_and_fake_succs (constraint_graph_t graph) in remove_preds_and_fake_succs() argument
4892 if (graph->succs[i]) in remove_preds_and_fake_succs()
4893 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE, in remove_preds_and_fake_succs()
4898 for (i = FIRST_REF_NODE; i < graph->size; i++) in remove_preds_and_fake_succs()
4900 if (graph->succs[i]) in remove_preds_and_fake_succs()
4901 BITMAP_FREE (graph->succs[i]); in remove_preds_and_fake_succs()
4906 graph->size = VEC_length (varinfo_t, varmap); in remove_preds_and_fake_succs()
4907 graph->succs = xrealloc (graph->succs, graph->size * sizeof (bitmap)); in remove_preds_and_fake_succs()
4909 free (graph->implicit_preds); in remove_preds_and_fake_succs()
4910 graph->implicit_preds = NULL; in remove_preds_and_fake_succs()
4911 free (graph->preds); in remove_preds_and_fake_succs()
4912 graph->preds = NULL; in remove_preds_and_fake_succs()
4978 si = perform_var_substitution (graph); in compute_points_to_sets()
4979 move_complex_constraints (graph, si); in compute_points_to_sets()
4983 find_indirect_cycles (graph); in compute_points_to_sets()
4987 remove_preds_and_fake_succs (graph); in compute_points_to_sets()
4992 solve_graph (graph); in compute_points_to_sets()
5019 VEC_free (constraint_t, heap, graph->complex[i]); in delete_points_to_sets()
5020 free (graph->complex); in delete_points_to_sets()
5022 free (graph->rep); in delete_points_to_sets()
5023 free (graph->succs); in delete_points_to_sets()
5024 free (graph->indirect_cycles); in delete_points_to_sets()
5025 free (graph); in delete_points_to_sets()
5124 find_and_collapse_graph_cycles (graph, false); in ipa_pta_execute()
5125 perform_var_substitution (graph); in ipa_pta_execute()
5130 solve_graph (graph); in ipa_pta_execute()