"Fossies" - the Fresh Open Source Software Archive

Member "dmd2/src/dmd/dmd/inlinecost.d" (20 Nov 2020, 14558 Bytes) of package /linux/misc/dmd.2.094.2.linux.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) D source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    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