partial_eval.cc 39.7 KB
Newer Older
雾雨魔理沙 committed
1 2 3 4 5 6 7 8
/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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
9
 *
雾雨魔理沙 committed
10
 *   http://www.apache.org/licenses/LICENSE-2.0
11
 *
雾雨魔理沙 committed
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
 * 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.
 */

/*!
 * \file partial_eval.cc
 *
 * \brief Perform known computation in compile time.
 *
 * The partial evaluator try to do computation at compile time,
 * so it can generate code that do less work.
 * Additionally, it might open more chance for further optimization,
 * since the high level, structural part of the code (closure, reference, control flow)
 * might get partially evaluated away, and the subsequent optimization (for example, kernel fusion)
 * can reason across those structural code as it got removed.
 * In the extreme case, partial evaluation can even turn the whole program
 * into pure first order computation with no control flow.
 * In such a case, we can compile the whole computation onto SIMD Instruction/GPU/FPGA,
 * and get huge speedup.
 *
 * It works by making the following modifications to the standard relay interpreter:
 *
 * 0: The values become partially static value.
 * Since we cannot know the value of every term at compile time,
 * Term might get partially evaluated to 'Unknown Value'.
 * Every partially static value is, hence,
 * a static fragment that might not be there (partially static),
 * and a dynamic fragment that is semantically equivalent to the original term,
 * so the unknown part will be computed at runtime, using the dynamic fragment.
 *
 * 1: The interpreter holds a LetList, which preserves A Normal Form for the generated code.
 * More specifically, we require that all dynamic is an atom.
 * This avoids code duplication (which is both inefficient and incorrect), as atom has constant size
 * and allow us to not handle capture-avoidance substitution (as atom has no binder).
 *
 * 2: The map of References to partially static values is reified, as described below.
 * Instead of Reference having mutable field, Reference only has an unique identifier.
 * There will be a mutable mapping of id to partially static value, called the store.
 * This allow us to rollback the store:
 * when a path may or may not be executed (as in a conditional), we copy the store,
 * recurse with the copy, and reinstate the original when the call returns
 * so that the effects of the computation are not preserved.
 * We do this in if else, pattern matching, and in function,
 * as, when we see a function, we partially evaluate it with all the argument as dynamic,
 * to generate efficient dynamic for that function.
 *
 * 3: The generated code reuses bindings (although they are not shadowed),
 * so we have to deduplicate them.
 *
65
 * 4: In the generated code, as it call TypeSubst, multiple VarNode might have same Id.
雾雨魔理沙 committed
66 67 68 69 70 71 72 73 74
 * While it is permitted, most pass use NodeHash for Var,
 * and having multiple VarNode for same Id break them.
 * Thus we remap them to a single Id for now.
 *
 * Also, It will also generate lots of dead code,
 * so it is a good idea to feed it through the dead code eliminator after partial evaluation.
 *
 * The partial evaluator makes several assumptions, so there is room for improvement:
 *
雾雨魔理沙 committed
75
 * 0: Every time an unknown effect happened, we clear the whole store.
雾雨魔理沙 committed
76 77 78 79
 * It is too conservative: if a local reference is created (and do not get passed outside),
 * An unknown global function call/global reference write can not modify it.
 * We can pair PE with escape analysis/alias analysis.
 *
雾雨魔理沙 committed
80
 * 1: We assume all unknown code has effect. Doing effect analysis can make the store more precise.
雾雨魔理沙 committed
81
 *
雾雨魔理沙 committed
82
 * 2: When doing pattern matching, we can simplify the match even for dynamic case.
雾雨魔理沙 committed
83 84 85 86
 * Right now it is all or nothing: either a complete match, or the original dynamic code.
 * Instead, we can get a match tree, pair it with the data and evaluate it to a normal form.
 * We then can reify the result.
 *
雾雨魔理沙 committed
87
 * 3: Every time a function is called, its code will get expanded and partially evaluated.
雾雨魔理沙 committed
88 89 90 91
 * We can do a binding time analysis to cache the result and avoid re-partial evaluation.
 *
 * These assumptions do not affect the correctness of the algorithm, however.
 */
Zhi committed
92 93
#include <tvm/relay/analysis.h>
#include <tvm/relay/transform.h>
雾雨魔理沙 committed
94 95 96
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
#include <tvm/relay/interpreter.h>
雾雨魔理沙 committed
97
#include "../ir/type_functor.h"
雾雨魔理沙 committed
98 99 100 101 102
#include "pass_util.h"
#include "let_list.h"

namespace tvm {
namespace relay {
103
namespace partial_eval {
雾雨魔理沙 committed
104 105 106 107 108 109 110 111 112

using namespace runtime;

/*! \brief Hash Var by it's id.
 * Different VarNode might has same vid, and they are considered to be the same var in such case.
 * Use VarHash to hash Var by id.
 */
struct VarHash {
  size_t operator()(const Var& v) const {
113
    return NodeHash()(v->vid);
雾雨魔理沙 committed
114 115 116 117 118 119 120 121 122 123 124 125 126
  }
};

/*! \brief Compare Var by it's id.
 * Different VarNode might has same vid, and they are considered to be the same var in such case.
 * Use VarEqual to compare Var by id.
 */
struct VarEqual {
  bool operator()(const Var& l, const Var& r) const {
    return l->vid.get() == r->vid.get();
  }
};

雾雨魔理沙 committed
127 128
Expr PostProcess(const Expr&);

129
/*! \brief A StaticNode contains some static data that the Partial Evaluator can use. */
雾雨魔理沙 committed
130 131
class StaticNode : public RelayNode {
 public:
132
  static constexpr const char* _type_key = "relay.Static";
133
  TVM_DECLARE_BASE_NODE_INFO(StaticNode, RelayNode);
雾雨魔理沙 committed
134 135 136 137 138
};

class Static : public NodeRef {
 public:
  Static() {}
139 140 141
  explicit Static(ObjectPtr<Object> n) : NodeRef(n) {}
  const StaticNode* operator->() const {
    return static_cast<const StaticNode*>(get());
雾雨魔理沙 committed
142 143 144 145 146
  }

  using ContainerType = StaticNode;
};

雾雨魔理沙 committed
147 148
using Time = size_t;

雾雨魔理沙 committed
149
struct PStaticNode : Node {
雾雨魔理沙 committed
150 151 152 153 154 155
  static Time time() {
    static Time time_ = 0;
    Time ret = time_;
    time_++;
    return ret;
  }
雾雨魔理沙 committed
156 157
  Static pstatic;  // may be null
  Expr dynamic;
雾雨魔理沙 committed
158 159 160
  Time created_time;
  PStaticNode(const Static& pstatic, const Expr& dynamic) :
    pstatic(pstatic), dynamic(dynamic), created_time(time()) { }
雾雨魔理沙 committed
161
  explicit PStaticNode(const Expr& dynamic) : PStaticNode(Static(), dynamic) { }
162
  static constexpr const char* _type_key = "relay.PStatic";
雾雨魔理沙 committed
163 164 165 166 167 168 169 170
  TVM_DECLARE_NODE_TYPE_INFO(PStaticNode, Node);
};

RELAY_DEFINE_NODE_REF(PStatic, PStaticNode, NodeRef);

struct STupleNode : StaticNode {
  std::vector<PStatic> fields;
  explicit STupleNode(const std::vector<PStatic>& fields) : fields(fields) { }
171
  static constexpr const char* _type_key = "relay.STuple";
雾雨魔理沙 committed
172 173 174
  TVM_DECLARE_NODE_TYPE_INFO(STupleNode, StaticNode);
};

175
RELAY_DEFINE_NODE_REF(STuple, STupleNode, Static);
雾雨魔理沙 committed
176 177 178 179 180 181 182 183

Static MkSTuple(const std::vector<PStatic>& fields) {
  return Static(make_node<STupleNode>(fields));
}

struct STensorNode : StaticNode {
  runtime::NDArray data;
  explicit STensorNode(const NDArray& data) : data(data) { }
184 185
  static constexpr const char* _type_key = "relay.STensor";
  TVM_DECLARE_NODE_TYPE_INFO(STensorNode, StaticNode);
雾雨魔理沙 committed
186 187
};

188
RELAY_DEFINE_NODE_REF(STensor, STensorNode, Static);
雾雨魔理沙 committed
189 190 191 192 193 194 195 196 197 198

Static MkSTensor(const NDArray& data) {
  return Static(make_node<STensorNode>(data));
}

struct SConstructorNode : StaticNode {
  Constructor constructor;
  std::vector<PStatic> fields;
  SConstructorNode(const Constructor& constructor, const std::vector<PStatic>& fields) :
    constructor(constructor), fields(fields) { }
199
  static constexpr const char* _type_key = "relay.SConstructor";
雾雨魔理沙 committed
200 201 202
  TVM_DECLARE_NODE_TYPE_INFO(SConstructorNode, StaticNode);
};

203
RELAY_DEFINE_NODE_REF(SConstructor, SConstructorNode, Static);
雾雨魔理沙 committed
204 205 206 207 208 209

Static MkSConstructor(const Constructor& constructor, const std::vector<PStatic>& fields) {
  return Static(make_node<SConstructorNode>(constructor, fields));
}

struct SRefNode : StaticNode {
210
  static constexpr const char* _type_key = "relay.SRef";
雾雨魔理沙 committed
211 212 213 214
  // we will use the address as the guid for hashing
  TVM_DECLARE_NODE_TYPE_INFO(SRefNode, StaticNode);
};

215
RELAY_DEFINE_NODE_REF(SRef, SRefNode, Static);
雾雨魔理沙 committed
216 217 218 219 220

Static MkSRef() {
  return Static(make_node<SRefNode>());
}

221 222
using Func = std::function<PStatic(const PStatic&,
                                   const std::vector<PStatic>&,
223 224 225
                                   const Attrs&,
                                   const Array<Type>&,
                                   LetList*)>;
雾雨魔理沙 committed
226 227 228 229

struct SFuncNode : StaticNode {
  Func func;
  explicit SFuncNode(const Func& func) : func(func) { }
230
  static constexpr const char* _type_key = "relay.SFunc";
雾雨魔理沙 committed
231 232 233
  TVM_DECLARE_NODE_TYPE_INFO(SFuncNode, StaticNode);
};

234
RELAY_DEFINE_NODE_REF(SFunc, SFuncNode, Static);
雾雨魔理沙 committed
235 236 237 238 239

Static MkSFunc(const Func& func) {
  return Static(make_node<SFuncNode>(func));
}

240 241 242 243 244 245 246 247 248 249 250 251

class FuelNode;
/*! \brief A meet-semilattice with finite descending chain.
 * It means that we can meet two element to get an element,
 * and for every element, there is only a finite amount of meet before getting back the same element.
 *
 * Every time we recurse, we do a meet and require that progress must be made.
 * This ensures we do not recurse infinitely in the Partial Evaluator.
 */
class Fuel : public NodeRef {
 public:
  Fuel() {}
252
  explicit Fuel(ObjectPtr<Object> n) : NodeRef(n) {}
253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
  const FuelNode* operator->() const;

  using ContainerType = FuelNode;
};

class FuelNode : public RelayNode {
 public:
  // Please implement one of the following function or there will be infinite loop.
  /*! \brief return the new Fuel, and whether progress is made.
   *
   * Note that progress is not symmetric - it only measure progress for (*this).
   *
   * Thus, if the generated is smaller then the argument of Meet,
   * and the generated is not smaller then (*this),
   * progress should be false.
   */
  virtual std::tuple<Fuel, bool> Meet(const Fuel& f) const {
    bool progress = false;
    auto ret = Meet(f, &progress);
    return std::make_tuple(ret, progress);
  }
  /*! \brief return the new Fuel, and write (*progress | is progress made) to *progress. */
  virtual Fuel Meet(const Fuel& f, bool* progress) const {
    CHECK(progress);
    auto ret = Meet(f);
    *progress |= std::get<1>(ret);
    return std::get<0>(ret);
  }
  static constexpr const char* _type_key = "relay.Fuel";
  TVM_DECLARE_BASE_NODE_INFO(FuelNode, RelayNode);
};

const FuelNode* Fuel::operator->() const {
286
  return static_cast<const FuelNode*>(get());
287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
}

Fuel MkFSeq(const std::vector<Fuel>& fuels);
struct FSeqNode : FuelNode {
  std::vector<Fuel> fuels;
  Fuel Meet(const Fuel& f, bool* progress) const final {
    auto x = f.as<FSeqNode>();
    CHECK(x);
    CHECK_EQ(fuels.size(), x->fuels.size());
    std::vector<Fuel> new_fuels;
    for (size_t i = 0; i < fuels.size(); ++i) {
      new_fuels.push_back(fuels[i]->Meet(x->fuels[i], progress));
    }
    return MkFSeq(new_fuels);
  }
  explicit FSeqNode(const std::vector<Fuel>& fuels) : fuels(fuels) { }
  static constexpr const char* _type_key = "relay.FSeq";
  TVM_DECLARE_NODE_TYPE_INFO(FSeqNode, FuelNode);
};

RELAY_DEFINE_NODE_REF(FSeq, FSeqNode, Fuel);

Fuel MkFSeq(const std::vector<Fuel>& fuels) {
  return Fuel(make_node<FSeqNode>(fuels));
}

Fuel MkFTime(Time time);
struct FTimeNode : FuelNode {
  Time time;
  std::tuple<Fuel, bool> Meet(const Fuel& f) const final {
    auto x = f.as<FTimeNode>();
    CHECK(x);
    Time new_time = std::min(time, x->time);
    return std::make_tuple(MkFTime(new_time), new_time < time);
  }
  explicit FTimeNode(Time time) : time(time) { }
  static constexpr const char* _type_key = "relay.FTime";
  TVM_DECLARE_NODE_TYPE_INFO(FTimeNode, FuelNode);
};

RELAY_DEFINE_NODE_REF(FTime, FTimeNode, Fuel);

Fuel MkFTime(Time time) {
  return Fuel(make_node<FTimeNode>(time));
}

Fuel MkFTValue(size_t tvalue);
/*! \brief If the pstatic is hold a positive integer scalar, that number, else 0. */
struct FTValueNode : FuelNode {
  size_t tvalue;
  std::tuple<Fuel, bool> Meet(const Fuel& f) const final {
    auto x = f.as<FTValueNode>();
    CHECK(x);
    size_t new_tvalue = std::min(tvalue, x->tvalue);
    return std::make_tuple(MkFTValue(new_tvalue), new_tvalue < tvalue);
  }
  explicit FTValueNode(size_t tvalue) : tvalue(tvalue) { }
  static constexpr const char* _type_key = "relay.FTValue";
  TVM_DECLARE_NODE_TYPE_INFO(FTValueNode, FuelNode);
};

RELAY_DEFINE_NODE_REF(FTValue, FTValueNode, Fuel);

Fuel MkFTValue(size_t tvalue) {
  return Fuel(make_node<FTValueNode>(tvalue));
}

/*! \brief Initially every element has Fuel of FTop. It is the largest element.
 *
 * Note that it is illegal to has FTop inside some other Fuel -
 * doing so break the finite descending chain property.
 */
struct FTopNode : FuelNode {
  std::tuple<Fuel, bool> Meet(const Fuel& f) const final {
    return std::make_tuple(f, !f.as<FTopNode>());
  }
  static constexpr const char* _type_key = "relay.FTop";
  TVM_DECLARE_NODE_TYPE_INFO(FTopNode, FuelNode);
};

RELAY_DEFINE_NODE_REF(FTop, FTopNode, Fuel);

Fuel MkFTop() {
  return Fuel(make_node<FTopNode>());
}

雾雨魔理沙 committed
373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396
/*!
 * \brief A stack frame in the Relay interpreter.
 *
 * Contains a mapping from relay::Var to relay::Value.
 */
struct Frame {
  /*! \brief The set of local variables and arguments for the frame. */
  std::unordered_map<Var, PStatic, VarHash, VarEqual> locals;
  Frame() = default;
};

class Environment {
 public:
  Environment() : env_({Frame()}) { }
  Environment(const Environment&) = delete;

  template<typename T>
  T Extend(const std::function<T()>& body) {
    FrameContext fc(this);
    return body();
  }

  void Insert(const Var& v, const PStatic& ps) {
    CHECK(ps.defined());
397
    CHECK_GT(env_.size(), 0);
398
    CHECK_EQ(env_.back().locals.count(v), 0);
雾雨魔理沙 committed
399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429
    env_.back().locals[v] = ps;
  }

  PStatic Lookup(const Var& v) {
    auto rit = env_.rbegin();
    while (rit != env_.rend()) {
      if (rit->locals.find(v) != rit->locals.end()) {
        return rit->locals.find(v)->second;
      }
      ++rit;
    }
    LOG(FATAL) << "Unknown Variable: " << v;
    throw;
  }

 private:
  std::list<Frame> env_;

  struct FrameContext {
    Environment* env_;
    explicit FrameContext(Environment* env) : env_(env) {
      env_->env_.push_back(Frame());
    }
    ~FrameContext() {
      env_->env_.pop_back();
    }
  };
};

/*!
 * \brief As our store require rollback, we implement it as a frame.
430 431 432
 *
 * Every time we need to copy the store, a new frame is insert.
 * Every time we roll back, a frame is popped.
雾雨魔理沙 committed
433 434 435
 */
struct StoreFrame {
  std::unordered_map<const SRefNode*, PStatic> store;
436 437 438 439 440
  /*!
   * \brief On unknown effect, history_valid is set to true to signal above frame is outdated.
   *
   * It only outdate the frame above it, but not the current frame.
   */
雾雨魔理沙 committed
441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457
  bool history_valid = true;
  explicit StoreFrame(const std::unordered_map<const SRefNode*, PStatic>& store) : store(store) { }
  StoreFrame() = default;
};

class Store {
 public:
  Store() : store_({StoreFrame()}) { }
  Store(const Store&) = delete;

  template<typename T>
  T Extend(const std::function<T()>& body) {
    StoreFrameContext sfc(this);
    return body();
  }

  void Insert(const SRefNode* r, const PStatic& ps) {
458
    CHECK(r);
雾雨魔理沙 committed
459 460 461 462 463 464 465 466 467 468
    store_.back().store[r] = ps;
  }

  // return null if not found
  PStatic Lookup(const SRefNode* r) {
    auto rit = store_.rbegin();
    while (rit != store_.rend()) {
      if (rit->store.find(r) != rit->store.end()) {
        return rit->store.find(r)->second;
      }
469 470 471
      if (!rit->history_valid) {
        return PStatic();
      }
雾雨魔理沙 committed
472 473 474 475 476 477
      ++rit;
    }
    return PStatic();
  }

  void Invalidate() {
478 479 480
    StoreFrame sf;
    sf.history_valid = false;
    store_.push_back(sf);
雾雨魔理沙 committed
481 482 483 484 485 486 487 488 489 490 491
  }

 private:
  std::list<StoreFrame> store_;

  struct StoreFrameContext {
    Store* store_;
    explicit StoreFrameContext(Store* store) : store_(store) {
      store_->store_.push_back(StoreFrame());
    }
    ~StoreFrameContext() {
492 493 494 495
      // push one history valid frame off.
      while (!store_->store_.back().history_valid) {
        store_->store_.pop_back();
      }
雾雨魔理沙 committed
496 497 498 499 500 501
      store_->store_.pop_back();
    }
  };
};

PStatic HasStatic(const Static& stat, const Expr& dynamic) {
雾雨魔理沙 committed
502
  CHECK(stat.defined());
雾雨魔理沙 committed
503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536
  return PStatic(make_node<PStaticNode>(stat, dynamic));
}

PStatic NoStatic(const Expr& dynamic) {
  return PStatic(make_node<PStaticNode>(dynamic));
}

enum struct MatchStatus {
  Match, NoMatch, Unknown
};

bool StatefulOp(const Expr& e) {
  static auto op_stateful = Op::GetAttr<TOpIsStateful>("TOpIsStateful");
  struct StatefulOpVisitor : ExprVisitor {
    bool stateful = false;
    void VisitExpr_(const OpNode* op) {
      stateful = stateful || op_stateful.get(GetRef<Op>(op), false);
    }
  };
  StatefulOpVisitor sov;
  sov(e);
  return sov.stateful;
}

using FInterpreter = runtime::TypedPackedFunc<Value(Expr)>;

DLContext CPUContext() {
  DLContext ctx;
  ctx.device_type = kDLCPU;
  ctx.device_id = 0;
  return ctx;
}

FInterpreter CPUInterpreter() {
537
  Target target = Target::Create("llvm");
雾雨魔理沙 committed
538 539
  // use a fresh build context
  // in case we are already in a build context.
540
  With<BuildConfig> fresh_build_ctx(BuildConfig::Create());
雾雨魔理沙 committed
541 542 543 544

  return CreateInterpreter(Module(nullptr), CPUContext(), target);
}

雾雨魔理沙 committed
545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593
using FuncId = int;

/*!
 * \brief Annotate a function with a FuncId.
 */
struct WithFuncIdAttrs : public tvm::AttrsNode<WithFuncIdAttrs> {
  FuncId fid;

  TVM_DECLARE_ATTRS(WithFuncIdAttrs, "relay.attrs.WithFuncIdAttrs") {
    TVM_ATTR_FIELD(fid)
      .describe("The FuncId that an function is annotated with.")
      .set_default(-1);
  }
};

TVM_REGISTER_NODE_TYPE(WithFuncIdAttrs);

Op WithFuncIdOp() {
  static const Op& op = Op::Get("annotation.with_funcid");
  return op;
}

Expr MkWithFuncId(const Expr& expr, FuncId fid) {
  auto attrs = make_node<WithFuncIdAttrs>();
  attrs->fid = fid;
  return CallNode::make(WithFuncIdOp(), {expr}, Attrs(attrs), {});
}

RELAY_REGISTER_OP("annotation.with_funcid")
.describe(R"code(Annotate a function with a funcid.)code"
TVM_ADD_FILELINE)
.set_num_inputs(1)
.add_argument("func", "Function", "The input data.");

Expr StripWithFuncId(const Expr& e);

Function AsFunc(const Expr& e) {
  if (e.as<FunctionNode>()) {
    return Downcast<Function>(e);
  } else if (const CallNode* c = e.as<CallNode>()) {
    CHECK(c->op.same_as(WithFuncIdOp()));
    CHECK_EQ(c->args.size(), 1);
    return AsFunc(c->args[0]);
  } else {
    LOG(FATAL) << "Unknown case";
    throw;
  }
}

雾雨魔理沙 committed
594 595 596
class PartialEvaluator : public ExprFunctor<PStatic(const Expr& e, LetList* ll)>,
                         public PatternFunctor<MatchStatus(const Pattern&, const PStatic&)> {
 public:
597
  PartialEvaluator(const Module& mod) : mod_(mod) { }
雾雨魔理沙 committed
598

雾雨魔理沙 committed
599 600 601 602 603 604
  PStatic VisitExpr(const Expr& e, LetList* ll) final {
    PStatic ret = ExprFunctor<PStatic(const Expr&, LetList*)>::VisitExpr(e, ll);
    CHECK(IsAtomic(ret->dynamic)) << ret->dynamic;
    return ret;
  }

605
  PStatic VisitExpr(const Expr& e, LetList* ll, const Var& name) {
606 607 608 609
    if (const CallNode* c = e.as<CallNode>()) {
      if (c->op.same_as(WithFuncIdOp())) {
        CHECK_EQ(c->args.size(), 1);
        return VisitExpr(c->args[0], ll, name);
610 611 612 613 614 615 616 617 618
      }
    }
    PStatic ret = e.as<FunctionNode>() ?
      VisitFunc(Downcast<Function>(e), ll, name) :
      VisitExpr(e, ll);
    CHECK(IsAtomic(ret->dynamic)) << ret->dynamic;
    return ret;
  }

雾雨魔理沙 committed
619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646
  PStatic VisitExpr_(const ConstantNode* op, LetList* ll) final {
    return HasStatic(MkSTensor(op->data.CopyTo(context_)), ll->Push(GetRef<Expr>(op)));
  }

  PStatic VisitExpr_(const TupleNode* op, LetList* ll) final {
    std::vector<PStatic> value;
    tvm::Array<Expr> expr;
    for (const Expr& e : op->fields) {
      PStatic ps = VisitExpr(e, ll);
      value.push_back(ps);
      expr.push_back(ps->dynamic);
    }
    return HasStatic(MkSTuple(value), ll->Push(TupleNode::make(expr)));
  }

  PStatic VisitExpr_(const TupleGetItemNode* op, LetList* ll) final {
    PStatic ps = VisitExpr(op->tuple, ll);
    if (ps->pstatic.defined()) {
      return Downcast<STuple>(ps->pstatic)->fields[op->index];
    } else {
      return NoStatic(ll->Push(TupleGetItemNode::make(ps->dynamic, op->index)));
    }
  }

  PStatic VisitExpr_(const VarNode* op, LetList* ll) final {
    return env_.Lookup(GetRef<Var>(op));
  }

647 648
  PStatic VisitGlobalVar(const GlobalVar& gv) {
    CHECK(mod_.defined());
雾雨魔理沙 committed
649
    if (gv_map_.count(gv) == 0) {
650 651 652 653
      Function func = mod_->Lookup(gv);
      InitializeFuncId(func);
      Func f = VisitFuncStatic(func, gv);
      gv_map_.insert({gv, HasStatic(MkSFunc(f), gv)});
654
      func = AsFunc(PostProcess(VisitFuncDynamic(func, f, gv)));
655
      mod_->Update(gv, func);
雾雨魔理沙 committed
656 657
    }
    return gv_map_.at(gv);
雾雨魔理沙 committed
658 659
  }

660 661 662 663
  PStatic VisitExpr_(const GlobalVarNode* op, LetList* ll) final {
    return VisitGlobalVar(GetRef<GlobalVar>(op));
  }

雾雨魔理沙 committed
664
  PStatic VisitExpr_(const LetNode* op, LetList* ll) final {
665
    env_.Insert(op->var, VisitExpr(op->value, ll, op->var));
雾雨魔理沙 committed
666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724
    return VisitExpr(op->body, ll);
  }

  PStatic VisitExpr_(const IfNode* op, LetList* ll) final {
    PStatic c = VisitExpr(op->cond, ll);
    if (c->pstatic.defined()) {
      NDArray cpu_array = Downcast<STensor>(c->pstatic)->data.CopyTo(CPUContext());
      CHECK_EQ(TVMType2Type(cpu_array->dtype), Bool());
      if (reinterpret_cast<uint8_t*>(cpu_array->data)[0]) {
        return VisitExpr(op->true_branch, ll);
      } else {
        return VisitExpr(op->false_branch, ll);
      }
    } else {
      Expr t = store_.Extend<Expr>([&]() {
          return LetList::With([&](LetList* ll) {
              return VisitExpr(op->true_branch, ll)->dynamic;
            });
        });
      Expr f = store_.Extend<Expr>([&]() {
          return LetList::With([&](LetList* ll) {
              return VisitExpr(op->false_branch, ll)->dynamic;
            });
        });
      store_.Invalidate();
      return NoStatic(ll->Push(IfNode::make(c->dynamic, t, f)));
    }
  }

  PStatic VisitExpr_(const RefCreateNode* op, LetList* ll) final {
    PStatic ps = VisitExpr(op->value, ll);
    Static r = MkSRef();
    store_.Insert(r.as<SRefNode>(), ps);
    return HasStatic(r, ll->Push(RefCreateNode::make(ps->dynamic)));
  }

  PStatic VisitExpr_(const RefWriteNode* op, LetList* ll) final {
    PStatic r = VisitExpr(op->ref, ll);
    PStatic v = VisitExpr(op->value, ll);
    if (r->pstatic.defined()) {
      store_.Insert(r->pstatic.as<SRefNode>(), v);
    } else {
      store_.Invalidate();
    }
    return HasStatic(MkSTuple({}), ll->Push(RefWriteNode::make(r->dynamic, v->dynamic)));
  }

  PStatic VisitExpr_(const RefReadNode* op, LetList* ll) final {
    PStatic r = VisitExpr(op->ref, ll);
    if (r->pstatic.defined()) {
      PStatic ret = store_.Lookup(r->pstatic.as<SRefNode>());
      if (ret) {
        return ret;
      }
    }
    return NoStatic(ll->Push(RefReadNode::make(r->dynamic)));
  }

  PStatic VisitExpr_(const CallNode* op, LetList* ll) final {
雾雨魔理沙 committed
725 726 727 728
    if (op->op.same_as(WithFuncIdOp())) {
      CHECK_EQ(op->args.size(), 1);
      return VisitExpr(op->args[0], ll);
    }
雾雨魔理沙 committed
729 730 731 732 733 734 735 736 737
    PStatic f = VisitExpr(op->op, ll);
    std::vector<PStatic> x;
    tvm::Array<Expr> x_dyn;
    for (const Expr& e : op->args) {
      PStatic ps = VisitExpr(e, ll);
      x.push_back(ps);
      x_dyn.push_back(ps->dynamic);
    }
    if (f->pstatic.defined()) {
738
      return Downcast<SFunc>(f->pstatic)->func(f, x, op->attrs, op->type_args, ll);
雾雨魔理沙 committed
739 740 741 742 743 744
    } else {
      store_.Invalidate();
      return NoStatic(ll->Push(CallNode::make(f->dynamic, x_dyn, op->attrs, op->type_args)));
    }
  }

745
  struct FuelFrame {
雾雨魔理沙 committed
746 747
    PartialEvaluator* pe_;
    FuncId fid_;
748 749
    Fuel old_fuel;
    FuelFrame(PartialEvaluator* pe,
雾雨魔理沙 committed
750
              FuncId fid,
751 752 753 754
              const Fuel& new_fuel) : pe_(pe), fid_(fid) {
      CHECK_GT(pe_->fuel_map_.count(fid_), 0);
      old_fuel = pe_->fuel_map_[fid_];
      pe_->fuel_map_[fid_] = new_fuel;
雾雨魔理沙 committed
755
    }
756 757
    ~FuelFrame() {
      pe_->fuel_map_[fid_] = old_fuel;
雾雨魔理沙 committed
758 759 760
    }
  };

761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784
  size_t GetFTValue(const PStatic& ps) {
    if (ps->pstatic.defined()) {
      if (auto* st = ps->pstatic.as<STensorNode>()) {
        if (st->data.Shape().empty()) {
          NDArray cpu_array = st->data.CopyTo(CPUContext());
          DataType dtype = TVMType2Type(cpu_array->dtype);
          if (dtype == Int(32)) {
            return std::max<int32_t>(0, *static_cast<const int32_t*>(cpu_array->data));
          } else if (dtype == Int(64)) {
            return std::max<int64_t>(0, *static_cast<const int64_t*>(cpu_array->data));
          }
        }
      }
    }
    return 0;
  }

  Fuel GetFuel(const PStatic& ps) {
    std::vector<Fuel> fuels;
    fuels.push_back(MkFTime(ps->created_time));
    fuels.push_back(MkFTValue(GetFTValue(ps)));
    return MkFSeq(fuels);
  }

雾雨魔理沙 committed
785 786
  Func VisitFuncStatic(const Function& func, const Expr& var) {
    CHECK(IsAtomic(var));
雾雨魔理沙 committed
787
    if (func->IsPrimitive()) {
雾雨魔理沙 committed
788
      return ConstEvaluateFunc(func);
雾雨魔理沙 committed
789 790
    }
    std::vector<std::pair<Var, PStatic> > free_vars;
雾雨魔理沙 committed
791
    for (const auto& v : FreeVars(func)) {
792 793 794
      if (v != var) {
        free_vars.push_back(std::pair<Var, PStatic>(v, env_.Lookup(v)));
      }
雾雨魔理沙 committed
795
    }
796 797
    return [=](const PStatic& self,
               const std::vector<PStatic>& pv,
雾雨魔理沙 committed
798 799 800
               const Attrs& attrs,
               const tvm::Array<Type>& type_args,
               LetList* ll) {
雾雨魔理沙 committed
801 802
      return env_.Extend<PStatic>([&]() {
          CHECK_EQ(pv.size(), func->params.size());
雾雨魔理沙 committed
803 804
          CHECK_GT(func_map_.count(func), 0);
          FuncId fid = func_map_.at(func);
805 806 807
          if (fuel_map_.count(fid) == 0) {
            fuel_map_.insert({fid, MkFTop()});
          }
808 809 810 811
          std::vector<Fuel> args_fuel;
          for (const auto& v : pv) {
            args_fuel.push_back(GetFuel(v));
          }
812 813 814
          auto meet_res = fuel_map_[fid]->Meet(MkFSeq(args_fuel));
          if (std::get<1>(meet_res)) {
            FuelFrame tf(this, fid, std::get<0>(meet_res));
815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832
            Expr dedup_func = RegisterFuncId(DeDup(AnnotateFuncId(func)));
            Function func = AsFunc(dedup_func);
            if (var.as<VarNode>()) {
              env_.Insert(Downcast<Var>(var), self);
            }
            for (size_t i = 0; i < pv.size(); ++i) {
              env_.Insert(func->params[i], pv[i]);
            }
            for (const auto& p : free_vars) {
              env_.Insert(p.first, p.second);
            }
            tvm::Map<TypeVar, Type> subst;
            for (size_t i = 0; i < type_args.size(); ++i) {
              subst.Set(func->type_params[i], type_args[i]);
            }
            for (size_t i = type_args.size(); i < func->type_params.size(); ++i) {
              subst.Set(func->type_params[i], IncompleteTypeNode::make(kType));
            }
雾雨魔理沙 committed
833 834
            return VisitExpr(RegisterFuncId(TypeSubst(AnnotateFuncId(func->body), subst)), ll);
          } else {
835 836 837
            std::vector<Expr> dyn;
            for (const auto& v : pv) {
              dyn.push_back(v->dynamic);
雾雨魔理沙 committed
838
            }
839
            return NoStatic(ll->Push(CallNode::make(var, dyn, attrs, type_args)));
雾雨魔理沙 committed
840
          }
雾雨魔理沙 committed
841 842
        });
    };
雾雨魔理沙 committed
843 844
  }

845
  Expr VisitFuncDynamic(const Function& func, const Func& f, const Expr& self) {
雾雨魔理沙 committed
846
    return store_.Extend<Expr>([&]() {
847 848 849 850 851 852 853 854 855 856 857
      store_.Invalidate();
      return FunctionNode::make(func->params,
                                LetList::With([&](LetList* ll) {
        std::vector<PStatic> pv;
        for (const auto& v : func->params) {
          pv.push_back(NoStatic(v));
        }
        tvm::Array<Type> type_args;
        for (const auto& tp : func->type_params) {
          type_args.push_back(tp);
        }
858
        return f(HasStatic(MkSFunc(f), self), pv, Attrs(), type_args, ll)->dynamic;
859 860
      }), func->ret_type, func->type_params, func->attrs);
    });
雾雨魔理沙 committed
861 862
  }

863 864 865 866
  PStatic VisitFunc(const Function& func,
                    LetList* ll,
                    const Var& name = VarNode::make("x", Type())) {
    Func f = VisitFuncStatic(func, name);
雾雨魔理沙 committed
867 868 869 870
    Function u_func = AsFunc(RegisterFuncId(DeDup(AnnotateFuncId(func))));
    // TODO(@M.K.): we seems to reduce landin knot into letrec.
    // restore letrec support across whole relay.
    return HasStatic(MkSFunc(f),
871
                     ll->Push(name, VisitFuncDynamic(u_func, f, name)));
雾雨魔理沙 committed
872 873 874 875
  }

  PStatic VisitExpr_(const FunctionNode* op, LetList* ll) final {
    return VisitFunc(GetRef<Function>(op), ll);
雾雨魔理沙 committed
876 877
  }

878 879 880 881
  struct ReflectError : dmlc::Error {
    ReflectError() : dmlc::Error("static value not found") { }
  };

雾雨魔理沙 committed
882
  Expr Reflect(const PStatic& st) {
883 884 885
    if (!st->pstatic.defined()) {
      throw ReflectError();
    } else if (const STensorNode* op = st->pstatic.as<STensorNode>()) {
雾雨魔理沙 committed
886 887 888 889 890 891 892 893
      return ConstantNode::make(op->data);
    } else if (const STupleNode* op = st->pstatic.as<STupleNode>()) {
      tvm::Array<Expr> fields;
      for (const PStatic& field : op->fields) {
        fields.push_back(Reflect(field));
      }
      return TupleNode::make(fields);
    } else {
894
      LOG(FATAL) << "Unknown case: " << st->dynamic;
雾雨魔理沙 committed
895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918
      throw;
    }
  }

  PStatic Reify(const Value& v, LetList* ll) const {
    if (const TensorValueNode* op = v.as<TensorValueNode>()) {
      return HasStatic(MkSTensor(op->data), ll->Push(ConstantNode::make(op->data)));
    } else if (const TupleValueNode* op = v.as<TupleValueNode>()) {
      std::vector<PStatic> fields;
      tvm::Array<Expr> fields_dyn;
      for (const Value& field : op->fields) {
        PStatic ps = Reify(field, ll);
        fields.push_back(ps);
        fields_dyn.push_back(ps->dynamic);
      }
      return HasStatic(MkSTuple(fields), ll->Push(TupleNode::make(fields_dyn)));
    } else {
      LOG(FATAL) << "Unknown case";
      throw;
    }
  }

  // Constant evaluate a expression.
  PStatic ConstEvaluate(const Expr& expr, LetList* ll) {
Zhi committed
919 920 921 922 923
    std::vector<transform::Pass> passes = {transform::FuseOps(0),
                                           transform::InferType()};
    auto mod = ModuleNode::FromExpr(expr);
    auto seq = transform::Sequential(passes);
    mod = seq(mod);
924
    auto entry_func = mod->Lookup("main");
Zhi committed
925 926
    auto fused_infered =
        expr.as<FunctionNode>() == nullptr ? entry_func->body : entry_func;
雾雨魔理沙 committed
927 928 929
    return Reify(executor_(fused_infered), ll);
  }

雾雨魔理沙 committed
930 931
  Func ConstEvaluateFunc(const Expr& expr) {
    CHECK_EQ(FreeVars(expr).size(), 0);
932 933
    return [=](const PStatic& self,
               const std::vector<PStatic>& pv,
雾雨魔理沙 committed
934 935 936 937 938 939 940
               const Attrs& attrs,
               const tvm::Array<Type>& type_args,
               LetList* ll) {
      tvm::Array<Expr> ns_args;
      for (const PStatic& ps : pv) {
        ns_args.push_back(ps->dynamic);
      }
941 942 943
      auto ns = [&]() {
        return NoStatic(ll->Push(CallNode::make(expr, ns_args, attrs, type_args)));
      };
雾雨魔理沙 committed
944
      if (StatefulOp(expr)) {
945
        return ns();
雾雨魔理沙 committed
946
      }
947 948 949
      try {
        tvm::Array<Expr> args;
        for (const PStatic& ps : pv) {
雾雨魔理沙 committed
950 951
          args.push_back(Reflect(ps));
        }
952 953 954 955
        return ConstEvaluate(CallNode::make(expr, args, attrs, type_args), ll);
      }
      catch (const ReflectError&) {
        return ns();
雾雨魔理沙 committed
956 957 958 959 960
      }
    };
  }

  PStatic VisitExpr_(const OpNode* op, LetList* ll) final {
雾雨魔理沙 committed
961
    return HasStatic(MkSFunc(ConstEvaluateFunc(GetRef<Expr>(op))), GetRef<Expr>(op));
雾雨魔理沙 committed
962 963 964 965
  }

  PStatic VisitExpr_(const ConstructorNode* op, LetList* ll) final {
    Constructor c = GetRef<Constructor>(op);
966 967
    Func f = [=](const PStatic& self,
                 const std::vector<PStatic>& pv,
雾雨魔理沙 committed
968 969 970 971 972 973 974 975 976 977 978 979 980 981 982
                 const Attrs& attrs,
                 const tvm::Array<Type>& type_args,
                 LetList* ll) {
      tvm::Array<Expr> dyn;
      for (const PStatic& ps : pv) {
        dyn.push_back(ps->dynamic);
      }
      return HasStatic(MkSConstructor(c, pv), ll->Push(CallNode::make(c, dyn)));
    };
    return HasStatic(MkSFunc(f), GetRef<Expr>(op));
  }

  PStatic VisitExpr_(const MatchNode* op, LetList* ll) final {
    PStatic ps = VisitExpr(op->data, ll);
    return env_.Extend<PStatic>([&]() {
983 984 985 986 987 988 989 990
      for (const Clause& c : op->clauses) {
        switch (VisitPattern(c->lhs, ps)) {
        case MatchStatus::Match:
          return VisitExpr(c->rhs, ll);
        case MatchStatus::NoMatch:
          continue;
        case MatchStatus::Unknown:
          return [&]() {
雾雨魔理沙 committed
991 992 993
            tvm::Array<Clause> clauses;
            for (const Clause& c : op->clauses) {
              Expr expr = store_.Extend<Expr>([&]() {
994 995 996 997 998
                return LetList::With([&](LetList* ll) {
                  for (const Var& v : BoundVars(c->lhs)) {
                    env_.Insert(v, NoStatic(v));
                  }
                  return VisitExpr(c->rhs, ll)->dynamic;
雾雨魔理沙 committed
999
                });
1000
              });
雾雨魔理沙 committed
1001 1002 1003
              clauses.push_back(ClauseNode::make(c->lhs, expr));
            }
            store_.Invalidate();
1004
            return NoStatic(ll->Push(MatchNode::make(ps->dynamic, clauses, op->complete)));
1005 1006 1007 1008
          }();
        default:
          LOG(FATAL) << "Unknown MatchStatus";
          throw;
雾雨魔理沙 committed
1009
        }
1010 1011 1012 1013
      }
      LOG(FATAL) << "No case Match";
      throw;
    });
雾雨魔理沙 committed
1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051
  }

  MatchStatus VisitPattern_(const PatternWildcardNode* op, const PStatic& ps) final {
    return MatchStatus::Match;
  }

  MatchStatus VisitPattern_(const PatternVarNode* op, const PStatic& ps) final {
    env_.Insert(op->var, ps);
    return MatchStatus::Match;
  }

  MatchStatus VisitPattern_(const PatternConstructorNode* op, const PStatic& ps) final {
    if (ps->pstatic.defined()) {
      SConstructor scn = Downcast<SConstructor>(ps->pstatic);
      CHECK_NE(op->constructor->tag, -1);
      CHECK_NE(scn->constructor->tag, -1);
      if (op->constructor->tag == scn->constructor->tag) {
        CHECK_EQ(op->patterns.size(), scn->fields.size());
        MatchStatus current_match_status = MatchStatus::Match;
        for (size_t i = 0; i < op->patterns.size(); ++i) {
          MatchStatus ms = VisitPattern(op->patterns[i], scn->fields[i]);
          switch (ms) {
          case MatchStatus::Match:
            continue;
          case MatchStatus::NoMatch:
            return MatchStatus::NoMatch;
          case MatchStatus::Unknown:
            current_match_status = MatchStatus::Unknown;
          }
        }
        return current_match_status;
      }
      return MatchStatus::NoMatch;
    } else {
      return MatchStatus::Unknown;
    }
  }

1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073
  MatchStatus VisitPattern_(const PatternTupleNode* op, const PStatic& ps) final {
    if (ps->pstatic.defined()) {
      STuple stn = Downcast<STuple>(ps->pstatic);
      CHECK_EQ(op->patterns.size(), stn->fields.size());
      MatchStatus current_match_status = MatchStatus::Match;
      for (size_t i = 0; i < op->patterns.size(); ++i) {
        MatchStatus ms = VisitPattern(op->patterns[i], stn->fields[i]);
        switch (ms) {
        case MatchStatus::Match:
          continue;
        case MatchStatus::NoMatch:
          return MatchStatus::NoMatch;
        case MatchStatus::Unknown:
          current_match_status = MatchStatus::Unknown;
        }
      }
      return current_match_status;
    } else {
      return MatchStatus::Unknown;
    }
  }

雾雨魔理沙 committed
1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148
  void InitializeFuncId(const Expr& e) {
    struct InitializeFuncIdVisitor : ExprVisitor, PatternVisitor {
      PartialEvaluator* pe;
      explicit InitializeFuncIdVisitor(PartialEvaluator* pe) : pe(pe) { }

      void VisitExpr_(const FunctionNode* op) final {
        Function f = GetRef<Function>(op);
        CHECK_EQ(pe->func_map_.count(f), 0);
        pe->func_map_.insert({f, pe->func_map_.size()});
        VisitExpr(f->body);
      }

      void VisitPattern(const Pattern& p) final {
        PatternVisitor::VisitPattern(p);
      }
    };
    InitializeFuncIdVisitor(this).VisitExpr(e);
  }

  Expr RegisterFuncId(const Expr& e) {
    struct RegisterFuncIdVisitor : ExprVisitor, PatternVisitor {
      PartialEvaluator* pe;
      explicit RegisterFuncIdVisitor(PartialEvaluator* pe) : pe(pe) { }

      void VisitExpr_(const CallNode* op) final {
        if (op->op.same_as(WithFuncIdOp())) {
          CHECK_EQ(op->args.size(), 1);
          CHECK(op->attrs.defined());
          CHECK(op->attrs.as<WithFuncIdAttrs>());
          Function f = AsFunc(op->args[0]);
          FuncId fid = op->attrs.as<WithFuncIdAttrs>()->fid;
          if (pe->func_map_.count(f) != 0) {
            CHECK_EQ(pe->func_map_.at(f), fid);
          }
          pe->func_map_.insert({f, fid});
        }
        ExprVisitor::VisitExpr_(op);
      }

      void VisitExpr_(const FunctionNode* op) final {
        Function f = GetRef<Function>(op);
        CHECK_GT(pe->func_map_.count(f), 0);
        ExprVisitor::VisitExpr_(op);
      }

      void VisitPattern(const Pattern& p) final {
        PatternVisitor::VisitPattern(p);
      }
    };
    RegisterFuncIdVisitor(this).VisitExpr(e);
    return e;
  }

  Expr AnnotateFuncId(const Expr& e) {
    struct AnnotateFuncIdMutator : ExprMutator, PatternMutator {
      PartialEvaluator* pe;
      explicit AnnotateFuncIdMutator(PartialEvaluator* pe) : pe(pe) { }

      Expr VisitExpr_(const FunctionNode* op) final {
        Function f = GetRef<Function>(op);
        CHECK_GT(pe->func_map_.count(f), 0);
        return MkWithFuncId(ExprMutator::VisitExpr_(op), pe->func_map_.at(f));
      }

      Pattern VisitPattern(const Pattern& p) final {
        return PatternMutator::VisitPattern(p);
      }

      Var VisitVar(const Var& v) final {
        return v;
      }
    };
    return AnnotateFuncIdMutator(this).VisitExpr(e);
  }

雾雨魔理沙 committed
1149 1150
 private:
  Environment env_;
雾雨魔理沙 committed
1151 1152 1153 1154 1155 1156
  Module mod_;
  std::unordered_map<GlobalVar, PStatic, NodeHash, NodeEqual> gv_map_;
  /*! Termination checking is done as follows:
   *  We have finitely many FunctionIds.
   *  Each FunctionId maps to a class of semantically equivalent function (ignoring type),
   *  as both TypeSubst and DeDup create semantically equivalent function.
1157
   *  We partially map each FunctionId to a Fuel.
雾雨魔理沙 committed
1158
   *  Every time we try to inline a Function,
1159 1160 1161 1162
   *  we make sure it either does not have a Fuel,
   *  or we meet the existing fuel with the fuel calculated from the argument.
   *  If no progress is made, we do not inline.
   *  In both case, we remap the mapping to the new Fuel
雾雨魔理沙 committed
1163
   *  when we PE inside the Function body.
1164
   *  Termination is guaranteed because Fuel is finitely descending - there can only be so many meet.
雾雨魔理沙 committed
1165 1166
   */
  std::unordered_map<Function, FuncId, NodeHash, NodeEqual> func_map_;
1167
  std::unordered_map<FuncId, Fuel> fuel_map_;
雾雨魔理沙 committed
1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193
  Store store_;
  DLContext context_ = CPUContext();
  FInterpreter executor_ = CPUInterpreter();
};

/*! \brief Remap multiple Var sharing the same Id into the same Var. */
Expr Remap(const Expr& e) {
  class RemapMutator : public ExprMutator, public PatternMutator {
    Expr VisitExpr_(const VarNode* op) final {
      Var v = GetRef<Var>(op);
      if (remap_.count(v) == 0) {
        remap_.insert({v, v});
      }
      return remap_.at(v);
    }

    Var VisitVar(const Var& v) final {
      return Downcast<Var>(VisitExpr(v));
    }

   private:
    std::unordered_map<Var, Var, VarHash, VarEqual> remap_;
  };
  return RemapMutator().VisitExpr(e);
}

雾雨魔理沙 committed
1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219
Expr StripWithFuncId(const Expr& e) {
  struct StripWithFuncIdMutator : ExprMutator, PatternMutator {
    Expr VisitExpr_(const CallNode* op) final {
      if (op->op.same_as(WithFuncIdOp())) {
        CHECK_EQ(op->args.size(), 1);
        return VisitExpr(op->args[0]);
      } else {
        return ExprMutator::VisitExpr_(op);
      }
    }

    Pattern VisitPattern(const Pattern& p) final {
      return PatternMutator::VisitPattern(p);
    }

    Var VisitVar(const Var& v) final {
      return v;
    }
  };
  return StripWithFuncIdMutator().VisitExpr(e);
}

Expr PostProcess(const Expr& e) {
  return StripWithFuncId(DeDup(Remap(e)));
}

1220 1221
}  // namespace partial_eval

1222
Module PartialEval(const Module& m) {
1223 1224 1225 1226 1227 1228 1229 1230
  relay::partial_eval::PartialEvaluator pe(m);
  std::vector<GlobalVar> gvs;
  for (const auto& p : m->functions) {
    gvs.push_back(p.first);
  }
  for (const auto& gv : gvs) {
    pe.VisitGlobalVar(gv);
  }
1231
  return m;
雾雨魔理沙 committed
1232 1233
}

1234 1235 1236
namespace transform {

Pass PartialEval() {
1237 1238 1239
  runtime::TypedPackedFunc<Module(Module, PassContext)> pass_func =
    [=](Module m, PassContext pc) {
    return PartialEval(m);
1240
  };
1241
  return CreateModulePass(pass_func, 1, "PartialEvaluate", {});
1242 1243
}

1244 1245 1246
TVM_REGISTER_API("relay._transform.PartialEvaluate")
.set_body_typed(PartialEval);

1247 1248
}  // namespace transform

雾雨魔理沙 committed
1249 1250
}  // namespace relay
}  // namespace tvm