/* * Copyright (c) 2023, 2025, Oracle and/or its affiliates. All rights reserved. * Copyright (c) 2023, Arm Limited. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ #include "opto/addnode.hpp" #include "opto/connode.hpp" #include "opto/convertnode.hpp" #include "opto/mulnode.hpp" #include "opto/rootnode.hpp" #include "opto/vectorization.hpp" bool VLoop::check_preconditions() { #ifndef PRODUCT if (is_trace_preconditions()) { tty->print_cr("\nVLoop::check_preconditions"); lpt()->dump_head(); lpt()->head()->dump(); } #endif VStatus status = check_preconditions_helper(); if (!status.is_success()) { #ifndef PRODUCT if (is_trace_preconditions()) { tty->print_cr("VLoop::check_preconditions: failed: %s", status.failure_reason()); } #endif return false; // failure } return true; // success } VStatus VLoop::check_preconditions_helper() { // Only accept vector width that is power of 2 int vector_width = Matcher::vector_width_in_bytes(T_BYTE); if (vector_width < 2 || !is_power_of_2(vector_width)) { return VStatus::make_failure(VLoop::FAILURE_VECTOR_WIDTH); } // Only accept valid counted loops (int) if (!_lpt->_head->as_Loop()->is_valid_counted_loop(T_INT)) { return VStatus::make_failure(VLoop::FAILURE_VALID_COUNTED_LOOP); } _cl = _lpt->_head->as_CountedLoop(); _iv = _cl->phi()->as_Phi(); if (_cl->is_vectorized_loop()) { return VStatus::make_failure(VLoop::FAILURE_ALREADY_VECTORIZED); } if (_cl->is_unroll_only()) { return VStatus::make_failure(VLoop::FAILURE_UNROLL_ONLY); } // Check for control flow in the body _cl_exit = _cl->loopexit(); bool has_cfg = _cl_exit->in(0) != _cl; if (has_cfg && !is_allow_cfg()) { #ifndef PRODUCT if (is_trace_preconditions()) { tty->print_cr("VLoop::check_preconditions: fails because of control flow."); tty->print(" cl_exit %d", _cl_exit->_idx); _cl_exit->dump(); tty->print(" cl_exit->in(0) %d", _cl_exit->in(0)->_idx); _cl_exit->in(0)->dump(); tty->print(" lpt->_head %d", _cl->_idx); _cl->dump(); _lpt->dump_head(); } #endif return VStatus::make_failure(VLoop::FAILURE_CONTROL_FLOW); } // Make sure the are no extra control users of the loop backedge if (_cl->back_control()->outcnt() != 1) { return VStatus::make_failure(VLoop::FAILURE_BACKEDGE); } if (_cl->is_main_loop()) { // To align vector memory accesses in the main-loop, we will have to adjust // the pre-loop limit. CountedLoopEndNode* pre_end = _cl->find_pre_loop_end(); if (pre_end == nullptr) { return VStatus::make_failure(VLoop::FAILURE_PRE_LOOP_LIMIT); } Node* pre_opaq1 = pre_end->limit(); if (pre_opaq1->Opcode() != Op_Opaque1) { return VStatus::make_failure(VLoop::FAILURE_PRE_LOOP_LIMIT); } _pre_loop_end = pre_end; // See if we find the infrastructure for speculative runtime-checks. // (1) Auto Vectorization Parse Predicate Node* pre_ctrl = pre_loop_head()->in(LoopNode::EntryControl); const Predicates predicates(pre_ctrl); const PredicateBlock* predicate_block = predicates.auto_vectorization_check_block(); if (predicate_block->has_parse_predicate()) { _auto_vectorization_parse_predicate_proj = predicate_block->parse_predicate_success_proj(); } // (2) Multiversioning fast-loop projection IfTrueNode* before_predicates = predicates.entry()->isa_IfTrue(); if (before_predicates != nullptr && before_predicates->in(0)->is_If() && before_predicates->in(0)->in(1)->is_OpaqueMultiversioning()) { _multiversioning_fast_proj = before_predicates; } #ifndef PRODUCT if (is_trace_preconditions() || is_trace_speculative_runtime_checks()) { tty->print_cr(" Infrastructure for speculative runtime-checks:"); if (_auto_vectorization_parse_predicate_proj != nullptr) { tty->print_cr(" auto_vectorization_parse_predicate_proj: speculate and trap"); _auto_vectorization_parse_predicate_proj->dump_bfs(5,0,""); } else if (_multiversioning_fast_proj != nullptr) { tty->print_cr(" multiversioning_fast_proj: speculate and multiversion"); _multiversioning_fast_proj->dump_bfs(5,0,""); } else { tty->print_cr(" Not found."); } } #endif assert(_auto_vectorization_parse_predicate_proj == nullptr || _multiversioning_fast_proj == nullptr, "we should only have at most one of these"); assert(_cl->is_multiversion_fast_loop() == (_multiversioning_fast_proj != nullptr), "must find the multiversion selector IFF loop is a multiversion fast loop"); } return VStatus::make_success(); } // Return true iff all submodules are loaded successfully bool VLoopAnalyzer::setup_submodules() { #ifndef PRODUCT if (_vloop.is_trace_loop_analyzer()) { tty->print_cr("\nVLoopAnalyzer::setup_submodules"); _vloop.lpt()->dump_head(); _vloop.cl()->dump(); } #endif VStatus status = setup_submodules_helper(); if (!status.is_success()) { #ifndef PRODUCT if (_vloop.is_trace_loop_analyzer()) { tty->print_cr("\nVLoopAnalyze::setup_submodules: failed: %s", status.failure_reason()); } #endif return false; // failed } return true; // success } VStatus VLoopAnalyzer::setup_submodules_helper() { // Skip any loop that has not been assigned max unroll by analysis. if (SuperWordLoopUnrollAnalysis && _vloop.cl()->slp_max_unroll() == 0) { return VStatus::make_failure(VLoopAnalyzer::FAILURE_NO_MAX_UNROLL); } if (SuperWordReductions) { _reductions.mark_reductions(); } _memory_slices.find_memory_slices(); // If there is no memory slice detected, it means there is no store. // If there is no reduction and no store, then we give up, because // vectorization is not possible anyway (given current limitations). if (!_reductions.is_marked_reduction_loop() && _memory_slices.heads().is_empty()) { return VStatus::make_failure(VLoopAnalyzer::FAILURE_NO_REDUCTION_OR_STORE); } VStatus body_status = _body.construct(); if (!body_status.is_success()) { return body_status; } _types.compute_vector_element_type(); _vpointers.compute_vpointers(); _dependency_graph.construct(); return VStatus::make_success(); } void VLoopVPointers::compute_vpointers() { count_vpointers(); allocate_vpointers_array(); compute_and_cache_vpointers(); NOT_PRODUCT( if (_vloop.is_trace_vpointers()) { print(); } ) } void VLoopVPointers::count_vpointers() { _vpointers_length = 0; _body.for_each_mem([&] (const MemNode* mem, int bb_idx) { _vpointers_length++; }); } void VLoopVPointers::allocate_vpointers_array() { uint bytes = _vpointers_length * sizeof(VPointer); _vpointers = (VPointer*)_arena->Amalloc(bytes); } void VLoopVPointers::compute_and_cache_vpointers() { int pointers_idx = 0; _body.for_each_mem([&] (MemNode* const mem, int bb_idx) { // Placement new: construct directly into the array. ::new (&_vpointers[pointers_idx]) VPointer(mem, _vloop); _bb_idx_to_vpointer.at_put(bb_idx, pointers_idx); pointers_idx++; }); } const VPointer& VLoopVPointers::vpointer(const MemNode* mem) const { assert(mem != nullptr && _vloop.in_bb(mem), "only mem in loop"); int bb_idx = _body.bb_idx(mem); int pointers_idx = _bb_idx_to_vpointer.at(bb_idx); assert(0 <= pointers_idx && pointers_idx < _vpointers_length, "valid range"); return _vpointers[pointers_idx]; } #ifndef PRODUCT void VLoopVPointers::print() const { tty->print_cr("\nVLoopVPointers::print:"); _body.for_each_mem([&] (const MemNode* mem, int bb_idx) { const VPointer& p = vpointer(mem); tty->print(" "); p.print_on(tty); }); } #endif // Construct the dependency graph: // - Data-dependencies: implicit (taken from C2 node inputs). // - Memory-dependencies: // - No edges between different slices. // - No Load-Load edges. // - Inside a slice, add all Store-Load, Load-Store, Store-Store edges, // except if we can prove that the memory does not overlap. void VLoopDependencyGraph::construct() { const GrowableArray& mem_slice_heads = _memory_slices.heads(); const GrowableArray& mem_slice_tails = _memory_slices.tails(); ResourceMark rm; GrowableArray slice_nodes; GrowableArray memory_pred_edges; // For each memory slice, create the memory subgraph for (int i = 0; i < mem_slice_heads.length(); i++) { PhiNode* head = mem_slice_heads.at(i); MemNode* tail = mem_slice_tails.at(i); _memory_slices.get_slice_in_reverse_order(head, tail, slice_nodes); // In forward order (reverse of reverse), visit all memory nodes in the slice. for (int j = slice_nodes.length() - 1; j >= 0 ; j--) { MemNode* n1 = slice_nodes.at(j); memory_pred_edges.clear(); const VPointer& p1 = _vpointers.vpointer(n1); // For all memory nodes before it, check if we need to add a memory edge. for (int k = slice_nodes.length() - 1; k > j; k--) { MemNode* n2 = slice_nodes.at(k); // Ignore Load-Load dependencies: if (n1->is_Load() && n2->is_Load()) { continue; } const VPointer& p2 = _vpointers.vpointer(n2); if (!p1.never_overlaps_with(p2)) { // Possibly overlapping memory memory_pred_edges.append(_body.bb_idx(n2)); } } if (memory_pred_edges.is_nonempty()) { // Data edges are taken implicitly from the C2 graph, thus we only add // a dependency node if we have memory edges. add_node(n1, memory_pred_edges); } } slice_nodes.clear(); } compute_depth(); NOT_PRODUCT( if (_vloop.is_trace_dependency_graph()) { print(); } ) } void VLoopDependencyGraph::add_node(MemNode* n, GrowableArray& memory_pred_edges) { assert(_dependency_nodes.at_grow(_body.bb_idx(n), nullptr) == nullptr, "not yet created"); assert(!memory_pred_edges.is_empty(), "no need to create a node without edges"); DependencyNode* dn = new (_arena) DependencyNode(n, memory_pred_edges, _arena); _dependency_nodes.at_put_grow(_body.bb_idx(n), dn, nullptr); } int VLoopDependencyGraph::find_max_pred_depth(const Node* n) const { int max_pred_depth = 0; if (!n->is_Phi()) { // ignore backedge for (PredsIterator it(*this, n); !it.done(); it.next()) { Node* pred = it.current(); if (_vloop.in_bb(pred)) { max_pred_depth = MAX2(max_pred_depth, depth(pred)); } } } return max_pred_depth; } // We iterate over the body, which is already ordered by the dependencies, i.e. pred comes // before use. With a single pass, we can compute the depth of every node, since we can // assume that the depth of all preds is already computed when we compute the depth of use. void VLoopDependencyGraph::compute_depth() { for (int i = 0; i < _body.body().length(); i++) { Node* n = _body.body().at(i); set_depth(n, find_max_pred_depth(n) + 1); } #ifdef ASSERT for (int i = 0; i < _body.body().length(); i++) { Node* n = _body.body().at(i); int max_pred_depth = find_max_pred_depth(n); if (depth(n) != max_pred_depth + 1) { print(); tty->print_cr("Incorrect depth: %d vs %d", depth(n), max_pred_depth + 1); n->dump(); } assert(depth(n) == max_pred_depth + 1, "must have correct depth"); } #endif } #ifndef PRODUCT void VLoopDependencyGraph::print() const { tty->print_cr("\nVLoopDependencyGraph::print:"); tty->print_cr(" Memory pred edges:"); for (int i = 0; i < _body.body().length(); i++) { Node* n = _body.body().at(i); const DependencyNode* dn = dependency_node(n); if (dn != nullptr) { tty->print(" DependencyNode[%d %s:", n->_idx, n->Name()); for (uint j = 0; j < dn->memory_pred_edges_length(); j++) { Node* pred = _body.body().at(dn->memory_pred_edge(j)); tty->print(" %d %s", pred->_idx, pred->Name()); } tty->print_cr("]"); } } tty->cr(); tty->print_cr(" Complete dependency graph:"); for (int i = 0; i < _body.body().length(); i++) { Node* n = _body.body().at(i); tty->print(" d%02d Dependencies[%d %s:", depth(n), n->_idx, n->Name()); for (PredsIterator it(*this, n); !it.done(); it.next()) { Node* pred = it.current(); tty->print(" %d %s", pred->_idx, pred->Name()); } tty->print_cr("]"); } } #endif VLoopDependencyGraph::DependencyNode::DependencyNode(MemNode* n, GrowableArray& memory_pred_edges, Arena* arena) : _node(n), _memory_pred_edges_length(memory_pred_edges.length()), _memory_pred_edges(nullptr) { assert(memory_pred_edges.is_nonempty(), "not empty"); uint bytes = memory_pred_edges.length() * sizeof(int); _memory_pred_edges = (int*)arena->Amalloc(bytes); memcpy(_memory_pred_edges, memory_pred_edges.adr_at(0), bytes); } VLoopDependencyGraph::PredsIterator::PredsIterator(const VLoopDependencyGraph& dependency_graph, const Node* node) : _dependency_graph(dependency_graph), _node(node), _dependency_node(dependency_graph.dependency_node(node)), _current(nullptr), _is_current_memory_edge(false), _next_pred(0), _end_pred(node->req()), _next_memory_pred(0), _end_memory_pred((_dependency_node != nullptr) ? _dependency_node->memory_pred_edges_length() : 0) { if (_node->is_Store() || _node->is_Load()) { // Load: address // Store: address, value _next_pred = MemNode::Address; } else { assert(!_node->is_Mem(), "only loads and stores are expected mem nodes"); _next_pred = 1; // skip control } next(); } void VLoopDependencyGraph::PredsIterator::next() { if (_next_pred < _end_pred) { _current = _node->in(_next_pred++); _is_current_memory_edge = false; } else if (_next_memory_pred < _end_memory_pred) { int pred_bb_idx = _dependency_node->memory_pred_edge(_next_memory_pred++); _current = _dependency_graph._body.body().at(pred_bb_idx); _is_current_memory_edge = true; } else { _current = nullptr; // done _is_current_memory_edge = false; } } #ifndef PRODUCT void VPointer::print_on(outputStream* st, bool end_with_cr) const { st->print("VPointer["); if (!is_valid()) { st->print_cr("invalid]"); return; } st->print("size: %2d, %s, ", size(), _mem_pointer.base().is_object() ? "object" : "native"); Node* base = _mem_pointer.base().object_or_native(); tty->print("base(%d %s) + con(%3d) + iv_scale(%3d) * iv + invar(", base->_idx, base->Name(), _mem_pointer.con().value(), _iv_scale); int count = 0; for_each_invar_summand([&] (const MemPointerSummand& s) { if (count > 0) { st->print(" + "); } s.print_on(tty); count++; }); if (count == 0) { st->print("0"); } st->print(")]"); if (end_with_cr) { st->cr(); } } #endif AlignmentSolution* AlignmentSolver::solve() const { DEBUG_ONLY( trace_start_solve(); ) // Out of simplicity: non power-of-2 stride not supported. if (!is_power_of_2(abs(_pre_stride))) { return new EmptyAlignmentSolution("non power-of-2 stride not supported"); } assert(is_power_of_2(abs(_main_stride)), "main_stride is power of 2"); assert(_aw > 0 && is_power_of_2(_aw), "aw must be power of 2"); // Out of simplicity: non power-of-2 iv_scale not supported. if (abs(iv_scale()) == 0 || !is_power_of_2(abs(iv_scale()))) { return new EmptyAlignmentSolution("non power-of-2 iv_scale not supported"); } // We analyze the address of mem_ref. The idea is to disassemble it into a linear // expression, where we can use the constant factors as the basis for ensuring the // alignment of vector memory accesses. // // The Simple form of the address is disassembled by VPointer into: // // adr = base + invar + iv_scale * iv + con // // Where the iv can be written as: // // iv = init + pre_stride * pre_iter + main_stride * main_iter // // init: value before pre-loop // pre_stride: increment per pre-loop iteration // pre_iter: number of pre-loop iterations (adjustable via pre-loop limit) // main_stride: increment per main-loop iteration (= pre_stride * unroll_factor) // main_iter: number of main-loop iterations (main_iter >= 0) // // In the following, we restate the Simple form of the address expression, by first // expanding the iv variable. In a second step, we reshape the expression again, and // state it as a linear expression, consisting of 6 terms. // // Simple form Expansion of iv variable Reshaped with constants Comments for terms // ----------- ------------------------ ----------------------- ------------------ // adr = base = base = base (assume: base % aw = 0) // + invar + invar_factor * var_invar + C_invar * var_invar (term for invariant) // / + iv_scale * init + C_init * var_init (term for variable init) // + iv_scale * iv -> | + iv_scale * pre_stride * pre_iter + C_pre * pre_iter (adjustable pre-loop term) // \ + iv_scale * main_stride * main_iter + C_main * main_iter (main-loop term) // + con + con + C_const (sum of constant terms) // // We describe the 6 terms: // 1) The "base" of the address: // - For heap objects, this is the base of the object, and as such // ObjectAlignmentInBytes (a power of 2) aligned. // - For off-heap / native memory, the "base" has no alignment // gurantees. To ensure alignment we can do either of these: // - Add a runtime check to verify ObjectAlignmentInBytes alignment, // i.e. we can speculatively compile with an alignment assumption. // If we pass the check, we can go into the loop with the alignment // assumption, if we fail we have to trap/deopt or take the other // loop version without alignment assumptions. // - If runtime checks are not possible, then we return an empty // solution, i.e. we do not vectorize the corresponding pack. // // Let us assume we have an object "base", or passed the alignment // runtime check for native "bases", hence we know: // // base % ObjectAlignmentInBytes = 0 // // We defined aw = MIN(vector_width, ObjectAlignmentInBytes), which is // a power of 2. And hence we know that "base" is thus also aw-aligned: // // base % ObjectAlignmentInBytes = 0 ==> base % aw = 0 (BASE_ALIGNED) // // 2) The "C_const" term is the sum of all constant terms. This is "con", // plus "iv_scale * init" if it is constant. // 3) The "C_invar * var_invar" is the factorization of "invar" into a constant // and variable term. If there is no invariant, then "C_invar" is zero. // // invar = C_invar * var_invar (FAC_INVAR) // // 4) The "C_init * var_init" is the factorization of "iv_scale * init" into a // constant and a variable term. If "init" is constant, then "C_init" is // zero, and "C_const" accounts for "init" instead. // // iv_scale * init = C_init * var_init + iv_scale * C_const_init (FAC_INIT) // C_init = (init is constant) ? 0 : iv_scale // C_const_init = (init is constant) ? init : 0 // // 5) The "C_pre * pre_iter" term represents how much the iv is incremented // during the "pre_iter" pre-loop iterations. This term can be adjusted // by changing the pre-loop limit, which defines how many pre-loop iterations // are executed. This allows us to adjust the alignment of the main-loop // memory reference. // 6) The "C_main * main_iter" term represents how much the iv is increased // during "main_iter" main-loop iterations. // For native memory, we must add a runtime-check that "base % ObjectAlignmentInBytes = ", // to ensure (BASE_ALIGNED). If we cannot add this runtime-check, we have no guarantee on // its alignment. if (!_vpointer.mem_pointer().base().is_object() && !_are_speculative_checks_possible) { return new EmptyAlignmentSolution("Cannot add speculative check for native memory alignment."); } // Attribute init (i.e. _init_node) either to C_const or to C_init term. const int C_const_init = _init_node->is_ConI() ? _init_node->as_ConI()->get_int() : 0; const int C_const = _vpointer.con() + C_const_init * iv_scale(); // Set C_invar depending on if invar is present const int C_invar = _vpointer.compute_invar_factor(); const int C_init = _init_node->is_ConI() ? 0 : iv_scale(); const int C_pre = iv_scale() * _pre_stride; const int C_main = iv_scale() * _main_stride; DEBUG_ONLY( trace_reshaped_form(C_const, C_const_init, C_invar, C_init, C_pre, C_main); ) // We must find a pre_iter, such that adr is aw aligned: adr % aw = 0. Note, that we are defining the // modulo operator "%" such that the remainder is always positive, see AlignmentSolution::mod(i, q). // // Since "base % aw = 0" (BASE_ALIGNED), we only need to ensure alignment of the other 5 terms: // // (C_const + C_invar * var_invar + C_init * var_init + C_pre * pre_iter + C_main * main_iter) % aw = 0 (1) // // Alignment must be maintained over all main-loop iterations, i.e. for any main_iter >= 0, we require: // // C_main % aw = 0 (2) // const int C_main_mod_aw = AlignmentSolution::mod(C_main, _aw); DEBUG_ONLY( trace_main_iteration_alignment(C_const, C_invar, C_init, C_pre, C_main, C_main_mod_aw); ) if (C_main_mod_aw != 0) { return new EmptyAlignmentSolution("EQ(2) not satisfied (cannot align across main-loop iterations)"); } // In what follows, we need to show that the C_const, init and invar terms can be aligned by // adjusting the pre-loop iteration count (pre_iter), which is controlled by the pre-loop // limit. // // (C_const + C_invar * var_invar + C_init * var_init + C_pre * pre_iter) % aw = 0 (3) // // We strengthen the constraints by splitting the equation into 3 equations, where we // want to find integer solutions for pre_iter_C_const, pre_iter_C_invar, and // pre_iter_C_init, which means that the C_const, init and invar terms can be aligned // independently: // // (C_const + C_pre * pre_iter_C_const) % aw = 0 (4a) // (C_invar * var_invar + C_pre * pre_iter_C_invar) % aw = 0 (4b) // (C_init * var_init + C_pre * pre_iter_C_init ) % aw = 0 (4c) // // We now prove that (4a, b, c) are sufficient as well as necessary to guarantee (3) // for any runtime value of var_invar and var_init (i.e. for any invar and init). // This tells us that the "strengthening" does not restrict the algorithm more than // necessary. // // Sufficient (i.e (4a, b, c) imply (3)): // // pre_iter = pre_iter_C_const + pre_iter_C_invar + pre_iter_C_init // // Adding up (4a, b, c): // // 0 = ( C_const + C_pre * pre_iter_C_const // + C_invar * var_invar + C_pre * pre_iter_C_invar // + C_init * var_init + C_pre * pre_iter_C_init ) % aw // // = ( C_const + C_invar * var_invar + C_init * var_init // + C_pre * (pre_iter_C_const + pre_iter_C_invar + pre_iter_C_init)) % aw // // = ( C_const + C_invar * var_invar + C_init * var_init // + C_pre * pre_iter) % aw // // Necessary (i.e. (3) implies (4a, b, c)): // (4a): Set var_invar = var_init = 0 at runtime. Applying this to (3), we get: // // 0 = // = (C_const + C_invar * var_invar + C_init * var_init + C_pre * pre_iter) % aw // = (C_const + C_invar * 0 + C_init * 0 + C_pre * pre_iter) % aw // = (C_const + C_pre * pre_iter) % aw // // This is of the same form as (4a), and we have a solution: // pre_iter_C_const = pre_iter // // (4b): Set var_init = 0, and assume (4a), which we just proved is implied by (3). // Subtract (4a) from (3): // // 0 = // = (C_const + C_invar * var_invar + C_init * var_init + C_pre * pre_iter) % aw // - (C_const + C_pre * pre_iter_C_const) % aw // = (C_invar * var_invar + C_init * var_init + C_pre * pre_iter - C_pre * pre_iter_C_const) % aw // = (C_invar * var_invar + C_init * 0 + C_pre * (pre_iter - pre_iter_C_const)) % aw // = (C_invar * var_invar + + C_pre * (pre_iter - pre_iter_C_const)) % aw // // This is of the same form as (4b), and we have a solution: // pre_iter_C_invar = pre_iter - pre_iter_C_const // // (4c): Set var_invar = 0, and assume (4a), which we just proved is implied by (3). // Subtract (4a) from (3): // // 0 = // = (C_const + C_invar * var_invar + C_init * var_init + C_pre * pre_iter) % aw // - (C_const + C_pre * pre_iter_C_const) % aw // = (C_invar * var_invar + C_init * var_init + C_pre * pre_iter - C_pre * pre_iter_C_const) % aw // = (C_invar * 0 + C_init * var_init + C_pre * (pre_iter - pre_iter_C_const)) % aw // = ( + C_init * var_init + C_pre * (pre_iter - pre_iter_C_const)) % aw // // This is of the same form as (4c), and we have a solution: // pre_iter_C_invar = pre_iter - pre_iter_C_const // // The solutions of Equations (4a, b, c) for pre_iter_C_const, pre_iter_C_invar, and pre_iter_C_init // respectively, can have one of these states: // // trivial: The solution can be any integer. // constrained: There is a (periodic) solution, but it is not trivial. // empty: Statically we cannot guarantee a solution for all var_invar and var_init. // // We look at (4a): // // abs(C_pre) >= aw // -> Since abs(C_pre) is a power of two, we have C_pre % aw = 0. Therefore: // // For any pre_iter_C_const: (C_pre * pre_iter_C_const) % aw = 0 // // (C_const + C_pre * pre_iter_C_const) % aw = 0 // C_const % aw = 0 // // Hence, we can only satisfy (4a) if C_Const is aw aligned: // // C_const % aw == 0: // -> (4a) has a trivial solution since we can choose any value for pre_iter_C_const. // // C_const % aw != 0: // -> (4a) has an empty solution since no pre_iter_C_const can achieve aw alignment. // // abs(C_pre) < aw: // -> Since both abs(C_pre) and aw are powers of two, we know: // // There exists integer x > 1: aw = abs(C_pre) * x // // C_const % abs(C_pre) == 0: // -> There exists integer z: C_const = C_pre * z // // (C_const + C_pre * pre_iter_C_const) % aw = 0 // ==> // (C_pre * z + C_pre * pre_iter_C_const) % aw = 0 // ==> // (C_pre * z + C_pre * pre_iter_C_const) % (abs(C_pre) * x) = 0 // ==> // ( z + pre_iter_C_const) % x = 0 // ==> // for any m: pre_iter_C_const = m * x - z // // Hence, pre_iter_C_const has a non-trivial (because x > 1) periodic (periodicity x) // solution, i.e. it has a constrained solution. // // C_const % abs(C_pre) != 0: // There exists integer x > 1: aw = abs(C_pre) * x // // C_const % abs(C_pre) != 0 // ==> // (C_const + C_pre * pre_iter_C_const) % abs(C_pre) != 0 // ==> // (C_const + C_pre * pre_iter_C_const) % (abs(C_pre) * x) != 0 // ==> // (C_const + C_pre * pre_iter_C_const) % aw != 0 // // This is in contradiction with (4a), and therefore there cannot be any solution, // i.e. we have an empty solution. // // In summary, for (4a): // // abs(C_pre) >= aw AND C_const % aw == 0 -> trivial // abs(C_pre) >= aw AND C_const % aw != 0 -> empty // abs(C_pre) < aw AND C_const % abs(C_pre) == 0 -> constrained // abs(C_pre) < aw AND C_const % abs(C_pre) != 0 -> empty // // With analogue argumentation for (4b): // // abs(C_pre) >= aw AND C_invar % aw == 0 -> trivial // abs(C_pre) >= aw AND C_invar % aw != 0 -> empty // abs(C_pre) < aw AND C_invar % abs(C_pre) == 0 -> constrained // abs(C_pre) < aw AND C_invar % abs(C_pre) != 0 -> empty // // With analogue argumentation for (4c): // // abs(C_pre) >= aw AND C_init % aw == 0 -> trivial // abs(C_pre) >= aw AND C_init % aw != 0 -> empty // abs(C_pre) < aw AND C_init % abs(C_pre) == 0 -> constrained // abs(C_pre) < aw AND C_init % abs(C_pre) != 0 -> empty // // Out of these states follows the state for the solution of pre_iter: // // Trivial: If (4a, b, c) are all trivial. // Empty: If any of (4a, b, c) is empty, because then we cannot guarantee a solution // for pre_iter, for all possible invar and init values. // Constrained: Else. Incidentally, (4a, b, c) are all constrained themselves, as we argue below. const EQ4 eq4(C_const, C_invar, C_init, C_pre, _aw); const EQ4::State eq4a_state = eq4.eq4a_state(); const EQ4::State eq4b_state = eq4.eq4b_state(); const EQ4::State eq4c_state = eq4.eq4c_state(); #ifdef ASSERT if (is_trace()) { eq4.trace(); } #endif // If (4a, b, c) are all trivial, then also the solution for pre_iter is trivial: if (eq4a_state == EQ4::State::TRIVIAL && eq4b_state == EQ4::State::TRIVIAL && eq4c_state == EQ4::State::TRIVIAL) { return new TrivialAlignmentSolution(); } // If any of (4a, b, c) is empty, then we also cannot guarantee a solution for pre_iter, for // any init and invar, hence the solution for pre_iter is empty: if (eq4a_state == EQ4::State::EMPTY || eq4b_state == EQ4::State::EMPTY || eq4c_state == EQ4::State::EMPTY) { return new EmptyAlignmentSolution("EQ(4a, b, c) not all non-empty: cannot align const, invar and init terms individually"); } // If abs(C_pre) >= aw, then the solutions to (4a, b, c) are all either trivial or empty, and // hence we would have found the solution to pre_iter above as either trivial or empty. Thus // we now know that: // // abs(C_pre) < aw // assert(abs(C_pre) < _aw, "implied by constrained case"); // And since abs(C_pre) < aw, the solutions of (4a, b, c) can now only be constrained or empty. // But since we already handled the empty case, the solutions are now all constrained. assert(eq4a_state == EQ4::State::CONSTRAINED && eq4a_state == EQ4::State::CONSTRAINED && eq4a_state == EQ4::State::CONSTRAINED, "all must be constrained now"); // And since they are all constrained, we must have: // // C_const % abs(C_pre) = 0 (5a) // C_invar % abs(C_pre) = 0 (5b) // C_init % abs(C_pre) = 0 (5c) // assert(AlignmentSolution::mod(C_const, abs(C_pre)) == 0, "EQ(5a): C_const must be alignable"); assert(AlignmentSolution::mod(C_invar, abs(C_pre)) == 0, "EQ(5b): C_invar must be alignable"); assert(AlignmentSolution::mod(C_init, abs(C_pre)) == 0, "EQ(5c): C_init must be alignable"); // With (5a, b, c), we know that there are integers X, Y, Z: // // C_const = X * abs(C_pre) ==> X = C_const / abs(C_pre) (6a) // C_invar = Y * abs(C_pre) ==> Y = C_invar / abs(C_pre) (6b) // C_init = Z * abs(C_pre) ==> Z = C_init / abs(C_pre) (6c) // // Further, we define: // // sign(C_pre) = C_pre / abs(C_pre) = (C_pre > 0) ? 1 : -1, (7) // // We know that abs(C_pre) as well as aw are powers of 2, and since (5) we can define integer q: // // q = aw / abs(C_pre) (8) // const int q = _aw / abs(C_pre); assert(q >= 2, "implied by constrained solution"); // We now know that all terms in (4a, b, c) are divisible by abs(C_pre): // // (C_const / abs(C_pre) + C_pre * pre_iter_C_const / abs(C_pre)) % (aw / abs(C_pre)) = // (X * abs(C_pre) / abs(C_pre) + C_pre * pre_iter_C_const / abs(C_pre)) % (aw / abs(C_pre)) = // (X + pre_iter_C_const * sign(C_pre)) % q = 0 (9a) // // -> pre_iter_C_const * sign(C_pre) = mx1 * q - X // -> pre_iter_C_const = mx2 * q - sign(C_pre) * X (10a) // (for any integers mx1, mx2) // // (C_invar * var_invar / abs(C_pre) + C_pre * pre_iter_C_invar / abs(C_pre)) % (aw / abs(C_pre)) = // (Y * abs(C_pre) * var_invar / abs(C_pre) + C_pre * pre_iter_C_invar / abs(C_pre)) % (aw / abs(C_pre)) = // (Y * var_invar + pre_iter_C_invar * sign(C_pre)) % q = 0 (9b) // // -> pre_iter_C_invar * sign(C_pre) = my1 * q - Y * var_invar // -> pre_iter_C_invar = my2 * q - sign(C_pre) * Y * var_invar (10b) // (for any integers my1, my2) // // (C_init * var_init / abs(C_pre) + C_pre * pre_iter_C_init / abs(C_pre)) % (aw / abs(C_pre)) = // (Z * abs(C_pre) * var_init / abs(C_pre) + C_pre * pre_iter_C_init / abs(C_pre)) % (aw / abs(C_pre)) = // (Z * var_init + pre_iter_C_init * sign(C_pre)) % q = 0 (9c) // // -> pre_iter_C_init * sign(C_pre) = mz1 * q - Z * var_init // -> pre_iter_C_init = mz2 * q - sign(C_pre) * Z * var_init (10c) // (for any integers mz1, mz2) // // // Having solved the equations using the division, we can re-substitute X, Y, and Z, and apply (FAC_INVAR) as // well as (FAC_INIT). We use the fact that sign(x) == 1 / sign(x) and sign(x) * abs(x) == x: // // pre_iter_C_const = mx2 * q - sign(C_pre) * X // = mx2 * q - sign(C_pre) * C_const / abs(C_pre) // = mx2 * q - C_const / C_pre // = mx2 * q - C_const / (iv_scale * pre_stride) (11a) // // If there is an invariant: // // pre_iter_C_invar = my2 * q - sign(C_pre) * Y * var_invar // = my2 * q - sign(C_pre) * C_invar * var_invar / abs(C_pre) // = my2 * q - sign(C_pre) * invar / abs(C_pre) // = my2 * q - invar / C_pre // = my2 * q - invar / (iv_scale * pre_stride) (11b, with invar) // // If there is no invariant (i.e. C_invar = 0 ==> Y = 0): // // pre_iter_C_invar = my2 * q (11b, no invar) // // If init is variable (i.e. C_init = iv_scale, init = var_init): // // pre_iter_C_init = mz2 * q - sign(C_pre) * Z * var_init // = mz2 * q - sign(C_pre) * C_init * var_init / abs(C_pre) // = mz2 * q - sign(C_pre) * iv_scale * init / abs(C_pre) // = mz2 * q - iv_scale * init / C_pre // = mz2 * q - iv_scale * init / (iv_scale * pre_stride) // = mz2 * q - init / pre_stride (11c, variable init) // // If init is constant (i.e. C_init = 0 ==> Z = 0): // // pre_iter_C_init = mz2 * q (11c, constant init) // // Note, that the solutions found by (11a, b, c) are all periodic with periodicity q. We combine them, // with m = mx2 + my2 + mz2: // // pre_iter = pre_iter_C_const + pre_iter_C_invar + pre_iter_C_init // = mx2 * q - C_const / (iv_scale * pre_stride) // + my2 * q [- invar / (iv_scale * pre_stride) ] // + mz2 * q [- init / pre_stride ] // // = m * q (periodic part) // - C_const / (iv_scale * pre_stride) (align constant term) // [- invar / (iv_scale * pre_stride) ] (align invariant term, if present) // [- init / pre_stride ] (align variable init term, if present) (12) // // We can further simplify this solution by introducing integer 0 <= r < q: // // r = (-C_const / (iv_scale * pre_stride)) % q (13) // const int r = AlignmentSolution::mod(-C_const / (iv_scale() * _pre_stride), q); // // pre_iter = m * q + r // [- invar / (iv_scale * pre_stride) ] // [- init / pre_stride ] (14) // // We thus get a solution that can be stated in terms of: // // q (periodicity), r (constant alignment), invar, iv_scale, pre_stride, init // // However, pre_stride and init are shared by all mem_ref in the loop, hence we do not need to provide // them in the solution description. DEBUG_ONLY( trace_constrained_solution(C_const, C_invar, C_init, C_pre, q, r); ) return new ConstrainedAlignmentSolution(_mem_ref, q, r, _vpointer /* holds invar and iv_scale */); // APPENDIX: // We can now verify the success of the solution given by (12): // // adr % aw = // // -> Simple form // (base + invar + iv_scale * iv + con) % aw = // // -> Expand iv // (base + con + invar + iv_scale * (init + pre_stride * pre_iter + main_stride * main_iter)) % aw = // // -> Reshape // (base + con + invar // + iv_scale * init // + iv_scale * pre_stride * pre_iter // + iv_scale * main_stride * main_iter)) % aw = // // -> apply (BASE_ALIGNED): base % aw = 0 // -> main-loop iterations aligned (2): C_main % aw = (iv_scale * main_stride) % aw = 0 // (con + invar + iv_scale * init + iv_scale * pre_stride * pre_iter) % aw = // // -> apply (12) // (con + invar + iv_scale * init // + iv_scale * pre_stride * (m * q - C_const / (iv_scale * pre_stride) // [- invar / (iv_scale * pre_stride) ] // [- init / pre_stride ] // ) // ) % aw = // // -> expand C_const = con [+ init * iv_scale] (if init const) // (con + invar + iv_scale * init // + iv_scale * pre_stride * (m * q - con / (iv_scale * pre_stride) // [- init / pre_stride ] (if init constant) // [- invar / (iv_scale * pre_stride) ] (if invar present) // [- init / pre_stride ] (if init variable) // ) // ) % aw = // // -> assuming invar = 0 if it is not present // -> merge the two init terms (variable or constant) // -> apply (8): q = aw / (abs(C_pre)) = aw / abs(iv_scale * pre_stride) // -> and hence: (iv_scale * pre_stride * q) % aw = 0 // -> all terms are canceled out // (con + invar + iv_scale * init // + iv_scale * pre_stride * m * q -> aw aligned // - iv_scale * pre_stride * con / (iv_scale * pre_stride) -> = con // - iv_scale * pre_stride * init / pre_stride -> = iv_scale * init // - iv_scale * pre_stride * invar / (iv_scale * pre_stride) -> = invar // ) % aw = 0 // // The solution given by (12) does indeed guarantee alignment. } #ifdef ASSERT void AlignmentSolver::trace_start_solve() const { if (is_trace()) { tty->print(" vector mem_ref:"); _mem_ref->dump(); tty->print(" VPointer: "); _vpointer.print_on(tty); tty->print_cr(" vector_width = %d", _vector_width); tty->print_cr(" aw = alignment_width = min(vector_width(%d), ObjectAlignmentInBytes(%d)) = %d", _vector_width, ObjectAlignmentInBytes, _aw); if (!_init_node->is_ConI()) { tty->print(" init:"); _init_node->dump(); } tty->print_cr(" invar = SUM(invar_summands), invar_summands:"); int invar_count = 0; _vpointer.for_each_invar_summand([&] (const MemPointerSummand& s) { tty->print(" "); s.print_on(tty); tty->print(" -> "); s.variable()->dump(); invar_count++; }); if (invar_count == 0) { tty->print_cr(" No invar_summands."); } const jint invar_factor = _vpointer.compute_invar_factor(); tty->print_cr(" invar_factor = %d", invar_factor); // iv = init + pre_iter * pre_stride + main_iter * main_stride tty->print(" iv = init"); if (_init_node->is_ConI()) { tty->print("(%4d)", _init_node->as_ConI()->get_int()); } else { tty->print("[%4d]", _init_node->_idx); } tty->print_cr(" + pre_iter * pre_stride(%d) + main_iter * main_stride(%d)", _pre_stride, _main_stride); // adr = base + con + invar + iv_scale * iv tty->print(" adr = base[%d]", base().object_or_native()->_idx); tty->print_cr(" + invar + iv_scale(%d) * iv + con(%d)", iv_scale(), _vpointer.con()); } } void AlignmentSolver::trace_reshaped_form(const int C_const, const int C_const_init, const int C_invar, const int C_init, const int C_pre, const int C_main) const { if (is_trace()) { tty->print(" = base[%d] + ", base().object_or_native()->_idx); tty->print_cr("C_const(%d) + C_invar(%d) * var_invar + C_init(%d) * var_init + C_pre(%d) * pre_iter + C_main(%d) * main_iter", C_const, C_invar, C_init, C_pre, C_main); if (_init_node->is_ConI()) { tty->print_cr(" init is constant:"); tty->print_cr(" C_const_init = %d", C_const_init); tty->print_cr(" C_init = %d", C_init); } else { tty->print_cr(" init is variable:"); tty->print_cr(" C_const_init = %d", C_const_init); tty->print_cr(" C_init = abs(iv_scale)= %d", C_init); } if (C_invar != 0) { tty->print_cr(" invariant present:"); tty->print_cr(" C_invar = invar_factor = %d", C_invar); } else { tty->print_cr(" no invariant:"); tty->print_cr(" C_invar = %d", C_invar); } tty->print_cr(" C_const = con(%d) + iv_scale(%d) * C_const_init(%d) = %d", _vpointer.con(), iv_scale(), C_const_init, C_const); tty->print_cr(" C_pre = iv_scale(%d) * pre_stride(%d) = %d", iv_scale(), _pre_stride, C_pre); tty->print_cr(" C_main = iv_scale(%d) * main_stride(%d) = %d", iv_scale(), _main_stride, C_main); } } void AlignmentSolver::trace_main_iteration_alignment(const int C_const, const int C_invar, const int C_init, const int C_pre, const int C_main, const int C_main_mod_aw) const { if (is_trace()) { tty->print(" EQ(1 ): (C_const(%d) + C_invar(%d) * var_invar + C_init(%d) * var_init", C_const, C_invar, C_init); tty->print(" + C_pre(%d) * pre_iter + C_main(%d) * main_iter) %% aw(%d) = 0", C_pre, C_main, _aw); tty->print_cr(" (given base aligned -> align rest)"); tty->print(" EQ(2 ): C_main(%d) %% aw(%d) = %d = 0", C_main, _aw, C_main_mod_aw); tty->print_cr(" (alignment across iterations)"); } } void AlignmentSolver::EQ4::trace() const { tty->print_cr(" EQ(4a): (C_const(%3d) + C_pre(%d) * pre_iter_C_const) %% aw(%d) = 0 (align const term individually)", _C_const, _C_pre, _aw); tty->print_cr(" -> %s", state_to_str(eq4a_state())); tty->print_cr(" EQ(4b): (C_invar(%3d) * var_invar + C_pre(%d) * pre_iter_C_invar) %% aw(%d) = 0 (align invar term individually)", _C_invar, _C_pre, _aw); tty->print_cr(" -> %s", state_to_str(eq4b_state())); tty->print_cr(" EQ(4c): (C_init( %3d) * var_init + C_pre(%d) * pre_iter_C_init ) %% aw(%d) = 0 (align init term individually)", _C_init, _C_pre, _aw); tty->print_cr(" -> %s", state_to_str(eq4c_state())); } void AlignmentSolver::trace_constrained_solution(const int C_const, const int C_invar, const int C_init, const int C_pre, const int q, const int r) const { if (is_trace()) { tty->print_cr(" EQ(4a, b, c) all constrained, hence:"); tty->print_cr(" EQ(5a): C_const(%3d) %% abs(C_pre(%d)) = 0", C_const, C_pre); tty->print_cr(" EQ(5b): C_invar(%3d) %% abs(C_pre(%d)) = 0", C_invar, C_pre); tty->print_cr(" EQ(5c): C_init( %3d) %% abs(C_pre(%d)) = 0", C_init, C_pre); tty->print_cr(" All terms in EQ(4a, b, c) are divisible by abs(C_pre(%d)).", C_pre); const int X = C_const / abs(C_pre); const int Y = C_invar / abs(C_pre); const int Z = C_init / abs(C_pre); const int sign = (C_pre > 0) ? 1 : -1; tty->print_cr(" X = C_const(%3d) / abs(C_pre(%d)) = %d (6a)", C_const, C_pre, X); tty->print_cr(" Y = C_invar(%3d) / abs(C_pre(%d)) = %d (6b)", C_invar, C_pre, Y); tty->print_cr(" Z = C_init( %3d) / abs(C_pre(%d)) = %d (6c)", C_init , C_pre, Z); tty->print_cr(" q = aw( %3d) / abs(C_pre(%d)) = %d (8)", _aw, C_pre, q); tty->print_cr(" sign(C_pre) = (C_pre(%d) > 0) ? 1 : -1 = %d (7)", C_pre, sign); tty->print_cr(" EQ(9a): (X(%3d) + pre_iter_C_const * sign(C_pre)) %% q(%d) = 0", X, q); tty->print_cr(" EQ(9b): (Y(%3d) * var_invar + pre_iter_C_invar * sign(C_pre)) %% q(%d) = 0", Y, q); tty->print_cr(" EQ(9c): (Z(%3d) * var_init + pre_iter_C_init * sign(C_pre)) %% q(%d) = 0", Z, q); tty->print_cr(" EQ(10a): pre_iter_C_const = mx2 * q(%d) - sign(C_pre) * X(%d)", q, X); tty->print_cr(" EQ(10b): pre_iter_C_invar = my2 * q(%d) - sign(C_pre) * Y(%d) * var_invar", q, Y); tty->print_cr(" EQ(10c): pre_iter_C_init = mz2 * q(%d) - sign(C_pre) * Z(%d) * var_init ", q, Z); tty->print_cr(" r = (-C_const(%d) / (iv_scale(%d) * pre_stride(%d)) %% q(%d) = %d", C_const, iv_scale(), _pre_stride, q, r); tty->print_cr(" EQ(14): pre_iter = m * q(%3d) - r(%d)", q, r); if (C_invar != 0) { tty->print_cr(" - invar / (iv_scale(%d) * pre_stride(%d))", iv_scale(), _pre_stride); } if (!_init_node->is_ConI()) { tty->print_cr(" - init / pre_stride(%d)", _pre_stride); } } } #endif