1//===------------- llubi.cpp - LLVM UB-aware Interpreter --------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This utility provides an UB-aware interpreter for programs in LLVM bitcode.
10// It is not built on top of the existing ExecutionEngine interface, but instead
11// implements its own value representation, state tracking and interpreter loop.
12//
13//===----------------------------------------------------------------------===//
14
15#include "lib/Context.h"
16#include "llvm/Config/llvm-config.h"
17#include "llvm/IR/LLVMContext.h"
18#include "llvm/IR/Module.h"
19#include "llvm/IR/Type.h"
20#include "llvm/IR/Verifier.h"
21#include "llvm/IRReader/IRReader.h"
22#include "llvm/Support/CommandLine.h"
23#include "llvm/Support/Format.h"
24#include "llvm/Support/InitLLVM.h"
25#include "llvm/Support/MathExtras.h"
26#include "llvm/Support/SourceMgr.h"
27#include "llvm/Support/WithColor.h"
28#include "llvm/Support/raw_ostream.h"
29
30using namespace llvm;
31
32static cl::opt<std::string> InputFile(cl::desc("<input bitcode>"),
33 cl::Positional, cl::init(Val: "-"));
34
35static cl::list<std::string> InputArgv(cl::ConsumeAfter,
36 cl::desc("<program arguments>..."));
37
38static cl::opt<std::string>
39 EntryFunc("entry-function",
40 cl::desc("Specify the entry function (default = 'main') "
41 "of the executable"),
42 cl::value_desc("function"), cl::init(Val: "main"));
43
44static cl::opt<std::string>
45 FakeArgv0("fake-argv0",
46 cl::desc("Override the 'argv[0]' value passed into the executing"
47 " program"),
48 cl::value_desc("executable"));
49
50static cl::opt<bool>
51 Verbose("verbose", cl::desc("Print results for each instruction executed."),
52 cl::init(Val: false));
53
54cl::OptionCategory InterpreterCategory("Interpreter Options");
55
56static cl::opt<unsigned> MaxMem(
57 "max-mem",
58 cl::desc("Max amount of memory (in bytes) that can be allocated by the"
59 " program, including stack, heap, and global variables."
60 " Set to 0 to disable the limit."),
61 cl::value_desc("N"), cl::init(Val: 0), cl::cat(InterpreterCategory));
62
63static cl::opt<unsigned>
64 MaxSteps("max-steps",
65 cl::desc("Max number of instructions executed."
66 " Set to 0 to disable the limit."),
67 cl::value_desc("N"), cl::init(Val: 0), cl::cat(InterpreterCategory));
68
69static cl::opt<unsigned> MaxStackDepth(
70 "max-stack-depth",
71 cl::desc("Max stack depth (default = 256). Set to 0 to disable the limit."),
72 cl::value_desc("N"), cl::init(Val: 256), cl::cat(InterpreterCategory));
73
74static cl::opt<unsigned>
75 VScale("vscale", cl::desc("The value of llvm.vscale (default = 4)"),
76 cl::value_desc("N"), cl::init(Val: 4), cl::cat(InterpreterCategory));
77
78static cl::opt<unsigned>
79 Seed("seed",
80 cl::desc("Random seed for non-deterministic behavior (default = 0)"),
81 cl::value_desc("N"), cl::init(Val: 0), cl::cat(InterpreterCategory));
82
83static cl::opt<bool>
84 Deterministic("deterministic",
85 cl::desc("Disable interpreter-introduced non-determinism."),
86 cl::init(Val: false), cl::cat(InterpreterCategory));
87
88static cl::opt<bool> FuseFMulAdd("fuse-fmuladd",
89 cl::desc("Fuse llvm.fmuladd.* intrinsic"),
90 cl::init(Val: true), cl::cat(InterpreterCategory));
91
92static cl::opt<bool> NoVerify("disable-verify",
93 cl::desc("Do not run the IR verifier"),
94 cl::init(Val: false), cl::cat(InterpreterCategory));
95
96cl::opt<ubi::UndefValueBehavior> UndefBehavior(
97 "undef-behavior", cl::desc("Choose undef value behavior:"),
98 cl::values(clEnumValN(ubi::UndefValueBehavior::NonDeterministic, "nondet",
99 "Each load of an uninitialized byte yields a freshly "
100 "random value."),
101 clEnumValN(ubi::UndefValueBehavior::Zero, "zero",
102 "All uses of an uninitialized byte yield zero.")));
103
104cl::opt<ubi::NaNPropagationBehavior> NaNPropagationBehavior(
105 "nan-behavior", cl::desc("Choose NaN propagation behavior:"),
106 cl::values(
107 clEnumValN(ubi::NaNPropagationBehavior::NonDeterministic, "nondet",
108 "Non-deterministically choose from valid NaN results as "
109 "specified by language reference."),
110 clEnumValN(ubi::NaNPropagationBehavior::PreferredNaN, "preferred",
111 "The quiet bit is set and the payload is all-zero."),
112 clEnumValN(
113 ubi::NaNPropagationBehavior::QuietingNaN, "quieting",
114 "The quiet bit is set and the payload is copied from any input"
115 "operand that is a NaN."),
116 clEnumValN(ubi::NaNPropagationBehavior::UnchangedNaN, "unchanged",
117 "The quiet bit and payload are copied from any input operand"
118 "that is a NaN"),
119 clEnumValN(ubi::NaNPropagationBehavior::TargetSpecificNaN,
120 "target-specific",
121 "The quiet bit is set and the payload is picked from a "
122 "known target-specific set of \"extra\" possible NaN "
123 "payloads.")),
124 cl::init(Val: ubi::NaNPropagationBehavior::NonDeterministic));
125
126class NoopEventHandler : public ubi::EventHandler {
127 void onImmediateUB(StringRef Msg) override {
128 errs() << "Immediate UB detected: " << Msg << '\n';
129 }
130
131 void onError(StringRef Msg) override { errs() << "Error: " << Msg << '\n'; }
132
133 void onUnrecognizedInstruction(Instruction &I) override {
134 errs() << "Unrecognized instruction: " << I << '\n';
135 }
136};
137
138class VerboseEventHandler : public NoopEventHandler {
139 ubi::AnyValuePrinter OS;
140
141public:
142 VerboseEventHandler(ubi::Context &Ctx) : OS(Ctx, errs()) {}
143
144 bool onInstructionExecuted(Instruction &I,
145 const ubi::AnyValue &Result) override {
146 if (Result.isNone()) {
147 OS << I << '\n';
148 } else {
149 OS << I << " => " << Result << '\n';
150 }
151
152 return true;
153 }
154
155 bool onBBJump(Instruction &I, BasicBlock &To) override {
156 OS << I << " jump to ";
157 To.printAsOperand(O&: OS, /*PrintType=*/false);
158 OS << '\n';
159 return true;
160 }
161
162 bool onFunctionEntry(Function &F, ArrayRef<ubi::AnyValue> Args,
163 CallBase *CallSite) override {
164 OS << "Entering function: " << F.getName() << '\n';
165 size_t ArgSize = F.arg_size();
166 for (auto &&[Idx, Arg] : enumerate(First&: Args)) {
167 if (Idx >= ArgSize)
168 OS << " vaarg[" << (Idx - ArgSize) << "] = " << Arg << '\n';
169 else
170 OS << " " << *F.getArg(i: Idx) << " = " << Arg << '\n';
171 }
172 return true;
173 }
174
175 bool onFunctionExit(Function &F, const ubi::AnyValue &RetVal) override {
176 OS << "Exiting function: " << F.getName() << '\n';
177 return true;
178 }
179
180 void onProgramExit(const ubi::ProgramExitInfo &Info) override {
181 switch (Info.Kind) {
182 case ubi::ProgramExitInfo::ProgramExitKind::Returned:
183 return;
184 case ubi::ProgramExitInfo::ProgramExitKind::Failed:
185 return;
186 case ubi::ProgramExitInfo::ProgramExitKind::Exited:
187 OS << "Program exited with code " << Info.ExitCode << '\n';
188 return;
189 case ubi::ProgramExitInfo::ProgramExitKind::Aborted:
190 OS << "Program aborted.\n";
191 return;
192 case ubi::ProgramExitInfo::ProgramExitKind::Terminated:
193 OS << "Program terminated.\n";
194 return;
195 }
196
197 llvm_unreachable("Unknown ProgramExitKind");
198 }
199};
200
201int main(int argc, char **argv) {
202 InitLLVM X(argc, argv);
203
204 cl::ParseCommandLineOptions(argc, argv, Overview: "llvm ub-aware interpreter\n");
205
206 if (EntryFunc.empty()) {
207 WithColor::error() << "--entry-function name cannot be empty\n";
208 return 1;
209 }
210
211 if (VScale == 0) {
212 WithColor::error() << "--vscale value must be positive\n";
213 return 1;
214 }
215
216 if (!isPowerOf2_32(Value: VScale)) {
217 WithColor::error() << "--vscale value must be a power of 2\n";
218 return 1;
219 }
220
221 LLVMContext Context;
222
223 // Load the bitcode...
224 SMDiagnostic Err;
225 AsmParserContext ParserContext;
226 std::unique_ptr<Module> Owner =
227 parseIRFile(Filename: InputFile, Err, Context, /*Callbacks=*/{}, ParserContext: &ParserContext);
228 Module *Mod = Owner.get();
229 if (!Mod) {
230 Err.print(ProgName: argv[0], S&: errs());
231 return 1;
232 }
233
234 if (!NoVerify && verifyModule(M: *Mod, OS: &errs())) {
235 WithColor::error() << InputFile << ": input module is broken!\n";
236 return 1;
237 }
238
239 // If the user specifically requested an argv[0] to pass into the program,
240 // do it now.
241 if (!FakeArgv0.empty()) {
242 InputFile = static_cast<std::string>(FakeArgv0);
243 } else {
244 // Otherwise, if there is a .bc suffix on the executable strip it off, it
245 // might confuse the program.
246 if (StringRef(InputFile).ends_with(Suffix: ".bc"))
247 InputFile.erase(pos: InputFile.length() - 3);
248 }
249
250 // Add the module's name to the start of the vector of arguments to main().
251 InputArgv.insert(pos: InputArgv.begin(), value: InputFile);
252
253 // Initialize the execution context and set parameters.
254 ubi::Context Ctx(*Mod, &ParserContext);
255 Ctx.setMemoryLimit(MaxMem);
256 Ctx.setVScale(VScale);
257 Ctx.setMaxSteps(MaxSteps);
258 Ctx.setMaxStackDepth(MaxStackDepth);
259 Ctx.setFusedMultiplyAdd(FuseFMulAdd);
260 Ctx.setDeterministic(Deterministic);
261 Ctx.setUndefValueBehavior(UndefBehavior);
262 Ctx.setNaNPropagationBehavior(NaNPropagationBehavior);
263 Ctx.reseed(Seed);
264
265 if (!Ctx.initGlobalValues()) {
266 WithColor::error() << "Failed to initialize global values (e.g., the "
267 "memory limit may be too low).\n";
268 return 1;
269 }
270
271 // Call the main function from M as if its signature were:
272 // int main (int argc, char **argv)
273 // using the contents of Args to determine argc & argv
274 Function *EntryFn = Mod->getFunction(Name: EntryFunc);
275 if (!EntryFn) {
276 WithColor::error() << '\'' << EntryFunc
277 << "\' function not found in module.\n";
278 return 1;
279 }
280 TargetLibraryInfo TLI(Ctx.getTLIImpl());
281 Type *IntTy = IntegerType::get(C&: Ctx.getContext(), NumBits: TLI.getIntSize());
282 Type *PtrTy = PointerType::getUnqual(C&: Ctx.getContext());
283 auto *MainFuncTy = FunctionType::get(Result: IntTy, Params: {IntTy, PtrTy}, isVarArg: false);
284 SmallVector<ubi::AnyValue> Args;
285 if (EntryFn->getFunctionType() == MainFuncTy) {
286 const ubi::AnyValue *Argc =
287 Ctx.getConstantValue(C: ConstantInt::get(Ty: IntTy, V: InputArgv.size()));
288 assert(Argc && "failed to initialize argc");
289 Args.push_back(Elt: *Argc);
290
291 uint32_t PtrSize = Ctx.getDataLayout().getPointerSize();
292 uint64_t PtrsSize = PtrSize * (InputArgv.size() + 1);
293 auto ArgvPtrsMem = Ctx.allocate(Size: PtrsSize, Align: 8, Name: "argv",
294 /*AS=*/0, InitKind: ubi::MemInitKind::Zeroed,
295 AllocKind: ubi::MemAllocKind::Global);
296 if (!ArgvPtrsMem) {
297 WithColor::error() << "Failed to allocate memory for argv pointers.\n";
298 return 1;
299 }
300 for (const auto &[Idx, Arg] : enumerate(First&: InputArgv)) {
301 uint64_t Size = Arg.length() + 1;
302 auto ArgvStrMem = Ctx.allocate(Size, Align: 8, Name: "argv_str",
303 /*AS=*/0, InitKind: ubi::MemInitKind::Zeroed,
304 AllocKind: ubi::MemAllocKind::Global);
305 if (!ArgvStrMem) {
306 WithColor::error() << "Failed to allocate memory for argv strings.\n";
307 return 1;
308 }
309 ubi::Pointer ArgPtr = Ctx.deriveFromMemoryObject(Obj: ArgvStrMem);
310 Ctx.storeRawBytes(MO&: *ArgvStrMem, Offset: 0, Data: Arg.c_str(), Size: Arg.length());
311 Ctx.store(MO&: *ArgvPtrsMem, Offset: Idx * PtrSize, Val: ArgPtr, ValTy: PtrTy);
312 }
313 Args.push_back(Elt: Ctx.deriveFromMemoryObject(Obj: ArgvPtrsMem));
314 } else if (!EntryFn->arg_empty()) {
315 // If the signature does not match (e.g., llvm-reduce change the signature
316 // of main), it will pass null values for all arguments.
317 WithColor::warning()
318 << "The signature of function '" << EntryFunc
319 << "' does not match 'int main(int, char**)', passing null values for "
320 "all arguments.\n";
321 Args.reserve(N: EntryFn->arg_size());
322 for (Argument &Arg : EntryFn->args())
323 Args.push_back(Elt: ubi::AnyValue::getNullValue(Ctx, Ty: Arg.getType()));
324 }
325
326 NoopEventHandler NoopHandler;
327 VerboseEventHandler VerboseHandler(Ctx);
328 ubi::AnyValue RetVal;
329 ubi::ProgramExitInfo ExitInfo = Ctx.runFunction(
330 F&: *EntryFn, Args, RetVal, Handler&: Verbose ? VerboseHandler : NoopHandler);
331 switch (ExitInfo.Kind) {
332 case ubi::ProgramExitInfo::ProgramExitKind::Failed:
333 WithColor::error() << "Execution of function '" << EntryFunc
334 << "' failed.\n";
335 return 1;
336 case ubi::ProgramExitInfo::ProgramExitKind::Aborted:
337 case ubi::ProgramExitInfo::ProgramExitKind::Terminated:
338 return 134;
339 case ubi::ProgramExitInfo::ProgramExitKind::Exited:
340 return static_cast<int>(ExitInfo.ExitCode & 0xFF);
341 case ubi::ProgramExitInfo::ProgramExitKind::Returned:
342 // If the function returns an integer, return that as the exit code.
343 if (EntryFn->getReturnType()->isIntegerTy()) {
344 assert(!RetVal.isNone() && "Expected a return value from entry function");
345 if (RetVal.isPoison()) {
346 WithColor::error() << "Execution of function '" << EntryFunc
347 << "' resulted in poison return value.\n";
348 return 1;
349 }
350 APInt Result = RetVal.asInteger();
351 return (int)Result.extractBitsAsZExtValue(
352 numBits: std::min(a: Result.getBitWidth(), b: 8U), bitPosition: 0);
353 }
354 return 0;
355 }
356
357 llvm_unreachable("Unknown ProgramExitKind");
358}
359