dmd.backend.glocal source code

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