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 return false; 34 } 35 36 bool 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 63 void StackReachingUses::preflight() { 64 LLVM_DEBUG(dbgs() << "Starting StackReachingUses on \"" << Func.getPrintName() 65 << "\"\n"); 66 67 // Populate our universe of tracked expressions. We are interested in 68 // tracking reaching loads from frame position at any given point of the 69 // 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 88 bool StackReachingUses::doesXKillsY(const MCInst *X, const MCInst *Y) { 89 // if X is a store to the same stack location and the bytes fetched is a 90 // superset of those bytes affected by the load in Y, return true 91 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 103 BitVector StackReachingUses::computeNext(const MCInst &Point, 104 const BitVector &Cur) { 105 BitVector Next = Cur; 106 // Kill 107 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 // Gen 116 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 bolt 127 } // namespace llvm 128