1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19
20/*!
21 * \file tir/analysis/deep_equal.cc
22 * \brief Deep equality checking.
23 */
24#include <tvm/node/object_path.h>
25#include <tvm/node/reflection.h>
26#include <tvm/node/structural_equal.h>
27#include <tvm/runtime/registry.h>
28#include <tvm/tir/analysis.h>
29
30namespace tvm {
31namespace tir {
32
33class DeepCmpSEqualHandler : public SEqualReducer::Handler {
34 public:
35 // use direct recursion.
36 bool SEqualReduce(const ObjectRef& lhs, const ObjectRef& rhs, bool map_free_vars,
37 const Optional<ObjectPathPair>&) final {
38 if (lhs.same_as(rhs)) return true;
39 if (!lhs.defined() && rhs.defined()) return false;
40 if (!rhs.defined() && lhs.defined()) return false;
41 if (lhs->type_index() != rhs->type_index()) return false;
42 return vtable_->SEqualReduce(lhs.get(), rhs.get(), SEqualReducer(this, nullptr, false)) &&
43 !fail_;
44 }
45
46 void DeferFail(const ObjectPathPair&) final { fail_ = true; }
47 bool IsFailDeferralEnabled() final { return false; }
48
49 ObjectRef MapLhsToRhs(const ObjectRef& lhs) final { return ObjectRef(nullptr); }
50 void MarkGraphNode() final {}
51
52 private:
53 // reflection vtable
54 ReflectionVTable* vtable_ = ReflectionVTable::Global();
55 bool fail_ = false;
56};
57
58bool ExprDeepEqual::operator()(const PrimExpr& lhs, const PrimExpr& rhs) const {
59 // quick path
60 if (lhs.same_as(rhs)) return true;
61 if (!lhs.defined() && rhs.defined()) return false;
62 if (!rhs.defined() && lhs.defined()) return false;
63 if (lhs->type_index() != rhs->type_index()) return false;
64 if (auto* plhs = lhs.as<IntImmNode>()) {
65 auto* prhs = rhs.as<IntImmNode>();
66 return plhs->dtype == prhs->dtype && plhs->value == prhs->value;
67 }
68 if (lhs.as<AnyNode>()) {
69 return false;
70 }
71 return DeepCmpSEqualHandler().SEqualReduce(lhs, rhs, false, NullOpt);
72}
73
74TVM_REGISTER_GLOBAL("tir.analysis.expr_deep_equal")
75 .set_body_typed([](const PrimExpr& lhs, const PrimExpr& rhs) {
76 return ExprDeepEqual()(lhs, rhs);
77 });
78
79} // namespace tir
80} // namespace tvm
81