1 /**
2  * Compute the cost of inlining a function call by counting expressions.
3  *
4  * Copyright:   Copyright (C) 1999-2020 by The D Language Foundation, All Rights Reserved
5  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
6  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
7  * Source:    $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/inlinecost.d, _inlinecost.d)
8  * Documentation:  https://dlang.org/phobos/dmd_inlinecost.html
9  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/inlinecost.d
10  */
11 
12 module dmd.inlinecost;
13 
14 import core.stdc.stdio;
15 import core.stdc.string;
16 
17 import dmd.aggregate;
18 import dmd.apply;
19 import dmd.arraytypes;
20 import dmd.attrib;
21 import dmd.dclass;
22 import dmd.declaration;
23 import dmd.dmodule;
24 import dmd.dscope;
25 import dmd.dstruct;
26 import dmd.dsymbol;
27 import dmd.expression;
28 import dmd.func;
29 import dmd.globals;
30 import dmd.id;
31 import dmd.identifier;
32 import dmd.init;
33 import dmd.mtype;
34 import dmd.opover;
35 import dmd.statement;
36 import dmd.tokens;
37 import dmd.visitor;
38 
39 enum COST_MAX = 250;
40 
41 private enum STATEMENT_COST = 0x1000;
42 private enum STATEMENT_COST_MAX = 250 * STATEMENT_COST;
43 
44 // STATEMENT_COST be power of 2 and greater than COST_MAX
45 static assert((STATEMENT_COST & (STATEMENT_COST - 1)) == 0);
46 static assert(STATEMENT_COST > COST_MAX);
47 
48 /*********************************
49  * Determine if too expensive to inline.
50  * Params:
51  *      cost = cost of inlining
52  * Returns:
53  *      true if too costly
54  */
55 bool tooCostly(int cost) pure nothrow
56 {
57     return ((cost & (STATEMENT_COST - 1)) >= COST_MAX);
58 }
59 
60 /*********************************
61  * Determine cost of inlining Expression
62  * Params:
63  *      e = Expression to determine cost of
64  * Returns:
65  *      cost of inlining e
66  */
67 int inlineCostExpression(Expression e)
68 {
69     scope InlineCostVisitor icv = new InlineCostVisitor(false, true, true, null);
70     icv.expressionInlineCost(e);
71     return icv.cost;
72 }
73 
74 
75 /*********************************
76  * Determine cost of inlining function
77  * Params:
78  *      fd = function to determine cost of
79  *      hasthis = if the function call has explicit 'this' expression
80  *      hdrscan = if generating a header file
81  * Returns:
82  *      cost of inlining fd
83  */
84 int inlineCostFunction(FuncDeclaration fd, bool hasthis, bool hdrscan)
85 {
86     scope InlineCostVisitor icv = new InlineCostVisitor(hasthis, hdrscan, false, fd);
87     fd.fbody.accept(icv);
88     return icv.cost;
89 }
90 
91 /**
92  * Indicates if a nested aggregate prevents or not a function to be inlined.
93  * It's used to compute the cost but also to avoid a copy of the aggregate
94  * while the inliner processes.
95  *
96  * Params:
97  *      e = the declaration expression that may represent an aggregate.
98  *
99  * Returns: `null` if `e` is not an aggregate or if it is an aggregate that
100  *      doesn't permit inlining, and the aggregate otherwise.
101  */
102 AggregateDeclaration isInlinableNestedAggregate(DeclarationExp e)
103 {
104     AggregateDeclaration result;
105     if (e.declaration.isAnonymous() && e.declaration.isAttribDeclaration)
106     {
107         AttribDeclaration ad = e.declaration.isAttribDeclaration;
108         if (ad.decl.dim == 1)
109         {
110             if ((result = (*ad.decl)[0].isAggregateDeclaration) !is null)
111             {
112                 // classes would have to be destroyed
113                 if (auto cdecl = result.isClassDeclaration)
114                     return null;
115                 // if it's a struct: must not have dtor
116                 StructDeclaration sdecl = result.isStructDeclaration;
117                 if (sdecl && (sdecl.fieldDtor || sdecl.dtor))
118                     return null;
119                 // the aggregate must be static
120                 UnionDeclaration udecl = result.isUnionDeclaration;
121                 if ((sdecl || udecl) && !(result.storage_class & STC.static_))
122                     return null;
123 
124                 return result;
125             }
126         }
127     }
128     else if ((result = e.declaration.isStructDeclaration) !is null)
129     {
130         return result;
131     }
132     else if ((result = e.declaration.isUnionDeclaration) !is null)
133     {
134         return result;
135     }
136     return null;
137 }
138 
139 private:
140 
141 /***********************************************************
142  * Compute cost of inlining.
143  *
144  * Walk trees to determine if inlining can be done, and if so,
145  * if it is too complex to be worth inlining or not.
146  */
147 extern (C++) final class InlineCostVisitor : Visitor
148 {
149     alias visit = Visitor.visit;
150 public:
151     int nested;
152     bool hasthis;
153     bool hdrscan;       // if inline scan for 'header' content
154     bool allowAlloca;
155     FuncDeclaration fd;
156     int cost;           // zero start for subsequent AST
157 
158     extern (D) this()
159     {
160     }
161 
162     extern (D) this(bool hasthis, bool hdrscan, bool allowAlloca, FuncDeclaration fd)
163     {
164         this.hasthis = hasthis;
165         this.hdrscan = hdrscan;
166         this.allowAlloca = allowAlloca;
167         this.fd = fd;
168     }
169 
170     extern (D) this(InlineCostVisitor icv)
171     {
172         nested = icv.nested;
173         hasthis = icv.hasthis;
174         hdrscan = icv.hdrscan;
175         allowAlloca = icv.allowAlloca;
176         fd = icv.fd;
177     }
178 
179     override void visit(Statement s)
180     {
181         //printf("Statement.inlineCost = %d\n", COST_MAX);
182         //printf("%p\n", s.isScopeStatement());
183         //printf("%s\n", s.toChars());
184         cost += COST_MAX; // default is we can't inline it
185     }
186 
187     override void visit(ExpStatement s)
188     {
189         expressionInlineCost(s.exp);
190     }
191 
192     override void visit(CompoundStatement s)
193     {
194         scope InlineCostVisitor icv = new InlineCostVisitor(this);
195         foreach (i; 0 .. s.statements.dim)
196         {
197             if (Statement s2 = (*s.statements)[i])
198             {
199                 /* Specifically allow:
200                  *  if (condition)
201                  *      return exp1;
202                  *  return exp2;
203                  */
204                 IfStatement ifs;
205                 Statement s3;
206                 if ((ifs = s2.isIfStatement()) !is null &&
207                     ifs.ifbody &&
208                     ifs.ifbody.endsWithReturnStatement() &&
209                     !ifs.elsebody &&
210                     i + 1 < s.statements.dim &&
211                     (s3 = (*s.statements)[i + 1]) !is null &&
212                     s3.endsWithReturnStatement()
213                    )
214                 {
215                     if (ifs.prm)       // if variables are declared
216                     {
217                         cost = COST_MAX;
218                         return;
219                     }
220                     expressionInlineCost(ifs.condition);
221                     ifs.ifbody.accept(this);
222                     s3.accept(this);
223                 }
224                 else
225                     s2.accept(icv);
226                 if (tooCostly(icv.cost))
227                     break;
228             }
229         }
230         cost += icv.cost;
231     }
232 
233     override void visit(UnrolledLoopStatement s)
234     {
235         scope InlineCostVisitor icv = new InlineCostVisitor(this);
236         foreach (s2; *s.statements)
237         {
238             if (s2)
239             {
240                 s2.accept(icv);
241                 if (tooCostly(icv.cost))
242                     break;
243             }
244         }
245         cost += icv.cost;
246     }
247 
248     override void visit(ScopeStatement s)
249     {
250         cost++;
251         if (s.statement)
252             s.statement.accept(this);
253     }
254 
255     override void visit(IfStatement s)
256     {
257         /* Can't declare variables inside ?: expressions, so
258          * we cannot inline if a variable is declared.
259          */
260         if (s.prm)
261         {
262             cost = COST_MAX;
263             return;
264         }
265         expressionInlineCost(s.condition);
266         /* Specifically allow:
267          *  if (condition)
268          *      return exp1;
269          *  else
270          *      return exp2;
271          * Otherwise, we can't handle return statements nested in if's.
272          */
273         if (s.elsebody && s.ifbody && s.ifbody.endsWithReturnStatement() && s.elsebody.endsWithReturnStatement())
274         {
275             s.ifbody.accept(this);
276             s.elsebody.accept(this);
277             //printf("cost = %d\n", cost);
278         }
279         else
280         {
281             nested += 1;
282             if (s.ifbody)
283                 s.ifbody.accept(this);
284             if (s.elsebody)
285                 s.elsebody.accept(this);
286             nested -= 1;
287         }
288         //printf("IfStatement.inlineCost = %d\n", cost);
289     }
290 
291     override void visit(ReturnStatement s)
292     {
293         // Can't handle return statements nested in if's
294         if (nested)
295         {
296             cost = COST_MAX;
297         }
298         else
299         {
300             expressionInlineCost(s.exp);
301         }
302     }
303 
304     override void visit(ImportStatement s)
305     {
306     }
307 
308     override void visit(ForStatement s)
309     {
310         cost += STATEMENT_COST;
311         if (s._init)
312             s._init.accept(this);
313         if (s.condition)
314             s.condition.accept(this);
315         if (s.increment)
316             s.increment.accept(this);
317         if (s._body)
318             s._body.accept(this);
319         //printf("ForStatement: inlineCost = %d\n", cost);
320     }
321 
322     override void visit(ThrowStatement s)
323     {
324         cost += STATEMENT_COST;
325         s.exp.accept(this);
326     }
327 
328     /* -------------------------- */
329     void expressionInlineCost(Expression e)
330     {
331         //printf("expressionInlineCost()\n");
332         //e.print();
333         if (e)
334         {
335             extern (C++) final class LambdaInlineCost : StoppableVisitor
336             {
337                 alias visit = typeof(super).visit;
338                 InlineCostVisitor icv;
339 
340             public:
341                 extern (D) this(InlineCostVisitor icv)
342                 {
343                     this.icv = icv;
344                 }
345 
346                 override void visit(Expression e)
347                 {
348                     e.accept(icv);
349                     stop = icv.cost >= COST_MAX;
350                 }
351             }
352 
353             scope InlineCostVisitor icv = new InlineCostVisitor(this);
354             scope LambdaInlineCost lic = new LambdaInlineCost(icv);
355             walkPostorder(e, lic);
356             cost += icv.cost;
357         }
358     }
359 
360     override void visit(Expression e)
361     {
362         cost++;
363     }
364 
365     override void visit(VarExp e)
366     {
367         //printf("VarExp.inlineCost3() %s\n", toChars());
368         Type tb = e.type.toBasetype();
369         if (auto ts = tb.isTypeStruct())
370         {
371             StructDeclaration sd = ts.sym;
372             if (sd.isNested())
373             {
374                 /* An inner struct will be nested inside another function hierarchy than where
375                  * we're inlining into, so don't inline it.
376                  * At least not until we figure out how to 'move' the struct to be nested
377                  * locally. Example:
378                  *   struct S(alias pred) { void unused_func(); }
379                  *   void abc() { int w; S!(w) m; }
380                  *   void bar() { abc(); }
381                  */
382                 cost = COST_MAX;
383                 return;
384             }
385         }
386         FuncDeclaration fd = e.var.isFuncDeclaration();
387         if (fd && fd.isNested()) // https://issues.dlang.org/show_bug.cgi?id=7199 for test case
388             cost = COST_MAX;
389         else
390             cost++;
391     }
392 
393     override void visit(ThisExp e)
394     {
395         //printf("ThisExp.inlineCost3() %s\n", toChars());
396         if (!fd)
397         {
398             cost = COST_MAX;
399             return;
400         }
401         if (!hdrscan)
402         {
403             if (fd.isNested() || !hasthis)
404             {
405                 cost = COST_MAX;
406                 return;
407             }
408         }
409         cost++;
410     }
411 
412     override void visit(StructLiteralExp e)
413     {
414         //printf("StructLiteralExp.inlineCost3() %s\n", toChars());
415         if (e.sd.isNested())
416             cost = COST_MAX;
417         else
418             cost++;
419     }
420 
421     override void visit(NewExp e)
422     {
423         //printf("NewExp.inlineCost3() %s\n", e.toChars());
424         AggregateDeclaration ad = isAggregate(e.newtype);
425         if (ad && ad.isNested())
426             cost = COST_MAX;
427         else
428             cost++;
429     }
430 
431     override void visit(FuncExp e)
432     {
433         //printf("FuncExp.inlineCost3()\n");
434         // Right now, this makes the function be output to the .obj file twice.
435         cost = COST_MAX;
436     }
437 
438     override void visit(DelegateExp e)
439     {
440         //printf("DelegateExp.inlineCost3()\n");
441         cost = COST_MAX;
442     }
443 
444     override void visit(DeclarationExp e)
445     {
446         //printf("DeclarationExp.inlineCost3()\n");
447         if (auto vd = e.declaration.isVarDeclaration())
448         {
449             if (auto td = vd.toAlias().isTupleDeclaration())
450             {
451                 cost = COST_MAX; // finish DeclarationExp.doInlineAs
452                 return;
453             }
454             if (!hdrscan && vd.isDataseg())
455             {
456                 cost = COST_MAX;
457                 return;
458             }
459             if (vd.edtor)
460             {
461                 // if destructor required
462                 // needs work to make this work
463                 cost = COST_MAX;
464                 return;
465             }
466             // Scan initializer (vd.init)
467             if (vd._init)
468             {
469                 if (auto ie = vd._init.isExpInitializer())
470                 {
471                     expressionInlineCost(ie.exp);
472                 }
473             }
474             ++cost;
475         }
476 
477         // aggregates are accepted under certain circumstances
478         if (isInlinableNestedAggregate(e))
479         {
480             cost++;
481             return;
482         }
483 
484         // These can contain functions, which when copied, get output twice.
485         if (e.declaration.isStructDeclaration() ||
486             e.declaration.isClassDeclaration()  ||
487             e.declaration.isFuncDeclaration()   ||
488             e.declaration.isAttribDeclaration() ||
489             e.declaration.isTemplateMixin())
490         {
491             cost = COST_MAX;
492             return;
493         }
494         //printf("DeclarationExp.inlineCost3('%s')\n", toChars());
495     }
496 
497     override void visit(CallExp e)
498     {
499         //printf("CallExp.inlineCost3() %s\n", toChars());
500         // https://issues.dlang.org/show_bug.cgi?id=3500
501         // super.func() calls must be devirtualized, and the inliner
502         // can't handle that at present.
503         if (e.e1.op == TOK.dotVariable && (cast(DotVarExp)e.e1).e1.op == TOK.super_)
504             cost = COST_MAX;
505         else if (e.f && e.f.ident == Id.__alloca && e.f.linkage == LINK.c && !allowAlloca)
506             cost = COST_MAX; // inlining alloca may cause stack overflows
507         else
508             cost++;
509     }
510 }
511