Fabcoin Core  0.16.2
P2P Digital Currency
Memory.cpp
Go to the documentation of this file.
1 #include "Memory.h"
2 
4 #include <llvm/IR/IntrinsicInst.h>
6 
7 #include "Type.h"
8 #include "GasMeter.h"
9 #include "Endianness.h"
10 #include "RuntimeManager.h"
11 
12 namespace dev
13 {
14 namespace eth
15 {
16 namespace jit
17 {
18 
19 Memory::Memory(RuntimeManager& _runtimeManager, GasMeter& _gasMeter):
20  RuntimeHelper(_runtimeManager), // TODO: RuntimeHelper not needed
21  m_memory{m_builder, _runtimeManager.getMem()},
22  m_gasMeter(_gasMeter)
23 {}
24 
25 llvm::Function* Memory::getRequireFunc()
26 {
27  auto& func = m_require;
28  if (!func)
29  {
30  llvm::Type* argTypes[] = {Array::getType()->getPointerTo(), Type::Word, Type::Word, Type::BytePtr, Type::GasPtr};
31  func = llvm::Function::Create(llvm::FunctionType::get(Type::Void, argTypes, false), llvm::Function::PrivateLinkage, "mem.require", getModule());
32  func->setDoesNotThrow();
33 
34  auto iter = func->arg_begin();
35  llvm::Argument* mem = &(*iter++);
36  mem->setName("mem");
37  llvm::Argument* blkOffset = &(*iter++);
38  blkOffset->setName("blkOffset");
39  llvm::Argument* blkSize = &(*iter++);
40  blkSize->setName("blkSize");
41  llvm::Argument* jmpBuf = &(*iter++);
42  jmpBuf->setName("jmpBuf");
43  llvm::Argument* gas = &(*iter);
44  gas->setName("gas");
45 
46  auto preBB = llvm::BasicBlock::Create(func->getContext(), "Pre", func);
47  auto checkBB = llvm::BasicBlock::Create(func->getContext(), "Check", func);
48  auto resizeBB = llvm::BasicBlock::Create(func->getContext(), "Resize", func);
49  auto returnBB = llvm::BasicBlock::Create(func->getContext(), "Return", func);
50 
51  InsertPointGuard guard(m_builder); // Restores insert point at function exit
52 
53  // BB "Pre": Ignore checks with size 0
54  m_builder.SetInsertPoint(preBB);
55  m_builder.CreateCondBr(m_builder.CreateICmpNE(blkSize, Constant::get(0)), checkBB, returnBB, Type::expectTrue);
56 
57  // BB "Check"
58  m_builder.SetInsertPoint(checkBB);
59  static const auto c_inputMax = uint64_t(1) << 33; // max value of blkSize and blkOffset that will not result in integer overflow in calculations below
60  auto blkOffsetOk = m_builder.CreateICmpULE(blkOffset, Constant::get(c_inputMax), "blkOffsetOk");
61  auto blkO = m_builder.CreateSelect(blkOffsetOk, m_builder.CreateTrunc(blkOffset, Type::Size), m_builder.getInt64(c_inputMax), "bklO");
62  auto blkSizeOk = m_builder.CreateICmpULE(blkSize, Constant::get(c_inputMax), "blkSizeOk");
63  auto blkS = m_builder.CreateSelect(blkSizeOk, m_builder.CreateTrunc(blkSize, Type::Size), m_builder.getInt64(c_inputMax), "bklS");
64 
65  auto sizeReq0 = m_builder.CreateNUWAdd(blkO, blkS, "sizeReq0");
66  auto sizeReq = m_builder.CreateAnd(m_builder.CreateNUWAdd(sizeReq0, m_builder.getInt64(31)), uint64_t(-1) << 5, "sizeReq"); // s' = ((s0 + 31) / 32) * 32
67  auto sizeCur = m_memory.size(mem);
68  auto sizeOk = m_builder.CreateICmpULE(sizeReq, sizeCur, "sizeOk");
69 
70  m_builder.CreateCondBr(sizeOk, returnBB, resizeBB, Type::expectTrue);
71 
72  // BB "Resize"
73  m_builder.SetInsertPoint(resizeBB);
74  // Check gas first
75  auto w1 = m_builder.CreateLShr(sizeReq, 5);
76  auto w1s = m_builder.CreateNUWMul(w1, w1);
77  auto c1 = m_builder.CreateAdd(m_builder.CreateNUWMul(w1, m_builder.getInt64(3)), m_builder.CreateLShr(w1s, 9));
78  auto w0 = m_builder.CreateLShr(sizeCur, 5);
79  auto w0s = m_builder.CreateNUWMul(w0, w0);
80  auto c0 = m_builder.CreateAdd(m_builder.CreateNUWMul(w0, m_builder.getInt64(3)), m_builder.CreateLShr(w0s, 9));
81  auto cc = m_builder.CreateNUWSub(c1, c0);
82  auto costOk = m_builder.CreateAnd(blkOffsetOk, blkSizeOk, "costOk");
83  auto c = m_builder.CreateSelect(costOk, cc, m_builder.getInt64(std::numeric_limits<int64_t>::max()), "c");
84  m_gasMeter.count(c, jmpBuf, gas);
85  // Resize
86  m_memory.extend(mem, sizeReq);
87  m_builder.CreateBr(returnBB);
88 
89  // BB "Return"
90  m_builder.SetInsertPoint(returnBB);
91  m_builder.CreateRetVoid();
92  }
93  return func;
94 }
95 
96 llvm::Function* Memory::createFunc(bool _isStore, llvm::Type* _valueType)
97 {
98  auto isWord = _valueType == Type::Word;
99 
100  llvm::Type* storeArgs[] = {Array::getType()->getPointerTo(), Type::Word, _valueType};
101  llvm::Type* loadArgs[] = {Array::getType()->getPointerTo(), Type::Word};
102  auto name = _isStore ? isWord ? "mstore" : "mstore8" : "mload";
103  auto funcType = _isStore ? llvm::FunctionType::get(Type::Void, storeArgs, false) : llvm::FunctionType::get(Type::Word, loadArgs, false);
104  auto func = llvm::Function::Create(funcType, llvm::Function::PrivateLinkage, name, getModule());
105 
106  InsertPointGuard guard(m_builder); // Restores insert point at function exit
107 
108  m_builder.SetInsertPoint(llvm::BasicBlock::Create(func->getContext(), {}, func));
109 
110  auto iter = func->arg_begin();
111  llvm::Argument* mem = &(*iter++);
112  mem->setName("mem");
113  llvm::Argument* index = &(*iter++);
114  index->setName("index");
115 
116  if (_isStore)
117  {
118  llvm::Argument* valueArg = &(*iter);
119  valueArg->setName("value");
120  auto value = isWord ? Endianness::toBE(m_builder, valueArg) : valueArg;
121  auto memPtr = m_memory.getPtr(mem, m_builder.CreateTrunc(index, Type::Size));
122  auto valuePtr = m_builder.CreateBitCast(memPtr, _valueType->getPointerTo(), "valuePtr");
123  m_builder.CreateStore(value, valuePtr);
124  m_builder.CreateRetVoid();
125  }
126  else
127  {
128  auto memPtr = m_memory.getPtr(mem, m_builder.CreateTrunc(index, Type::Size));
129  llvm::Value* ret = m_builder.CreateLoad(memPtr);
130  ret = Endianness::toNative(m_builder, ret);
131  m_builder.CreateRet(ret);
132  }
133 
134  return func;
135 }
136 
137 llvm::Function* Memory::getLoadWordFunc()
138 {
139  auto& func = m_loadWord;
140  if (!func)
141  func = createFunc(false, Type::Word);
142  return func;
143 }
144 
145 llvm::Function* Memory::getStoreWordFunc()
146 {
147  auto& func = m_storeWord;
148  if (!func)
149  func = createFunc(true, Type::Word);
150  return func;
151 }
152 
153 llvm::Function* Memory::getStoreByteFunc()
154 {
155  auto& func = m_storeByte;
156  if (!func)
157  func = createFunc(true, Type::Byte);
158  return func;
159 }
160 
161 
163 {
164  require(_addr, Constant::get(Type::Word->getPrimitiveSizeInBits() / 8));
165  return m_builder.CreateCall(getLoadWordFunc(), {getRuntimeManager().getMem(), _addr});
166 }
167 
169 {
170  require(_addr, Constant::get(Type::Word->getPrimitiveSizeInBits() / 8));
171  m_builder.CreateCall(getStoreWordFunc(), {getRuntimeManager().getMem(), _addr, _word});
172 }
173 
175 {
176  require(_addr, Constant::get(Type::Byte->getPrimitiveSizeInBits() / 8));
177  auto byte = m_builder.CreateTrunc(_word, Type::Byte, "byte");
178  m_builder.CreateCall(getStoreByteFunc(), {getRuntimeManager().getMem(), _addr, byte});
179 }
180 
182 {
183  auto memPtr = m_builder.CreateBitCast(getRuntimeManager().getMem(), Type::BytePtr->getPointerTo());
184  auto data = m_builder.CreateLoad(memPtr, "data");
185  assert(data->getType() == Type::BytePtr);
186  return data;
187 }
188 
190 {
191  return m_builder.CreateZExt(m_memory.size(), Type::Word, "msize");
192 }
193 
195 {
196  return m_builder.CreateGEP(getData(), _index, "ptr");
197 }
198 
200 {
201  if (auto constant = llvm::dyn_cast<llvm::ConstantInt>(_size))
202  {
203  if (!constant->getValue())
204  return;
205  }
207 }
208 
209 void Memory::copyBytes(llvm::Value* _srcPtr, llvm::Value* _srcSize, llvm::Value* _srcIdx,
210  llvm::Value* _destMemIdx, llvm::Value* _reqBytes)
211 {
212  require(_destMemIdx, _reqBytes);
213 
214  // Additional copy cost
215  // TODO: This round ups to 32 happens in many places
216  auto reqBytes = m_builder.CreateTrunc(_reqBytes, Type::Gas);
217  auto copyWords = m_builder.CreateUDiv(m_builder.CreateNUWAdd(reqBytes, m_builder.getInt64(31)), m_builder.getInt64(32));
218  m_gasMeter.countCopy(copyWords);
219 
220  // Algorithm:
221  // isOutsideData = idx256 >= size256
222  // idx64 = trunc idx256
223  // size64 = trunc size256
224  // dataLeftSize = size64 - idx64 // safe if not isOutsideData
225  // reqBytes64 = trunc _reqBytes // require() handles large values
226  // bytesToCopy0 = select(reqBytes64 > dataLeftSize, dataSizeLeft, reqBytes64) // min
227  // bytesToCopy = select(isOutsideData, 0, bytesToCopy0)
228 
229  auto isOutsideData = m_builder.CreateICmpUGE(_srcIdx, _srcSize);
230  auto idx64 = m_builder.CreateTrunc(_srcIdx, Type::Size);
231  auto size64 = m_builder.CreateTrunc(_srcSize, Type::Size);
232  auto dataLeftSize = m_builder.CreateNUWSub(size64, idx64);
233  auto outOfBound = m_builder.CreateICmpUGT(reqBytes, dataLeftSize);
234  auto bytesToCopyInner = m_builder.CreateSelect(outOfBound, dataLeftSize, reqBytes);
235  auto bytesToCopy = m_builder.CreateSelect(isOutsideData, m_builder.getInt64(0), bytesToCopyInner, "bytesToCopy");
236  auto bytesToZero = m_builder.CreateNUWSub(reqBytes, bytesToCopy, "bytesToZero");
237 
238  auto src = m_builder.CreateGEP(_srcPtr, idx64, "src");
239  auto dstIdx = m_builder.CreateTrunc(_destMemIdx, Type::Size, "dstIdx");
240  auto padIdx = m_builder.CreateNUWAdd(dstIdx, bytesToCopy, "padIdx");
241  auto dst = m_memory.getPtr(getRuntimeManager().getMem(), dstIdx);
242  auto pad = m_memory.getPtr(getRuntimeManager().getMem(), padIdx);
243  m_builder.CreateMemCpy(dst, src, bytesToCopy, 0);
244  m_builder.CreateMemSet(pad, m_builder.getInt8(0), bytesToZero, 0);
245 }
246 
247 }
248 }
249 }
llvm::Value * getBytePtr(llvm::Value *_index)
Definition: Memory.cpp:194
Adapted from code found on http://stackoverflow.com/questions/180947/base64-decode-snippet-in-c Origi...
Definition: Arith256.cpp:15
GasMeter & m_gasMeter
Definition: Memory.h:33
llvm::Module * getModule()
Reference to the IR module being compiled.
llvm::Function * getRequireFunc()
Definition: Memory.cpp:25
void countCopy(llvm::Value *_copyWords)
Count addional gas cost for memory copy.
Definition: GasMeter.cpp:160
llvm::Function * m_loadWord
Definition: Memory.h:43
llvm::Function * getStoreWordFunc()
Definition: Memory.cpp:145
Memory(RuntimeManager &_runtimeManager, GasMeter &_gasMeter)
Definition: Memory.cpp:19
static llvm::Type * Void
Definition: Type.h:32
llvm::Value * getData()
Definition: Memory.cpp:181
#define c(i)
assert(len-trim+(2 *lenIndices)<=WIDTH)
llvm::Value * loadWord(llvm::Value *_addr)
Definition: Memory.cpp:162
static llvm::Type * getType()
Definition: Array.cpp:217
void require(llvm::Value *_offset, llvm::Value *_size)
Requires the amount of memory to for data defined by offset and size. And counts gas fee for that mem...
Definition: Memory.cpp:199
void copyBytes(llvm::Value *_srcPtr, llvm::Value *_srcSize, llvm::Value *_srcIndex, llvm::Value *_destMemIdx, llvm::Value *_byteCount)
Definition: Memory.cpp:209
static llvm::PointerType * BytePtr
Definition: Type.h:30
Config::Value_type Value
static llvm::Value * toBE(IRBuilder &_builder, llvm::Value *_word)
Definition: Endianness.h:14
const char * name
Definition: rest.cpp:36
ExecStats::duration max
Definition: ExecStats.cpp:36
void extend(llvm::Value *_arrayPtr, llvm::Value *_size)
Definition: Array.cpp:253
static llvm::IntegerType * Word
Definition: Type.h:21
void storeWord(llvm::Value *_addr, llvm::Value *_word)
Definition: Memory.cpp:168
static llvm::ConstantInt * get(int64_t _n)
Returns word-size constant.
Definition: Type.cpp:55
static llvm::Value * toNative(IRBuilder &_builder, llvm::Value *_word)
Definition: Endianness.h:15
llvm::Function * createFunc(bool _isStore, llvm::Type *_type)
Definition: Memory.cpp:96
llvm::Function * getLoadWordFunc()
Definition: Memory.cpp:137
static llvm::PointerType * GasPtr
Definition: Type.h:27
llvm::Function * getStoreByteFunc()
Definition: Memory.cpp:153
llvm::Function * m_require
Definition: Memory.h:42
llvm::Function * m_storeWord
Definition: Memory.h:44
uint8_t byte
Definition: Common.h:10
llvm::Function * m_storeByte
Definition: Memory.h:45
Compiler helper that depends on runtime data.
llvm::Value * getSize()
Definition: Memory.cpp:189
void storeByte(llvm::Value *_addr, llvm::Value *_byte)
Definition: Memory.cpp:174
void count(Instruction _inst)
Count step cost of instruction.
Definition: GasMeter.cpp:56
static llvm::IntegerType * Size
Definition: Type.h:25
llvm::Value * getPtr(llvm::Value *_arrayPtr, llvm::Value *_index)
Definition: Array.h:44
IRBuilder & m_builder
Reference to parent compiler IR builder.
llvm::Value * size(llvm::Value *_array=nullptr)
Definition: Array.cpp:247
RuntimeManager & getRuntimeManager()
static llvm::MDNode * expectTrue
Definition: Type.h:42
static llvm::IntegerType * Gas
Definition: Type.h:26
uint8_t const * data
Definition: sha3.h:19
static llvm::IntegerType * Byte
Definition: Type.h:29