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