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