Branch data Line data Source code
1 : : /* CRC optimization.
2 : : Copyright (C) 2022-2025 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 : 214519 : crc_optimization () : m_visited_stmts (BITMAP_ALLOC (NULL)),
235 : 214519 : m_crc_loop (nullptr), m_polynomial (0)
236 : : {
237 : 214519 : set_initial_values ();
238 : 214519 : }
239 : 214519 : ~crc_optimization ()
240 : : {
241 : 214519 : 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 : 288 : crc_optimization::dump_crc_information ()
250 : : {
251 : 288 : if (dump_file)
252 : : {
253 : 239 : fprintf (dump_file,
254 : : "Loop iteration number is " HOST_WIDE_INT_PRINT_UNSIGNED ".\n",
255 : 239 : tree_to_uhwi (m_crc_loop->nb_iterations));
256 : 239 : if (m_is_bit_forward)
257 : 115 : fprintf (dump_file, "Bit forward.\n");
258 : : else
259 : 124 : fprintf (dump_file, "Bit reversed.\n");
260 : : }
261 : 288 : }
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 : 15 : 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 : 39 : 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 : : }
314 : : return nullptr;
315 : : }
316 : :
317 : : /* Returns opposite block of the XOR_BB from PRED_BB's dest blocks. */
318 : :
319 : : basic_block
320 : 38 : 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 : 38 : if (EDGE_COUNT (pred_bb->succs) != 2)
324 : : return nullptr;
325 : :
326 : 38 : edge e0 = EDGE_SUCC (pred_bb, 0);
327 : 38 : edge e1 = EDGE_SUCC (pred_bb, 1);
328 : :
329 : : /* Ensure neither outgoing edge is marked as complex. */
330 : 38 : if ((e0->flags & EDGE_COMPLEX)
331 : 38 : || (e1->flags & EDGE_COMPLEX))
332 : : return nullptr;
333 : :
334 : : /* Check that one of the successors is indeed XOR_BB. */
335 : 38 : gcc_assert ((e0->dest == xor_bb)
336 : : || (e1->dest == xor_bb));
337 : :
338 : : /* Return the opposite block of XOR_BB. */
339 : 38 : if (EDGE_SUCC (pred_bb, 0)->dest != xor_bb)
340 : : return e0->dest;
341 : 38 : 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 : 38 : crc_optimization::exists_shift_for_opp_xor_shift (basic_block opposite_bb)
351 : : {
352 : 38 : if (!opposite_bb)
353 : : return false;
354 : :
355 : : /* Walk through the instructions of given basic block. */
356 : 38 : for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (opposite_bb);
357 : 39 : !gsi_end_p (bsi); gsi_next_nondebug (&bsi))
358 : : {
359 : 37 : 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 : 37 : if (is_gimple_assign (stmt))
364 : : {
365 : 37 : if ((gimple_assign_rhs_code (stmt)
366 : 37 : == gimple_assign_rhs_code (m_shift_stmt))
367 : 37 : && integer_onep (gimple_assign_rhs2 (stmt)))
368 : 36 : 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 : 293 : crc_optimization::cond_true_is_checked_for_bit_one (const gcond *cond)
380 : : {
381 : 293 : if (!cond)
382 : : return false;
383 : :
384 : 293 : tree rhs = gimple_cond_rhs (cond);
385 : 293 : enum tree_code code = gimple_cond_code (cond);
386 : :
387 : : /* If the condition is something == 1 -> return true. */
388 : 293 : if (code == EQ_EXPR && integer_onep (rhs))
389 : : return true;
390 : :
391 : : /* If the condition is something != 0 or something < 0 -> return true. */
392 : 291 : if ((code == NE_EXPR || code == LT_EXPR)
393 : 291 : && 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 : 293 : crc_optimization::is_crc_satisfiable_cond (basic_block pred_bb,
411 : : basic_block xor_bb,
412 : : gcond *cond)
413 : : {
414 : 293 : edge true_edge;
415 : 293 : edge false_edge;
416 : 293 : extract_true_false_edges_from_block (pred_bb, &true_edge, &false_edge);
417 : 293 : 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 : 293 : if (cond_is_checked_for_bit_one && true_edge->dest == xor_bb)
420 : : {
421 : 292 : if (dump_file && (dump_flags & TDF_DETAILS))
422 : 230 : 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 : 293 : crc_optimization::is_crc_checked (gcond *cond)
445 : : {
446 : 293 : tree lhs = gimple_cond_lhs (cond);
447 : :
448 : : /* As conditions are in canonical form, only left part must be an
449 : : SSA_NAME. */
450 : 293 : 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 : 293 : auto_vec<gimple *> cond_dep_stmts (m_crc_loop->num_nodes);
456 : 293 : bool set_defs_succeeded = set_defs (lhs, cond_dep_stmts, true);
457 : 293 : bitmap_clear (m_visited_stmts);
458 : 293 : if (!set_defs_succeeded)
459 : : return false;
460 : 290 : return cond_depends_on_crc (cond_dep_stmts);
461 : 293 : }
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 : 293 : 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 : 586 : gcond *cond = safe_dyn_cast<gcond *> (gsi_stmt (gsi_last_bb (pred_bb)));
482 : 293 : 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 : 293 : 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 : 293 : 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 : 981 : crc_optimization::is_acceptable_stmt_code (const tree_code &stmt_code)
509 : : {
510 : 981 : return (stmt_code == BIT_IOR_EXPR)
511 : 981 : || (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 : 285 : || (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 : 318 : crc_optimization::can_be_crc_shift (gimple *assign_stmt)
524 : : {
525 : 318 : tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
526 : 318 : if (stmt_code == LSHIFT_EXPR || stmt_code == RSHIFT_EXPR)
527 : : {
528 : 300 : m_is_bit_forward = (stmt_code == LSHIFT_EXPR);
529 : : /* Check that shift one is done, keep shift statement. */
530 : 300 : if (integer_onep (gimple_assign_rhs2 (assign_stmt)))
531 : : {
532 : 295 : 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 : 295 : if (dump_file && (dump_flags & TDF_DETAILS))
540 : 231 : fprintf (dump_file,
541 : : "Found <<1 or >>1.\n");
542 : 295 : 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 : 981 : crc_optimization::can_not_be_crc_stmt (gimple *assign_stmt)
555 : : {
556 : 981 : tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
557 : 981 : 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 : 2542 : crc_optimization::passes_checks_for_def_chain (tree variable)
575 : : {
576 : 2542 : if (!(variable && TREE_CODE (variable) == SSA_NAME))
577 : : return false;
578 : :
579 : : /* No definition chain for default defs. */
580 : 1730 : if (SSA_NAME_IS_DEFAULT_DEF (variable))
581 : : return false;
582 : :
583 : 1730 : gimple *stmt = SSA_NAME_DEF_STMT (variable);
584 : :
585 : 1730 : if (!stmt)
586 : : return false;
587 : :
588 : : /* Don't go outside the loop. */
589 : 1730 : 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 : 2542 : crc_optimization::set_defs (tree name, auto_vec<gimple *> &use_defs,
603 : : bool keep_only_header_phis = false)
604 : : {
605 : 2542 : if (!passes_checks_for_def_chain (name))
606 : : return true;
607 : :
608 : : /* Don't consider already visited names. */
609 : 1725 : unsigned v = SSA_NAME_VERSION (name);
610 : 1725 : if (bitmap_bit_p (m_visited_stmts, v))
611 : : return true;
612 : 1723 : 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 : 1723 : if (use_defs.length () > 12)
619 : : return false;
620 : :
621 : 1723 : 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 : 1723 : if (!keep_only_header_phis)
626 : 686 : 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 : 1723 : if (is_a<gassign *> (stmt))
631 : : {
632 : 981 : if (can_not_be_crc_stmt (stmt))
633 : : return false;
634 : :
635 : 977 : tree ssa1 = gimple_assign_rhs1 (stmt);
636 : 977 : tree ssa2 = gimple_assign_rhs2 (stmt);
637 : 977 : if (!set_defs (ssa1, use_defs, keep_only_header_phis))
638 : : return false;
639 : 965 : 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 : 742 : else if (is_a<gphi *> (stmt))
647 : : {
648 : 737 : if (bb_loop_header_p (gimple_bb (stmt)))
649 : : {
650 : : /* If it's specified to keep only header phi's, keep it. */
651 : 737 : if (keep_only_header_phis)
652 : 429 : 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 : 737 : 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 : 301 : crc_optimization::find_shift_before_xor (const auto_vec<gimple *> &stmts)
677 : : {
678 : 985 : 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 : 327 : if (is_a<gassign *> (*stmt_it))
682 : : {
683 : 308 : if (can_be_crc_shift (*stmt_it))
684 : 286 : 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 : 301 : crc_optimization::set_crc_and_data_phi (auto_vec<gimple *> &stmts)
700 : : {
701 : 2243 : for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
702 : : {
703 : 670 : if (is_a<gphi *> (*stmt_it) && bb_loop_header_p (gimple_bb (*stmt_it)))
704 : : {
705 : 308 : if (!m_phi_for_crc)
706 : 301 : 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 : 301 : 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 : 290 : crc_optimization::cond_depends_on_crc (auto_vec<gimple *>& stmts)
726 : : {
727 : 290 : bool con_depends_on_crc = false;
728 : :
729 : : /* The condition may depend maximum on data and CRC phi's. */
730 : 290 : if (stmts.length () > 2)
731 : : return false;
732 : :
733 : 1720 : for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
734 : : {
735 : 429 : 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 : 429 : if (m_phi_for_crc == (*stmt_it))
741 : : con_depends_on_crc = true;
742 : 141 : 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 : 137 : else if (!m_phi_for_data)
747 : 137 : 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 : 215034 : crc_optimization::set_initial_values ()
758 : : {
759 : 215034 : m_crc_arg = nullptr;
760 : 215034 : m_data_arg = nullptr;
761 : 215034 : m_shift_stmt = nullptr;
762 : 215034 : m_phi_for_crc = nullptr;
763 : 215034 : m_phi_for_data = nullptr;
764 : 215034 : m_is_bit_forward = false;
765 : 215034 : }
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 : 515 : crc_optimization::xor_calculates_crc (function *crc_fun,
779 : : const gimple *xor_stmt)
780 : : {
781 : 515 : tree crc_var = gimple_assign_lhs (xor_stmt);
782 : 515 : set_initial_values ();
783 : 515 : tree ssa1 = gimple_assign_rhs1 (xor_stmt);
784 : 515 : tree ssa2 = gimple_assign_rhs2 (xor_stmt);
785 : 515 : if (TREE_CODE (ssa2) != INTEGER_CST)
786 : : {
787 : 208 : if (dump_file && (dump_flags & TDF_DETAILS))
788 : 142 : fprintf (dump_file, "Second operand of the "
789 : : "xor statement isn't an integer constant.\n");
790 : 208 : return false;
791 : : }
792 : :
793 : : /* Get the statements within the loop on which xor-ed variable depends. */
794 : 307 : auto_vec<gimple *> xor_dep_stmts (m_crc_loop->num_nodes);
795 : 307 : bool set_defs_succeeded = set_defs (ssa1, xor_dep_stmts);
796 : 307 : bitmap_clear (m_visited_stmts);
797 : 307 : if (!set_defs_succeeded)
798 : : {
799 : 6 : xor_dep_stmts.release ();
800 : 6 : return false;
801 : : }
802 : :
803 : 301 : m_shift_stmt = find_shift_before_xor (xor_dep_stmts);
804 : :
805 : 301 : 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 : 301 : 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 : 295 : basic_block xor_bb = gimple_bb (xor_stmt);
826 : :
827 : : /* Get the predecessor basic block of xor's block. */
828 : 314 : if (!single_pred_p (xor_bb))
829 : : return false;
830 : 295 : 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 : 295 : if (m_shift_stmt && gimple_bb (m_shift_stmt) == xor_bb)
837 : : {
838 : 38 : basic_block opposite_block = get_xor_bb_opposite (block_of_condition,
839 : : xor_bb);
840 : 38 : 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 : 293 : if (crc_cond (block_of_condition, xor_bb))
852 : : {
853 : 288 : if (dump_file)
854 : 239 : fprintf (dump_file,
855 : : "\n%s function maybe contains CRC calculation.\n",
856 : : function_name (crc_fun));
857 : 288 : return true;
858 : : }
859 : :
860 : : return false;
861 : 307 : }
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 : 17536 : crc_optimization::loop_contains_two_conditional_bb (basic_block *loop_bbs,
870 : : unsigned loop_num_nodes)
871 : : {
872 : 17536 : unsigned conditional_bb_count = 0;
873 : : /* Iterate through the loop until the conditional branches count
874 : : is below 3. */
875 : 68075 : for (unsigned i = 0; i < loop_num_nodes && conditional_bb_count <= 2; i++)
876 : : {
877 : 50539 : basic_block bb = loop_bbs[i];
878 : 50539 : if (!single_succ_p (bb))
879 : 23597 : conditional_bb_count++;
880 : : }
881 : 17536 : 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 : 476660 : 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 : 476660 : number_of_latch_executions (func_loop);
893 : 476660 : tree n_inters = func_loop->nb_iterations;
894 : 476660 : if (n_inters == NULL_TREE || n_inters == chrec_dont_know)
895 : : {
896 : 246104 : if (dump_file && (dump_flags & TDF_DETAILS))
897 : 41 : fprintf (dump_file,
898 : : "Loop iteration number is chrec_dont_know.\n");
899 : 246104 : return false;
900 : :
901 : : }
902 : 230556 : else if (tree_fits_uhwi_p (n_inters))
903 : : {
904 : 148186 : unsigned HOST_WIDE_INT
905 : 148186 : loop_iteration_number = tree_to_uhwi (n_inters);
906 : 148186 : if (dump_file && (dump_flags & TDF_DETAILS))
907 : 266 : fprintf (dump_file, "Loop iteration number is "
908 : : HOST_WIDE_INT_PRINT_UNSIGNED ".\n", loop_iteration_number);
909 : :
910 : 148186 : 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 : 213020 : 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 : 476660 : crc_optimization::loop_may_calculate_crc (class loop *loop)
931 : : {
932 : : /* Only examine innermost loops. */
933 : 476660 : if (!loop || loop->inner)
934 : : return false;
935 : :
936 : 476660 : if (!satisfies_crc_loop_iteration_count (loop))
937 : : return false;
938 : :
939 : 17536 : m_crc_loop = loop;
940 : 17536 : 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 : 17536 : if (!loop_contains_two_conditional_bb (loop_bbs, m_crc_loop->num_nodes))
945 : : {
946 : 13297 : 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 : 13297 : free (loop_bbs);
951 : 13297 : return false;
952 : : }
953 : :
954 : : unsigned short checked_xor_count = 0;
955 : : /* Walk bbs of the loop. */
956 : 24152 : for (unsigned int i = 0; i < m_crc_loop->num_nodes; i++)
957 : : {
958 : 20218 : basic_block bb = loop_bbs[i];
959 : : /* Walk instructions of the bb. */
960 : 20218 : for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (bb);
961 : 65919 : !gsi_end_p (bsi); gsi_next_nondebug (&bsi))
962 : : {
963 : 46006 : gimple *stmt = gsi_stmt (bsi);
964 : : /* If there is an xor instruction,
965 : : check that it is calculating CRC. */
966 : 46006 : if (is_gimple_assign (stmt)
967 : 46006 : && gimple_assign_rhs_code (stmt) == BIT_XOR_EXPR)
968 : : {
969 : 515 : if (dump_file && (dump_flags & TDF_DETAILS))
970 : 373 : fprintf (dump_file,
971 : : "Found xor, "
972 : : "checking whether it is for CRC calculation.\n");
973 : :
974 : 515 : if (xor_calculates_crc (cfun, stmt))
975 : : {
976 : 288 : dump_crc_information ();
977 : 288 : free (loop_bbs);
978 : 305 : return true;
979 : : }
980 : :
981 : 227 : if (++checked_xor_count == 2)
982 : : {
983 : 17 : free (loop_bbs);
984 : 17 : return false;
985 : : }
986 : : }
987 : : }
988 : : }
989 : 3934 : free (loop_bbs);
990 : 3934 : 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 : 247 : crc_optimization::loop_calculates_crc (gphi *output_crc,
1002 : : std::pair<tree, value *> calc_polynom)
1003 : : {
1004 : : /* Create LFSR state using extracted polynomial. */
1005 : 494 : value * lfsr = state::create_lfsr (calc_polynom.first, calc_polynom.second,
1006 : 247 : m_is_bit_forward);
1007 : 247 : 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 : 227 : if (dump_file && (dump_flags & TDF_DETAILS))
1015 : : {
1016 : 177 : fprintf (dump_file, "\nLFSR value is \n");
1017 : 177 : 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 : 227 : bool is_crc = true;
1024 : 227 : crc_symbolic_execution loop_executor (m_crc_loop, output_crc);
1025 : 3503 : while (!loop_executor.is_last_iteration ())
1026 : : {
1027 : 3053 : 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 : 3053 : tree calculated_crc = PHI_ARG_DEF_FROM_EDGE (output_crc,
1038 : : single_exit (m_crc_loop));
1039 : 3053 : if (!all_states_match_lfsr (lfsr, m_is_bit_forward, calculated_crc,
1040 : : loop_executor.get_final_states ()))
1041 : : {
1042 : 4 : if (dump_file && (dump_flags & TDF_DETAILS))
1043 : 2 : fprintf (dump_file, "Returned state and LFSR differ.\n");
1044 : : is_crc = false;
1045 : : break;
1046 : : }
1047 : : }
1048 : 227 : delete lfsr;
1049 : 227 : return is_crc;
1050 : 227 : }
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 : 270 : crc_optimization::is_output_crc (gphi *output_crc)
1057 : : {
1058 : 270 : tree crc_of_exit
1059 : 270 : = PHI_ARG_DEF_FROM_EDGE (output_crc, single_exit (m_crc_loop));
1060 : 270 : tree crc_of_latch
1061 : 270 : = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, loop_latch_edge (m_crc_loop));
1062 : 270 : if (crc_of_exit == crc_of_latch)
1063 : : {
1064 : 267 : if (dump_file && (dump_flags & TDF_DETAILS))
1065 : : {
1066 : 211 : fprintf (dump_file, "Output CRC is ");
1067 : 211 : print_gimple_expr (dump_file, (gimple *) output_crc, dump_flags);
1068 : 211 : fprintf (dump_file, "\n");
1069 : : }
1070 : 267 : 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 : 270 : crc_optimization::swap_crc_and_data_if_needed (gphi *output_crc)
1085 : : {
1086 : 270 : tree crc_of_exit
1087 : 270 : = PHI_ARG_DEF_FROM_EDGE (output_crc, single_exit (m_crc_loop));
1088 : 270 : edge crc_loop_latch = loop_latch_edge (m_crc_loop);
1089 : 270 : 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 : 270 : }
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 : 267 : bool crc_optimization::validate_crc_and_data ()
1111 : : {
1112 : : /* Set m_crc_arg and check if fits in word_mode. */
1113 : 267 : gcc_assert (m_phi_for_crc);
1114 : 267 : m_crc_arg = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc,
1115 : : loop_preheader_edge (m_crc_loop));
1116 : 267 : gcc_assert (m_crc_arg);
1117 : :
1118 : 267 : unsigned HOST_WIDE_INT
1119 : 267 : 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 : 267 : 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 : 267 : if (m_phi_for_data)
1128 : : {
1129 : 124 : if (dump_file && (dump_flags & TDF_DETAILS))
1130 : 120 : fprintf (dump_file,
1131 : : "Data and CRC are xor-ed in the for loop. Initializing data "
1132 : : "with its value.\n");
1133 : 124 : m_data_arg = PHI_ARG_DEF_FROM_EDGE (m_phi_for_data,
1134 : : loop_preheader_edge (m_crc_loop));
1135 : 124 : gcc_assert (m_data_arg);
1136 : 124 : 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 : 247 : crc_optimization::construct_constant_polynomial (value *polynomial)
1152 : : {
1153 : 247 : m_polynomial = 0;
1154 : 6551 : for (unsigned i = 0; i < (*polynomial).length (); i++)
1155 : : {
1156 : 6304 : value_bit *const_bit;
1157 : 6304 : if (m_is_bit_forward)
1158 : 2888 : const_bit = (*polynomial)[(*polynomial).length () - 1 - i];
1159 : : else
1160 : 3416 : const_bit = (*polynomial)[i];
1161 : 6304 : m_polynomial <<= 1;
1162 : 10664 : m_polynomial ^= (as_a<bit *> (const_bit))->get_val () ? 1 : 0;
1163 : : }
1164 : 247 : }
1165 : :
1166 : : /* Returns phi statement which may hold the calculated CRC. */
1167 : :
1168 : : gphi *
1169 : 288 : crc_optimization::get_output_phi ()
1170 : : {
1171 : 288 : edge loop_exit = single_exit (m_crc_loop);
1172 : 288 : 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 : 288 : basic_block bb = loop_exit->dest;
1179 : 288 : gphi *output_crc = nullptr;
1180 : 288 : 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 : 601 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1187 : 313 : gsi_next (&gsi))
1188 : : {
1189 : 331 : tree phi_result = gimple_phi_result (gsi.phi ());
1190 : :
1191 : : /* Don't consider virtual operands. */
1192 : 662 : if (!virtual_operand_p (phi_result))
1193 : : {
1194 : 306 : if (phi_count < 1)
1195 : : {
1196 : : output_crc = gsi.phi ();
1197 : : phi_count++;
1198 : : }
1199 : : else
1200 : : {
1201 : 18 : if (dump_file && (dump_flags & TDF_DETAILS))
1202 : 17 : fprintf (dump_file, "There is more than one output phi.\n");
1203 : 18 : return nullptr;
1204 : : }
1205 : : }
1206 : : }
1207 : :
1208 : 270 : if (output_crc)
1209 : : {
1210 : 270 : 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 : 223 : crc_optimization::optimize_crc_loop (gphi *output_crc)
1225 : : {
1226 : 223 : 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 : 223 : if (!m_data_arg)
1234 : : {
1235 : 127 : if (dump_file && (dump_flags & TDF_DETAILS))
1236 : 79 : 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 : 127 : unsigned HOST_WIDE_INT
1242 : 127 : data_size = tree_to_uhwi (m_crc_loop->nb_iterations) + 1;
1243 : 127 : 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 : 127 : m_data_arg = build_int_cstu (type, 0);
1247 : : }
1248 : :
1249 : : /* Build tree node for the polynomial from its constant value. */
1250 : 223 : tree polynomial_arg = build_int_cstu (TREE_TYPE (m_crc_arg), m_polynomial);
1251 : 223 : gcc_assert (polynomial_arg);
1252 : :
1253 : 223 : internal_fn ifn;
1254 : 223 : if (m_is_bit_forward)
1255 : : ifn = IFN_CRC;
1256 : : else
1257 : 109 : ifn = IFN_CRC_REV;
1258 : :
1259 : 223 : tree phi_result = gimple_phi_result (output_crc);
1260 : 223 : location_t loc;
1261 : 223 : loc = EXPR_LOCATION (phi_result);
1262 : :
1263 : : /* Add IFN call and write the return value in the phi_result. */
1264 : 223 : gcall *call
1265 : 223 : = gimple_build_call_internal (ifn, 3,
1266 : : m_crc_arg,
1267 : : m_data_arg,
1268 : : polynomial_arg);
1269 : :
1270 : 223 : gimple_call_set_lhs (call, phi_result);
1271 : 223 : gimple_set_location (call, loc);
1272 : 223 : gimple_stmt_iterator si = gsi_start_bb (output_crc->bb);
1273 : 223 : gsi_insert_before (&si, call, GSI_SAME_STMT);
1274 : :
1275 : : /* Remove phi statement, which was holding CRC result. */
1276 : 223 : gimple_stmt_iterator tmp_gsi = gsi_for_stmt (output_crc);
1277 : 223 : remove_phi_node (&tmp_gsi, false);
1278 : :
1279 : : /* Alter the exit condition of the loop to always exit. */
1280 : 223 : gcond* loop_exit_cond = get_loop_exit_condition (m_crc_loop);
1281 : 223 : gimple_cond_make_false (loop_exit_cond);
1282 : 223 : update_stmt (loop_exit_cond);
1283 : 223 : return true;
1284 : : }
1285 : :
1286 : : unsigned int
1287 : 214519 : crc_optimization::execute (function *fun)
1288 : : {
1289 : 214519 : if (dump_file && (dump_flags & TDF_DETAILS))
1290 : 291 : fprintf (dump_file, "\nExamining %s function.\n",
1291 : : function_name (fun));
1292 : :
1293 : 429038 : if (number_of_loops (fun) <= 1)
1294 : : return 0;
1295 : :
1296 : : /* Get loops of the function. */
1297 : 214519 : auto loop_list = loops_list (fun, LI_ONLY_INNERMOST);
1298 : 1120152 : for (auto loop: loop_list)
1299 : : {
1300 : : /* Perform initial checks to filter out non-CRCs. */
1301 : 476660 : if (loop_may_calculate_crc (loop))
1302 : : {
1303 : : /* Get the phi which will hold the calculated CRC. */
1304 : 288 : gphi *output_crc = get_output_phi ();
1305 : 288 : if (!output_crc)
1306 : : break;
1307 : :
1308 : 270 : swap_crc_and_data_if_needed (output_crc);
1309 : 270 : if (!is_output_crc (output_crc))
1310 : : break;
1311 : 267 : if (!validate_crc_and_data ())
1312 : : break;
1313 : :
1314 : 258 : edge loop_latch = loop_latch_edge (m_crc_loop);
1315 : 258 : tree calced_crc = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, loop_latch);
1316 : 258 : crc_symbolic_execution execute_loop (m_crc_loop, nullptr);
1317 : : /* Execute the loop assigning specific values to CRC and data
1318 : : for extracting the polynomial. */
1319 : 258 : std::pair <tree, value *>
1320 : 258 : calc_polynom = execute_loop.extract_polynomial (m_phi_for_crc,
1321 : : m_phi_for_data,
1322 : : calced_crc,
1323 : 258 : m_is_bit_forward);
1324 : :
1325 : 258 : value *polynom_value = calc_polynom.second;
1326 : : /* Stop analysis if we couldn't get the polynomial's value. */
1327 : 258 : if (!polynom_value)
1328 : : break;
1329 : :
1330 : : /* Stop analysis in case optimize_size is specified
1331 : : and table-based would be generated. This check is only needed for
1332 : : TARGET_CRC case, as polynomial's value isn't known in the
1333 : : beginning. */
1334 : 247 : construct_constant_polynomial (polynom_value);
1335 : :
1336 : 247 : if (!loop_calculates_crc (output_crc, calc_polynom))
1337 : : break;
1338 : :
1339 : 223 : if (dump_file)
1340 : 178 : fprintf (dump_file, "The loop with %d header BB index "
1341 : 178 : "calculates CRC!\n", m_crc_loop->header->index);
1342 : :
1343 : 223 : if (!optimize_crc_loop (output_crc))
1344 : : {
1345 : 0 : if (dump_file)
1346 : 0 : fprintf (dump_file, "Couldn't generate faster CRC code.\n");
1347 : : }
1348 : 258 : }
1349 : : }
1350 : 214519 : return 0;
1351 : 214519 : }
1352 : :
1353 : : namespace
1354 : : {
1355 : :
1356 : : const pass_data pass_data_crc_optimization
1357 : : = {
1358 : : GIMPLE_PASS, /* type */
1359 : : "crc", /* name */
1360 : : OPTGROUP_NONE, /* optinfo_flags */
1361 : : TV_GIMPLE_CRC_OPTIMIZATION, /* tv_id */
1362 : : (PROP_cfg | PROP_ssa), /* properties_required */
1363 : : 0, /* properties_provided */
1364 : : 0, /* properties_destroyed */
1365 : : 0, /* todo_flags_start */
1366 : : 0, /* todo_flags_finish */
1367 : : };
1368 : :
1369 : : class pass_crc_optimization : public gimple_opt_pass {
1370 : : public:
1371 : 283157 : pass_crc_optimization (gcc::context *ctxt)
1372 : 566314 : : gimple_opt_pass (pass_data_crc_optimization, ctxt)
1373 : : {}
1374 : :
1375 : : /* opt_pass methods: */
1376 : 230065 : virtual bool gate (function *)
1377 : : {
1378 : 230065 : return flag_optimize_crc;
1379 : : }
1380 : :
1381 : : virtual unsigned int execute (function *);
1382 : :
1383 : : }; // class pass_crc_optimization
1384 : :
1385 : : unsigned int
1386 : 214519 : pass_crc_optimization::execute (function *fun)
1387 : : {
1388 : 214519 : return crc_optimization ().execute (fun);
1389 : : }
1390 : :
1391 : : } // anon namespace
1392 : :
1393 : : gimple_opt_pass *
1394 : 283157 : make_pass_crc_optimization (gcc::context *ctxt)
1395 : : {
1396 : 283157 : return new pass_crc_optimization (ctxt);
1397 : : }
|
