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     Symbol *s;
118     elem *e1;
119     OPER op1;
120 
121 Loop:
122     elem_debug(e);
123     const op = e.Eoper;
124     switch (op)
125     {
126         case OPcomma:
127             local_exp(lt,e.EV.E1,0);
128             e = e.EV.E2;
129             goto Loop;
130 
131         case OPandand:
132         case OPoror:
133             local_exp(lt,e.EV.E1,1);
134             lt.setLength(0);         // we can do better than this, fix later
135             break;
136 
137         case OPcolon:
138         case OPcolon2:
139             lt.setLength(0);         // we can do better than this, fix later
140             break;
141 
142         case OPinfo:
143             if (e.EV.E1.Eoper == OPmark)
144             {   lt.setLength(0);
145                 e = e.EV.E2;
146                 goto Loop;
147             }
148             goto case_bin;
149 
150         case OPdtor:
151         case OPctor:
152         case OPdctor:
153             lt.setLength(0);         // don't move expressions across ctor/dtor
154             break;              // boundaries, it would goof up EH cleanup
155 
156         case OPddtor:
157             lt.setLength(0);         // don't move expressions across ctor/dtor
158                                 // boundaries, it would goof up EH cleanup
159             local_exp(lt,e.EV.E1,0);
160             lt.setLength(0);
161             break;
162 
163         case OPeq:
164         case OPstreq:
165             e1 = e.EV.E1;
166             local_exp(lt,e.EV.E2,1);
167             if (e1.Eoper == OPvar)
168             {   s = e1.EV.Vsym;
169                 if (s.Sflags & SFLunambig)
170                 {   local_symdef(lt, s);
171                     if (!goal)
172                         local_ins(lt, e);
173                 }
174                 else
175                     local_ambigdef(lt);
176             }
177             else
178             {
179                 assert(!OTleaf(e1.Eoper));
180                 local_exp(lt,e1.EV.E1,1);
181                 if (OTbinary(e1.Eoper))
182                     local_exp(lt,e1.EV.E2,1);
183                 local_ambigdef(lt);
184             }
185             break;
186 
187         case OPpostinc:
188         case OPpostdec:
189         case OPaddass:
190         case OPminass:
191         case OPmulass:
192         case OPdivass:
193         case OPmodass:
194         case OPashrass:
195         case OPshrass:
196         case OPshlass:
197         case OPandass:
198         case OPxorass:
199         case OPorass:
200         case OPcmpxchg:
201             if (ERTOL(e))
202             {   local_exp(lt,e.EV.E2,1);
203         case OPnegass:
204                 e1 = e.EV.E1;
205                 op1 = e1.Eoper;
206                 if (op1 != OPvar)
207                 {
208                     local_exp(lt,e1.EV.E1,1);
209                     if (OTbinary(op1))
210                         local_exp(lt,e1.EV.E2,1);
211                 }
212                 else if (lt.length && (op == OPaddass || op == OPxorass))
213                 {
214                     s = e1.EV.Vsym;
215                     for (uint u = 0; u < lt.length; u++)
216                     {   elem *em;
217 
218                         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                 {   if (op1 == OPvar &&
258                         ((s = e1.EV.Vsym).Sflags & SFLunambig))
259                         local_symref(lt, s);
260                     else
261                         local_ambigref(lt);
262                 }
263                 local_exp(lt,e.EV.E2,1);
264             }
265             if (op1 == OPvar &&
266                 ((s = e1.EV.Vsym).Sflags & SFLunambig))
267             {   local_symref(lt, s);
268                 local_symdef(lt, s);
269                 if (op == OPaddass || op == OPxorass)
270                     local_ins(lt, e);
271             }
272             else if (lt.length)
273             {
274                 local_remove(lt, LFambigdef | LFambigref);
275             }
276             break;
277 
278         case OPstrlen:
279         case OPind:
280             local_exp(lt,e.EV.E1,1);
281             local_ambigref(lt);
282             break;
283 
284         case OPstrcmp:
285         case OPmemcmp:
286         case OPbt:
287             local_exp(lt,e.EV.E1,1);
288             local_exp(lt,e.EV.E2,1);
289             local_ambigref(lt);
290             break;
291 
292         case OPstrcpy:
293         case OPmemcpy:
294         case OPstrcat:
295         case OPcall:
296         case OPcallns:
297             local_exp(lt,e.EV.E2,1);
298             local_exp(lt,e.EV.E1,1);
299             goto Lrd;
300 
301         case OPstrctor:
302         case OPucall:
303         case OPucallns:
304             local_exp(lt,e.EV.E1,1);
305             goto Lrd;
306 
307         case OPbtc:
308         case OPbtr:
309         case OPbts:
310             local_exp(lt,e.EV.E1,1);
311             local_exp(lt,e.EV.E2,1);
312             goto Lrd;
313 
314         case OPasm:
315         Lrd:
316             local_remove(lt, LFfloat | LFambigref | LFambigdef);
317             break;
318 
319         case OPmemset:
320             local_exp(lt,e.EV.E2,1);
321             if (e.EV.E1.Eoper == OPvar)
322             {
323                 /* Don't want to rearrange (p = get(); p memset 0;)
324                  * as elemxxx() will rearrange it back.
325                  */
326                 s = e.EV.E1.EV.Vsym;
327                 if (s.Sflags & SFLunambig)
328                     local_symref(lt, s);
329                 else
330                     local_ambigref(lt);     // ambiguous reference
331             }
332             else
333                 local_exp(lt,e.EV.E1,1);
334             local_ambigdef(lt);
335             break;
336 
337         case OPvar:
338             s = e.EV.Vsym;
339             if (lt.length)
340             {
341                 // If potential candidate for replacement
342                 if (s.Sflags & SFLunambig)
343                 {
344                     foreach (const u; 0 .. lt.length)
345                     {
346                         auto em = lt[u].e;
347                         if (em.EV.E1.EV.Vsym == s &&
348                             (em.Eoper == OPeq || em.Eoper == OPstreq))
349                         {
350                             if (tysize(em.Ety) == tysize(e.Ety) &&
351                                 em.EV.E1.EV.Voffset == e.EV.Voffset &&
352                                 ((tyfloating(em.Ety) != 0) == (tyfloating(e.Ety) != 0) ||
353                                  /** Hack to fix https://issues.dlang.org/show_bug.cgi?id=10226
354                                   * Recognize assignments of float vectors to void16, as used by
355                                   * core.simd intrinsics. The backend type for void16 is Tschar16!
356                                   */
357                                  (tyvector(em.Ety) != 0) == (tyvector(e.Ety) != 0) && tybasic(e.Ety) == TYschar16) &&
358                                 /* Changing the Ety to a OPvecfill node means we're potentially generating
359                                  * wrong code.
360                                  * Ref: https://issues.dlang.org/show_bug.cgi?id=18034
361                                  */
362                                 (em.EV.E2.Eoper != OPvecfill || tybasic(e.Ety) == tybasic(em.Ety)) &&
363                                 !local_preserveAssignmentTo(em.EV.E1.Ety))
364                             {
365 
366                                 debug if (debugc)
367                                 {   printf("Moved equation ");
368                                     WReqn(em);
369                                     printf(";\n");
370                                 }
371 
372                                 go.changes++;
373                                 em.Ety = e.Ety;
374                                 el_copy(e,em);
375                                 em.EV.E1 = em.EV.E2 = null;
376                                 em.Eoper = OPconst;
377                             }
378                             local_rem(lt, u);
379                             break;
380                         }
381                     }
382                     local_symref(lt, s);
383                 }
384                 else
385                     local_ambigref(lt);     // ambiguous reference
386             }
387             break;
388 
389         case OPremquo:
390             if (e.EV.E1.Eoper != OPvar)
391                 goto case_bin;
392             s = e.EV.E1.EV.Vsym;
393             if (lt.length)
394             {
395                 if (s.Sflags & SFLunambig)
396                     local_symref(lt, s);
397                 else
398                     local_ambigref(lt);     // ambiguous reference
399             }
400             goal = 1;
401             e = e.EV.E2;
402             goto Loop;
403 
404         default:
405             if (OTcommut(e.Eoper))
406             {   // Since commutative operators may get their leaves
407                 // swapped, we eliminate any that may be affected by that.
408 
409                 for (uint u = 0; u < lt.length;)
410                 {
411                     const f = lt[u].flags;
412                     elem* eu = lt[u].e;
413                     s = eu.EV.E1.EV.Vsym;
414                     const f1 = local_getflags(e.EV.E1,s);
415                     const f2 = local_getflags(e.EV.E2,s);
416                     if (f1 & f2 & LFsymref ||   // if both reference or
417                         (f1 | f2) & LFsymdef || // either define
418                         f & LFambigref && (f1 | f2) & LFambigdef ||
419                         f & LFambigdef && (f1 | f2) & (LFambigref | LFambigdef)
420                        )
421                         local_rem(lt, u);
422                     else if (f & LFunambigdef && local_chkrem(e,eu.EV.E2))
423                         local_rem(lt, u);
424                     else
425                         u++;
426                 }
427             }
428             if (OTunary(e.Eoper))
429             {   goal = 1;
430                 e = e.EV.E1;
431                 goto Loop;
432             }
433         case_bin:
434             if (OTbinary(e.Eoper))
435             {   local_exp(lt,e.EV.E1,1);
436                 goal = 1;
437                 e = e.EV.E2;
438                 goto Loop;
439             }
440             break;
441     }   // end of switch (e.Eoper)
442 }
443 
444 ///////////////////////////////////
445 // Examine expression tree eu to see if it defines any variables
446 // that e refs or defs.
447 // Note that e is a binary operator.
448 // Returns:
449 //      true if it does
450 
451 private bool local_chkrem(elem *e,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             auto 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 private void local_ins(ref Barray!loc_t lt, elem *e)
481 {
482     elem_debug(e);
483     if (e.EV.E1.Eoper == OPvar)
484     {
485         auto s = e.EV.E1.EV.Vsym;
486         symbol_debug(s);
487         if (s.Sflags & SFLunambig)     // if can only be referenced directly
488         {
489             const flags = local_getflags(e.EV.E2,null);
490             if (!(flags & (LFvolatile | LFinp | LFoutp)) &&
491                 !(e.EV.E1.Ety & (mTYvolatile | mTYshared)))
492             {
493                 // Add e to the candidate array
494                 //printf("local_ins('%s'), loctop = %d\n",s.Sident.ptr,lt.length);
495                 lt.push(loc_t(e, flags));
496             }
497         }
498     }
499 }
500 
501 //////////////////////////////////////
502 // Remove entry i from lt[], and then compress the table.
503 //
504 
505 private void local_rem(ref Barray!loc_t lt, size_t u)
506 {
507     //printf("local_rem(%u)\n",u);
508     lt.remove(u);
509 }
510 
511 //////////////////////////////////////
512 // Analyze and gather LFxxxx flags about expression e and symbol s.
513 
514 private int local_getflags(elem *e,Symbol *s)
515 {
516     elem_debug(e);
517     if (s)
518         symbol_debug(s);
519     int flags = 0;
520     while (1)
521     {
522         if (e.Ety & (mTYvolatile | mTYshared))
523             flags |= LFvolatile;
524         switch (e.Eoper)
525         {
526             case OPeq:
527             case OPstreq:
528                 if (e.EV.E1.Eoper == OPvar)
529                 {
530                     auto s1 = e.EV.E1.EV.Vsym;
531                     if (s1.Sflags & SFLunambig)
532                         flags |= (s1 == s) ? LFsymdef : LFunambigdef;
533                     else
534                         flags |= LFambigdef;
535                 }
536                 else
537                     flags |= LFambigdef;
538                 goto L1;
539 
540             case OPpostinc:
541             case OPpostdec:
542             case OPaddass:
543             case OPminass:
544             case OPmulass:
545             case OPdivass:
546             case OPmodass:
547             case OPashrass:
548             case OPshrass:
549             case OPshlass:
550             case OPandass:
551             case OPxorass:
552             case OPorass:
553             case OPcmpxchg:
554                 if (e.EV.E1.Eoper == OPvar)
555                 {
556                     auto s1 = e.EV.E1.EV.Vsym;
557                     if (s1.Sflags & SFLunambig)
558                         flags |= (s1 == s) ? LFsymdef | LFsymref
559                                            : LFunambigdef | LFunambigref;
560                     else
561                         flags |= LFambigdef | LFambigref;
562                 }
563                 else
564                     flags |= LFambigdef | LFambigref;
565             L1:
566                 flags |= local_getflags(e.EV.E2,s);
567                 e = e.EV.E1;
568                 break;
569 
570             case OPucall:
571             case OPucallns:
572             case OPcall:
573             case OPcallns:
574             case OPstrcat:
575             case OPstrcpy:
576             case OPmemcpy:
577             case OPbtc:
578             case OPbtr:
579             case OPbts:
580             case OPstrctor:
581                 flags |= LFambigref | LFambigdef;
582                 break;
583 
584             case OPmemset:
585                 flags |= LFambigdef;
586                 break;
587 
588             case OPvar:
589                 if (e.EV.Vsym == s)
590                     flags |= LFsymref;
591                 else if (!(e.EV.Vsym.Sflags & SFLunambig))
592                     flags |= LFambigref;
593                 break;
594 
595             case OPind:
596             case OPstrlen:
597             case OPstrcmp:
598             case OPmemcmp:
599             case OPbt:
600                 flags |= LFambigref;
601                 break;
602 
603             case OPinp:
604                 flags |= LFinp;
605                 break;
606 
607             case OPoutp:
608                 flags |= LFoutp;
609                 break;
610 
611             default:
612                 break;
613         }
614         if (OTunary(e.Eoper))
615         {
616             if (tyfloating(e.Ety))
617                 flags |= LFfloat;
618             e = e.EV.E1;
619         }
620         else if (OTbinary(e.Eoper))
621         {
622             if (tyfloating(e.Ety))
623                 flags |= LFfloat;
624             flags |= local_getflags(e.EV.E2,s);
625             e = e.EV.E1;
626         }
627         else
628             break;
629     }
630     return flags;
631 }
632 
633 //////////////////////////////////////
634 // Remove all entries with flags set.
635 //
636 
637 private void local_remove(ref Barray!loc_t lt, int flags)
638 {
639     for (uint u = 0; u < lt.length;)
640     {
641         if (lt[u].flags & flags)
642             local_rem(lt, u);
643         else
644             ++u;
645     }
646 }
647 
648 //////////////////////////////////////
649 // Ambiguous reference. Remove all with ambiguous defs
650 //
651 
652 private void local_ambigref(ref Barray!loc_t lt)
653 {
654     local_remove(lt, LFambigdef);
655 }
656 
657 //////////////////////////////////////
658 // Ambiguous definition. Remove all with ambiguous refs.
659 //
660 
661 private void local_ambigdef(ref Barray!loc_t lt)
662 {
663     local_remove(lt, LFambigref | LFambigdef);
664 }
665 
666 //////////////////////////////////////
667 // Reference to symbol.
668 // Remove any that define that symbol.
669 
670 private void local_symref(ref Barray!loc_t lt, Symbol *s)
671 {
672     symbol_debug(s);
673     for (uint u = 0; u < lt.length;)
674     {
675         if (local_getflags(lt[u].e,s) & LFsymdef)
676             local_rem(lt, u);
677         else
678             ++u;
679     }
680 }
681 
682 //////////////////////////////////////
683 // Definition of symbol.
684 // Remove any that reference that symbol.
685 
686 private void local_symdef(ref Barray!loc_t lt, Symbol *s)
687 {
688     symbol_debug(s);
689     for (uint u = 0; u < lt.length;)
690     {
691         if (local_getflags(lt[u].e,s) & (LFsymref | LFsymdef))
692             local_rem(lt, u);
693         else
694             ++u;
695     }
696 }
697 
698 /***************************************************
699  * See if we should preserve assignment to Symbol of type ty.
700  * Returns:
701  *      true if preserve assignment
702  * References:
703  *      https://issues.dlang.org/show_bug.cgi?id=13474
704  */
705 private bool local_preserveAssignmentTo(tym_t ty)
706 {
707     /* Need to preserve assignment if generating code using
708      * the x87, as that is the only way to get the x87 to
709      * convert to float/double precision.
710      */
711     if (config.inline8087 && !config.fpxmmregs)
712     {
713         switch (tybasic(ty))
714         {
715             case TYfloat:
716             case TYifloat:
717             case TYcfloat:
718             case TYdouble:
719             case TYidouble:
720             case TYdouble_alias:
721             case TYcdouble:
722                 return true;
723 
724             default:
725                 break;
726         }
727     }
728     return false;
729 }
730 
731 }