Branch data Line data Source code
1 : : /* do not edit automatically generated by mc from M2Optimize. */
2 : : /* M2Optimize.mod removes redundant quadruples.
3 : :
4 : : Copyright (C) 2001-2025 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 : : #define INCLUDE_MEMORY
24 : : #include "config.h"
25 : : #include "system.h"
26 : : #include "gcc-consolidation.h"
27 : :
28 : : #include <stdbool.h>
29 : : # if !defined (PROC_D)
30 : : # define PROC_D
31 : : typedef void (*PROC_t) (void);
32 : : typedef struct { PROC_t proc; } PROC;
33 : : # endif
34 : :
35 : : # if !defined (TRUE)
36 : : # define TRUE (1==1)
37 : : # endif
38 : :
39 : : # if !defined (FALSE)
40 : : # define FALSE (1==0)
41 : : # endif
42 : :
43 : : #define _M2Optimize_C
44 : :
45 : : #include "GM2Optimize.h"
46 : : # include "GM2Debug.h"
47 : : # include "GNameKey.h"
48 : : # include "GStrIO.h"
49 : : # include "GNumberIO.h"
50 : : # include "GM2Error.h"
51 : : # include "GM2Batch.h"
52 : : # include "GM2Quiet.h"
53 : : # include "GM2Scope.h"
54 : : # include "GSymbolTable.h"
55 : : # include "GM2Quads.h"
56 : :
57 : :
58 : : /*
59 : : FoldBranches - folds unneccessary branches in the list of quadruples.
60 : : It searches for the following patterns:
61 : :
62 : : [x] GotoOp _ _ y GotoOp _ _ z
63 : : ... ...
64 : : [y] GotoOp _ _ z "deleted"
65 : :
66 : : WHERE ... may contain 0..n Pseudo Quads
67 : :
68 : :
69 : : OR
70 : :
71 : :
72 : : [x] IfREL _ _ z If NOT REL _ _ a
73 : : ... ...
74 : : [y] Goto _ _ a "deleted"
75 : : ... ...
76 : : [z]
77 : :
78 : :
79 : : WHERE ... may contain 0..n Pseudo Quads
80 : : but in this case they must not be a
81 : : target of any other quad.
82 : : */
83 : :
84 : : extern "C" void M2Optimize_FoldBranches (unsigned int start, unsigned int end);
85 : :
86 : : /*
87 : : RemoveProcedures - removes any procedures that are never referenced
88 : : by the quadruples.
89 : : */
90 : :
91 : : extern "C" void M2Optimize_RemoveProcedures (unsigned int scope);
92 : :
93 : : /*
94 : : DisplayReachable - Displays the data structures surrounding Reachablity.
95 : : */
96 : :
97 : : extern "C" void M2Optimize_DisplayReachable (void);
98 : :
99 : : /*
100 : : ReduceBranch - searches for the following pattern:
101 : :
102 : : [x] IfREL _ _ z If NOT REL _ _ a
103 : : ... ...
104 : : [y] Goto _ _ a "deleted"
105 : : ... ...
106 : : [z]
107 : :
108 : :
109 : : WHERE ... may contain 0..n Pseudo Quads
110 : : but in this case they must not be a
111 : : target of any other quad.
112 : :
113 : : */
114 : :
115 : : static bool ReduceBranch (M2Quads_QuadOperator Operator, unsigned int CurrentQuad, unsigned int CurrentOperand1, unsigned int CurrentOperand2, unsigned int CurrentOperand3, unsigned int *NextQuad, bool Folded);
116 : :
117 : : /*
118 : : IsBasicBlock - returns TRUE if no other quadruple jumps inbetween
119 : : the range From..To.
120 : : It assumes that there are no jumps in the quadruples
121 : : From..To.
122 : : */
123 : :
124 : : static bool IsBasicBlock (unsigned int From, unsigned int To);
125 : :
126 : : /*
127 : : ReduceGoto - searches for the following patterns:
128 : :
129 : : [x] GotoOp _ _ y GotoOp _ _ z
130 : : ... ...
131 : : [y] GotoOp _ _ z "deleted"
132 : :
133 : :
134 : : */
135 : :
136 : : static bool ReduceGoto (unsigned int CurrentQuad, unsigned int CurrentOperand3, unsigned int NextQuad, bool Folded);
137 : :
138 : : /*
139 : : FoldMultipleGoto - takes a QuadNo and if it jumps to another GotoOp
140 : : then it takes the later target as a replacement
141 : : for its own.
142 : :
143 : : NOTE it does not remove any quadruples.
144 : : */
145 : :
146 : : static bool FoldMultipleGoto (unsigned int QuadNo);
147 : :
148 : : /*
149 : : CheckNeedSavePriority -
150 : : */
151 : :
152 : : static void CheckNeedSavePriority (unsigned int sym);
153 : :
154 : : /*
155 : : CheckExportedReachable - checks to see whether procedure, sym, was
156 : : exported and if so it calls RemoveProcedures.
157 : : */
158 : :
159 : : static void CheckExportedReachable (unsigned int sym);
160 : : static void KnownReachable (unsigned int Start, unsigned int End);
161 : : static void KnownReach (unsigned int sym);
162 : :
163 : :
164 : : /*
165 : : ReduceBranch - searches for the following pattern:
166 : :
167 : : [x] IfREL _ _ z If NOT REL _ _ a
168 : : ... ...
169 : : [y] Goto _ _ a "deleted"
170 : : ... ...
171 : : [z]
172 : :
173 : :
174 : : WHERE ... may contain 0..n Pseudo Quads
175 : : but in this case they must not be a
176 : : target of any other quad.
177 : :
178 : : */
179 : :
180 : 284030 : static bool ReduceBranch (M2Quads_QuadOperator Operator, unsigned int CurrentQuad, unsigned int CurrentOperand1, unsigned int CurrentOperand2, unsigned int CurrentOperand3, unsigned int *NextQuad, bool Folded)
181 : : {
182 : 284030 : bool constExpr;
183 : 284030 : bool overflowChecking;
184 : 284030 : M2Quads_QuadOperator OpNext;
185 : 284030 : unsigned int tok;
186 : 284030 : unsigned int NextPlusOne;
187 : 284030 : unsigned int Op1Next;
188 : 284030 : unsigned int Op2Next;
189 : 284030 : unsigned int Op3Next;
190 : 284030 : unsigned int op1tok;
191 : 284030 : unsigned int op2tok;
192 : 284030 : unsigned int op3tok;
193 : 284030 : unsigned int From;
194 : 284030 : unsigned int To;
195 : :
196 : : /* Goto x */
197 : 284030 : if ((*NextQuad) != 0)
198 : : {
199 : 284030 : if (((M2Quads_GetNextQuad (CurrentQuad)) == CurrentOperand3) || ((M2Quads_GetRealQuad (M2Quads_GetNextQuad (CurrentQuad))) == CurrentOperand3))
200 : : {
201 : 412 : M2Quads_SubQuad (CurrentQuad);
202 : 412 : Folded = true;
203 : : }
204 : : else
205 : : {
206 : 283618 : From = M2Quads_GetNextQuad (CurrentQuad); /* start after CurrentQuad */
207 : 283618 : To = (*NextQuad); /* start after CurrentQuad */
208 : 283618 : CurrentOperand3 = M2Quads_GetRealQuad (CurrentOperand3);
209 : 283618 : NextPlusOne = M2Quads_GetRealQuad (M2Quads_GetNextQuad ((*NextQuad)));
210 : 283618 : M2Quads_GetQuad ((*NextQuad), &OpNext, &Op1Next, &Op2Next, &Op3Next);
211 : 283618 : if (((OpNext == M2Quads_GotoOp) && (NextPlusOne == CurrentOperand3)) && (IsBasicBlock (From, To)))
212 : : {
213 : 68188 : M2Quads_GetQuadOtok (CurrentQuad, &tok, &Operator, &CurrentOperand1, &CurrentOperand2, &CurrentOperand3, &overflowChecking, &constExpr, &op1tok, &op2tok, &op3tok);
214 : 68188 : M2Quads_SubQuad ((*NextQuad));
215 : 68188 : M2Quads_PutQuadOtok (CurrentQuad, tok, M2Quads_Opposite (Operator), CurrentOperand1, CurrentOperand2, Op3Next, overflowChecking, constExpr, op1tok, op2tok, op3tok);
216 : 68188 : (*NextQuad) = NextPlusOne;
217 : 68188 : Folded = true;
218 : : }
219 : : }
220 : 284030 : if (FoldMultipleGoto (CurrentQuad))
221 : : {
222 : 3049 : Folded = true;
223 : : }
224 : : }
225 : 284030 : return Folded;
226 : : /* static analysis guarentees a RETURN statement will be used before here. */
227 : : __builtin_unreachable ();
228 : : }
229 : :
230 : :
231 : : /*
232 : : IsBasicBlock - returns TRUE if no other quadruple jumps inbetween
233 : : the range From..To.
234 : : It assumes that there are no jumps in the quadruples
235 : : From..To.
236 : : */
237 : :
238 : 68188 : static bool IsBasicBlock (unsigned int From, unsigned int To)
239 : : {
240 : 69498 : while (From != To)
241 : : {
242 : 1310 : if (M2Quads_IsReferenced (From))
243 : : {
244 : : return false;
245 : : }
246 : : else
247 : : {
248 : 1310 : if (From > To)
249 : : {
250 : 0 : M2Error_InternalError ((const char *) "assert failed From should never be larger than To", 49);
251 : : }
252 : 1310 : From = M2Quads_GetNextQuad (From);
253 : : }
254 : : }
255 : : return true;
256 : : /* static analysis guarentees a RETURN statement will be used before here. */
257 : : __builtin_unreachable ();
258 : : }
259 : :
260 : :
261 : : /*
262 : : ReduceGoto - searches for the following patterns:
263 : :
264 : : [x] GotoOp _ _ y GotoOp _ _ z
265 : : ... ...
266 : : [y] GotoOp _ _ z "deleted"
267 : :
268 : :
269 : : */
270 : :
271 : 189199 : static bool ReduceGoto (unsigned int CurrentQuad, unsigned int CurrentOperand3, unsigned int NextQuad, bool Folded)
272 : : {
273 : 189199 : CurrentOperand3 = M2Quads_GetRealQuad (CurrentOperand3);
274 : : /* IF next quad is a GotoOp */
275 : 189199 : if (CurrentOperand3 == NextQuad)
276 : : {
277 : 25947 : M2Quads_SubQuad (CurrentQuad);
278 : 25947 : Folded = true;
279 : : }
280 : : else
281 : : {
282 : : /* Does Goto point to another Goto ? */
283 : 163252 : if (FoldMultipleGoto (CurrentQuad))
284 : : {
285 : 29373 : Folded = true;
286 : : }
287 : : }
288 : 189199 : return Folded;
289 : : /* static analysis guarentees a RETURN statement will be used before here. */
290 : : __builtin_unreachable ();
291 : : }
292 : :
293 : :
294 : : /*
295 : : FoldMultipleGoto - takes a QuadNo and if it jumps to another GotoOp
296 : : then it takes the later target as a replacement
297 : : for its own.
298 : :
299 : : NOTE it does not remove any quadruples.
300 : : */
301 : :
302 : 447282 : static bool FoldMultipleGoto (unsigned int QuadNo)
303 : : {
304 : 447282 : M2Quads_QuadOperator Operator;
305 : 447282 : M2Quads_QuadOperator Op;
306 : 447282 : unsigned int Op1;
307 : 447282 : unsigned int Op2;
308 : 447282 : unsigned int Op3;
309 : 447282 : unsigned int Operand1;
310 : 447282 : unsigned int Operand2;
311 : 447282 : unsigned int Operand3;
312 : :
313 : 447282 : M2Quads_GetQuad (QuadNo, &Operator, &Operand1, &Operand2, &Operand3);
314 : 447282 : Operand3 = M2Quads_GetRealQuad (Operand3); /* skip pseudo quadruples */
315 : 447282 : M2Quads_GetQuad (Operand3, &Op, &Op1, &Op2, &Op3); /* skip pseudo quadruples */
316 : 447282 : if (Op == M2Quads_GotoOp)
317 : : {
318 : 6475 : M2Quads_PutQuad (QuadNo, Operator, Operand1, Operand2, Op3);
319 : : /* forever. */
320 : 6475 : return Op3 != Operand3;
321 : : }
322 : : else
323 : : {
324 : : return false;
325 : : }
326 : : /* static analysis guarentees a RETURN statement will be used before here. */
327 : : __builtin_unreachable ();
328 : : }
329 : :
330 : :
331 : : /*
332 : : CheckNeedSavePriority -
333 : : */
334 : :
335 : 806695 : static void CheckNeedSavePriority (unsigned int sym)
336 : : {
337 : 806695 : if ((SymbolTable_IsProcedure (sym)) && ((SymbolTable_GetPriority (SymbolTable_GetModuleScope (sym))) != SymbolTable_NulSym))
338 : : {
339 : 162 : SymbolTable_PutNeedSavePriority (sym);
340 : : }
341 : 806695 : }
342 : :
343 : :
344 : : /*
345 : : CheckExportedReachable - checks to see whether procedure, sym, was
346 : : exported and if so it calls RemoveProcedures.
347 : : */
348 : :
349 : 181676 : static void CheckExportedReachable (unsigned int sym)
350 : : {
351 : 181676 : if (SymbolTable_IsExported (SymbolTable_GetModuleScope (sym), sym))
352 : : {
353 : 14187 : M2Optimize_RemoveProcedures (sym);
354 : 14187 : CheckNeedSavePriority (sym);
355 : : }
356 : 181676 : }
357 : :
358 : 311234 : static void KnownReachable (unsigned int Start, unsigned int End)
359 : : {
360 : 311234 : M2Quads_QuadOperator Op;
361 : 311234 : unsigned int Op1;
362 : 311234 : unsigned int Op2;
363 : 311234 : unsigned int Op3;
364 : :
365 : : /* DeleteUnReachableProcedures */
366 : 311234 : if (Start != 0)
367 : : {
368 : 3992375 : do {
369 : 3992375 : M2Quads_GetQuad (Start, &Op, &Op1, &Op2, &Op3);
370 : 3992375 : switch (Op)
371 : : {
372 : 134621 : case M2Quads_CallOp:
373 : 134621 : KnownReach (Op3);
374 : 134621 : break;
375 : :
376 : 792508 : case M2Quads_AddrOp:
377 : 792508 : case M2Quads_ParamOp:
378 : 792508 : case M2Quads_XIndrOp:
379 : 792508 : case M2Quads_BecomesOp:
380 : 792508 : KnownReach (Op3);
381 : 792508 : CheckNeedSavePriority (Op3);
382 : 792508 : break;
383 : :
384 : :
385 : : default:
386 : : break;
387 : : }
388 : 3992375 : Start = M2Quads_GetNextQuad (Start);
389 : 3992375 : } while (! ((Start > End) || (Start == 0)));
390 : : }
391 : 311234 : }
392 : :
393 : 927129 : static void KnownReach (unsigned int sym)
394 : : {
395 : 927129 : if ((SymbolTable_IsProcedure (sym)) && (! (SymbolTable_IsProcedureReachable (sym))))
396 : : {
397 : 45153 : M2Optimize_RemoveProcedures (sym);
398 : : }
399 : 927129 : }
400 : :
401 : :
402 : : /*
403 : : FoldBranches - folds unneccessary branches in the list of quadruples.
404 : : It searches for the following patterns:
405 : :
406 : : [x] GotoOp _ _ y GotoOp _ _ z
407 : : ... ...
408 : : [y] GotoOp _ _ z "deleted"
409 : :
410 : : WHERE ... may contain 0..n Pseudo Quads
411 : :
412 : :
413 : : OR
414 : :
415 : :
416 : : [x] IfREL _ _ z If NOT REL _ _ a
417 : : ... ...
418 : : [y] Goto _ _ a "deleted"
419 : : ... ...
420 : : [z]
421 : :
422 : :
423 : : WHERE ... may contain 0..n Pseudo Quads
424 : : but in this case they must not be a
425 : : target of any other quad.
426 : : */
427 : :
428 : 905824 : extern "C" void M2Optimize_FoldBranches (unsigned int start, unsigned int end)
429 : : {
430 : 907390 : bool Folded;
431 : 907390 : unsigned int i;
432 : 907390 : unsigned int j;
433 : 907390 : unsigned int Right;
434 : 907390 : M2Quads_QuadOperator Operator;
435 : 907390 : unsigned int Operand1;
436 : 907390 : unsigned int Operand2;
437 : 907390 : unsigned int Operand3;
438 : :
439 : 907390 : do {
440 : 907390 : i = start;
441 : 907390 : Folded = false;
442 : 11857623 : while ((i <= end) && (i != 0))
443 : : {
444 : 11585393 : j = M2Quads_GetNextQuad (i);
445 : 11585393 : if ((j > end) || (j == 0))
446 : : {
447 : 635160 : return;
448 : : }
449 : 11014149 : Right = M2Quads_GetRealQuad (j);
450 : 11014149 : if (Right == 0)
451 : : {
452 : : return;
453 : : }
454 : 10950233 : M2Quads_GetQuad (i, &Operator, &Operand1, &Operand2, &Operand3);
455 : 10950233 : switch (Operator)
456 : : {
457 : 189199 : case M2Quads_GotoOp:
458 : 189199 : Folded = ReduceGoto (i, Operand3, Right, Folded);
459 : 189199 : break;
460 : :
461 : 284030 : case M2Quads_IfInOp:
462 : 284030 : case M2Quads_IfNotInOp:
463 : 284030 : case M2Quads_IfNotEquOp:
464 : 284030 : case M2Quads_IfEquOp:
465 : 284030 : case M2Quads_IfLessEquOp:
466 : 284030 : case M2Quads_IfGreEquOp:
467 : 284030 : case M2Quads_IfGreOp:
468 : 284030 : case M2Quads_IfLessOp:
469 : 284030 : Folded = ReduceBranch (Operator, i, Operand1, Operand2, Operand3, &Right, Folded);
470 : 284030 : break;
471 : :
472 : :
473 : : default:
474 : : break;
475 : : }
476 : 10950233 : i = Right;
477 : : }
478 : 272230 : } while (! (! Folded));
479 : : }
480 : :
481 : :
482 : : /*
483 : : RemoveProcedures - removes any procedures that are never referenced
484 : : by the quadruples.
485 : : */
486 : :
487 : 74517 : extern "C" void M2Optimize_RemoveProcedures (unsigned int scope)
488 : : {
489 : 74517 : M2Scope_ScopeBlock sb;
490 : :
491 : 74517 : sb = M2Scope_InitScopeBlock (scope);
492 : 74517 : if (SymbolTable_IsProcedure (scope))
493 : : {
494 : 59340 : SymbolTable_PutProcedureReachable (scope);
495 : 59340 : M2Scope_ForeachScopeBlockDo2 (sb, (M2Scope_ScopeProcedure2) {(M2Scope_ScopeProcedure2_t) KnownReachable});
496 : : }
497 : 15177 : else if (SymbolTable_IsModuleWithinProcedure (scope))
498 : : {
499 : : /* avoid dangling else. */
500 : 36 : M2Scope_ForeachScopeBlockDo2 (sb, (M2Scope_ScopeProcedure2) {(M2Scope_ScopeProcedure2_t) KnownReachable});
501 : 36 : SymbolTable_ForeachProcedureDo (scope, (SymbolKey_PerformOperation) {(SymbolKey_PerformOperation_t) CheckExportedReachable});
502 : : }
503 : : else
504 : : {
505 : : /* avoid dangling else. */
506 : 15141 : M2Scope_ForeachScopeBlockDo2 (sb, (M2Scope_ScopeProcedure2) {(M2Scope_ScopeProcedure2_t) KnownReachable});
507 : 15141 : SymbolTable_ForeachProcedureDo (scope, (SymbolKey_PerformOperation) {(SymbolKey_PerformOperation_t) CheckExportedReachable});
508 : : }
509 : 74517 : SymbolTable_ForeachInnerModuleDo (scope, (SymbolKey_PerformOperation) {(SymbolKey_PerformOperation_t) M2Optimize_RemoveProcedures});
510 : 74517 : M2Scope_KillScopeBlock (&sb);
511 : 74517 : }
512 : :
513 : :
514 : : /*
515 : : DisplayReachable - Displays the data structures surrounding Reachablity.
516 : : */
517 : :
518 : 0 : extern "C" void M2Optimize_DisplayReachable (void)
519 : : {
520 : 0 : unsigned int n;
521 : 0 : unsigned int m;
522 : 0 : unsigned int Scope;
523 : 0 : unsigned int StartInit;
524 : 0 : unsigned int EndInit;
525 : 0 : unsigned int StartFinish;
526 : 0 : unsigned int EndFinish;
527 : 0 : unsigned int Module;
528 : 0 : unsigned int Proc;
529 : :
530 : 0 : m = 1;
531 : 0 : do {
532 : 0 : Module = M2Batch_GetModuleNo (m);
533 : 0 : if (Module != SymbolTable_NulSym)
534 : : {
535 : 0 : StrIO_WriteString ((const char *) "Module", 6);
536 : 0 : NumberIO_WriteCard (m, 3);
537 : 0 : NameKey_WriteKey (SymbolTable_GetSymName (Module));
538 : 0 : SymbolTable_GetModuleQuads (Module, &StartInit, &EndInit, &StartFinish, &EndFinish);
539 : 0 : StrIO_WriteString ((const char *) " Reachable initialization", 25);
540 : 0 : NumberIO_WriteCard (StartInit, 6);
541 : 0 : NumberIO_WriteCard (EndInit, 6);
542 : 0 : StrIO_WriteLn ();
543 : 0 : StrIO_WriteString ((const char *) "Module", 6);
544 : 0 : NumberIO_WriteCard (m, 3);
545 : 0 : NameKey_WriteKey (SymbolTable_GetSymName (Module));
546 : 0 : SymbolTable_GetModuleQuads (Module, &StartInit, &EndInit, &StartFinish, &EndFinish);
547 : 0 : StrIO_WriteString ((const char *) " Reachable finalization", 23);
548 : 0 : NumberIO_WriteCard (StartFinish, 6);
549 : 0 : NumberIO_WriteCard (EndFinish, 6);
550 : 0 : StrIO_WriteLn ();
551 : 0 : n = 1;
552 : 0 : Proc = SymbolTable_GetNthProcedure (Module, n);
553 : 0 : while (Proc != SymbolTable_NulSym)
554 : : {
555 : 0 : StrIO_WriteString ((const char *) "Procedure ", 10);
556 : 0 : NameKey_WriteKey (SymbolTable_GetSymName (Proc));
557 : 0 : SymbolTable_GetProcedureQuads (Proc, &Scope, &StartInit, &EndInit);
558 : 0 : StrIO_WriteString ((const char *) " Quads: ", 8);
559 : 0 : NumberIO_WriteCard (StartInit, 6);
560 : 0 : NumberIO_WriteCard (EndInit, 6);
561 : 0 : if (! (SymbolTable_IsProcedureReachable (Proc)))
562 : : {
563 : 0 : StrIO_WriteString ((const char *) " UN reachable", 13);
564 : : }
565 : : else
566 : : {
567 : 0 : StrIO_WriteString ((const char *) " IS reachable", 13);
568 : : }
569 : 0 : StrIO_WriteLn ();
570 : 0 : n += 1;
571 : 0 : Proc = SymbolTable_GetNthProcedure (Module, n);
572 : : }
573 : 0 : m += 1;
574 : : }
575 : 0 : } while (! (Module == SymbolTable_NulSym));
576 : 0 : }
577 : :
578 : 0 : extern "C" void _M2_M2Optimize_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
579 : : {
580 : 0 : }
581 : :
582 : 0 : extern "C" void _M2_M2Optimize_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
583 : : {
584 : 0 : }
|
