dmd.backend.cgcs source code

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