LLVM 20.0.0git
DIExpressionOptimizer.cpp
Go to the documentation of this file.
1//===- DIExpressionOptimizer.cpp - Constant folding of DIExpressions ------===//
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 implements functions to constant fold DIExpressions. Which were
10// declared in DIExpressionOptimizer.h
11//
12//===----------------------------------------------------------------------===//
13
16
17using namespace llvm;
18
19/// Returns true if the Op is a DW_OP_constu.
20static std::optional<uint64_t> isConstantVal(DIExpression::ExprOperand Op) {
21 if (Op.getOp() == dwarf::DW_OP_constu)
22 return Op.getArg(0);
23 return std::nullopt;
24}
25
26/// Returns true if an operation and operand result in a No Op.
28 switch (Op) {
29 case dwarf::DW_OP_plus:
30 case dwarf::DW_OP_minus:
31 case dwarf::DW_OP_shl:
32 case dwarf::DW_OP_shr:
33 return Val == 0;
34 case dwarf::DW_OP_mul:
35 case dwarf::DW_OP_div:
36 return Val == 1;
37 default:
38 return false;
39 }
40}
41
42/// Try to fold \p Const1 and \p Const2 by applying \p Operator and returning
43/// the result, if there is an overflow, return a std::nullopt.
44static std::optional<uint64_t>
47
48 bool ResultOverflowed;
49 switch (Operator) {
50 case dwarf::DW_OP_plus: {
51 auto Result = SaturatingAdd(Const1, Const2, &ResultOverflowed);
52 if (ResultOverflowed)
53 return std::nullopt;
54 return Result;
55 }
56 case dwarf::DW_OP_minus: {
57 if (Const1 < Const2)
58 return std::nullopt;
59 return Const1 - Const2;
60 }
61 case dwarf::DW_OP_shl: {
62 if ((uint64_t)countl_zero(Const1) < Const2)
63 return std::nullopt;
64 return Const1 << Const2;
65 }
66 case dwarf::DW_OP_shr: {
67 if ((uint64_t)countr_zero(Const1) < Const2)
68 return std::nullopt;
69 return Const1 >> Const2;
70 }
71 case dwarf::DW_OP_mul: {
72 auto Result = SaturatingMultiply(Const1, Const2, &ResultOverflowed);
73 if (ResultOverflowed)
74 return std::nullopt;
75 return Result;
76 }
77 case dwarf::DW_OP_div: {
78 if (Const2)
79 return Const1 / Const2;
80 return std::nullopt;
81 }
82 default:
83 return std::nullopt;
84 }
85}
86
87/// Returns true if the two operations \p Operator1 and \p Operator2 are
88/// commutative and can be folded.
90 dwarf::LocationAtom Operator2) {
91 return Operator1 == Operator2 &&
92 (Operator1 == dwarf::DW_OP_plus || Operator1 == dwarf::DW_OP_mul);
93}
94
95/// Consume one operator and its operand(s).
98 Cursor.consume(1);
99 Loc = Loc + Op.getSize();
100}
101
102/// Reset the Cursor to the beginning of the WorkingOps.
104 ArrayRef<uint64_t> WorkingOps) {
105 Cursor.assignNewExpr(WorkingOps);
106 Loc = 0;
107}
108
109/// This function will canonicalize:
110/// 1. DW_OP_plus_uconst to DW_OP_constu <const-val> DW_OP_plus
111/// 2. DW_OP_lit<n> to DW_OP_constu <n>
114 DIExpressionCursor Cursor(WorkingOps);
115 uint64_t Loc = 0;
116 SmallVector<uint64_t> ResultOps;
117 while (Loc < WorkingOps.size()) {
118 auto Op = Cursor.peek();
119 /// Expression has no operations, break.
120 if (!Op)
121 break;
122 auto OpRaw = Op->getOp();
123
124 if (OpRaw >= dwarf::DW_OP_lit0 && OpRaw <= dwarf::DW_OP_lit31) {
125 ResultOps.push_back(dwarf::DW_OP_constu);
126 ResultOps.push_back(OpRaw - dwarf::DW_OP_lit0);
127 consumeOneOperator(Cursor, Loc, *Cursor.peek());
128 continue;
129 }
130 if (OpRaw == dwarf::DW_OP_plus_uconst) {
131 ResultOps.push_back(dwarf::DW_OP_constu);
132 ResultOps.push_back(Op->getArg(0));
133 ResultOps.push_back(dwarf::DW_OP_plus);
134 consumeOneOperator(Cursor, Loc, *Cursor.peek());
135 continue;
136 }
137 uint64_t PrevLoc = Loc;
138 consumeOneOperator(Cursor, Loc, *Cursor.peek());
139 ResultOps.append(WorkingOps.begin() + PrevLoc, WorkingOps.begin() + Loc);
140 }
141 return ResultOps;
142}
143
144/// This function will convert:
145/// 1. DW_OP_constu <const-val> DW_OP_plus to DW_OP_plus_uconst
146/// 2. DW_OP_constu, 0 to DW_OP_lit0
149 DIExpressionCursor Cursor(WorkingOps);
150 uint64_t Loc = 0;
151 SmallVector<uint64_t> ResultOps;
152 while (Loc < WorkingOps.size()) {
153 auto Op1 = Cursor.peek();
154 /// Expression has no operations, exit.
155 if (!Op1)
156 break;
157 auto Op1Raw = Op1->getOp();
158
159 if (Op1Raw == dwarf::DW_OP_constu && Op1->getArg(0) == 0) {
160 ResultOps.push_back(dwarf::DW_OP_lit0);
161 consumeOneOperator(Cursor, Loc, *Cursor.peek());
162 continue;
163 }
164
165 auto Op2 = Cursor.peekNext();
166 /// Expression has no more operations, copy into ResultOps and exit.
167 if (!Op2) {
168 uint64_t PrevLoc = Loc;
169 consumeOneOperator(Cursor, Loc, *Cursor.peek());
170 ResultOps.append(WorkingOps.begin() + PrevLoc, WorkingOps.begin() + Loc);
171 break;
172 }
173 auto Op2Raw = Op2->getOp();
174
175 if (Op1Raw == dwarf::DW_OP_constu && Op2Raw == dwarf::DW_OP_plus) {
176 ResultOps.push_back(dwarf::DW_OP_plus_uconst);
177 ResultOps.push_back(Op1->getArg(0));
178 consumeOneOperator(Cursor, Loc, *Cursor.peek());
179 consumeOneOperator(Cursor, Loc, *Cursor.peek());
180 continue;
181 }
182 uint64_t PrevLoc = Loc;
183 consumeOneOperator(Cursor, Loc, *Cursor.peek());
184 ResultOps.append(WorkingOps.begin() + PrevLoc, WorkingOps.begin() + Loc);
185 }
186 return ResultOps;
187}
188
189/// {DW_OP_constu, 0, DW_OP_[plus, minus, shl, shr]} -> {}
190/// {DW_OP_constu, 1, DW_OP_[mul, div]} -> {}
191static bool tryFoldNoOpMath(uint64_t Const1,
193 uint64_t &Loc, DIExpressionCursor &Cursor,
194 SmallVectorImpl<uint64_t> &WorkingOps) {
195
196 if (isNeutralElement(Ops[1].getOp(), Const1)) {
197 WorkingOps.erase(WorkingOps.begin() + Loc, WorkingOps.begin() + Loc + 3);
198 startFromBeginning(Loc, Cursor, WorkingOps);
199 return true;
200 }
201 return false;
202}
203
204/// {DW_OP_constu, Const1, DW_OP_constu, Const2, DW_OP_[plus,
205/// minus, mul, div, shl, shr] -> {DW_OP_constu, Const1 [+, -, *, /, <<, >>]
206/// Const2}
207static bool tryFoldConstants(uint64_t Const1,
209 uint64_t &Loc, DIExpressionCursor &Cursor,
210 SmallVectorImpl<uint64_t> &WorkingOps) {
211
212 auto Const2 = isConstantVal(Ops[1]);
213 if (!Const2)
214 return false;
215
216 auto Result = foldOperationIfPossible(
217 Const1, *Const2, static_cast<dwarf::LocationAtom>(Ops[2].getOp()));
218 if (!Result) {
219 consumeOneOperator(Cursor, Loc, Ops[0]);
220 return true;
221 }
222 WorkingOps.erase(WorkingOps.begin() + Loc + 2, WorkingOps.begin() + Loc + 5);
223 WorkingOps[Loc] = dwarf::DW_OP_constu;
224 WorkingOps[Loc + 1] = *Result;
225 startFromBeginning(Loc, Cursor, WorkingOps);
226 return true;
227}
228
229/// {DW_OP_constu, Const1, DW_OP_[plus, mul], DW_OP_constu, Const2,
230/// DW_OP_[plus, mul]} -> {DW_OP_constu, Const1 [+, *] Const2, DW_OP_[plus,
231/// mul]}
234 uint64_t &Loc, DIExpressionCursor &Cursor,
235 SmallVectorImpl<uint64_t> &WorkingOps) {
236
237 auto Const2 = isConstantVal(Ops[2]);
238 auto Operand1 = static_cast<dwarf::LocationAtom>(Ops[1].getOp());
239 auto Operand2 = static_cast<dwarf::LocationAtom>(Ops[3].getOp());
240
241 if (!Const2 || !operationsAreFoldableAndCommutative(Operand1, Operand2))
242 return false;
243
244 auto Result = foldOperationIfPossible(Const1, *Const2, Operand1);
245 if (!Result) {
246 consumeOneOperator(Cursor, Loc, Ops[0]);
247 return true;
248 }
249 WorkingOps.erase(WorkingOps.begin() + Loc + 3, WorkingOps.begin() + Loc + 6);
250 WorkingOps[Loc] = dwarf::DW_OP_constu;
251 WorkingOps[Loc + 1] = *Result;
252 startFromBeginning(Loc, Cursor, WorkingOps);
253 return true;
254}
255
256/// {DW_OP_constu, Const1, DW_OP_[plus, mul], DW_OP_LLVM_arg, Arg1,
257/// DW_OP_[plus, mul], DW_OP_constu, Const2, DW_OP_[plus, mul]} ->
258/// {DW_OP_constu, Const1 [+, *] Const2, DW_OP_[plus, mul], DW_OP_LLVM_arg,
259/// Arg1, DW_OP_[plus, mul]}
262 DIExpressionCursor &Cursor, SmallVectorImpl<uint64_t> &WorkingOps) {
263
264 auto Const2 = isConstantVal(Ops[4]);
265 auto Operand1 = static_cast<dwarf::LocationAtom>(Ops[1].getOp());
266 auto Operand2 = static_cast<dwarf::LocationAtom>(Ops[3].getOp());
267 auto Operand3 = static_cast<dwarf::LocationAtom>(Ops[5].getOp());
268
269 if (!Const2 || Ops[2].getOp() != dwarf::DW_OP_LLVM_arg ||
270 !operationsAreFoldableAndCommutative(Operand1, Operand2) ||
271 !operationsAreFoldableAndCommutative(Operand2, Operand3))
272 return false;
273
274 auto Result = foldOperationIfPossible(Const1, *Const2, Operand1);
275 if (!Result) {
276 consumeOneOperator(Cursor, Loc, Ops[0]);
277 return true;
278 }
279 WorkingOps.erase(WorkingOps.begin() + Loc + 6, WorkingOps.begin() + Loc + 9);
280 WorkingOps[Loc] = dwarf::DW_OP_constu;
281 WorkingOps[Loc + 1] = *Result;
282 startFromBeginning(Loc, Cursor, WorkingOps);
283 return true;
284}
285
287
288 SmallVector<uint64_t, 8> WorkingOps(Elements.begin(), Elements.end());
289 uint64_t Loc = 0;
291 DIExpressionCursor Cursor(ResultOps);
293
294 // Iterate over all Operations in a DIExpression to match the smallest pattern
295 // that can be folded.
296 while (Loc < ResultOps.size()) {
297 Ops.clear();
298
299 auto Op = Cursor.peek();
300 // Expression has no operations, exit.
301 if (!Op)
302 break;
303
304 auto Const1 = isConstantVal(*Op);
305
306 if (!Const1) {
307 // Early exit, all of the following patterns start with a constant value.
308 consumeOneOperator(Cursor, Loc, *Op);
309 continue;
310 }
311
312 Ops.push_back(*Op);
313
314 Op = Cursor.peekNext();
315 // All following patterns require at least 2 Operations, exit.
316 if (!Op)
317 break;
318
319 Ops.push_back(*Op);
320
321 // Try to fold a constant no-op, such as {+ 0}
322 if (tryFoldNoOpMath(*Const1, Ops, Loc, Cursor, ResultOps))
323 continue;
324
325 Op = Cursor.peekNextN(2);
326 // Op[1] could still match a pattern, skip iteration.
327 if (!Op) {
328 consumeOneOperator(Cursor, Loc, Ops[0]);
329 continue;
330 }
331
332 Ops.push_back(*Op);
333
334 // Try to fold a pattern of two constants such as {C1 + C2}.
335 if (tryFoldConstants(*Const1, Ops, Loc, Cursor, ResultOps))
336 continue;
337
338 Op = Cursor.peekNextN(3);
339 // Op[1] and Op[2] could still match a pattern, skip iteration.
340 if (!Op) {
341 consumeOneOperator(Cursor, Loc, Ops[0]);
342 continue;
343 }
344
345 Ops.push_back(*Op);
346
347 // Try to fold commutative constant math, such as {C1 + C2 +}.
348 if (tryFoldCommutativeMath(*Const1, Ops, Loc, Cursor, ResultOps))
349 continue;
350
351 Op = Cursor.peekNextN(4);
352 if (!Op) {
353 consumeOneOperator(Cursor, Loc, Ops[0]);
354 continue;
355 }
356
357 Ops.push_back(*Op);
358 Op = Cursor.peekNextN(5);
359 if (!Op) {
360 consumeOneOperator(Cursor, Loc, Ops[0]);
361 continue;
362 }
363
364 Ops.push_back(*Op);
365
366 // Try to fold commutative constant math with an LLVM_Arg in between, such
367 // as {C1 + Arg + C2 +}.
368 if (tryFoldCommutativeMathWithArgInBetween(*Const1, Ops, Loc, Cursor,
369 ResultOps))
370 continue;
371
372 consumeOneOperator(Cursor, Loc, Ops[0]);
373 }
374 ResultOps = optimizeDwarfOperations(ResultOps);
375 auto *Result = DIExpression::get(getContext(), ResultOps);
376 assert(Result->isValid() && "concatenated expression is not valid");
377 return Result;
378}
static bool tryFoldNoOpMath(uint64_t Const1, ArrayRef< DIExpression::ExprOperand > Ops, uint64_t &Loc, DIExpressionCursor &Cursor, SmallVectorImpl< uint64_t > &WorkingOps)
{DW_OP_constu, 0, DW_OP_[plus, minus, shl, shr]} -> {} {DW_OP_constu, 1, DW_OP_[mul,...
static bool operationsAreFoldableAndCommutative(dwarf::LocationAtom Operator1, dwarf::LocationAtom Operator2)
Returns true if the two operations Operator1 and Operator2 are commutative and can be folded.
static bool isNeutralElement(uint64_t Op, uint64_t Val)
Returns true if an operation and operand result in a No Op.
static std::optional< uint64_t > foldOperationIfPossible(uint64_t Const1, uint64_t Const2, dwarf::LocationAtom Operator)
Try to fold Const1 and Const2 by applying Operator and returning the result, if there is an overflow,...
static bool tryFoldCommutativeMath(uint64_t Const1, ArrayRef< DIExpression::ExprOperand > Ops, uint64_t &Loc, DIExpressionCursor &Cursor, SmallVectorImpl< uint64_t > &WorkingOps)
{DW_OP_constu, Const1, DW_OP_[plus, mul], DW_OP_constu, Const2, DW_OP_[plus, mul]} -> {DW_OP_constu,...
void startFromBeginning(uint64_t &Loc, DIExpressionCursor &Cursor, ArrayRef< uint64_t > WorkingOps)
Reset the Cursor to the beginning of the WorkingOps.
static SmallVector< uint64_t > optimizeDwarfOperations(ArrayRef< uint64_t > WorkingOps)
This function will convert:
static bool tryFoldCommutativeMathWithArgInBetween(uint64_t Const1, ArrayRef< DIExpression::ExprOperand > Ops, uint64_t &Loc, DIExpressionCursor &Cursor, SmallVectorImpl< uint64_t > &WorkingOps)
{DW_OP_constu, Const1, DW_OP_[plus, mul], DW_OP_LLVM_arg, Arg1, DW_OP_[plus, mul],...
static bool tryFoldConstants(uint64_t Const1, ArrayRef< DIExpression::ExprOperand > Ops, uint64_t &Loc, DIExpressionCursor &Cursor, SmallVectorImpl< uint64_t > &WorkingOps)
{DW_OP_constu, Const1, DW_OP_constu, Const2, DW_OP_[plus, minus, mul, div, shl, shr] -> {DW_OP_constu...
static void consumeOneOperator(DIExpressionCursor &Cursor, uint64_t &Loc, const DIExpression::ExprOperand &Op)
Consume one operator and its operand(s).
static std::optional< uint64_t > isConstantVal(DIExpression::ExprOperand Op)
Returns true if the Op is a DW_OP_constu.
static SmallVector< uint64_t > canonicalizeDwarfOperations(ArrayRef< uint64_t > WorkingOps)
This function will canonicalize:
This file contains constants used for implementing Dwarf debug support.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
iterator begin() const
Definition: ArrayRef.h:153
Holds a DIExpression and keeps track of how many operands have been consumed so far.
std::optional< DIExpression::ExprOperand > peekNext() const
Return the next operation.
std::optional< DIExpression::ExprOperand > peekNextN(unsigned N) const
std::optional< DIExpression::ExprOperand > peek() const
Return the current operation.
void consume(unsigned N)
Consume N operations.
void assignNewExpr(ArrayRef< uint64_t > Expr)
A lightweight wrapper around an expression operand.
DWARF expression.
DIExpression * foldConstantMath()
Try to shorten an expression with constant math operations that can be evaluated at compile time.
This class represents an Operation in the Expression.
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1542
LLVMContext & getContext() const
Definition: Metadata.h:1233
This is a utility class that provides an abstraction for the common functionality between Instruction...
Definition: Operator.h:32
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
iterator erase(const_iterator CI)
Definition: SmallVector.h:750
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
LocationAtom
Definition: Dwarf.h:136
@ DW_OP_LLVM_arg
Only used in LLVM metadata.
Definition: Dwarf.h:147
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition: bit.h:215
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Definition: bit.h:281
std::enable_if_t< std::is_unsigned_v< T >, T > SaturatingMultiply(T X, T Y, bool *ResultOverflowed=nullptr)
Multiply two unsigned integers, X and Y, of type T.
Definition: MathExtras.h:638
std::enable_if_t< std::is_unsigned_v< T >, T > SaturatingAdd(T X, T Y, bool *ResultOverflowed=nullptr)
Add two unsigned integers, X and Y, of type T.
Definition: MathExtras.h:609