[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  <kirtchev@adacore.com>

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

1 files changed, 8 insertions, 4 deletions

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.