llvm/lib/IR/DIExpressionOptimizer.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-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 }