llvm/llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

//===- InstCombineNegator.cpp -----------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements sinking of negation into expression trees,
// as long as that can be done without increasing instruction count.
//
//===----------------------------------------------------------------------===//

#include "InstCombineInternal.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/TargetFolder.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include <cassert>
#include <cstdint>
#include <functional>
#include <type_traits>
#include <utility>

usingnamespacellvm;
usingnamespacellvm::PatternMatch;

#define DEBUG_TYPE …

STATISTIC(NegatorTotalNegationsAttempted,
          "Negator: Number of negations attempted to be sinked");
STATISTIC(NegatorNumTreesNegated,
          "Negator: Number of negations successfully sinked");
STATISTIC(NegatorMaxDepthVisited, "Negator: Maximal traversal depth ever "
                                  "reached while attempting to sink negation");
STATISTIC(NegatorTimesDepthLimitReached,
          "Negator: How many times did the traversal depth limit was reached "
          "during sinking");
STATISTIC(
    NegatorNumValuesVisited,
    "Negator: Total number of values visited during attempts to sink negation");
STATISTIC(NegatorNumNegationsFoundInCache,
          "Negator: How many negations did we retrieve/reuse from cache");
STATISTIC(NegatorMaxTotalValuesVisited,
          "Negator: Maximal number of values ever visited while attempting to "
          "sink negation");
STATISTIC(NegatorNumInstructionsCreatedTotal,
          "Negator: Number of new negated instructions created, total");
STATISTIC(NegatorMaxInstructionsCreated,
          "Negator: Maximal number of new instructions created during negation "
          "attempt");
STATISTIC(NegatorNumInstructionsNegatedSuccess,
          "Negator: Number of new negated instructions created in successful "
          "negation sinking attempts");

DEBUG_COUNTER(NegatorCounter, "instcombine-negator",
              "Controls Negator transformations in InstCombine pass");

static cl::opt<bool>
    NegatorEnabled("instcombine-negator-enabled", cl::init(true),
                   cl::desc("Should we attempt to sink negations?"));

static cl::opt<unsigned>
    NegatorMaxDepth("instcombine-negator-max-depth",
                    cl::init(NegatorDefaultMaxDepth),
                    cl::desc("What is the maximal lookup depth when trying to "
                             "check for viability of negation sinking."));

Negator::Negator(LLVMContext &C, const DataLayout &DL, const DominatorTree &DT_,
                 bool IsTrulyNegation_)
    : … { … }

#if LLVM_ENABLE_STATS
Negator::~Negator() {
  NegatorMaxTotalValuesVisited.updateMax(NumValuesVisitedInThisNegator);
}
#endif

// Due to the InstCombine's worklist management, there are no guarantees that
// each instruction we'll encounter has been visited by InstCombine already.
// In particular, most importantly for us, that means we have to canonicalize
// constants to RHS ourselves, since that is helpful sometimes.
std::array<Value *, 2> Negator::getSortedOperandsOfBinOp(Instruction *I) { … }

// FIXME: can this be reworked into a worklist-based algorithm while preserving
// the depth-first, early bailout traversal?
[[nodiscard]] Value *Negator::visitImpl(Value *V, bool IsNSW, unsigned Depth) { … }

[[nodiscard]] Value *Negator::negate(Value *V, bool IsNSW, unsigned Depth) { … }

[[nodiscard]] std::optional<Negator::Result> Negator::run(Value *Root,
                                                          bool IsNSW) { … }

[[nodiscard]] Value *Negator::Negate(bool LHSIsZero, bool IsNSW, Value *Root,
                                     InstCombinerImpl &IC) { … }