diff options
| -rw-r--r-- | gcc/ada/ChangeLog | 130 | ||||
| -rw-r--r-- | gcc/ada/bindo-builders.adb | 36 | ||||
| -rw-r--r-- | gcc/ada/bindo-builders.ads | 6 | ||||
| -rw-r--r-- | gcc/ada/bindo-diagnostics.adb | 45 | ||||
| -rw-r--r-- | gcc/ada/bindo-elaborators.adb | 1907 | ||||
| -rw-r--r-- | gcc/ada/bindo-graphs.adb | 527 | ||||
| -rw-r--r-- | gcc/ada/bindo-graphs.ads | 156 | ||||
| -rw-r--r-- | gcc/ada/bindo-validators.adb | 12 | ||||
| -rw-r--r-- | gcc/ada/bindo-writers.adb | 23 | ||||
| -rw-r--r-- | gcc/ada/bindo-writers.ads | 3 | ||||
| -rw-r--r-- | gcc/ada/bindo.adb | 48 | ||||
| -rw-r--r-- | gcc/ada/bindo.ads | 10 | ||||
| -rw-r--r-- | gcc/ada/debug.adb | 17 |
13 files changed, 1845 insertions, 1075 deletions
diff --git a/gcc/ada/ChangeLog b/gcc/ada/ChangeLog index 3bbc1cf..e6eac08 100644 --- a/gcc/ada/ChangeLog +++ b/gcc/ada/ChangeLog @@ -1,3 +1,133 @@ +2019-07-08 Hristian Kirtchev <kirtchev@adacore.com> + + * bindo.adb: Update the section on terminology to include new + concepts. Update the section on switches to include new + entries. + * bindo.ads: Add type Precedence_Kind. + * bindo-builders.adb: Add with and use clauses for Debug and + Bindo.Validators. Add use clauses for + Bindo.Validators.Invocation_Graph_Validators and + Bindo.Validators.Library_Graph_Validators. + (Build_Invocation_Graph): Validate the graph immediately after + it was built. + (Build_Library_Graph): Update the parameter profile. The + creation of the graph is now elaboration model-agnostic. + Validate the graph immediately after it was built. + (Create_With_Edge): Create regular with edges for Elaborate and + Elaborate_All edges when the appropriate debug switches are in + effect. + * bindo-builders.ads (Build_Library_Graph): Update the parameter + profile. + * bindo-diagnostics.adb (Diagnose_Cycle): Track the presence of + an Elaborate_All edge throughout the inspection of the cycle's + edges. + (Output_Dynamic_Model_Suggestions): Output the suggestion only + when the cycle contains at least one weak edge where the + successor was statically elaborated. + (Output_Elaborate_Body_Transition, Output_Forced_Transition, + Output_With_Transition): Update the assertions. + * bindo-elaborators.adb: Remove use clauses for + Bindo.Validators.Invocation_Graph_Validators and + Bindo.Validators.Library_Graph_Validators. Remove strings + Add_To_All_Candidates_Msg and Add_To_Comp_Candidates_Msg. + Remove type String_Ptr. + (Add_Vertex, Add_Vertex_If_Elaborable, Create_All_Candidates_Set + Create_Component_Candidates_Set): Remove. + (Create_Component_Vertex_Sets, Create_Vertex_Sets): New routine. + (Elaborate_Component): Update the parameter profile and the + comment on usage. Reimplement the elaboration of a component. + The algorithm will now attempt to elaborate as many vertices + possible. If this is not possible, and a weakly elaborable + vertex is available use unit was compiled using the dynamic + model, the algorithm will elaborate it. + (Elaborate_Library_Graph): Reimplement the elaboration of the + graph. The algorithm will now attempt to elaborate as many + vertices along with their components as possible. If this is not + possible, and a weakly elaborable vertex is available use unit + was compiled using the dynamic model, the algorithm will + elaborate it along with its component. + (Elaborate_Units): Merge with the functionality of + Elaborate_Units_Common. + (Elaborate_Units_Common, Elaborate_Units_Dynamic, + Elaborate_Units_Static): Remove. + (Elaborate_Vertex): Update the parameter profile and the comment + on usage. Reimplemented. + (Find_Best_Candidate): Remove. + (Find_Best_Elaborable_Vertex, Find_Best_Vertex, + Find_Best_Weakly_Elaborable_Vertex, Has_Elaborable_Body, + Insert_Elaborable_Successor, Insert_Vertex): New routines. + (Is_Better_Candidate): Remove. + (Is_Better_Elaborable_Vertex, + Is_Better_Weakly_Elaborable_Vertex, + Is_Suitable_Elaborable_Vertex, + Is_Suitable_Weakly_Elaborable_Vertex): New routines. + (Trace_Candidate_Vertices): Remove. + (Trace_Component): Output the number of strong and weak + predecessors. + (Trace_Unelaborated_Vertices): Remove. + (Trace_Vertex): Output the number of strong and weak + predecessors. + (Trace_Vertices): New routine. + (Update_Successor, Update_Successors): Update the parameter + profile and the comment on usage. + * bindo-graphs.adb: Remove type Precedence_Kind. + (Add_Edge_With_Return): Update the increment of pending + predecessors. + (Add_Vertex): Provide default values for strong and weak + predecessors. + (Complementary_Vertex): Move the initial declaration to the + spec. Update the parameter profile and the comment on usage. + (Contains_Weak_Static_Successor): New routine. + (Create): Update the parameter profile. The creation of the + graph is now elaboration model-agnostic. + (Decrement_Pending_Predecessors): Update the parameter profile + and the comment on usage. Reimplemented. + (Delete_Edge): Update the decrement of pending predecesors. + (Has_Elaborate_Body): Do not treat a vertex as being subject to + Elaborate_Body when a debug switch is in effect. + (Increment_Pending_Predecessors): Update the parameter profile + and the comment on usage. Reimplemented. + (Is_Elaborable_Component): Reimplemented. + (Is_Elaborable_Vertex): Move the initial declaration to the + spec. Reimplemented. + (Is_Elaborate_Body_Pair): New routine. + (Is_Dynamically_Elaborated): Update the parameter profile. + Reimplemented. + (Is_Weakly_Elaborable_Vertex): New routine. + (Pending_Predecessors): Removed. + (Pending_Predecessors_For_Elaboration, + Pending_Strong_Predecessors, Pending_Weak_Predecessors, + Update_Pending_Predecessors): New routines. + (Update_Pending_Predecessors_Of_Components): Update the + increment of pending predecessors. + * bindo-graphs.ads: Update the components of type + Component_Attributes. Update the components of type + Library_Graph_Attributes. Update the components of type + Library_Graph_Vertex_Attributes. Update the initialization of + No_Component_Attributes. Update the initialization of + No_Library_Graph_Vertex_Attributes. + (Complementary_Vertex, Contains_Weak_Static_Successor): New + routines. + (Create): Update the parameter profile and the comment on usage. + (Decrement_Pending_Predecessors, Is_Dynamically_Elaborated): + Update the parameter profile and the comment on usage. + (Is_Elaborate_Body_Pair, Is_Weakly_Elaborable_Vertex): New + routines. + (Pending_Predecessors): Removed. + (Pending_Predecessors_For_Elaboration, + Pending_Strong_Predecessors, Pending_Weak_Predecessors): New + routines. + * bindo-writers.adb (Write_Components): Moved from the spec. + (Write_Component): Output the strong and weak predecessors. + (Write_Library_Graph): Output the components as part of the + graph. + (Write_Library_Graph_Vertex): Output the strong and weak + predecessors. + * bindo-writers.ads (Write_Components): Moved to the body. + * debug.adb: Add and document new GNATbind switches -d_a, -d_b, + -d_e. + * bindo-validators.adb: Minor reformattings. + 2019-07-08 Bob Duff <duff@adacore.com> * libgnat/g-sercom.ads, libgnat/g-sercom__linux.adb (Data_Rate): diff --git a/gcc/ada/bindo-builders.adb b/gcc/ada/bindo-builders.adb index f4b8e42..233891d 100644 --- a/gcc/ada/bindo-builders.adb +++ b/gcc/ada/bindo-builders.adb @@ -25,12 +25,18 @@ with Binderr; use Binderr; with Butil; use Butil; +with Debug; use Debug; with Opt; use Opt; with Output; use Output; with Types; use Types; with Bindo.Units; use Bindo.Units; +with Bindo.Validators; +use Bindo.Validators; +use Bindo.Validators.Invocation_Graph_Validators; +use Bindo.Validators.Library_Graph_Validators; + with GNAT; use GNAT; with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables; @@ -104,6 +110,8 @@ package body Bindo.Builders is For_Each_Elaborable_Unit (Create_Vertices'Access); For_Each_Elaborable_Unit (Create_Edges'Access); + Validate_Invocation_Graph (Inv_Graph); + return Inv_Graph; end Build_Invocation_Graph; @@ -365,24 +373,22 @@ package body Bindo.Builders is -- Build_Library_Graph -- ------------------------- - function Build_Library_Graph - (Dynamically_Elaborated : Boolean) return Library_Graph - is + function Build_Library_Graph return Library_Graph is begin -- Prepare the global data Lib_Graph := Create - (Initial_Vertices => Number_Of_Elaborable_Units, - Initial_Edges => Number_Of_Elaborable_Units, - Dynamically_Elaborated => Dynamically_Elaborated); + (Initial_Vertices => Number_Of_Elaborable_Units, + Initial_Edges => Number_Of_Elaborable_Units); For_Each_Elaborable_Unit (Create_Vertex'Access); For_Each_Elaborable_Unit (Create_Spec_And_Body_Edge'Access); For_Each_Elaborable_Unit (Create_With_Edges'Access); - Create_Forced_Edges; + Validate_Library_Graph (Lib_Graph); + return Lib_Graph; end Build_Library_Graph; @@ -549,9 +555,13 @@ package body Bindo.Builders is Withed_Vertex := Corresponding_Vertex (Lib_Graph, Withed_U_Id); - -- The with comes with pragma Elaborate + -- The with comes with pragma Elaborate. Treat the edge as a with + -- edge when switch -d_e (ignore the effects of pragma Elaborate) + -- is in effect. - if Withed_Rec.Elaborate then + if Withed_Rec.Elaborate + and then not Debug_Flag_Underscore_E + then Kind := Elaborate_Edge; -- The withed unit is a spec with a completing body. Add an edge @@ -568,9 +578,13 @@ package body Bindo.Builders is Kind => Kind); end if; - -- The with comes with pragma Elaborate_All + -- The with comes with pragma Elaborate_All. Treat the edge as a with + -- edge when switch -d_a (ignore the effects of pragma Elaborate_All) + -- is in effect. - elsif Withed_Rec.Elaborate_All then + elsif Withed_Rec.Elaborate_All + and then not Debug_Flag_Underscore_A + then Kind := Elaborate_All_Edge; -- Otherwise this is a regular with diff --git a/gcc/ada/bindo-builders.ads b/gcc/ada/bindo-builders.ads index 0e8519f..54c39e4 100644 --- a/gcc/ada/bindo-builders.ads +++ b/gcc/ada/bindo-builders.ads @@ -56,11 +56,9 @@ package Bindo.Builders is ---------------------------- package Library_Graph_Builders is - function Build_Library_Graph - (Dynamically_Elaborated : Boolean) return Library_Graph; + function Build_Library_Graph return Library_Graph; -- Return a new library graph that reflects the dependencies between - -- all units of the bind. Flag Dynamically_Elaborated must be set when - -- the main library unit was compiled using the dynamic model. + -- all units of the bind. end Library_Graph_Builders; diff --git a/gcc/ada/bindo-diagnostics.adb b/gcc/ada/bindo-diagnostics.adb index 0c9da46..0c1a924 100644 --- a/gcc/ada/bindo-diagnostics.adb +++ b/gcc/ada/bindo-diagnostics.adb @@ -285,9 +285,9 @@ package body Bindo.Diagnostics is end loop; end Diagnose_All_Cycles; - -------------------------- + ---------------------------- -- Diagnose_Circularities -- - -------------------------- + ---------------------------- procedure Diagnose_Circularities (Inv_Graph : Invocation_Graph; @@ -374,6 +374,12 @@ package body Bindo.Diagnostics is -- taking into account the predecessors and successors involved, as -- well as the nature of the edge. + Elaborate_All_Active := + Elaborate_All_Active + or else Is_Elaborate_All_Edge + (G => Lib_Graph, + Edge => Current_Edge); + Output_Transition (Inv_Graph => Inv_Graph, Lib_Graph => Lib_Graph, @@ -533,12 +539,12 @@ package body Bindo.Diagnostics is pragma Assert (Present (G)); pragma Assert (Present (Cycle)); - -- The cycle contains at least one invocation edge and the main library - -- unit was compiled with the static model. Using the dynamic model may - -- eliminate the invocation edge, and thus the cycle. + -- The cycle contains at least one invocation edge where the successor + -- was statically elaborated. Using the dynamic model may eliminate an + -- invocation edge, and thus the cycle. if Invocation_Edge_Count (G, Cycle) > 0 - and then not Is_Dynamically_Elaborated (G) + and then Contains_Weak_Static_Successor (G, Cycle) then Error_Msg_Info (" use the dynamic elaboration model (compiler switch -gnatE)"); @@ -703,10 +709,11 @@ package body Bindo.Diagnostics is -- Expected_Destination else - pragma Assert (Is_Spec_With_Body (G, Actual_Destination)); - pragma Assert (Is_Body_With_Spec (G, Expected_Destination)); pragma Assert - (Proper_Body (G, Actual_Destination) = Expected_Destination); + (Is_Elaborate_Body_Pair + (G => G, + Spec_Vertex => Actual_Destination, + Body_Vertex => Expected_Destination)); Error_Msg_Unit_1 := Name (G, Source); Error_Msg_Unit_2 := Name (G, Actual_Destination); @@ -922,13 +929,11 @@ package body Bindo.Diagnostics is -- Expected_Destination else - pragma Assert (Is_Spec_With_Body (G, Actual_Destination)); - pragma Assert (Is_Spec_With_Elaborate_Body (G, Actual_Destination)); - pragma Assert (Is_Body_With_Spec (G, Expected_Destination)); - pragma Assert - (Is_Body_Of_Spec_With_Elaborate_Body (G, Expected_Destination)); pragma Assert - (Proper_Body (G, Actual_Destination) = Expected_Destination); + (Is_Elaborate_Body_Pair + (G => G, + Spec_Vertex => Actual_Destination, + Body_Vertex => Expected_Destination)); Error_Msg_Unit_1 := Name (G, Source); Error_Msg_Unit_2 := Name (G, Actual_Destination); @@ -1392,13 +1397,11 @@ package body Bindo.Diagnostics is -- Expected_Destination else - pragma Assert (Is_Spec_With_Body (G, Actual_Destination)); - pragma Assert (Is_Spec_With_Elaborate_Body (G, Actual_Destination)); - pragma Assert (Is_Body_With_Spec (G, Expected_Destination)); - pragma Assert - (Is_Body_Of_Spec_With_Elaborate_Body (G, Expected_Destination)); pragma Assert - (Proper_Body (G, Actual_Destination) = Expected_Destination); + (Is_Elaborate_Body_Pair + (G => G, + Spec_Vertex => Actual_Destination, + Body_Vertex => Expected_Destination)); Error_Msg_Unit_1 := Name (G, Source); Error_Msg_Unit_2 := Name (G, Actual_Destination); diff --git a/gcc/ada/bindo-elaborators.adb b/gcc/ada/bindo-elaborators.adb index 762198b..192e4a2 100644 --- a/gcc/ada/bindo-elaborators.adb +++ b/gcc/ada/bindo-elaborators.adb @@ -46,8 +46,6 @@ use Bindo.Units; with Bindo.Validators; use Bindo.Validators; use Bindo.Validators.Elaboration_Order_Validators; -use Bindo.Validators.Invocation_Graph_Validators; -use Bindo.Validators.Library_Graph_Validators; with Bindo.Writers; use Bindo.Writers; @@ -76,76 +74,61 @@ package body Bindo.Elaborators is ---------------------------------------------- package body Invocation_And_Library_Graph_Elaborators is - Add_To_All_Candidates_Msg : aliased String := - "add vertex to all candidates"; - Add_To_Comp_Candidates_Msg : aliased String := - "add vertex to component candidates"; - - ----------- - -- Types -- - ----------- - - type String_Ptr is access all String; ----------------------- -- Local subprograms -- ----------------------- - procedure Add_Vertex - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - Set : LGV_Sets.Membership_Set; - Msg : String; - Step : Elaboration_Order_Step; - Indent : Indentation_Level); - pragma Inline (Add_Vertex); - -- Add vertex Vertex of library graph G to membership set Set. Msg is - -- a message emitted for tracing purposes. Step is the current step in - -- the elaboration order. Indent is the desired indentation level for - -- tracing. - - procedure Add_Vertex_If_Elaborable - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - Set : LGV_Sets.Membership_Set; - Msg : String; - Step : Elaboration_Order_Step; - Indent : Indentation_Level); - pragma Inline (Add_Vertex_If_Elaborable); - -- Add vertex Vertex of library graph G to membership set Set if it can - -- be elaborated. Msg is a message emitted for tracing purposes. Step is - -- the current step in the elaboration order. Indent is the desired - -- indentation level for tracing. - - function Create_All_Candidates_Set - (G : Library_Graph; - Step : Elaboration_Order_Step) return LGV_Sets.Membership_Set; - pragma Inline (Create_All_Candidates_Set); - -- Collect all elaborable candidate vertices of library graph G in a - -- set. Step is the current step in the elaboration order. - - function Create_Component_Candidates_Set - (G : Library_Graph; - Comp : Component_Id; - Step : Elaboration_Order_Step) return LGV_Sets.Membership_Set; - pragma Inline (Create_Component_Candidates_Set); - -- Collect all elaborable candidate vertices that appear in component - -- Comp of library graph G in a set. Step is the current step in the - -- elaboration order. + procedure Create_Component_Vertex_Sets + (G : Library_Graph; + Comp : Component_Id; + Elaborable_Vertices : out LGV_Sets.Membership_Set; + Waiting_Vertices : out LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step); + pragma Inline (Create_Component_Vertex_Sets); + -- Split all vertices of component Comp of library graph G as follows: + -- + -- * Elaborable vertices are added to set Elaborable_Vertices. + -- + -- * Vertices that are still waiting on their predecessors to be + -- elaborated are added to set Waiting_Vertices. + -- + -- Step is the current step in the elaboration order. + + procedure Create_Vertex_Sets + (G : Library_Graph; + Elaborable_Vertices : out LGV_Sets.Membership_Set; + Waiting_Vertices : out LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step); + pragma Inline (Create_Vertex_Sets); + -- Split all vertices of library graph G as follows: + -- + -- * Elaborable vertices are added to set Elaborable_Vertices. + -- + -- * Vertices that are still waiting on their predecessors to be + -- elaborated are added to set Waiting_Vertices. + -- + -- Step is the current step in the elaboration order. procedure Elaborate_Component - (G : Library_Graph; - Comp : Component_Id; - All_Candidates : LGV_Sets.Membership_Set; - Remaining_Vertices : in out Natural; - Order : in out Unit_Id_Table; - Step : Elaboration_Order_Step); + (G : Library_Graph; + Comp : Component_Id; + All_Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Order : in out Unit_Id_Table; + Step : Elaboration_Order_Step); pragma Inline (Elaborate_Component); - -- Elaborate as many vertices as possible that appear in component - -- Comp of library graph G. All_Candidates is the set of all elaborable - -- vertices across the whole library graph. Remaining_Vertices is the - -- number of vertices that remain to be elaborated. Order denotes the - -- elaboration order. Step is the current step in the elaboration order. + -- Elaborate as many vertices as possible that appear in component Comp + -- of library graph G. The sets contain vertices arranged as follows: + -- + -- * All_Elaborable_Vertices - all elaborable vertices in the library + -- graph. + -- + -- * All_Waiting_Vertices - all vertices in the library graph that are + -- waiting on predecessors to be elaborated. + -- + -- Order is the elaboration order. Step denotes the current step in the + -- elaboration order. procedure Elaborate_Library_Graph (G : Library_Graph; @@ -156,81 +139,149 @@ package body Bindo.Elaborators is -- the elaboration order. Status is the condition of the elaboration -- order. - procedure Elaborate_Units_Common - (Use_Inv_Graph : Boolean; - Is_Dyn_Elab : Boolean; - Inv_Graph : out Invocation_Graph; - Lib_Graph : out Library_Graph; - Order : out Unit_Id_Table; - Status : out Elaboration_Order_Status); - pragma Inline (Elaborate_Units_Common); - -- Find the elaboration order of all units in the bind. Use_Inv_Graph - -- should be set when library graph Lib_Graph is to be augmented with - -- information from invocation graph Inv_Graph. Is_Dyn_Elab should be - -- set when the main library unit was compiled using the dynamic model. - -- Order is the elaboration order. Status is the condition of the - -- elaboration order. - - procedure Elaborate_Units_Dynamic (Order : out Unit_Id_Table); - pragma Inline (Elaborate_Units_Dynamic); - -- Find the elaboration order of all units in the bind using the dynamic - -- model. Order is the elaboration order. In the event where no ordering - -- is possible, this routine diagnoses the issue(s) and raises exception - -- Unrecoverable_Error. - - procedure Elaborate_Units_Static (Order : out Unit_Id_Table); - pragma Inline (Elaborate_Units_Static); - -- Find the elaboration order of all units in the bind using the static - -- model. Order is the elaboration order. In the event where no ordering - -- is possible, this routine diagnoses the issue(s) and raises exception - -- Unrecoverable_Error. - procedure Elaborate_Vertex - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - All_Candidates : LGV_Sets.Membership_Set; - Comp_Candidates : LGV_Sets.Membership_Set; - Remaining_Vertices : in out Natural; - Order : in out Unit_Id_Table; - Step : Elaboration_Order_Step; - Indent : Indentation_Level); + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + All_Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Comp_Elaborable_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Order : in out Unit_Id_Table; + Step : Elaboration_Order_Step; + Indent : Indentation_Level); pragma Inline (Elaborate_Vertex); -- Elaborate vertex Vertex of library graph G by adding its unit to -- elaboration order Order. The routine updates awaiting successors - -- where applicable. All_Candidates denotes the set of all elaborable - -- vertices across the whole library graph. Comp_Candidates is the set - -- of all elaborable vertices in the component of Vertex. Parameter - -- Remaining_Vertices denotes the number of vertices that remain to - -- be elaborated. Step is the current step in the elaboration order. + -- where applicable. The sets contain vertices arranged as follows: + -- + -- * All_Elaborable_Vertices - all elaborable vertices in the library + -- graph. + -- + -- * All_Waiting_Vertices - all vertices in the library graph that are + -- waiting on predecessors to be elaborated. + -- + -- * Comp_Elaborable_Vertices - all elaborable vertices found in the + -- component of Vertex. + -- + -- * Comp_Waiting_Vertices - all vertices found in the component of + -- Vertex that are still waiting on predecessors to be elaborated. + -- + -- Order denotes the elaboration order. Step is the current step in the + -- elaboration order. Indent denotes the desired indentation level for + -- tracing. + + function Find_Best_Elaborable_Vertex + (G : Library_Graph; + Set : LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) return Library_Graph_Vertex_Id; + pragma Inline (Find_Best_Elaborable_Vertex); + -- Find the best vertex of library graph G from membership set S that + -- can be elaborated. Step is the current step in the elaboration order. -- Indent is the desired indentation level for tracing. - function Find_Best_Candidate + type Comparator_Ptr is access function + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind; + + type Predicate_Ptr is access function + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean; + + function Find_Best_Vertex + (G : Library_Graph; + Set : LGV_Sets.Membership_Set; + Is_Suitable_Vertex : Predicate_Ptr; + Compare_Vertices : Comparator_Ptr; + Initial_Best_Msg : String; + Subsequent_Best_Msg : String; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) + return Library_Graph_Vertex_Id; + pragma Inline (Find_Best_Vertex); + -- Find the best vertex of library graph G from membership set S which + -- satisfies predicate Is_Suitable_Vertex and is preferred by comparator + -- Compare_Vertices. Initial_Best_Msg is emitted on the first candidate + -- vertex. Subsequent_Best_Msg is emitted whenever a better vertex is + -- discovered. Step is the current step in the elaboration order. Indent + -- is the desired indentation level for tracing. + + function Find_Best_Weakly_Elaborable_Vertex (G : Library_Graph; Set : LGV_Sets.Membership_Set; Step : Elaboration_Order_Step; Indent : Indentation_Level) return Library_Graph_Vertex_Id; - pragma Inline (Find_Best_Candidate); - -- Find the most suitable vertex of library graph G for elaboration from - -- membership set Set. Step denotes the current step in the elaboration + pragma Inline (Find_Best_Weakly_Elaborable_Vertex); + -- Find the best vertex of library graph G from membership set S that + -- can be weakly elaborated. Step is the current step in the elaboration -- order. Indent is the desired indentation level for tracing. - function Is_Better_Candidate - (G : Library_Graph; - Best_Candidate : Library_Graph_Vertex_Id; - New_Candidate : Library_Graph_Vertex_Id) return Boolean; - pragma Inline (Is_Better_Candidate); - -- Determine whether new candidate vertex New_Candidate of library graph - -- G is a more suitable choice for elaboration compared to the current - -- best candidate Best_Candidate. + function Has_Elaborable_Body + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean; + pragma Inline (Has_Elaborable_Body); + -- Determine whether vertex Vertex of library graph G has a body that is + -- elaborable. It is assumed that the vertex has been elaborated. + + procedure Insert_Elaborable_Successor + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Msg : String; + Step : Elaboration_Order_Step; + Indent : Indentation_Level); + pragma Inline (Insert_Elaborable_Successor); + -- Add elaborable successor Vertex of library graph G to membership set + -- Elaborable_Vertices and remove it from both All_Waiting_Vertices and + -- Comp_Waiting_Vertices. Msg is a message emitted for tracing purposes. + -- Step is the current step in the elaboration order. Indent denotes the + -- desired indentation level for tracing. + + procedure Insert_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Set : LGV_Sets.Membership_Set; + Msg : String; + Step : Elaboration_Order_Step; + Indent : Indentation_Level); + pragma Inline (Insert_Vertex); + -- Add vertex Vertex of library graph G to membership set Set. Msg is + -- a message emitted for tracing purposes. Step is the current step in + -- the elaboration order. Indent is the desired indentation level for + -- tracing. - procedure Trace_Candidate_Vertices - (G : Library_Graph; - Set : LGV_Sets.Membership_Set; - Step : Elaboration_Order_Step); - pragma Inline (Trace_Candidate_Vertices); - -- Write the candidate vertices of library graph G present in membership - -- set Set to standard output. Formal Step denotes the current step in - -- the elaboration order. + function Is_Better_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind; + pragma Inline (Is_Better_Elaborable_Vertex); + -- Determine whether vertex Vertex of library graph G is a better choice + -- for elaboration compared to vertex Compared_To. + + function Is_Better_Weakly_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind; + pragma Inline (Is_Better_Weakly_Elaborable_Vertex); + -- Determine whether vertex Vertex of library graph G is a better choice + -- for weak elaboration compared to vertex Compared_To. + + function Is_Suitable_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean; + pragma Inline (Is_Suitable_Elaborable_Vertex); + -- Determine whether vertex Vertex of library graph G is suitable for + -- elaboration. + + function Is_Suitable_Weakly_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean; + pragma Inline (Is_Suitable_Weakly_Elaborable_Vertex); + -- Determine whether vertex Vertex of library graph G is suitable for + -- weak elaboration. procedure Trace_Component (G : Library_Graph; @@ -246,15 +297,6 @@ package body Bindo.Elaborators is pragma Inline (Trace_Step); -- Write current step Step of the elaboration order to standard output - procedure Trace_Unelaborated_Vertices - (G : Library_Graph; - Count : Natural; - Step : Elaboration_Order_Step); - pragma Inline (Trace_Unelaborated_Vertices); - -- Write the remaining unelaborated vertices of library graph G to - -- standard output. Count is the number of vertices that remain to - -- be elaborated. Step is the current step in the elaboration order. - procedure Trace_Vertex (G : Library_Graph; Vertex : Library_Graph_Vertex_Id; @@ -267,220 +309,202 @@ package body Bindo.Elaborators is -- current step in the elaboration order. Indent denotes the desired -- indentation level for tracing. + procedure Trace_Vertices + (G : Library_Graph; + Set : LGV_Sets.Membership_Set; + Set_Msg : String; + Vertex_Msg : String; + Step : Elaboration_Order_Step; + Indent : Indentation_Level); + pragma Inline (Trace_Vertices); + -- Write the candidate vertices of library graph G present in membership + -- set Set to standard output, starting with message Set_Msg. Vertex_Msg + -- is the message emitted prior to each vertex. Step denotes the current + -- step in the elaboration order. Indent denotes the desired indentation + -- level for tracing. + procedure Update_Successor - (G : Library_Graph; - Pred : Library_Graph_Vertex_Id; - Succ : Library_Graph_Vertex_Id; - All_Candidates : LGV_Sets.Membership_Set; - Comp_Candidates : LGV_Sets.Membership_Set; - Step : Elaboration_Order_Step; - Indent : Indentation_Level); + (G : Library_Graph; + Edge : Library_Graph_Edge_Id; + All_Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Comp_Elaborable_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step; + Indent : Indentation_Level); pragma Inline (Update_Successor); - -- Notify successor vertex Succ of library graph G along with its - -- component that their predecessor Pred has just been elaborated. - -- This may cause new vertices to become elaborable, and thus be added - -- to one of the two sets. All_Candidates is the set of all elaborable - -- vertices across the whole library graph. Comp_Candidates is the set - -- of all elaborable vertices in the component of Pred. Step is the - -- current step in the elaboration order. Indent denotes the desired - -- indentation level for tracing. + -- Notify the successor of edge Edge of library graph G along with its + -- component that their predecessor has just been elaborated. This may + -- cause new vertices to become elaborable. The sets contain vertices + -- arranged as follows: + -- + -- * All_Elaborable_Vertices - all elaborable vertices in the library + -- graph. + -- + -- * All_Waiting_Vertices - all vertices in the library graph that are + -- waiting on predecessors to be elaborated. + -- + -- * Comp_Elaborable_Vertices - all elaborable vertices found in the + -- component of Vertex. + -- + -- * Comp_Waiting_Vertices - all vertices found in the component of + -- Vertex that are still waiting on predecessors to be elaborated. + -- + -- Step is the current step in the elaboration order. Indent denotes the + -- desired indentation level for tracing. procedure Update_Successors - (G : Library_Graph; - Pred : Library_Graph_Vertex_Id; - All_Candidates : LGV_Sets.Membership_Set; - Comp_Candidates : LGV_Sets.Membership_Set; - Step : Elaboration_Order_Step; - Indent : Indentation_Level); + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + All_Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Comp_Elaborable_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step; + Indent : Indentation_Level); pragma Inline (Update_Successors); - -- Notify all successors along with their components that their - -- predecessor vertex Pred of ligrary graph G has just been elaborated. - -- This may cause new vertices to become elaborable, and thus be added - -- to one of the two sets. All_Candidates is the set of all elaborable - -- vertices across the whole library graph. Comp_Candidates is the set - -- of all elaborable vertices in the component of Pred. Step is the - -- current step in the elaboration order. Indent denotes the desired - -- indentation level for tracing. - - ---------------- - -- Add_Vertex -- - ---------------- - - procedure Add_Vertex - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - Set : LGV_Sets.Membership_Set; - Msg : String; - Step : Elaboration_Order_Step; - Indent : Indentation_Level) + -- Notify all successors of vertex Vertex of library graph G along with + -- their components that their predecessor has just been elaborated. + -- This may cause new vertices to become elaborable. The sets contain + -- vertices arranged as follows: + -- + -- * All_Elaborable_Vertices - all elaborable vertices in the library + -- graph. + -- + -- * All_Waiting_Vertices - all vertices in the library graph that are + -- waiting on predecessors to be elaborated. + -- + -- * Comp_Elaborable_Vertices - all elaborable vertices found in the + -- component of Vertex. + -- + -- * Comp_Waiting_Vertices - all vertices found in the component of + -- Vertex that are still waiting on predecessors to be elaborated. + -- + -- Step is the current step in the elaboration order. Indent denotes the + -- desired indentation level for tracing. + + ---------------------------------- + -- Create_Component_Vertex_Sets -- + ---------------------------------- + + procedure Create_Component_Vertex_Sets + (G : Library_Graph; + Comp : Component_Id; + Elaborable_Vertices : out LGV_Sets.Membership_Set; + Waiting_Vertices : out LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step) is - begin - pragma Assert (Present (Vertex)); - pragma Assert (Needs_Elaboration (G, Vertex)); - pragma Assert (LGV_Sets.Present (Set)); - - -- Add vertex only when it is not present in the set. This is not - -- strictly necessary because the set implementation handles this - -- case, however the check eliminates spurious traces. - - if not LGV_Sets.Contains (Set, Vertex) then - Trace_Vertex - (G => G, - Vertex => Vertex, - Msg => Msg, - Step => Step, - Indent => Indent); - - LGV_Sets.Insert (Set, Vertex); - end if; - end Add_Vertex; + pragma Assert (Present (G)); + pragma Assert (Present (Comp)); - ------------------------------ - -- Add_Vertex_If_Elaborable -- - ------------------------------ + Num_Of_Vertices : constant Natural := + Number_Of_Component_Vertices (G, Comp); - procedure Add_Vertex_If_Elaborable - (G : Library_Graph; + Iter : Component_Vertex_Iterator; Vertex : Library_Graph_Vertex_Id; - Set : LGV_Sets.Membership_Set; - Msg : String; - Step : Elaboration_Order_Step; - Indent : Indentation_Level) - is - Extra_Vertex : Library_Graph_Vertex_Id; begin - pragma Assert (Present (G)); - pragma Assert (Present (Vertex)); - pragma Assert (Needs_Elaboration (G, Vertex)); - pragma Assert (LGV_Sets.Present (Set)); - - if Is_Elaborable_Vertex (G, Vertex) then - Add_Vertex - (G => G, - Vertex => Vertex, - Set => Set, - Msg => Msg, - Step => Step, - Indent => Indent); - - -- Assume that there is no extra vertex that needs to be added + Elaborable_Vertices := LGV_Sets.Create (Num_Of_Vertices); + Waiting_Vertices := LGV_Sets.Create (Num_Of_Vertices); - Extra_Vertex := No_Library_Graph_Vertex; - - -- A spec-body pair where the spec carries pragma Elaborate_Body - -- must be treated as one vertex for elaboration purposes. If one - -- of them is elaborable, then the other is also elaborable. This - -- property is guaranteed by predicate Is_Elaborable_Vertex. - - if Is_Body_Of_Spec_With_Elaborate_Body (G, Vertex) then - Extra_Vertex := Proper_Spec (G, Vertex); - pragma Assert (Present (Extra_Vertex)); + Iter := Iterate_Component_Vertices (G, Comp); + while Has_Next (Iter) loop + Next (Iter, Vertex); - elsif Is_Spec_With_Elaborate_Body (G, Vertex) then - Extra_Vertex := Proper_Body (G, Vertex); - pragma Assert (Present (Extra_Vertex)); - end if; + -- Add the vertex to the proper set depending on whether it can be + -- elaborated. - if Present (Extra_Vertex) then - pragma Assert (Needs_Elaboration (G, Extra_Vertex)); + if Is_Elaborable_Vertex (G, Vertex) then + Insert_Vertex + (G => G, + Vertex => Vertex, + Set => Elaborable_Vertices, + Msg => "add elaborable component vertex", + Step => Step, + Indent => No_Indentation); - Add_Vertex + else + Insert_Vertex (G => G, - Vertex => Extra_Vertex, - Set => Set, - Msg => Msg, + Vertex => Vertex, + Set => Waiting_Vertices, + Msg => "add waiting component vertex", Step => Step, - Indent => Indent); + Indent => No_Indentation); end if; - end if; - end Add_Vertex_If_Elaborable; + end loop; + end Create_Component_Vertex_Sets; - ------------------------------- - -- Create_All_Candidates_Set -- - ------------------------------- + ------------------------ + -- Create_Vertex_Sets -- + ------------------------ - function Create_All_Candidates_Set - (G : Library_Graph; - Step : Elaboration_Order_Step) return LGV_Sets.Membership_Set + procedure Create_Vertex_Sets + (G : Library_Graph; + Elaborable_Vertices : out LGV_Sets.Membership_Set; + Waiting_Vertices : out LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step) is + pragma Assert (Present (G)); + + Num_Of_Vertices : constant Natural := Number_Of_Vertices (G); + Iter : Library_Graphs.All_Vertex_Iterator; - Set : LGV_Sets.Membership_Set; Vertex : Library_Graph_Vertex_Id; begin - pragma Assert (Present (G)); + Elaborable_Vertices := LGV_Sets.Create (Num_Of_Vertices); + Waiting_Vertices := LGV_Sets.Create (Num_Of_Vertices); - Set := LGV_Sets.Create (Number_Of_Vertices (G)); Iter := Iterate_All_Vertices (G); while Has_Next (Iter) loop Next (Iter, Vertex); - Add_Vertex_If_Elaborable - (G => G, - Vertex => Vertex, - Set => Set, - Msg => Add_To_All_Candidates_Msg, - Step => Step, - Indent => No_Indentation); - end loop; - - return Set; - end Create_All_Candidates_Set; - - ------------------------------------- - -- Create_Component_Candidates_Set -- - ------------------------------------- - - function Create_Component_Candidates_Set - (G : Library_Graph; - Comp : Component_Id; - Step : Elaboration_Order_Step) return LGV_Sets.Membership_Set - is - Iter : Component_Vertex_Iterator; - Set : LGV_Sets.Membership_Set; - Vertex : Library_Graph_Vertex_Id; - - begin - pragma Assert (Present (G)); - pragma Assert (Present (Comp)); + -- Add the vertex to the proper set depending on whether it can be + -- elaborated. - Set := LGV_Sets.Create (Number_Of_Component_Vertices (G, Comp)); - Iter := Iterate_Component_Vertices (G, Comp); - while Has_Next (Iter) loop - Next (Iter, Vertex); + if Is_Elaborable_Vertex (G, Vertex) then + Insert_Vertex + (G => G, + Vertex => Vertex, + Set => Elaborable_Vertices, + Msg => "add elaborable vertex", + Step => Step, + Indent => No_Indentation); - Add_Vertex_If_Elaborable - (G => G, - Vertex => Vertex, - Set => Set, - Msg => Add_To_Comp_Candidates_Msg, - Step => Step, - Indent => No_Indentation); + else + Insert_Vertex + (G => G, + Vertex => Vertex, + Set => Waiting_Vertices, + Msg => "add waiting vertex", + Step => Step, + Indent => No_Indentation); + end if; end loop; - - return Set; - end Create_Component_Candidates_Set; + end Create_Vertex_Sets; ------------------------- -- Elaborate_Component -- ------------------------- procedure Elaborate_Component - (G : Library_Graph; - Comp : Component_Id; - All_Candidates : LGV_Sets.Membership_Set; - Remaining_Vertices : in out Natural; - Order : in out Unit_Id_Table; - Step : Elaboration_Order_Step) + (G : Library_Graph; + Comp : Component_Id; + All_Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Order : in out Unit_Id_Table; + Step : Elaboration_Order_Step) is - Candidate : Library_Graph_Vertex_Id; - Comp_Candidates : LGV_Sets.Membership_Set; + Comp_Elaborable_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Vertex : Library_Graph_Vertex_Id; begin pragma Assert (Present (G)); pragma Assert (Present (Comp)); - pragma Assert (LGV_Sets.Present (All_Candidates)); + pragma Assert (LGV_Sets.Present (All_Elaborable_Vertices)); + pragma Assert (LGV_Sets.Present (All_Waiting_Vertices)); Trace_Component (G => G, @@ -488,35 +512,81 @@ package body Bindo.Elaborators is Msg => "elaborating component", Step => Step); - Comp_Candidates := Create_Component_Candidates_Set (G, Comp, Step); + -- Divide all vertices of the component into an elaborable and + -- waiting vertex set. + + Create_Component_Vertex_Sets + (G => G, + Comp => Comp, + Elaborable_Vertices => Comp_Elaborable_Vertices, + Waiting_Vertices => Comp_Waiting_Vertices, + Step => Step); loop - Candidate := - Find_Best_Candidate + Trace_Vertices + (G => G, + Set => Comp_Elaborable_Vertices, + Set_Msg => "elaborable component vertices", + Vertex_Msg => "elaborable component vertex", + Step => Step, + Indent => Nested_Indentation); + + Trace_Vertices + (G => G, + Set => Comp_Waiting_Vertices, + Set_Msg => "waiting component vertices", + Vertex_Msg => "waiting component vertex", + Step => Step, + Indent => Nested_Indentation); + + Vertex := + Find_Best_Elaborable_Vertex (G => G, - Set => Comp_Candidates, + Set => Comp_Elaborable_Vertices, Step => Step, Indent => Nested_Indentation); - -- Stop the elaboration of the component when there is no suitable - -- candidate. This indicates that either all vertices within the - -- component have been elaborated, or the library graph contains a - -- circularity. + -- The component lacks an elaborable vertex. This indicates that + -- either all vertices of the component have been elaborated or + -- the graph has a circularity. Locate the best weak vertex that + -- was compiled with the dynamic model to elaborate from the set + -- waiting vertices. This action assumes that certain invocations + -- will not take place at elaboration time. An order produced in + -- this fashion may fail an ABE check at run time. + + if not Present (Vertex) then + Vertex := + Find_Best_Weakly_Elaborable_Vertex + (G => G, + Set => Comp_Waiting_Vertices, + Step => Step, + Indent => Nested_Indentation); + end if; + + -- Stop the elaboration when either all vertices of the component + -- have been elaborated, or the graph contains a circularity. + + exit when not Present (Vertex); - exit when not Present (Candidate); + -- Try to elaborate as many vertices within the component as + -- possible. Each successful elaboration signals the appropriate + -- successors and components that they have one less predecessor + -- to wait on. Elaborate_Vertex - (G => G, - Vertex => Candidate, - All_Candidates => All_Candidates, - Comp_Candidates => Comp_Candidates, - Remaining_Vertices => Remaining_Vertices, - Order => Order, - Step => Step, - Indent => Nested_Indentation); + (G => G, + Vertex => Vertex, + All_Elaborable_Vertices => All_Elaborable_Vertices, + All_Waiting_Vertices => All_Waiting_Vertices, + Comp_Elaborable_Vertices => Comp_Elaborable_Vertices, + Comp_Waiting_Vertices => Comp_Waiting_Vertices, + Order => Order, + Step => Step, + Indent => Nested_Indentation); end loop; - LGV_Sets.Destroy (Comp_Candidates); + LGV_Sets.Destroy (Comp_Elaborable_Vertices); + LGV_Sets.Destroy (Comp_Waiting_Vertices); end Elaborate_Component; ----------------------------- @@ -528,73 +598,97 @@ package body Bindo.Elaborators is Order : out Unit_Id_Table; Status : out Elaboration_Order_Status) is - All_Candidates : LGV_Sets.Membership_Set; - Candidate : Library_Graph_Vertex_Id; - Remaining_Vertices : Natural; - Step : Elaboration_Order_Step; + Elaborable_Vertices : LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step; + Vertex : Library_Graph_Vertex_Id; + Waiting_Vertices : LGV_Sets.Membership_Set; begin pragma Assert (Present (G)); Step := Initial_Step; - All_Candidates := Create_All_Candidates_Set (G, Step); - Remaining_Vertices := Number_Of_Vertices (G); + -- Divide all vertices of the library graph into an elaborable and + -- waiting vertex set. + + Create_Vertex_Sets + (G => G, + Elaborable_Vertices => Elaborable_Vertices, + Waiting_Vertices => Waiting_Vertices, + Step => Step); loop Step := Step + 1; - Trace_Candidate_Vertices - (G => G, - Set => All_Candidates, - Step => Step); - - Trace_Unelaborated_Vertices - (G => G, - Count => Remaining_Vertices, - Step => Step); - - Candidate := - Find_Best_Candidate + Trace_Vertices + (G => G, + Set => Elaborable_Vertices, + Set_Msg => "elaborable vertices", + Vertex_Msg => "elaborable vertex", + Step => Step, + Indent => No_Indentation); + + Trace_Vertices + (G => G, + Set => Waiting_Vertices, + Set_Msg => "waiting vertices", + Vertex_Msg => "waiting vertex", + Step => Step, + Indent => No_Indentation); + + Vertex := + Find_Best_Elaborable_Vertex (G => G, - Set => All_Candidates, + Set => Elaborable_Vertices, Step => Step, Indent => No_Indentation); - -- Stop the elaboration when there is no suitable candidate. This - -- indicates that either all units were elaborated or the library - -- graph contains a circularity. + -- The graph lacks an elaborable vertex. This indicates that + -- either all vertices have been elaborated or the graph has a + -- circularity. Find the best weak vertex that was compiled with + -- the dynamic model to elaborate from set of waiting vertices. + -- This action assumes that certain invocations will not take + -- place at elaboration time. An order produced in this fashion + -- may fail an ABE check at run time. + + if not Present (Vertex) then + Vertex := + Find_Best_Weakly_Elaborable_Vertex + (G => G, + Set => Waiting_Vertices, + Step => Step, + Indent => No_Indentation); + end if; + + -- Stop the elaboration when either all vertices of the graph have + -- been elaborated, or the graph contains a circularity. - exit when not Present (Candidate); + exit when not Present (Vertex); - -- Elaborate the component of the candidate vertex by trying to - -- elaborate as many vertices within the component as possible. - -- Each successful elaboration signals the appropriate successors - -- and their components that they have one less predecessor to - -- wait on. This may add new candidates to set All_Candidates. + -- Elaborate the component of the vertex by trying to elaborate as + -- many vertices within the component as possible. Each successful + -- elaboration signals the appropriate successors and components + -- that they have one less predecessor to wait on. Elaborate_Component - (G => G, - Comp => Component (G, Candidate), - All_Candidates => All_Candidates, - Remaining_Vertices => Remaining_Vertices, - Order => Order, - Step => Step); + (G => G, + Comp => Component (G, Vertex), + All_Elaborable_Vertices => Elaborable_Vertices, + All_Waiting_Vertices => Waiting_Vertices, + Order => Order, + Step => Step); end loop; - LGV_Sets.Destroy (All_Candidates); - - -- The library graph contains an Elaborate_All circularity when - -- at least one edge subject to the related pragma appears in a - -- component. + -- The graph contains an Elaborate_All circularity when at least one + -- edge subject to the related pragma appears in a component. if Has_Elaborate_All_Cycle (G) then Status := Order_Has_Elaborate_All_Circularity; - -- The library contains a circularity when at least one vertex failed + -- The graph contains a circularity when at least one vertex failed -- to elaborate. - elsif Remaining_Vertices /= 0 then + elsif LGV_Sets.Size (Waiting_Vertices) /= 0 then Status := Order_Has_Circularity; -- Otherwise the elaboration order is satisfactory @@ -602,6 +696,9 @@ package body Bindo.Elaborators is else Status := Order_OK; end if; + + LGV_Sets.Destroy (Elaborable_Vertices); + LGV_Sets.Destroy (Waiting_Vertices); end Elaborate_Library_Graph; --------------------- @@ -612,271 +709,114 @@ package body Bindo.Elaborators is (Order : out Unit_Id_Table; Main_Lib_File : File_Name_Type) is - Main_Lib_Unit : constant Unit_Id := - Corresponding_Unit (Unit_Name_Type (Main_Lib_File)); + pragma Unreferenced (Main_Lib_File); - begin - pragma Assert (Present (Main_Lib_Unit)); + Inv_Graph : Invocation_Graph; + Lib_Graph : Library_Graph; + Status : Elaboration_Order_Status; + begin -- Initialize all unit-related data structures and gather all units -- that need elaboration. Initialize_Units; Collect_Elaborable_Units; - Write_ALI_Tables; - - -- Choose the proper elaboration strategy based on whether the main - -- library unit was compiled using the dynamic model. - - if Is_Dynamically_Elaborated (Main_Lib_Unit) then - Elaborate_Units_Dynamic (Order); - else - Elaborate_Units_Static (Order); - end if; - - Validate_Elaboration_Order (Order); - Write_Elaboration_Order (Order); - - -- Enumerate the sources referenced in the closure of the order - - Write_Unit_Closure (Order); - - -- Destroy all unit-delated data structures - - Finalize_Units; - - exception - when others => - Finalize_Units; - raise; - end Elaborate_Units; - - ---------------------------- - -- Elaborate_Units_Common -- - ---------------------------- - - procedure Elaborate_Units_Common - (Use_Inv_Graph : Boolean; - Is_Dyn_Elab : Boolean; - Inv_Graph : out Invocation_Graph; - Lib_Graph : out Library_Graph; - Order : out Unit_Id_Table; - Status : out Elaboration_Order_Status) - is - begin - -- Create, validate, and output the library graph that captures the - -- dependencies between library items. - - Lib_Graph := Build_Library_Graph (Is_Dyn_Elab); - Validate_Library_Graph (Lib_Graph); - Write_Library_Graph (Lib_Graph); - - -- Create, validate, output, and use the invocation graph that - -- represents the flow of execusion only when requested by the - -- caller. + -- Create the library graph that captures the dependencies between + -- library items. - if Use_Inv_Graph then - Inv_Graph := Build_Invocation_Graph (Lib_Graph); - Validate_Invocation_Graph (Inv_Graph); - Write_Invocation_Graph (Inv_Graph); + Lib_Graph := Build_Library_Graph; - -- Otherwise the invocation graph is not used. Create a dummy graph - -- as this allows for a uniform behavior on the caller side. + -- Create the invocation graph that represents the flow of execution - else - Inv_Graph := - Invocation_Graphs.Create - (Initial_Vertices => 1, - Initial_Edges => 1); - end if; + Inv_Graph := Build_Invocation_Graph (Lib_Graph); -- Traverse the invocation graph starting from elaboration code in -- order to discover transitions of the execution flow from a unit -- to a unit that result in extra edges within the library graph. Augment_Library_Graph (Inv_Graph, Lib_Graph); - Write_Library_Graph (Lib_Graph); - -- Create and output the component graph by collapsing all library - -- items into library units and traversing the library graph. + -- Create the component graph by collapsing all library items into + -- library units and traversing the library graph. - Find_Components (Lib_Graph); - Write_Components (Lib_Graph); + Find_Components (Lib_Graph); - -- Traverse the library graph to determine the elaboration order of - -- units. + -- Output the contents of the ALI tables and both graphs to standard + -- output now that they have been fully decorated. - Elaborate_Library_Graph - (G => Lib_Graph, - Order => Order, - Status => Status); - end Elaborate_Units_Common; - - ----------------------------- - -- Elaborate_Units_Dynamic -- - ----------------------------- + Write_ALI_Tables; + Write_Invocation_Graph (Inv_Graph); + Write_Library_Graph (Lib_Graph); - procedure Elaborate_Units_Dynamic (Order : out Unit_Id_Table) is - Dyn_Inv_Graph : Invocation_Graph; - Dyn_Lib_Graph : Library_Graph; - Dyn_Order : Unit_Id_Table; - Mix_Inv_Graph : Invocation_Graph; - Mix_Lib_Graph : Library_Graph; - Mix_Order : Unit_Id_Table; - Status : Elaboration_Order_Status; + -- Traverse the library graph to determine the elaboration order of + -- units. - begin - -- Attempt to elaborate the units in the library graph by mixing in - -- the information from the invocation graph. This assumes that all - -- invocations will take place at elaboration time. - - Elaborate_Units_Common - (Use_Inv_Graph => True, - Is_Dyn_Elab => True, - Inv_Graph => Mix_Inv_Graph, - Lib_Graph => Mix_Lib_Graph, - Order => Mix_Order, - Status => Status); + Elaborate_Library_Graph (Lib_Graph, Order, Status); -- The elaboration order is satisfactory if Status = Order_OK then - Order := Mix_Order; + Validate_Elaboration_Order (Order); - -- Output the dependencies of vertices when switch -e (output + -- Output the dependencies among units when switch -e (output -- complete list of elaboration order dependencies) is active. - Write_Dependencies (Mix_Lib_Graph); - - -- The library graph contains an Elaborate_All circularity. There is - -- no point in re-elaborating the units without the information from - -- the invocation graph because the circularity will persist. - - elsif Status = Order_Has_Elaborate_All_Circularity then - Diagnose_Circularities - (Inv_Graph => Mix_Inv_Graph, - Lib_Graph => Mix_Lib_Graph); - - -- Otherwise the library graph contains a circularity, or the extra - -- information provided by the invocation graph caused a circularity. - -- Re-elaborate the units without using the invocation graph. This - -- assumes that all invocations will not take place at elaboration - -- time. - - else - pragma Assert (Status = Order_Has_Circularity); - - Elaborate_Units_Common - (Use_Inv_Graph => False, - Is_Dyn_Elab => True, - Inv_Graph => Dyn_Inv_Graph, - Lib_Graph => Dyn_Lib_Graph, - Order => Dyn_Order, - Status => Status); - - -- The elaboration order is satisfactory. The elaboration of the - -- program may still fail at runtime with an ABE. - - if Status = Order_OK then - Order := Dyn_Order; - - -- Output the dependencies of vertices when switch -e (output - -- complete list of elaboration order dependencies) is active. - - Write_Dependencies (Dyn_Lib_Graph); - - -- Otherwise the library graph contains a circularity without the - -- extra information provided by the invocation graph. Diagnose - -- the circularity. - - else - Diagnose_Circularities - (Inv_Graph => Dyn_Inv_Graph, - Lib_Graph => Dyn_Lib_Graph); - end if; - - Destroy (Dyn_Inv_Graph); - Destroy (Dyn_Lib_Graph); - end if; - - Destroy (Mix_Inv_Graph); - Destroy (Mix_Lib_Graph); - - -- Halt the bind as there is no satisfactory elaboration order - - if Status /= Order_OK then - raise Unrecoverable_Error; - end if; - end Elaborate_Units_Dynamic; + Write_Dependencies (Lib_Graph); - ---------------------------- - -- Elaborate_Units_Static -- - ---------------------------- + -- Output the elaboration order when switch -l (output chosen + -- elaboration order) is in effect. - procedure Elaborate_Units_Static (Order : out Unit_Id_Table) is - Inv_Graph : Invocation_Graph; - Lib_Graph : Library_Graph; - Status : Elaboration_Order_Status; + Write_Elaboration_Order (Order); - begin - -- Attempt to elaborate the units in the library graph by mixing in - -- the information from the invocation graph. This assumes that all - -- invocations will take place at elaboration time. - - Elaborate_Units_Common - (Use_Inv_Graph => True, - Is_Dyn_Elab => False, - Inv_Graph => Inv_Graph, - Lib_Graph => Lib_Graph, - Order => Order, - Status => Status); - - -- The elaboration order is satisfactory. Output the dependencies of - -- vertices when switch -e (output complete list of elaboration order - -- dependencies) is active. + -- Output the sources referenced in the closure of the order when + -- switch -R (list sources referenced in closure) is in effect. - if Status = Order_OK then - Write_Dependencies (Lib_Graph); + Write_Unit_Closure (Order); - -- Otherwise the augmented library graph contains a circularity + -- Otherwise the library graph contains at least one circularity else - Diagnose_Circularities - (Inv_Graph => Inv_Graph, - Lib_Graph => Lib_Graph); + Diagnose_Circularities (Inv_Graph, Lib_Graph); end if; Destroy (Inv_Graph); Destroy (Lib_Graph); - -- Halt the bind as there is no satisfactory elaboration order + -- Destroy all unit-related data structures + + Finalize_Units; + + -- Halt the bind when there is no satisfactory elaboration order if Status /= Order_OK then raise Unrecoverable_Error; end if; - end Elaborate_Units_Static; + end Elaborate_Units; ---------------------- -- Elaborate_Vertex -- ---------------------- procedure Elaborate_Vertex - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - All_Candidates : LGV_Sets.Membership_Set; - Comp_Candidates : LGV_Sets.Membership_Set; - Remaining_Vertices : in out Natural; - Order : in out Unit_Id_Table; - Step : Elaboration_Order_Step; - Indent : Indentation_Level) + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + All_Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Comp_Elaborable_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Order : in out Unit_Id_Table; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) is begin pragma Assert (Present (G)); pragma Assert (Present (Vertex)); pragma Assert (Needs_Elaboration (G, Vertex)); - pragma Assert (LGV_Sets.Present (All_Candidates)); - pragma Assert (LGV_Sets.Present (Comp_Candidates)); + pragma Assert (LGV_Sets.Present (All_Elaborable_Vertices)); + pragma Assert (LGV_Sets.Present (All_Waiting_Vertices)); + pragma Assert (LGV_Sets.Present (Comp_Elaborable_Vertices)); + pragma Assert (LGV_Sets.Present (Comp_Waiting_Vertices)); Trace_Vertex (G => G, @@ -885,14 +825,20 @@ package body Bindo.Elaborators is Step => Step, Indent => Indent); - -- Remove the vertex from both candidate sets. This is needed when + -- Remove the vertex from both elaborable sets. This is needed when -- the vertex is both an overall best candidate among all vertices, - -- and the best candidate within the component. There is no need to - -- check that the vertex is present in either set because the set - -- implementation handles this case. + -- and the best candidate within the component. + + LGV_Sets.Delete (All_Elaborable_Vertices, Vertex); + LGV_Sets.Delete (Comp_Elaborable_Vertices, Vertex); - LGV_Sets.Delete (All_Candidates, Vertex); - LGV_Sets.Delete (Comp_Candidates, Vertex); + -- Remove the vertex from both waiting sets. This is needed when a + -- weakly elaborable vertex is both an overall best candidate among + -- all waiting vertices and the best waiting candidate within the + -- component. + + LGV_Sets.Delete (All_Waiting_Vertices, Vertex); + LGV_Sets.Delete (Comp_Waiting_Vertices, Vertex); -- Mark the vertex as elaborated in order to prevent further attempts -- to re-elaborate it. @@ -903,202 +849,469 @@ package body Bindo.Elaborators is Unit_Id_Tables.Append (Order, Unit (G, Vertex)); - -- There is now one fewer vertex to elaborate - - Remaining_Vertices := Remaining_Vertices - 1; - -- Notify all successors and their components that they have one -- fewer predecessor to wait on. This may cause some successors to -- be included in one of the sets. Update_Successors - (G => G, - Pred => Vertex, - All_Candidates => All_Candidates, - Comp_Candidates => Comp_Candidates, - Step => Step, - Indent => Indent + Nested_Indentation); - - -- The vertex denotes a spec with a completing body, and is subject - -- to pragma Elaborate_Body. Elaborate the body in order to satisfy - -- the semantics of the pragma. - - if Is_Spec_With_Elaborate_Body (G, Vertex) then + (G => G, + Vertex => Vertex, + All_Elaborable_Vertices => All_Elaborable_Vertices, + All_Waiting_Vertices => All_Waiting_Vertices, + Comp_Elaborable_Vertices => Comp_Elaborable_Vertices, + Comp_Waiting_Vertices => Comp_Waiting_Vertices, + Step => Step, + Indent => Indent + Nested_Indentation); + + -- Elaborate an eligible completing body immediately after its spec. + -- This action satisfies the semantics of pragma Elaborate_Body. In + -- addition, it ensures that a body will not "drift" too far from its + -- spec in case invocation edges are removed from the library graph. + + if Has_Elaborable_Body (G, Vertex) then Elaborate_Vertex - (G => G, - Vertex => Proper_Body (G, Vertex), - All_Candidates => All_Candidates, - Comp_Candidates => Comp_Candidates, - Remaining_Vertices => Remaining_Vertices, - Order => Order, - Step => Step, - Indent => Indent); + (G => G, + Vertex => Proper_Body (G, Vertex), + All_Elaborable_Vertices => All_Elaborable_Vertices, + All_Waiting_Vertices => All_Waiting_Vertices, + Comp_Elaborable_Vertices => Comp_Elaborable_Vertices, + Comp_Waiting_Vertices => Comp_Waiting_Vertices, + Order => Order, + Step => Step, + Indent => Indent); end if; end Elaborate_Vertex; - ------------------------- - -- Find_Best_Candidate -- - ------------------------- + --------------------------------- + -- Find_Best_Elaborable_Vertex -- + --------------------------------- - function Find_Best_Candidate + function Find_Best_Elaborable_Vertex (G : Library_Graph; Set : LGV_Sets.Membership_Set; Step : Elaboration_Order_Step; Indent : Indentation_Level) return Library_Graph_Vertex_Id is - Best : Library_Graph_Vertex_Id; - Current : Library_Graph_Vertex_Id; - Iter : LGV_Sets.Iterator; + begin + pragma Assert (Present (G)); + pragma Assert (LGV_Sets.Present (Set)); + + return + Find_Best_Vertex + (G => G, + Set => Set, + Is_Suitable_Vertex => + Is_Suitable_Elaborable_Vertex'Access, + Compare_Vertices => + Is_Better_Elaborable_Vertex'Access, + Initial_Best_Msg => "initial best elaborable vertex", + Subsequent_Best_Msg => "better elaborable vertex", + Step => Step, + Indent => Indent); + end Find_Best_Elaborable_Vertex; + + ---------------------- + -- Find_Best_Vertex -- + ---------------------- + + function Find_Best_Vertex + (G : Library_Graph; + Set : LGV_Sets.Membership_Set; + Is_Suitable_Vertex : Predicate_Ptr; + Compare_Vertices : Comparator_Ptr; + Initial_Best_Msg : String; + Subsequent_Best_Msg : String; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) + return Library_Graph_Vertex_Id + is + Best_Vertex : Library_Graph_Vertex_Id; + Current_Vertex : Library_Graph_Vertex_Id; + Iter : LGV_Sets.Iterator; begin pragma Assert (Present (G)); pragma Assert (LGV_Sets.Present (Set)); + pragma Assert (Is_Suitable_Vertex /= null); + pragma Assert (Compare_Vertices /= null); -- Assume that there is no candidate - Best := No_Library_Graph_Vertex; + Best_Vertex := No_Library_Graph_Vertex; - -- Inspect all vertices in the set, looking for the best candidate to - -- elaborate. + -- Inspect all vertices in the set, looking for the best candidate + -- according to the comparator. Iter := LGV_Sets.Iterate (Set); while LGV_Sets.Has_Next (Iter) loop - LGV_Sets.Next (Iter, Current); - pragma Assert (Needs_Elaboration (G, Current)); + LGV_Sets.Next (Iter, Current_Vertex); + pragma Assert (Needs_Elaboration (G, Current_Vertex)); + + if Is_Suitable_Vertex.all (G, Current_Vertex) then + + -- A previous iteration already picked the best candidate. + -- Update the best candidate when the current vertex is a + -- better choice. + + if Present (Best_Vertex) then + if Compare_Vertices.all + (G => G, + Vertex => Current_Vertex, + Compared_To => Best_Vertex) = Higher_Precedence + then + Best_Vertex := Current_Vertex; + + Trace_Vertex + (G => G, + Vertex => Best_Vertex, + Msg => Subsequent_Best_Msg, + Step => Step, + Indent => Indent); + end if; + + -- Otherwise this is the first candidate + + else + Best_Vertex := Current_Vertex; + + Trace_Vertex + (G => G, + Vertex => Best_Vertex, + Msg => Initial_Best_Msg, + Step => Step, + Indent => Indent); + end if; + end if; + end loop; - -- Update the best candidate when there is no such candidate + return Best_Vertex; + end Find_Best_Vertex; - if not Present (Best) then - Best := Current; + ---------------------------------------- + -- Find_Best_Weakly_Elaborable_Vertex -- + ---------------------------------------- - Trace_Vertex - (G => G, - Vertex => Best, - Msg => "initial best candidate vertex", - Step => Step, - Indent => Indent); + function Find_Best_Weakly_Elaborable_Vertex + (G : Library_Graph; + Set : LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) return Library_Graph_Vertex_Id + is + begin + pragma Assert (Present (G)); + pragma Assert (LGV_Sets.Present (Set)); - -- Update the best candidate when the current vertex is a better - -- choice. + return + Find_Best_Vertex + (G => G, + Set => Set, + Is_Suitable_Vertex => + Is_Suitable_Weakly_Elaborable_Vertex'Access, + Compare_Vertices => + Is_Better_Weakly_Elaborable_Vertex'Access, + Initial_Best_Msg => "initial best weakly elaborable vertex", + Subsequent_Best_Msg => "better weakly elaborable vertex", + Step => Step, + Indent => Indent); + end Find_Best_Weakly_Elaborable_Vertex; - elsif Is_Better_Candidate - (G => G, - Best_Candidate => Best, - New_Candidate => Current) - then - Best := Current; + ------------------------- + -- Has_Elaborable_Body -- + ------------------------- - Trace_Vertex - (G => G, - Vertex => Best, - Msg => "best candidate vertex", - Step => Step, - Indent => Indent); - end if; - end loop; + function Has_Elaborable_Body + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean + is + begin + pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); - return Best; - end Find_Best_Candidate; + -- The body of an already-elaborated spec subject to Elaborate_Body + -- is always elaborable. - ------------------------- - -- Is_Better_Candidate -- - ------------------------- + if Is_Spec_With_Elaborate_Body (G, Vertex) then + return True; + + elsif Is_Spec_With_Body (G, Vertex) then + return Is_Elaborable_Vertex (G, Proper_Body (G, Vertex)); + end if; + + return False; + end Has_Elaborable_Body; + + --------------------------------- + -- Insert_Elaborable_Successor -- + --------------------------------- + + procedure Insert_Elaborable_Successor + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Msg : String; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) + is + pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); + pragma Assert (LGV_Sets.Present (Elaborable_Vertices)); + pragma Assert (LGV_Sets.Present (All_Waiting_Vertices)); + pragma Assert (LGV_Sets.Present (Comp_Waiting_Vertices)); + + Complement : constant Library_Graph_Vertex_Id := + Complementary_Vertex + (G => G, + Vertex => Vertex, + Force_Complement => False); + + begin + -- Remove the successor from both waiting vertex sets because it may + -- be the best vertex to elaborate across the whole graph and within + -- its component. + + LGV_Sets.Delete (All_Waiting_Vertices, Vertex); + LGV_Sets.Delete (Comp_Waiting_Vertices, Vertex); + + Insert_Vertex + (G => G, + Vertex => Vertex, + Set => Elaborable_Vertices, + Msg => Msg, + Step => Step, + Indent => Indent); + + if Present (Complement) then + + -- Remove the complement of the successor from both waiting vertex + -- sets because it may be the best vertex to elaborate across the + -- whole graph and within its component. + + LGV_Sets.Delete (All_Waiting_Vertices, Complement); + LGV_Sets.Delete (Comp_Waiting_Vertices, Complement); + + Insert_Vertex + (G => G, + Vertex => Complement, + Set => Elaborable_Vertices, + Msg => Msg, + Step => Step, + Indent => Indent); + end if; + end Insert_Elaborable_Successor; + + ------------------- + -- Insert_Vertex -- + ------------------- + + procedure Insert_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Set : LGV_Sets.Membership_Set; + Msg : String; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) + is + begin + pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); + pragma Assert (Needs_Elaboration (G, Vertex)); + pragma Assert (LGV_Sets.Present (Set)); + + -- Nothing to do when the vertex is already present in the set - function Is_Better_Candidate - (G : Library_Graph; - Best_Candidate : Library_Graph_Vertex_Id; - New_Candidate : Library_Graph_Vertex_Id) return Boolean + if LGV_Sets.Contains (Set, Vertex) then + return; + end if; + + Trace_Vertex + (G => G, + Vertex => Vertex, + Msg => Msg, + Step => Step, + Indent => Indent); + + -- Add the vertex to the set + + LGV_Sets.Insert (Set, Vertex); + end Insert_Vertex; + + --------------------------------- + -- Is_Better_Elaborable_Vertex -- + --------------------------------- + + function Is_Better_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind is begin pragma Assert (Present (G)); - pragma Assert (Present (Best_Candidate)); - pragma Assert (Present (New_Candidate)); + pragma Assert (Present (Vertex)); + pragma Assert (Present (Compared_To)); + + -- Prefer a spec with Elaborate_Body over its corresponding body + + if Is_Elaborate_Body_Pair + (G => G, + Spec_Vertex => Vertex, + Body_Vertex => Compared_To) + then + return Higher_Precedence; + + elsif Is_Elaborate_Body_Pair + (G => G, + Spec_Vertex => Compared_To, + Body_Vertex => Vertex) + then + return Lower_Precedence; -- Prefer a predefined unit over a non-predefined unit - if Is_Predefined_Unit (G, Best_Candidate) - and then not Is_Predefined_Unit (G, New_Candidate) + elsif Is_Predefined_Unit (G, Vertex) + and then not Is_Predefined_Unit (G, Compared_To) then - return False; + return Higher_Precedence; - elsif not Is_Predefined_Unit (G, Best_Candidate) - and then Is_Predefined_Unit (G, New_Candidate) + elsif not Is_Predefined_Unit (G, Vertex) + and then Is_Predefined_Unit (G, Compared_To) then - return True; + return Lower_Precedence; - -- Prefer an internal unit over a non-iternal unit + -- Prefer an internal unit over a non-internal unit - elsif Is_Internal_Unit (G, Best_Candidate) - and then not Is_Internal_Unit (G, New_Candidate) + elsif Is_Internal_Unit (G, Vertex) + and then not Is_Internal_Unit (G, Compared_To) then - return False; + return Higher_Precedence; - elsif not Is_Internal_Unit (G, Best_Candidate) - and then Is_Internal_Unit (G, New_Candidate) + elsif not Is_Internal_Unit (G, Vertex) + and then Is_Internal_Unit (G, Compared_To) then - return True; + return Lower_Precedence; -- Prefer a preelaborated unit over a non-preelaborated unit - elsif Is_Preelaborated_Unit (G, Best_Candidate) - and then not Is_Preelaborated_Unit (G, New_Candidate) + elsif Is_Preelaborated_Unit (G, Vertex) + and then not Is_Preelaborated_Unit (G, Compared_To) then - return False; + return Higher_Precedence; - elsif not Is_Preelaborated_Unit (G, Best_Candidate) - and then Is_Preelaborated_Unit (G, New_Candidate) + elsif not Is_Preelaborated_Unit (G, Vertex) + and then Is_Preelaborated_Unit (G, Compared_To) then - return True; + return Lower_Precedence; -- Otherwise default to lexicographical order to ensure deterministic -- behavior. + elsif Uname_Less (Name (G, Vertex), Name (G, Compared_To)) then + return Higher_Precedence; + else - return - Uname_Less (Name (G, Best_Candidate), Name (G, New_Candidate)); + return Lower_Precedence; end if; - end Is_Better_Candidate; + end Is_Better_Elaborable_Vertex; - ------------------------------ - -- Trace_Candidate_Vertices -- - ------------------------------ + ---------------------------------------- + -- Is_Better_Weakly_Elaborable_Vertex -- + ---------------------------------------- - procedure Trace_Candidate_Vertices - (G : Library_Graph; - Set : LGV_Sets.Membership_Set; - Step : Elaboration_Order_Step) + function Is_Better_Weakly_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Compared_To : Library_Graph_Vertex_Id) return Precedence_Kind is - Iter : LGV_Sets.Iterator; - Vertex : Library_Graph_Vertex_Id; + Comp_Strong_Preds : Natural; + Comp_Weak_Preds : Natural; + Vertex_Strong_Preds : Natural; + Vertex_Weak_Preds : Natural; begin pragma Assert (Present (G)); - pragma Assert (LGV_Sets.Present (Set)); + pragma Assert (Present (Vertex)); + pragma Assert (Present (Compared_To)); - -- Nothing to do when switch -d_T (output elaboration order and cycle - -- detection trace information) is not in effect. + -- Obtain the number of pending predecessors for both candidates, + -- taking into account Elaborate_Body pairs. - if not Debug_Flag_Underscore_TT then - return; + Pending_Predecessors_For_Elaboration + (G => G, + Vertex => Vertex, + Strong_Preds => Vertex_Strong_Preds, + Weak_Preds => Vertex_Weak_Preds); + + Pending_Predecessors_For_Elaboration + (G => G, + Vertex => Compared_To, + Strong_Preds => Comp_Strong_Preds, + Weak_Preds => Comp_Weak_Preds); + + -- Neither candidate should be waiting on strong predecessors, + -- otherwise the candidate cannot be weakly elaborated. + + pragma Assert (Vertex_Strong_Preds = 0); + pragma Assert (Comp_Strong_Preds = 0); + + -- Prefer a unit with fewer weak predecessors over a unit with more + -- weak predecessors. + + if Vertex_Weak_Preds < Comp_Weak_Preds then + return Higher_Precedence; + + elsif Vertex_Weak_Preds > Comp_Weak_Preds then + return Lower_Precedence; + + -- Otherwise default to lexicographical order to ensure deterministic + -- behavior. + + elsif Uname_Less (Name (G, Vertex), Name (G, Compared_To)) then + return Higher_Precedence; + + else + return Lower_Precedence; end if; + end Is_Better_Weakly_Elaborable_Vertex; - Trace_Step (Step); - Write_Str ("candidate vertices: "); - Write_Int (Int (LGV_Sets.Size (Set))); - Write_Eol; + ----------------------------------- + -- Is_Suitable_Elaborable_Vertex -- + ----------------------------------- - Iter := LGV_Sets.Iterate (Set); - while LGV_Sets.Has_Next (Iter) loop - LGV_Sets.Next (Iter, Vertex); + function Is_Suitable_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean + is + begin + pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); - Trace_Vertex - (G => G, - Vertex => Vertex, - Msg => "candidate vertex", - Step => Step, - Indent => Nested_Indentation); - end loop; - end Trace_Candidate_Vertices; + -- A vertex is suitable for elaboration as long it is not waiting on + -- any predecessors, ignoring the static or dynamic model. + + return Is_Elaborable_Vertex (G, Vertex); + end Is_Suitable_Elaborable_Vertex; + + ------------------------------------------ + -- Is_Suitable_Weakly_Elaborable_Vertex -- + ------------------------------------------ + + function Is_Suitable_Weakly_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean + is + begin + pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); + + -- A vertex is suitable for weak elaboration when it is waiting on + -- weak predecessors only, and the unit it represents was compiled + -- using the dynamic model. + + return + Is_Dynamically_Elaborated (G, Vertex) + and then Is_Weakly_Elaborable_Vertex (G, Vertex); + end Is_Suitable_Weakly_Elaborable_Vertex; --------------------- -- Trace_Component -- @@ -1130,8 +1343,14 @@ package body Bindo.Elaborators is Trace_Step (Step); Indent_By (Nested_Indentation); - Write_Str ("pending predecessors: "); - Write_Num (Int (Pending_Predecessors (G, Comp))); + Write_Str ("pending strong predecessors: "); + Write_Num (Int (Pending_Strong_Predecessors (G, Comp))); + Write_Eol; + + Trace_Step (Step); + Indent_By (Nested_Indentation); + Write_Str ("pending weak predecessors : "); + Write_Num (Int (Pending_Weak_Predecessors (G, Comp))); Write_Eol; end Trace_Component; @@ -1154,50 +1373,6 @@ package body Bindo.Elaborators is Write_Str (": "); end Trace_Step; - --------------------------------- - -- Trace_Unelaborated_Vertices -- - --------------------------------- - - procedure Trace_Unelaborated_Vertices - (G : Library_Graph; - Count : Natural; - Step : Elaboration_Order_Step) - is - Iter : Library_Graphs.All_Vertex_Iterator; - Vertex : Library_Graph_Vertex_Id; - - begin - pragma Assert (Present (G)); - - -- Nothing to do when switch -d_T (output elaboration order and cycle - -- detection trace information) is not in effect. - - if not Debug_Flag_Underscore_TT then - return; - end if; - - Trace_Step (Step); - Write_Str ("remaining unelaborated vertices: "); - Write_Int (Int (Count)); - Write_Eol; - - Iter := Iterate_All_Vertices (G); - while Has_Next (Iter) loop - Next (Iter, Vertex); - - if Needs_Elaboration (G, Vertex) - and then not In_Elaboration_Order (G, Vertex) - then - Trace_Vertex - (G => G, - Vertex => Vertex, - Msg => "remaining vertex", - Step => Step, - Indent => Nested_Indentation); - end if; - end loop; - end Trace_Unelaborated_Vertices; - ------------------ -- Trace_Vertex -- ------------------ @@ -1247,37 +1422,104 @@ package body Bindo.Elaborators is Trace_Step (Step); Indent_By (Attr_Indent); - Write_Str ("pending predecessors: "); - Write_Num (Int (Pending_Predecessors (G, Vertex))); + Write_Str ("pending strong predecessors: "); + Write_Num (Int (Pending_Strong_Predecessors (G, Vertex))); + Write_Eol; + + Trace_Step (Step); + Indent_By (Attr_Indent); + Write_Str ("pending weak predecessors : "); + Write_Num (Int (Pending_Weak_Predecessors (G, Vertex))); Write_Eol; Trace_Step (Step); Indent_By (Attr_Indent); - Write_Str ("pending components : "); - Write_Num (Int (Pending_Predecessors (G, Comp))); + Write_Str ("pending strong components : "); + Write_Num (Int (Pending_Strong_Predecessors (G, Comp))); + Write_Eol; + + Trace_Step (Step); + Indent_By (Attr_Indent); + Write_Str ("pending weak components : "); + Write_Num (Int (Pending_Weak_Predecessors (G, Comp))); Write_Eol; end Trace_Vertex; + -------------------- + -- Trace_Vertices -- + -------------------- + + procedure Trace_Vertices + (G : Library_Graph; + Set : LGV_Sets.Membership_Set; + Set_Msg : String; + Vertex_Msg : String; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) + is + Vertex_Indent : constant Indentation_Level := + Indent + Nested_Indentation; + + Iter : LGV_Sets.Iterator; + Vertex : Library_Graph_Vertex_Id; + + begin + pragma Assert (Present (G)); + pragma Assert (LGV_Sets.Present (Set)); + + -- Nothing to do when switch -d_T (output elaboration order and cycle + -- detection trace information) is not in effect. + + if not Debug_Flag_Underscore_TT then + return; + end if; + + Trace_Step (Step); + Indent_By (Indent); + Write_Str (Set_Msg); + Write_Str (": "); + Write_Int (Int (LGV_Sets.Size (Set))); + Write_Eol; + + Iter := LGV_Sets.Iterate (Set); + while LGV_Sets.Has_Next (Iter) loop + LGV_Sets.Next (Iter, Vertex); + + Trace_Vertex + (G => G, + Vertex => Vertex, + Msg => Vertex_Msg, + Step => Step, + Indent => Vertex_Indent); + end loop; + end Trace_Vertices; + ---------------------- -- Update_Successor -- ---------------------- procedure Update_Successor - (G : Library_Graph; - Pred : Library_Graph_Vertex_Id; - Succ : Library_Graph_Vertex_Id; - All_Candidates : LGV_Sets.Membership_Set; - Comp_Candidates : LGV_Sets.Membership_Set; - Step : Elaboration_Order_Step; - Indent : Indentation_Level) + (G : Library_Graph; + Edge : Library_Graph_Edge_Id; + All_Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Comp_Elaborable_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) is pragma Assert (Present (G)); - pragma Assert (Present (Pred)); + pragma Assert (Present (Edge)); + pragma Assert (LGV_Sets.Present (All_Elaborable_Vertices)); + pragma Assert (LGV_Sets.Present (All_Waiting_Vertices)); + pragma Assert (LGV_Sets.Present (Comp_Elaborable_Vertices)); + pragma Assert (LGV_Sets.Present (Comp_Waiting_Vertices)); + + Pred : constant Library_Graph_Vertex_Id := Predecessor (G, Edge); + Succ : constant Library_Graph_Vertex_Id := Successor (G, Edge); + pragma Assert (Needs_Elaboration (G, Pred)); - pragma Assert (Present (Succ)); pragma Assert (Needs_Elaboration (G, Succ)); - pragma Assert (LGV_Sets.Present (All_Candidates)); - pragma Assert (LGV_Sets.Present (Comp_Candidates)); In_Different_Components : constant Boolean := not In_Same_Component @@ -1289,10 +1531,8 @@ package body Bindo.Elaborators is Vertex_Indent : constant Indentation_Level := Indent + Nested_Indentation; - Candidate : Library_Graph_Vertex_Id; - Iter : Component_Vertex_Iterator; - Msg : String_Ptr; - Set : LGV_Sets.Membership_Set; + Iter : Component_Vertex_Iterator; + Vertex : Library_Graph_Vertex_Id; begin Trace_Vertex @@ -1305,45 +1545,61 @@ package body Bindo.Elaborators is -- Notify the successor that it has one less predecessor to wait on. -- This effectively eliminates the edge that links the two. - Decrement_Pending_Predecessors (G, Succ); + Decrement_Pending_Predecessors + (G => G, + Vertex => Succ, + Edge => Edge); -- The predecessor and successor reside in different components. -- Notify the successor component it has one fewer components to -- wait on. if In_Different_Components then - Decrement_Pending_Predecessors (G, Succ_Comp); + Decrement_Pending_Predecessors + (G => G, + Comp => Succ_Comp, + Edge => Edge); end if; -- At this point the successor may become elaborable when its final - -- predecessor or final predecessor component is elaborated. - - -- The predecessor and successor reside in different components. - -- The successor must not be added to the candidates of Pred's - -- component because this will mix units from the two components. - -- Instead, the successor is added to the set of all candidates - -- that must be elaborated. + -- predecessor or final predecessor component has been elaborated. + + if Is_Elaborable_Vertex (G, Succ) then + + -- The predecessor and successor reside in different components. + -- The successor must not be added to the candidates of Pred's + -- component because this will mix units from the two components. + -- Instead, the successor is added to the set of all elaborable + -- vertices. + + if In_Different_Components then + Insert_Elaborable_Successor + (G => G, + Vertex => Succ, + Elaborable_Vertices => All_Elaborable_Vertices, + All_Waiting_Vertices => All_Waiting_Vertices, + Comp_Waiting_Vertices => Comp_Waiting_Vertices, + Msg => "add elaborable successor", + Step => Step, + Indent => Vertex_Indent); + + -- Otherwise the predecessor and successor reside within the same + -- component. Pred's component gains another elaborable vertex. - if In_Different_Components then - Msg := Add_To_All_Candidates_Msg'Access; - Set := All_Candidates; - - -- Otherwise the predecessor and successor reside within the same - -- component. Pred's component gains another elaborable node. - - else - Msg := Add_To_Comp_Candidates_Msg'Access; - Set := Comp_Candidates; + else + Insert_Elaborable_Successor + (G => G, + Vertex => Succ, + Elaborable_Vertices => Comp_Elaborable_Vertices, + All_Waiting_Vertices => All_Waiting_Vertices, + Comp_Waiting_Vertices => Comp_Waiting_Vertices, + Msg => + "add elaborable component successor", + Step => Step, + Indent => Vertex_Indent); + end if; end if; - Add_Vertex_If_Elaborable - (G => G, - Vertex => Succ, - Set => Set, - Msg => Msg.all, - Step => Step, - Indent => Vertex_Indent); - -- At this point the successor component may become elaborable when -- its final predecessor component is elaborated. This in turn may -- allow vertices of the successor component to be elaborated. @@ -1353,15 +1609,19 @@ package body Bindo.Elaborators is then Iter := Iterate_Component_Vertices (G, Succ_Comp); while Has_Next (Iter) loop - Next (Iter, Candidate); - - Add_Vertex_If_Elaborable - (G => G, - Vertex => Candidate, - Set => All_Candidates, - Msg => Add_To_All_Candidates_Msg, - Step => Step, - Indent => Vertex_Indent); + Next (Iter, Vertex); + + if Is_Elaborable_Vertex (G, Vertex) then + Insert_Elaborable_Successor + (G => G, + Vertex => Vertex, + Elaborable_Vertices => All_Elaborable_Vertices, + All_Waiting_Vertices => All_Waiting_Vertices, + Comp_Waiting_Vertices => Comp_Waiting_Vertices, + Msg => "add elaborable vertex", + Step => Step, + Indent => Vertex_Indent); + end if; end loop; end if; end Update_Successor; @@ -1371,36 +1631,41 @@ package body Bindo.Elaborators is ----------------------- procedure Update_Successors - (G : Library_Graph; - Pred : Library_Graph_Vertex_Id; - All_Candidates : LGV_Sets.Membership_Set; - Comp_Candidates : LGV_Sets.Membership_Set; - Step : Elaboration_Order_Step; - Indent : Indentation_Level) + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + All_Elaborable_Vertices : LGV_Sets.Membership_Set; + All_Waiting_Vertices : LGV_Sets.Membership_Set; + Comp_Elaborable_Vertices : LGV_Sets.Membership_Set; + Comp_Waiting_Vertices : LGV_Sets.Membership_Set; + Step : Elaboration_Order_Step; + Indent : Indentation_Level) is Edge : Library_Graph_Edge_Id; Iter : Edges_To_Successors_Iterator; begin pragma Assert (Present (G)); - pragma Assert (Present (Pred)); - pragma Assert (Needs_Elaboration (G, Pred)); - pragma Assert (LGV_Sets.Present (All_Candidates)); - pragma Assert (LGV_Sets.Present (Comp_Candidates)); + pragma Assert (Present (Vertex)); + pragma Assert (Needs_Elaboration (G, Vertex)); + pragma Assert (LGV_Sets.Present (All_Elaborable_Vertices)); + pragma Assert (LGV_Sets.Present (All_Waiting_Vertices)); + pragma Assert (LGV_Sets.Present (Comp_Elaborable_Vertices)); + pragma Assert (LGV_Sets.Present (Comp_Waiting_Vertices)); - Iter := Iterate_Edges_To_Successors (G, Pred); + Iter := Iterate_Edges_To_Successors (G, Vertex); while Has_Next (Iter) loop Next (Iter, Edge); - pragma Assert (Predecessor (G, Edge) = Pred); + pragma Assert (Predecessor (G, Edge) = Vertex); Update_Successor - (G => G, - Pred => Pred, - Succ => Successor (G, Edge), - All_Candidates => All_Candidates, - Comp_Candidates => Comp_Candidates, - Step => Step, - Indent => Indent); + (G => G, + Edge => Edge, + All_Elaborable_Vertices => All_Elaborable_Vertices, + All_Waiting_Vertices => All_Waiting_Vertices, + Comp_Elaborable_Vertices => Comp_Elaborable_Vertices, + Comp_Waiting_Vertices => Comp_Waiting_Vertices, + Step => Step, + Indent => Indent); end loop; end Update_Successors; end Invocation_And_Library_Graph_Elaborators; diff --git a/gcc/ada/bindo-graphs.adb b/gcc/ada/bindo-graphs.adb index c68e367..387d969 100644 --- a/gcc/ada/bindo-graphs.adb +++ b/gcc/ada/bindo-graphs.adb @@ -205,7 +205,7 @@ package body Bindo.Graphs is (G : Invocation_Graph; Rel : Source_Target_Relation) return Boolean; pragma Inline (Is_Existing_Source_Target_Relation); - -- Determine whether a source vertex and a target vertex desctibed by + -- Determine whether a source vertex and a target vertex described by -- relation Rel are already related in invocation graph G. procedure Save_Elaboration_Root @@ -226,7 +226,7 @@ package body Bindo.Graphs is Rel : Source_Target_Relation; Val : Boolean := True); pragma Inline (Set_Is_Existing_Source_Target_Relation); - -- Mark a source vertex and a target vertex desctibed by relation Rel as + -- Mark a source vertex and a target vertex described by relation Rel as -- already related in invocation graph G depending on value Val. procedure Set_IGE_Attributes @@ -1026,18 +1026,6 @@ package body Bindo.Graphs is package body Library_Graphs is - ----------- - -- Types -- - ----------- - - -- The following type represents the various kinds of precedence between - -- two items. - - type Precedence_Kind is - (Lower_Precedence, - Equal_Precedence, - Higher_Precedence); - ----------------------- -- Local subprograms -- ----------------------- @@ -1064,7 +1052,7 @@ package body Bindo.Graphs is Attrs : Library_Graph_Cycle_Attributes; Indent : Indentation_Level); pragma Inline (Add_Cycle); - -- Store a cycle described by attribytes Attrs in library graph G, + -- Store a cycle described by attributes Attrs in library graph G, -- unless a prior rotation of it already exists. The edges of the cycle -- must be in normalized form. Indent is the desired indentation level -- for tracing. @@ -1090,15 +1078,6 @@ package body Bindo.Graphs is -- part of an Elaborate_Body pair, or flag Do_Complement is set, add -- the complementary vertex to the set. - function Complementary_Vertex - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - Do_Complement : Boolean) return Library_Graph_Vertex_Id; - pragma Inline (Complementary_Vertex); - -- If vertex Vertex of library graph G is part of an Elaborate_Body - -- pair, or flag Do_Complement is set, return the spec when Vertex is - -- a body, the body when Vertex is a spec, or No_Library_Graph_Vertex. - function Copy_Cycle_Path (Cycle_Path : LGE_Lists.Doubly_Linked_List) return LGE_Lists.Doubly_Linked_List; @@ -1228,17 +1207,21 @@ package body Bindo.Graphs is procedure Increment_Pending_Predecessors (G : Library_Graph; - Comp : Component_Id); + Comp : Component_Id; + Edge : Library_Graph_Edge_Id); pragma Inline (Increment_Pending_Predecessors); - -- Increment the number of pending precedessors component Comp of - -- library graph G must wait on before it can be elaborated by one. + -- Increment the number of pending predecessors component Comp which was + -- reached via edge Edge of library graph G must wait on before it can + -- be elaborated by one. procedure Increment_Pending_Predecessors (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id); + Vertex : Library_Graph_Vertex_Id; + Edge : Library_Graph_Edge_Id); pragma Inline (Increment_Pending_Predecessors); - -- Increment the number of pending precedessors vertex Vertex of library - -- graph G must wait on before it can be elaborated by one. + -- Increment the number of pending predecessors vertex Vertex which was + -- reached via edge Edge of library graph G must wait on before it can + -- be elaborated by one. procedure Initialize_Components (G : Library_Graph); pragma Inline (Initialize_Components); @@ -1306,22 +1289,14 @@ package body Bindo.Graphs is Edge : Library_Graph_Edge_Id) return Boolean; pragma Inline (Is_Cyclic_With_Edge); -- Determine whether edge Edge of library graph G participates in a - -- cycle and is the result of awith dependency between its successor + -- cycle and is the result of a with dependency between its successor -- and predecessor. - function Is_Elaborable_Vertex - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - Predecessors : Natural) return Boolean; - pragma Inline (Is_Elaborable_Vertex); - -- Determine whether vertex Vertex of library graph G can be elaborated - -- given that it meets number of predecessors Predecessors. - function Is_Recorded_Cycle (G : Library_Graph; Attrs : Library_Graph_Cycle_Attributes) return Boolean; pragma Inline (Is_Recorded_Cycle); - -- Determine whether a cycle desctibed by its attributes Attrs has + -- Determine whether a cycle described by its attributes Attrs has -- has already been recorded in library graph G. function Is_Recorded_Edge @@ -1329,7 +1304,7 @@ package body Bindo.Graphs is Rel : Predecessor_Successor_Relation) return Boolean; pragma Inline (Is_Recorded_Edge); -- Determine whether a predecessor vertex and a successor vertex - -- desctibed by relation Rel are already linked in library graph G. + -- described by relation Rel are already linked in library graph G. function Links_Vertices_In_Same_Component (G : Library_Graph; @@ -1441,7 +1416,7 @@ package body Bindo.Graphs is Rel : Predecessor_Successor_Relation; Val : Boolean := True); pragma Inline (Set_Is_Recorded_Edge); - -- Mark a predecessor vertex and a successor vertex desctibed by + -- Mark a predecessor vertex and a successor vertex described by -- relation Rel as already linked depending on value Val. procedure Set_LGC_Attributes @@ -1493,6 +1468,16 @@ package body Bindo.Graphs is -- Write the contents of vertex Vertex of library graph G to standard -- output. Indent is the desired indentation level for tracing. + procedure Update_Pending_Predecessors + (Strong_Predecessors : in out Natural; + Weak_Predecessors : in out Natural; + Update_Weak : Boolean; + Value : Integer); + pragma Inline (Update_Pending_Predecessors); + -- Update the number of pending strong or weak predecessors denoted by + -- Strong_Predecessors and Weak_Predecessors respectively depending on + -- flag Update_Weak by adding value Value. + procedure Update_Pending_Predecessors_Of_Components (G : Library_Graph); pragma Inline (Update_Pending_Predecessors_Of_Components); -- Update the number of pending predecessors all components of library @@ -1523,7 +1508,7 @@ package body Bindo.Graphs is pragma Assert (LGE_Lists.Present (Edges)); -- A vertex requires a special Body_Before_Spec edge to its - -- Corresponging_Item when it either denotes a + -- Corresponding_Item when it either denotes a -- -- * Body that completes a previous spec -- @@ -1717,7 +1702,10 @@ package body Bindo.Graphs is -- Update the number of pending predecessors the successor must wait -- on before it is elaborated. - Increment_Pending_Predecessors (G, Succ); + Increment_Pending_Predecessors + (G => G, + Vertex => Succ, + Edge => Edge); -- Update the edge statistics @@ -1757,10 +1745,12 @@ package body Bindo.Graphs is Set_LGV_Attributes (G => G, Vertex => Vertex, - Val => (Corresponding_Item => No_Library_Graph_Vertex, - In_Elaboration_Order => False, - Pending_Predecessors => 0, - Unit => U_Id)); + Val => + (Corresponding_Item => No_Library_Graph_Vertex, + In_Elaboration_Order => False, + Pending_Strong_Predecessors => 0, + Pending_Weak_Predecessors => 0, + Unit => U_Id)); -- Associate the unit with its corresponding vertex @@ -1783,9 +1773,9 @@ package body Bindo.Graphs is Complement : constant Library_Graph_Vertex_Id := Complementary_Vertex - (G => G, - Vertex => Vertex, - Do_Complement => Do_Complement); + (G => G, + Vertex => Vertex, + Force_Complement => Do_Complement); begin LGV_Sets.Insert (Set, Vertex); @@ -1800,9 +1790,9 @@ package body Bindo.Graphs is -------------------------- function Complementary_Vertex - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - Do_Complement : Boolean) return Library_Graph_Vertex_Id + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Force_Complement : Boolean) return Library_Graph_Vertex_Id is Complement : Library_Graph_Vertex_Id; @@ -1816,7 +1806,7 @@ package body Bindo.Graphs is -- The caller requests the complement explicitly - if Do_Complement then + if Force_Complement then Complement := Corresponding_Item (G, Vertex); -- The vertex is a completing body of a spec subject to pragma @@ -1850,6 +1840,46 @@ package body Bindo.Graphs is return DG.Component (G.Graph, Vertex); end Component; + ------------------------------------ + -- Contains_Weak_Static_Successor -- + ------------------------------------ + + function Contains_Weak_Static_Successor + (G : Library_Graph; + Cycle : Library_Graph_Cycle_Id) return Boolean + is + Edge : Library_Graph_Edge_Id; + Iter : Edges_Of_Cycle_Iterator; + Seen : Boolean; + + begin + pragma Assert (Present (G)); + pragma Assert (Present (Cycle)); + + -- Assume that no weak static successor has been seen + + Seen := False; + + -- IMPORTANT: + -- + -- * The iteration must run to completion in order to unlock the + -- edges of the cycle. + + Iter := Iterate_Edges_Of_Cycle (G, Cycle); + while Has_Next (Iter) loop + Next (Iter, Edge); + + if not Seen + and then Is_Invocation_Edge (G, Edge) + and then not Is_Dynamically_Elaborated (G, Successor (G, Edge)) + then + Seen := True; + end if; + end loop; + + return Seen; + end Contains_Weak_Static_Successor; + --------------------- -- Copy_Cycle_Path -- --------------------- @@ -1911,15 +1941,12 @@ package body Bindo.Graphs is ------------ function Create - (Initial_Vertices : Positive; - Initial_Edges : Positive; - Dynamically_Elaborated : Boolean) return Library_Graph + (Initial_Vertices : Positive; + Initial_Edges : Positive) return Library_Graph is G : constant Library_Graph := new Library_Graph_Attributes; begin - G.Dynamically_Elaborated := Dynamically_Elaborated; - G.Component_Attributes := Component_Tables.Create (Initial_Vertices); G.Cycle_Attributes := LGC_Tables.Create (Initial_Vertices); G.Cycles := LGC_Lists.Create; @@ -1990,7 +2017,8 @@ package body Bindo.Graphs is procedure Decrement_Pending_Predecessors (G : Library_Graph; - Comp : Component_Id) + Comp : Component_Id; + Edge : Library_Graph_Edge_Id) is Attrs : Component_Attributes; @@ -1999,7 +2027,13 @@ package body Bindo.Graphs is pragma Assert (Present (Comp)); Attrs := Get_Component_Attributes (G, Comp); - Attrs.Pending_Predecessors := Attrs.Pending_Predecessors - 1; + + Update_Pending_Predecessors + (Strong_Predecessors => Attrs.Pending_Strong_Predecessors, + Weak_Predecessors => Attrs.Pending_Weak_Predecessors, + Update_Weak => Is_Invocation_Edge (G, Edge), + Value => -1); + Set_Component_Attributes (G, Comp, Attrs); end Decrement_Pending_Predecessors; @@ -2009,7 +2043,8 @@ package body Bindo.Graphs is procedure Decrement_Pending_Predecessors (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id) + Vertex : Library_Graph_Vertex_Id; + Edge : Library_Graph_Edge_Id) is Attrs : Library_Graph_Vertex_Attributes; @@ -2018,7 +2053,13 @@ package body Bindo.Graphs is pragma Assert (Present (Vertex)); Attrs := Get_LGV_Attributes (G, Vertex); - Attrs.Pending_Predecessors := Attrs.Pending_Predecessors - 1; + + Update_Pending_Predecessors + (Strong_Predecessors => Attrs.Pending_Strong_Predecessors, + Weak_Predecessors => Attrs.Pending_Weak_Predecessors, + Update_Weak => Is_Invocation_Edge (G, Edge), + Value => -1); + Set_LGV_Attributes (G, Vertex, Attrs); end Decrement_Pending_Predecessors; @@ -2071,7 +2112,10 @@ package body Bindo.Graphs is -- Update the number of pending predecessors the successor must wait -- on before it is elaborated. - Decrement_Pending_Predecessors (G, Succ); + Decrement_Pending_Predecessors + (G => G, + Vertex => Succ, + Edge => Edge); -- Delete the link between the predecessor and successor. This allows -- for further attempts to link the same predecessor and successor. @@ -2298,9 +2342,9 @@ package body Bindo.Graphs is (G => G, Vertex => Complementary_Vertex - (G => G, - Vertex => Vertex, - Do_Complement => Spec_And_Body_Together), + (G => G, + Vertex => Vertex, + Force_Complement => Spec_And_Body_Together), End_Vertices => End_Vertices, Most_Significant_Edge => Most_Significant_Edge, Invocation_Edge_Count => Invocation_Edge_Count, @@ -2343,7 +2387,7 @@ package body Bindo.Graphs is Trace_Edge (G, Initial_Edge, Indent); -- Use a set to represent the end vertices of the cycle. The set is - -- needed to accomodate the Elaborate_All and Elaborate_Body cases + -- needed to accommodate the Elaborate_All and Elaborate_Body cases -- where a cycle may terminate on either a spec or a body vertex. End_Vertices := LGV_Sets.Create (2); @@ -2650,7 +2694,10 @@ package body Bindo.Graphs is U_Rec : Unit_Record renames ALI.Units.Table (U_Id); begin - return U_Rec.Elaborate_Body; + -- Treat the spec and body as decoupled when switch -d_b (ignore the + -- effects of pragma Elaborate_Body) is in effect. + + return U_Rec.Elaborate_Body and not Debug_Flag_Underscore_B; end Has_Elaborate_Body; -------------- @@ -2884,7 +2931,8 @@ package body Bindo.Graphs is procedure Increment_Pending_Predecessors (G : Library_Graph; - Comp : Component_Id) + Comp : Component_Id; + Edge : Library_Graph_Edge_Id) is Attrs : Component_Attributes; @@ -2893,7 +2941,13 @@ package body Bindo.Graphs is pragma Assert (Present (Comp)); Attrs := Get_Component_Attributes (G, Comp); - Attrs.Pending_Predecessors := Attrs.Pending_Predecessors + 1; + + Update_Pending_Predecessors + (Strong_Predecessors => Attrs.Pending_Strong_Predecessors, + Weak_Predecessors => Attrs.Pending_Weak_Predecessors, + Update_Weak => Is_Invocation_Edge (G, Edge), + Value => 1); + Set_Component_Attributes (G, Comp, Attrs); end Increment_Pending_Predecessors; @@ -2903,7 +2957,8 @@ package body Bindo.Graphs is procedure Increment_Pending_Predecessors (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id) + Vertex : Library_Graph_Vertex_Id; + Edge : Library_Graph_Edge_Id) is Attrs : Library_Graph_Vertex_Attributes; @@ -2912,7 +2967,13 @@ package body Bindo.Graphs is pragma Assert (Present (Vertex)); Attrs := Get_LGV_Attributes (G, Vertex); - Attrs.Pending_Predecessors := Attrs.Pending_Predecessors + 1; + + Update_Pending_Predecessors + (Strong_Predecessors => Attrs.Pending_Strong_Predecessors, + Weak_Predecessors => Attrs.Pending_Weak_Predecessors, + Update_Weak => Is_Invocation_Edge (G, Edge), + Value => 1); + Set_LGV_Attributes (G, Vertex, Attrs); end Increment_Pending_Predecessors; @@ -2925,7 +2986,7 @@ package body Bindo.Graphs is pragma Assert (Present (G)); -- The graph already contains a set of components. Reinitialize - -- them in order to accomodate the new set of components about to + -- them in order to accommodate the new set of components about to -- be computed. if Number_Of_Components (G) > 0 then @@ -3216,11 +3277,15 @@ package body Bindo.Graphs is -- Is_Dynamically_Elaborated -- ------------------------------- - function Is_Dynamically_Elaborated (G : Library_Graph) return Boolean is + function Is_Dynamically_Elaborated + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean + is begin pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); - return G.Dynamically_Elaborated; + return Is_Dynamically_Elaborated (Unit (G, Vertex)); end Is_Dynamically_Elaborated; ----------------------------- @@ -3235,12 +3300,14 @@ package body Bindo.Graphs is pragma Assert (Present (G)); pragma Assert (Present (Comp)); - -- A component can be elaborated when + -- A component is elaborable when: -- - -- * The component is no longer wanting on any of its predecessors - -- to be elaborated. + -- * It is not waiting on strong predecessors, and + -- * It is not waiting on weak predecessors - return Pending_Predecessors (G, Comp) = 0; + return + Pending_Strong_Predecessors (G, Comp) = 0 + and then Pending_Weak_Predecessors (G, Comp) = 0; end Is_Elaborable_Component; -------------------------- @@ -3251,80 +3318,47 @@ package body Bindo.Graphs is (G : Library_Graph; Vertex : Library_Graph_Vertex_Id) return Boolean is - Check_Vertex : Library_Graph_Vertex_Id; - - begin pragma Assert (Present (G)); pragma Assert (Present (Vertex)); - Check_Vertex := Vertex; - - -- A spec-body pair where the spec carries pragma Elaborate_Body must - -- be treated as one vertex for elaboration purposes. Use the spec as - -- the point of reference for the composite vertex. - - if Is_Body_Of_Spec_With_Elaborate_Body (G, Check_Vertex) then - Check_Vertex := Proper_Spec (G, Check_Vertex); - end if; - - return - Is_Elaborable_Vertex - (G => G, - Vertex => Check_Vertex, - Predecessors => 0); - end Is_Elaborable_Vertex; - - -------------------------- - -- Is_Elaborable_Vertex -- - -------------------------- + Complement : constant Library_Graph_Vertex_Id := + Complementary_Vertex + (G => G, + Vertex => Vertex, + Force_Complement => False); - function Is_Elaborable_Vertex - (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id; - Predecessors : Natural) return Boolean - is - Body_Vertex : Library_Graph_Vertex_Id; + Strong_Preds : Natural; + Weak_Preds : Natural; begin - pragma Assert (Present (G)); - pragma Assert (Present (Vertex)); - - -- The vertex must not be re-elaborated once it has been elaborated + -- A vertex is elaborable when: + -- + -- * It has not been elaborated yet, and + -- * The complement vertex of an Elaborate_Body pair has not been + -- elaborated yet, and + -- * It resides within an elaborable component, and + -- * It is not waiting on strong predecessors, and + -- * It is not waiting on weak predecessors if In_Elaboration_Order (G, Vertex) then return False; - -- The vertex must not be waiting on more precedessors than requested - -- to be elaborated. - - elsif Pending_Predecessors (G, Vertex) /= Predecessors then + elsif Present (Complement) + and then In_Elaboration_Order (G, Complement) + then return False; - -- The component where the vertex resides must not be waiting on any - -- of its precedessors to be elaborated. - elsif not Is_Elaborable_Component (G, Component (G, Vertex)) then return False; - - -- The vertex denotes a spec with a completing body, and is subject - -- to pragma Elaborate_Body. The body must be elaborable for the - -- vertex to be elaborated. Account for the sole predecessor of the - -- body which is the vertex itself. - - elsif Is_Spec_With_Elaborate_Body (G, Vertex) then - Body_Vertex := Proper_Body (G, Vertex); - pragma Assert (Present (Body_Vertex)); - - return - Is_Elaborable_Vertex - (G => G, - Vertex => Body_Vertex, - Predecessors => 1); end if; - -- At this point it is known that the vertex can be elaborated + Pending_Predecessors_For_Elaboration + (G => G, + Vertex => Vertex, + Strong_Preds => Strong_Preds, + Weak_Preds => Weak_Preds); - return True; + return Strong_Preds = 0 and then Weak_Preds = 0; end Is_Elaborable_Vertex; --------------------------- @@ -3378,6 +3412,26 @@ package body Bindo.Graphs is return Kind (G, Edge) = Elaborate_Edge; end Is_Elaborate_Edge; + ---------------------------- + -- Is_Elaborate_Body_Pair -- + ---------------------------- + + function Is_Elaborate_Body_Pair + (G : Library_Graph; + Spec_Vertex : Library_Graph_Vertex_Id; + Body_Vertex : Library_Graph_Vertex_Id) return Boolean + is + begin + pragma Assert (Present (G)); + pragma Assert (Present (Spec_Vertex)); + pragma Assert (Present (Body_Vertex)); + + return + Is_Spec_With_Elaborate_Body (G, Spec_Vertex) + and then Is_Body_Of_Spec_With_Elaborate_Body (G, Body_Vertex) + and then Proper_Body (G, Spec_Vertex) = Body_Vertex; + end Is_Elaborate_Body_Pair; + -------------------- -- Is_Forced_Edge -- -------------------- @@ -3539,6 +3593,57 @@ package body Bindo.Graphs is and then Has_Elaborate_Body (G, Vertex); end Is_Spec_With_Elaborate_Body; + --------------------------------- + -- Is_Weakly_Elaborable_Vertex -- + ---------------------------------- + + function Is_Weakly_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean + is + pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); + + Complement : constant Library_Graph_Vertex_Id := + Complementary_Vertex + (G => G, + Vertex => Vertex, + Force_Complement => False); + + Strong_Preds : Natural; + Weak_Preds : Natural; + + begin + -- A vertex is weakly elaborable when: + -- + -- * It has not been elaborated yet, and + -- * The complement vertex of an Elaborate_Body pair has not been + -- elaborated yet, and + -- * It resides within an elaborable component, and + -- * It is not waiting on strong predecessors, and + -- * It is waiting on at least one weak predecessor + + if In_Elaboration_Order (G, Vertex) then + return False; + + elsif Present (Complement) + and then In_Elaboration_Order (G, Complement) + then + return False; + + elsif not Is_Elaborable_Component (G, Component (G, Vertex)) then + return False; + end if; + + Pending_Predecessors_For_Elaboration + (G => G, + Vertex => Vertex, + Strong_Preds => Strong_Preds, + Weak_Preds => Weak_Preds); + + return Strong_Preds = 0 and then Weak_Preds >= 1; + end Is_Weakly_Elaborable_Vertex; + ------------------ -- Is_With_Edge -- ------------------ @@ -4044,11 +4149,72 @@ package body Bindo.Graphs is return Get_LGC_Attributes (G, Cycle).Path; end Path; - -------------------------- - -- Pending_Predecessors -- - -------------------------- + ------------------------------------------ + -- Pending_Predecessors_For_Elaboration -- + ------------------------------------------ - function Pending_Predecessors + procedure Pending_Predecessors_For_Elaboration + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Strong_Preds : out Natural; + Weak_Preds : out Natural) + is + Complement : Library_Graph_Vertex_Id; + Spec_Vertex : Library_Graph_Vertex_Id; + Total_Strong_Preds : Natural; + Total_Weak_Preds : Natural; + + begin + pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); + + Total_Strong_Preds := Pending_Strong_Predecessors (G, Vertex); + Total_Weak_Preds := Pending_Weak_Predecessors (G, Vertex); + + -- Assume that there is no complementary vertex that needs to be + -- examined. + + Complement := No_Library_Graph_Vertex; + Spec_Vertex := No_Library_Graph_Vertex; + + if Is_Body_Of_Spec_With_Elaborate_Body (G, Vertex) then + Complement := Proper_Spec (G, Vertex); + Spec_Vertex := Complement; + + elsif Is_Spec_With_Elaborate_Body (G, Vertex) then + Complement := Proper_Body (G, Vertex); + Spec_Vertex := Vertex; + end if; + + -- The vertex is part of an Elaborate_Body pair. Take into account + -- the strong and weak predecessors of the complementary vertex. + + if Present (Complement) then + Total_Strong_Preds := + Pending_Strong_Predecessors (G, Complement) + Total_Strong_Preds; + Total_Weak_Preds := + Pending_Weak_Predecessors (G, Complement) + Total_Weak_Preds; + + -- The body of an Elaborate_Body pair is the successor of a strong + -- edge where the predecessor is the spec. This edge must not be + -- considered for elaboration purposes because the pair is treated + -- as one vertex. Account for the edge only when the spec has not + -- been elaborated yet. + + if not In_Elaboration_Order (G, Spec_Vertex) then + Total_Strong_Preds := Total_Strong_Preds - 1; + end if; + end if; + + Strong_Preds := Total_Strong_Preds; + Weak_Preds := Total_Weak_Preds; + end Pending_Predecessors_For_Elaboration; + + --------------------------------- + -- Pending_Strong_Predecessors -- + --------------------------------- + + function Pending_Strong_Predecessors (G : Library_Graph; Comp : Component_Id) return Natural is @@ -4056,14 +4222,14 @@ package body Bindo.Graphs is pragma Assert (Present (G)); pragma Assert (Present (Comp)); - return Get_Component_Attributes (G, Comp).Pending_Predecessors; - end Pending_Predecessors; + return Get_Component_Attributes (G, Comp).Pending_Strong_Predecessors; + end Pending_Strong_Predecessors; - -------------------------- - -- Pending_Predecessors -- - -------------------------- + --------------------------------- + -- Pending_Strong_Predecessors -- + --------------------------------- - function Pending_Predecessors + function Pending_Strong_Predecessors (G : Library_Graph; Vertex : Library_Graph_Vertex_Id) return Natural is @@ -4071,8 +4237,38 @@ package body Bindo.Graphs is pragma Assert (Present (G)); pragma Assert (Present (Vertex)); - return Get_LGV_Attributes (G, Vertex).Pending_Predecessors; - end Pending_Predecessors; + return Get_LGV_Attributes (G, Vertex).Pending_Strong_Predecessors; + end Pending_Strong_Predecessors; + + ------------------------------- + -- Pending_Weak_Predecessors -- + ------------------------------- + + function Pending_Weak_Predecessors + (G : Library_Graph; + Comp : Component_Id) return Natural + is + begin + pragma Assert (Present (G)); + pragma Assert (Present (Comp)); + + return Get_Component_Attributes (G, Comp).Pending_Weak_Predecessors; + end Pending_Weak_Predecessors; + + ------------------------------- + -- Pending_Weak_Predecessors -- + ------------------------------- + + function Pending_Weak_Predecessors + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Natural + is + begin + pragma Assert (Present (G)); + pragma Assert (Present (Vertex)); + + return Get_LGV_Attributes (G, Vertex).Pending_Weak_Predecessors; + end Pending_Weak_Predecessors; ---------------- -- Precedence -- @@ -4306,9 +4502,9 @@ package body Bindo.Graphs is Complement : constant Library_Graph_Vertex_Id := Complementary_Vertex - (G => G, - Vertex => Vertex, - Do_Complement => Do_Complement); + (G => G, + Vertex => Vertex, + Force_Complement => Do_Complement); begin LGV_Sets.Delete (Set, Vertex); @@ -4702,6 +4898,24 @@ package body Bindo.Graphs is return Get_LGV_Attributes (G, Vertex).Unit; end Unit; + --------------------------------- + -- Update_Pending_Predecessors -- + --------------------------------- + + procedure Update_Pending_Predecessors + (Strong_Predecessors : in out Natural; + Weak_Predecessors : in out Natural; + Update_Weak : Boolean; + Value : Integer) + is + begin + if Update_Weak then + Weak_Predecessors := Weak_Predecessors + Value; + else + Strong_Predecessors := Strong_Predecessors + Value; + end if; + end Update_Pending_Predecessors; + ----------------------------------------------- -- Update_Pending_Predecessors_Of_Components -- ----------------------------------------------- @@ -4748,7 +4962,10 @@ package body Bindo.Graphs is -- must wait on another predecessor until it can be elaborated. if Pred_Comp /= Succ_Comp then - Increment_Pending_Predecessors (G, Succ_Comp); + Increment_Pending_Predecessors + (G => G, + Comp => Succ_Comp, + Edge => Edge); end if; end Update_Pending_Predecessors_Of_Components; end Library_Graphs; @@ -4835,7 +5052,7 @@ package body Bindo.Graphs is -------------------------- LGC_Sequencer : Library_Graph_Cycle_Id := First_Library_Graph_Cycle; - -- The couhnter for library graph cycles. Do not directly manipulate its + -- The counter for library graph cycles. Do not directly manipulate its -- value. function Sequence_Next_Cycle return Library_Graph_Cycle_Id is diff --git a/gcc/ada/bindo-graphs.ads b/gcc/ada/bindo-graphs.ads index 02f8e52..3c2fef01 100644 --- a/gcc/ada/bindo-graphs.ads +++ b/gcc/ada/bindo-graphs.ads @@ -668,7 +668,7 @@ package Bindo.Graphs is -- The following type represents the various kinds of library graph -- cycles. The ordering of kinds is significant, where a literal with - -- lower ordinal has a higner precedence than one with higher ordinal. + -- lower ordinal has a higher precedence than one with higher ordinal. type Library_Graph_Cycle_Kind is (Elaborate_Body_Cycle, @@ -753,13 +753,11 @@ package Bindo.Graphs is -- describes. function Create - (Initial_Vertices : Positive; - Initial_Edges : Positive; - Dynamically_Elaborated : Boolean) return Library_Graph; + (Initial_Vertices : Positive; + Initial_Edges : Positive) return Library_Graph; pragma Inline (Create); -- Create a new empty graph with vertex capacity Initial_Vertices and - -- edge capacity Initial_Edges. Flag Dynamically_Elaborated must be set - -- when the main library unit was compiled using the dynamic model. + -- edge capacity Initial_Edges. procedure Destroy (G : in out Library_Graph); pragma Inline (Destroy); @@ -809,10 +807,12 @@ package Bindo.Graphs is procedure Decrement_Pending_Predecessors (G : Library_Graph; - Vertex : Library_Graph_Vertex_Id); + Vertex : Library_Graph_Vertex_Id; + Edge : Library_Graph_Edge_Id); pragma Inline (Decrement_Pending_Predecessors); - -- Decrease the number of pending predecessors vertex Vertex of library - -- graph G must wait on until it can be elaborated. + -- Decrease the number of pending predecessors vertex Vertex which was + -- reached via edge Edge of library graph G must wait until it can be + -- elaborated. function File_Name (G : Library_Graph; @@ -844,12 +844,30 @@ package Bindo.Graphs is -- Obtain the name of the unit which vertex Vertex of library graph G -- represents. - function Pending_Predecessors + procedure Pending_Predecessors_For_Elaboration + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Strong_Preds : out Natural; + Weak_Preds : out Natural); + pragma Inline (Pending_Predecessors_For_Elaboration); + -- Obtain the number of pending strong and weak predecessors of vertex + -- Vertex of library graph G, taking into account Elaborate_Body pairs. + -- Strong predecessors are returned in Strong_Preds. Weak predecessors + -- are returned in Weak_Preds. + + function Pending_Strong_Predecessors + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Natural; + pragma Inline (Pending_Strong_Predecessors); + -- Obtain the number of pending strong predecessors vertex Vertex of + -- library graph G must wait on until it can be elaborated. + + function Pending_Weak_Predecessors (G : Library_Graph; Vertex : Library_Graph_Vertex_Id) return Natural; - pragma Inline (Pending_Predecessors); - -- Obtain the number of pending predecessors vertex Vertex of library - -- graph G must wait on until it can be elaborated. + pragma Inline (Pending_Weak_Predecessors); + -- Obtain the number of pending weak predecessors vertex Vertex of + -- library graph G must wait on until it can be elaborated. procedure Set_Corresponding_Item (G : Library_Graph; @@ -901,17 +919,26 @@ package Bindo.Graphs is procedure Decrement_Pending_Predecessors (G : Library_Graph; - Comp : Component_Id); + Comp : Component_Id; + Edge : Library_Graph_Edge_Id); pragma Inline (Decrement_Pending_Predecessors); - -- Decrease the number of pending predecessors component Comp of library - -- graph G must wait on until it can be elaborated. + -- Decrease the number of pending predecessors component Comp which was + -- reached via edge Edge of library graph G must wait on until it can be + -- elaborated. - function Pending_Predecessors + function Pending_Strong_Predecessors (G : Library_Graph; Comp : Component_Id) return Natural; - pragma Inline (Pending_Predecessors); - -- Obtain the number of pending predecessors component Comp of library - -- graph G must wait on until it can be elaborated. + pragma Inline (Pending_Strong_Predecessors); + -- Obtain the number of pending strong predecessors component Comp of + -- library graph G must wait on until it can be elaborated. + + function Pending_Weak_Predecessors + (G : Library_Graph; + Comp : Component_Id) return Natural; + pragma Inline (Pending_Weak_Predecessors); + -- Obtain the number of pending weak predecessors component Comp of + -- library graph G must wait on until it can be elaborated. ---------------------- -- Cycle attributes -- @@ -940,6 +967,26 @@ package Bindo.Graphs is -- Semantics -- --------------- + function Complementary_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id; + Force_Complement : Boolean) return Library_Graph_Vertex_Id; + pragma Inline (Complementary_Vertex); + -- Obtain the complementary vertex of vertex Vertex of library graph G + -- as follows: + -- + -- * If Vertex is the spec of an Elaborate_Body pair, return the body + -- * If Vertex is the body of an Elaborate_Body pair, return the spec + -- + -- This behavior can be forced by setting flag Force_Complement to True. + + function Contains_Weak_Static_Successor + (G : Library_Graph; + Cycle : Library_Graph_Cycle_Id) return Boolean; + pragma Inline (Contains_Weak_Static_Successor); + -- Determine whether cycle Cycle of library graph G contains a weak edge + -- where the successor was compiled using the static model. + function Has_Elaborate_All_Cycle (G : Library_Graph) return Boolean; pragma Inline (Has_Elaborate_All_Cycle); -- Determine whether library graph G contains a cycle involving pragma @@ -973,22 +1020,26 @@ package Bindo.Graphs is -- Determine whether vertex Vertex of library graph G denotes a body -- with a corresponding spec. - function Is_Dynamically_Elaborated (G : Library_Graph) return Boolean; + function Is_Dynamically_Elaborated + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean; pragma Inline (Is_Dynamically_Elaborated); - -- Determine whether library graph G was created from a set of units - -- where the main library unit was compiled using the dynamic model. + -- Determine whether vertex Vertex of library graph G was compiled + -- using the dynamic model. function Is_Elaborable_Component (G : Library_Graph; Comp : Component_Id) return Boolean; pragma Inline (Is_Elaborable_Component); - -- Determine whether component Comp of library graph G can be elaborated + -- Determine whether component Comp of library graph G is not waiting on + -- any predecessors, and can thus be elaborated. function Is_Elaborable_Vertex (G : Library_Graph; Vertex : Library_Graph_Vertex_Id) return Boolean; pragma Inline (Is_Elaborable_Vertex); - -- Determine whether vertex Vertex of library graph G can be elaborated + -- Determine whether vertex Vertex of library graph G is not waiting on + -- any predecessors, and can thus be elaborated. function Is_Elaborate_All_Edge (G : Library_Graph; @@ -1012,6 +1063,15 @@ package Bindo.Graphs is -- Determine whether edge Edge of library graph G is an edge whose -- predecessor is subject to pragma Elaborate. + function Is_Elaborate_Body_Pair + (G : Library_Graph; + Spec_Vertex : Library_Graph_Vertex_Id; + Body_Vertex : Library_Graph_Vertex_Id) return Boolean; + pragma Inline (Is_Elaborate_Body_Pair); + -- Determine whether vertices Spec_Vertex and Body_Vertex of library + -- graph G denote a spec subject to Elaborate_Body and its completing + -- body. + function Is_Forced_Edge (G : Library_Graph; Edge : Library_Graph_Edge_Id) return Boolean; @@ -1045,7 +1105,7 @@ package Bindo.Graphs is Vertex : Library_Graph_Vertex_Id) return Boolean; pragma Inline (Is_Preelaborated_Unit); -- Determine whether vertex Vertex of library graph G denotes a unit - -- subjec to pragma Pure or Preelaborable. + -- subject to pragma Pure or Preelaborable. function Is_Spec (G : Library_Graph; @@ -1067,6 +1127,14 @@ package Bindo.Graphs is -- Determine whether vertex Vertex of library graph G denotes a spec -- with a corresponding body, and is subject to pragma Elaborate_Body. + function Is_Weakly_Elaborable_Vertex + (G : Library_Graph; + Vertex : Library_Graph_Vertex_Id) return Boolean; + pragma Inline (Is_Weakly_Elaborable_Vertex); + -- Determine whether vertex Vertex of library graph G is waiting on + -- weak predecessors only, in which case it can be elaborated assuming + -- that the weak edges will not be exercised at elaboration time. + function Is_With_Edge (G : Library_Graph; Edge : Library_Graph_Edge_Id) return Boolean; @@ -1320,9 +1388,13 @@ package Bindo.Graphs is In_Elaboration_Order : Boolean := False; -- Set when this vertex is elaborated - Pending_Predecessors : Natural := 0; - -- The number of pending predecessor vertices this vertex must wait - -- on before it can be elaborated. + Pending_Strong_Predecessors : Natural := 0; + -- The number of pending strong predecessor vertices this vertex must + -- wait on before it can be elaborated. + + Pending_Weak_Predecessors : Natural := 0; + -- The number of weak predecessor vertices this vertex must wait on + -- before it can be elaborated. Unit : Unit_Id := No_Unit_Id; -- The reference to unit this vertex represents @@ -1330,10 +1402,11 @@ package Bindo.Graphs is No_Library_Graph_Vertex_Attributes : constant Library_Graph_Vertex_Attributes := - (Corresponding_Item => No_Library_Graph_Vertex, - In_Elaboration_Order => False, - Pending_Predecessors => 0, - Unit => No_Unit_Id); + (Corresponding_Item => No_Library_Graph_Vertex, + In_Elaboration_Order => False, + Pending_Strong_Predecessors => 0, + Pending_Weak_Predecessors => 0, + Unit => No_Unit_Id); procedure Destroy_Library_Graph_Vertex_Attributes (Attrs : in out Library_Graph_Vertex_Attributes); @@ -1391,13 +1464,18 @@ package Bindo.Graphs is -- The following type represents the attributes of a component type Component_Attributes is record - Pending_Predecessors : Natural := 0; - -- The number of pending predecessor components this component must - -- wait on before it can be elaborated. + Pending_Strong_Predecessors : Natural := 0; + -- The number of pending strong predecessor components this component + -- must wait on before it can be elaborated. + + Pending_Weak_Predecessors : Natural := 0; + -- The number of pending weak predecessor components this component + -- must wait on before it can be elaborated. end record; No_Component_Attributes : constant Component_Attributes := - (Pending_Predecessors => 0); + (Pending_Strong_Predecessors => 0, + Pending_Weak_Predecessors => 0); procedure Destroy_Component_Attributes (Attrs : in out Component_Attributes); @@ -1560,10 +1638,6 @@ package Bindo.Graphs is Cycles : LGC_Lists.Doubly_Linked_List := LGC_Lists.Nil; -- The list of all cycles in the graph, sorted based on precedence - Dynamically_Elaborated : Boolean := False; - -- Set when the main library unit was compiled using the dynamic - -- model. - Edge_Attributes : LGE_Tables.Dynamic_Hash_Table := LGE_Tables.Nil; -- The map of edge -> edge attributes for all edges in the graph diff --git a/gcc/ada/bindo-validators.adb b/gcc/ada/bindo-validators.adb index aed4960..88be2e8 100644 --- a/gcc/ada/bindo-validators.adb +++ b/gcc/ada/bindo-validators.adb @@ -140,7 +140,7 @@ package body Bindo.Validators is Edges := LGE_Sets.Create (Length (G, Cycle)); - -- Inspect the edges of the cucle, trying to catch duplicates + -- Inspect the edges of the cycle, trying to catch duplicates Iter := Iterate_Edges_Of_Cycle (G, Cycle); while Has_Next (Iter) loop @@ -155,7 +155,7 @@ package body Bindo.Validators is Write_Str (" library graph edge (LGE_Id_"); Write_Int (Int (Edge)); - Write_Str (") is repeaded in cycle (LGC_Id_"); + Write_Str (") is repeated in cycle (LGC_Id_"); Write_Int (Int (Cycle)); Write_Str (")"); Write_Eol; @@ -421,7 +421,7 @@ package body Bindo.Validators is (G : Invocation_Graph; Vertex : Invocation_Graph_Vertex_Id); pragma Inline (Validate_Invocation_Graph_Vertex); - -- Verify that the attributes of vertex Vertex of inbocation graph G are + -- Verify that the attributes of vertex Vertex of invocation graph G are -- properly set. procedure Validate_Invocation_Graph_Vertices (G : Invocation_Graph); @@ -468,7 +468,7 @@ package body Bindo.Validators is if not Present (Edge) then Write_Error (Msg, Has_Invalid_Data); - Write_Str (" emply invocation graph edge"); + Write_Str (" empty invocation graph edge"); Write_Eol; Write_Eol; return; @@ -530,7 +530,7 @@ package body Bindo.Validators is if not Present (Vertex) then Write_Error (Msg, Has_Invalid_Data); - Write_Str (" emply invocation graph vertex"); + Write_Str (" empty invocation graph vertex"); Write_Eol; Write_Eol; return; @@ -662,7 +662,7 @@ package body Bindo.Validators is if not Present (Edge) then Write_Error (Msg, Has_Invalid_Data); - Write_Str (" emply library graph edge"); + Write_Str (" empty library graph edge"); Write_Eol; Write_Eol; return; diff --git a/gcc/ada/bindo-writers.adb b/gcc/ada/bindo-writers.adb index a3b45fc..99f93f5 100644 --- a/gcc/ada/bindo-writers.adb +++ b/gcc/ada/bindo-writers.adb @@ -1025,6 +1025,10 @@ package body Bindo.Writers is -- Write all vertices of component Comp of library graph G to standard -- output. + procedure Write_Components (G : Library_Graph); + pragma Inline (Write_Component); + -- Write all components of library graph G to standard output + procedure Write_Edges_To_Successors (G : Library_Graph; Vertex : Library_Graph_Vertex_Id); @@ -1089,8 +1093,12 @@ package body Bindo.Writers is Write_Str (")"); Write_Eol; - Write_Str (" Pending_Predecessors = "); - Write_Int (Int (Pending_Predecessors (G, Comp))); + Write_Str (" Pending_Strong_Predecessors = "); + Write_Int (Int (Pending_Strong_Predecessors (G, Comp))); + Write_Eol; + + Write_Str (" Pending_Weak_Predecessors = "); + Write_Int (Int (Pending_Weak_Predecessors (G, Comp))); Write_Eol; Write_Component_Vertices (G, Comp); @@ -1225,6 +1233,7 @@ package body Bindo.Writers is Write_Statistics (G); Write_Library_Graph_Vertices (G); + Write_Components (G); Write_Str ("Library Graph end"); Write_Eol; @@ -1312,8 +1321,12 @@ package body Bindo.Writers is end if; Write_Eol; - Write_Str (" Pending_Predecessors = "); - Write_Int (Int (Pending_Predecessors (G, Vertex))); + Write_Str (" Pending_Strong_Predecessors = "); + Write_Int (Int (Pending_Strong_Predecessors (G, Vertex))); + Write_Eol; + + Write_Str (" Pending_Weak_Predecessors = "); + Write_Int (Int (Pending_Weak_Predecessors (G, Vertex))); Write_Eol; Write_Str (" Component (Comp_Id_"); @@ -1612,7 +1625,7 @@ package body Bindo.Writers is is function Digits_Indentation return Indentation_Level; pragma Inline (Digits_Indentation); - -- Determine the level of indentation the number requies in order to + -- Determine the level of indentation the number requires in order to -- be right-justified by Val_Indent. ------------------------ diff --git a/gcc/ada/bindo-writers.ads b/gcc/ada/bindo-writers.ads index ff6b9b3..01e48e4 100644 --- a/gcc/ada/bindo-writers.ads +++ b/gcc/ada/bindo-writers.ads @@ -127,9 +127,6 @@ package Bindo.Writers is --------------------------- package Library_Graph_Writers is - procedure Write_Components (G : Library_Graph); - -- Write all components of library graph G to standard output - procedure Write_Library_Graph (G : Library_Graph); -- Write library graph G to standard output diff --git a/gcc/ada/bindo.adb b/gcc/ada/bindo.adb index b3106ad..897e746 100644 --- a/gcc/ada/bindo.adb +++ b/gcc/ada/bindo.adb @@ -74,7 +74,7 @@ package body Bindo is -- -- * Diagnose elaboration circularities between units -- - -- An elaboration circularity arrises when either + -- An elaboration circularity arises when either -- -- - At least one unit cannot be ordered, or -- @@ -95,6 +95,12 @@ package body Bindo is -- * Component - A strongly connected component of a graph. -- + -- * Elaborable component - A component that is not waiting on other + -- components to be elaborated. + -- + -- * Elaborable vertex - A vertex that is not waiting on strong and weak + -- predecessors, and whose component is elaborable. + -- -- * Elaboration circularity - A cycle involving units from the bind. -- -- * Elaboration root - A special invocation construct which denotes the @@ -136,8 +142,23 @@ package body Bindo is -- * Pending predecessor - A vertex that must be elaborated before another -- vertex can be elaborated. -- + -- * Strong edge - A non-invocation library graph edge. Strong edges + -- represent the language-defined relations between units. + -- + -- * Strong predecessor - A library graph vertex reachable via a strong + -- edge. + -- -- * Target - The destination construct of an invocation relation (the -- generic, subprogram, or task type). + -- + -- * Weak edge - An invocation library graph edge. Weak edges represent + -- the speculative flow of execution at elaboration time, which may or + -- may not take place. + -- + -- * Weak predecessor - A library graph vertex reachable via a weak edge. + -- + -- * Weakly elaborable vertex - A vertex that is waiting solely on weak + -- predecessors to be elaborated, and whose component is elaborable. ------------------ -- Architecture -- @@ -233,7 +254,7 @@ package body Bindo is -- bodies as single vertices. -- -- * Try to order as many vertices of the library graph as possible by - -- peforming a topological sort based on the pending predecessors of + -- performing a topological sort based on the pending predecessors of -- vertices across all components and within a single component. -- -- * Validate the consistency of the order, only when switch -d_V is in @@ -251,7 +272,7 @@ package body Bindo is -- The Diagnostics phase has the following objectives: -- -- * Discover, save, and sort all cycles in the library graph. The cycles - -- are sorted based on the following heiristics: + -- are sorted based on the following heuristics: -- -- - A cycle with higher precedence is preferred. -- @@ -268,7 +289,7 @@ package body Bindo is -- * Diagnose the most important cycle, or all cycles when switch -d_C is -- in effect. The diagnostic consists of: -- - -- - The reason for the existance of the cycle, along with the unit + -- - The reason for the existence of the cycle, along with the unit -- whose elaboration cannot be guaranteed. -- -- - A detailed traceback of the cycle, showcasing the transition @@ -276,7 +297,7 @@ package body Bindo is -- information. -- -- - A set of suggestions on how to break the cycle considering the - -- the edges coprising the circuit, the elaboration model used to + -- the edges comprising the circuit, the elaboration model used to -- compile the units, the availability of invocation information, -- and the state of various relevant switches. @@ -284,6 +305,23 @@ package body Bindo is -- Switches -- -------------- + -- -d_a Ignore the effects of pragma Elaborate_All + -- + -- GNATbind creates a regular with edge instead of an Elaborate_All + -- edge in the library graph, thus eliminating the effects of the + -- pragma. + -- + -- -d_b Ignore the effects of pragma Elaborate_Body + -- + -- GNATbind treats a spec and body pair as decoupled. + -- + -- -d_e Ignore the effects of pragma Elaborate + -- + -- GNATbind creates a regular with edge instead of an Elaborate edge + -- in the library graph, thus eliminating the effects of the pragma. + -- In addition, GNATbind does not create an edge to the body of the + -- pragma argument. + -- -- -d_A Output ALI invocation tables -- -- GNATbind outputs the contents of ALI table Invocation_Constructs diff --git a/gcc/ada/bindo.ads b/gcc/ada/bindo.ads index 39cf7a4..940b752 100644 --- a/gcc/ada/bindo.ads +++ b/gcc/ada/bindo.ads @@ -41,4 +41,14 @@ package Bindo is -- exists, it is returned in Order, otherwise Unrecoverable_Error is -- raised. +private + + -- The following type represents the various kinds of precedence between + -- two items. + + type Precedence_Kind is + (Lower_Precedence, + Equal_Precedence, + Higher_Precedence); + end Bindo; diff --git a/gcc/ada/debug.adb b/gcc/ada/debug.adb index da4bea1..680c38f 100644 --- a/gcc/ada/debug.adb +++ b/gcc/ada/debug.adb @@ -349,11 +349,11 @@ package body Debug is -- d.8 -- d.9 - -- d_a - -- d_b + -- d_a Ignore the effects of pragma Elaborate_All + -- d_b Ignore the effects of pragma Elaborate_Body -- d_c -- d_d - -- d_e + -- d_e Ignore the effects of pragma Elaborate -- d_f -- d_g -- d_h @@ -1141,6 +1141,17 @@ package body Debug is -- dx Force the binder to read (and then ignore) the xref information -- in ali files (used to check that read circuit is working OK). + -- d_a GNATBIND ignores the effects of pragma Elaborate_All in the case of + -- elaboration order and treats the associated dependency as a regular + -- with edge. + + -- d_b GNATBIND ignores the effects of pragma Elaborate_Body in the case + -- of elaboration order and treats the spec and body as decoupled. + + -- d_e GNATBIND ignores the effects of pragma Elaborate in the case of + -- elaboration order and no longer creates an implicit dependency on + -- the body of the argument. + -- d_A GNATBIND output the contents of all ALI invocation-related tables -- in textual format to standard output. |