Branch data Line data Source code
1 : : /* CRC optimization.
2 : : Copyright (C) 2022-2024 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 : 211328 : crc_optimization () : m_visited_stmts (BITMAP_ALLOC (NULL)),
235 : 211328 : m_crc_loop (nullptr), m_polynomial (0)
236 : : {
237 : 211328 : set_initial_values ();
238 : 211328 : }
239 : 211328 : ~crc_optimization ()
240 : : {
241 : 211328 : 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 : 284 : crc_optimization::dump_crc_information ()
250 : : {
251 : 284 : 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 : 284 : }
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 : 289 : crc_optimization::cond_true_is_checked_for_bit_one (const gcond *cond)
380 : : {
381 : 289 : if (!cond)
382 : : return false;
383 : :
384 : 289 : tree rhs = gimple_cond_rhs (cond);
385 : 289 : enum tree_code code = gimple_cond_code (cond);
386 : :
387 : : /* If the condition is something == 1 -> return true. */
388 : 289 : if (code == EQ_EXPR && integer_onep (rhs))
389 : : return true;
390 : :
391 : : /* If the condition is something != 0 or something < 0 -> return true. */
392 : 287 : if ((code == NE_EXPR || code == LT_EXPR)
393 : 287 : && 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 : 289 : crc_optimization::is_crc_satisfiable_cond (basic_block pred_bb,
411 : : basic_block xor_bb,
412 : : gcond *cond)
413 : : {
414 : 289 : edge true_edge;
415 : 289 : edge false_edge;
416 : 289 : extract_true_false_edges_from_block (pred_bb, &true_edge, &false_edge);
417 : 289 : 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 : 289 : if (cond_is_checked_for_bit_one && true_edge->dest == xor_bb)
420 : : {
421 : 288 : 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 : 289 : crc_optimization::is_crc_checked (gcond *cond)
445 : : {
446 : 289 : tree lhs = gimple_cond_lhs (cond);
447 : :
448 : : /* As conditions are in canonical form, only left part must be an
449 : : SSA_NAME. */
450 : 289 : 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 : 289 : auto_vec<gimple *> cond_dep_stmts (m_crc_loop->num_nodes);
456 : 289 : bool set_defs_succeeded = set_defs (lhs, cond_dep_stmts, true);
457 : 289 : bitmap_clear (m_visited_stmts);
458 : 289 : if (!set_defs_succeeded)
459 : : return false;
460 : 286 : return cond_depends_on_crc (cond_dep_stmts);
461 : 289 : }
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 : 289 : 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 : 578 : gcond *cond = safe_dyn_cast<gcond *> (gsi_stmt (gsi_last_bb (pred_bb)));
482 : 289 : 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 : 289 : 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 : 289 : 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 : 969 : crc_optimization::is_acceptable_stmt_code (const tree_code &stmt_code)
509 : : {
510 : 969 : return (stmt_code == BIT_IOR_EXPR)
511 : 969 : || (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 : 277 : || (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 : 314 : crc_optimization::can_be_crc_shift (gimple *assign_stmt)
524 : : {
525 : 314 : tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
526 : 314 : if (stmt_code == LSHIFT_EXPR || stmt_code == RSHIFT_EXPR)
527 : : {
528 : 296 : m_is_bit_forward = (stmt_code == LSHIFT_EXPR);
529 : : /* Check that shift one is done, keep shift statement. */
530 : 296 : if (integer_onep (gimple_assign_rhs2 (assign_stmt)))
531 : : {
532 : 291 : 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 : 291 : if (dump_file && (dump_flags & TDF_DETAILS))
540 : 231 : fprintf (dump_file,
541 : : "Found <<1 or >>1.\n");
542 : 291 : 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 : 969 : crc_optimization::can_not_be_crc_stmt (gimple *assign_stmt)
555 : : {
556 : 969 : tree_code stmt_code = gimple_assign_rhs_code (assign_stmt);
557 : 969 : 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 : 2510 : crc_optimization::passes_checks_for_def_chain (tree variable)
575 : : {
576 : 2510 : if (!(variable && TREE_CODE (variable) == SSA_NAME))
577 : : return false;
578 : :
579 : : /* No definition chain for default defs. */
580 : 1710 : if (SSA_NAME_IS_DEFAULT_DEF (variable))
581 : : return false;
582 : :
583 : 1710 : gimple *stmt = SSA_NAME_DEF_STMT (variable);
584 : :
585 : 1710 : if (!stmt)
586 : : return false;
587 : :
588 : : /* Don't go outside the loop. */
589 : 1710 : 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 : 2510 : crc_optimization::set_defs (tree name, auto_vec<gimple *> &use_defs,
603 : : bool keep_only_header_phis = false)
604 : : {
605 : 2510 : if (!passes_checks_for_def_chain (name))
606 : : return true;
607 : :
608 : : /* Don't consider already visited names. */
609 : 1705 : unsigned v = SSA_NAME_VERSION (name);
610 : 1705 : if (bitmap_bit_p (m_visited_stmts, v))
611 : : return true;
612 : 1703 : 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 : 1703 : if (use_defs.length () > 12)
619 : : return false;
620 : :
621 : 1703 : 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 : 1703 : if (!keep_only_header_phis)
626 : 674 : 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 : 1703 : if (is_a<gassign *> (stmt))
631 : : {
632 : 969 : if (can_not_be_crc_stmt (stmt))
633 : : return false;
634 : :
635 : 965 : tree ssa1 = gimple_assign_rhs1 (stmt);
636 : 965 : tree ssa2 = gimple_assign_rhs2 (stmt);
637 : 965 : if (!set_defs (ssa1, use_defs, keep_only_header_phis))
638 : : return false;
639 : 953 : 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 : 734 : else if (is_a<gphi *> (stmt))
647 : : {
648 : 729 : if (bb_loop_header_p (gimple_bb (stmt)))
649 : : {
650 : : /* If it's specified to keep only header phi's, keep it. */
651 : 729 : if (keep_only_header_phis)
652 : 425 : 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 : 729 : 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 : 297 : crc_optimization::find_shift_before_xor (const auto_vec<gimple *> &stmts)
677 : : {
678 : 973 : 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 : 323 : if (is_a<gassign *> (*stmt_it))
682 : : {
683 : 304 : if (can_be_crc_shift (*stmt_it))
684 : 282 : 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 : 297 : crc_optimization::set_crc_and_data_phi (auto_vec<gimple *> &stmts)
700 : : {
701 : 2207 : for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
702 : : {
703 : 658 : if (is_a<gphi *> (*stmt_it) && bb_loop_header_p (gimple_bb (*stmt_it)))
704 : : {
705 : 304 : if (!m_phi_for_crc)
706 : 297 : 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 : 297 : 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 : 286 : crc_optimization::cond_depends_on_crc (auto_vec<gimple *>& stmts)
726 : : {
727 : 286 : bool con_depends_on_crc = false;
728 : :
729 : : /* The condition may depend maximum on data and CRC phi's. */
730 : 286 : if (stmts.length () > 2)
731 : : return false;
732 : :
733 : 1700 : for (auto stmt_it = stmts.begin (); stmt_it != stmts.end (); stmt_it++)
734 : : {
735 : 425 : 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 : 425 : 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 : 211839 : crc_optimization::set_initial_values ()
758 : : {
759 : 211839 : m_crc_arg = nullptr;
760 : 211839 : m_data_arg = nullptr;
761 : 211839 : m_shift_stmt = nullptr;
762 : 211839 : m_phi_for_crc = nullptr;
763 : 211839 : m_phi_for_data = nullptr;
764 : 211839 : m_is_bit_forward = false;
765 : 211839 : }
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 : 511 : crc_optimization::xor_calculates_crc (function *crc_fun,
779 : : const gimple *xor_stmt)
780 : : {
781 : 511 : tree crc_var = gimple_assign_lhs (xor_stmt);
782 : 511 : set_initial_values ();
783 : 511 : tree ssa1 = gimple_assign_rhs1 (xor_stmt);
784 : 511 : tree ssa2 = gimple_assign_rhs2 (xor_stmt);
785 : 511 : 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 : 303 : auto_vec<gimple *> xor_dep_stmts (m_crc_loop->num_nodes);
795 : 303 : bool set_defs_succeeded = set_defs (ssa1, xor_dep_stmts);
796 : 303 : bitmap_clear (m_visited_stmts);
797 : 303 : if (!set_defs_succeeded)
798 : : {
799 : 6 : xor_dep_stmts.release ();
800 : 6 : return false;
801 : : }
802 : :
803 : 297 : m_shift_stmt = find_shift_before_xor (xor_dep_stmts);
804 : :
805 : 297 : 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 : 297 : 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 : 291 : basic_block xor_bb = gimple_bb (xor_stmt);
826 : :
827 : : /* Get the predecessor basic block of xor's block. */
828 : 310 : if (!single_pred_p (xor_bb))
829 : : return false;
830 : 291 : 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 : 291 : 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 : 289 : if (crc_cond (block_of_condition, xor_bb))
852 : : {
853 : 284 : if (dump_file)
854 : 239 : fprintf (dump_file,
855 : : "\n%s function maybe contains CRC calculation.\n",
856 : : function_name (crc_fun));
857 : 284 : return true;
858 : : }
859 : :
860 : : return false;
861 : 303 : }
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 : 17471 : crc_optimization::loop_contains_two_conditional_bb (basic_block *loop_bbs,
870 : : unsigned loop_num_nodes)
871 : : {
872 : 17471 : unsigned conditional_bb_count = 0;
873 : : /* Iterate through the loop until the conditional branches count
874 : : is below 3. */
875 : 67798 : for (unsigned i = 0; i < loop_num_nodes && conditional_bb_count <= 2; i++)
876 : : {
877 : 50327 : basic_block bb = loop_bbs[i];
878 : 50327 : if (!single_succ_p (bb))
879 : 23498 : conditional_bb_count++;
880 : : }
881 : 17471 : 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 : 468088 : 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 : 468088 : number_of_latch_executions (func_loop);
893 : 468088 : tree n_inters = func_loop->nb_iterations;
894 : 468088 : if (n_inters == NULL_TREE || n_inters == chrec_dont_know)
895 : : {
896 : 239634 : if (dump_file && (dump_flags & TDF_DETAILS))
897 : 41 : fprintf (dump_file,
898 : : "Loop iteration number is chrec_dont_know.\n");
899 : 239634 : return false;
900 : :
901 : : }
902 : 228454 : else if (tree_fits_uhwi_p (n_inters))
903 : : {
904 : 147953 : unsigned HOST_WIDE_INT
905 : 147953 : loop_iteration_number = tree_to_uhwi (n_inters);
906 : 147953 : if (dump_file && (dump_flags & TDF_DETAILS))
907 : 268 : fprintf (dump_file, "Loop iteration number is "
908 : : HOST_WIDE_INT_PRINT_UNSIGNED ".\n", loop_iteration_number);
909 : :
910 : 147953 : 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 : 210983 : 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 : 468088 : crc_optimization::loop_may_calculate_crc (class loop *loop)
931 : : {
932 : : /* Only examine innermost loops. */
933 : 468088 : if (!loop || loop->inner)
934 : : return false;
935 : :
936 : 468088 : if (!satisfies_crc_loop_iteration_count (loop))
937 : : return false;
938 : :
939 : 17471 : m_crc_loop = loop;
940 : 17471 : 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 : 17471 : if (!loop_contains_two_conditional_bb (loop_bbs, m_crc_loop->num_nodes))
945 : : {
946 : 13264 : 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 : 13264 : return false;
951 : : }
952 : :
953 : : unsigned short checked_xor_count = 0;
954 : : /* Walk bbs of the loop. */
955 : 23988 : for (unsigned int i = 0; i < m_crc_loop->num_nodes; i++)
956 : : {
957 : 20082 : basic_block bb = loop_bbs[i];
958 : : /* Walk instructions of the bb. */
959 : 20082 : for (gimple_stmt_iterator bsi = gsi_start_nondebug_bb (bb);
960 : 65506 : !gsi_end_p (bsi); gsi_next_nondebug (&bsi))
961 : : {
962 : 45725 : gimple *stmt = gsi_stmt (bsi);
963 : : /* If there is an xor instruction,
964 : : check that it is calculating CRC. */
965 : 45725 : if (is_gimple_assign (stmt)
966 : 45725 : && gimple_assign_rhs_code (stmt) == BIT_XOR_EXPR)
967 : : {
968 : 511 : if (dump_file && (dump_flags & TDF_DETAILS))
969 : 373 : fprintf (dump_file,
970 : : "Found xor, "
971 : : "checking whether it is for CRC calculation.\n");
972 : :
973 : 511 : if (xor_calculates_crc (cfun, stmt))
974 : : {
975 : 284 : dump_crc_information ();
976 : 284 : free (loop_bbs);
977 : 301 : return true;
978 : : }
979 : :
980 : 227 : if (++checked_xor_count == 2)
981 : : return false;
982 : : }
983 : : }
984 : : }
985 : 3906 : free (loop_bbs);
986 : 3906 : return false;
987 : : }
988 : :
989 : : /* Symbolically executes the loop and checks that LFSR and resulting states
990 : : match.
991 : : Returns true if it is verified that the loop calculates CRC.
992 : : Otherwise, return false.
993 : : OUTPUT_CRC is the phi statement which will hold the calculated CRC value
994 : : after the loop exit. */
995 : :
996 : : bool
997 : 243 : crc_optimization::loop_calculates_crc (gphi *output_crc,
998 : : std::pair<tree, value *> calc_polynom)
999 : : {
1000 : : /* Create LFSR state using extracted polynomial. */
1001 : 486 : value * lfsr = state::create_lfsr (calc_polynom.first, calc_polynom.second,
1002 : 243 : m_is_bit_forward);
1003 : 243 : if (!lfsr)
1004 : : {
1005 : 20 : if (dump_file && (dump_flags & TDF_DETAILS))
1006 : 14 : fprintf (dump_file, "Couldn't create LFSR!\n");
1007 : 20 : return false;
1008 : : }
1009 : :
1010 : 223 : if (dump_file && (dump_flags & TDF_DETAILS))
1011 : : {
1012 : 177 : fprintf (dump_file, "\nLFSR value is \n");
1013 : 177 : state::print_value (lfsr);
1014 : : }
1015 : :
1016 : : /* Execute the loop with symbolic values
1017 : : (symbolic value is assigned to the variable when its value isn't known)
1018 : : to keep states, for further comparison. */
1019 : 223 : bool is_crc = true;
1020 : 223 : crc_symbolic_execution loop_executor (m_crc_loop, output_crc);
1021 : 3463 : while (!loop_executor.is_last_iteration ())
1022 : : {
1023 : 3021 : if (!loop_executor.symb_execute_crc_loop ())
1024 : : {
1025 : 0 : if (dump_file)
1026 : 0 : fprintf (dump_file, "\nCRC verification didn't succeed "
1027 : : "during symbolic execution!\n");
1028 : : is_crc = false;
1029 : : break;
1030 : : }
1031 : :
1032 : : /* Check whether LFSR and obtained states are same. */
1033 : 3021 : tree calculated_crc = PHI_ARG_DEF_FROM_EDGE (output_crc,
1034 : : single_exit (m_crc_loop));
1035 : 3021 : if (!all_states_match_lfsr (lfsr, m_is_bit_forward, calculated_crc,
1036 : : loop_executor.get_final_states ()))
1037 : : {
1038 : 4 : if (dump_file && (dump_flags & TDF_DETAILS))
1039 : 2 : fprintf (dump_file, "Returned state and LFSR differ.\n");
1040 : : is_crc = false;
1041 : : break;
1042 : : }
1043 : : }
1044 : 223 : delete lfsr;
1045 : 223 : return is_crc;
1046 : 223 : }
1047 : :
1048 : : /* Returns true if OUTPUT_CRC's result is the input of M_PHI_FOR_CRC.
1049 : : Otherwise, returns false. */
1050 : :
1051 : : bool
1052 : 266 : crc_optimization::is_output_crc (gphi *output_crc)
1053 : : {
1054 : 266 : tree crc_of_exit
1055 : 266 : = PHI_ARG_DEF_FROM_EDGE (output_crc, single_exit (m_crc_loop));
1056 : 266 : tree crc_of_latch
1057 : 266 : = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, loop_latch_edge (m_crc_loop));
1058 : 266 : if (crc_of_exit == crc_of_latch)
1059 : : {
1060 : 263 : if (dump_file && (dump_flags & TDF_DETAILS))
1061 : : {
1062 : 211 : fprintf (dump_file, "Output CRC is ");
1063 : 211 : print_gimple_expr (dump_file, (gimple *) output_crc, dump_flags);
1064 : 211 : fprintf (dump_file, "\n");
1065 : : }
1066 : 263 : return true;
1067 : : }
1068 : : else
1069 : : {
1070 : 3 : if (dump_file && (dump_flags & TDF_DETAILS))
1071 : 3 : fprintf (dump_file, "Output CRC and determined input CRC "
1072 : : "differ.\n");
1073 : 3 : return false;
1074 : : }
1075 : : }
1076 : :
1077 : : /* Swaps M_PHI_FOR_CRC and M_PHI_FOR_DATA if they are mixed. */
1078 : :
1079 : : void
1080 : 266 : crc_optimization::swap_crc_and_data_if_needed (gphi *output_crc)
1081 : : {
1082 : 266 : tree crc_of_exit
1083 : 266 : = PHI_ARG_DEF_FROM_EDGE (output_crc, single_exit (m_crc_loop));
1084 : 266 : edge crc_loop_latch = loop_latch_edge (m_crc_loop);
1085 : 266 : if (crc_of_exit != PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, crc_loop_latch))
1086 : : {
1087 : 7 : if (m_phi_for_data
1088 : 7 : && crc_of_exit == PHI_ARG_DEF_FROM_EDGE (m_phi_for_data,
1089 : : crc_loop_latch))
1090 : : {
1091 : 4 : std::swap (m_phi_for_crc, m_phi_for_data);
1092 : : }
1093 : : }
1094 : 266 : }
1095 : :
1096 : : /* Validates CRC and data arguments and
1097 : : sets them for potential CRC loop replacement.
1098 : :
1099 : : The function extracts the CRC and data arguments from PHI nodes and
1100 : : performs several checks to ensure that the CRC and data are suitable for
1101 : : replacing the CRC loop with a more efficient implementation.
1102 : :
1103 : : Returns true if the arguments are valid and the loop replacement is possible,
1104 : : false otherwise. */
1105 : :
1106 : 263 : bool crc_optimization::validate_crc_and_data ()
1107 : : {
1108 : : /* Set m_crc_arg and check if fits in word_mode. */
1109 : 263 : gcc_assert (m_phi_for_crc);
1110 : 263 : m_crc_arg = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc,
1111 : : loop_preheader_edge (m_crc_loop));
1112 : 263 : gcc_assert (m_crc_arg);
1113 : :
1114 : 263 : unsigned HOST_WIDE_INT
1115 : 263 : data_size = tree_to_uhwi (m_crc_loop->nb_iterations) + 1;
1116 : : /* We don't support the case where data is larger than the CRC. */
1117 : 263 : if (TYPE_PRECISION (TREE_TYPE (m_crc_arg)) < data_size)
1118 : : return false;
1119 : :
1120 : : /* Set m_data_arg if a PHI node for data exists,
1121 : : and check its size against loop iterations.
1122 : : This is the case when data and CRC are XOR-ed in the loop. */
1123 : 263 : if (m_phi_for_data)
1124 : : {
1125 : 124 : if (dump_file && (dump_flags & TDF_DETAILS))
1126 : 120 : fprintf (dump_file,
1127 : : "Data and CRC are xor-ed in the for loop. Initializing data "
1128 : : "with its value.\n");
1129 : 124 : m_data_arg = PHI_ARG_DEF_FROM_EDGE (m_phi_for_data,
1130 : : loop_preheader_edge (m_crc_loop));
1131 : 124 : gcc_assert (m_data_arg);
1132 : 124 : if (TYPE_PRECISION (TREE_TYPE (m_data_arg)) != data_size)
1133 : : {
1134 : 9 : if (dump_file && (dump_flags & TDF_DETAILS))
1135 : 9 : fprintf (dump_file,
1136 : : "Loop iteration number and data's size differ.\n");
1137 : 9 : return false;
1138 : : }
1139 : : return true;
1140 : : }
1141 : : return true;
1142 : : }
1143 : :
1144 : : /* Convert polynomial to unsigned HOST_WIDE_INT. */
1145 : :
1146 : : void
1147 : 243 : crc_optimization::construct_constant_polynomial (value *polynomial)
1148 : : {
1149 : 243 : m_polynomial = 0;
1150 : 6507 : for (unsigned i = 0; i < (*polynomial).length (); i++)
1151 : : {
1152 : 6264 : value_bit *const_bit;
1153 : 6264 : if (m_is_bit_forward)
1154 : 2848 : const_bit = (*polynomial)[(*polynomial).length () - 1 - i];
1155 : : else
1156 : 3416 : const_bit = (*polynomial)[i];
1157 : 6264 : m_polynomial <<= 1;
1158 : 10596 : m_polynomial ^= (as_a<bit *> (const_bit))->get_val () ? 1 : 0;
1159 : : }
1160 : 243 : }
1161 : :
1162 : : /* Returns phi statement which may hold the calculated CRC. */
1163 : :
1164 : : gphi *
1165 : 284 : crc_optimization::get_output_phi ()
1166 : : {
1167 : 284 : edge loop_exit = single_exit (m_crc_loop);
1168 : 284 : if (!loop_exit)
1169 : : {
1170 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1171 : 0 : fprintf (dump_file, "The loop doesn't have single exit.\n");
1172 : 0 : return nullptr;
1173 : : }
1174 : 284 : basic_block bb = loop_exit->dest;
1175 : 284 : gphi *output_crc = nullptr;
1176 : 284 : int phi_count = 0;
1177 : :
1178 : : /* We are only interested in cases when there is only one phi at the
1179 : : loop exit, and that phi can potentially represent the CRC.
1180 : : If there are other phis present, it indicates that additional values are
1181 : : being calculated within the loop that are used outside it. */
1182 : 593 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1183 : 309 : gsi_next (&gsi))
1184 : : {
1185 : 327 : tree phi_result = gimple_phi_result (gsi.phi ());
1186 : :
1187 : : /* Don't consider virtual operands. */
1188 : 654 : if (!virtual_operand_p (phi_result))
1189 : : {
1190 : 302 : if (phi_count < 1)
1191 : : {
1192 : : output_crc = gsi.phi ();
1193 : : phi_count++;
1194 : : }
1195 : : else
1196 : : {
1197 : 18 : if (dump_file && (dump_flags & TDF_DETAILS))
1198 : 17 : fprintf (dump_file, "There is more than one output phi.\n");
1199 : 18 : return nullptr;
1200 : : }
1201 : : }
1202 : : }
1203 : :
1204 : 266 : if (output_crc)
1205 : : {
1206 : 266 : if (gimple_phi_num_args (output_crc) == 1)
1207 : : return output_crc;
1208 : : }
1209 : :
1210 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1211 : 0 : fprintf (dump_file, "Couldn't determine output CRC.\n");
1212 : : return nullptr;
1213 : : }
1214 : :
1215 : : /* Attempts to optimize a CRC calculation loop by replacing it with a call to
1216 : : an internal function (IFN_CRC or IFN_CRC_REV).
1217 : : Returns true if replacement succeeded, otherwise false. */
1218 : :
1219 : : bool
1220 : 219 : crc_optimization::optimize_crc_loop (gphi *output_crc)
1221 : : {
1222 : 219 : if (!output_crc)
1223 : : {
1224 : 0 : if (dump_file)
1225 : 0 : fprintf (dump_file, "Couldn't determine output CRC.\n");
1226 : 0 : return false;
1227 : : }
1228 : :
1229 : 219 : if (!m_data_arg)
1230 : : {
1231 : 123 : if (dump_file && (dump_flags & TDF_DETAILS))
1232 : 79 : fprintf (dump_file,
1233 : : "Data and CRC are xor-ed before for loop. Initializing data "
1234 : : "with 0.\n");
1235 : : /* Create a new variable for the data.
1236 : : Determine the data's size with the loop iteration count. */
1237 : 123 : unsigned HOST_WIDE_INT
1238 : 123 : data_size = tree_to_uhwi (m_crc_loop->nb_iterations) + 1;
1239 : 123 : tree type = build_nonstandard_integer_type (data_size, 1);
1240 : : /* For the CRC calculation, it doesn't matter CRC is calculated for the
1241 : : (CRC^data, 0) or (CRC, data). */
1242 : 123 : m_data_arg = build_int_cstu (type, 0);
1243 : : }
1244 : :
1245 : : /* Build tree node for the polynomial from its constant value. */
1246 : 219 : tree polynomial_arg = build_int_cstu (TREE_TYPE (m_crc_arg), m_polynomial);
1247 : 219 : gcc_assert (polynomial_arg);
1248 : :
1249 : 219 : internal_fn ifn;
1250 : 219 : if (m_is_bit_forward)
1251 : : ifn = IFN_CRC;
1252 : : else
1253 : 109 : ifn = IFN_CRC_REV;
1254 : :
1255 : 219 : tree phi_result = gimple_phi_result (output_crc);
1256 : 219 : location_t loc;
1257 : 219 : loc = EXPR_LOCATION (phi_result);
1258 : :
1259 : : /* Add IFN call and write the return value in the phi_result. */
1260 : 219 : gcall *call
1261 : 219 : = gimple_build_call_internal (ifn, 3,
1262 : : m_crc_arg,
1263 : : m_data_arg,
1264 : : polynomial_arg);
1265 : :
1266 : 219 : gimple_call_set_lhs (call, phi_result);
1267 : 219 : gimple_set_location (call, loc);
1268 : 219 : gimple_stmt_iterator si = gsi_start_bb (output_crc->bb);
1269 : 219 : gsi_insert_before (&si, call, GSI_SAME_STMT);
1270 : :
1271 : : /* Remove phi statement, which was holding CRC result. */
1272 : 219 : gimple_stmt_iterator tmp_gsi = gsi_for_stmt (output_crc);
1273 : 219 : remove_phi_node (&tmp_gsi, false);
1274 : :
1275 : : /* Alter the exit condition of the loop to always exit. */
1276 : 219 : gcond* loop_exit_cond = get_loop_exit_condition (m_crc_loop);
1277 : 219 : gimple_cond_make_false (loop_exit_cond);
1278 : 219 : update_stmt (loop_exit_cond);
1279 : 219 : return true;
1280 : : }
1281 : :
1282 : : unsigned int
1283 : 211328 : crc_optimization::execute (function *fun)
1284 : : {
1285 : 211328 : if (dump_file && (dump_flags & TDF_DETAILS))
1286 : 291 : fprintf (dump_file, "\nExamining %s function.\n",
1287 : : function_name (fun));
1288 : :
1289 : 422656 : if (number_of_loops (fun) <= 1)
1290 : : return 0;
1291 : :
1292 : : /* Get loops of the function. */
1293 : 211328 : auto loop_list = loops_list (fun, LI_ONLY_INNERMOST);
1294 : 1102007 : for (auto loop: loop_list)
1295 : : {
1296 : : /* Perform initial checks to filter out non-CRCs. */
1297 : 468088 : if (loop_may_calculate_crc (loop))
1298 : : {
1299 : : /* Get the phi which will hold the calculated CRC. */
1300 : 284 : gphi *output_crc = get_output_phi ();
1301 : 284 : if (!output_crc)
1302 : : break;
1303 : :
1304 : 266 : swap_crc_and_data_if_needed (output_crc);
1305 : 266 : if (!is_output_crc (output_crc))
1306 : : break;
1307 : 263 : if (!validate_crc_and_data ())
1308 : : break;
1309 : :
1310 : 254 : edge loop_latch = loop_latch_edge (m_crc_loop);
1311 : 254 : tree calced_crc = PHI_ARG_DEF_FROM_EDGE (m_phi_for_crc, loop_latch);
1312 : 254 : crc_symbolic_execution execute_loop (m_crc_loop, nullptr);
1313 : : /* Execute the loop assigning specific values to CRC and data
1314 : : for extracting the polynomial. */
1315 : 254 : std::pair <tree, value *>
1316 : 254 : calc_polynom = execute_loop.extract_polynomial (m_phi_for_crc,
1317 : : m_phi_for_data,
1318 : : calced_crc,
1319 : 254 : m_is_bit_forward);
1320 : :
1321 : 254 : value *polynom_value = calc_polynom.second;
1322 : : /* Stop analysis if we couldn't get the polynomial's value. */
1323 : 254 : if (!polynom_value)
1324 : : break;
1325 : :
1326 : : /* Stop analysis in case optimize_size is specified
1327 : : and table-based would be generated. This check is only needed for
1328 : : TARGET_CRC case, as polynomial's value isn't known in the
1329 : : beginning. */
1330 : 243 : construct_constant_polynomial (polynom_value);
1331 : :
1332 : 243 : if (!loop_calculates_crc (output_crc, calc_polynom))
1333 : : break;
1334 : :
1335 : 219 : if (dump_file)
1336 : 178 : fprintf (dump_file, "The loop with %d header BB index "
1337 : 178 : "calculates CRC!\n", m_crc_loop->header->index);
1338 : :
1339 : 219 : if (!optimize_crc_loop (output_crc))
1340 : : {
1341 : 0 : if (dump_file)
1342 : 0 : fprintf (dump_file, "Couldn't generate faster CRC code.\n");
1343 : : }
1344 : 254 : }
1345 : : }
1346 : 211328 : return 0;
1347 : 211328 : }
1348 : :
1349 : : namespace
1350 : : {
1351 : :
1352 : : const pass_data pass_data_crc_optimization
1353 : : = {
1354 : : GIMPLE_PASS, /* type */
1355 : : "crc", /* name */
1356 : : OPTGROUP_NONE, /* optinfo_flags */
1357 : : TV_GIMPLE_CRC_OPTIMIZATION, /* tv_id */
1358 : : (PROP_cfg | PROP_ssa), /* properties_required */
1359 : : 0, /* properties_provided */
1360 : : 0, /* properties_destroyed */
1361 : : 0, /* todo_flags_start */
1362 : : 0, /* todo_flags_finish */
1363 : : };
1364 : :
1365 : : class pass_crc_optimization : public gimple_opt_pass {
1366 : : public:
1367 : 279404 : pass_crc_optimization (gcc::context *ctxt)
1368 : 558808 : : gimple_opt_pass (pass_data_crc_optimization, ctxt)
1369 : : {}
1370 : :
1371 : : /* opt_pass methods: */
1372 : 226406 : virtual bool gate (function *)
1373 : : {
1374 : 226406 : return flag_optimize_crc;
1375 : : }
1376 : :
1377 : : virtual unsigned int execute (function *);
1378 : :
1379 : : }; // class pass_crc_optimization
1380 : :
1381 : : unsigned int
1382 : 211328 : pass_crc_optimization::execute (function *fun)
1383 : : {
1384 : 211328 : return crc_optimization ().execute (fun);
1385 : : }
1386 : :
1387 : : } // anon namespace
1388 : :
1389 : : gimple_opt_pass *
1390 : 279404 : make_pass_crc_optimization (gcc::context *ctxt)
1391 : : {
1392 : 279404 : return new pass_crc_optimization (ctxt);
1393 : : }
|
