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 283287569 : static M2BasicBlock_BasicBlock__opaque New (unsigned int Scope, bool First)
194 : {
195 283287569 : M2BasicBlock_BasicBlock__opaque b;
196 :
197 283287569 : if (FreeList == NULL)
198 : {
199 682435 : Storage_ALLOCATE ((void **) &b, sizeof (M2BasicBlock__T1));
200 : }
201 : else
202 : {
203 282605134 : b = FreeList;
204 282605134 : FreeList = FreeList->Right;
205 : }
206 283287569 : M2Debug_Assert (b != NULL);
207 283287569 : b->Scope = Scope;
208 283287569 : b->First = First;
209 283287569 : 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 150431955 : static void ConvertQuads2BasicBlock (unsigned int ScopeSym, unsigned int Start, unsigned int End)
223 : {
224 150431955 : bool First;
225 150431955 : bool LastQuadDefMod;
226 150431955 : bool LastQuadConditional;
227 150431955 : bool LastQuadCall;
228 150431955 : bool LastQuadReturn;
229 150431955 : unsigned int Quad;
230 150431955 : M2BasicBlock_BasicBlock__opaque CurrentBB;
231 150431955 : M2BasicBlock_BasicBlock__opaque LastBB;
232 :
233 150431955 : 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 150431955 : LastBB = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
260 150431955 : CurrentBB = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
261 150431955 : Quad = Start;
262 150431955 : LastQuadConditional = true; /* Force Rule (i). */
263 150431955 : LastQuadCall = false; /* Force Rule (i). */
264 150431955 : LastQuadReturn = false;
265 150431955 : LastQuadDefMod = false;
266 150431955 : First = true;
267 : /* Scan all quadruples. */
268 681283945 : while ((Quad <= End) && (Quad != 0))
269 : {
270 530851990 : if (Quad == 200)
271 : {
272 530851990 : stop ();
273 : }
274 530851990 : if ((((LastQuadConditional || LastQuadCall) || LastQuadReturn) || LastQuadDefMod) || (M2Quads_IsReferenced (Quad)))
275 : {
276 : /* Rule (ii) */
277 283287569 : CurrentBB = New (ScopeSym, First); /* Get a new Basic Block. */
278 : /* At least one quad in this Basic Block. */
279 566575138 : StartBB (CurrentBB, Quad);
280 283287569 : EndBB (CurrentBB, Quad);
281 283287569 : First = false;
282 : }
283 247564421 : else if (CurrentBB != NULL)
284 : {
285 : /* avoid dangling else. */
286 : /* We have a Basic Block - therefore add quad to this Block */
287 247395131 : EndBB (CurrentBB, Quad);
288 : }
289 169290 : else if (M2Quads_IsPseudoQuad (Quad))
290 : {
291 : /* avoid dangling else. */
292 : /* must not be thrown away. */
293 5454 : EndBB (LastBB, Quad);
294 : }
295 163836 : 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 41838 : EndBB (LastBB, Quad);
300 : }
301 121998 : 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 121340 : M2Quads_SubQuad (Quad);
317 : }
318 530851990 : LastQuadConditional = M2Quads_IsConditional (Quad);
319 530851990 : LastQuadCall = M2Quads_IsCall (Quad);
320 530851990 : LastQuadReturn = M2Quads_IsReturn (Quad);
321 530851990 : LastQuadDefMod = M2Quads_IsDefOrModFile (Quad);
322 530851990 : if (M2Quads_IsUnConditional (Quad))
323 : {
324 20785429 : LastBB = CurrentBB;
325 20785429 : CurrentBB = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
326 : }
327 530851990 : Quad = M2Quads_GetNextQuad (Quad);
328 : }
329 150431955 : if (Debugging)
330 : {
331 : StrIO_WriteString ((const char *) "Exit ConvertQuads2BasicBlock", 28);
332 : StrIO_WriteLn ();
333 : M2Quads_DisplayQuadRange (ScopeSym, Start, End);
334 : }
335 150431955 : }
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 283287569 : static void StartBB (M2BasicBlock_BasicBlock__opaque b, unsigned int Quad)
344 : {
345 283287569 : b->StartQuad = Quad;
346 283287569 : b->EndQuad = Quad;
347 283287569 : 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 530729992 : static void EndBB (M2BasicBlock_BasicBlock__opaque b, unsigned int Quad)
356 : {
357 283287569 : b->EndQuad = Quad;
358 247442423 : }
359 :
360 :
361 : /*
362 : Add adds a specified element to the end of a queue.
363 : */
364 :
365 283287569 : static void Add (M2BasicBlock_BasicBlock__opaque *Head, M2BasicBlock_BasicBlock__opaque b)
366 : {
367 283287569 : if ((*Head) == NULL)
368 : {
369 6207391 : (*Head) = b;
370 6207391 : b->Left = b;
371 6207391 : b->Right = b;
372 : }
373 : else
374 : {
375 277080178 : b->Right = (*Head);
376 277080178 : b->Left = (*Head)->Left;
377 277080178 : (*Head)->Left->Right = b;
378 277080178 : (*Head)->Left = b;
379 : }
380 283287569 : }
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 2546735 : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocks (M2Scope_ScopeBlock sb)
425 : {
426 2546735 : HeadOfBasicBlock = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
427 2546735 : M2Scope_ForeachScopeBlockDo3 (sb, (M2Scope_ScopeProcedure3) {(M2Scope_ScopeProcedure3_t) ConvertQuads2BasicBlock});
428 2546735 : 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 3660656 : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocksFromRange (unsigned int ScopeSym, unsigned int start, unsigned int end)
442 : {
443 3660656 : HeadOfBasicBlock = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
444 3660656 : ConvertQuads2BasicBlock (ScopeSym, start, end);
445 3660656 : if (Debugging)
446 : {
447 : DisplayBasicBlocks (HeadOfBasicBlock);
448 : }
449 3660656 : 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 2571026 : extern "C" void M2BasicBlock_KillBasicBlocks (M2BasicBlock_BasicBlock *bb)
460 : {
461 2571026 : M2BasicBlock_FreeBasicBlocks ((*bb));
462 2571026 : (*bb) = static_cast<M2BasicBlock_BasicBlock> (NULL);
463 2571026 : }
464 :
465 :
466 : /*
467 : FreeBasicBlocks - destroys the list of Basic Blocks.
468 : */
469 :
470 6207217 : extern "C" void M2BasicBlock_FreeBasicBlocks (M2BasicBlock_BasicBlock bb)
471 : {
472 6207217 : M2BasicBlock_BasicBlock__opaque b;
473 6207217 : M2BasicBlock_BasicBlock__opaque c;
474 :
475 6207217 : if (bb != NULL)
476 : {
477 : b = static_cast<M2BasicBlock_BasicBlock__opaque> (bb);
478 283286849 : do {
479 283286849 : c = static_cast<M2BasicBlock_BasicBlock__opaque> (bb)->Right;
480 283286849 : static_cast<M2BasicBlock_BasicBlock__opaque> (bb)->Right = FreeList;
481 283286849 : FreeList = static_cast<M2BasicBlock_BasicBlock__opaque> (bb);
482 283286849 : bb = static_cast<M2BasicBlock_BasicBlock> (c);
483 283286849 : } while (! (bb == b));
484 : }
485 6207217 : }
486 :
487 :
488 : /*
489 : ForeachBasicBlockDo - for each basic block call procedure p.
490 : */
491 :
492 1688183 : extern "C" void M2BasicBlock_ForeachBasicBlockDo (M2BasicBlock_BasicBlock bb, M2BasicBlock_BasicBlockProc p)
493 : {
494 1688183 : M2BasicBlock_BasicBlock__opaque b;
495 :
496 1688183 : if (bb != NULL)
497 : {
498 : b = static_cast<M2BasicBlock_BasicBlock__opaque> (bb);
499 93563338 : do {
500 93563338 : (*p.proc) (static_cast<M2BasicBlock_BasicBlock> (b));
501 93563164 : b = b->Right;
502 93563164 : } while (! (b == bb));
503 : }
504 1688009 : }
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 93563338 : extern "C" unsigned int M2BasicBlock_GetBasicBlockStart (M2BasicBlock_BasicBlock bb)
524 : {
525 93563338 : 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 93563338 : extern "C" unsigned int M2BasicBlock_GetBasicBlockEnd (M2BasicBlock_BasicBlock bb)
536 : {
537 93563338 : 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 16268 : extern "C" void _M2_M2BasicBlock_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
555 : {
556 16268 : FreeList = static_cast<M2BasicBlock_BasicBlock__opaque> (NULL);
557 16268 : }
558 :
559 0 : extern "C" void _M2_M2BasicBlock_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
560 : {
561 0 : }
|
