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
20namespace llvm {
21namespace bolt {
22
23StackAvailableExpressions::StackAvailableExpressions(const RegAnalysis &RA,
24 const FrameAnalysis &FA,
25 BinaryFunction &BF)
26 : InstrsDataflowAnalysis(BF), RA(RA), FA(FA) {}
27
28void 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(x: &Inst);
42 ExprToIdx[&Inst] = NumInstrs++;
43 }
44 }
45 }
46}
47
48BitVector
49StackAvailableExpressions::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
57BitVector
58StackAvailableExpressions::getStartingStateAtPoint(const MCInst &Point) {
59 return BitVector(NumInstrs, true);
60}
61
62void StackAvailableExpressions::doConfluence(BitVector &StateOut,
63 const BitVector &StateIn) {
64 StateOut &= StateIn;
65}
66
67namespace {
68
69bool 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
81bool 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(Inst: *X);
85 ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(Inst: *Y);
86 if (FIEX && FIEY) {
87 if (isLoadRedundant(LoadFIE: *FIEX, StoreFIE: *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(Inst: *X, KillSet&: 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(Inst: *Y, KillSet&: YClobbers);
105
106 XClobbers &= YClobbers;
107 return XClobbers.any();
108}
109
110BitVector StackAvailableExpressions::computeNext(const MCInst &Point,
111 const BitVector &Cur) {
112 BitVector Next = Cur;
113 // Kill
114 for (auto I = expr_begin(BV: 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(X: &Point, Y: *I)) {
119 LLVM_DEBUG(dbgs() << "\t\t\t\tKilling ");
120 LLVM_DEBUG((*I)->dump());
121 Next.reset(Idx: I.getBitVectorIndex());
122 }
123 }
124 // Gen
125 if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst: 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

source code of bolt/lib/Passes/StackAvailableExpressions.cpp