dmd.backend.glocal source code

1 /**
2  * Local optimizations
3  *
4  * Compiler implementation of the
5  * $(LINK2 https://www.dlang.org, D programming language).
6  *
7  * Copyright:   Copyright (C) 1993-1998 by Symantec
8  *              Copyright (C) 2000-2023 by The D Language Foundation, All Rights Reserved
9  * Authors:     $(LINK2 https://www.digitalmars.com, Walter Bright)
10  * License:     $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
11  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/glocal.d, backend/glocal.d)
12  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/backend/glocal.d
13  */
14 
15 module dmd.backend.glocal;
16 
17 version (SCPP)
18     version = COMPILE;
19 version (MARS)
20     version = COMPILE;
21 
22 version (COMPILE)
23 {
24 
25 import core.stdc.stdio;
26 import core.stdc.stdlib;
27 import core.stdc.string;
28 import core.stdc.time;
29 
30 import dmd.backend.cc;
31 import dmd.backend.cdef;
32 import dmd.backend.code_x86;
33 import dmd.backend.oper;
34 import dmd.backend.global;
35 import dmd.backend.goh;
36 import dmd.backend.el;
37 import dmd.backend.ty;
38 import dmd.backend.type;
39 
40 import dmd.backend.barray;
41 import dmd.backend.dlist;
42 import dmd.backend.dvec;
43 
44 extern (C++):
45 
46 nothrow:
47 @safe:
48 
49 
50 
51 enum
52 {
53     LFvolatile     = 1,       // contains volatile or shared refs or defs
54     LFambigref     = 2,       // references ambiguous data
55     LFambigdef     = 4,       // defines ambiguous data
56     LFsymref       = 8,       // reference to symbol s
57     LFsymdef       = 0x10,    // definition of symbol s
58     LFunambigref   = 0x20,    // references unambiguous data other than s
59     LFunambigdef   = 0x40,    // defines unambiguous data other than s
60     LFinp          = 0x80,    // input from I/O port
61     LFoutp         = 0x100,   // output to I/O port
62     LFfloat        = 0x200,   // sets float flags and/or depends on
63                               // floating point settings
64 }
65 
66 struct loc_t
67 {
68     elem *e;
69     int flags;  // LFxxxxx
70 }
71 
72 
73 ///////////////////////////////
74 // This optimization attempts to replace sequences like:
75 //      x = func();
76 //      y = 3;
77 //      z = x + 5;
78 // with:
79 //      y = 3;
80 //      z = (x = func()) + 5;
81 // In other words, we attempt to localize expressions by moving them
82 // as near as we can to where they are used. This should minimize
83 // temporary generation and register usage.
84 
85 @trusted
86 void localize()
87 {
88     if (debugc) printf("localize()\n");
89 
90     __gshared Barray!(loc_t) loctab;       // cache the array so it usually won't need reallocating
91 
92     // Table should not get any larger than the symbol table
93     loctab.setLength(globsym.symmax);
94 
95     foreach (b; BlockRange(startblock))       // for each block
96     {
97         loctab.setLength(0);                     // start over for each block
98         if (b.Belem &&
99             /* Overly broad way to account for the case:
100              * try
101              * { i++;
102              *   foo(); // throws exception
103              *   i++;   // shouldn't combine previous i++ with this one
104              * }
105              */
106             !b.Btry)
107         {
108             local_exp(loctab,b.Belem,0);
109         }
110     }
111 }
112 
113 //////////////////////////////////////
114 // Input:
115 //      goal    !=0 if we want the result of the expression
116 //
117 
118 @trusted
119 private void local_exp(ref Barray!loc_t lt, elem *e, int goal)
120 {
121     elem *e1;
122     OPER op1;
123 
124 Loop:
125     elem_debug(e);
126     const op = e.Eoper;
127     switch (op)
128     {
129         case OPcomma:
130             local_exp(lt,e.EV.E1,0);
131             e = e.EV.E2;
132             goto Loop;
133 
134         case OPandand:
135         case OPoror:
136             local_exp(lt,e.EV.E1,1);
137             lt.setLength(0);         // we can do better than this, fix later
138             break;
139 
140         case OPcolon:
141         case OPcolon2:
142             lt.setLength(0);         // we can do better than this, fix later
143             break;
144 
145         case OPinfo:
146             if (e.EV.E1.Eoper == OPmark)
147             {   lt.setLength(0);
148                 e = e.EV.E2;
149                 goto Loop;
150             }
151             goto case_bin;
152 
153         case OPdtor:
154         case OPctor:
155         case OPdctor:
156             lt.setLength(0);         // don't move expressions across ctor/dtor
157             break;              // boundaries, it would goof up EH cleanup
158 
159         case OPddtor:
160             lt.setLength(0);         // don't move expressions across ctor/dtor
161                                 // boundaries, it would goof up EH cleanup
162             local_exp(lt,e.EV.E1,0);
163             lt.setLength(0);
164             break;
165 
166         case OPeq:
167         case OPstreq:
168         case OPvecsto:
169             e1 = e.EV.E1;
170             local_exp(lt,e.EV.E2,1);
171             if (e1.Eoper == OPvar)
172             {
173                 const s = e1.EV.Vsym;
174                 if (s.Sflags & SFLunambig)
175                 {   local_symdef(lt, s);
176                     if (!goal)
177                         local_ins(lt, e);
178                 }
179                 else
180                     local_ambigdef(lt);
181             }
182             else
183             {
184                 assert(!OTleaf(e1.Eoper));
185                 local_exp(lt,e1.EV.E1,1);
186                 if (OTbinary(e1.Eoper))
187                     local_exp(lt,e1.EV.E2,1);
188                 local_ambigdef(lt);
189             }
190             break;
191 
192         case OPpostinc:
193         case OPpostdec:
194         case OPaddass:
195         case OPminass:
196         case OPmulass:
197         case OPdivass:
198         case OPmodass:
199         case OPashrass:
200         case OPshrass:
201         case OPshlass:
202         case OPandass:
203         case OPxorass:
204         case OPorass:
205         case OPcmpxchg:
206             if (ERTOL(e))
207             {   local_exp(lt,e.EV.E2,1);
208         case OPnegass:
209                 e1 = e.EV.E1;
210                 op1 = e1.Eoper;
211                 if (op1 != OPvar)
212                 {
213                     local_exp(lt,e1.EV.E1,1);
214                     if (OTbinary(op1))
215                         local_exp(lt,e1.EV.E2,1);
216                 }
217                 else if (lt.length && (op == OPaddass || op == OPxorass))
218                 {
219                     const s = e1.EV.Vsym;
220                     for (uint u = 0; u < lt.length; u++)
221                     {
222                         auto em = lt[u].e;
223                         if (em.Eoper == op &&
224                             em.EV.E1.EV.Vsym == s &&
225                             tysize(em.Ety) == tysize(e1.Ety) &&
226                             !tyfloating(em.Ety) &&
227                             em.EV.E1.EV.Voffset == e1.EV.Voffset &&
228                             !el_sideeffect(em.EV.E2)
229                            )
230                         {   // Change (x += a),(x += b) to
231                             // (x + a),(x += a + b)
232                             go.changes++;
233                             e.EV.E2 = el_bin(opeqtoop(op),e.EV.E2.Ety,em.EV.E2,e.EV.E2);
234                             em.Eoper = cast(ubyte)opeqtoop(op);
235                             em.EV.E2 = el_copytree(em.EV.E2);
236                             local_rem(lt, u);
237 
238                             debug if (debugc)
239                             {   printf("Combined equation ");
240                                 WReqn(e);
241                                 printf(";\n");
242                                 e = doptelem(e,GOALvalue);
243                             }
244 
245                             break;
246                         }
247                     }
248                 }
249             }
250             else
251             {
252                 e1 = e.EV.E1;
253                 op1 = e1.Eoper;
254                 if (op1 != OPvar)
255                 {
256                     local_exp(lt,e1.EV.E1,1);
257                     if (OTbinary(op1))
258                         local_exp(lt,e1.EV.E2,1);
259                 }
260                 if (lt.length)
261                 {
262                     Symbol* s;
263                     if (op1 == OPvar &&
264                         ((s = e1.EV.Vsym).Sflags & SFLunambig))
265                         local_symref(lt, s);
266                     else
267                         local_ambigref(lt);
268                 }
269                 local_exp(lt,e.EV.E2,1);
270             }
271 
272             Symbol* s;
273             if (op1 == OPvar &&
274                 ((s = e1.EV.Vsym).Sflags & SFLunambig))
275             {   local_symref(lt, s);
276                 local_symdef(lt, s);
277                 if (op == OPaddass || op == OPxorass)
278                     local_ins(lt, e);
279             }
280             else if (lt.length)
281             {
282                 local_remove(lt, LFambigdef | LFambigref);
283             }
284             break;
285 
286         case OPstrlen:
287         case OPind:
288             local_exp(lt,e.EV.E1,1);
289             local_ambigref(lt);
290             break;
291 
292         case OPstrcmp:
293         case OPmemcmp:
294         case OPbt:
295             local_exp(lt,e.EV.E1,1);
296             local_exp(lt,e.EV.E2,1);
297             local_ambigref(lt);
298             break;
299 
300         case OPstrcpy:
301         case OPmemcpy:
302         case OPstrcat:
303         case OPcall:
304         case OPcallns:
305             local_exp(lt,e.EV.E2,1);
306             local_exp(lt,e.EV.E1,1);
307             goto Lrd;
308 
309         case OPstrctor:
310         case OPucall:
311         case OPucallns:
312             local_exp(lt,e.EV.E1,1);
313             goto Lrd;
314 
315         case OPbtc:
316         case OPbtr:
317         case OPbts:
318             local_exp(lt,e.EV.E1,1);
319             local_exp(lt,e.EV.E2,1);
320             goto Lrd;
321 
322         case OPasm:
323         Lrd:
324             local_remove(lt, LFfloat | LFambigref | LFambigdef);
325             break;
326 
327         case OPmemset:
328             local_exp(lt,e.EV.E2,1);
329             if (e.EV.E1.Eoper == OPvar)
330             {
331                 /* Don't want to rearrange (p = get(); p memset 0;)
332                  * as elemxxx() will rearrange it back.
333                  */
334                 const s = e.EV.E1.EV.Vsym;
335                 if (s.Sflags & SFLunambig)
336                     local_symref(lt, s);
337                 else
338                     local_ambigref(lt);     // ambiguous reference
339             }
340             else
341                 local_exp(lt,e.EV.E1,1);
342             local_ambigdef(lt);
343             break;
344 
345         case OPvar:
346             const s = e.EV.Vsym;
347             if (lt.length)
348             {
349                 // If potential candidate for replacement
350                 if (s.Sflags & SFLunambig)
351                 {
352                     foreach (const u; 0 .. lt.length)
353                     {
354                         auto em = lt[u].e;
355                         if (em.EV.E1.EV.Vsym == s &&
356                             (em.Eoper == OPeq || em.Eoper == OPstreq))
357                         {
358                             if (tysize(em.Ety) == tysize(e.Ety) &&
359                                 em.EV.E1.EV.Voffset == e.EV.Voffset &&
360                                 ((tyfloating(em.Ety) != 0) == (tyfloating(e.Ety) != 0) ||
361                                  /** Hack to fix https://issues.dlang.org/show_bug.cgi?id=10226
362                                   * Recognize assignments of float vectors to void16, as used by
363                                   * core.simd intrinsics. The backend type for void16 is Tschar16!
364                                   */
365                                  (tyvector(em.Ety) != 0) == (tyvector(e.Ety) != 0) && tybasic(e.Ety) == TYschar16) &&
366                                 /* Changing the Ety to a OPvecfill node means we're potentially generating
367                                  * wrong code.
368                                  * Ref: https://issues.dlang.org/show_bug.cgi?id=18034
369                                  */
370                                 (em.EV.E2.Eoper != OPvecfill || tybasic(e.Ety) == tybasic(em.Ety)) &&
371                                 !local_preserveAssignmentTo(em.EV.E1.Ety))
372                             {
373 
374                                 debug if (debugc)
375                                 {   printf("Moved equation ");
376                                     WReqn(em);
377                                     printf(";\n");
378                                 }
379 
380                                 go.changes++;
381                                 em.Ety = e.Ety;
382                                 el_copy(e,em);
383                                 em.EV.E1 = em.EV.E2 = null;
384                                 em.Eoper = OPconst;
385                             }
386                             local_rem(lt, u);
387                             break;
388                         }
389                     }
390                     local_symref(lt, s);
391                 }
392                 else
393                     local_ambigref(lt);     // ambiguous reference
394             }
395             break;
396 
397         case OPremquo:
398             if (e.EV.E1.Eoper != OPvar)
399                 goto case_bin;
400             const s = e.EV.E1.EV.Vsym;
401             if (lt.length)
402             {
403                 if (s.Sflags & SFLunambig)
404                     local_symref(lt, s);
405                 else
406                     local_ambigref(lt);     // ambiguous reference
407             }
408             goal = 1;
409             e = e.EV.E2;
410             goto Loop;
411 
412         default:
413             if (OTcommut(e.Eoper))
414             {   // Since commutative operators may get their leaves
415                 // swapped, we eliminate any that may be affected by that.
416 
417                 for (uint u = 0; u < lt.length;)
418                 {
419                     const f = lt[u].flags;
420                     elem* eu = lt[u].e;
421                     const s = eu.EV.E1.EV.Vsym;
422                     const f1 = local_getflags(e.EV.E1,s);
423                     const f2 = local_getflags(e.EV.E2,s);
424                     if (f1 & f2 & LFsymref ||   // if both reference or
425                         (f1 | f2) & LFsymdef || // either define
426                         f & LFambigref && (f1 | f2) & LFambigdef ||
427                         f & LFambigdef && (f1 | f2) & (LFambigref | LFambigdef)
428                        )
429                         local_rem(lt, u);
430                     else if (f & LFunambigdef && local_chkrem(e,eu.EV.E2))
431                         local_rem(lt, u);
432                     else
433                         u++;
434                 }
435             }
436             if (OTunary(e.Eoper))
437             {   goal = 1;
438                 e = e.EV.E1;
439                 goto Loop;
440             }
441         case_bin:
442             if (OTbinary(e.Eoper))
443             {   local_exp(lt,e.EV.E1,1);
444                 goal = 1;
445                 e = e.EV.E2;
446                 goto Loop;
447             }
448             break;
449     }   // end of switch (e.Eoper)
450 }
451 
452 ///////////////////////////////////
453 // Examine expression tree eu to see if it defines any variables
454 // that e refs or defs.
455 // Note that e is a binary operator.
456 // Returns:
457 //      true if it does
458 
459 @trusted
460 private bool local_chkrem(const elem* e, const(elem)* eu)
461 {
462     while (1)
463     {
464         elem_debug(eu);
465         const op = eu.Eoper;
466         if (OTassign(op) && eu.EV.E1.Eoper == OPvar)
467         {
468             const s = eu.EV.E1.EV.Vsym;
469             const f1 = local_getflags(e.EV.E1,s);
470             const f2 = local_getflags(e.EV.E2,s);
471             if ((f1 | f2) & (LFsymref | LFsymdef))      // if either reference or define
472                 return true;
473         }
474         if (OTbinary(op))
475         {
476             if (local_chkrem(e,eu.EV.E2))
477                 return true;
478         }
479         else if (!OTunary(op))
480             break;                      // leaf node
481         eu = eu.EV.E1;
482     }
483     return false;
484 }
485 
486 //////////////////////////////////////
487 // Add entry e to lt[]
488 
489 @trusted
490 private void local_ins(ref Barray!loc_t lt, elem *e)
491 {
492     elem_debug(e);
493     if (e.EV.E1.Eoper == OPvar)
494     {
495         const s = e.EV.E1.EV.Vsym;
496         symbol_debug(s);
497         if (s.Sflags & SFLunambig)     // if can only be referenced directly
498         {
499             const flags = local_getflags(e.EV.E2,null);
500             if (!(flags & (LFvolatile | LFinp | LFoutp)) &&
501                 !(e.EV.E1.Ety & (mTYvolatile | mTYshared)))
502             {
503                 // Add e to the candidate array
504                 //printf("local_ins('%s'), loctop = %d\n",s.Sident.ptr,lt.length);
505                 lt.push(loc_t(e, flags));
506             }
507         }
508     }
509 }
510 
511 //////////////////////////////////////
512 // Remove entry i from lt[], and then compress the table.
513 //
514 @trusted
515 private void local_rem(ref Barray!loc_t lt, size_t u)
516 {
517     //printf("local_rem(%u)\n",u);
518     lt.remove(u);
519 }
520 
521 //////////////////////////////////////
522 // Analyze and gather LFxxxx flags about expression e and symbol s.
523 
524 @trusted
525 private int local_getflags(const(elem)* e, const Symbol* s)
526 {
527     elem_debug(e);
528     if (s)
529         symbol_debug(s);
530     int flags = 0;
531     while (1)
532     {
533         if (e.Ety & (mTYvolatile | mTYshared))
534             flags |= LFvolatile;
535         switch (e.Eoper)
536         {
537             case OPeq:
538             case OPstreq:
539                 if (e.EV.E1.Eoper == OPvar)
540                 {
541                     const s1 = e.EV.E1.EV.Vsym;
542                     if (s1.Sflags & SFLunambig)
543                         flags |= (s1 == s) ? LFsymdef : LFunambigdef;
544                     else
545                         flags |= LFambigdef;
546                 }
547                 else
548                     flags |= LFambigdef;
549                 goto L1;
550 
551             case OPpostinc:
552             case OPpostdec:
553             case OPaddass:
554             case OPminass:
555             case OPmulass:
556             case OPdivass:
557             case OPmodass:
558             case OPashrass:
559             case OPshrass:
560             case OPshlass:
561             case OPandass:
562             case OPxorass:
563             case OPorass:
564             case OPcmpxchg:
565                 if (e.EV.E1.Eoper == OPvar)
566                 {
567                     const s1 = e.EV.E1.EV.Vsym;
568                     if (s1.Sflags & SFLunambig)
569                         flags |= (s1 == s) ? LFsymdef | LFsymref
570                                            : LFunambigdef | LFunambigref;
571                     else
572                         flags |= LFambigdef | LFambigref;
573                 }
574                 else
575                     flags |= LFambigdef | LFambigref;
576             L1:
577                 flags |= local_getflags(e.EV.E2,s);
578                 e = e.EV.E1;
579                 break;
580 
581             case OPucall:
582             case OPucallns:
583             case OPcall:
584             case OPcallns:
585             case OPstrcat:
586             case OPstrcpy:
587             case OPmemcpy:
588             case OPbtc:
589             case OPbtr:
590             case OPbts:
591             case OPstrctor:
592                 flags |= LFambigref | LFambigdef;
593                 break;
594 
595             case OPmemset:
596                 flags |= LFambigdef;
597                 break;
598 
599             case OPvar:
600                 if (e.EV.Vsym == s)
601                     flags |= LFsymref;
602                 else if (!(e.EV.Vsym.Sflags & SFLunambig))
603                     flags |= LFambigref;
604                 break;
605 
606             case OPind:
607             case OPstrlen:
608             case OPstrcmp:
609             case OPmemcmp:
610             case OPbt:
611                 flags |= LFambigref;
612                 break;
613 
614             case OPinp:
615                 flags |= LFinp;
616                 break;
617 
618             case OPoutp:
619                 flags |= LFoutp;
620                 break;
621 
622             default:
623                 break;
624         }
625         if (OTunary(e.Eoper))
626         {
627             if (tyfloating(e.Ety))
628                 flags |= LFfloat;
629             e = e.EV.E1;
630         }
631         else if (OTbinary(e.Eoper))
632         {
633             if (tyfloating(e.Ety))
634                 flags |= LFfloat;
635             flags |= local_getflags(e.EV.E2,s);
636             e = e.EV.E1;
637         }
638         else
639             break;
640     }
641     return flags;
642 }
643 
644 //////////////////////////////////////
645 // Remove all entries with flags set.
646 //
647 
648 private void local_remove(ref Barray!loc_t lt, int flags)
649 {
650     for (uint u = 0; u < lt.length;)
651     {
652         if (lt[u].flags & flags)
653             local_rem(lt, u);
654         else
655             ++u;
656     }
657 }
658 
659 //////////////////////////////////////
660 // Ambiguous reference. Remove all with ambiguous defs
661 //
662 
663 private void local_ambigref(ref Barray!loc_t lt)
664 {
665     local_remove(lt, LFambigdef);
666 }
667 
668 //////////////////////////////////////
669 // Ambiguous definition. Remove all with ambiguous refs.
670 //
671 
672 private void local_ambigdef(ref Barray!loc_t lt)
673 {
674     local_remove(lt, LFambigref | LFambigdef);
675 }
676 
677 //////////////////////////////////////
678 // Reference to symbol.
679 // Remove any that define that symbol.
680 
681 private void local_symref(ref Barray!loc_t lt, const Symbol* s)
682 {
683     symbol_debug(s);
684     for (uint u = 0; u < lt.length;)
685     {
686         if (local_getflags(lt[u].e,s) & LFsymdef)
687             local_rem(lt, u);
688         else
689             ++u;
690     }
691 }
692 
693 //////////////////////////////////////
694 // Definition of symbol.
695 // Remove any that reference that symbol.
696 
697 private void local_symdef(ref Barray!loc_t lt, const Symbol* s)
698 {
699     symbol_debug(s);
700     for (uint u = 0; u < lt.length;)
701     {
702         if (local_getflags(lt[u].e,s) & (LFsymref | LFsymdef))
703             local_rem(lt, u);
704         else
705             ++u;
706     }
707 }
708 
709 /***************************************************
710  * See if we should preserve assignment to Symbol of type ty.
711  * Returns:
712  *      true if preserve assignment
713  * References:
714  *      https://issues.dlang.org/show_bug.cgi?id=13474
715  */
716 @trusted
717 private bool local_preserveAssignmentTo(tym_t ty)
718 {
719     /* Need to preserve assignment if generating code using
720      * the x87, as that is the only way to get the x87 to
721      * convert to float/double precision.
722      */
723     /* Don't do this for 64 bit compiles because returns are in
724      * the XMM registers so it doesn't evaluate floats/doubles in the x87.
725      * 32 bit returns are in ST0, so it evaluates in the x87.
726      * https://issues.dlang.org/show_bug.cgi?id=21526
727      */
728     if (config.inline8087 && !I64)
729     {
730         switch (tybasic(ty))
731         {
732             case TYfloat:
733             case TYifloat:
734             case TYcfloat:
735             case TYdouble:
736             case TYidouble:
737             case TYdouble_alias:
738             case TYcdouble:
739                 return true;
740 
741             default:
742                 break;
743         }
744     }
745     return false;
746 }
747 
748 }