LCOV - code coverage report
Current view: top level - gcc - gimple-crc-optimization.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 93.8 % 420 394
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 33 33
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* CRC optimization.
       2              :    Copyright (C) 2022-2026 Free Software Foundation, Inc.
       3              :    Contributed by Mariam Arutunian <mariamarutunian@gmail.com>
       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              : /* This pass performs CRC optimization.  */
      22              : #include "config.h"
      23              : #include "system.h"
      24              : #include "coretypes.h"
      25              : #include "backend.h"
      26              : #include "tree.h"
      27              : #include "gimple.h"
      28              : #include "tree-pass.h"
      29              : #include "ssa.h"
      30              : #include "gimple-iterator.h"
      31              : #include "tree-cfg.h"
      32              : #include "cfgloop.h"
      33              : #include "tree-scalar-evolution.h"
      34              : #include "tree-ssa-loop-manip.h"
      35              : #include "crc-verification.h"
      36              : #include "internal-fn.h"
      37              : #include "predict.h"
      38              : 
      39              : class crc_optimization {
      40              :  private:
      41              :   /* Record of statements already seen.  */
      42              :   bitmap m_visited_stmts;
      43              : 
      44              :   /* Input CRC of the loop.  */
      45              :   tree m_crc_arg;
      46              : 
      47              :   /* Input data of the loop.  */
      48              :   tree m_data_arg;
      49              : 
      50              :   /* The statement doing shift 1 operation before/after xor operation.  */
      51              :   gimple *m_shift_stmt;
      52              : 
      53              :   /* Phi statement from the head of the loop for CRC.  */
      54              :   gphi *m_phi_for_crc;
      55              : 
      56              :   /* Phi statement for the data from the head of the loop if exists,
      57              :      otherwise - nullptr.  */
      58              :   gphi *m_phi_for_data;
      59              : 
      60              :   /* The loop, which probably calculates CRC.  */
      61              :   class loop *m_crc_loop;
      62              : 
      63              :   /* Polynomial used in CRC calculation.  */
      64              :   unsigned HOST_WIDE_INT m_polynomial;
      65              : 
      66              :   /* Depending on the value of M_IS_BIT_FORWARD, may be forward or reversed CRC.
      67              :      If M_IS_BIT_FORWARD, then it is bit-forward implementation,
      68              :      otherwise bit-reversed.  */
      69              :   bool m_is_bit_forward;
      70              : 
      71              :   /* Sets initial values for CRC analyses.  */
      72              :   void set_initial_values ();
      73              : 
      74              :   /* This is the main function that checks whether the given LOOP
      75              :      calculates CRC and extracts details of the CRC calculation.
      76              : 
      77              :      The main idea is to find the innermost loop with 8, 16, 24, 32, 64
      78              :      iterations and xor instruction (xor is the key operation for naive CRC
      79              :      calculation). Then, checks that the variable is shifted by one before/after
      80              :      being used in xor.
      81              :      Xor must be done under the condition of MSB/LSB being 1.  */
      82              :   bool loop_may_calculate_crc (class loop *loop);
      83              : 
      84              :   /* Symbolically executes the loop and checks that LFSR and resulting states
      85              :      match.
      86              :      Returns true if it is verified that the loop calculates CRC.
      87              :      Otherwise, return false.
      88              :      OUTPUT_CRC is the phi statement which will hold the calculated CRC value
      89              :      after the loop exit.  */
      90              :   bool loop_calculates_crc (gphi *output_crc,
      91              :                             std::pair<tree, value *> calc_polynom);
      92              : 
      93              :   /* Returns true if there is only two conditional blocks in the loop
      94              :      (one may be for the CRC bit check and the other for the loop counter).
      95              :      This may filter out some real CRCs, where more than one condition
      96              :      is checked for the CRC calculation.  */
      97              :   static bool loop_contains_two_conditional_bb (basic_block *loop_bbs,
      98              :                                                 unsigned loop_num_nodes);
      99              : 
     100              :   /* Checks the FUNC_LOOP loop's iteration number.
     101              :      The loop for CRC calculation may do 8, 16, 24, 32, 64 iterations.  */
     102              :   bool satisfies_crc_loop_iteration_count (class loop *func_loop);
     103              : 
     104              :   /* This function checks if the XOR_STMT is used for CRC calculation.
     105              :      It verifies the presence of a shift operation in the CRC_FUN function
     106              :      inside the CRC loop.  It examines operands of XOR, its dependencies, the
     107              :      relative position of the shift operation, and the existence of a shift
     108              :      operation in the opposite branch of conditional statements.  It also
     109              :      checks if XOR is performed when MSB/LSB is one.
     110              :      If these conditions are met, the XOR operation may be part of a CRC
     111              :      calculation.  The function returns true if these conditions are fulfilled,
     112              :      otherwise, it returns false.  */
     113              :   bool xor_calculates_crc (function *crc_fun, const gimple *xor_stmt);
     114              : 
     115              :   /* Returns true if we can get definition of the VARIABLE, and the definition
     116              :      it's not outside the loop.  Otherwise, returns false.  */
     117              :   bool passes_checks_for_def_chain (tree variable);
     118              : 
     119              :   /* This function goes up through the def-use chains of the parameter NAME.
     120              :      Gathers all the statements within the loop,
     121              :      from which the variable depends on and adds to the USE_DEFS.
     122              :      Returns false, if there is a statement that may not exist in the CRC
     123              :      loop.  Otherwise, returns true.  */
     124              :   bool set_defs (tree name, auto_vec<gimple *>& use_defs,
     125              :                  bool keep_only_header_phis);
     126              : 
     127              :   /* Set M_PHI_FOR_CRC and M_PHI_FOR_DATA fields.
     128              :      Returns false if there are more than two (as in CRC calculation only CRC's
     129              :      and data's phi may exist) or no phi statements in STMTS (at least there
     130              :      must be CRC's phi).
     131              :      Otherwise, returns true.  */
     132              :   bool set_crc_and_data_phi (auto_vec<gimple *>& stmts);
     133              : 
     134              :   /*  Returns true if the variable checked in the condition depends on possible
     135              :       CRC value.  Otherwise, returns false.  */
     136              :   bool cond_depends_on_crc (auto_vec<gimple *>& stmts);
     137              : 
     138              : 
     139              :   /* Checks that the condition is for checking CRC.
     140              :      Returns true if xor is done under the condition of MSB/LSB being 1, and
     141              :      the condition's variable and xor-ed variable depend on the same variable.
     142              :      Otherwise, returns false.
     143              :      XOR_BB is the basic block, where the xor operation is done.
     144              :      PRED_BB is the predecessor basic block of the XOR_BB, it is assumed that
     145              :      the last stmt of PRED_BB checks the condition under which xor is done.  */
     146              :   bool crc_cond (basic_block pred_bb, basic_block xor_bb);
     147              : 
     148              :   /* Returns true if xor is done in case the MSB/LSB is 1.
     149              :      Otherwise, returns false.
     150              :      In CRC calculation algorithms CRC is xor-ed with the polynomial only
     151              :      if MSB/LSB is 1.
     152              : 
     153              :      PRED_BB is the block containing the condition for the xor.
     154              :      XOR_BB is the one of the successor blocks of PRED_BB, it is assumed that
     155              :      CRC is xor-ed with the polynomial in XOR_BB.
     156              :      COND is the condition, which is checked to satisfy the CRC condition.  */
     157              :   bool is_crc_satisfiable_cond (basic_block pred_bb, basic_block xor_bb,
     158              :                                 gcond *cond);
     159              : 
     160              :   /* Checks that the variable used in the condition COND is the assumed CRC
     161              :      (or depends on the assumed CRC).
     162              :      Also sets data member m_phi_for_data if it isn't set and exists.  */
     163              :   bool is_crc_checked (gcond *cond);
     164              : 
     165              :   /* Returns true if condition COND checks MSB/LSB bit is 1.
     166              :      Otherwise, return false.  */
     167              :   static bool cond_true_is_checked_for_bit_one (const gcond *cond);
     168              : 
     169              :   /* Returns opposite block of the XOR_BB from PRED_BB's dest blocks.  */
     170              :   static basic_block get_xor_bb_opposite (basic_block pred_bb,
     171              :                                           basic_block xor_bb);
     172              : 
     173              :   /* Checks whether the pair of xor's shift exists in the opposite
     174              :      basic block (OPPOSITE_BB).
     175              :      If there is a shift and xor in the same block,
     176              :      then in the opposite block must be another shift.  */
     177              :   bool exists_shift_for_opp_xor_shift (basic_block opposite_bb);
     178              : 
     179              :   /* Follow def-use chains of XORED_CRC and return the statement where
     180              :      XORED_CRC is shifted by one bit position.  Only PHI statements are
     181              :      allowed between XORED_CRC and the shift in the def-use chain.
     182              : 
     183              :    If no such statement is found, return NULL.  */
     184              :   gimple *find_shift_after_xor (tree xored_crc);
     185              : 
     186              :   /* Returns the statement which does shift 1 operation.
     187              :      If there is no such statement, returns nullptr.
     188              :      STMTS - are the statements within the loop before xor operation on
     189              :      which possible CRC variable depends.  */
     190              :   gimple *find_shift_before_xor (const auto_vec <gimple *> &stmts);
     191              : 
     192              :   /* Returns true if ASSIGN_STMT does shift with 1.
     193              :      Otherwise, returns false.  */
     194              :   bool can_be_crc_shift (gimple *assign_stmt);
     195              : 
     196              :   /* Returns true if the operation done in ASSIGN_STMT can occur during CRC
     197              :      calculation.  Otherwise, returns false.  */
     198              :   bool can_not_be_crc_stmt (gimple *assign_stmt);
     199              : 
     200              :   /* Returns true if the statement with STMT_CODE may occur in CRC calculation.
     201              :      Otherwise, returns false.  */
     202              :   static bool is_acceptable_stmt_code (const tree_code &stmt_code);
     203              : 
     204              :   /* Prints extracted details of CRC calculation.  */
     205              :   void dump_crc_information ();
     206              : 
     207              :   /* Returns true if OUTPUT_CRC's result is the input of m_phi_for_crc.
     208              :      Otherwise, returns false.  */
     209              :   bool is_output_crc (gphi *output_crc);
     210              : 
     211              :   /* Swaps m_phi_for_crc and m_phi_for_data if they are mixed.  */
     212              :   void swap_crc_and_data_if_needed (gphi *output_crc);
     213              : 
     214              :   /* Validates CRC and data arguments and
     215              :    sets them for potential CRC loop replacement.
     216              : 
     217              :    The function extracts the CRC and data arguments from PHI nodes and
     218              :    performs several checks to ensure that the CRC and data are suitable for
     219              :    replacing the CRC loop with a more efficient implementation.
     220              : 
     221              :   Returns true if the arguments are valid and the loop replacement is possible,
     222              :   false otherwise.  */
     223              :   bool validate_crc_and_data ();
     224              : 
     225              :   /* Convert polynomial to unsigned HOST_WIDE_INT.  */
     226              :   void construct_constant_polynomial (value *polynomial);
     227              : 
     228              :   /* Returns phi statement which may hold the calculated CRC.  */
     229              :   gphi *get_output_phi ();
     230              : 
     231              :   /* Attempts to optimize a CRC calculation calculated by LOOP by replacing it
     232              :      with a call to an internal function (IFN_CRC or IFN_CRC_REV).
     233              :      Returns true if replacement succeeded, otherwise false.  */
     234              :   bool optimize_crc_loop (class loop *loop, gphi *output_crc);
     235              : 
     236              :  public:
     237       231308 :   crc_optimization () : m_visited_stmts (BITMAP_ALLOC (NULL)),
     238       231308 :                         m_crc_loop (nullptr), m_polynomial (0)
     239              :   {
     240       231308 :     set_initial_values ();
     241       231308 :   }
     242       231308 :   ~crc_optimization ()
     243              :   {
     244       231308 :     BITMAP_FREE (m_visited_stmts);
     245              :   }
     246              :   unsigned int execute (function *fun);
     247              : };
     248              : 
     249              : /* Prints extracted details of CRC calculation.  */
     250              : 
     251              : void
     252          412 : crc_optimization::dump_crc_information ()
     253              : {
     254          412 :   if (dump_file)
     255              :     {
     256          353 :       fprintf (dump_file,
     257              :                "Loop iteration number is " HOST_WIDE_INT_PRINT_UNSIGNED ".\n",
     258          353 :                tree_to_uhwi (m_crc_loop->nb_iterations));
     259          353 :       if (m_is_bit_forward)
     260          166 :         fprintf (dump_file, "Bit forward.\n");
     261              :       else
     262          187 :         fprintf (dump_file, "Bit reversed.\n");
     263              :     }
     264          412 : }
     265              : 
     266              : /* Goes down by def-use chain (within the CRC loop) and returns the statement
     267              :    where variable (dependent on xor-ed variable) is shifted with 1.
     268              :    Between xor and shift operations only phi statements are allowed.
     269              :    Otherwise, returns nullptr.  */
     270              : 
     271              : gimple *
     272           33 : crc_optimization::find_shift_after_xor (tree xored_crc)
     273              : {
     274           33 :   imm_use_iterator imm_iter;
     275           33 :   use_operand_p use_p;
     276              : 
     277           33 :   gcc_assert (TREE_CODE (xored_crc) == SSA_NAME);
     278              : 
     279           33 :   unsigned v = SSA_NAME_VERSION (xored_crc);
     280           33 :   if (bitmap_bit_p (m_visited_stmts, v))
     281              :     return nullptr;
     282           33 :   bitmap_set_bit (m_visited_stmts, v);
     283              : 
     284              :   /* Iterate through the immediate uses of the XORED_CRC.
     285              :      If there is a shift return true,
     286              :      if before shift there is other instruction (besides phi) return false.  */
     287           43 :   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, xored_crc)
     288              :     {
     289           38 :       gimple *stmt = USE_STMT (use_p);
     290              :       // Consider only statements within the loop
     291           38 :       if (!flow_bb_inside_loop_p (m_crc_loop, gimple_bb (stmt)))
     292            5 :         continue;
     293              : 
     294              :       /* If encountered phi statement, check immediate use of its result.
     295              :          Otherwise, if encountered assign statement, check whether it does shift
     296              :          (some other operations are allowed to be between shift and xor).  */
     297           33 :       if (gimple_code (stmt) == GIMPLE_PHI)
     298              :         {
     299              :           /* Don't continue searching if encountered the loop's beginning.  */
     300           21 :           if (bb_loop_header_p (gimple_bb (stmt)))
     301            5 :             continue;
     302              : 
     303           16 :           return find_shift_after_xor (gimple_phi_result (stmt));
     304              :         }
     305           12 :       else if (is_gimple_assign (stmt))
     306              :         {
     307              :           /* Check that stmt does shift by 1.
     308              :              There are no other statements between
     309              :              xor and shift, in CRC cases we detect.  */
     310           12 :           if (can_be_crc_shift (stmt))
     311              :             return stmt;
     312            1 :           return nullptr;
     313              :         }
     314            0 :       else if (!is_gimple_debug (stmt))
     315              :         return  nullptr;
     316           28 :     }
     317            5 :     return nullptr;
     318              : }
     319              : 
     320              : /* Returns opposite block of the XOR_BB from PRED_BB's dest blocks.  */
     321              : 
     322              : basic_block
     323           52 : crc_optimization::get_xor_bb_opposite (basic_block pred_bb, basic_block xor_bb)
     324              : {
     325              :   /* Check that the predecessor block has exactly two successors.  */
     326           52 :   if (EDGE_COUNT (pred_bb->succs) != 2)
     327              :     return nullptr;
     328              : 
     329           52 :   edge e0 = EDGE_SUCC (pred_bb, 0);
     330           52 :   edge e1 = EDGE_SUCC (pred_bb, 1);
     331              : 
     332              :   /* Ensure neither outgoing edge is marked as complex.  */
     333           52 :   if ((e0->flags & EDGE_COMPLEX)
     334           52 :       || (e1->flags & EDGE_COMPLEX))
     335              :     return nullptr;
     336              : 
     337              :   /* Check that one of the successors is indeed XOR_BB.  */
     338           52 :   gcc_assert ((e0->dest == xor_bb)
     339              :               || (e1->dest == xor_bb));
     340              : 
     341              :   /* Return the opposite block of XOR_BB.  */
     342           52 :   if (EDGE_SUCC (pred_bb, 0)->dest != xor_bb)
     343              :     return e0->dest;
     344           52 :   return e1->dest;
     345              : }
     346              : 
     347              : /* Checks whether the pair of xor's shift exists in the opposite
     348              :    basic block (OPPOSITE_BB).
     349              :    If there is a shift and xor in the same block,
     350              :    then in the opposite block must be another shift.  */
     351              : 
     352              : bool
     353           52 : crc_optimization::exists_shift_for_opp_xor_shift (basic_block opposite_bb)
     354              : {
     355           52 :   if (!opposite_bb)
     356              :     return false;
     357              : 
     358              :   /* Walk through the instructions of given basic block.  */
     359           52 :   for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (opposite_bb);
     360           53 :        !gsi_end_p (bsi); gsi_next_nondebug (&bsi))
     361              :     {
     362           51 :       gimple *stmt = gsi_stmt (bsi);
     363              :       /* Find assignment statement with shift operation.
     364              :          Check that shift's direction is same with the shift done
     365              :          on the path with xor, and it is a shift by one.  */
     366           51 :       if (is_gimple_assign (stmt))
     367              :         {
     368           51 :           if ((gimple_assign_rhs_code (stmt)
     369           51 :                == gimple_assign_rhs_code (m_shift_stmt))
     370           51 :               && integer_onep (gimple_assign_rhs2 (stmt)))
     371           50 :             return true;
     372              :         }
     373              :     }
     374              :   /* If there is no shift, return false.  */
     375            2 :   return false;
     376              : }
     377              : 
     378              : /* Returns true if condition COND checks MSB/LSB bit is 1.
     379              :    Otherwise, return false.  */
     380              : 
     381              : bool
     382          417 : crc_optimization::cond_true_is_checked_for_bit_one (const gcond *cond)
     383              : {
     384          417 :   if (!cond)
     385              :     return false;
     386              : 
     387          417 :   tree rhs = gimple_cond_rhs (cond);
     388          417 :   enum tree_code code = gimple_cond_code (cond);
     389              : 
     390              :   /* If the condition is something == 1 -> return true.  */
     391          417 :   if (code == EQ_EXPR && integer_onep (rhs))
     392              :     return true;
     393              : 
     394              :   /* If the condition is something != 0  or something < 0 -> return true.  */
     395          415 :   if ((code == NE_EXPR || code == LT_EXPR)
     396          415 :        && integer_zerop (rhs))
     397              :     return true;
     398              : 
     399              :   return false;
     400              : }
     401              : 
     402              : /* Returns true if xor is done in case the MSB/LSB is 1.
     403              :    Otherwise, returns false.
     404              :    In CRC calculation algorithms CRC is xor-ed with the polynomial only
     405              :    if MSB/LSB is 1.
     406              : 
     407              :    PRED_BB is the block containing the condition for the xor.
     408              :    XOR_BB is the one of the successor blocks of PRED_BB, it is assumed that CRC
     409              :    is xor-ed with the polynomial in XOR_BB.
     410              :    COND is the condition, which is checked to satisfy the CRC condition.  */
     411              : 
     412              : bool
     413          417 : crc_optimization::is_crc_satisfiable_cond (basic_block pred_bb,
     414              :                                            basic_block xor_bb,
     415              :                                            gcond *cond)
     416              : {
     417          417 :   edge true_edge;
     418          417 :   edge false_edge;
     419          417 :   extract_true_false_edges_from_block (pred_bb, &true_edge, &false_edge);
     420          417 :   bool cond_is_checked_for_bit_one = cond_true_is_checked_for_bit_one (cond);
     421              :   /* Check that xor is done in case the MSB/LSB is 1.  */
     422          417 :   if (cond_is_checked_for_bit_one && true_edge->dest == xor_bb)
     423              :     {
     424          416 :       if (dump_file && (dump_flags & TDF_DETAILS))
     425          279 :         fprintf (dump_file, "Xor is done on true branch.\n");
     426              :     }
     427            1 :   else if (!cond_is_checked_for_bit_one && false_edge->dest == xor_bb)
     428              :     {
     429            1 :       if (dump_file && (dump_flags & TDF_DETAILS))
     430            1 :         fprintf (dump_file, "Xor is done on false branch.\n");
     431              :     }
     432              :   else
     433              :     {
     434            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     435            0 :         fprintf (dump_file,
     436              :                  "Xor is done if MSB/LSB is not one, not CRC.\n");
     437              :       return false;
     438              :     }
     439              :   return true;
     440              : }
     441              : 
     442              : /* Checks that the variable used in the condition COND is the assumed CRC
     443              :   (or depends on the assumed CRC).
     444              :   Also sets data member m_phi_for_data if it isn't set and exists.  */
     445              : 
     446              : bool
     447          417 : crc_optimization::is_crc_checked (gcond *cond)
     448              : {
     449          417 :   tree lhs = gimple_cond_lhs (cond);
     450              : 
     451              :   /* As conditions are in canonical form, only left part must be an
     452              :     SSA_NAME.  */
     453          417 :   if (TREE_CODE (lhs) == SSA_NAME)
     454              :     {
     455              :       /* Return whether there is a dependence between if condition's variable
     456              :          and xor-ed variable.  Also set phi statement of data if it is not
     457              :          determined earlier and is used in the loop.  */
     458          417 :       auto_vec<gimple *> cond_dep_stmts (m_crc_loop->num_nodes);
     459          417 :       bool set_defs_succeeded = set_defs (lhs, cond_dep_stmts, true);
     460          417 :       bitmap_clear (m_visited_stmts);
     461          417 :       if (!set_defs_succeeded)
     462              :         return false;
     463          414 :       return cond_depends_on_crc (cond_dep_stmts);
     464          417 :     }
     465              : 
     466              :   /* Return false if there is no dependence between if condition's variable
     467              :      and xor-ed variable.  */
     468              :   return false;
     469              : }
     470              : 
     471              : /* Checks that the condition is for checking CRC.
     472              :    Returns true if xor is done under the condition of MSB/LSB being 1, and
     473              :    the condition's variable and xor-ed variable depend on the same variable.
     474              :    Otherwise, returns false.
     475              :    XOR_BB is the basic block, where the xor operation is done.
     476              :    PRED_BB is the predecessor basic block of the XOR_BB, it is assumed that
     477              :    the last stmt of PRED_BB checks the condition under which xor is done.  */
     478              : 
     479              : bool
     480          417 : crc_optimization::crc_cond (basic_block pred_bb, basic_block xor_bb)
     481              : {
     482              :   /* Check whether PRED_BB contains condition.  We will consider only those
     483              :      cases when xor is done immediately under the condition.  */
     484          834 :   gcond *cond = safe_dyn_cast<gcond *> (gsi_stmt (gsi_last_bb (pred_bb)));
     485          417 :   if (!cond)
     486              :     {
     487            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     488            0 :         fprintf (dump_file, "No condition.\n");
     489              :       return false;
     490              :     }
     491              : 
     492              :   /* Check that xor is done in case the MSB/LSB is 1.  */
     493          417 :   if (!is_crc_satisfiable_cond (pred_bb, xor_bb, cond))
     494              :     return false;
     495              : 
     496              :   /* Check that CRC's MSB/LSB is checked in the condition.
     497              :      Set data member if not set and exists.  */
     498          417 :   if (!is_crc_checked (cond))
     499              :     {
     500            5 :       if (dump_file && (dump_flags & TDF_DETAILS))
     501            0 :         fprintf (dump_file, "The condition is not related to the CRC check.\n");
     502              :       return false;
     503              :     }
     504              :   return true;
     505              : }
     506              : 
     507              : /* Returns true if the statement with STMT_CODE may occur in CRC calculation.
     508              :    Otherwise, returns false.  */
     509              : 
     510              : bool
     511         1437 : crc_optimization::is_acceptable_stmt_code (const tree_code &stmt_code)
     512              : {
     513         1437 :   return (stmt_code == BIT_IOR_EXPR)
     514         1437 :          || (stmt_code == BIT_AND_EXPR)
     515              :          || (stmt_code == BIT_XOR_EXPR)
     516              :          || (stmt_code == MINUS_EXPR)
     517              :          || (stmt_code == PLUS_EXPR)
     518              :          || (stmt_code == RSHIFT_EXPR)
     519              :          || (stmt_code == LSHIFT_EXPR)
     520          427 :          || (TREE_CODE_CLASS (stmt_code) == tcc_unary);
     521              : }
     522              : 
     523              : /* Returns true if ASSIGN_STMT does shift with 1.  Otherwise, returns false.  */
     524              : 
     525              : bool
     526          442 : crc_optimization::can_be_crc_shift (gimple *assign_stmt)
     527              : {
     528          442 :   tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
     529          442 :   if (stmt_code == LSHIFT_EXPR || stmt_code == RSHIFT_EXPR)
     530              :     {
     531          424 :       m_is_bit_forward = (stmt_code == LSHIFT_EXPR);
     532              :       /* Check that shift one is done, keep shift statement.  */
     533          424 :       if (integer_onep (gimple_assign_rhs2 (assign_stmt)))
     534              :         {
     535          419 :           if (m_shift_stmt)
     536              :             {
     537            0 :               if (dump_file && (dump_flags & TDF_DETAILS))
     538            0 :                 fprintf (dump_file,
     539              :                          "Already there is one shift.\n");
     540              :               return false;
     541              :             }
     542          419 :           if (dump_file && (dump_flags & TDF_DETAILS))
     543          280 :             fprintf (dump_file,
     544              :                      "Found <<1 or >>1.\n");
     545              :           return true;
     546              :         }
     547              :       /* This filters out cases, when xor-ed variable is shifted by values
     548              :          other than 1.  */
     549              :     }
     550              :     return false;
     551              : }
     552              : 
     553              : /* Returns true if the operation done in ASSIGN_STMT can occur during CRC
     554              :    calculation.  Otherwise, returns false.  */
     555              : 
     556              : bool
     557         1437 : crc_optimization::can_not_be_crc_stmt (gimple *assign_stmt)
     558              : {
     559         1437 :   tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
     560         1437 :   if (!is_acceptable_stmt_code (stmt_code))
     561              :     {
     562           11 :       if (dump_file && (dump_flags & TDF_DETAILS))
     563            0 :         fprintf (dump_file,
     564              :                  "\nStmt with the following operation "
     565              :                  "code %s between xor and shift, "
     566              :                  "may not be CRC.\n", get_tree_code_name (stmt_code));
     567              : 
     568              :       return true;
     569              :     }
     570              :   return false;
     571              : }
     572              : 
     573              : /* Returns true if we can get definition of the VARIABLE, and the definition
     574              :    is not outside the loop.  Otherwise, returns false.  */
     575              : 
     576              : bool
     577         3689 : crc_optimization::passes_checks_for_def_chain (tree variable)
     578              : {
     579         3689 :   if (!(variable && TREE_CODE (variable) == SSA_NAME))
     580              :     return false;
     581              : 
     582              :   /* No definition chain for default defs.  */
     583         2525 :   if (SSA_NAME_IS_DEFAULT_DEF (variable))
     584              :     return false;
     585              : 
     586         2525 :   gimple *stmt = SSA_NAME_DEF_STMT (variable);
     587              : 
     588         2525 :   if (!stmt)
     589              :     return false;
     590              : 
     591              :   /* Don't go outside the loop.  */
     592         2525 :   if (!flow_bb_inside_loop_p (m_crc_loop, gimple_bb (stmt)))
     593              :     return false;
     594              : 
     595              :   return true;
     596              : }
     597              : 
     598              : /* This function goes up through the def-use chains of the parameter NAME.
     599              :    Gathers all the statements within the loop,
     600              :    from which the variable depends on and adds to the USE_DEFS.
     601              :    Returns false, if there is a statement that may not exist in the CRC
     602              :    loop.  Otherwise, returns true.  */
     603              : 
     604              : bool
     605         2289 : crc_optimization::set_defs (tree name, auto_vec<gimple *> &use_defs,
     606              :                             bool keep_only_header_phis = false)
     607              : {
     608         3689 :   if (!passes_checks_for_def_chain (name))
     609              :     return true;
     610              : 
     611              :   /* Don't consider already visited names.  */
     612         2520 :   unsigned v = SSA_NAME_VERSION (name);
     613         2520 :   if (bitmap_bit_p (m_visited_stmts, v))
     614              :     return true;
     615         2518 :   bitmap_set_bit (m_visited_stmts, v);
     616              : 
     617              :   /* In CRC implementations with constant polynomial maximum 12 use_def
     618              :      statements may occur.  This limit is based on an analysis of various CRC
     619              :      implementations as well as theoretical possibilities.
     620              :      TODO: Find a better solution.  */
     621         2518 :   if (use_defs.length () > 12)
     622              :     return false;
     623              : 
     624         2518 :   gimple *stmt = SSA_NAME_DEF_STMT (name);
     625              : 
     626              :   /* If it's not specified to keep only header phi's,
     627              :      then keep all statements.  */
     628         2518 :   if (!keep_only_header_phis)
     629          981 :     use_defs.safe_push (stmt);
     630              : 
     631              :   /* If it is an assignment statement,
     632              :      get and check def-use chain for the first and second operands.  */
     633         2518 :   if (is_a<gassign *> (stmt))
     634              :     {
     635         1437 :       if (can_not_be_crc_stmt (stmt))
     636              :         return false;
     637              : 
     638         1426 :       tree ssa1 = gimple_assign_rhs1 (stmt);
     639         1426 :       tree ssa2 = gimple_assign_rhs2 (stmt);
     640         1426 :       if (!set_defs (ssa1, use_defs, keep_only_header_phis))
     641              :         return false;
     642              :       if (!set_defs (ssa2, use_defs, keep_only_header_phis))
     643              :         return false;
     644              :       return true;
     645              :     }
     646              :   /* If it's a phi statement, not declared in loop's header,
     647              :      get and check def-use chain for its values.  For the one declared in loop's
     648              :      header just return true and keep it, if keep_only_header_phis is true.  */
     649         1081 :   else if (is_a<gphi *> (stmt))
     650              :     {
     651         1068 :       if (bb_loop_header_p (gimple_bb (stmt)))
     652              :         {
     653              :           /* If it's specified to keep only header phi's, keep it.  */
     654         1068 :           if (keep_only_header_phis)
     655          634 :             use_defs.safe_push (stmt);
     656              :         }
     657              :       else
     658              :         {
     659            0 :           for (unsigned i = 0; i < gimple_phi_num_args (stmt); i++)
     660              :             {
     661            0 :               tree val = gimple_phi_arg_def (stmt, i);
     662            0 :               if (!set_defs (val, use_defs, keep_only_header_phis))
     663              :                 return false;
     664              :             }
     665              :         }
     666              :       return true;
     667              :     }
     668              : 
     669              :   /* Return false for other than assignment and phi statement.  */
     670              :   return false;
     671              : }
     672              : 
     673              : /* Returns the statement which does shift 1 operation.
     674              :    If there is no such statement, returns nullptr.
     675              :    STMTS - are the statements within the loop before xor operation on
     676              :    which possible CRC variable depends.  */
     677              : 
     678              : gimple *
     679          425 : crc_optimization::find_shift_before_xor (const auto_vec<gimple *> &stmts)
     680              : {
     681         1361 :   for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
     682              :     {
     683              :       /* If it is an assignment statement, check that is does shift 1.  */
     684          451 :       if (is_a<gassign *> (*stmt_it))
     685              :         {
     686          430 :           if (can_be_crc_shift (*stmt_it))
     687          408 :             return *stmt_it;
     688              :         }
     689              :     }
     690              :   return nullptr;
     691              : }
     692              : 
     693              : /* This function sets M_PHI_FOR_CRC and M_PHI_FOR_DATA fields.
     694              :    At this step phi nodes for CRC and data may be mixed in places.
     695              :    It is fixed later with the "swap_crc_and_data_if_needed" function.
     696              :    The function returns false if there are more than two (as in CRC calculation
     697              :    only CRC's and data's phi may exist) or no phi statements in STMTS (at least
     698              :    there must be CRC's phi).
     699              :    Otherwise, returns true.  */
     700              : 
     701              : bool
     702          425 : crc_optimization::set_crc_and_data_phi (auto_vec<gimple *> &stmts)
     703              : {
     704         3147 :   for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
     705              :     {
     706          936 :       if (is_a<gphi *> (*stmt_it) && bb_loop_header_p (gimple_bb (*stmt_it)))
     707              :         {
     708          434 :           if (!m_phi_for_crc)
     709          425 :             m_phi_for_crc = as_a<gphi *> (*stmt_it);
     710            9 :           else if (!m_phi_for_data)
     711            9 :             m_phi_for_data = as_a<gphi *> (*stmt_it);
     712              :           else
     713              :             {
     714            0 :               if (dump_file && (dump_flags & TDF_DETAILS))
     715            0 :                 fprintf (dump_file, "Xor-ed variable depends on more than 2 "
     716              :                                     "phis.\n");
     717              :               return false;
     718              :             }
     719              :         }
     720              :     }
     721          425 :   return m_phi_for_crc;
     722              : }
     723              : 
     724              : /*  Returns true if the variable checked in the condition depends on possible
     725              :     CRC value.  Otherwise, returns false.  */
     726              : 
     727              : bool
     728          414 : crc_optimization::cond_depends_on_crc (auto_vec<gimple *>& stmts)
     729              : {
     730          414 :   bool con_depends_on_crc = false;
     731              : 
     732              :   /* The condition may depend maximum on data and CRC phi's.  */
     733          414 :   if (stmts.length () > 2)
     734              :     return false;
     735              : 
     736         2498 :   for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
     737              :     {
     738          634 :       if (is_a<gphi *> (*stmt_it) && bb_loop_header_p (gimple_bb (*stmt_it)))
     739              :         {
     740              :           /* Check whether variable checked in the condition depends on
     741              :              M_PHI_FOR_CRC.
     742              :              Here don't stop the check, to set data if needed.  */
     743          634 :           if (m_phi_for_crc == (*stmt_it))
     744              :             con_depends_on_crc = true;
     745          222 :           else if (m_phi_for_data && m_phi_for_data == (*stmt_it))
     746              :             return true;
     747              :           /* If M_PHI_FOR_DATA isn't determined, the phi statement maybe for the
     748              :              data.  Just set it.  */
     749          216 :           else if (!m_phi_for_data)
     750          216 :             m_phi_for_data = as_a<gphi *> (*stmt_it);
     751              :         }
     752              :     }
     753              :   return con_depends_on_crc;
     754              : }
     755              : 
     756              : /* Sets initial values for the CRC analysis.
     757              :    This function is used multiple times during the analyses.  */
     758              : 
     759              : void
     760       232043 : crc_optimization::set_initial_values ()
     761              : {
     762       232043 :   m_crc_arg = nullptr;
     763       232043 :   m_data_arg = nullptr;
     764       232043 :   m_shift_stmt = nullptr;
     765       232043 :   m_phi_for_crc = nullptr;
     766       232043 :   m_phi_for_data = nullptr;
     767       232043 :   m_is_bit_forward = false;
     768       232043 : }
     769              : 
     770              : /* This function checks if the XOR_STMT is used for CRC calculation.
     771              :    It verifies the presence of a shift operation in the CRC_FUN function inside
     772              :    the CRC loop.  It examines operands of XOR, its dependencies, the relative
     773              :    position of the shift operation, and the existence of a shift operation in
     774              :    the opposite branch of conditional statements.  It also checks if XOR is
     775              :    performed when MSB/LSB is one.
     776              :    If these conditions are met, the XOR operation may be part of a CRC
     777              :    calculation.  The function returns true if these conditions are fulfilled,
     778              :    otherwise, it returns false.  */
     779              : 
     780              : bool
     781          735 : crc_optimization::xor_calculates_crc (function *crc_fun,
     782              :                                       const gimple *xor_stmt)
     783              : {
     784          735 :   tree crc_var = gimple_assign_lhs (xor_stmt);
     785          735 :   set_initial_values ();
     786          735 :   tree ssa1 = gimple_assign_rhs1 (xor_stmt);
     787          735 :   tree ssa2 = gimple_assign_rhs2 (xor_stmt);
     788          735 :   if (TREE_CODE (ssa2) != INTEGER_CST)
     789              :     {
     790          289 :       if (dump_file && (dump_flags & TDF_DETAILS))
     791          185 :         fprintf (dump_file, "Second operand of the "
     792              :                             "xor statement isn't an integer constant.\n");
     793              :       return false;
     794              :     }
     795              : 
     796              :   /* Get the statements within the loop on which xor-ed variable depends.  */
     797          446 :   auto_vec<gimple *> xor_dep_stmts (m_crc_loop->num_nodes);
     798          446 :   bool set_defs_succeeded = set_defs (ssa1, xor_dep_stmts);
     799          446 :   bitmap_clear (m_visited_stmts);
     800          446 :   if (!set_defs_succeeded)
     801              :     {
     802           21 :       xor_dep_stmts.release ();
     803           21 :       return false;
     804              :     }
     805              : 
     806          425 :   m_shift_stmt = find_shift_before_xor (xor_dep_stmts);
     807              : 
     808          425 :   if (!set_crc_and_data_phi (xor_dep_stmts))
     809              :     {
     810            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     811            0 :         fprintf (dump_file, "Xor isn't used for CRC calculation.\n");
     812              :       return false;
     813              :     }
     814              : 
     815              :   /* Check the case when shift is done after xor.  */
     816          425 :   if (!m_shift_stmt)
     817              :     {
     818           17 :       if (dump_file && (dump_flags & TDF_DETAILS))
     819            9 :         fprintf (dump_file, "No shift before xor, trying to find after xor.\n");
     820              : 
     821           17 :       m_shift_stmt = find_shift_after_xor (crc_var);
     822           17 :       bitmap_clear (m_visited_stmts);
     823           17 :       if (!m_shift_stmt)
     824              :         return false;
     825              :     }
     826              : 
     827              :   /* Get the basic block where xor operation is done.  */
     828          419 :   basic_block xor_bb = gimple_bb (xor_stmt);
     829              : 
     830              :   /* Get the predecessor basic block of xor's block.  */
     831          865 :   if (!single_pred_p (xor_bb))
     832              :     return false;
     833          419 :   basic_block block_of_condition = single_pred (xor_bb);
     834              : 
     835              : 
     836              :   /* If the found shift operation is in the same block as the xor operation,
     837              :      verify whether another shift exists in the opposite branch of the
     838              :      conditional statements.  */
     839          419 :   if (m_shift_stmt && gimple_bb (m_shift_stmt) == xor_bb)
     840              :     {
     841           52 :       basic_block opposite_block = get_xor_bb_opposite (block_of_condition,
     842              :                                                         xor_bb);
     843           52 :       if (!exists_shift_for_opp_xor_shift (opposite_block))
     844              :         {
     845            2 :           if (dump_file && (dump_flags & TDF_DETAILS))
     846            0 :             fprintf (dump_file,
     847              :                      "Opposite block doesn't contain shift's pair.\n");
     848              :           return false;
     849              :         }
     850              :     }
     851              : 
     852              :   /* Check that xor is done if MSB/LSB is one.
     853              :      If all checks succeed, then it may be a CRC.  */
     854          417 :   if (crc_cond (block_of_condition, xor_bb))
     855              :     {
     856          412 :       if (dump_file)
     857          353 :         fprintf (dump_file,
     858              :                  "\n%s function maybe contains CRC calculation.\n",
     859              :                  function_name (crc_fun));
     860              :       return true;
     861              :     }
     862              : 
     863              :   return false;
     864          446 : }
     865              : 
     866              : /* Returns true if there is only two conditional blocks in the loop,
     867              :    one may be for the CRC bit check and the other for the loop counter.
     868              :    This may filter out some real CRCs, where more than one condition
     869              :    is checked for the CRC calculation and branch-less CRCs.  */
     870              : 
     871              : bool
     872        20211 : crc_optimization::loop_contains_two_conditional_bb (basic_block *loop_bbs,
     873              :                                                     unsigned loop_num_nodes)
     874              : {
     875        20211 :   unsigned conditional_bb_count = 0;
     876              :   /* Iterate through the loop until the conditional branches count
     877              :      is below 3.  */
     878        79173 :   for (unsigned i = 0; i < loop_num_nodes && conditional_bb_count <= 2; i++)
     879              :     {
     880        58962 :       basic_block bb = loop_bbs[i];
     881        58962 :       if (!single_succ_p (bb))
     882        27443 :         conditional_bb_count++;
     883              :     }
     884        20211 :   return conditional_bb_count == 2;
     885              : }
     886              : 
     887              : /* Checks the FUNC_LOOP loop's iteration number.
     888              :    The loop for CRC calculation may do 8, 16, 24, 32, 64 iterations.  */
     889              : 
     890              : bool
     891       523484 : crc_optimization::satisfies_crc_loop_iteration_count (class loop *func_loop)
     892              : {
     893              :   /* Calculate the number of times the latch of the loop is executed.
     894              :      The function sets NB_ITERATIONS field of the loop.  */
     895       523484 :   number_of_latch_executions (func_loop);
     896       523484 :   tree n_inters = func_loop->nb_iterations;
     897       523484 :   if (n_inters == NULL_TREE || n_inters == chrec_dont_know)
     898              :     {
     899       267413 :       if (dump_file && (dump_flags & TDF_DETAILS))
     900           45 :         fprintf (dump_file,
     901              :                  "Loop iteration number is chrec_dont_know.\n");
     902              :       return false;
     903              : 
     904              :     }
     905       256071 :   else if (tree_fits_uhwi_p (n_inters))
     906              :     {
     907       163209 :       unsigned HOST_WIDE_INT
     908       163209 :       loop_iteration_number = tree_to_uhwi (n_inters);
     909       163209 :       if (dump_file && (dump_flags & TDF_DETAILS))
     910          315 :         fprintf (dump_file, "Loop iteration number is "
     911              :                  HOST_WIDE_INT_PRINT_UNSIGNED ".\n", loop_iteration_number);
     912              : 
     913       163209 :       if ((loop_iteration_number == 7 || loop_iteration_number == 15
     914              :            || loop_iteration_number == 23 || loop_iteration_number == 31
     915              :            || loop_iteration_number == 63))
     916              :         return true;
     917              :     }
     918       235860 :   if (stderr && (dump_flags & TDF_DETAILS))
     919           30 :     fprintf (dump_file, "Loop iteration number isn't a constant.\n");
     920              :   return false;
     921              : }
     922              : 
     923              : /* This is the main function that checks whether the given LOOP
     924              :    calculates CRC and extracts details of the CRC calculation.
     925              : 
     926              :    The main idea is to find the innermost loop with 8, 16, 24, 32, 64
     927              :    iterations and xor instruction (xor is the key operation for naive CRC
     928              :    calculation). Then, checks that the variable is shifted by one before/after
     929              :    being used in xor.
     930              :    Xor must be done under the condition of MSB/LSB being 1.  */
     931              : 
     932              : bool
     933       523484 : crc_optimization::loop_may_calculate_crc (class loop *loop)
     934              : {
     935              :   /* Only examine innermost loops.  */
     936       523484 :   if (!loop || loop->inner)
     937              :     return false;
     938              : 
     939       523484 :   if (!satisfies_crc_loop_iteration_count (loop))
     940              :     return false;
     941              : 
     942        20211 :   m_crc_loop = loop;
     943        20211 :   basic_block *loop_bbs = get_loop_body_in_dom_order (m_crc_loop);
     944              : 
     945              :   /* Filter out the cases, which don't have exactly two conditions in the loop.
     946              :      One for the CRC bit check, the other for the loop counter.  */
     947        20211 :   if (!loop_contains_two_conditional_bb (loop_bbs, m_crc_loop->num_nodes))
     948              :     {
     949        15333 :       if (dump_file && (dump_flags & TDF_DETAILS))
     950            6 :         fprintf (dump_file,
     951              :                  "The number of conditional "
     952              :                  "branches in the loop isn't 2.\n");
     953        15333 :       free (loop_bbs);
     954        15333 :       return false;
     955              :     }
     956              : 
     957              :   unsigned short checked_xor_count = 0;
     958              :   /* Walk bbs of the loop.  */
     959        27532 :   for (unsigned int i = 0; i < m_crc_loop->num_nodes; i++)
     960              :     {
     961        23083 :       basic_block bb = loop_bbs[i];
     962              :       /* Walk instructions of the bb.  */
     963        23083 :       for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (bb);
     964        75960 :            !gsi_end_p (bsi); gsi_next_nondebug (&bsi))
     965              :         {
     966        53306 :           gimple *stmt = gsi_stmt (bsi);
     967              :           /* If there is an xor instruction,
     968              :              check that it is calculating CRC.  */
     969        53306 :           if (is_gimple_assign (stmt)
     970        53306 :               && gimple_assign_rhs_code (stmt) == BIT_XOR_EXPR)
     971              :             {
     972          735 :               if (dump_file && (dump_flags & TDF_DETAILS))
     973          465 :                 fprintf (dump_file,
     974              :                          "Found xor, "
     975              :                          "checking whether it is for CRC calculation.\n");
     976              : 
     977          735 :               if (xor_calculates_crc (cfun, stmt))
     978              :                 {
     979          412 :                   dump_crc_information ();
     980          412 :                   free (loop_bbs);
     981          429 :                   return true;
     982              :                 }
     983              : 
     984          323 :               if (++checked_xor_count == 2)
     985              :                 {
     986           17 :                   free (loop_bbs);
     987           17 :                   return false;
     988              :                 }
     989              :             }
     990              :         }
     991              :     }
     992         4449 :   free (loop_bbs);
     993         4449 :   return false;
     994              : }
     995              : 
     996              : /* Symbolically executes the loop and checks that LFSR and resulting states
     997              :    match.
     998              :    Returns true if it is verified that the loop calculates CRC.
     999              :    Otherwise, return false.
    1000              :    OUTPUT_CRC is the phi statement which will hold the calculated CRC value
    1001              :    after the loop exit.  */
    1002              : 
    1003              : bool
    1004          369 : crc_optimization::loop_calculates_crc (gphi *output_crc,
    1005              :                                        std::pair<tree, value *> calc_polynom)
    1006              : {
    1007              :   /* Create LFSR state using extracted polynomial.  */
    1008          369 :   value * lfsr = state::create_lfsr (calc_polynom.first, calc_polynom.second,
    1009              :                                      m_is_bit_forward);
    1010          369 :   if (!lfsr)
    1011              :     {
    1012           19 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1013           14 :         fprintf (dump_file, "Couldn't create LFSR!\n");
    1014              :       return false;
    1015              :     }
    1016              : 
    1017          350 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1018              :     {
    1019          224 :       fprintf (dump_file, "\nLFSR value is \n");
    1020          224 :       state::print_value (lfsr);
    1021              :     }
    1022              : 
    1023              :   /* Execute the loop with symbolic values
    1024              :      (symbolic value is assigned to the variable when its value isn't known)
    1025              :      to keep states, for further comparison.  */
    1026          350 :   bool is_crc = true;
    1027          350 :   crc_symbolic_execution loop_executor (m_crc_loop, output_crc);
    1028         6493 :   while (!loop_executor.is_last_iteration ())
    1029              :     {
    1030         5798 :       if (!loop_executor.symb_execute_crc_loop ())
    1031              :         {
    1032            0 :           if (dump_file)
    1033            0 :             fprintf (dump_file, "\nCRC verification didn't succeed "
    1034              :                                 "during symbolic execution!\n");
    1035              :           is_crc = false;
    1036              :           break;
    1037              :         }
    1038              : 
    1039              :       /* Check whether LFSR and obtained states are same.  */
    1040         5798 :       tree calculated_crc = PHI_ARG_DEF_FROM_EDGE (output_crc,
    1041              :                                                    single_exit (m_crc_loop));
    1042         5798 :       if (!all_states_match_lfsr (lfsr, m_is_bit_forward, calculated_crc,
    1043              :                                  loop_executor.get_final_states ()))
    1044              :         {
    1045            5 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1046            3 :             fprintf (dump_file, "Returned state and LFSR differ.\n");
    1047              :           is_crc = false;
    1048              :           break;
    1049              :         }
    1050              :     }
    1051          350 :   delete lfsr;
    1052          350 :   return is_crc;
    1053          350 : }
    1054              : 
    1055              : /* Returns true if OUTPUT_CRC's result is the input of M_PHI_FOR_CRC.
    1056              :   Otherwise, returns false.  */
    1057              : 
    1058              : bool
    1059          393 : crc_optimization::is_output_crc (gphi *output_crc)
    1060              : {
    1061          393 :   tree crc_of_exit
    1062          393 :     = PHI_ARG_DEF_FROM_EDGE (output_crc, single_exit (m_crc_loop));
    1063          393 :   tree crc_of_latch
    1064          393 :     = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, loop_latch_edge (m_crc_loop));
    1065          393 :   if (crc_of_exit == crc_of_latch)
    1066              :     {
    1067          390 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1068              :         {
    1069          259 :           fprintf (dump_file, "Output CRC is ");
    1070          259 :           print_gimple_expr (dump_file, (gimple *) output_crc, dump_flags);
    1071          259 :           fprintf (dump_file, "\n");
    1072              :         }
    1073              :       return true;
    1074              :     }
    1075              :   else
    1076              :     {
    1077            3 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1078            3 :         fprintf (dump_file, "Output CRC and determined input CRC "
    1079              :                             "differ.\n");
    1080              :       return false;
    1081              :     }
    1082              : }
    1083              : 
    1084              : /* Swaps M_PHI_FOR_CRC and M_PHI_FOR_DATA if they are mixed.  */
    1085              : 
    1086              : void
    1087          393 : crc_optimization::swap_crc_and_data_if_needed (gphi *output_crc)
    1088              : {
    1089          393 :   tree crc_of_exit
    1090          393 :     = PHI_ARG_DEF_FROM_EDGE (output_crc, single_exit (m_crc_loop));
    1091          393 :   edge crc_loop_latch = loop_latch_edge (m_crc_loop);
    1092          393 :   if (crc_of_exit != PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, crc_loop_latch))
    1093              :     {
    1094            9 :       if (m_phi_for_data
    1095            9 :           && crc_of_exit == PHI_ARG_DEF_FROM_EDGE (m_phi_for_data,
    1096              :                                                    crc_loop_latch))
    1097              :         {
    1098            6 :           std::swap (m_phi_for_crc, m_phi_for_data);
    1099              :         }
    1100              :     }
    1101          393 : }
    1102              : 
    1103              : /* Validates CRC and data arguments and
    1104              :    sets them for potential CRC loop replacement.
    1105              : 
    1106              :    The function extracts the CRC and data arguments from PHI nodes and
    1107              :    performs several checks to ensure that the CRC and data are suitable for
    1108              :    replacing the CRC loop with a more efficient implementation.
    1109              : 
    1110              :   Returns true if the arguments are valid and the loop replacement is possible,
    1111              :   false otherwise.  */
    1112              : 
    1113          390 : bool crc_optimization::validate_crc_and_data ()
    1114              : {
    1115              :   /* Set m_crc_arg and check if fits in word_mode.  */
    1116          390 :   gcc_assert (m_phi_for_crc);
    1117          390 :   m_crc_arg = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc,
    1118              :                                      loop_preheader_edge (m_crc_loop));
    1119          390 :   gcc_assert (m_crc_arg);
    1120              : 
    1121          390 :   unsigned HOST_WIDE_INT
    1122          390 :   data_size = tree_to_uhwi (m_crc_loop->nb_iterations) + 1;
    1123              :   /* We don't support the case where data is larger than the CRC.  */
    1124          390 :   if (TYPE_PRECISION (TREE_TYPE (m_crc_arg)) < data_size)
    1125              :     return false;
    1126              : 
    1127              :   /* Set m_data_arg if a PHI node for data exists,
    1128              :      and check its size against loop iterations.
    1129              :      This is the case when data and CRC are XOR-ed in the loop.  */
    1130          390 :   if (m_phi_for_data)
    1131              :     {
    1132          205 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1133          163 :         fprintf (dump_file,
    1134              :                  "Data and CRC are xor-ed in the for loop.  Initializing data "
    1135              :                  "with its value.\n");
    1136          205 :       m_data_arg = PHI_ARG_DEF_FROM_EDGE (m_phi_for_data,
    1137              :                                           loop_preheader_edge (m_crc_loop));
    1138          205 :       gcc_assert (m_data_arg);
    1139          205 :       if (TYPE_PRECISION (TREE_TYPE (m_data_arg)) != data_size)
    1140              :         {
    1141            9 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1142            9 :             fprintf (dump_file,
    1143              :                      "Loop iteration number and data's size differ.\n");
    1144              :           return false;
    1145              :         }
    1146              :         return true;
    1147              :     }
    1148              :   return true;
    1149              : }
    1150              : 
    1151              : /* Convert polynomial to unsigned HOST_WIDE_INT.  */
    1152              : 
    1153              : void
    1154          369 : crc_optimization::construct_constant_polynomial (value *polynomial)
    1155              : {
    1156          369 :   m_polynomial = 0;
    1157        12001 :   for (unsigned i = 0; i < (*polynomial).length (); i++)
    1158              :     {
    1159        11632 :       value_bit *const_bit;
    1160        11632 :       if (m_is_bit_forward)
    1161         4712 :         const_bit = (*polynomial)[(*polynomial).length () - 1 - i];
    1162              :       else
    1163         6920 :         const_bit = (*polynomial)[i];
    1164        11632 :       m_polynomial <<= 1;
    1165        18854 :       m_polynomial ^= (as_a<bit *> (const_bit))->get_val () ? 1 : 0;
    1166              :     }
    1167          369 : }
    1168              : 
    1169              : /* Returns phi statement which may hold the calculated CRC.  */
    1170              : 
    1171              : gphi *
    1172          412 : crc_optimization::get_output_phi ()
    1173              : {
    1174          412 :   edge loop_exit = single_exit (m_crc_loop);
    1175          412 :   if (!loop_exit)
    1176              :     {
    1177            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1178            0 :         fprintf (dump_file, "The loop doesn't have single exit.\n");
    1179              :       return nullptr;
    1180              :     }
    1181          412 :   basic_block bb = loop_exit->dest;
    1182          412 :   gphi *output_crc = nullptr;
    1183          412 :   int phi_count = 0;
    1184              : 
    1185              :   /* We are only interested in cases when there is only one phi at the
    1186              :    loop exit, and that phi can potentially represent the CRC.
    1187              :    If there are other phis present, it indicates that additional values are
    1188              :    being calculated within the loop that are used outside it.  */
    1189          863 :   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
    1190          451 :        gsi_next (&gsi))
    1191              :     {
    1192          470 :       tree phi_result = gimple_phi_result (gsi.phi ());
    1193              : 
    1194              :       /* Don't consider virtual operands.  */
    1195          940 :       if (!virtual_operand_p (phi_result))
    1196              :         {
    1197          431 :           if (phi_count < 1)
    1198              :             {
    1199              :               output_crc = gsi.phi ();
    1200              :               phi_count++;
    1201              :             }
    1202              :           else
    1203              :             {
    1204           19 :               if (dump_file && (dump_flags & TDF_DETAILS))
    1205           18 :                 fprintf (dump_file, "There is more than one output phi.\n");
    1206           19 :               return nullptr;
    1207              :             }
    1208              :         }
    1209              :     }
    1210              : 
    1211          393 :   if (output_crc)
    1212              :     {
    1213          393 :       if (gimple_phi_num_args (output_crc) == 1)
    1214              :         return output_crc;
    1215              :     }
    1216              : 
    1217            0 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1218            0 :     fprintf (dump_file, "Couldn't determine output CRC.\n");
    1219              :   return nullptr;
    1220              : }
    1221              : 
    1222              : /* Attempts to optimize a CRC calculation loop by replacing it with a call to
    1223              :    an internal function (IFN_CRC or IFN_CRC_REV).
    1224              :    Returns true if replacement succeeded, otherwise false.  */
    1225              : 
    1226              : bool
    1227          345 : crc_optimization::optimize_crc_loop (class loop *loop, gphi *output_crc)
    1228              : {
    1229          345 :   if (!output_crc)
    1230              :     {
    1231            0 :       if (dump_file)
    1232            0 :         fprintf (dump_file, "Couldn't determine output CRC.\n");
    1233              :       return false;
    1234              :     }
    1235              : 
    1236          345 :   if (!m_data_arg)
    1237              :     {
    1238          168 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1239           82 :         fprintf (dump_file,
    1240              :                  "Data and CRC are xor-ed before for loop.  Initializing data "
    1241              :                  "with 0.\n");
    1242              :       /* Create a new variable for the data.
    1243              :        Determine the data's size with the loop iteration count.  */
    1244          168 :       unsigned HOST_WIDE_INT
    1245          168 :         data_size = tree_to_uhwi (m_crc_loop->nb_iterations) + 1;
    1246          168 :       tree type = build_nonstandard_integer_type (data_size, 1);
    1247              :      /* For the CRC calculation, it doesn't matter CRC is calculated for the
    1248              :         (CRC^data, 0) or (CRC, data).  */
    1249          168 :       m_data_arg = build_int_cstu (type, 0);
    1250              :     }
    1251              : 
    1252              :   /* Build tree node for the polynomial from its constant value.  */
    1253          345 :   tree polynomial_arg = build_int_cstu (TREE_TYPE (m_crc_arg), m_polynomial);
    1254          345 :   gcc_assert (polynomial_arg);
    1255              : 
    1256          345 :   internal_fn ifn;
    1257          345 :   if (m_is_bit_forward)
    1258              :     ifn = IFN_CRC;
    1259              :   else
    1260          180 :     ifn = IFN_CRC_REV;
    1261              : 
    1262          345 :   tree phi_result = gimple_phi_result (output_crc);
    1263          345 :   location_t loc;
    1264          345 :   loc = EXPR_LOCATION (phi_result);
    1265              : 
    1266              :   /* If the target does not have an expansion for CRC optimally then the table
    1267              :      based lookup will need at least 255-bytes of RODATA and won't be smaller
    1268              :      than the original code itself.  */
    1269          345 :   if (!optimize_loop_for_speed_p (loop))
    1270              :     {
    1271            2 :       tree data_type = TREE_TYPE (m_data_arg);
    1272            2 :       tree result_type = TREE_TYPE (phi_result);
    1273            2 :       auto ty_pair = tree_pair (data_type, result_type);
    1274            2 :       if (!direct_internal_fn_supported_p (ifn, ty_pair, OPTIMIZE_FOR_BOTH))
    1275            2 :         return false;
    1276              :     }
    1277              : 
    1278          343 :   basic_block *bbs = get_loop_body (loop);
    1279          343 :   reset_debug_uses_outside_loop (loop, bbs, loop->num_nodes);
    1280          343 :   free (bbs);
    1281              : 
    1282              :   /* Add IFN call and write the return value in the phi_result.  */
    1283          343 :   gcall *call = gimple_build_call_internal (ifn, 3, m_crc_arg, m_data_arg,
    1284              :                                             polynomial_arg);
    1285              : 
    1286          343 :   gimple_call_set_lhs (call, phi_result);
    1287          343 :   gimple_set_location (call, loc);
    1288          343 :   gimple_stmt_iterator si = gsi_after_labels (gimple_bb (output_crc));
    1289          343 :   gsi_insert_before (&si, call, GSI_SAME_STMT);
    1290              : 
    1291              :   /* Remove phi statement, which was holding CRC result.  */
    1292          343 :   gimple_stmt_iterator tmp_gsi = gsi_for_stmt (output_crc);
    1293          343 :   remove_phi_node (&tmp_gsi, false);
    1294              : 
    1295              :   /* Alter the exit condition of the loop to always exit.  */
    1296          343 :   gcond* loop_exit_cond = get_loop_exit_condition (m_crc_loop);
    1297          343 :   gimple_cond_make_false (loop_exit_cond);
    1298          343 :   update_stmt (loop_exit_cond);
    1299          343 :   return true;
    1300              : }
    1301              : 
    1302              : unsigned int
    1303       231308 : crc_optimization::execute (function *fun)
    1304              : {
    1305       231308 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1306          339 :     fprintf (dump_file, "\nExamining %s function.\n",
    1307              :              function_name (fun));
    1308              : 
    1309       462616 :   if (number_of_loops (fun) <= 1)
    1310              :     return 0;
    1311              : 
    1312              :   /* Get loops of the function.  */
    1313       231308 :   auto loop_list = loops_list (fun, LI_ONLY_INNERMOST);
    1314      1217341 :   for (auto loop: loop_list)
    1315              :     {
    1316              :       /* Perform initial checks to filter out non-CRCs.  */
    1317       523484 :       if (loop_may_calculate_crc (loop))
    1318              :         {
    1319              :           /* Get the phi which will hold the calculated CRC.  */
    1320          412 :           gphi *output_crc = get_output_phi ();
    1321          412 :           if (!output_crc)
    1322              :             break;
    1323              : 
    1324          393 :           swap_crc_and_data_if_needed (output_crc);
    1325          393 :           if (!is_output_crc (output_crc))
    1326              :             break;
    1327          390 :           if (!validate_crc_and_data ())
    1328              :             break;
    1329              : 
    1330          381 :           edge loop_latch = loop_latch_edge (m_crc_loop);
    1331          381 :           tree calced_crc = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, loop_latch);
    1332          381 :           crc_symbolic_execution execute_loop (m_crc_loop, nullptr);
    1333              :           /* Execute the loop assigning specific values to CRC and data
    1334              :              for extracting the polynomial.  */
    1335          381 :           std::pair <tree, value *>
    1336          381 :               calc_polynom = execute_loop.extract_polynomial (m_phi_for_crc,
    1337              :                                                               m_phi_for_data,
    1338              :                                                               calced_crc,
    1339              :                                                               m_is_bit_forward);
    1340              : 
    1341          381 :           value *polynom_value = calc_polynom.second;
    1342              :           /* Stop analysis if we couldn't get the polynomial's value.  */
    1343          381 :           if (!polynom_value)
    1344              :             break;
    1345              : 
    1346              :           /* Stop analysis in case optimize_size is specified
    1347              :              and table-based would be generated.  This check is only needed for
    1348              :              TARGET_CRC case, as polynomial's value isn't known in the
    1349              :              beginning.  */
    1350          369 :           construct_constant_polynomial (polynom_value);
    1351              : 
    1352          369 :           if (!loop_calculates_crc (output_crc, calc_polynom))
    1353              :             break;
    1354              : 
    1355          345 :           if (dump_file)
    1356          289 :             fprintf (dump_file, "The loop with %d header BB index "
    1357          289 :                                 "calculates CRC!\n", m_crc_loop->header->index);
    1358              : 
    1359          345 :           if (!optimize_crc_loop (loop, output_crc))
    1360              :             {
    1361            2 :               if (dump_file)
    1362            0 :                 fprintf (dump_file, "Couldn't generate faster CRC code.\n");
    1363              :             }
    1364          381 :         }
    1365              :     }
    1366       231308 :   return 0;
    1367       231308 : }
    1368              : 
    1369              : namespace
    1370              : {
    1371              : 
    1372              :     const pass_data pass_data_crc_optimization
    1373              :         = {
    1374              :             GIMPLE_PASS, /* type */
    1375              :             "crc", /* name */
    1376              :             OPTGROUP_NONE, /* optinfo_flags */
    1377              :             TV_GIMPLE_CRC_OPTIMIZATION, /* tv_id */
    1378              :             (PROP_cfg | PROP_ssa), /* properties_required */
    1379              :             0, /* properties_provided */
    1380              :             0, /* properties_destroyed */
    1381              :             0, /* todo_flags_start */
    1382              :             0, /* todo_flags_finish */
    1383              :         };
    1384              : 
    1385              :     class pass_crc_optimization : public gimple_opt_pass {
    1386              :      public:
    1387       297180 :       pass_crc_optimization (gcc::context *ctxt)
    1388       594360 :           : gimple_opt_pass (pass_data_crc_optimization, ctxt)
    1389              :       {}
    1390              : 
    1391              :       /* opt_pass methods: */
    1392       248475 :       virtual bool gate (function *)
    1393              :       {
    1394       248475 :         return flag_optimize_crc;
    1395              :       }
    1396              : 
    1397              :       virtual unsigned int execute (function *);
    1398              : 
    1399              :     }; // class pass_crc_optimization
    1400              : 
    1401              :     unsigned int
    1402       231308 :     pass_crc_optimization::execute (function *fun)
    1403              :     {
    1404       231308 :       return crc_optimization ().execute (fun);
    1405              :     }
    1406              : 
    1407              : } // anon namespace
    1408              : 
    1409              : gimple_opt_pass *
    1410       297180 : make_pass_crc_optimization (gcc::context *ctxt)
    1411              : {
    1412       297180 :   return new pass_crc_optimization (ctxt);
    1413              : }
        

Generated by: LCOV version 2.5.0-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.