381 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements functions to constant fold DIExpressions. Which were10// declared in DIExpressionOptimizer.h11//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(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 returning43/// 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(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 are90/// 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(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(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_plus113/// 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(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_uconst148/// 2. DW_OP_constu, 0 to DW_OP_lit0149static 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(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]} -> {}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(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}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(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]}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(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]}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(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 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 pattern297 // 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, such369 // 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}381