CorrelatedValuePropagation.cpp | Explore in Territory

//===- CorrelatedValuePropagation.cpp - Propagate CFG-derived info --------===//
//
// 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 the Correlated Value Propagation pass.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <optional>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumPhis,      "Number of phis propagated");
STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
STATISTIC(NumSelects,   "Number of selects propagated");
STATISTIC(NumCmps,      "Number of comparisons propagated");
STATISTIC(NumReturns,   "Number of return values propagated");
STATISTIC(NumDeadCases, "Number of switch cases removed");
STATISTIC(NumSDivSRemsNarrowed,
          "Number of sdivs/srems whose width was decreased");
STATISTIC(NumSDivs,     "Number of sdiv converted to udiv");
STATISTIC(NumUDivURemsNarrowed,
          "Number of udivs/urems whose width was decreased");
STATISTIC(NumAShrsConverted, "Number of ashr converted to lshr");
STATISTIC(NumAShrsRemoved, "Number of ashr removed");
STATISTIC(NumSRems,     "Number of srem converted to urem");
STATISTIC(NumSExt,      "Number of sext converted to zext");
STATISTIC(NumSIToFP,    "Number of sitofp converted to uitofp");
STATISTIC(NumSICmps,    "Number of signed icmp preds simplified to unsigned");
STATISTIC(NumAnd,       "Number of ands removed");
STATISTIC(NumNW,        "Number of no-wrap deductions");
STATISTIC(NumNSW,       "Number of no-signed-wrap deductions");
STATISTIC(NumNUW,       "Number of no-unsigned-wrap deductions");
STATISTIC(NumAddNW,     "Number of no-wrap deductions for add");
STATISTIC(NumAddNSW,    "Number of no-signed-wrap deductions for add");
STATISTIC(NumAddNUW,    "Number of no-unsigned-wrap deductions for add");
STATISTIC(NumSubNW,     "Number of no-wrap deductions for sub");
STATISTIC(NumSubNSW,    "Number of no-signed-wrap deductions for sub");
STATISTIC(NumSubNUW,    "Number of no-unsigned-wrap deductions for sub");
STATISTIC(NumMulNW,     "Number of no-wrap deductions for mul");
STATISTIC(NumMulNSW,    "Number of no-signed-wrap deductions for mul");
STATISTIC(NumMulNUW,    "Number of no-unsigned-wrap deductions for mul");
STATISTIC(NumShlNW,     "Number of no-wrap deductions for shl");
STATISTIC(NumShlNSW,    "Number of no-signed-wrap deductions for shl");
STATISTIC(NumShlNUW,    "Number of no-unsigned-wrap deductions for shl");
STATISTIC(NumAbs,       "Number of llvm.abs intrinsics removed");
STATISTIC(NumOverflows, "Number of overflow checks removed");
STATISTIC(NumSaturating,
    "Number of saturating arithmetics converted to normal arithmetics");
STATISTIC(NumNonNull, "Number of function pointer arguments marked non-null");
STATISTIC(NumCmpIntr, "Number of llvm.[us]cmp intrinsics removed");
STATISTIC(NumMinMax, "Number of llvm.[us]{min,max} intrinsics removed");
STATISTIC(NumSMinMax,
          "Number of llvm.s{min,max} intrinsics simplified to unsigned");
STATISTIC(NumUDivURemsNarrowedExpanded,
          "Number of bound udiv's/urem's expanded");
STATISTIC(NumNNeg, "Number of zext/uitofp non-negative deductions");

static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) { … }

static bool processSelect(SelectInst *S, LazyValueInfo *LVI) { … }

/// Try to simplify a phi with constant incoming values that match the edge
/// values of a non-constant value on all other edges:
/// bb0:
///   %isnull = icmp eq i8* %x, null
///   br i1 %isnull, label %bb2, label %bb1
/// bb1:
///   br label %bb2
/// bb2:
///   %r = phi i8* [ %x, %bb1 ], [ null, %bb0 ]
/// -->
///   %r = %x
static bool simplifyCommonValuePhi(PHINode *P, LazyValueInfo *LVI,
                                   DominatorTree *DT) { … }

static Value *getValueOnEdge(LazyValueInfo *LVI, Value *Incoming,
                             BasicBlock *From, BasicBlock *To,
                             Instruction *CxtI) { … }

static bool processPHI(PHINode *P, LazyValueInfo *LVI, DominatorTree *DT,
                       const SimplifyQuery &SQ) { … }

static bool processICmp(ICmpInst *Cmp, LazyValueInfo *LVI) { … }

/// See if LazyValueInfo's ability to exploit edge conditions or range
/// information is sufficient to prove this comparison. Even for local
/// conditions, this can sometimes prove conditions instcombine can't by
/// exploiting range information.
static bool constantFoldCmp(CmpInst *Cmp, LazyValueInfo *LVI) { … }

static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) { … }

/// Simplify a switch instruction by removing cases which can never fire. If the
/// uselessness of a case could be determined locally then constant propagation
/// would already have figured it out. Instead, walk the predecessors and
/// statically evaluate cases based on information available on that edge. Cases
/// that cannot fire no matter what the incoming edge can safely be removed. If
/// a case fires on every incoming edge then the entire switch can be removed
/// and replaced with a branch to the case destination.
static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI,
                          DominatorTree *DT) { … }

// See if we can prove that the given binary op intrinsic will not overflow.
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI) { … }

static void setDeducedOverflowingFlags(Value *V, Instruction::BinaryOps Opcode,
                                       bool NewNSW, bool NewNUW) { … }

static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);

// See if @llvm.abs argument is alays positive/negative, and simplify.
// Notably, INT_MIN can belong to either range, regardless of the NSW,
// because it is negation-invariant.
static bool processAbsIntrinsic(IntrinsicInst *II, LazyValueInfo *LVI) { … }

static bool processCmpIntrinsic(CmpIntrinsic *CI, LazyValueInfo *LVI) { … }

// See if this min/max intrinsic always picks it's one specific operand.
// If not, check whether we can canonicalize signed minmax into unsigned version
static bool processMinMaxIntrinsic(MinMaxIntrinsic *MM, LazyValueInfo *LVI) { … }

// Rewrite this with.overflow intrinsic as non-overflowing.
static bool processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI) { … }

static bool processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI) { … }

/// Infer nonnull attributes for the arguments at the specified callsite.
static bool processCallSite(CallBase &CB, LazyValueInfo *LVI) { … }

enum class Domain { … };

static Domain getDomain(const ConstantRange &CR) { … }

/// Try to shrink a sdiv/srem's width down to the smallest power of two that's
/// sufficient to contain its operands.
static bool narrowSDivOrSRem(BinaryOperator *Instr, const ConstantRange &LCR,
                             const ConstantRange &RCR) { … }

static bool expandUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR,
                             const ConstantRange &YCR) { … }

/// Try to shrink a udiv/urem's width down to the smallest power of two that's
/// sufficient to contain its operands.
static bool narrowUDivOrURem(BinaryOperator *Instr, const ConstantRange &XCR,
                             const ConstantRange &YCR) { … }

static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) { … }

static bool processSRem(BinaryOperator *SDI, const ConstantRange &LCR,
                        const ConstantRange &RCR, LazyValueInfo *LVI) { … }

/// See if LazyValueInfo's ability to exploit edge conditions or range
/// information is sufficient to prove the signs of both operands of this SDiv.
/// If this is the case, replace the SDiv with a UDiv. Even for local
/// conditions, this can sometimes prove conditions instcombine can't by
/// exploiting range information.
static bool processSDiv(BinaryOperator *SDI, const ConstantRange &LCR,
                        const ConstantRange &RCR, LazyValueInfo *LVI) { … }

static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) { … }

static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) { … }

static bool processSExt(SExtInst *SDI, LazyValueInfo *LVI) { … }

static bool processPossibleNonNeg(PossiblyNonNegInst *I, LazyValueInfo *LVI) { … }

static bool processZExt(ZExtInst *ZExt, LazyValueInfo *LVI) { … }

static bool processUIToFP(UIToFPInst *UIToFP, LazyValueInfo *LVI) { … }

static bool processSIToFP(SIToFPInst *SIToFP, LazyValueInfo *LVI) { … }

static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI) { … }

static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) { … }

static bool runImpl(Function &F, LazyValueInfo *LVI, DominatorTree *DT,
                    const SimplifyQuery &SQ) { … }

PreservedAnalyses
CorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) { … }
llvm/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
