6502/llvm-6502
1
0
Fork 0
mirror of https://github.com/c64scene-ar/llvm-6502.git synced 2024-12-12 13:30:51 +00:00
Code Issues Projects Releases Wiki Activity
master
llvm-6502/lib/Target/Hexagon/BitTracker.cpp
Benjamin Kramer 7e320cc2c8 [Hexagon] Use composition instead of inheritance from STL types 
The standard containers are not designed to be inherited from, as
illustrated by the MSVC hacks for NodeOrdering. No functional change
intended.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@242616 91177308-0d34-0410-b5e6-96231b3b80d8
2015-07-18 17:43:23 +00:00

1128 lines
33 KiB
C++
Raw Permalink Blame History

//===--- BitTracker.cpp ---------------------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
// SSA-based bit propagation.
//
// The purpose of this code is, for a given virtual register, to provide
// information about the value of each bit in the register. The values
// of bits are represented by the class BitValue, and take one of four
// cases: 0, 1, "ref" and "bottom". The 0 and 1 are rather clear, the
// "ref" value means that the bit is a copy of another bit (which itself
// cannot be a copy of yet another bit---such chains are not allowed).
// A "ref" value is associated with a BitRef structure, which indicates
// which virtual register, and which bit in that register is the origin
// of the value. For example, given an instruction
// vreg2 = ASL vreg1, 1
// assuming that nothing is known about bits of vreg1, bit 1 of vreg2
// will be a "ref" to (vreg1, 0). If there is a subsequent instruction
// vreg3 = ASL vreg2, 2
// then bit 3 of vreg3 will be a "ref" to (vreg1, 0) as well.
// The "bottom" case means that the bit's value cannot be determined,
// and that this virtual register actually defines it. The "bottom" case
// is discussed in detail in BitTracker.h. In fact, "bottom" is a "ref
// to self", so for the vreg1 above, the bit 0 of it will be a "ref" to
// (vreg1, 0), bit 1 will be a "ref" to (vreg1, 1), etc.
//
// The tracker implements the Wegman-Zadeck algorithm, originally developed
// for SSA-based constant propagation. Each register is represented as
// a sequence of bits, with the convention that bit 0 is the least signi-
// ficant bit. Each bit is propagated individually. The class RegisterCell
// implements the register's representation, and is also the subject of
// the lattice operations in the tracker.
//
// The intended usage of the bit tracker is to create a target-specific
// machine instruction evaluator, pass the evaluator to the BitTracker
// object, and run the tracker. The tracker will then collect the bit
// value information for a given machine function. After that, it can be
// queried for the cells for each virtual register.
// Sample code:
// const TargetSpecificEvaluator TSE(TRI, MRI);
// BitTracker BT(TSE, MF);
// BT.run();
// ...
// unsigned Reg = interestingRegister();
// RegisterCell RC = BT.get(Reg);
// if (RC[3].is(1))
// Reg0bit3 = 1;
//
// The code below is intended to be fully target-independent.
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "BitTracker.h"
using namespace llvm;
typedef BitTracker BT;
namespace {
// Local trickery to pretty print a register (without the whole "%vreg"
// business).
struct printv {
printv(unsigned r) : R(r) {}
unsigned R;
};
raw_ostream &operator<< (raw_ostream &OS, const printv &PV) {
if (PV.R)
OS << 'v' << TargetRegisterInfo::virtReg2Index(PV.R);
else
OS << 's';
return OS;
}
}
raw_ostream &llvm::operator<<(raw_ostream &OS, const BT::BitValue &BV) {
switch (BV.Type) {
case BT::BitValue::Top:
OS << 'T';
break;
case BT::BitValue::Zero:
OS << '0';
break;
case BT::BitValue::One:
OS << '1';
break;
case BT::BitValue::Ref:
OS << printv(BV.RefI.Reg) << '[' << BV.RefI.Pos << ']';
break;
}
return OS;
}
raw_ostream &llvm::operator<<(raw_ostream &OS, const BT::RegisterCell &RC) {
unsigned n = RC.Bits.size();
OS << "{ w:" << n;
// Instead of printing each bit value individually, try to group them
// into logical segments, such as sequences of 0 or 1 bits or references
// to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz").
// "Start" will be the index of the beginning of the most recent segment.
unsigned Start = 0;
bool SeqRef = false; // A sequence of refs to consecutive bits.
bool ConstRef = false; // A sequence of refs to the same bit.
for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) {
const BT::BitValue &V = RC[i];
const BT::BitValue &SV = RC[Start];
bool IsRef = (V.Type == BT::BitValue::Ref);
// If the current value is the same as Start, skip to the next one.
if (!IsRef && V == SV)
continue;
if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) {
if (Start+1 == i) {
SeqRef = (V.RefI.Pos == SV.RefI.Pos+1);
ConstRef = (V.RefI.Pos == SV.RefI.Pos);
}
if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start))
continue;
if (ConstRef && V.RefI.Pos == SV.RefI.Pos)
continue;
}
// The current value is different. Print the previous one and reset
// the Start.
OS << " [" << Start;
unsigned Count = i - Start;
if (Count == 1) {
OS << "]:" << SV;
} else {
OS << '-' << i-1 << "]:";
if (SV.Type == BT::BitValue::Ref && SeqRef)
OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
<< SV.RefI.Pos+(Count-1) << ']';
else
OS << SV;
}
Start = i;
SeqRef = ConstRef = false;
}
OS << " [" << Start;
unsigned Count = n - Start;
if (n-Start == 1) {
OS << "]:" << RC[Start];
} else {
OS << '-' << n-1 << "]:";
const BT::BitValue &SV = RC[Start];
if (SV.Type == BT::BitValue::Ref && SeqRef)
OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
<< SV.RefI.Pos+(Count-1) << ']';
else
OS << SV;
}
OS << " }";
return OS;
}
BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F)
: Trace(false), ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType) {}
BitTracker::~BitTracker() {
delete &Map;
}
// If we were allowed to update a cell for a part of a register, the meet
// operation would need to be parametrized by the register number and the
// exact part of the register, so that the computer BitRefs correspond to
// the actual bits of the "self" register.
// While this cannot happen in the current implementation, I'm not sure
// if this should be ruled out in the future.
bool BT::RegisterCell::meet(const RegisterCell &RC, unsigned SelfR) {
// An example when "meet" can be invoked with SelfR == 0 is a phi node
// with a physical register as an operand.
assert(SelfR == 0 || TargetRegisterInfo::isVirtualRegister(SelfR));
bool Changed = false;
for (uint16_t i = 0, n = Bits.size(); i < n; ++i) {
const BitValue &RCV = RC[i];
Changed |= Bits[i].meet(RCV, BitRef(SelfR, i));
}
return Changed;
}
// Insert the entire cell RC into the current cell at position given by M.
BT::RegisterCell &BT::RegisterCell::insert(const BT::RegisterCell &RC,
const BitMask &M) {
uint16_t B = M.first(), E = M.last(), W = width();
// Sanity: M must be a valid mask for *this.
assert(B < W && E < W);
// Sanity: the masked part of *this must have the same number of bits
// as the source.
assert(B > E || E-B+1 == RC.width()); // B <= E => E-B+1 = |RC|.
assert(B <= E || E+(W-B)+1 == RC.width()); // E < B => E+(W-B)+1 = |RC|.
if (B <= E) {
for (uint16_t i = 0; i <= E-B; ++i)
Bits[i+B] = RC[i];
} else {
for (uint16_t i = 0; i < W-B; ++i)
Bits[i+B] = RC[i];
for (uint16_t i = 0; i <= E; ++i)
Bits[i] = RC[i+(W-B)];
}
return *this;
}
BT::RegisterCell BT::RegisterCell::extract(const BitMask &M) const {
uint16_t B = M.first(), E = M.last(), W = width();
assert(B < W && E < W);
if (B <= E) {
RegisterCell RC(E-B+1);
for (uint16_t i = B; i <= E; ++i)
RC.Bits[i-B] = Bits[i];
return RC;
}
RegisterCell RC(E+(W-B)+1);
for (uint16_t i = 0; i < W-B; ++i)
RC.Bits[i] = Bits[i+B];
for (uint16_t i = 0; i <= E; ++i)
RC.Bits[i+(W-B)] = Bits[i];
return RC;
}
BT::RegisterCell &BT::RegisterCell::rol(uint16_t Sh) {
// Rotate left (i.e. towards increasing bit indices).
// Swap the two parts: [0..W-Sh-1] [W-Sh..W-1]
uint16_t W = width();
Sh = Sh % W;
if (Sh == 0)
return *this;
RegisterCell Tmp(W-Sh);
// Tmp = [0..W-Sh-1].
for (uint16_t i = 0; i < W-Sh; ++i)
Tmp[i] = Bits[i];
// Shift [W-Sh..W-1] to [0..Sh-1].
for (uint16_t i = 0; i < Sh; ++i)
Bits[i] = Bits[W-Sh+i];
// Copy Tmp to [Sh..W-1].
for (uint16_t i = 0; i < W-Sh; ++i)
Bits[i+Sh] = Tmp.Bits[i];
return *this;
}
BT::RegisterCell &BT::RegisterCell::fill(uint16_t B, uint16_t E,
const BitValue &V) {
assert(B <= E);
while (B < E)
Bits[B++] = V;
return *this;
}
BT::RegisterCell &BT::RegisterCell::cat(const RegisterCell &RC) {
// Append the cell given as the argument to the "this" cell.
// Bit 0 of RC becomes bit W of the result, where W is this->width().
uint16_t W = width(), WRC = RC.width();
Bits.resize(W+WRC);
for (uint16_t i = 0; i < WRC; ++i)
Bits[i+W] = RC.Bits[i];
return *this;
}
uint16_t BT::RegisterCell::ct(bool B) const {
uint16_t W = width();
uint16_t C = 0;
BitValue V = B;
while (C < W && Bits[C] == V)
C++;
return C;
}
uint16_t BT::RegisterCell::cl(bool B) const {
uint16_t W = width();
uint16_t C = 0;
BitValue V = B;
while (C < W && Bits[W-(C+1)] == V)
C++;
return C;
}
bool BT::RegisterCell::operator== (const RegisterCell &RC) const {
uint16_t W = Bits.size();
if (RC.Bits.size() != W)
return false;
for (uint16_t i = 0; i < W; ++i)
if (Bits[i] != RC[i])
return false;
return true;
}
uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const {
// The general problem is with finding a register class that corresponds
// to a given reference reg:sub. There can be several such classes, and
// since we only care about the register size, it does not matter which
// such class we would find.
// The easiest way to accomplish what we want is to
// 1. find a physical register PhysR from the same class as RR.Reg,
// 2. find a physical register PhysS that corresponds to PhysR:RR.Sub,
// 3. find a register class that contains PhysS.
unsigned PhysR;
if (TargetRegisterInfo::isVirtualRegister(RR.Reg)) {
const TargetRegisterClass *VC = MRI.getRegClass(RR.Reg);
assert(VC->begin() != VC->end() && "Empty register class");
PhysR = *VC->begin();
} else {
assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg));
PhysR = RR.Reg;
}
unsigned PhysS = (RR.Sub == 0) ? PhysR : TRI.getSubReg(PhysR, RR.Sub);
const TargetRegisterClass *RC = TRI.getMinimalPhysRegClass(PhysS);
uint16_t BW = RC->getSize()*8;
return BW;
}
BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR,
const CellMapType &M) const {
uint16_t BW = getRegBitWidth(RR);
// Physical registers are assumed to be present in the map with an unknown
// value. Don't actually insert anything in the map, just return the cell.
if (TargetRegisterInfo::isPhysicalRegister(RR.Reg))
return RegisterCell::self(0, BW);
assert(TargetRegisterInfo::isVirtualRegister(RR.Reg));
// For virtual registers that belong to a class that is not tracked,
// generate an "unknown" value as well.
const TargetRegisterClass *C = MRI.getRegClass(RR.Reg);
if (!track(C))
return RegisterCell::self(0, BW);
CellMapType::const_iterator F = M.find(RR.Reg);
if (F != M.end()) {
if (!RR.Sub)
return F->second;
BitMask M = mask(RR.Reg, RR.Sub);
return F->second.extract(M);
}
// If not found, create a "top" entry, but do not insert it in the map.
return RegisterCell::top(BW);
}
void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC,
CellMapType &M) const {
// While updating the cell map can be done in a meaningful way for
// a part of a register, it makes little sense to implement it as the
// SSA representation would never contain such "partial definitions".
if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
return;
assert(RR.Sub == 0 && "Unexpected sub-register in definition");
// Eliminate all ref-to-reg-0 bit values: replace them with "self".
for (unsigned i = 0, n = RC.width(); i < n; ++i) {
const BitValue &V = RC[i];
if (V.Type == BitValue::Ref && V.RefI.Reg == 0)
RC[i].RefI = BitRef(RR.Reg, i);
}
M[RR.Reg] = RC;
}
// Check if the cell represents a compile-time integer value.
bool BT::MachineEvaluator::isInt(const RegisterCell &A) const {
uint16_t W = A.width();
for (uint16_t i = 0; i < W; ++i)
if (!A[i].is(0) && !A[i].is(1))
return false;
return true;
}
// Convert a cell to the integer value. The result must fit in uint64_t.
uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const {
assert(isInt(A));
uint64_t Val = 0;
uint16_t W = A.width();
for (uint16_t i = 0; i < W; ++i) {
Val <<= 1;
Val |= A[i].is(1);
}
return Val;
}
// Evaluator helper functions. These implement some common operation on
// register cells that can be used to implement target-specific instructions
// in a target-specific evaluator.
BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const {
RegisterCell Res(W);
// For bits beyond the 63rd, this will generate the sign bit of V.
for (uint16_t i = 0; i < W; ++i) {
Res[i] = BitValue(V & 1);
V >>= 1;
}
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const {
APInt A = CI->getValue();
uint16_t BW = A.getBitWidth();
assert((unsigned)BW == A.getBitWidth() && "BitWidth overflow");
RegisterCell Res(BW);
for (uint16_t i = 0; i < BW; ++i)
Res[i] = A[i];
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1,
const RegisterCell &A2) const {
uint16_t W = A1.width();
assert(W == A2.width());
RegisterCell Res(W);
bool Carry = false;
uint16_t I;
for (I = 0; I < W; ++I) {
const BitValue &V1 = A1[I];
const BitValue &V2 = A2[I];
if (!V1.num() || !V2.num())
break;
unsigned S = bool(V1) + bool(V2) + Carry;
Res[I] = BitValue(S & 1);
Carry = (S > 1);
}
for (; I < W; ++I) {
const BitValue &V1 = A1[I];
const BitValue &V2 = A2[I];
// If the next bit is same as Carry, the result will be 0 plus the
// other bit. The Carry bit will remain unchanged.
if (V1.is(Carry))
Res[I] = BitValue::ref(V2);
else if (V2.is(Carry))
Res[I] = BitValue::ref(V1);
else
break;
}
for (; I < W; ++I)
Res[I] = BitValue::self();
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1,
const RegisterCell &A2) const {
uint16_t W = A1.width();
assert(W == A2.width());
RegisterCell Res(W);
bool Borrow = false;
uint16_t I;
for (I = 0; I < W; ++I) {
const BitValue &V1 = A1[I];
const BitValue &V2 = A2[I];
if (!V1.num() || !V2.num())
break;
unsigned S = bool(V1) - bool(V2) - Borrow;
Res[I] = BitValue(S & 1);
Borrow = (S > 1);
}
for (; I < W; ++I) {
const BitValue &V1 = A1[I];
const BitValue &V2 = A2[I];
if (V1.is(Borrow)) {
Res[I] = BitValue::ref(V2);
break;
}
if (V2.is(Borrow))
Res[I] = BitValue::ref(V1);
else
break;
}
for (; I < W; ++I)
Res[I] = BitValue::self();
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1,
const RegisterCell &A2) const {
uint16_t W = A1.width() + A2.width();
uint16_t Z = A1.ct(0) + A2.ct(0);
RegisterCell Res(W);
Res.fill(0, Z, BitValue::Zero);
Res.fill(Z, W, BitValue::self());
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1,
const RegisterCell &A2) const {
uint16_t W = A1.width() + A2.width();
uint16_t Z = A1.ct(0) + A2.ct(0);
RegisterCell Res(W);
Res.fill(0, Z, BitValue::Zero);
Res.fill(Z, W, BitValue::self());
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1,
uint16_t Sh) const {
assert(Sh <= A1.width());
RegisterCell Res = RegisterCell::ref(A1);
Res.rol(Sh);
Res.fill(0, Sh, BitValue::Zero);
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1,
uint16_t Sh) const {
uint16_t W = A1.width();
assert(Sh <= W);
RegisterCell Res = RegisterCell::ref(A1);
Res.rol(W-Sh);
Res.fill(W-Sh, W, BitValue::Zero);
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1,
uint16_t Sh) const {
uint16_t W = A1.width();
assert(Sh <= W);
RegisterCell Res = RegisterCell::ref(A1);
BitValue Sign = Res[W-1];
Res.rol(W-Sh);
Res.fill(W-Sh, W, Sign);
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1,
const RegisterCell &A2) const {
uint16_t W = A1.width();
assert(W == A2.width());
RegisterCell Res(W);
for (uint16_t i = 0; i < W; ++i) {
const BitValue &V1 = A1[i];
const BitValue &V2 = A2[i];
if (V1.is(1))
Res[i] = BitValue::ref(V2);
else if (V2.is(1))
Res[i] = BitValue::ref(V1);
else if (V1.is(0) || V2.is(0))
Res[i] = BitValue::Zero;
else if (V1 == V2)
Res[i] = V1;
else
Res[i] = BitValue::self();
}
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1,
const RegisterCell &A2) const {
uint16_t W = A1.width();
assert(W == A2.width());
RegisterCell Res(W);
for (uint16_t i = 0; i < W; ++i) {
const BitValue &V1 = A1[i];
const BitValue &V2 = A2[i];
if (V1.is(1) || V2.is(1))
Res[i] = BitValue::One;
else if (V1.is(0))
Res[i] = BitValue::ref(V2);
else if (V2.is(0))
Res[i] = BitValue::ref(V1);
else if (V1 == V2)
Res[i] = V1;
else
Res[i] = BitValue::self();
}
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1,
const RegisterCell &A2) const {
uint16_t W = A1.width();
assert(W == A2.width());
RegisterCell Res(W);
for (uint16_t i = 0; i < W; ++i) {
const BitValue &V1 = A1[i];
const BitValue &V2 = A2[i];
if (V1.is(0))
Res[i] = BitValue::ref(V2);
else if (V2.is(0))
Res[i] = BitValue::ref(V1);
else if (V1 == V2)
Res[i] = BitValue::Zero;
else
Res[i] = BitValue::self();
}
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const {
uint16_t W = A1.width();
RegisterCell Res(W);
for (uint16_t i = 0; i < W; ++i) {
const BitValue &V = A1[i];
if (V.is(0))
Res[i] = BitValue::One;
else if (V.is(1))
Res[i] = BitValue::Zero;
else
Res[i] = BitValue::self();
}
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1,
uint16_t BitN) const {
assert(BitN < A1.width());
RegisterCell Res = RegisterCell::ref(A1);
Res[BitN] = BitValue::One;
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1,
uint16_t BitN) const {
assert(BitN < A1.width());
RegisterCell Res = RegisterCell::ref(A1);
Res[BitN] = BitValue::Zero;
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B,
uint16_t W) const {
uint16_t C = A1.cl(B), AW = A1.width();
// If the last leading non-B bit is not a constant, then we don't know
// the real count.
if ((C < AW && A1[AW-1-C].num()) || C == AW)
return eIMM(C, W);
return RegisterCell::self(0, W);
}
BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B,
uint16_t W) const {
uint16_t C = A1.ct(B), AW = A1.width();
// If the last trailing non-B bit is not a constant, then we don't know
// the real count.
if ((C < AW && A1[C].num()) || C == AW)
return eIMM(C, W);
return RegisterCell::self(0, W);
}
BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1,
uint16_t FromN) const {
uint16_t W = A1.width();
assert(FromN <= W);
RegisterCell Res = RegisterCell::ref(A1);
BitValue Sign = Res[FromN-1];
// Sign-extend "inreg".
Res.fill(FromN, W, Sign);
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1,
uint16_t FromN) const {
uint16_t W = A1.width();
assert(FromN <= W);
RegisterCell Res = RegisterCell::ref(A1);
Res.fill(FromN, W, BitValue::Zero);
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1,
uint16_t B, uint16_t E) const {
uint16_t W = A1.width();
assert(B < W && E <= W);
if (B == E)
return RegisterCell(0);
uint16_t Last = (E > 0) ? E-1 : W-1;
RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last));
// Return shorter cell.
return Res;
}
BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1,
const RegisterCell &A2, uint16_t AtN) const {
uint16_t W1 = A1.width(), W2 = A2.width();
(void)W1;
assert(AtN < W1 && AtN+W2 <= W1);
// Copy bits from A1, insert A2 at position AtN.
RegisterCell Res = RegisterCell::ref(A1);
if (W2 > 0)
Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1));
return Res;
}
BT::BitMask BT::MachineEvaluator::mask(unsigned Reg, unsigned Sub) const {
assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0");
uint16_t W = getRegBitWidth(Reg);
assert(W > 0 && "Cannot generate mask for empty register");
return BitMask(0, W-1);
}
bool BT::MachineEvaluator::evaluate(const MachineInstr *MI,
const CellMapType &Inputs, CellMapType &Outputs) const {
unsigned Opc = MI->getOpcode();
switch (Opc) {
case TargetOpcode::REG_SEQUENCE: {
RegisterRef RD = MI->getOperand(0);
assert(RD.Sub == 0);
RegisterRef RS = MI->getOperand(1);
unsigned SS = MI->getOperand(2).getImm();
RegisterRef RT = MI->getOperand(3);
unsigned ST = MI->getOperand(4).getImm();
assert(SS != ST);
uint16_t W = getRegBitWidth(RD);
RegisterCell Res(W);
Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS));
Res.insert(RegisterCell::ref(getCell(RT, Inputs)), mask(RD.Reg, ST));
putCell(RD, Res, Outputs);
break;
}
case TargetOpcode::COPY: {
// COPY can transfer a smaller register into a wider one.
// If that is the case, fill the remaining high bits with 0.
RegisterRef RD = MI->getOperand(0);
RegisterRef RS = MI->getOperand(1);
assert(RD.Sub == 0);
uint16_t WD = getRegBitWidth(RD);
uint16_t WS = getRegBitWidth(RS);
assert(WD >= WS);
RegisterCell Src = getCell(RS, Inputs);
RegisterCell Res(WD);
Res.insert(Src, BitMask(0, WS-1));
Res.fill(WS, WD, BitValue::Zero);
putCell(RD, Res, Outputs);
break;
}
default:
return false;
}
return true;
}
// Main W-Z implementation.
void BT::visitPHI(const MachineInstr *PI) {
int ThisN = PI->getParent()->getNumber();
if (Trace)
dbgs() << "Visit FI(BB#" << ThisN << "): " << *PI;
const MachineOperand &MD = PI->getOperand(0);
assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition");
RegisterRef DefRR(MD);
uint16_t DefBW = ME.getRegBitWidth(DefRR);
RegisterCell DefC = ME.getCell(DefRR, Map);
if (DefC == RegisterCell::self(DefRR.Reg, DefBW)) // XXX slow
return;
bool Changed = false;
for (unsigned i = 1, n = PI->getNumOperands(); i < n; i += 2) {
const MachineBasicBlock *PB = PI->getOperand(i+1).getMBB();
int PredN = PB->getNumber();
if (Trace)
dbgs() << " edge BB#" << PredN << "->BB#" << ThisN;
if (!EdgeExec.count(CFGEdge(PredN, ThisN))) {
if (Trace)
dbgs() << " not executable\n";
continue;
}
RegisterRef RU = PI->getOperand(i);
RegisterCell ResC = ME.getCell(RU, Map);
if (Trace)
dbgs() << " input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub)
<< " cell: " << ResC << "\n";
Changed |= DefC.meet(ResC, DefRR.Reg);
}
if (Changed) {
if (Trace)
dbgs() << "Output: " << PrintReg(DefRR.Reg, &ME.TRI, DefRR.Sub)
<< " cell: " << DefC << "\n";
ME.putCell(DefRR, DefC, Map);
visitUsesOf(DefRR.Reg);
}
}
void BT::visitNonBranch(const MachineInstr *MI) {
if (Trace) {
int ThisN = MI->getParent()->getNumber();
dbgs() << "Visit MI(BB#" << ThisN << "): " << *MI;
}
if (MI->isDebugValue())
return;
assert(!MI->isBranch() && "Unexpected branch instruction");
CellMapType ResMap;
bool Eval = ME.evaluate(MI, Map, ResMap);
if (Trace && Eval) {
for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
const MachineOperand &MO = MI->getOperand(i);
if (!MO.isReg() || !MO.isUse())
continue;
RegisterRef RU(MO);
dbgs() << " input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub)
<< " cell: " << ME.getCell(RU, Map) << "\n";
}
dbgs() << "Outputs:\n";
for (CellMapType::iterator I = ResMap.begin(), E = ResMap.end();
I != E; ++I) {
RegisterRef RD(I->first);
dbgs() << " " << PrintReg(I->first, &ME.TRI) << " cell: "
<< ME.getCell(RD, ResMap) << "\n";
}
}
// Iterate over all definitions of the instruction, and update the
// cells accordingly.
for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
const MachineOperand &MO = MI->getOperand(i);
// Visit register defs only.
if (!MO.isReg() || !MO.isDef())
continue;
RegisterRef RD(MO);
assert(RD.Sub == 0 && "Unexpected sub-register in definition");
if (!TargetRegisterInfo::isVirtualRegister(RD.Reg))
continue;
bool Changed = false;
if (!Eval || ResMap.count(RD.Reg) == 0) {
// Set to "ref" (aka "bottom").
uint16_t DefBW = ME.getRegBitWidth(RD);
RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW);
if (RefC != ME.getCell(RD, Map)) {
ME.putCell(RD, RefC, Map);
Changed = true;
}
} else {
RegisterCell DefC = ME.getCell(RD, Map);
RegisterCell ResC = ME.getCell(RD, ResMap);
// This is a non-phi instruction, so the values of the inputs come
// from the same registers each time this instruction is evaluated.
// During the propagation, the values of the inputs can become lowered
// in the sense of the lattice operation, which may cause different
// results to be calculated in subsequent evaluations. This should
// not cause the bottoming of the result in the map, since the new
// result is already reflecting the lowered inputs.
for (uint16_t i = 0, w = DefC.width(); i < w; ++i) {
BitValue &V = DefC[i];
// Bits that are already "bottom" should not be updated.
if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg)
continue;
// Same for those that are identical in DefC and ResC.
if (V == ResC[i])
continue;
V = ResC[i];
Changed = true;
}
if (Changed)
ME.putCell(RD, DefC, Map);
}
if (Changed)
visitUsesOf(RD.Reg);
}
}
void BT::visitBranchesFrom(const MachineInstr *BI) {
const MachineBasicBlock &B = *BI->getParent();
MachineBasicBlock::const_iterator It = BI, End = B.end();
BranchTargetList Targets, BTs;
bool FallsThrough = true, DefaultToAll = false;
int ThisN = B.getNumber();
do {
BTs.clear();
const MachineInstr *MI = &*It;
if (Trace)
dbgs() << "Visit BR(BB#" << ThisN << "): " << *MI;
assert(MI->isBranch() && "Expecting branch instruction");
InstrExec.insert(MI);
bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough);
if (!Eval) {
// If the evaluation failed, we will add all targets. Keep going in
// the loop to mark all executable branches as such.
DefaultToAll = true;
FallsThrough = true;
if (Trace)
dbgs() << " failed to evaluate: will add all CFG successors\n";
} else if (!DefaultToAll) {
// If evaluated successfully add the targets to the cumulative list.
if (Trace) {
dbgs() << " adding targets:";
for (unsigned i = 0, n = BTs.size(); i < n; ++i)
dbgs() << " BB#" << BTs[i]->getNumber();
if (FallsThrough)
dbgs() << "\n falls through\n";
else
dbgs() << "\n does not fall through\n";
}
Targets.insert(BTs.begin(), BTs.end());
}
++It;
} while (FallsThrough && It != End);
typedef MachineBasicBlock::const_succ_iterator succ_iterator;
if (!DefaultToAll) {
// Need to add all CFG successors that lead to EH landing pads.
// There won't be explicit branches to these blocks, but they must
// be processed.
for (succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I) {
const MachineBasicBlock *SB = *I;
if (SB->isLandingPad())
Targets.insert(SB);
}
if (FallsThrough) {
MachineFunction::const_iterator BIt = &B;
MachineFunction::const_iterator Next = std::next(BIt);
if (Next != MF.end())
Targets.insert(&*Next);
}
} else {
for (succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I)
Targets.insert(*I);
}
for (unsigned i = 0, n = Targets.size(); i < n; ++i) {
int TargetN = Targets[i]->getNumber();
FlowQ.push(CFGEdge(ThisN, TargetN));
}
}
void BT::visitUsesOf(unsigned Reg) {
if (Trace)
dbgs() << "visiting uses of " << PrintReg(Reg, &ME.TRI) << "\n";
typedef MachineRegisterInfo::use_nodbg_iterator use_iterator;
use_iterator End = MRI.use_nodbg_end();
for (use_iterator I = MRI.use_nodbg_begin(Reg); I != End; ++I) {
MachineInstr *UseI = I->getParent();
if (!InstrExec.count(UseI))
continue;
if (UseI->isPHI())
visitPHI(UseI);
else if (!UseI->isBranch())
visitNonBranch(UseI);
else
visitBranchesFrom(UseI);
}
}
BT::RegisterCell BT::get(RegisterRef RR) const {
return ME.getCell(RR, Map);
}
void BT::put(RegisterRef RR, const RegisterCell &RC) {
ME.putCell(RR, RC, Map);
}
// Replace all references to bits from OldRR with the corresponding bits
// in NewRR.
void BT::subst(RegisterRef OldRR, RegisterRef NewRR) {
assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map");
BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub);
BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub);
uint16_t OMB = OM.first(), OME = OM.last();
uint16_t NMB = NM.first(), NME = NM.last();
(void)NME;
assert((OME-OMB == NME-NMB) &&
"Substituting registers of different lengths");
for (CellMapType::iterator I = Map.begin(), E = Map.end(); I != E; ++I) {
RegisterCell &RC = I->second;
for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
BitValue &V = RC[i];
if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg)
continue;
if (V.RefI.Pos < OMB || V.RefI.Pos > OME)
continue;
V.RefI.Reg = NewRR.Reg;
V.RefI.Pos += NMB-OMB;
}
}
}
// Check if the block has been "executed" during propagation. (If not, the
// block is dead, but it may still appear to be reachable.)
bool BT::reached(const MachineBasicBlock *B) const {
int BN = B->getNumber();
assert(BN >= 0);
for (EdgeSetType::iterator I = EdgeExec.begin(), E = EdgeExec.end();
I != E; ++I) {
if (I->second == BN)
return true;
}
return false;
}
void BT::reset() {
EdgeExec.clear();
InstrExec.clear();
Map.clear();
}
void BT::run() {
reset();
assert(FlowQ.empty());
typedef GraphTraits<const MachineFunction*> MachineFlowGraphTraits;
const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF);
unsigned MaxBN = 0;
for (MachineFunction::const_iterator I = MF.begin(), E = MF.end();
I != E; ++I) {
assert(I->getNumber() >= 0 && "Disconnected block");
unsigned BN = I->getNumber();
if (BN > MaxBN)
MaxBN = BN;
}
// Keep track of visited blocks.
BitVector BlockScanned(MaxBN+1);
int EntryN = Entry->getNumber();
// Generate a fake edge to get something to start with.
FlowQ.push(CFGEdge(-1, EntryN));
while (!FlowQ.empty()) {
CFGEdge Edge = FlowQ.front();
FlowQ.pop();
if (EdgeExec.count(Edge))
continue;
EdgeExec.insert(Edge);
const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second);
MachineBasicBlock::const_iterator It = B.begin(), End = B.end();
// Visit PHI nodes first.
while (It != End && It->isPHI()) {
const MachineInstr *PI = &*It++;
InstrExec.insert(PI);
visitPHI(PI);
}
// If this block has already been visited through a flow graph edge,
// then the instructions have already been processed. Any updates to
// the cells would now only happen through visitUsesOf...
if (BlockScanned[Edge.second])
continue;
BlockScanned[Edge.second] = true;
// Visit non-branch instructions.
while (It != End && !It->isBranch()) {
const MachineInstr *MI = &*It++;
InstrExec.insert(MI);
visitNonBranch(MI);
}
// If block end has been reached, add the fall-through edge to the queue.
if (It == End) {
MachineFunction::const_iterator BIt = &B;
MachineFunction::const_iterator Next = std::next(BIt);
if (Next != MF.end()) {
int ThisN = B.getNumber();
int NextN = Next->getNumber();
FlowQ.push(CFGEdge(ThisN, NextN));
}
} else {
// Handle the remaining sequence of branches. This function will update
// the work queue.
visitBranchesFrom(It);
}
} // while (!FlowQ->empty())
if (Trace) {
dbgs() << "Cells after propagation:\n";
for (CellMapType::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
dbgs() << PrintReg(I->first, &ME.TRI) << " -> " << I->second << "\n";
}
}
Reference in New Issue View Git Blame Copy Permalink