1 /**
2  * Compiler implementation of the
3  * $(LINK2 http://www.dlang.org, D programming language).
4  *
5  * Compute common subexpressions for non-optimized builds.
6  *
7  * Copyright:   Copyright (C) 1985-1995 by Symantec
8  *              Copyright (C) 2000-2020 by The D Language Foundation, All Rights Reserved
9  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
10  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
11  * Source:      https://github.com/dlang/dmd/blob/master/src/dmd/backend/cgcs.d
12  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/backend/cgcs.d
13  */
14 
15 module dmd.backend.cgcs;
16 
17 version (SPP)
18 {
19 }
20 else
21 {
22 
23 import core.stdc.stdio;
24 import core.stdc.stdlib;
25 
26 import dmd.backend.cc;
27 import dmd.backend.cdef;
28 import dmd.backend.code;
29 import dmd.backend.el;
30 import dmd.backend.global;
31 import dmd.backend.oper;
32 import dmd.backend.ty;
33 import dmd.backend.type;
34 
35 import dmd.backend.barray;
36 import dmd.backend.dlist;
37 import dmd.backend.dvec;
38 
39 
40 nothrow:
41 
42 /*******************************
43  * Eliminate common subexpressions across extended basic blocks.
44  * String together as many blocks as we can.
45  */
46 
47 public extern (C++) void comsubs()
48 {
49     //static int xx;
50     //printf("comsubs() %d\n", ++xx);
51     //debugx = (xx == 37);
52 
53     debug if (debugx) printf("comsubs(%p)\n",startblock);
54 
55     // No longer do we just compute Bcount. We now eliminate unreachable
56     // blocks.
57     block_compbcount();                   // eliminate unreachable blocks
58 
59     version (SCPP)
60     {
61         if (errcnt)
62             return;
63     }
64 
65     if (!csvec)
66     {
67         csvec = vec_calloc(CSVECDIM);
68     }
69 
70     block* bln;
71     for (block* bl = startblock; bl; bl = bln)
72     {
73         bln = bl.Bnext;
74         if (!bl.Belem)
75             continue;                   /* if no expression or no parents       */
76 
77         // Count up n, the number of blocks in this extended basic block (EBB)
78         int n = 1;                      // always at least one block in EBB
79         auto blc = bl;
80         while (bln && list_nitems(bln.Bpred) == 1 &&
81                ((blc.BC == BCiftrue &&
82                  blc.nthSucc(1) == bln) ||
83                 (blc.BC == BCgoto && blc.nthSucc(0) == bln)
84                ) &&
85                bln.BC != BCasm         // no CSE's extending across ASM blocks
86               )
87         {
88             n++;                    // add block to EBB
89             blc = bln;
90             bln = blc.Bnext;
91         }
92         vec_clear(csvec);
93         hcstab.setLength(0);
94         hcsarray.touchstari = 0;
95         hcsarray.touchfunci[0] = 0;
96         hcsarray.touchfunci[1] = 0;
97         bln = bl;
98         while (n--)                     // while more blocks in EBB
99         {
100             debug if (debugx)
101                 printf("cses for block %p\n",bln);
102 
103             if (bln.Belem)
104                 ecom(&bln.Belem);  // do the tree
105             bln = bln.Bnext;
106         }
107     }
108 
109     debug if (debugx)
110         printf("done with comsubs()\n");
111 }
112 
113 /*******************************
114  */
115 
116 public extern (C++) void cgcs_term()
117 {
118     vec_free(csvec);
119     csvec = null;
120     debug debugw && printf("freeing hcstab\n");
121     //hcstab.dtor();  // cache allocation for next iteration
122 }
123 
124 
125 /***********************************************************************/
126 
127 private:
128 
129 alias hash_t = uint;    // for hash values
130 
131 /*********************************
132  * Struct for each elem:
133  *      Helem   pointer to elem
134  *      Hhash   hash value for the elem
135  */
136 
137 struct HCS
138 {
139     elem* Helem;
140     hash_t Hhash;
141 }
142 
143 struct HCSArray
144 {
145     uint touchstari;
146     uint[2] touchfunci;
147 }
148 
149 __gshared
150 {
151     Barray!HCS hcstab;           // array of hcs's
152     HCSArray hcsarray;
153 
154     // Use a bit vector for quick check if expression is possibly in hcstab[].
155     // This results in much faster compiles when hcstab[] gets big.
156     vec_t csvec;                 // vector of used entries
157     enum CSVECDIM = 16001; //8009 //3001     // dimension of csvec (should be prime)
158 }
159 
160 
161 /*************************
162  * Eliminate common subexpressions for an element.
163  */
164 
165 void ecom(elem **pe)
166 {
167     auto e = *pe;
168     assert(e);
169     elem_debug(e);
170     debug assert(e.Ecount == 0);
171     //assert(e.Ecomsub == 0);
172     const tym = tybasic(e.Ety);
173     const op = e.Eoper;
174     switch (op)
175     {
176         case OPconst:
177         case OPrelconst:
178             break;
179 
180         case OPvar:
181             if (e.EV.Vsym.ty() & mTYshared)
182                 return;         // don't cache shared variables
183             break;
184 
185         case OPstreq:
186         case OPpostinc:
187         case OPpostdec:
188         case OPeq:
189         case OPaddass:
190         case OPminass:
191         case OPmulass:
192         case OPdivass:
193         case OPmodass:
194         case OPshrass:
195         case OPashrass:
196         case OPshlass:
197         case OPandass:
198         case OPxorass:
199         case OPorass:
200         case OPvecsto:
201             /* Reverse order of evaluation for double op=. This is so that  */
202             /* the pushing of the address of the second operand is easier.  */
203             /* However, with the 8087 we don't need the kludge.             */
204             if (op != OPeq && tym == TYdouble && !config.inline8087)
205             {
206                 if (!OTleaf(e.EV.E1.Eoper))
207                     ecom(&e.EV.E1.EV.E1);
208                 ecom(&e.EV.E2);
209             }
210             else
211             {
212                 /* Don't mark the increment of an i++ or i-- as a CSE, if it */
213                 /* can be done with an INC or DEC instruction.               */
214                 if (!(OTpost(op) && elemisone(e.EV.E2)))
215                     ecom(&e.EV.E2);           /* evaluate 2nd operand first   */
216         case OPnegass:
217                 if (!OTleaf(e.EV.E1.Eoper))             /* if lvalue is an operator     */
218                 {
219                     if (e.EV.E1.Eoper != OPind)
220                         elem_print(e);
221                     assert(e.EV.E1.Eoper == OPind);
222                     ecom(&(e.EV.E1.EV.E1));
223                 }
224             }
225             touchlvalue(e.EV.E1);
226             if (!OTpost(op))                /* lvalue of i++ or i-- is not a cse*/
227             {
228                 const hash = cs_comphash(e.EV.E1);
229                 vec_setbit(hash % CSVECDIM,csvec);
230                 addhcstab(e.EV.E1,hash);              // add lvalue to hcstab[]
231             }
232             return;
233 
234         case OPbtc:
235         case OPbts:
236         case OPbtr:
237         case OPcmpxchg:
238             ecom(&e.EV.E1);
239             ecom(&e.EV.E2);
240             touchfunc(0);                   // indirect assignment
241             return;
242 
243         case OPandand:
244         case OPoror:
245         {
246             ecom(&e.EV.E1);
247             const lengthSave = hcstab.length;
248             auto hcsarraySave = hcsarray;
249             ecom(&e.EV.E2);
250             hcsarray = hcsarraySave;        // no common subs by E2
251             hcstab.setLength(lengthSave);
252             return;                         /* if comsub then logexp() will */
253         }
254 
255         case OPcond:
256         {
257             ecom(&e.EV.E1);
258             const lengthSave = hcstab.length;
259             auto hcsarraySave = hcsarray;
260             ecom(&e.EV.E2.EV.E1);               // left condition
261             hcsarray = hcsarraySave;        // no common subs by E2
262             hcstab.setLength(lengthSave);
263             ecom(&e.EV.E2.EV.E2);               // right condition
264             hcsarray = hcsarraySave;        // no common subs by E2
265             hcstab.setLength(lengthSave);
266             return;                         // can't be a common sub
267         }
268 
269         case OPcall:
270         case OPcallns:
271             ecom(&e.EV.E2);                   /* eval right first             */
272             goto case OPucall;
273 
274         case OPucall:
275         case OPucallns:
276             ecom(&e.EV.E1);
277             touchfunc(1);
278             return;
279 
280         case OPstrpar:                      /* so we don't break logexp()   */
281         case OPinp:                 /* never CSE the I/O instruction itself */
282         case OPprefetch:            // don't CSE E2 or the instruction
283             ecom(&e.EV.E1);
284             goto case OPasm;
285 
286         case OPasm:
287         case OPstrthis:             // don't CSE these
288         case OPframeptr:
289         case OPgot:
290         case OPctor:
291         case OPdtor:
292         case OPdctor:
293         case OPmark:
294             return;
295 
296         case OPddtor:
297             touchall();
298             ecom(&e.EV.E1);
299             touchall();
300             return;
301 
302         case OPparam:
303         case OPoutp:
304             ecom(&e.EV.E1);
305             goto case OPinfo;
306 
307         case OPinfo:
308             ecom(&e.EV.E2);
309             return;
310 
311         case OPcomma:
312             ecom(&e.EV.E1);
313             ecom(&e.EV.E2);
314             return;
315 
316         case OPremquo:
317             ecom(&e.EV.E1);
318             ecom(&e.EV.E2);
319             break;
320 
321         case OPvp_fp:
322         case OPcvp_fp:
323             ecom(&e.EV.E1);
324             touchaccess(hcstab, e);
325             break;
326 
327         case OPind:
328             ecom(&e.EV.E1);
329             /* Generally, CSEing a *(double *) results in worse code        */
330             if (tyfloating(tym))
331                 return;
332             if (tybasic(e.EV.E1.Ety) == TYsharePtr)
333                 return;
334             break;
335 
336         case OPstrcpy:
337         case OPstrcat:
338         case OPmemcpy:
339         case OPmemset:
340             ecom(&e.EV.E2);
341             goto case OPsetjmp;
342 
343         case OPsetjmp:
344             ecom(&e.EV.E1);
345             touchfunc(0);
346             return;
347 
348         default:                            /* other operators */
349             if (!OTbinary(e.Eoper))
350                WROP(e.Eoper);
351             assert(OTbinary(e.Eoper));
352             goto case OPadd;
353 
354         case OPadd:
355         case OPmin:
356         case OPmul:
357         case OPdiv:
358         case OPor:
359         case OPxor:
360         case OPand:
361         case OPeqeq:
362         case OPne:
363         case OPscale:
364         case OPyl2x:
365         case OPyl2xp1:
366             ecom(&e.EV.E1);
367             ecom(&e.EV.E2);
368             break;
369 
370         case OPstring:
371         case OPaddr:
372         case OPbit:
373             WROP(e.Eoper);
374             elem_print(e);
375             assert(0);              /* optelem() should have removed these  */
376             /* NOTREACHED */
377 
378         // Explicitly list all the unary ops for speed
379         case OPnot: case OPcom: case OPneg: case OPuadd:
380         case OPabs: case OPrndtol: case OPrint:
381         case OPpreinc: case OPpredec:
382         case OPbool: case OPstrlen: case OPs16_32: case OPu16_32:
383         case OPs32_d: case OPu32_d: case OPd_s16: case OPs16_d: case OP32_16:
384         case OPf_d:
385         case OPld_d:
386         case OPc_r: case OPc_i:
387         case OPu8_16: case OPs8_16: case OP16_8:
388         case OPu32_64: case OPs32_64: case OP64_32: case OPmsw:
389         case OPu64_128: case OPs64_128: case OP128_64:
390         case OPs64_d: case OPd_u64: case OPu64_d:
391         case OPstrctor: case OPu16_d: case OPd_u16:
392         case OParrow:
393         case OPvoid:
394         case OPbsf: case OPbsr: case OPbswap: case OPpopcnt: case OPvector:
395         case OPld_u64:
396         case OPsqrt: case OPsin: case OPcos:
397         case OPoffset: case OPnp_fp: case OPnp_f16p: case OPf16p_np:
398         case OPvecfill:
399             ecom(&e.EV.E1);
400             break;
401 
402         case OPd_ld:
403             return;
404 
405         case OPd_f:
406         {
407             const op1 = e.EV.E1.Eoper;
408             if (config.fpxmmregs &&
409                 (op1 == OPs32_d ||
410                  I64 && (op1 == OPs64_d || op1 == OPu32_d))
411                )
412                 ecom(&e.EV.E1.EV.E1);   // e and e1 ops are fused (see xmmcnvt())
413             else
414                 ecom(&e.EV.E1);
415             break;
416         }
417 
418         case OPd_s32:
419         case OPd_u32:
420         case OPd_s64:
421             if (e.EV.E1.Eoper == OPf_d && config.fpxmmregs)
422                 ecom(&e.EV.E1.EV.E1);   // e and e1 ops are fused (see xmmcnvt());
423             else
424                 ecom(&e.EV.E1);
425             break;
426 
427         case OPhalt:
428             return;
429     }
430 
431     /* don't CSE structures or unions or volatile stuff   */
432     if (tym == TYstruct ||
433         tym == TYvoid ||
434         e.Ety & mTYvolatile)
435         return;
436     if (tyfloating(tym) && config.inline8087)
437     {
438         /* can CSE XMM code, but not x87
439          */
440         if (!(config.fpxmmregs && tyxmmreg(tym)))
441             return;
442     }
443 
444     const hash = cs_comphash(e);                /* must be AFTER leaves are done */
445 
446     /* Search for a match in hcstab[].
447      * Search backwards, as most likely matches will be towards the end
448      * of the list.
449      */
450 
451     debug if (debugx) printf("elem: %p hash: %6d\n",e,hash);
452     int csveci = hash % CSVECDIM;
453     if (vec_testbit(csveci,csvec))
454     {
455         foreach_reverse (i, ref hcs; hcstab[])
456         {
457             debug if (debugx)
458                 printf("i: %2d Hhash: %6d Helem: %p\n",
459                        cast(int) i,hcs.Hhash,hcs.Helem);
460 
461             elem* ehash;
462             if (hash == hcs.Hhash && (ehash = hcs.Helem) != null)
463             {
464                 /* if elems are the same and we still have room for more    */
465                 if (el_match(e,ehash) && ehash.Ecount < 0xFF)
466                 {
467                     /* Make sure leaves are also common subexpressions
468                      * to avoid false matches.
469                      */
470                     if (!OTleaf(op))
471                     {
472                         if (!e.EV.E1.Ecount)
473                             continue;
474                         if (OTbinary(op) && !e.EV.E2.Ecount)
475                             continue;
476                     }
477                     ehash.Ecount++;
478                     *pe = ehash;
479 
480                     debug if (debugx)
481                         printf("**MATCH** %p with %p\n",e,*pe);
482 
483                     el_free(e);
484                     return;
485                 }
486             }
487         }
488     }
489     else
490         vec_setbit(csveci,csvec);
491     addhcstab(e,hash);                    // add this elem to hcstab[]
492 }
493 
494 /**************************
495  * Compute hash function for elem e.
496  */
497 
498 hash_t cs_comphash(const elem *e)
499 {
500     elem_debug(e);
501     const op = e.Eoper;
502     hash_t hash = (e.Ety & (mTYbasic | mTYconst | mTYvolatile)) + (op << 8);
503     if (!OTleaf(op))
504     {
505         hash += cast(size_t) e.EV.E1;
506         if (OTbinary(op))
507             hash += cast(size_t) e.EV.E2;
508     }
509     else
510     {
511         hash += e.EV.Vint;
512         if (op == OPvar || op == OPrelconst)
513             hash += cast(size_t) e.EV.Vsym;
514     }
515     return hash;
516 }
517 
518 /****************************
519  * Add an elem to the common subexpression table.
520  */
521 
522 void addhcstab(elem *e, hash_t hash)
523 {
524     hcstab.push(HCS(e, hash));
525 }
526 
527 /***************************
528  * "touch" the elem.
529  * If it is a pointer, "touch" all the suspects
530  * who could be pointed to.
531  * Eliminate common subs that are indirect loads.
532  */
533 
534 void touchlvalue(elem *e)
535 {
536     if (e.Eoper == OPind)                /* if indirect store            */
537     {
538         /* NOTE: Some types of array assignments do not need
539          * to touch all variables. (Like a[5], where a is an
540          * array instead of a pointer.)
541          */
542 
543         touchfunc(0);
544         return;
545     }
546 
547     foreach_reverse (ref hcs; hcstab[])
548     {
549         if (hcs.Helem &&
550             hcs.Helem.EV.Vsym == e.EV.Vsym)
551             hcs.Helem = null;
552     }
553 
554     if (!(e.Eoper == OPvar || e.Eoper == OPrelconst))
555         elem_print(e);
556     assert(e.Eoper == OPvar || e.Eoper == OPrelconst);
557     switch (e.EV.Vsym.Sclass)
558     {
559         case SCregpar:
560         case SCregister:
561         case SCpseudo:
562             break;
563 
564         case SCauto:
565         case SCparameter:
566         case SCfastpar:
567         case SCshadowreg:
568         case SCbprel:
569             if (e.EV.Vsym.Sflags & SFLunambig)
570                 break;
571             goto case SCstatic;
572 
573         case SCstatic:
574         case SCextern:
575         case SCglobal:
576         case SClocstat:
577         case SCcomdat:
578         case SCinline:
579         case SCsinline:
580         case SCeinline:
581         case SCcomdef:
582             touchstar();
583             break;
584 
585         default:
586             elem_print(e);
587             symbol_print(e.EV.Vsym);
588             assert(0);
589     }
590 }
591 
592 /**************************
593  * "touch" variables that could be changed by a function call or
594  * an indirect assignment.
595  * Eliminate any subexpressions that are "starred" (they need to
596  * be recomputed).
597  * Params:
598  *      flag =  If 1, then this is a function call.
599  *              If 0, then this is an indirect assignment.
600  */
601 
602 void touchfunc(int flag)
603 {
604 
605     //printf("touchfunc(%d)\n", flag);
606     HCS *petop = hcstab.ptr + hcstab.length;
607     //pe = &hcstab[0]; printf("pe = %p, petop = %p\n",pe,petop);
608     assert(hcsarray.touchfunci[flag] <= hcstab.length);
609     for (HCS *pe = hcstab.ptr + hcsarray.touchfunci[flag]; pe < petop; pe++)
610     {
611         elem *he = pe.Helem;
612         if (!he)
613             continue;
614         switch (he.Eoper)
615         {
616             case OPvar:
617                 if (Symbol_isAffected(*he.EV.Vsym))
618                 {
619                     pe.Helem = null;
620                     continue;
621                 }
622                 break;
623 
624             case OPind:
625                 if (tybasic(he.EV.E1.Ety) == TYimmutPtr)
626                     break;
627                 goto Ltouch;
628 
629             case OPstrlen:
630             case OPstrcmp:
631             case OPmemcmp:
632             case OPbt:
633                 goto Ltouch;
634 
635             case OPvp_fp:
636             case OPcvp_fp:
637                 if (flag == 0)          /* function calls destroy vptrfptr's, */
638                     break;              /* not indirect assignments     */
639             Ltouch:
640                 pe.Helem = null;
641                 break;
642 
643             default:
644                 break;
645         }
646     }
647     hcsarray.touchfunci[flag] = cast(uint)hcstab.length;
648 }
649 
650 
651 /*******************************
652  * Eliminate all common subexpressions that
653  * do any indirection ("starred" elems).
654  */
655 
656 void touchstar()
657 {
658     foreach (ref hcs; hcstab[hcsarray.touchstari .. $])
659     {
660         const e = hcs.Helem;
661         if (e &&
662                (e.Eoper == OPind && tybasic(e.EV.E1.Ety) != TYimmutPtr ||
663                 e.Eoper == OPbt) )
664             hcs.Helem = null;
665     }
666     hcsarray.touchstari = cast(uint)hcstab.length;
667 }
668 
669 /*******************************
670  * Eliminate all common subexpressions.
671  */
672 
673 void touchall()
674 {
675     foreach (ref hcs; hcstab[])
676     {
677         hcs.Helem = null;
678     }
679     hcsarray.touchstari    = cast(uint)hcstab.length;
680     hcsarray.touchfunci[0] = cast(uint)hcstab.length;
681     hcsarray.touchfunci[1] = cast(uint)hcstab.length;
682 }
683 
684 /*****************************************
685  * Eliminate any common subexpressions that could be modified
686  * if a handle pointer access occurs.
687  */
688 
689 void touchaccess(ref Barray!HCS hcstab, const elem *ev) pure nothrow
690 {
691     const ev1 = ev.EV.E1;
692     foreach (ref hcs; hcstab[])
693     {
694         const e = hcs.Helem;
695         /* Invalidate any previous handle pointer accesses that */
696         /* are not accesses of ev.                              */
697         if (e && (e.Eoper == OPvp_fp || e.Eoper == OPcvp_fp) && e.EV.E1 != ev1)
698             hcs.Helem = null;
699     }
700 }
701 
702 }