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 } 34 return false; 35 } 36 37 bool StackReachingUses::isStoreUsed(const FrameIndexEntry &StoreFIE, 38 ExprIterator Candidates, 39 bool IncludeLocalAccesses) const { 40 for (auto I = Candidates; I != expr_end(); ++I) { 41 const MCInst *ReachingInst = *I; 42 if (IncludeLocalAccesses) { 43 if (ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*ReachingInst)) { 44 assert(FIEY->IsLoad == 1); 45 if (StoreFIE.StackOffset + StoreFIE.Size > FIEY->StackOffset && 46 StoreFIE.StackOffset < FIEY->StackOffset + FIEY->Size) { 47 return true; 48 } 49 } 50 } 51 ErrorOr<const ArgAccesses &> Args = FA.getArgAccessesFor(*ReachingInst); 52 if (!Args) 53 continue; 54 if (Args->AssumeEverything) { 55 return true; 56 } 57 for (ArgInStackAccess FIEY : Args->Set) { 58 if (StoreFIE.StackOffset + StoreFIE.Size > FIEY.StackOffset && 59 StoreFIE.StackOffset < FIEY.StackOffset + FIEY.Size) { 60 return true; 61 } 62 } 63 } 64 return false; 65 } 66 67 void StackReachingUses::preflight() { 68 LLVM_DEBUG(dbgs() << "Starting StackReachingUses on \"" << Func.getPrintName() 69 << "\"\n"); 70 71 // Populate our universe of tracked expressions. We are interested in 72 // tracking reaching loads from frame position at any given point of the 73 // program. 74 for (BinaryBasicBlock &BB : Func) { 75 for (MCInst &Inst : BB) { 76 if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst)) { 77 if (FIE->IsLoad == true) { 78 Expressions.push_back(&Inst); 79 ExprToIdx[&Inst] = NumInstrs++; 80 continue; 81 } 82 } 83 ErrorOr<const ArgAccesses &> AA = FA.getArgAccessesFor(Inst); 84 if (AA && (!AA->Set.empty() || AA->AssumeEverything)) { 85 Expressions.push_back(&Inst); 86 ExprToIdx[&Inst] = NumInstrs++; 87 } 88 } 89 } 90 } 91 92 bool StackReachingUses::doesXKillsY(const MCInst *X, const MCInst *Y) { 93 // if X is a store to the same stack location and the bytes fetched is a 94 // superset of those bytes affected by the load in Y, return true 95 ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(*X); 96 ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*Y); 97 if (FIEX && FIEY) { 98 if (FIEX->IsSimple == true && FIEY->IsSimple == true && 99 FIEX->IsStore == true && FIEY->IsLoad == true && 100 FIEX->StackOffset <= FIEY->StackOffset && 101 FIEX->StackOffset + FIEX->Size >= FIEY->StackOffset + FIEY->Size) 102 return true; 103 } 104 return false; 105 } 106 107 BitVector StackReachingUses::computeNext(const MCInst &Point, 108 const BitVector &Cur) { 109 BitVector Next = Cur; 110 // Kill 111 for (auto I = expr_begin(Next), E = expr_end(); I != E; ++I) { 112 assert(*I != nullptr && "Lost pointers"); 113 if (doesXKillsY(&Point, *I)) { 114 LLVM_DEBUG(dbgs() << "\t\t\tKilling "); 115 LLVM_DEBUG((*I)->dump()); 116 Next.reset(I.getBitVectorIndex()); 117 } 118 }; 119 // Gen 120 if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Point)) { 121 if (FIE->IsLoad == true) 122 Next.set(ExprToIdx[&Point]); 123 } 124 ErrorOr<const ArgAccesses &> AA = FA.getArgAccessesFor(Point); 125 if (AA && (!AA->Set.empty() || AA->AssumeEverything)) 126 Next.set(ExprToIdx[&Point]); 127 return Next; 128 } 129 130 } // namespace bolt 131 } // namespace llvm 132