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 <stdbool.h>
26 : : # if !defined (PROC_D)
27 : : # define PROC_D
28 : : typedef void (*PROC_t) (void);
29 : : typedef struct { PROC_t proc; } PROC;
30 : : # endif
31 : :
32 : : # if !defined (TRUE)
33 : : # define TRUE (1==1)
34 : : # endif
35 : :
36 : : # if !defined (FALSE)
37 : : # define FALSE (1==0)
38 : : # endif
39 : :
40 : : # include "GStorage.h"
41 : : #if defined(__cplusplus)
42 : : # undef NULL
43 : : # define NULL 0
44 : : #endif
45 : : #define _M2BasicBlock_H
46 : : #define _M2BasicBlock_C
47 : :
48 : : # include "GStorage.h"
49 : : # include "GStrIO.h"
50 : : # include "GNumberIO.h"
51 : : # include "GM2Debug.h"
52 : : # include "GM2Options.h"
53 : : # include "GM2Quads.h"
54 : : # include "GM2Scope.h"
55 : :
56 : : typedef struct M2BasicBlock_BasicBlockProc_p M2BasicBlock_BasicBlockProc;
57 : :
58 : : # define Debugging false
59 : : typedef struct M2BasicBlock__T1_r M2BasicBlock__T1;
60 : :
61 : : typedef M2BasicBlock__T1 *M2BasicBlock_BasicBlock;
62 : :
63 : : typedef void (*M2BasicBlock_BasicBlockProc_t) (unsigned int, unsigned int);
64 : : struct M2BasicBlock_BasicBlockProc_p { M2BasicBlock_BasicBlockProc_t proc; };
65 : :
66 : : struct M2BasicBlock__T1_r {
67 : : unsigned int StartQuad;
68 : : unsigned int EndQuad;
69 : : M2BasicBlock_BasicBlock Right;
70 : : M2BasicBlock_BasicBlock Left;
71 : : };
72 : :
73 : : static M2BasicBlock_BasicBlock FreeList;
74 : : static M2BasicBlock_BasicBlock HeadOfBasicBlock;
75 : :
76 : : /*
77 : : InitBasicBlocks - converts a list of quadruples as defined by
78 : : scope blocks into a set of basic blocks.
79 : : All quadruples within this list which are not
80 : : reachable are removed.
81 : : */
82 : :
83 : : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocks (M2Scope_ScopeBlock sb);
84 : :
85 : : /*
86 : : InitBasicBlocksFromRange - converts a list of quadruples as defined by
87 : : start..end.
88 : : All quadruples within this list which are not
89 : : reachable are removed.
90 : : */
91 : :
92 : : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocksFromRange (unsigned int ScopeSym, unsigned int start, unsigned int end);
93 : :
94 : : /*
95 : : KillBasicBlocks - destroys the list of Basic Blocks.
96 : : */
97 : :
98 : : extern "C" void M2BasicBlock_KillBasicBlocks (M2BasicBlock_BasicBlock *bb);
99 : :
100 : : /*
101 : : FreeBasicBlocks - destroys the list of Basic Blocks.
102 : : */
103 : :
104 : : extern "C" void M2BasicBlock_FreeBasicBlocks (M2BasicBlock_BasicBlock bb);
105 : :
106 : : /*
107 : : ForeachBasicBlockDo - for each basic block call procedure, p.
108 : : */
109 : :
110 : : extern "C" void M2BasicBlock_ForeachBasicBlockDo (M2BasicBlock_BasicBlock bb, M2BasicBlock_BasicBlockProc p);
111 : :
112 : : /*
113 : : New - returns a basic block.
114 : : */
115 : :
116 : : static M2BasicBlock_BasicBlock New (void);
117 : :
118 : : /*
119 : : ConvertQuads2BasicBlock - converts a list of quadruples to a list of
120 : : Basic Blocks.
121 : : A Basic Block is defined as a list of quadruples
122 : : which has only has one entry and exit point.
123 : : */
124 : :
125 : : static void ConvertQuads2BasicBlock (unsigned int ScopeSym, unsigned int Start, unsigned int End);
126 : :
127 : : /*
128 : : StartBB - Initially fills a Basic Block, b, with a start quad Quad.
129 : : The Basic Block is then added to the end of Basic Block list.
130 : : */
131 : :
132 : : static void StartBB (M2BasicBlock_BasicBlock b, unsigned int Quad);
133 : :
134 : : /*
135 : : EndBB - Fills a Basic Block, b, with an end quad Quad.
136 : : */
137 : :
138 : : static void EndBB (M2BasicBlock_BasicBlock b, unsigned int Quad);
139 : :
140 : : /*
141 : : Add adds a specified element to the end of a queue.
142 : : */
143 : :
144 : : static void Add (M2BasicBlock_BasicBlock *Head, M2BasicBlock_BasicBlock b);
145 : :
146 : : /*
147 : : DisplayBasicBlocks - displays the basic block data structure.
148 : : */
149 : :
150 : : static void DisplayBasicBlocks (M2BasicBlock_BasicBlock bb);
151 : :
152 : : /*
153 : : DisplayBasicBlocks - displays the basic block data structure.
154 : : */
155 : :
156 : : static void DisplayBlock (M2BasicBlock_BasicBlock b);
157 : :
158 : :
159 : : /*
160 : : New - returns a basic block.
161 : : */
162 : :
163 : 7841773 : static M2BasicBlock_BasicBlock New (void)
164 : : {
165 : 7841773 : M2BasicBlock_BasicBlock b;
166 : :
167 : 7841773 : if (FreeList == NULL)
168 : : {
169 : 180312 : Storage_ALLOCATE ((void **) &b, sizeof (M2BasicBlock__T1));
170 : : }
171 : : else
172 : : {
173 : 7661461 : b = FreeList;
174 : 7661461 : FreeList = FreeList->Right;
175 : : }
176 : 7841773 : M2Debug_Assert (b != NULL);
177 : 7841773 : return b;
178 : : /* static analysis guarentees a RETURN statement will be used before here. */
179 : : __builtin_unreachable ();
180 : : }
181 : :
182 : :
183 : : /*
184 : : ConvertQuads2BasicBlock - converts a list of quadruples to a list of
185 : : Basic Blocks.
186 : : A Basic Block is defined as a list of quadruples
187 : : which has only has one entry and exit point.
188 : : */
189 : :
190 : 2158394 : static void ConvertQuads2BasicBlock (unsigned int ScopeSym, unsigned int Start, unsigned int End)
191 : : {
192 : 2158394 : bool LastQuadDefMod;
193 : 2158394 : bool LastQuadConditional;
194 : 2158394 : bool LastQuadCall;
195 : 2158394 : bool LastQuadReturn;
196 : 2158394 : unsigned int Quad;
197 : 2158394 : M2BasicBlock_BasicBlock CurrentBB;
198 : 2158394 : M2BasicBlock_BasicBlock LastBB;
199 : :
200 : 2158394 : if (Debugging)
201 : : {
202 : : M2Quads_DisplayQuadRange (ScopeSym, Start, End);
203 : : }
204 : : /*
205 : : Algorithm to perform Basic Block:
206 : :
207 : : For every quadruple establish a set of leaders.
208 : : A Leader is defined as a quadruple which is
209 : : either:
210 : :
211 : : (i) The first quadruple.
212 : : (ii) Any quadruple which is the target of a jump or unconditional jump.
213 : : (iii) Any statement which follows a conditional jump
214 : :
215 : : For each leader construct a basic block.
216 : : A Basic Block starts with a leader quadruple and ends with either:
217 : :
218 : : (i) Another Leader
219 : : (ii) An unconditional Jump.
220 : :
221 : : Any quadruples that do not fall into a Basic Block can be thrown away
222 : : since they will never be executed.
223 : : */
224 : 2158394 : LastBB = NULL;
225 : 2158394 : CurrentBB = NULL;
226 : 2158394 : Quad = Start;
227 : 2158394 : LastQuadConditional = true; /* Force Rule (i) */
228 : 2158394 : LastQuadCall = false; /* Force Rule (i) */
229 : 2158394 : LastQuadReturn = false;
230 : 2158394 : LastQuadDefMod = false;
231 : : /* Scan all quadruples */
232 : 38997110 : while ((Quad <= End) && (Quad != 0))
233 : : {
234 : 36838716 : if ((((LastQuadConditional || LastQuadCall) || LastQuadReturn) || LastQuadDefMod) || (M2Quads_IsReferenced (Quad)))
235 : : {
236 : : /* Rule (ii) */
237 : 7841773 : CurrentBB = New (); /* Get a new Basic Block */
238 : : /* At least one quad in this Basic Block */
239 : 15683546 : StartBB (CurrentBB, Quad);
240 : 7841773 : EndBB (CurrentBB, Quad);
241 : : }
242 : 28996943 : else if (CurrentBB != NULL)
243 : : {
244 : : /* avoid dangling else. */
245 : : /* We have a Basic Block - therefore add quad to this Block */
246 : 28917862 : EndBB (CurrentBB, Quad);
247 : : }
248 : 79081 : else if (M2Quads_IsPseudoQuad (Quad))
249 : : {
250 : : /* avoid dangling else. */
251 : : /* must not be thrown away. */
252 : 432 : EndBB (LastBB, Quad);
253 : : }
254 : 78649 : 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)))
255 : : {
256 : : /* avoid dangling else. */
257 : : /* we must leave these quads alone */
258 : 9538 : EndBB (LastBB, Quad);
259 : : }
260 : 69111 : else if (M2Quads_IsInitialisingConst (Quad))
261 : : {
262 : : /* avoid dangling else. */
263 : : /* we must leave these quads alone */
264 : 12 : EndBB (LastBB, Quad);
265 : : }
266 : : else
267 : : {
268 : : /* avoid dangling else. */
269 : : /* remove this Quad since it will never be reached */
270 : 69099 : M2Quads_SubQuad (Quad);
271 : : }
272 : 36838716 : LastQuadConditional = M2Quads_IsConditional (Quad);
273 : 36838716 : LastQuadCall = M2Quads_IsCall (Quad);
274 : 36838716 : LastQuadReturn = M2Quads_IsReturn (Quad);
275 : 36838716 : LastQuadDefMod = M2Quads_IsDefOrModFile (Quad);
276 : 36838716 : if (M2Quads_IsUnConditional (Quad))
277 : : {
278 : 3403677 : LastBB = CurrentBB;
279 : 3403677 : CurrentBB = NULL;
280 : : }
281 : 36838716 : Quad = M2Quads_GetNextQuad (Quad);
282 : : }
283 : 2158394 : }
284 : :
285 : :
286 : : /*
287 : : StartBB - Initially fills a Basic Block, b, with a start quad Quad.
288 : : The Basic Block is then added to the end of Basic Block list.
289 : : */
290 : :
291 : 7841773 : static void StartBB (M2BasicBlock_BasicBlock b, unsigned int Quad)
292 : : {
293 : 7841773 : b->StartQuad = Quad;
294 : 7841773 : b->EndQuad = Quad;
295 : 7841773 : Add (&HeadOfBasicBlock, b); /* Add b to the end of the Basic Block list */
296 : 0 : }
297 : :
298 : :
299 : : /*
300 : : EndBB - Fills a Basic Block, b, with an end quad Quad.
301 : : */
302 : :
303 : 36769617 : static void EndBB (M2BasicBlock_BasicBlock b, unsigned int Quad)
304 : : {
305 : 36769617 : b->EndQuad = Quad;
306 : 36769617 : }
307 : :
308 : :
309 : : /*
310 : : Add adds a specified element to the end of a queue.
311 : : */
312 : :
313 : 7841773 : static void Add (M2BasicBlock_BasicBlock *Head, M2BasicBlock_BasicBlock b)
314 : : {
315 : 7841773 : if ((*Head) == NULL)
316 : : {
317 : 2158394 : (*Head) = b;
318 : 2158394 : b->Left = b;
319 : 2158394 : b->Right = b;
320 : : }
321 : : else
322 : : {
323 : 5683379 : b->Right = (*Head);
324 : 5683379 : b->Left = (*Head)->Left;
325 : 5683379 : (*Head)->Left->Right = b;
326 : 5683379 : (*Head)->Left = b;
327 : : }
328 : 7841773 : }
329 : :
330 : :
331 : : /*
332 : : DisplayBasicBlocks - displays the basic block data structure.
333 : : */
334 : :
335 : 0 : static void DisplayBasicBlocks (M2BasicBlock_BasicBlock bb)
336 : : {
337 : 0 : M2BasicBlock_BasicBlock b;
338 : :
339 : 0 : b = bb;
340 : 0 : StrIO_WriteString ((const char *) "quadruples", 10);
341 : 0 : StrIO_WriteLn ();
342 : 0 : if (b != NULL)
343 : : {
344 : 0 : do {
345 : 0 : DisplayBlock (b);
346 : 0 : b = b->Right;
347 : 0 : } while (! (b == bb));
348 : : }
349 : 0 : }
350 : :
351 : :
352 : : /*
353 : : DisplayBasicBlocks - displays the basic block data structure.
354 : : */
355 : :
356 : 0 : static void DisplayBlock (M2BasicBlock_BasicBlock b)
357 : : {
358 : 0 : StrIO_WriteString ((const char *) " start ", 7);
359 : 0 : NumberIO_WriteCard (b->StartQuad, 6);
360 : 0 : StrIO_WriteString ((const char *) " end ", 7);
361 : 0 : NumberIO_WriteCard (b->EndQuad, 6);
362 : 0 : }
363 : :
364 : :
365 : : /*
366 : : InitBasicBlocks - converts a list of quadruples as defined by
367 : : scope blocks into a set of basic blocks.
368 : : All quadruples within this list which are not
369 : : reachable are removed.
370 : : */
371 : :
372 : 0 : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocks (M2Scope_ScopeBlock sb)
373 : : {
374 : 0 : HeadOfBasicBlock = NULL;
375 : 0 : M2Scope_ForeachScopeBlockDo3 (sb, (M2Scope_ScopeProcedure3) {(M2Scope_ScopeProcedure3_t) ConvertQuads2BasicBlock});
376 : 0 : return HeadOfBasicBlock;
377 : : /* static analysis guarentees a RETURN statement will be used before here. */
378 : : __builtin_unreachable ();
379 : : }
380 : :
381 : :
382 : : /*
383 : : InitBasicBlocksFromRange - converts a list of quadruples as defined by
384 : : start..end.
385 : : All quadruples within this list which are not
386 : : reachable are removed.
387 : : */
388 : :
389 : 2158394 : extern "C" M2BasicBlock_BasicBlock M2BasicBlock_InitBasicBlocksFromRange (unsigned int ScopeSym, unsigned int start, unsigned int end)
390 : : {
391 : 2158394 : HeadOfBasicBlock = NULL;
392 : 2158394 : ConvertQuads2BasicBlock (ScopeSym, start, end);
393 : 2158394 : if (Debugging)
394 : : {
395 : : DisplayBasicBlocks (HeadOfBasicBlock);
396 : : }
397 : 2158394 : return HeadOfBasicBlock;
398 : : /* static analysis guarentees a RETURN statement will be used before here. */
399 : : __builtin_unreachable ();
400 : : }
401 : :
402 : :
403 : : /*
404 : : KillBasicBlocks - destroys the list of Basic Blocks.
405 : : */
406 : :
407 : 2258 : extern "C" void M2BasicBlock_KillBasicBlocks (M2BasicBlock_BasicBlock *bb)
408 : : {
409 : 2258 : M2BasicBlock_FreeBasicBlocks ((*bb));
410 : 2258 : (*bb) = NULL;
411 : 2258 : }
412 : :
413 : :
414 : : /*
415 : : FreeBasicBlocks - destroys the list of Basic Blocks.
416 : : */
417 : :
418 : 2158394 : extern "C" void M2BasicBlock_FreeBasicBlocks (M2BasicBlock_BasicBlock bb)
419 : : {
420 : 2158394 : M2BasicBlock_BasicBlock b;
421 : 2158394 : M2BasicBlock_BasicBlock c;
422 : :
423 : 2158394 : if (bb != NULL)
424 : : {
425 : : b = bb;
426 : 7841773 : do {
427 : 7841773 : c = bb->Right;
428 : 7841773 : bb->Right = FreeList;
429 : 7841773 : FreeList = bb;
430 : 7841773 : bb = c;
431 : 7841773 : } while (! (bb == b));
432 : : }
433 : 2158394 : }
434 : :
435 : :
436 : : /*
437 : : ForeachBasicBlockDo - for each basic block call procedure, p.
438 : : */
439 : :
440 : 2258 : extern "C" void M2BasicBlock_ForeachBasicBlockDo (M2BasicBlock_BasicBlock bb, M2BasicBlock_BasicBlockProc p)
441 : : {
442 : 2258 : M2BasicBlock_BasicBlock b;
443 : :
444 : 2258 : if (bb != NULL)
445 : : {
446 : : b = bb;
447 : 5765 : do {
448 : 5765 : (*p.proc) (b->StartQuad, b->EndQuad);
449 : 5765 : b = b->Right;
450 : 5765 : } while (! (b == bb));
451 : : }
452 : 2258 : }
453 : :
454 : 16817 : extern "C" void _M2_M2BasicBlock_init (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
455 : : {
456 : 16817 : FreeList = NULL;
457 : 16817 : }
458 : :
459 : 0 : extern "C" void _M2_M2BasicBlock_fini (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
460 : : {
461 : 0 : }
|
