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
isLoadedInDifferentReg(const FrameIndexEntry & StoreFIE,ExprIterator Candidates) const21 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
isStoreUsed(const FrameIndexEntry & StoreFIE,ExprIterator Candidates,bool IncludeLocalAccesses) const36 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
preflight()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
doesXKillsY(const MCInst * X,const MCInst * Y)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
computeNext(const MCInst & Point,const BitVector & Cur)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