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-exception 6 // 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 17 #define DEBUG_TYPE "sae" 18 19 namespace llvm { 20 namespace bolt { 21 22 StackAvailableExpressions::StackAvailableExpressions(const RegAnalysis &RA, 23 const FrameAnalysis &FA, 24 BinaryFunction &BF) 25 : InstrsDataflowAnalysis(BF), RA(RA), FA(FA) {} 26 27 void StackAvailableExpressions::preflight() { 28 LLVM_DEBUG(dbgs() << "Starting StackAvailableExpressions on \"" 29 << Func.getPrintName() << "\"\n"); 30 31 // Populate our universe of tracked expressions. We are interested in 32 // tracking available stores to frame position at any given point of the 33 // program. 34 for (BinaryBasicBlock &BB : Func) { 35 for (MCInst &Inst : BB) { 36 ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst); 37 if (!FIE) 38 continue; 39 if (FIE->IsStore == true && FIE->IsSimple == true) { 40 Expressions.push_back(&Inst); 41 ExprToIdx[&Inst] = NumInstrs++; 42 } 43 } 44 } 45 } 46 47 BitVector 48 StackAvailableExpressions::getStartingStateAtBB(const BinaryBasicBlock &BB) { 49 // Entry points start with empty set 50 // All others start with the full set. 51 if (BB.pred_size() == 0 && BB.throw_size() == 0) 52 return BitVector(NumInstrs, false); 53 return BitVector(NumInstrs, true); 54 } 55 56 BitVector 57 StackAvailableExpressions::getStartingStateAtPoint(const MCInst &Point) { 58 return BitVector(NumInstrs, true); 59 } 60 61 void StackAvailableExpressions::doConfluence(BitVector &StateOut, 62 const BitVector &StateIn) { 63 StateOut &= StateIn; 64 } 65 66 namespace { 67 68 bool isLoadRedundant(const FrameIndexEntry &LoadFIE, 69 const FrameIndexEntry &StoreFIE) { 70 if (LoadFIE.IsLoad == false || LoadFIE.IsSimple == false) { 71 return false; 72 } 73 if (LoadFIE.StackOffset == StoreFIE.StackOffset && 74 LoadFIE.Size == StoreFIE.Size) { 75 return true; 76 } 77 78 return false; 79 } 80 } 81 82 bool StackAvailableExpressions::doesXKillsY(const MCInst *X, const MCInst *Y) { 83 // if both are stores, and both store to the same stack location, return 84 // true 85 ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(*X); 86 ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*Y); 87 if (FIEX && FIEY) { 88 if (isLoadRedundant(*FIEX, *FIEY)) 89 return false; 90 if (FIEX->IsStore == true && FIEY->IsStore == true && 91 FIEX->StackOffset + FIEX->Size > FIEY->StackOffset && 92 FIEX->StackOffset < FIEY->StackOffset + FIEY->Size) 93 return true; 94 } 95 // getClobberedRegs for X and Y. If they intersect, return true 96 BitVector XClobbers = BitVector(BC.MRI->getNumRegs(), false); 97 BitVector YClobbers = BitVector(BC.MRI->getNumRegs(), false); 98 RA.getInstClobberList(*X, XClobbers); 99 // If Y is a store to stack, its clobber list is its source reg. This is 100 // different than the rest because we want to check if the store source 101 // reaches its corresponding load untouched. 102 if (FIEY && FIEY->IsStore == true && FIEY->IsStoreFromReg) { 103 YClobbers.set(FIEY->RegOrImm); 104 } else { 105 RA.getInstClobberList(*Y, YClobbers); 106 } 107 XClobbers &= YClobbers; 108 return XClobbers.any(); 109 } 110 111 BitVector StackAvailableExpressions::computeNext(const MCInst &Point, 112 const BitVector &Cur) { 113 BitVector Next = Cur; 114 // Kill 115 for (auto I = expr_begin(Next), E = expr_end(); I != E; ++I) { 116 assert(*I != nullptr && "Lost pointers"); 117 LLVM_DEBUG(dbgs() << "\t\t\tDoes it kill "); 118 LLVM_DEBUG((*I)->dump()); 119 if (doesXKillsY(&Point, *I)) { 120 LLVM_DEBUG(dbgs() << "\t\t\t\tKilling "); 121 LLVM_DEBUG((*I)->dump()); 122 Next.reset(I.getBitVectorIndex()); 123 } 124 } 125 // Gen 126 if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Point)) { 127 if (FIE->IsStore == true && FIE->IsSimple == true) 128 Next.set(ExprToIdx[&Point]); 129 } 130 return Next; 131 } 132 133 } // namespace bolt 134 } // namespace llvm 135