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   if (LoadFIE.StackOffset == StoreFIE.StackOffset &&
73       LoadFIE.Size == StoreFIE.Size)
74     return true;
75 
76   return false;
77 }
78 }
79 
80 bool StackAvailableExpressions::doesXKillsY(const MCInst *X, const MCInst *Y) {
81   // if both are stores, and both store to the same stack location, return
82   // true
83   ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(*X);
84   ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*Y);
85   if (FIEX && FIEY) {
86     if (isLoadRedundant(*FIEX, *FIEY))
87       return false;
88     if (FIEX->IsStore == true && FIEY->IsStore == true &&
89         FIEX->StackOffset + FIEX->Size > FIEY->StackOffset &&
90         FIEX->StackOffset < FIEY->StackOffset + FIEY->Size)
91       return true;
92   }
93   // getClobberedRegs for X and Y. If they intersect, return true
94   BitVector XClobbers = BitVector(BC.MRI->getNumRegs(), false);
95   BitVector YClobbers = BitVector(BC.MRI->getNumRegs(), false);
96   RA.getInstClobberList(*X, XClobbers);
97   // If Y is a store to stack, its clobber list is its source reg. This is
98   // different than the rest because we want to check if the store source
99   // reaches its corresponding load untouched.
100   if (FIEY && FIEY->IsStore == true && FIEY->IsStoreFromReg)
101     YClobbers.set(FIEY->RegOrImm);
102   else
103     RA.getInstClobberList(*Y, YClobbers);
104 
105   XClobbers &= YClobbers;
106   return XClobbers.any();
107 }
108 
109 BitVector StackAvailableExpressions::computeNext(const MCInst &Point,
110                                                  const BitVector &Cur) {
111   BitVector Next = Cur;
112   // Kill
113   for (auto I = expr_begin(Next), E = expr_end(); I != E; ++I) {
114     assert(*I != nullptr && "Lost pointers");
115     LLVM_DEBUG(dbgs() << "\t\t\tDoes it kill ");
116     LLVM_DEBUG((*I)->dump());
117     if (doesXKillsY(&Point, *I)) {
118       LLVM_DEBUG(dbgs() << "\t\t\t\tKilling ");
119       LLVM_DEBUG((*I)->dump());
120       Next.reset(I.getBitVectorIndex());
121     }
122   }
123   // Gen
124   if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Point)) {
125     if (FIE->IsStore == true && FIE->IsSimple == true)
126       Next.set(ExprToIdx[&Point]);
127   }
128   return Next;
129 }
130 
131 } // namespace bolt
132 } // namespace llvm
133