/*
 * 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
//
// A more advanced use case of MemPointers is speculative aliasing analysis. If we can prove that
// the MemPointer has a linear form in the loop induction variable (iv), we can formulate runtime
// checks to establish that two MemPointer never overlap for all iterations, i.e. for all iv values.
//
// -----------------------------------------------------------------------------------------
//
// 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 MemPointerSummand 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".
//
//   Even further down, we prove the "MemPointer Linearity Corrolary", where we show that
//   (under reasonable restrictions) both the MemPointer and the corresponding pointer
//   can be considered linear functions.
//
//
// 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.
//
//
// Having proven the "MemPointer Lemma", we can now derive an interesting corrolary.
//
// With the "Linearity Corrolary" below, we can prove that some MemPointers can be treated as
// linear in some summand variable v over some range r. This is useful when MemPointers are
// used in loops, where v=iv scale_v=scale_iv and the range is the iv range from some initial
// iv value to the last iv value just before the limit.
// For an application, see: VPointer::make_speculative_aliasing_check_with
//
// MemPointer Linearity Corrolary:
//   Given:
//     (C0) pointer p and its MemPointer mp, which is constructed with safe decompositions.
//     (C1) a specific summand "scale_v * v" that occurs in mp.
//     (C2) a strided range r = [lo, lo + stride_v, .. hi] for v (lo and hi are inclusive in the range).
//     (C3) for all v in this strided range r we know that p is within bounds of its memory object.
//     (C4) abs(scale_v * stride_v) < 2^31
//            Required for (S2) in application of MemPointer Lemma below, it is essencial in
//            establishing linearity of mp.
//
//   Then:
//     Both p and mp have a linear form for v in r:
//       p(v)  = p(lo)  - lo * scale_v + v * scale_v              (Corrolary P)
//       mp(v) = mp(lo) - lo * scale_v + v * scale_v              (Corrolary MP)
//
//     Note: the calculations are done in long, and hence there can be no int overflow.
//           Thus, p(v) and mp(v) can be considered linear functions for v in r.
//
//   It can be useful to "anchor" at hi instead of lo:
//     p(hi) = p(lo) - lo * scale_v + hi * scale_v
//
//     p(v) = p(lo) - lo * scale_v + v * scale_v
//            --------------------
//          = p(hi) - hi * scale_v + v * scale_v             (Alternative Corrolary P)
//
//
// Proof of "MemPointer Linearity Corrolary":
//   We state the form of mp:
//
//     mp = summand_rest + scale_v * v + con
//
//   We prove the Corrolary by induction over v:
//   Base Case: v = lo
//     p(lo)  = p(lo)  - lo * scale_v + lo * scale_v
//     mp(lo) = mp(lo) - lo * scale_v + lo * scale_v
//
//   Step Case: v0 and v1 in r, v1 = v0 + stride_v
//     Assume:
//       p(v0)  = p(lo)  - lo * scale_v + v * scale_v          (Induction Hypothesis IH-P)
//       mp(v0) = mp(lo) - lo * scale_v + v * scale_v          (Induction Hypothesis IH-MP)
//
//     We take the form of mp, and further apply SAFE1 decompositions, i.e. long addition,
//     subtraction and multiplication:
//       mp(v1) = summand_rest + scale_v * v1                                   + con
//              = summand_rest + scale_v * (v0 + stride_v)                      + con
//              = summand_rest + scale_v * v0              + scale_v * stride_v + con
//              = mp(v0)                                   + scale_v * stride_v
//
//     From this it follows that we can see mp(v0) and mp(v1) as two MemPointer with the
//     same summands, and only their constants differ by exactly "scale_v * stride_v":
//       mp(v0) = summand_rest + scale_v * v0 + con
//       mp(v1) = summand_rest + scale_v * v0 + con + scale_v * stride_v            (MP-DIFF)
//
//     We continue by applying the Induction Hypothesis IH-MP
//       mp(v1) = mp(v0)                                + scale_v * stride_v
//                -------- apply (IH-MP) -------------
//              = mp(lo) - lo * scale_v + v0 * scale_v  + scale_v * stride_v
//              = mp(lo) - lo * scale_v + (v0 + stride_v) * scale_v
//              = mp(lo) - lo * scale_v + v1 * scale_v
//
//     This proves the Corrolary MP.
//
//     To prove the Corrolary P, we now apply the MemPointer Lemma:
//       (S0) Let p(v0) and p(v1) be the pointers corresponding to v0 and v1, and mp(v0) and mp(v1)
//            their MemPointer. (C0) provides the safe deconstruction, and reformulation of terms
//            happens with long addition, subtraction and multiplication only, and is hence SAFE
//            as well.
//       (S1) According to (C3), p is in bounds of its memory object for all v in r. Since v0 and
//            v1 are in r, it follows that p(v0) and p(v1) are in bounds of the same memory object.
//       (S2) The difference of constants of mp(v0) and mp(v1) is exactly "scale_v * stride_v" (MP-DIFF).
//            Given (C4), this difference is not too large.
//       (S3) All summands of mp0 and mp1 are the same (only the constants differ), given (MP-DIFF).
//
//     It follows:
//       p(v1) - p(v0) = mp(v1) - mp(v0)
//
//     Reformulating and applying (MP-DIFF) and (IH-P):
//       p(v1) = p(v0)                                  + mp(v1) - mp(v1)
//                                                        apply (MP-DIFF)
//             = p(v0)                                  + scale_v * stride_v
//               ------------ apply (IH-P) ------------
//             = p(lo) - lo * scale_v + v0 * scale_v    + scale_v * stride_v
//             = p(lo) - lo * scale_v + (v0 + stride_v) * scale_v
//             = p(lo) - lo * scale_v + v1 * scale_v
//
//     This proves Corrolary P.
//
#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);
  }

  // Use case: overlap.
  // Note: the bounds are exclusive: lo < element < hi
  bool is_always_in_distance_range(const jint distance_lo, const jint distance_hi) const {
    return _aliasing == AlwaysAtDistance &&
           (distance_lo < _distance && _distance < distance_hi);
  }

#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);
    st->print(" * [%d %s]", _variable->_idx, _variable->Name());
  }

  static void print_on(outputStream* st, NoOverflowInt con, const GrowableArray<MemPointerSummand>& summands) {
    st->print("Summands (%d): con(", summands.length());
    con.print_on(st);
    st->print(")");
    for (int i = 0; i < summands.length(); i++) {
      st->print(" + ");
      summands.at(i).print_on(tty);
    }
    st->cr();
  }
#endif
};

// We need two different ways of tracking the summands:
// - MemPointerRawSummand: designed to keep track of the original form of
//                         the pointer, preserving its overflow behavior.
// - MemPointerSummand:    designed to allow simplification of the MemPointer
//                         form, does not preserve the original form and
//                         ignores overflow from ConvI2L.
//
// The MemPointerSummand is designed to allow the simplification of
// the MemPointer form as much as possible, to allow aliasing checks
// to be as simple as possible. For example, the C2 IR pointer:
//
//   pointer = AddP(
//               AddP(
//                 base,
//                 LShiftL(
//                   ConvI2L(
//                     AddI(AddI(i, LShiftI(j, 2)), con1)
//                   ),
//                   1
//                 )
//               ),
//               con2
//             )
//
// and more readable:
//
//   pointer = base + 2L * ConvI2L(i + 4 * j + con1) + con2
//
// is simplified to this MemPointer form, using only MemPointerSummands,
// which ignore the possible overflow in ConvI2L:
//
//   pointer = base + 2L * ConvI2L(i) + 8L * ConvI2L(j) + con
//   con = 2L * con1 + con2
//
// This is really convenient, because this way we are able to ignore
// the ConvI2L in the aliasing anaylsis computation, and we can collect
// all constants to a single constant. Even with this simplicication,
// we are able to prove the correctness of the aliasing checks.
//
// However, there is one thing we are not able to do with this simplification:
// we cannot reconstruct the original pointer expression, because the
// simplification ignores overflows that could happen inside the ConvI2L:
//
//   2L * ConvI2L(i + 4 * j + con1) != 2L * ConvI2L(i) + 8L * ConvI2L(j) + 2L * con1
//
// The MemPointerRawSummand is designed to keep track of the original form
// of the pointer, preserving its overflow behaviour. We observe that the
// only critical point for overflows is at the ConvI2L. Thus, we give each
// ConvI2L a "int group" id > 0, and all raw summands belonging to that ConvI2L
// have that id. This allows us to reconstruct which raw summands need to
// be added together before the ConvI2L. Any raw summands that do not belong
// to a ConvI2L (i.e. the summands with long variables) have "int group"
// id = 0, since they do not belong to any such "int group" and can be
// directly added together. For raw summands belonging to an "int group",
// we need to track the scale inside (scaleI) and outside (scaleL) the
// ConvI2L. With the example from above:
//
//   pointer = base + 2L * ConvI2L(i + 4 * j + con1) + con2
//
//   _variable  = base  _variable  = i  _variable  = j  _variable  = null  _variable  = null
//   _scaleI    = 1     _scaleI    = 1  _scaleI    = 4  _scaleI    = con1  _scaleI    = 1
//   _scaleL    = 1     _scaleL    = 2  _scaleL    = 2  _scaleL    = 2     _scaleL    = con2
//   _int_group = 0     _int_group = 1  _int_group = 1  _int_group = 1     _int_group = 0
//
// Note: we also need to track constants as separate raw summands. For
//       this, we say that a raw summand tracks a constant iff _variable == null,
//       and we store the constant value in _scaleI (for int constant) and in
//       _scaleL (for long constants).
//
class MemPointerRawSummand : public StackObj {
private:
  Node* _variable;
  NoOverflowInt _scaleI;
  NoOverflowInt _scaleL;
  int _int_group;

public:
  MemPointerRawSummand(Node* variable, NoOverflowInt scaleI, NoOverflowInt scaleL, int int_group) :
    _variable(variable), _scaleI(scaleI), _scaleL(scaleL), _int_group(int_group) {}

  MemPointerRawSummand() :
    MemPointerRawSummand(nullptr, NoOverflowInt::make_NaN(), NoOverflowInt::make_NaN(), -1) {}

  static MemPointerRawSummand make_trivial(Node* variable) {
    assert(variable != nullptr, "must have variable");
    return MemPointerRawSummand(variable, NoOverflowInt(1), NoOverflowInt(1), 0);
  }

  static MemPointerRawSummand make_con(NoOverflowInt scaleI, NoOverflowInt scaleL, int int_group) {
    return MemPointerRawSummand(nullptr, scaleI, scaleL, int_group);
  }

  bool is_valid() const { return _int_group >= 0; }
  bool is_con() const { assert(is_valid(), ""); return _variable == nullptr; }
  Node* variable() const { assert(is_valid(), ""); return _variable; }
  NoOverflowInt scaleI() const { assert(is_valid(), ""); return _scaleI; }
  NoOverflowInt scaleL() const { assert(is_valid(), ""); return _scaleL; }
  int int_group() const { assert(is_valid(), ""); return _int_group; }

  MemPointerSummand to_summand() const {
    assert(!is_con(), "must be variable");
    return MemPointerSummand(variable(), scaleL() * scaleI());
  }

  NoOverflowInt to_con() const {
    assert(is_con(), "must be constant");
    return scaleL() * scaleI();
  }

  static int cmp_by_int_group_and_variable_idx(MemPointerRawSummand* p1, MemPointerRawSummand* p2) {
    int int_group_diff = p1->int_group() - p2->int_group();
    if (int_group_diff != 0) { return int_group_diff; }

    if (p1->is_con()) {
      return p2->is_con() ? 0 : 1;
    }
    if (p2->is_con()) {
      return -1;
    }
    return p1->variable()->_idx - p2->variable()->_idx;
  }

#ifndef PRODUCT
  void print_on(outputStream* st) const {
    if (!is_valid()) {
      st->print("<invalid>");
    } else {
      st->print("<%d: ", _int_group);
      _scaleL.print_on(st);
      st->print(" * ");
      _scaleI.print_on(st);
      if (!is_con()) {
        st->print(" * [%d %s]", _variable->_idx, _variable->Name());
      }
      st->print(">");
    }
  }

  static void print_on(outputStream* st, const GrowableArray<MemPointerRawSummand>& summands) {
    st->print("Raw Summands (%d): ", summands.length());
    for (int i = 0; i < summands.length(); i++) {
      if (i > 0) { st->print(" + "); }
      summands.at(i).print_on(tty);
    }
    st->cr();
  }
#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, and the raw summands to 16. 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. We need
  // a few more raw summands, especially because there can be multiple constants, one
  // per ConvI2L "int group".
  static const int RAW_SUMMANDS_SIZE = 16;
  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:
  // Raw summands: represent the pointer form exactly, allowing the reconstruction of the
  //               pointer expression. Overflows inside the "int groups" (i.e. ConvI2L)
  //               are preserved, and there may be multiple constants.
  MemPointerRawSummand _raw_summands[RAW_SUMMANDS_SIZE];

  // Summands:     Simplified form, with only a single constant. Makes aliasing analysis
  //               much simpler.
  MemPointerSummand _summands[SUMMANDS_SIZE];
  const NoOverflowInt _con;
  const Base _base;

  // Size in bytes for the referenced memory region: [pointer, pointer + size)
  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<MemPointerRawSummand>& raw_summands,
             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");
    assert(raw_summands.length() <= RAW_SUMMANDS_SIZE, "raw 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");
    }
    for (int i = 0; i < raw_summands.length(); i++) {
      const MemPointerRawSummand& s = raw_summands.at(i);
      assert(!s.scaleI().is_NaN(), "non-NaN scale");
      assert(!s.scaleL().is_NaN(), "non-NaN scale");
    }
#endif

    // Copy raw summands in the same order.
    for (int i = 0; i < raw_summands.length(); i++) {
      _raw_summands[i] = raw_summands.at(i);
    }

    // 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 < RAW_SUMMANDS_SIZE; i++) {
      _raw_summands[i] = old.raw_summands_at(i);
    }

    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<MemPointerRawSummand>& raw_summands,
                         const NoOverflowInt con,
                         const GrowableArray<MemPointerSummand>& summands,
                         const jint size
                         NOT_PRODUCT(COMMA const TraceMemPointer& trace)) {
    if (raw_summands.length() <= RAW_SUMMANDS_SIZE &&
        summands.length() <= SUMMANDS_SIZE &&
        has_no_NaN_in_con_and_summands(con, summands)) {
      return MemPointer(pointer, raw_summands, summands, con, size NOT_PRODUCT(COMMA trace));
    } else {
      return MemPointer::make_trivial(pointer, size NOT_PRODUCT(COMMA trace));
    }
  }

  static bool has_no_NaN_in_con_and_summands(const NoOverflowInt con,
                                             const GrowableArray<MemPointerSummand>& summands) {
    if (con.is_NaN()) { return false; }
    for (int i = 0; i < summands.length(); i++) {
      if (summands.at(i).scale().is_NaN()) { return false; }
    }
    return true;
  }

  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 MemPointerRawSummand& raw_summands_at(const uint i) const {
    assert(i < RAW_SUMMANDS_SIZE, "in bounds");
    return _raw_summands[i];
  }

  const NoOverflowInt con() const { return _con; }
  const Base& base() const { return _base; }
  jint size() const { return _size; }

  int max_int_group() const {
    int n = 0;
    for (int i = 0; i < RAW_SUMMANDS_SIZE; i++) {
      const MemPointerRawSummand& s = _raw_summands[i];
      if (!s.is_valid()) { continue; }
      n = MAX2(n, s.int_group());
    }
    return n;
  }

  template<typename Callback>
  void for_each_raw_summand_of_int_group(int int_group, Callback callback) const {
    for (int i = 0; i < RAW_SUMMANDS_SIZE; i++) {
      const MemPointerRawSummand& s = _raw_summands[i];
      if (!s.is_valid() || s.int_group() != int_group) { continue; }
      callback(s);
    }
  }

  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;
  bool always_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) const {
    st->print("MemPointer[size: %2d, base: ", size());
    _base.print_on(st);
    st->print(", form: ");
    print_form_on(st);
    st->print("]");
    st->cr();

    st->print("  raw: ");

    int long_count = 0;
    for_each_raw_summand_of_int_group(0, [&] (const MemPointerRawSummand& s) {
      if (long_count > 0) { st->print(" + "); }
      long_count++;
      if (s.is_con()) {
        // Long constant.
        NoOverflowInt con = s.scaleI() * s.scaleL();
        con.print_on(st);
        st->print("L");
      } else {
        // Long variable.
        assert(s.scaleI().is_one(), "must be long variable");
        s.scaleL().print_on(st);
        st->print("L * [%d %s]", s.variable()->_idx, s.variable()->Name());
      }
    });

    // Int groups, i.e. "ConvI2L(...)"
    for (int int_group = 1; int_group <= max_int_group(); int_group++) {
      if (long_count > 0) { st->print(" + "); }
      long_count++;
      int int_count = 0;
      for_each_raw_summand_of_int_group(int_group, [&] (const MemPointerRawSummand& s) {
        if (int_count == 0) {
          s.scaleL().print_on(st);
          st->print("L * ConvI2L(");
        } else {
          st->print(" + ");
        }
        int_count++;
        s.scaleI().print_on(st);
        if (!s.is_con()) {
          st->print(" * [%d %s]", s.variable()->_idx, s.variable()->Name());
        }
      });
      st->print(")");
    }
    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 raw summands.
  int _next_int_group = 1;
  GrowableArray<MemPointerRawSummand> _worklist;
  GrowableArray<MemPointerRawSummand> _raw_summands;

  // Internal data-structures for parsing "regular" summands.
  NoOverflowInt _con = NoOverflowInt(0);
  GrowableArray<MemPointerSummand> _summands;

  // Resulting decomposed-form.
  MemPointer _mem_pointer;

  MemPointerParser(const MemNode* mem,
                   MemPointerParserCallback& callback
                   NOT_PRODUCT(COMMA const TraceMemPointer& trace)) :
    _mem(mem),
    _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 MemPointerRawSummand& 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;

  void canonicalize_raw_summands();
  void create_summands();
  void canonicalize_summands();
};

#endif // SHARE_OPTO_MEMPOINTER_HPP