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