Bug Summary

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'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name InstrRefBasedImpl.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -D PIC -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -D_RET_PROTECTOR -ret-protector -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

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
204using 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.
212static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
213 cl::desc("Act like old LiveDebugValues did"),
214 cl::init(false));
215
216namespace {
217
218// The location at which a spilled value resides. It consists of a register and
219// an offset.
220struct 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
235class 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
242public:
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
281class LocIdxToIndexFunctor {
282public:
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.
299class 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
305public:
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
360namespace {
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.
364class DbgValueProperties {
365public:
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.
409class MLocTracker {
410public:
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.
799class DbgValue {
800public:
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.
883using FragmentOfVar =
884 std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
885using 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.
892class VLocTracker {
893public:
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
906public:
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).
956class TransferTracker {
957public:
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
1416class InstrRefBasedLDV : public LDVImpl {
1417private:
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
1689public:
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
1711ValueIDNum 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.
1714InstrRefBasedLDV::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
1725SpillLoc
1726InstrRefBasedLDV::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.
1742bool 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
1793bool 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
1998bool 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
2048void 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
2123void 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
2171bool 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
2184bool 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
2194Optional<SpillLoc>
2195InstrRefBasedLDV::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
2209bool 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
2298bool 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.
2368void 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
2417void 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
2435void 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
2556std::tuple<bool, bool>
2557InstrRefBasedLDV::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
2657void 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
2776bool 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
2817std::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
2909std::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
3178void 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)
3411void 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
3421void 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
3486void 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.
3526bool 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
3690LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
3691 return new InstrRefBasedLDV();
3692}
3693
3694namespace {
3695class LDVSSABlock;
3696class 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.
3701typedef 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.
3706class LDVSSAPhi {
3707public:
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.
3719class LDVSSABlockIterator {
3720public:
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.
3743class LDVSSABlock {
3744public:
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>.
3775class LDVSSAUpdater {
3776public:
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
3820LDVSSABlock *LDVSSABlockIterator::operator*() {
3821 return Updater.getSSALDVBlock(*PredIt);
3822}
3823
3824#ifndef NDEBUG1
3825
3826raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
3827 out << "SSALDVPHI " << PHI.PHIValNum;
3828 return out;
3829}
3830
3831#endif
3832
3833} // namespace
3834
3835namespace 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.
3841template <> class SSAUpdaterTraits<LDVSSAUpdater> {
3842public:
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
3948Optional<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)
1
Assuming 'LowerIt' is not equal to 'UpperIt'
2
Taking false branch
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)
3
Assuming the condition is false
4
Taking false branch
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) {
5
Assuming '__begin1' is equal to '__end1'
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()) {
6
Taking false branch
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()));
7
Calling 'SSAUpdaterImpl::GetValue'
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}

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h

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
25namespace llvm {
26
27template<typename T> class SSAUpdaterTraits;
28
29template<typename UpdaterT>
30class SSAUpdaterImpl {
31private:
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
84public:
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);
8
Calling 'SSAUpdaterImpl::BuildBlockList'
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);
9
Calling 'operator new<llvm::MallocAllocator, 4096UL, 4096UL, 128UL>'
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

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/Allocator.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
37namespace llvm {
38
39namespace 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.
43void 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.
65template <typename AllocatorT = MallocAllocator, size_t SlabSize = 4096,
66 size_t SizeThreshold = SlabSize, size_t GrowthDelay = 128>
67class BumpPtrAllocatorImpl
68 : public AllocatorBase<BumpPtrAllocatorImpl<AllocatorT, SlabSize,
69 SizeThreshold, GrowthDelay>>,
70 private AllocatorT {
71public:
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);
12
Calling 'offsetToAlignedAddr'
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));
11
Calling 'BumpPtrAllocatorImpl::Allocate'
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
296private:
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.
369typedef 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.
376template <typename T> class SpecificBumpPtrAllocator {
377 BumpPtrAllocator Allocator;
378
379public:
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
431template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold,
432 size_t GrowthDelay>
433void *
434operator 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),
10
Calling 'BumpPtrAllocatorImpl::Allocate'
438 alignof(std::max_align_t)));
439}
440
441template <typename AllocatorT, size_t SlabSize, size_t SizeThreshold,
442 size_t GrowthDelay>
443void operator delete(void *,
444 llvm::BumpPtrAllocatorImpl<AllocatorT, SlabSize,
445 SizeThreshold, GrowthDelay> &) {
446}
447
448#endif // LLVM_SUPPORT_ALLOCATOR_H

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/Alignment.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
31namespace 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.
39struct Align {
40private:
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
66public:
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; }
17
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'
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.
103inline 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.
109struct MaybeAlign : public llvm::Optional<Align> {
110private:
111 using UP = llvm::Optional<Align>;
112
113public:
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.
138inline 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.
143inline 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.
148inline uint64_t alignTo(uint64_t Size, Align A) {
149 const uint64_t Value = A.value();
16
Calling 'Align::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
173inline 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.
181inline 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.
186inline 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.
196inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
197 return alignTo(Value, Alignment) - Value;
14
The value 255 is assigned to 'A.ShiftValue'
15
Calling 'alignTo'
198}
199
200/// Returns the necessary adjustment for aligning `Addr` to `Alignment`
201/// bytes, rounding up.
202inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
203 return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
13
Calling 'offsetToAlignment'
204}
205
206/// Returns the log2 of the alignment.
207inline unsigned Log2(Align A) { return A.ShiftValue; }
208
209/// Returns the alignment that satisfies both alignments.
210/// Same semantic as MinAlign.
211inline 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.
215inline 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.
221inline 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.
227inline 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.
232inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
233
234/// Dual operation of the encode function above.
235inline 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.
245inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }
246
247/// Comparisons between Align and scalars. Rhs must be positive.
248inline bool operator==(Align Lhs, uint64_t Rhs) {
249 ALIGN_CHECK_ISPOSITIVE(Rhs);
250 return Lhs.value() == Rhs;
251}
252inline bool operator!=(Align Lhs, uint64_t Rhs) {
253 ALIGN_CHECK_ISPOSITIVE(Rhs);
254 return Lhs.value() != Rhs;
255}
256inline bool operator<=(Align Lhs, uint64_t Rhs) {
257 ALIGN_CHECK_ISPOSITIVE(Rhs);
258 return Lhs.value() <= Rhs;
259}
260inline bool operator>=(Align Lhs, uint64_t Rhs) {
261 ALIGN_CHECK_ISPOSITIVE(Rhs);
262 return Lhs.value() >= Rhs;
263}
264inline bool operator<(Align Lhs, uint64_t Rhs) {
265 ALIGN_CHECK_ISPOSITIVE(Rhs);
266 return Lhs.value() < Rhs;
267}
268inline 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.
274inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) {
275 return Lhs ? (*Lhs).value() == Rhs : Rhs == 0;
276}
277inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) {
278 return Lhs ? (*Lhs).value() != Rhs : Rhs != 0;
279}
280
281/// Comparisons operators between Align.
282inline bool operator==(Align Lhs, Align Rhs) {
283 return Lhs.ShiftValue == Rhs.ShiftValue;
284}
285inline bool operator!=(Align Lhs, Align Rhs) {
286 return Lhs.ShiftValue != Rhs.ShiftValue;
287}
288inline bool operator<=(Align Lhs, Align Rhs) {
289 return Lhs.ShiftValue <= Rhs.ShiftValue;
290}
291inline bool operator>=(Align Lhs, Align Rhs) {
292 return Lhs.ShiftValue >= Rhs.ShiftValue;
293}
294inline bool operator<(Align Lhs, Align Rhs) {
295 return Lhs.ShiftValue < Rhs.ShiftValue;
296}
297inline bool operator>(Align Lhs, Align Rhs) {
298 return Lhs.ShiftValue > Rhs.ShiftValue;
299}
300
301// Don't allow relational comparisons with MaybeAlign.
302bool operator<=(Align Lhs, MaybeAlign Rhs) = delete;
303bool operator>=(Align Lhs, MaybeAlign Rhs) = delete;
304bool operator<(Align Lhs, MaybeAlign Rhs) = delete;
305bool operator>(Align Lhs, MaybeAlign Rhs) = delete;
306
307bool operator<=(MaybeAlign Lhs, Align Rhs) = delete;
308bool operator>=(MaybeAlign Lhs, Align Rhs) = delete;
309bool operator<(MaybeAlign Lhs, Align Rhs) = delete;
310bool operator>(MaybeAlign Lhs, Align Rhs) = delete;
311
312bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
313bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
314bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
315bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
316
317inline 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
322inline 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
327inline 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
334inline 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
340inline Align max(MaybeAlign Lhs, Align Rhs) {
341 return Lhs && *Lhs > Rhs ? *Lhs : Rhs;
342}
343
344inline 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.
350inline std::string DebugStr(const Align &A) {
351 return std::to_string(A.value());
352}
353// For usage in LLVM_DEBUG macros.
354inline 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_