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