blob: 47e420498036295d9c49d36ad1025bb55daae2ae [file] [log] [blame]
//=== unittests/CodeGen/IRMatchers.h - Match on the LLVM IR -----*- 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
//
//===----------------------------------------------------------------------===//
/// \file
/// This file provides a simple mechanism for performing search operations over
/// IR including metadata and types. It allows writing complex search patterns
/// using understandable syntax. For instance, the code:
///
/// \code
/// const BasicBlock *BB = ...
/// const Instruction *I = match(BB,
/// MInstruction(Instruction::Store,
/// MConstInt(4, 8),
/// MMTuple(
/// MMTuple(
/// MMString("omnipotent char"),
/// MMTuple(
/// MMString("Simple C/C++ TBAA")),
/// MConstInt(0, 64)),
/// MSameAs(0),
/// MConstInt(0))));
/// \endcode
///
/// searches the basic block BB for the 'store' instruction, first argument of
/// which is 'i8 4', and the attached metadata has an item described by the
/// given tree.
//===----------------------------------------------------------------------===//
#ifndef CLANG_UNITTESTS_CODEGEN_IRMATCHERS_H
#define CLANG_UNITTESTS_CODEGEN_IRMATCHERS_H
#include "llvm/ADT/PointerUnion.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Value.h"
namespace llvm {
/// Keeps information about pending match queries.
///
/// This class stores state of all unfinished match actions. It allows to
/// use queries like "this operand is the same as n-th operand", which are
/// hard to implement otherwise.
///
class MatcherContext {
public:
/// Describes pending match query.
///
/// The query is represented by the current entity being investigated (type,
/// value or metadata). If the entity is a member of a list (like arguments),
/// the query also keeps the entity number in that list.
///
class Query {
PointerUnion<const Value *, const Metadata *, const Type *> Entity;
unsigned OperandNo;
public:
Query(const Value *V, unsigned N) : Entity(V), OperandNo(N) {}
Query(const Metadata *M, unsigned N) : Entity(M), OperandNo(N) {}
Query(const Type *T, unsigned N) : Entity(T), OperandNo(N) {}
template<typename T>
const T *get() const {
return Entity.dyn_cast<const T *>();
}
unsigned getOperandNo() const { return OperandNo; }
};
template<typename T>
void push(const T *V, unsigned N = ~0) {
MatchStack.push_back(Query(V, N));
}
void pop() { MatchStack.pop_back(); }
template<typename T>
const T *top() const { return MatchStack.back().get<T>(); }
size_t size() const { return MatchStack.size(); }
unsigned getOperandNo() const { return MatchStack.back().getOperandNo(); }
/// Returns match query at the given offset from the top of queries.
///
/// Offset 0 corresponds to the topmost query.
///
const Query &getQuery(unsigned Offset) const {
assert(MatchStack.size() > Offset);
return MatchStack[MatchStack.size() - 1 - Offset];
}
private:
SmallVector<Query, 8> MatchStack;
};
/// Base of all matcher classes.
///
class Matcher {
public:
virtual ~Matcher() {}
/// Returns true if the entity on the top of the specified context satisfies
/// the matcher condition.
///
virtual bool match(MatcherContext &MC) = 0;
};
/// Base class of matchers that test particular entity.
///
template<typename T>
class EntityMatcher : public Matcher {
public:
bool match(MatcherContext &MC) override {
if (auto V = MC.top<T>())
return matchEntity(*V, MC);
return false;
}
virtual bool matchEntity(const T &M, MatcherContext &C) = 0;
};
/// Matcher that matches any entity of the specified kind.
///
template<typename T>
class AnyMatcher : public EntityMatcher<T> {
public:
bool matchEntity(const T &M, MatcherContext &C) override { return true; }
};
/// Matcher that tests if the current entity satisfies the specified
/// condition.
///
template<typename T>
class CondMatcher : public EntityMatcher<T> {
std::function<bool(const T &)> Condition;
public:
CondMatcher(std::function<bool(const T &)> C) : Condition(C) {}
bool matchEntity(const T &V, MatcherContext &C) override {
return Condition(V);
}
};
/// Matcher that save pointer to the entity that satisfies condition of the
// specified matcher.
///
template<typename T>
class SavingMatcher : public EntityMatcher<T> {
const T *&Var;
std::shared_ptr<Matcher> Next;
public:
SavingMatcher(const T *&V, std::shared_ptr<Matcher> N) : Var(V), Next(N) {}
bool matchEntity(const T &V, MatcherContext &C) override {
bool Result = Next->match(C);
if (Result)
Var = &V;
return Result;
}
};
/// Matcher that checks that the entity is identical to another entity in the
/// same container.
///
class SameAsMatcher : public Matcher {
unsigned OpNo;
public:
SameAsMatcher(unsigned N) : OpNo(N) {}
bool match(MatcherContext &C) override {
if (C.getOperandNo() != ~0U) {
// Handle all known containers here.
const MatcherContext::Query &StackRec = C.getQuery(1);
if (const Metadata *MR = StackRec.get<Metadata>()) {
if (const auto *MT = dyn_cast<MDTuple>(MR)) {
if (OpNo < MT->getNumOperands())
return C.top<Metadata>() == MT->getOperand(OpNo).get();
return false;
}
llvm_unreachable("Unknown metadata container");
}
if (const Value *VR = StackRec.get<Value>()) {
if (const auto *Insn = dyn_cast<Instruction>(VR)) {
if (OpNo < Insn->getNumOperands())
return C.top<Value>() == Insn->getOperand(OpNo);
return false;
}
llvm_unreachable("Unknown value container");
}
llvm_unreachable("Unknown type container");
}
return false;
}
};
/// Matcher that tests if the entity is a constant integer.
///
class ConstantIntMatcher : public Matcher {
uint64_t IntValue;
unsigned Width;
public:
ConstantIntMatcher(uint64_t V, unsigned W = 0) : IntValue(V), Width(W) {}
bool match(MatcherContext &Ctx) override {
if (const Value *V = Ctx.top<Value>()) {
if (const auto *CI = dyn_cast<ConstantInt>(V))
return (Width == 0 || CI->getBitWidth() == Width) &&
CI->getLimitedValue() == IntValue;
}
if (const Metadata *M = Ctx.top<Metadata>()) {
if (const auto *MT = dyn_cast<ValueAsMetadata>(M))
if (const auto *C = dyn_cast<ConstantInt>(MT->getValue()))
return (Width == 0 || C->getBitWidth() == Width) &&
C->getLimitedValue() == IntValue;
}
return false;
}
};
/// Value matcher tuned to test instructions.
///
class InstructionMatcher : public EntityMatcher<Value> {
SmallVector<std::shared_ptr<Matcher>, 8> OperandMatchers;
std::shared_ptr<EntityMatcher<Metadata>> MetaMatcher = nullptr;
unsigned Code;
public:
InstructionMatcher(unsigned C) : Code(C) {}
void push(std::shared_ptr<EntityMatcher<Metadata>> M) {
assert(!MetaMatcher && "Only one metadata matcher may be specified");
MetaMatcher = M;
}
void push(std::shared_ptr<Matcher> V) { OperandMatchers.push_back(V); }
template<typename... Args>
void push(std::shared_ptr<Matcher> V, Args... A) {
push(V);
push(A...);
}
virtual bool matchInstruction(const Instruction &I) {
return I.getOpcode() == Code;
}
bool matchEntity(const Value &V, MatcherContext &C) override {
if (const auto *I = dyn_cast<Instruction>(&V)) {
if (!matchInstruction(*I))
return false;
if (OperandMatchers.size() > I->getNumOperands())
return false;
for (unsigned N = 0, E = OperandMatchers.size(); N != E; ++N) {
C.push(I->getOperand(N), N);
if (!OperandMatchers[N]->match(C)) {
C.pop();
return false;
}
C.pop();
}
if (MetaMatcher) {
SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
I->getAllMetadata(MDs);
bool Found = false;
for (auto Item : MDs) {
C.push(Item.second);
if (MetaMatcher->match(C)) {
Found = true;
C.pop();
break;
}
C.pop();
}
return Found;
}
return true;
}
return false;
}
};
/// Matcher that tests type of the current value using the specified
/// type matcher.
///
class ValueTypeMatcher : public EntityMatcher<Value> {
std::shared_ptr<EntityMatcher<Type>> TyM;
public:
ValueTypeMatcher(std::shared_ptr<EntityMatcher<Type>> T) : TyM(T) {}
ValueTypeMatcher(const Type *T)
: TyM(new CondMatcher<Type>([T](const Type &Ty) -> bool {
return &Ty == T;
})) {}
bool matchEntity(const Value &V, MatcherContext &Ctx) override {
Type *Ty = V.getType();
Ctx.push(Ty);
bool Res = TyM->match(Ctx);
Ctx.pop();
return Res;
}
};
/// Matcher that matches string metadata.
///
class NameMetaMatcher : public EntityMatcher<Metadata> {
StringRef Name;
public:
NameMetaMatcher(StringRef N) : Name(N) {}
bool matchEntity(const Metadata &M, MatcherContext &C) override {
if (auto *MDS = dyn_cast<MDString>(&M))
return MDS->getString().equals(Name);
return false;
}
};
/// Matcher that matches metadata tuples.
///
class MTupleMatcher : public EntityMatcher<Metadata> {
SmallVector<std::shared_ptr<Matcher>, 4> Operands;
public:
void push(std::shared_ptr<Matcher> M) { Operands.push_back(M); }
template<typename... Args>
void push(std::shared_ptr<Matcher> M, Args... A) {
push(M);
push(A...);
}
bool matchEntity(const Metadata &M, MatcherContext &C) override {
if (const auto *MT = dyn_cast<MDTuple>(&M)) {
if (MT->getNumOperands() != Operands.size())
return false;
for (unsigned I = 0, E = MT->getNumOperands(); I != E; ++I) {
const MDOperand &Op = MT->getOperand(I);
C.push(Op.get(), I);
if (!Operands[I]->match(C)) {
C.pop();
return false;
}
C.pop();
}
return true;
}
return false;
}
};
// Helper function used to construct matchers.
inline std::shared_ptr<Matcher> MSameAs(unsigned N) {
return std::shared_ptr<Matcher>(new SameAsMatcher(N));
}
template<typename... T>
std::shared_ptr<InstructionMatcher> MInstruction(unsigned C, T... Args) {
auto Result = new InstructionMatcher(C);
Result->push(Args...);
return std::shared_ptr<InstructionMatcher>(Result);
}
inline std::shared_ptr<Matcher> MConstInt(uint64_t V, unsigned W = 0) {
return std::shared_ptr<Matcher>(new ConstantIntMatcher(V, W));
}
inline std::shared_ptr<EntityMatcher<Value>>
MValType(std::shared_ptr<EntityMatcher<Type>> T) {
return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
}
inline std::shared_ptr<EntityMatcher<Value>> MValType(const Type *T) {
return std::shared_ptr<EntityMatcher<Value>>(new ValueTypeMatcher(T));
}
inline std::shared_ptr<EntityMatcher<Type>>
MType(std::function<bool(const Type &)> C) {
return std::shared_ptr<EntityMatcher<Type>>(new CondMatcher<Type>(C));
}
inline std::shared_ptr<EntityMatcher<Metadata>> MMAny() {
return std::shared_ptr<EntityMatcher<Metadata>>(new AnyMatcher<Metadata>);
}
inline std::shared_ptr<EntityMatcher<Metadata>>
MMSave(const Metadata *&V, std::shared_ptr<EntityMatcher<Metadata>> M) {
return std::shared_ptr<EntityMatcher<Metadata>>(
new SavingMatcher<Metadata>(V, M));
}
inline std::shared_ptr<EntityMatcher<Metadata>> MMString(const char *Name) {
return std::shared_ptr<EntityMatcher<Metadata>>(new NameMetaMatcher(Name));
}
template<typename... T>
std::shared_ptr<EntityMatcher<Metadata>> MMTuple(T... Args) {
auto Res = new MTupleMatcher();
Res->push(Args...);
return std::shared_ptr<EntityMatcher<Metadata>>(Res);
}
/// Looks for the instruction that satisfies condition of the specified
/// matcher inside the given basic block.
/// \returns Pointer to the found instruction or nullptr if such instruction
/// was not found.
///
inline const Instruction *match(const BasicBlock *BB,
std::shared_ptr<Matcher> M) {
MatcherContext MC;
for (const auto &I : *BB) {
MC.push(&I);
if (M->match(MC))
return &I;
MC.pop();
}
assert(MC.size() == 0);
return nullptr;
}
/// Looks for the instruction that satisfies condition of the specified
/// matcher starting from the specified instruction inside the same basic block.
///
/// The given instruction is not checked.
///
inline const Instruction *matchNext(const Instruction *I, std::shared_ptr<Matcher> M) {
if (!I)
return nullptr;
MatcherContext MC;
const BasicBlock *BB = I->getParent();
if (!BB)
return nullptr;
for (auto P = ++BasicBlock::const_iterator(I), E = BB->end(); P != E; ++P) {
MC.push(&*P);
if (M->match(MC))
return &*P;
MC.pop();
}
assert(MC.size() == 0);
return nullptr;
}
}
#endif