134 lines · 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-exception6//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 20namespace llvm {21namespace bolt {22 23StackAvailableExpressions::StackAvailableExpressions(const RegAnalysis &RA,24 const FrameAnalysis &FA,25 BinaryFunction &BF)26 : InstrsDataflowAnalysis(BF), RA(RA), FA(FA) {}27 28void StackAvailableExpressions::preflight() {29 LLVM_DEBUG(dbgs() << "Starting StackAvailableExpressions on \""30 << Func.getPrintName() << "\"\n");31 32 // Populate our universe of tracked expressions. We are interested in33 // tracking available stores to frame position at any given point of the34 // 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 48BitVector49StackAvailableExpressions::getStartingStateAtBB(const BinaryBasicBlock &BB) {50 // Entry points start with empty set51 // 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 57BitVector58StackAvailableExpressions::getStartingStateAtPoint(const MCInst &Point) {59 return BitVector(NumInstrs, true);60}61 62void StackAvailableExpressions::doConfluence(BitVector &StateOut,63 const BitVector &StateIn) {64 StateOut &= StateIn;65}66 67namespace {68 69bool 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 81bool StackAvailableExpressions::doesXKillsY(const MCInst *X, const MCInst *Y) {82 // if both are stores, and both store to the same stack location, return83 // true84 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 true95 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 is99 // different than the rest because we want to check if the store source100 // reaches its corresponding load untouched.101 if (FIEY && FIEY->IsStore == true && FIEY->IsStoreFromReg)102 YClobbers.set(FIEY->RegOrImm);103 else104 RA.getInstClobberList(*Y, YClobbers);105 106 XClobbers &= YClobbers;107 return XClobbers.any();108}109 110BitVector StackAvailableExpressions::computeNext(const MCInst &Point,111 const BitVector &Cur) {112 BitVector Next = Cur;113 // Kill114 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 // Gen125 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 bolt133} // namespace llvm134