128 lines · 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-exception6//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 18namespace llvm {19namespace bolt {20 21bool 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 36bool 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 63void StackReachingUses::preflight() {64 LLVM_DEBUG(dbgs() << "Starting StackReachingUses on \"" << Func.getPrintName()65 << "\"\n");66 67 // Populate our universe of tracked expressions. We are interested in68 // tracking reaching loads from frame position at any given point of the69 // 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 88bool StackReachingUses::doesXKillsY(const MCInst *X, const MCInst *Y) {89 // if X is a store to the same stack location and the bytes fetched is a90 // superset of those bytes affected by the load in Y, return true91 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 103BitVector StackReachingUses::computeNext(const MCInst &Point,104 const BitVector &Cur) {105 BitVector Next = Cur;106 // Kill107 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 // Gen116 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 bolt127} // namespace llvm128