1 | //===- SandboxIR.cpp - A transactional overlay IR on top of LLVM IR -------===// |
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 | #include "llvm/SandboxIR/SandboxIR.h" |
10 | #include "llvm/ADT/SmallPtrSet.h" |
11 | #include "llvm/IR/Constants.h" |
12 | #include "llvm/Support/Debug.h" |
13 | #include <sstream> |
14 | |
15 | using namespace llvm::sandboxir; |
16 | |
17 | Value *Use::get() const { return Ctx->getValue(V: LLVMUse->get()); } |
18 | |
19 | void Use::set(Value *V) { LLVMUse->set(V->Val); } |
20 | |
21 | unsigned Use::getOperandNo() const { return Usr->getUseOperandNo(Use: *this); } |
22 | |
23 | #ifndef NDEBUG |
24 | void Use::dump(raw_ostream &OS) const { |
25 | Value *Def = nullptr; |
26 | if (LLVMUse == nullptr) |
27 | OS << "<null> LLVM Use! " ; |
28 | else |
29 | Def = Ctx->getValue(LLVMUse->get()); |
30 | OS << "Def: " ; |
31 | if (Def == nullptr) |
32 | OS << "NULL" ; |
33 | else |
34 | OS << *Def; |
35 | OS << "\n" ; |
36 | |
37 | OS << "User: " ; |
38 | if (Usr == nullptr) |
39 | OS << "NULL" ; |
40 | else |
41 | OS << *Usr; |
42 | OS << "\n" ; |
43 | |
44 | OS << "OperandNo: " ; |
45 | if (Usr == nullptr) |
46 | OS << "N/A" ; |
47 | else |
48 | OS << getOperandNo(); |
49 | OS << "\n" ; |
50 | } |
51 | |
52 | void Use::dump() const { dump(dbgs()); } |
53 | #endif // NDEBUG |
54 | |
55 | Use OperandUseIterator::operator*() const { return Use; } |
56 | |
57 | OperandUseIterator &OperandUseIterator::operator++() { |
58 | assert(Use.LLVMUse != nullptr && "Already at end!" ); |
59 | User *User = Use.getUser(); |
60 | Use = User->getOperandUseInternal(OpIdx: Use.getOperandNo() + 1, /*Verify=*/false); |
61 | return *this; |
62 | } |
63 | |
64 | UserUseIterator &UserUseIterator::operator++() { |
65 | // Get the corresponding llvm::Use, get the next in the list, and update the |
66 | // sandboxir::Use. |
67 | llvm::Use *&LLVMUse = Use.LLVMUse; |
68 | assert(LLVMUse != nullptr && "Already at end!" ); |
69 | LLVMUse = LLVMUse->getNext(); |
70 | if (LLVMUse == nullptr) { |
71 | Use.Usr = nullptr; |
72 | return *this; |
73 | } |
74 | auto *Ctx = Use.Ctx; |
75 | auto *LLVMUser = LLVMUse->getUser(); |
76 | Use.Usr = cast_or_null<sandboxir::User>(Val: Ctx->getValue(V: LLVMUser)); |
77 | return *this; |
78 | } |
79 | |
80 | Value::Value(ClassID SubclassID, llvm::Value *Val, Context &Ctx) |
81 | : SubclassID(SubclassID), Val(Val), Ctx(Ctx) { |
82 | #ifndef NDEBUG |
83 | UID = Ctx.getNumValues(); |
84 | #endif |
85 | } |
86 | |
87 | Value::use_iterator Value::use_begin() { |
88 | llvm::Use *LLVMUse = nullptr; |
89 | if (Val->use_begin() != Val->use_end()) |
90 | LLVMUse = &*Val->use_begin(); |
91 | User *User = LLVMUse != nullptr ? cast_or_null<sandboxir::User>(Val: Ctx.getValue( |
92 | V: Val->use_begin()->getUser())) |
93 | : nullptr; |
94 | return use_iterator(Use(LLVMUse, User, Ctx)); |
95 | } |
96 | |
97 | Value::user_iterator Value::user_begin() { |
98 | auto UseBegin = Val->use_begin(); |
99 | auto UseEnd = Val->use_end(); |
100 | bool AtEnd = UseBegin == UseEnd; |
101 | llvm::Use *LLVMUse = AtEnd ? nullptr : &*UseBegin; |
102 | User *User = |
103 | AtEnd ? nullptr |
104 | : cast_or_null<sandboxir::User>(Val: Ctx.getValue(V: &*LLVMUse->getUser())); |
105 | return user_iterator(Use(LLVMUse, User, Ctx), UseToUser()); |
106 | } |
107 | |
108 | unsigned Value::getNumUses() const { return range_size(Range: Val->users()); } |
109 | |
110 | void Value::replaceUsesWithIf( |
111 | Value *OtherV, llvm::function_ref<bool(const Use &)> ShouldReplace) { |
112 | assert(getType() == OtherV->getType() && "Can't replace with different type" ); |
113 | llvm::Value *OtherVal = OtherV->Val; |
114 | // We are delegating RUWIf to LLVM IR's RUWIf. |
115 | Val->replaceUsesWithIf( |
116 | New: OtherVal, ShouldReplace: [&ShouldReplace, this](llvm::Use &LLVMUse) -> bool { |
117 | User *DstU = cast_or_null<User>(Val: Ctx.getValue(V: LLVMUse.getUser())); |
118 | if (DstU == nullptr) |
119 | return false; |
120 | Use UseToReplace(&LLVMUse, DstU, Ctx); |
121 | if (!ShouldReplace(UseToReplace)) |
122 | return false; |
123 | auto &Tracker = Ctx.getTracker(); |
124 | if (Tracker.isTracking()) |
125 | Tracker.track(Change: std::make_unique<UseSet>(args&: UseToReplace, args&: Tracker)); |
126 | return true; |
127 | }); |
128 | } |
129 | |
130 | void Value::replaceAllUsesWith(Value *Other) { |
131 | assert(getType() == Other->getType() && |
132 | "Replacing with Value of different type!" ); |
133 | auto &Tracker = Ctx.getTracker(); |
134 | if (Tracker.isTracking()) { |
135 | for (auto Use : uses()) |
136 | Tracker.track(Change: std::make_unique<UseSet>(args&: Use, args&: Tracker)); |
137 | } |
138 | // We are delegating RAUW to LLVM IR's RAUW. |
139 | Val->replaceAllUsesWith(V: Other->Val); |
140 | } |
141 | |
142 | #ifndef NDEBUG |
143 | std::string Value::getUid() const { |
144 | std::stringstream SS; |
145 | SS << "SB" << UID << "." ; |
146 | return SS.str(); |
147 | } |
148 | |
149 | void Value::dumpCommonHeader(raw_ostream &OS) const { |
150 | OS << getUid() << " " << getSubclassIDStr(SubclassID) << " " ; |
151 | } |
152 | |
153 | void Value::dumpCommonFooter(raw_ostream &OS) const { |
154 | OS.indent(2) << "Val: " ; |
155 | if (Val) |
156 | OS << *Val; |
157 | else |
158 | OS << "NULL" ; |
159 | OS << "\n" ; |
160 | } |
161 | |
162 | void Value::dumpCommonPrefix(raw_ostream &OS) const { |
163 | if (Val) |
164 | OS << *Val; |
165 | else |
166 | OS << "NULL " ; |
167 | } |
168 | |
169 | void Value::dumpCommonSuffix(raw_ostream &OS) const { |
170 | OS << " ; " << getUid() << " (" << getSubclassIDStr(SubclassID) << ")" ; |
171 | } |
172 | |
173 | void Value::printAsOperandCommon(raw_ostream &OS) const { |
174 | if (Val) |
175 | Val->printAsOperand(OS); |
176 | else |
177 | OS << "NULL " ; |
178 | } |
179 | |
180 | void Argument::printAsOperand(raw_ostream &OS) const { |
181 | printAsOperandCommon(OS); |
182 | } |
183 | void Argument::dump(raw_ostream &OS) const { |
184 | dumpCommonPrefix(OS); |
185 | dumpCommonSuffix(OS); |
186 | } |
187 | void Argument::dump() const { |
188 | dump(dbgs()); |
189 | dbgs() << "\n" ; |
190 | } |
191 | #endif // NDEBUG |
192 | |
193 | Use User::getOperandUseDefault(unsigned OpIdx, bool Verify) const { |
194 | assert((!Verify || OpIdx < getNumOperands()) && "Out of bounds!" ); |
195 | assert(isa<llvm::User>(Val) && "Non-users have no operands!" ); |
196 | llvm::Use *LLVMUse; |
197 | if (OpIdx != getNumOperands()) |
198 | LLVMUse = &cast<llvm::User>(Val)->getOperandUse(i: OpIdx); |
199 | else |
200 | LLVMUse = cast<llvm::User>(Val)->op_end(); |
201 | return Use(LLVMUse, const_cast<User *>(this), Ctx); |
202 | } |
203 | |
204 | #ifndef NDEBUG |
205 | void User::verifyUserOfLLVMUse(const llvm::Use &Use) const { |
206 | assert(Ctx.getValue(Use.getUser()) == this && |
207 | "Use not found in this SBUser's operands!" ); |
208 | } |
209 | #endif |
210 | |
211 | bool User::classof(const Value *From) { |
212 | switch (From->getSubclassID()) { |
213 | #define DEF_VALUE(ID, CLASS) |
214 | #define DEF_USER(ID, CLASS) \ |
215 | case ClassID::ID: \ |
216 | return true; |
217 | #define DEF_INSTR(ID, OPC, CLASS) \ |
218 | case ClassID::ID: \ |
219 | return true; |
220 | #include "llvm/SandboxIR/SandboxIRValues.def" |
221 | default: |
222 | return false; |
223 | } |
224 | } |
225 | |
226 | void User::setOperand(unsigned OperandIdx, Value *Operand) { |
227 | assert(isa<llvm::User>(Val) && "No operands!" ); |
228 | auto &Tracker = Ctx.getTracker(); |
229 | if (Tracker.isTracking()) |
230 | Tracker.track(Change: std::make_unique<UseSet>(args: getOperandUse(OpIdx: OperandIdx), args&: Tracker)); |
231 | // We are delegating to llvm::User::setOperand(). |
232 | cast<llvm::User>(Val)->setOperand(i: OperandIdx, Val: Operand->Val); |
233 | } |
234 | |
235 | bool User::replaceUsesOfWith(Value *FromV, Value *ToV) { |
236 | auto &Tracker = Ctx.getTracker(); |
237 | if (Tracker.isTracking()) { |
238 | for (auto OpIdx : seq<unsigned>(Begin: 0, End: getNumOperands())) { |
239 | auto Use = getOperandUse(OpIdx); |
240 | if (Use.get() == FromV) |
241 | Tracker.track(Change: std::make_unique<UseSet>(args&: Use, args&: Tracker)); |
242 | } |
243 | } |
244 | // We are delegating RUOW to LLVM IR's RUOW. |
245 | return cast<llvm::User>(Val)->replaceUsesOfWith(From: FromV->Val, To: ToV->Val); |
246 | } |
247 | |
248 | #ifndef NDEBUG |
249 | void User::dumpCommonHeader(raw_ostream &OS) const { |
250 | Value::dumpCommonHeader(OS); |
251 | // TODO: This is incomplete |
252 | } |
253 | #endif // NDEBUG |
254 | |
255 | BBIterator &BBIterator::operator++() { |
256 | auto ItE = BB->end(); |
257 | assert(It != ItE && "Already at end!" ); |
258 | ++It; |
259 | if (It == ItE) |
260 | return *this; |
261 | Instruction &NextI = *cast<sandboxir::Instruction>(Val: Ctx->getValue(V: &*It)); |
262 | unsigned Num = NextI.getNumOfIRInstrs(); |
263 | assert(Num > 0 && "Bad getNumOfIRInstrs()" ); |
264 | It = std::next(x: It, n: Num - 1); |
265 | return *this; |
266 | } |
267 | |
268 | BBIterator &BBIterator::operator--() { |
269 | assert(It != BB->begin() && "Already at begin!" ); |
270 | if (It == BB->end()) { |
271 | --It; |
272 | return *this; |
273 | } |
274 | Instruction &CurrI = **this; |
275 | unsigned Num = CurrI.getNumOfIRInstrs(); |
276 | assert(Num > 0 && "Bad getNumOfIRInstrs()" ); |
277 | assert(std::prev(It, Num - 1) != BB->begin() && "Already at begin!" ); |
278 | It = std::prev(x: It, n: Num); |
279 | return *this; |
280 | } |
281 | |
282 | const char *Instruction::getOpcodeName(Opcode Opc) { |
283 | switch (Opc) { |
284 | #define DEF_VALUE(ID, CLASS) |
285 | #define DEF_USER(ID, CLASS) |
286 | #define OP(OPC) \ |
287 | case Opcode::OPC: \ |
288 | return #OPC; |
289 | #define DEF_INSTR(ID, OPC, CLASS) OPC |
290 | #include "llvm/SandboxIR/SandboxIRValues.def" |
291 | } |
292 | llvm_unreachable("Unknown Opcode" ); |
293 | } |
294 | |
295 | llvm::Instruction *Instruction::getTopmostLLVMInstruction() const { |
296 | Instruction *Prev = getPrevNode(); |
297 | if (Prev == nullptr) { |
298 | // If at top of the BB, return the first BB instruction. |
299 | return &*cast<llvm::BasicBlock>(Val: getParent()->Val)->begin(); |
300 | } |
301 | // Else get the Previous sandbox IR instruction's bottom IR instruction and |
302 | // return its successor. |
303 | llvm::Instruction *PrevBotI = cast<llvm::Instruction>(Val: Prev->Val); |
304 | return PrevBotI->getNextNode(); |
305 | } |
306 | |
307 | BBIterator Instruction::getIterator() const { |
308 | auto *I = cast<llvm::Instruction>(Val); |
309 | return BasicBlock::iterator(I->getParent(), I->getIterator(), &Ctx); |
310 | } |
311 | |
312 | Instruction *Instruction::getNextNode() const { |
313 | assert(getParent() != nullptr && "Detached!" ); |
314 | assert(getIterator() != getParent()->end() && "Already at end!" ); |
315 | // `Val` is the bottom-most LLVM IR instruction. Get the next in the chain, |
316 | // and get the corresponding sandboxir Instruction that maps to it. This works |
317 | // even for SandboxIR Instructions that map to more than one LLVM Instruction. |
318 | auto *LLVMI = cast<llvm::Instruction>(Val); |
319 | assert(LLVMI->getParent() != nullptr && "LLVM IR instr is detached!" ); |
320 | auto *NextLLVMI = LLVMI->getNextNode(); |
321 | auto *NextI = cast_or_null<Instruction>(Val: Ctx.getValue(V: NextLLVMI)); |
322 | if (NextI == nullptr) |
323 | return nullptr; |
324 | return NextI; |
325 | } |
326 | |
327 | Instruction *Instruction::getPrevNode() const { |
328 | assert(getParent() != nullptr && "Detached!" ); |
329 | auto It = getIterator(); |
330 | if (It != getParent()->begin()) |
331 | return std::prev(x: getIterator()).get(); |
332 | return nullptr; |
333 | } |
334 | |
335 | void Instruction::removeFromParent() { |
336 | auto &Tracker = Ctx.getTracker(); |
337 | if (Tracker.isTracking()) |
338 | Tracker.track(Change: std::make_unique<RemoveFromParent>(args: this, args&: Tracker)); |
339 | |
340 | // Detach all the LLVM IR instructions from their parent BB. |
341 | for (llvm::Instruction *I : getLLVMInstrs()) |
342 | I->removeFromParent(); |
343 | } |
344 | |
345 | void Instruction::eraseFromParent() { |
346 | assert(users().empty() && "Still connected to users, can't erase!" ); |
347 | std::unique_ptr<Value> Detached = Ctx.detach(V: this); |
348 | auto LLVMInstrs = getLLVMInstrs(); |
349 | |
350 | auto &Tracker = Ctx.getTracker(); |
351 | if (Tracker.isTracking()) { |
352 | Tracker.track( |
353 | Change: std::make_unique<EraseFromParent>(args: std::move(Detached), args&: Tracker)); |
354 | // We don't actually delete the IR instruction, because then it would be |
355 | // impossible to bring it back from the dead at the same memory location. |
356 | // Instead we remove it from its BB and track its current location. |
357 | for (llvm::Instruction *I : LLVMInstrs) |
358 | I->removeFromParent(); |
359 | // TODO: Multi-instructions need special treatment because some of the |
360 | // references are internal to the instruction. |
361 | for (llvm::Instruction *I : LLVMInstrs) |
362 | I->dropAllReferences(); |
363 | } else { |
364 | // Erase in reverse to avoid erasing nstructions with attached uses. |
365 | for (llvm::Instruction *I : reverse(C&: LLVMInstrs)) |
366 | I->eraseFromParent(); |
367 | } |
368 | } |
369 | |
370 | void Instruction::moveBefore(BasicBlock &BB, const BBIterator &WhereIt) { |
371 | if (std::next(x: getIterator()) == WhereIt) |
372 | // Destination is same as origin, nothing to do. |
373 | return; |
374 | |
375 | auto &Tracker = Ctx.getTracker(); |
376 | if (Tracker.isTracking()) |
377 | Tracker.track(Change: std::make_unique<MoveInstr>(args: this, args&: Tracker)); |
378 | |
379 | auto *LLVMBB = cast<llvm::BasicBlock>(Val: BB.Val); |
380 | llvm::BasicBlock::iterator It; |
381 | if (WhereIt == BB.end()) { |
382 | It = LLVMBB->end(); |
383 | } else { |
384 | Instruction *WhereI = &*WhereIt; |
385 | It = WhereI->getTopmostLLVMInstruction()->getIterator(); |
386 | } |
387 | // TODO: Move this to the verifier of sandboxir::Instruction. |
388 | assert(is_sorted(getLLVMInstrs(), |
389 | [](auto *I1, auto *I2) { return I1->comesBefore(I2); }) && |
390 | "Expected program order!" ); |
391 | // Do the actual move in LLVM IR. |
392 | for (auto *I : getLLVMInstrs()) |
393 | I->moveBefore(BB&: *LLVMBB, I: It); |
394 | } |
395 | |
396 | void Instruction::insertBefore(Instruction *BeforeI) { |
397 | llvm::Instruction *BeforeTopI = BeforeI->getTopmostLLVMInstruction(); |
398 | // TODO: Move this to the verifier of sandboxir::Instruction. |
399 | assert(is_sorted(getLLVMInstrs(), |
400 | [](auto *I1, auto *I2) { return I1->comesBefore(I2); }) && |
401 | "Expected program order!" ); |
402 | // Insert the LLVM IR Instructions in program order. |
403 | for (llvm::Instruction *I : getLLVMInstrs()) |
404 | I->insertBefore(InsertPos: BeforeTopI); |
405 | } |
406 | |
407 | void Instruction::insertAfter(Instruction *AfterI) { |
408 | insertInto(BB: AfterI->getParent(), WhereIt: std::next(x: AfterI->getIterator())); |
409 | } |
410 | |
411 | void Instruction::insertInto(BasicBlock *BB, const BBIterator &WhereIt) { |
412 | llvm::BasicBlock *LLVMBB = cast<llvm::BasicBlock>(Val: BB->Val); |
413 | llvm::Instruction *LLVMBeforeI; |
414 | llvm::BasicBlock::iterator LLVMBeforeIt; |
415 | if (WhereIt != BB->end()) { |
416 | Instruction *BeforeI = &*WhereIt; |
417 | LLVMBeforeI = BeforeI->getTopmostLLVMInstruction(); |
418 | LLVMBeforeIt = LLVMBeforeI->getIterator(); |
419 | } else { |
420 | LLVMBeforeI = nullptr; |
421 | LLVMBeforeIt = LLVMBB->end(); |
422 | } |
423 | // Insert the LLVM IR Instructions in program order. |
424 | for (llvm::Instruction *I : getLLVMInstrs()) |
425 | I->insertInto(ParentBB: LLVMBB, It: LLVMBeforeIt); |
426 | } |
427 | |
428 | BasicBlock *Instruction::getParent() const { |
429 | // Get the LLVM IR Instruction that this maps to, get its parent, and get the |
430 | // corresponding sandboxir::BasicBlock by looking it up in sandboxir::Context. |
431 | auto *BB = cast<llvm::Instruction>(Val)->getParent(); |
432 | if (BB == nullptr) |
433 | return nullptr; |
434 | return cast<BasicBlock>(Val: Ctx.getValue(V: BB)); |
435 | } |
436 | |
437 | bool Instruction::classof(const sandboxir::Value *From) { |
438 | switch (From->getSubclassID()) { |
439 | #define DEF_INSTR(ID, OPC, CLASS) \ |
440 | case ClassID::ID: \ |
441 | return true; |
442 | #include "llvm/SandboxIR/SandboxIRValues.def" |
443 | default: |
444 | return false; |
445 | } |
446 | } |
447 | |
448 | #ifndef NDEBUG |
449 | void Instruction::dump(raw_ostream &OS) const { |
450 | OS << "Unimplemented! Please override dump()." ; |
451 | } |
452 | void Instruction::dump() const { |
453 | dump(dbgs()); |
454 | dbgs() << "\n" ; |
455 | } |
456 | #endif // NDEBUG |
457 | |
458 | Value *SelectInst::createCommon(Value *Cond, Value *True, Value *False, |
459 | const Twine &Name, IRBuilder<> &Builder, |
460 | Context &Ctx) { |
461 | llvm::Value *NewV = |
462 | Builder.CreateSelect(C: Cond->Val, True: True->Val, False: False->Val, Name); |
463 | if (auto *NewSI = dyn_cast<llvm::SelectInst>(Val: NewV)) |
464 | return Ctx.createSelectInst(SI: NewSI); |
465 | assert(isa<llvm::Constant>(NewV) && "Expected constant" ); |
466 | return Ctx.getOrCreateConstant(LLVMC: cast<llvm::Constant>(Val: NewV)); |
467 | } |
468 | |
469 | Value *SelectInst::create(Value *Cond, Value *True, Value *False, |
470 | Instruction *InsertBefore, Context &Ctx, |
471 | const Twine &Name) { |
472 | llvm::Instruction *BeforeIR = InsertBefore->getTopmostLLVMInstruction(); |
473 | auto &Builder = Ctx.getLLVMIRBuilder(); |
474 | Builder.SetInsertPoint(BeforeIR); |
475 | return createCommon(Cond, True, False, Name, Builder, Ctx); |
476 | } |
477 | |
478 | Value *SelectInst::create(Value *Cond, Value *True, Value *False, |
479 | BasicBlock *InsertAtEnd, Context &Ctx, |
480 | const Twine &Name) { |
481 | auto *IRInsertAtEnd = cast<llvm::BasicBlock>(Val: InsertAtEnd->Val); |
482 | auto &Builder = Ctx.getLLVMIRBuilder(); |
483 | Builder.SetInsertPoint(IRInsertAtEnd); |
484 | return createCommon(Cond, True, False, Name, Builder, Ctx); |
485 | } |
486 | |
487 | bool SelectInst::classof(const Value *From) { |
488 | return From->getSubclassID() == ClassID::Select; |
489 | } |
490 | |
491 | #ifndef NDEBUG |
492 | void SelectInst::dump(raw_ostream &OS) const { |
493 | dumpCommonPrefix(OS); |
494 | dumpCommonSuffix(OS); |
495 | } |
496 | |
497 | void SelectInst::dump() const { |
498 | dump(dbgs()); |
499 | dbgs() << "\n" ; |
500 | } |
501 | #endif // NDEBUG |
502 | |
503 | LoadInst *LoadInst::create(Type *Ty, Value *Ptr, MaybeAlign Align, |
504 | Instruction *InsertBefore, Context &Ctx, |
505 | const Twine &Name) { |
506 | llvm::Instruction *BeforeIR = InsertBefore->getTopmostLLVMInstruction(); |
507 | auto &Builder = Ctx.getLLVMIRBuilder(); |
508 | Builder.SetInsertPoint(BeforeIR); |
509 | auto *NewLI = Builder.CreateAlignedLoad(Ty, Ptr: Ptr->Val, Align, |
510 | /*isVolatile=*/false, Name); |
511 | auto *NewSBI = Ctx.createLoadInst(LI: NewLI); |
512 | return NewSBI; |
513 | } |
514 | |
515 | LoadInst *LoadInst::create(Type *Ty, Value *Ptr, MaybeAlign Align, |
516 | BasicBlock *InsertAtEnd, Context &Ctx, |
517 | const Twine &Name) { |
518 | auto &Builder = Ctx.getLLVMIRBuilder(); |
519 | Builder.SetInsertPoint(cast<llvm::BasicBlock>(Val: InsertAtEnd->Val)); |
520 | auto *NewLI = Builder.CreateAlignedLoad(Ty, Ptr: Ptr->Val, Align, |
521 | /*isVolatile=*/false, Name); |
522 | auto *NewSBI = Ctx.createLoadInst(LI: NewLI); |
523 | return NewSBI; |
524 | } |
525 | |
526 | bool LoadInst::classof(const Value *From) { |
527 | return From->getSubclassID() == ClassID::Load; |
528 | } |
529 | |
530 | Value *LoadInst::getPointerOperand() const { |
531 | return Ctx.getValue(V: cast<llvm::LoadInst>(Val)->getPointerOperand()); |
532 | } |
533 | |
534 | #ifndef NDEBUG |
535 | void LoadInst::dump(raw_ostream &OS) const { |
536 | dumpCommonPrefix(OS); |
537 | dumpCommonSuffix(OS); |
538 | } |
539 | |
540 | void LoadInst::dump() const { |
541 | dump(dbgs()); |
542 | dbgs() << "\n" ; |
543 | } |
544 | #endif // NDEBUG |
545 | StoreInst *StoreInst::create(Value *V, Value *Ptr, MaybeAlign Align, |
546 | Instruction *InsertBefore, Context &Ctx) { |
547 | llvm::Instruction *BeforeIR = InsertBefore->getTopmostLLVMInstruction(); |
548 | auto &Builder = Ctx.getLLVMIRBuilder(); |
549 | Builder.SetInsertPoint(BeforeIR); |
550 | auto *NewSI = |
551 | Builder.CreateAlignedStore(Val: V->Val, Ptr: Ptr->Val, Align, /*isVolatile=*/false); |
552 | auto *NewSBI = Ctx.createStoreInst(SI: NewSI); |
553 | return NewSBI; |
554 | } |
555 | StoreInst *StoreInst::create(Value *V, Value *Ptr, MaybeAlign Align, |
556 | BasicBlock *InsertAtEnd, Context &Ctx) { |
557 | auto *InsertAtEndIR = cast<llvm::BasicBlock>(Val: InsertAtEnd->Val); |
558 | auto &Builder = Ctx.getLLVMIRBuilder(); |
559 | Builder.SetInsertPoint(InsertAtEndIR); |
560 | auto *NewSI = |
561 | Builder.CreateAlignedStore(Val: V->Val, Ptr: Ptr->Val, Align, /*isVolatile=*/false); |
562 | auto *NewSBI = Ctx.createStoreInst(SI: NewSI); |
563 | return NewSBI; |
564 | } |
565 | |
566 | bool StoreInst::classof(const Value *From) { |
567 | return From->getSubclassID() == ClassID::Store; |
568 | } |
569 | |
570 | Value *StoreInst::getValueOperand() const { |
571 | return Ctx.getValue(V: cast<llvm::StoreInst>(Val)->getValueOperand()); |
572 | } |
573 | |
574 | Value *StoreInst::getPointerOperand() const { |
575 | return Ctx.getValue(V: cast<llvm::StoreInst>(Val)->getPointerOperand()); |
576 | } |
577 | |
578 | #ifndef NDEBUG |
579 | void StoreInst::dump(raw_ostream &OS) const { |
580 | dumpCommonPrefix(OS); |
581 | dumpCommonSuffix(OS); |
582 | } |
583 | |
584 | void StoreInst::dump() const { |
585 | dump(dbgs()); |
586 | dbgs() << "\n" ; |
587 | } |
588 | #endif // NDEBUG |
589 | |
590 | ReturnInst *ReturnInst::createCommon(Value *RetVal, IRBuilder<> &Builder, |
591 | Context &Ctx) { |
592 | llvm::ReturnInst *NewRI; |
593 | if (RetVal != nullptr) |
594 | NewRI = Builder.CreateRet(V: RetVal->Val); |
595 | else |
596 | NewRI = Builder.CreateRetVoid(); |
597 | return Ctx.createReturnInst(I: NewRI); |
598 | } |
599 | |
600 | ReturnInst *ReturnInst::create(Value *RetVal, Instruction *InsertBefore, |
601 | Context &Ctx) { |
602 | llvm::Instruction *BeforeIR = InsertBefore->getTopmostLLVMInstruction(); |
603 | auto &Builder = Ctx.getLLVMIRBuilder(); |
604 | Builder.SetInsertPoint(BeforeIR); |
605 | return createCommon(RetVal, Builder, Ctx); |
606 | } |
607 | |
608 | ReturnInst *ReturnInst::create(Value *RetVal, BasicBlock *InsertAtEnd, |
609 | Context &Ctx) { |
610 | auto &Builder = Ctx.getLLVMIRBuilder(); |
611 | Builder.SetInsertPoint(cast<llvm::BasicBlock>(Val: InsertAtEnd->Val)); |
612 | return createCommon(RetVal, Builder, Ctx); |
613 | } |
614 | |
615 | Value *ReturnInst::getReturnValue() const { |
616 | auto *LLVMRetVal = cast<llvm::ReturnInst>(Val)->getReturnValue(); |
617 | return LLVMRetVal != nullptr ? Ctx.getValue(V: LLVMRetVal) : nullptr; |
618 | } |
619 | |
620 | #ifndef NDEBUG |
621 | void ReturnInst::dump(raw_ostream &OS) const { |
622 | dumpCommonPrefix(OS); |
623 | dumpCommonSuffix(OS); |
624 | } |
625 | |
626 | void ReturnInst::dump() const { |
627 | dump(dbgs()); |
628 | dbgs() << "\n" ; |
629 | } |
630 | |
631 | void OpaqueInst::dump(raw_ostream &OS) const { |
632 | dumpCommonPrefix(OS); |
633 | dumpCommonSuffix(OS); |
634 | } |
635 | |
636 | void OpaqueInst::dump() const { |
637 | dump(dbgs()); |
638 | dbgs() << "\n" ; |
639 | } |
640 | #endif // NDEBUG |
641 | |
642 | Constant *Constant::createInt(Type *Ty, uint64_t V, Context &Ctx, |
643 | bool IsSigned) { |
644 | llvm::Constant *LLVMC = llvm::ConstantInt::get(Ty, V, IsSigned); |
645 | return Ctx.getOrCreateConstant(LLVMC); |
646 | } |
647 | |
648 | #ifndef NDEBUG |
649 | void Constant::dump(raw_ostream &OS) const { |
650 | dumpCommonPrefix(OS); |
651 | dumpCommonSuffix(OS); |
652 | } |
653 | |
654 | void Constant::dump() const { |
655 | dump(dbgs()); |
656 | dbgs() << "\n" ; |
657 | } |
658 | |
659 | void Function::dumpNameAndArgs(raw_ostream &OS) const { |
660 | auto *F = cast<llvm::Function>(Val); |
661 | OS << *F->getReturnType() << " @" << F->getName() << "(" ; |
662 | interleave( |
663 | F->args(), |
664 | [this, &OS](const llvm::Argument &LLVMArg) { |
665 | auto *SBArg = cast_or_null<Argument>(Ctx.getValue(&LLVMArg)); |
666 | if (SBArg == nullptr) |
667 | OS << "NULL" ; |
668 | else |
669 | SBArg->printAsOperand(OS); |
670 | }, |
671 | [&] { OS << ", " ; }); |
672 | OS << ")" ; |
673 | } |
674 | void Function::dump(raw_ostream &OS) const { |
675 | dumpNameAndArgs(OS); |
676 | OS << " {\n" ; |
677 | auto *LLVMF = cast<llvm::Function>(Val); |
678 | interleave( |
679 | *LLVMF, |
680 | [this, &OS](const llvm::BasicBlock &LLVMBB) { |
681 | auto *BB = cast_or_null<BasicBlock>(Ctx.getValue(&LLVMBB)); |
682 | if (BB == nullptr) |
683 | OS << "NULL" ; |
684 | else |
685 | OS << *BB; |
686 | }, |
687 | [&OS] { OS << "\n" ; }); |
688 | OS << "}\n" ; |
689 | } |
690 | void Function::dump() const { |
691 | dump(dbgs()); |
692 | dbgs() << "\n" ; |
693 | } |
694 | #endif // NDEBUG |
695 | |
696 | BasicBlock::iterator::pointer |
697 | BasicBlock::iterator::getInstr(llvm::BasicBlock::iterator It) const { |
698 | return cast_or_null<Instruction>(Val: Ctx->getValue(V: &*It)); |
699 | } |
700 | |
701 | std::unique_ptr<Value> Context::detachLLVMValue(llvm::Value *V) { |
702 | std::unique_ptr<Value> Erased; |
703 | auto It = LLVMValueToValueMap.find(Val: V); |
704 | if (It != LLVMValueToValueMap.end()) { |
705 | auto *Val = It->second.release(); |
706 | Erased = std::unique_ptr<Value>(Val); |
707 | LLVMValueToValueMap.erase(I: It); |
708 | } |
709 | return Erased; |
710 | } |
711 | |
712 | std::unique_ptr<Value> Context::detach(Value *V) { |
713 | assert(V->getSubclassID() != Value::ClassID::Constant && |
714 | "Can't detach a constant!" ); |
715 | assert(V->getSubclassID() != Value::ClassID::User && "Can't detach a user!" ); |
716 | return detachLLVMValue(V: V->Val); |
717 | } |
718 | |
719 | Value *Context::registerValue(std::unique_ptr<Value> &&VPtr) { |
720 | assert(VPtr->getSubclassID() != Value::ClassID::User && |
721 | "Can't register a user!" ); |
722 | Value *V = VPtr.get(); |
723 | [[maybe_unused]] auto Pair = |
724 | LLVMValueToValueMap.insert(KV: {VPtr->Val, std::move(VPtr)}); |
725 | assert(Pair.second && "Already exists!" ); |
726 | return V; |
727 | } |
728 | |
729 | Value *Context::getOrCreateValueInternal(llvm::Value *LLVMV, llvm::User *U) { |
730 | auto Pair = LLVMValueToValueMap.insert(KV: {LLVMV, nullptr}); |
731 | auto It = Pair.first; |
732 | if (!Pair.second) |
733 | return It->second.get(); |
734 | |
735 | if (auto *C = dyn_cast<llvm::Constant>(Val: LLVMV)) { |
736 | It->second = std::unique_ptr<Constant>(new Constant(C, *this)); |
737 | auto *NewC = It->second.get(); |
738 | for (llvm::Value *COp : C->operands()) |
739 | getOrCreateValueInternal(LLVMV: COp, U: C); |
740 | return NewC; |
741 | } |
742 | if (auto *Arg = dyn_cast<llvm::Argument>(Val: LLVMV)) { |
743 | It->second = std::unique_ptr<Argument>(new Argument(Arg, *this)); |
744 | return It->second.get(); |
745 | } |
746 | if (auto *BB = dyn_cast<llvm::BasicBlock>(Val: LLVMV)) { |
747 | assert(isa<BlockAddress>(U) && |
748 | "This won't create a SBBB, don't call this function directly!" ); |
749 | if (auto *SBBB = getValue(V: BB)) |
750 | return SBBB; |
751 | return nullptr; |
752 | } |
753 | assert(isa<llvm::Instruction>(LLVMV) && "Expected Instruction" ); |
754 | |
755 | switch (cast<llvm::Instruction>(Val: LLVMV)->getOpcode()) { |
756 | case llvm::Instruction::Select: { |
757 | auto *LLVMSel = cast<llvm::SelectInst>(Val: LLVMV); |
758 | It->second = std::unique_ptr<SelectInst>(new SelectInst(LLVMSel, *this)); |
759 | return It->second.get(); |
760 | } |
761 | case llvm::Instruction::Load: { |
762 | auto *LLVMLd = cast<llvm::LoadInst>(Val: LLVMV); |
763 | It->second = std::unique_ptr<LoadInst>(new LoadInst(LLVMLd, *this)); |
764 | return It->second.get(); |
765 | } |
766 | case llvm::Instruction::Store: { |
767 | auto *LLVMSt = cast<llvm::StoreInst>(Val: LLVMV); |
768 | It->second = std::unique_ptr<StoreInst>(new StoreInst(LLVMSt, *this)); |
769 | return It->second.get(); |
770 | } |
771 | case llvm::Instruction::Ret: { |
772 | auto *LLVMRet = cast<llvm::ReturnInst>(Val: LLVMV); |
773 | It->second = std::unique_ptr<ReturnInst>(new ReturnInst(LLVMRet, *this)); |
774 | return It->second.get(); |
775 | } |
776 | default: |
777 | break; |
778 | } |
779 | |
780 | It->second = std::unique_ptr<OpaqueInst>( |
781 | new OpaqueInst(cast<llvm::Instruction>(Val: LLVMV), *this)); |
782 | return It->second.get(); |
783 | } |
784 | |
785 | BasicBlock *Context::createBasicBlock(llvm::BasicBlock *LLVMBB) { |
786 | assert(getValue(LLVMBB) == nullptr && "Already exists!" ); |
787 | auto NewBBPtr = std::unique_ptr<BasicBlock>(new BasicBlock(LLVMBB, *this)); |
788 | auto *BB = cast<BasicBlock>(Val: registerValue(VPtr: std::move(NewBBPtr))); |
789 | // Create SandboxIR for BB's body. |
790 | BB->buildBasicBlockFromLLVMIR(LLVMBB); |
791 | return BB; |
792 | } |
793 | |
794 | SelectInst *Context::createSelectInst(llvm::SelectInst *SI) { |
795 | auto NewPtr = std::unique_ptr<SelectInst>(new SelectInst(SI, *this)); |
796 | return cast<SelectInst>(Val: registerValue(VPtr: std::move(NewPtr))); |
797 | } |
798 | |
799 | LoadInst *Context::createLoadInst(llvm::LoadInst *LI) { |
800 | auto NewPtr = std::unique_ptr<LoadInst>(new LoadInst(LI, *this)); |
801 | return cast<LoadInst>(Val: registerValue(VPtr: std::move(NewPtr))); |
802 | } |
803 | |
804 | StoreInst *Context::createStoreInst(llvm::StoreInst *SI) { |
805 | auto NewPtr = std::unique_ptr<StoreInst>(new StoreInst(SI, *this)); |
806 | return cast<StoreInst>(Val: registerValue(VPtr: std::move(NewPtr))); |
807 | } |
808 | |
809 | ReturnInst *Context::createReturnInst(llvm::ReturnInst *I) { |
810 | auto NewPtr = std::unique_ptr<ReturnInst>(new ReturnInst(I, *this)); |
811 | return cast<ReturnInst>(Val: registerValue(VPtr: std::move(NewPtr))); |
812 | } |
813 | |
814 | Value *Context::getValue(llvm::Value *V) const { |
815 | auto It = LLVMValueToValueMap.find(Val: V); |
816 | if (It != LLVMValueToValueMap.end()) |
817 | return It->second.get(); |
818 | return nullptr; |
819 | } |
820 | |
821 | Function *Context::createFunction(llvm::Function *F) { |
822 | assert(getValue(F) == nullptr && "Already exists!" ); |
823 | auto NewFPtr = std::unique_ptr<Function>(new Function(F, *this)); |
824 | // Create arguments. |
825 | for (auto &Arg : F->args()) |
826 | getOrCreateArgument(LLVMArg: &Arg); |
827 | // Create BBs. |
828 | for (auto &BB : *F) |
829 | createBasicBlock(LLVMBB: &BB); |
830 | auto *SBF = cast<Function>(Val: registerValue(VPtr: std::move(NewFPtr))); |
831 | return SBF; |
832 | } |
833 | |
834 | Function *BasicBlock::getParent() const { |
835 | auto *BB = cast<llvm::BasicBlock>(Val); |
836 | auto *F = BB->getParent(); |
837 | if (F == nullptr) |
838 | // Detached |
839 | return nullptr; |
840 | return cast_or_null<Function>(Val: Ctx.getValue(V: F)); |
841 | } |
842 | |
843 | void BasicBlock::buildBasicBlockFromLLVMIR(llvm::BasicBlock *LLVMBB) { |
844 | for (llvm::Instruction &IRef : reverse(C&: *LLVMBB)) { |
845 | llvm::Instruction *I = &IRef; |
846 | Ctx.getOrCreateValue(LLVMV: I); |
847 | for (auto [OpIdx, Op] : enumerate(First: I->operands())) { |
848 | // Skip instruction's label operands |
849 | if (isa<llvm::BasicBlock>(Val: Op)) |
850 | continue; |
851 | // Skip metadata |
852 | if (isa<llvm::MetadataAsValue>(Val: Op)) |
853 | continue; |
854 | // Skip asm |
855 | if (isa<llvm::InlineAsm>(Val: Op)) |
856 | continue; |
857 | Ctx.getOrCreateValue(LLVMV: Op); |
858 | } |
859 | } |
860 | #if !defined(NDEBUG) && defined(SBVEC_EXPENSIVE_CHECKS) |
861 | verify(); |
862 | #endif |
863 | } |
864 | |
865 | BasicBlock::iterator BasicBlock::begin() const { |
866 | llvm::BasicBlock *BB = cast<llvm::BasicBlock>(Val); |
867 | llvm::BasicBlock::iterator It = BB->begin(); |
868 | if (!BB->empty()) { |
869 | auto *V = Ctx.getValue(V: &*BB->begin()); |
870 | assert(V != nullptr && "No SandboxIR for BB->begin()!" ); |
871 | auto *I = cast<Instruction>(Val: V); |
872 | unsigned Num = I->getNumOfIRInstrs(); |
873 | assert(Num >= 1u && "Bad getNumOfIRInstrs()" ); |
874 | It = std::next(x: It, n: Num - 1); |
875 | } |
876 | return iterator(BB, It, &Ctx); |
877 | } |
878 | |
879 | Instruction *BasicBlock::getTerminator() const { |
880 | auto *TerminatorV = |
881 | Ctx.getValue(V: cast<llvm::BasicBlock>(Val)->getTerminator()); |
882 | return cast_or_null<Instruction>(Val: TerminatorV); |
883 | } |
884 | |
885 | Instruction &BasicBlock::front() const { |
886 | auto *BB = cast<llvm::BasicBlock>(Val); |
887 | assert(!BB->empty() && "Empty block!" ); |
888 | auto *SBI = cast<Instruction>(Val: getContext().getValue(V: &*BB->begin())); |
889 | assert(SBI != nullptr && "Expected Instr!" ); |
890 | return *SBI; |
891 | } |
892 | |
893 | Instruction &BasicBlock::back() const { |
894 | auto *BB = cast<llvm::BasicBlock>(Val); |
895 | assert(!BB->empty() && "Empty block!" ); |
896 | auto *SBI = cast<Instruction>(Val: getContext().getValue(V: &*BB->rbegin())); |
897 | assert(SBI != nullptr && "Expected Instr!" ); |
898 | return *SBI; |
899 | } |
900 | |
901 | #ifndef NDEBUG |
902 | void BasicBlock::dump(raw_ostream &OS) const { |
903 | llvm::BasicBlock *BB = cast<llvm::BasicBlock>(Val); |
904 | const auto &Name = BB->getName(); |
905 | OS << Name; |
906 | if (!Name.empty()) |
907 | OS << ":\n" ; |
908 | // If there are Instructions in the BB that are not mapped to SandboxIR, then |
909 | // use a crash-proof dump. |
910 | if (any_of(*BB, [this](llvm::Instruction &I) { |
911 | return Ctx.getValue(&I) == nullptr; |
912 | })) { |
913 | OS << "<Crash-proof mode!>\n" ; |
914 | DenseSet<Instruction *> Visited; |
915 | for (llvm::Instruction &IRef : *BB) { |
916 | Value *SBV = Ctx.getValue(&IRef); |
917 | if (SBV == nullptr) |
918 | OS << IRef << " *** No SandboxIR ***\n" ; |
919 | else { |
920 | auto *SBI = dyn_cast<Instruction>(SBV); |
921 | if (SBI == nullptr) { |
922 | OS << IRef << " *** Not a SBInstruction!!! ***\n" ; |
923 | } else { |
924 | if (Visited.insert(SBI).second) |
925 | OS << *SBI << "\n" ; |
926 | } |
927 | } |
928 | } |
929 | } else { |
930 | for (auto &SBI : *this) { |
931 | SBI.dump(OS); |
932 | OS << "\n" ; |
933 | } |
934 | } |
935 | } |
936 | void BasicBlock::dump() const { |
937 | dump(dbgs()); |
938 | dbgs() << "\n" ; |
939 | } |
940 | #endif // NDEBUG |
941 | |