blob: e830eb20fec0bb7f655a4a4be3aa9890f177f49b [file] [log] [blame]
//===-- BPFISelDAGToDAG.cpp - A dag to dag inst selector for BPF ----------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file defines a DAG pattern matching instruction selector for BPF,
// converting from a legalized dag to a BPF dag.
//
//===----------------------------------------------------------------------===//
#include "BPF.h"
#include "BPFRegisterInfo.h"
#include "BPFSubtarget.h"
#include "BPFTargetMachine.h"
#include "llvm/CodeGen/FunctionLoweringInfo.h"
#include "llvm/CodeGen/MachineConstantPool.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/IntrinsicsBPF.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Endian.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
using namespace llvm;
#define DEBUG_TYPE "bpf-isel"
#define PASS_NAME "BPF DAG->DAG Pattern Instruction Selection"
// Instruction Selector Implementation
namespace {
class BPFDAGToDAGISel : public SelectionDAGISel {
/// Subtarget - Keep a pointer to the BPFSubtarget around so that we can
/// make the right decision when generating code for different subtargets.
const BPFSubtarget *Subtarget;
public:
static char ID;
BPFDAGToDAGISel() = delete;
explicit BPFDAGToDAGISel(BPFTargetMachine &TM)
: SelectionDAGISel(ID, TM), Subtarget(nullptr) {}
bool runOnMachineFunction(MachineFunction &MF) override {
// Reset the subtarget each time through.
Subtarget = &MF.getSubtarget<BPFSubtarget>();
return SelectionDAGISel::runOnMachineFunction(MF);
}
void PreprocessISelDAG() override;
bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintCode,
std::vector<SDValue> &OutOps) override;
private:
// Include the pieces autogenerated from the target description.
#include "BPFGenDAGISel.inc"
void Select(SDNode *N) override;
// Complex Pattern for address selection.
bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
// Node preprocessing cases
void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator &I);
void PreprocessCopyToReg(SDNode *Node);
void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator &I);
// Find constants from a constant structure
typedef std::vector<unsigned char> val_vec_type;
bool fillGenericConstant(const DataLayout &DL, const Constant *CV,
val_vec_type &Vals, uint64_t Offset);
bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA,
val_vec_type &Vals, int Offset);
bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA,
val_vec_type &Vals, int Offset);
bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS,
val_vec_type &Vals, int Offset);
bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset,
uint64_t Size, unsigned char *ByteSeq);
// Mapping from ConstantStruct global value to corresponding byte-list values
std::map<const void *, val_vec_type> cs_vals_;
};
} // namespace
char BPFDAGToDAGISel::ID = 0;
INITIALIZE_PASS(BPFDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false)
// ComplexPattern used on BPF Load/Store instructions
bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) {
// if Address is FI, get the TargetFrameIndex.
SDLoc DL(Addr);
if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
return true;
}
if (Addr.getOpcode() == ISD::TargetExternalSymbol ||
Addr.getOpcode() == ISD::TargetGlobalAddress)
return false;
// Addresses of the form Addr+const or Addr|const
if (CurDAG->isBaseWithConstantOffset(Addr)) {
auto *CN = cast<ConstantSDNode>(Addr.getOperand(1));
if (isInt<16>(CN->getSExtValue())) {
// If the first operand is a FI, get the TargetFI Node
if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
else
Base = Addr.getOperand(0);
Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
return true;
}
}
Base = Addr;
Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
return true;
}
// ComplexPattern used on BPF FI instruction
bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base,
SDValue &Offset) {
SDLoc DL(Addr);
if (!CurDAG->isBaseWithConstantOffset(Addr))
return false;
// Addresses of the form Addr+const or Addr|const
auto *CN = cast<ConstantSDNode>(Addr.getOperand(1));
if (isInt<16>(CN->getSExtValue())) {
// If the first operand is a FI, get the TargetFI Node
if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
else
return false;
Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
return true;
}
return false;
}
bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand(
const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) {
SDValue Op0, Op1;
switch (ConstraintCode) {
default:
return true;
case InlineAsm::Constraint_m: // memory
if (!SelectAddr(Op, Op0, Op1))
return true;
break;
}
SDLoc DL(Op);
SDValue AluOp = CurDAG->getTargetConstant(ISD::ADD, DL, MVT::i32);;
OutOps.push_back(Op0);
OutOps.push_back(Op1);
OutOps.push_back(AluOp);
return false;
}
void BPFDAGToDAGISel::Select(SDNode *Node) {
unsigned Opcode = Node->getOpcode();
// If we have a custom node, we already have selected!
if (Node->isMachineOpcode()) {
LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n');
return;
}
// tablegen selection should be handled here.
switch (Opcode) {
default:
break;
case ISD::SDIV: {
DebugLoc Empty;
const DebugLoc &DL = Node->getDebugLoc();
if (DL != Empty)
errs() << "Error at line " << DL.getLine() << ": ";
else
errs() << "Error: ";
errs() << "Unsupport signed division for DAG: ";
Node->print(errs(), CurDAG);
errs() << "Please convert to unsigned div/mod.\n";
break;
}
case ISD::INTRINSIC_W_CHAIN: {
unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
switch (IntNo) {
case Intrinsic::bpf_load_byte:
case Intrinsic::bpf_load_half:
case Intrinsic::bpf_load_word: {
SDLoc DL(Node);
SDValue Chain = Node->getOperand(0);
SDValue N1 = Node->getOperand(1);
SDValue Skb = Node->getOperand(2);
SDValue N3 = Node->getOperand(3);
SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
break;
}
}
break;
}
case ISD::FrameIndex: {
int FI = cast<FrameIndexSDNode>(Node)->getIndex();
EVT VT = Node->getValueType(0);
SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
unsigned Opc = BPF::MOV_rr;
if (Node->hasOneUse()) {
CurDAG->SelectNodeTo(Node, Opc, VT, TFI);
return;
}
ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));
return;
}
}
// Select the default instruction
SelectCode(Node);
}
void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,
SelectionDAG::allnodes_iterator &I) {
union {
uint8_t c[8];
uint16_t s;
uint32_t i;
uint64_t d;
} new_val; // hold up the constant values replacing loads.
bool to_replace = false;
SDLoc DL(Node);
const LoadSDNode *LD = cast<LoadSDNode>(Node);
uint64_t size = LD->getMemOperand()->getSize();
if (!size || size > 8 || (size & (size - 1)) || !LD->isSimple())
return;
SDNode *LDAddrNode = LD->getOperand(1).getNode();
// Match LDAddr against either global_addr or (global_addr + offset)
unsigned opcode = LDAddrNode->getOpcode();
if (opcode == ISD::ADD) {
SDValue OP1 = LDAddrNode->getOperand(0);
SDValue OP2 = LDAddrNode->getOperand(1);
// We want to find the pattern global_addr + offset
SDNode *OP1N = OP1.getNode();
if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0)
return;
LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
const GlobalAddressSDNode *GADN =
dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode());
const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode());
if (GADN && CDN)
to_replace =
getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c);
} else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&
LDAddrNode->getNumOperands() > 0) {
LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
SDValue OP1 = LDAddrNode->getOperand(0);
if (const GlobalAddressSDNode *GADN =
dyn_cast<GlobalAddressSDNode>(OP1.getNode()))
to_replace = getConstantFieldValue(GADN, 0, size, new_val.c);
}
if (!to_replace)
return;
// replacing the old with a new value
uint64_t val;
if (size == 1)
val = new_val.c[0];
else if (size == 2)
val = new_val.s;
else if (size == 4)
val = new_val.i;
else {
val = new_val.d;
}
LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant "
<< val << '\n');
SDValue NVal = CurDAG->getConstant(val, DL, LD->getValueType(0));
// After replacement, the current node is dead, we need to
// go backward one step to make iterator still work
I--;
SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};
SDValue To[] = {NVal, NVal};
CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2);
I++;
// It is safe to delete node now
CurDAG->DeleteNode(Node);
}
void BPFDAGToDAGISel::PreprocessISelDAG() {
// Iterate through all nodes, interested in the following case:
//
// . loads from ConstantStruct or ConstantArray of constructs
// which can be turns into constant itself, with this we can
// avoid reading from read-only section at runtime.
//
// . Removing redundant AND for intrinsic narrow loads.
for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
E = CurDAG->allnodes_end();
I != E;) {
SDNode *Node = &*I++;
unsigned Opcode = Node->getOpcode();
if (Opcode == ISD::LOAD)
PreprocessLoad(Node, I);
else if (Opcode == ISD::AND)
PreprocessTrunc(Node, I);
}
}
bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
uint64_t Offset, uint64_t Size,
unsigned char *ByteSeq) {
const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
if (!V || !V->hasInitializer() || !V->isConstant())
return false;
const Constant *Init = V->getInitializer();
const DataLayout &DL = CurDAG->getDataLayout();
val_vec_type TmpVal;
auto it = cs_vals_.find(static_cast<const void *>(Init));
if (it != cs_vals_.end()) {
TmpVal = it->second;
} else {
uint64_t total_size = 0;
if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
total_size =
DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
CA->getNumOperands();
else
return false;
val_vec_type Vals(total_size, 0);
if (fillGenericConstant(DL, Init, Vals, 0) == false)
return false;
cs_vals_[static_cast<const void *>(Init)] = Vals;
TmpVal = std::move(Vals);
}
// test whether host endianness matches target
union {
uint8_t c[2];
uint16_t s;
} test_buf;
uint16_t test_val = 0x2345;
if (DL.isLittleEndian())
support::endian::write16le(test_buf.c, test_val);
else
support::endian::write16be(test_buf.c, test_val);
bool endian_match = test_buf.s == test_val;
for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
return true;
}
bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
const Constant *CV,
val_vec_type &Vals, uint64_t Offset) {
uint64_t Size = DL.getTypeAllocSize(CV->getType());
if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))
return true; // already done
if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
uint64_t val = CI->getZExtValue();
LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value "
<< val << '\n');
if (Size > 8 || (Size & (Size - 1)))
return false;
// Store based on target endian
for (uint64_t i = 0; i < Size; ++i) {
Vals[Offset + i] = DL.isLittleEndian()
? ((val >> (i * 8)) & 0xFF)
: ((val >> ((Size - i - 1) * 8)) & 0xFF);
}
return true;
}
if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
return fillConstantDataArray(DL, CDA, Vals, Offset);
if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
return fillConstantArray(DL, CA, Vals, Offset);
if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
return fillConstantStruct(DL, CVS, Vals, Offset);
return false;
}
bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
const ConstantDataArray *CDA,
val_vec_type &Vals, int Offset) {
for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
false)
return false;
Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
}
return true;
}
bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
const ConstantArray *CA,
val_vec_type &Vals, int Offset) {
for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
return false;
Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
}
return true;
}
bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
const ConstantStruct *CS,
val_vec_type &Vals, int Offset) {
const StructLayout *Layout = DL.getStructLayout(CS->getType());
for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
const Constant *Field = CS->getOperand(i);
uint64_t SizeSoFar = Layout->getElementOffset(i);
if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
return false;
}
return true;
}
void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
SelectionDAG::allnodes_iterator &I) {
ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
if (!MaskN)
return;
// The Reg operand should be a virtual register, which is defined
// outside the current basic block. DAG combiner has done a pretty
// good job in removing truncating inside a single basic block except
// when the Reg operand comes from bpf_load_[byte | half | word] for
// which the generic optimizer doesn't understand their results are
// zero extended.
SDValue BaseV = Node->getOperand(0);
if (BaseV.getOpcode() != ISD::INTRINSIC_W_CHAIN)
return;
unsigned IntNo = cast<ConstantSDNode>(BaseV->getOperand(1))->getZExtValue();
uint64_t MaskV = MaskN->getZExtValue();
if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) ||
(IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) ||
(IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF)))
return;
LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: ";
Node->dump(); dbgs() << '\n');
I--;
CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
I++;
CurDAG->DeleteNode(Node);
}
FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
return new BPFDAGToDAGISel(TM);
}