File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/Alignment.h |
Warning: | line 85, column 47 The result of the left shift is undefined due to shifting by '255', which is greater or equal to the width of type 'uint64_t' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- InstrRefBasedImpl.cpp - Tracking Debug Value MIs -------------------===// | |||
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 | /// \file InstrRefBasedImpl.cpp | |||
9 | /// | |||
10 | /// This is a separate implementation of LiveDebugValues, see | |||
11 | /// LiveDebugValues.cpp and VarLocBasedImpl.cpp for more information. | |||
12 | /// | |||
13 | /// This pass propagates variable locations between basic blocks, resolving | |||
14 | /// control flow conflicts between them. The problem is much like SSA | |||
15 | /// construction, where each DBG_VALUE instruction assigns the *value* that | |||
16 | /// a variable has, and every instruction where the variable is in scope uses | |||
17 | /// that variable. The resulting map of instruction-to-value is then translated | |||
18 | /// into a register (or spill) location for each variable over each instruction. | |||
19 | /// | |||
20 | /// This pass determines which DBG_VALUE dominates which instructions, or if | |||
21 | /// none do, where values must be merged (like PHI nodes). The added | |||
22 | /// complication is that because codegen has already finished, a PHI node may | |||
23 | /// be needed for a variable location to be correct, but no register or spill | |||
24 | /// slot merges the necessary values. In these circumstances, the variable | |||
25 | /// location is dropped. | |||
26 | /// | |||
27 | /// What makes this analysis non-trivial is loops: we cannot tell in advance | |||
28 | /// whether a variable location is live throughout a loop, or whether its | |||
29 | /// location is clobbered (or redefined by another DBG_VALUE), without | |||
30 | /// exploring all the way through. | |||
31 | /// | |||
32 | /// To make this simpler we perform two kinds of analysis. First, we identify | |||
33 | /// every value defined by every instruction (ignoring those that only move | |||
34 | /// another value), then compute a map of which values are available for each | |||
35 | /// instruction. This is stronger than a reaching-def analysis, as we create | |||
36 | /// PHI values where other values merge. | |||
37 | /// | |||
38 | /// Secondly, for each variable, we effectively re-construct SSA using each | |||
39 | /// DBG_VALUE as a def. The DBG_VALUEs read a value-number computed by the | |||
40 | /// first analysis from the location they refer to. We can then compute the | |||
41 | /// dominance frontiers of where a variable has a value, and create PHI nodes | |||
42 | /// where they merge. | |||
43 | /// This isn't precisely SSA-construction though, because the function shape | |||
44 | /// is pre-defined. If a variable location requires a PHI node, but no | |||
45 | /// PHI for the relevant values is present in the function (as computed by the | |||
46 | /// first analysis), the location must be dropped. | |||
47 | /// | |||
48 | /// Once both are complete, we can pass back over all instructions knowing: | |||
49 | /// * What _value_ each variable should contain, either defined by an | |||
50 | /// instruction or where control flow merges | |||
51 | /// * What the location of that value is (if any). | |||
52 | /// Allowing us to create appropriate live-in DBG_VALUEs, and DBG_VALUEs when | |||
53 | /// a value moves location. After this pass runs, all variable locations within | |||
54 | /// a block should be specified by DBG_VALUEs within that block, allowing | |||
55 | /// DbgEntityHistoryCalculator to focus on individual blocks. | |||
56 | /// | |||
57 | /// This pass is able to go fast because the size of the first | |||
58 | /// reaching-definition analysis is proportional to the working-set size of | |||
59 | /// the function, which the compiler tries to keep small. (It's also | |||
60 | /// proportional to the number of blocks). Additionally, we repeatedly perform | |||
61 | /// the second reaching-definition analysis with only the variables and blocks | |||
62 | /// in a single lexical scope, exploiting their locality. | |||
63 | /// | |||
64 | /// Determining where PHIs happen is trickier with this approach, and it comes | |||
65 | /// to a head in the major problem for LiveDebugValues: is a value live-through | |||
66 | /// a loop, or not? Your garden-variety dataflow analysis aims to build a set of | |||
67 | /// facts about a function, however this analysis needs to generate new value | |||
68 | /// numbers at joins. | |||
69 | /// | |||
70 | /// To do this, consider a lattice of all definition values, from instructions | |||
71 | /// and from PHIs. Each PHI is characterised by the RPO number of the block it | |||
72 | /// occurs in. Each value pair A, B can be ordered by RPO(A) < RPO(B): | |||
73 | /// with non-PHI values at the top, and any PHI value in the last block (by RPO | |||
74 | /// order) at the bottom. | |||
75 | /// | |||
76 | /// (Awkwardly: lower-down-the _lattice_ means a greater RPO _number_. Below, | |||
77 | /// "rank" always refers to the former). | |||
78 | /// | |||
79 | /// At any join, for each register, we consider: | |||
80 | /// * All incoming values, and | |||
81 | /// * The PREVIOUS live-in value at this join. | |||
82 | /// If all incoming values agree: that's the live-in value. If they do not, the | |||
83 | /// incoming values are ranked according to the partial order, and the NEXT | |||
84 | /// LOWEST rank after the PREVIOUS live-in value is picked (multiple values of | |||
85 | /// the same rank are ignored as conflicting). If there are no candidate values, | |||
86 | /// or if the rank of the live-in would be lower than the rank of the current | |||
87 | /// blocks PHIs, create a new PHI value. | |||
88 | /// | |||
89 | /// Intuitively: if it's not immediately obvious what value a join should result | |||
90 | /// in, we iteratively descend from instruction-definitions down through PHI | |||
91 | /// values, getting closer to the current block each time. If the current block | |||
92 | /// is a loop head, this ordering is effectively searching outer levels of | |||
93 | /// loops, to find a value that's live-through the current loop. | |||
94 | /// | |||
95 | /// If there is no value that's live-through this loop, a PHI is created for | |||
96 | /// this location instead. We can't use a lower-ranked PHI because by definition | |||
97 | /// it doesn't dominate the current block. We can't create a PHI value any | |||
98 | /// earlier, because we risk creating a PHI value at a location where values do | |||
99 | /// not in fact merge, thus misrepresenting the truth, and not making the true | |||
100 | /// live-through value for variable locations. | |||
101 | /// | |||
102 | /// This algorithm applies to both calculating the availability of values in | |||
103 | /// the first analysis, and the location of variables in the second. However | |||
104 | /// for the second we add an extra dimension of pain: creating a variable | |||
105 | /// location PHI is only valid if, for each incoming edge, | |||
106 | /// * There is a value for the variable on the incoming edge, and | |||
107 | /// * All the edges have that value in the same register. | |||
108 | /// Or put another way: we can only create a variable-location PHI if there is | |||
109 | /// a matching machine-location PHI, each input to which is the variables value | |||
110 | /// in the predecessor block. | |||
111 | /// | |||
112 | /// To accommodate this difference, each point on the lattice is split in | |||
113 | /// two: a "proposed" PHI and "definite" PHI. Any PHI that can immediately | |||
114 | /// have a location determined are "definite" PHIs, and no further work is | |||
115 | /// needed. Otherwise, a location that all non-backedge predecessors agree | |||
116 | /// on is picked and propagated as a "proposed" PHI value. If that PHI value | |||
117 | /// is truly live-through, it'll appear on the loop backedges on the next | |||
118 | /// dataflow iteration, after which the block live-in moves to be a "definite" | |||
119 | /// PHI. If it's not truly live-through, the variable value will be downgraded | |||
120 | /// further as we explore the lattice, or remains "proposed" and is considered | |||
121 | /// invalid once dataflow completes. | |||
122 | /// | |||
123 | /// ### Terminology | |||
124 | /// | |||
125 | /// A machine location is a register or spill slot, a value is something that's | |||
126 | /// defined by an instruction or PHI node, while a variable value is the value | |||
127 | /// assigned to a variable. A variable location is a machine location, that must | |||
128 | /// contain the appropriate variable value. A value that is a PHI node is | |||
129 | /// occasionally called an mphi. | |||
130 | /// | |||
131 | /// The first dataflow problem is the "machine value location" problem, | |||
132 | /// because we're determining which machine locations contain which values. | |||
133 | /// The "locations" are constant: what's unknown is what value they contain. | |||
134 | /// | |||
135 | /// The second dataflow problem (the one for variables) is the "variable value | |||
136 | /// problem", because it's determining what values a variable has, rather than | |||
137 | /// what location those values are placed in. Unfortunately, it's not that | |||
138 | /// simple, because producing a PHI value always involves picking a location. | |||
139 | /// This is an imperfection that we just have to accept, at least for now. | |||
140 | /// | |||
141 | /// TODO: | |||
142 | /// Overlapping fragments | |||
143 | /// Entry values | |||
144 | /// Add back DEBUG statements for debugging this | |||
145 | /// Collect statistics | |||
146 | /// | |||
147 | //===----------------------------------------------------------------------===// | |||
148 | ||||
149 | #include "llvm/ADT/DenseMap.h" | |||
150 | #include "llvm/ADT/PostOrderIterator.h" | |||
151 | #include "llvm/ADT/STLExtras.h" | |||
152 | #include "llvm/ADT/SmallPtrSet.h" | |||
153 | #include "llvm/ADT/SmallSet.h" | |||
154 | #include "llvm/ADT/SmallVector.h" | |||
155 | #include "llvm/ADT/Statistic.h" | |||
156 | #include "llvm/ADT/UniqueVector.h" | |||
157 | #include "llvm/CodeGen/LexicalScopes.h" | |||
158 | #include "llvm/CodeGen/MachineBasicBlock.h" | |||
159 | #include "llvm/CodeGen/MachineFrameInfo.h" | |||
160 | #include "llvm/CodeGen/MachineFunction.h" | |||
161 | #include "llvm/CodeGen/MachineFunctionPass.h" | |||
162 | #include "llvm/CodeGen/MachineInstr.h" | |||
163 | #include "llvm/CodeGen/MachineInstrBuilder.h" | |||
164 | #include "llvm/CodeGen/MachineInstrBundle.h" | |||
165 | #include "llvm/CodeGen/MachineMemOperand.h" | |||
166 | #include "llvm/CodeGen/MachineOperand.h" | |||
167 | #include "llvm/CodeGen/PseudoSourceValue.h" | |||
168 | #include "llvm/CodeGen/RegisterScavenging.h" | |||
169 | #include "llvm/CodeGen/TargetFrameLowering.h" | |||
170 | #include "llvm/CodeGen/TargetInstrInfo.h" | |||
171 | #include "llvm/CodeGen/TargetLowering.h" | |||
172 | #include "llvm/CodeGen/TargetPassConfig.h" | |||
173 | #include "llvm/CodeGen/TargetRegisterInfo.h" | |||
174 | #include "llvm/CodeGen/TargetSubtargetInfo.h" | |||
175 | #include "llvm/Config/llvm-config.h" | |||
176 | #include "llvm/IR/DIBuilder.h" | |||
177 | #include "llvm/IR/DebugInfoMetadata.h" | |||
178 | #include "llvm/IR/DebugLoc.h" | |||
179 | #include "llvm/IR/Function.h" | |||
180 | #include "llvm/IR/Module.h" | |||
181 | #include "llvm/InitializePasses.h" | |||
182 | #include "llvm/MC/MCRegisterInfo.h" | |||
183 | #include "llvm/Pass.h" | |||
184 | #include "llvm/Support/Casting.h" | |||
185 | #include "llvm/Support/Compiler.h" | |||
186 | #include "llvm/Support/Debug.h" | |||
187 | #include "llvm/Support/TypeSize.h" | |||
188 | #include "llvm/Support/raw_ostream.h" | |||
189 | #include "llvm/Target/TargetMachine.h" | |||
190 | #include "llvm/Transforms/Utils/SSAUpdaterImpl.h" | |||
191 | #include <algorithm> | |||
192 | #include <cassert> | |||
193 | #include <cstdint> | |||
194 | #include <functional> | |||
195 | #include <queue> | |||
196 | #include <tuple> | |||
197 | #include <utility> | |||
198 | #include <vector> | |||
199 | #include <limits.h> | |||
200 | #include <limits> | |||
201 | ||||
202 | #include "LiveDebugValues.h" | |||
203 | ||||
204 | using namespace llvm; | |||
205 | ||||
206 | // SSAUpdaterImple sets DEBUG_TYPE, change it. | |||
207 | #undef DEBUG_TYPE"livedebugvalues" | |||
208 | #define DEBUG_TYPE"livedebugvalues" "livedebugvalues" | |||
209 | ||||
210 | // Act more like the VarLoc implementation, by propagating some locations too | |||
211 | // far and ignoring some transfers. | |||
212 | static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden, | |||
213 | cl::desc("Act like old LiveDebugValues did"), | |||
214 | cl::init(false)); | |||
215 | ||||
216 | namespace { | |||
217 | ||||
218 | // The location at which a spilled value resides. It consists of a register and | |||
219 | // an offset. | |||
220 | struct SpillLoc { | |||
221 | unsigned SpillBase; | |||
222 | StackOffset SpillOffset; | |||
223 | bool operator==(const SpillLoc &Other) const { | |||
224 | return std::make_pair(SpillBase, SpillOffset) == | |||
225 | std::make_pair(Other.SpillBase, Other.SpillOffset); | |||
226 | } | |||
227 | bool operator<(const SpillLoc &Other) const { | |||
228 | return std::make_tuple(SpillBase, SpillOffset.getFixed(), | |||
229 | SpillOffset.getScalable()) < | |||
230 | std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(), | |||
231 | Other.SpillOffset.getScalable()); | |||
232 | } | |||
233 | }; | |||
234 | ||||
235 | class LocIdx { | |||
236 | unsigned Location; | |||
237 | ||||
238 | // Default constructor is private, initializing to an illegal location number. | |||
239 | // Use only for "not an entry" elements in IndexedMaps. | |||
240 | LocIdx() : Location(UINT_MAX(2147483647 *2U +1U)) { } | |||
241 | ||||
242 | public: | |||
243 | #define NUM_LOC_BITS24 24 | |||
244 | LocIdx(unsigned L) : Location(L) { | |||
245 | assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits")((void)0); | |||
246 | } | |||
247 | ||||
248 | static LocIdx MakeIllegalLoc() { | |||
249 | return LocIdx(); | |||
250 | } | |||
251 | ||||
252 | bool isIllegal() const { | |||
253 | return Location == UINT_MAX(2147483647 *2U +1U); | |||
254 | } | |||
255 | ||||
256 | uint64_t asU64() const { | |||
257 | return Location; | |||
258 | } | |||
259 | ||||
260 | bool operator==(unsigned L) const { | |||
261 | return Location == L; | |||
262 | } | |||
263 | ||||
264 | bool operator==(const LocIdx &L) const { | |||
265 | return Location == L.Location; | |||
266 | } | |||
267 | ||||
268 | bool operator!=(unsigned L) const { | |||
269 | return !(*this == L); | |||
270 | } | |||
271 | ||||
272 | bool operator!=(const LocIdx &L) const { | |||
273 | return !(*this == L); | |||
274 | } | |||
275 | ||||
276 | bool operator<(const LocIdx &Other) const { | |||
277 | return Location < Other.Location; | |||
278 | } | |||
279 | }; | |||
280 | ||||
281 | class LocIdxToIndexFunctor { | |||
282 | public: | |||
283 | using argument_type = LocIdx; | |||
284 | unsigned operator()(const LocIdx &L) const { | |||
285 | return L.asU64(); | |||
286 | } | |||
287 | }; | |||
288 | ||||
289 | /// Unique identifier for a value defined by an instruction, as a value type. | |||
290 | /// Casts back and forth to a uint64_t. Probably replacable with something less | |||
291 | /// bit-constrained. Each value identifies the instruction and machine location | |||
292 | /// where the value is defined, although there may be no corresponding machine | |||
293 | /// operand for it (ex: regmasks clobbering values). The instructions are | |||
294 | /// one-based, and definitions that are PHIs have instruction number zero. | |||
295 | /// | |||
296 | /// The obvious limits of a 1M block function or 1M instruction blocks are | |||
297 | /// problematic; but by that point we should probably have bailed out of | |||
298 | /// trying to analyse the function. | |||
299 | class ValueIDNum { | |||
300 | uint64_t BlockNo : 20; /// The block where the def happens. | |||
301 | uint64_t InstNo : 20; /// The Instruction where the def happens. | |||
302 | /// One based, is distance from start of block. | |||
303 | uint64_t LocNo : NUM_LOC_BITS24; /// The machine location where the def happens. | |||
304 | ||||
305 | public: | |||
306 | // XXX -- temporarily enabled while the live-in / live-out tables are moved | |||
307 | // to something more type-y | |||
308 | ValueIDNum() : BlockNo(0xFFFFF), | |||
309 | InstNo(0xFFFFF), | |||
310 | LocNo(0xFFFFFF) { } | |||
311 | ||||
312 | ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc) | |||
313 | : BlockNo(Block), InstNo(Inst), LocNo(Loc) { } | |||
314 | ||||
315 | ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc) | |||
316 | : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) { } | |||
317 | ||||
318 | uint64_t getBlock() const { return BlockNo; } | |||
319 | uint64_t getInst() const { return InstNo; } | |||
320 | uint64_t getLoc() const { return LocNo; } | |||
321 | bool isPHI() const { return InstNo == 0; } | |||
322 | ||||
323 | uint64_t asU64() const { | |||
324 | uint64_t TmpBlock = BlockNo; | |||
325 | uint64_t TmpInst = InstNo; | |||
326 | return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS24 | LocNo; | |||
327 | } | |||
328 | ||||
329 | static ValueIDNum fromU64(uint64_t v) { | |||
330 | uint64_t L = (v & 0x3FFF); | |||
331 | return {v >> 44ull, ((v >> NUM_LOC_BITS24) & 0xFFFFF), L}; | |||
332 | } | |||
333 | ||||
334 | bool operator<(const ValueIDNum &Other) const { | |||
335 | return asU64() < Other.asU64(); | |||
336 | } | |||
337 | ||||
338 | bool operator==(const ValueIDNum &Other) const { | |||
339 | return std::tie(BlockNo, InstNo, LocNo) == | |||
340 | std::tie(Other.BlockNo, Other.InstNo, Other.LocNo); | |||
341 | } | |||
342 | ||||
343 | bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); } | |||
344 | ||||
345 | std::string asString(const std::string &mlocname) const { | |||
346 | return Twine("Value{bb: ") | |||
347 | .concat(Twine(BlockNo).concat( | |||
348 | Twine(", inst: ") | |||
349 | .concat((InstNo ? Twine(InstNo) : Twine("live-in")) | |||
350 | .concat(Twine(", loc: ").concat(Twine(mlocname))) | |||
351 | .concat(Twine("}"))))) | |||
352 | .str(); | |||
353 | } | |||
354 | ||||
355 | static ValueIDNum EmptyValue; | |||
356 | }; | |||
357 | ||||
358 | } // end anonymous namespace | |||
359 | ||||
360 | namespace { | |||
361 | ||||
362 | /// Meta qualifiers for a value. Pair of whatever expression is used to qualify | |||
363 | /// the the value, and Boolean of whether or not it's indirect. | |||
364 | class DbgValueProperties { | |||
365 | public: | |||
366 | DbgValueProperties(const DIExpression *DIExpr, bool Indirect) | |||
367 | : DIExpr(DIExpr), Indirect(Indirect) {} | |||
368 | ||||
369 | /// Extract properties from an existing DBG_VALUE instruction. | |||
370 | DbgValueProperties(const MachineInstr &MI) { | |||
371 | assert(MI.isDebugValue())((void)0); | |||
372 | DIExpr = MI.getDebugExpression(); | |||
373 | Indirect = MI.getOperand(1).isImm(); | |||
374 | } | |||
375 | ||||
376 | bool operator==(const DbgValueProperties &Other) const { | |||
377 | return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect); | |||
378 | } | |||
379 | ||||
380 | bool operator!=(const DbgValueProperties &Other) const { | |||
381 | return !(*this == Other); | |||
382 | } | |||
383 | ||||
384 | const DIExpression *DIExpr; | |||
385 | bool Indirect; | |||
386 | }; | |||
387 | ||||
388 | /// Tracker for what values are in machine locations. Listens to the Things | |||
389 | /// being Done by various instructions, and maintains a table of what machine | |||
390 | /// locations have what values (as defined by a ValueIDNum). | |||
391 | /// | |||
392 | /// There are potentially a much larger number of machine locations on the | |||
393 | /// target machine than the actual working-set size of the function. On x86 for | |||
394 | /// example, we're extremely unlikely to want to track values through control | |||
395 | /// or debug registers. To avoid doing so, MLocTracker has several layers of | |||
396 | /// indirection going on, with two kinds of ``location'': | |||
397 | /// * A LocID uniquely identifies a register or spill location, with a | |||
398 | /// predictable value. | |||
399 | /// * A LocIdx is a key (in the database sense) for a LocID and a ValueIDNum. | |||
400 | /// Whenever a location is def'd or used by a MachineInstr, we automagically | |||
401 | /// create a new LocIdx for a location, but not otherwise. This ensures we only | |||
402 | /// account for locations that are actually used or defined. The cost is another | |||
403 | /// vector lookup (of LocID -> LocIdx) over any other implementation. This is | |||
404 | /// fairly cheap, and the compiler tries to reduce the working-set at any one | |||
405 | /// time in the function anyway. | |||
406 | /// | |||
407 | /// Register mask operands completely blow this out of the water; I've just | |||
408 | /// piled hacks on top of hacks to get around that. | |||
409 | class MLocTracker { | |||
410 | public: | |||
411 | MachineFunction &MF; | |||
412 | const TargetInstrInfo &TII; | |||
413 | const TargetRegisterInfo &TRI; | |||
414 | const TargetLowering &TLI; | |||
415 | ||||
416 | /// IndexedMap type, mapping from LocIdx to ValueIDNum. | |||
417 | using LocToValueType = IndexedMap<ValueIDNum, LocIdxToIndexFunctor>; | |||
418 | ||||
419 | /// Map of LocIdxes to the ValueIDNums that they store. This is tightly | |||
420 | /// packed, entries only exist for locations that are being tracked. | |||
421 | LocToValueType LocIdxToIDNum; | |||
422 | ||||
423 | /// "Map" of machine location IDs (i.e., raw register or spill number) to the | |||
424 | /// LocIdx key / number for that location. There are always at least as many | |||
425 | /// as the number of registers on the target -- if the value in the register | |||
426 | /// is not being tracked, then the LocIdx value will be zero. New entries are | |||
427 | /// appended if a new spill slot begins being tracked. | |||
428 | /// This, and the corresponding reverse map persist for the analysis of the | |||
429 | /// whole function, and is necessarying for decoding various vectors of | |||
430 | /// values. | |||
431 | std::vector<LocIdx> LocIDToLocIdx; | |||
432 | ||||
433 | /// Inverse map of LocIDToLocIdx. | |||
434 | IndexedMap<unsigned, LocIdxToIndexFunctor> LocIdxToLocID; | |||
435 | ||||
436 | /// Unique-ification of spill slots. Used to number them -- their LocID | |||
437 | /// number is the index in SpillLocs minus one plus NumRegs. | |||
438 | UniqueVector<SpillLoc> SpillLocs; | |||
439 | ||||
440 | // If we discover a new machine location, assign it an mphi with this | |||
441 | // block number. | |||
442 | unsigned CurBB; | |||
443 | ||||
444 | /// Cached local copy of the number of registers the target has. | |||
445 | unsigned NumRegs; | |||
446 | ||||
447 | /// Collection of register mask operands that have been observed. Second part | |||
448 | /// of pair indicates the instruction that they happened in. Used to | |||
449 | /// reconstruct where defs happened if we start tracking a location later | |||
450 | /// on. | |||
451 | SmallVector<std::pair<const MachineOperand *, unsigned>, 32> Masks; | |||
452 | ||||
453 | /// Iterator for locations and the values they contain. Dereferencing | |||
454 | /// produces a struct/pair containing the LocIdx key for this location, | |||
455 | /// and a reference to the value currently stored. Simplifies the process | |||
456 | /// of seeking a particular location. | |||
457 | class MLocIterator { | |||
458 | LocToValueType &ValueMap; | |||
459 | LocIdx Idx; | |||
460 | ||||
461 | public: | |||
462 | class value_type { | |||
463 | public: | |||
464 | value_type(LocIdx Idx, ValueIDNum &Value) : Idx(Idx), Value(Value) { } | |||
465 | const LocIdx Idx; /// Read-only index of this location. | |||
466 | ValueIDNum &Value; /// Reference to the stored value at this location. | |||
467 | }; | |||
468 | ||||
469 | MLocIterator(LocToValueType &ValueMap, LocIdx Idx) | |||
470 | : ValueMap(ValueMap), Idx(Idx) { } | |||
471 | ||||
472 | bool operator==(const MLocIterator &Other) const { | |||
473 | assert(&ValueMap == &Other.ValueMap)((void)0); | |||
474 | return Idx == Other.Idx; | |||
475 | } | |||
476 | ||||
477 | bool operator!=(const MLocIterator &Other) const { | |||
478 | return !(*this == Other); | |||
479 | } | |||
480 | ||||
481 | void operator++() { | |||
482 | Idx = LocIdx(Idx.asU64() + 1); | |||
483 | } | |||
484 | ||||
485 | value_type operator*() { | |||
486 | return value_type(Idx, ValueMap[LocIdx(Idx)]); | |||
487 | } | |||
488 | }; | |||
489 | ||||
490 | MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII, | |||
491 | const TargetRegisterInfo &TRI, const TargetLowering &TLI) | |||
492 | : MF(MF), TII(TII), TRI(TRI), TLI(TLI), | |||
493 | LocIdxToIDNum(ValueIDNum::EmptyValue), | |||
494 | LocIdxToLocID(0) { | |||
495 | NumRegs = TRI.getNumRegs(); | |||
496 | reset(); | |||
497 | LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc()); | |||
498 | assert(NumRegs < (1u << NUM_LOC_BITS))((void)0); // Detect bit packing failure | |||
499 | ||||
500 | // Always track SP. This avoids the implicit clobbering caused by regmasks | |||
501 | // from affectings its values. (LiveDebugValues disbelieves calls and | |||
502 | // regmasks that claim to clobber SP). | |||
503 | Register SP = TLI.getStackPointerRegisterToSaveRestore(); | |||
504 | if (SP) { | |||
505 | unsigned ID = getLocID(SP, false); | |||
506 | (void)lookupOrTrackRegister(ID); | |||
507 | } | |||
508 | } | |||
509 | ||||
510 | /// Produce location ID number for indexing LocIDToLocIdx. Takes the register | |||
511 | /// or spill number, and flag for whether it's a spill or not. | |||
512 | unsigned getLocID(Register RegOrSpill, bool isSpill) { | |||
513 | return (isSpill) ? RegOrSpill.id() + NumRegs - 1 : RegOrSpill.id(); | |||
514 | } | |||
515 | ||||
516 | /// Accessor for reading the value at Idx. | |||
517 | ValueIDNum getNumAtPos(LocIdx Idx) const { | |||
518 | assert(Idx.asU64() < LocIdxToIDNum.size())((void)0); | |||
519 | return LocIdxToIDNum[Idx]; | |||
520 | } | |||
521 | ||||
522 | unsigned getNumLocs(void) const { return LocIdxToIDNum.size(); } | |||
523 | ||||
524 | /// Reset all locations to contain a PHI value at the designated block. Used | |||
525 | /// sometimes for actual PHI values, othertimes to indicate the block entry | |||
526 | /// value (before any more information is known). | |||
527 | void setMPhis(unsigned NewCurBB) { | |||
528 | CurBB = NewCurBB; | |||
529 | for (auto Location : locations()) | |||
530 | Location.Value = {CurBB, 0, Location.Idx}; | |||
531 | } | |||
532 | ||||
533 | /// Load values for each location from array of ValueIDNums. Take current | |||
534 | /// bbnum just in case we read a value from a hitherto untouched register. | |||
535 | void loadFromArray(ValueIDNum *Locs, unsigned NewCurBB) { | |||
536 | CurBB = NewCurBB; | |||
537 | // Iterate over all tracked locations, and load each locations live-in | |||
538 | // value into our local index. | |||
539 | for (auto Location : locations()) | |||
540 | Location.Value = Locs[Location.Idx.asU64()]; | |||
541 | } | |||
542 | ||||
543 | /// Wipe any un-necessary location records after traversing a block. | |||
544 | void reset(void) { | |||
545 | // We could reset all the location values too; however either loadFromArray | |||
546 | // or setMPhis should be called before this object is re-used. Just | |||
547 | // clear Masks, they're definitely not needed. | |||
548 | Masks.clear(); | |||
549 | } | |||
550 | ||||
551 | /// Clear all data. Destroys the LocID <=> LocIdx map, which makes most of | |||
552 | /// the information in this pass uninterpretable. | |||
553 | void clear(void) { | |||
554 | reset(); | |||
555 | LocIDToLocIdx.clear(); | |||
556 | LocIdxToLocID.clear(); | |||
557 | LocIdxToIDNum.clear(); | |||
558 | //SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from 0 | |||
559 | SpillLocs = decltype(SpillLocs)(); | |||
560 | ||||
561 | LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc()); | |||
562 | } | |||
563 | ||||
564 | /// Set a locaiton to a certain value. | |||
565 | void setMLoc(LocIdx L, ValueIDNum Num) { | |||
566 | assert(L.asU64() < LocIdxToIDNum.size())((void)0); | |||
567 | LocIdxToIDNum[L] = Num; | |||
568 | } | |||
569 | ||||
570 | /// Create a LocIdx for an untracked register ID. Initialize it to either an | |||
571 | /// mphi value representing a live-in, or a recent register mask clobber. | |||
572 | LocIdx trackRegister(unsigned ID) { | |||
573 | assert(ID != 0)((void)0); | |||
574 | LocIdx NewIdx = LocIdx(LocIdxToIDNum.size()); | |||
575 | LocIdxToIDNum.grow(NewIdx); | |||
576 | LocIdxToLocID.grow(NewIdx); | |||
577 | ||||
578 | // Default: it's an mphi. | |||
579 | ValueIDNum ValNum = {CurBB, 0, NewIdx}; | |||
580 | // Was this reg ever touched by a regmask? | |||
581 | for (const auto &MaskPair : reverse(Masks)) { | |||
582 | if (MaskPair.first->clobbersPhysReg(ID)) { | |||
583 | // There was an earlier def we skipped. | |||
584 | ValNum = {CurBB, MaskPair.second, NewIdx}; | |||
585 | break; | |||
586 | } | |||
587 | } | |||
588 | ||||
589 | LocIdxToIDNum[NewIdx] = ValNum; | |||
590 | LocIdxToLocID[NewIdx] = ID; | |||
591 | return NewIdx; | |||
592 | } | |||
593 | ||||
594 | LocIdx lookupOrTrackRegister(unsigned ID) { | |||
595 | LocIdx &Index = LocIDToLocIdx[ID]; | |||
596 | if (Index.isIllegal()) | |||
597 | Index = trackRegister(ID); | |||
598 | return Index; | |||
599 | } | |||
600 | ||||
601 | /// Record a definition of the specified register at the given block / inst. | |||
602 | /// This doesn't take a ValueIDNum, because the definition and its location | |||
603 | /// are synonymous. | |||
604 | void defReg(Register R, unsigned BB, unsigned Inst) { | |||
605 | unsigned ID = getLocID(R, false); | |||
606 | LocIdx Idx = lookupOrTrackRegister(ID); | |||
607 | ValueIDNum ValueID = {BB, Inst, Idx}; | |||
608 | LocIdxToIDNum[Idx] = ValueID; | |||
609 | } | |||
610 | ||||
611 | /// Set a register to a value number. To be used if the value number is | |||
612 | /// known in advance. | |||
613 | void setReg(Register R, ValueIDNum ValueID) { | |||
614 | unsigned ID = getLocID(R, false); | |||
615 | LocIdx Idx = lookupOrTrackRegister(ID); | |||
616 | LocIdxToIDNum[Idx] = ValueID; | |||
617 | } | |||
618 | ||||
619 | ValueIDNum readReg(Register R) { | |||
620 | unsigned ID = getLocID(R, false); | |||
621 | LocIdx Idx = lookupOrTrackRegister(ID); | |||
622 | return LocIdxToIDNum[Idx]; | |||
623 | } | |||
624 | ||||
625 | /// Reset a register value to zero / empty. Needed to replicate the | |||
626 | /// VarLoc implementation where a copy to/from a register effectively | |||
627 | /// clears the contents of the source register. (Values can only have one | |||
628 | /// machine location in VarLocBasedImpl). | |||
629 | void wipeRegister(Register R) { | |||
630 | unsigned ID = getLocID(R, false); | |||
631 | LocIdx Idx = LocIDToLocIdx[ID]; | |||
632 | LocIdxToIDNum[Idx] = ValueIDNum::EmptyValue; | |||
633 | } | |||
634 | ||||
635 | /// Determine the LocIdx of an existing register. | |||
636 | LocIdx getRegMLoc(Register R) { | |||
637 | unsigned ID = getLocID(R, false); | |||
638 | return LocIDToLocIdx[ID]; | |||
639 | } | |||
640 | ||||
641 | /// Record a RegMask operand being executed. Defs any register we currently | |||
642 | /// track, stores a pointer to the mask in case we have to account for it | |||
643 | /// later. | |||
644 | void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID) { | |||
645 | // Ensure SP exists, so that we don't override it later. | |||
646 | Register SP = TLI.getStackPointerRegisterToSaveRestore(); | |||
647 | ||||
648 | // Def any register we track have that isn't preserved. The regmask | |||
649 | // terminates the liveness of a register, meaning its value can't be | |||
650 | // relied upon -- we represent this by giving it a new value. | |||
651 | for (auto Location : locations()) { | |||
652 | unsigned ID = LocIdxToLocID[Location.Idx]; | |||
653 | // Don't clobber SP, even if the mask says it's clobbered. | |||
654 | if (ID < NumRegs && ID != SP && MO->clobbersPhysReg(ID)) | |||
655 | defReg(ID, CurBB, InstID); | |||
656 | } | |||
657 | Masks.push_back(std::make_pair(MO, InstID)); | |||
658 | } | |||
659 | ||||
660 | /// Find LocIdx for SpillLoc \p L, creating a new one if it's not tracked. | |||
661 | LocIdx getOrTrackSpillLoc(SpillLoc L) { | |||
662 | unsigned SpillID = SpillLocs.idFor(L); | |||
663 | if (SpillID == 0) { | |||
664 | SpillID = SpillLocs.insert(L); | |||
665 | unsigned L = getLocID(SpillID, true); | |||
666 | LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx | |||
667 | LocIdxToIDNum.grow(Idx); | |||
668 | LocIdxToLocID.grow(Idx); | |||
669 | LocIDToLocIdx.push_back(Idx); | |||
670 | LocIdxToLocID[Idx] = L; | |||
671 | return Idx; | |||
672 | } else { | |||
673 | unsigned L = getLocID(SpillID, true); | |||
674 | LocIdx Idx = LocIDToLocIdx[L]; | |||
675 | return Idx; | |||
676 | } | |||
677 | } | |||
678 | ||||
679 | /// Set the value stored in a spill slot. | |||
680 | void setSpill(SpillLoc L, ValueIDNum ValueID) { | |||
681 | LocIdx Idx = getOrTrackSpillLoc(L); | |||
682 | LocIdxToIDNum[Idx] = ValueID; | |||
683 | } | |||
684 | ||||
685 | /// Read whatever value is in a spill slot, or None if it isn't tracked. | |||
686 | Optional<ValueIDNum> readSpill(SpillLoc L) { | |||
687 | unsigned SpillID = SpillLocs.idFor(L); | |||
688 | if (SpillID == 0) | |||
689 | return None; | |||
690 | ||||
691 | unsigned LocID = getLocID(SpillID, true); | |||
692 | LocIdx Idx = LocIDToLocIdx[LocID]; | |||
693 | return LocIdxToIDNum[Idx]; | |||
694 | } | |||
695 | ||||
696 | /// Determine the LocIdx of a spill slot. Return None if it previously | |||
697 | /// hasn't had a value assigned. | |||
698 | Optional<LocIdx> getSpillMLoc(SpillLoc L) { | |||
699 | unsigned SpillID = SpillLocs.idFor(L); | |||
700 | if (SpillID == 0) | |||
701 | return None; | |||
702 | unsigned LocNo = getLocID(SpillID, true); | |||
703 | return LocIDToLocIdx[LocNo]; | |||
704 | } | |||
705 | ||||
706 | /// Return true if Idx is a spill machine location. | |||
707 | bool isSpill(LocIdx Idx) const { | |||
708 | return LocIdxToLocID[Idx] >= NumRegs; | |||
709 | } | |||
710 | ||||
711 | MLocIterator begin() { | |||
712 | return MLocIterator(LocIdxToIDNum, 0); | |||
713 | } | |||
714 | ||||
715 | MLocIterator end() { | |||
716 | return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size()); | |||
717 | } | |||
718 | ||||
719 | /// Return a range over all locations currently tracked. | |||
720 | iterator_range<MLocIterator> locations() { | |||
721 | return llvm::make_range(begin(), end()); | |||
722 | } | |||
723 | ||||
724 | std::string LocIdxToName(LocIdx Idx) const { | |||
725 | unsigned ID = LocIdxToLocID[Idx]; | |||
726 | if (ID >= NumRegs) | |||
727 | return Twine("slot ").concat(Twine(ID - NumRegs)).str(); | |||
728 | else | |||
729 | return TRI.getRegAsmName(ID).str(); | |||
730 | } | |||
731 | ||||
732 | std::string IDAsString(const ValueIDNum &Num) const { | |||
733 | std::string DefName = LocIdxToName(Num.getLoc()); | |||
734 | return Num.asString(DefName); | |||
735 | } | |||
736 | ||||
737 | LLVM_DUMP_METHOD__attribute__((noinline)) | |||
738 | void dump() { | |||
739 | for (auto Location : locations()) { | |||
740 | std::string MLocName = LocIdxToName(Location.Value.getLoc()); | |||
741 | std::string DefName = Location.Value.asString(MLocName); | |||
742 | dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n"; | |||
743 | } | |||
744 | } | |||
745 | ||||
746 | LLVM_DUMP_METHOD__attribute__((noinline)) | |||
747 | void dump_mloc_map() { | |||
748 | for (auto Location : locations()) { | |||
749 | std::string foo = LocIdxToName(Location.Idx); | |||
750 | dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n"; | |||
751 | } | |||
752 | } | |||
753 | ||||
754 | /// Create a DBG_VALUE based on machine location \p MLoc. Qualify it with the | |||
755 | /// information in \pProperties, for variable Var. Don't insert it anywhere, | |||
756 | /// just return the builder for it. | |||
757 | MachineInstrBuilder emitLoc(Optional<LocIdx> MLoc, const DebugVariable &Var, | |||
758 | const DbgValueProperties &Properties) { | |||
759 | DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, | |||
760 | Var.getVariable()->getScope(), | |||
761 | const_cast<DILocation *>(Var.getInlinedAt())); | |||
762 | auto MIB = BuildMI(MF, DL, TII.get(TargetOpcode::DBG_VALUE)); | |||
763 | ||||
764 | const DIExpression *Expr = Properties.DIExpr; | |||
765 | if (!MLoc) { | |||
766 | // No location -> DBG_VALUE $noreg | |||
767 | MIB.addReg(0, RegState::Debug); | |||
768 | MIB.addReg(0, RegState::Debug); | |||
769 | } else if (LocIdxToLocID[*MLoc] >= NumRegs) { | |||
770 | unsigned LocID = LocIdxToLocID[*MLoc]; | |||
771 | const SpillLoc &Spill = SpillLocs[LocID - NumRegs + 1]; | |||
772 | ||||
773 | auto *TRI = MF.getSubtarget().getRegisterInfo(); | |||
774 | Expr = TRI->prependOffsetExpression(Expr, DIExpression::ApplyOffset, | |||
775 | Spill.SpillOffset); | |||
776 | unsigned Base = Spill.SpillBase; | |||
777 | MIB.addReg(Base, RegState::Debug); | |||
778 | MIB.addImm(0); | |||
779 | } else { | |||
780 | unsigned LocID = LocIdxToLocID[*MLoc]; | |||
781 | MIB.addReg(LocID, RegState::Debug); | |||
782 | if (Properties.Indirect) | |||
783 | MIB.addImm(0); | |||
784 | else | |||
785 | MIB.addReg(0, RegState::Debug); | |||
786 | } | |||
787 | ||||
788 | MIB.addMetadata(Var.getVariable()); | |||
789 | MIB.addMetadata(Expr); | |||
790 | return MIB; | |||
791 | } | |||
792 | }; | |||
793 | ||||
794 | /// Class recording the (high level) _value_ of a variable. Identifies either | |||
795 | /// the value of the variable as a ValueIDNum, or a constant MachineOperand. | |||
796 | /// This class also stores meta-information about how the value is qualified. | |||
797 | /// Used to reason about variable values when performing the second | |||
798 | /// (DebugVariable specific) dataflow analysis. | |||
799 | class DbgValue { | |||
800 | public: | |||
801 | union { | |||
802 | /// If Kind is Def, the value number that this value is based on. | |||
803 | ValueIDNum ID; | |||
804 | /// If Kind is Const, the MachineOperand defining this value. | |||
805 | MachineOperand MO; | |||
806 | /// For a NoVal DbgValue, which block it was generated in. | |||
807 | unsigned BlockNo; | |||
808 | }; | |||
809 | /// Qualifiers for the ValueIDNum above. | |||
810 | DbgValueProperties Properties; | |||
811 | ||||
812 | typedef enum { | |||
813 | Undef, // Represents a DBG_VALUE $noreg in the transfer function only. | |||
814 | Def, // This value is defined by an inst, or is a PHI value. | |||
815 | Const, // A constant value contained in the MachineOperand field. | |||
816 | Proposed, // This is a tentative PHI value, which may be confirmed or | |||
817 | // invalidated later. | |||
818 | NoVal // Empty DbgValue, generated during dataflow. BlockNo stores | |||
819 | // which block this was generated in. | |||
820 | } KindT; | |||
821 | /// Discriminator for whether this is a constant or an in-program value. | |||
822 | KindT Kind; | |||
823 | ||||
824 | DbgValue(const ValueIDNum &Val, const DbgValueProperties &Prop, KindT Kind) | |||
825 | : ID(Val), Properties(Prop), Kind(Kind) { | |||
826 | assert(Kind == Def || Kind == Proposed)((void)0); | |||
827 | } | |||
828 | ||||
829 | DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind) | |||
830 | : BlockNo(BlockNo), Properties(Prop), Kind(Kind) { | |||
831 | assert(Kind == NoVal)((void)0); | |||
832 | } | |||
833 | ||||
834 | DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind) | |||
835 | : MO(MO), Properties(Prop), Kind(Kind) { | |||
836 | assert(Kind == Const)((void)0); | |||
837 | } | |||
838 | ||||
839 | DbgValue(const DbgValueProperties &Prop, KindT Kind) | |||
840 | : Properties(Prop), Kind(Kind) { | |||
841 | assert(Kind == Undef &&((void)0) | |||
842 | "Empty DbgValue constructor must pass in Undef kind")((void)0); | |||
843 | } | |||
844 | ||||
845 | void dump(const MLocTracker *MTrack) const { | |||
846 | if (Kind == Const) { | |||
847 | MO.dump(); | |||
848 | } else if (Kind == NoVal) { | |||
849 | dbgs() << "NoVal(" << BlockNo << ")"; | |||
850 | } else if (Kind == Proposed) { | |||
851 | dbgs() << "VPHI(" << MTrack->IDAsString(ID) << ")"; | |||
852 | } else { | |||
853 | assert(Kind == Def)((void)0); | |||
854 | dbgs() << MTrack->IDAsString(ID); | |||
855 | } | |||
856 | if (Properties.Indirect) | |||
857 | dbgs() << " indir"; | |||
858 | if (Properties.DIExpr) | |||
859 | dbgs() << " " << *Properties.DIExpr; | |||
860 | } | |||
861 | ||||
862 | bool operator==(const DbgValue &Other) const { | |||
863 | if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties)) | |||
864 | return false; | |||
865 | else if (Kind == Proposed && ID != Other.ID) | |||
866 | return false; | |||
867 | else if (Kind == Def && ID != Other.ID) | |||
868 | return false; | |||
869 | else if (Kind == NoVal && BlockNo != Other.BlockNo) | |||
870 | return false; | |||
871 | else if (Kind == Const) | |||
872 | return MO.isIdenticalTo(Other.MO); | |||
873 | ||||
874 | return true; | |||
875 | } | |||
876 | ||||
877 | bool operator!=(const DbgValue &Other) const { return !(*this == Other); } | |||
878 | }; | |||
879 | ||||
880 | /// Types for recording sets of variable fragments that overlap. For a given | |||
881 | /// local variable, we record all other fragments of that variable that could | |||
882 | /// overlap it, to reduce search time. | |||
883 | using FragmentOfVar = | |||
884 | std::pair<const DILocalVariable *, DIExpression::FragmentInfo>; | |||
885 | using OverlapMap = | |||
886 | DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>; | |||
887 | ||||
888 | /// Collection of DBG_VALUEs observed when traversing a block. Records each | |||
889 | /// variable and the value the DBG_VALUE refers to. Requires the machine value | |||
890 | /// location dataflow algorithm to have run already, so that values can be | |||
891 | /// identified. | |||
892 | class VLocTracker { | |||
893 | public: | |||
894 | /// Map DebugVariable to the latest Value it's defined to have. | |||
895 | /// Needs to be a MapVector because we determine order-in-the-input-MIR from | |||
896 | /// the order in this container. | |||
897 | /// We only retain the last DbgValue in each block for each variable, to | |||
898 | /// determine the blocks live-out variable value. The Vars container forms the | |||
899 | /// transfer function for this block, as part of the dataflow analysis. The | |||
900 | /// movement of values between locations inside of a block is handled at a | |||
901 | /// much later stage, in the TransferTracker class. | |||
902 | MapVector<DebugVariable, DbgValue> Vars; | |||
903 | DenseMap<DebugVariable, const DILocation *> Scopes; | |||
904 | MachineBasicBlock *MBB; | |||
905 | ||||
906 | public: | |||
907 | VLocTracker() {} | |||
908 | ||||
909 | void defVar(const MachineInstr &MI, const DbgValueProperties &Properties, | |||
910 | Optional<ValueIDNum> ID) { | |||
911 | assert(MI.isDebugValue() || MI.isDebugRef())((void)0); | |||
912 | DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), | |||
913 | MI.getDebugLoc()->getInlinedAt()); | |||
914 | DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def) | |||
915 | : DbgValue(Properties, DbgValue::Undef); | |||
916 | ||||
917 | // Attempt insertion; overwrite if it's already mapped. | |||
918 | auto Result = Vars.insert(std::make_pair(Var, Rec)); | |||
919 | if (!Result.second) | |||
920 | Result.first->second = Rec; | |||
921 | Scopes[Var] = MI.getDebugLoc().get(); | |||
922 | } | |||
923 | ||||
924 | void defVar(const MachineInstr &MI, const MachineOperand &MO) { | |||
925 | // Only DBG_VALUEs can define constant-valued variables. | |||
926 | assert(MI.isDebugValue())((void)0); | |||
927 | DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), | |||
928 | MI.getDebugLoc()->getInlinedAt()); | |||
929 | DbgValueProperties Properties(MI); | |||
930 | DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const); | |||
931 | ||||
932 | // Attempt insertion; overwrite if it's already mapped. | |||
933 | auto Result = Vars.insert(std::make_pair(Var, Rec)); | |||
934 | if (!Result.second) | |||
935 | Result.first->second = Rec; | |||
936 | Scopes[Var] = MI.getDebugLoc().get(); | |||
937 | } | |||
938 | }; | |||
939 | ||||
940 | /// Tracker for converting machine value locations and variable values into | |||
941 | /// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs | |||
942 | /// specifying block live-in locations and transfers within blocks. | |||
943 | /// | |||
944 | /// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker | |||
945 | /// and must be initialized with the set of variable values that are live-in to | |||
946 | /// the block. The caller then repeatedly calls process(). TransferTracker picks | |||
947 | /// out variable locations for the live-in variable values (if there _is_ a | |||
948 | /// location) and creates the corresponding DBG_VALUEs. Then, as the block is | |||
949 | /// stepped through, transfers of values between machine locations are | |||
950 | /// identified and if profitable, a DBG_VALUE created. | |||
951 | /// | |||
952 | /// This is where debug use-before-defs would be resolved: a variable with an | |||
953 | /// unavailable value could materialize in the middle of a block, when the | |||
954 | /// value becomes available. Or, we could detect clobbers and re-specify the | |||
955 | /// variable in a backup location. (XXX these are unimplemented). | |||
956 | class TransferTracker { | |||
957 | public: | |||
958 | const TargetInstrInfo *TII; | |||
959 | const TargetLowering *TLI; | |||
960 | /// This machine location tracker is assumed to always contain the up-to-date | |||
961 | /// value mapping for all machine locations. TransferTracker only reads | |||
962 | /// information from it. (XXX make it const?) | |||
963 | MLocTracker *MTracker; | |||
964 | MachineFunction &MF; | |||
965 | bool ShouldEmitDebugEntryValues; | |||
966 | ||||
967 | /// Record of all changes in variable locations at a block position. Awkwardly | |||
968 | /// we allow inserting either before or after the point: MBB != nullptr | |||
969 | /// indicates it's before, otherwise after. | |||
970 | struct Transfer { | |||
971 | MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes | |||
972 | MachineBasicBlock *MBB; /// non-null if we should insert after. | |||
973 | SmallVector<MachineInstr *, 4> Insts; /// Vector of DBG_VALUEs to insert. | |||
974 | }; | |||
975 | ||||
976 | struct LocAndProperties { | |||
977 | LocIdx Loc; | |||
978 | DbgValueProperties Properties; | |||
979 | }; | |||
980 | ||||
981 | /// Collection of transfers (DBG_VALUEs) to be inserted. | |||
982 | SmallVector<Transfer, 32> Transfers; | |||
983 | ||||
984 | /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences | |||
985 | /// between TransferTrackers view of variable locations and MLocTrackers. For | |||
986 | /// example, MLocTracker observes all clobbers, but TransferTracker lazily | |||
987 | /// does not. | |||
988 | std::vector<ValueIDNum> VarLocs; | |||
989 | ||||
990 | /// Map from LocIdxes to which DebugVariables are based that location. | |||
991 | /// Mantained while stepping through the block. Not accurate if | |||
992 | /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx]. | |||
993 | std::map<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs; | |||
994 | ||||
995 | /// Map from DebugVariable to it's current location and qualifying meta | |||
996 | /// information. To be used in conjunction with ActiveMLocs to construct | |||
997 | /// enough information for the DBG_VALUEs for a particular LocIdx. | |||
998 | DenseMap<DebugVariable, LocAndProperties> ActiveVLocs; | |||
999 | ||||
1000 | /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection. | |||
1001 | SmallVector<MachineInstr *, 4> PendingDbgValues; | |||
1002 | ||||
1003 | /// Record of a use-before-def: created when a value that's live-in to the | |||
1004 | /// current block isn't available in any machine location, but it will be | |||
1005 | /// defined in this block. | |||
1006 | struct UseBeforeDef { | |||
1007 | /// Value of this variable, def'd in block. | |||
1008 | ValueIDNum ID; | |||
1009 | /// Identity of this variable. | |||
1010 | DebugVariable Var; | |||
1011 | /// Additional variable properties. | |||
1012 | DbgValueProperties Properties; | |||
1013 | }; | |||
1014 | ||||
1015 | /// Map from instruction index (within the block) to the set of UseBeforeDefs | |||
1016 | /// that become defined at that instruction. | |||
1017 | DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs; | |||
1018 | ||||
1019 | /// The set of variables that are in UseBeforeDefs and can become a location | |||
1020 | /// once the relevant value is defined. An element being erased from this | |||
1021 | /// collection prevents the use-before-def materializing. | |||
1022 | DenseSet<DebugVariable> UseBeforeDefVariables; | |||
1023 | ||||
1024 | const TargetRegisterInfo &TRI; | |||
1025 | const BitVector &CalleeSavedRegs; | |||
1026 | ||||
1027 | TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker, | |||
1028 | MachineFunction &MF, const TargetRegisterInfo &TRI, | |||
1029 | const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC) | |||
1030 | : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI), | |||
1031 | CalleeSavedRegs(CalleeSavedRegs) { | |||
1032 | TLI = MF.getSubtarget().getTargetLowering(); | |||
1033 | auto &TM = TPC.getTM<TargetMachine>(); | |||
1034 | ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues(); | |||
1035 | } | |||
1036 | ||||
1037 | /// Load object with live-in variable values. \p mlocs contains the live-in | |||
1038 | /// values in each machine location, while \p vlocs the live-in variable | |||
1039 | /// values. This method picks variable locations for the live-in variables, | |||
1040 | /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other | |||
1041 | /// object fields to track variable locations as we step through the block. | |||
1042 | /// FIXME: could just examine mloctracker instead of passing in \p mlocs? | |||
1043 | void loadInlocs(MachineBasicBlock &MBB, ValueIDNum *MLocs, | |||
1044 | SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs, | |||
1045 | unsigned NumLocs) { | |||
1046 | ActiveMLocs.clear(); | |||
1047 | ActiveVLocs.clear(); | |||
1048 | VarLocs.clear(); | |||
1049 | VarLocs.reserve(NumLocs); | |||
1050 | UseBeforeDefs.clear(); | |||
1051 | UseBeforeDefVariables.clear(); | |||
1052 | ||||
1053 | auto isCalleeSaved = [&](LocIdx L) { | |||
1054 | unsigned Reg = MTracker->LocIdxToLocID[L]; | |||
1055 | if (Reg >= MTracker->NumRegs) | |||
1056 | return false; | |||
1057 | for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI) | |||
1058 | if (CalleeSavedRegs.test(*RAI)) | |||
1059 | return true; | |||
1060 | return false; | |||
1061 | }; | |||
1062 | ||||
1063 | // Map of the preferred location for each value. | |||
1064 | std::map<ValueIDNum, LocIdx> ValueToLoc; | |||
1065 | ||||
1066 | // Produce a map of value numbers to the current machine locs they live | |||
1067 | // in. When emulating VarLocBasedImpl, there should only be one | |||
1068 | // location; when not, we get to pick. | |||
1069 | for (auto Location : MTracker->locations()) { | |||
1070 | LocIdx Idx = Location.Idx; | |||
1071 | ValueIDNum &VNum = MLocs[Idx.asU64()]; | |||
1072 | VarLocs.push_back(VNum); | |||
1073 | auto it = ValueToLoc.find(VNum); | |||
1074 | // In order of preference, pick: | |||
1075 | // * Callee saved registers, | |||
1076 | // * Other registers, | |||
1077 | // * Spill slots. | |||
1078 | if (it == ValueToLoc.end() || MTracker->isSpill(it->second) || | |||
1079 | (!isCalleeSaved(it->second) && isCalleeSaved(Idx.asU64()))) { | |||
1080 | // Insert, or overwrite if insertion failed. | |||
1081 | auto PrefLocRes = ValueToLoc.insert(std::make_pair(VNum, Idx)); | |||
1082 | if (!PrefLocRes.second) | |||
1083 | PrefLocRes.first->second = Idx; | |||
1084 | } | |||
1085 | } | |||
1086 | ||||
1087 | // Now map variables to their picked LocIdxes. | |||
1088 | for (auto Var : VLocs) { | |||
1089 | if (Var.second.Kind == DbgValue::Const) { | |||
1090 | PendingDbgValues.push_back( | |||
1091 | emitMOLoc(Var.second.MO, Var.first, Var.second.Properties)); | |||
1092 | continue; | |||
1093 | } | |||
1094 | ||||
1095 | // If the value has no location, we can't make a variable location. | |||
1096 | const ValueIDNum &Num = Var.second.ID; | |||
1097 | auto ValuesPreferredLoc = ValueToLoc.find(Num); | |||
1098 | if (ValuesPreferredLoc == ValueToLoc.end()) { | |||
1099 | // If it's a def that occurs in this block, register it as a | |||
1100 | // use-before-def to be resolved as we step through the block. | |||
1101 | if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI()) | |||
1102 | addUseBeforeDef(Var.first, Var.second.Properties, Num); | |||
1103 | else | |||
1104 | recoverAsEntryValue(Var.first, Var.second.Properties, Num); | |||
1105 | continue; | |||
1106 | } | |||
1107 | ||||
1108 | LocIdx M = ValuesPreferredLoc->second; | |||
1109 | auto NewValue = LocAndProperties{M, Var.second.Properties}; | |||
1110 | auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue)); | |||
1111 | if (!Result.second) | |||
1112 | Result.first->second = NewValue; | |||
1113 | ActiveMLocs[M].insert(Var.first); | |||
1114 | PendingDbgValues.push_back( | |||
1115 | MTracker->emitLoc(M, Var.first, Var.second.Properties)); | |||
1116 | } | |||
1117 | flushDbgValues(MBB.begin(), &MBB); | |||
1118 | } | |||
1119 | ||||
1120 | /// Record that \p Var has value \p ID, a value that becomes available | |||
1121 | /// later in the function. | |||
1122 | void addUseBeforeDef(const DebugVariable &Var, | |||
1123 | const DbgValueProperties &Properties, ValueIDNum ID) { | |||
1124 | UseBeforeDef UBD = {ID, Var, Properties}; | |||
1125 | UseBeforeDefs[ID.getInst()].push_back(UBD); | |||
1126 | UseBeforeDefVariables.insert(Var); | |||
1127 | } | |||
1128 | ||||
1129 | /// After the instruction at index \p Inst and position \p pos has been | |||
1130 | /// processed, check whether it defines a variable value in a use-before-def. | |||
1131 | /// If so, and the variable value hasn't changed since the start of the | |||
1132 | /// block, create a DBG_VALUE. | |||
1133 | void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) { | |||
1134 | auto MIt = UseBeforeDefs.find(Inst); | |||
1135 | if (MIt == UseBeforeDefs.end()) | |||
1136 | return; | |||
1137 | ||||
1138 | for (auto &Use : MIt->second) { | |||
1139 | LocIdx L = Use.ID.getLoc(); | |||
1140 | ||||
1141 | // If something goes very wrong, we might end up labelling a COPY | |||
1142 | // instruction or similar with an instruction number, where it doesn't | |||
1143 | // actually define a new value, instead it moves a value. In case this | |||
1144 | // happens, discard. | |||
1145 | if (MTracker->LocIdxToIDNum[L] != Use.ID) | |||
1146 | continue; | |||
1147 | ||||
1148 | // If a different debug instruction defined the variable value / location | |||
1149 | // since the start of the block, don't materialize this use-before-def. | |||
1150 | if (!UseBeforeDefVariables.count(Use.Var)) | |||
1151 | continue; | |||
1152 | ||||
1153 | PendingDbgValues.push_back(MTracker->emitLoc(L, Use.Var, Use.Properties)); | |||
1154 | } | |||
1155 | flushDbgValues(pos, nullptr); | |||
1156 | } | |||
1157 | ||||
1158 | /// Helper to move created DBG_VALUEs into Transfers collection. | |||
1159 | void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) { | |||
1160 | if (PendingDbgValues.size() == 0) | |||
1161 | return; | |||
1162 | ||||
1163 | // Pick out the instruction start position. | |||
1164 | MachineBasicBlock::instr_iterator BundleStart; | |||
1165 | if (MBB && Pos == MBB->begin()) | |||
1166 | BundleStart = MBB->instr_begin(); | |||
1167 | else | |||
1168 | BundleStart = getBundleStart(Pos->getIterator()); | |||
1169 | ||||
1170 | Transfers.push_back({BundleStart, MBB, PendingDbgValues}); | |||
1171 | PendingDbgValues.clear(); | |||
1172 | } | |||
1173 | ||||
1174 | bool isEntryValueVariable(const DebugVariable &Var, | |||
1175 | const DIExpression *Expr) const { | |||
1176 | if (!Var.getVariable()->isParameter()) | |||
1177 | return false; | |||
1178 | ||||
1179 | if (Var.getInlinedAt()) | |||
1180 | return false; | |||
1181 | ||||
1182 | if (Expr->getNumElements() > 0) | |||
1183 | return false; | |||
1184 | ||||
1185 | return true; | |||
1186 | } | |||
1187 | ||||
1188 | bool isEntryValueValue(const ValueIDNum &Val) const { | |||
1189 | // Must be in entry block (block number zero), and be a PHI / live-in value. | |||
1190 | if (Val.getBlock() || !Val.isPHI()) | |||
1191 | return false; | |||
1192 | ||||
1193 | // Entry values must enter in a register. | |||
1194 | if (MTracker->isSpill(Val.getLoc())) | |||
1195 | return false; | |||
1196 | ||||
1197 | Register SP = TLI->getStackPointerRegisterToSaveRestore(); | |||
1198 | Register FP = TRI.getFrameRegister(MF); | |||
1199 | Register Reg = MTracker->LocIdxToLocID[Val.getLoc()]; | |||
1200 | return Reg != SP && Reg != FP; | |||
1201 | } | |||
1202 | ||||
1203 | bool recoverAsEntryValue(const DebugVariable &Var, DbgValueProperties &Prop, | |||
1204 | const ValueIDNum &Num) { | |||
1205 | // Is this variable location a candidate to be an entry value. First, | |||
1206 | // should we be trying this at all? | |||
1207 | if (!ShouldEmitDebugEntryValues) | |||
1208 | return false; | |||
1209 | ||||
1210 | // Is the variable appropriate for entry values (i.e., is a parameter). | |||
1211 | if (!isEntryValueVariable(Var, Prop.DIExpr)) | |||
1212 | return false; | |||
1213 | ||||
1214 | // Is the value assigned to this variable still the entry value? | |||
1215 | if (!isEntryValueValue(Num)) | |||
1216 | return false; | |||
1217 | ||||
1218 | // Emit a variable location using an entry value expression. | |||
1219 | DIExpression *NewExpr = | |||
1220 | DIExpression::prepend(Prop.DIExpr, DIExpression::EntryValue); | |||
1221 | Register Reg = MTracker->LocIdxToLocID[Num.getLoc()]; | |||
1222 | MachineOperand MO = MachineOperand::CreateReg(Reg, false); | |||
1223 | MO.setIsDebug(true); | |||
1224 | ||||
1225 | PendingDbgValues.push_back(emitMOLoc(MO, Var, {NewExpr, Prop.Indirect})); | |||
1226 | return true; | |||
1227 | } | |||
1228 | ||||
1229 | /// Change a variable value after encountering a DBG_VALUE inside a block. | |||
1230 | void redefVar(const MachineInstr &MI) { | |||
1231 | DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), | |||
1232 | MI.getDebugLoc()->getInlinedAt()); | |||
1233 | DbgValueProperties Properties(MI); | |||
1234 | ||||
1235 | const MachineOperand &MO = MI.getOperand(0); | |||
1236 | ||||
1237 | // Ignore non-register locations, we don't transfer those. | |||
1238 | if (!MO.isReg() || MO.getReg() == 0) { | |||
1239 | auto It = ActiveVLocs.find(Var); | |||
1240 | if (It != ActiveVLocs.end()) { | |||
1241 | ActiveMLocs[It->second.Loc].erase(Var); | |||
1242 | ActiveVLocs.erase(It); | |||
1243 | } | |||
1244 | // Any use-before-defs no longer apply. | |||
1245 | UseBeforeDefVariables.erase(Var); | |||
1246 | return; | |||
1247 | } | |||
1248 | ||||
1249 | Register Reg = MO.getReg(); | |||
1250 | LocIdx NewLoc = MTracker->getRegMLoc(Reg); | |||
1251 | redefVar(MI, Properties, NewLoc); | |||
1252 | } | |||
1253 | ||||
1254 | /// Handle a change in variable location within a block. Terminate the | |||
1255 | /// variables current location, and record the value it now refers to, so | |||
1256 | /// that we can detect location transfers later on. | |||
1257 | void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties, | |||
1258 | Optional<LocIdx> OptNewLoc) { | |||
1259 | DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), | |||
1260 | MI.getDebugLoc()->getInlinedAt()); | |||
1261 | // Any use-before-defs no longer apply. | |||
1262 | UseBeforeDefVariables.erase(Var); | |||
1263 | ||||
1264 | // Erase any previous location, | |||
1265 | auto It = ActiveVLocs.find(Var); | |||
1266 | if (It != ActiveVLocs.end()) | |||
1267 | ActiveMLocs[It->second.Loc].erase(Var); | |||
1268 | ||||
1269 | // If there _is_ no new location, all we had to do was erase. | |||
1270 | if (!OptNewLoc) | |||
1271 | return; | |||
1272 | LocIdx NewLoc = *OptNewLoc; | |||
1273 | ||||
1274 | // Check whether our local copy of values-by-location in #VarLocs is out of | |||
1275 | // date. Wipe old tracking data for the location if it's been clobbered in | |||
1276 | // the meantime. | |||
1277 | if (MTracker->getNumAtPos(NewLoc) != VarLocs[NewLoc.asU64()]) { | |||
1278 | for (auto &P : ActiveMLocs[NewLoc]) { | |||
1279 | ActiveVLocs.erase(P); | |||
1280 | } | |||
1281 | ActiveMLocs[NewLoc.asU64()].clear(); | |||
1282 | VarLocs[NewLoc.asU64()] = MTracker->getNumAtPos(NewLoc); | |||
1283 | } | |||
1284 | ||||
1285 | ActiveMLocs[NewLoc].insert(Var); | |||
1286 | if (It == ActiveVLocs.end()) { | |||
1287 | ActiveVLocs.insert( | |||
1288 | std::make_pair(Var, LocAndProperties{NewLoc, Properties})); | |||
1289 | } else { | |||
1290 | It->second.Loc = NewLoc; | |||
1291 | It->second.Properties = Properties; | |||
1292 | } | |||
1293 | } | |||
1294 | ||||
1295 | /// Account for a location \p mloc being clobbered. Examine the variable | |||
1296 | /// locations that will be terminated: and try to recover them by using | |||
1297 | /// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to | |||
1298 | /// explicitly terminate a location if it can't be recovered. | |||
1299 | void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos, | |||
1300 | bool MakeUndef = true) { | |||
1301 | auto ActiveMLocIt = ActiveMLocs.find(MLoc); | |||
1302 | if (ActiveMLocIt == ActiveMLocs.end()) | |||
1303 | return; | |||
1304 | ||||
1305 | // What was the old variable value? | |||
1306 | ValueIDNum OldValue = VarLocs[MLoc.asU64()]; | |||
1307 | VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue; | |||
1308 | ||||
1309 | // Examine the remaining variable locations: if we can find the same value | |||
1310 | // again, we can recover the location. | |||
1311 | Optional<LocIdx> NewLoc = None; | |||
1312 | for (auto Loc : MTracker->locations()) | |||
1313 | if (Loc.Value == OldValue) | |||
1314 | NewLoc = Loc.Idx; | |||
1315 | ||||
1316 | // If there is no location, and we weren't asked to make the variable | |||
1317 | // explicitly undef, then stop here. | |||
1318 | if (!NewLoc && !MakeUndef) { | |||
1319 | // Try and recover a few more locations with entry values. | |||
1320 | for (auto &Var : ActiveMLocIt->second) { | |||
1321 | auto &Prop = ActiveVLocs.find(Var)->second.Properties; | |||
1322 | recoverAsEntryValue(Var, Prop, OldValue); | |||
1323 | } | |||
1324 | flushDbgValues(Pos, nullptr); | |||
1325 | return; | |||
1326 | } | |||
1327 | ||||
1328 | // Examine all the variables based on this location. | |||
1329 | DenseSet<DebugVariable> NewMLocs; | |||
1330 | for (auto &Var : ActiveMLocIt->second) { | |||
1331 | auto ActiveVLocIt = ActiveVLocs.find(Var); | |||
1332 | // Re-state the variable location: if there's no replacement then NewLoc | |||
1333 | // is None and a $noreg DBG_VALUE will be created. Otherwise, a DBG_VALUE | |||
1334 | // identifying the alternative location will be emitted. | |||
1335 | const DIExpression *Expr = ActiveVLocIt->second.Properties.DIExpr; | |||
1336 | DbgValueProperties Properties(Expr, false); | |||
1337 | PendingDbgValues.push_back(MTracker->emitLoc(NewLoc, Var, Properties)); | |||
1338 | ||||
1339 | // Update machine locations <=> variable locations maps. Defer updating | |||
1340 | // ActiveMLocs to avoid invalidaing the ActiveMLocIt iterator. | |||
1341 | if (!NewLoc) { | |||
1342 | ActiveVLocs.erase(ActiveVLocIt); | |||
1343 | } else { | |||
1344 | ActiveVLocIt->second.Loc = *NewLoc; | |||
1345 | NewMLocs.insert(Var); | |||
1346 | } | |||
1347 | } | |||
1348 | ||||
1349 | // Commit any deferred ActiveMLoc changes. | |||
1350 | if (!NewMLocs.empty()) | |||
1351 | for (auto &Var : NewMLocs) | |||
1352 | ActiveMLocs[*NewLoc].insert(Var); | |||
1353 | ||||
1354 | // We lazily track what locations have which values; if we've found a new | |||
1355 | // location for the clobbered value, remember it. | |||
1356 | if (NewLoc) | |||
1357 | VarLocs[NewLoc->asU64()] = OldValue; | |||
1358 | ||||
1359 | flushDbgValues(Pos, nullptr); | |||
1360 | ||||
1361 | ActiveMLocIt->second.clear(); | |||
1362 | } | |||
1363 | ||||
1364 | /// Transfer variables based on \p Src to be based on \p Dst. This handles | |||
1365 | /// both register copies as well as spills and restores. Creates DBG_VALUEs | |||
1366 | /// describing the movement. | |||
1367 | void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) { | |||
1368 | // Does Src still contain the value num we expect? If not, it's been | |||
1369 | // clobbered in the meantime, and our variable locations are stale. | |||
1370 | if (VarLocs[Src.asU64()] != MTracker->getNumAtPos(Src)) | |||
1371 | return; | |||
1372 | ||||
1373 | // assert(ActiveMLocs[Dst].size() == 0); | |||
1374 | //^^^ Legitimate scenario on account of un-clobbered slot being assigned to? | |||
1375 | ActiveMLocs[Dst] = ActiveMLocs[Src]; | |||
1376 | VarLocs[Dst.asU64()] = VarLocs[Src.asU64()]; | |||
1377 | ||||
1378 | // For each variable based on Src; create a location at Dst. | |||
1379 | for (auto &Var : ActiveMLocs[Src]) { | |||
1380 | auto ActiveVLocIt = ActiveVLocs.find(Var); | |||
1381 | assert(ActiveVLocIt != ActiveVLocs.end())((void)0); | |||
1382 | ActiveVLocIt->second.Loc = Dst; | |||
1383 | ||||
1384 | assert(Dst != 0)((void)0); | |||
1385 | MachineInstr *MI = | |||
1386 | MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties); | |||
1387 | PendingDbgValues.push_back(MI); | |||
1388 | } | |||
1389 | ActiveMLocs[Src].clear(); | |||
1390 | flushDbgValues(Pos, nullptr); | |||
1391 | ||||
1392 | // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data | |||
1393 | // about the old location. | |||
1394 | if (EmulateOldLDV) | |||
1395 | VarLocs[Src.asU64()] = ValueIDNum::EmptyValue; | |||
1396 | } | |||
1397 | ||||
1398 | MachineInstrBuilder emitMOLoc(const MachineOperand &MO, | |||
1399 | const DebugVariable &Var, | |||
1400 | const DbgValueProperties &Properties) { | |||
1401 | DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, | |||
1402 | Var.getVariable()->getScope(), | |||
1403 | const_cast<DILocation *>(Var.getInlinedAt())); | |||
1404 | auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE)); | |||
1405 | MIB.add(MO); | |||
1406 | if (Properties.Indirect) | |||
1407 | MIB.addImm(0); | |||
1408 | else | |||
1409 | MIB.addReg(0); | |||
1410 | MIB.addMetadata(Var.getVariable()); | |||
1411 | MIB.addMetadata(Properties.DIExpr); | |||
1412 | return MIB; | |||
1413 | } | |||
1414 | }; | |||
1415 | ||||
1416 | class InstrRefBasedLDV : public LDVImpl { | |||
1417 | private: | |||
1418 | using FragmentInfo = DIExpression::FragmentInfo; | |||
1419 | using OptFragmentInfo = Optional<DIExpression::FragmentInfo>; | |||
1420 | ||||
1421 | // Helper while building OverlapMap, a map of all fragments seen for a given | |||
1422 | // DILocalVariable. | |||
1423 | using VarToFragments = | |||
1424 | DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>; | |||
1425 | ||||
1426 | /// Machine location/value transfer function, a mapping of which locations | |||
1427 | /// are assigned which new values. | |||
1428 | using MLocTransferMap = std::map<LocIdx, ValueIDNum>; | |||
1429 | ||||
1430 | /// Live in/out structure for the variable values: a per-block map of | |||
1431 | /// variables to their values. XXX, better name? | |||
1432 | using LiveIdxT = | |||
1433 | DenseMap<const MachineBasicBlock *, DenseMap<DebugVariable, DbgValue> *>; | |||
1434 | ||||
1435 | using VarAndLoc = std::pair<DebugVariable, DbgValue>; | |||
1436 | ||||
1437 | /// Type for a live-in value: the predecessor block, and its value. | |||
1438 | using InValueT = std::pair<MachineBasicBlock *, DbgValue *>; | |||
1439 | ||||
1440 | /// Vector (per block) of a collection (inner smallvector) of live-ins. | |||
1441 | /// Used as the result type for the variable value dataflow problem. | |||
1442 | using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>; | |||
1443 | ||||
1444 | const TargetRegisterInfo *TRI; | |||
1445 | const TargetInstrInfo *TII; | |||
1446 | const TargetFrameLowering *TFI; | |||
1447 | const MachineFrameInfo *MFI; | |||
1448 | BitVector CalleeSavedRegs; | |||
1449 | LexicalScopes LS; | |||
1450 | TargetPassConfig *TPC; | |||
1451 | ||||
1452 | /// Object to track machine locations as we step through a block. Could | |||
1453 | /// probably be a field rather than a pointer, as it's always used. | |||
1454 | MLocTracker *MTracker; | |||
1455 | ||||
1456 | /// Number of the current block LiveDebugValues is stepping through. | |||
1457 | unsigned CurBB; | |||
1458 | ||||
1459 | /// Number of the current instruction LiveDebugValues is evaluating. | |||
1460 | unsigned CurInst; | |||
1461 | ||||
1462 | /// Variable tracker -- listens to DBG_VALUEs occurring as InstrRefBasedImpl | |||
1463 | /// steps through a block. Reads the values at each location from the | |||
1464 | /// MLocTracker object. | |||
1465 | VLocTracker *VTracker; | |||
1466 | ||||
1467 | /// Tracker for transfers, listens to DBG_VALUEs and transfers of values | |||
1468 | /// between locations during stepping, creates new DBG_VALUEs when values move | |||
1469 | /// location. | |||
1470 | TransferTracker *TTracker; | |||
1471 | ||||
1472 | /// Blocks which are artificial, i.e. blocks which exclusively contain | |||
1473 | /// instructions without DebugLocs, or with line 0 locations. | |||
1474 | SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks; | |||
1475 | ||||
1476 | // Mapping of blocks to and from their RPOT order. | |||
1477 | DenseMap<unsigned int, MachineBasicBlock *> OrderToBB; | |||
1478 | DenseMap<MachineBasicBlock *, unsigned int> BBToOrder; | |||
1479 | DenseMap<unsigned, unsigned> BBNumToRPO; | |||
1480 | ||||
1481 | /// Pair of MachineInstr, and its 1-based offset into the containing block. | |||
1482 | using InstAndNum = std::pair<const MachineInstr *, unsigned>; | |||
1483 | /// Map from debug instruction number to the MachineInstr labelled with that | |||
1484 | /// number, and its location within the function. Used to transform | |||
1485 | /// instruction numbers in DBG_INSTR_REFs into machine value numbers. | |||
1486 | std::map<uint64_t, InstAndNum> DebugInstrNumToInstr; | |||
1487 | ||||
1488 | /// Record of where we observed a DBG_PHI instruction. | |||
1489 | class DebugPHIRecord { | |||
1490 | public: | |||
1491 | uint64_t InstrNum; ///< Instruction number of this DBG_PHI. | |||
1492 | MachineBasicBlock *MBB; ///< Block where DBG_PHI occurred. | |||
1493 | ValueIDNum ValueRead; ///< The value number read by the DBG_PHI. | |||
1494 | LocIdx ReadLoc; ///< Register/Stack location the DBG_PHI reads. | |||
1495 | ||||
1496 | operator unsigned() const { return InstrNum; } | |||
1497 | }; | |||
1498 | ||||
1499 | /// Map from instruction numbers defined by DBG_PHIs to a record of what that | |||
1500 | /// DBG_PHI read and where. Populated and edited during the machine value | |||
1501 | /// location problem -- we use LLVMs SSA Updater to fix changes by | |||
1502 | /// optimizations that destroy PHI instructions. | |||
1503 | SmallVector<DebugPHIRecord, 32> DebugPHINumToValue; | |||
1504 | ||||
1505 | // Map of overlapping variable fragments. | |||
1506 | OverlapMap OverlapFragments; | |||
1507 | VarToFragments SeenFragments; | |||
1508 | ||||
1509 | /// Tests whether this instruction is a spill to a stack slot. | |||
1510 | bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF); | |||
1511 | ||||
1512 | /// Decide if @MI is a spill instruction and return true if it is. We use 2 | |||
1513 | /// criteria to make this decision: | |||
1514 | /// - Is this instruction a store to a spill slot? | |||
1515 | /// - Is there a register operand that is both used and killed? | |||
1516 | /// TODO: Store optimization can fold spills into other stores (including | |||
1517 | /// other spills). We do not handle this yet (more than one memory operand). | |||
1518 | bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF, | |||
1519 | unsigned &Reg); | |||
1520 | ||||
1521 | /// If a given instruction is identified as a spill, return the spill slot | |||
1522 | /// and set \p Reg to the spilled register. | |||
1523 | Optional<SpillLoc> isRestoreInstruction(const MachineInstr &MI, | |||
1524 | MachineFunction *MF, unsigned &Reg); | |||
1525 | ||||
1526 | /// Given a spill instruction, extract the register and offset used to | |||
1527 | /// address the spill slot in a target independent way. | |||
1528 | SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI); | |||
1529 | ||||
1530 | /// Observe a single instruction while stepping through a block. | |||
1531 | void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr, | |||
1532 | ValueIDNum **MLiveIns = nullptr); | |||
1533 | ||||
1534 | /// Examines whether \p MI is a DBG_VALUE and notifies trackers. | |||
1535 | /// \returns true if MI was recognized and processed. | |||
1536 | bool transferDebugValue(const MachineInstr &MI); | |||
1537 | ||||
1538 | /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers. | |||
1539 | /// \returns true if MI was recognized and processed. | |||
1540 | bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts, | |||
1541 | ValueIDNum **MLiveIns); | |||
1542 | ||||
1543 | /// Stores value-information about where this PHI occurred, and what | |||
1544 | /// instruction number is associated with it. | |||
1545 | /// \returns true if MI was recognized and processed. | |||
1546 | bool transferDebugPHI(MachineInstr &MI); | |||
1547 | ||||
1548 | /// Examines whether \p MI is copy instruction, and notifies trackers. | |||
1549 | /// \returns true if MI was recognized and processed. | |||
1550 | bool transferRegisterCopy(MachineInstr &MI); | |||
1551 | ||||
1552 | /// Examines whether \p MI is stack spill or restore instruction, and | |||
1553 | /// notifies trackers. \returns true if MI was recognized and processed. | |||
1554 | bool transferSpillOrRestoreInst(MachineInstr &MI); | |||
1555 | ||||
1556 | /// Examines \p MI for any registers that it defines, and notifies trackers. | |||
1557 | void transferRegisterDef(MachineInstr &MI); | |||
1558 | ||||
1559 | /// Copy one location to the other, accounting for movement of subregisters | |||
1560 | /// too. | |||
1561 | void performCopy(Register Src, Register Dst); | |||
1562 | ||||
1563 | void accumulateFragmentMap(MachineInstr &MI); | |||
1564 | ||||
1565 | /// Determine the machine value number referred to by (potentially several) | |||
1566 | /// DBG_PHI instructions. Block duplication and tail folding can duplicate | |||
1567 | /// DBG_PHIs, shifting the position where values in registers merge, and | |||
1568 | /// forming another mini-ssa problem to solve. | |||
1569 | /// \p Here the position of a DBG_INSTR_REF seeking a machine value number | |||
1570 | /// \p InstrNum Debug instruction number defined by DBG_PHI instructions. | |||
1571 | /// \returns The machine value number at position Here, or None. | |||
1572 | Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF, | |||
1573 | ValueIDNum **MLiveOuts, | |||
1574 | ValueIDNum **MLiveIns, MachineInstr &Here, | |||
1575 | uint64_t InstrNum); | |||
1576 | ||||
1577 | /// Step through the function, recording register definitions and movements | |||
1578 | /// in an MLocTracker. Convert the observations into a per-block transfer | |||
1579 | /// function in \p MLocTransfer, suitable for using with the machine value | |||
1580 | /// location dataflow problem. | |||
1581 | void | |||
1582 | produceMLocTransferFunction(MachineFunction &MF, | |||
1583 | SmallVectorImpl<MLocTransferMap> &MLocTransfer, | |||
1584 | unsigned MaxNumBlocks); | |||
1585 | ||||
1586 | /// Solve the machine value location dataflow problem. Takes as input the | |||
1587 | /// transfer functions in \p MLocTransfer. Writes the output live-in and | |||
1588 | /// live-out arrays to the (initialized to zero) multidimensional arrays in | |||
1589 | /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block | |||
1590 | /// number, the inner by LocIdx. | |||
1591 | void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs, | |||
1592 | SmallVectorImpl<MLocTransferMap> &MLocTransfer); | |||
1593 | ||||
1594 | /// Perform a control flow join (lattice value meet) of the values in machine | |||
1595 | /// locations at \p MBB. Follows the algorithm described in the file-comment, | |||
1596 | /// reading live-outs of predecessors from \p OutLocs, the current live ins | |||
1597 | /// from \p InLocs, and assigning the newly computed live ins back into | |||
1598 | /// \p InLocs. \returns two bools -- the first indicates whether a change | |||
1599 | /// was made, the second whether a lattice downgrade occurred. If the latter | |||
1600 | /// is true, revisiting this block is necessary. | |||
1601 | std::tuple<bool, bool> | |||
1602 | mlocJoin(MachineBasicBlock &MBB, | |||
1603 | SmallPtrSet<const MachineBasicBlock *, 16> &Visited, | |||
1604 | ValueIDNum **OutLocs, ValueIDNum *InLocs); | |||
1605 | ||||
1606 | /// Solve the variable value dataflow problem, for a single lexical scope. | |||
1607 | /// Uses the algorithm from the file comment to resolve control flow joins, | |||
1608 | /// although there are extra hacks, see vlocJoin. Reads the | |||
1609 | /// locations of values from the \p MInLocs and \p MOutLocs arrays (see | |||
1610 | /// mlocDataflow) and reads the variable values transfer function from | |||
1611 | /// \p AllTheVlocs. Live-in and Live-out variable values are stored locally, | |||
1612 | /// with the live-ins permanently stored to \p Output once the fixedpoint is | |||
1613 | /// reached. | |||
1614 | /// \p VarsWeCareAbout contains a collection of the variables in \p Scope | |||
1615 | /// that we should be tracking. | |||
1616 | /// \p AssignBlocks contains the set of blocks that aren't in \p Scope, but | |||
1617 | /// which do contain DBG_VALUEs, which VarLocBasedImpl tracks locations | |||
1618 | /// through. | |||
1619 | void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc, | |||
1620 | const SmallSet<DebugVariable, 4> &VarsWeCareAbout, | |||
1621 | SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, | |||
1622 | LiveInsT &Output, ValueIDNum **MOutLocs, | |||
1623 | ValueIDNum **MInLocs, | |||
1624 | SmallVectorImpl<VLocTracker> &AllTheVLocs); | |||
1625 | ||||
1626 | /// Compute the live-ins to a block, considering control flow merges according | |||
1627 | /// to the method in the file comment. Live out and live in variable values | |||
1628 | /// are stored in \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB | |||
1629 | /// are computed and stored into \p VLOCInLocs. \returns true if the live-ins | |||
1630 | /// are modified. | |||
1631 | /// \p InLocsT Output argument, storage for calculated live-ins. | |||
1632 | /// \returns two bools -- the first indicates whether a change | |||
1633 | /// was made, the second whether a lattice downgrade occurred. If the latter | |||
1634 | /// is true, revisiting this block is necessary. | |||
1635 | std::tuple<bool, bool> | |||
1636 | vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, | |||
1637 | SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, | |||
1638 | unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars, | |||
1639 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, | |||
1640 | SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks, | |||
1641 | SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, | |||
1642 | DenseMap<DebugVariable, DbgValue> &InLocsT); | |||
1643 | ||||
1644 | /// Continue exploration of the variable-value lattice, as explained in the | |||
1645 | /// file-level comment. \p OldLiveInLocation contains the current | |||
1646 | /// exploration position, from which we need to descend further. \p Values | |||
1647 | /// contains the set of live-in values, \p CurBlockRPONum the RPO number of | |||
1648 | /// the current block, and \p CandidateLocations a set of locations that | |||
1649 | /// should be considered as PHI locations, if we reach the bottom of the | |||
1650 | /// lattice. \returns true if we should downgrade; the value is the agreeing | |||
1651 | /// value number in a non-backedge predecessor. | |||
1652 | bool vlocDowngradeLattice(const MachineBasicBlock &MBB, | |||
1653 | const DbgValue &OldLiveInLocation, | |||
1654 | const SmallVectorImpl<InValueT> &Values, | |||
1655 | unsigned CurBlockRPONum); | |||
1656 | ||||
1657 | /// For the given block and live-outs feeding into it, try to find a | |||
1658 | /// machine location where they all join. If a solution for all predecessors | |||
1659 | /// can't be found, a location where all non-backedge-predecessors join | |||
1660 | /// will be returned instead. While this method finds a join location, this | |||
1661 | /// says nothing as to whether it should be used. | |||
1662 | /// \returns Pair of value ID if found, and true when the correct value | |||
1663 | /// is available on all predecessor edges, or false if it's only available | |||
1664 | /// for non-backedge predecessors. | |||
1665 | std::tuple<Optional<ValueIDNum>, bool> | |||
1666 | pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var, | |||
1667 | const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, | |||
1668 | ValueIDNum **MInLocs, | |||
1669 | const SmallVectorImpl<MachineBasicBlock *> &BlockOrders); | |||
1670 | ||||
1671 | /// Given the solutions to the two dataflow problems, machine value locations | |||
1672 | /// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the | |||
1673 | /// TransferTracker class over the function to produce live-in and transfer | |||
1674 | /// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the | |||
1675 | /// order given by AllVarsNumbering -- this could be any stable order, but | |||
1676 | /// right now "order of appearence in function, when explored in RPO", so | |||
1677 | /// that we can compare explictly against VarLocBasedImpl. | |||
1678 | void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns, | |||
1679 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, | |||
1680 | DenseMap<DebugVariable, unsigned> &AllVarsNumbering, | |||
1681 | const TargetPassConfig &TPC); | |||
1682 | ||||
1683 | /// Boilerplate computation of some initial sets, artifical blocks and | |||
1684 | /// RPOT block ordering. | |||
1685 | void initialSetup(MachineFunction &MF); | |||
1686 | ||||
1687 | bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override; | |||
1688 | ||||
1689 | public: | |||
1690 | /// Default construct and initialize the pass. | |||
1691 | InstrRefBasedLDV(); | |||
1692 | ||||
1693 | LLVM_DUMP_METHOD__attribute__((noinline)) | |||
1694 | void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const; | |||
1695 | ||||
1696 | bool isCalleeSaved(LocIdx L) { | |||
1697 | unsigned Reg = MTracker->LocIdxToLocID[L]; | |||
1698 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) | |||
1699 | if (CalleeSavedRegs.test(*RAI)) | |||
1700 | return true; | |||
1701 | return false; | |||
1702 | } | |||
1703 | }; | |||
1704 | ||||
1705 | } // end anonymous namespace | |||
1706 | ||||
1707 | //===----------------------------------------------------------------------===// | |||
1708 | // Implementation | |||
1709 | //===----------------------------------------------------------------------===// | |||
1710 | ||||
1711 | ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX(2147483647 *2U +1U), UINT_MAX(2147483647 *2U +1U), UINT_MAX(2147483647 *2U +1U)}; | |||
1712 | ||||
1713 | /// Default construct and initialize the pass. | |||
1714 | InstrRefBasedLDV::InstrRefBasedLDV() {} | |||
1715 | ||||
1716 | //===----------------------------------------------------------------------===// | |||
1717 | // Debug Range Extension Implementation | |||
1718 | //===----------------------------------------------------------------------===// | |||
1719 | ||||
1720 | #ifndef NDEBUG1 | |||
1721 | // Something to restore in the future. | |||
1722 | // void InstrRefBasedLDV::printVarLocInMBB(..) | |||
1723 | #endif | |||
1724 | ||||
1725 | SpillLoc | |||
1726 | InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) { | |||
1727 | assert(MI.hasOneMemOperand() &&((void)0) | |||
1728 | "Spill instruction does not have exactly one memory operand?")((void)0); | |||
1729 | auto MMOI = MI.memoperands_begin(); | |||
1730 | const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue(); | |||
1731 | assert(PVal->kind() == PseudoSourceValue::FixedStack &&((void)0) | |||
1732 | "Inconsistent memory operand in spill instruction")((void)0); | |||
1733 | int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex(); | |||
1734 | const MachineBasicBlock *MBB = MI.getParent(); | |||
1735 | Register Reg; | |||
1736 | StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg); | |||
1737 | return {Reg, Offset}; | |||
1738 | } | |||
1739 | ||||
1740 | /// End all previous ranges related to @MI and start a new range from @MI | |||
1741 | /// if it is a DBG_VALUE instr. | |||
1742 | bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) { | |||
1743 | if (!MI.isDebugValue()) | |||
1744 | return false; | |||
1745 | ||||
1746 | const DILocalVariable *Var = MI.getDebugVariable(); | |||
1747 | const DIExpression *Expr = MI.getDebugExpression(); | |||
1748 | const DILocation *DebugLoc = MI.getDebugLoc(); | |||
1749 | const DILocation *InlinedAt = DebugLoc->getInlinedAt(); | |||
1750 | assert(Var->isValidLocationForIntrinsic(DebugLoc) &&((void)0) | |||
1751 | "Expected inlined-at fields to agree")((void)0); | |||
1752 | ||||
1753 | DebugVariable V(Var, Expr, InlinedAt); | |||
1754 | DbgValueProperties Properties(MI); | |||
1755 | ||||
1756 | // If there are no instructions in this lexical scope, do no location tracking | |||
1757 | // at all, this variable shouldn't get a legitimate location range. | |||
1758 | auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get()); | |||
1759 | if (Scope == nullptr) | |||
1760 | return true; // handled it; by doing nothing | |||
1761 | ||||
1762 | const MachineOperand &MO = MI.getOperand(0); | |||
1763 | ||||
1764 | // MLocTracker needs to know that this register is read, even if it's only | |||
1765 | // read by a debug inst. | |||
1766 | if (MO.isReg() && MO.getReg() != 0) | |||
1767 | (void)MTracker->readReg(MO.getReg()); | |||
1768 | ||||
1769 | // If we're preparing for the second analysis (variables), the machine value | |||
1770 | // locations are already solved, and we report this DBG_VALUE and the value | |||
1771 | // it refers to to VLocTracker. | |||
1772 | if (VTracker) { | |||
1773 | if (MO.isReg()) { | |||
1774 | // Feed defVar the new variable location, or if this is a | |||
1775 | // DBG_VALUE $noreg, feed defVar None. | |||
1776 | if (MO.getReg()) | |||
1777 | VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg())); | |||
1778 | else | |||
1779 | VTracker->defVar(MI, Properties, None); | |||
1780 | } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() || | |||
1781 | MI.getOperand(0).isCImm()) { | |||
1782 | VTracker->defVar(MI, MI.getOperand(0)); | |||
1783 | } | |||
1784 | } | |||
1785 | ||||
1786 | // If performing final tracking of transfers, report this variable definition | |||
1787 | // to the TransferTracker too. | |||
1788 | if (TTracker) | |||
1789 | TTracker->redefVar(MI); | |||
1790 | return true; | |||
1791 | } | |||
1792 | ||||
1793 | bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI, | |||
1794 | ValueIDNum **MLiveOuts, | |||
1795 | ValueIDNum **MLiveIns) { | |||
1796 | if (!MI.isDebugRef()) | |||
1797 | return false; | |||
1798 | ||||
1799 | // Only handle this instruction when we are building the variable value | |||
1800 | // transfer function. | |||
1801 | if (!VTracker) | |||
1802 | return false; | |||
1803 | ||||
1804 | unsigned InstNo = MI.getOperand(0).getImm(); | |||
1805 | unsigned OpNo = MI.getOperand(1).getImm(); | |||
1806 | ||||
1807 | const DILocalVariable *Var = MI.getDebugVariable(); | |||
1808 | const DIExpression *Expr = MI.getDebugExpression(); | |||
1809 | const DILocation *DebugLoc = MI.getDebugLoc(); | |||
1810 | const DILocation *InlinedAt = DebugLoc->getInlinedAt(); | |||
1811 | assert(Var->isValidLocationForIntrinsic(DebugLoc) &&((void)0) | |||
1812 | "Expected inlined-at fields to agree")((void)0); | |||
1813 | ||||
1814 | DebugVariable V(Var, Expr, InlinedAt); | |||
1815 | ||||
1816 | auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get()); | |||
1817 | if (Scope == nullptr) | |||
1818 | return true; // Handled by doing nothing. This variable is never in scope. | |||
1819 | ||||
1820 | const MachineFunction &MF = *MI.getParent()->getParent(); | |||
1821 | ||||
1822 | // Various optimizations may have happened to the value during codegen, | |||
1823 | // recorded in the value substitution table. Apply any substitutions to | |||
1824 | // the instruction / operand number in this DBG_INSTR_REF, and collect | |||
1825 | // any subregister extractions performed during optimization. | |||
1826 | ||||
1827 | // Create dummy substitution with Src set, for lookup. | |||
1828 | auto SoughtSub = | |||
1829 | MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0); | |||
1830 | ||||
1831 | SmallVector<unsigned, 4> SeenSubregs; | |||
1832 | auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub); | |||
1833 | while (LowerBoundIt != MF.DebugValueSubstitutions.end() && | |||
1834 | LowerBoundIt->Src == SoughtSub.Src) { | |||
1835 | std::tie(InstNo, OpNo) = LowerBoundIt->Dest; | |||
1836 | SoughtSub.Src = LowerBoundIt->Dest; | |||
1837 | if (unsigned Subreg = LowerBoundIt->Subreg) | |||
1838 | SeenSubregs.push_back(Subreg); | |||
1839 | LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub); | |||
1840 | } | |||
1841 | ||||
1842 | // Default machine value number is <None> -- if no instruction defines | |||
1843 | // the corresponding value, it must have been optimized out. | |||
1844 | Optional<ValueIDNum> NewID = None; | |||
1845 | ||||
1846 | // Try to lookup the instruction number, and find the machine value number | |||
1847 | // that it defines. It could be an instruction, or a PHI. | |||
1848 | auto InstrIt = DebugInstrNumToInstr.find(InstNo); | |||
1849 | auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(), | |||
1850 | DebugPHINumToValue.end(), InstNo); | |||
1851 | if (InstrIt != DebugInstrNumToInstr.end()) { | |||
1852 | const MachineInstr &TargetInstr = *InstrIt->second.first; | |||
1853 | uint64_t BlockNo = TargetInstr.getParent()->getNumber(); | |||
1854 | ||||
1855 | // Pick out the designated operand. | |||
1856 | assert(OpNo < TargetInstr.getNumOperands())((void)0); | |||
1857 | const MachineOperand &MO = TargetInstr.getOperand(OpNo); | |||
1858 | ||||
1859 | // Today, this can only be a register. | |||
1860 | assert(MO.isReg() && MO.isDef())((void)0); | |||
1861 | ||||
1862 | unsigned LocID = MTracker->getLocID(MO.getReg(), false); | |||
1863 | LocIdx L = MTracker->LocIDToLocIdx[LocID]; | |||
1864 | NewID = ValueIDNum(BlockNo, InstrIt->second.second, L); | |||
1865 | } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) { | |||
1866 | // It's actually a PHI value. Which value it is might not be obvious, use | |||
1867 | // the resolver helper to find out. | |||
1868 | NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns, | |||
1869 | MI, InstNo); | |||
1870 | } | |||
1871 | ||||
1872 | // Apply any subregister extractions, in reverse. We might have seen code | |||
1873 | // like this: | |||
1874 | // CALL64 @foo, implicit-def $rax | |||
1875 | // %0:gr64 = COPY $rax | |||
1876 | // %1:gr32 = COPY %0.sub_32bit | |||
1877 | // %2:gr16 = COPY %1.sub_16bit | |||
1878 | // %3:gr8 = COPY %2.sub_8bit | |||
1879 | // In which case each copy would have been recorded as a substitution with | |||
1880 | // a subregister qualifier. Apply those qualifiers now. | |||
1881 | if (NewID && !SeenSubregs.empty()) { | |||
1882 | unsigned Offset = 0; | |||
1883 | unsigned Size = 0; | |||
1884 | ||||
1885 | // Look at each subregister that we passed through, and progressively | |||
1886 | // narrow in, accumulating any offsets that occur. Substitutions should | |||
1887 | // only ever be the same or narrower width than what they read from; | |||
1888 | // iterate in reverse order so that we go from wide to small. | |||
1889 | for (unsigned Subreg : reverse(SeenSubregs)) { | |||
1890 | unsigned ThisSize = TRI->getSubRegIdxSize(Subreg); | |||
1891 | unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg); | |||
1892 | Offset += ThisOffset; | |||
1893 | Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize); | |||
1894 | } | |||
1895 | ||||
1896 | // If that worked, look for an appropriate subregister with the register | |||
1897 | // where the define happens. Don't look at values that were defined during | |||
1898 | // a stack write: we can't currently express register locations within | |||
1899 | // spills. | |||
1900 | LocIdx L = NewID->getLoc(); | |||
1901 | if (NewID && !MTracker->isSpill(L)) { | |||
1902 | // Find the register class for the register where this def happened. | |||
1903 | // FIXME: no index for this? | |||
1904 | Register Reg = MTracker->LocIdxToLocID[L]; | |||
1905 | const TargetRegisterClass *TRC = nullptr; | |||
1906 | for (auto *TRCI : TRI->regclasses()) | |||
1907 | if (TRCI->contains(Reg)) | |||
1908 | TRC = TRCI; | |||
1909 | assert(TRC && "Couldn't find target register class?")((void)0); | |||
1910 | ||||
1911 | // If the register we have isn't the right size or in the right place, | |||
1912 | // Try to find a subregister inside it. | |||
1913 | unsigned MainRegSize = TRI->getRegSizeInBits(*TRC); | |||
1914 | if (Size != MainRegSize || Offset) { | |||
1915 | // Enumerate all subregisters, searching. | |||
1916 | Register NewReg = 0; | |||
1917 | for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) { | |||
1918 | unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI); | |||
1919 | unsigned SubregSize = TRI->getSubRegIdxSize(Subreg); | |||
1920 | unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg); | |||
1921 | if (SubregSize == Size && SubregOffset == Offset) { | |||
1922 | NewReg = *SRI; | |||
1923 | break; | |||
1924 | } | |||
1925 | } | |||
1926 | ||||
1927 | // If we didn't find anything: there's no way to express our value. | |||
1928 | if (!NewReg) { | |||
1929 | NewID = None; | |||
1930 | } else { | |||
1931 | // Re-state the value as being defined within the subregister | |||
1932 | // that we found. | |||
1933 | LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg); | |||
1934 | NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc); | |||
1935 | } | |||
1936 | } | |||
1937 | } else { | |||
1938 | // If we can't handle subregisters, unset the new value. | |||
1939 | NewID = None; | |||
1940 | } | |||
1941 | } | |||
1942 | ||||
1943 | // We, we have a value number or None. Tell the variable value tracker about | |||
1944 | // it. The rest of this LiveDebugValues implementation acts exactly the same | |||
1945 | // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that | |||
1946 | // aren't immediately available). | |||
1947 | DbgValueProperties Properties(Expr, false); | |||
1948 | VTracker->defVar(MI, Properties, NewID); | |||
1949 | ||||
1950 | // If we're on the final pass through the function, decompose this INSTR_REF | |||
1951 | // into a plain DBG_VALUE. | |||
1952 | if (!TTracker) | |||
1953 | return true; | |||
1954 | ||||
1955 | // Pick a location for the machine value number, if such a location exists. | |||
1956 | // (This information could be stored in TransferTracker to make it faster). | |||
1957 | Optional<LocIdx> FoundLoc = None; | |||
1958 | for (auto Location : MTracker->locations()) { | |||
1959 | LocIdx CurL = Location.Idx; | |||
1960 | ValueIDNum ID = MTracker->LocIdxToIDNum[CurL]; | |||
1961 | if (NewID && ID == NewID) { | |||
1962 | // If this is the first location with that value, pick it. Otherwise, | |||
1963 | // consider whether it's a "longer term" location. | |||
1964 | if (!FoundLoc) { | |||
1965 | FoundLoc = CurL; | |||
1966 | continue; | |||
1967 | } | |||
1968 | ||||
1969 | if (MTracker->isSpill(CurL)) | |||
1970 | FoundLoc = CurL; // Spills are a longer term location. | |||
1971 | else if (!MTracker->isSpill(*FoundLoc) && | |||
1972 | !MTracker->isSpill(CurL) && | |||
1973 | !isCalleeSaved(*FoundLoc) && | |||
1974 | isCalleeSaved(CurL)) | |||
1975 | FoundLoc = CurL; // Callee saved regs are longer term than normal. | |||
1976 | } | |||
1977 | } | |||
1978 | ||||
1979 | // Tell transfer tracker that the variable value has changed. | |||
1980 | TTracker->redefVar(MI, Properties, FoundLoc); | |||
1981 | ||||
1982 | // If there was a value with no location; but the value is defined in a | |||
1983 | // later instruction in this block, this is a block-local use-before-def. | |||
1984 | if (!FoundLoc && NewID && NewID->getBlock() == CurBB && | |||
1985 | NewID->getInst() > CurInst) | |||
1986 | TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false}, *NewID); | |||
1987 | ||||
1988 | // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant. | |||
1989 | // This DBG_VALUE is potentially a $noreg / undefined location, if | |||
1990 | // FoundLoc is None. | |||
1991 | // (XXX -- could morph the DBG_INSTR_REF in the future). | |||
1992 | MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties); | |||
1993 | TTracker->PendingDbgValues.push_back(DbgMI); | |||
1994 | TTracker->flushDbgValues(MI.getIterator(), nullptr); | |||
1995 | return true; | |||
1996 | } | |||
1997 | ||||
1998 | bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) { | |||
1999 | if (!MI.isDebugPHI()) | |||
2000 | return false; | |||
2001 | ||||
2002 | // Analyse these only when solving the machine value location problem. | |||
2003 | if (VTracker || TTracker) | |||
2004 | return true; | |||
2005 | ||||
2006 | // First operand is the value location, either a stack slot or register. | |||
2007 | // Second is the debug instruction number of the original PHI. | |||
2008 | const MachineOperand &MO = MI.getOperand(0); | |||
2009 | unsigned InstrNum = MI.getOperand(1).getImm(); | |||
2010 | ||||
2011 | if (MO.isReg()) { | |||
2012 | // The value is whatever's currently in the register. Read and record it, | |||
2013 | // to be analysed later. | |||
2014 | Register Reg = MO.getReg(); | |||
2015 | ValueIDNum Num = MTracker->readReg(Reg); | |||
2016 | auto PHIRec = DebugPHIRecord( | |||
2017 | {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)}); | |||
2018 | DebugPHINumToValue.push_back(PHIRec); | |||
2019 | } else { | |||
2020 | // The value is whatever's in this stack slot. | |||
2021 | assert(MO.isFI())((void)0); | |||
2022 | unsigned FI = MO.getIndex(); | |||
2023 | ||||
2024 | // If the stack slot is dead, then this was optimized away. | |||
2025 | // FIXME: stack slot colouring should account for slots that get merged. | |||
2026 | if (MFI->isDeadObjectIndex(FI)) | |||
2027 | return true; | |||
2028 | ||||
2029 | // Identify this spill slot. | |||
2030 | Register Base; | |||
2031 | StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base); | |||
2032 | SpillLoc SL = {Base, Offs}; | |||
2033 | Optional<ValueIDNum> Num = MTracker->readSpill(SL); | |||
2034 | ||||
2035 | if (!Num) | |||
2036 | // Nothing ever writes to this slot. Curious, but nothing we can do. | |||
2037 | return true; | |||
2038 | ||||
2039 | // Record this DBG_PHI for later analysis. | |||
2040 | auto DbgPHI = DebugPHIRecord( | |||
2041 | {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)}); | |||
2042 | DebugPHINumToValue.push_back(DbgPHI); | |||
2043 | } | |||
2044 | ||||
2045 | return true; | |||
2046 | } | |||
2047 | ||||
2048 | void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) { | |||
2049 | // Meta Instructions do not affect the debug liveness of any register they | |||
2050 | // define. | |||
2051 | if (MI.isImplicitDef()) { | |||
2052 | // Except when there's an implicit def, and the location it's defining has | |||
2053 | // no value number. The whole point of an implicit def is to announce that | |||
2054 | // the register is live, without be specific about it's value. So define | |||
2055 | // a value if there isn't one already. | |||
2056 | ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg()); | |||
2057 | // Has a legitimate value -> ignore the implicit def. | |||
2058 | if (Num.getLoc() != 0) | |||
2059 | return; | |||
2060 | // Otherwise, def it here. | |||
2061 | } else if (MI.isMetaInstruction()) | |||
2062 | return; | |||
2063 | ||||
2064 | MachineFunction *MF = MI.getMF(); | |||
2065 | const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); | |||
2066 | Register SP = TLI->getStackPointerRegisterToSaveRestore(); | |||
2067 | ||||
2068 | // Find the regs killed by MI, and find regmasks of preserved regs. | |||
2069 | // Max out the number of statically allocated elements in `DeadRegs`, as this | |||
2070 | // prevents fallback to std::set::count() operations. | |||
2071 | SmallSet<uint32_t, 32> DeadRegs; | |||
2072 | SmallVector<const uint32_t *, 4> RegMasks; | |||
2073 | SmallVector<const MachineOperand *, 4> RegMaskPtrs; | |||
2074 | for (const MachineOperand &MO : MI.operands()) { | |||
2075 | // Determine whether the operand is a register def. | |||
2076 | if (MO.isReg() && MO.isDef() && MO.getReg() && | |||
2077 | Register::isPhysicalRegister(MO.getReg()) && | |||
2078 | !(MI.isCall() && MO.getReg() == SP)) { | |||
2079 | // Remove ranges of all aliased registers. | |||
2080 | for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) | |||
2081 | // FIXME: Can we break out of this loop early if no insertion occurs? | |||
2082 | DeadRegs.insert(*RAI); | |||
2083 | } else if (MO.isRegMask()) { | |||
2084 | RegMasks.push_back(MO.getRegMask()); | |||
2085 | RegMaskPtrs.push_back(&MO); | |||
2086 | } | |||
2087 | } | |||
2088 | ||||
2089 | // Tell MLocTracker about all definitions, of regmasks and otherwise. | |||
2090 | for (uint32_t DeadReg : DeadRegs) | |||
2091 | MTracker->defReg(DeadReg, CurBB, CurInst); | |||
2092 | ||||
2093 | for (auto *MO : RegMaskPtrs) | |||
2094 | MTracker->writeRegMask(MO, CurBB, CurInst); | |||
2095 | ||||
2096 | if (!TTracker) | |||
2097 | return; | |||
2098 | ||||
2099 | // When committing variable values to locations: tell transfer tracker that | |||
2100 | // we've clobbered things. It may be able to recover the variable from a | |||
2101 | // different location. | |||
2102 | ||||
2103 | // Inform TTracker about any direct clobbers. | |||
2104 | for (uint32_t DeadReg : DeadRegs) { | |||
2105 | LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg); | |||
2106 | TTracker->clobberMloc(Loc, MI.getIterator(), false); | |||
2107 | } | |||
2108 | ||||
2109 | // Look for any clobbers performed by a register mask. Only test locations | |||
2110 | // that are actually being tracked. | |||
2111 | for (auto L : MTracker->locations()) { | |||
2112 | // Stack locations can't be clobbered by regmasks. | |||
2113 | if (MTracker->isSpill(L.Idx)) | |||
2114 | continue; | |||
2115 | ||||
2116 | Register Reg = MTracker->LocIdxToLocID[L.Idx]; | |||
2117 | for (auto *MO : RegMaskPtrs) | |||
2118 | if (MO->clobbersPhysReg(Reg)) | |||
2119 | TTracker->clobberMloc(L.Idx, MI.getIterator(), false); | |||
2120 | } | |||
2121 | } | |||
2122 | ||||
2123 | void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) { | |||
2124 | ValueIDNum SrcValue = MTracker->readReg(SrcRegNum); | |||
2125 | ||||
2126 | MTracker->setReg(DstRegNum, SrcValue); | |||
2127 | ||||
2128 | // In all circumstances, re-def the super registers. It's definitely a new | |||
2129 | // value now. This doesn't uniquely identify the composition of subregs, for | |||
2130 | // example, two identical values in subregisters composed in different | |||
2131 | // places would not get equal value numbers. | |||
2132 | for (MCSuperRegIterator SRI(DstRegNum, TRI); SRI.isValid(); ++SRI) | |||
2133 | MTracker->defReg(*SRI, CurBB, CurInst); | |||
2134 | ||||
2135 | // If we're emulating VarLocBasedImpl, just define all the subregisters. | |||
2136 | // DBG_VALUEs of them will expect to be tracked from the DBG_VALUE, not | |||
2137 | // through prior copies. | |||
2138 | if (EmulateOldLDV) { | |||
2139 | for (MCSubRegIndexIterator DRI(DstRegNum, TRI); DRI.isValid(); ++DRI) | |||
2140 | MTracker->defReg(DRI.getSubReg(), CurBB, CurInst); | |||
2141 | return; | |||
2142 | } | |||
2143 | ||||
2144 | // Otherwise, actually copy subregisters from one location to another. | |||
2145 | // XXX: in addition, any subregisters of DstRegNum that don't line up with | |||
2146 | // the source register should be def'd. | |||
2147 | for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) { | |||
2148 | unsigned SrcSubReg = SRI.getSubReg(); | |||
2149 | unsigned SubRegIdx = SRI.getSubRegIndex(); | |||
2150 | unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx); | |||
2151 | if (!DstSubReg) | |||
2152 | continue; | |||
2153 | ||||
2154 | // Do copy. There are two matching subregisters, the source value should | |||
2155 | // have been def'd when the super-reg was, the latter might not be tracked | |||
2156 | // yet. | |||
2157 | // This will force SrcSubReg to be tracked, if it isn't yet. | |||
2158 | (void)MTracker->readReg(SrcSubReg); | |||
2159 | LocIdx SrcL = MTracker->getRegMLoc(SrcSubReg); | |||
2160 | assert(SrcL.asU64())((void)0); | |||
2161 | (void)MTracker->readReg(DstSubReg); | |||
2162 | LocIdx DstL = MTracker->getRegMLoc(DstSubReg); | |||
2163 | assert(DstL.asU64())((void)0); | |||
2164 | (void)DstL; | |||
2165 | ValueIDNum CpyValue = {SrcValue.getBlock(), SrcValue.getInst(), SrcL}; | |||
2166 | ||||
2167 | MTracker->setReg(DstSubReg, CpyValue); | |||
2168 | } | |||
2169 | } | |||
2170 | ||||
2171 | bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI, | |||
2172 | MachineFunction *MF) { | |||
2173 | // TODO: Handle multiple stores folded into one. | |||
2174 | if (!MI.hasOneMemOperand()) | |||
2175 | return false; | |||
2176 | ||||
2177 | if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII)) | |||
2178 | return false; // This is not a spill instruction, since no valid size was | |||
2179 | // returned from either function. | |||
2180 | ||||
2181 | return true; | |||
2182 | } | |||
2183 | ||||
2184 | bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI, | |||
2185 | MachineFunction *MF, unsigned &Reg) { | |||
2186 | if (!isSpillInstruction(MI, MF)) | |||
2187 | return false; | |||
2188 | ||||
2189 | int FI; | |||
2190 | Reg = TII->isStoreToStackSlotPostFE(MI, FI); | |||
2191 | return Reg != 0; | |||
2192 | } | |||
2193 | ||||
2194 | Optional<SpillLoc> | |||
2195 | InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI, | |||
2196 | MachineFunction *MF, unsigned &Reg) { | |||
2197 | if (!MI.hasOneMemOperand()) | |||
2198 | return None; | |||
2199 | ||||
2200 | // FIXME: Handle folded restore instructions with more than one memory | |||
2201 | // operand. | |||
2202 | if (MI.getRestoreSize(TII)) { | |||
2203 | Reg = MI.getOperand(0).getReg(); | |||
2204 | return extractSpillBaseRegAndOffset(MI); | |||
2205 | } | |||
2206 | return None; | |||
2207 | } | |||
2208 | ||||
2209 | bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) { | |||
2210 | // XXX -- it's too difficult to implement VarLocBasedImpl's stack location | |||
2211 | // limitations under the new model. Therefore, when comparing them, compare | |||
2212 | // versions that don't attempt spills or restores at all. | |||
2213 | if (EmulateOldLDV) | |||
2214 | return false; | |||
2215 | ||||
2216 | MachineFunction *MF = MI.getMF(); | |||
2217 | unsigned Reg; | |||
2218 | Optional<SpillLoc> Loc; | |||
2219 | ||||
2220 | LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();)do { } while (false); | |||
2221 | ||||
2222 | // First, if there are any DBG_VALUEs pointing at a spill slot that is | |||
2223 | // written to, terminate that variable location. The value in memory | |||
2224 | // will have changed. DbgEntityHistoryCalculator doesn't try to detect this. | |||
2225 | if (isSpillInstruction(MI, MF)) { | |||
2226 | Loc = extractSpillBaseRegAndOffset(MI); | |||
2227 | ||||
2228 | if (TTracker) { | |||
2229 | Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc); | |||
2230 | if (MLoc) { | |||
2231 | // Un-set this location before clobbering, so that we don't salvage | |||
2232 | // the variable location back to the same place. | |||
2233 | MTracker->setMLoc(*MLoc, ValueIDNum::EmptyValue); | |||
2234 | TTracker->clobberMloc(*MLoc, MI.getIterator()); | |||
2235 | } | |||
2236 | } | |||
2237 | } | |||
2238 | ||||
2239 | // Try to recognise spill and restore instructions that may transfer a value. | |||
2240 | if (isLocationSpill(MI, MF, Reg)) { | |||
2241 | Loc = extractSpillBaseRegAndOffset(MI); | |||
2242 | auto ValueID = MTracker->readReg(Reg); | |||
2243 | ||||
2244 | // If the location is empty, produce a phi, signify it's the live-in value. | |||
2245 | if (ValueID.getLoc() == 0) | |||
2246 | ValueID = {CurBB, 0, MTracker->getRegMLoc(Reg)}; | |||
2247 | ||||
2248 | MTracker->setSpill(*Loc, ValueID); | |||
2249 | auto OptSpillLocIdx = MTracker->getSpillMLoc(*Loc); | |||
2250 | assert(OptSpillLocIdx && "Spill slot set but has no LocIdx?")((void)0); | |||
2251 | LocIdx SpillLocIdx = *OptSpillLocIdx; | |||
2252 | ||||
2253 | // Tell TransferTracker about this spill, produce DBG_VALUEs for it. | |||
2254 | if (TTracker) | |||
2255 | TTracker->transferMlocs(MTracker->getRegMLoc(Reg), SpillLocIdx, | |||
2256 | MI.getIterator()); | |||
2257 | } else { | |||
2258 | if (!(Loc = isRestoreInstruction(MI, MF, Reg))) | |||
2259 | return false; | |||
2260 | ||||
2261 | // Is there a value to be restored? | |||
2262 | auto OptValueID = MTracker->readSpill(*Loc); | |||
2263 | if (OptValueID) { | |||
2264 | ValueIDNum ValueID = *OptValueID; | |||
2265 | LocIdx SpillLocIdx = *MTracker->getSpillMLoc(*Loc); | |||
2266 | // XXX -- can we recover sub-registers of this value? Until we can, first | |||
2267 | // overwrite all defs of the register being restored to. | |||
2268 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) | |||
2269 | MTracker->defReg(*RAI, CurBB, CurInst); | |||
2270 | ||||
2271 | // Now override the reg we're restoring to. | |||
2272 | MTracker->setReg(Reg, ValueID); | |||
2273 | ||||
2274 | // Report this restore to the transfer tracker too. | |||
2275 | if (TTracker) | |||
2276 | TTracker->transferMlocs(SpillLocIdx, MTracker->getRegMLoc(Reg), | |||
2277 | MI.getIterator()); | |||
2278 | } else { | |||
2279 | // There isn't anything in the location; not clear if this is a code path | |||
2280 | // that still runs. Def this register anyway just in case. | |||
2281 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) | |||
2282 | MTracker->defReg(*RAI, CurBB, CurInst); | |||
2283 | ||||
2284 | // Force the spill slot to be tracked. | |||
2285 | LocIdx L = MTracker->getOrTrackSpillLoc(*Loc); | |||
2286 | ||||
2287 | // Set the restored value to be a machine phi number, signifying that it's | |||
2288 | // whatever the spills live-in value is in this block. Definitely has | |||
2289 | // a LocIdx due to the setSpill above. | |||
2290 | ValueIDNum ValueID = {CurBB, 0, L}; | |||
2291 | MTracker->setReg(Reg, ValueID); | |||
2292 | MTracker->setSpill(*Loc, ValueID); | |||
2293 | } | |||
2294 | } | |||
2295 | return true; | |||
2296 | } | |||
2297 | ||||
2298 | bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) { | |||
2299 | auto DestSrc = TII->isCopyInstr(MI); | |||
2300 | if (!DestSrc) | |||
2301 | return false; | |||
2302 | ||||
2303 | const MachineOperand *DestRegOp = DestSrc->Destination; | |||
2304 | const MachineOperand *SrcRegOp = DestSrc->Source; | |||
2305 | ||||
2306 | auto isCalleeSavedReg = [&](unsigned Reg) { | |||
2307 | for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) | |||
2308 | if (CalleeSavedRegs.test(*RAI)) | |||
2309 | return true; | |||
2310 | return false; | |||
2311 | }; | |||
2312 | ||||
2313 | Register SrcReg = SrcRegOp->getReg(); | |||
2314 | Register DestReg = DestRegOp->getReg(); | |||
2315 | ||||
2316 | // Ignore identity copies. Yep, these make it as far as LiveDebugValues. | |||
2317 | if (SrcReg == DestReg) | |||
2318 | return true; | |||
2319 | ||||
2320 | // For emulating VarLocBasedImpl: | |||
2321 | // We want to recognize instructions where destination register is callee | |||
2322 | // saved register. If register that could be clobbered by the call is | |||
2323 | // included, there would be a great chance that it is going to be clobbered | |||
2324 | // soon. It is more likely that previous register, which is callee saved, is | |||
2325 | // going to stay unclobbered longer, even if it is killed. | |||
2326 | // | |||
2327 | // For InstrRefBasedImpl, we can track multiple locations per value, so | |||
2328 | // ignore this condition. | |||
2329 | if (EmulateOldLDV && !isCalleeSavedReg(DestReg)) | |||
2330 | return false; | |||
2331 | ||||
2332 | // InstrRefBasedImpl only followed killing copies. | |||
2333 | if (EmulateOldLDV && !SrcRegOp->isKill()) | |||
2334 | return false; | |||
2335 | ||||
2336 | // Copy MTracker info, including subregs if available. | |||
2337 | InstrRefBasedLDV::performCopy(SrcReg, DestReg); | |||
2338 | ||||
2339 | // Only produce a transfer of DBG_VALUE within a block where old LDV | |||
2340 | // would have. We might make use of the additional value tracking in some | |||
2341 | // other way, later. | |||
2342 | if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill()) | |||
2343 | TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg), | |||
2344 | MTracker->getRegMLoc(DestReg), MI.getIterator()); | |||
2345 | ||||
2346 | // VarLocBasedImpl would quit tracking the old location after copying. | |||
2347 | if (EmulateOldLDV && SrcReg != DestReg) | |||
2348 | MTracker->defReg(SrcReg, CurBB, CurInst); | |||
2349 | ||||
2350 | // Finally, the copy might have clobbered variables based on the destination | |||
2351 | // register. Tell TTracker about it, in case a backup location exists. | |||
2352 | if (TTracker) { | |||
2353 | for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) { | |||
2354 | LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI); | |||
2355 | TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false); | |||
2356 | } | |||
2357 | } | |||
2358 | ||||
2359 | return true; | |||
2360 | } | |||
2361 | ||||
2362 | /// Accumulate a mapping between each DILocalVariable fragment and other | |||
2363 | /// fragments of that DILocalVariable which overlap. This reduces work during | |||
2364 | /// the data-flow stage from "Find any overlapping fragments" to "Check if the | |||
2365 | /// known-to-overlap fragments are present". | |||
2366 | /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for | |||
2367 | /// fragment usage. | |||
2368 | void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) { | |||
2369 | DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(), | |||
2370 | MI.getDebugLoc()->getInlinedAt()); | |||
2371 | FragmentInfo ThisFragment = MIVar.getFragmentOrDefault(); | |||
2372 | ||||
2373 | // If this is the first sighting of this variable, then we are guaranteed | |||
2374 | // there are currently no overlapping fragments either. Initialize the set | |||
2375 | // of seen fragments, record no overlaps for the current one, and return. | |||
2376 | auto SeenIt = SeenFragments.find(MIVar.getVariable()); | |||
2377 | if (SeenIt == SeenFragments.end()) { | |||
2378 | SmallSet<FragmentInfo, 4> OneFragment; | |||
2379 | OneFragment.insert(ThisFragment); | |||
2380 | SeenFragments.insert({MIVar.getVariable(), OneFragment}); | |||
2381 | ||||
2382 | OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); | |||
2383 | return; | |||
2384 | } | |||
2385 | ||||
2386 | // If this particular Variable/Fragment pair already exists in the overlap | |||
2387 | // map, it has already been accounted for. | |||
2388 | auto IsInOLapMap = | |||
2389 | OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); | |||
2390 | if (!IsInOLapMap.second) | |||
2391 | return; | |||
2392 | ||||
2393 | auto &ThisFragmentsOverlaps = IsInOLapMap.first->second; | |||
2394 | auto &AllSeenFragments = SeenIt->second; | |||
2395 | ||||
2396 | // Otherwise, examine all other seen fragments for this variable, with "this" | |||
2397 | // fragment being a previously unseen fragment. Record any pair of | |||
2398 | // overlapping fragments. | |||
2399 | for (auto &ASeenFragment : AllSeenFragments) { | |||
2400 | // Does this previously seen fragment overlap? | |||
2401 | if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) { | |||
2402 | // Yes: Mark the current fragment as being overlapped. | |||
2403 | ThisFragmentsOverlaps.push_back(ASeenFragment); | |||
2404 | // Mark the previously seen fragment as being overlapped by the current | |||
2405 | // one. | |||
2406 | auto ASeenFragmentsOverlaps = | |||
2407 | OverlapFragments.find({MIVar.getVariable(), ASeenFragment}); | |||
2408 | assert(ASeenFragmentsOverlaps != OverlapFragments.end() &&((void)0) | |||
2409 | "Previously seen var fragment has no vector of overlaps")((void)0); | |||
2410 | ASeenFragmentsOverlaps->second.push_back(ThisFragment); | |||
2411 | } | |||
2412 | } | |||
2413 | ||||
2414 | AllSeenFragments.insert(ThisFragment); | |||
2415 | } | |||
2416 | ||||
2417 | void InstrRefBasedLDV::process(MachineInstr &MI, ValueIDNum **MLiveOuts, | |||
2418 | ValueIDNum **MLiveIns) { | |||
2419 | // Try to interpret an MI as a debug or transfer instruction. Only if it's | |||
2420 | // none of these should we interpret it's register defs as new value | |||
2421 | // definitions. | |||
2422 | if (transferDebugValue(MI)) | |||
2423 | return; | |||
2424 | if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns)) | |||
2425 | return; | |||
2426 | if (transferDebugPHI(MI)) | |||
2427 | return; | |||
2428 | if (transferRegisterCopy(MI)) | |||
2429 | return; | |||
2430 | if (transferSpillOrRestoreInst(MI)) | |||
2431 | return; | |||
2432 | transferRegisterDef(MI); | |||
2433 | } | |||
2434 | ||||
2435 | void InstrRefBasedLDV::produceMLocTransferFunction( | |||
2436 | MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer, | |||
2437 | unsigned MaxNumBlocks) { | |||
2438 | // Because we try to optimize around register mask operands by ignoring regs | |||
2439 | // that aren't currently tracked, we set up something ugly for later: RegMask | |||
2440 | // operands that are seen earlier than the first use of a register, still need | |||
2441 | // to clobber that register in the transfer function. But this information | |||
2442 | // isn't actively recorded. Instead, we track each RegMask used in each block, | |||
2443 | // and accumulated the clobbered but untracked registers in each block into | |||
2444 | // the following bitvector. Later, if new values are tracked, we can add | |||
2445 | // appropriate clobbers. | |||
2446 | SmallVector<BitVector, 32> BlockMasks; | |||
2447 | BlockMasks.resize(MaxNumBlocks); | |||
2448 | ||||
2449 | // Reserve one bit per register for the masks described above. | |||
2450 | unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs()); | |||
2451 | for (auto &BV : BlockMasks) | |||
2452 | BV.resize(TRI->getNumRegs(), true); | |||
2453 | ||||
2454 | // Step through all instructions and inhale the transfer function. | |||
2455 | for (auto &MBB : MF) { | |||
2456 | // Object fields that are read by trackers to know where we are in the | |||
2457 | // function. | |||
2458 | CurBB = MBB.getNumber(); | |||
2459 | CurInst = 1; | |||
2460 | ||||
2461 | // Set all machine locations to a PHI value. For transfer function | |||
2462 | // production only, this signifies the live-in value to the block. | |||
2463 | MTracker->reset(); | |||
2464 | MTracker->setMPhis(CurBB); | |||
2465 | ||||
2466 | // Step through each instruction in this block. | |||
2467 | for (auto &MI : MBB) { | |||
2468 | process(MI); | |||
2469 | // Also accumulate fragment map. | |||
2470 | if (MI.isDebugValue()) | |||
2471 | accumulateFragmentMap(MI); | |||
2472 | ||||
2473 | // Create a map from the instruction number (if present) to the | |||
2474 | // MachineInstr and its position. | |||
2475 | if (uint64_t InstrNo = MI.peekDebugInstrNum()) { | |||
2476 | auto InstrAndPos = std::make_pair(&MI, CurInst); | |||
2477 | auto InsertResult = | |||
2478 | DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos)); | |||
2479 | ||||
2480 | // There should never be duplicate instruction numbers. | |||
2481 | assert(InsertResult.second)((void)0); | |||
2482 | (void)InsertResult; | |||
2483 | } | |||
2484 | ||||
2485 | ++CurInst; | |||
2486 | } | |||
2487 | ||||
2488 | // Produce the transfer function, a map of machine location to new value. If | |||
2489 | // any machine location has the live-in phi value from the start of the | |||
2490 | // block, it's live-through and doesn't need recording in the transfer | |||
2491 | // function. | |||
2492 | for (auto Location : MTracker->locations()) { | |||
2493 | LocIdx Idx = Location.Idx; | |||
2494 | ValueIDNum &P = Location.Value; | |||
2495 | if (P.isPHI() && P.getLoc() == Idx.asU64()) | |||
2496 | continue; | |||
2497 | ||||
2498 | // Insert-or-update. | |||
2499 | auto &TransferMap = MLocTransfer[CurBB]; | |||
2500 | auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P)); | |||
2501 | if (!Result.second) | |||
2502 | Result.first->second = P; | |||
2503 | } | |||
2504 | ||||
2505 | // Accumulate any bitmask operands into the clobberred reg mask for this | |||
2506 | // block. | |||
2507 | for (auto &P : MTracker->Masks) { | |||
2508 | BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords); | |||
2509 | } | |||
2510 | } | |||
2511 | ||||
2512 | // Compute a bitvector of all the registers that are tracked in this block. | |||
2513 | const TargetLowering *TLI = MF.getSubtarget().getTargetLowering(); | |||
2514 | Register SP = TLI->getStackPointerRegisterToSaveRestore(); | |||
2515 | BitVector UsedRegs(TRI->getNumRegs()); | |||
2516 | for (auto Location : MTracker->locations()) { | |||
2517 | unsigned ID = MTracker->LocIdxToLocID[Location.Idx]; | |||
2518 | if (ID >= TRI->getNumRegs() || ID == SP) | |||
2519 | continue; | |||
2520 | UsedRegs.set(ID); | |||
2521 | } | |||
2522 | ||||
2523 | // Check that any regmask-clobber of a register that gets tracked, is not | |||
2524 | // live-through in the transfer function. It needs to be clobbered at the | |||
2525 | // very least. | |||
2526 | for (unsigned int I = 0; I < MaxNumBlocks; ++I) { | |||
2527 | BitVector &BV = BlockMasks[I]; | |||
2528 | BV.flip(); | |||
2529 | BV &= UsedRegs; | |||
2530 | // This produces all the bits that we clobber, but also use. Check that | |||
2531 | // they're all clobbered or at least set in the designated transfer | |||
2532 | // elem. | |||
2533 | for (unsigned Bit : BV.set_bits()) { | |||
2534 | unsigned ID = MTracker->getLocID(Bit, false); | |||
2535 | LocIdx Idx = MTracker->LocIDToLocIdx[ID]; | |||
2536 | auto &TransferMap = MLocTransfer[I]; | |||
2537 | ||||
2538 | // Install a value representing the fact that this location is effectively | |||
2539 | // written to in this block. As there's no reserved value, instead use | |||
2540 | // a value number that is never generated. Pick the value number for the | |||
2541 | // first instruction in the block, def'ing this location, which we know | |||
2542 | // this block never used anyway. | |||
2543 | ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx); | |||
2544 | auto Result = | |||
2545 | TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum)); | |||
2546 | if (!Result.second) { | |||
2547 | ValueIDNum &ValueID = Result.first->second; | |||
2548 | if (ValueID.getBlock() == I && ValueID.isPHI()) | |||
2549 | // It was left as live-through. Set it to clobbered. | |||
2550 | ValueID = NotGeneratedNum; | |||
2551 | } | |||
2552 | } | |||
2553 | } | |||
2554 | } | |||
2555 | ||||
2556 | std::tuple<bool, bool> | |||
2557 | InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB, | |||
2558 | SmallPtrSet<const MachineBasicBlock *, 16> &Visited, | |||
2559 | ValueIDNum **OutLocs, ValueIDNum *InLocs) { | |||
2560 | LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n")do { } while (false); | |||
2561 | bool Changed = false; | |||
2562 | bool DowngradeOccurred = false; | |||
2563 | ||||
2564 | // Collect predecessors that have been visited. Anything that hasn't been | |||
2565 | // visited yet is a backedge on the first iteration, and the meet of it's | |||
2566 | // lattice value for all locations will be unaffected. | |||
2567 | SmallVector<const MachineBasicBlock *, 8> BlockOrders; | |||
2568 | for (auto Pred : MBB.predecessors()) { | |||
2569 | if (Visited.count(Pred)) { | |||
2570 | BlockOrders.push_back(Pred); | |||
2571 | } | |||
2572 | } | |||
2573 | ||||
2574 | // Visit predecessors in RPOT order. | |||
2575 | auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) { | |||
2576 | return BBToOrder.find(A)->second < BBToOrder.find(B)->second; | |||
2577 | }; | |||
2578 | llvm::sort(BlockOrders, Cmp); | |||
2579 | ||||
2580 | // Skip entry block. | |||
2581 | if (BlockOrders.size() == 0) | |||
2582 | return std::tuple<bool, bool>(false, false); | |||
2583 | ||||
2584 | // Step through all machine locations, then look at each predecessor and | |||
2585 | // detect disagreements. | |||
2586 | unsigned ThisBlockRPO = BBToOrder.find(&MBB)->second; | |||
2587 | for (auto Location : MTracker->locations()) { | |||
2588 | LocIdx Idx = Location.Idx; | |||
2589 | // Pick out the first predecessors live-out value for this location. It's | |||
2590 | // guaranteed to be not a backedge, as we order by RPO. | |||
2591 | ValueIDNum BaseVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()]; | |||
2592 | ||||
2593 | // Some flags for whether there's a disagreement, and whether it's a | |||
2594 | // disagreement with a backedge or not. | |||
2595 | bool Disagree = false; | |||
2596 | bool NonBackEdgeDisagree = false; | |||
2597 | ||||
2598 | // Loop around everything that wasn't 'base'. | |||
2599 | for (unsigned int I = 1; I < BlockOrders.size(); ++I) { | |||
2600 | auto *MBB = BlockOrders[I]; | |||
2601 | if (BaseVal != OutLocs[MBB->getNumber()][Idx.asU64()]) { | |||
2602 | // Live-out of a predecessor disagrees with the first predecessor. | |||
2603 | Disagree = true; | |||
2604 | ||||
2605 | // Test whether it's a disagreemnt in the backedges or not. | |||
2606 | if (BBToOrder.find(MBB)->second < ThisBlockRPO) // might be self b/e | |||
2607 | NonBackEdgeDisagree = true; | |||
2608 | } | |||
2609 | } | |||
2610 | ||||
2611 | bool OverRide = false; | |||
2612 | if (Disagree && !NonBackEdgeDisagree) { | |||
2613 | // Only the backedges disagree. Consider demoting the livein | |||
2614 | // lattice value, as per the file level comment. The value we consider | |||
2615 | // demoting to is the value that the non-backedge predecessors agree on. | |||
2616 | // The order of values is that non-PHIs are \top, a PHI at this block | |||
2617 | // \bot, and phis between the two are ordered by their RPO number. | |||
2618 | // If there's no agreement, or we've already demoted to this PHI value | |||
2619 | // before, replace with a PHI value at this block. | |||
2620 | ||||
2621 | // Calculate order numbers: zero means normal def, nonzero means RPO | |||
2622 | // number. | |||
2623 | unsigned BaseBlockRPONum = BBNumToRPO[BaseVal.getBlock()] + 1; | |||
2624 | if (!BaseVal.isPHI()) | |||
2625 | BaseBlockRPONum = 0; | |||
2626 | ||||
2627 | ValueIDNum &InLocID = InLocs[Idx.asU64()]; | |||
2628 | unsigned InLocRPONum = BBNumToRPO[InLocID.getBlock()] + 1; | |||
2629 | if (!InLocID.isPHI()) | |||
2630 | InLocRPONum = 0; | |||
2631 | ||||
2632 | // Should we ignore the disagreeing backedges, and override with the | |||
2633 | // value the other predecessors agree on (in "base")? | |||
2634 | unsigned ThisBlockRPONum = BBNumToRPO[MBB.getNumber()] + 1; | |||
2635 | if (BaseBlockRPONum > InLocRPONum && BaseBlockRPONum < ThisBlockRPONum) { | |||
2636 | // Override. | |||
2637 | OverRide = true; | |||
2638 | DowngradeOccurred = true; | |||
2639 | } | |||
2640 | } | |||
2641 | // else: if we disagree in the non-backedges, then this is definitely | |||
2642 | // a control flow merge where different values merge. Make it a PHI. | |||
2643 | ||||
2644 | // Generate a phi... | |||
2645 | ValueIDNum PHI = {(uint64_t)MBB.getNumber(), 0, Idx}; | |||
2646 | ValueIDNum NewVal = (Disagree && !OverRide) ? PHI : BaseVal; | |||
2647 | if (InLocs[Idx.asU64()] != NewVal) { | |||
2648 | Changed |= true; | |||
2649 | InLocs[Idx.asU64()] = NewVal; | |||
2650 | } | |||
2651 | } | |||
2652 | ||||
2653 | // TODO: Reimplement NumInserted and NumRemoved. | |||
2654 | return std::tuple<bool, bool>(Changed, DowngradeOccurred); | |||
2655 | } | |||
2656 | ||||
2657 | void InstrRefBasedLDV::mlocDataflow( | |||
2658 | ValueIDNum **MInLocs, ValueIDNum **MOutLocs, | |||
2659 | SmallVectorImpl<MLocTransferMap> &MLocTransfer) { | |||
2660 | std::priority_queue<unsigned int, std::vector<unsigned int>, | |||
2661 | std::greater<unsigned int>> | |||
2662 | Worklist, Pending; | |||
2663 | ||||
2664 | // We track what is on the current and pending worklist to avoid inserting | |||
2665 | // the same thing twice. We could avoid this with a custom priority queue, | |||
2666 | // but this is probably not worth it. | |||
2667 | SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist; | |||
2668 | ||||
2669 | // Initialize worklist with every block to be visited. | |||
2670 | for (unsigned int I = 0; I < BBToOrder.size(); ++I) { | |||
2671 | Worklist.push(I); | |||
2672 | OnWorklist.insert(OrderToBB[I]); | |||
2673 | } | |||
2674 | ||||
2675 | MTracker->reset(); | |||
2676 | ||||
2677 | // Set inlocs for entry block -- each as a PHI at the entry block. Represents | |||
2678 | // the incoming value to the function. | |||
2679 | MTracker->setMPhis(0); | |||
2680 | for (auto Location : MTracker->locations()) | |||
2681 | MInLocs[0][Location.Idx.asU64()] = Location.Value; | |||
2682 | ||||
2683 | SmallPtrSet<const MachineBasicBlock *, 16> Visited; | |||
2684 | while (!Worklist.empty() || !Pending.empty()) { | |||
2685 | // Vector for storing the evaluated block transfer function. | |||
2686 | SmallVector<std::pair<LocIdx, ValueIDNum>, 32> ToRemap; | |||
2687 | ||||
2688 | while (!Worklist.empty()) { | |||
2689 | MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; | |||
2690 | CurBB = MBB->getNumber(); | |||
2691 | Worklist.pop(); | |||
2692 | ||||
2693 | // Join the values in all predecessor blocks. | |||
2694 | bool InLocsChanged, DowngradeOccurred; | |||
2695 | std::tie(InLocsChanged, DowngradeOccurred) = | |||
2696 | mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]); | |||
2697 | InLocsChanged |= Visited.insert(MBB).second; | |||
2698 | ||||
2699 | // If a downgrade occurred, book us in for re-examination on the next | |||
2700 | // iteration. | |||
2701 | if (DowngradeOccurred && OnPending.insert(MBB).second) | |||
2702 | Pending.push(BBToOrder[MBB]); | |||
2703 | ||||
2704 | // Don't examine transfer function if we've visited this loc at least | |||
2705 | // once, and inlocs haven't changed. | |||
2706 | if (!InLocsChanged) | |||
2707 | continue; | |||
2708 | ||||
2709 | // Load the current set of live-ins into MLocTracker. | |||
2710 | MTracker->loadFromArray(MInLocs[CurBB], CurBB); | |||
2711 | ||||
2712 | // Each element of the transfer function can be a new def, or a read of | |||
2713 | // a live-in value. Evaluate each element, and store to "ToRemap". | |||
2714 | ToRemap.clear(); | |||
2715 | for (auto &P : MLocTransfer[CurBB]) { | |||
2716 | if (P.second.getBlock() == CurBB && P.second.isPHI()) { | |||
2717 | // This is a movement of whatever was live in. Read it. | |||
2718 | ValueIDNum NewID = MTracker->getNumAtPos(P.second.getLoc()); | |||
2719 | ToRemap.push_back(std::make_pair(P.first, NewID)); | |||
2720 | } else { | |||
2721 | // It's a def. Just set it. | |||
2722 | assert(P.second.getBlock() == CurBB)((void)0); | |||
2723 | ToRemap.push_back(std::make_pair(P.first, P.second)); | |||
2724 | } | |||
2725 | } | |||
2726 | ||||
2727 | // Commit the transfer function changes into mloc tracker, which | |||
2728 | // transforms the contents of the MLocTracker into the live-outs. | |||
2729 | for (auto &P : ToRemap) | |||
2730 | MTracker->setMLoc(P.first, P.second); | |||
2731 | ||||
2732 | // Now copy out-locs from mloc tracker into out-loc vector, checking | |||
2733 | // whether changes have occurred. These changes can have come from both | |||
2734 | // the transfer function, and mlocJoin. | |||
2735 | bool OLChanged = false; | |||
2736 | for (auto Location : MTracker->locations()) { | |||
2737 | OLChanged |= MOutLocs[CurBB][Location.Idx.asU64()] != Location.Value; | |||
2738 | MOutLocs[CurBB][Location.Idx.asU64()] = Location.Value; | |||
2739 | } | |||
2740 | ||||
2741 | MTracker->reset(); | |||
2742 | ||||
2743 | // No need to examine successors again if out-locs didn't change. | |||
2744 | if (!OLChanged) | |||
2745 | continue; | |||
2746 | ||||
2747 | // All successors should be visited: put any back-edges on the pending | |||
2748 | // list for the next dataflow iteration, and any other successors to be | |||
2749 | // visited this iteration, if they're not going to be already. | |||
2750 | for (auto s : MBB->successors()) { | |||
2751 | // Does branching to this successor represent a back-edge? | |||
2752 | if (BBToOrder[s] > BBToOrder[MBB]) { | |||
2753 | // No: visit it during this dataflow iteration. | |||
2754 | if (OnWorklist.insert(s).second) | |||
2755 | Worklist.push(BBToOrder[s]); | |||
2756 | } else { | |||
2757 | // Yes: visit it on the next iteration. | |||
2758 | if (OnPending.insert(s).second) | |||
2759 | Pending.push(BBToOrder[s]); | |||
2760 | } | |||
2761 | } | |||
2762 | } | |||
2763 | ||||
2764 | Worklist.swap(Pending); | |||
2765 | std::swap(OnPending, OnWorklist); | |||
2766 | OnPending.clear(); | |||
2767 | // At this point, pending must be empty, since it was just the empty | |||
2768 | // worklist | |||
2769 | assert(Pending.empty() && "Pending should be empty")((void)0); | |||
2770 | } | |||
2771 | ||||
2772 | // Once all the live-ins don't change on mlocJoin(), we've reached a | |||
2773 | // fixedpoint. | |||
2774 | } | |||
2775 | ||||
2776 | bool InstrRefBasedLDV::vlocDowngradeLattice( | |||
2777 | const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation, | |||
2778 | const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) { | |||
2779 | // Ranking value preference: see file level comment, the highest rank is | |||
2780 | // a plain def, followed by PHI values in reverse post-order. Numerically, | |||
2781 | // we assign all defs the rank '0', all PHIs their blocks RPO number plus | |||
2782 | // one, and consider the lowest value the highest ranked. | |||
2783 | int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1; | |||
2784 | if (!OldLiveInLocation.ID.isPHI()) | |||
2785 | OldLiveInRank = 0; | |||
2786 | ||||
2787 | // Allow any unresolvable conflict to be over-ridden. | |||
2788 | if (OldLiveInLocation.Kind == DbgValue::NoVal) { | |||
2789 | // Although if it was an unresolvable conflict from _this_ block, then | |||
2790 | // all other seeking of downgrades and PHIs must have failed before hand. | |||
2791 | if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber()) | |||
2792 | return false; | |||
2793 | OldLiveInRank = INT_MIN(-2147483647 -1); | |||
2794 | } | |||
2795 | ||||
2796 | auto &InValue = *Values[0].second; | |||
2797 | ||||
2798 | if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal) | |||
2799 | return false; | |||
2800 | ||||
2801 | unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()]; | |||
2802 | int ThisRank = ThisRPO + 1; | |||
2803 | if (!InValue.ID.isPHI()) | |||
2804 | ThisRank = 0; | |||
2805 | ||||
2806 | // Too far down the lattice? | |||
2807 | if (ThisRPO >= CurBlockRPONum) | |||
2808 | return false; | |||
2809 | ||||
2810 | // Higher in the lattice than what we've already explored? | |||
2811 | if (ThisRank <= OldLiveInRank) | |||
2812 | return false; | |||
2813 | ||||
2814 | return true; | |||
2815 | } | |||
2816 | ||||
2817 | std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc( | |||
2818 | MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts, | |||
2819 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, | |||
2820 | const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) { | |||
2821 | // Collect a set of locations from predecessor where its live-out value can | |||
2822 | // be found. | |||
2823 | SmallVector<SmallVector<LocIdx, 4>, 8> Locs; | |||
2824 | unsigned NumLocs = MTracker->getNumLocs(); | |||
2825 | unsigned BackEdgesStart = 0; | |||
2826 | ||||
2827 | for (auto p : BlockOrders) { | |||
2828 | // Pick out where backedges start in the list of predecessors. Relies on | |||
2829 | // BlockOrders being sorted by RPO. | |||
2830 | if (BBToOrder[p] < BBToOrder[&MBB]) | |||
2831 | ++BackEdgesStart; | |||
2832 | ||||
2833 | // For each predecessor, create a new set of locations. | |||
2834 | Locs.resize(Locs.size() + 1); | |||
2835 | unsigned ThisBBNum = p->getNumber(); | |||
2836 | auto LiveOutMap = LiveOuts.find(p); | |||
2837 | if (LiveOutMap == LiveOuts.end()) | |||
2838 | // This predecessor isn't in scope, it must have no live-in/live-out | |||
2839 | // locations. | |||
2840 | continue; | |||
2841 | ||||
2842 | auto It = LiveOutMap->second->find(Var); | |||
2843 | if (It == LiveOutMap->second->end()) | |||
2844 | // There's no value recorded for this variable in this predecessor, | |||
2845 | // leave an empty set of locations. | |||
2846 | continue; | |||
2847 | ||||
2848 | const DbgValue &OutVal = It->second; | |||
2849 | ||||
2850 | if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal) | |||
2851 | // Consts and no-values cannot have locations we can join on. | |||
2852 | continue; | |||
2853 | ||||
2854 | assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def)((void)0); | |||
2855 | ValueIDNum ValToLookFor = OutVal.ID; | |||
2856 | ||||
2857 | // Search the live-outs of the predecessor for the specified value. | |||
2858 | for (unsigned int I = 0; I < NumLocs; ++I) { | |||
2859 | if (MOutLocs[ThisBBNum][I] == ValToLookFor) | |||
2860 | Locs.back().push_back(LocIdx(I)); | |||
2861 | } | |||
2862 | } | |||
2863 | ||||
2864 | // If there were no locations at all, return an empty result. | |||
2865 | if (Locs.empty()) | |||
2866 | return std::tuple<Optional<ValueIDNum>, bool>(None, false); | |||
2867 | ||||
2868 | // Lambda for seeking a common location within a range of location-sets. | |||
2869 | using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator; | |||
2870 | auto SeekLocation = | |||
2871 | [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> { | |||
2872 | // Starting with the first set of locations, take the intersection with | |||
2873 | // subsequent sets. | |||
2874 | SmallVector<LocIdx, 4> base = Locs[0]; | |||
2875 | for (auto &S : SearchRange) { | |||
2876 | SmallVector<LocIdx, 4> new_base; | |||
2877 | std::set_intersection(base.begin(), base.end(), S.begin(), S.end(), | |||
2878 | std::inserter(new_base, new_base.begin())); | |||
2879 | base = new_base; | |||
2880 | } | |||
2881 | if (base.empty()) | |||
2882 | return None; | |||
2883 | ||||
2884 | // We now have a set of LocIdxes that contain the right output value in | |||
2885 | // each of the predecessors. Pick the lowest; if there's a register loc, | |||
2886 | // that'll be it. | |||
2887 | return *base.begin(); | |||
2888 | }; | |||
2889 | ||||
2890 | // Search for a common location for all predecessors. If we can't, then fall | |||
2891 | // back to only finding a common location between non-backedge predecessors. | |||
2892 | bool ValidForAllLocs = true; | |||
2893 | auto TheLoc = SeekLocation(Locs); | |||
2894 | if (!TheLoc) { | |||
2895 | ValidForAllLocs = false; | |||
2896 | TheLoc = | |||
2897 | SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart)); | |||
2898 | } | |||
2899 | ||||
2900 | if (!TheLoc) | |||
2901 | return std::tuple<Optional<ValueIDNum>, bool>(None, false); | |||
2902 | ||||
2903 | // Return a PHI-value-number for the found location. | |||
2904 | LocIdx L = *TheLoc; | |||
2905 | ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L}; | |||
2906 | return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs); | |||
2907 | } | |||
2908 | ||||
2909 | std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin( | |||
2910 | MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, | |||
2911 | SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum, | |||
2912 | const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs, | |||
2913 | ValueIDNum **MInLocs, | |||
2914 | SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks, | |||
2915 | SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, | |||
2916 | DenseMap<DebugVariable, DbgValue> &InLocsT) { | |||
2917 | bool DowngradeOccurred = false; | |||
2918 | ||||
2919 | // To emulate VarLocBasedImpl, process this block if it's not in scope but | |||
2920 | // _does_ assign a variable value. No live-ins for this scope are transferred | |||
2921 | // in though, so we can return immediately. | |||
2922 | if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) { | |||
2923 | if (VLOCVisited) | |||
2924 | return std::tuple<bool, bool>(true, false); | |||
2925 | return std::tuple<bool, bool>(false, false); | |||
2926 | } | |||
2927 | ||||
2928 | LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n")do { } while (false); | |||
2929 | bool Changed = false; | |||
2930 | ||||
2931 | // Find any live-ins computed in a prior iteration. | |||
2932 | auto ILSIt = VLOCInLocs.find(&MBB); | |||
2933 | assert(ILSIt != VLOCInLocs.end())((void)0); | |||
2934 | auto &ILS = *ILSIt->second; | |||
2935 | ||||
2936 | // Order predecessors by RPOT order, for exploring them in that order. | |||
2937 | SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors()); | |||
2938 | ||||
2939 | auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) { | |||
2940 | return BBToOrder[A] < BBToOrder[B]; | |||
2941 | }; | |||
2942 | ||||
2943 | llvm::sort(BlockOrders, Cmp); | |||
2944 | ||||
2945 | unsigned CurBlockRPONum = BBToOrder[&MBB]; | |||
2946 | ||||
2947 | // Force a re-visit to loop heads in the first dataflow iteration. | |||
2948 | // FIXME: if we could "propose" Const values this wouldn't be needed, | |||
2949 | // because they'd need to be confirmed before being emitted. | |||
2950 | if (!BlockOrders.empty() && | |||
2951 | BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum && | |||
2952 | VLOCVisited) | |||
2953 | DowngradeOccurred = true; | |||
2954 | ||||
2955 | auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) { | |||
2956 | auto Result = InLocsT.insert(std::make_pair(DV, VR)); | |||
2957 | (void)Result; | |||
2958 | assert(Result.second)((void)0); | |||
2959 | }; | |||
2960 | ||||
2961 | auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) { | |||
2962 | DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal); | |||
2963 | ||||
2964 | ConfirmValue(Var, NoLocPHIVal); | |||
2965 | }; | |||
2966 | ||||
2967 | // Attempt to join the values for each variable. | |||
2968 | for (auto &Var : AllVars) { | |||
2969 | // Collect all the DbgValues for this variable. | |||
2970 | SmallVector<InValueT, 8> Values; | |||
2971 | bool Bail = false; | |||
2972 | unsigned BackEdgesStart = 0; | |||
2973 | for (auto p : BlockOrders) { | |||
2974 | // If the predecessor isn't in scope / to be explored, we'll never be | |||
2975 | // able to join any locations. | |||
2976 | if (!BlocksToExplore.contains(p)) { | |||
2977 | Bail = true; | |||
2978 | break; | |||
2979 | } | |||
2980 | ||||
2981 | // Don't attempt to handle unvisited predecessors: they're implicitly | |||
2982 | // "unknown"s in the lattice. | |||
2983 | if (VLOCVisited && !VLOCVisited->count(p)) | |||
2984 | continue; | |||
2985 | ||||
2986 | // If the predecessors OutLocs is absent, there's not much we can do. | |||
2987 | auto OL = VLOCOutLocs.find(p); | |||
2988 | if (OL == VLOCOutLocs.end()) { | |||
2989 | Bail = true; | |||
2990 | break; | |||
2991 | } | |||
2992 | ||||
2993 | // No live-out value for this predecessor also means we can't produce | |||
2994 | // a joined value. | |||
2995 | auto VIt = OL->second->find(Var); | |||
2996 | if (VIt == OL->second->end()) { | |||
2997 | Bail = true; | |||
2998 | break; | |||
2999 | } | |||
3000 | ||||
3001 | // Keep track of where back-edges begin in the Values vector. Relies on | |||
3002 | // BlockOrders being sorted by RPO. | |||
3003 | unsigned ThisBBRPONum = BBToOrder[p]; | |||
3004 | if (ThisBBRPONum < CurBlockRPONum) | |||
3005 | ++BackEdgesStart; | |||
3006 | ||||
3007 | Values.push_back(std::make_pair(p, &VIt->second)); | |||
3008 | } | |||
3009 | ||||
3010 | // If there were no values, or one of the predecessors couldn't have a | |||
3011 | // value, then give up immediately. It's not safe to produce a live-in | |||
3012 | // value. | |||
3013 | if (Bail || Values.size() == 0) | |||
3014 | continue; | |||
3015 | ||||
3016 | // Enumeration identifying the current state of the predecessors values. | |||
3017 | enum { | |||
3018 | Unset = 0, | |||
3019 | Agreed, // All preds agree on the variable value. | |||
3020 | PropDisagree, // All preds agree, but the value kind is Proposed in some. | |||
3021 | BEDisagree, // Only back-edges disagree on variable value. | |||
3022 | PHINeeded, // Non-back-edge predecessors have conflicing values. | |||
3023 | NoSolution // Conflicting Value metadata makes solution impossible. | |||
3024 | } OurState = Unset; | |||
3025 | ||||
3026 | // All (non-entry) blocks have at least one non-backedge predecessor. | |||
3027 | // Pick the variable value from the first of these, to compare against | |||
3028 | // all others. | |||
3029 | const DbgValue &FirstVal = *Values[0].second; | |||
3030 | const ValueIDNum &FirstID = FirstVal.ID; | |||
3031 | ||||
3032 | // Scan for variable values that can't be resolved: if they have different | |||
3033 | // DIExpressions, different indirectness, or are mixed constants / | |||
3034 | // non-constants. | |||
3035 | for (auto &V : Values) { | |||
3036 | if (V.second->Properties != FirstVal.Properties) | |||
3037 | OurState = NoSolution; | |||
3038 | if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const) | |||
3039 | OurState = NoSolution; | |||
3040 | } | |||
3041 | ||||
3042 | // Flags diagnosing _how_ the values disagree. | |||
3043 | bool NonBackEdgeDisagree = false; | |||
3044 | bool DisagreeOnPHINess = false; | |||
3045 | bool IDDisagree = false; | |||
3046 | bool Disagree = false; | |||
3047 | if (OurState == Unset) { | |||
3048 | for (auto &V : Values) { | |||
3049 | if (*V.second == FirstVal) | |||
3050 | continue; // No disagreement. | |||
3051 | ||||
3052 | Disagree = true; | |||
3053 | ||||
3054 | // Flag whether the value number actually diagrees. | |||
3055 | if (V.second->ID != FirstID) | |||
3056 | IDDisagree = true; | |||
3057 | ||||
3058 | // Distinguish whether disagreement happens in backedges or not. | |||
3059 | // Relies on Values (and BlockOrders) being sorted by RPO. | |||
3060 | unsigned ThisBBRPONum = BBToOrder[V.first]; | |||
3061 | if (ThisBBRPONum < CurBlockRPONum) | |||
3062 | NonBackEdgeDisagree = true; | |||
3063 | ||||
3064 | // Is there a difference in whether the value is definite or only | |||
3065 | // proposed? | |||
3066 | if (V.second->Kind != FirstVal.Kind && | |||
3067 | (V.second->Kind == DbgValue::Proposed || | |||
3068 | V.second->Kind == DbgValue::Def) && | |||
3069 | (FirstVal.Kind == DbgValue::Proposed || | |||
3070 | FirstVal.Kind == DbgValue::Def)) | |||
3071 | DisagreeOnPHINess = true; | |||
3072 | } | |||
3073 | ||||
3074 | // Collect those flags together and determine an overall state for | |||
3075 | // what extend the predecessors agree on a live-in value. | |||
3076 | if (!Disagree) | |||
3077 | OurState = Agreed; | |||
3078 | else if (!IDDisagree && DisagreeOnPHINess) | |||
3079 | OurState = PropDisagree; | |||
3080 | else if (!NonBackEdgeDisagree) | |||
3081 | OurState = BEDisagree; | |||
3082 | else | |||
3083 | OurState = PHINeeded; | |||
3084 | } | |||
3085 | ||||
3086 | // An extra indicator: if we only disagree on whether the value is a | |||
3087 | // Def, or proposed, then also flag whether that disagreement happens | |||
3088 | // in backedges only. | |||
3089 | bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess && | |||
3090 | !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def; | |||
3091 | ||||
3092 | const auto &Properties = FirstVal.Properties; | |||
3093 | ||||
3094 | auto OldLiveInIt = ILS.find(Var); | |||
3095 | const DbgValue *OldLiveInLocation = | |||
3096 | (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr; | |||
3097 | ||||
3098 | bool OverRide = false; | |||
3099 | if (OurState == BEDisagree && OldLiveInLocation) { | |||
3100 | // Only backedges disagree: we can consider downgrading. If there was a | |||
3101 | // previous live-in value, use it to work out whether the current | |||
3102 | // incoming value represents a lattice downgrade or not. | |||
3103 | OverRide = | |||
3104 | vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum); | |||
3105 | } | |||
3106 | ||||
3107 | // Use the current state of predecessor agreement and other flags to work | |||
3108 | // out what to do next. Possibilities include: | |||
3109 | // * Accept a value all predecessors agree on, or accept one that | |||
3110 | // represents a step down the exploration lattice, | |||
3111 | // * Use a PHI value number, if one can be found, | |||
3112 | // * Propose a PHI value number, and see if it gets confirmed later, | |||
3113 | // * Emit a 'NoVal' value, indicating we couldn't resolve anything. | |||
3114 | if (OurState == Agreed) { | |||
3115 | // Easiest solution: all predecessors agree on the variable value. | |||
3116 | ConfirmValue(Var, FirstVal); | |||
3117 | } else if (OurState == BEDisagree && OverRide) { | |||
3118 | // Only backedges disagree, and the other predecessors have produced | |||
3119 | // a new live-in value further down the exploration lattice. | |||
3120 | DowngradeOccurred = true; | |||
3121 | ConfirmValue(Var, FirstVal); | |||
3122 | } else if (OurState == PropDisagree) { | |||
3123 | // Predecessors agree on value, but some say it's only a proposed value. | |||
3124 | // Propagate it as proposed: unless it was proposed in this block, in | |||
3125 | // which case we're able to confirm the value. | |||
3126 | if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) { | |||
3127 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def)); | |||
3128 | } else if (PropOnlyInBEs) { | |||
3129 | // If only backedges disagree, a higher (in RPO) block confirmed this | |||
3130 | // location, and we need to propagate it into this loop. | |||
3131 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def)); | |||
3132 | } else { | |||
3133 | // Otherwise; a Def meeting a Proposed is still a Proposed. | |||
3134 | ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed)); | |||
3135 | } | |||
3136 | } else if ((OurState == PHINeeded || OurState == BEDisagree)) { | |||
3137 | // Predecessors disagree and can't be downgraded: this can only be | |||
3138 | // solved with a PHI. Use pickVPHILoc to go look for one. | |||
3139 | Optional<ValueIDNum> VPHI; | |||
3140 | bool AllEdgesVPHI = false; | |||
3141 | std::tie(VPHI, AllEdgesVPHI) = | |||
3142 | pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders); | |||
3143 | ||||
3144 | if (VPHI && AllEdgesVPHI) { | |||
3145 | // There's a PHI value that's valid for all predecessors -- we can use | |||
3146 | // it. If any of the non-backedge predecessors have proposed values | |||
3147 | // though, this PHI is also only proposed, until the predecessors are | |||
3148 | // confirmed. | |||
3149 | DbgValue::KindT K = DbgValue::Def; | |||
3150 | for (unsigned int I = 0; I < BackEdgesStart; ++I) | |||
3151 | if (Values[I].second->Kind == DbgValue::Proposed) | |||
3152 | K = DbgValue::Proposed; | |||
3153 | ||||
3154 | ConfirmValue(Var, DbgValue(*VPHI, Properties, K)); | |||
3155 | } else if (VPHI) { | |||
3156 | // There's a PHI value, but it's only legal for backedges. Leave this | |||
3157 | // as a proposed PHI value: it might come back on the backedges, | |||
3158 | // and allow us to confirm it in the future. | |||
3159 | DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed); | |||
3160 | ConfirmValue(Var, NoBEValue); | |||
3161 | } else { | |||
3162 | ConfirmNoVal(Var, Properties); | |||
3163 | } | |||
3164 | } else { | |||
3165 | // Otherwise: we don't know. Emit a "phi but no real loc" phi. | |||
3166 | ConfirmNoVal(Var, Properties); | |||
3167 | } | |||
3168 | } | |||
3169 | ||||
3170 | // Store newly calculated in-locs into VLOCInLocs, if they've changed. | |||
3171 | Changed = ILS != InLocsT; | |||
3172 | if (Changed) | |||
3173 | ILS = InLocsT; | |||
3174 | ||||
3175 | return std::tuple<bool, bool>(Changed, DowngradeOccurred); | |||
3176 | } | |||
3177 | ||||
3178 | void InstrRefBasedLDV::vlocDataflow( | |||
3179 | const LexicalScope *Scope, const DILocation *DILoc, | |||
3180 | const SmallSet<DebugVariable, 4> &VarsWeCareAbout, | |||
3181 | SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output, | |||
3182 | ValueIDNum **MOutLocs, ValueIDNum **MInLocs, | |||
3183 | SmallVectorImpl<VLocTracker> &AllTheVLocs) { | |||
3184 | // This method is much like mlocDataflow: but focuses on a single | |||
3185 | // LexicalScope at a time. Pick out a set of blocks and variables that are | |||
3186 | // to have their value assignments solved, then run our dataflow algorithm | |||
3187 | // until a fixedpoint is reached. | |||
3188 | std::priority_queue<unsigned int, std::vector<unsigned int>, | |||
3189 | std::greater<unsigned int>> | |||
3190 | Worklist, Pending; | |||
3191 | SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending; | |||
3192 | ||||
3193 | // The set of blocks we'll be examining. | |||
3194 | SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore; | |||
3195 | ||||
3196 | // The order in which to examine them (RPO). | |||
3197 | SmallVector<MachineBasicBlock *, 8> BlockOrders; | |||
3198 | ||||
3199 | // RPO ordering function. | |||
3200 | auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) { | |||
3201 | return BBToOrder[A] < BBToOrder[B]; | |||
3202 | }; | |||
3203 | ||||
3204 | LS.getMachineBasicBlocks(DILoc, BlocksToExplore); | |||
3205 | ||||
3206 | // A separate container to distinguish "blocks we're exploring" versus | |||
3207 | // "blocks that are potentially in scope. See comment at start of vlocJoin. | |||
3208 | SmallPtrSet<const MachineBasicBlock *, 8> InScopeBlocks = BlocksToExplore; | |||
3209 | ||||
3210 | // Old LiveDebugValues tracks variable locations that come out of blocks | |||
3211 | // not in scope, where DBG_VALUEs occur. This is something we could | |||
3212 | // legitimately ignore, but lets allow it for now. | |||
3213 | if (EmulateOldLDV) | |||
3214 | BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end()); | |||
3215 | ||||
3216 | // We also need to propagate variable values through any artificial blocks | |||
3217 | // that immediately follow blocks in scope. | |||
3218 | DenseSet<const MachineBasicBlock *> ToAdd; | |||
3219 | ||||
3220 | // Helper lambda: For a given block in scope, perform a depth first search | |||
3221 | // of all the artificial successors, adding them to the ToAdd collection. | |||
3222 | auto AccumulateArtificialBlocks = | |||
3223 | [this, &ToAdd, &BlocksToExplore, | |||
3224 | &InScopeBlocks](const MachineBasicBlock *MBB) { | |||
3225 | // Depth-first-search state: each node is a block and which successor | |||
3226 | // we're currently exploring. | |||
3227 | SmallVector<std::pair<const MachineBasicBlock *, | |||
3228 | MachineBasicBlock::const_succ_iterator>, | |||
3229 | 8> | |||
3230 | DFS; | |||
3231 | ||||
3232 | // Find any artificial successors not already tracked. | |||
3233 | for (auto *succ : MBB->successors()) { | |||
3234 | if (BlocksToExplore.count(succ) || InScopeBlocks.count(succ)) | |||
3235 | continue; | |||
3236 | if (!ArtificialBlocks.count(succ)) | |||
3237 | continue; | |||
3238 | DFS.push_back(std::make_pair(succ, succ->succ_begin())); | |||
3239 | ToAdd.insert(succ); | |||
3240 | } | |||
3241 | ||||
3242 | // Search all those blocks, depth first. | |||
3243 | while (!DFS.empty()) { | |||
3244 | const MachineBasicBlock *CurBB = DFS.back().first; | |||
3245 | MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second; | |||
3246 | // Walk back if we've explored this blocks successors to the end. | |||
3247 | if (CurSucc == CurBB->succ_end()) { | |||
3248 | DFS.pop_back(); | |||
3249 | continue; | |||
3250 | } | |||
3251 | ||||
3252 | // If the current successor is artificial and unexplored, descend into | |||
3253 | // it. | |||
3254 | if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) { | |||
3255 | DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin())); | |||
3256 | ToAdd.insert(*CurSucc); | |||
3257 | continue; | |||
3258 | } | |||
3259 | ||||
3260 | ++CurSucc; | |||
3261 | } | |||
3262 | }; | |||
3263 | ||||
3264 | // Search in-scope blocks and those containing a DBG_VALUE from this scope | |||
3265 | // for artificial successors. | |||
3266 | for (auto *MBB : BlocksToExplore) | |||
3267 | AccumulateArtificialBlocks(MBB); | |||
3268 | for (auto *MBB : InScopeBlocks) | |||
3269 | AccumulateArtificialBlocks(MBB); | |||
3270 | ||||
3271 | BlocksToExplore.insert(ToAdd.begin(), ToAdd.end()); | |||
3272 | InScopeBlocks.insert(ToAdd.begin(), ToAdd.end()); | |||
3273 | ||||
3274 | // Single block scope: not interesting! No propagation at all. Note that | |||
3275 | // this could probably go above ArtificialBlocks without damage, but | |||
3276 | // that then produces output differences from original-live-debug-values, | |||
3277 | // which propagates from a single block into many artificial ones. | |||
3278 | if (BlocksToExplore.size() == 1) | |||
3279 | return; | |||
3280 | ||||
3281 | // Picks out relevants blocks RPO order and sort them. | |||
3282 | for (auto *MBB : BlocksToExplore) | |||
3283 | BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB)); | |||
3284 | ||||
3285 | llvm::sort(BlockOrders, Cmp); | |||
3286 | unsigned NumBlocks = BlockOrders.size(); | |||
3287 | ||||
3288 | // Allocate some vectors for storing the live ins and live outs. Large. | |||
3289 | SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts; | |||
3290 | LiveIns.resize(NumBlocks); | |||
3291 | LiveOuts.resize(NumBlocks); | |||
3292 | ||||
3293 | // Produce by-MBB indexes of live-in/live-outs, to ease lookup within | |||
3294 | // vlocJoin. | |||
3295 | LiveIdxT LiveOutIdx, LiveInIdx; | |||
3296 | LiveOutIdx.reserve(NumBlocks); | |||
3297 | LiveInIdx.reserve(NumBlocks); | |||
3298 | for (unsigned I = 0; I < NumBlocks; ++I) { | |||
3299 | LiveOutIdx[BlockOrders[I]] = &LiveOuts[I]; | |||
3300 | LiveInIdx[BlockOrders[I]] = &LiveIns[I]; | |||
3301 | } | |||
3302 | ||||
3303 | for (auto *MBB : BlockOrders) { | |||
3304 | Worklist.push(BBToOrder[MBB]); | |||
3305 | OnWorklist.insert(MBB); | |||
3306 | } | |||
3307 | ||||
3308 | // Iterate over all the blocks we selected, propagating variable values. | |||
3309 | bool FirstTrip = true; | |||
3310 | SmallPtrSet<const MachineBasicBlock *, 16> VLOCVisited; | |||
3311 | while (!Worklist.empty() || !Pending.empty()) { | |||
3312 | while (!Worklist.empty()) { | |||
3313 | auto *MBB = OrderToBB[Worklist.top()]; | |||
3314 | CurBB = MBB->getNumber(); | |||
3315 | Worklist.pop(); | |||
3316 | ||||
3317 | DenseMap<DebugVariable, DbgValue> JoinedInLocs; | |||
3318 | ||||
3319 | // Join values from predecessors. Updates LiveInIdx, and writes output | |||
3320 | // into JoinedInLocs. | |||
3321 | bool InLocsChanged, DowngradeOccurred; | |||
3322 | std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin( | |||
3323 | *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr, | |||
3324 | CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks, | |||
3325 | BlocksToExplore, JoinedInLocs); | |||
3326 | ||||
3327 | bool FirstVisit = VLOCVisited.insert(MBB).second; | |||
3328 | ||||
3329 | // Always explore transfer function if inlocs changed, or if we've not | |||
3330 | // visited this block before. | |||
3331 | InLocsChanged |= FirstVisit; | |||
3332 | ||||
3333 | // If a downgrade occurred, book us in for re-examination on the next | |||
3334 | // iteration. | |||
3335 | if (DowngradeOccurred && OnPending.insert(MBB).second) | |||
3336 | Pending.push(BBToOrder[MBB]); | |||
3337 | ||||
3338 | if (!InLocsChanged) | |||
3339 | continue; | |||
3340 | ||||
3341 | // Do transfer function. | |||
3342 | auto &VTracker = AllTheVLocs[MBB->getNumber()]; | |||
3343 | for (auto &Transfer : VTracker.Vars) { | |||
3344 | // Is this var we're mangling in this scope? | |||
3345 | if (VarsWeCareAbout.count(Transfer.first)) { | |||
3346 | // Erase on empty transfer (DBG_VALUE $noreg). | |||
3347 | if (Transfer.second.Kind == DbgValue::Undef) { | |||
3348 | JoinedInLocs.erase(Transfer.first); | |||
3349 | } else { | |||
3350 | // Insert new variable value; or overwrite. | |||
3351 | auto NewValuePair = std::make_pair(Transfer.first, Transfer.second); | |||
3352 | auto Result = JoinedInLocs.insert(NewValuePair); | |||
3353 | if (!Result.second) | |||
3354 | Result.first->second = Transfer.second; | |||
3355 | } | |||
3356 | } | |||
3357 | } | |||
3358 | ||||
3359 | // Did the live-out locations change? | |||
3360 | bool OLChanged = JoinedInLocs != *LiveOutIdx[MBB]; | |||
3361 | ||||
3362 | // If they haven't changed, there's no need to explore further. | |||
3363 | if (!OLChanged) | |||
3364 | continue; | |||
3365 | ||||
3366 | // Commit to the live-out record. | |||
3367 | *LiveOutIdx[MBB] = JoinedInLocs; | |||
3368 | ||||
3369 | // We should visit all successors. Ensure we'll visit any non-backedge | |||
3370 | // successors during this dataflow iteration; book backedge successors | |||
3371 | // to be visited next time around. | |||
3372 | for (auto s : MBB->successors()) { | |||
3373 | // Ignore out of scope / not-to-be-explored successors. | |||
3374 | if (LiveInIdx.find(s) == LiveInIdx.end()) | |||
3375 | continue; | |||
3376 | ||||
3377 | if (BBToOrder[s] > BBToOrder[MBB]) { | |||
3378 | if (OnWorklist.insert(s).second) | |||
3379 | Worklist.push(BBToOrder[s]); | |||
3380 | } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) { | |||
3381 | Pending.push(BBToOrder[s]); | |||
3382 | } | |||
3383 | } | |||
3384 | } | |||
3385 | Worklist.swap(Pending); | |||
3386 | std::swap(OnWorklist, OnPending); | |||
3387 | OnPending.clear(); | |||
3388 | assert(Pending.empty())((void)0); | |||
3389 | FirstTrip = false; | |||
3390 | } | |||
3391 | ||||
3392 | // Dataflow done. Now what? Save live-ins. Ignore any that are still marked | |||
3393 | // as being variable-PHIs, because those did not have their machine-PHI | |||
3394 | // value confirmed. Such variable values are places that could have been | |||
3395 | // PHIs, but are not. | |||
3396 | for (auto *MBB : BlockOrders) { | |||
3397 | auto &VarMap = *LiveInIdx[MBB]; | |||
3398 | for (auto &P : VarMap) { | |||
3399 | if (P.second.Kind == DbgValue::Proposed || | |||
3400 | P.second.Kind == DbgValue::NoVal) | |||
3401 | continue; | |||
3402 | Output[MBB->getNumber()].push_back(P); | |||
3403 | } | |||
3404 | } | |||
3405 | ||||
3406 | BlockOrders.clear(); | |||
3407 | BlocksToExplore.clear(); | |||
3408 | } | |||
3409 | ||||
3410 | #if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP) | |||
3411 | void InstrRefBasedLDV::dump_mloc_transfer( | |||
3412 | const MLocTransferMap &mloc_transfer) const { | |||
3413 | for (auto &P : mloc_transfer) { | |||
3414 | std::string foo = MTracker->LocIdxToName(P.first); | |||
3415 | std::string bar = MTracker->IDAsString(P.second); | |||
3416 | dbgs() << "Loc " << foo << " --> " << bar << "\n"; | |||
3417 | } | |||
3418 | } | |||
3419 | #endif | |||
3420 | ||||
3421 | void InstrRefBasedLDV::emitLocations( | |||
3422 | MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs, | |||
3423 | ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering, | |||
3424 | const TargetPassConfig &TPC) { | |||
3425 | TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC); | |||
3426 | unsigned NumLocs = MTracker->getNumLocs(); | |||
3427 | ||||
3428 | // For each block, load in the machine value locations and variable value | |||
3429 | // live-ins, then step through each instruction in the block. New DBG_VALUEs | |||
3430 | // to be inserted will be created along the way. | |||
3431 | for (MachineBasicBlock &MBB : MF) { | |||
3432 | unsigned bbnum = MBB.getNumber(); | |||
3433 | MTracker->reset(); | |||
3434 | MTracker->loadFromArray(MInLocs[bbnum], bbnum); | |||
3435 | TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()], | |||
3436 | NumLocs); | |||
3437 | ||||
3438 | CurBB = bbnum; | |||
3439 | CurInst = 1; | |||
3440 | for (auto &MI : MBB) { | |||
3441 | process(MI, MOutLocs, MInLocs); | |||
3442 | TTracker->checkInstForNewValues(CurInst, MI.getIterator()); | |||
3443 | ++CurInst; | |||
3444 | } | |||
3445 | } | |||
3446 | ||||
3447 | // We have to insert DBG_VALUEs in a consistent order, otherwise they appeaer | |||
3448 | // in DWARF in different orders. Use the order that they appear when walking | |||
3449 | // through each block / each instruction, stored in AllVarsNumbering. | |||
3450 | auto OrderDbgValues = [&](const MachineInstr *A, | |||
3451 | const MachineInstr *B) -> bool { | |||
3452 | DebugVariable VarA(A->getDebugVariable(), A->getDebugExpression(), | |||
3453 | A->getDebugLoc()->getInlinedAt()); | |||
3454 | DebugVariable VarB(B->getDebugVariable(), B->getDebugExpression(), | |||
3455 | B->getDebugLoc()->getInlinedAt()); | |||
3456 | return AllVarsNumbering.find(VarA)->second < | |||
3457 | AllVarsNumbering.find(VarB)->second; | |||
3458 | }; | |||
3459 | ||||
3460 | // Go through all the transfers recorded in the TransferTracker -- this is | |||
3461 | // both the live-ins to a block, and any movements of values that happen | |||
3462 | // in the middle. | |||
3463 | for (auto &P : TTracker->Transfers) { | |||
3464 | // Sort them according to appearance order. | |||
3465 | llvm::sort(P.Insts, OrderDbgValues); | |||
3466 | // Insert either before or after the designated point... | |||
3467 | if (P.MBB) { | |||
3468 | MachineBasicBlock &MBB = *P.MBB; | |||
3469 | for (auto *MI : P.Insts) { | |||
3470 | MBB.insert(P.Pos, MI); | |||
3471 | } | |||
3472 | } else { | |||
3473 | // Terminators, like tail calls, can clobber things. Don't try and place | |||
3474 | // transfers after them. | |||
3475 | if (P.Pos->isTerminator()) | |||
3476 | continue; | |||
3477 | ||||
3478 | MachineBasicBlock &MBB = *P.Pos->getParent(); | |||
3479 | for (auto *MI : P.Insts) { | |||
3480 | MBB.insertAfterBundle(P.Pos, MI); | |||
3481 | } | |||
3482 | } | |||
3483 | } | |||
3484 | } | |||
3485 | ||||
3486 | void InstrRefBasedLDV::initialSetup(MachineFunction &MF) { | |||
3487 | // Build some useful data structures. | |||
3488 | auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { | |||
3489 | if (const DebugLoc &DL = MI.getDebugLoc()) | |||
3490 | return DL.getLine() != 0; | |||
3491 | return false; | |||
3492 | }; | |||
3493 | // Collect a set of all the artificial blocks. | |||
3494 | for (auto &MBB : MF) | |||
3495 | if (none_of(MBB.instrs(), hasNonArtificialLocation)) | |||
3496 | ArtificialBlocks.insert(&MBB); | |||
3497 | ||||
3498 | // Compute mappings of block <=> RPO order. | |||
3499 | ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); | |||
3500 | unsigned int RPONumber = 0; | |||
3501 | for (MachineBasicBlock *MBB : RPOT) { | |||
3502 | OrderToBB[RPONumber] = MBB; | |||
3503 | BBToOrder[MBB] = RPONumber; | |||
3504 | BBNumToRPO[MBB->getNumber()] = RPONumber; | |||
3505 | ++RPONumber; | |||
3506 | } | |||
3507 | ||||
3508 | // Order value substitutions by their "source" operand pair, for quick lookup. | |||
3509 | llvm::sort(MF.DebugValueSubstitutions); | |||
3510 | ||||
3511 | #ifdef EXPENSIVE_CHECKS | |||
3512 | // As an expensive check, test whether there are any duplicate substitution | |||
3513 | // sources in the collection. | |||
3514 | if (MF.DebugValueSubstitutions.size() > 2) { | |||
3515 | for (auto It = MF.DebugValueSubstitutions.begin(); | |||
3516 | It != std::prev(MF.DebugValueSubstitutions.end()); ++It) { | |||
3517 | assert(It->Src != std::next(It)->Src && "Duplicate variable location "((void)0) | |||
3518 | "substitution seen")((void)0); | |||
3519 | } | |||
3520 | } | |||
3521 | #endif | |||
3522 | } | |||
3523 | ||||
3524 | /// Calculate the liveness information for the given machine function and | |||
3525 | /// extend ranges across basic blocks. | |||
3526 | bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, | |||
3527 | TargetPassConfig *TPC) { | |||
3528 | // No subprogram means this function contains no debuginfo. | |||
3529 | if (!MF.getFunction().getSubprogram()) | |||
3530 | return false; | |||
3531 | ||||
3532 | LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n")do { } while (false); | |||
3533 | this->TPC = TPC; | |||
3534 | ||||
3535 | TRI = MF.getSubtarget().getRegisterInfo(); | |||
3536 | TII = MF.getSubtarget().getInstrInfo(); | |||
3537 | TFI = MF.getSubtarget().getFrameLowering(); | |||
3538 | TFI->getCalleeSaves(MF, CalleeSavedRegs); | |||
3539 | MFI = &MF.getFrameInfo(); | |||
3540 | LS.initialize(MF); | |||
3541 | ||||
3542 | MTracker = | |||
3543 | new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering()); | |||
3544 | VTracker = nullptr; | |||
3545 | TTracker = nullptr; | |||
3546 | ||||
3547 | SmallVector<MLocTransferMap, 32> MLocTransfer; | |||
3548 | SmallVector<VLocTracker, 8> vlocs; | |||
3549 | LiveInsT SavedLiveIns; | |||
3550 | ||||
3551 | int MaxNumBlocks = -1; | |||
3552 | for (auto &MBB : MF) | |||
3553 | MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks); | |||
3554 | assert(MaxNumBlocks >= 0)((void)0); | |||
3555 | ++MaxNumBlocks; | |||
3556 | ||||
3557 | MLocTransfer.resize(MaxNumBlocks); | |||
3558 | vlocs.resize(MaxNumBlocks); | |||
3559 | SavedLiveIns.resize(MaxNumBlocks); | |||
3560 | ||||
3561 | initialSetup(MF); | |||
3562 | ||||
3563 | produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks); | |||
3564 | ||||
3565 | // Allocate and initialize two array-of-arrays for the live-in and live-out | |||
3566 | // machine values. The outer dimension is the block number; while the inner | |||
3567 | // dimension is a LocIdx from MLocTracker. | |||
3568 | ValueIDNum **MOutLocs = new ValueIDNum *[MaxNumBlocks]; | |||
3569 | ValueIDNum **MInLocs = new ValueIDNum *[MaxNumBlocks]; | |||
3570 | unsigned NumLocs = MTracker->getNumLocs(); | |||
3571 | for (int i = 0; i < MaxNumBlocks; ++i) { | |||
3572 | MOutLocs[i] = new ValueIDNum[NumLocs]; | |||
3573 | MInLocs[i] = new ValueIDNum[NumLocs]; | |||
3574 | } | |||
3575 | ||||
3576 | // Solve the machine value dataflow problem using the MLocTransfer function, | |||
3577 | // storing the computed live-ins / live-outs into the array-of-arrays. We use | |||
3578 | // both live-ins and live-outs for decision making in the variable value | |||
3579 | // dataflow problem. | |||
3580 | mlocDataflow(MInLocs, MOutLocs, MLocTransfer); | |||
3581 | ||||
3582 | // Patch up debug phi numbers, turning unknown block-live-in values into | |||
3583 | // either live-through machine values, or PHIs. | |||
3584 | for (auto &DBG_PHI : DebugPHINumToValue) { | |||
3585 | // Identify unresolved block-live-ins. | |||
3586 | ValueIDNum &Num = DBG_PHI.ValueRead; | |||
3587 | if (!Num.isPHI()) | |||
3588 | continue; | |||
3589 | ||||
3590 | unsigned BlockNo = Num.getBlock(); | |||
3591 | LocIdx LocNo = Num.getLoc(); | |||
3592 | Num = MInLocs[BlockNo][LocNo.asU64()]; | |||
3593 | } | |||
3594 | // Later, we'll be looking up ranges of instruction numbers. | |||
3595 | llvm::sort(DebugPHINumToValue); | |||
3596 | ||||
3597 | // Walk back through each block / instruction, collecting DBG_VALUE | |||
3598 | // instructions and recording what machine value their operands refer to. | |||
3599 | for (auto &OrderPair : OrderToBB) { | |||
3600 | MachineBasicBlock &MBB = *OrderPair.second; | |||
3601 | CurBB = MBB.getNumber(); | |||
3602 | VTracker = &vlocs[CurBB]; | |||
3603 | VTracker->MBB = &MBB; | |||
3604 | MTracker->loadFromArray(MInLocs[CurBB], CurBB); | |||
3605 | CurInst = 1; | |||
3606 | for (auto &MI : MBB) { | |||
3607 | process(MI, MOutLocs, MInLocs); | |||
3608 | ++CurInst; | |||
3609 | } | |||
3610 | MTracker->reset(); | |||
3611 | } | |||
3612 | ||||
3613 | // Number all variables in the order that they appear, to be used as a stable | |||
3614 | // insertion order later. | |||
3615 | DenseMap<DebugVariable, unsigned> AllVarsNumbering; | |||
3616 | ||||
3617 | // Map from one LexicalScope to all the variables in that scope. | |||
3618 | DenseMap<const LexicalScope *, SmallSet<DebugVariable, 4>> ScopeToVars; | |||
3619 | ||||
3620 | // Map from One lexical scope to all blocks in that scope. | |||
3621 | DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>> | |||
3622 | ScopeToBlocks; | |||
3623 | ||||
3624 | // Store a DILocation that describes a scope. | |||
3625 | DenseMap<const LexicalScope *, const DILocation *> ScopeToDILocation; | |||
3626 | ||||
3627 | // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise | |||
3628 | // the order is unimportant, it just has to be stable. | |||
3629 | for (unsigned int I = 0; I < OrderToBB.size(); ++I) { | |||
3630 | auto *MBB = OrderToBB[I]; | |||
3631 | auto *VTracker = &vlocs[MBB->getNumber()]; | |||
3632 | // Collect each variable with a DBG_VALUE in this block. | |||
3633 | for (auto &idx : VTracker->Vars) { | |||
3634 | const auto &Var = idx.first; | |||
3635 | const DILocation *ScopeLoc = VTracker->Scopes[Var]; | |||
3636 | assert(ScopeLoc != nullptr)((void)0); | |||
3637 | auto *Scope = LS.findLexicalScope(ScopeLoc); | |||
3638 | ||||
3639 | // No insts in scope -> shouldn't have been recorded. | |||
3640 | assert(Scope != nullptr)((void)0); | |||
3641 | ||||
3642 | AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size())); | |||
3643 | ScopeToVars[Scope].insert(Var); | |||
3644 | ScopeToBlocks[Scope].insert(VTracker->MBB); | |||
3645 | ScopeToDILocation[Scope] = ScopeLoc; | |||
3646 | } | |||
3647 | } | |||
3648 | ||||
3649 | // OK. Iterate over scopes: there might be something to be said for | |||
3650 | // ordering them by size/locality, but that's for the future. For each scope, | |||
3651 | // solve the variable value problem, producing a map of variables to values | |||
3652 | // in SavedLiveIns. | |||
3653 | for (auto &P : ScopeToVars) { | |||
3654 | vlocDataflow(P.first, ScopeToDILocation[P.first], P.second, | |||
3655 | ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs, | |||
3656 | vlocs); | |||
3657 | } | |||
3658 | ||||
3659 | // Using the computed value locations and variable values for each block, | |||
3660 | // create the DBG_VALUE instructions representing the extended variable | |||
3661 | // locations. | |||
3662 | emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC); | |||
3663 | ||||
3664 | for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) { | |||
3665 | delete[] MOutLocs[Idx]; | |||
3666 | delete[] MInLocs[Idx]; | |||
3667 | } | |||
3668 | delete[] MOutLocs; | |||
3669 | delete[] MInLocs; | |||
3670 | ||||
3671 | // Did we actually make any changes? If we created any DBG_VALUEs, then yes. | |||
3672 | bool Changed = TTracker->Transfers.size() != 0; | |||
3673 | ||||
3674 | delete MTracker; | |||
3675 | delete TTracker; | |||
3676 | MTracker = nullptr; | |||
3677 | VTracker = nullptr; | |||
3678 | TTracker = nullptr; | |||
3679 | ||||
3680 | ArtificialBlocks.clear(); | |||
3681 | OrderToBB.clear(); | |||
3682 | BBToOrder.clear(); | |||
3683 | BBNumToRPO.clear(); | |||
3684 | DebugInstrNumToInstr.clear(); | |||
3685 | DebugPHINumToValue.clear(); | |||
3686 | ||||
3687 | return Changed; | |||
3688 | } | |||
3689 | ||||
3690 | LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() { | |||
3691 | return new InstrRefBasedLDV(); | |||
3692 | } | |||
3693 | ||||
3694 | namespace { | |||
3695 | class LDVSSABlock; | |||
3696 | class LDVSSAUpdater; | |||
3697 | ||||
3698 | // Pick a type to identify incoming block values as we construct SSA. We | |||
3699 | // can't use anything more robust than an integer unfortunately, as SSAUpdater | |||
3700 | // expects to zero-initialize the type. | |||
3701 | typedef uint64_t BlockValueNum; | |||
3702 | ||||
3703 | /// Represents an SSA PHI node for the SSA updater class. Contains the block | |||
3704 | /// this PHI is in, the value number it would have, and the expected incoming | |||
3705 | /// values from parent blocks. | |||
3706 | class LDVSSAPhi { | |||
3707 | public: | |||
3708 | SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues; | |||
3709 | LDVSSABlock *ParentBlock; | |||
3710 | BlockValueNum PHIValNum; | |||
3711 | LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock) | |||
3712 | : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {} | |||
3713 | ||||
3714 | LDVSSABlock *getParent() { return ParentBlock; } | |||
3715 | }; | |||
3716 | ||||
3717 | /// Thin wrapper around a block predecessor iterator. Only difference from a | |||
3718 | /// normal block iterator is that it dereferences to an LDVSSABlock. | |||
3719 | class LDVSSABlockIterator { | |||
3720 | public: | |||
3721 | MachineBasicBlock::pred_iterator PredIt; | |||
3722 | LDVSSAUpdater &Updater; | |||
3723 | ||||
3724 | LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt, | |||
3725 | LDVSSAUpdater &Updater) | |||
3726 | : PredIt(PredIt), Updater(Updater) {} | |||
3727 | ||||
3728 | bool operator!=(const LDVSSABlockIterator &OtherIt) const { | |||
3729 | return OtherIt.PredIt != PredIt; | |||
3730 | } | |||
3731 | ||||
3732 | LDVSSABlockIterator &operator++() { | |||
3733 | ++PredIt; | |||
3734 | return *this; | |||
3735 | } | |||
3736 | ||||
3737 | LDVSSABlock *operator*(); | |||
3738 | }; | |||
3739 | ||||
3740 | /// Thin wrapper around a block for SSA Updater interface. Necessary because | |||
3741 | /// we need to track the PHI value(s) that we may have observed as necessary | |||
3742 | /// in this block. | |||
3743 | class LDVSSABlock { | |||
3744 | public: | |||
3745 | MachineBasicBlock &BB; | |||
3746 | LDVSSAUpdater &Updater; | |||
3747 | using PHIListT = SmallVector<LDVSSAPhi, 1>; | |||
3748 | /// List of PHIs in this block. There should only ever be one. | |||
3749 | PHIListT PHIList; | |||
3750 | ||||
3751 | LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater) | |||
3752 | : BB(BB), Updater(Updater) {} | |||
3753 | ||||
3754 | LDVSSABlockIterator succ_begin() { | |||
3755 | return LDVSSABlockIterator(BB.succ_begin(), Updater); | |||
3756 | } | |||
3757 | ||||
3758 | LDVSSABlockIterator succ_end() { | |||
3759 | return LDVSSABlockIterator(BB.succ_end(), Updater); | |||
3760 | } | |||
3761 | ||||
3762 | /// SSAUpdater has requested a PHI: create that within this block record. | |||
3763 | LDVSSAPhi *newPHI(BlockValueNum Value) { | |||
3764 | PHIList.emplace_back(Value, this); | |||
3765 | return &PHIList.back(); | |||
3766 | } | |||
3767 | ||||
3768 | /// SSAUpdater wishes to know what PHIs already exist in this block. | |||
3769 | PHIListT &phis() { return PHIList; } | |||
3770 | }; | |||
3771 | ||||
3772 | /// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values | |||
3773 | /// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to | |||
3774 | // SSAUpdaterTraits<LDVSSAUpdater>. | |||
3775 | class LDVSSAUpdater { | |||
3776 | public: | |||
3777 | /// Map of value numbers to PHI records. | |||
3778 | DenseMap<BlockValueNum, LDVSSAPhi *> PHIs; | |||
3779 | /// Map of which blocks generate Undef values -- blocks that are not | |||
3780 | /// dominated by any Def. | |||
3781 | DenseMap<MachineBasicBlock *, BlockValueNum> UndefMap; | |||
3782 | /// Map of machine blocks to our own records of them. | |||
3783 | DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap; | |||
3784 | /// Machine location where any PHI must occur. | |||
3785 | LocIdx Loc; | |||
3786 | /// Table of live-in machine value numbers for blocks / locations. | |||
3787 | ValueIDNum **MLiveIns; | |||
3788 | ||||
3789 | LDVSSAUpdater(LocIdx L, ValueIDNum **MLiveIns) : Loc(L), MLiveIns(MLiveIns) {} | |||
3790 | ||||
3791 | void reset() { | |||
3792 | for (auto &Block : BlockMap) | |||
3793 | delete Block.second; | |||
3794 | ||||
3795 | PHIs.clear(); | |||
3796 | UndefMap.clear(); | |||
3797 | BlockMap.clear(); | |||
3798 | } | |||
3799 | ||||
3800 | ~LDVSSAUpdater() { reset(); } | |||
3801 | ||||
3802 | /// For a given MBB, create a wrapper block for it. Stores it in the | |||
3803 | /// LDVSSAUpdater block map. | |||
3804 | LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) { | |||
3805 | auto it = BlockMap.find(BB); | |||
3806 | if (it == BlockMap.end()) { | |||
3807 | BlockMap[BB] = new LDVSSABlock(*BB, *this); | |||
3808 | it = BlockMap.find(BB); | |||
3809 | } | |||
3810 | return it->second; | |||
3811 | } | |||
3812 | ||||
3813 | /// Find the live-in value number for the given block. Looks up the value at | |||
3814 | /// the PHI location on entry. | |||
3815 | BlockValueNum getValue(LDVSSABlock *LDVBB) { | |||
3816 | return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64(); | |||
3817 | } | |||
3818 | }; | |||
3819 | ||||
3820 | LDVSSABlock *LDVSSABlockIterator::operator*() { | |||
3821 | return Updater.getSSALDVBlock(*PredIt); | |||
3822 | } | |||
3823 | ||||
3824 | #ifndef NDEBUG1 | |||
3825 | ||||
3826 | raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) { | |||
3827 | out << "SSALDVPHI " << PHI.PHIValNum; | |||
3828 | return out; | |||
3829 | } | |||
3830 | ||||
3831 | #endif | |||
3832 | ||||
3833 | } // namespace | |||
3834 | ||||
3835 | namespace llvm { | |||
3836 | ||||
3837 | /// Template specialization to give SSAUpdater access to CFG and value | |||
3838 | /// information. SSAUpdater calls methods in these traits, passing in the | |||
3839 | /// LDVSSAUpdater object, to learn about blocks and the values they define. | |||
3840 | /// It also provides methods to create PHI nodes and track them. | |||
3841 | template <> class SSAUpdaterTraits<LDVSSAUpdater> { | |||
3842 | public: | |||
3843 | using BlkT = LDVSSABlock; | |||
3844 | using ValT = BlockValueNum; | |||
3845 | using PhiT = LDVSSAPhi; | |||
3846 | using BlkSucc_iterator = LDVSSABlockIterator; | |||
3847 | ||||
3848 | // Methods to access block successors -- dereferencing to our wrapper class. | |||
3849 | static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } | |||
3850 | static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } | |||
3851 | ||||
3852 | /// Iterator for PHI operands. | |||
3853 | class PHI_iterator { | |||
3854 | private: | |||
3855 | LDVSSAPhi *PHI; | |||
3856 | unsigned Idx; | |||
3857 | ||||
3858 | public: | |||
3859 | explicit PHI_iterator(LDVSSAPhi *P) // begin iterator | |||
3860 | : PHI(P), Idx(0) {} | |||
3861 | PHI_iterator(LDVSSAPhi *P, bool) // end iterator | |||
3862 | : PHI(P), Idx(PHI->IncomingValues.size()) {} | |||
3863 | ||||
3864 | PHI_iterator &operator++() { | |||
3865 | Idx++; | |||
3866 | return *this; | |||
3867 | } | |||
3868 | bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; } | |||
3869 | bool operator!=(const PHI_iterator &X) const { return !operator==(X); } | |||
3870 | ||||
3871 | BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; } | |||
3872 | ||||
3873 | LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; } | |||
3874 | }; | |||
3875 | ||||
3876 | static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } | |||
3877 | ||||
3878 | static inline PHI_iterator PHI_end(PhiT *PHI) { | |||
3879 | return PHI_iterator(PHI, true); | |||
3880 | } | |||
3881 | ||||
3882 | /// FindPredecessorBlocks - Put the predecessors of BB into the Preds | |||
3883 | /// vector. | |||
3884 | static void FindPredecessorBlocks(LDVSSABlock *BB, | |||
3885 | SmallVectorImpl<LDVSSABlock *> *Preds) { | |||
3886 | for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(), | |||
3887 | E = BB->BB.pred_end(); | |||
3888 | PI != E; ++PI) | |||
3889 | Preds->push_back(BB->Updater.getSSALDVBlock(*PI)); | |||
3890 | } | |||
3891 | ||||
3892 | /// GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new | |||
3893 | /// register. For LiveDebugValues, represents a block identified as not having | |||
3894 | /// any DBG_PHI predecessors. | |||
3895 | static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) { | |||
3896 | // Create a value number for this block -- it needs to be unique and in the | |||
3897 | // "undef" collection, so that we know it's not real. Use a number | |||
3898 | // representing a PHI into this block. | |||
3899 | BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64(); | |||
3900 | Updater->UndefMap[&BB->BB] = Num; | |||
3901 | return Num; | |||
3902 | } | |||
3903 | ||||
3904 | /// CreateEmptyPHI - Create a (representation of a) PHI in the given block. | |||
3905 | /// SSAUpdater will populate it with information about incoming values. The | |||
3906 | /// value number of this PHI is whatever the machine value number problem | |||
3907 | /// solution determined it to be. This includes non-phi values if SSAUpdater | |||
3908 | /// tries to create a PHI where the incoming values are identical. | |||
3909 | static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds, | |||
3910 | LDVSSAUpdater *Updater) { | |||
3911 | BlockValueNum PHIValNum = Updater->getValue(BB); | |||
3912 | LDVSSAPhi *PHI = BB->newPHI(PHIValNum); | |||
3913 | Updater->PHIs[PHIValNum] = PHI; | |||
3914 | return PHIValNum; | |||
3915 | } | |||
3916 | ||||
3917 | /// AddPHIOperand - Add the specified value as an operand of the PHI for | |||
3918 | /// the specified predecessor block. | |||
3919 | static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) { | |||
3920 | PHI->IncomingValues.push_back(std::make_pair(Pred, Val)); | |||
3921 | } | |||
3922 | ||||
3923 | /// ValueIsPHI - Check if the instruction that defines the specified value | |||
3924 | /// is a PHI instruction. | |||
3925 | static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) { | |||
3926 | auto PHIIt = Updater->PHIs.find(Val); | |||
3927 | if (PHIIt == Updater->PHIs.end()) | |||
3928 | return nullptr; | |||
3929 | return PHIIt->second; | |||
3930 | } | |||
3931 | ||||
3932 | /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source | |||
3933 | /// operands, i.e., it was just added. | |||
3934 | static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) { | |||
3935 | LDVSSAPhi *PHI = ValueIsPHI(Val, Updater); | |||
3936 | if (PHI && PHI->IncomingValues.size() == 0) | |||
3937 | return PHI; | |||
3938 | return nullptr; | |||
3939 | } | |||
3940 | ||||
3941 | /// GetPHIValue - For the specified PHI instruction, return the value | |||
3942 | /// that it defines. | |||
3943 | static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; } | |||
3944 | }; | |||
3945 | ||||
3946 | } // end namespace llvm | |||
3947 | ||||
3948 | Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF, | |||
3949 | ValueIDNum **MLiveOuts, | |||
3950 | ValueIDNum **MLiveIns, | |||
3951 | MachineInstr &Here, | |||
3952 | uint64_t InstrNum) { | |||
3953 | // Pick out records of DBG_PHI instructions that have been observed. If there | |||
3954 | // are none, then we cannot compute a value number. | |||
3955 | auto RangePair = std::equal_range(DebugPHINumToValue.begin(), | |||
3956 | DebugPHINumToValue.end(), InstrNum); | |||
3957 | auto LowerIt = RangePair.first; | |||
3958 | auto UpperIt = RangePair.second; | |||
3959 | ||||
3960 | // No DBG_PHI means there can be no location. | |||
3961 | if (LowerIt == UpperIt) | |||
| ||||
3962 | return None; | |||
3963 | ||||
3964 | // If there's only one DBG_PHI, then that is our value number. | |||
3965 | if (std::distance(LowerIt, UpperIt) == 1) | |||
3966 | return LowerIt->ValueRead; | |||
3967 | ||||
3968 | auto DBGPHIRange = make_range(LowerIt, UpperIt); | |||
3969 | ||||
3970 | // Pick out the location (physreg, slot) where any PHIs must occur. It's | |||
3971 | // technically possible for us to merge values in different registers in each | |||
3972 | // block, but highly unlikely that LLVM will generate such code after register | |||
3973 | // allocation. | |||
3974 | LocIdx Loc = LowerIt->ReadLoc; | |||
3975 | ||||
3976 | // We have several DBG_PHIs, and a use position (the Here inst). All each | |||
3977 | // DBG_PHI does is identify a value at a program position. We can treat each | |||
3978 | // DBG_PHI like it's a Def of a value, and the use position is a Use of a | |||
3979 | // value, just like SSA. We use the bulk-standard LLVM SSA updater class to | |||
3980 | // determine which Def is used at the Use, and any PHIs that happen along | |||
3981 | // the way. | |||
3982 | // Adapted LLVM SSA Updater: | |||
3983 | LDVSSAUpdater Updater(Loc, MLiveIns); | |||
3984 | // Map of which Def or PHI is the current value in each block. | |||
3985 | DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues; | |||
3986 | // Set of PHIs that we have created along the way. | |||
3987 | SmallVector<LDVSSAPhi *, 8> CreatedPHIs; | |||
3988 | ||||
3989 | // Each existing DBG_PHI is a Def'd value under this model. Record these Defs | |||
3990 | // for the SSAUpdater. | |||
3991 | for (const auto &DBG_PHI : DBGPHIRange) { | |||
3992 | LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB); | |||
3993 | const ValueIDNum &Num = DBG_PHI.ValueRead; | |||
3994 | AvailableValues.insert(std::make_pair(Block, Num.asU64())); | |||
3995 | } | |||
3996 | ||||
3997 | LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent()); | |||
3998 | const auto &AvailIt = AvailableValues.find(HereBlock); | |||
3999 | if (AvailIt != AvailableValues.end()) { | |||
4000 | // Actually, we already know what the value is -- the Use is in the same | |||
4001 | // block as the Def. | |||
4002 | return ValueIDNum::fromU64(AvailIt->second); | |||
4003 | } | |||
4004 | ||||
4005 | // Otherwise, we must use the SSA Updater. It will identify the value number | |||
4006 | // that we are to use, and the PHIs that must happen along the way. | |||
4007 | SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs); | |||
4008 | BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent())); | |||
4009 | ValueIDNum Result = ValueIDNum::fromU64(ResultInt); | |||
4010 | ||||
4011 | // We have the number for a PHI, or possibly live-through value, to be used | |||
4012 | // at this Use. There are a number of things we have to check about it though: | |||
4013 | // * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this | |||
4014 | // Use was not completely dominated by DBG_PHIs and we should abort. | |||
4015 | // * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that | |||
4016 | // we've left SSA form. Validate that the inputs to each PHI are the | |||
4017 | // expected values. | |||
4018 | // * Is a PHI we've created actually a merging of values, or are all the | |||
4019 | // predecessor values the same, leading to a non-PHI machine value number? | |||
4020 | // (SSAUpdater doesn't know that either). Remap validated PHIs into the | |||
4021 | // the ValidatedValues collection below to sort this out. | |||
4022 | DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues; | |||
4023 | ||||
4024 | // Define all the input DBG_PHI values in ValidatedValues. | |||
4025 | for (const auto &DBG_PHI : DBGPHIRange) { | |||
4026 | LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB); | |||
4027 | const ValueIDNum &Num = DBG_PHI.ValueRead; | |||
4028 | ValidatedValues.insert(std::make_pair(Block, Num)); | |||
4029 | } | |||
4030 | ||||
4031 | // Sort PHIs to validate into RPO-order. | |||
4032 | SmallVector<LDVSSAPhi *, 8> SortedPHIs; | |||
4033 | for (auto &PHI : CreatedPHIs) | |||
4034 | SortedPHIs.push_back(PHI); | |||
4035 | ||||
4036 | std::sort( | |||
4037 | SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) { | |||
4038 | return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB]; | |||
4039 | }); | |||
4040 | ||||
4041 | for (auto &PHI : SortedPHIs) { | |||
4042 | ValueIDNum ThisBlockValueNum = | |||
4043 | MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()]; | |||
4044 | ||||
4045 | // Are all these things actually defined? | |||
4046 | for (auto &PHIIt : PHI->IncomingValues) { | |||
4047 | // Any undef input means DBG_PHIs didn't dominate the use point. | |||
4048 | if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end()) | |||
4049 | return None; | |||
4050 | ||||
4051 | ValueIDNum ValueToCheck; | |||
4052 | ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()]; | |||
4053 | ||||
4054 | auto VVal = ValidatedValues.find(PHIIt.first); | |||
4055 | if (VVal == ValidatedValues.end()) { | |||
4056 | // We cross a loop, and this is a backedge. LLVMs tail duplication | |||
4057 | // happens so late that DBG_PHI instructions should not be able to | |||
4058 | // migrate into loops -- meaning we can only be live-through this | |||
4059 | // loop. | |||
4060 | ValueToCheck = ThisBlockValueNum; | |||
4061 | } else { | |||
4062 | // Does the block have as a live-out, in the location we're examining, | |||
4063 | // the value that we expect? If not, it's been moved or clobbered. | |||
4064 | ValueToCheck = VVal->second; | |||
4065 | } | |||
4066 | ||||
4067 | if (BlockLiveOuts[Loc.asU64()] != ValueToCheck) | |||
4068 | return None; | |||
4069 | } | |||
4070 | ||||
4071 | // Record this value as validated. | |||
4072 | ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum}); | |||
4073 | } | |||
4074 | ||||
4075 | // All the PHIs are valid: we can return what the SSAUpdater said our value | |||
4076 | // number was. | |||
4077 | return Result; | |||
4078 | } |
1 | //===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file provides a template that implements the core algorithm for the |
10 | // SSAUpdater and MachineSSAUpdater. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H |
15 | #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H |
16 | |
17 | #include "llvm/ADT/DenseMap.h" |
18 | #include "llvm/ADT/SmallVector.h" |
19 | #include "llvm/Support/Allocator.h" |
20 | #include "llvm/Support/Debug.h" |
21 | #include "llvm/Support/raw_ostream.h" |
22 | |
23 | #define DEBUG_TYPE"livedebugvalues" "ssaupdater" |
24 | |
25 | namespace llvm { |
26 | |
27 | template<typename T> class SSAUpdaterTraits; |
28 | |
29 | template<typename UpdaterT> |
30 | class SSAUpdaterImpl { |
31 | private: |
32 | UpdaterT *Updater; |
33 | |
34 | using Traits = SSAUpdaterTraits<UpdaterT>; |
35 | using BlkT = typename Traits::BlkT; |
36 | using ValT = typename Traits::ValT; |
37 | using PhiT = typename Traits::PhiT; |
38 | |
39 | /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl. |
40 | /// The predecessors of each block are cached here since pred_iterator is |
41 | /// slow and we need to iterate over the blocks at least a few times. |
42 | class BBInfo { |
43 | public: |
44 | // Back-pointer to the corresponding block. |
45 | BlkT *BB; |
46 | |
47 | // Value to use in this block. |
48 | ValT AvailableVal; |
49 | |
50 | // Block that defines the available value. |
51 | BBInfo *DefBB; |
52 | |
53 | // Postorder number. |
54 | int BlkNum = 0; |
55 | |
56 | // Immediate dominator. |
57 | BBInfo *IDom = nullptr; |
58 | |
59 | // Number of predecessor blocks. |
60 | unsigned NumPreds = 0; |
61 | |
62 | // Array[NumPreds] of predecessor blocks. |
63 | BBInfo **Preds = nullptr; |
64 | |
65 | // Marker for existing PHIs that match. |
66 | PhiT *PHITag = nullptr; |
67 | |
68 | BBInfo(BlkT *ThisBB, ValT V) |
69 | : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {} |
70 | }; |
71 | |
72 | using AvailableValsTy = DenseMap<BlkT *, ValT>; |
73 | |
74 | AvailableValsTy *AvailableVals; |
75 | |
76 | SmallVectorImpl<PhiT *> *InsertedPHIs; |
77 | |
78 | using BlockListTy = SmallVectorImpl<BBInfo *>; |
79 | using BBMapTy = DenseMap<BlkT *, BBInfo *>; |
80 | |
81 | BBMapTy BBMap; |
82 | BumpPtrAllocator Allocator; |
83 | |
84 | public: |
85 | explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A, |
86 | SmallVectorImpl<PhiT *> *Ins) : |
87 | Updater(U), AvailableVals(A), InsertedPHIs(Ins) {} |
88 | |
89 | /// GetValue - Check to see if AvailableVals has an entry for the specified |
90 | /// BB and if so, return it. If not, construct SSA form by first |
91 | /// calculating the required placement of PHIs and then inserting new PHIs |
92 | /// where needed. |
93 | ValT GetValue(BlkT *BB) { |
94 | SmallVector<BBInfo *, 100> BlockList; |
95 | BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList); |
96 | |
97 | // Special case: bail out if BB is unreachable. |
98 | if (BlockList.size() == 0) { |
99 | ValT V = Traits::GetUndefVal(BB, Updater); |
100 | (*AvailableVals)[BB] = V; |
101 | return V; |
102 | } |
103 | |
104 | FindDominators(&BlockList, PseudoEntry); |
105 | FindPHIPlacement(&BlockList); |
106 | FindAvailableVals(&BlockList); |
107 | |
108 | return BBMap[BB]->DefBB->AvailableVal; |
109 | } |
110 | |
111 | /// BuildBlockList - Starting from the specified basic block, traverse back |
112 | /// through its predecessors until reaching blocks with known values. |
113 | /// Create BBInfo structures for the blocks and append them to the block |
114 | /// list. |
115 | BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) { |
116 | SmallVector<BBInfo *, 10> RootList; |
117 | SmallVector<BBInfo *, 64> WorkList; |
118 | |
119 | BBInfo *Info = new (Allocator) BBInfo(BB, 0); |
120 | BBMap[BB] = Info; |
121 | WorkList.push_back(Info); |
122 | |
123 | // Search backward from BB, creating BBInfos along the way and stopping |
124 | // when reaching blocks that define the value. Record those defining |
125 | // blocks on the RootList. |
126 | SmallVector<BlkT *, 10> Preds; |
127 | while (!WorkList.empty()) { |
128 | Info = WorkList.pop_back_val(); |
129 | Preds.clear(); |
130 | Traits::FindPredecessorBlocks(Info->BB, &Preds); |
131 | Info->NumPreds = Preds.size(); |
132 | if (Info->NumPreds == 0) |
133 | Info->Preds = nullptr; |
134 | else |
135 | Info->Preds = static_cast<BBInfo **>(Allocator.Allocate( |
136 | Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *))); |
137 | |
138 | for (unsigned p = 0; p != Info->NumPreds; ++p) { |
139 | BlkT *Pred = Preds[p]; |
140 | // Check if BBMap already has a BBInfo for the predecessor block. |
141 | typename BBMapTy::value_type &BBMapBucket = |
142 | BBMap.FindAndConstruct(Pred); |
143 | if (BBMapBucket.second) { |
144 | Info->Preds[p] = BBMapBucket.second; |
145 | continue; |
146 | } |
147 | |
148 | // Create a new BBInfo for the predecessor. |
149 | ValT PredVal = AvailableVals->lookup(Pred); |
150 | BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal); |
151 | BBMapBucket.second = PredInfo; |
152 | Info->Preds[p] = PredInfo; |
153 | |
154 | if (PredInfo->AvailableVal) { |
155 | RootList.push_back(PredInfo); |
156 | continue; |
157 | } |
158 | WorkList.push_back(PredInfo); |
159 | } |
160 | } |
161 | |
162 | // Now that we know what blocks are backwards-reachable from the starting |
163 | // block, do a forward depth-first traversal to assign postorder numbers |
164 | // to those blocks. |
165 | BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0); |
166 | unsigned BlkNum = 1; |
167 | |
168 | // Initialize the worklist with the roots from the backward traversal. |
169 | while (!RootList.empty()) { |
170 | Info = RootList.pop_back_val(); |
171 | Info->IDom = PseudoEntry; |
172 | Info->BlkNum = -1; |
173 | WorkList.push_back(Info); |
174 | } |
175 | |
176 | while (!WorkList.empty()) { |
177 | Info = WorkList.back(); |
178 | |
179 | if (Info->BlkNum == -2) { |
180 | // All the successors have been handled; assign the postorder number. |
181 | Info->BlkNum = BlkNum++; |
182 | // If not a root, put it on the BlockList. |
183 | if (!Info->AvailableVal) |
184 | BlockList->push_back(Info); |
185 | WorkList.pop_back(); |
186 | continue; |
187 | } |
188 | |
189 | // Leave this entry on the worklist, but set its BlkNum to mark that its |
190 | // successors have been put on the worklist. When it returns to the top |
191 | // the list, after handling its successors, it will be assigned a |
192 | // number. |
193 | Info->BlkNum = -2; |
194 | |
195 | // Add unvisited successors to the work list. |
196 | for (typename Traits::BlkSucc_iterator SI = |
197 | Traits::BlkSucc_begin(Info->BB), |
198 | E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) { |
199 | BBInfo *SuccInfo = BBMap[*SI]; |
200 | if (!SuccInfo || SuccInfo->BlkNum) |
201 | continue; |
202 | SuccInfo->BlkNum = -1; |
203 | WorkList.push_back(SuccInfo); |
204 | } |
205 | } |
206 | PseudoEntry->BlkNum = BlkNum; |
207 | return PseudoEntry; |
208 | } |
209 | |
210 | /// IntersectDominators - This is the dataflow lattice "meet" operation for |
211 | /// finding dominators. Given two basic blocks, it walks up the dominator |
212 | /// tree until it finds a common dominator of both. It uses the postorder |
213 | /// number of the blocks to determine how to do that. |
214 | BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) { |
215 | while (Blk1 != Blk2) { |
216 | while (Blk1->BlkNum < Blk2->BlkNum) { |
217 | Blk1 = Blk1->IDom; |
218 | if (!Blk1) |
219 | return Blk2; |
220 | } |
221 | while (Blk2->BlkNum < Blk1->BlkNum) { |
222 | Blk2 = Blk2->IDom; |
223 | if (!Blk2) |
224 | return Blk1; |
225 | } |
226 | } |
227 | return Blk1; |
228 | } |
229 | |
230 | /// FindDominators - Calculate the dominator tree for the subset of the CFG |
231 | /// corresponding to the basic blocks on the BlockList. This uses the |
232 | /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey |
233 | /// and Kennedy, published in Software--Practice and Experience, 2001, |
234 | /// 4:1-10. Because the CFG subset does not include any edges leading into |
235 | /// blocks that define the value, the results are not the usual dominator |
236 | /// tree. The CFG subset has a single pseudo-entry node with edges to a set |
237 | /// of root nodes for blocks that define the value. The dominators for this |
238 | /// subset CFG are not the standard dominators but they are adequate for |
239 | /// placing PHIs within the subset CFG. |
240 | void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) { |
241 | bool Changed; |
242 | do { |
243 | Changed = false; |
244 | // Iterate over the list in reverse order, i.e., forward on CFG edges. |
245 | for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), |
246 | E = BlockList->rend(); I != E; ++I) { |
247 | BBInfo *Info = *I; |
248 | BBInfo *NewIDom = nullptr; |
249 | |
250 | // Iterate through the block's predecessors. |
251 | for (unsigned p = 0; p != Info->NumPreds; ++p) { |
252 | BBInfo *Pred = Info->Preds[p]; |
253 | |
254 | // Treat an unreachable predecessor as a definition with 'undef'. |
255 | if (Pred->BlkNum == 0) { |
256 | Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater); |
257 | (*AvailableVals)[Pred->BB] = Pred->AvailableVal; |
258 | Pred->DefBB = Pred; |
259 | Pred->BlkNum = PseudoEntry->BlkNum; |
260 | PseudoEntry->BlkNum++; |
261 | } |
262 | |
263 | if (!NewIDom) |
264 | NewIDom = Pred; |
265 | else |
266 | NewIDom = IntersectDominators(NewIDom, Pred); |
267 | } |
268 | |
269 | // Check if the IDom value has changed. |
270 | if (NewIDom && NewIDom != Info->IDom) { |
271 | Info->IDom = NewIDom; |
272 | Changed = true; |
273 | } |
274 | } |
275 | } while (Changed); |
276 | } |
277 | |
278 | /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for |
279 | /// any blocks containing definitions of the value. If one is found, then |
280 | /// the successor of Pred is in the dominance frontier for the definition, |
281 | /// and this function returns true. |
282 | bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) { |
283 | for (; Pred != IDom; Pred = Pred->IDom) { |
284 | if (Pred->DefBB == Pred) |
285 | return true; |
286 | } |
287 | return false; |
288 | } |
289 | |
290 | /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers |
291 | /// of the known definitions. Iteratively add PHIs in the dom frontiers |
292 | /// until nothing changes. Along the way, keep track of the nearest |
293 | /// dominating definitions for non-PHI blocks. |
294 | void FindPHIPlacement(BlockListTy *BlockList) { |
295 | bool Changed; |
296 | do { |
297 | Changed = false; |
298 | // Iterate over the list in reverse order, i.e., forward on CFG edges. |
299 | for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), |
300 | E = BlockList->rend(); I != E; ++I) { |
301 | BBInfo *Info = *I; |
302 | |
303 | // If this block already needs a PHI, there is nothing to do here. |
304 | if (Info->DefBB == Info) |
305 | continue; |
306 | |
307 | // Default to use the same def as the immediate dominator. |
308 | BBInfo *NewDefBB = Info->IDom->DefBB; |
309 | for (unsigned p = 0; p != Info->NumPreds; ++p) { |
310 | if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) { |
311 | // Need a PHI here. |
312 | NewDefBB = Info; |
313 | break; |
314 | } |
315 | } |
316 | |
317 | // Check if anything changed. |
318 | if (NewDefBB != Info->DefBB) { |
319 | Info->DefBB = NewDefBB; |
320 | Changed = true; |
321 | } |
322 | } |
323 | } while (Changed); |
324 | } |
325 | |
326 | /// FindAvailableVal - If this block requires a PHI, first check if an |
327 | /// existing PHI matches the PHI placement and reaching definitions computed |
328 | /// earlier, and if not, create a new PHI. Visit all the block's |
329 | /// predecessors to calculate the available value for each one and fill in |
330 | /// the incoming values for a new PHI. |
331 | void FindAvailableVals(BlockListTy *BlockList) { |
332 | // Go through the worklist in forward order (i.e., backward through the CFG) |
333 | // and check if existing PHIs can be used. If not, create empty PHIs where |
334 | // they are needed. |
335 | for (typename BlockListTy::iterator I = BlockList->begin(), |
336 | E = BlockList->end(); I != E; ++I) { |
337 | BBInfo *Info = *I; |
338 | // Check if there needs to be a PHI in BB. |
339 | if (Info->DefBB != Info) |
340 | continue; |
341 | |
342 | // Look for an existing PHI. |
343 | FindExistingPHI(Info->BB, BlockList); |
344 | if (Info->AvailableVal) |
345 | continue; |
346 | |
347 | ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater); |
348 | Info->AvailableVal = PHI; |
349 | (*AvailableVals)[Info->BB] = PHI; |
350 | } |
351 | |
352 | // Now go back through the worklist in reverse order to fill in the |
353 | // arguments for any new PHIs added in the forward traversal. |
354 | for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(), |
355 | E = BlockList->rend(); I != E; ++I) { |
356 | BBInfo *Info = *I; |
357 | |
358 | if (Info->DefBB != Info) { |
359 | // Record the available value to speed up subsequent uses of this |
360 | // SSAUpdater for the same value. |
361 | (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal; |
362 | continue; |
363 | } |
364 | |
365 | // Check if this block contains a newly added PHI. |
366 | PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater); |
367 | if (!PHI) |
368 | continue; |
369 | |
370 | // Iterate through the block's predecessors. |
371 | for (unsigned p = 0; p != Info->NumPreds; ++p) { |
372 | BBInfo *PredInfo = Info->Preds[p]; |
373 | BlkT *Pred = PredInfo->BB; |
374 | // Skip to the nearest preceding definition. |
375 | if (PredInfo->DefBB != PredInfo) |
376 | PredInfo = PredInfo->DefBB; |
377 | Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred); |
378 | } |
379 | |
380 | LLVM_DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n")do { } while (false); |
381 | |
382 | // If the client wants to know about all new instructions, tell it. |
383 | if (InsertedPHIs) InsertedPHIs->push_back(PHI); |
384 | } |
385 | } |
386 | |
387 | /// FindExistingPHI - Look through the PHI nodes in a block to see if any of |
388 | /// them match what is needed. |
389 | void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) { |
390 | for (auto &SomePHI : BB->phis()) { |
391 | if (CheckIfPHIMatches(&SomePHI)) { |
392 | RecordMatchingPHIs(BlockList); |
393 | break; |
394 | } |
395 | // Match failed: clear all the PHITag values. |
396 | for (typename BlockListTy::iterator I = BlockList->begin(), |
397 | E = BlockList->end(); I != E; ++I) |
398 | (*I)->PHITag = nullptr; |
399 | } |
400 | } |
401 | |
402 | /// CheckIfPHIMatches - Check if a PHI node matches the placement and values |
403 | /// in the BBMap. |
404 | bool CheckIfPHIMatches(PhiT *PHI) { |
405 | SmallVector<PhiT *, 20> WorkList; |
406 | WorkList.push_back(PHI); |
407 | |
408 | // Mark that the block containing this PHI has been visited. |
409 | BBMap[PHI->getParent()]->PHITag = PHI; |
410 | |
411 | while (!WorkList.empty()) { |
412 | PHI = WorkList.pop_back_val(); |
413 | |
414 | // Iterate through the PHI's incoming values. |
415 | for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI), |
416 | E = Traits::PHI_end(PHI); I != E; ++I) { |
417 | ValT IncomingVal = I.getIncomingValue(); |
418 | BBInfo *PredInfo = BBMap[I.getIncomingBlock()]; |
419 | // Skip to the nearest preceding definition. |
420 | if (PredInfo->DefBB != PredInfo) |
421 | PredInfo = PredInfo->DefBB; |
422 | |
423 | // Check if it matches the expected value. |
424 | if (PredInfo->AvailableVal) { |
425 | if (IncomingVal == PredInfo->AvailableVal) |
426 | continue; |
427 | return false; |
428 | } |
429 | |
430 | // Check if the value is a PHI in the correct block. |
431 | PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater); |
432 | if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB) |
433 | return false; |
434 | |
435 | // If this block has already been visited, check if this PHI matches. |
436 | if (PredInfo->PHITag) { |
437 | if (IncomingPHIVal == PredInfo->PHITag) |
438 | continue; |
439 | return false; |
440 | } |
441 | PredInfo->PHITag = IncomingPHIVal; |
442 | |
443 | WorkList.push_back(IncomingPHIVal); |
444 | } |
445 | } |
446 | return true; |
447 | } |
448 | |
449 | /// RecordMatchingPHIs - For each PHI node that matches, record it in both |
450 | /// the BBMap and the AvailableVals mapping. |
451 | void RecordMatchingPHIs(BlockListTy *BlockList) { |
452 | for (typename BlockListTy::iterator I = BlockList->begin(), |
453 | E = BlockList->end(); I != E; ++I) |
454 | if (PhiT *PHI = (*I)->PHITag) { |
455 | BlkT *BB = PHI->getParent(); |
456 | ValT PHIVal = Traits::GetPHIValue(PHI); |
457 | (*AvailableVals)[BB] = PHIVal; |
458 | BBMap[BB]->AvailableVal = PHIVal; |
459 | } |
460 | } |
461 | }; |
462 | |
463 | } // end namespace llvm |
464 | |
465 | #undef DEBUG_TYPE"livedebugvalues" // "ssaupdater" |
466 | |
467 | #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H |
1 | //===- Allocator.h - Simple memory allocation abstraction -------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | /// \file |
9 | /// |
10 | /// This file defines the BumpPtrAllocator interface. BumpPtrAllocator conforms |
11 | /// to the LLVM "Allocator" concept and is similar to MallocAllocator, but |
12 | /// objects cannot be deallocated. Their lifetime is tied to the lifetime of the |
13 | /// allocator. |
14 | /// |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef LLVM_SUPPORT_ALLOCATOR_H |
18 | #define LLVM_SUPPORT_ALLOCATOR_H |
19 | |
20 | #include "llvm/ADT/Optional.h" |
21 | #include "llvm/ADT/SmallVector.h" |
22 | #include "llvm/Support/Alignment.h" |
23 | #include "llvm/Support/AllocatorBase.h" |
24 | #include "llvm/Support/Compiler.h" |
25 | #include "llvm/Support/ErrorHandling.h" |
26 | #include "llvm/Support/MathExtras.h" |
27 | #include "llvm/Support/MemAlloc.h" |
28 | #include <algorithm> |
29 | #include <cassert> |
30 | #include <cstddef> |
31 | #include <cstdint> |
32 | #include <cstdlib> |
33 | #include <iterator> |
34 | #include <type_traits> |
35 | #include <utility> |
36 | |
37 | namespace llvm { |
38 | |
39 | namespace detail { |
40 | |
41 | // We call out to an external function to actually print the message as the |
42 | // printing code uses Allocator.h in its implementation. |
43 | void printBumpPtrAllocatorStats(unsigned NumSlabs, size_t BytesAllocated, |
44 | size_t TotalMemory); |
45 | |
46 | } // end namespace detail |
47 | |
48 | /// Allocate memory in an ever growing pool, as if by bump-pointer. |
49 | /// |
50 | /// This isn't strictly a bump-pointer allocator as it uses backing slabs of |
51 | /// memory rather than relying on a boundless contiguous heap. However, it has |
52 | /// bump-pointer semantics in that it is a monotonically growing pool of memory |
53 | /// where every allocation is found by merely allocating the next N bytes in |
54 | /// the slab, or the next N bytes in the next slab. |
55 | /// |
56 | /// Note that this also has a threshold for forcing allocations above a certain |
57 | /// size into their own slab. |
58 | /// |
59 | /// The BumpPtrAllocatorImpl template defaults to using a MallocAllocator |
60 | /// object, which wraps malloc, to allocate memory, but it can be changed to |
61 | /// use a custom allocator. |
62 | /// |
63 | /// The GrowthDelay specifies after how many allocated slabs the allocator |
64 | /// increases the size of the slabs. |
65 | template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096, |
66 | size_t SizeThreshold = SlabSize, size_t GrowthDelay = 128> |
67 | class BumpPtrAllocatorImpl |
68 | : public AllocatorBase<BumpPtrAllocatorImpl<AllocatorT, SlabSize, |
69 | SizeThreshold, GrowthDelay>>, |
70 | private AllocatorT { |
71 | public: |
72 | static_assert(SizeThreshold <= SlabSize, |
73 | "The SizeThreshold must be at most the SlabSize to ensure " |
74 | "that objects larger than a slab go into their own memory " |
75 | "allocation."); |
76 | static_assert(GrowthDelay > 0, |
77 | "GrowthDelay must be at least 1 which already increases the" |
78 | "slab size after each allocated slab."); |
79 | |
80 | BumpPtrAllocatorImpl() = default; |
81 | |
82 | template <typename T> |
83 | BumpPtrAllocatorImpl(T &&Allocator) |
84 | : AllocatorT(std::forward<T &&>(Allocator)) {} |
85 | |
86 | // Manually implement a move constructor as we must clear the old allocator's |
87 | // slabs as a matter of correctness. |
88 | BumpPtrAllocatorImpl(BumpPtrAllocatorImpl &&Old) |
89 | : AllocatorT(static_cast<AllocatorT &&>(Old)), CurPtr(Old.CurPtr), |
90 | End(Old.End), Slabs(std::move(Old.Slabs)), |
91 | CustomSizedSlabs(std::move(Old.CustomSizedSlabs)), |
92 | BytesAllocated(Old.BytesAllocated), RedZoneSize(Old.RedZoneSize) { |
93 | Old.CurPtr = Old.End = nullptr; |
94 | Old.BytesAllocated = 0; |
95 | Old.Slabs.clear(); |
96 | Old.CustomSizedSlabs.clear(); |
97 | } |
98 | |
99 | ~BumpPtrAllocatorImpl() { |
100 | DeallocateSlabs(Slabs.begin(), Slabs.end()); |
101 | DeallocateCustomSizedSlabs(); |
102 | } |
103 | |
104 | BumpPtrAllocatorImpl &operator=(BumpPtrAllocatorImpl &&RHS) { |
105 | DeallocateSlabs(Slabs.begin(), Slabs.end()); |
106 | DeallocateCustomSizedSlabs(); |
107 | |
108 | CurPtr = RHS.CurPtr; |
109 | End = RHS.End; |
110 | BytesAllocated = RHS.BytesAllocated; |
111 | RedZoneSize = RHS.RedZoneSize; |
112 | Slabs = std::move(RHS.Slabs); |
113 | CustomSizedSlabs = std::move(RHS.CustomSizedSlabs); |
114 | AllocatorT::operator=(static_cast<AllocatorT &&>(RHS)); |
115 | |
116 | RHS.CurPtr = RHS.End = nullptr; |
117 | RHS.BytesAllocated = 0; |
118 | RHS.Slabs.clear(); |
119 | RHS.CustomSizedSlabs.clear(); |
120 | return *this; |
121 | } |
122 | |
123 | /// Deallocate all but the current slab and reset the current pointer |
124 | /// to the beginning of it, freeing all memory allocated so far. |
125 | void Reset() { |
126 | // Deallocate all but the first slab, and deallocate all custom-sized slabs. |
127 | DeallocateCustomSizedSlabs(); |
128 | CustomSizedSlabs.clear(); |
129 | |
130 | if (Slabs.empty()) |
131 | return; |
132 | |
133 | // Reset the state. |
134 | BytesAllocated = 0; |
135 | CurPtr = (char *)Slabs.front(); |
136 | End = CurPtr + SlabSize; |
137 | |
138 | __asan_poison_memory_region(*Slabs.begin(), computeSlabSize(0)); |
139 | DeallocateSlabs(std::next(Slabs.begin()), Slabs.end()); |
140 | Slabs.erase(std::next(Slabs.begin()), Slabs.end()); |
141 | } |
142 | |
143 | /// Allocate space at the specified alignment. |
144 | LLVM_ATTRIBUTE_RETURNS_NONNULL__attribute__((returns_nonnull)) LLVM_ATTRIBUTE_RETURNS_NOALIAS__attribute__((__malloc__)) void * |
145 | Allocate(size_t Size, Align Alignment) { |
146 | // Keep track of how many bytes we've allocated. |
147 | BytesAllocated += Size; |
148 | |
149 | size_t Adjustment = offsetToAlignedAddr(CurPtr, Alignment); |
150 | assert(Adjustment + Size >= Size && "Adjustment + Size must not overflow")((void)0); |
151 | |
152 | size_t SizeToAllocate = Size; |
153 | #if LLVM_ADDRESS_SANITIZER_BUILD0 |
154 | // Add trailing bytes as a "red zone" under ASan. |
155 | SizeToAllocate += RedZoneSize; |
156 | #endif |
157 | |
158 | // Check if we have enough space. |
159 | if (Adjustment + SizeToAllocate <= size_t(End - CurPtr)) { |
160 | char *AlignedPtr = CurPtr + Adjustment; |
161 | CurPtr = AlignedPtr + SizeToAllocate; |
162 | // Update the allocation point of this memory block in MemorySanitizer. |
163 | // Without this, MemorySanitizer messages for values originated from here |
164 | // will point to the allocation of the entire slab. |
165 | __msan_allocated_memory(AlignedPtr, Size); |
166 | // Similarly, tell ASan about this space. |
167 | __asan_unpoison_memory_region(AlignedPtr, Size); |
168 | return AlignedPtr; |
169 | } |
170 | |
171 | // If Size is really big, allocate a separate slab for it. |
172 | size_t PaddedSize = SizeToAllocate + Alignment.value() - 1; |
173 | if (PaddedSize > SizeThreshold) { |
174 | void *NewSlab = |
175 | AllocatorT::Allocate(PaddedSize, alignof(std::max_align_t)); |
176 | // We own the new slab and don't want anyone reading anyting other than |
177 | // pieces returned from this method. So poison the whole slab. |
178 | __asan_poison_memory_region(NewSlab, PaddedSize); |
179 | CustomSizedSlabs.push_back(std::make_pair(NewSlab, PaddedSize)); |
180 | |
181 | uintptr_t AlignedAddr = alignAddr(NewSlab, Alignment); |
182 | assert(AlignedAddr + Size <= (uintptr_t)NewSlab + PaddedSize)((void)0); |
183 | char *AlignedPtr = (char*)AlignedAddr; |
184 | __msan_allocated_memory(AlignedPtr, Size); |
185 | __asan_unpoison_memory_region(AlignedPtr, Size); |
186 | return AlignedPtr; |
187 | } |
188 | |
189 | // Otherwise, start a new slab and try again. |
190 | StartNewSlab(); |
191 | uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment); |
192 | assert(AlignedAddr + SizeToAllocate <= (uintptr_t)End &&((void)0) |
193 | "Unable to allocate memory!")((void)0); |
194 | char *AlignedPtr = (char*)AlignedAddr; |
195 | CurPtr = AlignedPtr + SizeToAllocate; |
196 | __msan_allocated_memory(AlignedPtr, Size); |
197 | __asan_unpoison_memory_region(AlignedPtr, Size); |
198 | return AlignedPtr; |
199 | } |
200 | |
201 | inline LLVM_ATTRIBUTE_RETURNS_NONNULL__attribute__((returns_nonnull)) LLVM_ATTRIBUTE_RETURNS_NOALIAS__attribute__((__malloc__)) void * |
202 | Allocate(size_t Size, size_t Alignment) { |
203 | assert(Alignment > 0 && "0-byte alignment is not allowed. Use 1 instead.")((void)0); |
204 | return Allocate(Size, Align(Alignment)); |
205 | } |
206 | |
207 | // Pull in base class overloads. |
208 | using AllocatorBase<BumpPtrAllocatorImpl>::Allocate; |
209 | |
210 | // Bump pointer allocators are expected to never free their storage; and |
211 | // clients expect pointers to remain valid for non-dereferencing uses even |
212 | // after deallocation. |
213 | void Deallocate(const void *Ptr, size_t Size, size_t /*Alignment*/) { |
214 | __asan_poison_memory_region(Ptr, Size); |
215 | } |
216 | |
217 | // Pull in base class overloads. |
218 | using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate; |
219 | |
220 | size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); } |
221 | |
222 | /// \return An index uniquely and reproducibly identifying |
223 | /// an input pointer \p Ptr in the given allocator. |
224 | /// The returned value is negative iff the object is inside a custom-size |
225 | /// slab. |
226 | /// Returns an empty optional if the pointer is not found in the allocator. |
227 | llvm::Optional<int64_t> identifyObject(const void *Ptr) { |
228 | const char *P = static_cast<const char *>(Ptr); |
229 | int64_t InSlabIdx = 0; |
230 | for (size_t Idx = 0, E = Slabs.size(); Idx < E; Idx++) { |
231 | const char *S = static_cast<const char *>(Slabs[Idx]); |
232 | if (P >= S && P < S + computeSlabSize(Idx)) |
233 | return InSlabIdx + static_cast<int64_t>(P - S); |
234 | InSlabIdx += static_cast<int64_t>(computeSlabSize(Idx)); |
235 | } |
236 | |
237 | // Use negative index to denote custom sized slabs. |
238 | int64_t InCustomSizedSlabIdx = -1; |
239 | for (size_t Idx = 0, E = CustomSizedSlabs.size(); Idx < E; Idx++) { |
240 | const char *S = static_cast<const char *>(CustomSizedSlabs[Idx].first); |
241 | size_t Size = CustomSizedSlabs[Idx].second; |
242 | if (P >= S && P < S + Size) |
243 | return InCustomSizedSlabIdx - static_cast<int64_t>(P - S); |
244 | InCustomSizedSlabIdx -= static_cast<int64_t>(Size); |
245 | } |
246 | return None; |
247 | } |
248 | |
249 | /// A wrapper around identifyObject that additionally asserts that |
250 | /// the object is indeed within the allocator. |
251 | /// \return An index uniquely and reproducibly identifying |
252 | /// an input pointer \p Ptr in the given allocator. |
253 | int64_t identifyKnownObject(const void *Ptr) { |
254 | Optional<int64_t> Out = identifyObject(Ptr); |
255 | assert(Out && "Wrong allocator used")((void)0); |
256 | return *Out; |
257 | } |
258 | |
259 | /// A wrapper around identifyKnownObject. Accepts type information |
260 | /// about the object and produces a smaller identifier by relying on |
261 | /// the alignment information. Note that sub-classes may have different |
262 | /// alignment, so the most base class should be passed as template parameter |
263 | /// in order to obtain correct results. For that reason automatic template |
264 | /// parameter deduction is disabled. |
265 | /// \return An index uniquely and reproducibly identifying |
266 | /// an input pointer \p Ptr in the given allocator. This identifier is |
267 | /// different from the ones produced by identifyObject and |
268 | /// identifyAlignedObject. |
269 | template <typename T> |
270 | int64_t identifyKnownAlignedObject(const void *Ptr) { |
271 | int64_t Out = identifyKnownObject(Ptr); |
272 | assert(Out % alignof(T) == 0 && "Wrong alignment information")((void)0); |
273 | return Out / alignof(T); |
274 | } |
275 | |
276 | size_t getTotalMemory() const { |
277 | size_t TotalMemory = 0; |
278 | for (auto I = Slabs.begin(), E = Slabs.end(); I != E; ++I) |
279 | TotalMemory += computeSlabSize(std::distance(Slabs.begin(), I)); |
280 | for (auto &PtrAndSize : CustomSizedSlabs) |
281 | TotalMemory += PtrAndSize.second; |
282 | return TotalMemory; |
283 | } |
284 | |
285 | size_t getBytesAllocated() const { return BytesAllocated; } |
286 | |
287 | void setRedZoneSize(size_t NewSize) { |
288 | RedZoneSize = NewSize; |
289 | } |
290 | |
291 | void PrintStats() const { |
292 | detail::printBumpPtrAllocatorStats(Slabs.size(), BytesAllocated, |
293 | getTotalMemory()); |
294 | } |
295 | |
296 | private: |
297 | /// The current pointer into the current slab. |
298 | /// |
299 | /// This points to the next free byte in the slab. |
300 | char *CurPtr = nullptr; |
301 | |
302 | /// The end of the current slab. |
303 | char *End = nullptr; |
304 | |
305 | /// The slabs allocated so far. |
306 | SmallVector<void *, 4> Slabs; |
307 | |
308 | /// Custom-sized slabs allocated for too-large allocation requests. |
309 | SmallVector<std::pair<void *, size_t>, 0> CustomSizedSlabs; |
310 | |
311 | /// How many bytes we've allocated. |
312 | /// |
313 | /// Used so that we can compute how much space was wasted. |
314 | size_t BytesAllocated = 0; |
315 | |
316 | /// The number of bytes to put between allocations when running under |
317 | /// a sanitizer. |
318 | size_t RedZoneSize = 1; |
319 | |
320 | static size_t computeSlabSize(unsigned SlabIdx) { |
321 | // Scale the actual allocated slab size based on the number of slabs |
322 | // allocated. Every GrowthDelay slabs allocated, we double |
323 | // the allocated size to reduce allocation frequency, but saturate at |
324 | // multiplying the slab size by 2^30. |
325 | return SlabSize * |
326 | ((size_t)1 << std::min<size_t>(30, SlabIdx / GrowthDelay)); |
327 | } |
328 | |
329 | /// Allocate a new slab and move the bump pointers over into the new |
330 | /// slab, modifying CurPtr and End. |
331 | void StartNewSlab() { |
332 | size_t AllocatedSlabSize = computeSlabSize(Slabs.size()); |
333 | |
334 | void *NewSlab = |
335 | AllocatorT::Allocate(AllocatedSlabSize, alignof(std::max_align_t)); |
336 | // We own the new slab and don't want anyone reading anything other than |
337 | // pieces returned from this method. So poison the whole slab. |
338 | __asan_poison_memory_region(NewSlab, AllocatedSlabSize); |
339 | |
340 | Slabs.push_back(NewSlab); |
341 | CurPtr = (char *)(NewSlab); |
342 | End = ((char *)NewSlab) + AllocatedSlabSize; |
343 | } |
344 | |
345 | /// Deallocate a sequence of slabs. |
346 | void DeallocateSlabs(SmallVectorImpl<void *>::iterator I, |
347 | SmallVectorImpl<void *>::iterator E) { |
348 | for (; I != E; ++I) { |
349 | size_t AllocatedSlabSize = |
350 | computeSlabSize(std::distance(Slabs.begin(), I)); |
351 | AllocatorT::Deallocate(*I, AllocatedSlabSize, alignof(std::max_align_t)); |
352 | } |
353 | } |
354 | |
355 | /// Deallocate all memory for custom sized slabs. |
356 | void DeallocateCustomSizedSlabs() { |
357 | for (auto &PtrAndSize : CustomSizedSlabs) { |
358 | void *Ptr = PtrAndSize.first; |
359 | size_t Size = PtrAndSize.second; |
360 | AllocatorT::Deallocate(Ptr, Size, alignof(std::max_align_t)); |
361 | } |
362 | } |
363 | |
364 | template <typename T> friend class SpecificBumpPtrAllocator; |
365 | }; |
366 | |
367 | /// The standard BumpPtrAllocator which just uses the default template |
368 | /// parameters. |
369 | typedef BumpPtrAllocatorImpl<> BumpPtrAllocator; |
370 | |
371 | /// A BumpPtrAllocator that allows only elements of a specific type to be |
372 | /// allocated. |
373 | /// |
374 | /// This allows calling the destructor in DestroyAll() and when the allocator is |
375 | /// destroyed. |
376 | template <typename T> class SpecificBumpPtrAllocator { |
377 | BumpPtrAllocator Allocator; |
378 | |
379 | public: |
380 | SpecificBumpPtrAllocator() { |
381 | // Because SpecificBumpPtrAllocator walks the memory to call destructors, |
382 | // it can't have red zones between allocations. |
383 | Allocator.setRedZoneSize(0); |
384 | } |
385 | SpecificBumpPtrAllocator(SpecificBumpPtrAllocator &&Old) |
386 | : Allocator(std::move(Old.Allocator)) {} |
387 | ~SpecificBumpPtrAllocator() { DestroyAll(); } |
388 | |
389 | SpecificBumpPtrAllocator &operator=(SpecificBumpPtrAllocator &&RHS) { |
390 | Allocator = std::move(RHS.Allocator); |
391 | return *this; |
392 | } |
393 | |
394 | /// Call the destructor of each allocated object and deallocate all but the |
395 | /// current slab and reset the current pointer to the beginning of it, freeing |
396 | /// all memory allocated so far. |
397 | void DestroyAll() { |
398 | auto DestroyElements = [](char *Begin, char *End) { |
399 | assert(Begin == (char *)alignAddr(Begin, Align::Of<T>()))((void)0); |
400 | for (char *Ptr = Begin; Ptr + sizeof(T) <= End; Ptr += sizeof(T)) |
401 | reinterpret_cast<T *>(Ptr)->~T(); |
402 | }; |
403 | |
404 | for (auto I = Allocator.Slabs.begin(), E = Allocator.Slabs.end(); I != E; |
405 | ++I) { |
406 | size_t AllocatedSlabSize = BumpPtrAllocator::computeSlabSize( |
407 | std::distance(Allocator.Slabs.begin(), I)); |
408 | char *Begin = (char *)alignAddr(*I, Align::Of<T>()); |
409 | char *End = *I == Allocator.Slabs.back() ? Allocator.CurPtr |
410 | : (char *)*I + AllocatedSlabSize; |
411 | |
412 | DestroyElements(Begin, End); |
413 | } |
414 | |
415 | for (auto &PtrAndSize : Allocator.CustomSizedSlabs) { |
416 | void *Ptr = PtrAndSize.first; |
417 | size_t Size = PtrAndSize.second; |
418 | DestroyElements((char *)alignAddr(Ptr, Align::Of<T>()), |
419 | (char *)Ptr + Size); |
420 | } |
421 | |
422 | Allocator.Reset(); |
423 | } |
424 | |
425 | /// Allocate space for an array of objects without constructing them. |
426 | T *Allocate(size_t num = 1) { return Allocator.Allocate<T>(num); } |
427 | }; |
428 | |
429 | } // end namespace llvm |
430 | |
431 | template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold, |
432 | size_t GrowthDelay> |
433 | void * |
434 | operator new(size_t Size, |
435 | llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, SizeThreshold, |
436 | GrowthDelay> &Allocator) { |
437 | return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size), |
438 | alignof(std::max_align_t))); |
439 | } |
440 | |
441 | template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold, |
442 | size_t GrowthDelay> |
443 | void operator delete(void *, |
444 | llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize, |
445 | SizeThreshold, GrowthDelay> &) { |
446 | } |
447 | |
448 | #endif // LLVM_SUPPORT_ALLOCATOR_H |
1 | //===-- llvm/Support/Alignment.h - Useful alignment functions ---*- C++ -*-===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // This file contains types to represent alignments. | |||
10 | // They are instrumented to guarantee some invariants are preserved and prevent | |||
11 | // invalid manipulations. | |||
12 | // | |||
13 | // - Align represents an alignment in bytes, it is always set and always a valid | |||
14 | // power of two, its minimum value is 1 which means no alignment requirements. | |||
15 | // | |||
16 | // - MaybeAlign is an optional type, it may be undefined or set. When it's set | |||
17 | // you can get the underlying Align type by using the getValue() method. | |||
18 | // | |||
19 | //===----------------------------------------------------------------------===// | |||
20 | ||||
21 | #ifndef LLVM_SUPPORT_ALIGNMENT_H_ | |||
22 | #define LLVM_SUPPORT_ALIGNMENT_H_ | |||
23 | ||||
24 | #include "llvm/ADT/Optional.h" | |||
25 | #include "llvm/Support/MathExtras.h" | |||
26 | #include <cassert> | |||
27 | #ifndef NDEBUG1 | |||
28 | #include <string> | |||
29 | #endif // NDEBUG | |||
30 | ||||
31 | namespace llvm { | |||
32 | ||||
33 | #define ALIGN_CHECK_ISPOSITIVE(decl) \ | |||
34 | assert(decl > 0 && (#decl " should be defined"))((void)0) | |||
35 | ||||
36 | /// This struct is a compact representation of a valid (non-zero power of two) | |||
37 | /// alignment. | |||
38 | /// It is suitable for use as static global constants. | |||
39 | struct Align { | |||
40 | private: | |||
41 | uint8_t ShiftValue = 0; /// The log2 of the required alignment. | |||
42 | /// ShiftValue is less than 64 by construction. | |||
43 | ||||
44 | friend struct MaybeAlign; | |||
45 | friend unsigned Log2(Align); | |||
46 | friend bool operator==(Align Lhs, Align Rhs); | |||
47 | friend bool operator!=(Align Lhs, Align Rhs); | |||
48 | friend bool operator<=(Align Lhs, Align Rhs); | |||
49 | friend bool operator>=(Align Lhs, Align Rhs); | |||
50 | friend bool operator<(Align Lhs, Align Rhs); | |||
51 | friend bool operator>(Align Lhs, Align Rhs); | |||
52 | friend unsigned encode(struct MaybeAlign A); | |||
53 | friend struct MaybeAlign decodeMaybeAlign(unsigned Value); | |||
54 | ||||
55 | /// A trivial type to allow construction of constexpr Align. | |||
56 | /// This is currently needed to workaround a bug in GCC 5.3 which prevents | |||
57 | /// definition of constexpr assign operators. | |||
58 | /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic | |||
59 | /// FIXME: Remove this, make all assign operators constexpr and introduce user | |||
60 | /// defined literals when we don't have to support GCC 5.3 anymore. | |||
61 | /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain | |||
62 | struct LogValue { | |||
63 | uint8_t Log; | |||
64 | }; | |||
65 | ||||
66 | public: | |||
67 | /// Default is byte-aligned. | |||
68 | constexpr Align() = default; | |||
69 | /// Do not perform checks in case of copy/move construct/assign, because the | |||
70 | /// checks have been performed when building `Other`. | |||
71 | constexpr Align(const Align &Other) = default; | |||
72 | constexpr Align(Align &&Other) = default; | |||
73 | Align &operator=(const Align &Other) = default; | |||
74 | Align &operator=(Align &&Other) = default; | |||
75 | ||||
76 | explicit Align(uint64_t Value) { | |||
77 | assert(Value > 0 && "Value must not be 0")((void)0); | |||
78 | assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2")((void)0); | |||
79 | ShiftValue = Log2_64(Value); | |||
80 | assert(ShiftValue < 64 && "Broken invariant")((void)0); | |||
81 | } | |||
82 | ||||
83 | /// This is a hole in the type system and should not be abused. | |||
84 | /// Needed to interact with C for instance. | |||
85 | uint64_t value() const { return uint64_t(1) << ShiftValue; } | |||
| ||||
86 | ||||
87 | /// Allow constructions of constexpr Align. | |||
88 | template <size_t kValue> constexpr static LogValue Constant() { | |||
89 | return LogValue{static_cast<uint8_t>(CTLog2<kValue>())}; | |||
90 | } | |||
91 | ||||
92 | /// Allow constructions of constexpr Align from types. | |||
93 | /// Compile time equivalent to Align(alignof(T)). | |||
94 | template <typename T> constexpr static LogValue Of() { | |||
95 | return Constant<std::alignment_of<T>::value>(); | |||
96 | } | |||
97 | ||||
98 | /// Constexpr constructor from LogValue type. | |||
99 | constexpr Align(LogValue CA) : ShiftValue(CA.Log) {} | |||
100 | }; | |||
101 | ||||
102 | /// Treats the value 0 as a 1, so Align is always at least 1. | |||
103 | inline Align assumeAligned(uint64_t Value) { | |||
104 | return Value ? Align(Value) : Align(); | |||
105 | } | |||
106 | ||||
107 | /// This struct is a compact representation of a valid (power of two) or | |||
108 | /// undefined (0) alignment. | |||
109 | struct MaybeAlign : public llvm::Optional<Align> { | |||
110 | private: | |||
111 | using UP = llvm::Optional<Align>; | |||
112 | ||||
113 | public: | |||
114 | /// Default is undefined. | |||
115 | MaybeAlign() = default; | |||
116 | /// Do not perform checks in case of copy/move construct/assign, because the | |||
117 | /// checks have been performed when building `Other`. | |||
118 | MaybeAlign(const MaybeAlign &Other) = default; | |||
119 | MaybeAlign &operator=(const MaybeAlign &Other) = default; | |||
120 | MaybeAlign(MaybeAlign &&Other) = default; | |||
121 | MaybeAlign &operator=(MaybeAlign &&Other) = default; | |||
122 | ||||
123 | /// Use llvm::Optional<Align> constructor. | |||
124 | using UP::UP; | |||
125 | ||||
126 | explicit MaybeAlign(uint64_t Value) { | |||
127 | assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&((void)0) | |||
128 | "Alignment is neither 0 nor a power of 2")((void)0); | |||
129 | if (Value) | |||
130 | emplace(Value); | |||
131 | } | |||
132 | ||||
133 | /// For convenience, returns a valid alignment or 1 if undefined. | |||
134 | Align valueOrOne() const { return hasValue() ? getValue() : Align(); } | |||
135 | }; | |||
136 | ||||
137 | /// Checks that SizeInBytes is a multiple of the alignment. | |||
138 | inline bool isAligned(Align Lhs, uint64_t SizeInBytes) { | |||
139 | return SizeInBytes % Lhs.value() == 0; | |||
140 | } | |||
141 | ||||
142 | /// Checks that Addr is a multiple of the alignment. | |||
143 | inline bool isAddrAligned(Align Lhs, const void *Addr) { | |||
144 | return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr)); | |||
145 | } | |||
146 | ||||
147 | /// Returns a multiple of A needed to store `Size` bytes. | |||
148 | inline uint64_t alignTo(uint64_t Size, Align A) { | |||
149 | const uint64_t Value = A.value(); | |||
150 | // The following line is equivalent to `(Size + Value - 1) / Value * Value`. | |||
151 | ||||
152 | // The division followed by a multiplication can be thought of as a right | |||
153 | // shift followed by a left shift which zeros out the extra bits produced in | |||
154 | // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out | |||
155 | // are just zero. | |||
156 | ||||
157 | // Most compilers can generate this code but the pattern may be missed when | |||
158 | // multiple functions gets inlined. | |||
159 | return (Size + Value - 1) & ~(Value - 1U); | |||
160 | } | |||
161 | ||||
162 | /// If non-zero \p Skew is specified, the return value will be a minimal integer | |||
163 | /// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for | |||
164 | /// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p | |||
165 | /// Skew mod \p A'. | |||
166 | /// | |||
167 | /// Examples: | |||
168 | /// \code | |||
169 | /// alignTo(5, Align(8), 7) = 7 | |||
170 | /// alignTo(17, Align(8), 1) = 17 | |||
171 | /// alignTo(~0LL, Align(8), 3) = 3 | |||
172 | /// \endcode | |||
173 | inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) { | |||
174 | const uint64_t Value = A.value(); | |||
175 | Skew %= Value; | |||
176 | return ((Size + Value - 1 - Skew) & ~(Value - 1U)) + Skew; | |||
177 | } | |||
178 | ||||
179 | /// Returns a multiple of A needed to store `Size` bytes. | |||
180 | /// Returns `Size` if current alignment is undefined. | |||
181 | inline uint64_t alignTo(uint64_t Size, MaybeAlign A) { | |||
182 | return A ? alignTo(Size, A.getValue()) : Size; | |||
183 | } | |||
184 | ||||
185 | /// Aligns `Addr` to `Alignment` bytes, rounding up. | |||
186 | inline uintptr_t alignAddr(const void *Addr, Align Alignment) { | |||
187 | uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr); | |||
188 | assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=((void)0) | |||
189 | ArithAddr &&((void)0) | |||
190 | "Overflow")((void)0); | |||
191 | return alignTo(ArithAddr, Alignment); | |||
192 | } | |||
193 | ||||
194 | /// Returns the offset to the next integer (mod 2**64) that is greater than | |||
195 | /// or equal to \p Value and is a multiple of \p Align. | |||
196 | inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) { | |||
197 | return alignTo(Value, Alignment) - Value; | |||
198 | } | |||
199 | ||||
200 | /// Returns the necessary adjustment for aligning `Addr` to `Alignment` | |||
201 | /// bytes, rounding up. | |||
202 | inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) { | |||
203 | return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment); | |||
204 | } | |||
205 | ||||
206 | /// Returns the log2 of the alignment. | |||
207 | inline unsigned Log2(Align A) { return A.ShiftValue; } | |||
208 | ||||
209 | /// Returns the alignment that satisfies both alignments. | |||
210 | /// Same semantic as MinAlign. | |||
211 | inline Align commonAlignment(Align A, Align B) { return std::min(A, B); } | |||
212 | ||||
213 | /// Returns the alignment that satisfies both alignments. | |||
214 | /// Same semantic as MinAlign. | |||
215 | inline Align commonAlignment(Align A, uint64_t Offset) { | |||
216 | return Align(MinAlign(A.value(), Offset)); | |||
217 | } | |||
218 | ||||
219 | /// Returns the alignment that satisfies both alignments. | |||
220 | /// Same semantic as MinAlign. | |||
221 | inline MaybeAlign commonAlignment(MaybeAlign A, MaybeAlign B) { | |||
222 | return A && B ? commonAlignment(*A, *B) : A ? A : B; | |||
223 | } | |||
224 | ||||
225 | /// Returns the alignment that satisfies both alignments. | |||
226 | /// Same semantic as MinAlign. | |||
227 | inline MaybeAlign commonAlignment(MaybeAlign A, uint64_t Offset) { | |||
228 | return MaybeAlign(MinAlign((*A).value(), Offset)); | |||
229 | } | |||
230 | ||||
231 | /// Returns a representation of the alignment that encodes undefined as 0. | |||
232 | inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; } | |||
233 | ||||
234 | /// Dual operation of the encode function above. | |||
235 | inline MaybeAlign decodeMaybeAlign(unsigned Value) { | |||
236 | if (Value == 0) | |||
237 | return MaybeAlign(); | |||
238 | Align Out; | |||
239 | Out.ShiftValue = Value - 1; | |||
240 | return Out; | |||
241 | } | |||
242 | ||||
243 | /// Returns a representation of the alignment, the encoded value is positive by | |||
244 | /// definition. | |||
245 | inline unsigned encode(Align A) { return encode(MaybeAlign(A)); } | |||
246 | ||||
247 | /// Comparisons between Align and scalars. Rhs must be positive. | |||
248 | inline bool operator==(Align Lhs, uint64_t Rhs) { | |||
249 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
250 | return Lhs.value() == Rhs; | |||
251 | } | |||
252 | inline bool operator!=(Align Lhs, uint64_t Rhs) { | |||
253 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
254 | return Lhs.value() != Rhs; | |||
255 | } | |||
256 | inline bool operator<=(Align Lhs, uint64_t Rhs) { | |||
257 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
258 | return Lhs.value() <= Rhs; | |||
259 | } | |||
260 | inline bool operator>=(Align Lhs, uint64_t Rhs) { | |||
261 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
262 | return Lhs.value() >= Rhs; | |||
263 | } | |||
264 | inline bool operator<(Align Lhs, uint64_t Rhs) { | |||
265 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
266 | return Lhs.value() < Rhs; | |||
267 | } | |||
268 | inline bool operator>(Align Lhs, uint64_t Rhs) { | |||
269 | ALIGN_CHECK_ISPOSITIVE(Rhs); | |||
270 | return Lhs.value() > Rhs; | |||
271 | } | |||
272 | ||||
273 | /// Comparisons between MaybeAlign and scalars. | |||
274 | inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) { | |||
275 | return Lhs ? (*Lhs).value() == Rhs : Rhs == 0; | |||
276 | } | |||
277 | inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) { | |||
278 | return Lhs ? (*Lhs).value() != Rhs : Rhs != 0; | |||
279 | } | |||
280 | ||||
281 | /// Comparisons operators between Align. | |||
282 | inline bool operator==(Align Lhs, Align Rhs) { | |||
283 | return Lhs.ShiftValue == Rhs.ShiftValue; | |||
284 | } | |||
285 | inline bool operator!=(Align Lhs, Align Rhs) { | |||
286 | return Lhs.ShiftValue != Rhs.ShiftValue; | |||
287 | } | |||
288 | inline bool operator<=(Align Lhs, Align Rhs) { | |||
289 | return Lhs.ShiftValue <= Rhs.ShiftValue; | |||
290 | } | |||
291 | inline bool operator>=(Align Lhs, Align Rhs) { | |||
292 | return Lhs.ShiftValue >= Rhs.ShiftValue; | |||
293 | } | |||
294 | inline bool operator<(Align Lhs, Align Rhs) { | |||
295 | return Lhs.ShiftValue < Rhs.ShiftValue; | |||
296 | } | |||
297 | inline bool operator>(Align Lhs, Align Rhs) { | |||
298 | return Lhs.ShiftValue > Rhs.ShiftValue; | |||
299 | } | |||
300 | ||||
301 | // Don't allow relational comparisons with MaybeAlign. | |||
302 | bool operator<=(Align Lhs, MaybeAlign Rhs) = delete; | |||
303 | bool operator>=(Align Lhs, MaybeAlign Rhs) = delete; | |||
304 | bool operator<(Align Lhs, MaybeAlign Rhs) = delete; | |||
305 | bool operator>(Align Lhs, MaybeAlign Rhs) = delete; | |||
306 | ||||
307 | bool operator<=(MaybeAlign Lhs, Align Rhs) = delete; | |||
308 | bool operator>=(MaybeAlign Lhs, Align Rhs) = delete; | |||
309 | bool operator<(MaybeAlign Lhs, Align Rhs) = delete; | |||
310 | bool operator>(MaybeAlign Lhs, Align Rhs) = delete; | |||
311 | ||||
312 | bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
313 | bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
314 | bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
315 | bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete; | |||
316 | ||||
317 | inline Align operator*(Align Lhs, uint64_t Rhs) { | |||
318 | assert(Rhs > 0 && "Rhs must be positive")((void)0); | |||
319 | return Align(Lhs.value() * Rhs); | |||
320 | } | |||
321 | ||||
322 | inline MaybeAlign operator*(MaybeAlign Lhs, uint64_t Rhs) { | |||
323 | assert(Rhs > 0 && "Rhs must be positive")((void)0); | |||
324 | return Lhs ? Lhs.getValue() * Rhs : MaybeAlign(); | |||
325 | } | |||
326 | ||||
327 | inline Align operator/(Align Lhs, uint64_t Divisor) { | |||
328 | assert(llvm::isPowerOf2_64(Divisor) &&((void)0) | |||
329 | "Divisor must be positive and a power of 2")((void)0); | |||
330 | assert(Lhs != 1 && "Can't halve byte alignment")((void)0); | |||
331 | return Align(Lhs.value() / Divisor); | |||
332 | } | |||
333 | ||||
334 | inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) { | |||
335 | assert(llvm::isPowerOf2_64(Divisor) &&((void)0) | |||
336 | "Divisor must be positive and a power of 2")((void)0); | |||
337 | return Lhs ? Lhs.getValue() / Divisor : MaybeAlign(); | |||
338 | } | |||
339 | ||||
340 | inline Align max(MaybeAlign Lhs, Align Rhs) { | |||
341 | return Lhs && *Lhs > Rhs ? *Lhs : Rhs; | |||
342 | } | |||
343 | ||||
344 | inline Align max(Align Lhs, MaybeAlign Rhs) { | |||
345 | return Rhs && *Rhs > Lhs ? *Rhs : Lhs; | |||
346 | } | |||
347 | ||||
348 | #ifndef NDEBUG1 | |||
349 | // For usage in LLVM_DEBUG macros. | |||
350 | inline std::string DebugStr(const Align &A) { | |||
351 | return std::to_string(A.value()); | |||
352 | } | |||
353 | // For usage in LLVM_DEBUG macros. | |||
354 | inline std::string DebugStr(const MaybeAlign &MA) { | |||
355 | if (MA) | |||
356 | return std::to_string(MA->value()); | |||
357 | return "None"; | |||
358 | } | |||
359 | #endif // NDEBUG | |||
360 | ||||
361 | #undef ALIGN_CHECK_ISPOSITIVE | |||
362 | ||||
363 | } // namespace llvm | |||
364 | ||||
365 | #endif // LLVM_SUPPORT_ALIGNMENT_H_ |