Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : #undef DEBUG
4 : : #include "llvm-version.h"
5 : :
6 : : #include <llvm-c/Core.h>
7 : : #include <llvm-c/Types.h>
8 : :
9 : : #include <llvm/ADT/SmallSet.h>
10 : : #include <llvm/ADT/SmallVector.h>
11 : : #include <llvm/ADT/SetVector.h>
12 : : #include <llvm/ADT/Statistic.h>
13 : : #include <llvm/IR/Value.h>
14 : : #include <llvm/IR/CFG.h>
15 : : #include <llvm/IR/LegacyPassManager.h>
16 : : #include <llvm/IR/Dominators.h>
17 : : #include <llvm/IR/Function.h>
18 : : #include <llvm/IR/Instructions.h>
19 : : #include <llvm/IR/IntrinsicInst.h>
20 : : #include <llvm/IR/Module.h>
21 : : #include <llvm/IR/Operator.h>
22 : : #include <llvm/IR/IRBuilder.h>
23 : : #include <llvm/IR/Verifier.h>
24 : : #include <llvm/Pass.h>
25 : : #include <llvm/Support/Debug.h>
26 : : #include <llvm/Transforms/Utils/PromoteMemToReg.h>
27 : :
28 : : #include <llvm/InitializePasses.h>
29 : :
30 : : #include "codegen_shared.h"
31 : : #include "julia.h"
32 : : #include "julia_internal.h"
33 : : #include "llvm-pass-helpers.h"
34 : : #include "llvm-alloc-helpers.h"
35 : : #include "passes.h"
36 : :
37 : : #include <map>
38 : : #include <set>
39 : :
40 : : #define DEBUG_TYPE "alloc_opt"
41 : : #include "julia_assert.h"
42 : :
43 : : using namespace llvm;
44 : : using namespace jl_alloc;
45 : :
46 : : STATISTIC(RemovedAllocs, "Total number of heap allocations elided");
47 : : STATISTIC(DeletedAllocs, "Total number of heap allocations fully deleted");
48 : : STATISTIC(SplitAllocs, "Total number of allocations split into registers");
49 : : STATISTIC(StackAllocs, "Total number of allocations moved to the stack");
50 : : STATISTIC(RemovedTypeofs, "Total number of typeofs removed");
51 : : STATISTIC(RemovedWriteBarriers, "Total number of write barriers removed");
52 : : STATISTIC(RemovedGCPreserve, "Total number of GC preserve instructions removed");
53 : :
54 : : namespace {
55 : :
56 : 487 : static void removeGCPreserve(CallInst *call, Instruction *val)
57 : : {
58 : 487 : ++RemovedGCPreserve;
59 : 487 : auto replace = Constant::getNullValue(val->getType());
60 : 487 : call->replaceUsesOfWith(val, replace);
61 [ + + ]: 974 : for (auto &arg: call->args()) {
62 [ + + ]: 497 : if (!isa<Constant>(arg.get())) {
63 : 10 : return;
64 : : }
65 : : }
66 [ + + ]: 612 : while (!call->use_empty()) {
67 : 135 : auto end = cast<Instruction>(*call->user_begin());
68 : : // gc_preserve_end returns void.
69 [ - + ]: 135 : assert(end->use_empty());
70 : 135 : end->eraseFromParent();
71 : : }
72 : 477 : call->eraseFromParent();
73 : : }
74 : :
75 : : /**
76 : : * Promote `julia.gc_alloc_obj` which do not have escaping root to a alloca.
77 : : * Uses that are not considered to escape the object (i.e. heap address) includes,
78 : : *
79 : : * * load
80 : : * * `pointer_from_objref`
81 : : * * Any real llvm intrinsics
82 : : * * gc preserve intrinsics
83 : : * * `ccall` gcroot array (`jl_roots` operand bundle)
84 : : * * store (as address)
85 : : * * addrspacecast, bitcast, getelementptr
86 : : *
87 : : * The results of these cast instructions will be scanned recursively.
88 : : *
89 : : * All other uses are considered to escape conservatively.
90 : : */
91 : :
92 : : /**
93 : : * TODO:
94 : : * * Return twice
95 : : * * Handle phi node.
96 : : * * Look through `pointer_from_objref`.
97 : : * * Handle jl_box*
98 : : */
99 : :
100 : : struct AllocOpt : public JuliaPassContext {
101 : :
102 : : const DataLayout *DL;
103 : :
104 : : Function *lifetime_start;
105 : : Function *lifetime_end;
106 : :
107 : : bool doInitialization(Module &m);
108 : : bool runOnFunction(Function &F, function_ref<DominatorTree&()> GetDT);
109 : : };
110 : :
111 : : struct Optimizer {
112 : 1294250 : Optimizer(Function &F, AllocOpt &pass, function_ref<DominatorTree&()> GetDT)
113 : 1294250 : : F(F),
114 : : pass(pass),
115 : 1294250 : GetDT(std::move(GetDT))
116 : 1294250 : {}
117 : :
118 : : void initialize();
119 : : void optimizeAll();
120 : : bool finalize();
121 : : private:
122 : : bool isSafepoint(Instruction *inst);
123 : : Instruction *getFirstSafepoint(BasicBlock *bb);
124 : : ssize_t getGCAllocSize(Instruction *I);
125 : : void pushInstruction(Instruction *I);
126 : :
127 : : void insertLifetimeEnd(Value *ptr, Constant *sz, Instruction *insert);
128 : : // insert llvm.lifetime.* calls for `ptr` with size `sz` based on the use of `orig`.
129 : : void insertLifetime(Value *ptr, Constant *sz, Instruction *orig);
130 : :
131 : : void checkInst(Instruction *I);
132 : :
133 : : void replaceIntrinsicUseWith(IntrinsicInst *call, Intrinsic::ID ID,
134 : : Instruction *orig_i, Instruction *new_i);
135 : : void removeAlloc(CallInst *orig_inst);
136 : : void moveToStack(CallInst *orig_inst, size_t sz, bool has_ref);
137 : : void splitOnStack(CallInst *orig_inst);
138 : : void optimizeTag(CallInst *orig_inst);
139 : :
140 : : Function &F;
141 : : AllocOpt &pass;
142 : : DominatorTree *_DT = nullptr;
143 : : function_ref<DominatorTree &()> GetDT;
144 : :
145 : 18499 : DominatorTree &getDomTree()
146 : : {
147 [ + + ]: 18499 : if (!_DT)
148 : 4475 : _DT = &GetDT();
149 : 18499 : return *_DT;
150 : : }
151 : : struct Lifetime {
152 : : struct Frame {
153 : : BasicBlock *bb;
154 : : pred_iterator p_cur;
155 : : pred_iterator p_end;
156 : 31966 : Frame(BasicBlock *bb)
157 : 31966 : : bb(bb),
158 : 31966 : p_cur(pred_begin(bb)),
159 : 31966 : p_end(pred_end(bb))
160 : 31966 : {}
161 : : };
162 : : typedef SmallVector<Frame,4> Stack;
163 : : };
164 : : struct ReplaceUses {
165 : : struct Frame {
166 : : Instruction *orig_i;
167 : : union {
168 : : Instruction *new_i;
169 : : uint32_t offset;
170 : : };
171 : 83028 : Frame(Instruction *orig_i, Instruction *new_i)
172 : 83028 : : orig_i(orig_i),
173 : 83028 : new_i(new_i)
174 : 83028 : {}
175 : 123 : Frame(Instruction *orig_i, uint32_t offset)
176 : 123 : : orig_i(orig_i),
177 : 123 : offset(offset)
178 : 123 : {}
179 : : };
180 : : typedef SmallVector<Frame,4> Stack;
181 : : };
182 : :
183 : : SetVector<std::pair<CallInst*,size_t>> worklist;
184 : : SmallVector<CallInst*,6> removed;
185 : : AllocUseInfo use_info;
186 : : CheckInst::Stack check_stack;
187 : : Lifetime::Stack lifetime_stack;
188 : : ReplaceUses::Stack replace_stack;
189 : : std::map<BasicBlock*, llvm::WeakVH> first_safepoint;
190 : : };
191 : :
192 : 178023000 : void Optimizer::pushInstruction(Instruction *I)
193 : : {
194 : 178023000 : ssize_t sz = getGCAllocSize(I);
195 [ + + ]: 178023000 : if (sz != -1) {
196 : 1544190 : worklist.insert(std::make_pair(cast<CallInst>(I), sz));
197 : : }
198 : 178023000 : }
199 : :
200 : 1294250 : void Optimizer::initialize()
201 : : {
202 [ + + ]: 22071800 : for (auto &bb: F) {
203 [ + + ]: 198800000 : for (auto &I: bb) {
204 : 178022000 : pushInstruction(&I);
205 : : }
206 : : }
207 : 1294250 : }
208 : :
209 : 2838440 : void Optimizer::optimizeAll()
210 : : {
211 [ + + ]: 2838440 : while (!worklist.empty()) {
212 : 1544190 : auto item = worklist.pop_back_val();
213 : 1544190 : auto orig = item.first;
214 : 1544190 : size_t sz = item.second;
215 : 1544190 : checkInst(orig);
216 [ + + ]: 1544190 : if (use_info.escaped) {
217 [ + + ]: 779872 : if (use_info.hastypeof)
218 : 199 : optimizeTag(orig);
219 : 1525750 : continue;
220 : : }
221 [ + + + + ]: 764322 : if (use_info.haserror || use_info.returned) {
222 [ + + ]: 744495 : if (use_info.hastypeof)
223 : 35 : optimizeTag(orig);
224 : 744495 : continue;
225 : : }
226 [ + + + + : 19827 : if (!use_info.addrescaped && !use_info.hasload && (!use_info.haspreserve ||
- + ]
227 [ # # ]: 0 : !use_info.refstore)) {
228 : : // No one took the address, no one reads anything and there's no meaningful
229 : : // preserve of fields (either no preserve/ccall or no object reference fields)
230 : : // We can just delete all the uses.
231 : 359 : removeAlloc(orig);
232 : 359 : continue;
233 : : }
234 : 19468 : bool has_ref = false;
235 : 19468 : bool has_refaggr = false;
236 [ + + ]: 40177 : for (auto memop: use_info.memops) {
237 : 21678 : auto &field = memop.second;
238 [ + + ]: 21678 : if (field.hasobjref) {
239 : 969 : has_ref = true;
240 : : // This can be relaxed a little based on hasload
241 : : // TODO: add support for hasaggr load/store
242 [ + + - + : 969 : if (field.hasaggr || field.multiloc || field.size != sizeof(void*)) {
- - ]
243 : 969 : has_refaggr = true;
244 : 969 : break;
245 : : }
246 : : }
247 : : }
248 [ + - + + : 19468 : if (!use_info.hasunknownmem && !use_info.addrescaped && !has_refaggr) {
+ + ]
249 : : // No one actually care about the memory layout of this object, split it.
250 : 54 : splitOnStack(orig);
251 : 54 : continue;
252 : : }
253 [ + + ]: 19414 : if (has_refaggr) {
254 [ + + ]: 969 : if (use_info.hastypeof)
255 : 46 : optimizeTag(orig);
256 : 969 : continue;
257 : : }
258 : : // The object has no fields with mix reference access
259 : 18445 : moveToStack(orig, sz, has_ref);
260 : : }
261 : 1294250 : }
262 : :
263 : 1294250 : bool Optimizer::finalize()
264 : : {
265 [ + + ]: 1294250 : if (removed.empty())
266 : 1289320 : return false;
267 [ + + ]: 24082 : for (auto inst: removed)
268 : 19160 : inst->eraseFromParent();
269 : 4922 : return true;
270 : : }
271 : :
272 : 791408 : bool Optimizer::isSafepoint(Instruction *inst)
273 : : {
274 : 791408 : auto call = dyn_cast<CallInst>(inst);
275 [ + + ]: 791408 : if (!call)
276 : 760546 : return false;
277 [ + + ]: 30862 : if (isa<IntrinsicInst>(call))
278 : 15087 : return false;
279 [ + + ]: 15775 : if (auto callee = call->getCalledFunction()) {
280 : : // Known functions emitted in codegen that are not safepoints
281 [ + + - + : 13695 : if (callee == pass.pointer_from_objref_func || callee->getName() == "memcmp") {
+ + ]
282 : 291 : return false;
283 : : }
284 : : }
285 : 15484 : return true;
286 : : }
287 : :
288 : 136773 : Instruction *Optimizer::getFirstSafepoint(BasicBlock *bb)
289 : : {
290 : 136773 : auto it = first_safepoint.find(bb);
291 [ + + ]: 136773 : if (it != first_safepoint.end()) {
292 : 108525 : Value *Val = it->second;
293 [ + + ]: 108525 : if (Val)
294 : 52632 : return cast<Instruction>(Val);
295 : : }
296 : 84141 : Instruction *first = nullptr;
297 [ + + ]: 748154 : for (auto &I: *bb) {
298 [ + + ]: 678844 : if (isSafepoint(&I)) {
299 : 14831 : first = &I;
300 : 14831 : break;
301 : : }
302 : : }
303 : 84141 : first_safepoint[bb] = first;
304 : 84141 : return first;
305 : : }
306 : :
307 : 178023000 : ssize_t Optimizer::getGCAllocSize(Instruction *I)
308 : : {
309 : 178023000 : auto call = dyn_cast<CallInst>(I);
310 [ + + ]: 178023000 : if (!call)
311 : 159394000 : return -1;
312 [ + + ]: 18628600 : if (call->getCalledOperand() != pass.alloc_obj_func)
313 : 17084400 : return -1;
314 [ - + ]: 1544190 : assert(call->arg_size() == 3);
315 : 1544190 : size_t sz = (size_t)cast<ConstantInt>(call->getArgOperand(1))->getZExtValue();
316 [ + - + - ]: 1544190 : if (sz < IntegerType::MAX_INT_BITS / 8 && sz < INT32_MAX)
317 : 1544190 : return sz;
318 : 0 : return -1;
319 : : }
320 : :
321 : 1544190 : void Optimizer::checkInst(Instruction *I)
322 : : {
323 : 1544190 : jl_alloc::EscapeAnalysisRequiredArgs required{use_info, check_stack, pass, *pass.DL};
324 : 1544190 : jl_alloc::runEscapeAnalysis(I, required);
325 : 1544190 : }
326 : :
327 : 73296 : void Optimizer::insertLifetimeEnd(Value *ptr, Constant *sz, Instruction *insert)
328 : : {
329 : 73296 : BasicBlock::iterator it(insert);
330 : 73296 : BasicBlock::iterator begin(insert->getParent()->begin());
331 : : // Makes sure that the end is inserted before nearby start.
332 : : // We insert start before the allocation call, if it is the first safepoint we find for
333 : : // another instruction, it's better if we insert the end before the start instead of the
334 : : // allocation so that the two allocations do not have overlapping lifetime.
335 [ + + ]: 317231 : while (it != begin) {
336 : 272688 : --it;
337 [ + + ]: 272688 : if (auto II = dyn_cast<IntrinsicInst>(&*it)) {
338 [ + + + + : 487721 : if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
+ + ]
339 : 243767 : II->getIntrinsicID() == Intrinsic::lifetime_end) {
340 : 243935 : insert = II;
341 : 243935 : continue;
342 : : }
343 : : }
344 : 28753 : break;
345 : : }
346 : 73296 : CallInst::Create(pass.lifetime_end, {sz, ptr}, "", insert);
347 : 73296 : }
348 : :
349 : 18499 : void Optimizer::insertLifetime(Value *ptr, Constant *sz, Instruction *orig)
350 : : {
351 : 18499 : CallInst::Create(pass.lifetime_start, {sz, ptr}, "", orig);
352 : 18499 : BasicBlock *def_bb = orig->getParent();
353 : 36998 : std::set<BasicBlock*> bbs{def_bb};
354 : 18499 : auto &DT = getDomTree();
355 : : // Collect all BB where the allocation is live
356 [ + + ]: 139987 : for (auto use: use_info.uses) {
357 : 121488 : auto bb = use->getParent();
358 [ + + ]: 121488 : if (!bbs.insert(bb).second)
359 : 116263 : continue;
360 [ - + ]: 5225 : assert(lifetime_stack.empty());
361 : 5225 : Lifetime::Frame cur{bb};
362 : : while (true) {
363 [ - + ]: 41437 : assert(cur.p_cur != cur.p_end);
364 : 41437 : auto pred = *cur.p_cur;
365 : 41437 : ++cur.p_cur;
366 [ + + ]: 41437 : if (bbs.insert(pred).second) {
367 [ + + ]: 26741 : if (cur.p_cur != cur.p_end)
368 : 7898 : lifetime_stack.push_back(cur);
369 : 26741 : cur = Lifetime::Frame(pred);
370 : : }
371 [ + + ]: 41437 : if (cur.p_cur == cur.p_end) {
372 [ + + ]: 13123 : if (lifetime_stack.empty())
373 : 5225 : break;
374 : 7898 : cur = lifetime_stack.back();
375 : 7898 : lifetime_stack.pop_back();
376 : : }
377 : 36212 : }
378 : : }
379 : : #ifndef JL_NDEBUG
380 [ + + ]: 68964 : for (auto bb: bbs) {
381 [ + + ]: 50465 : if (bb == def_bb)
382 : 18499 : continue;
383 [ + - ]: 31966 : if (DT.dominates(orig, bb))
384 : 31966 : continue;
385 : 0 : auto F = bb->getParent();
386 : 0 : llvm_dump(F);
387 : 0 : llvm_dump(orig);
388 : 0 : jl_safe_printf("Does not dominate BB:\n");
389 : 0 : llvm_dump(bb);
390 : 0 : abort();
391 : : }
392 : : #endif
393 : : // Record extra BBs that contain invisible uses.
394 : 36998 : SmallSet<BasicBlock*, 8> extra_use;
395 : 36998 : SmallVector<DomTreeNodeBase<BasicBlock>*, 8> dominated;
396 [ + + ]: 18986 : for (auto preserve: use_info.preserves) {
397 [ + + ]: 7557 : for (auto RN = DT.getNode(preserve->getParent()); RN;
398 [ + + ]: 7070 : RN = dominated.empty() ? nullptr : dominated.pop_back_val()) {
399 [ + + ]: 13790 : for (auto N: *RN) {
400 : 6720 : auto bb = N->getBlock();
401 [ - + ]: 6720 : if (extra_use.count(bb))
402 : 137 : continue;
403 : 6720 : bool ended = false;
404 [ + + ]: 7734 : for (auto end: preserve->users()) {
405 : 1151 : auto end_bb = cast<Instruction>(end)->getParent();
406 : 1151 : auto end_node = DT.getNode(end_bb);
407 [ + + + - : 1151 : if (end_bb == bb || (end_node && DT.dominates(end_node, N))) {
+ + + + ]
408 : 137 : ended = true;
409 : 137 : break;
410 : : }
411 : : }
412 [ + + ]: 6720 : if (ended)
413 : 137 : continue;
414 : 6583 : bbs.insert(bb);
415 : 6583 : extra_use.insert(bb);
416 : 6583 : dominated.push_back(N);
417 : : }
418 : : }
419 [ - + ]: 487 : assert(dominated.empty());
420 : : }
421 : : // For each BB, find the first instruction(s) where the allocation is possibly dead.
422 : : // If all successors are live, then there isn't one.
423 : : // If all successors are dead, then it's the first instruction after the last use
424 : : // within the BB.
425 : : // If some successors are live and others are dead, it's the first instruction in
426 : : // the successors that are dead.
427 : 36998 : std::vector<Instruction*> first_dead;
428 [ + + ]: 74609 : for (auto bb: bbs) {
429 : 56110 : bool has_use = false;
430 [ + + ]: 84232 : for (auto succ: successors(bb)) {
431 : : // def_bb is the only bb in bbs that's not dominated by orig
432 [ + + + + : 64014 : if (succ != def_bb && bbs.count(succ)) {
+ + ]
433 : 35892 : has_use = true;
434 : 35892 : break;
435 : : }
436 : : }
437 [ + + ]: 56110 : if (has_use) {
438 [ + + ]: 98371 : for (auto succ: successors(bb)) {
439 [ + + ]: 62479 : if (!bbs.count(succ)) {
440 : 14252 : first_dead.push_back(&*succ->begin());
441 : : }
442 : : }
443 : : }
444 [ + + ]: 20218 : else if (extra_use.count(bb)) {
445 : 2537 : first_dead.push_back(bb->getTerminator());
446 : : }
447 : : else {
448 [ + - ]: 132883 : for (auto it = bb->rbegin(), end = bb->rend(); it != end; ++it) {
449 [ + + ]: 132883 : if (use_info.uses.count(&*it)) {
450 : 17681 : --it;
451 : 17681 : first_dead.push_back(&*it);
452 : 17681 : break;
453 : : }
454 : : }
455 : : }
456 : : }
457 : 18499 : bbs.clear();
458 : : // There can/need only be one lifetime.end for each allocation in each bb, use bbs
459 : : // to record that.
460 : : // Iterate through the first dead and find the first safepoint following each of them.
461 [ + + ]: 193630 : while (!first_dead.empty()) {
462 : 175131 : auto I = first_dead.back();
463 : 175131 : first_dead.pop_back();
464 : 175131 : auto bb = I->getParent();
465 [ + + ]: 175131 : if (!bbs.insert(bb).second)
466 : 86256 : continue;
467 [ + + ]: 162171 : if (I == &*bb->begin()) {
468 : : // There's no use in or after this bb. If this bb is not dominated by
469 : : // the def then it has to be dead on entering this bb.
470 : : // Otherwise, there could be use that we don't track
471 : : // before hitting the next safepoint.
472 [ + + ]: 141953 : if (!DT.dominates(orig, bb)) {
473 : 5180 : insertLifetimeEnd(ptr, sz, &*bb->getFirstInsertionPt());
474 : 5180 : continue;
475 : : }
476 [ + + ]: 136773 : else if (auto insert = getFirstSafepoint(bb)) {
477 : 67463 : insertLifetimeEnd(ptr, sz, insert);
478 : 67463 : continue;
479 : : }
480 : : }
481 : : else {
482 [ + + - + ]: 20218 : assert(bb == def_bb || DT.dominates(orig, I));
483 : 20218 : BasicBlock::iterator it(I);
484 : 20218 : BasicBlock::iterator end = bb->end();
485 : 20218 : bool safepoint_found = false;
486 [ + + ]: 132129 : for (; it != end; ++it) {
487 : 112564 : auto insert = &*it;
488 [ + + ]: 112564 : if (isSafepoint(insert)) {
489 : 653 : insertLifetimeEnd(ptr, sz, insert);
490 : 653 : safepoint_found = true;
491 : 653 : break;
492 : : }
493 : : }
494 [ + + ]: 20218 : if (safepoint_found) {
495 : 653 : continue;
496 : : }
497 : : }
498 [ + + ]: 229536 : for (auto succ: successors(bb)) {
499 : 140661 : first_dead.push_back(&*succ->begin());
500 : : }
501 : : }
502 : 18499 : }
503 : :
504 : 1438 : void Optimizer::replaceIntrinsicUseWith(IntrinsicInst *call, Intrinsic::ID ID,
505 : : Instruction *orig_i, Instruction *new_i)
506 : : {
507 : 1438 : auto nargs = call->arg_size();
508 : 2876 : SmallVector<Value*, 8> args(nargs);
509 : 2876 : SmallVector<Type*, 8> argTys(nargs);
510 [ + + ]: 7190 : for (unsigned i = 0; i < nargs; i++) {
511 : 5752 : auto arg = call->getArgOperand(i);
512 [ + + ]: 5752 : args[i] = arg == orig_i ? new_i : arg;
513 : 5752 : argTys[i] = args[i]->getType();
514 : : }
515 : 1438 : auto oldfType = call->getFunctionType();
516 : 1438 : auto newfType = FunctionType::get(
517 : : oldfType->getReturnType(),
518 : 1438 : makeArrayRef(argTys).slice(0, oldfType->getNumParams()),
519 : 1438 : oldfType->isVarArg());
520 : :
521 : : // Accumulate an array of overloaded types for the given intrinsic
522 : : // and compute the new name mangling schema
523 : 2876 : SmallVector<Type*, 4> overloadTys;
524 : : {
525 : 2876 : SmallVector<Intrinsic::IITDescriptor, 8> Table;
526 : 1438 : getIntrinsicInfoTableEntries(ID, Table);
527 : 1438 : ArrayRef<Intrinsic::IITDescriptor> TableRef = Table;
528 : 1438 : auto res = Intrinsic::matchIntrinsicSignature(newfType, TableRef, overloadTys);
529 [ - + ]: 1438 : assert(res == Intrinsic::MatchIntrinsicTypes_Match);
530 : : (void)res;
531 : 1438 : bool matchvararg = !Intrinsic::matchIntrinsicVarArg(newfType->isVarArg(), TableRef);
532 [ - + ]: 1438 : assert(matchvararg);
533 : : (void)matchvararg;
534 : : }
535 : 1438 : auto newF = Intrinsic::getDeclaration(call->getModule(), ID, overloadTys);
536 [ - + ]: 1438 : assert(newF->getFunctionType() == newfType);
537 : 1438 : newF->setCallingConv(call->getCallingConv());
538 : 1438 : auto newCall = CallInst::Create(newF, args, "", call);
539 : 1438 : newCall->setTailCallKind(call->getTailCallKind());
540 : 1438 : auto old_attrs = call->getAttributes();
541 : 1438 : newCall->setAttributes(AttributeList::get(pass.getLLVMContext(), getFnAttrs(old_attrs),
542 : : getRetAttrs(old_attrs), {}));
543 : 1438 : newCall->setDebugLoc(call->getDebugLoc());
544 : 1438 : call->replaceAllUsesWith(newCall);
545 : 1438 : call->eraseFromParent();
546 : 1438 : }
547 : :
548 : : // This function should not erase any safepoint so that the lifetime marker can find and cache
549 : : // all the original safepoints.
550 : 18445 : void Optimizer::moveToStack(CallInst *orig_inst, size_t sz, bool has_ref)
551 : : {
552 : 18445 : ++RemovedAllocs;
553 : 18445 : ++StackAllocs;
554 : 18445 : auto tag = orig_inst->getArgOperand(2);
555 : 18445 : removed.push_back(orig_inst);
556 : : // The allocation does not escape or get used in a phi node so none of the derived
557 : : // SSA from it are live when we run the allocation again.
558 : : // It is now safe to promote the allocation to an entry block alloca.
559 : 18445 : size_t align = 1;
560 : : // TODO: This is overly conservative. May want to instead pass this as a
561 : : // parameter to the allocation function directly.
562 [ + + ]: 18445 : if (sz > 1)
563 : 15529 : align = MinAlign(JL_SMALL_BYTE_ALIGNMENT, NextPowerOf2(sz));
564 : : // No debug info for prolog instructions
565 : 36890 : IRBuilder<> prolog_builder(&F.getEntryBlock().front());
566 : : AllocaInst *buff;
567 : : Instruction *ptr;
568 [ + + ]: 18445 : if (sz == 0) {
569 : 6 : ptr = buff = prolog_builder.CreateAlloca(Type::getInt8Ty(prolog_builder.getContext()), ConstantInt::get(Type::getInt64Ty(prolog_builder.getContext()), 0));
570 : : }
571 [ - + ]: 18439 : else if (has_ref) {
572 : : // Allocate with the correct type so that the GC frame lowering pass will
573 : : // treat this as a non-mem2reg'd alloca
574 : : // The ccall root and GC preserve handling below makes sure that
575 : : // the alloca isn't optimized out.
576 : 0 : buff = prolog_builder.CreateAlloca(pass.T_prjlvalue);
577 : 0 : buff->setAlignment(Align(align));
578 : 0 : ptr = cast<Instruction>(prolog_builder.CreateBitCast(buff, Type::getInt8PtrTy(prolog_builder.getContext())));
579 : : }
580 : : else {
581 : : Type *buffty;
582 [ + + ]: 18439 : if (pass.DL->isLegalInteger(sz * 8))
583 : 17198 : buffty = Type::getIntNTy(pass.getLLVMContext(), sz * 8);
584 : : else
585 : 1241 : buffty = ArrayType::get(Type::getInt8Ty(pass.getLLVMContext()), sz);
586 : 18439 : buff = prolog_builder.CreateAlloca(buffty);
587 : 18439 : buff->setAlignment(Align(align));
588 : 18439 : ptr = cast<Instruction>(prolog_builder.CreateBitCast(buff, Type::getInt8PtrTy(prolog_builder.getContext())));
589 : : }
590 : 18445 : insertLifetime(ptr, ConstantInt::get(Type::getInt64Ty(prolog_builder.getContext()), sz), orig_inst);
591 : 18445 : auto new_inst = cast<Instruction>(prolog_builder.CreateBitCast(ptr, JuliaType::get_pjlvalue_ty(prolog_builder.getContext())));
592 : 18445 : new_inst->takeName(orig_inst);
593 : :
594 : 81615 : auto simple_replace = [&] (Instruction *orig_i, Instruction *new_i) {
595 [ - + ]: 81615 : if (orig_i->user_empty()) {
596 [ # # ]: 0 : if (orig_i != orig_inst)
597 : 0 : orig_i->eraseFromParent();
598 : 0 : return true;
599 : : }
600 : 81615 : Type *orig_t = orig_i->getType();
601 : 81615 : Type *new_t = new_i->getType();
602 [ - + ]: 81615 : if (orig_t == new_t) {
603 : 0 : orig_i->replaceAllUsesWith(new_i);
604 [ # # ]: 0 : if (orig_i != orig_inst)
605 : 0 : orig_i->eraseFromParent();
606 : 0 : return true;
607 : : }
608 : 81615 : return false;
609 : 18445 : };
610 [ - + ]: 18445 : if (simple_replace(orig_inst, new_inst))
611 : 0 : return;
612 [ - + ]: 18445 : assert(replace_stack.empty());
613 : 18445 : ReplaceUses::Frame cur{orig_inst, new_inst};
614 : 81615 : auto finish_cur = [&] () {
615 [ - + ]: 81615 : assert(cur.orig_i->user_empty());
616 [ + + ]: 81615 : if (cur.orig_i != orig_inst) {
617 : 63170 : cur.orig_i->eraseFromParent();
618 : : }
619 : 100060 : };
620 : 63170 : auto push_frame = [&] (Instruction *orig_i, Instruction *new_i) {
621 [ - + ]: 63170 : if (simple_replace(orig_i, new_i))
622 : 0 : return;
623 : 63170 : replace_stack.push_back(cur);
624 : 63170 : cur = {orig_i, new_i};
625 : 18445 : };
626 : : // Both `orig_i` and `new_i` should be pointer of the same type
627 : : // but possibly different address spaces. `new_i` is always in addrspace 0.
628 : 121166 : auto replace_inst = [&] (Instruction *user) {
629 : 121166 : Instruction *orig_i = cur.orig_i;
630 : 121166 : Instruction *new_i = cur.new_i;
631 [ + + + + : 121166 : if (isa<LoadInst>(user) || isa<StoreInst>(user)) {
+ + ]
632 : 20093 : user->replaceUsesOfWith(orig_i, new_i);
633 : : }
634 [ + + ]: 101073 : else if (auto call = dyn_cast<CallInst>(user)) {
635 : 37903 : auto callee = call->getCalledOperand();
636 [ + + ]: 37903 : if (pass.pointer_from_objref_func == callee) {
637 : 18265 : call->replaceAllUsesWith(new_i);
638 : 18265 : call->eraseFromParent();
639 : 18265 : return;
640 : : }
641 [ - + ]: 19638 : if (pass.typeof_func == callee) {
642 : 0 : ++RemovedTypeofs;
643 : 0 : call->replaceAllUsesWith(tag);
644 : 0 : call->eraseFromParent();
645 : 0 : return;
646 : : }
647 : : // Also remove the preserve intrinsics so that it can be better optimized.
648 [ + + ]: 19638 : if (pass.gc_preserve_begin_func == callee) {
649 [ - + ]: 487 : if (has_ref) {
650 : 0 : call->replaceUsesOfWith(orig_i, buff);
651 : : }
652 : : else {
653 : 487 : removeGCPreserve(call, orig_i);
654 : : }
655 : 487 : return;
656 : : }
657 [ + - ]: 19151 : if (pass.write_barrier_func == callee ||
658 [ - + ]: 19151 : pass.write_barrier_binding_func == callee) {
659 : 0 : ++RemovedWriteBarriers;
660 : 0 : call->eraseFromParent();
661 : 0 : return;
662 : : }
663 [ + + ]: 19151 : if (auto intrinsic = dyn_cast<IntrinsicInst>(call)) {
664 [ + - ]: 1438 : if (Intrinsic::ID ID = intrinsic->getIntrinsicID()) {
665 : 1438 : replaceIntrinsicUseWith(intrinsic, ID, orig_i, new_i);
666 : 1438 : return;
667 : : }
668 : : }
669 : : // remove from operand bundle
670 [ - + ]: 17713 : Value *replace = has_ref ? (Value*)buff : Constant::getNullValue(orig_i->getType());
671 : 17713 : user->replaceUsesOfWith(orig_i, replace);
672 : : }
673 [ + + + + : 63170 : else if (isa<AddrSpaceCastInst>(user) || isa<BitCastInst>(user)) {
+ + ]
674 : 62250 : auto cast_t = PointerType::getWithSamePointeeType(cast<PointerType>(user->getType()), AddressSpace::Generic);
675 : 62250 : auto replace_i = new_i;
676 : 62250 : Type *new_t = new_i->getType();
677 [ + + ]: 62250 : if (cast_t != new_t) {
678 : 23019 : replace_i = new BitCastInst(replace_i, cast_t, "", user);
679 : 23019 : replace_i->setDebugLoc(user->getDebugLoc());
680 : 23019 : replace_i->takeName(user);
681 : : }
682 : 62250 : push_frame(user, replace_i);
683 : : }
684 [ + - ]: 920 : else if (auto gep = dyn_cast<GetElementPtrInst>(user)) {
685 : 1840 : SmallVector<Value *, 4> IdxOperands(gep->idx_begin(), gep->idx_end());
686 : 920 : auto new_gep = GetElementPtrInst::Create(gep->getSourceElementType(),
687 : : new_i, IdxOperands,
688 : 920 : gep->getName(), gep);
689 : 920 : new_gep->setIsInBounds(gep->isInBounds());
690 : 920 : new_gep->takeName(gep);
691 : 920 : new_gep->copyMetadata(*gep);
692 : 920 : push_frame(gep, new_gep);
693 : : }
694 : : else {
695 : 0 : abort();
696 : : }
697 : 18445 : };
698 : :
699 : : while (true) {
700 : 121166 : replace_inst(cast<Instruction>(*cur.orig_i->user_begin()));
701 [ + + ]: 184336 : while (cur.orig_i->use_empty()) {
702 : 81615 : finish_cur();
703 [ + + ]: 81615 : if (replace_stack.empty())
704 : 18445 : return;
705 : 63170 : cur = replace_stack.back();
706 : 63170 : replace_stack.pop_back();
707 : : }
708 : : }
709 : : }
710 : :
711 : : // This function should not erase any safepoint so that the lifetime marker can find and cache
712 : : // all the original safepoints.
713 : 359 : void Optimizer::removeAlloc(CallInst *orig_inst)
714 : : {
715 : 359 : ++RemovedAllocs;
716 : 359 : ++DeletedAllocs;
717 : 359 : auto tag = orig_inst->getArgOperand(2);
718 : 359 : removed.push_back(orig_inst);
719 : 1502 : auto simple_remove = [&] (Instruction *orig_i) {
720 [ + + ]: 1502 : if (orig_i->user_empty()) {
721 [ - + ]: 89 : if (orig_i != orig_inst)
722 : 0 : orig_i->eraseFromParent();
723 : 89 : return true;
724 : : }
725 : 1413 : return false;
726 : 359 : };
727 [ + + ]: 359 : if (simple_remove(orig_inst))
728 : 89 : return;
729 [ - + ]: 270 : assert(replace_stack.empty());
730 : 270 : ReplaceUses::Frame cur{orig_inst, nullptr};
731 : 1413 : auto finish_cur = [&] () {
732 [ - + ]: 1413 : assert(cur.orig_i->user_empty());
733 [ + + ]: 1413 : if (cur.orig_i != orig_inst) {
734 : 1143 : cur.orig_i->eraseFromParent();
735 : : }
736 : 1683 : };
737 : 1143 : auto push_frame = [&] (Instruction *orig_i) {
738 [ - + ]: 1143 : if (simple_remove(orig_i))
739 : 0 : return;
740 : 1143 : replace_stack.push_back(cur);
741 : 1143 : cur = {orig_i, nullptr};
742 : 270 : };
743 : 1851 : auto remove_inst = [&] (Instruction *user) {
744 : 1851 : Instruction *orig_i = cur.orig_i;
745 [ + + ]: 1851 : if (auto store = dyn_cast<StoreInst>(user)) {
746 : : // All stores are known to be dead.
747 : : // The stored value might be an gc pointer in which case deleting the object
748 : : // might open more optimization opportunities.
749 [ + + ]: 703 : if (auto stored_inst = dyn_cast<Instruction>(store->getValueOperand()))
750 : 556 : pushInstruction(stored_inst);
751 : 703 : user->eraseFromParent();
752 : 703 : return;
753 : : }
754 [ + + ]: 1148 : else if (auto call = dyn_cast<CallInst>(user)) {
755 : 5 : auto callee = call->getCalledOperand();
756 [ - + ]: 5 : if (pass.gc_preserve_begin_func == callee) {
757 : 0 : removeGCPreserve(call, orig_i);
758 : 0 : return;
759 : : }
760 [ + - ]: 5 : if (pass.typeof_func == callee) {
761 : 5 : ++RemovedTypeofs;
762 : 5 : call->replaceAllUsesWith(tag);
763 : 5 : call->eraseFromParent();
764 : 5 : return;
765 : : }
766 [ # # ]: 0 : if (pass.write_barrier_func == callee ||
767 [ # # ]: 0 : pass.write_barrier_binding_func == callee) {
768 : 0 : ++RemovedWriteBarriers;
769 : 0 : call->eraseFromParent();
770 : 0 : return;
771 : : }
772 [ # # ]: 0 : if (auto II = dyn_cast<IntrinsicInst>(call)) {
773 : 0 : auto id = II->getIntrinsicID();
774 [ # # # # ]: 0 : if (id == Intrinsic::memset || id == Intrinsic::lifetime_start ||
775 [ # # # # : 0 : id == Intrinsic::lifetime_end || isa<DbgInfoIntrinsic>(II)) {
# # ]
776 : 0 : call->eraseFromParent();
777 : 0 : return;
778 : : }
779 : : }
780 : : // remove from operand bundle
781 : 0 : user->replaceUsesOfWith(orig_i, Constant::getNullValue(orig_i->getType()));
782 : : }
783 [ + + + + : 1522 : else if (isa<AddrSpaceCastInst>(user) || isa<BitCastInst>(user) ||
+ - + - ]
784 : 379 : isa<GetElementPtrInst>(user)) {
785 : 1143 : push_frame(user);
786 : : }
787 : : else {
788 : 0 : abort();
789 : : }
790 : 270 : };
791 : :
792 : : while (true) {
793 : 1851 : remove_inst(cast<Instruction>(*cur.orig_i->user_begin()));
794 [ + + ]: 2994 : while (cur.orig_i->use_empty()) {
795 : 1413 : finish_cur();
796 [ + + ]: 1413 : if (replace_stack.empty())
797 : 270 : return;
798 : 1143 : cur = replace_stack.back();
799 : 1143 : replace_stack.pop_back();
800 : : }
801 : : }
802 : : }
803 : :
804 : : // Unable to optimize out the allocation, do store to load forwarding on the tag instead.
805 : 280 : void Optimizer::optimizeTag(CallInst *orig_inst)
806 : : {
807 : 280 : auto tag = orig_inst->getArgOperand(2);
808 : : // `julia.typeof` is only legal on the original pointer, no need to scan recursively
809 : 280 : size_t last_deleted = removed.size();
810 [ + + ]: 1575 : for (auto user: orig_inst->users()) {
811 [ + + ]: 1295 : if (auto call = dyn_cast<CallInst>(user)) {
812 : 456 : auto callee = call->getCalledOperand();
813 [ + + ]: 456 : if (pass.typeof_func == callee) {
814 : 302 : ++RemovedTypeofs;
815 : 302 : call->replaceAllUsesWith(tag);
816 : : // Push to the removed instructions to trigger `finalize` to
817 : : // return the correct result.
818 : : // Also so that we don't have to worry about iterator invalidation...
819 : 302 : removed.push_back(call);
820 : : }
821 : : }
822 : : }
823 [ + + ]: 582 : while (last_deleted < removed.size())
824 : 302 : removed[last_deleted++]->replaceUsesOfWith(orig_inst, UndefValue::get(orig_inst->getType()));
825 : 280 : }
826 : :
827 : 54 : void Optimizer::splitOnStack(CallInst *orig_inst)
828 : : {
829 : 54 : auto tag = orig_inst->getArgOperand(2);
830 : 54 : ++RemovedAllocs;
831 : 54 : ++SplitAllocs;
832 : 54 : removed.push_back(orig_inst);
833 : 54 : IRBuilder<> prolog_builder(&F.getEntryBlock().front());
834 : : struct SplitSlot {
835 : : AllocaInst *slot;
836 : : bool isref;
837 : : uint32_t offset;
838 : : uint32_t size;
839 : : };
840 : 54 : SmallVector<SplitSlot,8> slots;
841 [ + + ]: 108 : for (auto memop: use_info.memops) {
842 : 54 : auto offset = memop.first;
843 : 54 : auto &field = memop.second;
844 : : // If the field has no reader and is not a object reference field that we
845 : : // need to preserve at some point, there's no need to allocate the field.
846 [ - + - - : 54 : if (!field.hasload && (!field.hasobjref || !use_info.haspreserve))
- - ]
847 : 0 : continue;
848 : 54 : SplitSlot slot{nullptr, field.hasobjref, offset, field.size};
849 : : Type *allocty;
850 [ - + ]: 54 : if (field.hasobjref) {
851 : 0 : allocty = pass.T_prjlvalue;
852 : : }
853 [ + + + - ]: 54 : else if (field.elty && !field.multiloc) {
854 : 53 : allocty = field.elty;
855 : : }
856 [ - + ]: 1 : else if (pass.DL->isLegalInteger(field.size * 8)) {
857 : 0 : allocty = Type::getIntNTy(pass.getLLVMContext(), field.size * 8);
858 : : } else {
859 : 1 : allocty = ArrayType::get(Type::getInt8Ty(pass.getLLVMContext()), field.size);
860 : : }
861 : 54 : slot.slot = prolog_builder.CreateAlloca(allocty);
862 : 54 : insertLifetime(prolog_builder.CreateBitCast(slot.slot, Type::getInt8PtrTy(prolog_builder.getContext())),
863 : 54 : ConstantInt::get(Type::getInt64Ty(prolog_builder.getContext()), field.size), orig_inst);
864 : 54 : slots.push_back(std::move(slot));
865 : : }
866 : 54 : const auto nslots = slots.size();
867 : 108 : auto find_slot = [&] (uint32_t offset) {
868 [ + + ]: 108 : if (offset == 0)
869 : 107 : return 0u;
870 : 1 : unsigned lb = 0;
871 : 1 : unsigned ub = slots.size();
872 [ - + ]: 1 : while (lb + 1 < ub) {
873 : 0 : unsigned mid = (lb + ub) / 2;
874 [ # # ]: 0 : if (slots[mid].offset <= offset) {
875 : 0 : lb = mid;
876 : : }
877 : : else {
878 : 0 : ub = mid;
879 : : }
880 : : }
881 : 1 : return lb;
882 : 54 : };
883 : 123 : auto simple_replace = [&] (Instruction *orig_i) {
884 [ - + ]: 123 : if (orig_i->user_empty()) {
885 [ # # ]: 0 : if (orig_i != orig_inst)
886 : 0 : orig_i->eraseFromParent();
887 : 0 : return true;
888 : : }
889 : 123 : return false;
890 : 54 : };
891 [ - + ]: 54 : if (simple_replace(orig_inst))
892 : 0 : return;
893 [ - + ]: 54 : assert(replace_stack.empty());
894 : 54 : ReplaceUses::Frame cur{orig_inst, uint32_t(0)};
895 : 123 : auto finish_cur = [&] () {
896 [ - + ]: 123 : assert(cur.orig_i->user_empty());
897 [ + + ]: 123 : if (cur.orig_i != orig_inst) {
898 : 69 : cur.orig_i->eraseFromParent();
899 : : }
900 : 177 : };
901 : 69 : auto push_frame = [&] (Instruction *orig_i, uint32_t offset) {
902 [ - + ]: 69 : if (simple_replace(orig_i))
903 : 0 : return;
904 : 69 : replace_stack.push_back(cur);
905 : 69 : cur = {orig_i, offset};
906 : 54 : };
907 : 108 : auto slot_gep = [&] (SplitSlot &slot, uint32_t offset, Type *elty, IRBuilder<> &builder) {
908 [ - + ]: 108 : assert(slot.offset <= offset);
909 : 108 : offset -= slot.offset;
910 : 108 : auto size = pass.DL->getTypeAllocSize(elty);
911 : : Value *addr;
912 [ + - ]: 108 : if (offset % size == 0) {
913 : 108 : addr = builder.CreateBitCast(slot.slot, elty->getPointerTo());
914 [ + + ]: 108 : if (offset != 0) {
915 : 1 : addr = builder.CreateConstInBoundsGEP1_32(elty, addr, offset / size);
916 : : }
917 : : }
918 : : else {
919 : 0 : addr = builder.CreateBitCast(slot.slot, Type::getInt8PtrTy(builder.getContext()));
920 : 0 : addr = builder.CreateConstInBoundsGEP1_32(Type::getInt8Ty(builder.getContext()), addr, offset);
921 : 0 : addr = builder.CreateBitCast(addr, elty->getPointerTo());
922 : : }
923 : 108 : return addr;
924 : 54 : };
925 : 177 : auto replace_inst = [&] (Use *use) {
926 : 177 : Instruction *user = cast<Instruction>(use->getUser());
927 : 177 : Instruction *orig_i = cur.orig_i;
928 : 177 : uint32_t offset = cur.offset;
929 [ + + ]: 177 : if (auto load = dyn_cast<LoadInst>(user)) {
930 : 54 : auto slot_idx = find_slot(offset);
931 : 54 : auto &slot = slots[slot_idx];
932 [ + - + - ]: 54 : assert(slot.offset <= offset && slot.offset + slot.size >= offset);
933 : 54 : IRBuilder<> builder(load);
934 : : Value *val;
935 : 54 : Type *load_ty = load->getType();
936 : : LoadInst *newload;
937 [ - + ]: 54 : if (slot.isref) {
938 [ # # ]: 0 : assert(slot.offset == offset);
939 : 0 : newload = builder.CreateLoad(pass.T_prjlvalue, slot.slot);
940 : : // Assume the addrspace is correct.
941 : 0 : val = builder.CreateBitCast(newload, load_ty);
942 : : }
943 : : else {
944 : 54 : newload = builder.CreateLoad(load_ty, slot_gep(slot, offset, load_ty, builder));
945 : 54 : val = newload;
946 : : }
947 : : // TODO: should we use `load->clone()`, or manually copy any other metadata?
948 : 54 : newload->setAlignment(load->getAlign());
949 : : // since we're moving heap-to-stack, it is safe to downgrade the atomic level to NotAtomic
950 : 54 : newload->setOrdering(AtomicOrdering::NotAtomic);
951 : 54 : load->replaceAllUsesWith(val);
952 : 54 : load->eraseFromParent();
953 : 54 : return;
954 : : }
955 [ + + ]: 123 : else if (auto store = dyn_cast<StoreInst>(user)) {
956 [ + + ]: 54 : if (auto stored_inst = dyn_cast<Instruction>(store->getValueOperand()))
957 : 9 : pushInstruction(stored_inst);
958 : 54 : auto slot_idx = find_slot(offset);
959 : 54 : auto &slot = slots[slot_idx];
960 [ + - - + ]: 54 : if (slot.offset > offset || slot.offset + slot.size <= offset) {
961 : 0 : store->eraseFromParent();
962 : 0 : return;
963 : : }
964 : 54 : IRBuilder<> builder(store);
965 : 54 : auto store_val = store->getValueOperand();
966 : 54 : auto store_ty = store_val->getType();
967 : : StoreInst *newstore;
968 [ - + ]: 54 : if (slot.isref) {
969 [ # # ]: 0 : assert(slot.offset == offset);
970 : 0 : auto T_pjlvalue = JuliaType::get_pjlvalue_ty(builder.getContext());
971 [ # # ]: 0 : if (!isa<PointerType>(store_ty)) {
972 : 0 : store_val = builder.CreateBitCast(store_val, getSizeTy(builder.getContext()));
973 : 0 : store_val = builder.CreateIntToPtr(store_val, T_pjlvalue);
974 : 0 : store_ty = T_pjlvalue;
975 : : }
976 : : else {
977 : 0 : store_ty = PointerType::getWithSamePointeeType(T_pjlvalue, cast<PointerType>(store_ty)->getAddressSpace());
978 : 0 : store_val = builder.CreateBitCast(store_val, store_ty);
979 : : }
980 [ # # ]: 0 : if (cast<PointerType>(store_ty)->getAddressSpace() != AddressSpace::Tracked)
981 : 0 : store_val = builder.CreateAddrSpaceCast(store_val, pass.T_prjlvalue);
982 : 0 : newstore = builder.CreateStore(store_val, slot.slot);
983 : : }
984 : : else {
985 : 54 : newstore = builder.CreateStore(store_val, slot_gep(slot, offset, store_ty, builder));
986 : : }
987 : : // TODO: should we use `store->clone()`, or manually copy any other metadata?
988 : 54 : newstore->setAlignment(store->getAlign());
989 : : // since we're moving heap-to-stack, it is safe to downgrade the atomic level to NotAtomic
990 : 54 : newstore->setOrdering(AtomicOrdering::NotAtomic);
991 : 54 : store->eraseFromParent();
992 : 54 : return;
993 : : }
994 [ + - - + : 69 : else if (isa<AtomicCmpXchgInst>(user) || isa<AtomicRMWInst>(user)) {
- + ]
995 : 0 : auto slot_idx = find_slot(offset);
996 : 0 : auto &slot = slots[slot_idx];
997 [ # # # # ]: 0 : assert(slot.offset <= offset && slot.offset + slot.size >= offset);
998 : 0 : IRBuilder<> builder(user);
999 : : Value *newptr;
1000 [ # # ]: 0 : if (slot.isref) {
1001 [ # # ]: 0 : assert(slot.offset == offset);
1002 : 0 : newptr = slot.slot;
1003 : : }
1004 : : else {
1005 [ # # ]: 0 : Value *Val = isa<AtomicCmpXchgInst>(user) ? cast<AtomicCmpXchgInst>(user)->getNewValOperand() : cast<AtomicRMWInst>(user)->getValOperand();
1006 : 0 : newptr = slot_gep(slot, offset, Val->getType(), builder);
1007 : : }
1008 : 0 : *use = newptr;
1009 : : }
1010 [ - + ]: 69 : else if (auto call = dyn_cast<CallInst>(user)) {
1011 : 0 : auto callee = call->getCalledOperand();
1012 [ # # ]: 0 : assert(callee); // makes it clear for clang analyser that `callee` is not NULL
1013 [ # # ]: 0 : if (auto intrinsic = dyn_cast<IntrinsicInst>(call)) {
1014 [ # # ]: 0 : if (Intrinsic::ID id = intrinsic->getIntrinsicID()) {
1015 [ # # ]: 0 : if (id == Intrinsic::memset) {
1016 : 0 : IRBuilder<> builder(call);
1017 : 0 : auto val_arg = cast<ConstantInt>(call->getArgOperand(1));
1018 : 0 : auto size_arg = cast<ConstantInt>(call->getArgOperand(2));
1019 : 0 : uint8_t val = val_arg->getLimitedValue();
1020 : 0 : uint32_t size = size_arg->getLimitedValue();
1021 [ # # ]: 0 : for (unsigned idx = find_slot(offset); idx < nslots; idx++) {
1022 : 0 : auto &slot = slots[idx];
1023 [ # # # # ]: 0 : if (slot.offset + slot.size <= offset || slot.offset >= offset + size)
1024 : : break;
1025 [ # # ]: 0 : if (slot.isref) {
1026 [ # # # # ]: 0 : assert(slot.offset >= offset &&
1027 : : slot.offset + slot.size <= offset + size);
1028 : : Constant *ptr;
1029 [ # # ]: 0 : if (val == 0) {
1030 : 0 : ptr = Constant::getNullValue(pass.T_prjlvalue);
1031 : : }
1032 : : else {
1033 : : uint64_t intval;
1034 : 0 : memset(&intval, val, 8);
1035 : 0 : Constant *val = ConstantInt::get(getSizeTy(builder.getContext()), intval);
1036 : 0 : val = ConstantExpr::getIntToPtr(val, JuliaType::get_pjlvalue_ty(builder.getContext()));
1037 : 0 : ptr = ConstantExpr::getAddrSpaceCast(val, pass.T_prjlvalue);
1038 : : }
1039 : 0 : StoreInst *store = builder.CreateAlignedStore(ptr, slot.slot, Align(sizeof(void*)));
1040 : 0 : store->setOrdering(AtomicOrdering::NotAtomic);
1041 : 0 : continue;
1042 : : }
1043 : 0 : auto ptr8 = builder.CreateBitCast(slot.slot, Type::getInt8PtrTy(builder.getContext()));
1044 [ # # ]: 0 : if (offset > slot.offset)
1045 : 0 : ptr8 = builder.CreateConstInBoundsGEP1_32(Type::getInt8Ty(builder.getContext()), ptr8,
1046 : 0 : offset - slot.offset);
1047 : 0 : auto sub_size = std::min(slot.offset + slot.size, offset + size) -
1048 : 0 : std::max(offset, slot.offset);
1049 : : // TODO: alignment computation
1050 : 0 : builder.CreateMemSet(ptr8, val_arg, sub_size, MaybeAlign(0));
1051 : : }
1052 : 0 : call->eraseFromParent();
1053 : 0 : return;
1054 : : }
1055 : 0 : call->eraseFromParent();
1056 : 0 : return;
1057 : : }
1058 : : }
1059 [ # # ]: 0 : if (pass.typeof_func == callee) {
1060 : 0 : ++RemovedTypeofs;
1061 : 0 : call->replaceAllUsesWith(tag);
1062 : 0 : call->eraseFromParent();
1063 : 0 : return;
1064 : : }
1065 [ # # ]: 0 : if (pass.write_barrier_func == callee ||
1066 [ # # ]: 0 : pass.write_barrier_binding_func == callee) {
1067 : 0 : ++RemovedWriteBarriers;
1068 : 0 : call->eraseFromParent();
1069 : 0 : return;
1070 : : }
1071 [ # # ]: 0 : if (pass.gc_preserve_begin_func == callee) {
1072 : 0 : SmallVector<Value*,8> operands;
1073 [ # # ]: 0 : for (auto &arg: call->args()) {
1074 [ # # # # : 0 : if (arg.get() == orig_i || isa<Constant>(arg.get()))
# # ]
1075 : 0 : continue;
1076 : 0 : operands.push_back(arg.get());
1077 : : }
1078 : 0 : IRBuilder<> builder(call);
1079 [ # # ]: 0 : for (auto &slot: slots) {
1080 [ # # ]: 0 : if (!slot.isref)
1081 : 0 : continue;
1082 : 0 : LoadInst *ref = builder.CreateAlignedLoad(pass.T_prjlvalue, slot.slot, Align(sizeof(void*)));
1083 : : // since we're moving heap-to-stack, it is safe to downgrade the atomic level to NotAtomic
1084 : 0 : ref->setOrdering(AtomicOrdering::NotAtomic);
1085 : 0 : operands.push_back(ref);
1086 : : }
1087 : 0 : auto new_call = builder.CreateCall(pass.gc_preserve_begin_func, operands);
1088 : 0 : new_call->takeName(call);
1089 : 0 : new_call->setAttributes(call->getAttributes());
1090 : 0 : call->replaceAllUsesWith(new_call);
1091 : 0 : call->eraseFromParent();
1092 : 0 : return;
1093 : : }
1094 : : // remove from operand bundle
1095 [ # # ]: 0 : assert(call->isBundleOperand(use->getOperandNo()));
1096 [ # # ]: 0 : assert(call->getOperandBundleForOperand(use->getOperandNo()).getTagName() ==
1097 : : "jl_roots");
1098 : 0 : SmallVector<OperandBundleDef,2> bundles;
1099 : 0 : call->getOperandBundlesAsDefs(bundles);
1100 [ # # ]: 0 : for (auto &bundle: bundles) {
1101 [ # # ]: 0 : if (bundle.getTag() != "jl_roots")
1102 : 0 : continue;
1103 : 0 : std::vector<Value*> operands;
1104 [ # # ]: 0 : for (auto op: bundle.inputs()) {
1105 [ # # # # : 0 : if (op == orig_i || isa<Constant>(op))
# # ]
1106 : 0 : continue;
1107 : 0 : operands.push_back(op);
1108 : : }
1109 : 0 : IRBuilder<> builder(call);
1110 [ # # ]: 0 : for (auto &slot: slots) {
1111 [ # # ]: 0 : if (!slot.isref)
1112 : 0 : continue;
1113 : 0 : LoadInst *ref = builder.CreateAlignedLoad(pass.T_prjlvalue, slot.slot, Align(sizeof(void*)));
1114 : : // since we're moving heap-to-stack, it is safe to downgrade the atomic level to NotAtomic
1115 : 0 : ref->setOrdering(AtomicOrdering::NotAtomic);
1116 : 0 : operands.push_back(ref);
1117 : : }
1118 : 0 : bundle = OperandBundleDef("jl_roots", std::move(operands));
1119 : 0 : break;
1120 : : }
1121 : 0 : auto new_call = CallInst::Create(call, bundles, call);
1122 : 0 : new_call->takeName(call);
1123 : 0 : call->replaceAllUsesWith(new_call);
1124 : 0 : call->eraseFromParent();
1125 : 0 : return;
1126 : : }
1127 [ + + + + : 69 : else if (isa<AddrSpaceCastInst>(user) || isa<BitCastInst>(user)) {
+ + ]
1128 : 68 : push_frame(user, offset);
1129 : : }
1130 [ + - ]: 1 : else if (auto gep = dyn_cast<GetElementPtrInst>(user)) {
1131 : 2 : APInt apoffset(sizeof(void*) * 8, offset, true);
1132 : 1 : gep->accumulateConstantOffset(*pass.DL, apoffset);
1133 : 1 : push_frame(gep, apoffset.getLimitedValue());
1134 : : }
1135 : : else {
1136 : 0 : abort();
1137 : : }
1138 : 54 : };
1139 : :
1140 : : while (true) {
1141 : 177 : replace_inst(&*cur.orig_i->use_begin());
1142 [ + + ]: 246 : while (cur.orig_i->use_empty()) {
1143 : 123 : finish_cur();
1144 [ + + ]: 123 : if (replace_stack.empty())
1145 : 54 : goto cleanup;
1146 : 69 : cur = replace_stack.back();
1147 : 69 : replace_stack.pop_back();
1148 : : }
1149 : : }
1150 : 54 : cleanup:
1151 [ + + ]: 108 : for (auto &slot: slots) {
1152 [ + - ]: 54 : if (!slot.isref)
1153 : 54 : continue;
1154 : 0 : PromoteMemToReg({slot.slot}, getDomTree());
1155 : : }
1156 : : }
1157 : :
1158 : 1239060 : bool AllocOpt::doInitialization(Module &M)
1159 : : {
1160 : 1239060 : initAll(M);
1161 [ + + ]: 1239060 : if (!alloc_obj_func)
1162 : 597576 : return false;
1163 : :
1164 : 641488 : DL = &M.getDataLayout();
1165 : :
1166 : 641488 : lifetime_start = Intrinsic::getDeclaration(&M, Intrinsic::lifetime_start, { Type::getInt8PtrTy(M.getContext()) });
1167 : 641488 : lifetime_end = Intrinsic::getDeclaration(&M, Intrinsic::lifetime_end, { Type::getInt8PtrTy(M.getContext()) });
1168 : :
1169 : 641488 : return true;
1170 : : }
1171 : :
1172 : 2453640 : bool AllocOpt::runOnFunction(Function &F, function_ref<DominatorTree&()> GetDT)
1173 : : {
1174 [ + + ]: 2453640 : if (!alloc_obj_func)
1175 : 1159390 : return false;
1176 : 1294250 : Optimizer optimizer(F, *this, std::move(GetDT));
1177 : 1294250 : optimizer.initialize();
1178 : 1294250 : optimizer.optimizeAll();
1179 : 1294250 : bool modified = optimizer.finalize();
1180 [ - + ]: 1294250 : assert(!verifyFunction(F, &errs()));
1181 : 1294250 : return modified;
1182 : : }
1183 : :
1184 : : struct AllocOptLegacy : public FunctionPass {
1185 : : static char ID;
1186 : : AllocOpt opt;
1187 : 2296 : AllocOptLegacy() : FunctionPass(ID) {
1188 : 2296 : llvm::initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
1189 : 2296 : }
1190 : 1239060 : bool doInitialization(Module &m) override {
1191 : 1239060 : return opt.doInitialization(m);
1192 : : }
1193 : 2453640 : bool runOnFunction(Function &F) override {
1194 : 2458110 : return opt.runOnFunction(F, [this]() -> DominatorTree & {return getAnalysis<DominatorTreeWrapperPass>().getDomTree();});
1195 : : }
1196 : 2296 : void getAnalysisUsage(AnalysisUsage &AU) const override
1197 : : {
1198 : 2296 : FunctionPass::getAnalysisUsage(AU);
1199 : 2296 : AU.addRequired<DominatorTreeWrapperPass>();
1200 : 2296 : AU.addPreserved<DominatorTreeWrapperPass>();
1201 : 2296 : AU.setPreservesCFG();
1202 : 2296 : }
1203 : : };
1204 : :
1205 : : char AllocOptLegacy::ID = 0;
1206 : : static RegisterPass<AllocOptLegacy> X("AllocOpt", "Promote heap allocation to stack",
1207 : : false /* Only looks at CFG */,
1208 : : false /* Analysis Pass */);
1209 : :
1210 : : }
1211 : :
1212 : 2296 : Pass *createAllocOptPass()
1213 : : {
1214 : 2296 : return new AllocOptLegacy();
1215 : : }
1216 : :
1217 : 0 : PreservedAnalyses AllocOptPass::run(Function &F, FunctionAnalysisManager &AM) {
1218 : 0 : AllocOpt opt;
1219 : 0 : bool modified = opt.doInitialization(*F.getParent());
1220 [ # # ]: 0 : if (opt.runOnFunction(F, [&]()->DominatorTree &{ return AM.getResult<DominatorTreeAnalysis>(F); })) {
1221 : 0 : modified = true;
1222 : : }
1223 [ # # ]: 0 : if (modified) {
1224 : 0 : auto preserved = PreservedAnalyses::allInSet<CFGAnalyses>();
1225 : 0 : preserved.preserve<DominatorTreeAnalysis>();
1226 : 0 : return preserved;
1227 : : } else {
1228 : 0 : return PreservedAnalyses::all();
1229 : : }
1230 : : }
1231 : :
1232 : 0 : extern "C" JL_DLLEXPORT void LLVMExtraAddAllocOptPass_impl(LLVMPassManagerRef PM)
1233 : : {
1234 : 0 : unwrap(PM)->add(createAllocOptPass());
1235 : 0 : }
|
