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