LoadExtensions.hpp

/*******************************************************************************
 * 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 LOADEXTENSIONS_INCL
#define LOADEXTENSIONS_INCL

#include <stdint.h>
#include "codegen/CodeGenerator.hpp"
#include "compile/Compilation.hpp"
#include "il/DataTypes.hpp"
#include "il/ILOps.hpp"
#include "il/Node.hpp"
#include "il/Node_inlines.hpp"
#include "il/Symbol.hpp"
#include "optimizer/Optimization.hpp"
#include "optimizer/Optimization_inlines.hpp"
#include "optimizer/OptimizationManager.hpp"

/** \brief
 *     Examines how often a load is being used to feed into a signed vs. unsigned conversion (ex. i2l vs iu2l) and
 *     attempts to skip the conversion by sign/zero extending the load at the point it is evaluated (where the source 
 *     value is actually loaded). This codegen optimization relies on the assumption that the target codegen supports 
 *     load and sign/zero extend instructions and that emitting such an instruction is no more expensive than an 
 *     ordinary load.
 *
 *  \details
 *     This codegen phase pass consists of two steps; the find and the flag preferred load extensions steps.
 *
 *     1. Find preferred load extensions
 *
 *        We iterate through every node in the current compilation unit looking for conversion operations with loads
 *        as the operand. For example a conversion from int to long of a field load o.f:
 *
 *        \code
 *        i2l
 *          iloadi <f>
 *            aload <o>
 *        \endcode
 *
 *        For each such conversion, depending on the type, i.e. sign/zero extension, we record how often each unique
 *        load feeds into such a conversion. In the above snippet the conversion is a sign extension so we would bias
 *        the load towards sign extensions. If the same load were to appear underneath an iu2l conversion we would bias
 *        the load towards zero extensions.
 *
 *        When all trees in the compilation unit have been processed for each load we know exactly how many times it
 *        appears underneath a signed vs. unsigned conversion.
 *
 *     2. Flag preferred load extensions
 *
 *        Since we know the preference of sign vs. zero extension for each load we can now traverse the compilation
 *        unit again and based on the preference of a load we can mark it with the signExtendTo[32|64]BitAtSource or 
 *        zeroExtendTo[32|64]BitAtSource flags to force the extension to happen right at the source. Since we have an
 *        implicit assumption that such extensions are effectively free we can now skip the evaluation of all 
 *        conversions of the respective extensions.
 *
 *        For example in the above code snippet if the load was found to prefer sign extensions we can mark the load
 *        with the signExtendTo64BitAtSource flag and subsequently the i2l conversion can be skipped by marking it with
 *        the unneededConv flag. The final trees will look like this:
 *
 *        \code
 *        i2l (unneededConv)
 *          iloadi <f> (signExtendTo64BitAtSource)
 *            aload <o>
 *        \endcode
 *
 *        Note that if the same load were to appear underneath an iu2l conversion, this conversion cannot be skipped
 *        because of the extension preference of the load.
 *
 *     All load evaluators must respect the signExtendTo[32|64]BitAtSource and zeroExtendTo[32|64]BitAtSource flags.
 *
 *  \section Debug Counters
 *     You can track the locations of where this optimization succeeded via the following debug counter:
 *
 *     \code
 *     -Xjit:staticDebugCounters={codegen/LoadExtensions/success/unneededConversion*}
 *     \endcode
 *
 *  \section Node Flags
 *     This optimization sets the following node flags:
 *        - unneededConv
 *        - signExtendTo32BitAtSource
 *        - signExtendTo64BitAtSource
 *        - zeroExtendTo32BitAtSource
 *        - zeroExtendTo64BitAtSource
 */
class TR_LoadExtensions : public TR::Optimization
   {
   public:

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

   /** \brief
    *     Initializes the LoadExtensions codegen phase.
    *
    *  \param manager
    *     The optimization manager for this local optimization.
    */
   TR_LoadExtensions(TR::OptimizationManager* manager);

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

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

   private:

   /** \brief
    *     Determines whether the conversion of a load can be skipped based on the loads extension preference and if the
    *     conversion can be skipped determine whether the respective load needs to be sign/zero extended.
    *
    *  \param conversion
    *     The conversion to examine.
    *
    *  \param child
    *     The child on which the conversion acts. Note this may not necessarily be the conversions first child as the
    *     conversion may act indirectly on a globally allocated register.
    *
    *  \param forceExtension
    *     Determines whether the respective child load needs to be sign/zero extended.
    *
    *  \return
    *     <c>true</c> if this \p conversion can be skipped; <c>false</c> otherwise.
    */
   const bool canSkipConversion(TR::Node* conversion, TR::Node* child, bool& forceExtension);

   /** \brief
    *     Finds the (zero/sign) extension preference of a node.
    *
    *  \param node
    *     The node to examine.
    */
   void findPreferredLoadExtensions(TR::Node* node);

   /** \brief
    *     Flags conversions with the unneededConv flag and sets preference of loads to zero/sign extend at source by
    *     flagging them with signExtendTo[32|64]BitAtSource and zeroExtendTo[32|64]BitAtSource flags.
    *
    *  \param node
    *     The node to flag.
    */
   void flagPreferredLoadExtensions(TR::Node* node);

   /** \brief
    *     Determines whether a node is of the supported type for skipping conversion operations or forcing sign or zero
    *     extensions on loads.
    *
    *  \param node
    *     The node to examine.
    *
    *  \return
    *     <c>true</c> if this \p node is a load which is a candidate type for this optimization; <c>false</c> otherwise.
    */
   const bool isSupportedType(TR::Node* node) const;

   /** \brief
    *     Determines whether a node is a load candidate for skipping conversion operations.
    *
    *  \param node
    *     The node to examine.
    *
    *  \return
    *     <c>true</c> if this \p node is a load which is a candidate type for this optimization; <c>false</c> otherwise.
    */
   const bool isSupportedLoad(TR::Node* node) const;

   /** \brief
    *     Gets the zero/sign extension preference of a load.
    *
    *  \param load
    *     The load to examine.
    *
    *  \return
    *     Negative value if this \p load prefers to be zero extended and a positive value if this \p load prefers to be
    *     sign extended.
    */
   const int32_t getExtensionPreference(TR::Node* load) const;

   /** \brief
    *     Sets the zero/sign extension preference of a load based on the conversion it feeds into.
    *
    *  \param load
    *     The load to examine.
    *
    *  \return
    *     Negative value if this \p load prefers to be zero extended and a positive value if this \p load prefers to be
    *     sign extended.
    */
   const int32_t setExtensionPreference(TR::Node* load, TR::Node* conversion);

   private:

   typedef TR::typed_allocator<std::pair<const TR::Node* const, int32_t>, TR::Region&> NodeToIntTableAllocator;
   typedef std::less<const TR::Node*> NodeToIntTableComparator;
   typedef std::map<const TR::Node*, int32_t, NodeToIntTableComparator, NodeToIntTableAllocator> NodeToIntTable;

   /** \brief
    *     Keeps track of all nodes which should be excluded from consideration in this optimization.
    */
   NodeToIntTable* excludedNodes;

   /** \brief
    *     Keeps track of the load extension preference where a negative value indicates a preference towards a zero
    *     extension and a positive value indicates a preference towards a sign extension.
    */
   NodeToIntTable* loadExtensionPreference;
   };

#endif /* LOADEXTENSIONS_INCL_ */