LCOV - code coverage report
Current view: top level - lib/CodeGen/SelectionDAG - SelectionDAGAddressAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 54 64 84.4 %
Date: 2018-10-20 13:21:21 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //==- llvm/CodeGen/SelectionDAGAddressAnalysis.cpp - DAG Address Analysis --==//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
      11             : #include "llvm/CodeGen/ISDOpcodes.h"
      12             : #include "llvm/CodeGen/MachineFrameInfo.h"
      13             : #include "llvm/CodeGen/MachineFunction.h"
      14             : #include "llvm/CodeGen/SelectionDAG.h"
      15             : #include "llvm/CodeGen/SelectionDAGNodes.h"
      16             : #include "llvm/CodeGen/TargetLowering.h"
      17             : #include "llvm/Support/Casting.h"
      18             : #include <cstdint>
      19             : 
      20             : using namespace llvm;
      21             : 
      22    11119950 : bool BaseIndexOffset::equalBaseIndex(BaseIndexOffset &Other,
      23             :                                      const SelectionDAG &DAG, int64_t &Off) {
      24             :   // Conservatively fail if we a match failed..
      25    11119950 :   if (!Base.getNode() || !Other.Base.getNode())
      26             :     return false;
      27             :   // Initial Offset difference.
      28    11119950 :   Off = Other.Offset - Offset;
      29             : 
      30    21810425 :   if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) {
      31             :     // Trivial match.
      32             :     if (Other.Base == Base)
      33             :       return true;
      34             : 
      35             :     // Match GlobalAddresses
      36             :     if (auto *A = dyn_cast<GlobalAddressSDNode>(Base))
      37             :       if (auto *B = dyn_cast<GlobalAddressSDNode>(Other.Base))
      38     3290537 :         if (A->getGlobal() == B->getGlobal()) {
      39       12456 :           Off += B->getOffset() - A->getOffset();
      40       12456 :           return true;
      41             :         }
      42             : 
      43             :     // Match Constants
      44             :     if (auto *A = dyn_cast<ConstantPoolSDNode>(Base))
      45             :       if (auto *B = dyn_cast<ConstantPoolSDNode>(Other.Base)) {
      46             :         bool IsMatch =
      47           0 :             A->isMachineConstantPoolEntry() == B->isMachineConstantPoolEntry();
      48           0 :         if (IsMatch) {
      49           0 :           if (A->isMachineConstantPoolEntry())
      50           0 :             IsMatch = A->getMachineCPVal() == B->getMachineCPVal();
      51             :           else
      52           0 :             IsMatch = A->getConstVal() == B->getConstVal();
      53             :         }
      54           0 :         if (IsMatch) {
      55           0 :           Off += B->getOffset() - A->getOffset();
      56           0 :           return true;
      57             :         }
      58             :       }
      59             : 
      60     5399093 :     const MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
      61             : 
      62             :     // Match non-equal FrameIndexes - If both frame indices are fixed
      63             :     // we know their relative offsets and can compare them. Otherwise
      64             :     // we must be conservative.
      65             :     if (auto *A = dyn_cast<FrameIndexSDNode>(Base))
      66             :       if (auto *B = dyn_cast<FrameIndexSDNode>(Other.Base))
      67       66985 :         if (MFI.isFixedObjectIndex(A->getIndex()) &&
      68       17865 :             MFI.isFixedObjectIndex(B->getIndex())) {
      69       17708 :           Off += MFI.getObjectOffset(B->getIndex()) -
      70             :                  MFI.getObjectOffset(A->getIndex());
      71       17708 :           return true;
      72             :         }
      73             :   }
      74             :   return false;
      75             : }
      76             : 
      77             : /// Parses tree in Ptr for base, index, offset addresses.
      78    21189902 : BaseIndexOffset BaseIndexOffset::match(LSBaseSDNode *N,
      79             :                                        const SelectionDAG &DAG) {
      80    21189902 :   SDValue Ptr = N->getBasePtr();
      81             : 
      82             :   // (((B + I*M) + c)) + c ...
      83    21189902 :   SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(Ptr);
      84             :   SDValue Index = SDValue();
      85             :   int64_t Offset = 0;
      86             :   bool IsIndexSignExt = false;
      87             : 
      88             :   // pre-inc/pre-dec ops are components of EA.
      89    21189902 :   if (N->getAddressingMode() == ISD::PRE_INC) {
      90             :     if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
      91         111 :       Offset += C->getSExtValue();
      92             :     else // If unknown, give up now.
      93             :       return BaseIndexOffset(SDValue(), SDValue(), 0, false);
      94    21189775 :   } else if (N->getAddressingMode() == ISD::PRE_DEC) {
      95             :     if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
      96           0 :       Offset -= C->getSExtValue();
      97             :     else // If unknown, give up now.
      98             :       return BaseIndexOffset(SDValue(), SDValue(), 0, false);
      99             :   }
     100             : 
     101             :   // Consume constant adds & ors with appropriate masking.
     102             :   while (true) {
     103    76666374 :     switch (Base->getOpcode()) {
     104      433064 :     case ISD::OR:
     105             :       // Only consider ORs which act as adds.
     106      433064 :       if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1)))
     107      789698 :         if (DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue())) {
     108      394847 :           Offset += C->getSExtValue();
     109      394847 :           Base = Base->getOperand(0);
     110      394847 :           continue;
     111             :         }
     112             :       break;
     113    18193506 :     case ISD::ADD:
     114    18193506 :       if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {
     115    16742187 :         Offset += C->getSExtValue();
     116    16742187 :         Base = Base->getOperand(0);
     117    16742187 :         continue;
     118             :       }
     119             :       break;
     120      642406 :     case ISD::LOAD:
     121             :     case ISD::STORE: {
     122             :       auto *LSBase = cast<LSBaseSDNode>(Base.getNode());
     123      642406 :       unsigned int IndexResNo = (Base->getOpcode() == ISD::LOAD) ? 1 : 0;
     124      642406 :       if (LSBase->isIndexed() && Base.getResNo() == IndexResNo)
     125             :         if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) {
     126        6267 :           auto Off = C->getSExtValue();
     127        6267 :           if (LSBase->getAddressingMode() == ISD::PRE_DEC ||
     128             :               LSBase->getAddressingMode() == ISD::POST_DEC)
     129           0 :             Offset -= Off;
     130             :           else
     131        6267 :             Offset += Off;
     132        6267 :           Base = LSBase->getBasePtr();
     133        6267 :           continue;
     134             :         }
     135             :       break;
     136             :     }
     137             :     }
     138             :     // If we get here break out of the loop.
     139             :     break;
     140             :   }
     141             : 
     142    21189886 :   if (Base->getOpcode() == ISD::ADD) {
     143             :     // TODO: The following code appears to be needless as it just
     144             :     //       bails on some Ptrs early, reducing the cases where we
     145             :     //       find equivalence. We should be able to remove this.
     146             :     // Inside a loop the current BASE pointer is calculated using an ADD and a
     147             :     // MUL instruction. In this case Base is the actual BASE pointer.
     148             :     // (i64 add (i64 %array_ptr)
     149             :     //          (i64 mul (i64 %induction_var)
     150             :     //                   (i64 %element_size)))
     151     2902638 :     if (Base->getOperand(1)->getOpcode() == ISD::MUL)
     152     1449894 :       return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
     153             : 
     154             :     // Look at Base + Index + Offset cases.
     155     1404420 :     Index = Base->getOperand(1);
     156     1404420 :     SDValue PotentialBase = Base->getOperand(0);
     157             : 
     158             :     // Skip signextends.
     159     1404420 :     if (Index->getOpcode() == ISD::SIGN_EXTEND) {
     160         514 :       Index = Index->getOperand(0);
     161             :       IsIndexSignExt = true;
     162             :     }
     163             : 
     164             :     // Check if Index Offset pattern
     165     1404420 :     if (Index->getOpcode() != ISD::ADD ||
     166        1644 :         !isa<ConstantSDNode>(Index->getOperand(1)))
     167     1402995 :       return BaseIndexOffset(PotentialBase, Index, Offset, IsIndexSignExt);
     168             : 
     169        1425 :     Offset += cast<ConstantSDNode>(Index->getOperand(1))->getSExtValue();
     170        1425 :     Index = Index->getOperand(0);
     171        1425 :     if (Index->getOpcode() == ISD::SIGN_EXTEND) {
     172          74 :       Index = Index->getOperand(0);
     173             :       IsIndexSignExt = true;
     174             :     } else
     175             :       IsIndexSignExt = false;
     176        1425 :     Base = PotentialBase;
     177             :   }
     178    19739992 :   return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
     179             : }

Generated by: LCOV version 1.13