Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : #include "llvm-version.h"
4 : : #include "llvm-alloc-helpers.h"
5 : : #include "codegen_shared.h"
6 : : #include "julia_assert.h"
7 : :
8 : : #include <llvm/IR/IntrinsicInst.h>
9 : :
10 : : using namespace llvm;
11 : : using namespace jl_alloc;
12 : :
13 : 1362400 : static bool hasObjref(Type *ty)
14 : : {
15 [ + + ]: 1362400 : if (auto ptrty = dyn_cast<PointerType>(ty))
16 : 644588 : return ptrty->getAddressSpace() == AddressSpace::Tracked;
17 [ + + + + : 717816 : if (isa<ArrayType>(ty) || isa<VectorType>(ty))
+ + ]
18 : 60362 : return hasObjref(GetElementPtrInst::getTypeAtIndex(ty, (uint64_t)0));
19 [ + + ]: 657454 : if (auto structty = dyn_cast<StructType>(ty)) {
20 [ + + ]: 15212 : for (auto elty: structty->elements()) {
21 [ + + ]: 14283 : if (hasObjref(elty)) {
22 : 9405 : return true;
23 : : }
24 : : }
25 : : }
26 : 648049 : return false;
27 : : }
28 : :
29 : : std::pair<const uint32_t,Field>&
30 : 1287760 : AllocUseInfo::getField(uint32_t offset, uint32_t size, Type *elty)
31 : : {
32 : 1287760 : auto it = findLowerField(offset);
33 : 1287760 : auto end = memops.end();
34 : 1287760 : auto lb = end; // first overlap
35 : 1287760 : auto ub = end; // last overlap
36 [ + + ]: 1287760 : if (it != end) {
37 : : // The slot found contains the current location
38 [ + + ]: 368475 : if (it->first + it->second.size >= offset + size) {
39 [ + + ]: 156733 : if (it->second.elty != elty)
40 : 54095 : it->second.elty = nullptr;
41 : : assert(it->second.elty == nullptr || (it->first == offset && it->second.size == size));
42 : 156733 : return *it;
43 : : }
44 [ + + ]: 211742 : if (it->first + it->second.size > offset) {
45 : 2 : lb = it;
46 : 2 : ub = it;
47 : : }
48 : : }
49 : : else {
50 : 919284 : it = memops.begin();
51 : : }
52 : : // Now find the last slot that overlaps with the current memory location.
53 : : // Also set `lb` if we didn't find any above.
54 [ + + + + : 1342770 : for (; it != end && it->first < offset + size; ++it) {
+ + ]
55 [ + + ]: 211746 : if (lb == end)
56 : 211740 : lb = it;
57 : 211746 : ub = it;
58 : : }
59 : : // no overlap found just create a new one.
60 [ + + ]: 1131030 : if (lb == end)
61 : 919284 : return *memops.emplace(offset, Field(size, elty)).first;
62 : : // We find overlapping but not containing slot we need to merge slot/create new one
63 : 211742 : uint32_t new_offset = std::min(offset, lb->first);
64 : 211742 : uint32_t new_addrub = std::max(offset + uint32_t(size), ub->first + ub->second.size);
65 : 211742 : uint32_t new_size = new_addrub - new_offset;
66 : 211742 : Field field(new_size, nullptr);
67 : 211742 : field.multiloc = true;
68 : 211742 : ++ub;
69 [ + + ]: 423488 : for (it = lb; it != ub; ++it) {
70 : 211746 : field.hasobjref |= it->second.hasobjref;
71 : 211746 : field.hasload |= it->second.hasload;
72 : 211746 : field.hasaggr |= it->second.hasaggr;
73 : 211746 : field.accesses.append(it->second.accesses.begin(), it->second.accesses.end());
74 : : }
75 : 211742 : memops.erase(lb, ub);
76 : 211742 : return *memops.emplace(new_offset, std::move(field)).first;
77 : : }
78 : :
79 : 1287760 : bool AllocUseInfo::addMemOp(Instruction *inst, unsigned opno, uint32_t offset,
80 : : Type *elty, bool isstore, const DataLayout &DL)
81 : : {
82 : 1287760 : MemOp memop(inst, opno);
83 : 1287760 : memop.offset = offset;
84 : 1287760 : uint64_t size = DL.getTypeStoreSize(elty);
85 : 1287760 : memop.size = size;
86 [ + + + + : 1287760 : memop.isaggr = isa<StructType>(elty) || isa<ArrayType>(elty) || isa<VectorType>(elty);
+ + ]
87 : 1287760 : memop.isobjref = hasObjref(elty);
88 : 1287760 : auto &field = getField(offset, size, elty);
89 [ + + ]: 1287760 : if (field.second.hasobjref != memop.isobjref)
90 : 555409 : field.second.multiloc = true; // can't split this field, since it contains a mix of references and bits
91 [ + + ]: 1287760 : if (!isstore)
92 : 49484 : field.second.hasload = true;
93 [ + + ]: 1287760 : if (memop.isobjref) {
94 [ + + ]: 644583 : if (isstore) {
95 : 625056 : refstore = true;
96 : : }
97 : : else {
98 : 19527 : refload = true;
99 : : }
100 [ + + ]: 644583 : if (memop.isaggr)
101 : 66817 : field.second.hasaggr = true;
102 : 644583 : field.second.hasobjref = true;
103 : : }
104 [ + + ]: 643176 : else if (memop.isaggr) {
105 : 2152 : field.second.hasaggr = true;
106 : : }
107 : 1287760 : field.second.accesses.push_back(memop);
108 [ - + ]: 1287760 : if (size >= UINT32_MAX - offset)
109 : 0 : return false;
110 : 1287760 : return true;
111 : : }
112 : :
113 : 0 : JL_USED_FUNC void AllocUseInfo::dump()
114 : : {
115 : 0 : jl_safe_printf("escaped: %d\n", escaped);
116 : 0 : jl_safe_printf("addrescaped: %d\n", addrescaped);
117 : 0 : jl_safe_printf("returned: %d\n", returned);
118 : 0 : jl_safe_printf("haserror: %d\n", haserror);
119 : 0 : jl_safe_printf("hasload: %d\n", hasload);
120 : 0 : jl_safe_printf("haspreserve: %d\n", haspreserve);
121 : 0 : jl_safe_printf("hasunknownmem: %d\n", hasunknownmem);
122 : 0 : jl_safe_printf("hastypeof: %d\n", hastypeof);
123 : 0 : jl_safe_printf("refload: %d\n", refload);
124 : 0 : jl_safe_printf("refstore: %d\n", refstore);
125 : 0 : jl_safe_printf("Uses: %d\n", (unsigned)uses.size());
126 [ # # ]: 0 : for (auto inst: uses)
127 : 0 : llvm_dump(inst);
128 [ # # ]: 0 : if (!preserves.empty()) {
129 : 0 : jl_safe_printf("Preserves: %d\n", (unsigned)preserves.size());
130 [ # # ]: 0 : for (auto inst: preserves) {
131 : 0 : llvm_dump(inst);
132 : : }
133 : : }
134 [ # # ]: 0 : if (!memops.empty()) {
135 : 0 : jl_safe_printf("Memops: %d\n", (unsigned)memops.size());
136 [ # # ]: 0 : for (auto &field: memops) {
137 : 0 : jl_safe_printf(" Field %d @ %d\n", field.second.size, field.first);
138 : 0 : jl_safe_printf(" Accesses:\n");
139 [ # # ]: 0 : for (auto memop: field.second.accesses) {
140 : 0 : jl_safe_printf(" ");
141 : 0 : llvm_dump(memop.inst);
142 : : }
143 : : }
144 : : }
145 : 0 : }
146 : :
147 : 1641070 : void jl_alloc::runEscapeAnalysis(llvm::Instruction *I, EscapeAnalysisRequiredArgs required, EscapeAnalysisOptionalArgs options) {
148 : 1641070 : required.use_info.reset();
149 [ + + ]: 1641070 : if (I->use_empty())
150 : 89 : return;
151 : 1640980 : CheckInst::Frame cur{I, 0, I->use_begin(), I->use_end()};
152 : 1640980 : required.check_stack.clear();
153 : :
154 : : // Recursion
155 : 2556310 : auto push_inst = [&] (Instruction *inst) {
156 [ + + ]: 2556310 : if (cur.use_it != cur.use_end)
157 : 1137570 : required.check_stack.push_back(cur);
158 : 2556310 : cur.parent = inst;
159 : 2556310 : cur.use_it = inst->use_begin();
160 : 2556310 : cur.use_end = inst->use_end();
161 : 4197290 : };
162 : :
163 : 5887120 : auto check_inst = [&] (Instruction *inst, Use *use) {
164 [ + + ]: 5887120 : if (isa<LoadInst>(inst)) {
165 : 7735600 : required.use_info.hasload = true;
166 [ + - - + : 49484 : if (cur.offset == UINT32_MAX || !required.use_info.addMemOp(inst, 0, cur.offset,
- + ]
167 : : inst->getType(),
168 : : false, required.DL))
169 : 0 : required.use_info.hasunknownmem = true;
170 : 49484 : return true;
171 : : }
172 [ + + ]: 5837630 : if (auto call = dyn_cast<CallInst>(inst)) {
173 : : // TODO handle `memcmp`
174 : : // None of the intrinsics should care if the memory is stack or heap allocated.
175 : 1329060 : auto callee = call->getCalledOperand();
176 [ + + ]: 1329060 : if (auto II = dyn_cast<IntrinsicInst>(call)) {
177 [ + + ]: 315650 : if (auto id = II->getIntrinsicID()) {
178 [ + + ]: 315122 : if (id == Intrinsic::memset) {
179 : : assert(call->arg_size() == 4);
180 : 3906 : if (cur.offset == UINT32_MAX ||
181 [ + - ]: 1302 : !isa<ConstantInt>(call->getArgOperand(2)) ||
182 [ + - + - : 3906 : !isa<ConstantInt>(call->getArgOperand(1)) ||
- + ]
183 : 1302 : (cast<ConstantInt>(call->getArgOperand(2))->getLimitedValue() >=
184 [ - + ]: 1302 : UINT32_MAX - cur.offset))
185 : 0 : required.use_info.hasunknownmem = true;
186 : 315650 : return true;
187 : : }
188 [ + - + - : 627640 : if (id == Intrinsic::lifetime_start || id == Intrinsic::lifetime_end ||
- + - + ]
189 : 313820 : isa<DbgInfoIntrinsic>(II))
190 : 0 : return true;
191 : 313820 : required.use_info.addrescaped = true;
192 : 313820 : return true;
193 : : }
194 [ + - ]: 528 : if (required.pass.gc_preserve_begin_func == callee) {
195 [ + + ]: 714 : for (auto user: call->users())
196 : 186 : required.use_info.uses.insert(cast<Instruction>(user));
197 : 528 : required.use_info.preserves.insert(call);
198 : 528 : required.use_info.haspreserve = true;
199 : 528 : return true;
200 : : }
201 : : }
202 [ + + ]: 1013410 : if (required.pass.pointer_from_objref_func == callee) {
203 : 18946 : required.use_info.addrescaped = true;
204 : 18946 : return true;
205 : : }
206 [ + + ]: 994463 : if (required.pass.typeof_func == callee) {
207 : 307 : required.use_info.hastypeof = true;
208 : : assert(use->get() == I);
209 : 307 : return true;
210 : : }
211 [ + + ]: 994156 : if (required.pass.write_barrier_func == callee ||
212 [ + + ]: 928734 : required.pass.write_barrier_binding_func == callee)
213 : 65790 : return true;
214 : 928366 : auto opno = use->getOperandNo();
215 : : // Uses in `jl_roots` operand bundle are not counted as escaping, everything else is.
216 [ + + - + ]: 947056 : if (!call->isBundleOperand(opno) ||
217 [ + + ]: 947056 : call->getOperandBundleForOperand(opno).getTagName() != "jl_roots") {
218 [ + + ]: 909676 : if (isa<UnreachableInst>(call->getParent()->getTerminator())) {
219 : 455857 : required.use_info.haserror = true;
220 : 455857 : return true;
221 : : }
222 : 453819 : required.use_info.escaped = true;
223 : 453819 : return false;
224 : : }
225 : 18690 : required.use_info.haspreserve = true;
226 : 18690 : return true;
227 : : }
228 [ + + ]: 4508570 : if (auto store = dyn_cast<StoreInst>(inst)) {
229 : : // Only store value count
230 [ + + ]: 1390520 : if (use->getOperandNo() != StoreInst::getPointerOperandIndex()) {
231 : 158027 : required.use_info.escaped = true;
232 : 158027 : return false;
233 : : }
234 : 1232490 : auto storev = store->getValueOperand();
235 [ + - - + : 1232490 : if (cur.offset == UINT32_MAX || !required.use_info.addMemOp(inst, use->getOperandNo(),
- + ]
236 : : cur.offset, storev->getType(),
237 : : true, required.DL))
238 : 0 : required.use_info.hasunknownmem = true;
239 : 1232490 : return true;
240 : : }
241 [ + + - + : 3118060 : if (isa<AtomicCmpXchgInst>(inst) || isa<AtomicRMWInst>(inst)) {
+ + ]
242 : : // Only store value count
243 [ + - - + ]: 5786 : if (use->getOperandNo() != isa<AtomicCmpXchgInst>(inst) ? AtomicCmpXchgInst::getPointerOperandIndex() : AtomicRMWInst::getPointerOperandIndex()) {
244 : 0 : required.use_info.escaped = true;
245 : 0 : return false;
246 : : }
247 : 5786 : required.use_info.hasload = true;
248 [ + - ]: 5786 : auto storev = isa<AtomicCmpXchgInst>(inst) ? cast<AtomicCmpXchgInst>(inst)->getNewValOperand() : cast<AtomicRMWInst>(inst)->getValOperand();
249 [ + - - + : 5786 : if (cur.offset == UINT32_MAX || !required.use_info.addMemOp(inst, use->getOperandNo(),
- + ]
250 : : cur.offset, storev->getType(),
251 : : true, required.DL))
252 : 0 : required.use_info.hasunknownmem = true;
253 : 5786 : required.use_info.refload = true;
254 : 5786 : return true;
255 : : }
256 [ + + + + : 3112270 : if (isa<AddrSpaceCastInst>(inst) || isa<BitCastInst>(inst)) {
+ + ]
257 : 2077480 : push_inst(inst);
258 : 2077480 : return true;
259 : : }
260 [ + + ]: 1034790 : if (auto gep = dyn_cast<GetElementPtrInst>(inst)) {
261 : 478831 : uint64_t next_offset = cur.offset;
262 [ + - ]: 478831 : if (cur.offset != UINT32_MAX) {
263 : 957662 : APInt apoffset(sizeof(void*) * 8, cur.offset, true);
264 [ + - - + : 478831 : if (!gep->accumulateConstantOffset(required.DL, apoffset) || apoffset.isNegative()) {
- + ]
265 : 0 : next_offset = UINT32_MAX;
266 : : }
267 : : else {
268 : 478831 : next_offset = apoffset.getLimitedValue();
269 [ - + ]: 478831 : if (next_offset > UINT32_MAX) {
270 : 0 : next_offset = UINT32_MAX;
271 : : }
272 : : }
273 : : }
274 : 478831 : push_inst(inst);
275 : 478831 : cur.offset = (uint32_t)next_offset;
276 : 478831 : return true;
277 : : }
278 [ + + ]: 555960 : if (isa<ReturnInst>(inst)) {
279 : 291879 : required.use_info.returned = true;
280 : 291879 : return true;
281 : : }
282 : 264081 : required.use_info.escaped = true;
283 : 264081 : return false;
284 : 1640980 : };
285 : :
286 : : while (true) {
287 : : assert(cur.use_it != cur.use_end);
288 : 5887980 : auto use = &*cur.use_it;
289 : 5887980 : auto inst = dyn_cast<Instruction>(use->getUser());
290 : 5887980 : ++cur.use_it;
291 [ - + ]: 5887980 : if (!inst) {
292 : 0 : required.use_info.escaped = true;
293 : 0 : return;
294 : : }
295 [ + + + + : 5887980 : if (!options.valid_set || options.valid_set->contains(inst->getParent())) {
+ + ]
296 [ + + ]: 5887120 : if (!check_inst(inst, use))
297 : 875927 : return;
298 : 5011190 : required.use_info.uses.insert(inst);
299 : : }
300 [ + + ]: 5012050 : if (cur.use_it == cur.use_end) {
301 [ + + ]: 1900810 : if (required.check_stack.empty())
302 : 765053 : return;
303 : 1135760 : cur = required.check_stack.back();
304 : 1135760 : required.check_stack.pop_back();
305 : : }
306 : 4247000 : }
307 : : }
|
