compiler/luci/service/src/Validate.cpp

   1 /*
   2  * Copyright (c) 2020 Samsung Electronics Co., Ltd. All Rights Reserved
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "luci/Service/Validate.h"
  18
  19 #include <luci/IR/Nodes/CircleOutput.h>
  20 #include <luci/IR/CircleNodeVisitor.h>
  21 #include <luci/Log.h>
  22 #include <luci/LogHelper.h>
  23
  24 #include <loco/IR/NodeShape.h>
  25
  26 #include <cassert>
  27 #include <unordered_map>
  28 #include <vector>
  29 #include <iostream>
  30
  31 namespace
  32 {
  33
  34 std::ostream &operator<<(std::ostream &os, const loco::TensorShape &tensor_shape)
  35 {
  36   os << "[";
  37   for (uint32_t r = 0; r < tensor_shape.rank(); ++r)
  38   {
  39     if (r)
  40       os << ",";
  41
  42     if (tensor_shape.dim(r).known())
  43       os << tensor_shape.dim(r).value();
  44     else
  45       os << "?";
  46   }
  47   os << "]";
  48   return os;
  49 }
  50
  51 std::ostream &operator<<(std::ostream &os, const luci::CircleNode *circle_node)
  52 {
  53   os << "[";
  54   for (uint32_t r = 0; r < circle_node->rank(); ++r)
  55   {
  56     if (r)
  57       os << ",";
  58
  59     if (circle_node->dim(r).known())
  60       os << circle_node->dim(r).value();
  61     else
  62       os << "?";
  63   }
  64   os << "]";
  65   return os;
  66 }
  67
  68 /**
  69  * @brief  returns a node that is CircleOutput with index is out_index in nodes
  70  */
  71 luci::CircleOutput *find_node(std::vector<loco::Node *> nodes, loco::GraphOutputIndex out_index)
  72 {
  73   for (auto node : nodes)
  74   {
  75     auto circle_output = dynamic_cast<luci::CircleOutput *>(node);
  76     if (circle_output != nullptr)
  77     {
  78       if (circle_output->indexed() && circle_output->index() == out_index)
  79         return circle_output;
  80     }
  81   }
  82   return nullptr;
  83 }
  84
  85 // TODO Reduce duplicate with validate_shape_dtype
  86 bool validate_shape(loco::Graph *g)
  87 {
  88   LOGGER(l);
  89
  90   auto output_nodes = loco::output_nodes(g);
  91
  92   auto count = g->outputs()->size();
  93   for (uint32_t out = 0; out < count; ++out)
  94   {
  95     auto graph_out = g->outputs()->at(out);
  96     auto out_index = graph_out->index();
  97
  98     auto circle_output = find_node(output_nodes, out_index);
  99     assert(circle_output != nullptr);
 100     assert(circle_output->from() != nullptr);
 101     auto circle_node = loco::must_cast<luci::CircleNode *>(circle_output->from());
 102
 103     // Shape validation for CircleOutputExclude is not needed
 104     if (dynamic_cast<luci::CircleOutputExclude *>(circle_node))
 105       continue;
 106
 107     assert(circle_node->shape_status() != luci::ShapeStatus::UNDEFINED);
 108
 109     // check if output node shape is same as graph output shape
 110     auto go_tensor_shape = graph_out->shape();
 111     assert(go_tensor_shape);
 112
 113     // NOTE Even if shape of graph output is [] (which means "shape inference was impossible")
 114     //      but shape of CircleNode is not, it can be valid case because shape inference
 115     //      algorithm of CircleNode may be upgraded than before. The opposite is possible either.
 116     //      If such cases are appeared, following validation code should be fixed.
 117     bool is_shape_valid = (circle_node->rank() == go_tensor_shape->rank());
 118     for (uint32_t i = 0; is_shape_valid && i < circle_node->rank(); ++i)
 119     {
 120       if (!circle_node->dim(i).known() || !go_tensor_shape->dim(i).known())
 121       {
 122         // If at least one of two dimensions is unknown,
 123         // the unknown dimension can accept any value.
 124         INFO(l) << "Unknown dimension is matched with known dimension" << std::endl;
 125       }
 126       else if (circle_node->dim(i).value() != go_tensor_shape->dim(i).value())
 127       {
 128         is_shape_valid = false;
 129       }
 130     }
 131
 132     if (is_shape_valid == false)
 133     {
 134       INFO(l) << "[luci] Shape for output #" << out_index << " not same " << std::endl;
 135       INFO(l) << "[luci]    " << circle_node->name() << " " << circle_node << " vs "
 136               << *go_tensor_shape << std::endl;
 137       return false;
 138     }
 139   }
 140
 141   return true;
 142 }
 143
 144 bool validate_shape_dtype(loco::Graph *g)
 145 {
 146   LOGGER(l);
 147
 148   auto output_nodes = loco::output_nodes(g);
 149
 150   auto count = g->outputs()->size();
 151   for (uint32_t out = 0; out < count; ++out)
 152   {
 153     auto graph_out = g->outputs()->at(out);
 154     auto out_index = graph_out->index();
 155
 156     auto circle_output = find_node(output_nodes, out_index);
 157     assert(circle_output != nullptr);
 158     assert(circle_output->from() != nullptr);
 159     auto circle_node = loco::must_cast<luci::CircleNode *>(circle_output->from());
 160
 161     // Shape and dtype validation for CircleOutputExclude is not needed
 162     if (dynamic_cast<luci::CircleOutputExclude *>(circle_node))
 163       continue;
 164
 165     assert(circle_node->shape_status() != luci::ShapeStatus::UNDEFINED);
 166
 167     // check if output node shape is same as graph output shape
 168     auto go_tensor_shape = graph_out->shape();
 169     assert(go_tensor_shape);
 170
 171     // NOTE Even if shape of graph output is [] (which means "shape inference was impossible")
 172     //      but shape of CircleNode is not, it can be valid case because shape inference
 173     //      algorithm of CircleNode may be upgraded than before. The opposite is possible either.
 174     //      If such cases are appeared, following validation code should be fixed.
 175     bool is_shape_valid = (circle_node->rank() == go_tensor_shape->rank());
 176     for (uint32_t i = 0; is_shape_valid && i < circle_node->rank(); ++i)
 177     {
 178       if (!circle_node->dim(i).known() || !go_tensor_shape->dim(i).known())
 179       {
 180         // If at least one of two dimensions is unknown,
 181         // the unknown dimension can accept any value.
 182         INFO(l) << "Unknown dimension is matched with known dimension" << std::endl;
 183       }
 184       else if (circle_node->dim(i).value() != go_tensor_shape->dim(i).value())
 185       {
 186         is_shape_valid = false;
 187       }
 188     }
 189
 190     if (is_shape_valid == false)
 191     {
 192       INFO(l) << "[luci] Shape for output #" << out_index << " not same " << std::endl;
 193       INFO(l) << "[luci]    " << circle_node->name() << " " << circle_node << " vs "
 194               << *go_tensor_shape << std::endl;
 195       return false;
 196     }
 197
 198     // check if data type match
 199     assert(circle_node->dtype() != loco::DataType::Unknown);
 200     if (graph_out->dtype() != circle_node->dtype())
 201     {
 202       INFO(l) << "[luci] Type for output #" << out_index << " not same " << std::endl;
 203       return false;
 204     }
 205   }
 206
 207   return true;
 208 }
 209
 210 class MultiOutNodeValidate final : public luci::CircleNodeVisitor<bool>
 211 {
 212 public:
 213   MultiOutNodeValidate() {}
 214
 215 private:
 216   template <class T> bool check(const luci::CircleNode *node)
 217   {
 218     auto succs = loco::succs(node);
 219     if (succs.size() < 1)
 220       return false;
 221     for (const auto &cnode : succs)
 222     {
 223       auto const child = dynamic_cast<const T *>(cnode);
 224       if (child == nullptr)
 225         return false;
 226     }
 227     return true;
 228   }
 229
 230 public:
 231   bool visit(const luci::CircleBidirectionalSequenceLSTM *node) final
 232   {
 233     return check<luci::CircleBidirectionalSequenceLSTMOut>(node);
 234   }
 235   bool visit(const luci::CircleCustom *node) final { return check<luci::CircleCustomOut>(node); }
 236   bool visit(const luci::CircleIf *node) final { return check<luci::CircleIfOut>(node); }
 237   bool visit(const luci::CircleNonMaxSuppressionV4 *node) final
 238   {
 239     return check<luci::CircleNonMaxSuppressionV4Out>(node);
 240   }
 241   bool visit(const luci::CircleNonMaxSuppressionV5 *node) final
 242   {
 243     return check<luci::CircleNonMaxSuppressionV5Out>(node);
 244   }
 245   bool visit(const luci::CircleSplit *node) final { return check<luci::CircleSplitOut>(node); }
 246   bool visit(const luci::CircleSplitV *node) final { return check<luci::CircleSplitVOut>(node); }
 247   bool visit(const luci::CircleTopKV2 *node) final { return check<luci::CircleTopKV2Out>(node); }
 248   bool visit(const luci::CircleUnique *node) final { return check<luci::CircleUniqueOut>(node); }
 249   bool visit(const luci::CircleUnpack *node) final { return check<luci::CircleUnpackOut>(node); }
 250   bool visit(const luci::CircleWhile *node) final { return check<luci::CircleWhileOut>(node); }
 251
 252   // default true for other nodes
 253   bool visit(const luci::CircleNode *) final { return true; }
 254 };
 255
 256 /**
 257  * @brief Validate sequence of multi-output nodes are followed for specific
 258  *        IRs such as CircleIfOut.
 259  */
 260 bool validate_multi_outs(loco::Graph *g)
 261 {
 262   LOGGER(l);
 263
 264   for (auto node : loco::active_nodes(loco::output_nodes(g)))
 265   {
 266     auto const cnode = loco::must_cast<luci::CircleNode *>(node);
 267
 268     MultiOutNodeValidate d;
 269     if (cnode->accept(&d))
 270       continue;
 271
 272     auto const name = cnode->name();
 273     INFO(l) << "Node: " << name << ", " << (uint32_t)(cnode->opcode()) << " has invalid successor."
 274             << std::endl;
 275
 276     return false;
 277   }
 278
 279   return true;
 280 }
 281
 282 class VirtualNodeDetector final : public luci::CircleNodeVisitor<bool>
 283 {
 284 public:
 285   VirtualNodeDetector() {}
 286
 287 public:
 288   bool visit(const luci::CircleBidirectionalSequenceLSTMOut *) final { return true; }
 289   bool visit(const luci::CircleCustomOut *) final { return true; }
 290   bool visit(const luci::CircleIfOut *) final { return true; }
 291   bool visit(const luci::CircleNonMaxSuppressionV4Out *) final { return true; }
 292   bool visit(const luci::CircleNonMaxSuppressionV5Out *) final { return true; }
 293   bool visit(const luci::CircleSplitOut *) final { return true; }
 294   bool visit(const luci::CircleSplitVOut *) final { return true; }
 295   bool visit(const luci::CircleTopKV2Out *) final { return true; }
 296   bool visit(const luci::CircleUnpackOut *) final { return true; }
 297   bool visit(const luci::CircleUniqueOut *) final { return true; }
 298   bool visit(const luci::CircleWhileOut *) final { return true; }
 299   bool visit(const luci::CircleOutputDummy *) final { return true; }
 300   bool visit(const luci::CircleOutputExclude *) final { return true; }
 301
 302   // Return false by default
 303   bool visit(const luci::CircleNode *) final { return false; }
 304 };
 305
 306 } // namespace
 307
 308 namespace luci
 309 {
 310
 311 bool validate_shape(loco::Graph *g)
 312 {
 313   if (!loco::valid(g))
 314     return false;
 315
 316   if (!::validate_shape(g))
 317     return false;
 318
 319   return true;
 320 }
 321
 322 bool validate(loco::Graph *g)
 323 {
 324   if (!loco::valid(g))
 325     return false;
 326
 327   if (!validate_shape_dtype(g))
 328     return false;
 329
 330   if (!validate_multi_outs(g))
 331     return false;
 332
 333   // TODO add more validation
 334
 335   return true;
 336 }
 337
 338 bool validate_name(loco::Graph *g)
 339 {
 340   auto nodes = g->nodes();
 341   for (uint32_t n = 0; n < nodes->size(); ++n)
 342   {
 343     auto node = loco::must_cast<luci::CircleNode *>(nodes->at(n));
 344     // skip virtual nodes
 345     VirtualNodeDetector d;
 346     if (node->accept(&d))
 347       continue;
 348
 349     auto name = node->name();
 350     if (name.empty())
 351       return false;
 352   }
 353
 354   return true;
 355 }
 356
 357 bool validate_unique_name(luci::Module *m)
 358 {
 359   LOGGER(l);
 360
 361   std::unordered_map<std::string, bool> names_col;
 362
 363   for (size_t g = 0; g < m->size(); ++g)
 364   {
 365     auto graph = m->graph(g);
 366     auto nodes = graph->nodes();
 367     for (uint32_t n = 0; n < nodes->size(); ++n)
 368     {
 369       auto node = loco::must_cast<luci::CircleNode *>(nodes->at(n));
 370       // skip CircleOutput as it may have same name with from() node
 371       auto output = dynamic_cast<luci::CircleOutput *>(node);
 372       if (output != nullptr)
 373         continue;
 374       // skip virtual nodes
 375       VirtualNodeDetector d;
 376       if (node->accept(&d))
 377         continue;
 378
 379       auto name = node->name();
 380       INFO(l) << "Node: " << name << ", " << (uint32_t)(node->opcode()) << std::endl;
 381       auto it = names_col.find(name);
 382       if (it != names_col.end())
 383       {
 384         INFO(l) << "validate_unique_name: found duplicate " << name << ", " << graph->name()
 385                 << std::endl;
 386         return false;
 387       }
 388
 389       names_col[name] = true;
 390     }
 391     // There can exist same tensor name between different subgraphs.
 392     names_col.clear();
 393   }
 394
 395   return true;
 396 }
 397
 398 bool validate(luci::Module *module)
 399 {
 400   LOGGER(l);
 401
 402   INFO(l) << "--- validate Module -----------------------------------";
 403
 404   for (size_t g = 0; g < module->size(); ++g)
 405   {
 406     auto graph = module->graph(g);
 407
 408     INFO(l) << luci::fmt(graph) << std::endl;
 409
 410     if (!validate(graph))
 411     {
 412       std::cerr << "ERROR: Invalid circle model" << std::endl;
 413       return false;
 414     }
 415     if (!validate_name(graph))
 416     {
 417       std::cerr << "ERROR: circle model has empty name" << std::endl;
 418       return false;
 419     }
 420   }
 421
 422   if (!validate_unique_name(module))
 423   {
 424     std::cerr << "ERROR: circle model has duplicate names" << std::endl;
 425     return false;
 426   }
 427
 428   return true;
 429 }
 430
 431 bool validate_shape(luci::Module *module)
 432 {
 433   LOGGER(l);
 434
 435   INFO(l) << "--- validate shape of Module -----------------------------------";
 436
 437   for (size_t g = 0; g < module->size(); ++g)
 438   {
 439     auto graph = module->graph(g);
 440
 441     INFO(l) << luci::fmt(graph) << std::endl;
 442
 443     if (!validate_shape(graph))
 444     {
 445       std::cerr << "ERROR: Invalid circle model" << std::endl;
 446       return false;
 447     }
 448   }
 449
 450   return true;
 451 }
 452
 453 } // namespace luci