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/IR/Module.h"
16#include <map>
17
18namespace llvm::ubi {
19
20enum class MemInitKind {
21 Zeroed,
22 Uninitialized,
23 Poisoned,
24};
25
26enum class MemoryObjectState {
27 // This memory object is accessible.
28 // Valid transitions:
29 // -> Dead (after the end of lifetime of an alloca)
30 // -> Freed (after free is called on a heap object)
31 Alive,
32 // This memory object is out of lifetime. It is OK to perform
33 // operations that do not access its content, e.g., getelementptr.
34 // Otherwise, an immediate UB occurs.
35 // Valid transition:
36 // -> Alive (after the start of lifetime of an alloca)
37 Dead,
38 // This heap memory object has been freed. Any access to it
39 // causes immediate UB. Like dead objects, it is still possible to
40 // perform operations that do not access its content.
41 Freed,
42};
43
44class MemoryObject : public RefCountedBase<MemoryObject> {
45 uint64_t Address;
46 uint64_t Size;
47 SmallVector<Byte, 8> Bytes;
48 StringRef Name;
49 unsigned AS;
50
51 MemoryObjectState State;
52 bool IsConstant = false;
53
54public:
55 MemoryObject(uint64_t Addr, uint64_t Size, StringRef Name, unsigned AS,
56 MemInitKind InitKind);
57 MemoryObject(const MemoryObject &) = delete;
58 MemoryObject(MemoryObject &&) = delete;
59 MemoryObject &operator=(const MemoryObject &) = delete;
60 MemoryObject &operator=(MemoryObject &&) = delete;
61 ~MemoryObject();
62
63 uint64_t getAddress() const { return Address; }
64 uint64_t getSize() const { return Size; }
65 StringRef getName() const { return Name; }
66 unsigned getAddressSpace() const { return AS; }
67 MemoryObjectState getState() const { return State; }
68 bool isConstant() const { return IsConstant; }
69 void setIsConstant(bool C) { IsConstant = C; }
70
71 bool inBounds(const APInt &NewAddr) const {
72 return NewAddr.uge(RHS: Address) && NewAddr.ule(RHS: Address + Size);
73 }
74
75 Byte &operator[](uint64_t Offset) {
76 assert(Offset < Size && "Offset out of bounds");
77 return Bytes[Offset];
78 }
79 void writeRawBytes(uint64_t Offset, const void *Data, uint64_t Length);
80 void writeInteger(uint64_t Offset, const APInt &Int, const DataLayout &DL);
81 void writeFloat(uint64_t Offset, const APFloat &Float, const DataLayout &DL);
82 void writePointer(uint64_t Offset, const Pointer &Ptr, const DataLayout &DL);
83
84 void markAsFreed();
85};
86
87/// An interface for handling events and managing outputs during interpretation.
88/// If the handler returns false from any of the methods, the interpreter will
89/// stop execution immediately.
90class EventHandler {
91public:
92 virtual ~EventHandler() = default;
93
94 virtual bool onInstructionExecuted(Instruction &I, const AnyValue &Result) {
95 return true;
96 }
97 virtual void onError(StringRef Msg) {}
98 virtual void onUnrecognizedInstruction(Instruction &I) {}
99 virtual void onImmediateUB(StringRef Msg) {}
100 virtual bool onBBJump(Instruction &I, BasicBlock &To) { return true; }
101 virtual bool onFunctionEntry(Function &F, ArrayRef<AnyValue> Args,
102 CallBase *CallSite) {
103 return true;
104 }
105 virtual bool onFunctionExit(Function &F, const AnyValue &RetVal) {
106 return true;
107 }
108 virtual bool onPrint(StringRef Msg) {
109 outs() << Msg;
110 return true;
111 }
112};
113
114/// The global context for the interpreter.
115/// It tracks global state such as heap memory objects and floating point
116/// environment.
117class Context {
118 // Module
119 LLVMContext &Ctx;
120 Module &M;
121 const DataLayout &DL;
122 const TargetLibraryInfoImpl TLIImpl;
123
124 // Configuration
125 uint64_t MaxMem = 0;
126 uint32_t VScale = 4;
127 uint32_t MaxSteps = 0;
128 uint32_t MaxStackDepth = 256;
129
130 // Memory
131 uint64_t UsedMem = 0;
132 // The addresses of memory objects are monotonically increasing.
133 // For now we don't model the behavior of address reuse, which is common
134 // with stack coloring.
135 uint64_t AllocationBase = 8;
136 // Maintains a global list of 'exposed' provenances. This is used to form a
137 // pointer with an exposed provenance.
138 // FIXME: Currently all the allocations are considered exposed, regardless of
139 // their interaction with ptrtoint. That is, ptrtoint is allowed to recover
140 // the provenance of any allocation. We may track the exposed provenances more
141 // precisely after we make ptrtoint have the implicit side-effect of exposing
142 // the provenance.
143 std::map<uint64_t, IntrusiveRefCntPtr<MemoryObject>> MemoryObjects;
144
145 // Constants
146 // Use std::map to avoid iterator/reference invalidation.
147 std::map<Constant *, AnyValue> ConstCache;
148 DenseMap<Function *, Pointer> FuncAddrMap;
149 DenseMap<BasicBlock *, Pointer> BlockAddrMap;
150 DenseMap<uint64_t, std::pair<Function *, IntrusiveRefCntPtr<MemoryObject>>>
151 ValidFuncTargets;
152 DenseMap<uint64_t, std::pair<BasicBlock *, IntrusiveRefCntPtr<MemoryObject>>>
153 ValidBlockTargets;
154 AnyValue getConstantValueImpl(Constant *C);
155
156 // TODO: errno and fpenv
157
158public:
159 explicit Context(Module &M);
160 Context(const Context &) = delete;
161 Context(Context &&) = delete;
162 Context &operator=(const Context &) = delete;
163 Context &operator=(Context &&) = delete;
164 ~Context();
165
166 void setMemoryLimit(uint64_t Max) { MaxMem = Max; }
167 void setVScale(uint32_t VS) { VScale = VS; }
168 void setMaxSteps(uint32_t MS) { MaxSteps = MS; }
169 void setMaxStackDepth(uint32_t Depth) { MaxStackDepth = Depth; }
170 uint64_t getMemoryLimit() const { return MaxMem; }
171 uint32_t getVScale() const { return VScale; }
172 uint32_t getMaxSteps() const { return MaxSteps; }
173 uint32_t getMaxStackDepth() const { return MaxStackDepth; }
174
175 LLVMContext &getContext() const { return Ctx; }
176 const DataLayout &getDataLayout() const { return DL; }
177 const TargetLibraryInfoImpl &getTLIImpl() const { return TLIImpl; }
178 uint32_t getEVL(ElementCount EC) const {
179 if (EC.isScalable())
180 return VScale * EC.getKnownMinValue();
181 return EC.getFixedValue();
182 }
183
184 const AnyValue &getConstantValue(Constant *C);
185 IntrusiveRefCntPtr<MemoryObject> allocate(uint64_t Size, uint64_t Align,
186 StringRef Name, unsigned AS,
187 MemInitKind InitKind);
188 bool free(uint64_t Address);
189 /// Derive a pointer from a memory object with offset 0.
190 /// Please use Pointer's interface for further manipulations.
191 Pointer deriveFromMemoryObject(IntrusiveRefCntPtr<MemoryObject> Obj);
192
193 Function *getTargetFunction(const Pointer &Ptr);
194 BasicBlock *getTargetBlock(const Pointer &Ptr);
195
196 /// Initialize global variables and function/block objects. This function
197 /// should be called before executing any function. Returns false if the
198 /// initialization fails (e.g., the memory limit is exceeded during
199 /// initialization).
200 bool initGlobalValues();
201 /// Execute the function \p F with arguments \p Args, and store the return
202 /// value in \p RetVal if the function is not void.
203 /// Returns true if the function executed successfully. False indicates an
204 /// error occurred during execution.
205 bool runFunction(Function &F, ArrayRef<AnyValue> Args, AnyValue &RetVal,
206 EventHandler &Handler);
207};
208
209} // namespace llvm::ubi
210
211#endif
212