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