llvm/llvm/lib/Target/BPF/BPFCheckAndAdjustIR.cpp

//===------------ BPFCheckAndAdjustIR.cpp - Check and Adjust IR -----------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// Check IR and adjust IR for verifier friendly codes.
// The following are done for IR checking:
//   - no relocation globals in PHI node.
// The following are done for IR adjustment:
//   - remove __builtin_bpf_passthrough builtins. Target independent IR
//     optimizations are done and those builtins can be removed.
//   - remove llvm.bpf.getelementptr.and.load builtins.
//   - remove llvm.bpf.getelementptr.and.store builtins.
//   - for loads and stores with base addresses from non-zero address space
//     cast base address to zero address space (support for BPF address spaces).
//
//===----------------------------------------------------------------------===//

#include "BPF.h"
#include "BPFCORE.h"
#include "BPFTargetMachine.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicsBPF.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"

#define DEBUG_TYPE …

usingnamespacellvm;

namespace {

class BPFCheckAndAdjustIR final : public ModulePass { … };
} // End anonymous namespace

char BPFCheckAndAdjustIR::ID = …;
INITIALIZE_PASS(…)

ModulePass *llvm::createBPFCheckAndAdjustIR() { … }

void BPFCheckAndAdjustIR::checkIR(Module &M) { … }

bool BPFCheckAndAdjustIR::removePassThroughBuiltin(Module &M) { … }

bool BPFCheckAndAdjustIR::removeCompareBuiltin(Module &M) { … }

struct MinMaxSinkInfo { … };

static bool sinkMinMaxInBB(BasicBlock &BB,
                           const std::function<bool(Instruction *)> &Filter) { … }

// Do the following transformation:
//
//   x < min(a, b) -> x < a && x < b
//   x > min(a, b) -> x > a || x > b
//   x < max(a, b) -> x < a || x < b
//   x > max(a, b) -> x > a && x > b
//
// Such patterns are introduced by LICM.cpp:hoistMinMax()
// transformation and might lead to BPF verification failures for
// older kernels.
//
// To minimize "collateral" changes only do it for icmp + min/max
// calls when icmp is inside a loop and min/max is outside of that
// loop.
//
// Verification failure happens when:
// - RHS operand of some `icmp LHS, RHS` is replaced by some RHS1;
// - verifier can recognize RHS as a constant scalar in some context;
// - verifier can't recognize RHS1 as a constant scalar in the same
//   context;
//
// The "constant scalar" is not a compile time constant, but a register
// that holds a scalar value known to verifier at some point in time
// during abstract interpretation.
//
// See also:
//   https://lore.kernel.org/bpf/[email protected]/
bool BPFCheckAndAdjustIR::sinkMinMax(Module &M) { … }

void BPFCheckAndAdjustIR::getAnalysisUsage(AnalysisUsage &AU) const { … }

static void unrollGEPLoad(CallInst *Call) { … }

static void unrollGEPStore(CallInst *Call) { … }

static bool removeGEPBuiltinsInFunc(Function &F) { … }

// Rewrites the following builtins:
// - llvm.bpf.getelementptr.and.load
// - llvm.bpf.getelementptr.and.store
// As (load (getelementptr ...)) or (store (getelementptr ...)).
bool BPFCheckAndAdjustIR::removeGEPBuiltins(Module &M) { … }

// Wrap ToWrap with cast to address space zero:
// - if ToWrap is a getelementptr,
//   wrap it's base pointer instead and return a copy;
// - if ToWrap is Instruction, insert address space cast
//   immediately after ToWrap;
// - if ToWrap is not an Instruction (function parameter
//   or a global value), insert address space cast at the
//   beginning of the Function F;
// - use Cache to avoid inserting too many casts;
static Value *aspaceWrapValue(DenseMap<Value *, Value *> &Cache, Function *F,
                              Value *ToWrap) { … }

// Wrap a pointer operand OpNum of instruction I
// with cast to address space zero
static void aspaceWrapOperand(DenseMap<Value *, Value *> &Cache, Instruction *I,
                              unsigned OpNum) { … }

// Support for BPF address spaces:
// - for each function in the module M, update pointer operand of
//   each memory access instruction (load/store/cmpxchg/atomicrmw)
//   by casting it from non-zero address space to zero address space, e.g:
//
//   (load (ptr addrspace (N) %p) ...)
//     -> (load (addrspacecast ptr addrspace (N) %p to ptr))
//
// - assign section with name .addr_space.N for globals defined in
//   non-zero address space N
bool BPFCheckAndAdjustIR::insertASpaceCasts(Module &M) { … }

bool BPFCheckAndAdjustIR::adjustIR(Module &M) { … }

bool BPFCheckAndAdjustIR::runOnModule(Module &M) { … }