storage_rewrite.cc 31.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
/*!
 * Copyright (c) 2017 by Contributors
 * \file storage_rewrite.cc
 * \brief Memory access pattern analysis and optimization.
 *  Re-write data access to enable memory sharing when possible.
 */
#include <tvm/ir.h>
#include <tvm/ir_pass.h>
#include <tvm/ir_mutator.h>
#include <tvm/ir_visitor.h>
11
#include <tvm/target_info.h>
12 13 14 15
#include <map>
#include <unordered_set>
#include <unordered_map>
#include "./ir_util.h"
16
#include "../arithmetic/compute_expr.h"
17
#include "../runtime/thread_storage_scope.h"
18 19 20 21

namespace tvm {
namespace ir {

22 23
using runtime::StorageScope;

24
// Find a linear pattern of storage acess
25
// Used for liveness analysis.
26 27 28 29 30 31 32 33 34 35 36 37
// Composite scopes(loop/thread_launch/IfThen) is represented by two points:
// before_scope -> scope_body -> after_scope
//
// The linear_seq_ stores before_scope and after_scope.
// The access to the arrays are stored at the after_scope point.
//
// Define "scope" as the body of For/thread_launch/IfThenElse
// This pass tries to detect last point that we need to keep memory
// alive under the same scope as allocate.
// The storage need to be kept alive between allocate and last access.
// The free point is only inserted at the same scope of allocate.
//
38
class LinearAccessPatternFinder final : public IRVisitor {
39
 public:
40 41 42 43
  /*! \brief record the touch hist of statment. */
  struct StmtEntry {
    // The statment
    const Node* stmt;
44 45 46 47 48
    // The index in the linear_seq_ to point to end of the nested scope.
    // This is only set to non-zero if stmt is a nested scope.
    // if offset > 0, means this is the begin, the end entry is current_index + offset
    // if offset < 0, means this is the end, the begin entry is current_index + offset
    int64_t scope_pair_offset{0};
49 50 51
    // The buffer variables this statment touched.
    std::vector<const Variable*> touched;
  };
52 53 54 55 56 57 58 59 60
  // The scope of each allocation
  struct AllocEntry {
    // Scope used for allocation.
    StorageScope storage_scope;
    // scope level
    size_t level{0};
    // allocation stmt
    const Allocate* alloc{nullptr};
  };
61

62 63 64
  void Visit_(const Allocate* op) final {
    size_t level = scope_.size();
    const Variable* buf = op->buffer_var.get();
65 66 67 68 69
    auto it = alloc_info_.find(buf);
    CHECK(it != alloc_info_.end());
    CHECK(it->second.alloc == nullptr);
    it->second.alloc = op;
    it->second.level = level;
70 71 72 73 74 75 76 77
    IRVisitor::Visit_(op);
  }
  void Visit_(const Store* op) final {
    scope_.push_back(StmtEntry());
    // visit subexpr
    IRVisitor::Visit_(op);
    // Add write access.
    const Variable* buf = op->buffer_var.get();
78 79 80 81
    auto it = alloc_info_.find(buf);
    if (it != alloc_info_.end() && it->second.alloc) {
      CHECK_LT(it->second.level, scope_.size());
      scope_[it->second.level].touched.push_back(buf);
82 83 84
    }
    StmtEntry e = scope_.back();
    scope_.pop_back();
85
    if (e.touched.size() != 0) {
86 87 88 89
      e.stmt = op;
      linear_seq_.push_back(e);
    }
  }
90 91 92 93 94 95
  void Visit_(const Evaluate* op) final {
    scope_.push_back(StmtEntry());
    // visit subexpr
    IRVisitor::Visit_(op);
    StmtEntry e = scope_.back();
    scope_.pop_back();
96
    if (e.touched.size() != 0) {
97 98 99 100
      e.stmt = op;
      linear_seq_.push_back(e);
    }
  }
101 102 103 104
  void Visit_(const Load* op) final {
    // Add write access.
    IRVisitor::Visit_(op);
    const Variable* buf = op->buffer_var.get();
105 106 107
    auto it = alloc_info_.find(buf);
    if (it != alloc_info_.end() && it->second.alloc) {
      CHECK_LT(it->second.level, scope_.size())
108
          << "Load memory in places other than store.";
109
      scope_[it->second.level].touched.push_back(buf);
110 111
    }
  }
112 113 114 115 116 117 118 119
  void Visit_(const Call* op) final {
    if (op->is_intrinsic(intrinsic::tvm_address_of)) {
      const Load* l = op->args[0].as<Load>();
      this->Visit(l->index);
    } else {
      IRVisitor::Visit_(op);
    }
  }
120 121
  void Visit_(const Variable* buf) final {
    // Directly reference to the variable count as a read.
122 123 124 125 126
    auto it = alloc_info_.find(buf);
    if (it != alloc_info_.end() && it->second.alloc) {
      CHECK_LT(it->second.level, scope_.size())
          << " buf=" << buf->name_hint;
      scope_[it->second.level].touched.push_back(buf);
127 128 129 130 131 132 133
    }
  }
  template<typename T>
  void VisitNewScope(const T* op) {
    scope_.push_back(StmtEntry());
    StmtEntry e;
    e.stmt = op;
134
    int64_t begin_index =  static_cast<int64_t>(linear_seq_.size());
135 136 137 138
    // before scope.
    linear_seq_.push_back(e);
    IRVisitor::Visit_(op);
    // after scope.
139
    e.touched = std::move(scope_.back().touched);
140
    scope_.pop_back();
141 142 143
    int64_t end_index =  static_cast<int64_t>(linear_seq_.size());
    CHECK_GT(end_index, begin_index);
    e.scope_pair_offset = begin_index - end_index;
144
    linear_seq_.push_back(e);
145 146 147
    // record the pointer to end index.
    CHECK_NE(end_index, 0U);
    linear_seq_[begin_index].scope_pair_offset = end_index - begin_index;
148 149 150 151 152 153 154
  }
  void Visit_(const AttrStmt* op) final {
    // Only record the outer most thread extent.
    if (op->attr_key == attr::thread_extent && !in_thread_env_) {
      in_thread_env_ = true;
      VisitNewScope(op);
      in_thread_env_ = false;
155 156
    } else if (op->attr_key == attr::extern_scope) {
      VisitNewScope(op);
157 158
    } else if (op->attr_key == attr::storage_scope) {
      const Variable* buf = op->node.as<Variable>();
159
      alloc_info_[buf].storage_scope =
160 161 162 163 164 165 166 167 168 169
          StorageScope::make(op->value.as<StringImm>()->value);
      IRVisitor::Visit_(op);
    } else {
      IRVisitor::Visit_(op);
    }
  }
  void Visit_(const IfThenElse* op) final {
    VisitNewScope(op);
  }

170 171 172 173
  void Visit_(const For* op) final {
    VisitNewScope(op);
  }

174 175 176 177 178
  // linearized access sequence.
  std::vector<StmtEntry> linear_seq_;
  // The storage scope of each buffer
  std::unordered_map<const Variable*, AllocEntry> alloc_info_;

179 180 181 182 183
 private:
  // Whether already in thread env.
  bool in_thread_env_{false};
  // The scope stack.
  std::vector<StmtEntry> scope_;
184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 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 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
};

// Verify if the statement can be run safely via inplace fashion
//
// Detect pattern: dst[index] = f(src[index])
//
// WARNING: the current detection algorithm cannot handle the case
// when a location in an array is written multiple times
//
// For example, the following program will pass the check,
// but we cannot make A and B to be the same array.
//
//  A[0] = B[0] + 1
//  A[0] = B[0] + 1
//
// The high level code generator needs to ensure that the generated
// code only write each location of the target array once.
//
// This is the case with IR generated by the current compute schedule.
// We explicitly return false if we find there is an extern block
// which can be arbitrary IR.
//
// Neve-the-less, inplace detector should be used with care in mind.
// We may also consider introduce a condition checker that checks
// if every index only visited once for an absolute sufficient condition.
//
// The code after inplace transformation is no longer idempotent.
//
class InplaceOpVerifier : public IRVisitor {
 public:
  bool Check(const Node* stmt,
             const Variable* dst,
             const Variable* src) {
    dst_ = dst;
    src_ = src;
    result_ = true;
    if (stmt->is_type<AttrStmt>()) {
      Visit_(static_cast<const AttrStmt*>(stmt));
    } else if (stmt->is_type<For>()) {
      Visit_(static_cast<const For*>(stmt));
    } else if (stmt->is_type<IfThenElse>()) {
      Visit_(static_cast<const IfThenElse*>(stmt));
    } else if (stmt->is_type<Store>()) {
      Visit_(static_cast<const Store*>(stmt));
    } else {
      return false;
    }
    return result_;
  }

  using IRVisitor::Visit_;

  void Visit(const NodeRef& e) final {
    if (!result_) return;
    IRVisitor::Visit(e);
  }

  void Visit_(const Variable* op) final {
    // assume all opaque access is unsafe
    if (op == dst_ || op == src_) {
      result_ = false; return;
    }
  }

  void Visit_(const Store* op) final {
    ++mem_nest_;
    this->Visit(op->index);
    --mem_nest_;
    if (op->buffer_var.get() == dst_) {
      store_ = op;
      this->Visit(op->value);
      this->Visit(op->predicate);
      store_ = nullptr;
    } else {
      this->Visit(op->value);
      this->Visit(op->predicate);
    }
  }

  void Visit_(const AttrStmt* op) final {
    // always reject extern code
    if (op->attr_key == attr::extern_scope ||
        op->attr_key == attr::volatile_scope) {
      result_ = false; return;
    }
    IRVisitor::Visit_(op);
  }

  void Visit_(const Load* op) final {
    const Variable* buf = op->buffer_var.get();
    // cannot read from dst_ (no reduction)
    if (buf == dst_) {
      result_ = false; return;
    }
    // do not allow indirect memory load
    if (mem_nest_ != 0) {
      result_ = false; return;
    }
    if (src_ == buf) {
      if (store_ == nullptr ||
          store_->value.type() != op->type ||
          !ir::Equal(store_->index, op->index)) {
        result_ = false; return;
      }
    }
    ++mem_nest_;
    IRVisitor::Visit_(op);
    --mem_nest_;
  }


 private:
  // result of the check
  bool result_{true};
  // destination memory
  const Variable* dst_;
  // source variable
  const Variable* src_;
  // counter of load,
  // it is not safe to inplace when there is nested load like A[B[i]]
  int mem_nest_{0};
  // The current store to be inspected
  const Store* store_{nullptr};
307 308 309 310 311
};

// Planner to plan and rewrite memory allocation.
class StoragePlanRewriter : public IRMutator {
 public:
312
  using StmtEntry = LinearAccessPatternFinder::StmtEntry;
313
  using AllocEntry = LinearAccessPatternFinder::AllocEntry;
314

315 316 317 318 319 320 321
  Stmt Rewrite(Stmt stmt, bool detect_inplace) {
    detect_inplace_ = detect_inplace;
    // plan the rewrite
    LinearAccessPatternFinder finder;
    finder.Visit(stmt);
    this->LivenessAnalysis(finder.linear_seq_);
    this->PlanMemory(finder.linear_seq_, finder.alloc_info_);
322
    this->PrepareNewAlloc();
323
    // start rewrite
324 325 326 327
    stmt = this->Mutate(stmt);
    if (attach_map_.count(nullptr)) {
      std::vector<Stmt> nest;
      for (StorageEntry* e : attach_map_.at(nullptr)) {
328
        // CHECK_EQ(e->scope.rank, 0);
329 330 331 332 333 334 335
        if (e->new_alloc.defined()) {
          nest.emplace_back(AttrStmt::make(
              e->alloc_var, attr::storage_scope,
              StringImm::make(e->scope.to_string()),
              Evaluate::make(0)));
          nest.push_back(e->new_alloc);
        }
336 337 338 339 340 341 342 343 344 345
      }
      stmt = MergeNest(nest, stmt);
    }
    return stmt;
  }
  Stmt Mutate_(const Store* op, const Stmt& s) final {
    Stmt stmt = IRMutator::Mutate_(op, s);
    op = stmt.as<Store>();
    auto it = alloc_map_.find(op->buffer_var.get());
    if (it == alloc_map_.end()) return stmt;
346 347 348 349
    return Store::make(it->second->alloc_var,
                       op->value,
                       RemapIndex(op->value.type(), op->index, it->second),
                       op->predicate);
350 351 352 353 354 355
  }
  Expr Mutate_(const Load* op, const Expr& e) final {
    Expr expr = IRMutator::Mutate_(op, e);
    op = expr.as<Load>();
    auto it = alloc_map_.find(op->buffer_var.get());
    if (it == alloc_map_.end()) return expr;
356 357 358 359
    return Load::make(op->type,
                      it->second->alloc_var,
                      RemapIndex(op->type, op->index, it->second),
                      op->predicate);
360 361 362 363
  }
  Expr Mutate_(const Variable* op, const Expr& e) final {
    auto it = alloc_map_.find(op);
    if (it != alloc_map_.end()) {
364 365 366
      if (it->second->elem_offset != 0) {
        LOG(WARNING) << "Use a merged buffer variable address, could cause error";
      }
367 368 369 370 371
      return it->second->alloc_var;
    } else {
      return e;
    }
  }
372 373 374 375 376 377 378
  Expr Mutate_(const Call* op, const Expr& e) final {
    if (op->is_intrinsic(intrinsic::tvm_access_ptr)) {
      CHECK_EQ(op->args.size(), 5U);
      Type dtype = op->args[0].type();
      const Variable* buffer = op->args[1].as<Variable>();
      auto it = alloc_map_.find(buffer);
       if (it == alloc_map_.end()) return IRMutator::Mutate_(op, e);
379
       const StorageEntry* se = it->second;
380 381
       Expr offset = Mutate(op->args[2]);
       Expr extent = Mutate(op->args[3]);
382 383 384 385 386
       CHECK_EQ(se->elem_type, dtype.element_of())
           << " buffer=" << buffer->name_hint;
       CHECK_EQ(se->elem_offset % dtype.lanes(), 0);
       if (se->elem_offset != 0) {
         offset = make_const(offset.type(), se->elem_offset / dtype.lanes()) + offset;
387 388 389
       }
       return Call::make(
           op->type, op->name,
390
           {op->args[0], se->alloc_var, offset, extent, op->args[4]},
391 392 393 394 395
           op->call_type);
    } else {
      return IRMutator::Mutate_(op, e);
    }
  }
396

397 398 399 400 401
  Stmt Mutate_(const AttrStmt* op, const Stmt& s) final {
    CHECK(op->attr_key != attr::virtual_thread)
        << "InjectVirtualThread before StoragePlan";
    if (op->attr_key == attr::storage_scope) {
      return this->Mutate(op->body);
402 403 404
    } else if (op->attr_key == attr::thread_extent ||
               op->attr_key == attr::pragma_scope) {
      // remake all the allocation at the attach scope.
405
      if (attach_map_.count(op)) {
406
        auto& svec = attach_map_[op];
407 408 409
        Stmt stmt = IRMutator::Mutate_(op, s);
        op = stmt.as<AttrStmt>();
        return AttrStmt::make(
410 411
            op->node, op->attr_key, op->value,
            MakeAttach(svec, op->body));
412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428
      } else {
        return IRMutator::Mutate_(op, s);
      }
    } else if (op->attr_key == attr::volatile_scope) {
      Stmt stmt = IRMutator::Mutate_(op, s);
      op = stmt.as<AttrStmt>();
      auto it = alloc_map_.find(op->node.as<Variable>());
      if (it == alloc_map_.end()) return stmt;
      return AttrStmt::make(
          it->second->alloc_var, op->attr_key, op->value, op->body);
    } else {
      return IRMutator::Mutate_(op, s);
    }
  }
  Stmt Mutate_(const For* op, const Stmt& s) final {
    CHECK(op->for_type != ForType::Vectorized)
        << "VectorizeLoop before LiftStorageAlloc";
429 430 431 432 433 434 435 436 437 438 439
    // remake all the allocation at the attach scope.
    if (attach_map_.count(op)) {
      auto& svec = attach_map_[op];
      Stmt stmt = IRMutator::Mutate_(op, s);
      op = stmt.as<For>();
      return For::make(
          op->loop_var, op->min, op->extent, op->for_type, op->device_api,
          MakeAttach(svec, op->body));
    } else {
      return IRMutator::Mutate_(op, s);
    }
440
  }
441

442 443 444 445 446 447 448 449 450 451
  Stmt Mutate_(const Allocate* op, const Stmt& s) final {
    return this->Mutate(op->body);
  }

 private:
  struct StorageEntry {
    // The scope that this alloc attaches after
    // For shared/local memory it is beginning of the thread extent.
    // for global memory it is nullptr, means beginning of everything.
    const Node* attach_scope_{nullptr};
452
    // The constant size of the buffer in bits, only used if it is constant
453
    uint64_t const_nbits{0};
454 455 456 457
    // The storage scope.
    StorageScope scope;
    // Allocs that shares this entry.
    std::vector<const Allocate*> allocs;
458 459 460 461
    // The children of this entry, not including itself.
    std::vector<StorageEntry*> merged_children;
    // The replacement allocation, if any.
    Stmt new_alloc;
462 463
    // The var expr of new allocation.
    VarExpr alloc_var;
464 465 466 467
    // The allocation element type.
    Type elem_type;
    // This is non-zero if this allocate is folded into another one
    // the address becomes alloc_var + sizeof(elem_type) * elem_offset;
468
    uint64_t elem_offset{0};
469
  };
470 471 472 473 474 475 476 477 478 479

  // Alllocate entry of node.
  // Event entry in liveness analysis
  struct EventEntry {
    // variables we generate
    std::vector<const Variable*> gen;
    // variables we kill
    std::vector<const Variable*> kill;
  };

480 481 482 483 484 485 486 487 488 489 490 491
  Stmt MakeAttach(const std::vector<StorageEntry*>& svec,
                  Stmt body) {
    std::vector<Stmt> nest;
    for (StorageEntry* e : svec) {
      nest.emplace_back(AttrStmt::make(
          e->alloc_var, attr::storage_scope,
          StringImm::make(e->scope.to_string()),
          Evaluate::make(0)));
      nest.push_back(e->new_alloc);
    }
    return MergeNest(nest, body);
  }
492 493 494 495 496 497
  // Remap the index
  Expr RemapIndex(Type dtype, Expr index, StorageEntry* e) {
    CHECK_EQ(dtype.element_of(), e->elem_type);
    if (e->elem_offset == 0) return index;
    return make_const(index.type(), e->elem_offset) + index;
  }
498 499 500 501
  // Prepare the new allocations
  void PrepareNewAlloc() {
    for (size_t i = 0; i < alloc_vec_.size(); ++i) {
      StorageEntry* e = alloc_vec_[i].get();
502 503 504 505
      attach_map_[e->attach_scope_].push_back(e);
    }
    // find allocation via attach map.
    for (auto &kv : attach_map_) {
506
      // find the element with the most amount of bytes.
507 508 509 510 511 512 513 514 515 516 517 518 519
      std::vector<StorageEntry*>& vec = kv.second;
      // try to find merge, for tagged memory
      for (size_t i = 0; i < vec.size(); ++i) {
        StorageEntry* e = vec[i];
        if (e->scope.tag.length() != 0) {
          CHECK_NE(e->const_nbits, 0U)
              << "Special tagged memory must be const size";
          for (size_t j = 0; j < i; ++j) {
            if (e->scope == vec[j]->scope) {
              vec[j]->merged_children.push_back(e);
              break;
            }
          }
520 521
        }
      }
522 523 524 525 526 527 528 529 530 531 532
      // Start allocation
      for (size_t i = 0; i < vec.size(); ++i) {
        StorageEntry* e = vec[i];
        // already merged
        if (e->elem_offset != 0) continue;
        if (e->merged_children.size() != 0) {
          NewAllocTagMerged(e); continue;
        }
        // Get the allocation size;
        e->alloc_var = e->allocs[0]->buffer_var;
        Type alloc_type = e->allocs[0]->type;
533
        for (const Allocate* op : e->allocs) {
534 535
          if (op->type.lanes() > alloc_type.lanes()) {
            alloc_type = op->type;
536
          }
537 538 539 540 541 542
        }
        if (e->allocs.size() == 1) {
          // simply use the original allocation.
          e->new_alloc = Allocate::make(
              e->alloc_var, alloc_type, e->allocs[0]->extents,
              e->allocs[0]->condition, Evaluate::make(0));
543 544 545 546 547 548
          if (e->scope.tag.length() != 0) {
            MemoryInfo info = GetMemoryInfo(e->scope.to_string());
            uint64_t total_elem = e->const_nbits / e->elem_type.bits();
            CHECK_LE(total_elem * e->elem_type.bits(), info->max_num_bits)
                << "Allocation exceed bound of memory tag " << e->scope.to_string();
          }
549 550 551 552
        } else {
          // Build a merged allocation
          Expr combo_size;
          for (const Allocate* op : e->allocs) {
553
            Expr sz = arith::ComputeReduce<Mul>(op->extents, make_const(Int(32), 1));
554 555 556 557 558 559 560 561 562 563
            if (alloc_type.lanes() != op->type.lanes()) {
              sz = (sz * make_const(sz.type(), op->type.lanes()) +
                    make_const(sz.type(), alloc_type.lanes() - 1)) /
                  make_const(sz.type(), alloc_type.lanes());
            }
            if (combo_size.defined()) {
              combo_size = max(combo_size, sz);
            } else {
              combo_size = sz;
            }
564
          }
565 566 567 568
          combo_size = ir::Simplify(combo_size);
          e->new_alloc = Allocate::make(
              e->alloc_var, alloc_type, {combo_size}, const_true(),
              Evaluate::make(0));
569 570
        }
      }
571 572 573 574 575 576 577 578 579 580 581 582
    }
  }
  // New allocation for merged data
  void NewAllocTagMerged(StorageEntry* e) {
    CHECK_NE(e->scope.tag.length(), 0U);
    // allocate with element type.
    CHECK_NE(e->const_nbits, 0U);
    MemoryInfo info = GetMemoryInfo(e->scope.to_string());
    size_t align = 1;
    if (info.defined()) {
      align = (info->max_simd_bits + e->elem_type.bits() - 1) / e->elem_type.bits();
    }
583
    uint64_t total_elem = e->const_nbits / e->elem_type.bits();
584 585 586 587 588 589 590 591 592 593 594 595 596 597 598
    if (total_elem % align != 0) {
      total_elem += align  - (total_elem % align);
    }
    e->alloc_var = e->allocs[0]->buffer_var;
    for (StorageEntry* child : e->merged_children) {
      CHECK_NE(e->const_nbits, 0U);
      CHECK_NE(total_elem, 0U);
      size_t num_elem = child->const_nbits / child->elem_type.bits();
      child->elem_offset = total_elem;
      child->alloc_var = e->alloc_var;
      total_elem += num_elem;
      if (total_elem % align != 0) {
        total_elem += align  - (total_elem % align);
      }
    }
599 600
    Expr alloc_size = make_const(e->allocs[0]->extents[0].type(),
                                 total_elem);
601 602 603 604 605 606
    e->new_alloc = Allocate::make(
        e->alloc_var, e->elem_type, {alloc_size}, const_true(),
        Evaluate::make(0));
    if (info.defined()) {
      CHECK_LE(total_elem * e->elem_type.bits(), info->max_num_bits)
          << "Allocation exceed bound of memory tag " << e->scope.to_string();
607 608
    }
  }
609 610 611
  // Liveness analysis to find gen and kill point of each variable.
  void LivenessAnalysis(const std::vector<StmtEntry>& seq) {
    // find kill point, do a reverse linear scan.
612 613 614
    std::unordered_set<const Variable*> touched;
    for (size_t i = seq.size(); i != 0; --i) {
      const StmtEntry& s = seq[i - 1];
615 616 617
      for (const Variable* buffer : s.touched) {
        if (!touched.count(buffer)) {
          touched.insert(buffer);
618 619 620 621 622 623 624 625 626 627 628 629 630 631
          event_map_[s.stmt].kill.push_back(buffer);
        }
      }
    }
    // find gen point, do forward scan
    touched.clear();
    for (size_t i = 0; i < seq.size(); ++i) {
      int64_t offset = seq[i].scope_pair_offset;
      if (offset < 0) continue;
      const StmtEntry& s = seq[i + offset];
      for (const Variable* buffer : s.touched) {
        if (!touched.count(buffer)) {
          touched.insert(buffer);
          event_map_[s.stmt].gen.push_back(buffer);
632 633 634 635
        }
      }
    }
  }
636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659
  void PlanNewScope(const Node* op) {
    if (thread_scope_ != nullptr) {
      CHECK(thread_scope_ == op);
      // erase all memory atatched to this scope.
      for (auto it = const_free_map_.begin(); it != const_free_map_.end();) {
        if (it->second->attach_scope_ == op) {
          it = const_free_map_.erase(it);
        } else {
          ++it;
        }
      }
      for (auto it = sym_free_list_.begin(); it != sym_free_list_.end();) {
        if ((*it)->attach_scope_ == op) {
          it = sym_free_list_.erase(it);
        } else {
          ++it;
        }
      }
      thread_scope_ = nullptr;
    } else {
      thread_scope_ = op;
    }
  }

660
  // Memory plan algorithm
661 662 663 664
  void PlanMemory(const std::vector<StmtEntry>& seq,
                  const std::unordered_map<const Variable*, AllocEntry>& alloc_info) {
    std::unordered_set<const Variable*> inplace_flag;

665 666
    for (size_t i = 0; i < seq.size(); ++i) {
      const StmtEntry& s = seq[i];
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
      auto it = event_map_.find(seq[i].stmt);

      // scope_pair_offset >= 0 means it is either
      // - leaf stmt(offset = 0)
      // - beginning of scope(offset < 0)
      // In both cases, we need to handle the gen event correctly
      if (it != event_map_.end() && seq[i].scope_pair_offset >= 0) {
        // Inplace operation detection
        // specially handle this
        bool detect_inplace = detect_inplace_ && (it->second.gen.size() <= 2);

        for (const Variable* var : it->second.gen) {
          CHECK(alloc_info.count(var));
          const AllocEntry& ae = alloc_info.at(var);
          StorageEntry* dst_entry = nullptr;
          // inplace detection
          if (detect_inplace) {
            for (const Variable* src : it->second.kill) {
              if (!inplace_flag.count(src) && alloc_map_.count(src)) {
                InplaceOpVerifier visitor;
                StorageEntry* src_entry = alloc_map_.at(src);
                if (src_entry->scope == ae.storage_scope &&
                    src_entry->attach_scope_ == thread_scope_ &&
                    src_entry->elem_type == ae.alloc->type.element_of() &&
                    visitor.Check(s.stmt, var, src)) {
                  uint64_t const_nbits = static_cast<uint64_t>(
                      ae.alloc->constant_allocation_size() *
                      ae.alloc->type.bits() *
                      ae.alloc->type.lanes());
                  if (src_entry->const_nbits == const_nbits) {
                    // successfully inplace
                    dst_entry = src_entry;
                    inplace_flag.insert(src);
                  }
                }
              }
            }
          }
          if (dst_entry == nullptr) {
            dst_entry = FindAlloc(ae.alloc, thread_scope_, ae.storage_scope);
          }
          dst_entry->allocs.emplace_back(ae.alloc);
          alloc_map_[var] = dst_entry;
        }
      }
      // enter/exit new scope
713 714
      if (s.stmt->is_type<AttrStmt>()) {
        const auto* op = static_cast<const AttrStmt*>(s.stmt);
715 716 717 718 719 720
        if (op->attr_key == attr::thread_extent ||
            op->attr_key == attr::pragma_scope) {
          PlanNewScope(op);
        } else {
          CHECK(op->attr_key == attr::extern_scope);
        }
721 722 723 724 725
      } else if (s.stmt->is_type<For>()) {
        const auto* op = static_cast<const For*>(s.stmt);
        if (op->for_type == ForType::Parallel) {
          if (thread_scope_ == nullptr || thread_scope_ == op) {
            PlanNewScope(op);
726 727 728
          }
        }
      }
729 730 731 732 733 734 735 736 737 738
      // scope_pair_offset <= 0 means it is either
      // - leaf stmt(offset = 0)
      // - end of scope(offset < 0)
      // In both cases, we need to handle the kill event correctly
      if (it != event_map_.end() && seq[i].scope_pair_offset <= 0) {
        for (const Variable* var : it->second.kill) {
          // skip space which are already replaced by inplace
          if (!inplace_flag.count(var)) {
            this->Free(var);
          }
739 740 741 742 743 744
        }
      }
    }
  }
  // Allocate new storage entry.
  StorageEntry* NewAlloc(const Allocate* op,
745
                         const Node* attach_scope,
746
                         const StorageScope& scope,
747
                         size_t const_nbits) {
748
    CHECK(op != nullptr);
749 750
    // Re-use not successful, allocate a new buffer.
    std::unique_ptr<StorageEntry> entry(new StorageEntry());
751
    entry->attach_scope_ = attach_scope;
752
    entry->scope = scope;
753 754
    entry->elem_type = op->type.element_of();
    entry->const_nbits = const_nbits;
755 756 757 758
    StorageEntry* e = entry.get();
    alloc_vec_.emplace_back(std::move(entry));
    return e;
  }
759

760
  StorageEntry* FindAlloc(const Allocate* op,
761
                          const Node* attach_scope,
762
                          const StorageScope& scope) {
763
    CHECK(op != nullptr);
764 765
    // skip plan for local variable,
    // compiler can do a better job with register allocation.
766 767
    const uint64_t match_range = 16;
    uint64_t const_nbits = static_cast<uint64_t>(
768 769
        op->constant_allocation_size() * op->type.bits() * op->type.lanes());
    // disable reuse of small arrays, they will be lowered to registers in LLVM
770 771 772 773 774 775 776 777
    // This rules only apply if we are using non special memory
    if (scope.tag.length() == 0) {
      if (scope.rank > 1 || op->type.is_handle()) {
        return NewAlloc(op, attach_scope, scope, const_nbits);
      }
      if (const_nbits > 0  &&  const_nbits <= 32) {
        return NewAlloc(op, attach_scope, scope, const_nbits);
      }
778
    }
779
    if (const_nbits != 0) {
780
      // constant allocation.
781 782 783
      auto begin = const_free_map_.lower_bound(const_nbits / match_range);
      auto mid = const_free_map_.lower_bound(const_nbits);
      auto end = const_free_map_.upper_bound(const_nbits * match_range);
784 785
      for (auto it = mid; it != end; ++it) {
        StorageEntry *e = it->second;
786
        if (e->attach_scope_ != attach_scope) continue;
787 788 789
        if (e->scope != scope) continue;
        if (e->elem_type != op->type.element_of()) continue;
        e->const_nbits = std::max(const_nbits, e->const_nbits);
790 791 792 793 794 795
        const_free_map_.erase(it);
        return e;
      }
      for (auto it = mid; it != begin;) {
        --it;
        StorageEntry *e = it->second;
796
        if (e->attach_scope_ != attach_scope) continue;
797 798
        if (e->scope != scope) continue;
        if (e->elem_type != op->type.element_of()) continue;
799 800 801 802 803 804 805 806
        const_free_map_.erase(it);
        return e;
      }
    } else {
      // Simple strategy: round roubin.
      for (auto it = sym_free_list_.begin();
           it != sym_free_list_.end(); ++it) {
        StorageEntry* e = *it;
807
        if (e->attach_scope_ != attach_scope) continue;
808
        if (e->scope != scope) continue;
809
        if (e->elem_type != op->type.element_of()) continue;
810 811 812 813
        sym_free_list_.erase(it);
        return e;
      }
    }
814
    return NewAlloc(op, attach_scope, scope, const_nbits);
815 816 817 818 819 820
  }
  // simulated free.
  void Free(const Variable* var) {
    auto it = alloc_map_.find(var);
    CHECK(it != alloc_map_.end());
    StorageEntry* e = it->second;
821
    CHECK_NE(e->allocs.size(), 0U);
822 823 824 825 826 827 828 829 830

    // disable reuse of small arrays, they will be lowered to registers in LLVM
    // This rules only apply if we are using non special memory
    if (e->scope.tag.length() == 0) {
      // Disable sharing of local memory.
      if (e->scope.rank > 1 || e->allocs[0]->type.is_handle()) return;
      // disable reuse of small arrays
      if (e->const_nbits > 0 && e->const_nbits <= 32) return;
    }
831
    // normal free.
832 833
    if (e->const_nbits != 0) {
      const_free_map_.insert({e->const_nbits, e});
834 835 836 837 838 839
    } else {
      sym_free_list_.push_back(e);
    }
  }
  // thread scope.
  const Node* thread_scope_{nullptr};
840 841
  // whether enable inplace detection.
  bool detect_inplace_{false};
842
  // Locations of free ops.
843
  std::unordered_map<const Node*, EventEntry> event_map_;
844
  // constant size free map.
845
  std::multimap<uint64_t, StorageEntry*> const_free_map_;
846 847
  // symbolic free list, for non constant items.
  std::list<StorageEntry*> sym_free_list_;
848 849 850 851
  // The allocation attach map
  std::unordered_map<const Node*, std::vector<StorageEntry*> > attach_map_;
  // The allocation assign map
  std::unordered_map<const Variable*, StorageEntry*> alloc_map_;
852 853 854 855
  // The allocations
  std::vector<std::unique_ptr<StorageEntry> > alloc_vec_;
};

856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916
// Turn alloc into vector alloc
// if all its access is the same vector type.
class VectorAllocRewriter : public IRMutator {
 public:
  Expr Mutate_(const Load* op, const Expr& e) final {
    UpdateTypeMap(op->buffer_var.get(), op->type);
    return IRMutator::Mutate_(op, e);
  }

  Stmt Mutate_(const Store* op, const Stmt& s) final {
    UpdateTypeMap(op->buffer_var.get(), op->value.type());
    return IRMutator::Mutate_(op, s);
  }
  Expr Mutate_(const Call* op, const Expr& e) final {
    if (op->is_intrinsic(intrinsic::tvm_access_ptr)) {
      Type dtype = op->args[0].type();
      const Variable* buffer = op->args[1].as<Variable>();
      UpdateTypeMap(buffer, dtype);
    }
    return IRMutator::Mutate_(op, e);
  }

  Stmt Mutate_(const Allocate* op, const Stmt& s) final {
    Stmt stmt = IRMutator::Mutate_(op, s);
    op = stmt.as<Allocate>();
    const auto& tvec = acc_map_[op->buffer_var.get()];

    if (tvec.size() == 1 &&
        tvec[0].element_of() == op->type.element_of() &&
        tvec[0].lanes() % op->type.lanes() == 0 &&
        tvec[0].lanes() != op->type.lanes()) {
      int factor = tvec[0].lanes() / op->type.lanes();
      Array<Expr> extents = op->extents;
      arith::ModularEntry me = EvalModular(
          extents[extents.size() - 1],
          std::unordered_map<const Variable*, arith::ModularEntry>());
      if (me.base % factor == 0 && me.coeff % factor == 0) {
        extents.Set(extents.size() - 1,
                    extents[extents.size() - 1] / make_const(extents[0].type(), factor));
        return Allocate::make(
            op->buffer_var, tvec[0], extents,
            op->condition, op->body);
      }
    }
    return stmt;
  }


 private:
  void UpdateTypeMap(const Variable* buffer, Type t) {
    auto& tvec = acc_map_[buffer];
    if (std::find(tvec.begin(), tvec.end(), t) == tvec.end()) {
      tvec.push_back(t);
    }
  }
  // Internal access map
  std::unordered_map<const Variable*,
                     std::vector<Type> > acc_map_;
};


917
Stmt StorageRewrite(Stmt stmt) {
918
  stmt = StoragePlanRewriter().Rewrite(stmt, true);
919
  return VectorAllocRewriter().Mutate(stmt);
920 921 922
}
}  // namespace ir
}  // namespace tvm