1 /**
2  * Compiler implementation of the
3  * $(LINK2 http://www.dlang.org, D programming language).
4  *
5  * Manage the memory allocated on the runtime stack to save Common Subexpressions (CSE).
6  *
7  * Copyright:   Copyright (C) 1985-1998 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:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/cgcse.d, backend/cgcse.d)
12  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/backend/cgcse.d
13  */
14 
15 module dmd.backend.cgcse;
16 
17 version (SCPP)
18     version = COMPILE;
19 version (MARS)
20     version = COMPILE;
21 
22 version (COMPILE)
23 {
24 
25 import core.stdc.stdio;
26 import core.stdc.stdlib;
27 import core.stdc..string;
28 
29 import dmd.backend.cc;
30 import dmd.backend.cdef;
31 import dmd.backend.code;
32 import dmd.backend.code_x86;
33 import dmd.backend.el;
34 import dmd.backend.global;
35 import dmd.backend.ty;
36 
37 import dmd.backend.barray;
38 
39 extern (C++):
40 nothrow:
41 
42 
43 /****************************
44  * Table of common subexpressions stored on the stack.
45  *      csextab[]       array of info on saved CSEs
46  *      CSEpe           pointer to saved elem
47  *      CSEregm         mask of register that was saved (so for multi-
48  *                      register variables we know which part we have)
49  */
50 
51 enum CSEload       = 1;       // set if the CSE was ever loaded
52 enum CSEsimple     = 2;       // CSE can be regenerated easily
53 
54 struct CSE
55 {
56     elem*   e;              // pointer to elem
57     code    csimple;        // if CSEsimple, this is the code to regenerate it
58     regm_t  regm;           // mask of register stored there
59     int     slot;           // slot number
60     ubyte   flags;          // flag bytes
61 
62   nothrow:
63 
64     /************************
65      * Initialize at function entry.
66      */
67     static void initialize()
68     {
69         csextab.setLength(64);  // reserve some space
70     }
71 
72     /************************
73      * Start for generating code for this function.
74      * After ending generation, call finish().
75      */
76     static void start()
77     {
78         csextab.setLength(0);               // no entries in table yet
79         slotSize = REGSIZE;
80         alignment_ = REGSIZE;
81     }
82 
83     /*******************************
84      * Create and add a new CSE entry.
85      * Returns:
86      *  pointer to created entry
87      */
88     static CSE* add()
89     {
90         foreach (ref cse; csextab)
91         {
92             if (cse.e == null)  // can share with previously used one
93             {
94                 cse.flags &= CSEload;
95                 return &cse;
96             }
97         }
98 
99         // create new one
100         const slot = cast(int)csextab.length;
101         CSE cse;
102         cse.slot = slot;
103         csextab.push(cse);
104         return &csextab[slot];
105     }
106 
107     /********************************
108      * Update slot size and alignment to worst case.
109      *
110      * A bit wasteful of stack space.
111      * Params: e = elem with a size and an alignment
112      */
113     static void updateSizeAndAlign(elem* e)
114     {
115         if (I16)
116             return;
117         const sz = tysize(e.Ety);
118         if (slotSize < sz)
119             slotSize = sz;
120         const alignsize = el_alignsize(e);
121 
122         static if (0)
123         printf("set slot size = %d, sz = %d, al = %d, ty = x%x, %s\n",
124             slotSize, cast(int)sz, cast(int)alignsize,
125             cast(int)tybasic(e.Ety), funcsym_p.Sident.ptr);
126 
127         if (alignsize >= 16 && TARGET_STACKALIGN >= 16)
128         {
129             alignment_ = alignsize;
130             STACKALIGN = alignsize;
131             enforcealign = true;
132         }
133     }
134 
135     /****
136      * Get range of all CSEs filtered by matching `e`,
137      * starting with most recent.
138      * Params: e = elem to match
139      * Returns:
140      *  input range
141      */
142     static auto filter(const elem* e)
143     {
144         struct Range
145         {
146             const elem* e;
147             int i;
148 
149           nothrow:
150 
151             bool empty()
152             {
153                 while (i)
154                 {
155                     if (csextab[i - 1].e == e)
156                         return false;
157                     --i;
158                 }
159                 return true;
160             }
161 
162             ref CSE front() { return csextab[i - 1]; }
163 
164             void popFront() { --i; }
165         }
166 
167         return Range(e, cast(int)csextab.length);
168     }
169 
170     /*********************
171      * Remove instances of `e` from CSE table.
172      * Params: e = elem to remove
173      */
174     static void remove(const elem* e)
175     {
176         foreach (ref cse; csextab[])
177         {
178             if (cse.e == e)
179                 cse.e = null;
180         }
181     }
182 
183     /************************
184      * Create mask of registers from CSEs that refer to `e`.
185      * Params: e = elem to match
186      * Returns:
187      *  mask
188      */
189     static regm_t mask(const elem* e)
190     {
191         regm_t result = 0;
192         foreach (ref cse; csextab[])
193         {
194             if (cse.e)
195                 elem_debug(cse.e);
196             if (cse.e == e)
197                 result |= cse.regm;
198         }
199         return result;
200     }
201 
202     /***
203      * Finish generating code for this function.
204      *
205      * Get rid of unused cse temporaries by shrinking the array.
206      * References: loaded()
207      */
208     static void finish()
209     {
210         while (csextab.length != 0 && (csextab[csextab.length - 1].flags & CSEload) == 0)
211             csextab.setLength(csextab.length - 1);
212     }
213 
214     /**** The rest of the functions can be called only after finish() ****/
215 
216     /******************
217      * Returns:
218      *    total size used by CSE's
219      */
220     static uint size()
221     {
222         return cast(uint)csextab.length * CSE.slotSize;
223     }
224 
225     /*********************
226      * Returns:
227      *  alignment needed for CSE region of the stack
228      */
229     static uint alignment()
230     {
231         return alignment_;
232     }
233 
234     /// Returns: offset of slot i from start of CSE region
235     static uint offset(int i)
236     {
237         return i * slotSize;
238     }
239 
240     /// Returns: true if CSE was ever loaded
241     static bool loaded(int i)
242     {
243         return i < csextab.length &&   // array could be shrunk for non-CSEload entries
244                (csextab[i].flags & CSEload);
245     }
246 
247   private:
248   __gshared:
249     Barray!CSE csextab;     // CSE table (allocated for each function)
250     uint slotSize;          // size of each slot in table
251     uint alignment_;        // alignment for the table
252 }
253 
254 
255 /********************
256  * The above implementation of CSE is inefficient:
257  * 1. the optimization to not store CSE's that are never reloaded is based on the slot number,
258  * not the CSE. This means that when a slot is shared among multiple CSEs, it is treated
259  * as "reloaded" even if only one of the CSEs in that slot is reloaded.
260  * 2. updateSizeAndAlign should only be run when reloading when (1) is fixed.
261  * 3. all slots are aligned to worst case alignment of any slot.
262  * 4. unused slots still get memory allocated to them if they aren't at the end of the
263  * slot table.
264  *
265  * The slot number should be unique to each CSE, and allocation of actual slots should be
266  * done after the code is generated, not during generation.
267  */
268 
269 
270 }