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 #include "llvm/MC/MCRegisterInfo.h"
17
18 #define DEBUG_TYPE "sae"
19
20 namespace llvm {
21 namespace bolt {
22
StackAvailableExpressions(const RegAnalysis & RA,const FrameAnalysis & FA,BinaryFunction & BF)23 StackAvailableExpressions::StackAvailableExpressions(const RegAnalysis &RA,
24 const FrameAnalysis &FA,
25 BinaryFunction &BF)
26 : InstrsDataflowAnalysis(BF), RA(RA), FA(FA) {}
27
preflight()28 void StackAvailableExpressions::preflight() {
29 LLVM_DEBUG(dbgs() << "Starting StackAvailableExpressions on \""
30 << Func.getPrintName() << "\"\n");
31
32 // Populate our universe of tracked expressions. We are interested in
33 // tracking available stores to frame position at any given point of the
34 // program.
35 for (BinaryBasicBlock &BB : Func) {
36 for (MCInst &Inst : BB) {
37 ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst);
38 if (!FIE)
39 continue;
40 if (FIE->IsStore == true && FIE->IsSimple == true) {
41 Expressions.push_back(&Inst);
42 ExprToIdx[&Inst] = NumInstrs++;
43 }
44 }
45 }
46 }
47
48 BitVector
getStartingStateAtBB(const BinaryBasicBlock & BB)49 StackAvailableExpressions::getStartingStateAtBB(const BinaryBasicBlock &BB) {
50 // Entry points start with empty set
51 // All others start with the full set.
52 if (BB.pred_size() == 0 && BB.throw_size() == 0)
53 return BitVector(NumInstrs, false);
54 return BitVector(NumInstrs, true);
55 }
56
57 BitVector
getStartingStateAtPoint(const MCInst & Point)58 StackAvailableExpressions::getStartingStateAtPoint(const MCInst &Point) {
59 return BitVector(NumInstrs, true);
60 }
61
doConfluence(BitVector & StateOut,const BitVector & StateIn)62 void StackAvailableExpressions::doConfluence(BitVector &StateOut,
63 const BitVector &StateIn) {
64 StateOut &= StateIn;
65 }
66
67 namespace {
68
isLoadRedundant(const FrameIndexEntry & LoadFIE,const FrameIndexEntry & StoreFIE)69 bool isLoadRedundant(const FrameIndexEntry &LoadFIE,
70 const FrameIndexEntry &StoreFIE) {
71 if (LoadFIE.IsLoad == false || LoadFIE.IsSimple == false)
72 return false;
73 if (LoadFIE.StackOffset == StoreFIE.StackOffset &&
74 LoadFIE.Size == StoreFIE.Size)
75 return true;
76
77 return false;
78 }
79 }
80
doesXKillsY(const MCInst * X,const MCInst * Y)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
computeNext(const MCInst & Point,const BitVector & Cur)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