LCOV - code coverage report
Current view: top level - gcc - crc-verification.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 85.3 % 477 407
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 35 35
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Execute symbolically all paths of the loop.
       2              :    Calculate the value of the polynomial by executing loop with real values to
       3              :    create LFSR state.
       4              :    After each iteration check that final states of calculated CRC values match
       5              :    determined LFSR.
       6              :    Copyright (C) 2022-2026 Free Software Foundation, Inc.
       7              :    Contributed by Mariam Arutunian <mariamarutunian@gmail.com>
       8              : 
       9              : This file is part of GCC.
      10              : 
      11              : GCC is free software; you can redistribute it and/or modify it under
      12              : the terms of the GNU General Public License as published by the Free
      13              : Software Foundation; either version 3, or (at your option) any later
      14              : version.
      15              : 
      16              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      17              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      18              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      19              : for more details.
      20              : 
      21              : You should have received a copy of the GNU General Public License
      22              : along with GCC; see the file COPYING3.  If not see
      23              : <http://www.gnu.org/licenses/>.   */
      24              : 
      25              : #include "crc-verification.h"
      26              : #include "config.h"
      27              : #include "system.h"
      28              : #include "coretypes.h"
      29              : #include "backend.h"
      30              : #include "tree.h"
      31              : #include "gimple.h"
      32              : #include "ssa.h"
      33              : #include "gimple-iterator.h"
      34              : #include "tree-cfg.h"
      35              : #include "cfganal.h"
      36              : #include "tree-ssa-loop.h"
      37              : 
      38              : /* Check whether defined variable is used outside the loop, only
      39              :    CRC's definition is allowed to be used outside the loop.  */
      40              : 
      41              : bool
      42        67117 : crc_symbolic_execution::is_used_outside_the_loop (tree def)
      43              : {
      44        67117 :   imm_use_iterator imm_iter;
      45        67117 :   gimple *use_stmt;
      46       142122 :   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
      47              :     {
      48              :       /* Debug uses must not affect whether the loop is recognized.  Stale
      49              :          outside-loop binds are reset if the loop is transformed.  */
      50        86598 :       if (is_gimple_debug (use_stmt))
      51         2130 :         continue;
      52        84468 :       if (!flow_bb_inside_loop_p (m_crc_loop, use_stmt->bb))
      53              :         {
      54        11593 :           if (is_a<gphi *> (use_stmt)
      55        11593 :               && as_a<gphi *> (use_stmt) == m_output_crc)
      56              :             return false;
      57            0 :           if (dump_file)
      58            0 :             fprintf (dump_file, "Defined variable is used outside the loop.\n");
      59              :           return true;
      60              :         }
      61        11593 :     }
      62        55524 :   return false;
      63              : }
      64              : 
      65              : /* Calculate value of the rhs operation of GS assignment statement
      66              :    and assign it to lhs variable.  */
      67              : 
      68              : bool
      69        58057 : crc_symbolic_execution::execute_assign_statement (const gassign *gs)
      70              : {
      71        58057 :   enum tree_code rhs_code = gimple_assign_rhs_code (gs);
      72        58057 :   tree lhs = gimple_assign_lhs (gs);
      73        58057 :   if (dump_file && (dump_flags & TDF_DETAILS))
      74        41415 :     fprintf (dump_file, "lhs type : %s \n",
      75        41415 :              get_tree_code_name (TREE_CODE (lhs)));
      76              : 
      77              :   /* This will filter some normal cases too.  Ex.  usage of array.  */
      78        58057 :   if (TREE_CODE (lhs) != SSA_NAME)
      79              :     return false;
      80              : 
      81              :   /* Check uses only when m_output_crc is known.  */
      82        58051 :   if (m_output_crc)
      83        55524 :     if (is_used_outside_the_loop (lhs))
      84              :       return false;
      85              : 
      86        58051 :   if (gimple_num_ops (gs) != 2 && gimple_num_ops (gs) != 3)
      87              :     {
      88            0 :       if (dump_file)
      89            0 :         fprintf (dump_file,
      90              :                  "Warning, encountered unsupported operation, "
      91              :                  "with %s code while executing assign statement!\n",
      92              :                  get_tree_code_name (rhs_code));
      93              :       return false;
      94              :     }
      95              : 
      96        58051 :   tree op1 = gimple_assign_rhs1 (gs);
      97        58051 :   tree op2 = nullptr;
      98              : 
      99        58051 :   if (gimple_num_ops (gs) == 3)
     100        52791 :     op2 = gimple_assign_rhs2 (gs);
     101              : 
     102        58051 :   state *current_state = m_states.last ();
     103        58051 :   return current_state->do_operation (rhs_code, op1, op2, lhs);
     104              : }
     105              : 
     106              : /* Add E edge into the STACK if it doesn't have an immediate
     107              :    successor edge going to the loop header.
     108              : 
     109              :    When loop counter is checked in the if condition,
     110              :    we mustn't continue on real path as we want to stop the execution before
     111              :    the second iteration.  */
     112              : 
     113              : bool
     114        12334 : crc_symbolic_execution::add_edge (edge e, auto_vec<edge> &stack)
     115              : {
     116        12334 :   if (EDGE_COUNT (e->dest->succs) == 0)
     117              :     return false;
     118              : 
     119        12334 :   edge next_bb_edge = EDGE_SUCC (e->dest, 0);
     120        12334 :   if (next_bb_edge && next_bb_edge->dest == m_crc_loop->header)
     121              :     {
     122        11272 :       if (dump_file && (dump_flags & TDF_DETAILS))
     123         7911 :         fprintf (dump_file, "Completed one iteration.  "
     124              :                             "Won't iterate loop once more, yet.\n");
     125              : 
     126        11272 :       return keep_states ();
     127              :     }
     128              :   else
     129              :     {
     130         1062 :       if (dump_file && (dump_flags & TDF_DETAILS))
     131          683 :         fprintf (dump_file, "Adding the edge into the stack.\n");
     132              : 
     133              :       /* If the result of the condition is true/false,
     134              :          continue execution only by the true/false branch.  */
     135         1062 :       stack.quick_push (e);
     136              :     }
     137         1062 :   return true;
     138              : }
     139              : 
     140              : /* Add next basic blocks of the conditional block COND_BB
     141              :    for the execution path into the STACK.
     142              :    If the condition depends on symbolic values, keep both edges.
     143              :    If the condition is true, keep true edge, else - false edge.
     144              :    Returns true if addition succeeds.  Otherwise - false.  */
     145              : 
     146              : bool
     147        18129 : crc_symbolic_execution::add_next_bbs (basic_block cond_bb,
     148              :                                       state *new_branch_state,
     149              :                                       auto_vec<edge> &stack)
     150              : {
     151        18129 :   edge true_edge;
     152        18129 :   edge false_edge;
     153        18129 :   extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
     154              : 
     155              :   /* When the condition depends on symbolic values.  */
     156        18129 :   if (new_branch_state->get_last_cond_status () == CS_SYM)
     157              :     {
     158              :       /* Supported CRC cases may have only two states.  */
     159         5795 :       if (m_states.length () == 2)
     160              :         {
     161            0 :           if (dump_file && (dump_flags & TDF_DETAILS))
     162            0 :             fprintf (dump_file, "Going to add a new state, "
     163              :                                 "but there's already two states.\n");
     164              :           return false;
     165              :         }
     166              :       /* Add true branch's state into the states.
     167              :          False branch's state will be kept in the current state.  */
     168         5795 :       m_states.quick_push (new_branch_state);
     169              : 
     170         5795 :       if (dump_file && (dump_flags & TDF_DETAILS))
     171         4056 :         fprintf (dump_file, "Adding true and false edges into the stack.\n");
     172              : 
     173              :       /* Add outgoing edges to the stack.  */
     174         5795 :       stack.quick_push (false_edge);
     175         5795 :       stack.quick_push (true_edge);
     176              : 
     177         5795 :       return true;
     178              :     }
     179              :   /* When the condition evaluates to true.  */
     180        12334 :   else if (new_branch_state->get_last_cond_status () == CS_TRUE)
     181              :     {
     182        11629 :       if (dump_file && (dump_flags & TDF_DETAILS))
     183         8139 :         fprintf (dump_file, "Condition is true.\n");
     184        11629 :       add_edge (true_edge, stack);
     185              :     }
     186              :   /* When the condition evaluates to false.  */
     187          705 :   else if (new_branch_state->get_last_cond_status () == CS_FALSE)
     188              :     {
     189          705 :       if (dump_file && (dump_flags & TDF_DETAILS))
     190          455 :         fprintf (dump_file, "Condition is false.\n");
     191          705 :       add_edge (false_edge, stack);
     192              :     }
     193              :   else
     194              :     {
     195            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     196            0 :         fprintf (dump_file, "Something went wrong "
     197              :                             "during handling conditional statement.\n");
     198              :       return false;
     199              :     }
     200              : 
     201              :   /* When we continue execution of only one path,
     202              :      there's no need of new state.  */
     203        12334 :   delete new_branch_state;
     204              :   return true;
     205              : }
     206              : 
     207              : /* Add conditions depending on symbolic variables in the states.
     208              : 
     209              :    Keep conditions of each branch execution in its state.
     210              :      Ex.
     211              :        if (a == 0)  // a's value is unknown
     212              : 
     213              :        new_branch_state.keep (a==0)
     214              :        current_state.keep (a!=0)
     215              : 
     216              :      The condition is kept in the bit level.
     217              :      For ex.
     218              :      If a's size is 8 and its value is {symb_a, 0, 0, 0, 0, 0, 0, 0},
     219              :      then for a == 0 we'll have symb_a == 0 condition.  */
     220              : 
     221              : bool
     222        18129 : crc_symbolic_execution::add_condition (const gcond *cond,
     223              :                                        state *current_state,
     224              :                                        state *new_branch_state)
     225              : {
     226        18129 :   tree lhs = gimple_cond_lhs (cond);
     227        18129 :   tree rhs = gimple_cond_rhs (cond);
     228        18129 :   switch (gimple_cond_code (cond))
     229              :     {
     230            1 :       case EQ_EXPR:
     231            1 :         {
     232            1 :           new_branch_state->add_equal_cond (lhs, rhs);
     233            1 :           if (new_branch_state->get_last_cond_status () == CS_SYM)
     234            0 :             current_state->add_not_equal_cond (lhs, rhs);
     235              :           return true;
     236              :         }
     237        15872 :       case NE_EXPR:
     238        15872 :         {
     239        15872 :           new_branch_state->add_not_equal_cond (lhs, rhs);
     240        15872 :           if (new_branch_state->get_last_cond_status () == CS_SYM)
     241         3667 :             current_state->add_equal_cond (lhs, rhs);
     242              :           return true;
     243              :         }
     244            0 :       case GT_EXPR:
     245            0 :         {
     246            0 :           new_branch_state->add_greater_than_cond (lhs, rhs);
     247            0 :           if (new_branch_state->get_last_cond_status () == CS_SYM)
     248            0 :             current_state->add_less_or_equal_cond (lhs, rhs);
     249              :           return true;
     250              :         }
     251         2256 :       case LT_EXPR:
     252         2256 :         {
     253         2256 :           new_branch_state->add_less_than_cond (lhs, rhs);
     254         2256 :           if (new_branch_state->get_last_cond_status () == CS_SYM)
     255         2128 :             current_state->add_greater_or_equal_cond (lhs, rhs);
     256              :           return true;
     257              :         }
     258            0 :       case GE_EXPR:
     259            0 :         {
     260            0 :           new_branch_state->add_greater_or_equal_cond (lhs, rhs);
     261            0 :           if (new_branch_state->get_last_cond_status () == CS_SYM)
     262            0 :             current_state->add_less_than_cond (lhs, rhs);
     263              :           return true;
     264              :         }
     265            0 :       case LE_EXPR:
     266            0 :         {
     267            0 :           new_branch_state->add_less_or_equal_cond (lhs, rhs);
     268            0 :           if (new_branch_state->get_last_cond_status () == CS_SYM)
     269            0 :             current_state->add_greater_than_cond (lhs, rhs);
     270              :           return true;
     271              :         }
     272            0 :       default:
     273            0 :         {
     274            0 :           if (dump_file && (dump_flags & TDF_DETAILS))
     275            0 :             fprintf (dump_file, "Unsupported condition.\n");
     276              :           return false;
     277              :         }
     278              :     }
     279              : }
     280              : 
     281              : /* Create new states for true and false branches.
     282              :    Keep conditions in new created states.  */
     283              : 
     284              : bool
     285        18129 : crc_symbolic_execution::resolve_condition (const gcond *cond,
     286              :                                            auto_vec<edge> &stack)
     287              : {
     288        18129 :   state *current_state = m_states.last ();
     289        18129 :   state *new_branch_state = new state (*current_state);
     290              : 
     291              :   /* Create new states and for true and false branches keep corresponding
     292              :      conditions.  */
     293        18129 :   if (!add_condition (cond, current_state, new_branch_state))
     294              :     return false;
     295              : 
     296              :   /* Add true and false edges to the stack.  */
     297        18129 :   return add_next_bbs (cond->bb, new_branch_state, stack);
     298              : }
     299              : 
     300              : /* If final states are less than two, add new FINAL_STATE and return true.
     301              :    Otherwise, return false.
     302              :    Supported CRC cases may not have more than two final states.  */
     303        11962 : bool crc_symbolic_execution::add_final_state (state *final_state)
     304              : {
     305        11962 :   if (m_final_states.length () < 2)
     306        11962 :       m_final_states.quick_push (final_state);
     307              :   else
     308              :     {
     309            0 :       if (dump_file)
     310            0 :         fprintf (dump_file,
     311              :                  "There are already two final states\n");
     312              :       return false;
     313              :     }
     314        11962 :     return true;
     315              : }
     316              : 
     317              : /* Keep the state of the executed path in final states.  */
     318              : 
     319        11962 : bool crc_symbolic_execution::keep_states ()
     320              : {
     321        11962 :   if (m_states.is_empty ())
     322              :     return false;
     323              : 
     324        11962 :   if (!add_final_state (m_states.last ()))
     325              :     {
     326            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     327            0 :         fprintf (dump_file, "Couldn't add final state.\n");
     328              :       return false;
     329              :     }
     330              : 
     331        11962 :   m_states.pop ();
     332        11962 :   return true;
     333              : }
     334              : 
     335              : /* Execute gimple statements of BB.
     336              :    Keeping values of variables in the state.  */
     337              : 
     338              : bool
     339        29884 : crc_symbolic_execution::execute_bb_gimple_statements (basic_block bb,
     340              :                                                       auto_vec<edge> &stack)
     341              : {
     342        59768 :   for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
     343        97065 :        !gsi_end_p (bsi); gsi_next (&bsi))
     344              :     {
     345        85322 :       gimple *gs = gsi_stmt (bsi);
     346        85322 :       if (dump_file && (dump_flags & TDF_DETAILS))
     347              :         {
     348        59928 :           fprintf (dump_file, "Executing ");
     349        59928 :           print_gimple_stmt (dump_file, gs, dump_flags);
     350              :         }
     351        85322 :       switch (gimple_code (gs))
     352              :         {
     353        58057 :           case GIMPLE_ASSIGN:
     354        58057 :             {
     355        58057 :               if (!execute_assign_statement (as_a<const gassign *> (gs)))
     356        29884 :                 return false;
     357              :               break;
     358              :             }
     359        18129 :           case GIMPLE_COND:
     360        18129 :             {
     361        18129 :               return resolve_condition (as_a<const gcond *> (gs), stack);
     362              :             }
     363              :           /* Just skip debug statements.  */
     364              :           case GIMPLE_DEBUG:
     365              :             break;
     366            6 :           default:
     367            6 :             {
     368            6 :               if (dump_file)
     369            6 :                 fprintf (dump_file,
     370              :                          "Warning, encountered unsupported statement, "
     371              :                          "while executing gimple statements!\n");
     372              :               return false;
     373              :             }
     374              :         }
     375              :     }
     376              : 
     377              :   /* Add each outgoing edge of the current block to the stack,
     378              :      despite the edges going to the loop header.
     379              :      This code isn't reachable if the last statement of the basic block
     380              :      is a conditional statement or return statement.
     381              :      Those cases are handled separately.
     382              :      We mustn't encounter edges going to the CRC loop header.  */
     383              : 
     384        11743 :   edge out_edge;
     385        11743 :   edge_iterator ei;
     386        23486 :   FOR_EACH_EDGE (out_edge, ei, bb->succs)
     387        11743 :     if (out_edge->dest != m_crc_loop->header)
     388        11743 :       stack.quick_push (out_edge);
     389              :     else
     390              :       return false;
     391              : 
     392              :   return true;
     393              : }
     394              : 
     395              : /* Assign values of phi instruction to its result.
     396              :    Keep updated values in the state.  */
     397              : 
     398              : bool
     399        23705 : crc_symbolic_execution::execute_bb_phi_statements (basic_block bb,
     400              :                                                    edge incoming_edge)
     401              : {
     402        35667 :   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
     403        11962 :        gsi_next (&gsi))
     404              :     {
     405        11962 :       gphi *phi = gsi.phi ();
     406        11962 :       tree lhs = gimple_phi_result (phi);
     407              : 
     408              :       /* Check uses only when m_output_crc is known.  */
     409        11962 :       if (m_output_crc)
     410        11593 :         if (is_used_outside_the_loop (lhs))
     411            0 :           return false;
     412              : 
     413              :       /* Don't consider virtual operands.  */
     414        23924 :       if (virtual_operand_p (lhs))
     415            0 :         continue;
     416              : 
     417        11962 :       if (dump_file && (dump_flags & TDF_DETAILS))
     418              :         {
     419         8353 :           fprintf (dump_file, "Determining the value "
     420              :                               "for the following phi.\n");
     421         8353 :           print_gimple_stmt (dump_file, phi, dump_flags);
     422              :         }
     423              : 
     424        11962 :       tree rhs = PHI_ARG_DEF_FROM_EDGE (phi, incoming_edge);
     425              : 
     426        11962 :       state *current_state = m_states.last ();
     427        11962 :       if (!current_state->do_operation (VAR_DECL, rhs, nullptr, lhs))
     428              :         return false;
     429              :     }
     430        23705 :   return true;
     431              : }
     432              : 
     433              : /* Execute all statements of BB.
     434              :    Keeping values of variables in the state.  */
     435              : 
     436              : bool
     437        23705 : crc_symbolic_execution::execute_bb_statements (basic_block bb,
     438              :                                                edge incoming_edge,
     439              :                                                auto_vec<edge> &stack)
     440              : {
     441        23705 :   if (!execute_bb_phi_statements (bb, incoming_edge))
     442              :     return false;
     443              : 
     444        23705 :   return execute_bb_gimple_statements (bb, stack);
     445              : }
     446              : 
     447              : /* If the phi statements' result variables have initial constant value in the
     448              :    beginning of the loop, initialize those variables.  */
     449              : 
     450              : void
     451          350 : assign_known_vals_to_header_phis (state *state, class loop *crc_loop)
     452              : {
     453          350 :   basic_block bb = crc_loop->header;
     454         1603 :   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
     455         1253 :        gsi_next (&gsi))
     456              :     {
     457              : 
     458         1253 :       gphi *phi = gsi.phi ();
     459         1253 :       tree lhs = gimple_phi_result (phi);
     460              : 
     461              :       /* Don't consider virtual operands.  */
     462         2506 :       if (virtual_operand_p (lhs))
     463           25 :         continue;
     464              : 
     465         1228 :       tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi,
     466              :                                                loop_preheader_edge (crc_loop));
     467         1228 :       if (TREE_CODE (inital_val) == INTEGER_CST)
     468              :         {
     469          706 :           if (dump_file && (dump_flags & TDF_DETAILS))
     470              :             {
     471          453 :               fprintf (dump_file, "First value of phi is a constant, "
     472              :                                   "assigning the number to ");
     473          453 :               print_generic_expr (dump_file, lhs, dump_flags);
     474          453 :               fprintf (dump_file, " variable.\n");
     475              :             }
     476          706 :           state->do_operation (VAR_DECL, inital_val,
     477              :                                nullptr, lhs);
     478              :         }
     479              :     }
     480          350 : }
     481              : 
     482              : /* If the phi statements' result variables have initial constant value in the
     483              :    beginning of the loop, initialize those variables with
     484              :    the value calculated during the previous iteration.  */
     485              : 
     486              : bool
     487         5448 : assign_calc_vals_to_header_phis (const vec<state *> &prev_states,
     488              :                                  state *curr_state,
     489              :                                  class loop *crc_loop)
     490              : {
     491         5448 :   basic_block bb = crc_loop->header;
     492        25825 :   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
     493        20377 :        gsi_next (&gsi))
     494              :     {
     495        20377 :       gphi *phi = gsi.phi ();
     496        20377 :       tree lhs = gimple_phi_result (phi);
     497              : 
     498              :       /* Don't consider virtual operands.  */
     499        40754 :       if (virtual_operand_p (lhs))
     500          178 :         continue;
     501        20199 :       tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi,
     502              :                                                loop_preheader_edge (crc_loop));
     503        20199 :       if (TREE_CODE (inital_val) == INTEGER_CST)
     504              :         {
     505        10910 :           tree input_tree = PHI_ARG_DEF_FROM_EDGE (phi,
     506              :                                                    loop_latch_edge (crc_loop));
     507        10910 :           value * val_st1 = prev_states[0]->get_value (input_tree),
     508        10910 :               *val_st2 = prev_states[1]->get_value (input_tree);
     509        10910 :           if (!state::is_bit_vector (val_st1)
     510        10910 :               || !state::is_bit_vector (val_st2))
     511              :             {
     512            0 :               if (dump_file && (dump_flags & TDF_DETAILS))
     513              :                 {
     514            0 :                   fprintf (dump_file, "The calculated values of  ");
     515            0 :                   print_generic_expr (dump_file, input_tree, dump_flags);
     516            0 :                   fprintf (dump_file, " variable is not constant.\n");
     517              :                 }
     518            0 :               return false;
     519              :             }
     520        10910 :           else if (!state::check_const_value_equality (val_st1, val_st2))
     521              :             {
     522            0 :               if (dump_file && (dump_flags & TDF_DETAILS))
     523              :                 {
     524            0 :                   fprintf (dump_file, "The calculated values of  ");
     525            0 :                   print_generic_expr (dump_file, input_tree, dump_flags);
     526            0 :                   fprintf (dump_file, " variable is different in the previous "
     527              :                                       "iteration paths.\n");
     528              :                 }
     529              :               return false;
     530              :             }
     531              :           else
     532              :             {
     533        10910 :               if (dump_file && (dump_flags & TDF_DETAILS))
     534              :                 {
     535         7684 :                   fprintf (dump_file, "Assigning calculated number to ");
     536         7684 :                   print_generic_expr (dump_file, lhs, dump_flags);
     537         7684 :                   fprintf (dump_file, " variable.\n");
     538              :                 }
     539        10910 :               unsigned HOST_WIDE_INT calc_number
     540        10910 :                   = state::make_number (val_st1);
     541        10910 :               tree calc_num_tree = build_int_cstu (TREE_TYPE (lhs),
     542        10910 :                                                    calc_number);
     543        10910 :               curr_state->do_operation (VAR_DECL, calc_num_tree, nullptr, lhs);
     544              :             }
     545              :         }
     546              :     }
     547         5448 :   return true;
     548              : }
     549              : 
     550              : /* Create initial state of the CRC_LOOP's header BB variables which have
     551              :    constant values.
     552              :    If it is the first iteration of the loop, initialise variables with the
     553              :    initial values, otherwise initialise the variable with the value calculated
     554              :    during the previous execution.  */
     555              : 
     556              : state *
     557         5798 : crc_symbolic_execution::create_initial_state (class loop *crc_loop)
     558              : {
     559         5798 :   state *curr_state = new state;
     560         5798 :   if (!m_final_states.is_empty ())
     561              :     {
     562         5448 :       if (!assign_calc_vals_to_header_phis (m_final_states, curr_state,
     563              :                                             crc_loop))
     564              :         return nullptr;
     565         5448 :       state::remove_states (&m_final_states);
     566              :     }
     567              :   else
     568          350 :     assign_known_vals_to_header_phis (curr_state, crc_loop);
     569              :   return curr_state;
     570              : }
     571              : 
     572              : /* Symbolically execute the CRC loop, doing one iteration.  */
     573              : 
     574              : bool
     575         5798 : crc_symbolic_execution::symb_execute_crc_loop ()
     576              : {
     577         5798 :   if (dump_file && (dump_flags & TDF_DETAILS))
     578         4059 :     fprintf (dump_file, "\n\nExecuting the loop with symbolic values.\n\n");
     579              : 
     580         5798 :   state *curr_state = create_initial_state (m_crc_loop);
     581         5798 :   if (!curr_state)
     582              :     return false;
     583              : 
     584         5798 :   m_states.quick_push (curr_state);
     585              : 
     586         5798 :   auto_vec<edge> stack (m_crc_loop->num_nodes);
     587              : 
     588         5798 :   basic_block header_bb = m_crc_loop->header;
     589         5798 :   if (!execute_bb_gimple_statements (header_bb, stack))
     590              :     return false;
     591              : 
     592              :   /* Successor BB's are added into the stack
     593              :      from the execute_bb_gimple_statements function.  */
     594        35253 :   while (!stack.is_empty ())
     595              :     {
     596              :       /* Look at the edge on the top of the stack.  */
     597        23657 :       edge e = stack.last ();
     598        23657 :       stack.pop ();
     599              : 
     600              :       /* Get destination block of the edge.  */
     601        23657 :       basic_block dest_bb = e->dest;
     602              : 
     603              :       /* Execute only basic blocks of the m_crc_loop.
     604              :          At the end of the execution path save states in final states.  */
     605        23657 :       if (!flow_bb_inside_loop_p (m_crc_loop, dest_bb))
     606              :         {
     607          690 :           m_is_last_iteration = true;
     608          690 :           if (!keep_states ())
     609              :             return false;
     610          690 :           continue;
     611              :         }
     612              : 
     613              :       /* Execute statements.  */
     614        22967 :       if (!execute_bb_statements (dest_bb, e, stack))
     615              :         return false;
     616              :     }
     617              :   return true;
     618         5798 : }
     619              : 
     620              : /* Determine which bit of the DATA must be 1.
     621              :    We assume that last bit must be 1.  */
     622              : 
     623              : unsigned HOST_WIDE_INT
     624          381 : determine_index (tree data, bool is_shift_left)
     625              : {
     626          381 :   if (is_shift_left)
     627              :    /* This won't work correctly in the case when data's size is larger,
     628              :       but MSB is checked for the middle bit.  */
     629          178 :     return tree_to_uhwi (TYPE_SIZE (TREE_TYPE (data))) - 1;
     630              :   return 0;
     631              : }
     632              : 
     633              : /* Assign appropriate values to data, CRC
     634              :    and other phi results to calculate the polynomial.  */
     635              : 
     636              : void
     637          381 : assign_vals_to_header_phis (state *polynomial_state, class loop *crc_loop,
     638              :                             gphi *crc_phi, gphi *data_phi,
     639              :                             bool is_shift_left)
     640              : {
     641          381 :   basic_block bb = crc_loop->header;
     642         1760 :   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
     643         1379 :        gsi_next (&gsi))
     644              :     {
     645              : 
     646         1379 :       gphi *phi = gsi.phi ();
     647         1379 :       tree lhs = gimple_phi_result (phi);
     648              : 
     649              :       /* Don't consider virtual operands.  */
     650         2758 :       if (virtual_operand_p (lhs))
     651           37 :         continue;
     652              : 
     653         1342 :       if ((data_phi && phi == data_phi) || (!data_phi && phi == crc_phi))
     654              :         {
     655          381 :           if (dump_file && (dump_flags & TDF_DETAILS))
     656              :             {
     657          250 :               fprintf (dump_file, "Assigning the required value to ");
     658          250 :               print_generic_expr (dump_file, lhs, dump_flags);
     659          250 :               fprintf (dump_file, " variable.\n");
     660              :             }
     661          381 :           polynomial_state->do_assign_pow2 (lhs,
     662          381 :                                             determine_index (lhs,
     663              :                                                              is_shift_left));
     664              :         }
     665          961 :       else if (phi == crc_phi)
     666              :         {
     667          196 :           if (dump_file && (dump_flags & TDF_DETAILS))
     668              :             {
     669          154 :               fprintf (dump_file, "Assigning 0 value to ");
     670          154 :               print_generic_expr (dump_file, lhs, dump_flags);
     671          154 :               fprintf (dump_file, " variable.\n");
     672              :             }
     673          196 :           polynomial_state->do_operation (VAR_DECL,
     674          196 :                                           build_zero_cst (TREE_TYPE (lhs)),
     675              :                                           nullptr, lhs);
     676              :         }
     677              :       else
     678              :         {
     679          765 :           edge loop_preheader = loop_preheader_edge (crc_loop);
     680          765 :           tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader);
     681          765 :           if (TREE_CODE (inital_val) == INTEGER_CST)
     682              :             {
     683          759 :               if (dump_file && (dump_flags & TDF_DETAILS))
     684              :                 {
     685          498 :                   fprintf (dump_file, "First value of phi is a constant, "
     686              :                                       "assigning the number to ");
     687          498 :                   print_generic_expr (dump_file, lhs, dump_flags);
     688          498 :                   fprintf (dump_file, " variable.\n");
     689              :                 }
     690          759 :               polynomial_state->do_operation (VAR_DECL, inital_val,
     691              :                                               nullptr, lhs);
     692              :             }
     693              :           else
     694              :             {
     695            6 :               if (dump_file && (dump_flags & TDF_DETAILS))
     696              :                 {
     697            6 :                   fprintf (dump_file, "First value of phi isn't constant, "
     698              :                                       "assigning to ");
     699            6 :                   print_generic_expr (dump_file, lhs, dump_flags);
     700            6 :                   fprintf (dump_file, " variable.\n");
     701              :                 }
     702            6 :               polynomial_state->do_operation (VAR_DECL,
     703            6 :                                               build_zero_cst (TREE_TYPE (lhs)),
     704              :                                               nullptr, lhs);
     705              :             }
     706              :         }
     707              :     }
     708          381 : }
     709              : 
     710              : /* Execute the loop, which calculates CRC with initial values,
     711              :    to calculate the polynomial.  */
     712              : 
     713              : bool
     714          381 : crc_symbolic_execution::execute_crc_loop (gphi *crc_phi,
     715              :                                           gphi *data_phi,
     716              :                                           bool is_shift_left)
     717              : {
     718          381 :   if (dump_file && (dump_flags & TDF_DETAILS))
     719          250 :     fprintf (dump_file, "\n\nTrying to calculate the polynomial.\n\n");
     720              : 
     721          381 :   m_states.quick_push (new state);
     722              : 
     723          381 :   basic_block bb = m_crc_loop->header;
     724          381 :   assign_vals_to_header_phis (m_states.last (), m_crc_loop, crc_phi, data_phi,
     725              :                               is_shift_left);
     726              : 
     727          381 :   auto_vec<edge> stack (m_crc_loop->num_nodes);
     728              : 
     729          381 :   if (!execute_bb_gimple_statements (bb, stack))
     730              :     return false;
     731              : 
     732              :   /* stack may not be empty.  Successor BB's are added into the stack
     733              :      from the execute_bb_gimple_statements function.  */
     734         1107 :   while (!stack.is_empty ())
     735              :     {
     736              :       /* Look at the edge on the top of the stack.  */
     737          738 :       edge e = stack.last ();
     738          738 :       stack.pop ();
     739              : 
     740              :       /* Get dest block of the edge.  */
     741          738 :       basic_block bb = e->dest;
     742              : 
     743              :       /* Execute only basic blocks of the m_crc_loop.  */
     744          738 :       if (!flow_bb_inside_loop_p (m_crc_loop, bb))
     745            0 :         continue;
     746              : 
     747              :       /* Execute statements.  */
     748          738 :       if (!execute_bb_statements (bb, e, stack))
     749              :         return false;
     750              :     }
     751              : 
     752          369 :   if (m_final_states.length () != 1)
     753              :     {
     754            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     755            0 :         fprintf (dump_file, "The number of states is not one when executed "
     756              :                             "the loop for calculating the polynomial.\n");
     757              :       return false;
     758              :     }
     759              :   return true;
     760          381 : }
     761              : 
     762              : /* Return true if all bits of the POLYNOMIAL are constants (0 or 1).
     763              :    Otherwise return false.  */
     764              : 
     765              : bool
     766          369 : polynomial_is_known (const value *polynomial)
     767              : {
     768        12001 :   for (size_t i = 0; i < polynomial->length (); i++)
     769              :     {
     770        11632 :       if (!is_a<bit *> ((*polynomial)[i]))
     771              :         return false;
     772              :     }
     773              :   return true;
     774              : }
     775              : 
     776              : /* Execute the loop, which is expected to calculate CRC,
     777              :    to extract polynomial, assigning real numbers to CRC and data.
     778              :    Returns a pair, first value of the pair is the tree containing
     779              :    the value of the polynomial, second is the calculated polynomial.
     780              :    The pair may contain nullptr.  */
     781              : 
     782              : std::pair <tree, value *>
     783          381 : crc_symbolic_execution::extract_polynomial (gphi *crc_phi, gphi *data_phi,
     784              :                                             tree calculated_crc,
     785              :                                             bool is_shift_left)
     786              : {
     787          381 :   if (!execute_crc_loop (crc_phi, data_phi, is_shift_left))
     788           12 :     return std::make_pair (nullptr, nullptr);
     789              : 
     790          369 :   if (m_final_states.length () != 1)
     791              :     {
     792            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     793            0 :         fprintf (dump_file, "The number of states isn't one "
     794              :                             "after executing the loop.\n");
     795            0 :       return std::make_pair (nullptr, nullptr);
     796              :     }
     797          369 :   state *polynomial_state = m_final_states.last ();
     798              : 
     799              :   /* CALCULATED_CRC contains the value of the polynomial
     800              :      after one iteration of the loop.  */
     801          369 :   if (dump_file && (dump_flags & TDF_DETAILS))
     802              :     {
     803          238 :       fprintf (dump_file, "Getting the value of ");
     804          238 :       print_generic_expr (dump_file, calculated_crc, dump_flags);
     805          238 :       fprintf (dump_file, " variable.\n");
     806              :     }
     807              : 
     808              :   /* Get the value (bit vector) of the tree (it may be the polynomial).  */
     809          369 :   value *polynomial = polynomial_state->get_value (calculated_crc);
     810          369 :   if (!polynomial)
     811              :     {
     812            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     813            0 :         fprintf (dump_file, "Polynomial's value is null.\n");
     814            0 :       return std::make_pair (nullptr, nullptr);
     815              :     }
     816              : 
     817          369 :   if (dump_file && (dump_flags & TDF_DETAILS))
     818              :     {
     819              :       /* Note: It may not be the real polynomial.
     820              :          If it's a bit reflected CRC,
     821              :          then to get a real polynomial,
     822              :          it must be reflected and 1 bit added.  */
     823          238 :       fprintf (dump_file, "Polynomial's value is ");
     824          238 :       state::print_value (polynomial);
     825              :     }
     826              : 
     827              :   /* Check that polynomial's all bits are constants.  */
     828          369 :   if (!polynomial_is_known (polynomial))
     829              :     {
     830            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
     831            0 :         fprintf (dump_file, "Polynomial's value is not constant.\n");
     832            0 :       return std::make_pair (nullptr, nullptr);
     833              :     }
     834              : 
     835          369 :   return std::make_pair (calculated_crc, polynomial);
     836              : }
     837              : 
     838              : 
     839              : /**************************** LFSR MATCHING *********************************/
     840              : 
     841              : 
     842              : /* Return true if CONST_BIT value equals to 1.
     843              :    Otherwise, return false.  */
     844              : 
     845              : bool
     846       104242 : is_one (value_bit *const_bit)
     847              : {
     848       104242 :   return is_a<bit *> (const_bit)
     849       104242 :          && (as_a<bit *> (const_bit))->get_val () == 1;
     850              : }
     851              : 
     852              : /* Return true if BIT is symbolic,
     853              :    its index is same as LFSR bit's index (LFSR_BIT_INDEX)
     854              :    and the origin is same as CRC_ORIGIN.  */
     855              : 
     856              : bool
     857       489950 : is_a_valid_symb (value_bit *bit, tree crc_origin, size_t lfsr_bit_index)
     858              : {
     859       489950 :   if (!is_a<symbolic_bit *> (bit))
     860              :     return false;
     861              : 
     862       489950 :   symbolic_bit *sym_bit = as_a<symbolic_bit *> (bit);
     863       489950 :   bool is_correct_index = (sym_bit->get_index () == lfsr_bit_index);
     864       489950 :   bool is_same_crc_origin = (sym_bit->get_origin () == crc_origin);
     865       489950 :   return is_correct_index && is_same_crc_origin;
     866              : }
     867              : 
     868              : /* Return true if the BIT is a valid crc[LFSR_BIT_INDEX] ^ 1,
     869              :    where i is a whole number and left part's origin is same as CRC_ORIGIN.
     870              :    LFSR_BIT_INDEX is the index of the LFSR bit from the same position as in CRC.
     871              : 
     872              :    If there is lfsr[8] at LFSR value vectors' 9-th bit,
     873              :    when in the CRC vectors' 9-th bit's value must be
     874              :    crc[8].
     875              : 
     876              :    Otherwise, return false.  */
     877              : 
     878              : bool
     879       104242 : is_a_valid_xor_one (value_bit *bit, tree crc_origin, size_t lfsr_bit_index)
     880              : {
     881       104242 :   if (is_a<bit_xor_expression *> (bit))
     882              :     {
     883       104242 :       bit_xor_expression *xor_exp = as_a<bit_xor_expression *> (bit);
     884       104242 :       if (is_one (xor_exp->get_right ()))
     885       104242 :         return is_a_valid_symb (xor_exp->get_left (), crc_origin,
     886       104242 :                                 lfsr_bit_index);
     887              :       return false;
     888              :     }
     889              :   return false;
     890              : }
     891              : 
     892              : /* Return true, if CONDITION_EXP checks CRC's MSB/LSB value
     893              :    (under which xor is/not done).
     894              :    Otherwise, return false.  */
     895              : 
     896              : bool
     897        11588 : may_be_xors_condition (tree crc_origin, value_bit *condition_exp,
     898              :                        size_t sb_index)
     899              : {
     900        11588 :   if (!crc_origin)
     901              :     return false;
     902              : 
     903        11588 :   if (!condition_exp)
     904              :     return false;
     905              : 
     906              :   /* The CONDITION_EXP of CRC may be a symbolic bit, if CRC is xor-ed with
     907              :      the data, and updated CRC's significant bit is checked.
     908              :      So, the CONDITION_EXP will be CRC's condition if it's origin is the same as
     909              :      CRC_ORIGIN, and it's index equals to checked significant bit's index.  */
     910        11588 :   if (is_a<symbolic_bit *> (condition_exp))
     911              :     {
     912         3554 :       symbolic_bit *condition_symbolic = as_a<symbolic_bit *> (condition_exp);
     913         3554 :       return crc_origin == condition_symbolic->get_origin ()
     914         3554 :              && sb_index == condition_symbolic->get_index ();
     915              :     }
     916              :     /* The CONDITION_EXP of CRC may be a bit_xor_expression,
     917              :        if CRC and data are xor-ed only for significant bit's check.
     918              :        I.e.  CONDITION_EXP in this case may be crc[]^data[].
     919              :        So, the CONDITION_EXP will be CRC's condition if it's left or right
     920              :        part's origin is the same as CRC_ORIGIN, and it's index equals to checked
     921              :        significant bit's index.  */
     922         8034 :   else if (is_a<bit_xor_expression *> (condition_exp))
     923              :     {
     924         8034 :       bit_xor_expression *condition_xor_exp = as_a<bit_xor_expression *>
     925         8034 :           (condition_exp);
     926         8034 :       if (!(is_a<symbolic_bit *> (condition_xor_exp->get_left ())
     927         8034 :             && is_a<symbolic_bit *> (condition_xor_exp->get_right ())))
     928              :         return false;
     929              : 
     930         8032 :       symbolic_bit *cond_left
     931         8032 :           = as_a<symbolic_bit *> (condition_xor_exp->get_left ());
     932         8032 :       symbolic_bit *cond_right
     933         8032 :           = as_a<symbolic_bit *> (condition_xor_exp->get_right ());
     934         8032 :       bool cond_left_is_crc = (crc_origin == cond_left->get_origin ()
     935         8032 :                                && sb_index == cond_left->get_index ());
     936         8032 :       bool cond_right_is_crc = (crc_origin == cond_right->get_origin ()
     937         8032 :                                 && sb_index == cond_right->get_index ());
     938         8032 :       return cond_left_is_crc || cond_right_is_crc;
     939              :     }
     940              :   return false;
     941              : }
     942              : 
     943              : /* Check whether the condition is checked for significant bit being 0 or 1.
     944              :    If IS_ONE is 1, when check whether the significant bit is 1 (xor branch),
     945              :    if 0, whether the significant bit is 0 (not xor branch).  */
     946              : 
     947              : bool
     948        11588 : is_crc_xor_condition (tree crc_origin, unsigned char is_one,
     949              :                       size_t sb_index, state *final_state)
     950              : {
     951              :   /* The CRC cases we detect must contain only one condition related to CRC.  */
     952        11588 :   if (final_state->get_conditions ().elements () != 1)
     953              :     return false;
     954              : 
     955        11588 :   auto condition_iter = final_state->get_conditions ().begin ();
     956        11588 :   if (!is_a<bit_condition *> (*condition_iter))
     957              :     return false;
     958              : 
     959              :   /* If the condition is for checking MSB/LSB, then
     960              :      if is_one is 1 and the condition is for checking MSB/LSB being one, or
     961              :      if is_one is 0 and condition is for checking MSB/LSB being 0
     962              :      return true, otherwise - false.  */
     963        11588 :   value_bit *cond_exp = (*condition_iter)->get_left ();
     964        11588 :   if (may_be_xors_condition (crc_origin, cond_exp, sb_index))
     965              :     {
     966        11586 :       if (!is_a<bit *> ((*condition_iter)->get_right ()))
     967              :         return false;
     968              : 
     969        11586 :       bit_condition *condition = as_a<bit_condition *> (*condition_iter);
     970        11586 :       unsigned char comparison_val
     971        11586 :           = as_a<bit *> ((*condition_iter)->get_right ())->get_val ();
     972        11586 :       if (condition->get_code () == EQ_EXPR)
     973         7921 :         return comparison_val == is_one;
     974         3665 :       if (condition->get_code () == NE_EXPR)
     975         3665 :         return comparison_val != is_one;
     976              :       return false;
     977              :     }
     978              :   return false;
     979              : }
     980              : 
     981              : /* Check whether LSB/MSB of LFSR and calculated (maybe)CRC match.
     982              :    If MSB is checked in the CRC loop, then here we check LSB, or vice versa.
     983              :    CHECKED_SB_VALUE indicates which state of CRC value is checked.
     984              :    If the CHECKED_SB_VALUE is 1 - then xor-ed CRC value is checked,
     985              :    otherwise, not xor-ed is checked.  */
     986              : 
     987              : bool
     988        11586 : given_sb_match (value_bit *crc, value_bit *lfsr,
     989              :                 unsigned short checked_sb_value)
     990              : {
     991              :   /* If LFSR's MSB/LSB value is a constant (0 or 1),
     992              :      then CRC's MSB/LSB must have the same value.  */
     993        11586 :   if (is_a<bit *> (lfsr))
     994              :     {
     995         3712 :       if (!((is_a<bit *> (crc)
     996         1856 :              && as_a<bit *> (crc)->get_val ()
     997         1856 :                 == as_a<bit *> (lfsr)->get_val ())))
     998            0 :         return false;
     999              :       return true;
    1000              :     }
    1001              :     /* If LFSR's MSB/LSB value is a symbolic_bit
    1002              :        (that means MSB/LSB of the polynomial is 1),
    1003              :        then CRC's MSB/LSB must be equal to CHECKED_SB_VALUE.  */
    1004         9730 :   else if (is_a<symbolic_bit *> (lfsr))
    1005              :     {
    1006         9730 :       if (!(is_a<bit *> (crc)
    1007         9730 :             && (as_a<bit *> (crc)->get_val () == checked_sb_value)))
    1008            0 :         return false;
    1009              :       return true;
    1010              :     }
    1011              :   return false;
    1012              : }
    1013              : 
    1014              : /* Check whether significant bit of LFSR and calculated (maybe)CRC match.  */
    1015              : 
    1016              : bool
    1017        11586 : sb_match (const value *lfsr, const value *crc_value, size_t sb_index,
    1018              :           size_t it_end, unsigned short value)
    1019              : {
    1020              :   /* If it's bit-forward CRC, check 0 bit's value.  */
    1021        11586 :   if (sb_index == it_end - 1)
    1022              :     {
    1023         5456 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1024         3984 :         fprintf (dump_file, "Checking 0 bit.\n");
    1025              : 
    1026         5456 :       if (!given_sb_match ((*crc_value)[0], (*lfsr)[0], value))
    1027              :         return false;
    1028              :     }
    1029              :     /* If it's bit-reversed CRC, check last bit's value.  */
    1030         6130 :   else if (sb_index == 0)
    1031              :     {
    1032         6130 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1033         4128 :         fprintf (dump_file, "Checking " HOST_SIZE_T_PRINT_UNSIGNED " bit.\n",
    1034              :                  (fmt_size_t) it_end);
    1035              : 
    1036         6130 :       if (!given_sb_match ((*crc_value)[it_end], (*lfsr)[it_end], value))
    1037              :         return false;
    1038              :     }
    1039              :   else
    1040              :     {
    1041            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1042            0 :         fprintf (dump_file, "Significant bit index is incorrect.\n");
    1043              :     }
    1044              :   return true;
    1045              : }
    1046              : 
    1047              : /* Match the CRC to the LFSR, where CRC's all bit values are
    1048              :    symbolic_bit or symbolic_bit ^ 1, besides MSB/LSB (it may be constant).  */
    1049              : 
    1050              : bool
    1051        11586 : lfsr_and_crc_bits_match (const value *lfsr, const value *crc_state,
    1052              :                          tree crc_origin, size_t i, size_t it_end,
    1053              :                          size_t sb_index, unsigned short checked_sb_value)
    1054              : {
    1055              : 
    1056              :   /* Check whether significant bits of LFSR and CRC match.  */
    1057        11586 :   if (!sb_match (lfsr, crc_state, sb_index, it_end, checked_sb_value))
    1058              :     return false;
    1059              : 
    1060       501536 :   for (; i < it_end; i++)
    1061              :     {
    1062       489950 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1063       348624 :         fprintf (dump_file, "Checking " HOST_SIZE_T_PRINT_UNSIGNED " bit.\n",
    1064              :                  (fmt_size_t) i);
    1065              : 
    1066              :       /* Check the case when in lfsr we have LFSR (i)^LFSR (SBi),
    1067              :          where 0<i<LFSR_size and SBi is the index of MSB/LSB (LFSR_size-1/0).
    1068              :          In that case in crc_state (resulting CRC)
    1069              :          we must have crc (i) ^ 1 case, when condition is true
    1070              :          and crc (i) when condition is false,
    1071              :          (as CRC is xor-ed with the polynomial only if the LSB/MSB is one)
    1072              :          where k is a whole number.  */
    1073       489950 :       if (is_a<bit_xor_expression *> ((*lfsr)[i]))
    1074              :         {
    1075       208484 :           size_t index = (as_a<bit_xor_expression *> ((*lfsr)[i]))->get_left ()
    1076       208484 :               ->get_index ();
    1077              :           /* Check CRC value of xor branch.  */
    1078       208484 :           if (checked_sb_value == 1)
    1079              :             {
    1080       104242 :               if (!(is_a_valid_xor_one ((*crc_state)[i], crc_origin, index)))
    1081              :                 return false;
    1082              :             }
    1083              :           else /* Check CRC value of not xor branch.  */
    1084              :             {
    1085       104242 :               if (!(is_a_valid_symb ((*crc_state)[i], crc_origin, index)))
    1086              :                 return false;
    1087              :             }
    1088              :         }
    1089              :         /* Check the case when in LFSR we have LFSR (i), where 0<i<LFSR_size.
    1090              :            In that case in resulting CRC we must have crc (i) case,
    1091              :            when condition is true or condition is false.
    1092              :            If we have just LFSR (i), that means polynomial's i ± 1 bit is 0,
    1093              :            so despite CRC is xor-ed or not, we will have crc (i).  */
    1094       281466 :       else if (is_a<symbolic_bit *> ((*lfsr)[i]))
    1095              :         {
    1096       281466 :           size_t index = (as_a<symbolic_bit *> ((*lfsr)[i]))->get_index ();
    1097       281466 :           if (!(is_a_valid_symb ((*crc_state)[i], crc_origin, index)))
    1098              :             return false;
    1099              :         }
    1100              :       else
    1101              :         {
    1102            0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1103            0 :             fprintf (dump_file, "Not expected expression in LFSR.\n");
    1104              :           return false;
    1105              :         }
    1106              :     }
    1107              :   return true;
    1108              : }
    1109              : 
    1110              : /* Return origin of CRC_BIT.
    1111              :    The first tree in loop, from which CRC's calculation is started.  */
    1112              : 
    1113              : tree
    1114        15151 : get_origin_of_crc_from_symb_bit (value_bit *crc_bit)
    1115              : {
    1116        15151 :   if (is_a<symbolic_bit *> (crc_bit))
    1117        11588 :     return as_a<symbolic_bit *> (crc_bit)->get_origin ();
    1118              :   return nullptr;
    1119              : }
    1120              : 
    1121              : /* Return origin of CRC_BIT.  The first tree in loop, from which CRC's
    1122              :    calculation is started.  If the CRC_BIT is symbolic value, return its origin,
    1123              :    otherwise return its left part's origin (right must be 1 if its CRC's
    1124              :    value). */
    1125              : 
    1126              : tree
    1127        11588 : get_origin_of_crc (value_bit *crc_bit)
    1128              : {
    1129        11588 :   tree origin = get_origin_of_crc_from_symb_bit (crc_bit);
    1130        11588 :   if (origin)
    1131              :     return origin;
    1132         3563 :   else if (is_a<bit_xor_expression *> (crc_bit))
    1133              :     {
    1134         3563 :       value_bit *crc_bit_left
    1135         3563 :           = as_a<bit_xor_expression *> (crc_bit)->get_left ();
    1136         3563 :       return get_origin_of_crc_from_symb_bit (crc_bit_left);
    1137              :     }
    1138              :   return nullptr;
    1139              : }
    1140              : 
    1141              : /* Determine and initialize significant bit index
    1142              :    (if MSB is checked for CRC, then it's LSB index, and vice versa)
    1143              :    and the remaining part's begin and end.
    1144              :    SB_INDEX is the significant bit index.
    1145              :    IT_BEG is the beginning of the remaining part.
    1146              :    IT_END is the end of the remaining part.  */
    1147              : 
    1148              : void
    1149         5795 : init_sb_index_and_other_part_begin_end (size_t &it_beg, size_t &it_end,
    1150              :                                         size_t &sb_index, size_t crc_size,
    1151              :                                         bool is_bit_forward)
    1152              : {
    1153         5795 :   it_end = crc_size;
    1154         5795 :   if (is_bit_forward)
    1155              :     {
    1156         2728 :       sb_index = it_end - 1;
    1157         2728 :       it_beg = 1;
    1158              :     }
    1159              :   else
    1160              :     {
    1161         3067 :       it_beg = 0;
    1162         3067 :       sb_index = 0;
    1163         3067 :       --it_end;
    1164              :     }
    1165         5795 : }
    1166              : 
    1167              : /* Return true if CRC_STATE matches the LFSR, otherwise - false.
    1168              :    LFSR - is created LFSR value for the given polynomial and CRC size.
    1169              :    CRC_STATE - contains CRC's calculated value and execution path condition.
    1170              :    IT_BEG and IT_END - are the border indexes of the value to be matched.
    1171              :    SB_INDEX - is the significant bit index of the CRC value,
    1172              :               which will be checked separately.
    1173              :               IF MSB is checked for CRC, when sb_index will be the index of LSB.
    1174              :               Otherwise, will be the index of MSB.
    1175              :    CHECKED_SB_VALUE - is the significant bit's value (used for CRC's condition).
    1176              :               If CHECKED_SB_VALUE is 1, it indicates that CRC_STATE is
    1177              :               xor-ed path's state.
    1178              :               If CHECKED_SB_VALUE is 0, then CRC_STATE is the state of the
    1179              :               not xor branch.  */
    1180              : 
    1181              : bool
    1182        11588 : lfsr_matches_crc_state (const value *lfsr, state *crc_state, value *crc_value,
    1183              :                         size_t it_beg, size_t it_end, size_t sb_index,
    1184              :                         unsigned short checked_sb_value)
    1185              : {
    1186        11588 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1187              :     {
    1188         8112 :       fprintf (dump_file, "Starting to match the following CRC value: ");
    1189         8112 :       state::print_value (crc_value);
    1190              :     }
    1191              : 
    1192              :   /* Get the origin (name) of the calculated CRC value.
    1193              :      All bits must have the same origin.  */
    1194        11588 :   tree crc_origin = get_origin_of_crc ((*crc_value)[it_beg]);
    1195        11588 :   if (!crc_origin)
    1196              :     return false;
    1197              : 
    1198        11588 :   if (!is_crc_xor_condition (crc_origin, checked_sb_value, sb_index, crc_state))
    1199              :     return false;
    1200              : 
    1201              :   /* Check whether CRC_VALUE and LFSR bits match.  */
    1202        11586 :   return lfsr_and_crc_bits_match (lfsr, crc_value, crc_origin,
    1203        11586 :                                   it_beg, it_end, sb_index, checked_sb_value);
    1204              : }
    1205              : 
    1206              : /* Return true if in the CRC_VALUE exists xor expression.
    1207              :    Otherwise, return false.  */
    1208              : 
    1209              : bool
    1210         5795 : is_xor_state (value *crc_value, size_t it_beg, size_t it_end)
    1211              : {
    1212        14707 :    for (unsigned j = it_beg; j < it_end; ++j)
    1213        14707 :      if ((*crc_value)[j]->get_type () == BIT_XOR_EXPRESSION)
    1214              :        return true;
    1215              :    return false;
    1216              : }
    1217              : 
    1218              : /* Keep the value of calculated CRC.  */
    1219              : 
    1220              : value *
    1221        11590 : get_crc_val (tree calculated_crc, state *curr_state)
    1222              : {
    1223        11590 :   if (!calculated_crc)
    1224              :     {
    1225            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1226            0 :         fprintf (dump_file, "Couldn't get the potential CRC variable.\n");
    1227              :       return nullptr;
    1228              :     }
    1229              : 
    1230              :   /* When the calculated CRC is constant, it's not possible to determine
    1231              :      whether the CRC has been calculated.  */
    1232        11590 :   if (TREE_CODE (calculated_crc) == INTEGER_CST)
    1233              :     {
    1234            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1235            0 :         fprintf (dump_file, "Calculated CRC is a constant.\n");
    1236              :       return nullptr;
    1237              :     }
    1238              : 
    1239              :   /* Get calculated return value.  */
    1240        11590 :   value * crc_value = curr_state->get_value (calculated_crc);
    1241              : 
    1242        11590 :   if (!crc_value)
    1243              :     {
    1244            0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1245            0 :         fprintf (dump_file, "CRC is not in the state.\n");
    1246              :       return nullptr;
    1247              :     }
    1248              :   return crc_value;
    1249              : }
    1250              : 
    1251              : /* Return true if all states from the FINAL_STATES match the LFSR,
    1252              :    otherwise - false.  */
    1253              : 
    1254              : bool
    1255         5798 : all_states_match_lfsr (value *lfsr, bool is_bit_forward, tree calculated_crc,
    1256              :                        const vec<state *> &final_states)
    1257              : {
    1258         5798 :   if (final_states.length () != 2)
    1259              :     {
    1260            3 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1261            3 :         fprintf (dump_file, "The final states count isn't two.\n");
    1262              :       return false;
    1263              :     }
    1264              : 
    1265         5795 :   value *crc_xor_value = get_crc_val (calculated_crc, final_states[0]);
    1266         5795 :   value *crc_not_xor_value = get_crc_val (calculated_crc, final_states[1]);
    1267              : 
    1268              :   /* LFSR's size must be equal to CRC's size.  */
    1269         5795 :   if ((crc_xor_value->length () != lfsr->length ())
    1270         5795 :       || (crc_not_xor_value->length () != lfsr->length ()))
    1271              :     return false;
    1272              : 
    1273              :   /* Depending on whether it is bit-forward or reversed CRC,
    1274              :      determine in which significant bit new value is added,
    1275              :      to examine that bit separately.
    1276              :      If in the CRC algorithm MSB (sb_index) is checked to be one for xor,
    1277              :      then here we check LSB separately (marginal bit).
    1278              :      If LSB (sb_index) is checked, then we separate MSB (marginal bit).  */
    1279         5795 :   size_t it_beg, it_end, sb_index;
    1280         5795 :   init_sb_index_and_other_part_begin_end (it_beg, it_end, sb_index,
    1281         5795 :                                           crc_xor_value->length (),
    1282              :                                           is_bit_forward);
    1283              : 
    1284         5795 :     size_t xor_st_index = 0, not_xor_st_index = 1;
    1285              :   /* If first is not xor's state,
    1286              :      then the second state is assumed to be xor's state.  */
    1287         5795 :   if (!is_xor_state (crc_xor_value, it_beg, it_end))
    1288              :     {
    1289            0 :       std::swap (crc_xor_value, crc_not_xor_value);
    1290            0 :       xor_st_index = 1;
    1291            0 :       not_xor_st_index = 0;
    1292              :     }
    1293              : 
    1294              :   /*  If xor-ed CRC value doesn't match the LFSR value, return false.  */
    1295         5795 :   if (!lfsr_matches_crc_state (lfsr, final_states[xor_st_index], crc_xor_value,
    1296              :                                it_beg, it_end, sb_index, 1))
    1297              :     return false;
    1298              : 
    1299              :   /*  If not xor-ed CRC value doesn't match the LFSR value, return false.  */
    1300         5793 :   if (!lfsr_matches_crc_state (lfsr, final_states[not_xor_st_index],
    1301              :                                crc_not_xor_value, it_beg, it_end, sb_index, 0))
    1302              :     return false;
    1303              : 
    1304              :   return true;
    1305              : }
        

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.