1 //===-- FunctionAliasPass.cpp -----------------------------------*- C++ -*-===//
2 //
3 // The KLEE Symbolic Virtual Machine
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "Passes.h"
11
12 #include "klee/Support/Casting.h"
13 #include "klee/Support/ErrorHandling.h"
14 #include "klee/Support/OptionCategories.h"
15
16 #include "llvm/IR/GlobalAlias.h"
17 #include "llvm/Support/CommandLine.h"
18 #include "llvm/Support/Regex.h"
19
20 using namespace llvm;
21
22 namespace {
23
24 cl::list<std::string>
25 FunctionAlias("function-alias",
26 cl::desc("Replace functions that match name or regular "
27 "expression pattern with an alias to the function "
28 "whose name is given by replacement"),
29 cl::value_desc("name|pattern>:<replacement"),
30 cl::cat(klee::ModuleCat));
31
32 } // namespace
33
34 namespace klee {
35
runOnModule(Module & M)36 bool FunctionAliasPass::runOnModule(Module &M) {
37 bool modified = false;
38
39 #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 9)
40 assert((M.ifunc_size() == 0) && "Unexpected ifunc");
41 #endif
42
43 for (const auto &pair : FunctionAlias) {
44 bool matchFound = false;
45
46 // regex pattern can contain colons, e.g. in character classes,
47 // but replacement function name cannot
48 std::size_t lastColon = pair.rfind(':');
49 if (lastColon == std::string::npos) {
50 klee_error("function-alias: no replacement given");
51 }
52 std::string pattern = pair.substr(0, lastColon);
53 std::string replacement = pair.substr(lastColon + 1);
54
55 if (pattern.empty())
56 klee_error("function-alias: name or pattern cannot be empty");
57 if (replacement.empty())
58 klee_error("function-alias: replacement cannot be empty");
59
60 if (pattern == replacement) {
61 klee_error("function-alias: @%s cannot replace itself", pattern.c_str());
62 }
63
64 // check if replacement function exists
65 GlobalValue *replacementValue = M.getNamedValue(replacement);
66 if (!isFunctionOrGlobalFunctionAlias(replacementValue))
67 klee_error("function-alias: replacement function @%s could not be found",
68 replacement.c_str());
69
70 // directly replace if pattern is not a regex
71 GlobalValue *match = M.getNamedValue(pattern);
72 if (isFunctionOrGlobalFunctionAlias(match)) {
73 if (tryToReplace(match, replacementValue)) {
74 modified = true;
75 klee_message("function-alias: replaced @%s with @%s", pattern.c_str(),
76 replacement.c_str());
77 continue;
78 }
79 }
80 if (match != nullptr) {
81 // pattern is not a regex, but no replacement was found
82 klee_error("function-alias: no (replacable) match for '%s' found",
83 pattern.c_str());
84 }
85
86 Regex regex(pattern);
87 std::string error;
88 if (!regex.isValid(error)) {
89 klee_error("function-alias: '%s' is not a valid regex: %s",
90 pattern.c_str(), error.c_str());
91 }
92
93 std::vector<GlobalValue *> matches;
94
95 // find matches for regex
96 #if LLVM_VERSION_CODE >= LLVM_VERSION(5, 0)
97 for (GlobalValue &global : M.global_values()) {
98 #else
99 // chain iterators of alias list and function list
100 auto firstIt = M.getAliasList().begin();
101 auto firstIe = M.getAliasList().end();
102 auto secondIt = M.getFunctionList().begin();
103 auto secondIe = M.getFunctionList().end();
104 for (bool firstList = true;;
105 (firstList && (++firstIt != firstIe)) || (++secondIt != secondIe)) {
106 GlobalValue *gv = nullptr;
107 if (firstIt == firstIe)
108 firstList = false;
109 if (firstList) {
110 gv = cast<GlobalValue>(&*firstIt);
111 } else {
112 if (secondIt == secondIe)
113 break;
114 gv = cast<GlobalValue>(&*secondIt);
115 }
116 GlobalValue &global = *gv;
117 #endif
118 if (!global.hasName())
119 continue;
120
121 if (!isFunctionOrGlobalFunctionAlias(&global))
122 continue;
123
124 SmallVector<StringRef, 8> matchVec;
125 bool match = regex.match(global.getName(), &matchVec);
126 if (match && matchVec[0].str() == global.getName().str()) {
127 if (global.getName().str() == replacement) {
128 klee_warning("function-alias: do not replace @%s (matching '%s') "
129 "with @%s: cannot replace itself",
130 global.getName().str().c_str(), pattern.c_str(),
131 replacement.c_str());
132 continue;
133 }
134 matches.push_back(&global);
135 }
136 }
137
138 // replace all found regex matches
139 for (GlobalValue *global : matches) {
140 // name will be invalidated by tryToReplace
141 std::string name = global->getName().str();
142 if (tryToReplace(global, replacementValue)) {
143 modified = true;
144 matchFound = true;
145 klee_message("function-alias: replaced @%s (matching '%s') with @%s",
146 name.c_str(), pattern.c_str(), replacement.c_str());
147 }
148 }
149
150 if (!matchFound) {
151 klee_error("function-alias: no (replacable) match for '%s' found",
152 pattern.c_str());
153 }
154 }
155
156 return modified;
157 }
158
159 const FunctionType *FunctionAliasPass::getFunctionType(const GlobalValue *gv) {
160 const Type *type = gv->getType();
161 while (type->isPointerTy()) {
162 const PointerType *ptr = cast<PointerType>(type);
163 type = ptr->getElementType();
164 }
165 return cast<FunctionType>(type);
166 }
167
168 bool FunctionAliasPass::checkType(const GlobalValue *match,
169 const GlobalValue *replacement) {
170 const FunctionType *MFT = getFunctionType(match);
171 const FunctionType *RFT = getFunctionType(replacement);
172 assert(MFT != nullptr && RFT != nullptr);
173
174 if (MFT->getReturnType() != RFT->getReturnType()) {
175 klee_warning("function-alias: @%s could not be replaced with @%s: "
176 "return type differs",
177 match->getName().str().c_str(),
178 replacement->getName().str().c_str());
179 return false;
180 }
181
182 if (MFT->isVarArg() != RFT->isVarArg()) {
183 klee_warning("function-alias: @%s could not be replaced with @%s: "
184 "one has varargs while the other does not",
185 match->getName().str().c_str(),
186 replacement->getName().str().c_str());
187 return false;
188 }
189
190 if (MFT->getNumParams() != RFT->getNumParams()) {
191 klee_warning("function-alias: @%s could not be replaced with @%s: "
192 "number of parameters differs",
193 match->getName().str().c_str(),
194 replacement->getName().str().c_str());
195 return false;
196 }
197
198 std::size_t numParams = MFT->getNumParams();
199 for (std::size_t i = 0; i < numParams; ++i) {
200 if (MFT->getParamType(i) != RFT->getParamType(i)) {
201 klee_warning("function-alias: @%s could not be replaced with @%s: "
202 "parameter types differ",
203 match->getName().str().c_str(),
204 replacement->getName().str().c_str());
205 return false;
206 }
207 }
208 return true;
209 }
210
211 bool FunctionAliasPass::tryToReplace(GlobalValue *match,
212 GlobalValue *replacement) {
213 if (!checkType(match, replacement))
214 return false;
215
216 GlobalAlias *alias = GlobalAlias::create("", replacement);
217 match->replaceAllUsesWith(alias);
218 alias->takeName(match);
219 match->eraseFromParent();
220
221 return true;
222 }
223
224 bool FunctionAliasPass::isFunctionOrGlobalFunctionAlias(const GlobalValue *gv) {
225 if (isa_and_nonnull<Function>(gv))
226 return true;
227
228 if (const auto *ga = dyn_cast_or_null<GlobalAlias>(gv)) {
229 const auto *aliasee = dyn_cast<GlobalValue>(ga->getAliasee());
230 if (!aliasee) {
231 // check if GlobalAlias is alias bitcast
232 const auto *cexpr = dyn_cast<ConstantExpr>(ga->getAliasee());
233 if (!cexpr || !cexpr->isCast())
234 return false;
235 aliasee = dyn_cast<GlobalValue>(cexpr->getOperand(0));
236 }
237 return isFunctionOrGlobalFunctionAlias(aliasee);
238 }
239
240 return false;
241 }
242
243 char FunctionAliasPass::ID = 0;
244
245 } // namespace klee
246