1//===--- Context.h - State Tracking for llubi -------------------*- 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#ifndef LLVM_TOOLS_LLUBI_CONTEXT_H
10#define LLVM_TOOLS_LLUBI_CONTEXT_H
11
12#include "Value.h"
13#include "llvm/ADT/DenseMap.h"
14#include "llvm/Analysis/TargetLibraryInfo.h"
15#include "llvm/AsmParser/AsmParserContext.h"
16#include "llvm/IR/FPEnv.h"
17#include "llvm/IR/Module.h"
18#include "llvm/IR/Operator.h"
19#include <map>
20#include <optional>
21#include <random>
22
23namespace llvm::ubi {
24
25enum class MemInitKind {
26 Zeroed,
27 Uninitialized,
28 Poisoned,
29};
30
31enum class MemAllocKind {
32 Global,
33 BlockAddress,
34 Stack,
35 Malloc,
36 New,
37 NewArray,
38};
39
40enum class MemoryObjectState {
41 // This memory object is accessible.
42 // Valid transitions:
43 // -> Dead (after the end of lifetime of an alloca)
44 // -> Freed (after free is called on a heap object)
45 Alive,
46 // This memory object is out of lifetime. Its contents are poison. Loads and
47 // memory transfers from it are allowed and propagate poison, stores to it
48 // cause immediate UB, and non-accessing operations such as getelementptr are
49 // allowed.
50 // Valid transition:
51 // -> Alive (after the start of lifetime of an alloca)
52 Dead,
53 // This heap memory object has been freed. Any access to it
54 // causes immediate UB. Like dead objects, it is still possible to
55 // perform operations that do not access its content.
56 Freed,
57};
58
59enum class UndefValueBehavior {
60 NonDeterministic, // Each use of the undef value can yield different results.
61 Zero, // All uses of the undef value yield zero.
62};
63
64enum class NaNPropagationBehavior {
65 NonDeterministic, // Non-deterministically choose from valid NaN results
66 PreferredNaN, // The quiet bit is set and the payload is all-zero
67 QuietingNaN, // The quiet bit is set and the payload is copied from any input
68 // operand that is a NaN
69 UnchangedNaN, // The quiet bit and payload are copied from any input operand
70 // that is a NaN
71 TargetSpecificNaN // The quiet bit is set and the payload is picked from a
72 // known target-specific set of "extra" possible NaN
73 // payloads
74};
75
76struct ProgramExitInfo {
77 enum class ProgramExitKind {
78 // Program exited via a normal return
79 Returned,
80 // Program exited with an interpreter error (UB/Unsupported
81 // instruction/etc.)
82 Failed,
83 // Program exited via a call to exit()
84 Exited,
85 // Program exited via a call to abort()
86 Aborted,
87 // Program exited via a call to terminate()
88 Terminated,
89 };
90
91 ProgramExitKind Kind;
92 uint64_t ExitCode;
93
94 explicit ProgramExitInfo(ProgramExitKind Kind, uint64_t ExitCode)
95 : Kind(Kind), ExitCode(ExitCode) {}
96
97 bool isExitedByLibcall() const {
98 return Kind == ProgramExitKind::Exited ||
99 Kind == ProgramExitKind::Aborted ||
100 Kind == ProgramExitKind::Terminated;
101 }
102};
103
104class MemoryObject : public RefCountedBase<MemoryObject> {
105 uint64_t Address;
106 uint64_t Size;
107 SmallVector<Byte, 8> Bytes;
108 StringRef Name;
109 unsigned AS;
110
111 MemoryObjectState State;
112 MemAllocKind AllocKind;
113 bool IsConstant = false;
114 bool IsIRGlobalValue = false;
115
116 // Tagged provenances related to this memory object.
117 // It is used to erasing the tags after the memory object is freed.
118 SmallVector<APInt> AssociatedTags;
119
120 friend class Context;
121
122public:
123 MemoryObject(uint64_t Addr, uint64_t Size, StringRef Name, unsigned AS,
124 MemInitKind InitKind, MemAllocKind AllocKind,
125 bool IsIRGlobalValue = false);
126 MemoryObject(const MemoryObject &) = delete;
127 MemoryObject(MemoryObject &&) = delete;
128 MemoryObject &operator=(const MemoryObject &) = delete;
129 MemoryObject &operator=(MemoryObject &&) = delete;
130 ~MemoryObject();
131
132 uint64_t getAddress() const { return Address; }
133 uint64_t getSize() const { return Size; }
134 StringRef getName() const { return Name; }
135 unsigned getAddressSpace() const { return AS; }
136 MemoryObjectState getState() const { return State; }
137 void setState(MemoryObjectState S) { State = S; }
138 MemAllocKind getAllocKind() const { return AllocKind; }
139 bool isIRGlobalValue() const { return IsIRGlobalValue; }
140 bool isConstant() const { return IsConstant; }
141 void setIsConstant(bool C) { IsConstant = C; }
142
143 bool inBounds(const APInt &NewAddr) const {
144 return NewAddr.uge(RHS: Address) && NewAddr.ule(RHS: Address + Size);
145 }
146
147 Byte &operator[](uint64_t Offset) {
148 assert(Offset < Size && "Offset out of bounds");
149 return Bytes[Offset];
150 }
151 ArrayRef<Byte> getBytes() const { return Bytes; }
152 MutableArrayRef<Byte> getBytes() { return Bytes; }
153
154 bool isGlobal() const;
155 bool isStackAllocated() const;
156 bool isHeapAllocated() const;
157};
158
159/// An interface for handling events and managing outputs during interpretation.
160/// If the handler returns false from any of the methods, the interpreter will
161/// stop execution immediately.
162class EventHandler {
163public:
164 virtual ~EventHandler() = default;
165
166 virtual bool onInstructionExecuted(Instruction &I, const AnyValue &Result) {
167 return true;
168 }
169 virtual void onError(StringRef Msg) {}
170 virtual void onUnrecognizedInstruction(Instruction &I) {}
171 virtual void onImmediateUB(StringRef Msg) {}
172 virtual bool onBBJump(Instruction &I, BasicBlock &To) { return true; }
173 virtual bool onFunctionEntry(Function &F, ArrayRef<AnyValue> Args,
174 CallBase *CallSite) {
175 return true;
176 }
177 virtual bool onFunctionExit(Function &F, const AnyValue &RetVal) {
178 return true;
179 }
180 virtual void onProgramExit(const ProgramExitInfo &ExitInfo) {}
181 virtual bool onPrint(StringRef Msg) {
182 outs() << Msg;
183 outs().flush();
184 return true;
185 }
186};
187
188/// Endianness aware accessor for bytes.
189template <typename ArrayRefT> class BytesView {
190 ArrayRefT Bytes;
191 bool IsLittleEndian;
192
193public:
194 explicit BytesView(ArrayRefT Ref, bool IsLittleEndian)
195 : Bytes(Ref), IsLittleEndian(IsLittleEndian) {}
196 explicit BytesView(ArrayRefT Ref, const DataLayout &DL)
197 : BytesView(Ref, DL.isLittleEndian()) {}
198
199 auto &operator[](uint32_t Index) {
200 return Bytes[IsLittleEndian ? Index : Bytes.size() - 1 - Index];
201 }
202
203 size_t size() const { return Bytes.size(); }
204};
205
206using ConstBytesView = BytesView<ArrayRef<Byte>>;
207using MutableBytesView = BytesView<MutableArrayRef<Byte>>;
208
209class MaterializedConstant : public AnyValue {
210 bool Cacheable;
211
212public:
213 MaterializedConstant(std::nullopt_t) : Cacheable(false) {}
214 MaterializedConstant(AnyValue V, bool Cacheable)
215 : AnyValue(std::move(V)), Cacheable(Cacheable) {}
216
217 bool isCacheable() const { return Cacheable; }
218};
219
220/// The global context for the interpreter.
221/// It tracks global state such as heap memory objects and floating point
222/// environment.
223class Context {
224 // Module
225 LLVMContext &Ctx;
226 Module &M;
227 const AsmParserContext *ParserContext;
228 const DataLayout &DL;
229 const TargetLibraryInfoImpl TLIImpl;
230
231 // Configuration
232 uint64_t MaxMem = 0;
233 uint32_t VScale = 4;
234 uint32_t MaxSteps = 0;
235 uint32_t MaxStackDepth = 256;
236 bool Deterministic = false;
237 UndefValueBehavior UndefBehavior = UndefValueBehavior::NonDeterministic;
238 NaNPropagationBehavior NaNBehavior = NaNPropagationBehavior::NonDeterministic;
239 bool FusedMultiplyAdd = false;
240
241 std::mt19937_64 Rng;
242 /// Always returns a random APInt value. It is not controlled by
243 /// Deterministic.
244 APInt generateRandomAPInt(uint32_t BitWidth);
245
246 // Memory
247 uint64_t UsedMem = 0;
248 // The addresses of memory objects are monotonically increasing.
249 // For now we don't model the behavior of address reuse, which is common
250 // with stack coloring.
251 uint64_t AllocationBase = 8;
252 // All live memory objects.
253 DenseMap<uint64_t, IntrusiveRefCntPtr<MemoryObject>> MemoryObjects;
254 // Mapping from tags to provenances. Tags are lazily generated when a
255 // pointer is captured by memory.
256 DenseMap<APInt, IntrusiveRefCntPtr<Provenance>> TaggedProvenances;
257 // Maintains a global list of 'exposed' provenances. This is used to convert
258 // an address back to a pointer with a previously exposed provenance. In
259 // theory the provenance is picked from all previously exposed provenances
260 // using angelic non-determinism. Since llubi is just an interpreter, we make
261 // two approximations:
262 // 1. Each address maps to at most one memory object during the execution of
263 // the program, as AllocationBase increases monotonically.
264 // 2. We maintain the set of exposed provenances. When ptrtoint executes,
265 // the provenance is inserted to the set. When inttoptr executes, it yields
266 // a pointer with a wildcard provenance. That is, each later use will check
267 // whether there is an exposed provenance in the snapshot allowing the
268 // operation. The invalid provenance will be masked out after the operation.
269 // If we cannot pick one, it is UB.
270
271 /// Exposed provenances are grouped by associated memory objects for efficient
272 /// invalidation.
273 struct ExposedProvenance {
274 IntrusiveRefCntPtr<Provenance> Prov;
275 uint64_t Generation;
276
277 bool operator<(const ExposedProvenance &RHS) const {
278 return Generation < RHS.Generation;
279 }
280 };
281 struct ExposedProvenanceSet {
282 // (Provenance, Generation)
283 SmallVector<ExposedProvenance> List;
284 // FIXME: Implement a partial order comparator for provenance instead of
285 // deduplicating by pointers.
286 SmallPtrSet<Provenance *, 4> Set;
287 };
288 std::map<uint64_t, ExposedProvenanceSet> ExposedProvenances;
289 // Global version number for the set of exposed provenances.
290 uint64_t ExposedProvenanceSetGeneration = 0;
291
292 /// Get the tag for the given pointer provenance.
293 APInt getTag(uint32_t BitWidth, Provenance &Prov);
294 AnyValue fromBytes(ConstBytesView Bytes, Type *Ty, uint32_t OffsetInBits,
295 bool CheckPaddingBits, bool *ContainsUndefinedBits);
296 void toBytes(const AnyValue &Val, Type *Ty, uint32_t OffsetInBits,
297 MutableBytesView Bytes, bool PaddingBits);
298
299 AnyValue computePtrAdd(const Pointer &Ptr, const APInt &Offset,
300 GEPNoWrapFlags Flags, AnyValue &AccumulatedOffset);
301 AnyValue computePtrAdd(const AnyValue &Ptr, const APInt &Offset,
302 GEPNoWrapFlags Flags, AnyValue &AccumulatedOffset);
303 AnyValue computeScaledPtrAdd(const AnyValue &Ptr, const AnyValue &Index,
304 const APInt &Scale, GEPNoWrapFlags Flags,
305 AnyValue &AccumulatedOffset);
306
307 // Constants
308 // Use std::map to avoid iterator/reference invalidation.
309 std::map<Constant *, MaterializedConstant> ConstCache;
310 // Temporary buffer for non-cacheable constants (e.g.,
311 // undef/ptrtoint/inttoptr).
312 SpecificBumpPtrAllocator<MaterializedConstant> NoncacheableConstBuffer;
313 size_t NoncacheableConstCount = 0;
314 DenseMap<Function *, Pointer> FuncAddrMap;
315 DenseMap<BasicBlock *, Pointer> BlockAddrMap;
316 DenseMap<uint64_t, std::pair<Function *, IntrusiveRefCntPtr<MemoryObject>>>
317 ValidFuncTargets;
318 DenseMap<uint64_t, std::pair<BasicBlock *, IntrusiveRefCntPtr<MemoryObject>>>
319 ValidBlockTargets;
320 DenseMap<GlobalVariable *, Pointer> GlobalAddrMap;
321 MaterializedConstant getConstantValueImpl(Constant *C);
322 MaterializedConstant evaluateConstantExpression(ConstantExpr *CE);
323
324 // Floating-point environment
325 RoundingMode CurrentRoundingMode = RoundingMode::NearestTiesToEven;
326 fp::ExceptionBehavior CurrentExceptionBehavior =
327 fp::ExceptionBehavior::ebIgnore;
328
329 // TODO: errno
330
331public:
332 explicit Context(Module &M, const AsmParserContext *ParserContext);
333 Context(const Context &) = delete;
334 Context(Context &&) = delete;
335 Context &operator=(const Context &) = delete;
336 Context &operator=(Context &&) = delete;
337 ~Context();
338
339 void setMemoryLimit(uint64_t Max) { MaxMem = Max; }
340 void setVScale(uint32_t VS) { VScale = VS; }
341 void setMaxSteps(uint32_t MS) { MaxSteps = MS; }
342 void setMaxStackDepth(uint32_t Depth) { MaxStackDepth = Depth; }
343 void setFusedMultiplyAdd(bool F) { FusedMultiplyAdd = F; }
344 uint64_t getMemoryLimit() const { return MaxMem; }
345 uint32_t getVScale() const { return VScale; }
346 uint32_t getMaxSteps() const { return MaxSteps; }
347 uint32_t getMaxStackDepth() const { return MaxStackDepth; }
348 void setDeterministic(bool D) { Deterministic = D; }
349 bool isDeterministic() const { return Deterministic; }
350 bool mayUseNonDeterminism() const { return !Deterministic; }
351 UndefValueBehavior getEffectiveUndefValueBehavior() const;
352 NaNPropagationBehavior getEffectiveNaNPropagationBehavior() const;
353 bool fuseMultiplyAdd() const { return FusedMultiplyAdd; }
354 void setUndefValueBehavior(UndefValueBehavior UB) { UndefBehavior = UB; }
355 void setNaNPropagationBehavior(NaNPropagationBehavior NaNBehav) {
356 NaNBehavior = NaNBehav;
357 }
358 void reseed(uint32_t Seed) { Rng.seed(sd: Seed); }
359
360 LLVMContext &getContext() const { return Ctx; }
361 Module &getModule() const { return M; }
362 const AsmParserContext *getParserContext() const { return ParserContext; }
363 const DataLayout &getDataLayout() const { return DL; }
364 const Triple &getTargetTriple() const { return M.getTargetTriple(); }
365 const TargetLibraryInfoImpl &getTLIImpl() const { return TLIImpl; }
366 /// Get the effective vector length for a vector type.
367 uint32_t getEVL(ElementCount EC) const {
368 if (EC.isScalable())
369 return VScale * EC.getKnownMinValue();
370 return EC.getFixedValue();
371 }
372 /// The result is multiplied by VScale for scalable type sizes.
373 uint64_t getEffectiveTypeSize(TypeSize Size) const {
374 if (Size.isScalable())
375 return VScale * Size.getKnownMinValue();
376 return Size.getFixedValue();
377 }
378 /// Returns DL.getTypeAllocSize/getTypeStoreSize for the given type.
379 /// An exception to this is that for scalable vector types, the size is
380 /// computed as if the vector has getEVL(ElementCount) elements.
381 uint64_t getEffectiveTypeAllocSize(Type *Ty);
382 uint64_t getEffectiveTypeStoreSize(Type *Ty);
383
384 /// Returns a pointer to an evaluated constant \p C. If it cannot be
385 /// evaluated, returns nullptr. Note that it returns a pointer to a temporary
386 /// buffer when \p C is not context-free. The caller is responsible for
387 /// calling resetNoncacheableConstantBuffer after all references are dropped.
388 const MaterializedConstant *getConstantValue(Constant *C);
389 void resetNoncacheableConstantBuffer();
390 IntrusiveRefCntPtr<MemoryObject> allocate(uint64_t Size, uint64_t Align,
391 StringRef Name, unsigned AS,
392 MemInitKind InitKind,
393 MemAllocKind AllocKind,
394 bool IsIRGlobalValue = false);
395 bool free(const MemoryObject &Obj);
396 /// Derive a pointer from a memory object with offset 0.
397 /// Please use Pointer's interface for further manipulations.
398 Pointer deriveFromMemoryObject(IntrusiveRefCntPtr<MemoryObject> Obj);
399 /// Mark this provenance as exposed. It is no-op if it is not associated with
400 /// a memory object or a wildcard provenance.
401 void exposeProvenance(Provenance &Prov);
402 /// A helper to check both concrete and wildcard provenance. Please don't
403 /// report UB inside the \p Check callback due to the existence of wildcard
404 /// provenance.
405 /// Returns the resolved memory object if success. \p Ptr is guaranteed to be
406 /// within the bounds of the returned memory object. But the state is not
407 /// checked, for better diagnostic messages. If \p HasSideEffect is true, some
408 /// invalid provenances will be masked out. Note that in this case the caller
409 /// must report UB when the result is nullptr.
410 MemoryObject *checkProvenance(const Pointer &Ptr,
411 function_ref<bool(const Provenance &)> Check,
412 bool HasSideEffect = true);
413 /// Returns the snapshot of currently exposed provenances.
414 IntrusiveRefCntPtr<Provenance> getWildcardProvenance();
415 /// Convert byte sequence to a value of the given type. Uninitialized bits are
416 /// flushed according to the options.
417 /// If \p ContainsUndefinedBits is provided, it will be set to true when there
418 /// are poison or undef bits in the value (i.e., padding bits are ignored).
419 AnyValue fromBytes(ArrayRef<Byte> Bytes, Type *Ty,
420 bool *ContainsUndefinedBits = nullptr);
421 /// Convert a value to byte sequence. Padding bits are set to zero.
422 void toBytes(const AnyValue &Val, Type *Ty, MutableArrayRef<Byte> Bytes);
423 /// Direct memory load without checks.
424 AnyValue load(MemoryObject &MO, uint64_t Offset, Type *ValTy,
425 bool *ContainsUndefinedBits = nullptr);
426 /// Direct memory store without checks.
427 void store(MemoryObject &MO, uint64_t Offset, const AnyValue &Val,
428 Type *ValTy);
429 void storeRawBytes(MemoryObject &MO, uint64_t Offset, const void *Data,
430 uint64_t Size);
431
432 /// Freeze the value in-place.
433 void freeze(AnyValue &Val, Type *Ty);
434
435 AnyValue computeGEP(GEPOperator &GEP,
436 function_ref<const AnyValue &(Value *V)> GetValue);
437
438 Function *getTargetFunction(const Pointer &Ptr);
439 BasicBlock *getTargetBlock(const Pointer &Ptr);
440
441 /// Initialize global variables and function/block objects. This function
442 /// should be called before executing any function. Returns false if the
443 /// initialization fails (e.g., the memory limit is exceeded during
444 /// initialization).
445 bool initGlobalValues();
446 /// Execute the function \p F with arguments \p Args, and store the return
447 /// value in \p RetVal if the function is not void.
448 /// Returns a `ProgramExitInfo` indicating how the program finished:
449 /// Kind = Returned: The program executed successfully and returned normally.
450 /// Kind = Failed: The interpreter encountered an error and could not execute
451 /// the program.
452 /// Kind = Exited/Aborted/Terminated: The program ended via an
453 /// explicit call to `exit()`, `abort()`, or `terminate()`.
454 ProgramExitInfo runFunction(Function &F, ArrayRef<AnyValue> Args,
455 AnyValue &RetVal, EventHandler &Handler);
456
457 RoundingMode getCurrentRoundingMode() const;
458 fp::ExceptionBehavior getCurrentExceptionBehavior() const;
459 void setCurrentRoundingMode(RoundingMode RM);
460 void setCurrentExceptionBehavior(fp::ExceptionBehavior EB);
461 bool isDefaultFPEnv() const;
462
463 bool getRandomBool();
464 uint64_t getRandomUInt64();
465};
466
467} // namespace llvm::ubi
468
469#endif
470