bolt/lib/Passes/StackAvailableExpressions.cpp

   1 //===- bolt/Passes/StackAvailableExpressions.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 StackAvailableExpressions class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "bolt/Passes/StackAvailableExpressions.h"
  14 #include "bolt/Passes/FrameAnalysis.h"
  15 #include "bolt/Passes/RegAnalysis.h"
  16 #include "llvm/MC/MCRegisterInfo.h"
  17
  18 #define DEBUG_TYPE "sae"
  19
  20 namespace llvm {
  21 namespace bolt {
  22
  23 StackAvailableExpressions::StackAvailableExpressions(const RegAnalysis &RA,
  24                                                      const FrameAnalysis &FA,
  25                                                      BinaryFunction &BF)
  26     : InstrsDataflowAnalysis(BF), RA(RA), FA(FA) {}
  27
  28 void StackAvailableExpressions::preflight() {
  29   LLVM_DEBUG(dbgs() << "Starting StackAvailableExpressions on \""
  30                     << Func.getPrintName() << "\"\n");
  31
  32   // Populate our universe of tracked expressions. We are interested in
  33   // tracking available stores to frame position at any given point of the
  34   // program.
  35   for (BinaryBasicBlock &BB : Func) {
  36     for (MCInst &Inst : BB) {
  37       ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst);
  38       if (!FIE)
  39         continue;
  40       if (FIE->IsStore == true && FIE->IsSimple == true) {
  41         Expressions.push_back(&Inst);
  42         ExprToIdx[&Inst] = NumInstrs++;
  43       }
  44     }
  45   }
  46 }
  47
  48 BitVector
  49 StackAvailableExpressions::getStartingStateAtBB(const BinaryBasicBlock &BB) {
  50   // Entry points start with empty set
  51   // All others start with the full set.
  52   if (BB.pred_size() == 0 && BB.throw_size() == 0)
  53     return BitVector(NumInstrs, false);
  54   return BitVector(NumInstrs, true);
  55 }
  56
  57 BitVector
  58 StackAvailableExpressions::getStartingStateAtPoint(const MCInst &Point) {
  59   return BitVector(NumInstrs, true);
  60 }
  61
  62 void StackAvailableExpressions::doConfluence(BitVector &StateOut,
  63                                              const BitVector &StateIn) {
  64   StateOut &= StateIn;
  65 }
  66
  67 namespace {
  68
  69 bool isLoadRedundant(const FrameIndexEntry &LoadFIE,
  70                      const FrameIndexEntry &StoreFIE) {
  71   if (LoadFIE.IsLoad == false || LoadFIE.IsSimple == false)
  72     return false;
  73   if (LoadFIE.StackOffset == StoreFIE.StackOffset &&
  74       LoadFIE.Size == StoreFIE.Size)
  75     return true;
  76
  77   return false;
  78 }
  79 }
  80
  81 bool StackAvailableExpressions::doesXKillsY(const MCInst *X, const MCInst *Y) {
  82   // if both are stores, and both store to the same stack location, return
  83   // true
  84   ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(*X);
  85   ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*Y);
  86   if (FIEX && FIEY) {
  87     if (isLoadRedundant(*FIEX, *FIEY))
  88       return false;
  89     if (FIEX->IsStore == true && FIEY->IsStore == true &&
  90         FIEX->StackOffset + FIEX->Size > FIEY->StackOffset &&
  91         FIEX->StackOffset < FIEY->StackOffset + FIEY->Size)
  92       return true;
  93   }
  94   // getClobberedRegs for X and Y. If they intersect, return true
  95   BitVector XClobbers = BitVector(BC.MRI->getNumRegs(), false);
  96   BitVector YClobbers = BitVector(BC.MRI->getNumRegs(), false);
  97   RA.getInstClobberList(*X, XClobbers);
  98   // If Y is a store to stack, its clobber list is its source reg. This is
  99   // different than the rest because we want to check if the store source
 100   // reaches its corresponding load untouched.
 101   if (FIEY && FIEY->IsStore == true && FIEY->IsStoreFromReg)
 102     YClobbers.set(FIEY->RegOrImm);
 103   else
 104     RA.getInstClobberList(*Y, YClobbers);
 105
 106   XClobbers &= YClobbers;
 107   return XClobbers.any();
 108 }
 109
 110 BitVector StackAvailableExpressions::computeNext(const MCInst &Point,
 111                                                  const BitVector &Cur) {
 112   BitVector Next = Cur;
 113   // Kill
 114   for (auto I = expr_begin(Next), E = expr_end(); I != E; ++I) {
 115     assert(*I != nullptr && "Lost pointers");
 116     LLVM_DEBUG(dbgs() << "\t\t\tDoes it kill ");
 117     LLVM_DEBUG((*I)->dump());
 118     if (doesXKillsY(&Point, *I)) {
 119       LLVM_DEBUG(dbgs() << "\t\t\t\tKilling ");
 120       LLVM_DEBUG((*I)->dump());
 121       Next.reset(I.getBitVectorIndex());
 122     }
 123   }
 124   // Gen
 125   if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Point)) {
 126     if (FIE->IsStore == true && FIE->IsSimple == true)
 127       Next.set(ExprToIdx[&Point]);
 128   }
 129   return Next;
 130 }
 131
 132 } // namespace bolt
 133 } // namespace llvm