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