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

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.

20 static 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.

27 static 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>

45 foldOperationIfPossible(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(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 (Const2 >= std::numeric_limits<uint64_t>::digits ||

63 static_cast<uint64_t >(countl_zero(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(Const1)) < Const2)

70 return std::nullopt;

71 return Const1 >> Const2;

72 }

73 case dwarf::DW_OP_mul: {

74 auto Result = SaturatingMultiply(Const1, Const2, &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.

91 static 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).

98 static void consumeOneOperator(DIExpressionCursor &Cursor, uint64_t &Loc,

99 const DIExpression::ExprOperand &Op) {

100 Cursor.consume(1);

101 Loc = Loc + Op.getSize();

102}

103

104/// Reset the Cursor to the beginning of the WorkingOps.

105 void startFromBeginning(uint64_t &Loc, DIExpressionCursor &Cursor,

106 ArrayRef<uint64_t> WorkingOps) {

107 Cursor.assignNewExpr(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>

115 canonicalizeDwarfOperations(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(dwarf::DW_OP_constu);

128 ResultOps.push_back(OpRaw - dwarf::DW_OP_lit0);

129 consumeOneOperator(Cursor, Loc, *Cursor.peek());

130 continue;

131 }

132 if (OpRaw == dwarf::DW_OP_plus_uconst) {

133 ResultOps.push_back(dwarf::DW_OP_constu);

134 ResultOps.push_back(Op->getArg(0));

135 ResultOps.push_back(dwarf::DW_OP_plus);

136 consumeOneOperator(Cursor, Loc, *Cursor.peek());

137 continue;

138 }

139 uint64_t PrevLoc = Loc;

140 consumeOneOperator(Cursor, Loc, *Cursor.peek());

141 ResultOps.append(WorkingOps.begin() + PrevLoc, 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>

150 optimizeDwarfOperations(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(0) == 0) {

162 ResultOps.push_back(dwarf::DW_OP_lit0);

163 consumeOneOperator(Cursor, Loc, *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, *Cursor.peek());

172 ResultOps.append(WorkingOps.begin() + PrevLoc, 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(dwarf::DW_OP_plus_uconst);

179 ResultOps.push_back(Op1->getArg(0));

180 consumeOneOperator(Cursor, Loc, *Cursor.peek());

181 consumeOneOperator(Cursor, Loc, *Cursor.peek());

182 continue;

183 }

184 uint64_t PrevLoc = Loc;

185 consumeOneOperator(Cursor, Loc, *Cursor.peek());

186 ResultOps.append(WorkingOps.begin() + PrevLoc, 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]} -> {}

193 static 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(Ops[1].getOp(), Const1)) {

199 WorkingOps.erase(WorkingOps.begin() + Loc, 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}

209 static 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(Ops[1]);

215 if (!Const2)

216 return false;

217

218 auto Result = foldOperationIfPossible(

219 Const1, *Const2, static_cast<dwarf::LocationAtom >(Ops[2].getOp()));

220 if (!Result) {

221 consumeOneOperator(Cursor, Loc, Ops[0]);

222 return true;

223 }

224 WorkingOps.erase(WorkingOps.begin() + Loc + 2, 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]}

234 static 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(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(Operand1, Operand2))

244 return false;

245

246 auto Result = foldOperationIfPossible(Const1, *Const2, Operand1);

247 if (!Result) {

248 consumeOneOperator(Cursor, Loc, Ops[0]);

249 return true;

250 }

251 WorkingOps.erase(WorkingOps.begin() + Loc + 3, 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]}

262 static 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(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(Operand1, Operand2) ||

273 !operationsAreFoldableAndCommutative(Operand2, Operand3))

274 return false;

275

276 auto Result = foldOperationIfPossible(Const1, *Const2, Operand1);

277 if (!Result) {

278 consumeOneOperator(Cursor, Loc, Ops[0]);

279 return true;

280 }

281 WorkingOps.erase(WorkingOps.begin() + Loc + 6, 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

288 DIExpression *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);

307

308 if (!Const1) {

309 // Early exit, all of the following patterns start with a constant value.

310 consumeOneOperator(Cursor, Loc, *Op);

311 continue;

312 }

313

314 Ops.push_back(*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(*Op);

322

323 // Try to fold a constant no-op, such as {+ 0}

324 if (tryFoldNoOpMath(*Const1, Ops, Loc, Cursor, ResultOps))

325 continue;

326

327 Op = Cursor.peekNextN(2);

328 // Op[1] could still match a pattern, skip iteration.

329 if (!Op) {

330 consumeOneOperator(Cursor, Loc, Ops[0]);

331 continue;

332 }

333

334 Ops.push_back(*Op);

335

336 // Try to fold a pattern of two constants such as {C1 + C2}.

337 if (tryFoldConstants(*Const1, Ops, Loc, Cursor, ResultOps))

338 continue;

339

340 Op = Cursor.peekNextN(3);

341 // Op[1] and Op[2] could still match a pattern, skip iteration.

342 if (!Op) {

343 consumeOneOperator(Cursor, Loc, Ops[0]);

344 continue;

345 }

346

347 Ops.push_back(*Op);

348

349 // Try to fold commutative constant math, such as {C1 + C2 +}.

350 if (tryFoldCommutativeMath(*Const1, Ops, Loc, Cursor, ResultOps))

351 continue;

352

353 Op = Cursor.peekNextN(4);

354 if (!Op) {

355 consumeOneOperator(Cursor, Loc, Ops[0]);

356 continue;

357 }

358

359 Ops.push_back(*Op);

360 Op = Cursor.peekNextN(5);

361 if (!Op) {

362 consumeOneOperator(Cursor, Loc, Ops[0]);

363 continue;

364 }

365

366 Ops.push_back(*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, Ops, Loc, Cursor,

371 ResultOps))

372 continue;

373

374 consumeOneOperator(Cursor, Loc, Ops[0]);

375 }

376 ResultOps = optimizeDwarfOperations(ResultOps);

377 auto *Result = DIExpression::get(getContext(), ResultOps);

378 assert(Result->isValid() && "concatenated expression is not valid");

379 return Result;

380}

assert

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

tryFoldNoOpMath

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,...

Definition DIExpressionOptimizer.cpp:193

operationsAreFoldableAndCommutative

static bool operationsAreFoldableAndCommutative(dwarf::LocationAtom Operator1, dwarf::LocationAtom Operator2)

Returns true if the two operations Operator1 and Operator2 are commutative and can be folded.

Definition DIExpressionOptimizer.cpp:91

isNeutralElement

static bool isNeutralElement(uint64_t Op, uint64_t Val)

Returns true if an operation and operand result in a No Op.

Definition DIExpressionOptimizer.cpp:27

foldOperationIfPossible

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,...

Definition DIExpressionOptimizer.cpp:45

tryFoldCommutativeMath

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]}...

Definition DIExpressionOptimizer.cpp:234

startFromBeginning

void startFromBeginning(uint64_t &Loc, DIExpressionCursor &Cursor, ArrayRef< uint64_t > WorkingOps)

Reset the Cursor to the beginning of the WorkingOps.

Definition DIExpressionOptimizer.cpp:105

optimizeDwarfOperations

static SmallVector< uint64_t > optimizeDwarfOperations(ArrayRef< uint64_t > WorkingOps)

This function will convert:

Definition DIExpressionOptimizer.cpp:150

tryFoldCommutativeMathWithArgInBetween

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],...

Definition DIExpressionOptimizer.cpp:262

tryFoldConstants

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...

Definition DIExpressionOptimizer.cpp:209

consumeOneOperator

static void consumeOneOperator(DIExpressionCursor &Cursor, uint64_t &Loc, const DIExpression::ExprOperand &Op)

Consume one operator and its operand(s).

Definition DIExpressionOptimizer.cpp:98

isConstantVal

static std::optional< uint64_t > isConstantVal(DIExpression::ExprOperand Op)

Returns true if the Op is a DW_OP_constu.

Definition DIExpressionOptimizer.cpp:20

canonicalizeDwarfOperations

static SmallVector< uint64_t > canonicalizeDwarfOperations(ArrayRef< uint64_t > WorkingOps)

This function will canonicalize:

Definition DIExpressionOptimizer.cpp:115

DebugInfoMetadata.h

Dwarf.h

This file contains constants used for implementing Dwarf debug support.

Ops

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

Definition ItaniumDemangle.h:3368

llvm::ArrayRef

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition ArrayRef.h:41

llvm::ArrayRef::size

size_t size() const

size - Get the array size.

Definition ArrayRef.h:143

llvm::ArrayRef::begin

iterator begin() const

Definition ArrayRef.h:131

llvm::DIExpressionCursor

Holds a DIExpression and keeps track of how many operands have been consumed so far.

Definition DebugInfoMetadata.h:3854

llvm::DIExpression::ExprOperand

A lightweight wrapper around an expression operand.

Definition DebugInfoMetadata.h:3430

llvm::DIExpression::foldConstantMath

LLVM_ABI DIExpression * foldConstantMath()

Try to shorten an expression with constant math operations that can be evaluated at compile time.

Definition DIExpressionOptimizer.cpp:288

llvm::MDNode::get

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

Definition Metadata.h:1569

llvm::MDNode::getContext

LLVMContext & getContext() const

Definition Metadata.h:1242

llvm::Operator

This is a utility class that provides an abstraction for the common functionality between Instruction...

Definition Operator.h:33

llvm::SmallVectorImpl

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

Definition SmallVector.h:574

llvm::SmallVectorImpl::erase

iterator erase(const_iterator CI)

Definition SmallVector.h:744

llvm::SmallVectorImpl::append

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

Definition SmallVector.h:684

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition SmallVector.h:417

llvm::SmallVectorTemplateCommon::size

size_t size() const

Definition SmallVector.h:80

llvm::SmallVectorTemplateCommon::begin

iterator begin()

Definition SmallVector.h:271

llvm::SmallVector

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Definition SmallVector.h:1203

uint64_t

llvm::Loc

Definition DwarfDebug.h:129

llvm::dwarf::LocationAtom

LocationAtom

Definition Dwarf.h:138

llvm::dwarf::DW_OP_LLVM_arg

@ DW_OP_LLVM_arg

Only used in LLVM metadata.

Definition Dwarf.h:149

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition AddressRanges.h:18

llvm::countr_zero

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:202

llvm::countl_zero

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:236

llvm::SaturatingMultiply

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

llvm::Op

DWARFExpression::Operation Op

Definition DWARFExpressionPrinter.cpp:22

llvm::SaturatingAdd

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

Generated on for LLVM by doxygen 1.14.0

LLVM: lib/IR/DIExpressionOptimizer.cpp Source File