Line data Source code
1 : /* do not edit automatically generated by mc from M2BasicBlock. */
2 : /* M2BasicBlock.mod converts a scope block into a list of basic blocks.
3 :
4 : Copyright (C) 2001-2026 Free Software Foundation, Inc.
5 : Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>.
6 :
7 : This file is part of GNU Modula-2.
8 :
9 : GNU Modula-2 is free software; you can redistribute it and/or modify
10 : it under the terms of the GNU General Public License as published by
11 : the Free Software Foundation; either version 3, or (at your option)
12 : any later version.
13 :
14 : GNU Modula-2 is distributed in the hope that it will be useful, but
15 : WITHOUT ANY WARRANTY; without even the implied warranty of
16 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 : General Public License for more details.
18 :
19 : You should have received a copy of the GNU General Public License
20 : along with GNU Modula-2; see the file COPYING3. If not see
21 : <http://www.gnu.org/licenses/>. */
22 :
23 : #include "config.h"
24 : #include "system.h"
25 : #include "gcc-consolidation.h"
26 :
27 : #include <stdbool.h>
28 : # if !defined (PROC_D)
29 : # define PROC_D
30 : typedef void (*PROC_t) (void);
31 : typedef struct { PROC_t proc; } PROC;
32 : # endif
33 :
34 : # if !defined (TRUE)
35 : # define TRUE (1==1)
36 : # endif
37 :
38 : # if !defined (FALSE)
39 : # define FALSE (1==0)
40 : # endif
41 :
42 : # include "GStorage.h"
43 : #if defined(__cplusplus)
44 : # undef NULL
45 : # define NULL 0
46 : #endif
47 : #define _M2BasicBlock_C
48 :
49 : #include "GM2BasicBlock.h"
50 : # include "GStorage.h"
51 : # include "GStrIO.h"
52 : # include "GNumberIO.h"
53 : # include "GM2Debug.h"
54 : # include "GM2Options.h"
55 : # include "GM2Quads.h"
56 : # include "GM2Scope.h"
57 :
58 : typedef struct M2BasicBlock_BasicBlockProc_p M2BasicBlock_BasicBlockProc;
59 :
60 : # define Debugging false
61 : typedef struct M2BasicBlock__T1_r M2BasicBlock__T1;
62 :
63 : typedef M2BasicBlock__T1 *M2BasicBlock_BasicBlock__opaque;
64 :
65 : struct M2BasicBlock__T1_r {
66 : unsigned int Scope;
67 : unsigned int StartQuad;
68 : unsigned int EndQuad;
69 : bool First;
70 : M2BasicBlock_BasicBlock__opaque Right;
71 : M2BasicBlock_BasicBlock__opaque Left;
72 : };
73 :
74 : static M2BasicBlock_BasicBlock__opaque FreeList;
75 : static M2BasicBlock_BasicBlock__opaque HeadOfBasicBlock;
76 :
77 : /*
78 : InitBasicBlocks - converts a list of quadruples as defined by
79 : scope blocks into a set of basic blocks.
80 : All quadruples within this list which are not
81 : reachable are removed.
82 : */
83 :
84 : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocks (M2Scope_ScopeBlock sb);
85 :
86 : /*
87 : InitBasicBlocksFromRange - converts a list of quadruples as defined by
88 : start..end.
89 : All quadruples within this list which are not
90 : reachable are removed.
91 : */
92 :
93 : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocksFromRange (unsigned int ScopeSym, unsigned int start, unsigned int end);
94 :
95 : /*
96 : KillBasicBlocks - destroys the list of Basic Blocks.
97 : */
98 :
99 : extern "C" void M2BasicBlock_KillBasicBlocks (M2BasicBlock_BasicBlock *bb);
100 :
101 : /*
102 : FreeBasicBlocks - destroys the list of Basic Blocks.
103 : */
104 :
105 : extern "C" void M2BasicBlock_FreeBasicBlocks (M2BasicBlock_BasicBlock bb);
106 :
107 : /*
108 : ForeachBasicBlockDo - for each basic block call procedure p.
109 : */
110 :
111 : extern "C" void M2BasicBlock_ForeachBasicBlockDo (M2BasicBlock_BasicBlock bb, M2BasicBlock_BasicBlockProc p);
112 :
113 : /*
114 : GetBasicBlockScope - return the scope associated with the basic block.
115 : */
116 :
117 : extern "C" unsigned int M2BasicBlock_GetBasicBlockScope (M2BasicBlock_BasicBlock bb);
118 :
119 : /*
120 : GetBasicBlockStart - return the quad associated with the start of the basic block.
121 : */
122 :
123 : extern "C" unsigned int M2BasicBlock_GetBasicBlockStart (M2BasicBlock_BasicBlock bb);
124 :
125 : /*
126 : GetBasicBlockEnd - return the quad associated with the end of the basic block.
127 : */
128 :
129 : extern "C" unsigned int M2BasicBlock_GetBasicBlockEnd (M2BasicBlock_BasicBlock bb);
130 :
131 : /*
132 : IsBasicBlockFirst - return TRUE if this basic block is the first in the sequence.
133 : */
134 :
135 : extern "C" bool M2BasicBlock_IsBasicBlockFirst (M2BasicBlock_BasicBlock bb);
136 : static void stop (void);
137 :
138 : /*
139 : New - returns a basic block.
140 : */
141 :
142 : static M2BasicBlock_BasicBlock__opaque New (unsigned int Scope, bool First);
143 :
144 : /*
145 : ConvertQuads2BasicBlock - converts a list of quadruples to a list of
146 : Basic Blocks.
147 : A Basic Block is defined as a list of quadruples
148 : which has only has one entry and exit point.
149 : */
150 :
151 : static void ConvertQuads2BasicBlock (unsigned int ScopeSym, unsigned int Start, unsigned int End);
152 :
153 : /*
154 : StartBB - Initially fills a Basic Block, b, with a start quad Quad.
155 : The Basic Block is then added to the end of Basic Block list.
156 : */
157 :
158 : static void StartBB (M2BasicBlock_BasicBlock__opaque b, unsigned int Quad);
159 :
160 : /*
161 : EndBB - Fills a Basic Block, b, with an end quad Quad.
162 : */
163 :
164 : static void EndBB (M2BasicBlock_BasicBlock__opaque b, unsigned int Quad);
165 :
166 : /*
167 : Add adds a specified element to the end of a queue.
168 : */
169 :
170 : static void Add (M2BasicBlock_BasicBlock__opaque *Head, M2BasicBlock_BasicBlock__opaque b);
171 :
172 : /*
173 : DisplayBasicBlocks - displays the basic block data structure.
174 : */
175 :
176 : static void DisplayBasicBlocks (M2BasicBlock_BasicBlock__opaque bb);
177 :
178 : /*
179 : DisplayBasicBlocks - displays the basic block data structure.
180 : */
181 :
182 : static void DisplayBlock (M2BasicBlock_BasicBlock__opaque b);
183 :
184 0 : static void stop (void)
185 : {
186 0 : }
187 :
188 :
189 : /*
190 : New - returns a basic block.
191 : */
192 :
193 276970649 : static M2BasicBlock_BasicBlock__opaque New (unsigned int Scope, bool First)
194 : {
195 276970649 : M2BasicBlock_BasicBlock__opaque b;
196 :
197 276970649 : if (FreeList == NULL)
198 : {
199 653313 : Storage_ALLOCATE ((void **) &b, sizeof (M2BasicBlock__T1));
200 : }
201 : else
202 : {
203 276317336 : b = FreeList;
204 276317336 : FreeList = FreeList->Right;
205 : }
206 276970649 : M2Debug_Assert (b != NULL);
207 276970649 : b->Scope = Scope;
208 276970649 : b->First = First;
209 276970649 : return b;
210 : /* static analysis guarentees a RETURN statement will be used before here. */
211 : __builtin_unreachable ();
212 : }
213 :
214 :
215 : /*
216 : ConvertQuads2BasicBlock - converts a list of quadruples to a list of
217 : Basic Blocks.
218 : A Basic Block is defined as a list of quadruples
219 : which has only has one entry and exit point.
220 : */
221 :
222 147126079 : static void ConvertQuads2BasicBlock (unsigned int ScopeSym, unsigned int Start, unsigned int End)
223 : {
224 147126079 : bool First;
225 147126079 : bool LastQuadDefMod;
226 147126079 : bool LastQuadConditional;
227 147126079 : bool LastQuadCall;
228 147126079 : bool LastQuadReturn;
229 147126079 : unsigned int Quad;
230 147126079 : M2BasicBlock_BasicBlock__opaque CurrentBB;
231 147126079 : M2BasicBlock_BasicBlock__opaque LastBB;
232 :
233 147126079 : if (Debugging)
234 : {
235 : StrIO_WriteString ((const char *) "Enter ConvertQuads2BasicBlock", 29);
236 : StrIO_WriteLn ();
237 : M2Quads_DisplayQuadRange (ScopeSym, Start, End);
238 : }
239 : /*
240 : Algorithm to perform Basic Block:
241 :
242 : For every quadruple establish a set of leaders.
243 : A leader is defined as a quadruple which is
244 : either:
245 :
246 : (i) The first quadruple.
247 : (ii) Any quadruple which is the target of a jump or unconditional jump.
248 : (iii) Any statement which follows a conditional jump
249 :
250 : For each leader construct a basic block.
251 : A Basic Block starts with a leader quadruple and ends with either:
252 :
253 : (i) Another leader
254 : (ii) An unconditional Jump.
255 :
256 : Any quadruples that do not fall into a Basic Block can be thrown away
257 : since they will never be executed.
258 : */
259 147126079 : LastBB = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
260 147126079 : CurrentBB = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
261 147126079 : Quad = Start;
262 147126079 : LastQuadConditional = true; /* Force Rule (i). */
263 147126079 : LastQuadCall = false; /* Force Rule (i). */
264 147126079 : LastQuadReturn = false;
265 147126079 : LastQuadDefMod = false;
266 147126079 : First = true;
267 : /* Scan all quadruples. */
268 665753025 : while ((Quad <= End) && (Quad != 0))
269 : {
270 518626946 : if (Quad == 200)
271 : {
272 518626946 : stop ();
273 : }
274 518626946 : if ((((LastQuadConditional || LastQuadCall) || LastQuadReturn) || LastQuadDefMod) || (M2Quads_IsReferenced (Quad)))
275 : {
276 : /* Rule (ii) */
277 276970649 : CurrentBB = New (ScopeSym, First); /* Get a new Basic Block. */
278 : /* At least one quad in this Basic Block. */
279 553941298 : StartBB (CurrentBB, Quad);
280 276970649 : EndBB (CurrentBB, Quad);
281 276970649 : First = false;
282 : }
283 241656297 : else if (CurrentBB != NULL)
284 : {
285 : /* avoid dangling else. */
286 : /* We have a Basic Block - therefore add quad to this Block */
287 241490751 : EndBB (CurrentBB, Quad);
288 : }
289 165546 : else if (M2Quads_IsPseudoQuad (Quad))
290 : {
291 : /* avoid dangling else. */
292 : /* must not be thrown away. */
293 5454 : EndBB (LastBB, Quad);
294 : }
295 160092 : else if ((((((((M2Quads_IsReturn (Quad)) || (M2Quads_IsKillLocalVar (Quad))) || (M2Quads_IsCatchEnd (Quad))) || (M2Quads_IsCatchBegin (Quad))) || (M2Quads_IsInitStart (Quad))) || (M2Quads_IsInitEnd (Quad))) || (M2Quads_IsFinallyStart (Quad))) || (M2Quads_IsFinallyEnd (Quad)))
296 : {
297 : /* avoid dangling else. */
298 : /* We must leave these quads alone. */
299 40726 : EndBB (LastBB, Quad);
300 : }
301 119366 : else if (M2Quads_IsConditionalBooleanQuad (Quad))
302 : {
303 : /* avoid dangling else. */
304 : /*
305 : ELSIF IsInitialisingConst(Quad)
306 : THEN
307 : But we leave remaining constant quads alone.
308 : EndBB(LastBB, Quad)
309 : */
310 658 : M2Quads_SubQuad (Quad);
311 : }
312 : else
313 : {
314 : /* avoid dangling else. */
315 : /* Remove this Quad since it will never be reached. */
316 118708 : M2Quads_SubQuad (Quad);
317 : }
318 518626946 : LastQuadConditional = M2Quads_IsConditional (Quad);
319 518626946 : LastQuadCall = M2Quads_IsCall (Quad);
320 518626946 : LastQuadReturn = M2Quads_IsReturn (Quad);
321 518626946 : LastQuadDefMod = M2Quads_IsDefOrModFile (Quad);
322 518626946 : if (M2Quads_IsUnConditional (Quad))
323 : {
324 20327899 : LastBB = CurrentBB;
325 20327899 : CurrentBB = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
326 : }
327 518626946 : Quad = M2Quads_GetNextQuad (Quad);
328 : }
329 147126079 : if (Debugging)
330 : {
331 : StrIO_WriteString ((const char *) "Exit ConvertQuads2BasicBlock", 28);
332 : StrIO_WriteLn ();
333 : M2Quads_DisplayQuadRange (ScopeSym, Start, End);
334 : }
335 147126079 : }
336 :
337 :
338 : /*
339 : StartBB - Initially fills a Basic Block, b, with a start quad Quad.
340 : The Basic Block is then added to the end of Basic Block list.
341 : */
342 :
343 276970649 : static void StartBB (M2BasicBlock_BasicBlock__opaque b, unsigned int Quad)
344 : {
345 276970649 : b->StartQuad = Quad;
346 276970649 : b->EndQuad = Quad;
347 276970649 : Add (&HeadOfBasicBlock, b); /* Add b to the end of the Basic Block list */
348 0 : }
349 :
350 :
351 : /*
352 : EndBB - Fills a Basic Block, b, with an end quad Quad.
353 : */
354 :
355 518507580 : static void EndBB (M2BasicBlock_BasicBlock__opaque b, unsigned int Quad)
356 : {
357 276970649 : b->EndQuad = Quad;
358 241536931 : }
359 :
360 :
361 : /*
362 : Add adds a specified element to the end of a queue.
363 : */
364 :
365 276970649 : static void Add (M2BasicBlock_BasicBlock__opaque *Head, M2BasicBlock_BasicBlock__opaque b)
366 : {
367 276970649 : if ((*Head) == NULL)
368 : {
369 5949215 : (*Head) = b;
370 5949215 : b->Left = b;
371 5949215 : b->Right = b;
372 : }
373 : else
374 : {
375 271021434 : b->Right = (*Head);
376 271021434 : b->Left = (*Head)->Left;
377 271021434 : (*Head)->Left->Right = b;
378 271021434 : (*Head)->Left = b;
379 : }
380 276970649 : }
381 :
382 :
383 : /*
384 : DisplayBasicBlocks - displays the basic block data structure.
385 : */
386 :
387 0 : static void DisplayBasicBlocks (M2BasicBlock_BasicBlock__opaque bb)
388 : {
389 0 : M2BasicBlock_BasicBlock__opaque b;
390 :
391 0 : b = bb;
392 0 : StrIO_WriteString ((const char *) "quadruples", 10);
393 0 : StrIO_WriteLn ();
394 0 : if (b != NULL)
395 : {
396 0 : do {
397 0 : DisplayBlock (b);
398 0 : b = b->Right;
399 0 : } while (! (b == bb));
400 : }
401 0 : }
402 :
403 :
404 : /*
405 : DisplayBasicBlocks - displays the basic block data structure.
406 : */
407 :
408 0 : static void DisplayBlock (M2BasicBlock_BasicBlock__opaque b)
409 : {
410 0 : StrIO_WriteString ((const char *) " start ", 7);
411 0 : NumberIO_WriteCard (b->StartQuad, 6);
412 0 : StrIO_WriteString ((const char *) " end ", 7);
413 0 : NumberIO_WriteCard (b->EndQuad, 6);
414 0 : }
415 :
416 :
417 : /*
418 : InitBasicBlocks - converts a list of quadruples as defined by
419 : scope blocks into a set of basic blocks.
420 : All quadruples within this list which are not
421 : reachable are removed.
422 : */
423 :
424 2435925 : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocks (M2Scope_ScopeBlock sb)
425 : {
426 2435925 : HeadOfBasicBlock = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
427 2435925 : M2Scope_ForeachScopeBlockDo3 (sb, (M2Scope_ScopeProcedure3) {(M2Scope_ScopeProcedure3_t) ConvertQuads2BasicBlock});
428 2435925 : return static_cast<M2BasicBlock_BasicBlock> (HeadOfBasicBlock);
429 : /* static analysis guarentees a RETURN statement will be used before here. */
430 : __builtin_unreachable ();
431 : }
432 :
433 :
434 : /*
435 : InitBasicBlocksFromRange - converts a list of quadruples as defined by
436 : start..end.
437 : All quadruples within this list which are not
438 : reachable are removed.
439 : */
440 :
441 3513290 : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocksFromRange (unsigned int ScopeSym, unsigned int start, unsigned int end)
442 : {
443 3513290 : HeadOfBasicBlock = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
444 3513290 : ConvertQuads2BasicBlock (ScopeSym, start, end);
445 3513290 : if (Debugging)
446 : {
447 : DisplayBasicBlocks (HeadOfBasicBlock);
448 : }
449 3513290 : return static_cast<M2BasicBlock_BasicBlock> (HeadOfBasicBlock);
450 : /* static analysis guarentees a RETURN statement will be used before here. */
451 : __builtin_unreachable ();
452 : }
453 :
454 :
455 : /*
456 : KillBasicBlocks - destroys the list of Basic Blocks.
457 : */
458 :
459 2460212 : extern "C" void M2BasicBlock_KillBasicBlocks (M2BasicBlock_BasicBlock *bb)
460 : {
461 2460212 : M2BasicBlock_FreeBasicBlocks ((*bb));
462 2460212 : (*bb) = static_cast<M2BasicBlock_BasicBlock> (NULL);
463 2460212 : }
464 :
465 :
466 : /*
467 : FreeBasicBlocks - destroys the list of Basic Blocks.
468 : */
469 :
470 5949041 : extern "C" void M2BasicBlock_FreeBasicBlocks (M2BasicBlock_BasicBlock bb)
471 : {
472 5949041 : M2BasicBlock_BasicBlock__opaque b;
473 5949041 : M2BasicBlock_BasicBlock__opaque c;
474 :
475 5949041 : if (bb != NULL)
476 : {
477 : b = static_cast<M2BasicBlock_BasicBlock__opaque> (bb);
478 276969929 : do {
479 276969929 : c = static_cast<M2BasicBlock_BasicBlock__opaque> (bb)->Right;
480 276969929 : static_cast<M2BasicBlock_BasicBlock__opaque> (bb)->Right = FreeList;
481 276969929 : FreeList = static_cast<M2BasicBlock_BasicBlock__opaque> (bb);
482 276969929 : bb = static_cast<M2BasicBlock_BasicBlock> (c);
483 276969929 : } while (! (bb == b));
484 : }
485 5949041 : }
486 :
487 :
488 : /*
489 : ForeachBasicBlockDo - for each basic block call procedure p.
490 : */
491 :
492 1618559 : extern "C" void M2BasicBlock_ForeachBasicBlockDo (M2BasicBlock_BasicBlock bb, M2BasicBlock_BasicBlockProc p)
493 : {
494 1618559 : M2BasicBlock_BasicBlock__opaque b;
495 :
496 1618559 : if (bb != NULL)
497 : {
498 : b = static_cast<M2BasicBlock_BasicBlock__opaque> (bb);
499 91510590 : do {
500 91510590 : (*p.proc) (static_cast<M2BasicBlock_BasicBlock> (b));
501 91510416 : b = b->Right;
502 91510416 : } while (! (b == bb));
503 : }
504 1618385 : }
505 :
506 :
507 : /*
508 : GetBasicBlockScope - return the scope associated with the basic block.
509 : */
510 :
511 0 : extern "C" unsigned int M2BasicBlock_GetBasicBlockScope (M2BasicBlock_BasicBlock bb)
512 : {
513 0 : return static_cast<M2BasicBlock_BasicBlock__opaque> (bb)->Scope;
514 : /* static analysis guarentees a RETURN statement will be used before here. */
515 : __builtin_unreachable ();
516 : }
517 :
518 :
519 : /*
520 : GetBasicBlockStart - return the quad associated with the start of the basic block.
521 : */
522 :
523 91510590 : extern "C" unsigned int M2BasicBlock_GetBasicBlockStart (M2BasicBlock_BasicBlock bb)
524 : {
525 91510590 : return static_cast<M2BasicBlock_BasicBlock__opaque> (bb)->StartQuad;
526 : /* static analysis guarentees a RETURN statement will be used before here. */
527 : __builtin_unreachable ();
528 : }
529 :
530 :
531 : /*
532 : GetBasicBlockEnd - return the quad associated with the end of the basic block.
533 : */
534 :
535 91510590 : extern "C" unsigned int M2BasicBlock_GetBasicBlockEnd (M2BasicBlock_BasicBlock bb)
536 : {
537 91510590 : return static_cast<M2BasicBlock_BasicBlock__opaque> (bb)->EndQuad;
538 : /* static analysis guarentees a RETURN statement will be used before here. */
539 : __builtin_unreachable ();
540 : }
541 :
542 :
543 : /*
544 : IsBasicBlockFirst - return TRUE if this basic block is the first in the sequence.
545 : */
546 :
547 5208 : extern "C" bool M2BasicBlock_IsBasicBlockFirst (M2BasicBlock_BasicBlock bb)
548 : {
549 5208 : return static_cast<M2BasicBlock_BasicBlock__opaque> (bb)->First;
550 : /* static analysis guarentees a RETURN statement will be used before here. */
551 : __builtin_unreachable ();
552 : }
553 :
554 14952 : extern "C" void _M2_M2BasicBlock_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
555 : {
556 14952 : FreeList = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
557 14952 : }
558 :
559 0 : extern "C" void _M2_M2BasicBlock_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
560 : {
561 0 : }
|
