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