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

source code of gcc/gimple-crc-optimization.cc