1 //===--- 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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 //===----------------------------------------------------------------------===// 10 11 #include "bolt/Passes/StackAvailableExpressions.h" 12 #include "bolt/Passes/FrameAnalysis.h" 13 #include "bolt/Passes/RegAnalysis.h" 14 15 #define DEBUG_TYPE "sae" 16 17 namespace llvm { 18 namespace bolt { 19 20 StackAvailableExpressions::StackAvailableExpressions(const RegAnalysis &RA, 21 const FrameAnalysis &FA, 22 const BinaryContext &BC, 23 BinaryFunction &BF) 24 : InstrsDataflowAnalysis(BC, BF), RA(RA), FA(FA) {} 25 26 void StackAvailableExpressions::preflight() { 27 LLVM_DEBUG(dbgs() << "Starting StackAvailableExpressions on \"" 28 << Func.getPrintName() << "\"\n"); 29 30 // Populate our universe of tracked expressions. We are interested in 31 // tracking available stores to frame position at any given point of the 32 // program. 33 for (BinaryBasicBlock &BB : Func) { 34 for (MCInst &Inst : BB) { 35 ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst); 36 if (!FIE) 37 continue; 38 if (FIE->IsStore == true && FIE->IsSimple == true) { 39 Expressions.push_back(&Inst); 40 ExprToIdx[&Inst] = NumInstrs++; 41 } 42 } 43 } 44 } 45 46 BitVector 47 StackAvailableExpressions::getStartingStateAtBB(const BinaryBasicBlock &BB) { 48 // Entry points start with empty set 49 // All others start with the full set. 50 if (BB.pred_size() == 0 && BB.throw_size() == 0) 51 return BitVector(NumInstrs, false); 52 return BitVector(NumInstrs, true); 53 } 54 55 BitVector 56 StackAvailableExpressions::getStartingStateAtPoint(const MCInst &Point) { 57 return BitVector(NumInstrs, true); 58 } 59 60 void StackAvailableExpressions::doConfluence(BitVector &StateOut, 61 const BitVector &StateIn) { 62 StateOut &= StateIn; 63 } 64 65 namespace { 66 67 bool isLoadRedundant(const FrameIndexEntry &LoadFIE, 68 const FrameIndexEntry &StoreFIE) { 69 if (LoadFIE.IsLoad == false || LoadFIE.IsSimple == false) { 70 return false; 71 } 72 if (LoadFIE.StackOffset == StoreFIE.StackOffset && 73 LoadFIE.Size == StoreFIE.Size) { 74 return true; 75 } 76 77 return false; 78 } 79 } 80 81 bool StackAvailableExpressions::doesXKillsY(const MCInst *X, const MCInst *Y) { 82 // if both are stores, and both store to the same stack location, return 83 // true 84 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 true 95 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 is 99 // different than the rest because we want to check if the store source 100 // reaches its corresponding load untouched. 101 if (FIEY && FIEY->IsStore == true && FIEY->IsStoreFromReg) { 102 YClobbers.set(FIEY->RegOrImm); 103 } else { 104 RA.getInstClobberList(*Y, YClobbers); 105 } 106 XClobbers &= YClobbers; 107 return XClobbers.any(); 108 } 109 110 BitVector StackAvailableExpressions::computeNext(const MCInst &Point, 111 const BitVector &Cur) { 112 BitVector Next = Cur; 113 // Kill 114 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 // Gen 125 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 bolt 133 } // namespace llvm 134