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 17 using 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. 44 static 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> 114 static 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 149 static 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 } 381