LCOV - code coverage report
Current view: top level - gcc - ipa-predicate.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 42 42 100.0 %
Date: 2020-04-04 11:58:09 Functions: 2 2 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* IPA predicates.
       2                 :            :    Copyright (C) 2003-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Jan Hubicka
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : /* Representation of inline parameters that do depend on context function is
      22                 :            :    inlined into (i.e. known constant values of function parameters.
      23                 :            : 
      24                 :            :    Conditions that are interesting for function body are collected into CONDS
      25                 :            :    vector.  They are of simple as kind of a mathematical transformation on
      26                 :            :    function parameter, T(function_param), in which the parameter occurs only
      27                 :            :    once, and other operands are IPA invariant.  The conditions are then
      28                 :            :    referred by predicates.  */
      29                 :            : 
      30                 :            : 
      31                 :            : /* A simplified representation of tree node, for unary, binary and ternary
      32                 :            :    operation.  Computations on parameter are decomposed to a series of this
      33                 :            :    kind of structure.  */
      34                 :            : struct GTY(()) expr_eval_op
      35                 :            : {
      36                 :            :   /* Result type of expression.  */
      37                 :            :   tree type;
      38                 :            :   /* Constant operands in expression, there are at most two.  */
      39                 :            :   tree val[2];
      40                 :            :   /* Index of parameter operand in expression.  */
      41                 :            :   unsigned index : 2;
      42                 :            :   /* Operation code of expression.  */
      43                 :            :   ENUM_BITFIELD(tree_code) code : 16;
      44                 :            : };
      45                 :            : 
      46                 :            : typedef vec<expr_eval_op, va_gc> *expr_eval_ops;
      47                 :            : 
      48                 :            : struct GTY(()) condition
      49                 :            : {
      50                 :            :   /* If agg_contents is set, this is the offset from which the used data was
      51                 :            :      loaded.  */
      52                 :            :   HOST_WIDE_INT offset;
      53                 :            :   /* Type of the access reading the data (or the PARM_DECL SSA_NAME).  */
      54                 :            :   tree type;
      55                 :            :   tree val;
      56                 :            :   int operand_num;
      57                 :            :   ENUM_BITFIELD(tree_code) code : 16;
      58                 :            :   /* Set if the used data were loaded from an aggregate parameter or from
      59                 :            :      data received by reference.  */
      60                 :            :   unsigned agg_contents : 1;
      61                 :            :   /* If agg_contents is set, this differentiates between loads from data
      62                 :            :      passed by reference and by value.  */
      63                 :            :   unsigned by_ref : 1;
      64                 :            :   /* A set of sequential operations on the parameter, which can be seen as
      65                 :            :      a mathematical function on the parameter.  */
      66                 :            :   expr_eval_ops param_ops;
      67                 :            : };
      68                 :            : 
      69                 :            : /* Information kept about parameter of call site.  */
      70                 :            : struct inline_param_summary
      71                 :            : {
      72                 :            :   /* REG_BR_PROB_BASE based probability that parameter will change in between
      73                 :            :      two invocation of the calls.
      74                 :            :      I.e. loop invariant parameters
      75                 :            :      REG_BR_PROB_BASE/estimated_iterations and regular
      76                 :            :      parameters REG_BR_PROB_BASE.
      77                 :            : 
      78                 :            :      Value 0 is reserved for compile time invariants. */
      79                 :            :   int change_prob;
      80                 :    1035960 :   bool equal_to (const inline_param_summary &other) const
      81                 :            :   {
      82                 :    1035960 :     return change_prob == other.change_prob;
      83                 :            :   }
      84                 :    3857960 :   bool useless_p (void) const
      85                 :            :   {
      86                 :    3857960 :     return change_prob == REG_BR_PROB_BASE;
      87                 :            :   }
      88                 :            : };
      89                 :            : 
      90                 :            : typedef vec<condition, va_gc> *conditions;
      91                 :            : 
      92                 :            : /* Predicates are used to represent function parameters (such as runtime)
      93                 :            :    which depend on a context function is called in.
      94                 :            : 
      95                 :            :    Predicates are logical formulas in conjunctive-disjunctive form consisting
      96                 :            :    of clauses which are bitmaps specifying a set of condition that must
      97                 :            :    be true for a clause to be satisfied. Physically they are represented as
      98                 :            :    array of clauses terminated by 0.
      99                 :            : 
     100                 :            :    In order to make predicate (possibly) true, all of its clauses must
     101                 :            :    be (possibly) true. To make clause (possibly) true, one of conditions
     102                 :            :    it mentions must be (possibly) true.
     103                 :            : 
     104                 :            :    There are fixed bounds on number of clauses and conditions and all the
     105                 :            :    manipulation functions are conservative in positive direction. I.e. we
     106                 :            :    may lose precision by thinking that predicate may be true even when it
     107                 :            :    is not.  */
     108                 :            : 
     109                 :            : typedef uint32_t clause_t;
     110                 :            : class predicate
     111                 :            : {
     112                 :            : public:
     113                 :            :   enum predicate_conditions
     114                 :            :     {
     115                 :            :       false_condition = 0,
     116                 :            :       not_inlined_condition = 1,
     117                 :            :       first_dynamic_condition = 2
     118                 :            :     };
     119                 :            : 
     120                 :            :   /* Maximal number of conditions predicate can refer to.  This is limited
     121                 :            :      by using clause_t to be 32bit.  */
     122                 :            :   static const int num_conditions = 32;
     123                 :            : 
     124                 :            :   /* Special condition code we use to represent test that operand is compile
     125                 :            :      time constant.  */
     126                 :            :   static const tree_code is_not_constant = ERROR_MARK;
     127                 :            : 
     128                 :            :   /* Special condition code we use to represent test that operand is not changed
     129                 :            :      across invocation of the function.  When operand IS_NOT_CONSTANT it is
     130                 :            :      always CHANGED, however i.e. loop invariants can be NOT_CHANGED given
     131                 :            :      percentage of executions even when they are not compile time constants.  */
     132                 :            :   static const tree_code changed = IDENTIFIER_NODE;
     133                 :            : 
     134                 :            : 
     135                 :            : 
     136                 :            :   /* Initialize predicate either to true of false depending on P.  */
     137                 :  598745000 :   inline predicate (bool p = true)
     138                 :  556095000 :     {
     139                 :  598745000 :       if (p)
     140                 :            :         /* True predicate.  */
     141                 :     909162 :         m_clause[0] = 0;
     142                 :            :       else
     143                 :            :         /* False predicate. */
     144                 :  498130200 :         set_to_cond (false_condition);
     145                 :            :     }
     146                 :            : 
     147                 :            :   /* Sanity check that we do not mix pointers to predicates with predicates.  */
     148                 :            :   inline predicate (predicate *)
     149                 :            :     {
     150                 :            :       gcc_unreachable ();
     151                 :            :     }
     152                 :            : 
     153                 :            :   /* Return predicate testing condition I.  */
     154                 :    7145720 :   static inline predicate predicate_testing_cond (int i)
     155                 :            :     {
     156                 :    7145720 :       class predicate p;
     157                 :    7145720 :       p.set_to_cond (i + first_dynamic_condition);
     158                 :    7145720 :       return p;
     159                 :            :     }
     160                 :            : 
     161                 :            :   /* Return predicate testing that function was not inlined.  */
     162                 :   14250400 :   static predicate not_inlined (void)
     163                 :            :     {
     164                 :   14250400 :       class predicate p;
     165                 :   14250400 :       p.set_to_cond (not_inlined_condition);
     166                 :   14250400 :       return p;
     167                 :            :     }
     168                 :            : 
     169                 :            :   /* Compute logical and of predicates.  */
     170                 :            :   predicate & operator &= (const predicate &);
     171                 :  170178000 :   inline predicate operator &(const predicate &p) const
     172                 :            :     {
     173                 :  170178000 :       predicate ret = *this;
     174                 :  160547000 :       ret &= p;
     175                 :  170178000 :       return ret;
     176                 :            :     }
     177                 :            : 
     178                 :            :   /* Compute logical or of predicates.  This is not operator because
     179                 :            :      extra parameter CONDITIONS is needed  */
     180                 :            :   predicate or_with (conditions, const predicate &) const;
     181                 :            : 
     182                 :            :   /* Return true if predicates are known to be equal.  */
     183                 :  463681800 :   inline bool operator==(const predicate &p2) const
     184                 :            :     {
     185                 :  463681800 :       int i;
     186                 :  543005300 :       for (i = 0; m_clause[i]; i++)
     187                 :            :         {
     188                 :  290280800 :           gcc_checking_assert (i < max_clauses);
     189                 :  290280800 :           gcc_checking_assert (m_clause[i] > m_clause[i + 1]);
     190                 :  290280800 :           gcc_checking_assert (!p2.m_clause[i]
     191                 :            :                                || p2.m_clause[i] > p2.m_clause[i + 1]);
     192                 :  290280800 :           if (m_clause[i] != p2.m_clause[i])
     193                 :            :             return false;
     194                 :            :         }
     195                 :  252724540 :       return !p2.m_clause[i];
     196                 :            :     }
     197                 :            : 
     198                 :            :   /* Return true if predicates are known to be true or false depending
     199                 :            :      on COND.  */
     200                 : 1234330099 :   inline bool operator==(const bool cond) const
     201                 :            :     {
     202                 :  966910099 :       if (cond)
     203                 :  514334000 :         return !m_clause[0];
     204                 :  710002099 :       if (m_clause[0] == (1 << false_condition))
     205                 :            :         {
     206                 :   82933870 :           gcc_checking_assert (!m_clause[1]
     207                 :            :                                && m_clause[0] == 1
     208                 :            :                                   << false_condition);
     209                 :            :           return true;
     210                 :            :         }
     211                 :            :       return false;
     212                 :            :     }
     213                 :            : 
     214                 :   53899900 :   inline bool operator!=(const predicate &p2) const
     215                 :            :     {
     216                 :   53899900 :       return !(*this == p2);
     217                 :            :     }
     218                 :            : 
     219                 :  180300099 :   inline bool operator!=(const bool cond) const
     220                 :            :     {
     221                 :  180300099 :       return !(*this == cond);
     222                 :            :     }
     223                 :            : 
     224                 :            :   /* Evaluate if predicate is known to be false given the clause of possible
     225                 :            :      truths.  */
     226                 :            :   bool evaluate (clause_t) const;
     227                 :            : 
     228                 :            :   /* Estimate probability that predicate will be true in a given context.  */
     229                 :            :   int probability (conditions, clause_t, vec<inline_param_summary>) const;
     230                 :            : 
     231                 :            :   /* Dump predicate to F. Output newline if nl.  */
     232                 :            :   void dump (FILE *f, conditions, bool nl=true) const;
     233                 :            :   void DEBUG_FUNCTION debug (conditions) const;
     234                 :            : 
     235                 :            :   /* Return predicate equal to THIS after duplication.  */
     236                 :            :   predicate remap_after_duplication (clause_t);
     237                 :            : 
     238                 :            :   /* Return predicate equal to THIS after inlining.  */
     239                 :            :   predicate remap_after_inlining (class ipa_fn_summary *,
     240                 :            :                                   class ipa_node_params *params_summary,
     241                 :            :                                   class ipa_fn_summary *,
     242                 :            :                                   vec<int>, vec<int>, clause_t, const predicate &);
     243                 :            : 
     244                 :            :   void stream_in (class lto_input_block *);
     245                 :            :   void stream_out (struct output_block *);
     246                 :            : 
     247                 :            : private:
     248                 :            :   static const int max_clauses = 8;
     249                 :            :   clause_t m_clause[max_clauses + 1];
     250                 :            : 
     251                 :            :   /* Initialize predicate to one testing single condition number COND.  */
     252                 :   92985600 :   inline void set_to_cond (int cond)
     253                 :            :     {
     254                 :   92985600 :       m_clause[0] = 1 << cond;
     255                 :   92919700 :       m_clause[1] = 0;
     256                 :      65881 :     }
     257                 :            : 
     258                 :            :   void add_clause (conditions conditions, clause_t);
     259                 :            : };
     260                 :            : 
     261                 :            : void dump_condition (FILE *f, conditions conditions, int cond);
     262                 :            : predicate add_condition (class ipa_fn_summary *summary,
     263                 :            :                          class ipa_node_params *params_summary,
     264                 :            :                          int operand_num,
     265                 :            :                          tree type, struct agg_position_info *aggpos,
     266                 :            :                          enum tree_code code, tree val,
     267                 :            :                          expr_eval_ops param_ops = NULL);

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.