aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Bitcode/Writer
diff options
context:
space:
mode:
authorMichael Kuperstein <michael.m.kuperstein@intel.com>2016-01-06 18:40:11 +0000
committerMichael Kuperstein <michael.m.kuperstein@intel.com>2016-01-06 18:40:11 +0000
commit037c9984dbabe777f40a720e76b687a6c6dae581 (patch)
treed091c8abf580ac62dda53e6667e620d0eaf06dc5 /llvm/lib/Bitcode/Writer
parentb243c95c6ab25a84bc01d06f71a8a8b87c6e0b5b (diff)
downloadllvm-037c9984dbabe777f40a720e76b687a6c6dae581.zip
llvm-037c9984dbabe777f40a720e76b687a6c6dae581.tar.gz
llvm-037c9984dbabe777f40a720e76b687a6c6dae581.tar.bz2
[ShrinkWrap] Fix FindIDom to only have one kind of failure.
FindIDom() can fail in two different ways - it can either return nullptr or the block itself, depending on the circumstances. Some users of FindIDom() check one error condition, while others check the other. Change it to always return nullptr on failure. This fixes PR26004. Differential Revision: http://reviews.llvm.org/D15847 llvm-svn: 256955
Diffstat (limited to 'llvm/lib/Bitcode/Writer')
0 files changed, 0 insertions, 0 deletions
generated by cgit v1.1 at 2025-11-02 01:36:01 +0000
+, 1, +, a_2}_1 */ res = get_instantiated_value (cache, chrec); if (res) return res; /* Store the convenient value for chrec in the structure. If it is defined outside of the loop, we may just leave it in symbolic form, otherwise we need to admit that we do not know its behavior inside the loop. */ res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know; set_instantiated_value (cache, chrec, res); /* To make things even more complicated, instantiate_parameters_1 calls analyze_scalar_evolution that may call # of iterations analysis that may in turn call instantiate_parameters_1 again. To prevent the infinite recursion, keep also the bitmap of ssa names that are being instantiated globally. */ if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec))) return res; def_loop = find_common_loop (loop, def_bb->loop_father); /* If the analysis yields a parametric chrec, instantiate the result again. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); /* Don't instantiate loop-closed-ssa phi nodes. */ if (TREE_CODE (res) == SSA_NAME && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth > def_loop->depth))) { if (res == chrec) res = loop_closed_phi_def (chrec); else res = chrec; if (res == NULL_TREE) res = chrec_dont_know; } else if (res != chrec_dont_know) res = instantiate_parameters_1 (loop, res, flags, cache); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); /* Store the correct value to the cache. */ set_instantiated_value (cache, chrec, res); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), flags, cache); if (op1 == chrec_dont_know) return chrec_dont_know; if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); return chrec; case PLUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), flags, cache); if (op1 == chrec_dont_know) return chrec_dont_know; if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1); return chrec; case MINUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), flags, cache); if (op1 == chrec_dont_know) return chrec_dont_know; if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1); return chrec; case MULT_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), flags, cache); if (op1 == chrec_dont_know) return chrec_dont_know; if (TREE_OPERAND (chrec, 0) != op0 || TREE_OPERAND (chrec, 1) != op1) chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); return chrec; case NOP_EXPR: case CONVERT_EXPR: case NON_LVALUE_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; if (flags & FOLD_CONVERSIONS) { tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0); if (tmp) return tmp; } if (op0 == TREE_OPERAND (chrec, 0)) return chrec; return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE); case SCEV_NOT_KNOWN: return chrec_dont_know; case SCEV_KNOWN: return chrec_known; default: break; } switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) { case 3: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), flags, cache); if (op1 == chrec_dont_know) return chrec_dont_know; op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), flags, cache); if (op2 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) && op1 == TREE_OPERAND (chrec, 1) && op2 == TREE_OPERAND (chrec, 2)) return chrec; return fold_build3 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1, op2); case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), flags, cache); if (op1 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0) && op1 == TREE_OPERAND (chrec, 1)) return chrec; return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); case 1: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), flags, cache); if (op0 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0)) return chrec; return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); case 0: return chrec; default: break; } /* Too complicated to handle. */ return chrec_dont_know; } /* Analyze all the parameters of the chrec that were left under a symbolic form. LOOP is the loop in which symbolic names have to be analyzed and instantiated. */ tree instantiate_parameters (struct loop *loop, tree chrec) { tree res; htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "(instantiate_parameters \n"); fprintf (dump_file, " (loop_nb = %d)\n", loop->num); fprintf (dump_file, " (chrec = "); print_generic_expr (dump_file, chrec, 0); fprintf (dump_file, ")\n"); } res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache); if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (res = "); print_generic_expr (dump_file, res, 0); fprintf (dump_file, "))\n"); } htab_delete (cache); return res; } /* Similar to instantiate_parameters, but does not introduce the evolutions in outer loops for LOOP invariants in CHREC, and does not care about causing overflows, as long as they do not affect value of an expression. */ static tree resolve_mixers (struct loop *loop, tree chrec) { htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache); htab_delete (cache); return ret; } /* Entry point for the analysis of the number of iterations pass. This function tries to safely approximate the number of iterations the loop will run. When this property is not decidable at compile time, the result is chrec_dont_know. Otherwise the result is a scalar or a symbolic parameter. Example of analysis: suppose that the loop has an exit condition: "if (b > 49) goto end_loop;" and that in a previous analysis we have determined that the variable 'b' has an evolution function: "EF = {23, +, 5}_2". When we evaluate the function at the point 5, i.e. the value of the variable 'b' after 5 iterations in the loop, we have EF (5) = 48, and EF (6) = 53. In this case the value of 'b' on exit is '53' and the loop body has been executed 6 times. */ tree number_of_iterations_in_loop (struct loop *loop) { tree res, type; edge exit; struct tree_niter_desc niter_desc; /* Determine whether the number_of_iterations_in_loop has already been computed. */ res = loop->nb_iterations; if (res) return res; res = chrec_dont_know; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(number_of_iterations_in_loop\n"); exit = loop->single_exit; if (!exit) goto end; if (!number_of_iterations_exit (loop, exit, &niter_desc, false)) goto end; type = TREE_TYPE (niter_desc.niter); if (integer_nonzerop (niter_desc.may_be_zero)) res = build_int_cst (type, 0); else if (integer_zerop (niter_desc.may_be_zero)) res = niter_desc.niter; else res = chrec_dont_know; end: return set_nb_iterations_in_loop (loop, res); } /* One of the drivers for testing the scalar evolutions analysis. This function computes the number of iterations for all the loops from the EXIT_CONDITIONS array. */ static void number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions) { unsigned int i; unsigned nb_chrec_dont_know_loops = 0; unsigned nb_static_loops = 0; tree cond; for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { tree res = number_of_iterations_in_loop (loop_containing_stmt (cond)); if (chrec_contains_undetermined (res)) nb_chrec_dont_know_loops++; else nb_static_loops++; } if (dump_file) { fprintf (dump_file, "\n(\n"); fprintf (dump_file, "-----------------------------------------\n"); fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops); fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops); fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num); fprintf (dump_file, "-----------------------------------------\n"); fprintf (dump_file, ")\n\n"); print_loop_ir (dump_file); } } /* Counters for the stats. */ struct chrec_stats { unsigned nb_chrecs; unsigned nb_affine; unsigned nb_affine_multivar; unsigned nb_higher_poly; unsigned nb_chrec_dont_know; unsigned nb_undetermined; }; /* Reset the counters. */ static inline void reset_chrecs_counters (struct chrec_stats *stats) { stats->nb_chrecs = 0; stats->nb_affine = 0; stats->nb_affine_multivar = 0; stats->nb_higher_poly = 0; stats->nb_chrec_dont_know = 0; stats->nb_undetermined = 0; } /* Dump the contents of a CHREC_STATS structure. */ static void dump_chrecs_stats (FILE *file, struct chrec_stats *stats) { fprintf (file, "\n(\n"); fprintf (file, "-----------------------------------------\n"); fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine); fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar); fprintf (file, "%d\tdegree greater than 2 polynomials\n", stats->nb_higher_poly); fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know); fprintf (file, "-----------------------------------------\n"); fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs); fprintf (file, "%d\twith undetermined coefficients\n", stats->nb_undetermined); fprintf (file, "-----------------------------------------\n"); fprintf (file, "%d\tchrecs in the scev database\n", (int) htab_elements (scalar_evolution_info)); fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); fprintf (file, "-----------------------------------------\n"); fprintf (file, ")\n\n"); } /* Gather statistics about CHREC. */ static void gather_chrec_stats (tree chrec, struct chrec_stats *stats) { if (dump_file && (dump_flags & TDF_STATS)) { fprintf (dump_file, "(classify_chrec "); print_generic_expr (dump_file, chrec, 0); fprintf (dump_file, "\n"); } stats->nb_chrecs++; if (chrec == NULL_TREE) { stats->nb_undetermined++; return; } switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: if (evolution_function_is_affine_p (chrec)) { if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, " affine_univariate\n"); stats->nb_affine++; } else if (evolution_function_is_affine_multivariate_p (chrec)) { if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, " affine_multivariate\n"); stats->nb_affine_multivar++; } else { if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, " higher_degree_polynomial\n"); stats->nb_higher_poly++; } break; default: break; } if (chrec_contains_undetermined (chrec)) { if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, " undetermined\n"); stats->nb_undetermined++; } if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, ")\n"); } /* One of the drivers for testing the scalar evolutions analysis. This function analyzes the scalar evolution of all the scalars defined as loop phi nodes in one of the loops from the EXIT_CONDITIONS array. TODO Optimization: A loop is in canonical form if it contains only a single scalar loop phi node. All the other scalars that have an evolution in the loop are rewritten in function of this single index. This allows the parallelization of the loop. */ static void analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions) { unsigned int i; struct chrec_stats stats; tree cond; reset_chrecs_counters (&stats); for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { struct loop *loop; basic_block bb; tree phi, chrec; loop = loop_containing_stmt (cond); bb = loop->header; for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) if (is_gimple_reg (PHI_RESULT (phi))) { chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi))); if (dump_file && (dump_flags & TDF_STATS)) gather_chrec_stats (chrec, &stats); } } if (dump_file && (dump_flags & TDF_STATS)) dump_chrecs_stats (dump_file, &stats); } /* Callback for htab_traverse, gathers information on chrecs in the hashtable. */ static int gather_stats_on_scev_database_1 (void **slot, void *stats) { struct scev_info_str *entry = *slot; gather_chrec_stats (entry->chrec, stats); return 1; } /* Classify the chrecs of the whole database. */ void gather_stats_on_scev_database (void) { struct chrec_stats stats; if (!dump_file) return; reset_chrecs_counters (&stats); htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, &stats); dump_chrecs_stats (dump_file, &stats); } /* Initializer. */ static void initialize_scalar_evolutions_analyzer (void) { /* The elements below are unique. */ if (chrec_dont_know == NULL_TREE) { chrec_not_analyzed_yet = NULL_TREE; chrec_dont_know = make_node (SCEV_NOT_KNOWN); chrec_known = make_node (SCEV_KNOWN); TREE_TYPE (chrec_dont_know) = void_type_node; TREE_TYPE (chrec_known) = void_type_node; } } /* Initialize the analysis of scalar evolutions for LOOPS. */ void scev_initialize (struct loops *loops) { unsigned i; current_loops = loops; scalar_evolution_info = htab_create (100, hash_scev_info, eq_scev_info, del_scev_info); already_instantiated = BITMAP_ALLOC (NULL); initialize_scalar_evolutions_analyzer (); for (i = 1; i < loops->num; i++) if (loops->parray[i]) loops->parray[i]->nb_iterations = NULL_TREE; } /* Cleans up the information cached by the scalar evolutions analysis. */ void scev_reset (void) { unsigned i; struct loop *loop; if (!scalar_evolution_info || !current_loops) return; htab_empty (scalar_evolution_info); for (i = 1; i < current_loops->num; i++) { loop = current_loops->parray[i]; if (loop) loop->nb_iterations = NULL_TREE; } } /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we want STEP to be invariant in LOOP. Otherwise we require it to be an integer constant. */ bool simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step, bool allow_nonconstant_step) { basic_block bb = bb_for_stmt (stmt); tree type, ev; *base = NULL_TREE; *step = NULL_TREE; type = TREE_TYPE (op); if (TREE_CODE (type) != INTEGER_TYPE && TREE_CODE (type) != POINTER_TYPE) return false; ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op); if (chrec_contains_undetermined (ev)) return false; if (tree_does_not_contain_chrecs (ev) && !chrec_contains_symbols_defined_in_loop (ev, loop->num)) { *base = ev; return true; } if (TREE_CODE (ev) != POLYNOMIAL_CHREC || CHREC_VARIABLE (ev) != (unsigned) loop->num) return false; *step = CHREC_RIGHT (ev); if (allow_nonconstant_step) { if (tree_contains_chrecs (*step, NULL) || chrec_contains_symbols_defined_in_loop (*step, loop->num)) return false; } else if (TREE_CODE (*step) != INTEGER_CST) return false; *base = CHREC_LEFT (ev); if (tree_contains_chrecs (*base, NULL) || chrec_contains_symbols_defined_in_loop (*base, loop->num)) return false; return true; } /* Runs the analysis of scalar evolutions. */ void scev_analysis (void) { VEC(tree,heap) *exit_conditions; exit_conditions = VEC_alloc (tree, heap, 37); select_loops_exit_conditions (current_loops, &exit_conditions); if (dump_file && (dump_flags & TDF_STATS)) analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); number_of_iterations_for_all_loops (&exit_conditions); VEC_free (tree, heap, exit_conditions); } /* Finalize the scalar evolution analysis. */ void scev_finalize (void) { htab_delete (scalar_evolution_info); BITMAP_FREE (already_instantiated); } /* Replace ssa names for that scev can prove they are constant by the appropriate constants. Also perform final value replacement in loops, in case the replacement expressions are cheap. We only consider SSA names defined by phi nodes; rest is left to the ordinary constant propagation pass. */ void scev_const_prop (void) { basic_block bb; tree name, phi, next_phi, type, ev; struct loop *loop, *ex_loop; bitmap ssa_names_to_remove = NULL; unsigned i; if (!current_loops) return; FOR_EACH_BB (bb) { loop = bb->loop_father; for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { name = PHI_RESULT (phi); if (!is_gimple_reg (name)) continue; type = TREE_TYPE (name); if (!POINTER_TYPE_P (type) && !INTEGRAL_TYPE_P (type)) continue; ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); if (!is_gimple_min_invariant (ev) || !may_propagate_copy (name, ev)) continue; /* Replace the uses of the name. */ if (name != ev) replace_uses_by (name, ev); if (!ssa_names_to_remove) ssa_names_to_remove = BITMAP_ALLOC (NULL); bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); } } /* Remove the ssa names that were replaced by constants. We do not remove them directly in the previous cycle, since this invalidates scev cache. */ if (ssa_names_to_remove) { bitmap_iterator bi; unsigned i; EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) { name = ssa_name (i); phi = SSA_NAME_DEF_STMT (name); gcc_assert (TREE_CODE (phi) == PHI_NODE); remove_phi_node (phi, NULL); } BITMAP_FREE (ssa_names_to_remove); scev_reset (); } /* Now the regular final value replacement. */ for (i = current_loops->num - 1; i > 0; i--) { edge exit; tree def, stmts; loop = current_loops->parray[i]; if (!loop) continue; /* If we do not know exact number of iterations of the loop, we cannot replace the final value. */ exit = loop->single_exit; if (!exit || number_of_iterations_in_loop (loop) == chrec_dont_know) continue; ex_loop = exit->dest->loop_father; for (phi = phi_nodes (exit->dest); phi; phi = next_phi) { next_phi = PHI_CHAIN (phi); def = PHI_ARG_DEF_FROM_EDGE (phi, exit); if (!is_gimple_reg (def) || expr_invariant_in_loop_p (loop, def)) continue; if (!POINTER_TYPE_P (TREE_TYPE (def)) && !INTEGRAL_TYPE_P (TREE_TYPE (def))) continue; def = analyze_scalar_evolution_in_loop (ex_loop, ex_loop, def); if (!tree_does_not_contain_chrecs (def) || chrec_contains_symbols_defined_in_loop (def, loop->num) || def == PHI_RESULT (phi) || (TREE_CODE (def) == SSA_NAME && loop_containing_stmt (SSA_NAME_DEF_STMT (def)) && loop_containing_stmt (phi) && loop_containing_stmt (SSA_NAME_DEF_STMT (def)) == loop_containing_stmt (phi))) continue; /* If computing the expression is expensive, let it remain in loop. TODO -- we should take the cost of computing the expression in loop into account. */ if (force_expr_to_var_cost (def) >= target_spill_cost) continue; def = unshare_expr (def); if (is_gimple_val (def)) stmts = NULL_TREE; else def = force_gimple_operand (def, &stmts, true, SSA_NAME_VAR (PHI_RESULT (phi))); SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit), def); if (stmts) compute_phi_arg_on_exit (exit, stmts, def); } } }
generated by cgit v1.1 at 2025-11-02 01:35:58 +0000