From e52135f16010e55eac0af7ea7ccfe65835ea7eef Mon Sep 17 00:00:00 2001 From: =?utf8?q?=EB=B0=95=EC=A2=85=ED=98=84/=EB=8F=99=EC=9E=91=EC=A0=9C?= =?utf8?q?=EC=96=B4Lab=28SR=29/Staff=20Engineer/=EC=82=BC=EC=84=B1?= =?utf8?q?=EC=A0=84=EC=9E=90?= Date: Thu, 29 Nov 2018 14:25:48 +0900 Subject: [PATCH] [enco] Support constant folding (#2441) This commit introduces constant folding pass into the enco compilation pipeline. Note that the current implementation supports folding over "copy" instruction only. Signed-off-by: Jonghyun Park --- contrib/enco/core/src/Backend.cpp | 3 + .../enco/core/src/Transforms/ConstantFolding.cpp | 206 +++++++++++++++++++++ contrib/enco/core/src/Transforms/ConstantFolding.h | 32 ++++ 3 files changed, 241 insertions(+) create mode 100644 contrib/enco/core/src/Transforms/ConstantFolding.cpp create mode 100644 contrib/enco/core/src/Transforms/ConstantFolding.h diff --git a/contrib/enco/core/src/Backend.cpp b/contrib/enco/core/src/Backend.cpp index 43feb9d..b725e7c 100644 --- a/contrib/enco/core/src/Backend.cpp +++ b/contrib/enco/core/src/Backend.cpp @@ -30,6 +30,7 @@ #include "Transforms/IdenticalObjectReduction.h" #include "Transforms/DuplicatedObjectReduction.h" #include "Transforms/DeadObjectElimination.h" +#include "Transforms/ConstantFolding.h" #include "Transforms/CopyLowering.h" #include "Transforms/ConcatLowering.h" #include "Transforms/DeadBagElimination.h" @@ -111,6 +112,8 @@ void BackendImpl::compile(coco::Module *m, coco::Data *d) reduce_identical_object(code(sess)); reduce_duplicated_object(code(sess)); + fold_constants(code(sess)); + // Eliminate dead object // // NOTE Dead Object Elimination (DOE) is performed before Copy lowering diff --git a/contrib/enco/core/src/Transforms/ConstantFolding.cpp b/contrib/enco/core/src/Transforms/ConstantFolding.cpp new file mode 100644 index 0000000..3ebca81 --- /dev/null +++ b/contrib/enco/core/src/Transforms/ConstantFolding.cpp @@ -0,0 +1,206 @@ +/* + * 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 + +#include + +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 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 void operator<<(const ConstantBagEnumerator &e, Callable &&cb) +{ + e.enumerate(std::forward(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 T take(std::queue &q) +{ + assert(q.size() > 0); + auto res = q.front(); + q.pop(); + return res; +} + +} // namespace + +namespace +{ + +void fold_constant(std::queue &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(); + + 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); +} + +void fold_constant(std::queue &q, coco::Instr *ins) +{ + if (auto copy = coco::safe_cast(ins)) + { + fold_constant(q, copy); + return; + } +} + +} // namespace + +namespace enco +{ + +void fold_constants(enco::Code *code) +{ + std::queue 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/contrib/enco/core/src/Transforms/ConstantFolding.h b/contrib/enco/core/src/Transforms/ConstantFolding.h new file mode 100644 index 0000000..20ab1a4 --- /dev/null +++ b/contrib/enco/core/src/Transforms/ConstantFolding.h @@ -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. + */ + +#ifndef __CONSTANT_FOLDING_H__ +#define __CONSTANT_FOLDING_H__ + +#include "Code.h" + +namespace enco +{ + +/** + * @brief Evaluate "constant" expressions at compile time + */ +void fold_constants(enco::Code *); + +} // namespace enco + +#endif // __CONSTANT_FOLDING_H__ -- 2.7.4