bolt/lib/Passes/StackReachingUses.cpp

   1 //===- bolt/Passes/StackReachingUses.cpp ----------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the StackReachingUses class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/StackReachingUses.h"
  14 #include "bolt/Passes/FrameAnalysis.h"
  15
  16 #define DEBUG_TYPE "sru"
  17
  18 namespace llvm {
  19 namespace bolt {
  20
  21 bool StackReachingUses::isLoadedInDifferentReg(const FrameIndexEntry &StoreFIE,
  22                                                ExprIterator Candidates) const {
  23   for (auto I = Candidates; I != expr_end(); ++I) {
  24     const MCInst *ReachingInst = *I;
  25     if (ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*ReachingInst)) {
  26       assert(FIEY->IsLoad == 1);
  27       if (StoreFIE.StackOffset + StoreFIE.Size > FIEY->StackOffset &&
  28           StoreFIE.StackOffset < FIEY->StackOffset + FIEY->Size &&
  29           StoreFIE.RegOrImm != FIEY->RegOrImm)
  30         return true;
  31     }
  32   }
  33   return false;
  34 }
  35
  36 bool StackReachingUses::isStoreUsed(const FrameIndexEntry &StoreFIE,
  37                                     ExprIterator Candidates,
  38                                     bool IncludeLocalAccesses) const {
  39   for (auto I = Candidates; I != expr_end(); ++I) {
  40     const MCInst *ReachingInst = *I;
  41     if (IncludeLocalAccesses) {
  42       if (ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*ReachingInst)) {
  43         assert(FIEY->IsLoad == 1);
  44         if (StoreFIE.StackOffset + StoreFIE.Size > FIEY->StackOffset &&
  45             StoreFIE.StackOffset < FIEY->StackOffset + FIEY->Size)
  46           return true;
  47       }
  48     }
  49     ErrorOr<const ArgAccesses &> Args = FA.getArgAccessesFor(*ReachingInst);
  50     if (!Args)
  51       continue;
  52     if (Args->AssumeEverything)
  53       return true;
  54
  55     for (ArgInStackAccess FIEY : Args->Set)
  56       if (StoreFIE.StackOffset + StoreFIE.Size > FIEY.StackOffset &&
  57           StoreFIE.StackOffset < FIEY.StackOffset + FIEY.Size)
  58         return true;
  59   }
  60   return false;
  61 }
  62
  63 void StackReachingUses::preflight() {
  64   LLVM_DEBUG(dbgs() << "Starting StackReachingUses on \"" << Func.getPrintName()
  65                     << "\"\n");
  66
  67   // Populate our universe of tracked expressions. We are interested in
  68   // tracking reaching loads from frame position at any given point of the
  69   // program.
  70   for (BinaryBasicBlock &BB : Func) {
  71     for (MCInst &Inst : BB) {
  72       if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst)) {
  73         if (FIE->IsLoad == true) {
  74           Expressions.push_back(&Inst);
  75           ExprToIdx[&Inst] = NumInstrs++;
  76           continue;
  77         }
  78       }
  79       ErrorOr<const ArgAccesses &> AA = FA.getArgAccessesFor(Inst);
  80       if (AA && (!AA->Set.empty() || AA->AssumeEverything)) {
  81         Expressions.push_back(&Inst);
  82         ExprToIdx[&Inst] = NumInstrs++;
  83       }
  84     }
  85   }
  86 }
  87
  88 bool StackReachingUses::doesXKillsY(const MCInst *X, const MCInst *Y) {
  89   // if X is a store to the same stack location and the bytes fetched is a
  90   // superset of those bytes affected by the load in Y, return true
  91   ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(*X);
  92   ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*Y);
  93   if (FIEX && FIEY) {
  94     if (FIEX->IsSimple == true && FIEY->IsSimple == true &&
  95         FIEX->IsStore == true && FIEY->IsLoad == true &&
  96         FIEX->StackOffset <= FIEY->StackOffset &&
  97         FIEX->StackOffset + FIEX->Size >= FIEY->StackOffset + FIEY->Size)
  98       return true;
  99   }
 100   return false;
 101 }
 102
 103 BitVector StackReachingUses::computeNext(const MCInst &Point,
 104                                          const BitVector &Cur) {
 105   BitVector Next = Cur;
 106   // Kill
 107   for (auto I = expr_begin(Next), E = expr_end(); I != E; ++I) {
 108     assert(*I != nullptr && "Lost pointers");
 109     if (doesXKillsY(&Point, *I)) {
 110       LLVM_DEBUG(dbgs() << "\t\t\tKilling ");
 111       LLVM_DEBUG((*I)->dump());
 112       Next.reset(I.getBitVectorIndex());
 113     }
 114   };
 115   // Gen
 116   if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Point)) {
 117     if (FIE->IsLoad == true)
 118       Next.set(ExprToIdx[&Point]);
 119   }
 120   ErrorOr<const ArgAccesses &> AA = FA.getArgAccessesFor(Point);
 121   if (AA && (!AA->Set.empty() || AA->AssumeEverything))
 122     Next.set(ExprToIdx[&Point]);
 123   return Next;
 124 }
 125
 126 } // namespace bolt
 127 } // namespace llvm