structural_hash.h

Go to the documentation of this file.

/*
 * 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
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * 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.
 */
#ifndef TVM_NODE_STRUCTURAL_HASH_H_
#define TVM_NODE_STRUCTURAL_HASH_H_

#include <tvm/node/functor.h>
#include <tvm/runtime/data_type.h>
#include <tvm/runtime/ndarray.h>

#include <functional>
#include <string>

namespace tvm {

class BaseValueHash {
 protected:
  template <typename T, typename U>
  uint64_t Reinterpret(T value) const {
    union Union {
      T a;
      U b;
    } u;
    static_assert(sizeof(Union) == sizeof(T), "sizeof(Union) != sizeof(T)");
    static_assert(sizeof(Union) == sizeof(U), "sizeof(Union) != sizeof(U)");
    u.b = 0;
    u.a = value;
    return u.b;
  }

 public:
  uint64_t operator()(const float& key) const { return Reinterpret<float, uint32_t>(key); }
  uint64_t operator()(const double& key) const { return Reinterpret<double, uint64_t>(key); }
  uint64_t operator()(const int64_t& key) const { return Reinterpret<int64_t, uint64_t>(key); }
  uint64_t operator()(const uint64_t& key) const { return key; }
  uint64_t operator()(const int& key) const { return Reinterpret<int, uint32_t>(key); }
  uint64_t operator()(const bool& key) const { return key; }
  uint64_t operator()(const runtime::DataType& key) const {
    return Reinterpret<DLDataType, uint32_t>(key);
  }
  template <typename ENum, typename = typename std::enable_if<std::is_enum<ENum>::value>::type>
  uint64_t operator()(const ENum& key) const {
    return Reinterpret<int64_t, uint64_t>(static_cast<int64_t>(key));
  }
  uint64_t operator()(const std::string& key) const {
    return runtime::String::StableHashBytes(key.data(), key.length());
  }
};

class StructuralHash : public BaseValueHash {
 public:
  // inherit operator()
  using BaseValueHash::operator();
  TVM_DLL uint64_t operator()(const ObjectRef& key) const;
};

class SHashReducer {
 public:
  class Handler {
   public:
    virtual void SHashReduceHashedValue(uint64_t hashed_value) = 0;
    virtual void SHashReduce(const ObjectRef& key, bool map_free_vars) = 0;
    virtual void SHashReduceFreeVar(const runtime::Object* var, bool map_free_vars) = 0;
    virtual bool LookupHashedValue(const ObjectRef& key, uint64_t* hashed_value) = 0;
    virtual void MarkGraphNode() = 0;
  };

  SHashReducer() = default;
  explicit SHashReducer(Handler* handler, bool map_free_vars)
      : handler_(handler), map_free_vars_(map_free_vars) {}
  template <typename T,
            typename = typename std::enable_if<!std::is_base_of<ObjectRef, T>::value>::type>
  void operator()(const T& key) const {
    // handle normal values.
    handler_->SHashReduceHashedValue(BaseValueHash()(key));
  }
  void operator()(const ObjectRef& key) const { return handler_->SHashReduce(key, map_free_vars_); }
  void DefHash(const ObjectRef& key) const { return handler_->SHashReduce(key, true); }
  void FreeVarHashImpl(const runtime::Object* var) const {
    handler_->SHashReduceFreeVar(var, map_free_vars_);
  }

  Handler* operator->() const { return handler_; }

 private:
  Handler* handler_;
  bool map_free_vars_;
};

class SHashHandlerDefault : public SHashReducer::Handler {
 public:
  SHashHandlerDefault();
  virtual ~SHashHandlerDefault();

  void SHashReduceHashedValue(uint64_t hashed_value) override;
  void SHashReduce(const ObjectRef& key, bool map_free_vars) override;
  void SHashReduceFreeVar(const runtime::Object* var, bool map_free_vars) override;
  bool LookupHashedValue(const ObjectRef& key, uint64_t* hashed_value) override;
  void MarkGraphNode() override;

  virtual uint64_t Hash(const ObjectRef& object, bool map_free_vars);

 protected:
  virtual void DispatchSHash(const ObjectRef& object, bool map_free_vars);

 private:
  class Impl;
  Impl* impl;
};

class SEqualReducer;
struct NDArrayContainerTrait {
  static constexpr const std::nullptr_t VisitAttrs = nullptr;
  static void SHashReduce(const runtime::NDArray::Container* key, SHashReducer hash_reduce);
  static bool SEqualReduce(const runtime::NDArray::Container* lhs,
                           const runtime::NDArray::Container* rhs, SEqualReducer equal);
};

}  // namespace tvm
#endif  // TVM_NODE_STRUCTURAL_HASH_H_