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