/*******************************************************************************
 * Copyright IBM Corp. and others 2000
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution and
 * is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following
 * Secondary Licenses when the conditions for such availability set
 * forth in the Eclipse Public License, v. 2.0 are satisfied: GNU
 * General Public License, version 2 with the GNU Classpath
 * Exception [1] and GNU General Public License, version 2 with the
 * OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] https://openjdk.org/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
 *******************************************************************************/

#ifndef STRINGBUILDERTRANSFORMER_INCL
#define STRINGBUILDERTRANSFORMER_INCL

#include <stdint.h>
#include "infra/ILWalk.hpp"
#include "optimizer/Optimization.hpp"
#include "optimizer/OptimizationManager.hpp"

namespace TR { class Block; }

/** \brief
 *     Transforms StringBuilder constructor calls to preallocate a heuristically determined capacity for StringBuilder
 *     objects generated by idiomatic Java String concatenation operations.
 *
 *  \details
 *     The Java Language Specification for the String Concatenation Operator + (Section 15.18.1) states that for a
 *     sequence of String concatenation operations a Java compiler implementation may choose to use a StringBuilder to
 *     reduce the number of intermediate String objects that are created by evaluation of an expression.
 *
 *     A canonical example is concatenating a String object and an integer. In such cases a StringBuilder will always
 *     be used as it allows appending arbitrary object types. The Java bytecode compiler will typically translate the
 *     following String concatenation operation:
 *
 *     \code
 *     String result = "test" + 1 + '2';
 *     \endcode
 *
 *     into the following sequence:
 *
 *     \code
 *     String result = (new StringBuilder ()).append("test").append(1).append('2').toString();
 *     \endcode
 *
 *     Although the Java Language Specification does not dictate which StringBuilder constructor overload is invoked,
 *     many Java bytecode compilers will chose to invoke the default constructor for which the Java Class Library
 *     dictates that it must allocate an initial buffer capacity of 16 chars.
 *
 *     When the chain of appends exhausts the StringBuilder's capacity the StringBuilder will reallocate a larger
 *     buffer to make room for the incoming append object. Unfortunately the StringBuilder implementation will at least
 *     double the size of it's buffer when a reallocation is needed. This could potentially result in many allocated
 *     bytes being unused. Note that the upon a reallocation the StringBuilder will also have to copy the contents of
 *     its current buffer into the new enlarged buffer, thus incurring an additional cost.
 *
 *     The realization here is that for compile time constants we can statically determine the size of the final
 *     resulting String at compile time. We can then use this information to transform the StringBuilder default
 *     constructor call to an overloaded constructor call accepting an initial capacity which we computed at compile
 *     time. The end result is an overall reduction in the number of reallocations that the StringBuilder will perform.
 *
 *     This optimization searches for these StringBuilder chained append calls followed by a toString and it
 *     heuristically tries to estimate the sizes of the append arguments. If it can the optimization will precisely
 *     determine the sizes of all constant append arguments.
 *
 *  \section Debug Counters
 *     You can track the locations of where this optimization succeeded or failed via the following debug counter:
 *
 *     \code
 *     -Xjit:staticDebugCounters={StringBuilderTransformer*}
 *     \endcode
 *
 *  \section Environment Variables
 *     The optimization provides 5 environment variables to collect various statistics on the locations in which this
 *     optimization can be performed. The environment variables displayed below require a modified StringBuilder.java
 *     implementation to collect the various statistics. The modifications necessary to StringBuilder.java to collect
 *     the statistics are outlined in PR #133. When using the below environment variables you must make sure the
 *     modified StringBuilder.class is prepended to the bootclasspath when invoking the JVM. Upon JVM shutdown the
 *     statistics will be printed to stdout.
 *
 *     \code
 *     export TR_StringBuilderTransformerCollectAppendStatistics=1;
 *     \endcode
 *
 *     This environment variable tracks the char size of the argument to append and for each size it tracks the number
 *     of such objects that passed through the respective append call. This statistic is collected for each overload of
 *     StringBuilder.append(...) that this optimization supports. The output will be a per overload sequential sorted
 *     list of append char lengths delimited by a comma with the count of the number of times the respective append
 *     overload was invoked with a value of the specified char length.
 *
 *     \code
 *     export TR_StringBuilderTransformerCollectAllocationStatistics=1;
 *     \endcode
 *
 *     This environment variable tracks the total number of allocated chars from all call sites in which this
 *     optimization was performed. The output will be the total number of chars that all the StringBuilders have
 *     allocated.
 *
 *     \code
 *     export TR_StringBuilderTransformerCollectAllocationBacktraces=1;
 *     \endcode
 *
 *     This environment variable tracks the back traces of all call sites that this optimization was performed on. The
 *     output will be a sorted back trace of the call site along with the invocation count.
 *
 *     \code
 *     export TR_StringBuilderTransformerCollectAppendObjectTypes=1;
 *     \endcode
 *
 *     This environment variable tracks the types of the arguments supplied to the StringBuilder.append(LObject)
 *     overload. The output will be a list of append char lengths delimited by a comma with the count of the number of
 *     times the StringBuilder.append(LObject) overload was invoked an object of the specified char length. This
 *     statistic will be displayed per object type.
 *
 *     \code
 *     export TR_StringBuilderTransformerOverrideInitialCapacity=###;
 *     \endcode
 *
 *     This environment variable can be used to override the final capacity that this optimization has heuristically
 *     calculated with the ### supplied.
 */
class TR_StringBuilderTransformer : public TR::Optimization
   {
   public:

   /** \brief
    *     Initializes the StringBuilderTransformer optimization.
    *
    *  \param manager
    *     The optimization manager.
    */
   TR_StringBuilderTransformer(TR::OptimizationManager* manager)
      : TR::Optimization(manager)
      {
      // Void
      }

   /** \brief
    *     Helper function to create an instance of the StringBuilderTransformer optimization using the
    *     OptimizationManager's default allocator.
    *
    *  \param manager
    *     The optimization manager.
    */
   static TR::Optimization* create(TR::OptimizationManager* manager)
      {
      return new (manager->allocator()) TR_StringBuilderTransformer(manager);
      }

   /** \brief
    *     Performs the optimization on this compilation unit.
    *
    *  \return
    *     1 if any transformation was performed; 0 otherwise.
    */
   virtual int32_t perform();

   /** \brief
    *     Performs the optimization on a specific block within this compilation unit.
    *
    *  \param block
    *     The block on which to perform this optimization.
    *
    *  \return
    *     1 if any transformation was performed; 0 otherwise.
    */
   virtual int32_t performOnBlock(TR::Block* block);

   virtual const char * optDetailString() const throw()
      {
      return "O^O STRINGBUILDER TRANSFORMER: ";
      }

   private:

   /** \brief
    *     Attempts to find a call to the StringBuilder.<init>() constructor whose receiver is \p newNode.
    *
    *  \param iter
    *     The iterator to begin searching from.
    *
    *  \param newNode
    *     A TR::New node which is the receiver of the constructor call we are searching for.
    *
    *  \return
    *     The call to StringBuilder.<init>() or NULL if the call was not found.
    */
   TR::Node* findStringBuilderInit(TR::TreeTopIterator iter, TR::Node* newNode);

   /** \brief
    *     Attempts to find and collect the arguments of a sequence of chained StringBuilder.append(...) calls which is
    *     terminated by a call to StringBuilder.toString().
    *
    *  \param iter
    *     The iterator to begin searching from.
    *
    *  \param newNode
    *     A TR::New node which is the receiver of the first chained StringBuilder.append(...) call.
    *
    *  \param appendArguments
    *     If this function returns non-NULL this out parameter contains an ordered list of all the arguments of the
    *     sequence of chained StringBuilder.append(...) calls.
    *
    *  \return
    *     The call to StringBuilder.toString() or NULL if the call was not found or if the StringBuilder.append(...)
    *     chain was broken.
    */
   TR::Node* findStringBuilderChainedAppendArguments(TR::TreeTopIterator iter, TR::Node* newNode, List<TR_Pair<TR::Node*, TR::RecognizedMethod> >& appendArguments);

   /** \brief
    *     Given a list of arguments of a sequence of chained StringBuilder.append(...) calls outputs the heuristically
    *     calculated char length of the String that is the result of a call to StringBuilder.toString().
    *
    *  \param appendArguments
    *     A list of arguments of a sequence of chained StringBuilder.append(...) calls.
    *
    *  \return
    *     Heuristically calculated char length of the String that is the result of a call to StringBuilder.toString().
    */
   int32_t computeHeuristicStringBuilderInitCapacity(List<TR_Pair<TR::Node*, TR::RecognizedMethod> >& appendArguments);
   };

#endif
