blob: cbb4f88302bc6580a88e97b70aa3e1d9796cafd1 [file] [log] [blame]
//===- bolt/Passes/StackPointerTracking.h -----------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef BOLT_PASSES_STACKPOINTERTRACKING_H
#define BOLT_PASSES_STACKPOINTERTRACKING_H
#include "bolt/Passes/DataflowAnalysis.h"
#include "llvm/Support/CommandLine.h"
namespace opts {
extern llvm::cl::opt<bool> TimeOpts;
} // namespace opts
namespace llvm {
namespace bolt {
/// Perform a dataflow analysis to track the value of SP as an offset relative
/// to the CFA.
template <typename Derived>
class StackPointerTrackingBase
: public DataflowAnalysis<Derived, std::pair<int, int>> {
friend class DataflowAnalysis<Derived, std::pair<int, int>>;
protected:
void preflight() {}
int getEmpty() { return EMPTY; }
std::pair<int, int> getStartingStateAtBB(const BinaryBasicBlock &BB) {
// Entry BB start with offset 8 from CFA.
// All others start with EMPTY (meaning we don't know anything).
if (BB.isEntryPoint())
return std::make_pair(-8, getEmpty());
return std::make_pair(getEmpty(), getEmpty());
}
std::pair<int, int> getStartingStateAtPoint(const MCInst &Point) {
return std::make_pair(getEmpty(), getEmpty());
}
void doConfluenceSingleReg(int &StateOut, const int &StateIn) {
if (StateOut == EMPTY) {
StateOut = StateIn;
return;
}
if (StateIn == EMPTY || StateIn == StateOut)
return;
// We can't agree on a specific value from this point on
StateOut = SUPERPOSITION;
}
void doConfluence(std::pair<int, int> &StateOut,
const std::pair<int, int> &StateIn) {
doConfluenceSingleReg(StateOut.first, StateIn.first);
doConfluenceSingleReg(StateOut.second, StateIn.second);
}
void doConfluenceWithLP(std::pair<int, int> &StateOut,
const std::pair<int, int> &StateIn,
const MCInst &Invoke) {
int SPVal = StateIn.first;
if (SPVal != EMPTY && SPVal != SUPERPOSITION) {
const int64_t GnuArgsSize = this->BC.MIB->getGnuArgsSize(Invoke);
if (GnuArgsSize > 0)
SPVal += GnuArgsSize;
}
doConfluenceSingleReg(StateOut.first, SPVal);
doConfluenceSingleReg(StateOut.second, StateIn.second);
}
int computeNextSP(const MCInst &Point, int SPVal, int FPVal) {
const auto &MIB = this->BC.MIB;
if (int Sz = MIB->getPushSize(Point)) {
if (SPVal == EMPTY || SPVal == SUPERPOSITION)
return SPVal;
return SPVal - Sz;
}
if (int Sz = MIB->getPopSize(Point)) {
if (SPVal == EMPTY || SPVal == SUPERPOSITION)
return SPVal;
return SPVal + Sz;
}
MCPhysReg From, To;
if (MIB->isRegToRegMove(Point, From, To) && To == MIB->getStackPointer() &&
From == MIB->getFramePointer()) {
if (FPVal == EMPTY || FPVal == SUPERPOSITION)
return FPVal;
if (MIB->isLeave(Point))
return FPVal + 8;
return FPVal;
}
if (this->BC.MII->get(Point.getOpcode())
.hasDefOfPhysReg(Point, MIB->getStackPointer(), *this->BC.MRI)) {
std::pair<MCPhysReg, int64_t> SP;
if (SPVal != EMPTY && SPVal != SUPERPOSITION)
SP = std::make_pair(MIB->getStackPointer(), SPVal);
else
SP = std::make_pair(0, 0);
std::pair<MCPhysReg, int64_t> FP;
if (FPVal != EMPTY && FPVal != SUPERPOSITION)
FP = std::make_pair(MIB->getFramePointer(), FPVal);
else
FP = std::make_pair(0, 0);
int64_t Output;
if (!MIB->evaluateStackOffsetExpr(Point, Output, SP, FP)) {
if (SPVal == EMPTY && FPVal == EMPTY)
return SPVal;
return SUPERPOSITION;
}
return static_cast<int>(Output);
}
return SPVal;
}
int computeNextFP(const MCInst &Point, int SPVal, int FPVal) {
const auto &MIB = this->BC.MIB;
MCPhysReg From, To;
if (MIB->isRegToRegMove(Point, From, To) && To == MIB->getFramePointer() &&
From == MIB->getStackPointer()) {
HasFramePointer = true;
return SPVal;
}
if (this->BC.MII->get(Point.getOpcode())
.hasDefOfPhysReg(Point, MIB->getFramePointer(), *this->BC.MRI)) {
std::pair<MCPhysReg, int64_t> FP;
if (FPVal != EMPTY && FPVal != SUPERPOSITION)
FP = std::make_pair(MIB->getFramePointer(), FPVal);
else
FP = std::make_pair(0, 0);
std::pair<MCPhysReg, int64_t> SP;
if (SPVal != EMPTY && SPVal != SUPERPOSITION)
SP = std::make_pair(MIB->getStackPointer(), SPVal);
else
SP = std::make_pair(0, 0);
int64_t Output;
if (!MIB->evaluateStackOffsetExpr(Point, Output, SP, FP)) {
if (SPVal == EMPTY && FPVal == EMPTY)
return FPVal;
return SUPERPOSITION;
}
if (!HasFramePointer && MIB->escapesVariable(Point, false))
HasFramePointer = true;
return static_cast<int>(Output);
}
return FPVal;
}
std::pair<int, int> computeNext(const MCInst &Point,
const std::pair<int, int> &Cur) {
return std::make_pair(computeNextSP(Point, Cur.first, Cur.second),
computeNextFP(Point, Cur.first, Cur.second));
}
StringRef getAnnotationName() const {
return StringRef("StackPointerTracking");
}
public:
StackPointerTrackingBase(BinaryFunction &BF,
MCPlusBuilder::AllocatorIdTy AllocatorId = 0)
: DataflowAnalysis<Derived, std::pair<int, int>>(BF, AllocatorId) {}
virtual ~StackPointerTrackingBase() {}
bool HasFramePointer{false};
static constexpr int SUPERPOSITION = std::numeric_limits<int>::max();
static constexpr int EMPTY = std::numeric_limits<int>::min();
};
class StackPointerTracking
: public StackPointerTrackingBase<StackPointerTracking> {
friend class DataflowAnalysis<StackPointerTracking, std::pair<int, int>>;
public:
StackPointerTracking(BinaryFunction &BF,
MCPlusBuilder::AllocatorIdTy AllocatorId = 0);
virtual ~StackPointerTracking() {}
void run() { StackPointerTrackingBase<StackPointerTracking>::run(); }
};
} // end namespace bolt
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
const std::pair<int, int> &Val);
} // end namespace llvm
#endif