This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
|
|
|
|
Accessors for the chains of recurrences. Definition at line 26 of file tree-chrec.h. |
|
|
|
After having added an automatically generated element, please include it in the following function. Definition at line 45 of file tree-chrec.h. References chrec_not_analyzed_yet. Referenced by analyze_scalar_evolution_1(), chrec_apply(), chrec_component_in_loop_num(), chrec_convert_1(), chrec_convert_aggressive(), chrec_fold_minus(), chrec_fold_multiply(), chrec_fold_plus(), chrec_fold_plus_1(), chrec_replace_initial_condition(), chrec_type(), convert_affine_scev(), create_data_ref(), hide_evolution_in_other_loops_than_loop(), initial_condition(), instantiate_parameters_1(), and tree_is_chrec(). 00046 { 00047 return (chrec == chrec_not_analyzed_yet 00048 || chrec == chrec_dont_know 00049 || chrec == chrec_known); 00050 }
|
|
||||||||||||||||
|
Build a polynomial chain of recurrence. Definition at line 100 of file tree-chrec.h. References build3, build_int_cst(), chrec_dont_know, NULL_TREE, and TREE_TYPE. Referenced by add_to_evolution_1(), analyze_subscript_affine_affine(), can_use_analyze_subscript_affine_affine(), chrec_component_in_loop_num(), chrec_convert_1(), chrec_convert_aggressive(), chrec_fold_multiply(), chrec_fold_multiply_poly_poly(), chrec_fold_plus_1(), chrec_fold_plus_poly_poly(), chrec_fold_poly_cst(), chrec_replace_initial_condition(), compute_overlap_steps_for_affine_univar(), fold_used_pointer_cast(), hide_evolution_in_other_loops_than_loop(), instantiate_parameters_1(), and reset_evolution_in_loop(). 00103 { 00104 if (left == chrec_dont_know 00105 || right == chrec_dont_know) 00106 return chrec_dont_know; 00107 00108 gcc_assert (TREE_TYPE (left) == TREE_TYPE (right)); 00109 00110 return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left), 00111 build_int_cst (NULL_TREE, loop_num), left, right); 00112 }
|
|
||||||||||||||||
|
Evaluates "CHREC (X)" when the varying variable is VAR.
Example: Given the following parameters,
var = 1
chrec = {3, +, 4}_1
x = 10
The result is given by the Newton's interpolating formula:
3 * \binom{10}{0} + 4 * \binom{10}{1}.
Definition at line 533 of file tree-chrec.c. References automatically_generated_chrec_p(), build_real_from_int_cst(), chrec_contains_symbols_defined_in_loop(), chrec_convert(), chrec_dont_know, chrec_evaluate(), chrec_fold_multiply(), chrec_fold_plus(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), dump_file, dump_flags, evolution_function_is_affine_p(), integer_zerop(), NULL_TREE, print_generic_expr(), SCALAR_FLOAT_TYPE_P, TDF_DETAILS, TREE_CODE, and tree_int_cst_sgn(). Referenced by chrec_is_positive(), and compute_overall_effect_of_inner_loop(). 00536 { 00537 tree type = chrec_type (chrec); 00538 tree res = chrec_dont_know; 00539 00540 if (automatically_generated_chrec_p (chrec) 00541 || automatically_generated_chrec_p (x) 00542 00543 /* When the symbols are defined in an outer loop, it is possible 00544 to symbolically compute the apply, since the symbols are 00545 constants with respect to the varying loop. */ 00546 || chrec_contains_symbols_defined_in_loop (chrec, var)) 00547 return chrec_dont_know; 00548 00549 if (dump_file && (dump_flags & TDF_DETAILS)) 00550 fprintf (dump_file, "(chrec_apply \n"); 00551 00552 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)) 00553 x = build_real_from_int_cst (type, x); 00554 00555 if (evolution_function_is_affine_p (chrec)) 00556 { 00557 /* "{a, +, b} (x)" -> "a + b*x". */ 00558 x = chrec_convert (type, x, NULL_TREE); 00559 res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x); 00560 if (!integer_zerop (CHREC_LEFT (chrec))) 00561 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); 00562 } 00563 00564 else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 00565 res = chrec; 00566 00567 else if (TREE_CODE (x) == INTEGER_CST 00568 && tree_int_cst_sgn (x) == 1) 00569 /* testsuite/.../ssa-chrec-38.c. */ 00570 res = chrec_evaluate (var, chrec, x, 0); 00571 else 00572 res = chrec_dont_know; 00573 00574 if (dump_file && (dump_flags & TDF_DETAILS)) 00575 { 00576 fprintf (dump_file, " (varying_loop = %d\n", var); 00577 fprintf (dump_file, ")\n (chrec = "); 00578 print_generic_expr (dump_file, chrec, 0); 00579 fprintf (dump_file, ")\n (x = "); 00580 print_generic_expr (dump_file, x, 0); 00581 fprintf (dump_file, ")\n (res = "); 00582 print_generic_expr (dump_file, res, 0); 00583 fprintf (dump_file, "))\n"); 00584 } 00585 00586 return res; 00587 }
|
|
|
|
|
||||||||||||
|
Referenced by chrec_apply(), chrec_contains_symbols_defined_in_loop(), no_evolution_in_loop_p(), and simple_iv(). |
|
|
|
|
||||||||||||||||
|
|
|
||||||||||||
|
|
|
||||||||||||||||
|
Fold the subtraction of two chrecs. Definition at line 340 of file tree-chrec.c. References automatically_generated_chrec_p(), chrec_fold_automatically_generated_operands(), chrec_fold_plus_1(), and integer_zerop(). Referenced by analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), analyze_ziv_subscript(), can_use_analyze_subscript_affine_affine(), chrec_fold_plus_1(), chrec_fold_plus_poly_poly(), chrec_fold_poly_cst(), chrec_is_positive(), compute_overall_effect_of_inner_loop(), compute_subscript_distance(), fold_used_pointer(), instantiate_parameters_1(), and interpret_rhs_modify_expr(). 00343 { 00344 if (automatically_generated_chrec_p (op0) 00345 || automatically_generated_chrec_p (op1)) 00346 return chrec_fold_automatically_generated_operands (op0, op1); 00347 00348 if (integer_zerop (op1)) 00349 return op0; 00350 00351 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1); 00352 }
|
|
||||||||||||||||
|
Fold the multiplication of two chrecs. Definition at line 357 of file tree-chrec.c. References automatically_generated_chrec_p(), build_int_cst(), build_polynomial_chrec(), chrec_fold_automatically_generated_operands(), chrec_fold_multiply(), chrec_fold_multiply_poly_poly(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, fold_build2, integer_onep(), integer_zerop(), and TREE_CODE. Referenced by add_to_evolution(), chrec_apply(), chrec_fold_multiply(), chrec_fold_multiply_poly_poly(), chrec_fold_plus_1(), chrec_fold_plus_poly_poly(), chrec_fold_poly_cst(), instantiate_parameters_1(), and interpret_rhs_modify_expr(). 00360 { 00361 if (automatically_generated_chrec_p (op0) 00362 || automatically_generated_chrec_p (op1)) 00363 return chrec_fold_automatically_generated_operands (op0, op1); 00364 00365 switch (TREE_CODE (op0)) 00366 { 00367 case POLYNOMIAL_CHREC: 00368 switch (TREE_CODE (op1)) 00369 { 00370 case POLYNOMIAL_CHREC: 00371 return chrec_fold_multiply_poly_poly (type, op0, op1); 00372 00373 default: 00374 if (integer_onep (op1)) 00375 return op0; 00376 if (integer_zerop (op1)) 00377 return build_int_cst (type, 0); 00378 00379 return build_polynomial_chrec 00380 (CHREC_VARIABLE (op0), 00381 chrec_fold_multiply (type, CHREC_LEFT (op0), op1), 00382 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); 00383 } 00384 00385 default: 00386 if (integer_onep (op0)) 00387 return op1; 00388 00389 if (integer_zerop (op0)) 00390 return build_int_cst (type, 0); 00391 00392 switch (TREE_CODE (op1)) 00393 { 00394 case POLYNOMIAL_CHREC: 00395 return build_polynomial_chrec 00396 (CHREC_VARIABLE (op1), 00397 chrec_fold_multiply (type, CHREC_LEFT (op1), op0), 00398 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); 00399 00400 default: 00401 if (integer_onep (op1)) 00402 return op0; 00403 if (integer_zerop (op1)) 00404 return build_int_cst (type, 0); 00405 return fold_build2 (MULT_EXPR, type, op0, op1); 00406 } 00407 } 00408 }
|
|
||||||||||||||||
|
Fold the addition of two chrecs. Definition at line 321 of file tree-chrec.c. References automatically_generated_chrec_p(), chrec_fold_automatically_generated_operands(), chrec_fold_plus_1(), and integer_zerop(). Referenced by add_to_evolution_1(), chrec_apply(), chrec_evaluate(), chrec_fold_multiply_poly_poly(), chrec_fold_plus_1(), chrec_fold_plus_poly_poly(), chrec_fold_poly_cst(), compute_overlap_steps_for_affine_1_2(), fold_used_pointer(), instantiate_parameters_1(), interpret_rhs_modify_expr(), and set_nb_iterations_in_loop(). 00324 { 00325 if (automatically_generated_chrec_p (op0) 00326 || automatically_generated_chrec_p (op1)) 00327 return chrec_fold_automatically_generated_operands (op0, op1); 00328 00329 if (integer_zerop (op0)) 00330 return op1; 00331 if (integer_zerop (op1)) 00332 return op0; 00333 00334 return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1); 00335 }
|
|
||||||||||||
|
Referenced by analyze_siv_subscript_cst_affine(), and chrec_is_positive(). |
|
||||||||||||
|
Merges two evolution functions that were found by following two alternate paths of a conditional expression. Definition at line 770 of file tree-chrec.c. References chrec_dont_know, chrec_known, chrec_not_analyzed_yet, and eq_evolutions_p(). Referenced by analyze_evolution_in_loop(), analyze_initial_condition(), follow_ssa_edge_in_condition_phi(), and interpret_condition_phi(). 00772 { 00773 if (chrec1 == chrec_dont_know 00774 || chrec2 == chrec_dont_know) 00775 return chrec_dont_know; 00776 00777 if (chrec1 == chrec_known 00778 || chrec2 == chrec_known) 00779 return chrec_known; 00780 00781 if (chrec1 == chrec_not_analyzed_yet) 00782 return chrec2; 00783 if (chrec2 == chrec_not_analyzed_yet) 00784 return chrec1; 00785 00786 if (eq_evolutions_p (chrec1, chrec2)) 00787 return chrec1; 00788 00789 return chrec_dont_know; 00790 }
|
|
||||||||||||
|
Replaces the initial condition in CHREC with INIT_COND. Definition at line 592 of file tree-chrec.c. References automatically_generated_chrec_p(), build_polynomial_chrec(), CHREC_LEFT, chrec_replace_initial_condition(), CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, and TREE_CODE. Referenced by chrec_replace_initial_condition(), and create_data_ref(). 00594 { 00595 if (automatically_generated_chrec_p (chrec)) 00596 return chrec; 00597 00598 gcc_assert (chrec_type (chrec) == chrec_type (init_cond)); 00599 00600 switch (TREE_CODE (chrec)) 00601 { 00602 case POLYNOMIAL_CHREC: 00603 return build_polynomial_chrec 00604 (CHREC_VARIABLE (chrec), 00605 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond), 00606 CHREC_RIGHT (chrec)); 00607 00608 default: 00609 return init_cond; 00610 } 00611 }
|
|
|
Returns the type of the chrec. Definition at line 215 of file tree-chrec.h. References automatically_generated_chrec_p(), NULL_TREE, and TREE_TYPE. Referenced by add_to_evolution(), add_to_evolution_1(), can_use_analyze_subscript_affine_affine(), chrec_apply(), chrec_convert_1(), chrec_fold_multiply_poly_poly(), chrec_fold_plus_poly_poly(), chrec_fold_poly_cst(), chrec_is_positive(), chrec_replace_initial_condition(), compute_overall_effect_of_inner_loop(), create_data_ref(), infer_loop_bounds_from_undefined(), instantiate_parameters_1(), reset_evolution_in_loop(), and set_nb_iterations_in_loop(). 00216 { 00217 if (automatically_generated_chrec_p (chrec)) 00218 return NULL_TREE; 00219 00220 return TREE_TYPE (chrec); 00221 }
|
|
|
Determines whether CHREC is equal to zero. Definition at line 121 of file tree-chrec.h. References integer_zerop(), NULL_TREE, and TREE_CODE. Referenced by chrec_fold_plus_poly_poly(). 00122 { 00123 if (chrec == NULL_TREE) 00124 return false; 00125 00126 if (TREE_CODE (chrec) == INTEGER_CST) 00127 return integer_zerop (chrec); 00128 00129 return false; 00130 }
|
|
||||||||||||
|
Returns true when CHREC0 == CHREC1. Definition at line 1352 of file tree-chrec.c. References CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, eq_evolutions_p(), NULL_TREE, operand_equal_p(), and TREE_CODE. Referenced by all_chrecs_equal_p(), analyze_miv_subscript(), analyze_overlapping_iterations(), analyze_subscript_affine_affine(), chrec_merge(), eq_evolutions_p(), and same_access_functions(). 01354 { 01355 if (chrec0 == NULL_TREE 01356 || chrec1 == NULL_TREE 01357 || TREE_CODE (chrec0) != TREE_CODE (chrec1)) 01358 return false; 01359 01360 if (chrec0 == chrec1) 01361 return true; 01362 01363 switch (TREE_CODE (chrec0)) 01364 { 01365 case INTEGER_CST: 01366 return operand_equal_p (chrec0, chrec1, 0); 01367 01368 case POLYNOMIAL_CHREC: 01369 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1) 01370 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1)) 01371 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1))); 01372 default: 01373 return false; 01374 } 01375 }
|
|
|
|
|
|
Determine whether the given tree is an affine or constant evolution function. Definition at line 180 of file tree-chrec.h. References evolution_function_is_affine_p(), and evolution_function_is_constant_p(). 00181 { 00182 return evolution_function_is_affine_p (chrec) 00183 || evolution_function_is_constant_p (chrec); 00184 }
|
|
|
Determine whether the given tree is an affine evolution function or not. Definition at line 155 of file tree-chrec.h. References CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_invariant_p(), NULL_TREE, and TREE_CODE. Referenced by analyze_siv_subscript(), chrec_apply(), chrec_convert_1(), chrec_is_positive(), evolution_function_is_affine_or_constant_p(), gather_chrec_stats(), and scev_direction(). 00156 { 00157 if (chrec == NULL_TREE) 00158 return false; 00159 00160 switch (TREE_CODE (chrec)) 00161 { 00162 case POLYNOMIAL_CHREC: 00163 if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), 00164 CHREC_VARIABLE (chrec)) 00165 && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), 00166 CHREC_VARIABLE (chrec))) 00167 return true; 00168 else 00169 return false; 00170 00171 default: 00172 return false; 00173 } 00174 }
|
|
|
Determines whether the expression CHREC is a constant. Definition at line 135 of file tree-chrec.h. References NULL_TREE, and TREE_CODE. Referenced by access_functions_are_affine_or_constant_p(), analyze_miv_subscript(), analyze_siv_subscript(), can_use_analyze_subscript_affine_affine(), chrec_steps_divide_constant_p(), compute_subscript_distance(), evolution_function_is_affine_multivariate_p(), evolution_function_is_affine_or_constant_p(), evolution_function_is_invariant_p(), evolution_function_is_invariant_rec_p(), siv_subscript_p(), and ziv_subscript_p(). 00136 { 00137 if (chrec == NULL_TREE) 00138 return false; 00139 00140 switch (TREE_CODE (chrec)) 00141 { 00142 case INTEGER_CST: 00143 case REAL_CST: 00144 return true; 00145 00146 default: 00147 return false; 00148 } 00149 }
|
|
||||||||||||
|
|
|
|
|
|
||||||||||||
|
Returns the evolution part in LOOP_NUM. Example: the call
evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
{1, +, 2}_1 Definition at line 718 of file tree-chrec.c. References chrec_component_in_loop_num(). Referenced by adjust_range_with_scev(), analyze_indirect_ref(), analyze_offset_expr(), estimate_niter_from_size_of_data(), infer_loop_bounds_from_undefined(), vect_can_advance_ivs_p(), vect_is_simple_iv_evolution(), and vect_update_ivs_after_vectorizer(). 00720 { 00721 return chrec_component_in_loop_num (chrec, loop_num, true); 00722 }
|
|
||||||||||||
|
Returns a univariate function that represents the evolution in LOOP_NUM. Mask the evolution of any other loop. Definition at line 631 of file tree-chrec.c. References automatically_generated_chrec_p(), build_polynomial_chrec(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, hide_evolution_in_other_loops_than_loop(), initial_condition(), and TREE_CODE. Referenced by hide_evolution_in_other_loops_than_loop(), and no_evolution_in_loop_p(). 00633 { 00634 if (automatically_generated_chrec_p (chrec)) 00635 return chrec; 00636 00637 switch (TREE_CODE (chrec)) 00638 { 00639 case POLYNOMIAL_CHREC: 00640 if (CHREC_VARIABLE (chrec) == loop_num) 00641 return build_polynomial_chrec 00642 (loop_num, 00643 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 00644 loop_num), 00645 CHREC_RIGHT (chrec)); 00646 00647 else if (CHREC_VARIABLE (chrec) < loop_num) 00648 /* There is no evolution in this loop. */ 00649 return initial_condition (chrec); 00650 00651 else 00652 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 00653 loop_num); 00654 00655 default: 00656 return chrec; 00657 } 00658 }
|
|
|
|
|
||||||||||||
|
Returns the initial condition in LOOP_NUM. Example: the call
initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
{0, +, 1}_1 Definition at line 729 of file tree-chrec.c. References chrec_component_in_loop_num(). Referenced by adjust_range_with_scev(), analyze_indirect_ref(), analyze_offset_expr(), infer_loop_bounds_from_undefined(), nb_vars_in_chrec(), vect_is_simple_iv_evolution(), and vect_update_ivs_after_vectorizer(). 00731 { 00732 return chrec_component_in_loop_num (chrec, loop_num, false); 00733 }
|
|
|
|
|
|
|
|
|
Determines whether CHREC is a loop invariant with respect to LOOP_NUM. Set the result in RES and return true when the property can be computed. Definition at line 198 of file tree-chrec.h. References chrec_contains_symbols_defined_in_loop(), chrec_dont_know, chrec_not_analyzed_yet, hide_evolution_in_other_loops_than_loop(), and tree_is_chrec(). Referenced by analyze_scalar_evolution_in_loop(), and compute_overall_effect_of_inner_loop(). 00199 { 00200 tree scev; 00201 00202 if (chrec == chrec_not_analyzed_yet 00203 || chrec == chrec_dont_know 00204 || chrec_contains_symbols_defined_in_loop (chrec, loop_num)) 00205 return false; 00206 00207 scev = hide_evolution_in_other_loops_than_loop (chrec, loop_num); 00208 *res = !tree_is_chrec (scev); 00209 return true; 00210 }
|
|
||||||||||||||||
|
Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM. This function is essentially used for setting the evolution to chrec_dont_know, for example after having determined that it is impossible to say how many times a loop will execute. Definition at line 741 of file tree-chrec.c. References build3, build_int_cst(), build_polynomial_chrec(), CHREC_LEFT, CHREC_RIGHT, chrec_type(), CHREC_VARIABLE, NULL_TREE, reset_evolution_in_loop(), TREE_CODE, and TREE_TYPE. Referenced by create_data_ref(), and reset_evolution_in_loop(). 00744 { 00745 gcc_assert (chrec_type (chrec) == chrec_type (new_evol)); 00746 00747 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC 00748 && CHREC_VARIABLE (chrec) > loop_num) 00749 { 00750 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), 00751 new_evol); 00752 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), 00753 new_evol); 00754 return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left), 00755 build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)), 00756 left, right); 00757 } 00758 00759 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 00760 && CHREC_VARIABLE (chrec) == loop_num) 00761 chrec = CHREC_LEFT (chrec); 00762 00763 return build_polynomial_chrec (loop_num, chrec, new_evol); 00764 }
|
|
||||||||||||
|
|
|
|
Determines whether EXPR does not contains chrec expressions. Definition at line 189 of file tree-chrec.h. References tree_contains_chrecs(). Referenced by simple_iv(). 00190 { 00191 return !tree_contains_chrecs (expr, NULL); 00192 }
|
|
|
The tree nodes aka. CHRECs. Definition at line 55 of file tree-chrec.h. References automatically_generated_chrec_p(), and TREE_CODE. Referenced by no_evolution_in_loop_p(), tree_contains_chrecs(), vect_can_advance_ivs_p(), vect_is_simple_iv_evolution(), and vect_update_ivs_after_vectorizer(). 00056 { 00057 if (TREE_CODE (expr) == POLYNOMIAL_CHREC 00058 || automatically_generated_chrec_p (expr)) 00059 return true; 00060 else 00061 return false; 00062 }
|
|
|
Reserved to the cases where the analyzer has detected an undecidable property at compile time. Definition at line 281 of file tree-scalar-evolution.c. Referenced by add_multivariate_self_dist(), add_other_self_distances(), add_to_evolution(), add_to_evolution_1(), analyze_evolution_in_loop(), analyze_indirect_ref(), analyze_initial_condition(), |