1 /**
2 * Compute the cost of inlining a function call by counting expressions.
3 *
4 * Copyright: Copyright (C) 1999-2021 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