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