diff options
author | Chunseok Lee <chunseok.lee@samsung.com> | 2020-04-23 14:45:49 +0900 |
---|---|---|
committer | Chunseok Lee <chunseok.lee@samsung.com> | 2020-04-23 14:45:49 +0900 |
commit | e2ef8438a24f7c56a0744eb579a6e293ee2fbf8e (patch) | |
tree | 44a1a7951d168dd4370e13593ed03f4bc6d920c5 /compiler/enco/core/src/Transforms | |
parent | 302e6564a7a76109e1178207e44e45a58631c477 (diff) | |
download | nnfw-e2ef8438a24f7c56a0744eb579a6e293ee2fbf8e.tar.gz nnfw-e2ef8438a24f7c56a0744eb579a6e293ee2fbf8e.tar.bz2 nnfw-e2ef8438a24f7c56a0744eb579a6e293ee2fbf8e.zip |
Imported Upstream version 1.4.0upstream/1.4.0submit/tizen/20200423.054851
Diffstat (limited to 'compiler/enco/core/src/Transforms')
41 files changed, 5555 insertions, 0 deletions
diff --git a/compiler/enco/core/src/Transforms/AvgPoolLowering.cpp b/compiler/enco/core/src/Transforms/AvgPoolLowering.cpp new file mode 100644 index 000000000..17502fb1f --- /dev/null +++ b/compiler/enco/core/src/Transforms/AvgPoolLowering.cpp @@ -0,0 +1,229 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "AvgPoolLowering.h" +#include "IRUtils.h" + +#include <coco/IR/FeatureLayouts.h> + +#include <nncc/core/ADT/feature/Shape.h> +#include <nncc/core/ADT/feature/HWCLayout.h> + +#include <set> +#include <cassert> + +using namespace nncc::core::ADT; +using nncc::core::ADT::feature::num_elements; + +namespace +{ + +bool empty(coco::Padding2D *pad) +{ + return (pad->top() == 0) && (pad->bottom() == 0) && (pad->left() == 0) && (pad->right() == 0); +} + +/** + * @brief Return a set of AvgPool2D operations (in Eval instruction) that SHOULD be lowered + */ +std::set<coco::AvgPool2D *> candidates(coco::Module *m) +{ + std::set<coco::AvgPool2D *> res; + + for (auto I : enco::instr_sequence(m)) + { + if (auto eval = I->asEval()) + { + if (auto avgpool = eval->op()->asAvgPool2D()) + { + /* Originally it was preferred to use `auto load = avgpool->arg()->asLoad()' for + * consitent style with other if statements. + * Someone may think compiler will be happy because `load` in `if` statement can + * be considered as a use, however, it turend out that it is not the case. + */ + if (avgpool->arg()->asLoad()) + { + if (avgpool->divisor() == coco::AvgPool2D::Divisor::Static) + { + res.insert(avgpool); + } + } + } + } + } + + return res; +} + +} // namespace + +namespace +{ +namespace ShapeTransform +{ + +class Pad +{ +public: + Pad(const coco::Padding2D *pad) : _pad{pad} + { + // DO NOTHING + } + +public: + /// @brief Return the expected OFM shape for a given IFM shape + feature::Shape forward(const feature::Shape &ifm_shape) const + { + const uint32_t OFM_C = ifm_shape.depth(); + const uint32_t OFM_H = ifm_shape.height() + _pad->top() + _pad->bottom(); + const uint32_t OFM_W = ifm_shape.width() + _pad->left() + _pad->right(); + + return feature::Shape{OFM_C, OFM_H, OFM_W}; + } + +private: + const coco::Padding2D *_pad; +}; + +} // namespace ShapeTransform + +ShapeTransform::Pad shape_xform(const coco::Padding2D *pad) { return ShapeTransform::Pad{pad}; } + +} // namespace + +namespace +{ + +class PadInstrBuilder final +{ +public: + PadInstrBuilder(const coco::Padding2D *pad) : _pad{pad} + { + // DO NOTHING + } + +public: + coco::Instr *build(coco::FeatureObject *ifm_obj, coco::FeatureObject *ofm_obj) const + { + assert(ifm_obj->module() == ofm_obj->module()); + auto m = ifm_obj->module(); + assert(m != nullptr); + + auto load_op = m->entity()->op()->create<coco::Load>(); + + load_op->object(ifm_obj); + + auto pad_op = m->entity()->op()->create<coco::PadF>(); + + pad_op->arg(load_op); + + pad_op->pad()->top(_pad->top()); + pad_op->pad()->bottom(_pad->bottom()); + pad_op->pad()->left(_pad->left()); + pad_op->pad()->right(_pad->right()); + + auto pad_instr = m->entity()->instr()->create<coco::Eval>(); + + pad_instr->out(ofm_obj); + pad_instr->op(pad_op); + + return pad_instr; + } + +private: + const coco::Padding2D *_pad; +}; + +PadInstrBuilder pad_instr_builder(const coco::Padding2D *pad) { return PadInstrBuilder{pad}; } + +} // namespace + +namespace +{ + +class AvgPoolRewritePass +{ +private: + void runOnModule(coco::Module *m) const; + +public: + void runOnCode(enco::Code *) const; +}; + +void AvgPoolRewritePass::runOnModule(coco::Module *m) const +{ + // Lower AvgPool2D op that resides in Eval instruction + for (auto avgpool : candidates(m)) + { + auto ins = avgpool->parent(); + auto load = avgpool->arg()->asLoad(); + + assert(ins != nullptr); + assert(load != nullptr); + assert(avgpool->divisor() == coco::AvgPool2D::Divisor::Static); + + if (empty(avgpool->pad())) + { + // NOTE If there is no padding, Static and PaddingExcluded schemes are equivalent + avgpool->divisor(coco::AvgPool2D::Divisor::PaddingExcluded); + } + else + { + // Before: Static AvgPool2D with Padding + // After: PadF; PaddingExcluded AvgPool2D without Padding + + // Create PadF + auto ifm_obj = load->object()->asFeature(); + assert(ifm_obj != nullptr); + + auto pad_shape = shape_xform(avgpool->pad()).forward(ifm_obj->shape()); + auto pad_bag = m->entity()->bag()->create(num_elements(pad_shape)); + auto pad_obj = m->entity()->object()->create<coco::FeatureObject>(); + + pad_obj->bag(pad_bag); + pad_obj->layout(coco::FeatureLayouts::BHWC::create(pad_shape)); + + auto pad_instr = pad_instr_builder(avgpool->pad()).build(ifm_obj, pad_obj); + + // Insert PadF before AvgPool2D + pad_instr->insertBefore(ins); + + // Rewrite AvgPool2D as PaddingExcluded AvgPool2D without Padding + load->object(pad_obj); + + avgpool->divisor(coco::AvgPool2D::Divisor::PaddingExcluded); + avgpool->pad()->top(0); + avgpool->pad()->bottom(0); + avgpool->pad()->left(0); + avgpool->pad()->right(0); + } + } +} + +void AvgPoolRewritePass::runOnCode(enco::Code *code) const { runOnModule(code->module()); } + +} // namespace + +namespace enco +{ + +void lower_avgpool(enco::Code *code) +{ + AvgPoolRewritePass pass; + pass.runOnCode(code); +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/AvgPoolLowering.h b/compiler/enco/core/src/Transforms/AvgPoolLowering.h new file mode 100644 index 000000000..71a5253df --- /dev/null +++ b/compiler/enco/core/src/Transforms/AvgPoolLowering.h @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __REWRITE_H__ +#define __REWRITE_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Rewrite NN API-incompatible average pooling + */ +void lower_avgpool(enco::Code *); + +struct AvgPoolLoweringPass final : public Pass +{ + PASS_CTOR(AvgPoolLoweringPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { lower_avgpool(code(sess)); } +}; + +} // namespace enco + +#endif // __REWRITE_H__ diff --git a/compiler/enco/core/src/Transforms/ConcatLowering.cpp b/compiler/enco/core/src/Transforms/ConcatLowering.cpp new file mode 100644 index 000000000..bf613c983 --- /dev/null +++ b/compiler/enco/core/src/Transforms/ConcatLowering.cpp @@ -0,0 +1,196 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "CopyLowering.h" +#include "IRUtils.h" + +#include <nncc/core/ADT/tensor/IndexEnumerator.h> + +#include <set> +#include <cassert> + +using namespace nncc::core::ADT; + +namespace +{ + +inline uint32_t as_tensor_axis(const coco::ConcatF::Axis &axis) +{ + switch (axis) + { + case coco::ConcatF::Axis::Batch: + return 0; + case coco::ConcatF::Axis::Depth: + return 1; + case coco::ConcatF::Axis::Height: + return 2; + case coco::ConcatF::Axis::Width: + return 3; + default: + break; + }; + + throw std::invalid_argument{"axis is unknown value"}; +} + +tensor::Shape as_tensor_shape(const coco::FeatureLayout *l) +{ + assert(l != nullptr); + + tensor::Shape res; + + res.resize(4); + + res.dim(as_tensor_axis(coco::ConcatF::Axis::Batch)) = l->batch(); + res.dim(as_tensor_axis(coco::ConcatF::Axis::Depth)) = l->depth(); + res.dim(as_tensor_axis(coco::ConcatF::Axis::Height)) = l->height(); + res.dim(as_tensor_axis(coco::ConcatF::Axis::Width)) = l->width(); + + return res; +} + +coco::ElemID as_element_index(const coco::FeatureLayout *l, const tensor::Index &idx) +{ + assert(l != nullptr); + assert(idx.rank() == 4); + + const auto b = idx.at(as_tensor_axis(coco::ConcatF::Axis::Batch)); + const auto ch = idx.at(as_tensor_axis(coco::ConcatF::Axis::Depth)); + const auto row = idx.at(as_tensor_axis(coco::ConcatF::Axis::Height)); + const auto col = idx.at(as_tensor_axis(coco::ConcatF::Axis::Width)); + + return l->at(b, ch, row, col); +} + +std::set<coco::Eval *> candidates(coco::Module *m) +{ + std::set<coco::Eval *> res; + + for (auto ins : enco::instr_sequence(m)) + { + if (auto eval = ins->asEval()) + { + if (eval->op()->asConcatF()) + { + res.insert(eval); + } + } + } + + return res; +} + +} // namespace + +namespace enco +{ + +void lower_concat(enco::Code *code) +{ + auto m = code->module(); + + for (auto eval : candidates(m)) + { + auto concat_f = eval->op()->asConcatF(); + assert(concat_f != nullptr); + + auto left_feature = concat_f->left()->asLoad()->object()->asFeature(); + assert(left_feature != nullptr); + auto left_shape = as_tensor_shape(left_feature->layout()); + + auto right_feature = concat_f->right()->asLoad()->object()->asFeature(); + assert(right_feature != nullptr); + auto right_shape = as_tensor_shape(right_feature->layout()); + + auto out_feature = eval->out()->asFeature(); + assert(out_feature != nullptr); + auto out_shape = as_tensor_shape(out_feature->layout()); + + auto concat_axe = as_tensor_axis(concat_f->axis()); + + // Lower: Left -> Output + { + auto src_feature = left_feature; + auto src_shape = left_shape; + + auto ins = m->entity()->instr()->create<coco::Shuffle>(); + + assert(src_feature->bag() != nullptr); + assert(out_feature->bag() != nullptr); + + ins->from(src_feature->bag()); + ins->into(out_feature->bag()); + + for (tensor::IndexEnumerator e{src_shape}; e.valid(); e.advance()) + { + tensor::Index src_index = e.current(); + tensor::Index out_index = e.current(); + + auto from = as_element_index(src_feature->layout(), src_index); + auto into = as_element_index(out_feature->layout(), out_index); + + ins->insert(from, into); + } + + ins->insertAfter(eval); + } + + // Lower: Right -> Output + { + auto src_feature = right_feature; + auto src_shape = right_shape; + + auto ins = m->entity()->instr()->create<coco::Shuffle>(); + + assert(src_feature->bag() != nullptr); + assert(out_feature->bag() != nullptr); + + ins->from(src_feature->bag()); + ins->into(out_feature->bag()); + + for (tensor::IndexEnumerator e{src_shape}; e.valid(); e.advance()) + { + tensor::Index src_index = e.current(); + tensor::Index out_index = e.current(); + + out_index.at(concat_axe) = out_index.at(concat_axe) + left_shape.dim(concat_axe); + + auto from = as_element_index(src_feature->layout(), src_index); + auto into = as_element_index(out_feature->layout(), out_index); + + ins->insert(from, into); + } + + ins->insertAfter(eval); + } + + // Unlink "Eval" and "ConcatF" op tree + eval->op(nullptr); + + // Delete "Concat" op tree + m->entity()->op()->destroy(concat_f->left()); + m->entity()->op()->destroy(concat_f->right()); + m->entity()->op()->destroy(concat_f); + + // Deatch "Eval" instruction from the block + eval->detach(); + + // Delete "Eval" instruction + m->entity()->instr()->destroy(eval); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/ConcatLowering.h b/compiler/enco/core/src/Transforms/ConcatLowering.h new file mode 100644 index 000000000..5d20e627b --- /dev/null +++ b/compiler/enco/core/src/Transforms/ConcatLowering.h @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_CONCAT_LOWERING_H__ +#define __ENCO_CONCAT_LOWERING_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Lower eval(Concat(...)) as a sequence of shuffle instructions + */ +void lower_concat(enco::Code *code); + +struct ConcatLoweringPass final : public Pass +{ + PASS_CTOR(ConcatLoweringPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { lower_concat(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_CONCAT_LOWERING_H__ diff --git a/compiler/enco/core/src/Transforms/ConstantFolding.cpp b/compiler/enco/core/src/Transforms/ConstantFolding.cpp new file mode 100644 index 000000000..cd6f22351 --- /dev/null +++ b/compiler/enco/core/src/Transforms/ConstantFolding.cpp @@ -0,0 +1,442 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "ConstantFolding.h" +#include "Session.h" + +#include <queue> +#include <cmath> +#include <cassert> + +namespace +{ + +/** + * @brief is_constant_bag(b) returns true if the bag "b" has corresponding weight + */ +bool is_constant_bag(coco::Bag *b) +{ + auto m = b->module(); + auto d = enco::data(m); + return d->allocated(b); +} + +class ConstantBagEnumerator +{ +public: + ConstantBagEnumerator(enco::Code *code) : _code{code} + { + // DO NOTHING + } + +public: + template <typename Callable> void enumerate(Callable cb) const + { + auto m = _code->module(); + + for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n) + { + auto b = m->entity()->bag()->at(n); + + if (is_constant_bag(b)) + { + cb(b); + } + } + } + +private: + enco::Code *_code; +}; + +template <typename Callable> void operator<<(const ConstantBagEnumerator &e, Callable &&cb) +{ + e.enumerate(std::forward<Callable>(cb)); +} + +ConstantBagEnumerator constant_bag_enumerator(enco::Code *code) +{ + return ConstantBagEnumerator{code}; +} + +} // namespace + +namespace +{ + +/** + * @brief Take the first element from the queue + * @note The queue SHOULD have at least one element. + */ +template <typename T> T take(std::queue<T> &q) +{ + assert(q.size() > 0); + auto res = q.front(); + q.pop(); + return res; +} + +} // namespace + +namespace +{ + +void fold_constant(std::queue<coco::Bag *> &q, coco::Copy *copy) +{ + auto m = copy->module(); + auto d = enco::data(m); + + auto src_obj = copy->from(); + auto src_bag = src_obj->bag(); + + auto dst_obj = copy->into(); + auto dst_bag = dst_obj->bag(); + + // Output calculation should not be folded + // TODO Reduce code duplication of this kind + if (dst_bag->isOutput()) + { + return; + } + + // NOTE d->allocated(bag) returns true if bag has corresponding initial + // values (e.g. convolution kernel) + assert(d->allocated(src_bag)); + assert(!d->allocated(dst_bag)); + + // TODO Support other data type + auto src_span = d->f32()->weight(src_bag); + + assert(src_span.data() != nullptr); + + auto src_feature = src_obj->asFeature(); + auto dst_feature = dst_obj->asFeature(); + + // TODO Support other object type + if (src_feature == nullptr || dst_feature == nullptr) + { + return; + } + + assert(src_feature != nullptr); + assert(dst_feature != nullptr); + + // Allocate weight for destination + d->f32()->allocate(dst_bag); + + auto dst_span = d->f32()->weight(dst_bag); + + assert(src_feature->layout()->batch() == dst_feature->layout()->batch()); + assert(src_feature->layout()->depth() == dst_feature->layout()->depth()); + assert(src_feature->layout()->height() == dst_feature->layout()->height()); + assert(src_feature->layout()->width() == dst_feature->layout()->width()); + + uint32_t const B = src_feature->layout()->batch(); + uint32_t const C = src_feature->layout()->depth(); + uint32_t const H = src_feature->layout()->height(); + uint32_t const W = src_feature->layout()->width(); + + for (uint32_t b = 0; b < B; ++b) + { + for (uint32_t ch = 0; ch < C; ++ch) + { + for (uint32_t row = 0; row < H; ++row) + { + for (uint32_t col = 0; col < W; ++col) + { + auto src_ind = src_feature->layout()->at(b, ch, row, col); + auto dst_ind = dst_feature->layout()->at(b, ch, row, col); + + dst_span[dst_ind.value()] = src_span[src_ind.value()]; + } + } + } + } + + // Let's detach copy + copy->from(nullptr); + copy->into(nullptr); + copy->detach(); + + // Let's visit destination bag! + q.push(dst_bag); +} + +template <typename Callable> +void fold_constant_op(std::queue<coco::Bag *> &q, coco::UnaryOp *op, Callable evaluate) +{ + auto m = op->module(); + auto d = enco::data(m); + + auto ins = op->parent(); + auto eval = ins->asEval(); + + // UnaryOp has only one arg + auto src_obj = *(op->uses().begin()); + auto src_bag = src_obj->bag(); + + auto dst_obj = eval->out(); + auto dst_bag = dst_obj->bag(); + + // Output calculation should not be folded + // TODO Reduce code duplication of this kind + if (dst_bag->isOutput()) + { + return; + } + + assert(d->allocated(src_bag)); + assert(!d->allocated(dst_bag)); + + // TODO Support other data type + auto src_span = d->f32()->weight(src_bag); + assert(src_span.data() != nullptr); + + auto src_feature = src_obj->asFeature(); + auto dst_feature = dst_obj->asFeature(); + + // TODO Support other object type + if (src_feature == nullptr || dst_feature == nullptr) + { + return; + } + + assert(src_feature != nullptr); + assert(dst_feature != nullptr); + + // Allocate weight for destination + d->f32()->allocate(dst_bag); + auto dst_span = d->f32()->weight(dst_bag); + + assert(src_feature->layout()->batch() == dst_feature->layout()->batch()); + assert(src_feature->layout()->depth() == dst_feature->layout()->depth()); + assert(src_feature->layout()->height() == dst_feature->layout()->height()); + assert(src_feature->layout()->width() == dst_feature->layout()->width()); + + uint32_t const B = src_feature->layout()->batch(); + uint32_t const C = src_feature->layout()->depth(); + uint32_t const H = src_feature->layout()->height(); + uint32_t const W = src_feature->layout()->width(); + + for (uint32_t b = 0; b < B; ++b) + { + for (uint32_t ch = 0; ch < C; ++ch) + { + for (uint32_t row = 0; row < H; ++row) + { + for (uint32_t col = 0; col < W; ++col) + { + auto src_ind = src_feature->layout()->at(b, ch, row, col); + auto dst_ind = dst_feature->layout()->at(b, ch, row, col); + + evaluate(&dst_span[dst_ind.value()], src_span[src_ind.value()]); + } + } + } + } + + // Let's detach eval + eval->out(nullptr); + eval->detach(); + + // Let's visit destination bag! + q.push(dst_bag); +} + +template <typename Callable> +void fold_constant_op(std::queue<coco::Bag *> &q, coco::BinaryOp *op, Callable evaluate) +{ + auto m = op->module(); + auto d = enco::data(m); + + auto ins = op->parent(); + auto eval = ins->asEval(); + + // Already folded by the other bag + if (!eval->out()) + { + return; + } + + auto lhs_load = op->left()->asLoad(); + auto lhs_obj = lhs_load->object(); + auto lhs_bag = lhs_obj->bag(); + + auto rhs_load = op->right()->asLoad(); + auto rhs_obj = rhs_load->object(); + auto rhs_bag = rhs_obj->bag(); + + auto dst_obj = eval->out(); + auto dst_bag = dst_obj->bag(); + + // Output calculation should not be folded + // TODO Reduce code duplication of this kind + if (dst_bag->isOutput()) + { + return; + } + + // The other bag is non-constant + if (!d->allocated(lhs_bag) || !d->allocated(rhs_bag)) + { + return; + } + + assert(d->allocated(lhs_bag)); + assert(d->allocated(rhs_bag)); + assert(!d->allocated(dst_bag)); + + // TODO Support other data type + auto lhs_span = d->f32()->weight(lhs_bag); + auto rhs_span = d->f32()->weight(rhs_bag); + assert(lhs_span.data() != nullptr); + assert(rhs_span.data() != nullptr); + + auto lhs_feature = lhs_obj->asFeature(); + auto rhs_feature = rhs_obj->asFeature(); + auto dst_feature = dst_obj->asFeature(); + + // TODO Support other object type + if (lhs_feature == nullptr || rhs_feature == nullptr || dst_feature == nullptr) + { + return; + } + + assert(lhs_feature != nullptr); + assert(rhs_feature != nullptr); + assert(dst_feature != nullptr); + + // Allocate weight for destination + d->f32()->allocate(dst_bag); + auto dst_span = d->f32()->weight(dst_bag); + + assert(lhs_feature->layout()->batch() == rhs_feature->layout()->batch()); + assert(lhs_feature->layout()->depth() == rhs_feature->layout()->depth()); + assert(lhs_feature->layout()->height() == rhs_feature->layout()->height()); + assert(lhs_feature->layout()->width() == rhs_feature->layout()->width()); + + assert(lhs_feature->layout()->batch() == dst_feature->layout()->batch()); + assert(lhs_feature->layout()->depth() == dst_feature->layout()->depth()); + assert(lhs_feature->layout()->height() == dst_feature->layout()->height()); + assert(lhs_feature->layout()->width() == dst_feature->layout()->width()); + + uint32_t const B = lhs_feature->layout()->batch(); + uint32_t const C = lhs_feature->layout()->depth(); + uint32_t const H = lhs_feature->layout()->height(); + uint32_t const W = lhs_feature->layout()->width(); + + for (uint32_t b = 0; b < B; ++b) + { + for (uint32_t ch = 0; ch < C; ++ch) + { + for (uint32_t row = 0; row < H; ++row) + { + for (uint32_t col = 0; col < W; ++col) + { + auto lhs_ind = lhs_feature->layout()->at(b, ch, row, col); + auto rhs_ind = rhs_feature->layout()->at(b, ch, row, col); + auto dst_ind = dst_feature->layout()->at(b, ch, row, col); + + evaluate(&dst_span[dst_ind.value()], lhs_span[lhs_ind.value()], + rhs_span[rhs_ind.value()]); + } + } + } + } + + // Let's detach eval + eval->out(nullptr); + eval->detach(); + + // Let's visit destination bag! + q.push(dst_bag); +} + +void fold_constant(std::queue<coco::Bag *> &q, coco::Eval *eval) +{ + // TODO Support other data types + if (auto op = eval->op()->asSqrt()) + { + fold_constant_op(q, op, [](float *dst, float value) { *dst = std::sqrt(value); }); + } + else if (auto op = eval->op()->asAdd()) + { + fold_constant_op(q, op, [](float *dst, float lhs, float rhs) { *dst = lhs + rhs; }); + } + else if (auto op = eval->op()->asSub()) + { + fold_constant_op(q, op, [](float *dst, float lhs, float rhs) { *dst = lhs - rhs; }); + } + else if (auto op = eval->op()->asMul()) + { + fold_constant_op(q, op, [](float *dst, float lhs, float rhs) { *dst = lhs * rhs; }); + } + else if (auto op = eval->op()->asDiv()) + { + fold_constant_op(q, op, [](float *dst, float lhs, float rhs) { *dst = lhs / rhs; }); + } + else + { + // Not supported opteration, do nothing + // TODO Support other operations + } +} + +void fold_constant(std::queue<coco::Bag *> &q, coco::Instr *ins) +{ + if (auto copy = coco::safe_cast<coco::Copy>(ins)) + { + fold_constant(q, copy); + return; + } + if (auto eval = coco::safe_cast<coco::Eval>(ins)) + { + fold_constant(q, eval); + return; + } + + // TODO Add more cases for constant folding +} + +} // namespace + +namespace enco +{ + +void fold_constants(enco::Code *code) +{ + std::queue<coco::Bag *> q; + + // Collect the initial set of "constant" bag + constant_bag_enumerator(code) << [&q](coco::Bag *bag) { q.push(bag); }; + + while (!q.empty()) + { + auto candidate_bag = take(q); + + // Scan the readers of each candidate bag + for (auto reader : coco::readers(candidate_bag)) + { + // TODO Decide how to handle the reader with unknown instruction + if (auto ins = reader->loc()) + { + fold_constant(q, ins); + } + } + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/ConstantFolding.h b/compiler/enco/core/src/Transforms/ConstantFolding.h new file mode 100644 index 000000000..6faa9c876 --- /dev/null +++ b/compiler/enco/core/src/Transforms/ConstantFolding.h @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __CONSTANT_FOLDING_H__ +#define __CONSTANT_FOLDING_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Evaluate "constant" expressions at compile time + */ +void fold_constants(enco::Code *); + +struct ConstantFoldingPass final : public Pass +{ + PASS_CTOR(ConstantFoldingPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { fold_constants(code(sess)); } +}; + +} // namespace enco + +#endif // __CONSTANT_FOLDING_H__ diff --git a/compiler/enco/core/src/Transforms/ConstantFolding.test.cpp b/compiler/enco/core/src/Transforms/ConstantFolding.test.cpp new file mode 100644 index 000000000..5ac71ac14 --- /dev/null +++ b/compiler/enco/core/src/Transforms/ConstantFolding.test.cpp @@ -0,0 +1,327 @@ +/* + * Copyright (c) 2019 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "ConstantFolding.h" +#include "Session.h" + +#include <cmath> +#include <gtest/gtest.h> + +namespace +{ + +class BinaryNetwork +{ +public: + BinaryNetwork(coco::Module *module, coco::Data *data) : _module{module}, _data{data} + { + // DO NOTHING + } + + template <typename Op> void build(void); + + void fold(void) + { + // Execute constant folding + enco::make_session(_module, _data); + enco::Code code{_module, _data}; + enco::fold_constants(&code); + } + +public: + coco::Bag *out; + coco::Bag *lhs; + coco::Bag *rhs; + + coco::Eval *eval; + +private: + coco::Module *_module; + coco::Data *_data; +}; + +template <typename Op> void BinaryNetwork::build(void) +{ + // Create lhs bag and object + auto lhs_bag = _module->entity()->bag()->create(12); + auto lhs_obj = _module->entity()->object()->template create<coco::FeatureObject>(); + coco::FeatureShape lhs_shape(1, 2, 2, 3); + lhs_obj->bag(lhs_bag); + lhs_obj->layout(coco::FeatureLayouts::BHWC::create(lhs_shape)); + + // Create rhs bag and object + auto rhs_bag = _module->entity()->bag()->create(12); + auto rhs_obj = _module->entity()->object()->template create<coco::FeatureObject>(); + coco::FeatureShape rhs_shape(1, 2, 2, 3); + rhs_obj->bag(rhs_bag); + rhs_obj->layout(coco::FeatureLayouts::BHWC::create(rhs_shape)); + + // Create output bag and object + auto output_bag = _module->entity()->bag()->create(12); + auto output_obj = _module->entity()->object()->template create<coco::FeatureObject>(); + coco::FeatureShape ofm_shape(1, 2, 2, 3); + output_obj->bag(output_bag); + output_obj->layout(coco::FeatureLayouts::BHWC::create(ofm_shape)); + + // Create instruction and operations + auto block = _module->entity()->block()->create(); + auto eval = _module->entity()->instr()->template create<coco::Eval>(); + auto load_lhs = _module->entity()->op()->template create<coco::Load>(); + auto load_rhs = _module->entity()->op()->template create<coco::Load>(); + auto add_op = _module->entity()->op()->template create<Op>(); + + _module->block()->append(block); + block->instr()->append(eval); + + load_lhs->object(lhs_obj); + load_rhs->object(rhs_obj); + add_op->left(load_lhs); + add_op->right(load_rhs); + + eval->op(add_op); + eval->out(output_obj); + + // Create a handle + this->lhs = lhs_bag; + this->rhs = rhs_bag; + this->out = output_bag; + + this->eval = eval; +} + +} // namespace + +TEST(ConstantFoldingTest, sqrt) +{ + auto module = coco::Module::create(); + auto data = coco::Data::create(); + + // Create input bag and object + auto input_bag = module->entity()->bag()->create(12); + auto input_obj = module->entity()->object()->create<coco::FeatureObject>(); + coco::FeatureShape ifm_shape(1, 2, 2, 3); + input_obj->bag(input_bag); + input_obj->layout(coco::FeatureLayouts::BHWC::create(ifm_shape)); + + // Create output bag and object + auto output_bag = module->entity()->bag()->create(12); + auto output_obj = module->entity()->object()->create<coco::FeatureObject>(); + coco::FeatureShape ofm_shape(1, 2, 2, 3); + output_obj->bag(output_bag); + output_obj->layout(coco::FeatureLayouts::BHWC::create(ofm_shape)); + + // Insert values into input bag + data->f32()->allocate(input_bag); + auto input = data->f32()->weight(input_bag); + for (uint32_t idx = 0; idx < input.size(); ++idx) + { + input[idx] = (float)idx; + } + + // Create instruction and operations + auto block = module->entity()->block()->create(); + auto eval = module->entity()->instr()->create<coco::Eval>(); + auto load = module->entity()->op()->create<coco::Load>(); + auto sqrt_op = module->entity()->op()->create<coco::Sqrt>(); + + module->block()->append(block); + block->instr()->append(eval); + + load->object(input_obj); + sqrt_op->arg(load); + + eval->op(sqrt_op); + eval->out(output_obj); + + // Execute constant folding + enco::make_session(module.get(), data.get()); + enco::Code code{module.get(), data.get()}; + enco::fold_constants(&code); + + // Validate the result + ASSERT_EQ(data->allocated(output_bag), true); + ASSERT_EQ(eval->out(), nullptr); + + auto output = data->f32()->weight(output_bag); + for (uint32_t idx = 0; idx < output.size(); ++idx) + { + ASSERT_FLOAT_EQ(output[idx], std::sqrt(input[idx])); + } +} + +TEST(ConstantFoldingTest, element_wise_add) +{ + auto module = coco::Module::create(); + auto data = coco::Data::create(); + + BinaryNetwork net{module.get(), data.get()}; + + // Build a network + net.build<coco::Add>(); + + // Create alises + auto lhs_bag = net.lhs; + auto rhs_bag = net.rhs; + auto output_bag = net.out; + auto eval = net.eval; + + // Insert values into lhs and rhs bag + data->f32()->allocate(lhs_bag); + data->f32()->allocate(rhs_bag); + auto lhs = data->f32()->weight(lhs_bag); + auto rhs = data->f32()->weight(rhs_bag); + for (uint32_t idx = 0; idx < lhs.size(); ++idx) + { + lhs[idx] = (float)idx; + rhs[idx] = 1.5; + } + + // Execute constant folding + net.fold(); + + // Validate the result + ASSERT_EQ(data->allocated(output_bag), true); + ASSERT_EQ(eval->out(), nullptr); + + auto output = data->f32()->weight(output_bag); + for (uint32_t idx = 0; idx < output.size(); ++idx) + { + ASSERT_FLOAT_EQ(output[idx], lhs[idx] + rhs[idx]); + } +} + +TEST(ConstantFoldingTest, element_wise_sub) +{ + auto module = coco::Module::create(); + auto data = coco::Data::create(); + + BinaryNetwork net{module.get(), data.get()}; + + // Build a network + net.build<coco::Sub>(); + + // Create alises + auto lhs_bag = net.lhs; + auto rhs_bag = net.rhs; + auto output_bag = net.out; + auto eval = net.eval; + + // Insert values into lhs and rhs bag + data->f32()->allocate(lhs_bag); + data->f32()->allocate(rhs_bag); + auto lhs = data->f32()->weight(lhs_bag); + auto rhs = data->f32()->weight(rhs_bag); + for (uint32_t idx = 0; idx < lhs.size(); ++idx) + { + lhs[idx] = (float)idx; + rhs[idx] = 1.5; + } + + // Execute constant folding + net.fold(); + + // Validate the result + ASSERT_EQ(data->allocated(output_bag), true); + ASSERT_EQ(eval->out(), nullptr); + + auto output = data->f32()->weight(output_bag); + for (uint32_t idx = 0; idx < output.size(); ++idx) + { + ASSERT_FLOAT_EQ(output[idx], lhs[idx] - rhs[idx]); + } +} + +TEST(ConstantFoldingTest, element_wise_mul) +{ + auto module = coco::Module::create(); + auto data = coco::Data::create(); + + BinaryNetwork net{module.get(), data.get()}; + + // Build a network + net.build<coco::Mul>(); + + // Create alises + auto lhs_bag = net.lhs; + auto rhs_bag = net.rhs; + auto output_bag = net.out; + auto eval = net.eval; + + // Insert values into lhs and rhs bag + data->f32()->allocate(lhs_bag); + data->f32()->allocate(rhs_bag); + auto lhs = data->f32()->weight(lhs_bag); + auto rhs = data->f32()->weight(rhs_bag); + for (uint32_t idx = 0; idx < lhs.size(); ++idx) + { + lhs[idx] = (float)idx; + rhs[idx] = 1.5; + } + + // Execute constant folding + net.fold(); + + // Validate the result + ASSERT_EQ(data->allocated(output_bag), true); + ASSERT_EQ(eval->out(), nullptr); + + auto output = data->f32()->weight(output_bag); + for (uint32_t idx = 0; idx < output.size(); ++idx) + { + ASSERT_FLOAT_EQ(output[idx], lhs[idx] * rhs[idx]); + } +} + +TEST(ConstantFoldingTest, element_wise_div) +{ + auto module = coco::Module::create(); + auto data = coco::Data::create(); + + BinaryNetwork net{module.get(), data.get()}; + + // Build a network + net.build<coco::Div>(); + + // Create alises + auto lhs_bag = net.lhs; + auto rhs_bag = net.rhs; + auto output_bag = net.out; + auto eval = net.eval; + + // Insert values into lhs and rhs bag + data->f32()->allocate(lhs_bag); + data->f32()->allocate(rhs_bag); + auto lhs = data->f32()->weight(lhs_bag); + auto rhs = data->f32()->weight(rhs_bag); + for (uint32_t idx = 0; idx < lhs.size(); ++idx) + { + lhs[idx] = (float)idx; + rhs[idx] = 1.5; + } + + // Execute constant folding + net.fold(); + + // Validate the result + ASSERT_EQ(data->allocated(output_bag), true); + ASSERT_EQ(eval->out(), nullptr); + + auto output = data->f32()->weight(output_bag); + for (uint32_t idx = 0; idx < output.size(); ++idx) + { + ASSERT_FLOAT_EQ(output[idx], lhs[idx] / rhs[idx]); + } +} diff --git a/compiler/enco/core/src/Transforms/CopyLowering.cpp b/compiler/enco/core/src/Transforms/CopyLowering.cpp new file mode 100644 index 000000000..ceb3bbd5c --- /dev/null +++ b/compiler/enco/core/src/Transforms/CopyLowering.cpp @@ -0,0 +1,105 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "CopyLowering.h" + +#include <set> +#include <cassert> + +// +// Lower Copy as Shuffle +// +namespace enco +{ + +void lower_copy(enco::Code *code) +{ + auto m = code->module(); + + std::set<coco::Copy *> lowered_copies; + + for (uint32_t n = 0; n < m->entity()->instr()->size(); ++n) + { + auto ins = m->entity()->instr()->at(n); + + assert(ins != nullptr); + + if (ins->parent() == nullptr) + { + // Skip if instruction does not belong to a list + continue; + } + + auto copy = ins->asCopy(); + + if (copy == nullptr) + { + // Skip if instruction is not a copy + continue; + } + + // TODO Support non-Feature objects + auto ifm = copy->from()->asFeature(); + auto ofm = copy->into()->asFeature(); + + if ((ifm == nullptr) || (ofm == nullptr)) + { + continue; + } + + assert(ifm->layout()->batch() == ofm->layout()->batch()); + assert(ifm->layout()->shape() == ofm->layout()->shape()); + + auto shuffle = m->entity()->instr()->create<coco::Shuffle>(); + + shuffle->from(ifm->bag()); + shuffle->into(ofm->bag()); + + const uint32_t B = ifm->layout()->batch(); + const uint32_t C = ifm->layout()->shape().depth(); + const uint32_t H = ifm->layout()->shape().height(); + const uint32_t W = ifm->layout()->shape().width(); + + for (uint32_t b = 0; b < B; ++b) + { + for (uint32_t ch = 0; ch < C; ++ch) + { + for (uint32_t row = 0; row < H; ++row) + { + for (uint32_t col = 0; col < W; ++col) + { + const auto from = ifm->layout()->at(b, ch, row, col); + const auto into = ofm->layout()->at(b, ch, row, col); + + shuffle->insert(from, into); + } + } + } + } + + shuffle->insertBefore(copy); + lowered_copies.insert(copy); + } + + // Destroy lowered copy + for (const auto © : lowered_copies) + { + copy->detach(); + m->entity()->instr()->destroy(copy); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/CopyLowering.h b/compiler/enco/core/src/Transforms/CopyLowering.h new file mode 100644 index 000000000..51f0f83e2 --- /dev/null +++ b/compiler/enco/core/src/Transforms/CopyLowering.h @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_LOWER_H__ +#define __ENCO_LOWER_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Lower copy(...) instruction into shuffle(...) + */ +void lower_copy(enco::Code *code); + +struct CopyLoweringPass final : public Pass +{ + PASS_CTOR(CopyLoweringPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { lower_copy(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_LOWER_H__ diff --git a/compiler/enco/core/src/Transforms/DataLayoutConversion.cpp b/compiler/enco/core/src/Transforms/DataLayoutConversion.cpp new file mode 100644 index 000000000..9d65d1c0b --- /dev/null +++ b/compiler/enco/core/src/Transforms/DataLayoutConversion.cpp @@ -0,0 +1,383 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "DataLayoutConversion.h" +#include "Session.h" +#include "IRUtils.h" + +#include "coex/IR.h" + +#include <coco/IR/FeatureLayouts.h> +#include <coco/IR/KernelLayouts.h> + +#include <nncc/core/ADT/feature/Layout.h> +#include <nncc/core/ADT/kernel/Layout.h> + +#include <nncc/core/ADT/feature/HWCLayout.h> +#include <nncc/core/ADT/kernel/NHWCLayout.h> + +#include <set> + +namespace +{ + +coco::Copy *make_copy(coco::FeatureObject *from, coco::FeatureObject *into) +{ + auto m = from->module(); + assert(m != nullptr); + assert(from->module() == into->module()); + + auto copy = m->entity()->instr()->create<coco::Copy>(); + + copy->from(from); + copy->into(into); + + return copy; +} + +coco::FeatureObject *clone_feature(const coco::FeatureObject *oldobj) +{ + auto module = oldobj->module(); + auto newobj = module->entity()->object()->create<coco::FeatureObject>(); + newobj->layout(coco::FeatureLayouts::BHWC::create(oldobj->shape())); + + if (oldobj->bag() != nullptr) + { + using nncc::core::ADT::feature::num_elements; + + // NOTE The size of bag should be at least "BxHxWxC" as "newobj" uses BHWC layout + const uint32_t batch = newobj->layout()->batch(); + const uint32_t count = num_elements(newobj->layout()->shape()); + const uint32_t bag_size = batch * count; + + // Clone bag only when there is a backing bag for a given feature object + auto newbag = module->entity()->bag()->create(bag_size); + newobj->bag(newbag); + } + + return newobj; +} + +/** + * @brief Insert Copy before Load if necessary + * + * @require "load" should be bounded + */ +void insert_copy_before_load(coco::Load *load) +{ + assert(load->parent() != nullptr); + assert(load->parent()->parent() != nullptr); + + if (auto obj = load->object()) + { + if (auto ifm = obj->asFeature()) + { + if (ifm->layout()->id() != coco::FeatureLayouts::BHWC::uid()) + { + auto oldobj = ifm; + auto newobj = clone_feature(oldobj); + + load->object(newobj); + + auto copy = make_copy(oldobj, newobj); + copy->insertBefore(load->parent()); + } + } + } +} + +/** + * @brief Insert Copy after Eval if necessary + */ +void insert_copy_after_eval(coco::Eval *eval) +{ + if (auto out = eval->out()) + { + if (auto ofm = out->asFeature()) + { + if (ofm->layout()->id() != coco::FeatureLayouts::BHWC::uid()) + { + auto oldobj = ofm; + auto newobj = clone_feature(oldobj); + + eval->out(newobj); + + auto copy = make_copy(newobj, oldobj); + copy->insertAfter(eval); + } + } + } +} + +/** + * @brief Insert copy (for data layout change) before/after ANNDepthConcatF if necessary + */ +void convert_data_layout(ANNDepthConcatF *concat) +{ + if (auto out = concat->out()) + { + if (auto ofm = out->asFeature()) + { + if (ofm->layout()->id() != coco::FeatureLayouts::BHWC::uid()) + { + auto oldobj = ofm; + auto newobj = clone_feature(oldobj); + + concat->out(newobj); + + auto copy = make_copy(newobj, oldobj); + copy->insertAfter(concat); + } + } + } + + if (auto obj = concat->fst()) + { + if (auto ifm = obj->asFeature()) + { + if (ifm->layout()->id() != coco::FeatureLayouts::BHWC::uid()) + { + auto oldobj = ifm; + auto newobj = clone_feature(oldobj); + + concat->fst(newobj); + + auto copy = make_copy(oldobj, newobj); + copy->insertBefore(concat); + } + } + } + + if (auto obj = concat->snd()) + { + if (auto ifm = obj->asFeature()) + { + if (ifm->layout()->id() != coco::FeatureLayouts::BHWC::uid()) + { + auto oldobj = ifm; + auto newobj = clone_feature(oldobj); + + concat->snd(newobj); + + auto copy = make_copy(oldobj, newobj); + copy->insertBefore(concat); + } + } + } +} + +/** + * @brief Update convolution kernel data layout + */ +void change_conv2d_kernel_layout(coco::Conv2D *conv) +{ + auto m = conv->module(); + assert(m != nullptr); + auto d = enco::data(enco::session(m)); + assert(d != nullptr); + + auto old_obj = conv->ker(); + assert(old_obj != nullptr); + auto old_bag = old_obj->bag(); + assert(old_bag != nullptr); + + if (old_obj->layout()->id() == coco::KernelLayouts::NHWC::uid()) + { + // Skip if kernel already uses NHWC layout + return; + } + + const auto &ker_shape = old_obj->shape(); + + assert(d->allocated(old_bag)); + + auto new_bag = m->entity()->bag()->create(old_bag->size()); + auto new_obj = m->entity()->object()->create<coco::KernelObject>(); + + new_obj->bag(new_bag); + new_obj->layout(coco::KernelLayouts::NHWC::create(ker_shape)); + + d->f32()->allocate(new_bag); + + auto src = d->f32()->read(old_obj); + auto dst = d->f32()->access(new_obj); + + const auto ker_N = ker_shape.count(); + const auto ker_C = ker_shape.depth(); + const auto ker_H = ker_shape.height(); + const auto ker_W = ker_shape.width(); + + for (uint32_t n = 0; n < ker_N; ++n) + { + for (uint32_t ch = 0; ch < ker_C; ++ch) + { + for (uint32_t row = 0; row < ker_H; ++row) + { + for (uint32_t col = 0; col < ker_W; ++col) + { + dst->at(n, ch, row, col) = src->at(n, ch, row, col); + } + } + } + } + + conv->ker(new_obj); + d->release(old_bag); +} + +} // namespace + +namespace +{ + +/** + * @brief Return the set of all of bounded Load Op(s) in a given module + * + * @note 'bounded' means it will be exectuted + */ +std::set<coco::Load *> loads(coco::Module *m) +{ + std::set<coco::Load *> res; + + for (uint32_t n = 0; n < m->entity()->op()->size(); ++n) + { + auto op = m->entity()->op()->at(n); + + // Skip if this op is dangling + if (op->parent() == nullptr) + { + continue; + } + + // Skip if eval instruction of this op is dangling + if (op->parent()->parent() == nullptr) + { + continue; + } + + if (auto load = m->entity()->op()->at(n)->asLoad()) + { + res.insert(load); + } + } + + return res; +} + +/** + * @brief Return the set of every (allocated) Eval instruction in a given module + */ +std::set<coco::Eval *> evals(coco::Module *m) +{ + std::set<coco::Eval *> res; + + for (uint32_t n = 0; n < m->entity()->instr()->size(); ++n) + { + if (auto eval = m->entity()->instr()->at(n)->asEval()) + { + res.insert(eval); + } + } + + return res; +} + +/** + * @brief Return the set of allocated Conv2D op in a given module + */ +std::set<coco::Conv2D *> convs(coco::Module *m) +{ + std::set<coco::Conv2D *> res; + + for (uint32_t n = 0; n < m->entity()->op()->size(); ++n) + { + if (auto op = m->entity()->op()->at(n)->asConv2D()) + { + res.insert(op); + } + } + + return res; +} + +/** + * @brief Return the set of "bounded" ANNDepthConcatF instructions + */ +std::set<ANNDepthConcatF *> depth_concats(coco::Module *m) +{ + std::set<ANNDepthConcatF *> res; + + for (auto ins : enco::instr_sequence(m)) + { + if (auto depth_concat_f = coco::safe_cast<ANNDepthConcatF>(ins)) + { + res.insert(depth_concat_f); + } + } + + return res; +} + +class NormalizePass +{ +private: + void runOnModule(coco::Module *m) const; + +public: + void runOnCode(enco::Code *) const; +}; + +void NormalizePass::runOnModule(coco::Module *m) const +{ + // Insert Copy before all Load Op (if necessary) + for (auto load : loads(m)) + { + insert_copy_before_load(load); + } + + // Insert Copy after all Eval Instr (if necessary) + for (auto eval : evals(m)) + { + insert_copy_after_eval(eval); + } + + // Change Kernel Layout of Conv2D opertion (if necessary) + for (auto conv : convs(m)) + { + change_conv2d_kernel_layout(conv); + } + + // Insert Copy (for Layout Conversion) before/after ANNDepthConcatF instructions (if necessary) + for (auto depth_concat : depth_concats(m)) + { + convert_data_layout(depth_concat); + } +} + +void NormalizePass::runOnCode(enco::Code *code) const { runOnModule(code->module()); } + +} // namespace + +namespace enco +{ + +void convert_data_layout(enco::Code *code) +{ + NormalizePass pass; + pass.runOnCode(code); +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/DataLayoutConversion.h b/compiler/enco/core/src/Transforms/DataLayoutConversion.h new file mode 100644 index 000000000..ac4052c8b --- /dev/null +++ b/compiler/enco/core/src/Transforms/DataLayoutConversion.h @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_DATA_LAYOUT_CONVERSION_H__ +#define __ENCO_TRANSFORM_DATA_LAYOUT_CONVERSION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Insert data reordering if necessary + */ +void convert_data_layout(enco::Code *code); + +struct DataLayoutConversionPass final : public enco::Pass +{ + PASS_CTOR(DataLayoutConversionPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { convert_data_layout(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_DATA_LAYOUT_CONVERSION_H__ diff --git a/compiler/enco/core/src/Transforms/DataLayoutConversion.test.cpp b/compiler/enco/core/src/Transforms/DataLayoutConversion.test.cpp new file mode 100644 index 000000000..812e38a78 --- /dev/null +++ b/compiler/enco/core/src/Transforms/DataLayoutConversion.test.cpp @@ -0,0 +1,33 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "DataLayoutConversion.h" + +#include <gtest/gtest.h> + +TEST(DataLayoutConversionTest, case_000) +{ + auto m = coco::Module::create(); + + // Create a "free" Load op + m->entity()->instr()->create<coco::Eval>(); + + enco::Code code{m.get(), nullptr}; + ASSERT_EQ(m->entity()->instr()->size(), 1); + + // "conver_data_layout" SHOULD NOT crash even if there is a "free" Load op + enco::convert_data_layout(&code); +} diff --git a/compiler/enco/core/src/Transforms/DeadBagElimination.cpp b/compiler/enco/core/src/Transforms/DeadBagElimination.cpp new file mode 100644 index 000000000..b3c598a55 --- /dev/null +++ b/compiler/enco/core/src/Transforms/DeadBagElimination.cpp @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "DeadBagElimination.h" + +#include <set> + +namespace +{ + +/// @brief Return true if a given bag is marked as either input or output +bool is_public(const coco::Bag *b) { return b->isInput() || b->isOutput(); } + +/// @brief Return the set of "dead" bags in a given module +std::set<coco::Bag *> dead_bags(const coco::Module *m) +{ + std::set<coco::Bag *> res; + + for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n) + { + auto bag = m->entity()->bag()->at(n); + + if (coco::readers(bag).empty() && !is_public(bag)) + { + res.insert(bag); + } + } + + return res; +} + +} // namespace + +namespace enco +{ + +void eliminate_dead_bag(enco::Code *code) +{ + auto m = code->module(); + + // Destroy a dead bag and its updaters + for (auto bag : dead_bags(m)) + { + for (auto updater : coco::updaters(bag)) + { + auto ins = updater->loc(); + + assert(ins != nullptr); + + ins->detach(); + m->entity()->instr()->destroy(ins); + } + + bag->replaceWith(nullptr); + m->entity()->bag()->destroy(bag); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/DeadBagElimination.h b/compiler/enco/core/src/Transforms/DeadBagElimination.h new file mode 100644 index 000000000..87e03e8ac --- /dev/null +++ b/compiler/enco/core/src/Transforms/DeadBagElimination.h @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_DEAD_BAG_ELIMINATION_H__ +#define __ENCO_TRANSFORM_DEAD_BAG_ELIMINATION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Eliminate dead bags + * + * A bag is referred to as dead if it is neither input nor output, and has no read. If a bag is + * dead, it is unnecessary to updates its values as these values are never used. + * + * "eliminate_dead_bag" removes all the dead bags and its updaters from IR. + */ +void eliminate_dead_bag(enco::Code *code); + +struct DeadBagEliminationPass final : public Pass +{ + PASS_CTOR(DeadBagEliminationPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { eliminate_dead_bag(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_DEAD_BAG_ELIMINATION_H__ diff --git a/compiler/enco/core/src/Transforms/DeadObjectElimination.cpp b/compiler/enco/core/src/Transforms/DeadObjectElimination.cpp new file mode 100644 index 000000000..df8cc628a --- /dev/null +++ b/compiler/enco/core/src/Transforms/DeadObjectElimination.cpp @@ -0,0 +1,77 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "DeadObjectElimination.h" + +#include <set> + +namespace +{ + +std::set<coco::Object *> dead_objects(const coco::Module *m) +{ + std::set<coco::Object *> res; + + for (uint32_t n = 0; n < m->entity()->object()->size(); ++n) + { + auto obj = m->entity()->object()->at(n); + + if (auto bag = obj->bag()) + { + if (coco::readers(bag).empty() && !(bag->isOutput())) + { + res.insert(obj); + } + } + else + { + // NOTE Just in case if there are Objects not related to Bags + if (obj->uses()->size() == 0) + { + res.insert(obj); + } + } + } + + return res; +} + +} // namespace + +namespace enco +{ + +void eliminate_dead_object(enco::Code *code) +{ + auto m = code->module(); + + // Destroy a dead object and its producer + for (auto obj : dead_objects(m)) + { + if (auto producer = coco::producer(obj)) + { + auto ins = producer->loc(); + assert(ins != nullptr); + + ins->detach(); + m->entity()->instr()->destroy(ins); + } + + m->entity()->object()->destroy(obj); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/DeadObjectElimination.h b/compiler/enco/core/src/Transforms/DeadObjectElimination.h new file mode 100644 index 000000000..4923e56fd --- /dev/null +++ b/compiler/enco/core/src/Transforms/DeadObjectElimination.h @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_DEAD_OBJECT_ELIMINATION_H__ +#define __ENCO_TRANSFORM_DEAD_OBJECT_ELIMINATION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Eliminate dead objects in IR + * + * An object whose backing bag is unused is referred to as a dead object. + * + * Dead Object Elimination (DOE) eliminates such dead objects along with their producer. + */ +void eliminate_dead_object(enco::Code *code); + +struct DeadObjectEliminationPass final : public Pass +{ + PASS_CTOR(DeadObjectEliminationPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { eliminate_dead_object(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_DEAD_OBJECT_ELIMINATION_H__ diff --git a/compiler/enco/core/src/Transforms/Duplicate.cpp b/compiler/enco/core/src/Transforms/Duplicate.cpp new file mode 100644 index 000000000..91f64a0ad --- /dev/null +++ b/compiler/enco/core/src/Transforms/Duplicate.cpp @@ -0,0 +1,135 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Duplicate.h" + +#include <map> +#include <set> + +#include <cassert> + +namespace +{ + +coco::Block *find_or_create_first_block(coco::Module *m) +{ + if (m->block()->empty()) + { + auto blk = m->entity()->block()->create(); + m->block()->append(blk); + return blk; + } + + return m->block()->head(); +} + +} // namespace + +namespace +{ + +class DuplicatePass +{ +private: + void runOnModule(coco::Module *m) const; + +public: + void runOnCode(enco::Code *) const; +}; + +void DuplicatePass::runOnModule(coco::Module *m) const +{ + // Let's find candidates + std::set<coco::Bag *> candidates; + + for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n) + { + auto bag = m->entity()->bag()->at(n); + + if (bag->isInput() && bag->isOutput()) + { + candidates.insert(bag); + } + } + + // Return if there is no candidate + if (candidates.empty()) + { + return; + } + + std::map<const coco::Bag *, coco::Input *> input_map; + std::map<const coco::Bag *, coco::Output *> output_map; + + for (uint32_t n = 0; n < m->input()->size(); ++n) + { + auto input = m->input()->at(n); + assert(input->bag() != nullptr); + input_map[input->bag()] = input; + } + + for (uint32_t n = 0; n < m->output()->size(); ++n) + { + auto output = m->output()->at(n); + assert(output->bag() != nullptr); + output_map[output->bag()] = output; + } + + // For each in/out bag, + // 1. Create a new bag of the same size + // 2. Copy the content from the original bag + // 3. Mark the newly created bag as an output + for (const auto &candidate : candidates) + { + assert(coco::updaters(candidate).empty()); + assert(input_map.find(candidate) != input_map.end()); + assert(output_map.find(candidate) != output_map.end()); + + auto src = candidate; + auto dst = m->entity()->bag()->create(src->size()); + + // Create a copy instruction + auto shuffle = m->entity()->instr()->create<coco::Shuffle>(); + + shuffle->from(src); + shuffle->into(dst); + + for (uint32_t n = 0; n < src->size(); ++n) + { + shuffle->insert(coco::ElemID{n} /* FROM */, coco::ElemID{n} /* INTO */); + } + + find_or_create_first_block(m)->instr()->prepend(shuffle); + + // Let's use the new bag as an output + output_map.at(src)->bag(dst); + } +} + +void DuplicatePass::runOnCode(enco::Code *code) const { runOnModule(code->module()); } + +} // namespace + +namespace enco +{ + +void duplicate_inout_bag(enco::Code *code) +{ + DuplicatePass duplicate; + duplicate.runOnCode(code); +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/Duplicate.h b/compiler/enco/core/src/Transforms/Duplicate.h new file mode 100644 index 000000000..93baa4589 --- /dev/null +++ b/compiler/enco/core/src/Transforms/Duplicate.h @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __DUPLICATE_H__ +#define __DUPLICATE_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Eliminate in/out bags by duplication + */ +void duplicate_inout_bag(enco::Code *code); + +struct BagDuplicationPass final : public Pass +{ + PASS_CTOR(BagDuplicationPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { duplicate_inout_bag(code(sess)); } +}; + +} // namespace enco + +#endif // __DUPLICATE_H__ diff --git a/compiler/enco/core/src/Transforms/DuplicatedObjectReduction.cpp b/compiler/enco/core/src/Transforms/DuplicatedObjectReduction.cpp new file mode 100644 index 000000000..fa84c005c --- /dev/null +++ b/compiler/enco/core/src/Transforms/DuplicatedObjectReduction.cpp @@ -0,0 +1,119 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "DuplicatedObjectReduction.h" + +#include "CodeIndex.h" +#include "IRUtils.h" + +#include <set> + +namespace +{ + +/** + * @brief Collect feature objects in coco IR + */ +std::set<coco::FeatureObject *> features(const coco::Module *m) +{ + std::set<coco::FeatureObject *> res; + + for (uint32_t n = 0; n < m->entity()->object()->size(); ++n) + { + if (auto feature = m->entity()->object()->at(n)->asFeature()) + { + res.insert(feature); + } + } + + return res; +} + +std::set<coco::FeatureObject *> candidates(const coco::FeatureObject *src) +{ + std::set<coco::FeatureObject *> res; + + for (auto consumer : coco::consumers(src)) + { + if (auto copy = consumer->loc()->asCopy()) + { + auto dst = copy->into()->asFeature(); + assert(dst != nullptr); + + if (dst->layout()->id() == coco::FeatureLayouts::BHWC::uid()) + { + res.insert(dst); + } + } + } + + return res; +} + +CodeIndex code_index(coco::Object::Producer *p) +{ + if (auto ins = p->loc()) + { + return ::code_index(ins); + } + + return CodeIndex{}; +} + +} // namespace + +namespace enco +{ + +void reduce_duplicated_object(enco::Code *code) +{ + auto m = code->module(); + + for (const auto &src : features(m)) + { + auto copied = candidates(src); + + if (copied.size() <= 1) + { + continue; + } + + // Find the dominator + coco::FeatureObject *dominator = nullptr; + + for (auto candidate : copied) + { + if (dominator == nullptr) + { + dominator = candidate; + } + else if (code_index(coco::producer(candidate)) < code_index(coco::producer(dominator))) + { + dominator = candidate; + } + } + + // Replace all the occurunce of dominated objects with its dominator + copied.erase(dominator); + + for (auto dominatee : copied) + { + subst(dominatee, dominator); + } + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/DuplicatedObjectReduction.h b/compiler/enco/core/src/Transforms/DuplicatedObjectReduction.h new file mode 100644 index 000000000..3aa20058e --- /dev/null +++ b/compiler/enco/core/src/Transforms/DuplicatedObjectReduction.h @@ -0,0 +1,73 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_DUPLICATED_OBJECT_REDUCTION_H__ +#define __ENCO_TRANSFORM_DUPLICATED_OBJECT_REDUCTION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Reduce duplicated feature objects as its dominating feature object + * + * >>> BEFORE <<< + * %obj_0 = Feature(layout: ???) at ... + * %obj_1 = Feature(layout: BHWC) at ... + * %obj_2 = Feature(layout: BHWC) at ... + * + * copy(from: %obj_0, into: %obj_1) + * copy(from: %obj_0, into: %obj_2) + * + * ... + * Use(%obj_1) + * Use(%obj_2) + * ... + * + * >>> AFTER <<< + * %obj_0 = Feature(layout: ???) at ... + * %obj_1 = Feature(layout: BHWC) at ... + * %obj_2 = Feature(layout: BHWC) at ... + * + * copy(from: %obj_0, into: %obj_1) + * copy(from: %obj_0, into: %obj_2) + * + * ... + * Use(%obj_1) + * Use(%obj_1) <-- CHANGED + * ... + * + * NOTE Given a set of feature objects, a feature object referred to as a dominating + * feature object if its producer proceeds the producer of every feature object + * in the given set + */ +void reduce_duplicated_object(enco::Code *code); + +struct DuplicatedObjectReductionPass final : public Pass +{ + PASS_CTOR(DuplicatedObjectReductionPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { reduce_duplicated_object(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_DUPLICATED_OBJECT_REDUCTION_H__ diff --git a/compiler/enco/core/src/Transforms/FeatureUnification.cpp b/compiler/enco/core/src/Transforms/FeatureUnification.cpp new file mode 100644 index 000000000..1a7a0a8a4 --- /dev/null +++ b/compiler/enco/core/src/Transforms/FeatureUnification.cpp @@ -0,0 +1,216 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "FeatureUnification.h" +#include "IRUtils.h" + +#include <stdex/Memory.h> + +#include <set> +#include <vector> + +#include <cassert> + +using stdex::make_unique; + +namespace +{ + +bool is_static_layout(const coco::FeatureLayout::ID *id) +{ + if (id == coco::FeatureLayouts::BHWC::uid()) + { + return true; + } + + if (id == coco::FeatureLayouts::BCHW::uid()) + { + return true; + } + + return false; +} + +bool is_static_layout(const coco::FeatureLayout *l) { return is_static_layout(l->id()); } +bool is_static_layout(const coco::FeatureObject *f) { return is_static_layout(f->layout()); } + +/** + * @brief Return ture if a given 'feature' is the candidate of unification + */ +bool candidate(const coco::FeatureObject *f) { return is_static_layout(f); } + +/** + * @brief Return true if two features are compatible + * + * Two features are referred to as compatible if these feature are interchangeable. + * + * NOTE The current implementation of "compatible" is sound, but incomplete. + * + * Soundness: + * For all feature objects "lhs" and "rhs" that "compatible(lhs, rhs)" returns true, + * "lhs" and "rhs" are interchangeable. + * + * Completeness: + * For all interchangeable feature objects "lhs" and "rhs", "compatible(lhs, rhs)" returns true. + */ +bool compatible(const coco::FeatureObject *lhs, const coco::FeatureObject *rhs) +{ + assert(candidate(lhs) && candidate(rhs)); + + if (lhs->layout()->id() != rhs->layout()->id()) + { + return false; + } + + if (lhs->layout()->batch() != rhs->layout()->batch()) + { + return false; + } + + if (!(lhs->layout()->shape() == rhs->layout()->shape())) + { + return false; + } + + return true; +} + +/** + * @brief A FeatureGroup denotes a group of FeatureObject(s) + * + * Each FeatureGroup includes at most 1 DEF FeatureObject (a FeatureObject that has a producer), + * and may include multiple USE FeatureObject(s) (a FeatureObject that has no producer). + * + * NOTE FeatureUnification pass internally uses this FeatureGroup to store a group of compatible + * FeatureObject(s) + */ +class FeatureGroup +{ +public: + explicit FeatureGroup(coco::FeatureObject *feature) { insert(feature); } + +public: + uint32_t size(void) const { return _uses.size() + (_def ? 1 : 0); } + +public: + void insert(coco::FeatureObject *feature) + { + if (feature->def() != nullptr) + { + assert(_def == nullptr); + _def = feature; + } + else + { + _uses.insert(feature); + } + } + +public: + coco::FeatureObject *parent(void) const + { + if (_def) + { + return _def; + } + + assert(_uses.size() > 0); + return *(_uses.begin()); + } + +public: + std::set<coco::FeatureObject *> children(void) const + { + auto res = _uses; + res.erase(parent()); + return res; + } + +private: + coco::FeatureObject *_def = nullptr; + std::set<coco::FeatureObject *> _uses; +}; + +} // namespace + +namespace enco +{ + +void unify_feature(enco::Code *code) +{ + auto m = code->module(); + + for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n) + { + std::vector<std::unique_ptr<FeatureGroup>> groups; + + auto assign_group = [&](coco::FeatureObject *feature) { + // Find a compatible FeatureGroup + FeatureGroup *group = nullptr; + + for (const auto &g : groups) + { + FeatureGroup *candidate = g.get(); + + if (!compatible(candidate->parent(), feature)) + { + continue; + } + + group = candidate; + break; + } + + if (group == nullptr) + { + // Insert FeatureObject into a new FeatureGroup + groups.emplace_back(make_unique<FeatureGroup>(feature)); + } + else + { + // Insert FeatureObject into the compatible FeatureGroup + group->insert(feature); + } + }; + + auto bag = m->entity()->bag()->at(n); + + for (auto o : coco::dependent_objects(bag)) + { + if (auto feature = o->asFeature()) + { + if (candidate(feature)) + { + assign_group(feature); + } + } + } + + for (const auto &g : groups) + { + auto group = g.get(); + for (const auto child : group->children()) + { + subst(child, group->parent()); + assert(child->def() == nullptr); + assert(child->uses()->size() == 0); + m->entity()->object()->destroy(child); + } + } + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/FeatureUnification.h b/compiler/enco/core/src/Transforms/FeatureUnification.h new file mode 100644 index 000000000..5ab0f9d7a --- /dev/null +++ b/compiler/enco/core/src/Transforms/FeatureUnification.h @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_FEATURE_UNIFICATION_H__ +#define __ENCO_TRANSFORM_FEATURE_UNIFICATION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Remove duplicated feature objects inside each bag + * + * >>> BEFORE <<< + * %b = Bag(...) + * + * %feature_0 = Feature(...) at %b + * %feature_1 = Feature(...) at %b + * + * ... + * Use(%feature_0) + * ... + * Use(%feature_1) + * ... + * + * >>> AFTER <<< + * %b = Bag(...) + * + * %feature_0 = Feature(...) at %b + * ~~%feature_1 = Feature(...) at %b~~ <- REMOVED + * + * ... + * Use(%feature_0) + * ... + * Use(%feature_0) + * ... + * + * Note that all the occurrences of "%feature_1" are replaced with "%feature_0" + */ +void unify_feature(enco::Code *code); + +struct FeatureUnificationPass final : public Pass +{ + PASS_CTOR(FeatureUnificationPass) + { + // DO NOTHING + } + void run(const SessionID &sess) const override { unify_feature(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_FEATURE_UNIFICATION_H__ diff --git a/compiler/enco/core/src/Transforms/FreeInstrElimination.cpp b/compiler/enco/core/src/Transforms/FreeInstrElimination.cpp new file mode 100644 index 000000000..a62324b28 --- /dev/null +++ b/compiler/enco/core/src/Transforms/FreeInstrElimination.cpp @@ -0,0 +1,65 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "FreeInstrElimination.h" + +#include <cassert> +#include <set> + +namespace +{ + +/** + * @brief Return the set of "free" instructions in a given module + */ +std::set<coco::Instr *> free_instrs(const coco::Module *m) +{ + std::set<coco::Instr *> res; + + for (uint32_t n = 0; n < m->entity()->instr()->size(); ++n) + { + if (auto ins = m->entity()->instr()->at(n)) + { + if (ins->parent() == nullptr) + { + res.insert(ins); + } + } + } + + return res; +} + +void destroy(coco::Instr *ins) +{ + auto m = ins->module(); + m->entity()->instr()->destroy(ins); +} + +} // namespace + +namespace enco +{ + +void eliminate_free_instr(coco::Module *m) +{ + for (auto ins : free_instrs(m)) + { + destroy(ins); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/FreeInstrElimination.h b/compiler/enco/core/src/Transforms/FreeInstrElimination.h new file mode 100644 index 000000000..1d311cd35 --- /dev/null +++ b/compiler/enco/core/src/Transforms/FreeInstrElimination.h @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_FREE_INSTR_ELIMINATION_H__ +#define __ENCO_TRANSFORM_FREE_INSTR_ELIMINATION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Eliminate free instructions + * + * An instruction is referred to as "free" if it is not bound to any "block" + */ +void eliminate_free_instr(coco::Module *mod); + +/** + * @brief Eliminate free instructions + */ +static inline void eliminate_free_instr(enco::Code *code) +{ + // This function is just a wrapper of the above "void eliminate_free_instr(coco::Module *mod)" + eliminate_free_instr(code->module()); +} + +struct FreeInstrEliminationPass final : public Pass +{ + PASS_CTOR(FreeInstrEliminationPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { eliminate_free_instr(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_FREE_INSTR_ELIMINATION_H__ diff --git a/compiler/enco/core/src/Transforms/FreeInstrElimination.test.cpp b/compiler/enco/core/src/Transforms/FreeInstrElimination.test.cpp new file mode 100644 index 000000000..c15f32e7d --- /dev/null +++ b/compiler/enco/core/src/Transforms/FreeInstrElimination.test.cpp @@ -0,0 +1,34 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "FreeInstrElimination.h" + +#include <gtest/gtest.h> + +TEST(FreeInstrEliminationTest, case_000) +{ + auto m = coco::Module::create(); + + // Create a "free" Eval instruction + m->entity()->instr()->create<coco::Eval>(); + + ASSERT_EQ(m->entity()->instr()->size(), 1); + + // Apply "Free Instruction Elimination" + enco::eliminate_free_instr(m.get()); + + ASSERT_EQ(m->entity()->instr()->size(), 0); +} diff --git a/compiler/enco/core/src/Transforms/FreeOpElimination.cpp b/compiler/enco/core/src/Transforms/FreeOpElimination.cpp new file mode 100644 index 000000000..25f2f44d0 --- /dev/null +++ b/compiler/enco/core/src/Transforms/FreeOpElimination.cpp @@ -0,0 +1,59 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "FreeOpElimination.h" + +#include <cassert> +#include <set> + +namespace +{ + +/** + * @brief Return the set of Free Op Elimination candidates + */ +std::set<coco::Op *> candidates(const coco::Module *m) +{ + std::set<coco::Op *> res; + + for (uint32_t n = 0; n < m->entity()->op()->size(); ++n) + { + if (auto op = m->entity()->op()->at(n)) + { + if ((op->parent() == nullptr) && (op->up() == nullptr)) + { + res.insert(op); + } + } + } + + return res; +} + +} // namespace + +namespace enco +{ + +void eliminate_free_op(coco::Module *m) +{ + for (auto op : candidates(m)) + { + m->entity()->op()->destroy_all(op); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/FreeOpElimination.h b/compiler/enco/core/src/Transforms/FreeOpElimination.h new file mode 100644 index 000000000..3aeacada5 --- /dev/null +++ b/compiler/enco/core/src/Transforms/FreeOpElimination.h @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_FREE_OP_ELIMINATION_H__ +#define __ENCO_TRANSFORM_FREE_OP_ELIMINATION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Eliminate free op + * + * An op is referred to as "free" if it is not bound to any "instruction" + */ +void eliminate_free_op(coco::Module *mod); + +/** + * @brief Eliminate free op + */ +static inline void eliminate_free_op(enco::Code *code) +{ + // This function is just a wrapper of the above "void eliminate_free_op(coco::Module *mod)" + eliminate_free_op(code->module()); +} + +struct FreeOpEliminationPass final : public Pass +{ + PASS_CTOR(FreeOpEliminationPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { eliminate_free_op(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_FREE_OP_ELIMINATION_H__ diff --git a/compiler/enco/core/src/Transforms/FreeOpElimination.test.cpp b/compiler/enco/core/src/Transforms/FreeOpElimination.test.cpp new file mode 100644 index 000000000..41600526b --- /dev/null +++ b/compiler/enco/core/src/Transforms/FreeOpElimination.test.cpp @@ -0,0 +1,34 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "FreeOpElimination.h" + +#include <gtest/gtest.h> + +TEST(FreeOpEliminationTest, case_000) +{ + auto m = coco::Module::create(); + + // Create a "free" Load op + m->entity()->op()->create<coco::Load>(); + + ASSERT_EQ(m->entity()->op()->size(), 1); + + // Apply "Free Op Elimination" + enco::eliminate_free_op(m.get()); + + ASSERT_EQ(m->entity()->op()->size(), 0); +} diff --git a/compiler/enco/core/src/Transforms/GlobalDataGeneration.cpp b/compiler/enco/core/src/Transforms/GlobalDataGeneration.cpp new file mode 100644 index 000000000..152477a51 --- /dev/null +++ b/compiler/enco/core/src/Transforms/GlobalDataGeneration.cpp @@ -0,0 +1,181 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "GlobalDataGeneration.h" +#include "Split.h" +#include "Dims.h" + +#include <stdex/Memory.h> + +#include <map> + +using stdex::make_unique; + +namespace +{ + +/** + * @brief Manage global variable declarations + */ +class Global +{ +public: + Global(std::ostream &os) : _os(os) + { + // DO NOTHING + } + +public: + /// @brief Create a global constant string (const char *) literal, and return variable name + enco::GlobalOffset constant(const std::string &value); + + /// @brief Create a global constant array variable of type T + template <typename T> enco::GlobalOffset constant(const std::vector<T> &values); + + /// @brief Create a global constant array variable of byte (uint8_t) type + enco::GlobalOffset constant(const uint8_t *base, uint32_t size); + +private: + uint32_t _offset = 0; + std::ostream &_os; +}; + +enco::GlobalOffset Global::constant(const std::string &s) +{ + auto const base = reinterpret_cast<const uint8_t *>(s.c_str()); + auto const size = s.size() + 1 /* NUL */; + return constant(base, size); +} + +template <> enco::GlobalOffset Global::constant(const std::vector<uint32_t> &values) +{ + auto const base = reinterpret_cast<const uint8_t *>(values.data()); + auto const size = sizeof(uint32_t) * values.size(); + return constant(base, size); +} + +enco::GlobalOffset Global::constant(const uint8_t *base, uint32_t size) +{ + auto pos = _os.tellp(); + assert(pos != -1); + + _os.write(reinterpret_cast<const char *>(base), size); + + return static_cast<enco::GlobalOffset>(pos); +} + +} // namespace + +namespace +{ + +std::map<const ann::Operand *, enco::GlobalOffset> data_offset_ctx; +std::map<const coco::Bag *, enco::GlobalOffset> bag_data_offset_ctx; + +std::map<const coco::Arg *, enco::GlobalOffset> name_offset_ctx; +std::map<const coco::Arg *, enco::GlobalOffset> dims_offset_ctx; + +} // namespace + +namespace enco +{ + +GlobalOffset GlobalData::data_offset(const ann::Operand *o) { return data_offset_ctx.at(o); } + +GlobalOffset GlobalData::data_offset(const coco::Bag *bag) +{ + assert(bag_data_offset_ctx.find(bag) != bag_data_offset_ctx.end()); + return bag_data_offset_ctx.at(bag); +} + +GlobalOffset GlobalData::name_offset(const coco::Input *in) { return name_offset_ctx.at(in); } +GlobalOffset GlobalData::dims_offset(const coco::Input *in) { return dims_offset_ctx.at(in); } + +GlobalOffset GlobalData::name_offset(const coco::Output *out) { return name_offset_ctx.at(out); } +GlobalOffset GlobalData::dims_offset(const coco::Output *out) { return dims_offset_ctx.at(out); } + +void generate_global_data(std::ostream &os, enco::Code *code) +{ + auto m = code->module(); + auto d = code->data(); + + auto ann_ctx = enco::SubnetManager::context(m); + + auto global = make_unique<Global>(os); + + // + // Emit Bag's weight + // + for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n) + { + auto bag = m->entity()->bag()->at(n); + + if (!d->allocated(bag)) + { + // Skip if the weight value does not exist for a given bag + continue; + } + + // NOTE The current implementation assumes that all the values are of float(fp32) type + // TODO Support non-float values + auto span = d->f32()->weight(bag); + + assert(span.data() != nullptr); + assert(span.size() > 0); + + auto const base = reinterpret_cast<const uint8_t *>(span.data()); + uint32_t const size = span.size() * sizeof(float); + + assert(bag_data_offset_ctx.find(bag) == bag_data_offset_ctx.end()); + bag_data_offset_ctx[bag] = global->constant(base, size); + } + + for (uint32_t n = 0; n < ann_ctx->count(); ++n) + { + auto binder = ann_ctx->nth(n); + + auto emit = [&](const ann::OperandID & /*id*/, const ann::Operand *info) { + if (info->weight()) + { + auto base = info->weight()->base(); + auto size = info->weight()->size(); + + data_offset_ctx[info] = global->constant(base, size); + } + }; + binder->module()->operand()->each(emit); + } + + for (uint32_t n = 0; n < m->input()->size(); ++n) + { + auto input = m->input()->at(n); + auto dims = as_dims(input->shape()); + + name_offset_ctx[input] = global->constant(input->name()); + dims_offset_ctx[input] = global->constant<uint32_t>(dims); + } + + for (uint32_t n = 0; n < m->output()->size(); ++n) + { + auto output = m->output()->at(n); + auto dims = as_dims(output->shape()); + + name_offset_ctx[output] = global->constant(output->name()); + dims_offset_ctx[output] = global->constant<uint32_t>(dims); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/GlobalDataGeneration.h b/compiler/enco/core/src/Transforms/GlobalDataGeneration.h new file mode 100644 index 000000000..433431401 --- /dev/null +++ b/compiler/enco/core/src/Transforms/GlobalDataGeneration.h @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_GLOBAL_DATA_GENERATION_H__ +#define __ENCO_TRANSFORM_GLOBAL_DATA_GENERATION_H__ + +#include "Code.h" + +#include <ostream> + +namespace enco +{ + +using GlobalOffset = uint32_t; + +struct GlobalData +{ + static GlobalOffset data_offset(const ann::Operand *); + /** + * @brief Return the weight offset of a given bag + * + * @note The behavior of "data_offset" is undefined if a bag has no weight. + */ + static GlobalOffset data_offset(const coco::Bag *); + + static GlobalOffset name_offset(const coco::Input *); + static GlobalOffset dims_offset(const coco::Input *); + static GlobalOffset name_offset(const coco::Output *); + static GlobalOffset dims_offset(const coco::Output *); +}; + +/** + * @brief Generate 'Global' weight array. + * + * NOTE Succeeding passes can access offsets via "GlobalData" + */ +void generate_global_data(std::ostream &, enco::Code *); + +} // namespace enco + +#endif // __ENCO_TRANSFORM_GLOBAL_DATA_GENERATION_H__ diff --git a/compiler/enco/core/src/Transforms/IdenticalObjectReduction.cpp b/compiler/enco/core/src/Transforms/IdenticalObjectReduction.cpp new file mode 100644 index 000000000..cb996d2ac --- /dev/null +++ b/compiler/enco/core/src/Transforms/IdenticalObjectReduction.cpp @@ -0,0 +1,139 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "IdenticalObjectReduction.h" +#include "IRUtils.h" + +#include <set> + +namespace enco +{ + +void reduce_identical_object(enco::Code *code) +{ + auto m = code->module(); + + std::set<coco::Copy *> detached; + + // Preceding optimizations may generate "free" instructions. + // - i.e. an instruction not linked to a block + // + // Let's iterate over only a sequence of "bounded" instructions. + for (auto ins : instr_sequence(m)) + { + assert(ins != nullptr); + assert(ins->parent() != nullptr); + + auto copy = ins->asCopy(); + + if (copy == nullptr) + { + // Skip if instruction is not a copy + continue; + } + + // TODO Support non-Feature Objects + auto ifm = copy->from()->asFeature(); + auto ofm = copy->into()->asFeature(); + + assert(ofm->bag() != nullptr); + + if (ifm->layout()->id() != ofm->layout()->id()) + { + continue; + } + + if (ifm->layout()->id() != coco::FeatureLayouts::BHWC::uid()) + { + continue; + } + + // Skip if this copy produces network output + if (ofm->bag()->output()) + { + // TODO Optimize this case + // + // Note that the code under optimization is of the following form: + // + // %ifm <- Instr(...) + // %ofm <- Copy(%ifm) + // + // Let's assume that "Copy" is the only reader of %ifm (to be precise, its bag). + // + // Then, it is possible to rewrite the above fragment as follows: + // + // %ofm <- Instr(...) + // + continue; + } + + if (ofm->bag()->reads()->size() > 0) + { + // Let us consider the following code: + // + // Bag: + // %bag_0 = Bag(...) + // %bag_1 = Bag(...) + // %bag_2 = Bag(...) + // + // Object: + // %obj_0 = FeatureObject(bag: %bag_0) + // %obj_1 = FeatureObject(bag: %bag_1) + // + // Instr: + // copy an object from %obj_0 into %obj_1 + // shuffle values from %bag_1 into %bag_2 + // eval Conv2D with %obj_1 + // + // Identical Object Reduction (IOR) tries to eliminate the first copy via + // substitution (substitute all the occurrence of %obj_1 as use with %obj_0). + // + // Here is the code transformed by IOR: + // + // Bag: + // %bag_0 = Bag(...) + // %bag_1 = Bag(...) + // %bag_2 = Bag(...) + // + // Object: + // %obj_0 = FeatureObject(bag: %bag_0) + // %obj_1 = FeatureObject(bag: %bag_1) + // + // Instr: + // shuffle values from %bag_1 into %bag_2 + // eval Conv2D with %obj_0 + // + // Note that there is no updater of %bag_1 after IOR, and thus the behavior + // of the first shuffle instruction has changed. + // + // This examples shows that it is impossible to simply substitute %obj_1 + // with %obj_0 in the presence of readers over its backing bag. + continue; + } + + subst(copy->into(), copy->from()); + + copy->detach(); + detached.insert(copy); + } + + for (auto copy : detached) + { + m->entity()->instr()->destroy(copy); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/IdenticalObjectReduction.h b/compiler/enco/core/src/Transforms/IdenticalObjectReduction.h new file mode 100644 index 000000000..b5bb25d7c --- /dev/null +++ b/compiler/enco/core/src/Transforms/IdenticalObjectReduction.h @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_IDENTICAL_OBJECT_REDUCTION_H__ +#define __ENCO_TRANSFORM_IDENTICAL_OBJECT_REDUCTION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Reduce identically copied objects as its original object + * + * >>> BEFORE <<< + * %bag_0 = Bag(size: N) + * %bag_1 = Bag(size: N) + * + * %obj_0 = Feature(layout: BHWC) at %bag_0 + * %obj_1 = Feature(layout: BHWC) at %bag_1 + * + * copy(from: %obj_0, into: %obj_1) + * ... + * Use(%obj_0) + * Use(%obj_1) + * ... + * + * >>> AFTER <<< + * %bag_0 = Bag(size: N) + * %bag_1 = Bag(size: N) + * + * %obj_0 = Feature(layout: BHWC) at %bag_0 + * %obj_1 = Feature(layout: BHWC) at %bag_1 + * + * copy(from: %obj_0, into: %obj_1) + * ... + * Use(%obj_0) + * Use(%obj_0) <- %obj_1 is replaced + * ... + */ +void reduce_identical_object(enco::Code *code); + +struct IdenticalObjectReductionPass final : public Pass +{ + PASS_CTOR(IdenticalObjectReductionPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { reduce_identical_object(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_IDENTICAL_OBJECT_REDUCTION_H__ diff --git a/compiler/enco/core/src/Transforms/IdenticalObjectReduction.test.cpp b/compiler/enco/core/src/Transforms/IdenticalObjectReduction.test.cpp new file mode 100644 index 000000000..772bea08e --- /dev/null +++ b/compiler/enco/core/src/Transforms/IdenticalObjectReduction.test.cpp @@ -0,0 +1,32 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "IdenticalObjectReduction.h" + +#include <gtest/gtest.h> + +TEST(IdenticalObjectReductionTest, case_000) +{ + auto m = coco::Module::create(); + + // Create a "free" Eval instruction + m->entity()->instr()->create<coco::Eval>(); + + enco::Code code{m.get(), nullptr}; + + // NOTE This code SHOULD NOT crash + enco::reduce_identical_object(&code); +} diff --git a/compiler/enco/core/src/Transforms/IndirectCopyElimination.cpp b/compiler/enco/core/src/Transforms/IndirectCopyElimination.cpp new file mode 100644 index 000000000..b36620f61 --- /dev/null +++ b/compiler/enco/core/src/Transforms/IndirectCopyElimination.cpp @@ -0,0 +1,84 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "IndirectCopyElimination.h" + +#include <cassert> + +namespace +{ + +coco::Copy *as_copy(coco::Instr *ins) { return ins ? ins->asCopy() : nullptr; } + +/** + * @brief Return a set of copy instructions that are accessible from top-level module + */ +std::set<coco::Copy *> linked_copy_instrs(coco::Module *m) +{ + std::set<coco::Copy *> res; + + for (uint32_t n = 0; n < m->entity()->instr()->size(); ++n) + { + auto ins = m->entity()->instr()->at(n); + assert(ins != nullptr); + + if (ins->parent() && ins->parent()->parent()) + { + if (auto copy = ins->asCopy()) + { + res.insert(copy); + } + } + } + + return res; +} + +} // namespace + +namespace enco +{ + +void eliminate_indirect_copy(enco::Code *code) +{ + auto m = code->module(); + + for (auto child : linked_copy_instrs(m)) + { + auto from = child->from(); + assert(from != nullptr); + + // Find the irreducible origin + while (true) + { + if (auto producer = coco::producer(from)) + { + if (auto parent = as_copy(producer->loc())) + { + assert(parent->from() != nullptr); + from = parent->from(); + continue; + } + } + + break; + } + + child->from(from); + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/IndirectCopyElimination.h b/compiler/enco/core/src/Transforms/IndirectCopyElimination.h new file mode 100644 index 000000000..acfdf569b --- /dev/null +++ b/compiler/enco/core/src/Transforms/IndirectCopyElimination.h @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_TRANSFORM_INDIRECT_COPY_ELIMINATION_H__ +#define __ENCO_TRANSFORM_INDIRECT_COPY_ELIMINATION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Convert all the indirect copies as a direct copy + * + * >>> BEFORE <<< + * %obj_0 = ... + * %obj_1 = ... + * %obj_2 = ... + * + * copy(from: %obj_0, into: %obj_1) + * copy(from: %obj_1, into: %obj_2) + * + * >>> AFTER <<< + * %obj_0 = ... + * %obj_1 = ... + * %obj_2 = ... + * + * copy(from: %obj_0, into: %obj_1) + * copy(from: %obj_0, into: %obj_2) + * + */ +void eliminate_indirect_copy(enco::Code *code); + +struct IndirectCopyEliminationPass final : public enco::Pass +{ + PASS_CTOR(IndirectCopyEliminationPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { eliminate_indirect_copy(code(sess)); } +}; + +} // namespace enco + +#endif // __ENCO_TRANSFORM_INDIRECT_COPY_ELIMINATION_H__ diff --git a/compiler/enco/core/src/Transforms/IntrinsicSelection.cpp b/compiler/enco/core/src/Transforms/IntrinsicSelection.cpp new file mode 100644 index 000000000..7bf1c4926 --- /dev/null +++ b/compiler/enco/core/src/Transforms/IntrinsicSelection.cpp @@ -0,0 +1,100 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "IntrinsicSelection.h" + +#include "coex/IR.h" + +namespace +{ + +/** + * @brief Return a backend-speicific coco (extend) instruction + * + * @note rewrite(ins) returns nullptr if selection fails + */ +coco::Instr *rewrite(coco::Instr *curr) +{ + auto m = curr->module(); + assert(m != nullptr); + + if (auto eval = coco::safe_cast<coco::Eval>(curr)) + { + if (auto concat_f = eval->op()->asConcatF()) + { + auto fst_load = concat_f->left()->asLoad(); + auto snd_load = concat_f->right()->asLoad(); + + if (fst_load && snd_load && (concat_f->axis() == coco::ConcatF::Axis::Depth)) + { + // Here is the pattern of interest + // + // %ofm = eval(ConcatF(Depth, Load(%left), Load(%right))) + // + auto fst_feature = fst_load->object()->asFeature(); + auto snd_feature = snd_load->object()->asFeature(); + assert((fst_feature != nullptr) && (snd_feature != nullptr)); + + auto out_feature = eval->out()->asFeature(); + assert(out_feature != nullptr); + + eval->out(nullptr); + + auto depth_concat = m->entity()->instr()->create<ANNDepthConcatF>(); + + depth_concat->out(out_feature); + depth_concat->fst(fst_feature); + depth_concat->snd(snd_feature); + + return depth_concat; + } + + return nullptr; + } + } + + return nullptr; +} + +} // namespace + +namespace enco +{ + +void select_intrinsic(enco::Code *code) +{ + auto m = code->module(); + + for (auto blk = m->block()->head(); blk; blk = blk->next()) + { + auto ins = blk->instr()->head(); + + while (ins) + { + if (auto rewritten_ins = rewrite(ins)) + { + rewritten_ins->insertBefore(ins); + ins->detach(); + + ins = rewritten_ins; + } + + ins = ins->next(); + } + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/IntrinsicSelection.h b/compiler/enco/core/src/Transforms/IntrinsicSelection.h new file mode 100644 index 000000000..67d38eaeb --- /dev/null +++ b/compiler/enco/core/src/Transforms/IntrinsicSelection.h @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __INTRINSIC_SELECTION_H__ +#define __INTRINSIC_SELECTION_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Select Intricsic (API) to be used + * + * This pass is analogue of "Instruction Selection" pass. This "Intrisic Selection" pass + * will replace a general coco IR instruction into a backend-specific coco (extended) IR + * instruction. + */ +void select_intrinsic(enco::Code *); + +struct IntrinsicSelectionPass final : public Pass +{ + PASS_CTOR(IntrinsicSelectionPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { select_intrinsic(code(sess)); } +}; + +} // namespace enco + +#endif // __INTRINSIC_SELECTION_H__ diff --git a/compiler/enco/core/src/Transforms/Optimizations.cpp b/compiler/enco/core/src/Transforms/Optimizations.cpp new file mode 100644 index 000000000..7f0974dd0 --- /dev/null +++ b/compiler/enco/core/src/Transforms/Optimizations.cpp @@ -0,0 +1,257 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Optimizations.h" +#include "CodeIndex.h" + +#include <cassert> + +namespace enco +{ + +void generate_bypass_shuffle(enco::Code *code) +{ + auto m = code->module(); + + for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n) + { + auto bag = m->entity()->bag()->at(n); + + // NOTE The current implementation assumes that all the updates occurs before the first read + // TODO Remove this assumption + for (auto u : coco::updaters(bag)) + { + if ((u->loc() == nullptr) || (u->loc()->asShuffle() == nullptr)) + { + // Skip if updater is not a Shuffle instruction + continue; + } + + for (auto r : coco::readers(bag)) + { + if ((r->loc() == nullptr) || (r->loc()->asShuffle() == nullptr)) + { + // Skip if reader is not a Shuffle instruction + continue; + } + + auto shuffle_1 = u->loc()->asShuffle(); + auto shuffle_2 = r->loc()->asShuffle(); + + // Construct a shuffle instruction + auto shuffle_3 = m->entity()->instr()->create<coco::Shuffle>(); + + shuffle_3->from(shuffle_1->from()); + shuffle_3->into(shuffle_2->into()); + + // Attempt to construct a valid bypass shuffle instruction + bool valid = true; + + for (const auto &C : shuffle_2->range()) + { + auto B = shuffle_2->at(C); + + if (!shuffle_1->defined(B)) + { + valid = false; + break; + } + + auto A = shuffle_1->at(B); + + shuffle_3->insert(A, C); + } + + if (valid) + { + // Insert shuffle_3 before shuffle_2 if shuffle_3 is a valid bypass of shuffle_2 + shuffle_3->insertBefore(shuffle_2); + + // NOTE shuffle_2 SHOULD BE detached and destroyed after shuffle_3 is inserted + shuffle_2->detach(); + m->entity()->instr()->destroy(shuffle_2); + } + else + { + // Destroy shuffle_3 (bypass shuffle) if it is invalid + m->entity()->instr()->destroy(shuffle_3); + } + } + } + } +} + +} // namespace enco + +// +// Hoist Object +// +namespace +{ + +bool hoistable(const coco::Shuffle *shuffle) +{ + auto range = shuffle->range(); + + if (range.size() != shuffle->into()->size()) + { + return false; + } + + for (const auto &dst : range) + { + if (shuffle->at(dst).value() != dst.value()) + { + return false; + } + } + + return true; +} + +bool complete(const coco::Shuffle *s) { return s->range().size() == s->into()->size(); } + +bool compatible(const coco::Shuffle *s1, const coco::Shuffle *s2) +{ + if (s1->from() != s2->from()) + { + return false; + } + + if (s1->into()->size() != s2->into()->size()) + { + return false; + } + + auto range_1 = s1->range(); + auto range_2 = s2->range(); + + if (range_1.size() != range_2.size()) + { + return false; + } + + bool res = true; + + for (const auto &dst : range_2) + { + if (!s1->defined(dst)) + { + res = false; + break; + } + + auto src_1 = s1->at(dst); + auto src_2 = s2->at(dst); + + if (src_1.value() != src_2.value()) + { + res = false; + break; + } + } + + return res; +} + +} // namespace + +namespace enco +{ + +void hoist_object(enco::Code *code) +{ + auto m = code->module(); + + // + // Case 1 + // + for (uint32_t n = 0; n < m->entity()->instr()->size(); ++n) + { + if (auto shuffle = m->entity()->instr()->at(n)->asShuffle()) + { + if (shuffle->parent() == nullptr) + { + continue; + } + + if (hoistable(shuffle)) + { + auto from = shuffle->from(); + auto into = shuffle->into(); + + into->replaceAllDepsWith(from); + } + } + } + + // + // Case 2 + // + for (uint32_t n = 0; n < m->entity()->bag()->size(); ++n) + { + auto bag = m->entity()->bag()->at(n); + + std::map<CodeIndex, coco::Shuffle *> collected; + + for (auto reader : coco::readers(bag)) + { + if (auto ins = reader->loc()) + { + if (auto shuffle = ins->asShuffle()) + { + collected[code_index(shuffle)] = shuffle; + } + } + } + + std::vector<coco::Shuffle *> sorted; + + for (auto it = collected.begin(); it != collected.end(); ++it) + { + sorted.emplace_back(it->second); + } + + for (uint32_t curr = 0; curr < sorted.size(); ++curr) + { + auto const curr_ins = sorted.at(curr); + auto const curr_bag = curr_ins->into(); + + if (!complete(curr_ins)) + { + continue; + } + + for (uint32_t next = curr + 1; next < sorted.size(); ++next) + { + auto const next_ins = sorted.at(next); + auto const next_bag = next_ins->into(); + + if (!complete(next_ins)) + { + continue; + } + + if (compatible(curr_ins, next_ins)) + { + next_bag->replaceAllDepsWith(curr_bag); + } + } + } + } +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/Optimizations.h b/compiler/enco/core/src/Transforms/Optimizations.h new file mode 100644 index 000000000..7cfc2305c --- /dev/null +++ b/compiler/enco/core/src/Transforms/Optimizations.h @@ -0,0 +1,123 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __ENCO_OPTIMIZATIONS_H__ +#define __ENCO_OPTIMIZATIONS_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +/** + * @brief Add a bypass Shuffle if two continued Shuffles map same from-into + * + * %bag_1 = Bag(size: N) + * %bag_2 = Bag(size: N) + * %bag_3 = Bag(size: N) + * + * >>> BEFORE <<< + * Shuffle(from: %bag_1, into: %bag_2, [0 -> 0]) + * Shuffle(from: %bag_2, into: %bag_3, [0 -> 0]) + * + * Let's refer to the former shuffle as Shuffle 1 and the latter one as Shuffle 2. + * We can replace Shuffle 2 with new Shuffle 3 as follows when Shuffle 1 and + * Shuffle 2 map to the same position. + * + * >>> AFTER <<< + * Shuffle(from: %bag_1, into: %bag_2, [0 -> 0]) <- Shuffle 1 + * Shuffle(from: %bag_1, into: %bag_3, [0 -> 0]) <- Shuffle 3 + * + * Note that Shuffle 1 can be eliminated when %bag_2 is not used + */ +void generate_bypass_shuffle(enco::Code *code); + +struct BypassGenerationPass final : public Pass +{ + PASS_CTOR(BypassGenerationPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { generate_bypass_shuffle(code(sess)); } +}; + +/** + * @brief Update the base bag of each object if possible + * + * --- Case 1 --- + * Let us consider the following code: + * + * %bag_1 = Bag(size: 4) + * %bag_2 = Bag(size: 1) + * + * %obj_1 = ... at %bag_1 + * %obj_2 = ... at %bag_2 + * + * ... + * Shuffle(from: %bag_1, into: %bag_2, [0 -> 0]) <- shuffle + * ... + * + * Note that the content of %bag_2 after shuffle is identical to a part of %bag_1, so + * the following code is identical to the above code + * + * %bag_1 = Bag(size: 4) + * %bag_2 = Bag(size: 1) + * + * %obj_1 = ... at %bag_1 + * %obj_2 = ... at %bag_1 + * + * ... + * Shuffle(from: %bag_1, into: %bag_2, [0 -> 0]) + * ... + * + * --- Case 2 --- + * Let us consider the following code: + * + * %bag_1 = Bag(size: 4) + * %bag_2 = Bag(size: 1) + * %bag_3 = Bag(size: 1) + * + * %obj_1 = ... at %bag_2 + * %obj_2 = ... at %bag_3 + * + * Shuffle(from: %bag_1, into: %bag_2, [0 -> 0]) <- shuffle_1 + * Shuffle(from: %bag_1, into: %bag_3, [0 -> 0]) <- shuffle_2 + * + * Note that the content of %bag_3 after shuffle_2 is identical to that of %bag_2 after shuffle_1, + * so the following code is identical to the above one: + * + * %bag_1 = Bag(size: 4) + * %bag_2 = Bag(size: 1) + * %bag_3 = Bag(size: 1) + * + * %obj_1 = ... at %bag_2 + * %obj_2 = ... at %bag_2 <- HERE + * + * Shuffle(from: %bag_1, into: %bag_2, [0 -> 0]) <- shuffle_1 + * Shuffle(from: %bag_1, into: %bag_3, [0 -> 0]) <- shuffle_2 + * + * "hoist_object" optimization rewrites the former code as the latter one. + * + * NOTE "hoist_object" DOES NOT change any instruction. It just updates the base bag of objects of + * interest. + */ +void hoist_object(enco::Code *code); + +} // namespace enco + +#endif // __ENCO_OPTIMIZATIONS_H__ diff --git a/compiler/enco/core/src/Transforms/Split.cpp b/compiler/enco/core/src/Transforms/Split.cpp new file mode 100644 index 000000000..b57b8f882 --- /dev/null +++ b/compiler/enco/core/src/Transforms/Split.cpp @@ -0,0 +1,1233 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Split.h" +#include "Usage.h" +#include "Session.h" +#include "coex/IR.h" + +#include <coco/IR.h> + +#include <nncc/core/ADT/kernel/NHWCLayout.h> +#include <stdex/Memory.h> + +#include <map> +#include <stdexcept> +#include <functional> + +using stdex::make_unique; + +namespace +{ + +std::map<const coco::Module *, std::unique_ptr<ANNContext>> _subnet_contexts; + +} // namespace + +namespace enco +{ + +const ANNContext *SubnetManager::context(const coco::Module *m) +{ + return _subnet_contexts.at(m).get(); +} + +} // namespace enco + +namespace +{ + +using Appender = std::function<void(ANNBinder *binder)>; + +struct ANNOpAppender +{ + virtual ~ANNOpAppender() = default; + + virtual void append(ANNBinder *binder) const = 0; +}; + +class ANNAddAppender final : public ANNOpAppender +{ +public: + void left(coco::FeatureObject *o) { _left = o; } + void right(coco::FeatureObject *o) { _right = o; } + void out(coco::FeatureObject *o) { _out = o; } + +public: + void append(ANNBinder *binder) const override + { + auto left = binder->addOperand<float>(_left); + auto right = binder->addOperand<float>(_right); + auto fuse = binder->addOperand<int32_t>(); + binder->setOperand(fuse, 0); + + auto out = binder->addOperand<float>(_out); + + binder->addOperation(ann::Operation::Code::ADD, {left, right, fuse}, {out}); + } + +private: + coco::FeatureObject *_left = nullptr; + coco::FeatureObject *_right = nullptr; + coco::FeatureObject *_out = nullptr; +}; + +class ANNMulAppender final : public ANNOpAppender +{ +public: + void left(coco::FeatureObject *o) { _left = o; } + void right(coco::FeatureObject *o) { _right = o; } + void out(coco::FeatureObject *o) { _out = o; } + +public: + void append(ANNBinder *binder) const override + { + auto left = binder->addOperand<float>(_left); + auto right = binder->addOperand<float>(_right); + auto fuse = binder->addOperand<int32_t>(); + binder->setOperand(fuse, 0); + + auto out = binder->addOperand<float>(_out); + + binder->addOperation(ann::Operation::Code::MUL, {left, right, fuse}, {out}); + } + +private: + coco::FeatureObject *_left = nullptr; + coco::FeatureObject *_right = nullptr; + coco::FeatureObject *_out = nullptr; +}; + +/** + * WARN The current implementation supports concatenation along depth only + */ +class ANNConcatAppender final : public ANNOpAppender +{ +public: + void left(coco::FeatureObject *o) { _left = o; } + void right(coco::FeatureObject *o) { _right = o; } + void out(coco::FeatureObject *o) { _out = o; } + +public: + void append(ANNBinder *binder) const override + { + auto left = binder->addOperand<float>(_left); + auto right = binder->addOperand<float>(_right); + auto axis = binder->addOperand<int32_t>(); + binder->setOperand(axis, 3 /* DEPTH */); + + auto out = binder->addOperand<float>(_out); + + binder->addOperation(ann::Operation::Code::CONCAT, {left, right, axis}, {out}); + } + +private: + coco::FeatureObject *_left = nullptr; + coco::FeatureObject *_right = nullptr; + coco::FeatureObject *_out = nullptr; +}; + +class ANNConv2DAppender final : public ANNOpAppender +{ +public: + void session(const enco::SessionID &sess) { _sess = sess; } + + void pad(const coco::Padding2D *pad) { _pad = *pad; } + void stride(const coco::Stride2D *stride) { _stride = *stride; } + + void ifm(coco::FeatureObject *ifm) { _ifm = ifm; } + void ker(coco::KernelObject *ker) { _ker = ker; } + // Q: Should we take a bias as a feature object? + // NOTE This interface is subject to change + void bias(coco::FeatureObject *bias) { _bias = bias; } + void ofm(coco::FeatureObject *ofm) { _ofm = ofm; } + +public: + void append(ANNBinder *binder) const override + { + auto data = enco::data(_sess); + + auto ifm = binder->addOperand<float>(_ifm); + auto ker = binder->addOperand<float>(_ker); + + // Fill kernel data + { + auto ker_bag = _ker->bag(); + auto ker_weight = data->f32()->weight(ker_bag); + + assert(ker_weight.data() != nullptr); + + binder->setOperand(ker, ker_weight.data(), ker_weight.data() + ker_weight.size()); + } + + // Conv2D in coco IR has no bias, but bias is mandatory in Android NN API + auto bias = binder->addOperand<float>(nncc::core::ADT::tensor::Shape{_ker->shape().count()}); + + // Fill bias data + if (_bias == nullptr) + { + // Use a fresh empty bias if "bias" is not specified + auto length = _ker->shape().count(); + + std::vector<float> values; + values.resize(length, 0.0f); + + binder->setOperand(bias, values.begin(), values.end()); + } + else + { + // Use specified "bias" + auto bias_bag = _bias->bag(); + auto bias_weight = data->f32()->weight(bias_bag); + + assert(bias_weight.data() != nullptr); + assert(bias_weight.size() == _ker->shape().count()); + + binder->setOperand(bias, bias_weight.data(), bias_weight.data() + bias_weight.size()); + } + + auto left = binder->addOperand<int32_t>(); + binder->setOperand(left, _pad.left()); + auto right = binder->addOperand<int32_t>(); + binder->setOperand(right, _pad.right()); + auto top = binder->addOperand<int32_t>(); + binder->setOperand(top, _pad.top()); + auto bottom = binder->addOperand<int32_t>(); + binder->setOperand(bottom, _pad.bottom()); + auto hstride = binder->addOperand<int32_t>(); + binder->setOperand(hstride, _stride.horizontal()); + auto vstride = binder->addOperand<int32_t>(); + binder->setOperand(vstride, _stride.vertical()); + auto fuse = binder->addOperand<int32_t>(); + binder->setOperand(fuse, 0); + + auto ofm = binder->addOperand<float>(_ofm); + + binder->addOperation(ann::Operation::Code::CONV_2D, + {ifm, ker, bias, left, right, top, bottom, hstride, vstride, fuse}, {ofm}); + } + +private: + enco::SessionID _sess; + +private: + coco::Padding2D _pad; + coco::Stride2D _stride; + +private: + coco::FeatureObject *_ifm = nullptr; + coco::KernelObject *_ker = nullptr; + coco::FeatureObject *_bias = nullptr; + coco::FeatureObject *_ofm = nullptr; +}; + +class ANNDepthwiseConv2DAppender final : public ANNOpAppender +{ +public: + void session(const enco::SessionID &sess) { _sess = sess; } + + void multiplier(const uint32_t &multiplier) { _multiplier = multiplier; } + void pad(const coco::Padding2D *pad) { _pad = *pad; } + void stride(const coco::Stride2D *stride) { _stride = *stride; } + + void ifm(coco::FeatureObject *ifm) { _ifm = ifm; } + void ker(coco::KernelObject *ker) { _ker = ker; } + void ofm(coco::FeatureObject *ofm) { _ofm = ofm; } + +public: + void append(ANNBinder *binder) const override + { + using namespace nncc::core::ADT; + + auto data = enco::data(_sess); + + const uint32_t ker_N = _ker->shape().count(); + const uint32_t ker_H = _ker->shape().height(); + const uint32_t ker_W = _ker->shape().width(); + + assert(ker_N % _multiplier == 0); + const uint32_t group = ker_N / _multiplier; + + auto ifm = binder->addOperand<float>(_ifm); + auto ker = binder->addOperand<float>(tensor::Shape{1, ker_H, ker_W, ker_N}); + + // Fill kernel data + { + auto obj = _ker; + auto shape = obj->shape(); + + auto ovl = data->f32()->read(obj); + assert(ovl != nullptr); + + // Flatten? + std::vector<float> values; + + /** + * Android NN computes DEPTHWISE_CONV_2D as follows: + * + * output[b, i, j, k * channel_multiplier + q] = + * sum_{di, dj} ( + * input[b, strides[1] * i + di, strides[2] * j + dj, k] * + * filter[1, di, dj, k * channel_multiplier + q] + * ) + bias[k * channel_multiplier + q] + * + */ + for (uint32_t row = 0; row < shape.height(); ++row) + { + for (uint32_t col = 0; col < shape.width(); ++col) + { + for (uint32_t g = 0; g < group; ++g) + { + for (uint32_t m = 0; m < _multiplier; ++m) + { + const auto value = ovl->at(g * _multiplier + m, 0, row, col); + values.emplace_back(value); + } + } + } + } + + assert(values.size() == nncc::core::ADT::kernel::num_elements(shape)); + binder->setOperand(ker, values.begin(), values.end()); + } + + // Conv2D in coco IR has no bias, but bias is mandatory in Android NN API + auto bias = binder->addOperand<float>(nncc::core::ADT::tensor::Shape{_ker->shape().count()}); + + // Fill bias data + { + auto length = _ker->shape().count(); + + std::vector<float> values; + values.resize(length, 0.0f); + + binder->setOperand(bias, values.begin(), values.end()); + } + + auto left = binder->addOperand<int32_t>(); + binder->setOperand(left, _pad.left()); + auto right = binder->addOperand<int32_t>(); + binder->setOperand(right, _pad.right()); + auto top = binder->addOperand<int32_t>(); + binder->setOperand(top, _pad.top()); + auto bottom = binder->addOperand<int32_t>(); + binder->setOperand(bottom, _pad.bottom()); + auto hstride = binder->addOperand<int32_t>(); + binder->setOperand(hstride, _stride.horizontal()); + auto vstride = binder->addOperand<int32_t>(); + binder->setOperand(vstride, _stride.vertical()); + auto multiplier = binder->addOperand<int32_t>(); + binder->setOperand(multiplier, _multiplier); + auto fuse = binder->addOperand<int32_t>(); + binder->setOperand(fuse, 0); + + auto ofm = binder->addOperand<float>(_ofm); + + binder->addOperation( + ann::Operation::Code::DEPTHWISE_CONV_2D, + {ifm, ker, bias, left, right, top, bottom, hstride, vstride, multiplier, fuse}, {ofm}); + } + +private: + enco::SessionID _sess; + +private: + uint32_t _multiplier; + coco::Padding2D _pad; + coco::Stride2D _stride; + +private: + coco::FeatureObject *_ifm = nullptr; + coco::KernelObject *_ker = nullptr; + coco::FeatureObject *_ofm = nullptr; +}; + +class ANNReLUAppender final : public ANNOpAppender +{ +public: + void ifm(coco::FeatureObject *ifm) { _ifm = ifm; } + void ofm(coco::FeatureObject *ofm) { _ofm = ofm; } + +public: + void append(ANNBinder *binder) const override + { + auto ifm = binder->addOperand<float>(_ifm); + auto ofm = binder->addOperand<float>(_ofm); + + binder->addOperation(ann::Operation::Code::RELU, {ifm}, {ofm}); + } + +private: + coco::FeatureObject *_ifm = nullptr; + coco::FeatureObject *_ofm = nullptr; +}; + +class ANNReLU6Appender final : public ANNOpAppender +{ +public: + void ifm(coco::FeatureObject *ifm) { _ifm = ifm; } + void ofm(coco::FeatureObject *ofm) { _ofm = ofm; } + +public: + void append(ANNBinder *binder) const override + { + auto ifm = binder->addOperand<float>(_ifm); + auto ofm = binder->addOperand<float>(_ofm); + + binder->addOperation(ann::Operation::Code::RELU6, {ifm}, {ofm}); + } + +private: + coco::FeatureObject *_ifm = nullptr; + coco::FeatureObject *_ofm = nullptr; +}; + +class ANNMaxPool2DAppender final : public ANNOpAppender +{ +public: + void pad(const coco::Padding2D *pad) { _pad = *pad; } + void stride(const coco::Stride2D *stride) { _stride = *stride; } + void window(const coco::Window2D *window) { _window = *window; } + + void ifm(coco::FeatureObject *ifm) { _ifm = ifm; } + void ofm(coco::FeatureObject *ofm) { _ofm = ofm; } + +public: + void append(ANNBinder *binder) const override + { + auto ifm = binder->addOperand<float>(_ifm); + + // Set padding + auto left = binder->addOperand<int32_t>(); + binder->setOperand(left, _pad.left()); + auto right = binder->addOperand<int32_t>(); + binder->setOperand(right, _pad.right()); + auto top = binder->addOperand<int32_t>(); + binder->setOperand(top, _pad.top()); + auto bottom = binder->addOperand<int32_t>(); + binder->setOperand(bottom, _pad.bottom()); + + // Set horizontal/vertical stride + auto hstride = binder->addOperand<int32_t>(); + binder->setOperand(hstride, _stride.horizontal()); + auto vstride = binder->addOperand<int32_t>(); + binder->setOperand(vstride, _stride.vertical()); + + // Set receptive field size + auto width = binder->addOperand<int32_t>(); + binder->setOperand(width, _window.width()); + auto height = binder->addOperand<int32_t>(); + binder->setOperand(height, _window.height()); + + // Set fuse code + // TODO Suport operation fusion + auto fuse = binder->addOperand<int32_t>(); + binder->setOperand(fuse, 0); + + auto ofm = binder->addOperand<float>(_ofm); + + binder->addOperation(ann::Operation::Code::MAX_POOL_2D, + {ifm, left, right, top, bottom, hstride, vstride, width, height, fuse}, + {ofm}); + } + +private: + coco::Padding2D _pad; + coco::Stride2D _stride; + coco::Window2D _window; + +private: + coco::FeatureObject *_ifm = nullptr; + coco::FeatureObject *_ofm = nullptr; +}; + +class ANNAvgPool2DAppender final : public ANNOpAppender +{ +public: + void pad(const coco::Padding2D *pad) { _pad = *pad; } + void stride(const coco::Stride2D *stride) { _stride = *stride; } + void window(const coco::Window2D *window) { _window = *window; } + + void ifm(coco::FeatureObject *ifm) { _ifm = ifm; } + void ofm(coco::FeatureObject *ofm) { _ofm = ofm; } + +public: + void append(ANNBinder *binder) const override + { + auto ifm = binder->addOperand<float>(_ifm); + + // Set padding + auto left = binder->addOperand<int32_t>(); + binder->setOperand(left, _pad.left()); + auto right = binder->addOperand<int32_t>(); + binder->setOperand(right, _pad.right()); + auto top = binder->addOperand<int32_t>(); + binder->setOperand(top, _pad.top()); + auto bottom = binder->addOperand<int32_t>(); + binder->setOperand(bottom, _pad.bottom()); + + // Set horizontal/vertical stride + auto hstride = binder->addOperand<int32_t>(); + binder->setOperand(hstride, _stride.horizontal()); + auto vstride = binder->addOperand<int32_t>(); + binder->setOperand(vstride, _stride.vertical()); + + // Set receptive field size + auto width = binder->addOperand<int32_t>(); + binder->setOperand(width, _window.width()); + auto height = binder->addOperand<int32_t>(); + binder->setOperand(height, _window.height()); + + // Set fuse code + // TODO Suport operation fusion + auto fuse = binder->addOperand<int32_t>(); + binder->setOperand(fuse, 0); + + auto ofm = binder->addOperand<float>(_ofm); + + binder->addOperation(ann::Operation::Code::AVG_POOL_2D, + {ifm, left, right, top, bottom, hstride, vstride, width, height, fuse}, + {ofm}); + } + +private: + coco::Padding2D _pad; + coco::Stride2D _stride; + coco::Window2D _window; + +private: + coco::FeatureObject *_ifm = nullptr; + coco::FeatureObject *_ofm = nullptr; +}; + +class ANNPadFAppender final : public ANNOpAppender +{ +public: + void pad(const coco::Padding2D *pad) { _pad = *pad; } + +public: + void ifm(coco::FeatureObject *ifm) { _ifm = ifm; } + void ofm(coco::FeatureObject *ofm) { _ofm = ofm; } + +public: + void append(ANNBinder *binder) const override + { + using nncc::core::ADT::tensor::Shape; + + auto ifm = binder->addOperand<float>(_ifm); + auto pad = binder->addOperand<int32_t>(Shape{4, 2}); + { + std::vector<int32_t> values; + values.resize(8); + // For 'N' + values.at(0) = values.at(1) = 0; + // For 'H' + values.at(2) = _pad.top(); + values.at(3) = _pad.bottom(); + // For 'W' + values.at(4) = _pad.left(); + values.at(5) = _pad.right(); + // For 'C' + values.at(6) = values.at(7) = 0; + + binder->setOperand(pad, values.begin(), values.end()); + } + + auto ofm = binder->addOperand<float>(_ofm); + + binder->addOperation(ann::Operation::Code::PAD, {ifm, pad}, {ofm}); + } + +private: + coco::Padding2D _pad; + +private: + coco::FeatureObject *_ifm = nullptr; + coco::FeatureObject *_ofm = nullptr; +}; + +class ANNOpFunctionalAppender final : public ANNOpAppender +{ +public: + ANNOpFunctionalAppender(const Appender &fun) : _fun{fun} + { + // DO NOTHING + } + +public: + void append(ANNBinder *binder) const { _fun(binder); } + +private: + Appender _fun; +}; + +class ANNSubAppender final : public ANNOpAppender +{ +public: + void left(coco::FeatureObject *o) { _left = o; } + void right(coco::FeatureObject *o) { _right = o; } + void out(coco::FeatureObject *o) { _out = o; } + +public: + void append(ANNBinder *binder) const override + { + auto left = binder->addOperand<float>(_left); + auto right = binder->addOperand<float>(_right); + auto fuse = binder->addOperand<int32_t>(); + binder->setOperand(fuse, 0); + + auto out = binder->addOperand<float>(_out); + + binder->addOperation(ann::Operation::Code::SUB, {left, right, fuse}, {out}); + } + +private: + coco::FeatureObject *_left = nullptr; + coco::FeatureObject *_right = nullptr; + coco::FeatureObject *_out = nullptr; +}; + +class ANNDivAppender final : public ANNOpAppender +{ +public: + void left(coco::FeatureObject *o) { _left = o; } + void right(coco::FeatureObject *o) { _right = o; } + void out(coco::FeatureObject *o) { _out = o; } + +public: + void append(ANNBinder *binder) const override + { + auto left = binder->addOperand<float>(_left); + auto right = binder->addOperand<float>(_right); + auto fuse = binder->addOperand<int32_t>(); + binder->setOperand(fuse, 0); + + auto out = binder->addOperand<float>(_out); + + binder->addOperation(ann::Operation::Code::DIV, {left, right, fuse}, {out}); + } + +private: + coco::FeatureObject *_left = nullptr; + coco::FeatureObject *_right = nullptr; + coco::FeatureObject *_out = nullptr; +}; + +class ANNOpBuilder : public coco::Instr::Visitor<std::unique_ptr<ANNOpAppender>> +{ +public: + std::unique_ptr<ANNOpAppender> visit(const coco::Eval *eval) + { + if (auto conv = eval->op()->asConv2D()) + { + if (auto load = conv->arg()->asLoad()) + { + auto sess = enco::session(eval->module()); + + auto ifm = load->object()->asFeature(); + auto ker = conv->ker(); + auto ofm = eval->out()->asFeature(); + + const auto group = conv->group(); + + if (group == 1) + { + auto app = make_unique<ANNConv2DAppender>(); + + app->session(sess); + + app->pad(conv->pad()); + app->stride(conv->stride()); + + app->ifm(ifm); + app->ofm(ofm); + app->ker(ker); + + return std::move(app); + } + else + { + assert(ifm->shape().depth() == group); + assert(ker->shape().count() % group == 0); + assert(ker->shape().depth() == 1); + + auto app = make_unique<ANNDepthwiseConv2DAppender>(); + + app->session(sess); + + app->multiplier(ker->shape().count() / group); + app->pad(conv->pad()); + app->stride(conv->stride()); + + app->ifm(ifm); + app->ofm(ofm); + app->ker(ker); + + return std::move(app); + } + } + } + else if (auto op = eval->op()->asAdd()) + { + auto left_load = op->left()->asLoad(); + auto right_load = op->right()->asLoad(); + + if (left_load && right_load) + { + // Let's compile the following code fragment: + // + // %ofm = eval(Add(Load(%left), Load(%right))) + // + auto left = left_load->object()->asFeature(); + auto right = right_load->object()->asFeature(); + assert(left != nullptr && right != nullptr); + + auto out = eval->out()->asFeature(); + assert(out != nullptr); + + auto app = make_unique<ANNAddAppender>(); + + app->left(left); + app->right(right); + app->out(out); + + return std::move(app); + } + } + else if (auto op = eval->op()->asMul()) + { + auto left_load = op->left()->asLoad(); + auto right_load = op->right()->asLoad(); + + if (left_load && right_load) + { + // Let's compile the following code fragment: + // + // %ofm = eval(Mul(Load(%left), Load(%right))) + // + auto left = left_load->object()->asFeature(); + auto right = right_load->object()->asFeature(); + assert(left != nullptr && right != nullptr); + + auto out = eval->out()->asFeature(); + assert(out != nullptr); + + auto app = make_unique<ANNMulAppender>(); + + app->left(left); + app->right(right); + app->out(out); + + return std::move(app); + } + } + else if (auto op = eval->op()->asPadF()) + { + if (auto load = op->arg()->asLoad()) + { + // Let's compile the following code fragment: + // + // %ofm = eval(PadF(Load(%ifm)) + // + auto ifm = load->object()->asFeature(); + auto ofm = eval->out()->asFeature(); + + assert(ifm != nullptr && ofm != nullptr); + + auto app = make_unique<ANNPadFAppender>(); + + app->pad(op->pad()); + + app->ifm(ifm); + app->ofm(ofm); + + return std::move(app); + } + } + else if (auto maxpool = eval->op()->asMaxPool2D()) + { + if (auto load = maxpool->arg()->asLoad()) + { + // Let's compile the following code fragment: + // + // %ofm = eval(MaxPool2D(Load(%ifm)) + // + auto ifm = load->object()->asFeature(); + auto ofm = eval->out()->asFeature(); + + assert(ifm != nullptr && ofm != nullptr); + + auto app = make_unique<ANNMaxPool2DAppender>(); + + app->pad(maxpool->pad()); + app->stride(maxpool->stride()); + app->window(maxpool->window()); + + app->ifm(ifm); + app->ofm(ofm); + + return std::move(app); + } + } + else if (auto avgpool = eval->op()->asAvgPool2D()) + { + if (auto load = avgpool->arg()->asLoad()) + { + // Let's compile the following code fragment: + // + // %ofm = eval(AvgPool2D(Load(%ifm)) + // + if (avgpool->divisor() == coco::AvgPool2D::Divisor::PaddingExcluded) + { + // When ANN runtime computes the average of each receptive field, + // it uses the number of valid(=non-padding) elements as a divisor. + auto ifm = load->object()->asFeature(); + auto ofm = eval->out()->asFeature(); + + assert(ifm != nullptr && ofm != nullptr); + + auto app = make_unique<ANNAvgPool2DAppender>(); + + app->pad(avgpool->pad()); + app->stride(avgpool->stride()); + app->window(avgpool->window()); + + app->ifm(ifm); + app->ofm(ofm); + + return std::move(app); + } + } + } + else if (auto relu = eval->op()->asReLU()) + { + if (auto load = relu->arg()->asLoad()) + { + // Let's compile the following code fragment: + // + // %ofm = eval(ReLU(Load(%ifm)) + // + // TODO Support objects of other kinds, such as Tensor + auto ifm = load->object()->asFeature(); + auto ofm = eval->out()->asFeature(); + + assert(ifm != nullptr && ofm != nullptr); + + auto app = make_unique<ANNReLUAppender>(); + + app->ifm(ifm); + app->ofm(ofm); + + return std::move(app); + } + } + else if (auto relu6 = eval->op()->asReLU6()) + { + if (auto load = relu6->arg()->asLoad()) + { + // Let's compile the following code fragment: + // + // %ofm = eval(ReLU6(Load(%ifm)) + // + // TODO Support objects of other kinds, such as Tensor + auto ifm = load->object()->asFeature(); + auto ofm = eval->out()->asFeature(); + + assert(ifm != nullptr && ofm != nullptr); + + auto app = make_unique<ANNReLU6Appender>(); + + app->ifm(ifm); + app->ofm(ofm); + + return std::move(app); + } + } + else if (auto op = eval->op()->asConcatF()) + { + auto left_load = op->left()->asLoad(); + auto right_load = op->right()->asLoad(); + + if (left_load && right_load && (op->axis() == coco::ConcatF::Axis::Depth)) + { + // Let's compile the following code fragment: + // + // %ofm = eval(ConcatF(Depth, Load(%left), Load(%right))) + // + auto left = left_load->object()->asFeature(); + auto right = right_load->object()->asFeature(); + assert(left != nullptr && right != nullptr); + + auto out = eval->out()->asFeature(); + assert(out != nullptr); + + auto app = make_unique<ANNConcatAppender>(); + + app->left(left); + app->right(right); + app->out(out); + + return std::move(app); + } + } + else if (auto op = eval->op()->asSub()) + { + auto left_load = op->left()->asLoad(); + auto right_load = op->right()->asLoad(); + + if (left_load && right_load) + { + // Let's compile the following code fragment: + // + // %out = eval(Sub(Load(%left), Load(%right))) + // + auto left = left_load->object()->asFeature(); + auto right = right_load->object()->asFeature(); + assert(left != nullptr && right != nullptr); + + auto out = eval->out()->asFeature(); + assert(out != nullptr); + + auto app = make_unique<ANNSubAppender>(); + + app->left(left); + app->right(right); + app->out(out); + + return std::move(app); + } + } + else if (auto op = eval->op()->asDiv()) + { + auto left_load = op->left()->asLoad(); + auto right_load = op->right()->asLoad(); + + if (left_load && right_load) + { + // Let's compile the following code fragment: + // + // %out = eval(Div(Load(%left), Load(%right))) + // + auto left = left_load->object()->asFeature(); + auto right = right_load->object()->asFeature(); + assert(left != nullptr && right != nullptr); + + auto out = eval->out()->asFeature(); + assert(out != nullptr); + + auto app = make_unique<ANNDivAppender>(); + + app->left(left); + app->right(right); + app->out(out); + + return std::move(app); + } + } + + // Return nullptr if a given Eval instruction is incompatible + return nullptr; + } + +public: + std::unique_ptr<ANNOpAppender> visit(const coco::Shuffle *) { return nullptr; } +}; + +namespace +{ + +std::unique_ptr<ANNOpAppender> make_appender(coco::Instr *ins) +{ + ANNOpBuilder op_builder; + + if (auto eval = coco::safe_cast<coco::Eval>(ins)) + { + return eval->accept(op_builder); + } + + if (auto depth_concat = coco::safe_cast<ANNDepthConcatF>(ins)) + { + auto app = make_unique<ANNConcatAppender>(); + + app->out(depth_concat->out()->asFeature()); + + app->left(depth_concat->fst()->asFeature()); + app->right(depth_concat->snd()->asFeature()); + + return std::move(app); + } + + // Build ANN IR from ANNConv2D instruction + if (auto conv2d = coco::safe_cast<ANNConv2D>(ins)) + { + auto sess = enco::session(conv2d->module()); + auto app = make_unique<ANNConv2DAppender>(); + + app->session(sess); + + app->pad(conv2d->pad()); + app->stride(conv2d->stride()); + + app->ofm(conv2d->ofm()->asFeature()); + app->ifm(conv2d->ifm()->asFeature()); + app->ker(conv2d->ker()->asKernel()); + app->bias(coco::safe_cast<coco::FeatureObject>(conv2d->bias())); + + return std::move(app); + } + + return nullptr; +} + +enum Compatibility +{ + COMPATIBLE, + INCOMPATIBLE +}; + +class ANNGroupBuilder +{ +public: + ANNGroupBuilder(ANNContext *ctx) : _ctx{ctx} + { + // DO NOTHING + } + +public: + Compatibility kind(const coco::Block *blk) const; + Compatibility kind(const std::unique_ptr<ANNOpAppender> &appender) const; + +public: + void build(enco::Code *code) const; + +private: + ANNContext *_ctx; +}; + +Compatibility ANNGroupBuilder::kind(const std::unique_ptr<ANNOpAppender> &app) const +{ + return app ? COMPATIBLE : INCOMPATIBLE; +} + +Compatibility ANNGroupBuilder::kind(const coco::Block *blk) const +{ + return (_ctx->find(blk) != nullptr) ? COMPATIBLE : INCOMPATIBLE; +} + +void ANNGroupBuilder::build(enco::Code *code) const +{ + auto m = code->module(); + + // ANNGroupBuilder will construct a sequence of blocks from the original block sequence, and + // a destination block (that dst_blk points to) is the tail of the generated sequence. + coco::Block *dst_blk = nullptr; + + auto append = [&](const Compatibility &t) { + auto blk = m->entity()->block()->create(); + + if (dst_blk == nullptr) + { + m->block()->prepend(blk); + } + else + { + blk->insertAfter(dst_blk); + } + + dst_blk = blk; + + if (COMPATIBLE == t) + { + _ctx->create(blk); + } + }; + + for (auto blk = m->block()->head(); blk;) + { + // Let's move instructions from a block of interest (referred to as source block) into + // a destination block + auto src_blk = blk; + blk = src_blk->next(); + src_blk->detach(); + + for (auto ins = src_blk->instr()->head(); ins;) + { + auto cur_ins = ins; + ins = cur_ins->next(); + cur_ins->detach(); + + auto cur_append = make_appender(cur_ins); + + // Create a new compatible block and use it as a destination block if the current + // destination block is absent or incompatible with the instruction of intereset. + if ((dst_blk == nullptr) || (kind(cur_append) != kind(dst_blk))) + { + append(kind(cur_append)); + } + + assert(dst_blk != nullptr); + assert(kind(cur_append) == kind(dst_blk)); + + // Append ins to the dst_blk block + dst_blk->instr()->append(cur_ins); + + if (cur_append) + { + // Update Android NN IR if the current instruction is compatible + auto binder = _ctx->find(dst_blk); + assert(binder != nullptr); + cur_append->append(binder); + } + } + + // Destroy the source block + assert(src_blk->instr()->empty()); + m->entity()->block()->destroy(src_blk); + } +} + +} // namespace + +class ANNModuleBuilder +{ +private: + std::set<coco::Bag *> inputs(ANNBinder *binder) const; + std::set<coco::Bag *> outputs(ANNBinder *binder) const; + +public: + void build(ANNContext *ann_ctx) const; +}; + +std::set<coco::Bag *> ANNModuleBuilder::inputs(ANNBinder *binder) const +{ + std::set<coco::Bag *> res; + + for (auto bag : binder->bags()) + { + auto u = enco::updaters(bag); + u.erase(binder->block()); + + /** + * A bag is the input of this block if + * 1. it is an input of the whole network, or + * 2. it is updated by preceding blocks during execution + */ + if (bag->isInput() || (u.size() > 0)) + { + res.insert(bag); + } + } + + return res; +} + +std::set<coco::Bag *> ANNModuleBuilder::outputs(ANNBinder *binder) const +{ + std::set<coco::Bag *> res; + + for (auto bag : binder->bags()) + { + auto u = enco::updaters(bag); + auto r = enco::readers(bag); + r.erase(binder->block()); + + /** + * Only a bag that this block updates can be the output of this block + */ + if (u.find(binder->block()) == u.end()) + { + continue; + } + + /** + * A bag is the output of this block if + * 1. it is an output of the whole network, or + * 2. it is read by following blocks during execution + */ + if (bag->isOutput() || (r.size() > 0)) + { + res.insert(bag); + } + } + + return res; +} + +void ANNModuleBuilder::build(ANNContext *ann_ctx) const +{ + for (uint32_t n = 0; n < ann_ctx->count(); ++n) + { + auto binder = ann_ctx->nth(n); + + // NOTE binder->module() returns an ANN IR module (not coco IR module) + auto m = binder->block()->module(); + auto d = enco::data(m); + + // Let's identify operands with initial values + for (auto bag : binder->bags()) + { + if (binder->associated(bag) && d->allocated(bag)) + { + // TODO Support other datatype + auto span = d->f32()->weight(bag); + assert(span.data() != nullptr); + + binder->setOperand(binder->operand(bag), span.data(), span.data() + span.size()); + } + } + + // Let's identify input/output bags + binder->identifyInputs(inputs(binder)); + binder->identifyOutputs(outputs(binder)); + } +} + +} // namespace + +namespace +{ + +class SplitPass +{ +public: + void runOnCode(enco::Code *code) const; +}; + +void SplitPass::runOnCode(enco::Code *code) const +{ + auto ann_ctx = make_unique<ANNContext>(); + + ANNGroupBuilder group_builder{ann_ctx.get()}; + group_builder.build(code); + + ANNModuleBuilder module_builder; + module_builder.build(ann_ctx.get()); + + _subnet_contexts[code->module()] = std::move(ann_ctx); +} + +} // namespace + +namespace enco +{ + +void split_into_phases(enco::Code *code) +{ + SplitPass split; + split.runOnCode(code); +} + +} // namespace enco diff --git a/compiler/enco/core/src/Transforms/Split.h b/compiler/enco/core/src/Transforms/Split.h new file mode 100644 index 000000000..b4e1d7baf --- /dev/null +++ b/compiler/enco/core/src/Transforms/Split.h @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2018 Samsung Electronics Co., Ltd. All Rights Reserved + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __SPLIT_H__ +#define __SPLIT_H__ + +#include "Code.h" +#include "Pass.h" + +namespace enco +{ + +struct SubnetManager +{ + static const ANNContext *context(const coco::Module *m); +}; + +/** + * @brief Split instructions into a set of phases + */ +void split_into_phases(enco::Code *code); + +struct PhaseConstructionPass final : public Pass +{ + PASS_CTOR(PhaseConstructionPass) + { + // DO NOTHING + } + + void run(const SessionID &sess) const override { split_into_phases(code(sess)); } +}; + +} // namespace enco; + +#endif // __SPLIT_H__ |