ssa.cc 5.27 KB
Newer Older
tqchen committed
1 2 3
/*!
 *  Copyright (c) 2016 by Contributors
 *  SSA related checks and pass.
4 5
 *
 *  SSA requires each varaible to be only defined once.
tqchen committed
6 7 8 9 10 11 12 13 14 15 16 17 18
 * \file ssa.cc
 */
#include <tvm/ir.h>
#include <tvm/ir_visitor.h>
#include <tvm/ir_mutator.h>
#include <tvm/ir_pass.h>
#include <unordered_set>
#include <unordered_map>
#include <vector>

namespace tvm {
namespace ir {
namespace {
19
class IRVerifySSA final : public IRVisitor {
tqchen committed
20 21 22
 public:
  bool is_ssa{true};

23
  void Visit(const NodeRef& n) final {
tqchen committed
24 25 26
    if (!is_ssa) return;
    IRVisitor::Visit(n);
  }
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
  void Visit_(const Let* op) final {
    MarkDef(op->var.get());
    IRVisitor::Visit_(op);
  }
  void Visit_(const LetStmt* op) final {
    MarkDef(op->var.get());
    IRVisitor::Visit_(op);
  }
  void Visit_(const For* op) final {
    MarkDef(op->loop_var.get());
    IRVisitor::Visit_(op);
  }
  void Visit_(const Allocate* op) final {
    MarkDef(op->buffer_var.get());
    IRVisitor::Visit_(op);
  }
tqchen committed
43 44

 private:
45 46 47 48 49 50 51
  void MarkDef(const Variable* v) {
    if (defined_.count(v) != 0) {
      is_ssa = false; return;
    } else {
      defined_[v] = 1;
    }
  }
tqchen committed
52 53 54
  std::unordered_map<const Variable*, int> defined_;
};

55
class IRConvertSSA final : public IRMutator {
tqchen committed
56
 public:
57 58 59 60 61 62 63 64 65 66 67 68
  Expr Mutate_(const Variable* op, const Expr& e) final {
    if (scope_.count(op)) {
      return scope_[op].back();
    } else {
      return e;
    }
  }
  Expr Mutate_(const Let* op, const Expr& e) final {
    const VarExpr& v = op->var;
    if (defined_.count(v.get())) {
      Expr value = IRMutator::Mutate(op->value);
      VarExpr new_var = Variable::make(v.type(), v->name_hint);
tqchen committed
69
      scope_[v.get()].push_back(new_var);
70
      Expr body = IRMutator::Mutate(op->body);
tqchen committed
71
      scope_[v.get()].pop_back();
72
      return Let::make(new_var, value, body);
tqchen committed
73
    } else {
74 75
      defined_.insert(v.get());
      return IRMutator::Mutate_(op, e);
tqchen committed
76 77
    }
  }
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
  Expr Mutate_(const Load* op, const Expr& e) final {
    Expr expr = IRMutator::Mutate_(op, e);
    op = expr.as<Load>();
    if (scope_.count(op->buffer_var.get())) {
      return Load::make(
          op->type, scope_[op->buffer_var.get()].back(),
          op->index, op->predicate);
    } else {
      return expr;
    }
  }
  Stmt Mutate_(const Store* op, const Stmt& s) final {
    Stmt stmt = IRMutator::Mutate_(op, s);
    op = stmt.as<Store>();
    if (scope_.count(op->buffer_var.get())) {
      return Store::make(
          scope_[op->buffer_var.get()].back(), op->value,
          op->index, op->predicate);
    } else {
      return stmt;
    }
  }
  Stmt Mutate_(const LetStmt* op, const Stmt& s) final {
    const VarExpr& v = op->var;
    if (defined_.count(v.get())) {
      Expr value = IRMutator::Mutate(op->value);
      VarExpr new_var = Variable::make(v.type(), v->name_hint);
tqchen committed
105
      scope_[v.get()].push_back(new_var);
106
      Stmt body = IRMutator::Mutate(op->body);
tqchen committed
107
      scope_[v.get()].pop_back();
108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
      return LetStmt::make(new_var, value, body);
    } else {
      defined_.insert(v.get());
      return IRMutator::Mutate_(op, s);
    }
  }
  Stmt Mutate_(const For* op, const Stmt& s) final {
    const VarExpr& v = op->loop_var;
    if (defined_.count(v.get())) {
      VarExpr new_var = Variable::make(v.type(), v->name_hint);
      scope_[v.get()].push_back(new_var);
      Stmt stmt = IRMutator::Mutate_(op, s);
      scope_[v.get()].pop_back();
      op = stmt.as<For>();
      return For::make(
          new_var, op->min, op->extent, op->for_type, op->device_api, op->body);
    } else {
      defined_.insert(v.get());
      return IRMutator::Mutate_(op, s);
    }
  }
  Stmt Mutate_(const Allocate* op, const Stmt& s) final {
    const VarExpr& v = op->buffer_var;
    if (defined_.count(v.get())) {
      VarExpr new_var = Variable::make(v.type(), v->name_hint);
      scope_[v.get()].push_back(new_var);
      Stmt stmt = IRMutator::Mutate_(op, s);
      scope_[v.get()].pop_back();
      op = stmt.as<Allocate>();
      return Allocate::make(
          new_var, op->type, op->extents, op->condition,
          op->body, op->new_expr, op->free_function);
    } else {
      defined_.insert(v.get());
      return IRMutator::Mutate_(op, s);
    }
  }
  Stmt Mutate_(const AttrStmt* op, const Stmt& s) final {
    if (const Variable* v = op->node.as<Variable>()) {
      if (op->attr_key == attr::storage_scope) {
        const Allocate* alloc = op->body.as<Allocate>();
        if (alloc && op->node.same_as(alloc->buffer_var)) {
          Stmt new_alloc = Mutate(op->body);
          if (new_alloc.same_as(op->body)) return s;
          alloc = new_alloc.as<Allocate>();
          CHECK(alloc);
          return AttrStmt::make(
              alloc->buffer_var, op->attr_key, op->value, new_alloc);
        }
      }
      Stmt stmt = IRMutator::Mutate_(op, s);
      op = stmt.as<AttrStmt>();
      if (scope_.count(v) && scope_[v].size() != 0) {
        return AttrStmt::make(
            scope_[v].back(), op->attr_key, op->value, op->body);
tqchen committed
163
      } else {
164
        return stmt;
tqchen committed
165 166
      }
    } else {
167
      return IRMutator::Mutate_(op, s);
tqchen committed
168 169 170 171 172 173 174 175 176 177
    }
  }

 private:
  std::unordered_map<const Variable*, std::vector<VarExpr> > scope_;
  std::unordered_set<const Variable*> defined_;
};

}  // namespace

tqchen committed
178
bool VerifySSA(const Stmt& ir) {
tqchen committed
179 180 181 182 183
  IRVerifySSA v;
  v.Visit(ir);
  return v.is_ssa;
}

tqchen committed
184
Stmt ConvertSSA(Stmt stmt) {
tqchen committed
185 186 187 188 189
  return IRConvertSSA().Mutate(stmt);
}

}  // namespace ir
}  // namespace tvm