1 /*
2 * Copyright (c) 2023-2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "gc_utils.h"
17 #include "transforms/transform_utils.h"
18
19 namespace {
20 /// Tag for instructions have a managed pointer type but the reference is not moved by GC
21 constexpr llvm::StringRef MD_NON_MOVABLE = "non-movable";
22 } // namespace
23
24 namespace ark::llvmbackend::gc_utils {
25
IsDerived(llvm::Value * val)26 bool IsDerived(llvm::Value *val)
27 {
28 auto isDerived = IsDerivedImpl(val);
29 ASSERT(isDerived != DerivedStatus::UNKNOWN);
30 return isDerived == DerivedStatus::DERIVED;
31 }
32
IsDerivedImpl(llvm::Value * val,llvm::SmallSet<llvm::Value *,8U> * visited)33 DerivedStatus IsDerivedImpl(llvm::Value *val, llvm::SmallSet<llvm::Value *, 8U> *visited)
34 {
35 auto phi = llvm::dyn_cast<llvm::PHINode>(val);
36 if (phi != nullptr) {
37 ASSERT(phi->getNumIncomingValues() > 0);
38 if (visited == nullptr) {
39 llvm::SmallSet<llvm::Value *, 8U> lvis;
40 return IsPHIDerived(phi, &lvis);
41 }
42 return IsPHIDerived(phi, visited);
43 }
44 auto select = llvm::dyn_cast<llvm::SelectInst>(val);
45 if (select != nullptr) {
46 auto derived = IsDerivedImpl(select->getTrueValue(), visited);
47 if (derived == DerivedStatus::UNKNOWN) {
48 derived = IsDerivedImpl(select->getFalseValue(), visited);
49 } else {
50 #ifndef NDEBUG
51 auto derivedFalseBr = IsDerivedImpl(select->getFalseValue(), visited);
52 ASSERT(derived == derivedFalseBr || derivedFalseBr == DerivedStatus::UNKNOWN);
53 #endif
54 }
55 return derived;
56 }
57 // NOTE: Workaround for situation when llvm do the following during optimization pipeline:
58 // gep(ptr + const) => gep(nullptr + const) => gep(const)
59 if (auto *constantExpr = llvm::dyn_cast<llvm::ConstantExpr>(val)) {
60 if (constantExpr->getOpcode() == llvm::Instruction::IntToPtr) {
61 return DerivedStatus::UNKNOWN;
62 }
63 }
64 if (llvm::isa<llvm::IntToPtrInst>(val)) {
65 return DerivedStatus::NOT_DERIVED;
66 }
67 if (llvm::isa<llvm::CastInst>(val)) {
68 if (!val->getType()->isPointerTy()) {
69 return DerivedStatus::NOT_DERIVED;
70 }
71 auto cast = llvm::cast<llvm::CastInst>(val);
72 return IsDerivedImpl(cast->stripPointerCasts(), visited);
73 }
74 return llvm::isa<llvm::GetElementPtrInst>(val) ? DerivedStatus::DERIVED : DerivedStatus::NOT_DERIVED;
75 }
76
IsPHIDerived(llvm::PHINode * phi,llvm::SmallSet<llvm::Value *,8U> * visited)77 DerivedStatus IsPHIDerived(llvm::PHINode *phi, llvm::SmallSet<llvm::Value *, 8U> *visited)
78 {
79 ASSERT(visited != nullptr);
80 if (visited->find(phi) != visited->end()) {
81 return DerivedStatus::UNKNOWN;
82 }
83 visited->insert(phi);
84 auto result = DerivedStatus::UNKNOWN;
85 for (auto &ival : phi->incoming_values()) {
86 auto isIvalDerived = IsDerivedImpl(&(*ival), visited);
87 #ifndef NDEBUG
88 if (result == DerivedStatus::UNKNOWN && isIvalDerived != DerivedStatus::UNKNOWN) {
89 result = isIvalDerived;
90 }
91 ASSERT(isIvalDerived == result || isIvalDerived == DerivedStatus::UNKNOWN);
92 #else
93 if (isIvalDerived != DerivedStatus::UNKNOWN) {
94 return isIvalDerived;
95 }
96 #endif
97 }
98 return result;
99 }
100
HasBeenGcRef(const llvm::Value * val,bool any)101 bool HasBeenGcRef(const llvm::Value *val, bool any)
102 {
103 auto stripUntilRoot = [](const llvm::Value *toStrip) {
104 auto cast = llvm::dyn_cast<llvm::CastInst>(toStrip);
105 while (cast != nullptr && !IsGcRefType(toStrip->getType())) {
106 toStrip = cast->getOperand(0);
107 cast = llvm::dyn_cast<llvm::CastInst>(toStrip);
108 }
109 return toStrip;
110 };
111
112 auto root = stripUntilRoot(val);
113 if (IsGcRefType(root->getType())) {
114 return true;
115 }
116
117 // Roots consist only of non-GC references that are free of casts.
118 llvm::SmallVector<const llvm::Value *, 8U> roots;
119 llvm::SmallSet<const llvm::Value *, 8U> visited;
120 roots.push_back(root);
121 bool oneRef = false;
122 while (!roots.empty()) {
123 if (any && oneRef) {
124 // Do not need to process further in ANY mode.
125 return true;
126 }
127 root = roots.pop_back_val();
128 if (!visited.insert(root).second) {
129 continue;
130 }
131 if (!llvm::isa<llvm::PHINode, llvm::SelectInst>(root)) {
132 if (!llvm::isa<llvm::Constant>(root) && !any) {
133 // A non-phi and non-constant:
134 // ANY mode should continue searching a GC reference
135 // NOT-ANY mode treat it as a non GC-reference, therefore can return false.
136 return false;
137 }
138 continue;
139 }
140 auto inst = llvm::cast<llvm::Instruction>(root);
141 for (size_t i = llvm::isa<llvm::SelectInst>(inst) ? 1 : 0; i < inst->getNumOperands(); ++i) {
142 root = stripUntilRoot(inst->getOperand(i));
143 if (IsGcRefType(root->getType())) {
144 oneRef = true;
145 } else {
146 roots.push_back(root);
147 }
148 }
149 }
150 return oneRef;
151 }
152
MarkAsNonMovable(llvm::Instruction * instruction)153 void MarkAsNonMovable(llvm::Instruction *instruction)
154 {
155 ASSERT(IsGcRefType(instruction->getType()));
156 instruction->setMetadata(MD_NON_MOVABLE, llvm::MDNode::get(instruction->getContext(), {}));
157 }
158
IsNonMovable(const llvm::Value * value)159 bool IsNonMovable(const llvm::Value *value)
160 {
161 auto instruction = llvm::dyn_cast<const llvm::Instruction>(value);
162 return instruction != nullptr && instruction->hasMetadata(MD_NON_MOVABLE);
163 }
164
165 } // namespace ark::llvmbackend::gc_utils
166