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