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 ((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 }