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 (Const2 >= std::numeric_limits<uint64_t>::digits ||
63 static_cast<uint64_t>(countl_zero(Val: Const1)) < Const2)
64 return std::nullopt;
65 return Const1 << Const2;
66 }
67 case dwarf::DW_OP_shr: {
68 if (Const2 >= std::numeric_limits<uint64_t>::digits ||
69 static_cast<uint64_t>(countr_zero(Val: Const1)) < Const2)
70 return std::nullopt;
71 return Const1 >> Const2;
72 }
73 case dwarf::DW_OP_mul: {
74 auto Result = SaturatingMultiply(X: Const1, Y: Const2, ResultOverflowed: &ResultOverflowed);
75 if (ResultOverflowed)
76 return std::nullopt;
77 return Result;
78 }
79 case dwarf::DW_OP_div: {
80 if (Const2)
81 return Const1 / Const2;
82 return std::nullopt;
83 }
84 default:
85 return std::nullopt;
86 }
87}
88
89/// Returns true if the two operations \p Operator1 and \p Operator2 are
90/// commutative and can be folded.
91static bool operationsAreFoldableAndCommutative(dwarf::LocationAtom Operator1,
92 dwarf::LocationAtom Operator2) {
93 return Operator1 == Operator2 &&
94 (Operator1 == dwarf::DW_OP_plus || Operator1 == dwarf::DW_OP_mul);
95}
96
97/// Consume one operator and its operand(s).
98static void consumeOneOperator(DIExpressionCursor &Cursor, uint64_t &Loc,
99 const DIExpression::ExprOperand &Op) {
100 Cursor.consume(N: 1);
101 Loc = Loc + Op.getSize();
102}
103
104/// Reset the Cursor to the beginning of the WorkingOps.
105void startFromBeginning(uint64_t &Loc, DIExpressionCursor &Cursor,
106 ArrayRef<uint64_t> WorkingOps) {
107 Cursor.assignNewExpr(Expr: WorkingOps);
108 Loc = 0;
109}
110
111/// This function will canonicalize:
112/// 1. DW_OP_plus_uconst to DW_OP_constu <const-val> DW_OP_plus
113/// 2. DW_OP_lit<n> to DW_OP_constu <n>
114static SmallVector<uint64_t>
115canonicalizeDwarfOperations(ArrayRef<uint64_t> WorkingOps) {
116 DIExpressionCursor Cursor(WorkingOps);
117 uint64_t Loc = 0;
118 SmallVector<uint64_t> ResultOps;
119 while (Loc < WorkingOps.size()) {
120 auto Op = Cursor.peek();
121 /// Expression has no operations, break.
122 if (!Op)
123 break;
124 auto OpRaw = Op->getOp();
125
126 if (OpRaw >= dwarf::DW_OP_lit0 && OpRaw <= dwarf::DW_OP_lit31) {
127 ResultOps.push_back(Elt: dwarf::DW_OP_constu);
128 ResultOps.push_back(Elt: OpRaw - dwarf::DW_OP_lit0);
129 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
130 continue;
131 }
132 if (OpRaw == dwarf::DW_OP_plus_uconst) {
133 ResultOps.push_back(Elt: dwarf::DW_OP_constu);
134 ResultOps.push_back(Elt: Op->getArg(I: 0));
135 ResultOps.push_back(Elt: dwarf::DW_OP_plus);
136 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
137 continue;
138 }
139 uint64_t PrevLoc = Loc;
140 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
141 ResultOps.append(in_start: WorkingOps.begin() + PrevLoc, in_end: WorkingOps.begin() + Loc);
142 }
143 return ResultOps;
144}
145
146/// This function will convert:
147/// 1. DW_OP_constu <const-val> DW_OP_plus to DW_OP_plus_uconst
148/// 2. DW_OP_constu, 0 to DW_OP_lit0
149static SmallVector<uint64_t>
150optimizeDwarfOperations(ArrayRef<uint64_t> WorkingOps) {
151 DIExpressionCursor Cursor(WorkingOps);
152 uint64_t Loc = 0;
153 SmallVector<uint64_t> ResultOps;
154 while (Loc < WorkingOps.size()) {
155 auto Op1 = Cursor.peek();
156 /// Expression has no operations, exit.
157 if (!Op1)
158 break;
159 auto Op1Raw = Op1->getOp();
160
161 if (Op1Raw == dwarf::DW_OP_constu && Op1->getArg(I: 0) == 0) {
162 ResultOps.push_back(Elt: dwarf::DW_OP_lit0);
163 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
164 continue;
165 }
166
167 auto Op2 = Cursor.peekNext();
168 /// Expression has no more operations, copy into ResultOps and exit.
169 if (!Op2) {
170 uint64_t PrevLoc = Loc;
171 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
172 ResultOps.append(in_start: WorkingOps.begin() + PrevLoc, in_end: WorkingOps.begin() + Loc);
173 break;
174 }
175 auto Op2Raw = Op2->getOp();
176
177 if (Op1Raw == dwarf::DW_OP_constu && Op2Raw == dwarf::DW_OP_plus) {
178 ResultOps.push_back(Elt: dwarf::DW_OP_plus_uconst);
179 ResultOps.push_back(Elt: Op1->getArg(I: 0));
180 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
181 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
182 continue;
183 }
184 uint64_t PrevLoc = Loc;
185 consumeOneOperator(Cursor, Loc, Op: *Cursor.peek());
186 ResultOps.append(in_start: WorkingOps.begin() + PrevLoc, in_end: WorkingOps.begin() + Loc);
187 }
188 return ResultOps;
189}
190
191/// {DW_OP_constu, 0, DW_OP_[plus, minus, shl, shr]} -> {}
192/// {DW_OP_constu, 1, DW_OP_[mul, div]} -> {}
193static bool tryFoldNoOpMath(uint64_t Const1,
194 ArrayRef<DIExpression::ExprOperand> Ops,
195 uint64_t &Loc, DIExpressionCursor &Cursor,
196 SmallVectorImpl<uint64_t> &WorkingOps) {
197
198 if (isNeutralElement(Op: Ops[1].getOp(), Val: Const1)) {
199 WorkingOps.erase(CS: WorkingOps.begin() + Loc, CE: WorkingOps.begin() + Loc + 3);
200 startFromBeginning(Loc, Cursor, WorkingOps);
201 return true;
202 }
203 return false;
204}
205
206/// {DW_OP_constu, Const1, DW_OP_constu, Const2, DW_OP_[plus,
207/// minus, mul, div, shl, shr] -> {DW_OP_constu, Const1 [+, -, *, /, <<, >>]
208/// Const2}
209static bool tryFoldConstants(uint64_t Const1,
210 ArrayRef<DIExpression::ExprOperand> Ops,
211 uint64_t &Loc, DIExpressionCursor &Cursor,
212 SmallVectorImpl<uint64_t> &WorkingOps) {
213
214 auto Const2 = isConstantVal(Op: Ops[1]);
215 if (!Const2)
216 return false;
217
218 auto Result = foldOperationIfPossible(
219 Const1, Const2: *Const2, Operator: static_cast<dwarf::LocationAtom>(Ops[2].getOp()));
220 if (!Result) {
221 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
222 return true;
223 }
224 WorkingOps.erase(CS: WorkingOps.begin() + Loc + 2, CE: WorkingOps.begin() + Loc + 5);
225 WorkingOps[Loc] = dwarf::DW_OP_constu;
226 WorkingOps[Loc + 1] = *Result;
227 startFromBeginning(Loc, Cursor, WorkingOps);
228 return true;
229}
230
231/// {DW_OP_constu, Const1, DW_OP_[plus, mul], DW_OP_constu, Const2,
232/// DW_OP_[plus, mul]} -> {DW_OP_constu, Const1 [+, *] Const2, DW_OP_[plus,
233/// mul]}
234static bool tryFoldCommutativeMath(uint64_t Const1,
235 ArrayRef<DIExpression::ExprOperand> Ops,
236 uint64_t &Loc, DIExpressionCursor &Cursor,
237 SmallVectorImpl<uint64_t> &WorkingOps) {
238
239 auto Const2 = isConstantVal(Op: Ops[2]);
240 auto Operand1 = static_cast<dwarf::LocationAtom>(Ops[1].getOp());
241 auto Operand2 = static_cast<dwarf::LocationAtom>(Ops[3].getOp());
242
243 if (!Const2 || !operationsAreFoldableAndCommutative(Operator1: Operand1, Operator2: Operand2))
244 return false;
245
246 auto Result = foldOperationIfPossible(Const1, Const2: *Const2, Operator: Operand1);
247 if (!Result) {
248 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
249 return true;
250 }
251 WorkingOps.erase(CS: WorkingOps.begin() + Loc + 3, CE: WorkingOps.begin() + Loc + 6);
252 WorkingOps[Loc] = dwarf::DW_OP_constu;
253 WorkingOps[Loc + 1] = *Result;
254 startFromBeginning(Loc, Cursor, WorkingOps);
255 return true;
256}
257
258/// {DW_OP_constu, Const1, DW_OP_[plus, mul], DW_OP_LLVM_arg, Arg1,
259/// DW_OP_[plus, mul], DW_OP_constu, Const2, DW_OP_[plus, mul]} ->
260/// {DW_OP_constu, Const1 [+, *] Const2, DW_OP_[plus, mul], DW_OP_LLVM_arg,
261/// Arg1, DW_OP_[plus, mul]}
262static bool tryFoldCommutativeMathWithArgInBetween(
263 uint64_t Const1, ArrayRef<DIExpression::ExprOperand> Ops, uint64_t &Loc,
264 DIExpressionCursor &Cursor, SmallVectorImpl<uint64_t> &WorkingOps) {
265
266 auto Const2 = isConstantVal(Op: Ops[4]);
267 auto Operand1 = static_cast<dwarf::LocationAtom>(Ops[1].getOp());
268 auto Operand2 = static_cast<dwarf::LocationAtom>(Ops[3].getOp());
269 auto Operand3 = static_cast<dwarf::LocationAtom>(Ops[5].getOp());
270
271 if (!Const2 || Ops[2].getOp() != dwarf::DW_OP_LLVM_arg ||
272 !operationsAreFoldableAndCommutative(Operator1: Operand1, Operator2: Operand2) ||
273 !operationsAreFoldableAndCommutative(Operator1: Operand2, Operator2: Operand3))
274 return false;
275
276 auto Result = foldOperationIfPossible(Const1, Const2: *Const2, Operator: Operand1);
277 if (!Result) {
278 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
279 return true;
280 }
281 WorkingOps.erase(CS: WorkingOps.begin() + Loc + 6, CE: WorkingOps.begin() + Loc + 9);
282 WorkingOps[Loc] = dwarf::DW_OP_constu;
283 WorkingOps[Loc + 1] = *Result;
284 startFromBeginning(Loc, Cursor, WorkingOps);
285 return true;
286}
287
288DIExpression *DIExpression::foldConstantMath() {
289
290 SmallVector<uint64_t, 8> WorkingOps(Elements.begin(), Elements.end());
291 uint64_t Loc = 0;
292 SmallVector<uint64_t> ResultOps = canonicalizeDwarfOperations(WorkingOps);
293 DIExpressionCursor Cursor(ResultOps);
294 SmallVector<DIExpression::ExprOperand, 8> Ops;
295
296 // Iterate over all Operations in a DIExpression to match the smallest pattern
297 // that can be folded.
298 while (Loc < ResultOps.size()) {
299 Ops.clear();
300
301 auto Op = Cursor.peek();
302 // Expression has no operations, exit.
303 if (!Op)
304 break;
305
306 auto Const1 = isConstantVal(Op: *Op);
307
308 if (!Const1) {
309 // Early exit, all of the following patterns start with a constant value.
310 consumeOneOperator(Cursor, Loc, Op: *Op);
311 continue;
312 }
313
314 Ops.push_back(Elt: *Op);
315
316 Op = Cursor.peekNext();
317 // All following patterns require at least 2 Operations, exit.
318 if (!Op)
319 break;
320
321 Ops.push_back(Elt: *Op);
322
323 // Try to fold a constant no-op, such as {+ 0}
324 if (tryFoldNoOpMath(Const1: *Const1, Ops, Loc, Cursor, WorkingOps&: ResultOps))
325 continue;
326
327 Op = Cursor.peekNextN(N: 2);
328 // Op[1] could still match a pattern, skip iteration.
329 if (!Op) {
330 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
331 continue;
332 }
333
334 Ops.push_back(Elt: *Op);
335
336 // Try to fold a pattern of two constants such as {C1 + C2}.
337 if (tryFoldConstants(Const1: *Const1, Ops, Loc, Cursor, WorkingOps&: ResultOps))
338 continue;
339
340 Op = Cursor.peekNextN(N: 3);
341 // Op[1] and Op[2] could still match a pattern, skip iteration.
342 if (!Op) {
343 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
344 continue;
345 }
346
347 Ops.push_back(Elt: *Op);
348
349 // Try to fold commutative constant math, such as {C1 + C2 +}.
350 if (tryFoldCommutativeMath(Const1: *Const1, Ops, Loc, Cursor, WorkingOps&: ResultOps))
351 continue;
352
353 Op = Cursor.peekNextN(N: 4);
354 if (!Op) {
355 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
356 continue;
357 }
358
359 Ops.push_back(Elt: *Op);
360 Op = Cursor.peekNextN(N: 5);
361 if (!Op) {
362 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
363 continue;
364 }
365
366 Ops.push_back(Elt: *Op);
367
368 // Try to fold commutative constant math with an LLVM_Arg in between, such
369 // as {C1 + Arg + C2 +}.
370 if (tryFoldCommutativeMathWithArgInBetween(Const1: *Const1, Ops, Loc, Cursor,
371 WorkingOps&: ResultOps))
372 continue;
373
374 consumeOneOperator(Cursor, Loc, Op: Ops[0]);
375 }
376 ResultOps = optimizeDwarfOperations(WorkingOps: ResultOps);
377 auto *Result = DIExpression::get(Context&: getContext(), Elements: ResultOps);
378 assert(Result->isValid() && "concatenated expression is not valid");
379 return Result;
380}
381