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 ((uint64_t)countl_zero(Const1) < Const2) 63 return std::nullopt; 64 return Const1 << Const2; 65 } 66 case dwarf::DW_OP_shr: { 67 if ((uint64_t)countr_zero(Const1) < Const2) 68 return std::nullopt; 69 return Const1 >> Const2; 70 } 71 case dwarf::DW_OP_mul: { 72 auto Result = SaturatingMultiply(Const1, Const2, &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. 89 static 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). 96 static void consumeOneOperator(DIExpressionCursor &Cursor, uint64_t &Loc, 97 const DIExpression::ExprOperand &Op) { 98 Cursor.consume(1); 99 Loc = Loc + Op.getSize(); 100 } 101 102 /// Reset the Cursor to the beginning of the WorkingOps. 103 void startFromBeginning(uint64_t &Loc, DIExpressionCursor &Cursor, 104 ArrayRef<uint64_t> WorkingOps) { 105 Cursor.assignNewExpr(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> 112 static SmallVector<uint64_t> 113 canonicalizeDwarfOperations(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(dwarf::DW_OP_constu); 126 ResultOps.push_back(OpRaw - dwarf::DW_OP_lit0); 127 consumeOneOperator(Cursor, Loc, *Cursor.peek()); 128 continue; 129 } 130 if (OpRaw == dwarf::DW_OP_plus_uconst) { 131 ResultOps.push_back(dwarf::DW_OP_constu); 132 ResultOps.push_back(Op->getArg(0)); 133 ResultOps.push_back(dwarf::DW_OP_plus); 134 consumeOneOperator(Cursor, Loc, *Cursor.peek()); 135 continue; 136 } 137 uint64_t PrevLoc = Loc; 138 consumeOneOperator(Cursor, Loc, *Cursor.peek()); 139 ResultOps.append(WorkingOps.begin() + PrevLoc, 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 147 static SmallVector<uint64_t> 148 optimizeDwarfOperations(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(0) == 0) { 160 ResultOps.push_back(dwarf::DW_OP_lit0); 161 consumeOneOperator(Cursor, Loc, *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, *Cursor.peek()); 170 ResultOps.append(WorkingOps.begin() + PrevLoc, 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(dwarf::DW_OP_plus_uconst); 177 ResultOps.push_back(Op1->getArg(0)); 178 consumeOneOperator(Cursor, Loc, *Cursor.peek()); 179 consumeOneOperator(Cursor, Loc, *Cursor.peek()); 180 continue; 181 } 182 uint64_t PrevLoc = Loc; 183 consumeOneOperator(Cursor, Loc, *Cursor.peek()); 184 ResultOps.append(WorkingOps.begin() + PrevLoc, 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]} -> {} 191 static 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(Ops[1].getOp(), Const1)) { 197 WorkingOps.erase(WorkingOps.begin() + Loc, 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} 207 static 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(Ops[1]); 213 if (!Const2) 214 return false; 215 216 auto Result = foldOperationIfPossible( 217 Const1, *Const2, static_cast<dwarf::LocationAtom>(Ops[2].getOp())); 218 if (!Result) { 219 consumeOneOperator(Cursor, Loc, Ops[0]); 220 return true; 221 } 222 WorkingOps.erase(WorkingOps.begin() + Loc + 2, 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]} 232 static 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(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(Operand1, Operand2)) 242 return false; 243 244 auto Result = foldOperationIfPossible(Const1, *Const2, Operand1); 245 if (!Result) { 246 consumeOneOperator(Cursor, Loc, Ops[0]); 247 return true; 248 } 249 WorkingOps.erase(WorkingOps.begin() + Loc + 3, 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]} 260 static 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(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(Operand1, Operand2) || 271 !operationsAreFoldableAndCommutative(Operand2, Operand3)) 272 return false; 273 274 auto Result = foldOperationIfPossible(Const1, *Const2, Operand1); 275 if (!Result) { 276 consumeOneOperator(Cursor, Loc, Ops[0]); 277 return true; 278 } 279 WorkingOps.erase(WorkingOps.begin() + Loc + 6, 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 286 DIExpression *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); 305 306 if (!Const1) { 307 // Early exit, all of the following patterns start with a constant value. 308 consumeOneOperator(Cursor, Loc, *Op); 309 continue; 310 } 311 312 Ops.push_back(*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(*Op); 320 321 // Try to fold a constant no-op, such as {+ 0} 322 if (tryFoldNoOpMath(*Const1, Ops, Loc, Cursor, ResultOps)) 323 continue; 324 325 Op = Cursor.peekNextN(2); 326 // Op[1] could still match a pattern, skip iteration. 327 if (!Op) { 328 consumeOneOperator(Cursor, Loc, Ops[0]); 329 continue; 330 } 331 332 Ops.push_back(*Op); 333 334 // Try to fold a pattern of two constants such as {C1 + C2}. 335 if (tryFoldConstants(*Const1, Ops, Loc, Cursor, ResultOps)) 336 continue; 337 338 Op = Cursor.peekNextN(3); 339 // Op[1] and Op[2] could still match a pattern, skip iteration. 340 if (!Op) { 341 consumeOneOperator(Cursor, Loc, Ops[0]); 342 continue; 343 } 344 345 Ops.push_back(*Op); 346 347 // Try to fold commutative constant math, such as {C1 + C2 +}. 348 if (tryFoldCommutativeMath(*Const1, Ops, Loc, Cursor, ResultOps)) 349 continue; 350 351 Op = Cursor.peekNextN(4); 352 if (!Op) { 353 consumeOneOperator(Cursor, Loc, Ops[0]); 354 continue; 355 } 356 357 Ops.push_back(*Op); 358 Op = Cursor.peekNextN(5); 359 if (!Op) { 360 consumeOneOperator(Cursor, Loc, Ops[0]); 361 continue; 362 } 363 364 Ops.push_back(*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, Ops, Loc, Cursor, 369 ResultOps)) 370 continue; 371 372 consumeOneOperator(Cursor, Loc, Ops[0]); 373 } 374 ResultOps = optimizeDwarfOperations(ResultOps); 375 auto *Result = DIExpression::get(getContext(), ResultOps); 376 assert(Result->isValid() && "concatenated expression is not valid"); 377 return Result; 378 } 379