145
|
1 ------------------------------------------------------------------------------
|
|
2 -- --
|
|
3 -- GNAT COMPILER COMPONENTS --
|
|
4 -- --
|
|
5 -- B I N D O --
|
|
6 -- --
|
|
7 -- B o d y --
|
|
8 -- --
|
|
9 -- Copyright (C) 2019, Free Software Foundation, Inc. --
|
|
10 -- --
|
|
11 -- GNAT is free software; you can redistribute it and/or modify it under --
|
|
12 -- terms of the GNU General Public License as published by the Free Soft- --
|
|
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
|
|
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
|
|
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
|
|
16 -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
|
|
17 -- for more details. You should have received a copy of the GNU General --
|
|
18 -- Public License distributed with GNAT; see file COPYING3. If not, go to --
|
|
19 -- http://www.gnu.org/licenses for a complete copy of the license. --
|
|
20 -- --
|
|
21 -- GNAT was originally developed by the GNAT team at New York University. --
|
|
22 -- Extensive contributions were provided by Ada Core Technologies Inc. --
|
|
23 -- --
|
|
24 ------------------------------------------------------------------------------
|
|
25
|
|
26 with Binde;
|
|
27 with Opt; use Opt;
|
|
28
|
|
29 with Bindo.Elaborators;
|
|
30 use Bindo.Elaborators;
|
|
31
|
|
32 package body Bindo is
|
|
33
|
|
34 ---------------------------------
|
|
35 -- Elaboration-order mechanism --
|
|
36 ---------------------------------
|
|
37
|
|
38 -- The elaboration-order (EO) mechanism implemented in this unit and its
|
|
39 -- children has the following objectives:
|
|
40 --
|
|
41 -- * Find an ordering of all library items (historically referred to as
|
|
42 -- "units") in the bind which require elaboration, taking into account:
|
|
43 --
|
|
44 -- - The dependencies between units expressed in the form of with
|
|
45 -- clauses.
|
|
46 --
|
|
47 -- - Pragmas Elaborate, Elaborate_All, Elaborate_Body, Preelaborable,
|
|
48 -- and Pure.
|
|
49 --
|
|
50 -- - The flow of execution at elaboration time.
|
|
51 --
|
|
52 -- - Additional dependencies between units supplied to the binder by
|
|
53 -- means of a forced-elaboration-order file.
|
|
54 --
|
|
55 -- The high-level idea empoyed by the EO mechanism is to construct two
|
|
56 -- graphs and use the information they represent to find an ordering of
|
|
57 -- all units.
|
|
58 --
|
|
59 -- The invocation graph represents the flow of execution at elaboration
|
|
60 -- time.
|
|
61 --
|
|
62 -- The library graph captures the dependencies between units expressed
|
|
63 -- by with clause and elaboration-related pragmas. The library graph is
|
|
64 -- further augmented with additional information from the invocation
|
|
65 -- graph by exploring the execution paths from a unit with elaboration
|
|
66 -- code to other external units.
|
|
67 --
|
|
68 -- The strongly connected components of the library graph are computed.
|
|
69 --
|
|
70 -- The order is obtained using a topological sort-like algorithm which
|
|
71 -- traverses the library graph and its strongly connected components in
|
|
72 -- an attempt to order available units while enabling other units to be
|
|
73 -- ordered.
|
|
74 --
|
|
75 -- * Diagnose elaboration circularities between units
|
|
76 --
|
|
77 -- An elaboration circularity arises when either
|
|
78 --
|
|
79 -- - At least one unit cannot be ordered, or
|
|
80 --
|
|
81 -- - All units can be ordered, but an edge with an Elaborate_All
|
|
82 -- pragma links two vertices within the same component of the
|
|
83 -- library graph.
|
|
84 --
|
|
85 -- The library graph is traversed to discover, collect, and sort all
|
|
86 -- cycles that hinder the elaboration order.
|
|
87 --
|
|
88 -- The most important cycle is diagnosed by describing its effects on
|
|
89 -- the elaboration order and listing all units comprising the circuit.
|
|
90 -- Various suggestions on how to break the cycle are offered.
|
|
91
|
|
92 -----------------
|
|
93 -- Terminology --
|
|
94 -----------------
|
|
95
|
|
96 -- * Component - A strongly connected component of a graph.
|
|
97 --
|
|
98 -- * Elaborable component - A component that is not waiting on other
|
|
99 -- components to be elaborated.
|
|
100 --
|
|
101 -- * Elaborable vertex - A vertex that is not waiting on strong and weak
|
|
102 -- predecessors, and whose component is elaborable.
|
|
103 --
|
|
104 -- * Elaboration circularity - A cycle involving units from the bind.
|
|
105 --
|
|
106 -- * Elaboration root - A special invocation construct which denotes the
|
|
107 -- elaboration procedure of a unit.
|
|
108 --
|
|
109 -- * Invocation - The act of activating a task, calling a subprogram, or
|
|
110 -- instantiating a generic.
|
|
111 --
|
|
112 -- * Invocation construct - An entry declaration, [single] protected type,
|
|
113 -- subprogram declaration, subprogram instantiation, or a [single] task
|
|
114 -- type declared in the visible, private, or body declarations of some
|
|
115 -- unit. The construct is encoded in the ALI file of the related unit.
|
|
116 --
|
|
117 -- * Invocation graph - A directed graph which models the flow of execution
|
|
118 -- at elaboration time.
|
|
119 --
|
|
120 -- - Vertices - Invocation constructs plus extra information. Certain
|
|
121 -- vertices act as elaboration roots.
|
|
122 --
|
|
123 -- - Edges - Invocation relations plus extra information.
|
|
124 --
|
|
125 -- * Invocation relation - A flow link between two invocation constructs.
|
|
126 -- This link is encoded in the ALI file of unit that houses the invoker.
|
|
127 --
|
|
128 -- * Invocation signature - A set of attributes that uniquely identify an
|
|
129 -- invocation construct within the namespace of all ALI files.
|
|
130 --
|
|
131 -- * Invoker - The source construct of an invocation relation (the caller,
|
|
132 -- instantiator, or task activator).
|
|
133 --
|
|
134 -- * Library graph - A directed graph which captures with clause and pragma
|
|
135 -- dependencies between units.
|
|
136 --
|
|
137 -- - Vertices - Units plus extra information.
|
|
138 --
|
|
139 -- - Edges - With clause, pragma, and additional dependencies between
|
|
140 -- units.
|
|
141 --
|
|
142 -- * Pending predecessor - A vertex that must be elaborated before another
|
|
143 -- vertex can be elaborated.
|
|
144 --
|
|
145 -- * Strong edge - A non-invocation library graph edge. Strong edges
|
|
146 -- represent the language-defined relations between units.
|
|
147 --
|
|
148 -- * Strong predecessor - A library graph vertex reachable via a strong
|
|
149 -- edge.
|
|
150 --
|
|
151 -- * Target - The destination construct of an invocation relation (the
|
|
152 -- generic, subprogram, or task type).
|
|
153 --
|
|
154 -- * Weak edge - An invocation library graph edge. Weak edges represent
|
|
155 -- the speculative flow of execution at elaboration time, which may or
|
|
156 -- may not take place.
|
|
157 --
|
|
158 -- * Weak predecessor - A library graph vertex reachable via a weak edge.
|
|
159 --
|
|
160 -- * Weakly elaborable vertex - A vertex that is waiting solely on weak
|
|
161 -- predecessors to be elaborated, and whose component is elaborable.
|
|
162
|
|
163 ------------------
|
|
164 -- Architecture --
|
|
165 ------------------
|
|
166
|
|
167 -- Find_Elaboration_Order
|
|
168 -- |
|
|
169 -- +--> Collect_Elaborable_Units
|
|
170 -- +--> Write_ALI_Tables
|
|
171 -- +--> Elaborate_Units
|
|
172 -- |
|
|
173 -- +------ | -------------- Construction phase ------------------------+
|
|
174 -- | | |
|
|
175 -- | +--> Build_Library_Graph |
|
|
176 -- | +--> Validate_Library_Graph |
|
|
177 -- | +--> Write_Library_Graph |
|
|
178 -- | | |
|
|
179 -- | +--> Build_Invocation_Graph |
|
|
180 -- | +--> Validate_Invocation_Graph |
|
|
181 -- | +--> Write_Invocation_Graph |
|
|
182 -- | | |
|
|
183 -- +------ | ----------------------------------------------------------+
|
|
184 -- |
|
|
185 -- +------ | -------------- Augmentation phase ------------------------+
|
|
186 -- | | |
|
|
187 -- | +--> Augment_Library_Graph |
|
|
188 -- | | |
|
|
189 -- +------ | ----------------------------------------------------------+
|
|
190 -- |
|
|
191 -- +------ | -------------- Ordering phase ----------------------------+
|
|
192 -- | | |
|
|
193 -- | +--> Find_Components |
|
|
194 -- | | |
|
|
195 -- | +--> Elaborate_Library_Graph |
|
|
196 -- | +--> Validate_Elaboration_Order |
|
|
197 -- | +--> Write_Elaboration_Order |
|
|
198 -- | | |
|
|
199 -- | +--> Write_Unit_Closure |
|
|
200 -- | | |
|
|
201 -- +------ | ----------------------------------------------------------+
|
|
202 -- |
|
|
203 -- +------ | -------------- Diagnostics phase -------------------------+
|
|
204 -- | | |
|
|
205 -- | +--> Find_Cycles |
|
|
206 -- | +--> Validate_Cycles |
|
|
207 -- | +--> Write_Cycles |
|
|
208 -- | | |
|
|
209 -- | +--> Diagnose_Cycle / Diagnose_All_Cycles |
|
|
210 -- | |
|
|
211 -- +-------------------------------------------------------------------+
|
|
212
|
|
213 ------------------------
|
|
214 -- Construction phase --
|
|
215 ------------------------
|
|
216
|
|
217 -- The Construction phase has the following objectives:
|
|
218 --
|
|
219 -- * Build the library graph by inspecting the ALI file of each unit that
|
|
220 -- requires elaboration.
|
|
221 --
|
|
222 -- * Validate the consistency of the library graph, only when switch -d_V
|
|
223 -- is in effect.
|
|
224 --
|
|
225 -- * Write the contents of the invocation graph in human-readable form to
|
|
226 -- standard output when switch -d_L is in effect.
|
|
227 --
|
|
228 -- * Build the invocation graph by inspecting invocation constructs and
|
|
229 -- relations in the ALI file of each unit that requires elaboration.
|
|
230 --
|
|
231 -- * Validate the consistency of the invocation graph, only when switch
|
|
232 -- -d_V is in effect.
|
|
233 --
|
|
234 -- * Write the contents of the invocation graph in human-readable form to
|
|
235 -- standard output when switch -d_I is in effect.
|
|
236
|
|
237 ------------------------
|
|
238 -- Augmentation phase --
|
|
239 ------------------------
|
|
240
|
|
241 -- The Augmentation phase has the following objectives:
|
|
242 --
|
|
243 -- * Discover transitions of the elaboration flow from a unit with an
|
|
244 -- elaboration root to other units. Augment the library graph with
|
|
245 -- extra edges for each such transition.
|
|
246
|
|
247 --------------------
|
|
248 -- Ordering phase --
|
|
249 --------------------
|
|
250
|
|
251 -- The Ordering phase has the following objectives:
|
|
252 --
|
|
253 -- * Discover all components of the library graph by treating specs and
|
|
254 -- bodies as single vertices.
|
|
255 --
|
|
256 -- * Try to order as many vertices of the library graph as possible by
|
|
257 -- performing a topological sort based on the pending predecessors of
|
|
258 -- vertices across all components and within a single component.
|
|
259 --
|
|
260 -- * Validate the consistency of the order, only when switch -d_V is in
|
|
261 -- effect.
|
|
262 --
|
|
263 -- * Write the contents of the order in human-readable form to standard
|
|
264 -- output when switch -d_O is in effect.
|
|
265 --
|
|
266 -- * Write the sources of the order closure when switch -R is in effect.
|
|
267
|
|
268 -----------------------
|
|
269 -- Diagnostics phase --
|
|
270 -----------------------
|
|
271
|
|
272 -- The Diagnostics phase has the following objectives:
|
|
273 --
|
|
274 -- * Discover, save, and sort all cycles in the library graph. The cycles
|
|
275 -- are sorted based on the following heuristics:
|
|
276 --
|
|
277 -- - A cycle with higher precedence is preferred.
|
|
278 --
|
|
279 -- - A cycle with fewer invocation edges is preferred.
|
|
280 --
|
|
281 -- - A cycle with a shorter length is preferred.
|
|
282 --
|
|
283 -- * Validate the consistency of cycles, only when switch -d_V is in
|
|
284 -- effect.
|
|
285 --
|
|
286 -- * Write the contents of all cycles in human-readable form to standard
|
|
287 -- output when switch -d_O is in effect.
|
|
288 --
|
|
289 -- * Diagnose the most important cycle, or all cycles when switch -d_C is
|
|
290 -- in effect. The diagnostic consists of:
|
|
291 --
|
|
292 -- - The reason for the existence of the cycle, along with the unit
|
|
293 -- whose elaboration cannot be guaranteed.
|
|
294 --
|
|
295 -- - A detailed traceback of the cycle, showcasing the transition
|
|
296 -- between units, along with any other elaboration-order-related
|
|
297 -- information.
|
|
298 --
|
|
299 -- - A set of suggestions on how to break the cycle considering the
|
|
300 -- the edges comprising the circuit, the elaboration model used to
|
|
301 -- compile the units, the availability of invocation information,
|
|
302 -- and the state of various relevant switches.
|
|
303
|
|
304 --------------
|
|
305 -- Switches --
|
|
306 --------------
|
|
307
|
|
308 -- -d_a Ignore the effects of pragma Elaborate_All
|
|
309 --
|
|
310 -- GNATbind creates a regular with edge instead of an Elaborate_All
|
|
311 -- edge in the library graph, thus eliminating the effects of the
|
|
312 -- pragma.
|
|
313 --
|
|
314 -- -d_b Ignore the effects of pragma Elaborate_Body
|
|
315 --
|
|
316 -- GNATbind treats a spec and body pair as decoupled.
|
|
317 --
|
|
318 -- -d_e Ignore the effects of pragma Elaborate
|
|
319 --
|
|
320 -- GNATbind creates a regular with edge instead of an Elaborate edge
|
|
321 -- in the library graph, thus eliminating the effects of the pragma.
|
|
322 -- In addition, GNATbind does not create an edge to the body of the
|
|
323 -- pragma argument.
|
|
324 --
|
|
325 -- -d_t Output cycle-detection trace information
|
|
326 --
|
|
327 -- GNATbind outputs trace information on cycle-detection activities
|
|
328 -- to standard output.
|
|
329 --
|
|
330 -- -d_A Output ALI invocation tables
|
|
331 --
|
|
332 -- GNATbind outputs the contents of ALI table Invocation_Constructs
|
|
333 -- and Invocation_Edges in textual format to standard output.
|
|
334 --
|
|
335 -- -d_C Diagnose all cycles
|
|
336 --
|
|
337 -- GNATbind outputs diagnostics for all unique cycles in the bind,
|
|
338 -- rather than just the most important one.
|
|
339 --
|
|
340 -- -d_I Output invocation graph
|
|
341 --
|
|
342 -- GNATbind outputs the invocation graph in text format to standard
|
|
343 -- output.
|
|
344 --
|
|
345 -- -d_L Output library graph
|
|
346 --
|
|
347 -- GNATbind outputs the library graph in textual format to standard
|
|
348 -- output.
|
|
349 --
|
|
350 -- -d_P Output cycle paths
|
|
351 --
|
|
352 -- GNATbind outputs the cycle paths in text format to standard output
|
|
353 --
|
|
354 -- -d_S Output elaboration-order status information
|
|
355 --
|
|
356 -- GNATbind outputs trace information concerning the status of its
|
|
357 -- various phases to standard output.
|
|
358 --
|
|
359 -- -d_T Output elaboration-order trace information
|
|
360 --
|
|
361 -- GNATbind outputs trace information on elaboration-order detection
|
|
362 -- activities to standard output.
|
|
363 --
|
|
364 -- -d_V Validate bindo cycles, graphs, and order
|
|
365 --
|
|
366 -- GNATbind validates the invocation graph, library graph along with
|
|
367 -- its cycles, and elaboration order by detecting inconsistencies and
|
|
368 -- producing error reports.
|
|
369 --
|
|
370 -- -e Output complete list of elaboration-order dependencies
|
|
371 --
|
|
372 -- GNATbind outputs the dependencies between units to standard
|
|
373 -- output.
|
|
374 --
|
|
375 -- -f Force elaboration order from given file
|
|
376 --
|
|
377 -- GNATbind applies an additional set of edges to the library graph.
|
|
378 -- The edges are read from a file specified by the argument of the
|
|
379 -- flag.
|
|
380 --
|
|
381 -- -H Legacy elaboration-order model enabled
|
|
382 --
|
|
383 -- GNATbind uses the library-graph and heuristics-based elaboration-
|
|
384 -- order model.
|
|
385 --
|
|
386 -- -l Output chosen elaboration order
|
|
387 --
|
|
388 -- GNATbind outputs the elaboration order in text format to standard
|
|
389 -- output.
|
|
390 --
|
|
391 -- -p Pessimistic (worst-case) elaboration order
|
|
392 --
|
|
393 -- This switch is not used in Bindo and its children.
|
|
394
|
|
395 ----------------------------------------
|
|
396 -- Debugging elaboration-order issues --
|
|
397 ----------------------------------------
|
|
398
|
|
399 -- Prior to debugging elaboration-order-related issues, enable all relevant
|
|
400 -- debug flags to collect as much information as possible. Depending on the
|
|
401 -- number of files in the bind, Bindo may emit anywhere between several MBs
|
|
402 -- to several hundred MBs of data to standard output. The switches are:
|
|
403 --
|
|
404 -- -d_A -d_C -d_I -d_L -d_P -d_t -d_T -d_V
|
|
405 --
|
|
406 -- Bindo offers several debugging routines that can be invoked from gdb.
|
|
407 -- Those are defined in the body of Bindo.Writers, in sections denoted by
|
|
408 -- header Debug. For quick reference, the routines are:
|
|
409 --
|
|
410 -- palgc -- print all library-graph cycles
|
|
411 -- pau -- print all units
|
|
412 -- pc -- print component
|
|
413 -- pige -- print invocation-graph edge
|
|
414 -- pigv -- print invocation-graph vertex
|
|
415 -- plgc -- print library-graph cycle
|
|
416 -- plge -- print library-graph edge
|
|
417 -- plgv -- print library-graph vertex
|
|
418 -- pu -- print units
|
|
419 --
|
|
420 -- * Apparent infinite loop
|
|
421 --
|
|
422 -- The elaboration order mechanism appears to be stuck in an infinite
|
|
423 -- loop. Use switch -d_S to output the status of each elaboration phase.
|
|
424 --
|
|
425 -- * Invalid elaboration order
|
|
426 --
|
|
427 -- The elaboration order is invalid when:
|
|
428 --
|
|
429 -- - A unit that requires elaboration is missing from the order
|
|
430 -- - A unit that does not require elaboration is present in the order
|
|
431 --
|
|
432 -- Examine the output of the elaboration algorithm available via switch
|
|
433 -- -d_T to determine how the related units were included in or excluded
|
|
434 -- from the order. Determine whether the library graph contains all the
|
|
435 -- relevant edges for those units.
|
|
436 --
|
|
437 -- Units and routines of interest:
|
|
438 -- Bindo.Elaborators
|
|
439 -- Elaborate_Library_Graph
|
|
440 -- Elaborate_Units
|
|
441 --
|
|
442 -- * Invalid invocation graph
|
|
443 --
|
|
444 -- The invocation graph is invalid when:
|
|
445 --
|
|
446 -- - An edge lacks an attribute
|
|
447 -- - A vertex lacks an attribute
|
|
448 --
|
|
449 -- Find the malformed edge or vertex and determine which attribute is
|
|
450 -- missing. Examine the contents of the invocation-related ALI tables
|
|
451 -- available via switch -d_A. If the invocation construct or relation
|
|
452 -- is missing, verify the ALI file. If the ALI lacks all the relevant
|
|
453 -- information, then Sem_Elab most likely failed to discover a valid
|
|
454 -- elaboration path.
|
|
455 --
|
|
456 -- Units and routines of interest:
|
|
457 -- Bindo.Builders
|
|
458 -- Bindo.Graphs
|
|
459 -- Add_Edge
|
|
460 -- Add_Vertex
|
|
461 -- Build_Invocation_Graph
|
|
462 --
|
|
463 -- * Invalid library graph
|
|
464 --
|
|
465 -- The library graph is invalid when:
|
|
466 --
|
|
467 -- - An edge lacks an attribute
|
|
468 -- - A vertex lacks an attribute
|
|
469 --
|
|
470 -- Find the malformed edge or vertex and determine which attribute is
|
|
471 -- missing.
|
|
472 --
|
|
473 -- Units and routines of interest:
|
|
474 -- Bindo.Builders
|
|
475 -- Bindo.Graphs
|
|
476 -- Add_Edge
|
|
477 -- Add_Vertex
|
|
478 -- Build_Library_Graph
|
|
479 --
|
|
480 -- * Invalid library-graph cycle
|
|
481 --
|
|
482 -- A library-graph cycle is invalid when:
|
|
483 --
|
|
484 -- - It lacks enough edges to form a circuit
|
|
485 -- - At least one edge in the circuit is repeated
|
|
486 --
|
|
487 -- Find the malformed cycle and determine which attribute is missing.
|
|
488 --
|
|
489 -- Units and routines of interest:
|
|
490 -- Bindo.Graphs
|
|
491 -- Find_Cycles
|
|
492
|
|
493 ----------------------------
|
|
494 -- Find_Elaboration_Order --
|
|
495 ----------------------------
|
|
496
|
|
497 procedure Find_Elaboration_Order
|
|
498 (Order : out Unit_Id_Table;
|
|
499 Main_Lib_File : File_Name_Type)
|
|
500 is
|
|
501 begin
|
|
502 -- Use the library graph and heuristic-based elaboration order when
|
|
503 -- switch -H (legacy elaboration-order mode enabled).
|
|
504
|
|
505 if Legacy_Elaboration_Order then
|
|
506 Binde.Find_Elab_Order (Order, Main_Lib_File);
|
|
507
|
|
508 -- Otherwise use the invocation and library-graph-based elaboration
|
|
509 -- order.
|
|
510
|
|
511 else
|
|
512 Invocation_And_Library_Graph_Elaborators.Elaborate_Units
|
|
513 (Order => Order,
|
|
514 Main_Lib_File => Main_Lib_File);
|
|
515 end if;
|
|
516 end Find_Elaboration_Order;
|
|
517
|
|
518 end Bindo;
|