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
302 // Constants
303 // Use std::map to avoid iterator/reference invalidation.
304 std::map<Constant *, MaterializedConstant> ConstCache;
305 // Temporary buffer for non-cacheable constants (e.g.,
306 // undef/ptrtoint/inttoptr).
307 SpecificBumpPtrAllocator<MaterializedConstant> NoncacheableConstBuffer;
308 size_t NoncacheableConstCount = 0;
309 DenseMap<Function *, Pointer> FuncAddrMap;
310 DenseMap<BasicBlock *, Pointer> BlockAddrMap;
311 DenseMap<uint64_t, std::pair<Function *, IntrusiveRefCntPtr<MemoryObject>>>
312 ValidFuncTargets;
313 DenseMap<uint64_t, std::pair<BasicBlock *, IntrusiveRefCntPtr<MemoryObject>>>
314 ValidBlockTargets;
315 DenseMap<GlobalVariable *, Pointer> GlobalAddrMap;
316 MaterializedConstant getConstantValueImpl(Constant *C);
317 MaterializedConstant evaluateConstantExpression(ConstantExpr *CE);
318
319 // Floating-point environment
320 RoundingMode CurrentRoundingMode = RoundingMode::NearestTiesToEven;
321 fp::ExceptionBehavior CurrentExceptionBehavior =
322 fp::ExceptionBehavior::ebIgnore;
323
324 // TODO: errno
325
326public:
327 explicit Context(Module &M, const AsmParserContext *ParserContext);
328 Context(const Context &) = delete;
329 Context(Context &&) = delete;
330 Context &operator=(const Context &) = delete;
331 Context &operator=(Context &&) = delete;
332 ~Context();
333
334 void setMemoryLimit(uint64_t Max) { MaxMem = Max; }
335 void setVScale(uint32_t VS) { VScale = VS; }
336 void setMaxSteps(uint32_t MS) { MaxSteps = MS; }
337 void setMaxStackDepth(uint32_t Depth) { MaxStackDepth = Depth; }
338 void setFusedMultiplyAdd(bool F) { FusedMultiplyAdd = F; }
339 uint64_t getMemoryLimit() const { return MaxMem; }
340 uint32_t getVScale() const { return VScale; }
341 uint32_t getMaxSteps() const { return MaxSteps; }
342 uint32_t getMaxStackDepth() const { return MaxStackDepth; }
343 void setDeterministic(bool D) { Deterministic = D; }
344 bool isDeterministic() const { return Deterministic; }
345 bool mayUseNonDeterminism() const { return !Deterministic; }
346 UndefValueBehavior getEffectiveUndefValueBehavior() const;
347 NaNPropagationBehavior getEffectiveNaNPropagationBehavior() const;
348 bool fuseMultiplyAdd() const { return FusedMultiplyAdd; }
349 void setUndefValueBehavior(UndefValueBehavior UB) { UndefBehavior = UB; }
350 void setNaNPropagationBehavior(NaNPropagationBehavior NaNBehav) {
351 NaNBehavior = NaNBehav;
352 }
353 void reseed(uint32_t Seed) { Rng.seed(sd: Seed); }
354
355 LLVMContext &getContext() const { return Ctx; }
356 Module &getModule() const { return M; }
357 const AsmParserContext *getParserContext() const { return ParserContext; }
358 const DataLayout &getDataLayout() const { return DL; }
359 const Triple &getTargetTriple() const { return M.getTargetTriple(); }
360 const TargetLibraryInfoImpl &getTLIImpl() const { return TLIImpl; }
361 /// Get the effective vector length for a vector type.
362 uint32_t getEVL(ElementCount EC) const {
363 if (EC.isScalable())
364 return VScale * EC.getKnownMinValue();
365 return EC.getFixedValue();
366 }
367 /// The result is multiplied by VScale for scalable type sizes.
368 uint64_t getEffectiveTypeSize(TypeSize Size) const {
369 if (Size.isScalable())
370 return VScale * Size.getKnownMinValue();
371 return Size.getFixedValue();
372 }
373 /// Returns DL.getTypeAllocSize/getTypeStoreSize for the given type.
374 /// An exception to this is that for scalable vector types, the size is
375 /// computed as if the vector has getEVL(ElementCount) elements.
376 uint64_t getEffectiveTypeAllocSize(Type *Ty);
377 uint64_t getEffectiveTypeStoreSize(Type *Ty);
378
379 /// Returns a pointer to an evaluated constant \p C. If it cannot be
380 /// evaluated, returns nullptr. Note that it returns a pointer to a temporary
381 /// buffer when \p C is not context-free. The caller is responsible for
382 /// calling resetNoncacheableConstantBuffer after all references are dropped.
383 const MaterializedConstant *getConstantValue(Constant *C);
384 void resetNoncacheableConstantBuffer();
385 /// Returns true if an object of \p Size bytes in address space \p AS is
386 /// larger than the largest signed integer that fits into the index type.
387 /// Creating such an object is undefined behavior.
388 bool exceedsMaxObjectSize(uint64_t Size, unsigned AS) const {
389 return !isUIntN(N: DL.getIndexSizeInBits(AS) - 1, x: Size);
390 }
391 IntrusiveRefCntPtr<MemoryObject> allocate(uint64_t Size, uint64_t Align,
392 StringRef Name, unsigned AS,
393 MemInitKind InitKind,
394 MemAllocKind AllocKind,
395 bool IsIRGlobalValue = false);
396 bool free(const MemoryObject &Obj);
397 /// Derive a pointer from a memory object with offset 0.
398 /// Please use Pointer's interface for further manipulations.
399 Pointer deriveFromMemoryObject(IntrusiveRefCntPtr<MemoryObject> Obj);
400 /// Mark this provenance as exposed. It is no-op if it is not associated with
401 /// a memory object or a wildcard provenance.
402 void exposeProvenance(Provenance &Prov);
403 /// A helper to check both concrete and wildcard provenance. Please don't
404 /// report UB inside the \p Check callback due to the existence of wildcard
405 /// provenance.
406 /// Returns the resolved memory object if success. \p Ptr is guaranteed to be
407 /// within the bounds of the returned memory object. But the state is not
408 /// checked, for better diagnostic messages. If \p HasSideEffect is true, some
409 /// invalid provenances will be masked out. Note that in this case the caller
410 /// must report UB when the result is nullptr.
411 MemoryObject *checkProvenance(const Pointer &Ptr,
412 function_ref<bool(const Provenance &)> Check,
413 bool HasSideEffect = true);
414 /// Returns the snapshot of currently exposed provenances.
415 IntrusiveRefCntPtr<Provenance> getWildcardProvenance();
416 /// Convert byte sequence to a value of the given type. Uninitialized bits are
417 /// flushed according to the options.
418 /// If \p ContainsUndefinedBits is provided, it will be set to true when there
419 /// are poison or undef bits in the value or in the padding bits that poison
420 /// value bits.
421 AnyValue fromBytes(ArrayRef<Byte> Bytes, Type *Ty,
422 bool *ContainsUndefinedBits = nullptr);
423 /// Convert a value to byte sequence. If every non-padding bit in the padding
424 /// byte is poison, the padding bits are poison; otherwise, they are zero.
425 void toBytes(const AnyValue &Val, Type *Ty, MutableArrayRef<Byte> Bytes);
426 /// Read the bits [OffsetInBits, OffsetInBits + bitwidth(Ty)) of \p Src as a
427 /// value of type \p Ty. The bit range must be within \p Src.
428 AnyValue extractBits(const ByteValue &Src, uint32_t OffsetInBits, Type *Ty);
429 /// Overwrite the bits [OffsetInBits, OffsetInBits + bitwidth(Ty)) of \p Base
430 /// with \p Val. The bit range must be within \p Base.
431 void insertBits(ByteValue &Base, uint32_t OffsetInBits, const AnyValue &Val,
432 Type *Ty);
433 /// Direct memory load without checks.
434 AnyValue load(MemoryObject &MO, uint64_t Offset, Type *ValTy,
435 bool *ContainsUndefinedBits = nullptr);
436 /// Direct memory store without checks.
437 void store(MemoryObject &MO, uint64_t Offset, const AnyValue &Val,
438 Type *ValTy);
439 void storeRawBytes(MemoryObject &MO, uint64_t Offset, const void *Data,
440 uint64_t Size);
441
442 /// Freeze the value in-place.
443 void freeze(AnyValue &Val, Type *Ty);
444
445 AnyValue computeGEP(GEPOperator &GEP,
446 function_ref<const AnyValue &(Value *V)> GetValue);
447 AnyValue computePtrAdd(const AnyValue &Ptr, const APInt &Offset,
448 GEPNoWrapFlags Flags, AnyValue &AccumulatedOffset);
449 AnyValue computeScaledPtrAdd(const AnyValue &Ptr, const AnyValue &Index,
450 const APInt &Scale, GEPNoWrapFlags Flags,
451 AnyValue &AccumulatedOffset);
452 /// Sign extends or truncates the GEP index \p Idx to \p IndexBitWidth bits.
453 /// Returns poison if truncating it would violate \p Flags.
454 static AnyValue canonicalizeIndex(const AnyValue &Idx, unsigned IndexBitWidth,
455 GEPNoWrapFlags Flags);
456
457 Function *getTargetFunction(const Pointer &Ptr);
458 BasicBlock *getTargetBlock(const Pointer &Ptr);
459
460 /// Initialize global variables and function/block objects. This function
461 /// should be called before executing any function. Returns false if the
462 /// initialization fails (e.g., the memory limit is exceeded during
463 /// initialization).
464 bool initGlobalValues();
465 /// Execute the function \p F with arguments \p Args, and store the return
466 /// value in \p RetVal if the function is not void.
467 /// Returns a `ProgramExitInfo` indicating how the program finished:
468 /// Kind = Returned: The program executed successfully and returned normally.
469 /// Kind = Failed: The interpreter encountered an error and could not execute
470 /// the program.
471 /// Kind = Exited/Aborted/Terminated: The program ended via an
472 /// explicit call to `exit()`, `abort()`, or `terminate()`.
473 ProgramExitInfo runFunction(Function &F, ArrayRef<AnyValue> Args,
474 AnyValue &RetVal, EventHandler &Handler);
475
476 RoundingMode getCurrentRoundingMode() const;
477 fp::ExceptionBehavior getCurrentExceptionBehavior() const;
478 void setCurrentRoundingMode(RoundingMode RM);
479 void setCurrentExceptionBehavior(fp::ExceptionBehavior EB);
480 bool isDefaultFPEnv() const;
481
482 bool getRandomBool();
483 uint64_t getRandomUInt64();
484};
485
486} // namespace llvm::ubi
487
488#endif
489