]>
Commit | Line | Data |
---|---|---|
69e6ee2f HK |
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 | ||
9795b203 | 26 | with Binde; |
16cc65b6 | 27 | with Opt; use Opt; |
9795b203 | 28 | |
69e6ee2f | 29 | with Bindo.Elaborators; |
9795b203 | 30 | use Bindo.Elaborators; |
69e6ee2f HK |
31 | |
32 | package body Bindo is | |
33 | ||
34 | --------------------------------- | |
3eb5e54a | 35 | -- Elaboration-order mechanism -- |
69e6ee2f HK |
36 | --------------------------------- |
37 | ||
3eb5e54a | 38 | -- The elaboration-order (EO) mechanism implemented in this unit and its |
69e6ee2f HK |
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 | |
9795b203 HK |
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. | |
69e6ee2f | 58 | -- |
9795b203 HK |
59 | -- The invocation graph represents the flow of execution at elaboration |
60 | -- time. | |
69e6ee2f | 61 | -- |
9795b203 HK |
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. | |
69e6ee2f | 67 | -- |
9795b203 | 68 | -- The strongly connected components of the library graph are computed. |
69e6ee2f | 69 | -- |
9795b203 HK |
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 | |
69e6ee2f HK |
73 | -- ordered. |
74 | -- | |
75 | -- * Diagnose elaboration circularities between units | |
76 | -- | |
92c7734d | 77 | -- An elaboration circularity arises when either |
9795b203 HK |
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. | |
69e6ee2f | 84 | -- |
9795b203 HK |
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. | |
69e6ee2f HK |
91 | |
92 | ----------------- | |
93 | -- Terminology -- | |
94 | ----------------- | |
95 | ||
96 | -- * Component - A strongly connected component of a graph. | |
97 | -- | |
92c7734d HK |
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 | -- | |
9795b203 HK |
104 | -- * Elaboration circularity - A cycle involving units from the bind. |
105 | -- | |
69e6ee2f HK |
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 | -- | |
92c7734d HK |
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 | -- | |
69e6ee2f HK |
151 | -- * Target - The destination construct of an invocation relation (the |
152 | -- generic, subprogram, or task type). | |
92c7734d HK |
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. | |
69e6ee2f HK |
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 | -- | | | | |
9795b203 HK |
205 | -- | +--> Find_Cycles | |
206 | -- | +--> Validate_Cycles | | |
207 | -- | +--> Write_Cycles | | |
208 | -- | | | | |
209 | -- | +--> Diagnose_Cycle / Diagnose_All_Cycles | | |
69e6ee2f HK |
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 | |
92c7734d | 257 | -- performing a topological sort based on the pending predecessors of |
69e6ee2f HK |
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 | ||
9795b203 HK |
272 | -- The Diagnostics phase has the following objectives: |
273 | -- | |
274 | -- * Discover, save, and sort all cycles in the library graph. The cycles | |
92c7734d | 275 | -- are sorted based on the following heuristics: |
9795b203 HK |
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 | -- | |
92c7734d | 292 | -- - The reason for the existence of the cycle, along with the unit |
9795b203 HK |
293 | -- whose elaboration cannot be guaranteed. |
294 | -- | |
295 | -- - A detailed traceback of the cycle, showcasing the transition | |
3eb5e54a | 296 | -- between units, along with any other elaboration-order-related |
9795b203 HK |
297 | -- information. |
298 | -- | |
299 | -- - A set of suggestions on how to break the cycle considering the | |
92c7734d | 300 | -- the edges comprising the circuit, the elaboration model used to |
9795b203 HK |
301 | -- compile the units, the availability of invocation information, |
302 | -- and the state of various relevant switches. | |
69e6ee2f HK |
303 | |
304 | -------------- | |
305 | -- Switches -- | |
306 | -------------- | |
307 | ||
92c7734d HK |
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 | -- | |
7f8c1cd3 | 325 | -- -d_t Output cycle-detection trace information |
9098d477 | 326 | -- |
7f8c1cd3 | 327 | -- GNATbind outputs trace information on cycle-detection activities |
9098d477 HK |
328 | -- to standard output. |
329 | -- | |
69e6ee2f HK |
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 | -- | |
9795b203 HK |
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 | -- | |
69e6ee2f HK |
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 | -- | |
9795b203 HK |
350 | -- -d_P Output cycle paths |
351 | -- | |
220dc4b2 | 352 | -- GNATbind outputs the cycle paths in text format to standard output |
9795b203 | 353 | -- |
490ed9ba HK |
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 | -- | |
3eb5e54a | 359 | -- -d_T Output elaboration-order trace information |
69e6ee2f | 360 | -- |
9098d477 HK |
361 | -- GNATbind outputs trace information on elaboration-order detection |
362 | -- activities to standard output. | |
69e6ee2f | 363 | -- |
9795b203 | 364 | -- -d_V Validate bindo cycles, graphs, and order |
69e6ee2f | 365 | -- |
9795b203 HK |
366 | -- GNATbind validates the invocation graph, library graph along with |
367 | -- its cycles, and elaboration order by detecting inconsistencies and | |
368 | -- producing error reports. | |
3eb5e54a HK |
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. | |
69e6ee2f HK |
394 | |
395 | ---------------------------------------- | |
3eb5e54a | 396 | -- Debugging elaboration-order issues -- |
69e6ee2f HK |
397 | ---------------------------------------- |
398 | ||
3eb5e54a HK |
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 | -- | |
9098d477 | 404 | -- -d_A -d_C -d_I -d_L -d_P -d_t -d_T -d_V |
3eb5e54a HK |
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 | -- | |
490ed9ba HK |
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 | -- | |
3eb5e54a HK |
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 | |
16cc65b6 | 440 | -- Elaborate_Units |
3eb5e54a HK |
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 | |
69e6ee2f HK |
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 | |
3eb5e54a HK |
502 | -- Use the library graph and heuristic-based elaboration order when |
503 | -- switch -H (legacy elaboration-order mode enabled). | |
504 | ||
16cc65b6 HK |
505 | if Legacy_Elaboration_Order then |
506 | Binde.Find_Elab_Order (Order, Main_Lib_File); | |
3eb5e54a HK |
507 | |
508 | -- Otherwise use the invocation and library-graph-based elaboration | |
509 | -- order. | |
510 | ||
16cc65b6 | 511 | else |
9795b203 HK |
512 | Invocation_And_Library_Graph_Elaborators.Elaborate_Units |
513 | (Order => Order, | |
514 | Main_Lib_File => Main_Lib_File); | |
9795b203 | 515 | end if; |
69e6ee2f HK |
516 | end Find_Elaboration_Order; |
517 | ||
518 | end Bindo; |