storage_rewrite.cc 35.2 KB
Newer Older
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
 *
10
 *   http://www.apache.org/licenses/LICENSE-2.0
11
 *
12 13 14 15 16 17 18 19
 * 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.
 */

20 21 22 23 24 25 26 27 28 29
/*!
 * 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>
30
#include <tvm/target_info.h>
31 32 33
#include <map>
#include <unordered_set>
#include <unordered_map>
34
#include "ir_util.h"
35
#include "../arithmetic/compute_expr.h"
36
#include "../runtime/thread_storage_scope.h"
37 38 39 40

namespace tvm {
namespace ir {

41
using runtime::StorageRank;
42 43
using runtime::StorageScope;

44
// Find a linear pattern of storage access
45
// Used for liveness analysis.
46 47 48 49 50 51 52 53 54 55 56 57
// 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.
//
58
class LinearAccessPatternFinder final : public IRVisitor {
59
 public:
60 61 62 63
  /*! \brief record the touch hist of statment. */
  struct StmtEntry {
    // The statment
    const Node* stmt;
64 65 66 67 68
    // 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};
69 70 71
    // The buffer variables this statment touched.
    std::vector<const Variable*> touched;
  };
72 73 74 75 76 77 78 79 80
  // 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};
  };
81

82 83 84
  void Visit_(const Allocate* op) final {
    size_t level = scope_.size();
    const Variable* buf = op->buffer_var.get();
85 86 87 88 89
    auto it = alloc_info_.find(buf);
    CHECK(it != alloc_info_.end());
    CHECK(it->second.alloc == nullptr);
    it->second.alloc = op;
    it->second.level = level;
90 91 92 93 94 95 96 97
    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();
98 99 100 101
    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);
102 103 104
    }
    StmtEntry e = scope_.back();
    scope_.pop_back();
105
    if (e.touched.size() != 0) {
106 107 108 109
      e.stmt = op;
      linear_seq_.push_back(e);
    }
  }
110 111 112 113 114 115
  void Visit_(const Evaluate* op) final {
    scope_.push_back(StmtEntry());
    // visit subexpr
    IRVisitor::Visit_(op);
    StmtEntry e = scope_.back();
    scope_.pop_back();
116
    if (e.touched.size() != 0) {
117 118 119 120
      e.stmt = op;
      linear_seq_.push_back(e);
    }
  }
121 122 123 124
  void Visit_(const Load* op) final {
    // Add write access.
    IRVisitor::Visit_(op);
    const Variable* buf = op->buffer_var.get();
125 126 127
    auto it = alloc_info_.find(buf);
    if (it != alloc_info_.end() && it->second.alloc) {
      CHECK_LT(it->second.level, scope_.size())
128
          << "Load memory in places other than store.";
129
      scope_[it->second.level].touched.push_back(buf);
130 131
    }
  }
132 133 134 135 136 137 138 139
  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);
    }
  }
140 141
  void Visit_(const Variable* buf) final {
    // Directly reference to the variable count as a read.
142 143 144 145 146
    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);
147 148 149 150 151 152 153
    }
  }
  template<typename T>
  void VisitNewScope(const T* op) {
    scope_.push_back(StmtEntry());
    StmtEntry e;
    e.stmt = op;
154
    int64_t begin_index =  static_cast<int64_t>(linear_seq_.size());
155 156 157 158
    // before scope.
    linear_seq_.push_back(e);
    IRVisitor::Visit_(op);
    // after scope.
159
    e.touched = std::move(scope_.back().touched);
160
    scope_.pop_back();
161 162 163
    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;
164
    linear_seq_.push_back(e);
165 166 167
    // record the pointer to end index.
    CHECK_NE(end_index, 0U);
    linear_seq_[begin_index].scope_pair_offset = end_index - begin_index;
168 169 170 171 172 173 174
  }
  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;
175 176
    } else if (op->attr_key == attr::extern_scope) {
      VisitNewScope(op);
177 178
    } else if (op->attr_key == attr::virtual_thread) {
      VisitNewScope(op);
179 180
    } else if (op->attr_key == attr::storage_scope) {
      const Variable* buf = op->node.as<Variable>();
181
      alloc_info_[buf].storage_scope =
182 183 184 185 186 187 188 189 190 191
          StorageScope::make(op->value.as<StringImm>()->value);
      IRVisitor::Visit_(op);
    } else {
      IRVisitor::Visit_(op);
    }
  }
  void Visit_(const IfThenElse* op) final {
    VisitNewScope(op);
  }

192 193 194 195
  void Visit_(const For* op) final {
    VisitNewScope(op);
  }

196 197 198 199
  void Visit_(const AssertStmt* op) final {
    VisitNewScope(op);
  }

200 201 202 203 204
  // linearized access sequence.
  std::vector<StmtEntry> linear_seq_;
  // The storage scope of each buffer
  std::unordered_map<const Variable*, AllocEntry> alloc_info_;

205 206 207 208 209
 private:
  // Whether already in thread env.
  bool in_thread_env_{false};
  // The scope stack.
  std::vector<StmtEntry> scope_;
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 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
};

// 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};
333 334 335 336 337
};

// Planner to plan and rewrite memory allocation.
class StoragePlanRewriter : public IRMutator {
 public:
338
  using StmtEntry = LinearAccessPatternFinder::StmtEntry;
339
  using AllocEntry = LinearAccessPatternFinder::AllocEntry;
340

341 342 343 344 345 346 347
  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_);
348
    this->PrepareNewAlloc();
349
    // start rewrite
350 351 352 353
    stmt = this->Mutate(stmt);
    if (attach_map_.count(nullptr)) {
      std::vector<Stmt> nest;
      for (StorageEntry* e : attach_map_.at(nullptr)) {
354
        // CHECK_EQ(e->scope.rank, 0);
355 356 357 358 359 360 361
        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);
        }
362 363 364 365 366 367 368 369 370 371
      }
      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;
372 373 374 375
    return Store::make(it->second->alloc_var,
                       op->value,
                       RemapIndex(op->value.type(), op->index, it->second),
                       op->predicate);
376 377 378 379 380 381
  }
  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;
382 383 384 385
    return Load::make(op->type,
                      it->second->alloc_var,
                      RemapIndex(op->type, op->index, it->second),
                      op->predicate);
386 387 388 389
  }
  Expr Mutate_(const Variable* op, const Expr& e) final {
    auto it = alloc_map_.find(op);
    if (it != alloc_map_.end()) {
390
      if (it->second->bits_offset != 0) {
391 392
        LOG(WARNING) << "Use a merged buffer variable address, could cause error";
      }
393 394 395 396 397
      return it->second->alloc_var;
    } else {
      return e;
    }
  }
398 399 400 401 402 403 404
  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);
405
       const StorageEntry* se = it->second;
406 407
       Expr offset = Mutate(op->args[2]);
       Expr extent = Mutate(op->args[3]);
408 409 410 411
       uint64_t elem_bits = dtype.bits() * dtype.lanes();
       CHECK_EQ(se->bits_offset % elem_bits, 0U);
       if (se->bits_offset != 0) {
         offset = make_const(offset.type(), se->bits_offset / elem_bits) + offset;
412 413 414
       }
       return Call::make(
           op->type, op->name,
415
           {op->args[0], se->alloc_var, offset, extent, op->args[4]},
416 417 418 419 420
           op->call_type);
    } else {
      return IRMutator::Mutate_(op, e);
    }
  }
421

422 423 424
  Stmt Mutate_(const AttrStmt* op, const Stmt& s) final {
    if (op->attr_key == attr::storage_scope) {
      return this->Mutate(op->body);
425
    } else if (op->attr_key == attr::thread_extent ||
426
               op->attr_key == attr::virtual_thread ||
427
               attr::IsPragmaKey(op->attr_key)) {
428
      // remake all the allocation at the attach scope.
429
      if (attach_map_.count(op)) {
430
        auto& svec = attach_map_[op];
431 432 433
        Stmt stmt = IRMutator::Mutate_(op, s);
        op = stmt.as<AttrStmt>();
        return AttrStmt::make(
434 435
            op->node, op->attr_key, op->value,
            MakeAttach(svec, op->body));
436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452
      } 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";
453 454 455 456 457 458 459 460 461 462 463
    // 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);
    }
464
  }
465

466 467 468 469 470 471 472 473 474 475
  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};
476
    // The constant size of the buffer in bits, only used if it is constant
477
    uint64_t const_nbits{0};
478 479 480 481
    // The storage scope.
    StorageScope scope;
    // Allocs that shares this entry.
    std::vector<const Allocate*> allocs;
482 483 484 485
    // The children of this entry, not including itself.
    std::vector<StorageEntry*> merged_children;
    // The replacement allocation, if any.
    Stmt new_alloc;
486 487
    // The var expr of new allocation.
    VarExpr alloc_var;
488 489 490
    // The allocation element type.
    Type elem_type;
    // This is non-zero if this allocate is folded into another one
491 492 493 494 495 496 497 498 499 500 501
    // the address(in bits) becomes alloc_var + bits_offset;
    // can be effectively converted to the element type.
    // We need to convert bit_offset to offset of specific element type later.
    //
    // We use bits(instead of bytes) to support non-conventional indexing in hardware.
    // When we are merging buffer together, the bits_offset are set to be aligned
    // to certain value given by the max_simd_bits property of the special memory.
    //
    // This allows effective sharing among different types as long as their alignment
    // requirement fits into the max_simd_bits.
    uint64_t bits_offset{0};
502
  };
503 504 505 506 507 508 509 510 511 512

  // 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;
  };

513 514 515 516
  Stmt MakeAttach(const std::vector<StorageEntry*>& svec,
                  Stmt body) {
    std::vector<Stmt> nest;
    for (StorageEntry* e : svec) {
517 518 519 520 521 522 523
      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);
      }
524 525 526
    }
    return MergeNest(nest, body);
  }
527 528
  // Remap the index
  Expr RemapIndex(Type dtype, Expr index, StorageEntry* e) {
529 530 531 532
    if (e->bits_offset == 0) return index;
    uint64_t elem_bits = dtype.bits() * dtype.lanes();
    CHECK_EQ(e->bits_offset % elem_bits, 0U);
    return make_const(index.type(), e->bits_offset / elem_bits) + index;
533
  }
534 535 536 537
  // Prepare the new allocations
  void PrepareNewAlloc() {
    for (size_t i = 0; i < alloc_vec_.size(); ++i) {
      StorageEntry* e = alloc_vec_[i].get();
538 539 540 541
      attach_map_[e->attach_scope_].push_back(e);
    }
    // find allocation via attach map.
    for (auto &kv : attach_map_) {
542
      // find the element with the most amount of bytes.
543 544 545 546 547 548 549 550 551 552 553 554 555
      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;
            }
          }
556 557
        }
      }
558 559 560 561
      // Start allocation
      for (size_t i = 0; i < vec.size(); ++i) {
        StorageEntry* e = vec[i];
        // already merged
562
        if (e->bits_offset != 0) continue;
563 564 565 566 567 568
        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;
569
        for (const Allocate* op : e->allocs) {
570 571
          if (op->type.lanes() > alloc_type.lanes()) {
            alloc_type = op->type;
572
          }
573 574 575
        }
        if (e->allocs.size() == 1) {
          // simply use the original allocation.
576 577
          Expr sz = arith::ComputeReduce<Mul>(e->allocs[0]->extents,
                                              make_const(Int(32), 1));
578
          e->new_alloc = Allocate::make(
579
              e->alloc_var, alloc_type, {sz},
580
              e->allocs[0]->condition, Evaluate::make(0));
581 582 583 584 585 586
          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();
          }
587 588 589 590
        } else {
          // Build a merged allocation
          Expr combo_size;
          for (const Allocate* op : e->allocs) {
591
            Expr sz = arith::ComputeReduce<Mul>(op->extents, make_const(Int(32), 1));
592 593 594 595 596 597 598 599 600 601 602
            auto nbits = op->type.bits() * op->type.lanes();
            if (const auto* imm = sz.as<IntImm>()) {
              if (imm->value > std::numeric_limits<int>::max() / nbits) {
                LOG(WARNING) << "The allocation requires : " << imm->value
                             << " * " << nbits
                             << " bits, which is greater than the maximum of"
                                " int32. The size is cast to int64."
                             << "\n";
                sz = make_const(Int(64), imm->value);
              }
            }
603
            // transform to bits
604
            auto sz_nbits = sz * nbits;
605
            if (combo_size.defined()) {
606
              combo_size = max(combo_size, sz_nbits);
607
            } else {
608
              combo_size = sz_nbits;
609
            }
610
          }
611 612
          // transform to alloc bytes
          auto type_bits = alloc_type.bits() * alloc_type.lanes();
613
          bool divided = analyzer_.CanProve(combo_size % type_bits == 0);
614 615 616
          combo_size = combo_size / type_bits;
          // round up for can not divided
          if (!divided) {
617
            combo_size = combo_size + make_const(Int(32), 1);
618
          }
619 620 621 622
          combo_size = ir::Simplify(combo_size);
          e->new_alloc = Allocate::make(
              e->alloc_var, alloc_type, {combo_size}, const_true(),
              Evaluate::make(0));
623 624 625 626 627 628
          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();
          }
629 630
        }
      }
631 632 633 634 635 636 637 638
    }
  }
  // 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());
639
    uint64_t total_bits = e->const_nbits;
640 641
    // By default, align to 32 bits.
    size_t align = 32;
642
    if (info.defined()) {
643
      align = info->max_simd_bits;
644
    }
645 646
    // Always align to max_simd_bits
    // so we can remap types by keeping this property
647 648
    if (total_bits % align != 0) {
      total_bits += align  - (total_bits % align);
649 650 651
    }
    e->alloc_var = e->allocs[0]->buffer_var;
    for (StorageEntry* child : e->merged_children) {
652 653
      CHECK_NE(child->const_nbits, 0U);
      CHECK_NE(total_bits, 0U);
654
      child->bits_offset = total_bits;
655
      child->alloc_var = e->alloc_var;
656 657 658
      total_bits += child->const_nbits;
      if (total_bits % align != 0) {
        total_bits += align  - (total_bits % align);
659 660
      }
    }
661
    uint64_t type_bits = e->elem_type.bits() * e->elem_type.lanes();
662
    Expr alloc_size = make_const(e->allocs[0]->extents[0].type(),
663
                                 (total_bits + type_bits - 1) / type_bits);
664 665 666 667
    e->new_alloc = Allocate::make(
        e->alloc_var, e->elem_type, {alloc_size}, const_true(),
        Evaluate::make(0));
    if (info.defined()) {
668
      CHECK_LE(total_bits, info->max_num_bits)
669
          << "Allocation exceed bound of memory tag " << e->scope.to_string();
670 671
    }
  }
672 673 674
  // 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.
675 676 677
    std::unordered_set<const Variable*> touched;
    for (size_t i = seq.size(); i != 0; --i) {
      const StmtEntry& s = seq[i - 1];
678 679 680
      for (const Variable* buffer : s.touched) {
        if (!touched.count(buffer)) {
          touched.insert(buffer);
681 682 683 684 685 686 687 688 689 690 691 692 693 694
          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);
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
  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;
    }
  }

723
  // Memory plan algorithm
724 725 726 727
  void PlanMemory(const std::vector<StmtEntry>& seq,
                  const std::unordered_map<const Variable*, AllocEntry>& alloc_info) {
    std::unordered_set<const Variable*> inplace_flag;

728 729
    for (size_t i = 0; i < seq.size(); ++i) {
      const StmtEntry& s = seq[i];
730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746
      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) {
747 748
            // only one inplace var for s.stmt
            bool inplace_found = false;
749 750 751 752 753 754 755 756
            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)) {
757 758
                  uint64_t const_nbits =
                      static_cast<uint64_t>(ae.alloc->constant_allocation_size()) *
759
                      ae.alloc->type.bits() *
760
                      ae.alloc->type.lanes();
761
                  if (src_entry->const_nbits == const_nbits && !inplace_found) {
762 763 764
                    // successfully inplace
                    dst_entry = src_entry;
                    inplace_flag.insert(src);
765
                    inplace_found = true;
766 767 768 769 770 771 772 773 774 775 776 777 778
                  }
                }
              }
            }
          }
          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
779 780
      if (s.stmt->is_type<AttrStmt>()) {
        const auto* op = static_cast<const AttrStmt*>(s.stmt);
781
        if (op->attr_key == attr::thread_extent ||
782 783
            op->attr_key == attr::virtual_thread ||
            attr::IsPragmaKey(op->attr_key)) {
784 785 786 787
          PlanNewScope(op);
        } else {
          CHECK(op->attr_key == attr::extern_scope);
        }
788 789 790 791 792
      } 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);
793 794 795
          }
        }
      }
796 797 798 799 800 801 802 803 804 805
      // 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);
          }
806 807 808 809 810 811
        }
      }
    }
  }
  // Allocate new storage entry.
  StorageEntry* NewAlloc(const Allocate* op,
812
                         const Node* attach_scope,
813
                         const StorageScope& scope,
814
                         size_t const_nbits) {
815
    CHECK(op != nullptr);
816 817
    // Re-use not successful, allocate a new buffer.
    std::unique_ptr<StorageEntry> entry(new StorageEntry());
818
    entry->attach_scope_ = attach_scope;
819
    entry->scope = scope;
820 821
    entry->elem_type = op->type.element_of();
    entry->const_nbits = const_nbits;
822 823 824 825
    StorageEntry* e = entry.get();
    alloc_vec_.emplace_back(std::move(entry));
    return e;
  }
826

827
  StorageEntry* FindAlloc(const Allocate* op,
828
                          const Node* attach_scope,
829
                          const StorageScope& scope) {
830
    CHECK(op != nullptr);
831 832
    // skip plan for local variable,
    // compiler can do a better job with register allocation.
833
    const uint64_t match_range = 16;
834
    uint64_t op_elem_bits = op->type.bits() * op->type.lanes();
835
    uint64_t const_nbits = static_cast<uint64_t>(
836
        op->constant_allocation_size() * op_elem_bits);
837
    // disable reuse of small arrays, they will be lowered to registers in LLVM
838 839
    // This rules only apply if we are using non special memory
    if (scope.tag.length() == 0) {
840
      if (scope.rank >= StorageRank::kWarp || op->type.is_handle()) {
841 842 843 844 845
        return NewAlloc(op, attach_scope, scope, const_nbits);
      }
      if (const_nbits > 0  &&  const_nbits <= 32) {
        return NewAlloc(op, attach_scope, scope, const_nbits);
      }
846
    }
847
    if (const_nbits != 0) {
848
      // constant allocation.
849 850 851
      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);
852
      // start looking at the buffer that is bigger than the required size first
853 854
      for (auto it = mid; it != end; ++it) {
        StorageEntry *e = it->second;
855
        if (e->attach_scope_ != attach_scope) continue;
856
        if (e->scope != scope) continue;
857 858
        // when not divided, no reuse, eg, float4 vs float3
        if (e->bits_offset % op_elem_bits != 0) continue;
859
        e->const_nbits = std::max(const_nbits, e->const_nbits);
860 861 862
        const_free_map_.erase(it);
        return e;
      }
863
      // then start looking at smaller buffers.
864 865 866
      for (auto it = mid; it != begin;) {
        --it;
        StorageEntry *e = it->second;
867
        if (e->attach_scope_ != attach_scope) continue;
868 869
        if (e->scope != scope) continue;
        if (e->elem_type != op->type.element_of()) continue;
870
        e->const_nbits = std::max(const_nbits, e->const_nbits);
871 872 873 874 875 876 877 878
        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;
879
        if (e->attach_scope_ != attach_scope) continue;
880
        if (e->scope != scope) continue;
881
        if (e->elem_type != op->type.element_of()) continue;
882 883 884 885
        sym_free_list_.erase(it);
        return e;
      }
    }
886
    return NewAlloc(op, attach_scope, scope, const_nbits);
887 888 889 890 891 892
  }
  // simulated free.
  void Free(const Variable* var) {
    auto it = alloc_map_.find(var);
    CHECK(it != alloc_map_.end());
    StorageEntry* e = it->second;
893
    CHECK_NE(e->allocs.size(), 0U);
894 895 896 897 898

    // 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.
899 900
      if (e->scope.rank >= StorageRank::kWarp ||
          e->allocs[0]->type.is_handle()) return;
901 902 903
      // disable reuse of small arrays
      if (e->const_nbits > 0 && e->const_nbits <= 32) return;
    }
904
    // normal free.
905 906
    if (e->const_nbits != 0) {
      const_free_map_.insert({e->const_nbits, e});
907 908 909 910 911 912
    } else {
      sym_free_list_.push_back(e);
    }
  }
  // thread scope.
  const Node* thread_scope_{nullptr};
913 914
  // whether enable inplace detection.
  bool detect_inplace_{false};
915
  // Locations of free ops.
916
  std::unordered_map<const Node*, EventEntry> event_map_;
917
  // constant size free map.
918
  std::multimap<uint64_t, StorageEntry*> const_free_map_;
919 920
  // symbolic free list, for non constant items.
  std::list<StorageEntry*> sym_free_list_;
921 922 923 924
  // 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_;
925 926
  // The allocations
  std::vector<std::unique_ptr<StorageEntry> > alloc_vec_;
927 928
  // analyzer
  arith::Analyzer analyzer_;
929 930
};

931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963
// 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;
964 965
      arith::ModularSet me = analyzer_.modular_set(extents[extents.size() - 1]);
      if (me->base % factor == 0 && me->coeff % factor == 0) {
966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981
        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;
  }

  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);
    }
  }
982

983
  // Internal access map
984
  std::unordered_map<const Variable*, std::vector<Type> > acc_map_;
985 986
  // internal analyzer
  arith::Analyzer analyzer_;
987 988 989
};


990
LoweredFunc PointerValueTypeRewrite(LoweredFunc f) {
991
  auto n = make_node<LoweredFuncNode>(*f.operator->());
992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012
  VectorAllocRewriter rewriter;
  n->body = rewriter.Mutate(n->body);
  for (Var arg : f->args) {
    if (arg.type().is_handle()) {
      const auto& tvec = rewriter.acc_map_[arg.get()];
      if (tvec.size() == 1) {
        Expr dtype = make_const(tvec[0], 0);
        n->handle_data_type.Set(arg, dtype);
      } else {
        // always set data type to be non vectorized so
        // load/store can still work via scalarization
        if (tvec.size() != 0 && !n->handle_data_type.count(arg)) {
          Expr dtype = make_const(tvec[0].with_lanes(1), 0);
          n->handle_data_type.Set(arg, dtype);
        }
      }
    }
  }
  return LoweredFunc(n);
}

1013
Stmt StorageRewrite(Stmt stmt) {
1014
  stmt = StoragePlanRewriter().Rewrite(stmt, true);
1015
  return VectorAllocRewriter().Mutate(stmt);
1016 1017 1018
}
}  // namespace ir
}  // namespace tvm