1//===- InstCombineNegator.cpp -----------------------------------*- C++ -*-===//
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 sinking of negation into expression trees,
10// as long as that can be done without increasing instruction count.
11//
12//===----------------------------------------------------------------------===//
13
14#include "InstCombineInternal.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/None.h"
19#include "llvm/ADT/Optional.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/ADT/Twine.h"
25#include "llvm/ADT/iterator_range.h"
26#include "llvm/Analysis/TargetFolder.h"
27#include "llvm/Analysis/ValueTracking.h"
28#include "llvm/IR/Constant.h"
29#include "llvm/IR/Constants.h"
30#include "llvm/IR/DebugLoc.h"
31#include "llvm/IR/IRBuilder.h"
32#include "llvm/IR/Instruction.h"
33#include "llvm/IR/Instructions.h"
34#include "llvm/IR/PatternMatch.h"
35#include "llvm/IR/Type.h"
36#include "llvm/IR/Use.h"
37#include "llvm/IR/User.h"
38#include "llvm/IR/Value.h"
39#include "llvm/Support/Casting.h"
40#include "llvm/Support/CommandLine.h"
41#include "llvm/Support/Compiler.h"
42#include "llvm/Support/DebugCounter.h"
43#include "llvm/Support/ErrorHandling.h"
44#include "llvm/Support/raw_ostream.h"
45#include <functional>
46#include <tuple>
47#include <type_traits>
48#include <utility>
49
50namespace llvm {
51class AssumptionCache;
52class DataLayout;
53class DominatorTree;
54class LLVMContext;
55} // namespace llvm
56
57using namespace llvm;
58
59#define DEBUG_TYPE "instcombine"
60
61STATISTIC(NegatorTotalNegationsAttempted,
62          "Negator: Number of negations attempted to be sinked");
63STATISTIC(NegatorNumTreesNegated,
64          "Negator: Number of negations successfully sinked");
65STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
66                                  "reached while attempting to sink negation");
67STATISTIC(NegatorTimesDepthLimitReached,
68          "Negator: How many times did the traversal depth limit was reached "
69          "during sinking");
70STATISTIC(
71    NegatorNumValuesVisited,
72    "Negator: Total number of values visited during attempts to sink negation");
73STATISTIC(NegatorNumNegationsFoundInCache,
74          "Negator: How many negations did we retrieve/reuse from cache");
75STATISTIC(NegatorMaxTotalValuesVisited,
76          "Negator: Maximal number of values ever visited while attempting to "
77          "sink negation");
78STATISTIC(NegatorNumInstructionsCreatedTotal,
79          "Negator: Number of new negated instructions created, total");
80STATISTIC(NegatorMaxInstructionsCreated,
81          "Negator: Maximal number of new instructions created during negation "
82          "attempt");
83STATISTIC(NegatorNumInstructionsNegatedSuccess,
84          "Negator: Number of new negated instructions created in successful "
85          "negation sinking attempts");
86
87DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
88              "Controls Negator transformations in InstCombine pass");
89
90static cl::opt<bool>
91    NegatorEnabled("instcombine-negator-enabled", cl::init(true),
92                   cl::desc("Should we attempt to sink negations?"));
93
94static cl::opt<unsigned>
95    NegatorMaxDepth("instcombine-negator-max-depth",
96                    cl::init(NegatorDefaultMaxDepth),
97                    cl::desc("What is the maximal lookup depth when trying to "
98                             "check for viability of negation sinking."));
99
100Negator::Negator(LLVMContext &C, const DataLayout &DL_, AssumptionCache &AC_,
101                 const DominatorTree &DT_, bool IsTrulyNegation_)
102    : Builder(C, TargetFolder(DL_),
103              IRBuilderCallbackInserter([&](Instruction *I) {
104                ++NegatorNumInstructionsCreatedTotal;
105                NewInstructions.push_back(I);
106              })),
107      DL(DL_), AC(AC_), DT(DT_), IsTrulyNegation(IsTrulyNegation_) {}
108
109#if LLVM_ENABLE_STATS
110Negator::~Negator() {
111  NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
112}
113#endif
114
115// FIXME: can this be reworked into a worklist-based algorithm while preserving
116// the depth-first, early bailout traversal?
117LLVM_NODISCARD Value *Negator::visitImpl(Value *V, unsigned Depth) {
118  // -(undef) -> undef.
119  if (match(V, m_Undef()))
120    return V;
121
122  // In i1, negation can simply be ignored.
123  if (V->getType()->isIntOrIntVectorTy(1))
124    return V;
125
126  Value *X;
127
128  // -(-(X)) -> X.
129  if (match(V, m_Neg(m_Value(X))))
130    return X;
131
132  // Integral constants can be freely negated.
133  if (match(V, m_AnyIntegralConstant()))
134    return ConstantExpr::getNeg(cast<Constant>(V), /*HasNUW=*/false,
135                                /*HasNSW=*/false);
136
137  // If we have a non-instruction, then give up.
138  if (!isa<Instruction>(V))
139    return nullptr;
140
141  // If we have started with a true negation (i.e. `sub 0, %y`), then if we've
142  // got instruction that does not require recursive reasoning, we can still
143  // negate it even if it has other uses, without increasing instruction count.
144  if (!V->hasOneUse() && !IsTrulyNegation)
145    return nullptr;
146
147  auto *I = cast<Instruction>(V);
148  unsigned BitWidth = I->getType()->getScalarSizeInBits();
149
150  // We must preserve the insertion point and debug info that is set in the
151  // builder at the time this function is called.
152  InstCombiner::BuilderTy::InsertPointGuard Guard(Builder);
153  // And since we are trying to negate instruction I, that tells us about the
154  // insertion point and the debug info that we need to keep.
155  Builder.SetInsertPoint(I);
156
157  // In some cases we can give the answer without further recursion.
158  switch (I->getOpcode()) {
159  case Instruction::Add:
160    // `inc` is always negatible.
161    if (match(I->getOperand(1), m_One()))
162      return Builder.CreateNot(I->getOperand(0), I->getName() + ".neg");
163    break;
164  case Instruction::Xor:
165    // `not` is always negatible.
166    if (match(I, m_Not(m_Value(X))))
167      return Builder.CreateAdd(X, ConstantInt::get(X->getType(), 1),
168                               I->getName() + ".neg");
169    break;
170  case Instruction::AShr:
171  case Instruction::LShr: {
172    // Right-shift sign bit smear is negatible.
173    const APInt *Op1Val;
174    if (match(I->getOperand(1), m_APInt(Op1Val)) && *Op1Val == BitWidth - 1) {
175      Value *BO = I->getOpcode() == Instruction::AShr
176                      ? Builder.CreateLShr(I->getOperand(0), I->getOperand(1))
177                      : Builder.CreateAShr(I->getOperand(0), I->getOperand(1));
178      if (auto *NewInstr = dyn_cast<Instruction>(BO)) {
179        NewInstr->copyIRFlags(I);
180        NewInstr->setName(I->getName() + ".neg");
181      }
182      return BO;
183    }
184    break;
185  }
186  case Instruction::SExt:
187  case Instruction::ZExt:
188    // `*ext` of i1 is always negatible
189    if (I->getOperand(0)->getType()->isIntOrIntVectorTy(1))
190      return I->getOpcode() == Instruction::SExt
191                 ? Builder.CreateZExt(I->getOperand(0), I->getType(),
192                                      I->getName() + ".neg")
193                 : Builder.CreateSExt(I->getOperand(0), I->getType(),
194                                      I->getName() + ".neg");
195    break;
196  default:
197    break; // Other instructions require recursive reasoning.
198  }
199
200  // Some other cases, while still don't require recursion,
201  // are restricted to the one-use case.
202  if (!V->hasOneUse())
203    return nullptr;
204
205  switch (I->getOpcode()) {
206  case Instruction::Sub:
207    // `sub` is always negatible.
208    // But if the old `sub` sticks around, even thought we don't increase
209    // instruction count, this is a likely regression since we increased
210    // live-range of *both* of the operands, which might lead to more spilling.
211    return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
212                             I->getName() + ".neg");
213  case Instruction::SDiv:
214    // `sdiv` is negatible if divisor is not undef/INT_MIN/1.
215    // While this is normally not behind a use-check,
216    // let's consider division to be special since it's costly.
217    if (auto *Op1C = dyn_cast<Constant>(I->getOperand(1))) {
218      if (!Op1C->containsUndefElement() && Op1C->isNotMinSignedValue() &&
219          Op1C->isNotOneValue()) {
220        Value *BO =
221            Builder.CreateSDiv(I->getOperand(0), ConstantExpr::getNeg(Op1C),
222                               I->getName() + ".neg");
223        if (auto *NewInstr = dyn_cast<Instruction>(BO))
224          NewInstr->setIsExact(I->isExact());
225        return BO;
226      }
227    }
228    break;
229  }
230
231  // Rest of the logic is recursive, so if it's time to give up then it's time.
232  if (Depth > NegatorMaxDepth) {
233    LLVM_DEBUG(dbgs() << "Negator: reached maximal allowed traversal depth in "
234                      << *V << ". Giving up.\n");
235    ++NegatorTimesDepthLimitReached;
236    return nullptr;
237  }
238
239  switch (I->getOpcode()) {
240  case Instruction::PHI: {
241    // `phi` is negatible if all the incoming values are negatible.
242    auto *PHI = cast<PHINode>(I);
243    SmallVector<Value *, 4> NegatedIncomingValues(PHI->getNumOperands());
244    for (auto I : zip(PHI->incoming_values(), NegatedIncomingValues)) {
245      if (!(std::get<1>(I) =
246                negate(std::get<0>(I), Depth + 1))) // Early return.
247        return nullptr;
248    }
249    // All incoming values are indeed negatible. Create negated PHI node.
250    PHINode *NegatedPHI = Builder.CreatePHI(
251        PHI->getType(), PHI->getNumOperands(), PHI->getName() + ".neg");
252    for (auto I : zip(NegatedIncomingValues, PHI->blocks()))
253      NegatedPHI->addIncoming(std::get<0>(I), std::get<1>(I));
254    return NegatedPHI;
255  }
256  case Instruction::Select: {
257    {
258      // `abs`/`nabs` is always negatible.
259      Value *LHS, *RHS;
260      SelectPatternFlavor SPF =
261          matchSelectPattern(I, LHS, RHS, /*CastOp=*/nullptr, Depth).Flavor;
262      if (SPF == SPF_ABS || SPF == SPF_NABS) {
263        auto *NewSelect = cast<SelectInst>(I->clone());
264        // Just swap the operands of the select.
265        NewSelect->swapValues();
266        // Don't swap prof metadata, we didn't change the branch behavior.
267        NewSelect->setName(I->getName() + ".neg");
268        Builder.Insert(NewSelect);
269        return NewSelect;
270      }
271    }
272    // `select` is negatible if both hands of `select` are negatible.
273    Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
274    if (!NegOp1) // Early return.
275      return nullptr;
276    Value *NegOp2 = negate(I->getOperand(2), Depth + 1);
277    if (!NegOp2)
278      return nullptr;
279    // Do preserve the metadata!
280    return Builder.CreateSelect(I->getOperand(0), NegOp1, NegOp2,
281                                I->getName() + ".neg", /*MDFrom=*/I);
282  }
283  case Instruction::ShuffleVector: {
284    // `shufflevector` is negatible if both operands are negatible.
285    auto *Shuf = cast<ShuffleVectorInst>(I);
286    Value *NegOp0 = negate(I->getOperand(0), Depth + 1);
287    if (!NegOp0) // Early return.
288      return nullptr;
289    Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
290    if (!NegOp1)
291      return nullptr;
292    return Builder.CreateShuffleVector(NegOp0, NegOp1, Shuf->getShuffleMask(),
293                                       I->getName() + ".neg");
294  }
295  case Instruction::ExtractElement: {
296    // `extractelement` is negatible if source operand is negatible.
297    auto *EEI = cast<ExtractElementInst>(I);
298    Value *NegVector = negate(EEI->getVectorOperand(), Depth + 1);
299    if (!NegVector) // Early return.
300      return nullptr;
301    return Builder.CreateExtractElement(NegVector, EEI->getIndexOperand(),
302                                        I->getName() + ".neg");
303  }
304  case Instruction::InsertElement: {
305    // `insertelement` is negatible if both the source vector and
306    // element-to-be-inserted are negatible.
307    auto *IEI = cast<InsertElementInst>(I);
308    Value *NegVector = negate(IEI->getOperand(0), Depth + 1);
309    if (!NegVector) // Early return.
310      return nullptr;
311    Value *NegNewElt = negate(IEI->getOperand(1), Depth + 1);
312    if (!NegNewElt) // Early return.
313      return nullptr;
314    return Builder.CreateInsertElement(NegVector, NegNewElt, IEI->getOperand(2),
315                                       I->getName() + ".neg");
316  }
317  case Instruction::Trunc: {
318    // `trunc` is negatible if its operand is negatible.
319    Value *NegOp = negate(I->getOperand(0), Depth + 1);
320    if (!NegOp) // Early return.
321      return nullptr;
322    return Builder.CreateTrunc(NegOp, I->getType(), I->getName() + ".neg");
323  }
324  case Instruction::Shl: {
325    // `shl` is negatible if the first operand is negatible.
326    Value *NegOp0 = negate(I->getOperand(0), Depth + 1);
327    if (!NegOp0) // Early return.
328      return nullptr;
329    return Builder.CreateShl(NegOp0, I->getOperand(1), I->getName() + ".neg");
330  }
331  case Instruction::Or:
332    if (!haveNoCommonBitsSet(I->getOperand(0), I->getOperand(1), DL, &AC, I,
333                             &DT))
334      return nullptr; // Don't know how to handle `or` in general.
335    // `or`/`add` are interchangeable when operands have no common bits set.
336    // `inc` is always negatible.
337    if (match(I->getOperand(1), m_One()))
338      return Builder.CreateNot(I->getOperand(0), I->getName() + ".neg");
339    // Else, just defer to Instruction::Add handling.
340    LLVM_FALLTHROUGH;
341  case Instruction::Add: {
342    // `add` is negatible if both of its operands are negatible.
343    Value *NegOp0 = negate(I->getOperand(0), Depth + 1);
344    if (!NegOp0) // Early return.
345      return nullptr;
346    Value *NegOp1 = negate(I->getOperand(1), Depth + 1);
347    if (!NegOp1)
348      return nullptr;
349    return Builder.CreateAdd(NegOp0, NegOp1, I->getName() + ".neg");
350  }
351  case Instruction::Xor:
352    // `xor` is negatible if one of its operands is invertible.
353    // FIXME: InstCombineInverter? But how to connect Inverter and Negator?
354    if (auto *C = dyn_cast<Constant>(I->getOperand(1))) {
355      Value *Xor = Builder.CreateXor(I->getOperand(0), ConstantExpr::getNot(C));
356      return Builder.CreateAdd(Xor, ConstantInt::get(Xor->getType(), 1),
357                               I->getName() + ".neg");
358    }
359    return nullptr;
360  case Instruction::Mul: {
361    // `mul` is negatible if one of its operands is negatible.
362    Value *NegatedOp, *OtherOp;
363    // First try the second operand, in case it's a constant it will be best to
364    // just invert it instead of sinking the `neg` deeper.
365    if (Value *NegOp1 = negate(I->getOperand(1), Depth + 1)) {
366      NegatedOp = NegOp1;
367      OtherOp = I->getOperand(0);
368    } else if (Value *NegOp0 = negate(I->getOperand(0), Depth + 1)) {
369      NegatedOp = NegOp0;
370      OtherOp = I->getOperand(1);
371    } else
372      // Can't negate either of them.
373      return nullptr;
374    return Builder.CreateMul(NegatedOp, OtherOp, I->getName() + ".neg");
375  }
376  default:
377    return nullptr; // Don't know, likely not negatible for free.
378  }
379
380  llvm_unreachable("Can't get here. We always return from switch.");
381}
382
383LLVM_NODISCARD Value *Negator::negate(Value *V, unsigned Depth) {
384  NegatorMaxDepthVisited.updateMax(Depth);
385  ++NegatorNumValuesVisited;
386
387#if LLVM_ENABLE_STATS
388  ++NumValuesVisitedInThisNegator;
389#endif
390
391#ifndef NDEBUG
392  // We can't ever have a Value with such an address.
393  Value *Placeholder = reinterpret_cast<Value *>(static_cast<uintptr_t>(-1));
394#endif
395
396  // Did we already try to negate this value?
397  auto NegationsCacheIterator = NegationsCache.find(V);
398  if (NegationsCacheIterator != NegationsCache.end()) {
399    ++NegatorNumNegationsFoundInCache;
400    Value *NegatedV = NegationsCacheIterator->second;
401    assert(NegatedV != Placeholder && "Encountered a cycle during negation.");
402    return NegatedV;
403  }
404
405#ifndef NDEBUG
406  // We did not find a cached result for negation of V. While there,
407  // let's temporairly cache a placeholder value, with the idea that if later
408  // during negation we fetch it from cache, we'll know we're in a cycle.
409  NegationsCache[V] = Placeholder;
410#endif
411
412  // No luck. Try negating it for real.
413  Value *NegatedV = visitImpl(V, Depth);
414  // And cache the (real) result for the future.
415  NegationsCache[V] = NegatedV;
416
417  return NegatedV;
418}
419
420LLVM_NODISCARD Optional<Negator::Result> Negator::run(Value *Root) {
421  Value *Negated = negate(Root, /*Depth=*/0);
422  if (!Negated) {
423    // We must cleanup newly-inserted instructions, to avoid any potential
424    // endless combine looping.
425    llvm::for_each(llvm::reverse(NewInstructions),
426                   [&](Instruction *I) { I->eraseFromParent(); });
427    return llvm::None;
428  }
429  return std::make_pair(ArrayRef<Instruction *>(NewInstructions), Negated);
430}
431
432LLVM_NODISCARD Value *Negator::Negate(bool LHSIsZero, Value *Root,
433                                      InstCombiner &IC) {
434  ++NegatorTotalNegationsAttempted;
435  LLVM_DEBUG(dbgs() << "Negator: attempting to sink negation into " << *Root
436                    << "\n");
437
438  if (!NegatorEnabled || !DebugCounter::shouldExecute(NegatorCounter))
439    return nullptr;
440
441  Negator N(Root->getContext(), IC.getDataLayout(), IC.getAssumptionCache(),
442            IC.getDominatorTree(), LHSIsZero);
443  Optional<Result> Res = N.run(Root);
444  if (!Res) { // Negation failed.
445    LLVM_DEBUG(dbgs() << "Negator: failed to sink negation into " << *Root
446                      << "\n");
447    return nullptr;
448  }
449
450  LLVM_DEBUG(dbgs() << "Negator: successfully sunk negation into " << *Root
451                    << "\n         NEW: " << *Res->second << "\n");
452  ++NegatorNumTreesNegated;
453
454  // We must temporarily unset the 'current' insertion point and DebugLoc of the
455  // InstCombine's IRBuilder so that it won't interfere with the ones we have
456  // already specified when producing negated instructions.
457  InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
458  IC.Builder.ClearInsertionPoint();
459  IC.Builder.SetCurrentDebugLocation(DebugLoc());
460
461  // And finally, we must add newly-created instructions into the InstCombine's
462  // worklist (in a proper order!) so it can attempt to combine them.
463  LLVM_DEBUG(dbgs() << "Negator: Propagating " << Res->first.size()
464                    << " instrs to InstCombine\n");
465  NegatorMaxInstructionsCreated.updateMax(Res->first.size());
466  NegatorNumInstructionsNegatedSuccess += Res->first.size();
467
468  // They are in def-use order, so nothing fancy, just insert them in order.
469  llvm::for_each(Res->first,
470                 [&](Instruction *I) { IC.Builder.Insert(I, I->getName()); });
471
472  // And return the new root.
473  return Res->second;
474}
475