| /* |
| * Copyright (c) 2024, 2025, Oracle and/or its affiliates. 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. |
| * |
| */ |
| |
| #ifndef SHARE_OPTO_MEMPOINTER_HPP |
| #define SHARE_OPTO_MEMPOINTER_HPP |
| |
| #include "opto/memnode.hpp" |
| #include "opto/noOverflowInt.hpp" |
| |
| // The MemPointer is a shared facility to parse pointers and check the aliasing of pointers. |
| // |
| // A MemPointer points to a region in memory, starting at a "pointer", and extending for "size" bytes: |
| // [pointer, pointer + size) |
| // |
| // We can check if two loads / two stores: |
| // - are adjacent -> pack multiple memops into a single memop |
| // - never overlap -> independent, can swap order |
| // |
| // Other use-cases: |
| // - alignment -> find an alignment solution for all memops in a vectorized loop |
| // - detect partial overlap -> indicates store-to-load-forwarding failures |
| // |
| // ----------------------------------------------------------------------------------------- |
| // |
| // Intuition and Examples: |
| // We parse / decompose pointers into a linear form: |
| // |
| // pointer = SUM(scale_i * variable_i) + con |
| // |
| // where SUM() adds all "scale_i * variable_i" for each i together. |
| // |
| // The con and scale_i are compile-time constants (NoOverflowInt), and the variable_i are |
| // compile-time variables (C2 nodes). |
| // |
| // For the MemPointer, we do not explicitly track the base address. For Java heap pointers, the |
| // base address is just a variable in a summand with scale == 1. For native memory (C heap) |
| // pointers, the base address is null, and is hence implicitly a zero constant. |
| // |
| // |
| // Example 1: byte array access: |
| // |
| // array[i] |
| // |
| // pointer = array_base + ARRAY_BYTE_BASE_OFFSET + 1 * i |
| // = 1 * array_base + ARRAY_BYTE_BASE_OFFSET + 1 * i |
| // -------------------- ---------------------- -------------------- |
| // = scale_0 * variable_0 + con + scale_1 * variable_1 |
| // |
| // |
| // Example 2: int array access |
| // |
| // array[5 + i + 3 * j] |
| // |
| // pointer = array_base + ARRAY_INT_BASE_OFFSET + 4 * 5 + 4 * i + 4 * 3 * j |
| // = 1 * array_base + ARRAY_INT_BASE_OFFSET + 20 + 4 * i + 12 * j |
| // -------------------- ----------------------------- -------------------- -------------------- |
| // = scale_0 * variable_0 + con + scale_1 * variable_1 + scale_2 * variable_2 |
| // |
| // |
| // Example 3: Unsafe with int array |
| // |
| // UNSAFE.getInt(array, ARRAY_INT_BASE_OFFSET + 4 * i); |
| // |
| // pointer = array_base + ARRAY_INT_BASE_OFFSET + 4 * i |
| // = 1 * array_base + ARRAY_INT_BASE_OFFSET + 4 * i |
| // -------------------- --------------------- -------------------- |
| // = scale_0 * variable_0 + con + scale_1 * variable_1 |
| // |
| // |
| // Example 4: Unsafe with native memory address |
| // |
| // long address; |
| // UNSAFE.getInt(null, address + 4 * i); |
| // |
| // pointer = address + 4 * i |
| // = 1 * address + 0 + 4 * i |
| // -------------------- --- -------------------- |
| // = scale_0 * variable_0 + con + scale_1 * variable_1 |
| // |
| // |
| // Example 5: MemorySegment with byte array as backing type |
| // |
| // byte[] array = new byte[1000]; |
| // MemorySegment ms = MemorySegment.ofArray(array); |
| // assert ms.heapBase().get() == array: "array is base"; |
| // assert ms.address() == 0: "zero offset from base"; |
| // byte val = ms.get(ValueLayout.JAVA_BYTE, i); |
| // |
| // pointer = ms.heapBase() + ARRAY_BYTE_BASE_OFFSET + ms.address() + i |
| // = 1 * array_base + ARRAY_BYTE_BASE_OFFSET + 0 + 1 * i |
| // ----------------------- ------------------------------------- -------------------- |
| // = scale_0 * variable_0 + con + scale_1 * variable_1 |
| // |
| // |
| // Example 6: MemorySegment with native memory |
| // |
| // MemorySegment ms = Arena.ofAuto().allocate(1000, 1); |
| // assert ms.heapBase().isEmpty(): "null base"; |
| // assert ms.address() != 0: "non-zero native memory address"; |
| // short val = ms.get(ValueLayout.JAVA_SHORT, 2L * i); |
| // |
| // pointer = ms.heapBase() + ms.address() + 2 i |
| // = 0 + 1 * ms.address() + 2 * i |
| // ------------ ---------------------- -------------------- |
| // = con scale_0 * variable_0 + scale_1 * variable_1 |
| // |
| // |
| // Example 7: Non-linear access to int array |
| // |
| // array[5 + i + j * k] |
| // |
| // pointer = array_base + ARRAY_INT_BASE_OFFSET + 4 * 5 + 4 * i + 4 * j * k |
| // = 1 * array_base + ARRAY_INT_BASE_OFFSET + 20 + 4 * i + 4 * j * k |
| // -------------------- ----------------------------- -------------------- -------------------- |
| // = scale_0 * variable_0 + con + scale_1 * variable_1 + scale_2 * variable_2 |
| // |
| // Note: we simply stop parsing once a term is not linear. We keep "j * k" as its own variable. |
| // |
| // |
| // Example 8: Unsafe with native memory address, non-linear access |
| // |
| // UNSAFE.getInt(null, i * j); |
| // |
| // pointer = i * j |
| // = 0 + 1 * i * j |
| // --- -------------------- |
| // = con + scale_0 * variable_0 |
| // |
| // Note: we can always parse a pointer into its trivial linear form: |
| // |
| // pointer = 0 + 1 * pointer. |
| // |
| // ----------------------------------------------------------------------------------------- |
| // |
| // MemPointer: |
| // When the pointer is parsed, it is decomposed into a SUM of summands plus a constant: |
| // |
| // pointer = SUM(summands) + con |
| // |
| // Where each summand_i in summands has the form: |
| // |
| // summand_i = scale_i * variable_i |
| // |
| // Hence, the full decomposed form is: |
| // |
| // pointer = SUM(scale_i * variable_i) + con |
| // |
| // Note: the scale_i are compile-time constants (NoOverflowInt), and the variable_i are |
| // compile-time variables (C2 nodes). |
| // On 64-bit systems, this decomposed form is computed with long-add/mul, on 32-bit systems |
| // it is computed with int-add/mul. |
| // |
| // Any pointer can be parsed into this (default / trivial) decomposed form: |
| // |
| // pointer = 1 * pointer + 0 |
| // scale_0 * variable_0 + con |
| // |
| // However, this is not particularly useful to compute aliasing. We would like to decompose |
| // the pointer as far as possible, i.e. extract as many summands and add up the constants to |
| // a single constant. |
| // |
| // Example (normal int-array access): |
| // pointer1 = array[i + 0] = array_base + array_int_base_offset + 4L * ConvI2L(i + 0) |
| // pointer2 = array[i + 1] = array_base + array_int_base_offset + 4L * ConvI2L(i + 1) |
| // |
| // At first, computing the aliasing is not immediately straight-forward in the general case because |
| // the distance is hidden inside the ConvI2L. We can convert this (with array_int_base_offset = 16) |
| // into these decomposed forms: |
| // |
| // pointer1 = 1L * array_base + 4L * i + 16L |
| // pointer2 = 1L * array_base + 4L * i + 20L |
| // |
| // This allows us to easily see that these two pointers are adjacent (distance = 4). |
| // |
| // Hence, in MemPointerParser::parse, we start with the pointer as a trivial summand. A summand can either |
| // be decomposed further or it is terminal (cannot be decomposed further). We decompose the summands |
| // recursively until all remaining summands are terminal, see MemPointerParser::parse_sub_expression. |
| // This effectively parses the pointer expression recursively. |
| // |
| // MemPointerAliasing: |
| // The decomposed form allows us to determine the aliasing between two pointers easily. For |
| // example, if two pointers are identical, except for their constant: |
| // |
| // pointer1 = SUM(summands) + con1 |
| // pointer2 = SUM(summands) + con2 |
| // |
| // then we can easily compute the distance between the pointers (distance = con2 - con1), |
| // and determine if they are adjacent. |
| // |
| // MemPointer::Base |
| // The MemPointer is decomposed like this: |
| // pointer = SUM(summands) + con |
| // |
| // This is sufficient for simple adjacency checks and we do not need to know if the pointer references |
| // native (off-heap) or object (heap) memory. However, in some cases it is necessary or useful to know |
| // the object base, or the native pointer's base. |
| // |
| // - Object (heap) base (MemPointer::base().is_object()): |
| // Is the base of the Java object, which resides on the Java heap. |
| // Guarantees: |
| // - Always has an alignment of ObjectAlignmentInBytes. |
| // - A MemPointer with a given object base always must point into the memory of that object. Thus, |
| // if we have two pointers with two different bases at runtime, we know the two pointers do not |
| // alias. |
| // |
| // - Native (off-heap) base (MemPointer::base().is_native()): |
| // When we decompose a pointer to native memory, it is at first not clear that there is a base address. |
| // Even if we could know that there is some base address to which we add index offsets, we cannot know |
| // if this reference address points to the beginning of a native memory allocation or into the middle, |
| // or outside it. We also have no guarantee for alignment with such a base address. |
| // |
| // Still: we would like to find such a base if possible, and if two pointers are similar (i.e. have the |
| // same summands), we would like to find the same base. Further, it is reasonable to speculatively |
| // assume that such base addresses are aligned. We performs such a speculative alignment runtime check |
| // in VTransform::add_speculative_alignment_check. |
| // |
| // A base pointer must have scale = 1, and be accepted byMemPointer::is_native_memory_base_candidate. |
| // It can thus be one of these: |
| // (1) CastX2P |
| // This is simply some arbitrary long cast to a pointer. It may be computed as an addition of |
| // multiple long and even int values. In some cases this means that we could have further |
| // decomposed the CastX2P, but at that point it is even harder to tell what should be a good |
| // candidate for a native memory base. |
| // (2) LoadL from field jdk.internal.foreign.NativeMemorySegmentImpl.min |
| // This would be preferable over CastX2P, because it holds the address() of a native |
| // MemorySegment, i.e. we know it points to the beginning of that MemorySegment. |
| // |
| // ----------------------------------------------------------------------------------------- |
| // |
| // We have to be careful on 64-bit systems with ConvI2L: decomposing its input is not |
| // correct in general, overflows may not be preserved in the decomposed form: |
| // |
| // AddI: ConvI2L(a + b) != ConvI2L(a) + ConvI2L(b) |
| // SubI: ConvI2L(a - b) != ConvI2L(a) - ConvI2L(b) |
| // MulI: ConvI2L(a * conI) != ConvI2L(a) * ConvI2L(conI) |
| // LShiftI: ConvI2L(a << conI) != ConvI2L(a) << ConvI2L(conI) |
| // |
| // If we want to prove the correctness of MemPointerAliasing, we need some guarantees, |
| // that the MemPointers adequately represent the underlying pointers, such that we can |
| // compute the aliasing based on the summands and constants. |
| // |
| // ----------------------------------------------------------------------------------------- |
| // |
| // Below, we will formulate a "MemPointer Lemma" that helps us to prove the correctness of |
| // the MemPointerAliasing computations. To prove the "MemPointer Lemma", we need to define |
| // the idea of a "safe decomposition", and then prove that all the decompositions we apply |
| // are such "safe decompositions". |
| // |
| // |
| // Definition: Safe decomposition |
| // Trivial decomposition: |
| // (SAFE0) The trivial decomposition from p to mp_0 = 0 + 1 * p is always safe. |
| // |
| // Non-trivial decomposition: |
| // We decompose summand in: |
| // mp_i = con + summand + SUM(other_summands) |
| // resulting in: +-------------------------+ |
| // mp_{i+1} = con + dec_con + SUM(dec_summands) + SUM(other_summands) |
| // = new_con + SUM(new_summands) |
| // where mp_i means that the original pointer p was decomposed i times. |
| // |
| // We call a non-trivial decomposition safe if either: |
| // (SAFE1) No matter the values of the summand variables: |
| // mp_i = mp_{i+1} |
| // |
| // (SAFE2) The pointer is on an array with a known array_element_size_in_bytes, |
| // and there is an integer x, such that: |
| // mp_i = mp_{i+1} + x * array_element_size_in_bytes * 2^32 |
| // |
| // Note: if "x = 0", we have "mp1 = mp2", and if "x != 0", then mp1 and mp2 |
| // have a distance at least twice as large as the array size, and so |
| // at least one of mp1 or mp2 must be out of bounds of the array. |
| // |
| // MemPointer Lemma: |
| // Given two pointers p1 and p2, and their respective MemPointers mp1 and mp2. |
| // If these conditions hold: |
| // (S0) mp1 and mp2 are constructed only with safe decompositions (SAFE0, SAFE1, SAFE2) |
| // from p1 and p2, respectively. |
| // (S1) Both p1 and p2 are within the bounds of the same memory object. |
| // (S2) The constants do not differ too much: abs(mp1.con - mp2.con) < 2^31. |
| // (S3) All summands of mp1 and mp2 are identical (i.e. only the constants are possibly different). |
| // |
| // then the pointer difference between p1 and p2 is identical to the difference between |
| // mp1 and mp2: |
| // p1 - p2 = mp1 - mp2 |
| // |
| // Note: MemPointer::get_aliasing_with relies on this MemPointer Lemma to prove the correctness of its |
| // aliasing computation between two MemPointers. |
| // |
| // |
| // Note: MemPointerParser::is_safe_to_decompose_op checks that all decompositions we apply are safe. |
| // |
| // |
| // Proof of the "MemPointer Lemma": |
| // Assume (S0-S3) and show that |
| // p1 - p2 = mp1 - mp2 |
| // |
| // We make a case distinction over the types of decompositions used in the construction of mp1 and mp2. |
| // |
| // Trivial Case: Only trivial (SAFE0) decompositions were used: |
| // mp1 = 0 + 1 * p1 = p1 |
| // mp2 = 0 + 1 * p2 = p2 |
| // => |
| // p1 - p2 = mp1 - mp2 |
| // |
| // Unsafe Case: We apply at least one unsafe decomposition: |
| // This is a contradiction to (S0) and we are done. |
| // |
| // Case 1: Only decomposition of type (SAFE0) and (SAFE1) are used: |
| // We make an induction proof over the decompositions from p1 to mp1, starting with |
| // the trivial decomposition (SAFE0): |
| // mp1_0 = 0 + 1 * p1 = p1 |
| // Then for the i-th non-trivial decomposition (SAFE1) we know that |
| // mp1_i = mp1_{i+1} |
| // and hence, after the n-th non-trivial decomposition from p1: |
| // p1 = mp1_0 = mp1_i = mp1_n = mp1 |
| // Analogously, we can prove: |
| // p2 = mp2 |
| // |
| // p1 = mp1 |
| // p2 = mp2 |
| // => |
| // p1 - p2 = mp1 - mp2 |
| // |
| // Case 2: At least one decomposition of type (SAFE2) and no unsafe decomposition is used. |
| // Given we have (SAFE2) decompositions, we know that we are operating on an array of |
| // known array_element_size_in_bytes. We can weaken the guarantees from (SAFE1) |
| // decompositions to the same guarantee as (SAFE2) decompositions. Hence all applied |
| // non-trivial decompositions satisfy: |
| // mp1_i = mp1_{i+1} + x1_i * array_element_size_in_bytes * 2^32 |
| // where x1_i = 0 for (SAFE1) decompositions. |
| // |
| // We make an induction proof over the decompositions from p1 to mp1, starting with |
| // the trivial decomposition (SAFE0): |
| // mp1_0 = 0 + 1 * p1 = p1 |
| // Then for the i-th non-trivial decomposition (SAFE1) or (SAFE2), we know that |
| // mp1_i = mp1_{i+1} + x1_i * array_element_size_in_bytes * 2^32 |
| // and hence, if mp1 was decomposed with n non-trivial decompositions (SAFE1) or (SAFE2) from p1: |
| // p1 = mp1 + x1 * array_element_size_in_bytes * 2^32 |
| // where |
| // x1 = SUM(x1_i) |
| // Analogously, we can prove: |
| // p2 = mp2 + x2 * array_element_size_in_bytes * 2^32 |
| // |
| // And hence, with x = x1 - x2 we have: |
| // p1 - p2 = mp1 - mp2 + x * array_element_size_in_bytes * 2^32 |
| // |
| // If "x = 0", then it follows: |
| // p1 - p2 = mp1 - mp2 |
| // |
| // If "x != 0", then: |
| // abs(p1 - p2) = abs(mp1 - mp2 + x * array_element_size_in_bytes * 2^32) |
| // >= abs(x * array_element_size_in_bytes * 2^32) - abs(mp1 - mp2) |
| // -- apply x != 0 -- |
| // >= array_element_size_in_bytes * 2^32 - abs(mp1 - mp2) |
| // -- apply (S3) -- |
| // = array_element_size_in_bytes * 2^32 - abs(mp1.con - mp2.con) |
| // -- apply (S2) -- |
| // > array_element_size_in_bytes * 2^32 - 2^31 |
| // -- apply array_element_size_in_bytes > 0 -- |
| // >= array_element_size_in_bytes * 2^31 |
| // >= max_possible_array_size_in_bytes |
| // >= array_size_in_bytes |
| // |
| // This shows that p1 and p2 have a distance greater than the array size, and hence at least one of the two |
| // pointers must be out of bounds. This contradicts our assumption (S1) and we are done. |
| |
| #ifndef PRODUCT |
| class TraceMemPointer : public StackObj { |
| private: |
| const bool _is_trace_parsing; |
| const bool _is_trace_aliasing; |
| const bool _is_trace_adjacency; |
| const bool _is_trace_overlap; |
| |
| public: |
| TraceMemPointer(const bool is_trace_parsing, |
| const bool is_trace_aliasing, |
| const bool is_trace_adjacency, |
| const bool is_trace_overlap) : |
| _is_trace_parsing( is_trace_parsing), |
| _is_trace_aliasing( is_trace_aliasing), |
| _is_trace_adjacency(is_trace_adjacency), |
| _is_trace_overlap(is_trace_overlap) |
| {} |
| |
| bool is_trace_parsing() const { return _is_trace_parsing; } |
| bool is_trace_aliasing() const { return _is_trace_aliasing; } |
| bool is_trace_adjacency() const { return _is_trace_adjacency; } |
| bool is_trace_overlap() const { return _is_trace_overlap; } |
| }; |
| #endif |
| |
| // Class to represent aliasing between two MemPointer. |
| class MemPointerAliasing { |
| private: |
| enum Aliasing { |
| Unknown, // Distance unknown. |
| // Example: two "int[]" (unknown if the same) with different variable index offsets: |
| // e.g. "array[i] vs array[j]". |
| // e.g. "array1[i] vs array2[j]". |
| AlwaysAtDistance, // Constant distance = p2 - p1. |
| // Example: The same address expression, except for a constant offset: |
| // e.g. "array[i] vs array[i+1]". |
| NotOrAtDistance}; // At compile-time, we know that at run-time it is either of these: |
| // (1) Not: The pointers belong to different memory objects. Distance unknown. |
| // (2) AtConstDistance: distance = p2 - p1. |
| // Example: two "int[]" (unknown if the same) with indices that only differ by a |
| // constant offset: |
| // e.g. "array1[i] vs array2[i+4]": |
| // if "array1 == array2": distance = 4. |
| // if "array1 != array2": different memory objects. |
| const Aliasing _aliasing; |
| const jint _distance; |
| |
| MemPointerAliasing(const Aliasing aliasing, const jint distance) : |
| _aliasing(aliasing), |
| _distance(distance) |
| { |
| assert(_distance != min_jint, "given by condition (S3) of MemPointer Lemma"); |
| } |
| |
| public: |
| static MemPointerAliasing make_unknown() { |
| return MemPointerAliasing(Unknown, 0); |
| } |
| |
| static MemPointerAliasing make_always_at_distance(const jint distance) { |
| return MemPointerAliasing(AlwaysAtDistance, distance); |
| } |
| |
| static MemPointerAliasing make_not_or_at_distance(const jint distance) { |
| return MemPointerAliasing(NotOrAtDistance, distance); |
| } |
| |
| // Use case: exact aliasing and adjacency. |
| bool is_always_at_distance(const jint distance) const { |
| return _aliasing == AlwaysAtDistance && _distance == distance; |
| } |
| |
| // Use case: overlap. |
| // Note: the bounds are exclusive: lo < element < hi |
| bool is_never_in_distance_range(const jint distance_lo, const jint distance_hi) const { |
| return (_aliasing == AlwaysAtDistance || _aliasing == NotOrAtDistance) && |
| (_distance <= distance_lo || distance_hi <= _distance); |
| } |
| |
| #ifndef PRODUCT |
| void print_on(outputStream* st) const { |
| switch(_aliasing) { |
| case Unknown: st->print("Unknown"); break; |
| case AlwaysAtDistance: st->print("AlwaysAtDistance(%d)", _distance); break; |
| case NotOrAtDistance: st->print("NotOrAtDistance(%d)", _distance); break; |
| default: ShouldNotReachHere(); |
| } |
| } |
| #endif |
| }; |
| |
| // Summand of a MemPointer: |
| // |
| // summand = scale * variable |
| // |
| // where variable is a C2 node. |
| class MemPointerSummand : public StackObj { |
| private: |
| Node* _variable; |
| NoOverflowInt _scale; |
| |
| public: |
| MemPointerSummand() : |
| _variable(nullptr), |
| _scale(NoOverflowInt::make_NaN()) {} |
| MemPointerSummand(Node* variable, const NoOverflowInt& scale) : |
| _variable(variable), |
| _scale(scale) |
| { |
| assert(_variable != nullptr, "must have variable"); |
| assert(!_scale.is_zero(), "non-zero scale"); |
| } |
| |
| Node* variable() const { return _variable; } |
| NoOverflowInt scale() const { return _scale; } |
| |
| static int cmp_by_variable_idx(MemPointerSummand* p1, MemPointerSummand* p2) { |
| return cmp_by_variable_idx(*p1, *p2); |
| } |
| |
| static int cmp_by_variable_idx(const MemPointerSummand& p1, const MemPointerSummand& p2) { |
| if (p1.variable() == nullptr) { |
| return (p2.variable() == nullptr) ? 0 : 1; |
| } |
| if (p2.variable() == nullptr) { |
| return -1; |
| } |
| return p1.variable()->_idx - p2.variable()->_idx; |
| } |
| |
| static int cmp(const MemPointerSummand& p1, const MemPointerSummand& p2) { |
| int cmp = cmp_by_variable_idx(p1, p2); |
| if (cmp != 0) { return cmp; } |
| |
| return NoOverflowInt::cmp(p1.scale(), p2.scale()); |
| } |
| |
| friend bool operator==(const MemPointerSummand a, const MemPointerSummand b) { |
| // Both "null" -> equal. |
| if (a.variable() == nullptr && b.variable() == nullptr) { return true; } |
| |
| // Same variable and scale? |
| if (a.variable() != b.variable()) { return false; } |
| return a.scale() == b.scale(); |
| } |
| |
| friend bool operator!=(const MemPointerSummand a, const MemPointerSummand b) { |
| return !(a == b); |
| } |
| |
| #ifndef PRODUCT |
| void print_on(outputStream* st) const { |
| _scale.print_on(st); |
| tty->print(" * [%d %s]", _variable->_idx, _variable->Name()); |
| } |
| #endif |
| }; |
| |
| // Parsing calls the callback on every decomposed node. These are all the |
| // nodes on the paths from the pointer to the summand variables, i.e. the |
| // "inner" nodes of the pointer expression. This callback is for example |
| // used in SuperWord::unrolling_analysis to collect all inner nodes of a |
| // pointer expression. |
| class MemPointerParserCallback : public StackObj { |
| private: |
| static MemPointerParserCallback _empty; |
| |
| public: |
| virtual void callback(Node* n) { /* do nothing by default */ } |
| |
| // Singleton for default arguments. |
| static MemPointerParserCallback& empty() { return _empty; } |
| }; |
| |
| // A MemPointer points to a region in memory, starting at a "pointer", and extending |
| // for "size" bytes: |
| // |
| // [pointer, pointer + size) |
| // |
| // Where the "pointer" is decomposed into the following form: |
| // |
| // pointer = SUM(summands) + con |
| // pointer = SUM(scale_i * variable_i) + con |
| // |
| // Where SUM() adds all "scale_i * variable_i" for each i together. |
| // |
| // Note: if the base is known, then it is in the 0th summand. A base can be: |
| // - on-heap / object: base().object() |
| // - off-heap / native: base().native() |
| // |
| // pointer = scale_0 * variable_0 + scale_1 * scale_1 + ... + con |
| // pointer = 1 * base + scale_1 * scale_1 + ... + con |
| // |
| class MemPointer : public StackObj { |
| public: |
| // We limit the number of summands to 10. This is just a best guess, and not at this |
| // point supported by evidence. But I think it is reasonable: usually, a pointer |
| // contains a base pointer (e.g. array pointer or null for native memory) and a few |
| // variables. It should be rare that we have more than 9 variables. |
| static const int SUMMANDS_SIZE = 10; |
| |
| // A base can be: |
| // - Known: |
| // - On-heap: Object |
| // - Off-heap: Native |
| // - Unknown |
| class Base : public StackObj { |
| private: |
| enum Kind { Unknown, Object, Native }; |
| Kind _kind; |
| Node* _base; |
| |
| Base(Kind kind, Node* base) : _kind(kind), _base(base) { |
| assert((kind == Unknown) == (base == nullptr), "known base"); |
| } |
| |
| public: |
| Base() : Base(Unknown, nullptr) {} |
| static Base make(Node* pointer, const GrowableArray<MemPointerSummand>& summands); |
| |
| bool is_known() const { return _kind != Unknown; } |
| bool is_object() const { return _kind == Object; } |
| bool is_native() const { return _kind == Native; } |
| Node* object() const { assert(is_object(), "unexpected kind"); return _base; } |
| Node* native() const { assert(is_native(), "unexpected kind"); return _base; } |
| Node* object_or_native() const { assert(is_known(), "unexpected kind"); return _base; } |
| Node* object_or_native_or_null() const { return _base; } |
| |
| #ifndef PRODUCT |
| void print_on(outputStream* st) const { |
| switch (_kind) { |
| case Object: |
| st->print("object "); |
| st->print("%d %s", _base->_idx, _base->Name()); |
| break; |
| case Native: |
| st->print("native "); |
| st->print("%d %s", _base->_idx, _base->Name()); |
| break; |
| default: |
| st->print("unknown "); |
| }; |
| } |
| #endif |
| |
| private: |
| static Node* find_base(Node* object_base, const GrowableArray<MemPointerSummand>& summands); |
| }; |
| |
| private: |
| MemPointerSummand _summands[SUMMANDS_SIZE]; |
| const NoOverflowInt _con; |
| const Base _base; |
| const jint _size; |
| NOT_PRODUCT( const TraceMemPointer& _trace; ) |
| |
| // Default / trivial: pointer = 0 + 1 * pointer |
| MemPointer(Node* pointer, |
| const jint size |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)) : |
| _con(NoOverflowInt(0)), |
| _base(Base()), |
| _size(size) |
| NOT_PRODUCT(COMMA _trace(trace)) |
| { |
| assert(pointer != nullptr, "pointer must be non-null"); |
| _summands[0] = MemPointerSummand(pointer, NoOverflowInt(1)); |
| assert(1 <= _size && _size <= 2048 && is_power_of_2(_size), "sanity: no vector is expected to be larger"); |
| } |
| |
| // pointer = SUM(SUMMANDS) + con |
| MemPointer(Node* pointer, |
| const GrowableArray<MemPointerSummand>& summands, |
| const NoOverflowInt& con, |
| const jint size |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)) : |
| _con(con), |
| _base(Base::make(pointer, summands)), |
| _size(size) |
| NOT_PRODUCT(COMMA _trace(trace)) |
| { |
| assert(!_con.is_NaN(), "non-NaN constant"); |
| assert(summands.length() <= SUMMANDS_SIZE, "summands must fit"); |
| #ifdef ASSERT |
| for (int i = 0; i < summands.length(); i++) { |
| const MemPointerSummand& s = summands.at(i); |
| assert(s.variable() != nullptr, "variable cannot be null"); |
| assert(!s.scale().is_NaN(), "non-NaN scale"); |
| } |
| #endif |
| |
| // Put the base in the 0th summand. |
| Node* base = _base.object_or_native_or_null(); |
| int pos = 0; |
| if (base != nullptr) { |
| MemPointerSummand b(base, NoOverflowInt(1)); |
| _summands[0] = b; |
| pos++; |
| } |
| // Put all other summands afterward. |
| for (int i = 0; i < summands.length(); i++) { |
| const MemPointerSummand& s = summands.at(i); |
| if (s.variable() == base && s.scale().is_one()) { continue; } |
| _summands[pos++] = summands.at(i); |
| } |
| assert(pos == summands.length(), "copied all summands"); |
| |
| assert(1 <= _size && _size <= 2048 && is_power_of_2(_size), "sanity: no vector is expected to be larger"); |
| } |
| |
| // Mutated copy. |
| // The new MemPointer is identical, except it has a different size and con. |
| MemPointer(const MemPointer& old, |
| const NoOverflowInt new_con, |
| const jint new_size) : |
| _con(new_con), |
| _base(old.base()), |
| _size(new_size) |
| NOT_PRODUCT(COMMA _trace(old._trace)) |
| { |
| assert(!_con.is_NaN(), "non-NaN constant"); |
| for (int i = 0; i < SUMMANDS_SIZE; i++) { |
| _summands[i] = old.summands_at(i); |
| } |
| } |
| |
| public: |
| // Parse pointer of MemNode. Delegates to MemPointerParser::parse. |
| // callback: receives a callback for every decomposed (inner) node |
| // of the pointer expression. |
| MemPointer(const MemNode* mem, |
| MemPointerParserCallback& callback |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)); |
| |
| // Parse pointer of MemNode. Delegates to MemPointerParser::parse. |
| MemPointer(const MemNode* mem |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)) : |
| MemPointer(mem, MemPointerParserCallback::empty() NOT_PRODUCT(COMMA trace)) {} |
| |
| static MemPointer make_trivial(Node* pointer, |
| const jint size |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)) { |
| return MemPointer(pointer, size NOT_PRODUCT(COMMA trace)); |
| } |
| |
| static MemPointer make(Node* pointer, |
| const GrowableArray<MemPointerSummand>& summands, |
| const NoOverflowInt& con, |
| const jint size |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)) { |
| if (summands.length() <= SUMMANDS_SIZE) { |
| return MemPointer(pointer, summands, con, size NOT_PRODUCT(COMMA trace)); |
| } else { |
| return MemPointer::make_trivial(pointer, size NOT_PRODUCT(COMMA trace)); |
| } |
| } |
| |
| MemPointer make_with_size(const jint new_size) const { |
| return MemPointer(*this, this->con(), new_size); |
| }; |
| |
| MemPointer make_with_con(const NoOverflowInt new_con) const { |
| return MemPointer(*this, new_con, this->size()); |
| }; |
| |
| private: |
| MemPointerAliasing get_aliasing_with(const MemPointer& other |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)) const; |
| |
| bool has_same_summands_as(const MemPointer& other, uint start) const; |
| bool has_same_summands_as(const MemPointer& other) const { return has_same_summands_as(other, 0); } |
| bool has_different_object_base_but_otherwise_same_summands_as(const MemPointer& other) const; |
| |
| public: |
| bool has_same_non_base_summands_as(const MemPointer& other) const { |
| if (!base().is_known() || !other.base().is_known()) { |
| assert(false, "unknown base case is not answered optimally"); |
| return false; |
| } |
| // Known base at 0th summand: all other summands are non-base summands. |
| return has_same_summands_as(other, 1); |
| } |
| |
| const MemPointerSummand& summands_at(const uint i) const { |
| assert(i < SUMMANDS_SIZE, "in bounds"); |
| return _summands[i]; |
| } |
| |
| const NoOverflowInt con() const { return _con; } |
| const Base& base() const { return _base; } |
| jint size() const { return _size; } |
| |
| static int cmp_summands(const MemPointer& a, const MemPointer& b) { |
| for (int i = 0; i < SUMMANDS_SIZE; i++) { |
| const MemPointerSummand& s_a = a.summands_at(i); |
| const MemPointerSummand& s_b = b.summands_at(i); |
| int cmp = MemPointerSummand::cmp(s_a, s_b); |
| if (cmp != 0) { return cmp;} |
| } |
| return 0; |
| } |
| |
| template<typename Callback> |
| void for_each_non_empty_summand(Callback callback) const { |
| for (int i = 0; i < SUMMANDS_SIZE; i++) { |
| const MemPointerSummand& s = summands_at(i); |
| if (s.variable() != nullptr) { |
| callback(s); |
| } |
| } |
| } |
| |
| bool is_adjacent_to_and_before(const MemPointer& other) const; |
| bool never_overlaps_with(const MemPointer& other) const; |
| |
| #ifndef PRODUCT |
| void print_form_on(outputStream* st) const { |
| if (_con.is_NaN()) { |
| st->print_cr("empty"); |
| return; |
| } |
| _con.print_on(st); |
| for (int i = 0; i < SUMMANDS_SIZE; i++) { |
| const MemPointerSummand& summand = _summands[i]; |
| if (summand.variable() != nullptr) { |
| st->print(" + "); |
| summand.print_on(st); |
| } |
| } |
| } |
| |
| void print_on(outputStream* st, bool end_with_cr = true) const { |
| st->print("MemPointer[size: %2d, base: ", size()); |
| _base.print_on(st); |
| st->print(", form: "); |
| print_form_on(st); |
| st->print("]"); |
| if (end_with_cr) { st->cr(); } |
| } |
| #endif |
| }; |
| |
| // Utility class. |
| // MemPointerParser::parse takes a MemNode (load or store) and computes its MemPointer. |
| // It temporarily allocates dynamic data structures (GrowableArray) in the resource |
| // area. This way, the computed MemPointer does not have to have any dynamic data |
| // structures and can be copied freely by value. |
| class MemPointerParser : public StackObj { |
| private: |
| const MemNode* _mem; |
| |
| // Internal data-structures for parsing. |
| NoOverflowInt _con; |
| GrowableArray<MemPointerSummand> _worklist; |
| GrowableArray<MemPointerSummand> _summands; |
| |
| // Resulting decomposed-form. |
| MemPointer _mem_pointer; |
| |
| MemPointerParser(const MemNode* mem, |
| MemPointerParserCallback& callback |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)) : |
| _mem(mem), |
| _con(NoOverflowInt(0)), |
| _mem_pointer(parse(callback NOT_PRODUCT(COMMA trace))) {} |
| |
| public: |
| static MemPointer parse(const MemNode* mem, |
| MemPointerParserCallback& callback |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)) { |
| assert(mem->is_Store() || mem->is_Load(), "only stores and loads are allowed"); |
| ResourceMark rm; |
| MemPointerParser parser(mem, callback NOT_PRODUCT(COMMA trace)); |
| |
| #ifndef PRODUCT |
| if (trace.is_trace_parsing()) { |
| tty->print_cr("\nMemPointerParser::parse:"); |
| tty->print(" mem: "); mem->dump(); |
| parser.mem_pointer().print_on(tty); |
| mem->in(MemNode::Address)->dump_bfs(7, nullptr, "d"); |
| } |
| #endif |
| |
| return parser.mem_pointer(); |
| } |
| |
| static bool is_native_memory_base_candidate(Node* n); |
| |
| private: |
| const MemPointer& mem_pointer() const { return _mem_pointer; } |
| |
| MemPointer parse(MemPointerParserCallback& callback |
| NOT_PRODUCT(COMMA const TraceMemPointer& trace)); |
| |
| void parse_sub_expression(const MemPointerSummand& summand, MemPointerParserCallback& callback); |
| static bool sub_expression_has_native_base_candidate(Node* n); |
| |
| bool is_safe_to_decompose_op(const int opc, const NoOverflowInt& scale) const; |
| }; |
| |
| #endif // SHARE_OPTO_MEMPOINTER_HPP |
