TreeServices.cpp

/*******************************************************************************
 * 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
 *******************************************************************************/

#include "infra/TreeServices.hpp"

#include "control/Options.hpp"
#include "control/Options_inlines.hpp"
#include "il/DataTypes.hpp"
#include "il/Node.hpp"

bool
TR_AddressTree::isLloadi(TR::Node * node)
   {
   if (node->getOpCodeValue() != TR::iload  && node->getOpCodeValue() != TR::lload &&
       node->getOpCodeValue() != TR::iloadi && node->getOpCodeValue() != TR::lloadi)
      {
      return false;
      }
   else
      {
      return true;
      }
   }

bool
TR_AddressTree::findComplexAddressGenerationTree(TR::Node *node, vcount_t visitCount, TR::Node *parent)
   {
   if (node->getVisitCount()==visitCount)
      return false;
   node->setVisitCount(visitCount);

   if (isLloadi(node))
      {
      int32_t childNumber;
      for (childNumber = 0; childNumber < parent->getNumChildren(); childNumber++)
         if (parent->getChild(childNumber)==node)
            break;
      _indVarNode.setParentAndChildNumber(parent, childNumber);
      _indexBaseNode.setParentAndChildNumber(node, 0);
      return true;
      }
   else
      return false;
   }


bool
TR_AddressTree::processBaseAndIndex(TR::Node* parent)
   {
   TR::Node * lhs = parent->getFirstChild();
   TR::Node * rhs = parent->getSecondChild();
   bool isValid = true;
   if (isLloadi(lhs) && isLloadi(rhs))
      {
      isValid = false; // exactly one child should be a variable
      }
   else if (isLloadi(lhs))
      {
      _indexBaseNode.setParentAndChildNumber(lhs, 0);
      _indVarNode.setParentAndChildNumber(parent, 0);
      }
   else if (isLloadi(rhs))
      {
      _indexBaseNode.setParentAndChildNumber(rhs, 0);
      _indVarNode.setParentAndChildNumber(parent, 1);
      }
   else
      {
      isValid = false; // one of the children must be variable
      }
   if (isValid)
      return isValid;
   else
      {
         return findComplexAddressGenerationTree(parent, comp()->incVisitCount(), parent);
      }
   }



bool
TR_AddressTree::processMultiplyNode(TR::Node * multiplyNode)
   {

   // (64-bit)
   // for aladds multiplysubTree
   // lmul
   //   i2l
   //     <index>
   //   lconst
   TR::Node * secondMulChild = multiplyNode->getSecondChild();
   TR::ILOpCodes opCodeSecondMulChild = secondMulChild->getOpCodeValue();
   if (opCodeSecondMulChild != TR::iconst && opCodeSecondMulChild != TR::lconst)
      {
      dumpOptDetails(comp(), "AddressTree: second node of multiply is not iconst\n");
      return false;
      }

   if (secondMulChild->getType().isInt64())
      {
      _multiplier = (int32_t) secondMulChild->getLongInt();
      }
   else
      {
      _multiplier = secondMulChild->getInt();
      }

   TR::Node * firstMulChild = multiplyNode->getFirstChild()->skipConversions();

   TR::ILOpCodes opCodeFirstMulChild = firstMulChild->getOpCodeValue();

   if (opCodeFirstMulChild == TR::iadd || opCodeFirstMulChild == TR::ladd)
      {
      if (!processBaseAndIndex(firstMulChild))
         {
         dumpOptDetails(comp(), "AddressTree: first node of multiply is iadd/ladd but children are not ok\n");
         return false;
         }
      }
   else if (isLloadi(firstMulChild))
      {
      _indexBaseNode.setParentAndChildNumber(firstMulChild, 0);
      _indVarNode.setParentAndChildNumber(multiplyNode, 0);
      }
   else
      {
      dumpOptDetails(comp(), "AddressTree: first node of multiply is not iadd/ladd/iload/lload\n");
      return false;
      }

   return true;
   }

//
// process looks for an address generation sub-tree. The tree typically is headed up with an aiadd
// but can also be an iadd or ladd tree in the case of unsafe get/put being used.
//
// aiadd <memory reference>
//    aload <address>
//    isub <index expression>
//       imul
//          iload <index>
//          iconst <stride>
//       iconst <displacement>
//
// -or-
// (32-bit)
// iadd
//    x2i
//       ixload
//          aiadd <memory reference sub-tree>
//    l2i
//       lloadi <DirectByteBuffer>
//          aload <Buffer>
//
// (64-bit)
// ladd
//    x2i
//       ixload
//          aladd <memory reference sub-tree>
//    lloadi <DirectByteBuffer>
//       aload <Buffer>
//
// For OffHeap tree can be without an add if accessing the first element of an array:
// aloadi <contiguousArrayDataAddrField>
//    aload <address>
//
bool
TR_AddressTree::process(TR::Node * elementAddrNode, bool onlyConsiderConstAiaddSecondChild)
   {
   TR::Node * multiplySubTree = NULL;
   bool validAiaddSubTree = false;

   _offset = 0;
   _rootNode = elementAddrNode;

   TR::ILOpCodes opCodeElementAddr = elementAddrNode->getOpCodeValue();

   if (opCodeElementAddr != TR::aiadd && opCodeElementAddr != TR::aladd && !elementAddrNode->isDataAddrPointer())
      {
      dumpOptDetails(comp(), "AddressTree: Can not construct an address tree without an address node\n");
      return false;
      }

   // Use 'UnconvertedChild' instead of 'Child' below to skip over potential l2i's that can be strewn about for
   // 64-bit sign extension work.
   TR::Node * elementAddrFirstChild = elementAddrNode->getFirstChild()->skipConversions();
   TR::ILOpCodes opCodeElementAddrFirstChild = elementAddrFirstChild->getOpCodeValue();

   if (opCodeElementAddrFirstChild == TR::aload || opCodeElementAddrFirstChild == TR::aloadi)
      {
      if (elementAddrNode->isDataAddrPointer()) // Accessing first element of an OffHeap array
         {
         validAiaddSubTree = true;
         _baseVarNode.setParentAndChildNumber(elementAddrNode, 0);
         _offset = 0;
         }
      else
         {
         _baseVarNode.setParentAndChildNumber(elementAddrNode->getFirstChild()->isDataAddrPointer() ? elementAddrNode->getFirstChild() : elementAddrNode, 0);
         
         TR::Node * aiaddSecondChild = elementAddrNode->getSecondChild()->skipConversions();
         TR::ILOpCodes opCodeAiaddSecondChild = aiaddSecondChild->getOpCodeValue();
         if ((opCodeAiaddSecondChild == TR::isub || opCodeAiaddSecondChild == TR::lsub ||
            opCodeAiaddSecondChild == TR::iadd || opCodeAiaddSecondChild == TR::ladd) &&
            !onlyConsiderConstAiaddSecondChild)
            {
            TR::Node * isubFirstChild = aiaddSecondChild->getFirstChild()->skipConversions();
            TR::ILOpCodes opCodeIsubFirstChild = isubFirstChild->getOpCodeValue();
            TR::Node * isubSecondChild = aiaddSecondChild->getSecondChild()->skipConversions();
            TR::ILOpCodes opCodeIsubSecondChild = isubSecondChild->getOpCodeValue();

            // (64-bit, for 32-bit, change the l to i in the opcodes below and remove the i2l...
            // aladd
            //   aload
            //   lsub
            //     lmul
            //       i2l
            //         <index>
            //       lconst
            //     lconst
            if (opCodeIsubSecondChild != TR::iconst && opCodeIsubSecondChild != TR::lconst)
               {
               dumpOptDetails(comp(), "AddressTree: i(l)sub second child is not constant\n");
               }
            else
               {
               if (opCodeIsubFirstChild == TR::imul || opCodeIsubFirstChild == TR::lmul)
                  {
                  multiplySubTree = isubFirstChild;
                  TR::Node * indSymFromSubTree = isubFirstChild->getFirstChild()->skipConversions();

                  _multiplyNode.setParentAndChildNumber(aiaddSecondChild, 0);
                  if (indSymFromSubTree->getOpCodeValue() == TR::iload || indSymFromSubTree->getOpCodeValue() == TR::lload)
                     {
                     validAiaddSubTree = true;
                     _indVarNode.setParentAndChildNumber(isubFirstChild, 0);
                     _indexBaseNode.setParentAndChildNumber(indSymFromSubTree, 0);
                     }
                  else if (indSymFromSubTree->getOpCodeValue() == TR::iadd || indSymFromSubTree->getOpCodeValue() == TR::ladd)
                     {
                     // the following check is safe because there should only be one induction
                     // variable active for loops we consider, but it does however require that
                     // the induction variable be the first child, so we will catch a case of:
                     //   a[indVar + j]
                     // but not:
                     //   a[j + indVar]
                     if (
                        (indSymFromSubTree->getFirstChild()->getOpCodeValue() == TR::iload || indSymFromSubTree->getFirstChild()->getOpCodeValue() == TR::lload)
                        &&
                        (indSymFromSubTree->getSecondChild()->getOpCodeValue() == TR::iload || indSymFromSubTree->getSecondChild()->getOpCodeValue() == TR::lload ||
                        indSymFromSubTree->getSecondChild()->getOpCodeValue() == TR::iconst || indSymFromSubTree->getSecondChild()->getOpCodeValue() == TR::lconst)
                        )
                        {
                        validAiaddSubTree = true;
                        _indVarNode.setParentAndChildNumber(indSymFromSubTree, 0);
                        _indexBaseNode.setParentAndChildNumber(indSymFromSubTree->getFirstChild(), 0);
                        }
                     }
                  }
               else if (isLloadi(isubFirstChild))
                  {
                  _multiplyNode.setParentAndChildNumber(aiaddSecondChild, 0);
                  _indVarNode.setParentAndChildNumber(aiaddSecondChild, 0);
                  _indexBaseNode.setParentAndChildNumber(isubFirstChild, 0);
                  validAiaddSubTree = true;
                  }
               else if (opCodeIsubFirstChild == TR::iadd || opCodeIsubFirstChild == TR::ladd)
                  {
                  _multiplyNode.setParentAndChildNumber(aiaddSecondChild, 0);
                  validAiaddSubTree = processBaseAndIndex(isubFirstChild);
                  }
               else
                  {
                  validAiaddSubTree = findComplexAddressGenerationTree(isubFirstChild, comp()->incVisitCount(),  aiaddSecondChild);
                  if (validAiaddSubTree)
                     _multiplyNode.setParentAndChildNumber(aiaddSecondChild, 0);
                  else
                     dumpOptDetails(comp(), "AddressTree: i(l)sub children are not i(l)mul or i(l)const\n");
                  }

               if (opCodeIsubSecondChild == TR::iconst)
                  {
                  _offset = (isubSecondChild->getInt());
                  }
               else
                  {
                  _offset = (isubSecondChild->getLongInt());
                  }
               if(opCodeAiaddSecondChild == TR::isub || opCodeAiaddSecondChild == TR::lsub)
                  {
                  _offset = -_offset;
                  }
               }
            }
         else if (opCodeAiaddSecondChild == TR::iconst || opCodeAiaddSecondChild == TR::lconst)
            {
            validAiaddSubTree = true;
            if (opCodeAiaddSecondChild == TR::iconst)
               {
               _offset = (aiaddSecondChild->getInt());
               }
            else
               {
               _offset = (aiaddSecondChild->getLongInt());
               }
            }
         else if ((opCodeAiaddSecondChild == TR::imul || opCodeAiaddSecondChild == TR::lmul) &&
                  !onlyConsiderConstAiaddSecondChild)
            {
            validAiaddSubTree = true;
            multiplySubTree = aiaddSecondChild;
            }
         else if (opCodeAiaddSecondChild == TR::iload)
            {
            validAiaddSubTree = true;
            _offset = 0;
            _indexBaseNode.setParentAndChildNumber(aiaddSecondChild, 0);
            }
         else
            {
            dumpOptDetails(comp(), "AddressTree: second child of aiadd/aladd is not iload/i(l)sub/i(l)mul\n");
            }
         }
      }
   else
      {
      dumpOptDetails(comp(), "AddressTree: base variable is not aiload\n");
      }

   if (validAiaddSubTree && (multiplySubTree != NULL))
      {
      validAiaddSubTree = processMultiplyNode(multiplySubTree);
      }

   return validAiaddSubTree;
   }

void TR_Pattern::tracePattern(TR::Node *node) {
   traceMsg(TR::comp(), "{ Trying %s pattern on %s n%dn\n", getName(), node->getOpCode().getName(), node->getGlobalIndex());
}

void TR_OpCodePattern::tracePattern(TR::Node *node) {
   traceMsg(TR::comp(), "{ Trying %s [%s] pattern on %s n%dn\n", getName(), TR::ILOpCode(_opCode).getName(), node->getOpCode().getName(), node->getGlobalIndex());
}

bool TR_Pattern::matches(TR::Node *node, TR_Unification &uni, TR::Compilation *comp)
   {
   // Note: ideally, if TR_DisableTreePatternMatching is set, we shouldn't even
   // have wasted memory on TR_Pattern objects in the first place.  Users should
   // guard their pattern builder code with a test of TR_DisableTreePatternMatching.
   // However, just in case they forgot, the following test at least ensures that
   // the patterns have no effect on generated code.
   //
   if (comp->getOption(TR_DisableTreePatternMatching))
      return false;

   // Attempts to match this pattern as well as _next.
   // On failure, uni is restored to its original state.

   if (comp->getOption(TR_TraceTreePatternMatching))
      tracePattern(node);

   bool result = false;
   TR_Unification::TR_Mark mark = uni.mark();
   if (thisMatches(node, uni, comp))
      result = (!_next || _next->matches(node, uni, comp));
   else
      uni.undoTo(mark);

   if (comp->getOption(TR_TraceTreePatternMatching))
      traceMsg(comp, "} result: %s\n", result? "true":"false");

   return result;
   }

bool TR_UnifyPattern::thisMatches(TR::Node *node, TR_Unification &uni, TR::Compilation *comp)
   {
   if (comp->getOption(TR_TraceTreePatternMatching))
      {
      traceMsg(comp, "Unify %d with %s in state ", _index, comp->getDebug()->getName(node));
      uni.dump(comp);
      traceMsg(comp, "\n");
      }

   if (uni.node(_index))
      {
      // Already unified; match succeeds only if it's the same node again
      return node == uni.node(_index);
      }
   else
      {
      uni.add(_index, node);
      return true;
      }
   }

bool TR_CommutativePattern::thisMatches(TR::Node *node, TR_Unification &uni, TR::Compilation *comp)
   {
   if (node->getNumChildren() < 2)
      return false;

   TR_Unification::TR_Mark mark = uni.mark();
   if (_leftPattern->matches(node->getFirstChild(), uni, comp) && _rightPattern->matches(node->getSecondChild(), uni, comp))
      {
      return true;
      }
   else
      {
      // If the left one matched and the right one failed, then we need to undo the unifications from the left one
      uni.undoTo(mark);

      // Now try again with the children swapped
      return (_leftPattern->matches(node->getSecondChild(), uni, comp) && _rightPattern->matches(node->getFirstChild(), uni, comp));
      }
   }