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 <unordered_map>
17
18 #include "transforms/passes/ark_gvn.h"
19 #include "transforms/transform_utils.h"
20
21 #include "llvm_ark_interface.h"
22 #include "transforms/builtins.h"
23 #include "utils.h"
24
25 #include <llvm/Pass.h>
26 #include <llvm/IR/Module.h>
27 #include <llvm/IR/Verifier.h>
28 #include <llvm/IR/Dominators.h>
29 #include <llvm/Transforms/Utils/BasicBlockUtils.h>
30 #include <llvm/ADT/DenseMapInfo.h>
31 #include <llvm/ADT/Hashing.h>
32 #include <llvm/ADT/StringSwitch.h>
33
34 namespace ark::llvmbackend::passes {
35
36 using ark::llvmbackend::utils::CopyDebugLoc;
37 using ark::llvmbackend::utils::CopyDeoptBundle;
38 using ark::llvmbackend::utils::GetMethodIdFromAttr;
39 using builtins::LoadClass;
40 using builtins::LoadInitClass;
41 using builtins::LoadString;
42 using builtins::ResolveVirtual;
43
Create(LLVMArkInterface * arkInterface,const ark::llvmbackend::LLVMCompilerOptions * options)44 ArkGVN ArkGVN::Create(LLVMArkInterface *arkInterface,
45 [[maybe_unused]] const ark::llvmbackend::LLVMCompilerOptions *options)
46 {
47 return ArkGVN(arkInterface);
48 }
49
ArkGVN(LLVMArkInterface * arkInterface)50 ArkGVN::ArkGVN(LLVMArkInterface *arkInterface) : arkInterface_ {arkInterface} {}
51
run(llvm::Function & function,llvm::FunctionAnalysisManager & analysisManager)52 llvm::PreservedAnalyses ArkGVN::run(llvm::Function &function, llvm::FunctionAnalysisManager &analysisManager)
53 {
54 ASSERT(workStack_.empty());
55 ASSERT(bbTables_.empty());
56 GvnBuiltins builtins = {LoadClass(function.getParent()), LoadInitClass(function.getParent()),
57 LoadString(function.getParent()), ResolveVirtual(function.getParent())};
58
59 auto &tree = analysisManager.getResult<llvm::DominatorTreeAnalysis>(function);
60 bool changed = RunOnFunction(tree, builtins);
61 ASSERT(workStack_.empty());
62 bbTables_.clear();
63 return changed ? llvm::PreservedAnalyses::none() : llvm::PreservedAnalyses::all();
64 }
65
CreateCallBuiltin(llvm::CallInst * callInst,uint32_t compiledEntrypointOffset)66 void CreateCallBuiltin(llvm::CallInst *callInst, uint32_t compiledEntrypointOffset)
67 {
68 auto isLaunchCall = callInst->hasFnAttr("is-launch-call");
69 llvm::Value *thiz = callInst->getArgOperand(isLaunchCall ? callInst->arg_size() - 1 : 1);
70 ASSERT(thiz->getType()->isPointerTy());
71
72 auto builder = llvm::IRBuilder<>(callInst);
73 auto builtin = ResolveVirtual(callInst->getModule());
74 auto zero = builder.getInt64(0);
75 auto arrayType = llvm::ArrayType::get(builder.getInt64Ty(), 0);
76 auto offset = builder.CreateIntToPtr(zero, arrayType->getPointerTo());
77
78 auto methodId = GetMethodIdFromAttr(callInst);
79 auto builtinCallInst =
80 builder.CreateCall(builtin, {thiz, builder.getInt64(methodId), offset}, CopyDeoptBundle(callInst));
81 CopyDebugLoc(callInst, builtinCallInst);
82 if (callInst->hasFnAttr("inline-info")) {
83 builtinCallInst->addFnAttr(callInst->getFnAttr("inline-info"));
84 }
85
86 if (!isLaunchCall) {
87 auto method = builder.CreateIntToPtr(builtinCallInst, builder.getPtrTy());
88 auto *fType = callInst->getFunctionType();
89 auto entrypointPtr = builder.CreateConstInBoundsGEP1_32(builder.getInt8Ty(), method, compiledEntrypointOffset);
90 auto entrypoint = builder.CreateLoad(builder.getPtrTy(), entrypointPtr);
91 callInst->setCalledFunction(fType, entrypoint);
92 }
93 callInst->setArgOperand(0, builtinCallInst);
94 callInst->setAttributes(callInst->getAttributes().removeFnAttribute(callInst->getContext(), "original-method-id"));
95 }
96
RunOnFunction(const llvm::DominatorTree & tree,const GvnBuiltins & builtins)97 bool ArkGVN::RunOnFunction(const llvm::DominatorTree &tree, const GvnBuiltins &builtins)
98 {
99 bool changed = false;
100 workStack_.push_back(tree.getRoot());
101 while (!workStack_.empty()) {
102 auto block = workStack_.back();
103 changed |= RunOnBasicBlock(block, tree, builtins);
104 workStack_.pop_back();
105 for (const auto &child : tree.getNode(block)->children()) {
106 workStack_.push_back(child->getBlock());
107 }
108 }
109 return changed;
110 }
111
RunOnBasicBlock(llvm::BasicBlock * block,const llvm::DominatorTree & tree,const GvnBuiltins & builtins)112 bool ArkGVN::RunOnBasicBlock(llvm::BasicBlock *block, const llvm::DominatorTree &tree, const GvnBuiltins &builtins)
113 {
114 bool changed = false;
115 llvm::SmallVector<llvm::CallInst *> replace;
116 for (auto &inst : *block) {
117 auto callInst = llvm::dyn_cast<llvm::CallInst>(&inst);
118 if (callInst != nullptr && callInst->hasFnAttr("original-method-id") &&
119 (arkInterface_->IsInterfaceMethod(callInst) || callInst->hasFnAttr("is-launch-call"))) {
120 replace.push_back(callInst);
121 }
122 }
123 for (auto &inst : replace) {
124 CreateCallBuiltin(inst, arkInterface_->GetCompiledEntryPointOffset());
125 changed = true;
126 }
127 for (auto iter = block->begin(), endIter = block->end(); iter != endIter;) {
128 auto callInst = llvm::dyn_cast<llvm::CallInst>(&*(iter++));
129 if (callInst == nullptr) {
130 continue;
131 }
132
133 auto builtinKey = ParseBuiltin(callInst, builtins);
134 if (builtinKey.builtinTy == BuiltinType::NONE) {
135 continue;
136 }
137
138 llvm::Value *alternative = FindDominantCall(builtinKey, block, tree);
139 if (alternative != nullptr) {
140 ASSERT(tree.dominates(alternative, callInst));
141 // need replace instruction by another
142 callInst->replaceAllUsesWith(alternative);
143 callInst->eraseFromParent();
144 changed = true;
145 continue;
146 }
147 if (builtinKey.builtinTy == RESOLVE_VIRTUAL_METHOD && arkInterface_->IsArm64() &&
148 llvm::isa<llvm::ConstantInt>(callInst->getOperand(1))) {
149 auto slotId = arkInterface_->CreateIntfInlineCacheSlotId(callInst->getFunction());
150 auto aotGot = callInst->getModule()->getGlobalVariable("__aot_got");
151 auto builder = llvm::IRBuilder<>(callInst);
152 auto arrayType = llvm::ArrayType::get(builder.getInt64Ty(), 0);
153 llvm::Value *slot = builder.CreateConstInBoundsGEP2_64(arrayType, aotGot, 0, slotId);
154 callInst->setArgOperand(2U, slot);
155 changed = true;
156 }
157
158 bbTables_[block].insert({builtinKey, callInst});
159 if (builtinKey.builtinTy == LOAD_AND_INIT_CLASS) {
160 BuiltinKey loadClass = builtinKey;
161 loadClass.builtinTy = LOAD_CLASS;
162 bbTables_[block].insert({loadClass, callInst});
163 }
164 }
165 return changed;
166 }
167
ParseBuiltin(const llvm::CallInst * callInst,const GvnBuiltins & builtins)168 ArkGVN::BuiltinKey ArkGVN::ParseBuiltin(const llvm::CallInst *callInst, const GvnBuiltins &builtins)
169 {
170 BuiltinKey result;
171 if (callInst == nullptr) {
172 return result;
173 }
174 auto calledFunc = callInst->getCalledFunction();
175 if (calledFunc == nullptr) {
176 return result;
177 }
178 auto builtin = std::find(builtins.begin(), builtins.end(), calledFunc);
179 if (builtin == builtins.end()) {
180 return result;
181 }
182
183 auto builtinTy = static_cast<BuiltinType>(builtin - builtins.begin());
184 // Parse arguments
185 if (builtinTy == LOAD_AND_INIT_CLASS || builtinTy == LOAD_CLASS || builtinTy == LOAD_STRING) {
186 auto typeId = callInst->getOperand(0U);
187 if (!llvm::isa<llvm::ConstantInt>(typeId)) {
188 return result;
189 }
190 result.args.push_back(typeId);
191 } else if (builtinTy == RESOLVE_VIRTUAL_METHOD) {
192 auto thiz = callInst->getOperand(0U);
193 auto methodId = callInst->getOperand(1U);
194
195 result.args.push_back(thiz);
196 result.args.push_back(methodId);
197 } else {
198 llvm_unreachable("Unsupported builtin type");
199 }
200
201 result.builtinTy = builtinTy;
202
203 return result;
204 }
205
FindDominantCall(const ArkGVN::BuiltinKey & curBuiltin,llvm::BasicBlock * block,const llvm::DominatorTree & tree)206 llvm::Value *ArkGVN::FindDominantCall(const ArkGVN::BuiltinKey &curBuiltin, llvm::BasicBlock *block,
207 const llvm::DominatorTree &tree)
208 {
209 do {
210 auto table = bbTables_[block];
211 auto dominant = table.find(curBuiltin);
212 if (dominant != table.end()) {
213 return dominant->second;
214 }
215 auto idom = tree.getNode(block)->getIDom();
216 block = idom == nullptr ? nullptr : idom->getBlock();
217 } while (block != nullptr);
218 return nullptr;
219 }
220
221 } // namespace ark::llvmbackend::passes
222