From 9098d477ba81e9fba2c41611513bbd643f5caab1 Mon Sep 17 00:00:00 2001 From: Hristian Kirtchev Date: Wed, 10 Jul 2019 09:00:59 +0000 Subject: [Ada] Elaboration order v4.0 and cycle detection This patch introduces a new cycle detection algorithm which is based on Tarjan's "Enumeration of the Elementary Circuits of a Directed Graph" algorithm, with several ideas borrowed from Jonson's "Finding all the Elementary Circuits of a Directed Graph" algorithm. No need for a test because the new algorithm improves the performance of cycle detection only. 2019-07-10 Hristian Kirtchev gcc/ada/ * bindo.adb: Update the section on switches. * bindo-graphs.adb (Add_Cycle, Add_Vertex_And_Complement): Remove. (Create): The graph no longer needs a set of recorded cycles because the cycles are not rediscovered in permuted forms. (Cycle_End_Vertices): New routine. (Destroy): The graph no longer needs a set of recorded cycles because the cycles are not rediscovered in permuted forms. (Destroy_Library_Graph_Vertex): Move to the library level. (Find_All_Cycles_Through_Vertex, Find_All_Cycles_With_Edge): Remove. (Find_Cycles_From_Successor, Find_Cycles_From_Vertex, Find_Cycles_In_Component, Has_Elaborate_All_Edge): New routines. (Insert_And_Sort): Remove. (Is_Elaborate_Body_Edge): Use predicate Is_Vertex_With_Elaborate_Body. (Is_Recorded_Cycle): Remove. (Is_Vertex_With_Elaborate_Body): New routine. (Normalize_And_Add_Cycle): Remove. (Precedence): Rename to xxx_Precedence, where xxx relates to the input. These versions better reflect the desired input precedence. (Record_Cycle): New routine. (Remove_Vertex_And_Complement, Set_Is_Recorded_Cycle): Remove. (Trace_xxx): Update all versions to use debug switch -d_t. (Trace_Component): New routine. (Trace_Eol): Removed. (Trace_Vertex): Do not output the component as this information is already available when the component is traced. (Unvisit, Visit): New routine. * bindo-graphs.ads: Add new instance LGV_Lists. Remove instance RC_Sets. Update the structure of type Library_Graph_Attributes to remove the set of recorded cycles. (Destroy_Library_Graph_Vertex): Move to the library level. * bindo-writers.adb (Write_Component_Vertices): Output information about the number of vertices. * debug.adb: Document the use of binder switch -d_t. Update the use of binder switch -d_T. From-SVN: r273330 --- gcc/ada/debug.adb | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'gcc/ada/debug.adb') diff --git a/gcc/ada/debug.adb b/gcc/ada/debug.adb index a4ff176..89bb7f8 100644 --- a/gcc/ada/debug.adb +++ b/gcc/ada/debug.adb @@ -368,7 +368,7 @@ package body Debug is -- d_q -- d_r -- d_s - -- d_t + -- d_t Output cycle detection trace information -- d_u -- d_v -- d_w @@ -380,6 +380,7 @@ package body Debug is -- d_B -- d_C Diagnose all cycles -- d_D + -- d_E -- d_F -- d_G -- d_H @@ -394,7 +395,7 @@ package body Debug is -- d_Q -- d_R -- d_S - -- d_T Output elaboration order and cycle detection trace information + -- d_T Output elaboration order trace information -- d_U -- d_V Validate bindo cycles, graphs, and order -- d_W @@ -1149,6 +1150,9 @@ package body Debug is -- elaboration order and no longer creates an implicit dependency on -- the body of the argument. + -- d_t GNATBIND output trace information of cycle detection activities to + -- standard output. + -- d_A GNATBIND output the contents of all ALI invocation-related tables -- in textual format to standard output. @@ -1163,8 +1167,8 @@ package body Debug is -- d_P GNATBIND outputs the cycle paths to standard output - -- d_T GNATBIND outputs trace information of elaboration order and cycle - -- detection activities to standard output. + -- d_T GNATBIND outputs trace information of elaboration order detection + -- activities to standard output. -- d_V GNATBIND validates the invocation graph, library graph along with -- its cycles, and the elaboration order. -- cgit v1.1