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
14#include "llvm/BinaryFormat/Dwarf.h"
15#include "llvm/IR/DebugInfoMetadata.h"
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(I: 0);
23 return std::nullopt;
24}
25
26/// Returns true if an operation and operand result in a No Op.
27static bool isNeutralElement(uint64_t Op, uint64_t Val) {
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>
45foldOperationIfPossible(uint64_t Const1, uint64_t Const2,
46 dwarf::LocationAtom Operator) {
47
48 bool ResultOverflowed;
49 switch (Operator) {
50 case dwarf::DW_OP_plus: {
51 auto Result = SaturatingAdd(X: Const1, Y: Const2, ResultOverflowed: &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(Val: Const1) < Const2)
63 return std::nullopt;
64 return Const1 << Const2;
65 }
66 case dwarf::DW_OP_shr: {
67 if ((uint64_t)countr_zero(Val: Const1) < Const2)
68 return std::nullopt;
69 return Const1 >> Const2;
70 }
71 case dwarf::DW_OP_mul: {
72 auto Result = SaturatingMultiply(X: Const1, Y: Const2, ResultOverflowed: &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.
89static bool operationsAreFoldableAndCommutative(dwarf::LocationAtom Operator1,
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).
96static void consumeOneOperator(DIExpressionCursor &Cursor, uint64_t &Loc,
97 const DIExpression::ExprOperand &Op) {
98 Cursor.consume(N: 1);
99 Loc = Loc + Op.getSize();
100}
101
102/// Reset the Cursor to the beginning of the WorkingOps.
103void startFromBeginning(uint64_t &Loc, DIExpressionCursor &Cursor,
104 ArrayRef<uint64_t> WorkingOps) {
105 Cursor.assignNewExpr(Expr: 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>
112static SmallVector<uint64_t>
113canonicalizeDwarfOperations(ArrayRef<uint64_t> WorkingOps) {
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(Elt: dwarf::DW_OP_constu);
126 ResultOps.push_back(Elt: OpRaw - dwarf::DW_OP_lit0);
127 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
128 continue;
129 }
130 if (OpRaw == dwarf::DW_OP_plus_uconst) {
131 ResultOps.push_back(Elt: dwarf::DW_OP_constu);
132 ResultOps.push_back(Elt: Op->getArg(I: 0));
133 ResultOps.push_back(Elt: dwarf::DW_OP_plus);
134 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
135 continue;
136 }
137 uint64_t PrevLoc = Loc;
138 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
139 ResultOps.append(in_start: WorkingOps.begin() + PrevLoc, in_end: 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
147static SmallVector<uint64_t>
148optimizeDwarfOperations(ArrayRef<uint64_t> WorkingOps) {
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(I: 0) == 0) {
160 ResultOps.push_back(Elt: dwarf::DW_OP_lit0);
161 consumeOneOperator(Cursor, Loc, Op: *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, Op: *Cursor.peek());
170 ResultOps.append(in_start: WorkingOps.begin() + PrevLoc, in_end: 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(Elt: dwarf::DW_OP_plus_uconst);
177 ResultOps.push_back(Elt: Op1->getArg(I: 0));
178 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
179 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
180 continue;
181 }
182 uint64_t PrevLoc = Loc;
183 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
184 ResultOps.append(in_start: WorkingOps.begin() + PrevLoc, in_end: 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,
192 ArrayRef<DIExpression::ExprOperand> Ops,
193 uint64_t &Loc, DIExpressionCursor &Cursor,
194 SmallVectorImpl<uint64_t> &WorkingOps) {
195
196 if (isNeutralElement(Op: Ops[1].getOp(), Val: Const1)) {
197 WorkingOps.erase(CS: WorkingOps.begin() + Loc, CE: 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,
208 ArrayRef<DIExpression::ExprOperand> Ops,
209 uint64_t &Loc, DIExpressionCursor &Cursor,
210 SmallVectorImpl<uint64_t> &WorkingOps) {
211
212 auto Const2 = isConstantVal(Op: Ops[1]);
213 if (!Const2)
214 return false;
215
216 auto Result = foldOperationIfPossible(
217 Const1, Const2: *Const2, Operator: static_cast<dwarf::LocationAtom>(Ops[2].getOp()));
218 if (!Result) {
219 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
220 return true;
221 }
222 WorkingOps.erase(CS: WorkingOps.begin() + Loc + 2, CE: 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]}
232static bool tryFoldCommutativeMath(uint64_t Const1,
233 ArrayRef<DIExpression::ExprOperand> Ops,
234 uint64_t &Loc, DIExpressionCursor &Cursor,
235 SmallVectorImpl<uint64_t> &WorkingOps) {
236
237 auto Const2 = isConstantVal(Op: 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(Operator1: Operand1, Operator2: Operand2))
242 return false;
243
244 auto Result = foldOperationIfPossible(Const1, Const2: *Const2, Operator: Operand1);
245 if (!Result) {
246 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
247 return true;
248 }
249 WorkingOps.erase(CS: WorkingOps.begin() + Loc + 3, CE: 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]}
260static bool tryFoldCommutativeMathWithArgInBetween(
261 uint64_t Const1, ArrayRef<DIExpression::ExprOperand> Ops, uint64_t &Loc,
262 DIExpressionCursor &Cursor, SmallVectorImpl<uint64_t> &WorkingOps) {
263
264 auto Const2 = isConstantVal(Op: 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(Operator1: Operand1, Operator2: Operand2) ||
271 !operationsAreFoldableAndCommutative(Operator1: Operand2, Operator2: Operand3))
272 return false;
273
274 auto Result = foldOperationIfPossible(Const1, Const2: *Const2, Operator: Operand1);
275 if (!Result) {
276 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
277 return true;
278 }
279 WorkingOps.erase(CS: WorkingOps.begin() + Loc + 6, CE: 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
286DIExpression *DIExpression::foldConstantMath() {
287
288 SmallVector<uint64_t, 8> WorkingOps(Elements.begin(), Elements.end());
289 uint64_t Loc = 0;
290 SmallVector<uint64_t> ResultOps = canonicalizeDwarfOperations(WorkingOps);
291 DIExpressionCursor Cursor(ResultOps);
292 SmallVector<DIExpression::ExprOperand, 8> Ops;
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: *Op);
305
306 if (!Const1) {
307 // Early exit, all of the following patterns start with a constant value.
308 consumeOneOperator(Cursor, Loc, Op: *Op);
309 continue;
310 }
311
312 Ops.push_back(Elt: *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(Elt: *Op);
320
321 // Try to fold a constant no-op, such as {+ 0}
322 if (tryFoldNoOpMath(Const1: *Const1, Ops, Loc, Cursor, WorkingOps&: ResultOps))
323 continue;
324
325 Op = Cursor.peekNextN(N: 2);
326 // Op[1] could still match a pattern, skip iteration.
327 if (!Op) {
328 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
329 continue;
330 }
331
332 Ops.push_back(Elt: *Op);
333
334 // Try to fold a pattern of two constants such as {C1 + C2}.
335 if (tryFoldConstants(Const1: *Const1, Ops, Loc, Cursor, WorkingOps&: ResultOps))
336 continue;
337
338 Op = Cursor.peekNextN(N: 3);
339 // Op[1] and Op[2] could still match a pattern, skip iteration.
340 if (!Op) {
341 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
342 continue;
343 }
344
345 Ops.push_back(Elt: *Op);
346
347 // Try to fold commutative constant math, such as {C1 + C2 +}.
348 if (tryFoldCommutativeMath(Const1: *Const1, Ops, Loc, Cursor, WorkingOps&: ResultOps))
349 continue;
350
351 Op = Cursor.peekNextN(N: 4);
352 if (!Op) {
353 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
354 continue;
355 }
356
357 Ops.push_back(Elt: *Op);
358 Op = Cursor.peekNextN(N: 5);
359 if (!Op) {
360 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
361 continue;
362 }
363
364 Ops.push_back(Elt: *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: *Const1, Ops, Loc, Cursor,
369 WorkingOps&: ResultOps))
370 continue;
371
372 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
373 }
374 ResultOps = optimizeDwarfOperations(WorkingOps: ResultOps);
375 auto *Result = DIExpression::get(Context&: getContext(), Elements: ResultOps);
376 assert(Result->isValid() && "concatenated expression is not valid");
377 return Result;
378}
379