diff --git a/libc/benchmarks/automemcpy/RandomFunctionGenerator.h b/libc/benchmarks/automemcpy/RandomFunctionGenerator.h new file mode 100644 --- /dev/null +++ b/libc/benchmarks/automemcpy/RandomFunctionGenerator.h @@ -0,0 +1,55 @@ +//===-- Generate random but valid function descriptors ---------*- 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 LLVM_LIBC_BENCHMARKS_AUTOMEMCPY_RANDOM_FUNCTION_GENERATOR_H +#define LLVM_LIBC_BENCHMARKS_AUTOMEMCPY_RANDOM_FUNCTION_GENERATOR_H + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace llvm { +namespace automemcpy { + +// Holds the state for the constraint solver. +// It implements a single method that returns the next valid description. +struct RandomFunctionGenerator { + RandomFunctionGenerator(); + + // Get the next valid FunctionDescriptor or llvm::None. + Optional next(); + +private: + // Returns an expression where `Variable` is forced to be one of the `Values`. + z3::expr disjunction(z3::expr &Variable, ArrayRef Values) const; + void addBoundsAndAnchors(z3::expr &Begin, z3::expr &End); + void addLoopConstraints(const z3::expr &LoopBegin, const z3::expr &LoopEnd, + z3::expr &LoopBlockSize, int LoopMinIter); + + z3::context Context; + z3::solver Solver; + + z3::expr Type; + z3::expr ContiguousBegin, ContiguousEnd; + z3::expr OverlapBegin, OverlapEnd; + z3::expr LoopBegin, LoopEnd, LoopBlockSize; + z3::expr AlignedLoopBegin, AlignedLoopEnd, AlignedLoopBlockSize, + AlignedAlignment, AlignedArg; + z3::expr AcceleratorBegin, AcceleratorEnd; + z3::expr ElementClass; +}; + +} // namespace automemcpy +} // namespace llvm + +#endif /* LLVM_LIBC_BENCHMARKS_AUTOMEMCPY_RANDOM_FUNCTION_GENERATOR_H */ diff --git a/libc/benchmarks/automemcpy/RandomFunctionGenerator.cpp b/libc/benchmarks/automemcpy/RandomFunctionGenerator.cpp new file mode 100644 --- /dev/null +++ b/libc/benchmarks/automemcpy/RandomFunctionGenerator.cpp @@ -0,0 +1,231 @@ +//===-- Generate random but valid function descriptors ---------*- 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 +// +//===----------------------------------------------------------------------===// + +#include + +#include +#include +#include + +#include + +namespace llvm { +namespace automemcpy { + +// Exploration parameters +static constexpr int kLoopMinIter = 3; +static constexpr int kAlignedLoopMinIter = 2; +static constexpr int kAnchors[] = {0, 1, 2, 4, 8, 16, 32, 48, + 64, 96, 128, 256, 512, 1024, kMaxSize}; +static constexpr bool kDisableLoop = false; +static constexpr bool kDisableAlignedLoop = false; +static constexpr bool kDisableAccelerator = false; +static constexpr bool kExploreAlignmentArg = true; + +RandomFunctionGenerator::RandomFunctionGenerator() + : Solver(Context), Type(Context.int_const("Type")), + ContiguousBegin(Context.int_const("ContiguousBegin")), + ContiguousEnd(Context.int_const("ContiguousEnd")), + OverlapBegin(Context.int_const("OverlapBegin")), + OverlapEnd(Context.int_const("OverlapEnd")), + LoopBegin(Context.int_const("LoopBegin")), + LoopEnd(Context.int_const("LoopEnd")), + LoopBlockSize(Context.int_const("LoopBlockSize")), + AlignedLoopBegin(Context.int_const("AlignedLoopBegin")), + AlignedLoopEnd(Context.int_const("AlignedLoopEnd")), + AlignedLoopBlockSize(Context.int_const("AlignedLoopBlockSize")), + AlignedAlignment(Context.int_const("AlignedAlignment")), + AlignedArg(Context.int_const("AlignedArg")), + AcceleratorBegin(Context.int_const("AcceleratorBegin")), + AcceleratorEnd(Context.int_const("AcceleratorEnd")), + ElementClass(Context.int_const("ElementClass")) { + // All possible functions. + Solver.add(disjunction(Type, { + (int)FunctionType::MEMCPY, + (int)FunctionType::MEMCMP, + (int)FunctionType::BCMP, + (int)FunctionType::MEMSET, + (int)FunctionType::BZERO, + })); + // But disallow Bcmp for now. + Solver.add(Type != (int)FunctionType::BCMP); + + // Span bounds are bounded. + addBoundsAndAnchors(ContiguousBegin, ContiguousEnd); + addBoundsAndAnchors(OverlapBegin, OverlapEnd); + addBoundsAndAnchors(LoopBegin, LoopEnd); + addBoundsAndAnchors(AlignedLoopBegin, AlignedLoopEnd); + addBoundsAndAnchors(AcceleratorBegin, AcceleratorEnd); + // Fix endpoints. + Solver.add(ContiguousBegin == 0); + Solver.add(AcceleratorEnd == kMaxSize); + // Spans are ordered relative to each others. + Solver.add(ContiguousEnd == OverlapBegin); + Solver.add(OverlapEnd == LoopBegin); + Solver.add(LoopEnd == AlignedLoopBegin); + Solver.add(AlignedLoopEnd == AcceleratorBegin); + // Contiguous + Solver.add(ContiguousEnd <= 5); // up to Size == 4 + // Overlap + Solver.add(OverlapEnd <= 257); // up to Size == 256 + Solver.add(OverlapBegin == OverlapEnd || OverlapBegin >= 2); + // Loop + addLoopConstraints(LoopBegin, LoopEnd, LoopBlockSize, kLoopMinIter); + // Aligned Loop + addLoopConstraints(AlignedLoopBegin, AlignedLoopEnd, AlignedLoopBlockSize, + kAlignedLoopMinIter); + Solver.add(disjunction(AlignedAlignment, {16, 32, 64})); + Solver.add(AlignedLoopBegin == AlignedLoopEnd || AlignedLoopBegin >= 64); + Solver.add(AlignedLoopBlockSize >= AlignedAlignment); + Solver.add(AlignedLoopBlockSize >= LoopBlockSize); + z3::expr IsMemcpy = Type == (int)FunctionType::MEMCPY; + z3::expr ExploreAlignment = IsMemcpy && kExploreAlignmentArg; + Solver.add( + (ExploreAlignment && + disjunction(AlignedArg, {(int)AlignArg::_1, (int)AlignArg::_2})) || + (!ExploreAlignment && AlignedArg == (int)AlignArg::_1)); + // Accelerator + Solver.add(IsMemcpy || + (AcceleratorBegin == + AcceleratorEnd)); // Only Memcpy has accelerator for now. + Solver.add(disjunction(ElementClass, {(int)ElementTypeClass::SCALAR, + (int)ElementTypeClass::NATIVE, + (int)ElementTypeClass::BUILTIN})); + // But we only keep native for now. + Solver.add(ElementClass == (int)ElementTypeClass::NATIVE); + + if (kDisableLoop) + Solver.add(LoopBegin == LoopEnd); + if (kDisableAlignedLoop) + Solver.add(AlignedLoopBegin == AlignedLoopEnd); + if (kDisableAccelerator) + Solver.add(AcceleratorBegin == AcceleratorEnd); +} + +// Creates SizeSpan from Begin/End values. +// Returns llvm::None if Begin==End. +static Optional AsSizeSpan(size_t Begin, size_t End) { + if (Begin == End) + return None; + SizeSpan SS; + SS.Begin = Begin; + SS.End = End; + return SS; +} + +// Generic method to create a `Region` struct with a Span or None if span is +// empty. +template +static Optional As(size_t Begin, size_t End) { + if (auto Span = AsSizeSpan(Begin, End)) { + Region Output; + Output.Span = *Span; + return Output; + } + return None; +} + +// Returns a Loop struct or None if span is empty. +static Optional AsLoop(size_t Begin, size_t End, size_t BlockSize) { + if (auto Span = AsSizeSpan(Begin, End)) { + Loop Output; + Output.Span = *Span; + Output.BlockSize = BlockSize; + return Output; + } + return None; +} + +// Returns an AlignedLoop struct or None if span is empty. +static Optional AsAlignedLoop(size_t Begin, size_t End, + size_t BlockSize, size_t Alignment, + AlignArg AlignTo) { + if (auto Loop = AsLoop(Begin, End, BlockSize)) { + AlignedLoop Output; + Output.Loop = *Loop; + Output.Alignment = Alignment; + Output.AlignTo = AlignTo; + return Output; + } + return None; +} + +Optional RandomFunctionGenerator::next() { + if (Solver.check() != z3::sat) + return {}; + + z3::model m = Solver.get_model(); + + // Helper method to get the current numerical value of a z3::expr. + const auto E = [&m](z3::expr &V) -> int { + return m.eval(V).get_numeral_int(); + }; + + // Fill is the function descriptor to return. + FunctionDescriptor R; + R.Type = FunctionType(E(Type)); + R.Contiguous = As(E(ContiguousBegin), E(ContiguousEnd)); + R.Overlap = As(E(OverlapBegin), E(OverlapEnd)); + R.Loop = AsLoop(E(LoopBegin), E(LoopEnd), E(LoopBlockSize)); + R.AlignedLoop = AsAlignedLoop(E(AlignedLoopBegin), E(AlignedLoopEnd), + E(AlignedLoopBlockSize), E(AlignedAlignment), + AlignArg(E(AlignedArg))); + R.Accelerator = As(E(AcceleratorBegin), E(AcceleratorEnd)); + R.ElementClass = ElementTypeClass(E(ElementClass)); + + // Express current state as a set of constraints. + z3::expr CurrentLayout = + (Type == E(Type)) && (ContiguousBegin == E(ContiguousBegin)) && + (ContiguousEnd == E(ContiguousEnd)) && + (OverlapBegin == E(OverlapBegin)) && (OverlapEnd == E(OverlapEnd)) && + (LoopBegin == E(LoopBegin)) && (LoopEnd == E(LoopEnd)) && + (LoopBlockSize == E(LoopBlockSize)) && + (AlignedLoopBegin == E(AlignedLoopBegin)) && + (AlignedLoopEnd == E(AlignedLoopEnd)) && + (AlignedLoopBlockSize == E(AlignedLoopBlockSize)) && + (AlignedAlignment == E(AlignedAlignment)) && + (AlignedArg == E(AlignedArg)) && + (AcceleratorBegin == E(AcceleratorBegin)) && + (AcceleratorEnd == E(AcceleratorEnd)) && + (ElementClass == E(ElementClass)); + + // Ask solver to never show this configuration ever again. + Solver.add(!CurrentLayout); + return R; +} + +// Make sure `Variable` is one of the provided values. +z3::expr RandomFunctionGenerator::disjunction(z3::expr &Variable, + ArrayRef Values) const { + z3::expr_vector Args(Variable.ctx()); + for (int Value : Values) + Args.push_back(Variable == Value); + return z3::mk_or(Args); +} + +void RandomFunctionGenerator::addBoundsAndAnchors(z3::expr &Begin, + z3::expr &End) { + // Begin and End are picked amongst a set of predefined values. + Solver.add(disjunction(Begin, kAnchors)); + Solver.add(disjunction(End, kAnchors)); + Solver.add(Begin >= 0); + Solver.add(Begin <= End); + Solver.add(End <= kMaxSize); +} + +void RandomFunctionGenerator::addLoopConstraints(const z3::expr &LoopBegin, + const z3::expr &LoopEnd, + z3::expr &LoopBlockSize, + int LoopMinIter) { + Solver.add(disjunction(LoopBlockSize, {16, 32, 64})); + Solver.add(LoopBegin == LoopEnd || + (LoopBegin > (LoopMinIter * LoopBlockSize))); +} + +} // namespace automemcpy +} // namespace llvm \ No newline at end of file