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