brintos / llvm-project-archived public Read only

1//===- InstructionCombining.cpp - Combine multiple instructions -----------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// InstructionCombining - Combine instructions to form fewer, simple10// instructions.  This pass does not modify the CFG.  This pass is where11// algebraic simplification happens.12//13// This pass combines things like:14//    %Y = add i32 %X, 115//    %Z = add i32 %Y, 116// into:17//    %Z = add i32 %X, 218//19// This is a simple worklist driven algorithm.20//21// This pass guarantees that the following canonicalizations are performed on22// the program:23//    1. If a binary operator has a constant operand, it is moved to the RHS24//    2. Bitwise operators with constant operands are always grouped so that25//       shifts are performed first, then or's, then and's, then xor's.26//    3. Compare instructions are converted from <,>,<=,>= to ==,!= if possible27//    4. All cmp instructions on boolean values are replaced with logical ops28//    5. add X, X is represented as (X*2) => (X << 1)29//    6. Multiplies with a power-of-two constant argument are transformed into30//       shifts.31//   ... etc.32//33//===----------------------------------------------------------------------===//34 35#include "InstCombineInternal.h"36#include "llvm/ADT/APFloat.h"37#include "llvm/ADT/APInt.h"38#include "llvm/ADT/ArrayRef.h"39#include "llvm/ADT/DenseMap.h"40#include "llvm/ADT/SmallPtrSet.h"41#include "llvm/ADT/SmallVector.h"42#include "llvm/ADT/Statistic.h"43#include "llvm/Analysis/AliasAnalysis.h"44#include "llvm/Analysis/AssumptionCache.h"45#include "llvm/Analysis/BasicAliasAnalysis.h"46#include "llvm/Analysis/BlockFrequencyInfo.h"47#include "llvm/Analysis/CFG.h"48#include "llvm/Analysis/ConstantFolding.h"49#include "llvm/Analysis/GlobalsModRef.h"50#include "llvm/Analysis/InstructionSimplify.h"51#include "llvm/Analysis/LastRunTrackingAnalysis.h"52#include "llvm/Analysis/LazyBlockFrequencyInfo.h"53#include "llvm/Analysis/MemoryBuiltins.h"54#include "llvm/Analysis/OptimizationRemarkEmitter.h"55#include "llvm/Analysis/ProfileSummaryInfo.h"56#include "llvm/Analysis/TargetFolder.h"57#include "llvm/Analysis/TargetLibraryInfo.h"58#include "llvm/Analysis/TargetTransformInfo.h"59#include "llvm/Analysis/Utils/Local.h"60#include "llvm/Analysis/ValueTracking.h"61#include "llvm/Analysis/VectorUtils.h"62#include "llvm/IR/BasicBlock.h"63#include "llvm/IR/CFG.h"64#include "llvm/IR/Constant.h"65#include "llvm/IR/Constants.h"66#include "llvm/IR/DIBuilder.h"67#include "llvm/IR/DataLayout.h"68#include "llvm/IR/DebugInfo.h"69#include "llvm/IR/DerivedTypes.h"70#include "llvm/IR/Dominators.h"71#include "llvm/IR/EHPersonalities.h"72#include "llvm/IR/Function.h"73#include "llvm/IR/GetElementPtrTypeIterator.h"74#include "llvm/IR/IRBuilder.h"75#include "llvm/IR/InstrTypes.h"76#include "llvm/IR/Instruction.h"77#include "llvm/IR/Instructions.h"78#include "llvm/IR/IntrinsicInst.h"79#include "llvm/IR/Intrinsics.h"80#include "llvm/IR/Metadata.h"81#include "llvm/IR/Operator.h"82#include "llvm/IR/PassManager.h"83#include "llvm/IR/PatternMatch.h"84#include "llvm/IR/Type.h"85#include "llvm/IR/Use.h"86#include "llvm/IR/User.h"87#include "llvm/IR/Value.h"88#include "llvm/IR/ValueHandle.h"89#include "llvm/InitializePasses.h"90#include "llvm/Support/Casting.h"91#include "llvm/Support/CommandLine.h"92#include "llvm/Support/Compiler.h"93#include "llvm/Support/Debug.h"94#include "llvm/Support/DebugCounter.h"95#include "llvm/Support/ErrorHandling.h"96#include "llvm/Support/KnownBits.h"97#include "llvm/Support/KnownFPClass.h"98#include "llvm/Support/raw_ostream.h"99#include "llvm/Transforms/InstCombine/InstCombine.h"100#include "llvm/Transforms/Utils/BasicBlockUtils.h"101#include "llvm/Transforms/Utils/Local.h"102#include <algorithm>103#include <cassert>104#include <cstdint>105#include <memory>106#include <optional>107#include <string>108#include <utility>109 110#define DEBUG_TYPE "instcombine"111#include "llvm/Transforms/Utils/InstructionWorklist.h"112#include <optional>113 114using namespace llvm;115using namespace llvm::PatternMatch;116 117STATISTIC(NumWorklistIterations,118          "Number of instruction combining iterations performed");119STATISTIC(NumOneIteration, "Number of functions with one iteration");120STATISTIC(NumTwoIterations, "Number of functions with two iterations");121STATISTIC(NumThreeIterations, "Number of functions with three iterations");122STATISTIC(NumFourOrMoreIterations,123          "Number of functions with four or more iterations");124 125STATISTIC(NumCombined , "Number of insts combined");126STATISTIC(NumConstProp, "Number of constant folds");127STATISTIC(NumDeadInst , "Number of dead inst eliminated");128STATISTIC(NumSunkInst , "Number of instructions sunk");129STATISTIC(NumExpand,    "Number of expansions");130STATISTIC(NumFactor   , "Number of factorizations");131STATISTIC(NumReassoc  , "Number of reassociations");132DEBUG_COUNTER(VisitCounter, "instcombine-visit",133              "Controls which instructions are visited");134 135static cl::opt<bool> EnableCodeSinking("instcombine-code-sinking",136                                       cl::desc("Enable code sinking"),137                                       cl::init(true));138 139static cl::opt<unsigned> MaxSinkNumUsers(140    "instcombine-max-sink-users", cl::init(32),141    cl::desc("Maximum number of undroppable users for instruction sinking"));142 143static cl::opt<unsigned>144MaxArraySize("instcombine-maxarray-size", cl::init(1024),145             cl::desc("Maximum array size considered when doing a combine"));146 147namespace llvm {148extern cl::opt<bool> ProfcheckDisableMetadataFixes;149} // end namespace llvm150 151// FIXME: Remove this flag when it is no longer necessary to convert152// llvm.dbg.declare to avoid inaccurate debug info. Setting this to false153// increases variable availability at the cost of accuracy. Variables that154// cannot be promoted by mem2reg or SROA will be described as living in memory155// for their entire lifetime. However, passes like DSE and instcombine can156// delete stores to the alloca, leading to misleading and inaccurate debug157// information. This flag can be removed when those passes are fixed.158static cl::opt<unsigned> ShouldLowerDbgDeclare("instcombine-lower-dbg-declare",159                                               cl::Hidden, cl::init(true));160 161std::optional<Instruction *>162InstCombiner::targetInstCombineIntrinsic(IntrinsicInst &II) {163  // Handle target specific intrinsics164  if (II.getCalledFunction()->isTargetIntrinsic()) {165    return TTIForTargetIntrinsicsOnly.instCombineIntrinsic(*this, II);166  }167  return std::nullopt;168}169 170std::optional<Value *> InstCombiner::targetSimplifyDemandedUseBitsIntrinsic(171    IntrinsicInst &II, APInt DemandedMask, KnownBits &Known,172    bool &KnownBitsComputed) {173  // Handle target specific intrinsics174  if (II.getCalledFunction()->isTargetIntrinsic()) {175    return TTIForTargetIntrinsicsOnly.simplifyDemandedUseBitsIntrinsic(176        *this, II, DemandedMask, Known, KnownBitsComputed);177  }178  return std::nullopt;179}180 181std::optional<Value *> InstCombiner::targetSimplifyDemandedVectorEltsIntrinsic(182    IntrinsicInst &II, APInt DemandedElts, APInt &PoisonElts,183    APInt &PoisonElts2, APInt &PoisonElts3,184    std::function<void(Instruction *, unsigned, APInt, APInt &)>185        SimplifyAndSetOp) {186  // Handle target specific intrinsics187  if (II.getCalledFunction()->isTargetIntrinsic()) {188    return TTIForTargetIntrinsicsOnly.simplifyDemandedVectorEltsIntrinsic(189        *this, II, DemandedElts, PoisonElts, PoisonElts2, PoisonElts3,190        SimplifyAndSetOp);191  }192  return std::nullopt;193}194 195bool InstCombiner::isValidAddrSpaceCast(unsigned FromAS, unsigned ToAS) const {196  // Approved exception for TTI use: This queries a legality property of the197  // target, not an profitability heuristic. Ideally this should be part of198  // DataLayout instead.199  return TTIForTargetIntrinsicsOnly.isValidAddrSpaceCast(FromAS, ToAS);200}201 202Value *InstCombinerImpl::EmitGEPOffset(GEPOperator *GEP, bool RewriteGEP) {203  if (!RewriteGEP)204    return llvm::emitGEPOffset(&Builder, DL, GEP);205 206  IRBuilderBase::InsertPointGuard Guard(Builder);207  auto *Inst = dyn_cast<Instruction>(GEP);208  if (Inst)209    Builder.SetInsertPoint(Inst);210 211  Value *Offset = EmitGEPOffset(GEP);212  // Rewrite non-trivial GEPs to avoid duplicating the offset arithmetic.213  if (Inst && !GEP->hasAllConstantIndices() &&214      !GEP->getSourceElementType()->isIntegerTy(8)) {215    replaceInstUsesWith(216        *Inst, Builder.CreateGEP(Builder.getInt8Ty(), GEP->getPointerOperand(),217                                 Offset, "", GEP->getNoWrapFlags()));218    eraseInstFromFunction(*Inst);219  }220  return Offset;221}222 223Value *InstCombinerImpl::EmitGEPOffsets(ArrayRef<GEPOperator *> GEPs,224                                        GEPNoWrapFlags NW, Type *IdxTy,225                                        bool RewriteGEPs) {226  auto Add = [&](Value *Sum, Value *Offset) -> Value * {227    if (Sum)228      return Builder.CreateAdd(Sum, Offset, "", NW.hasNoUnsignedWrap(),229                               NW.isInBounds());230    else231      return Offset;232  };233 234  Value *Sum = nullptr;235  Value *OneUseSum = nullptr;236  Value *OneUseBase = nullptr;237  GEPNoWrapFlags OneUseFlags = GEPNoWrapFlags::all();238  for (GEPOperator *GEP : reverse(GEPs)) {239    Value *Offset;240    {241      // Expand the offset at the point of the previous GEP to enable rewriting.242      // However, use the original insertion point for calculating Sum.243      IRBuilderBase::InsertPointGuard Guard(Builder);244      auto *Inst = dyn_cast<Instruction>(GEP);245      if (RewriteGEPs && Inst)246        Builder.SetInsertPoint(Inst);247 248      Offset = llvm::emitGEPOffset(&Builder, DL, GEP);249      if (Offset->getType() != IdxTy)250        Offset = Builder.CreateVectorSplat(251            cast<VectorType>(IdxTy)->getElementCount(), Offset);252      if (GEP->hasOneUse()) {253        // Offsets of one-use GEPs will be merged into the next multi-use GEP.254        OneUseSum = Add(OneUseSum, Offset);255        OneUseFlags = OneUseFlags.intersectForOffsetAdd(GEP->getNoWrapFlags());256        if (!OneUseBase)257          OneUseBase = GEP->getPointerOperand();258        continue;259      }260 261      if (OneUseSum)262        Offset = Add(OneUseSum, Offset);263 264      // Rewrite the GEP to reuse the computed offset. This also includes265      // offsets from preceding one-use GEPs.266      if (RewriteGEPs && Inst &&267          !(GEP->getSourceElementType()->isIntegerTy(8) &&268            GEP->getOperand(1) == Offset)) {269        replaceInstUsesWith(270            *Inst,271            Builder.CreatePtrAdd(272                OneUseBase ? OneUseBase : GEP->getPointerOperand(), Offset, "",273                OneUseFlags.intersectForOffsetAdd(GEP->getNoWrapFlags())));274        eraseInstFromFunction(*Inst);275      }276    }277 278    Sum = Add(Sum, Offset);279    OneUseSum = OneUseBase = nullptr;280    OneUseFlags = GEPNoWrapFlags::all();281  }282  if (OneUseSum)283    Sum = Add(Sum, OneUseSum);284  if (!Sum)285    return Constant::getNullValue(IdxTy);286  return Sum;287}288 289/// Legal integers and common types are considered desirable. This is used to290/// avoid creating instructions with types that may not be supported well by the291/// the backend.292/// NOTE: This treats i8, i16 and i32 specially because they are common293///       types in frontend languages.294bool InstCombinerImpl::isDesirableIntType(unsigned BitWidth) const {295  switch (BitWidth) {296  case 8:297  case 16:298  case 32:299    return true;300  default:301    return DL.isLegalInteger(BitWidth);302  }303}304 305/// Return true if it is desirable to convert an integer computation from a306/// given bit width to a new bit width.307/// We don't want to convert from a legal or desirable type (like i8) to an308/// illegal type or from a smaller to a larger illegal type. A width of '1'309/// is always treated as a desirable type because i1 is a fundamental type in310/// IR, and there are many specialized optimizations for i1 types.311/// Common/desirable widths are equally treated as legal to convert to, in312/// order to open up more combining opportunities.313bool InstCombinerImpl::shouldChangeType(unsigned FromWidth,314                                        unsigned ToWidth) const {315  bool FromLegal = FromWidth == 1 || DL.isLegalInteger(FromWidth);316  bool ToLegal = ToWidth == 1 || DL.isLegalInteger(ToWidth);317 318  // Convert to desirable widths even if they are not legal types.319  // Only shrink types, to prevent infinite loops.320  if (ToWidth < FromWidth && isDesirableIntType(ToWidth))321    return true;322 323  // If this is a legal or desiable integer from type, and the result would be324  // an illegal type, don't do the transformation.325  if ((FromLegal || isDesirableIntType(FromWidth)) && !ToLegal)326    return false;327 328  // Otherwise, if both are illegal, do not increase the size of the result. We329  // do allow things like i160 -> i64, but not i64 -> i160.330  if (!FromLegal && !ToLegal && ToWidth > FromWidth)331    return false;332 333  return true;334}335 336/// Return true if it is desirable to convert a computation from 'From' to 'To'.337/// We don't want to convert from a legal to an illegal type or from a smaller338/// to a larger illegal type. i1 is always treated as a legal type because it is339/// a fundamental type in IR, and there are many specialized optimizations for340/// i1 types.341bool InstCombinerImpl::shouldChangeType(Type *From, Type *To) const {342  // TODO: This could be extended to allow vectors. Datalayout changes might be343  // needed to properly support that.344  if (!From->isIntegerTy() || !To->isIntegerTy())345    return false;346 347  unsigned FromWidth = From->getPrimitiveSizeInBits();348  unsigned ToWidth = To->getPrimitiveSizeInBits();349  return shouldChangeType(FromWidth, ToWidth);350}351 352// Return true, if No Signed Wrap should be maintained for I.353// The No Signed Wrap flag can be kept if the operation "B (I.getOpcode) C",354// where both B and C should be ConstantInts, results in a constant that does355// not overflow. This function only handles the Add/Sub/Mul opcodes. For356// all other opcodes, the function conservatively returns false.357static bool maintainNoSignedWrap(BinaryOperator &I, Value *B, Value *C) {358  auto *OBO = dyn_cast<OverflowingBinaryOperator>(&I);359  if (!OBO || !OBO->hasNoSignedWrap())360    return false;361 362  const APInt *BVal, *CVal;363  if (!match(B, m_APInt(BVal)) || !match(C, m_APInt(CVal)))364    return false;365 366  // We reason about Add/Sub/Mul Only.367  bool Overflow = false;368  switch (I.getOpcode()) {369  case Instruction::Add:370    (void)BVal->sadd_ov(*CVal, Overflow);371    break;372  case Instruction::Sub:373    (void)BVal->ssub_ov(*CVal, Overflow);374    break;375  case Instruction::Mul:376    (void)BVal->smul_ov(*CVal, Overflow);377    break;378  default:379    // Conservatively return false for other opcodes.380    return false;381  }382  return !Overflow;383}384 385static bool hasNoUnsignedWrap(BinaryOperator &I) {386  auto *OBO = dyn_cast<OverflowingBinaryOperator>(&I);387  return OBO && OBO->hasNoUnsignedWrap();388}389 390static bool hasNoSignedWrap(BinaryOperator &I) {391  auto *OBO = dyn_cast<OverflowingBinaryOperator>(&I);392  return OBO && OBO->hasNoSignedWrap();393}394 395/// Conservatively clears subclassOptionalData after a reassociation or396/// commutation. We preserve fast-math flags when applicable as they can be397/// preserved.398static void ClearSubclassDataAfterReassociation(BinaryOperator &I) {399  FPMathOperator *FPMO = dyn_cast<FPMathOperator>(&I);400  if (!FPMO) {401    I.clearSubclassOptionalData();402    return;403  }404 405  FastMathFlags FMF = I.getFastMathFlags();406  I.clearSubclassOptionalData();407  I.setFastMathFlags(FMF);408}409 410/// Combine constant operands of associative operations either before or after a411/// cast to eliminate one of the associative operations:412/// (op (cast (op X, C2)), C1) --> (cast (op X, op (C1, C2)))413/// (op (cast (op X, C2)), C1) --> (op (cast X), op (C1, C2))414static bool simplifyAssocCastAssoc(BinaryOperator *BinOp1,415                                   InstCombinerImpl &IC) {416  auto *Cast = dyn_cast<CastInst>(BinOp1->getOperand(0));417  if (!Cast || !Cast->hasOneUse())418    return false;419 420  // TODO: Enhance logic for other casts and remove this check.421  auto CastOpcode = Cast->getOpcode();422  if (CastOpcode != Instruction::ZExt)423    return false;424 425  // TODO: Enhance logic for other BinOps and remove this check.426  if (!BinOp1->isBitwiseLogicOp())427    return false;428 429  auto AssocOpcode = BinOp1->getOpcode();430  auto *BinOp2 = dyn_cast<BinaryOperator>(Cast->getOperand(0));431  if (!BinOp2 || !BinOp2->hasOneUse() || BinOp2->getOpcode() != AssocOpcode)432    return false;433 434  Constant *C1, *C2;435  if (!match(BinOp1->getOperand(1), m_Constant(C1)) ||436      !match(BinOp2->getOperand(1), m_Constant(C2)))437    return false;438 439  // TODO: This assumes a zext cast.440  // Eg, if it was a trunc, we'd cast C1 to the source type because casting C2441  // to the destination type might lose bits.442 443  // Fold the constants together in the destination type:444  // (op (cast (op X, C2)), C1) --> (op (cast X), FoldedC)445  const DataLayout &DL = IC.getDataLayout();446  Type *DestTy = C1->getType();447  Constant *CastC2 = ConstantFoldCastOperand(CastOpcode, C2, DestTy, DL);448  if (!CastC2)449    return false;450  Constant *FoldedC = ConstantFoldBinaryOpOperands(AssocOpcode, C1, CastC2, DL);451  if (!FoldedC)452    return false;453 454  IC.replaceOperand(*Cast, 0, BinOp2->getOperand(0));455  IC.replaceOperand(*BinOp1, 1, FoldedC);456  BinOp1->dropPoisonGeneratingFlags();457  Cast->dropPoisonGeneratingFlags();458  return true;459}460 461// Simplifies IntToPtr/PtrToInt RoundTrip Cast.462// inttoptr ( ptrtoint (x) ) --> x463Value *InstCombinerImpl::simplifyIntToPtrRoundTripCast(Value *Val) {464  auto *IntToPtr = dyn_cast<IntToPtrInst>(Val);465  if (IntToPtr && DL.getTypeSizeInBits(IntToPtr->getDestTy()) ==466                      DL.getTypeSizeInBits(IntToPtr->getSrcTy())) {467    auto *PtrToInt = dyn_cast<PtrToIntInst>(IntToPtr->getOperand(0));468    Type *CastTy = IntToPtr->getDestTy();469    if (PtrToInt &&470        CastTy->getPointerAddressSpace() ==471            PtrToInt->getSrcTy()->getPointerAddressSpace() &&472        DL.getTypeSizeInBits(PtrToInt->getSrcTy()) ==473            DL.getTypeSizeInBits(PtrToInt->getDestTy()))474      return PtrToInt->getOperand(0);475  }476  return nullptr;477}478 479/// This performs a few simplifications for operators that are associative or480/// commutative:481///482///  Commutative operators:483///484///  1. Order operands such that they are listed from right (least complex) to485///     left (most complex).  This puts constants before unary operators before486///     binary operators.487///488///  Associative operators:489///490///  2. Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies.491///  3. Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies.492///493///  Associative and commutative operators:494///495///  4. Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies.496///  5. Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies.497///  6. Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"498///     if C1 and C2 are constants.499bool InstCombinerImpl::SimplifyAssociativeOrCommutative(BinaryOperator &I) {500  Instruction::BinaryOps Opcode = I.getOpcode();501  bool Changed = false;502 503  do {504    // Order operands such that they are listed from right (least complex) to505    // left (most complex).  This puts constants before unary operators before506    // binary operators.507    if (I.isCommutative() && getComplexity(I.getOperand(0)) <508        getComplexity(I.getOperand(1)))509      Changed = !I.swapOperands();510 511    if (I.isCommutative()) {512      if (auto Pair = matchSymmetricPair(I.getOperand(0), I.getOperand(1))) {513        replaceOperand(I, 0, Pair->first);514        replaceOperand(I, 1, Pair->second);515        Changed = true;516      }517    }518 519    BinaryOperator *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));520    BinaryOperator *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));521 522    if (I.isAssociative()) {523      // Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies.524      if (Op0 && Op0->getOpcode() == Opcode) {525        Value *A = Op0->getOperand(0);526        Value *B = Op0->getOperand(1);527        Value *C = I.getOperand(1);528 529        // Does "B op C" simplify?530        if (Value *V = simplifyBinOp(Opcode, B, C, SQ.getWithInstruction(&I))) {531          // It simplifies to V.  Form "A op V".532          replaceOperand(I, 0, A);533          replaceOperand(I, 1, V);534          bool IsNUW = hasNoUnsignedWrap(I) && hasNoUnsignedWrap(*Op0);535          bool IsNSW = maintainNoSignedWrap(I, B, C) && hasNoSignedWrap(*Op0);536 537          // Conservatively clear all optional flags since they may not be538          // preserved by the reassociation. Reset nsw/nuw based on the above539          // analysis.540          ClearSubclassDataAfterReassociation(I);541 542          // Note: this is only valid because SimplifyBinOp doesn't look at543          // the operands to Op0.544          if (IsNUW)545            I.setHasNoUnsignedWrap(true);546 547          if (IsNSW)548            I.setHasNoSignedWrap(true);549 550          Changed = true;551          ++NumReassoc;552          continue;553        }554      }555 556      // Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies.557      if (Op1 && Op1->getOpcode() == Opcode) {558        Value *A = I.getOperand(0);559        Value *B = Op1->getOperand(0);560        Value *C = Op1->getOperand(1);561 562        // Does "A op B" simplify?563        if (Value *V = simplifyBinOp(Opcode, A, B, SQ.getWithInstruction(&I))) {564          // It simplifies to V.  Form "V op C".565          replaceOperand(I, 0, V);566          replaceOperand(I, 1, C);567          // Conservatively clear the optional flags, since they may not be568          // preserved by the reassociation.569          ClearSubclassDataAfterReassociation(I);570          Changed = true;571          ++NumReassoc;572          continue;573        }574      }575    }576 577    if (I.isAssociative() && I.isCommutative()) {578      if (simplifyAssocCastAssoc(&I, *this)) {579        Changed = true;580        ++NumReassoc;581        continue;582      }583 584      // Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies.585      if (Op0 && Op0->getOpcode() == Opcode) {586        Value *A = Op0->getOperand(0);587        Value *B = Op0->getOperand(1);588        Value *C = I.getOperand(1);589 590        // Does "C op A" simplify?591        if (Value *V = simplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) {592          // It simplifies to V.  Form "V op B".593          replaceOperand(I, 0, V);594          replaceOperand(I, 1, B);595          // Conservatively clear the optional flags, since they may not be596          // preserved by the reassociation.597          ClearSubclassDataAfterReassociation(I);598          Changed = true;599          ++NumReassoc;600          continue;601        }602      }603 604      // Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies.605      if (Op1 && Op1->getOpcode() == Opcode) {606        Value *A = I.getOperand(0);607        Value *B = Op1->getOperand(0);608        Value *C = Op1->getOperand(1);609 610        // Does "C op A" simplify?611        if (Value *V = simplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) {612          // It simplifies to V.  Form "B op V".613          replaceOperand(I, 0, B);614          replaceOperand(I, 1, V);615          // Conservatively clear the optional flags, since they may not be616          // preserved by the reassociation.617          ClearSubclassDataAfterReassociation(I);618          Changed = true;619          ++NumReassoc;620          continue;621        }622      }623 624      // Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"625      // if C1 and C2 are constants.626      Value *A, *B;627      Constant *C1, *C2, *CRes;628      if (Op0 && Op1 &&629          Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode &&630          match(Op0, m_OneUse(m_BinOp(m_Value(A), m_Constant(C1)))) &&631          match(Op1, m_OneUse(m_BinOp(m_Value(B), m_Constant(C2)))) &&632          (CRes = ConstantFoldBinaryOpOperands(Opcode, C1, C2, DL))) {633        bool IsNUW = hasNoUnsignedWrap(I) &&634           hasNoUnsignedWrap(*Op0) &&635           hasNoUnsignedWrap(*Op1);636         BinaryOperator *NewBO = (IsNUW && Opcode == Instruction::Add) ?637           BinaryOperator::CreateNUW(Opcode, A, B) :638           BinaryOperator::Create(Opcode, A, B);639 640         if (isa<FPMathOperator>(NewBO)) {641           FastMathFlags Flags = I.getFastMathFlags() &642                                 Op0->getFastMathFlags() &643                                 Op1->getFastMathFlags();644           NewBO->setFastMathFlags(Flags);645        }646        InsertNewInstWith(NewBO, I.getIterator());647        NewBO->takeName(Op1);648        replaceOperand(I, 0, NewBO);649        replaceOperand(I, 1, CRes);650        // Conservatively clear the optional flags, since they may not be651        // preserved by the reassociation.652        ClearSubclassDataAfterReassociation(I);653        if (IsNUW)654          I.setHasNoUnsignedWrap(true);655 656        Changed = true;657        continue;658      }659    }660 661    // No further simplifications.662    return Changed;663  } while (true);664}665 666/// Return whether "X LOp (Y ROp Z)" is always equal to667/// "(X LOp Y) ROp (X LOp Z)".668static bool leftDistributesOverRight(Instruction::BinaryOps LOp,669                                     Instruction::BinaryOps ROp) {670  // X & (Y | Z) <--> (X & Y) | (X & Z)671  // X & (Y ^ Z) <--> (X & Y) ^ (X & Z)672  if (LOp == Instruction::And)673    return ROp == Instruction::Or || ROp == Instruction::Xor;674 675  // X | (Y & Z) <--> (X | Y) & (X | Z)676  if (LOp == Instruction::Or)677    return ROp == Instruction::And;678 679  // X * (Y + Z) <--> (X * Y) + (X * Z)680  // X * (Y - Z) <--> (X * Y) - (X * Z)681  if (LOp == Instruction::Mul)682    return ROp == Instruction::Add || ROp == Instruction::Sub;683 684  return false;685}686 687/// Return whether "(X LOp Y) ROp Z" is always equal to688/// "(X ROp Z) LOp (Y ROp Z)".689static bool rightDistributesOverLeft(Instruction::BinaryOps LOp,690                                     Instruction::BinaryOps ROp) {691  if (Instruction::isCommutative(ROp))692    return leftDistributesOverRight(ROp, LOp);693 694  // (X {&|^} Y) >> Z <--> (X >> Z) {&|^} (Y >> Z) for all shifts.695  return Instruction::isBitwiseLogicOp(LOp) && Instruction::isShift(ROp);696 697  // TODO: It would be nice to handle division, aka "(X + Y)/Z = X/Z + Y/Z",698  // but this requires knowing that the addition does not overflow and other699  // such subtleties.700}701 702/// This function returns identity value for given opcode, which can be used to703/// factor patterns like (X * 2) + X ==> (X * 2) + (X * 1) ==> X * (2 + 1).704static Value *getIdentityValue(Instruction::BinaryOps Opcode, Value *V) {705  if (isa<Constant>(V))706    return nullptr;707 708  return ConstantExpr::getBinOpIdentity(Opcode, V->getType());709}710 711/// This function predicates factorization using distributive laws. By default,712/// it just returns the 'Op' inputs. But for special-cases like713/// 'add(shl(X, 5), ...)', this function will have TopOpcode == Instruction::Add714/// and Op = shl(X, 5). The 'shl' is treated as the more general 'mul X, 32' to715/// allow more factorization opportunities.716static Instruction::BinaryOps717getBinOpsForFactorization(Instruction::BinaryOps TopOpcode, BinaryOperator *Op,718                          Value *&LHS, Value *&RHS, BinaryOperator *OtherOp) {719  assert(Op && "Expected a binary operator");720  LHS = Op->getOperand(0);721  RHS = Op->getOperand(1);722  if (TopOpcode == Instruction::Add || TopOpcode == Instruction::Sub) {723    Constant *C;724    if (match(Op, m_Shl(m_Value(), m_ImmConstant(C)))) {725      // X << C --> X * (1 << C)726      RHS = ConstantFoldBinaryInstruction(727          Instruction::Shl, ConstantInt::get(Op->getType(), 1), C);728      assert(RHS && "Constant folding of immediate constants failed");729      return Instruction::Mul;730    }731    // TODO: We can add other conversions e.g. shr => div etc.732  }733  if (Instruction::isBitwiseLogicOp(TopOpcode)) {734    if (OtherOp && OtherOp->getOpcode() == Instruction::AShr &&735        match(Op, m_LShr(m_NonNegative(), m_Value()))) {736      // lshr nneg C, X --> ashr nneg C, X737      return Instruction::AShr;738    }739  }740  return Op->getOpcode();741}742 743/// This tries to simplify binary operations by factorizing out common terms744/// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").745static Value *tryFactorization(BinaryOperator &I, const SimplifyQuery &SQ,746                               InstCombiner::BuilderTy &Builder,747                               Instruction::BinaryOps InnerOpcode, Value *A,748                               Value *B, Value *C, Value *D) {749  assert(A && B && C && D && "All values must be provided");750 751  Value *V = nullptr;752  Value *RetVal = nullptr;753  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);754  Instruction::BinaryOps TopLevelOpcode = I.getOpcode();755 756  // Does "X op' Y" always equal "Y op' X"?757  bool InnerCommutative = Instruction::isCommutative(InnerOpcode);758 759  // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"?760  if (leftDistributesOverRight(InnerOpcode, TopLevelOpcode)) {761    // Does the instruction have the form "(A op' B) op (A op' D)" or, in the762    // commutative case, "(A op' B) op (C op' A)"?763    if (A == C || (InnerCommutative && A == D)) {764      if (A != C)765        std::swap(C, D);766      // Consider forming "A op' (B op D)".767      // If "B op D" simplifies then it can be formed with no cost.768      V = simplifyBinOp(TopLevelOpcode, B, D, SQ.getWithInstruction(&I));769 770      // If "B op D" doesn't simplify then only go on if one of the existing771      // operations "A op' B" and "C op' D" will be zapped as no longer used.772      if (!V && (LHS->hasOneUse() || RHS->hasOneUse()))773        V = Builder.CreateBinOp(TopLevelOpcode, B, D, RHS->getName());774      if (V)775        RetVal = Builder.CreateBinOp(InnerOpcode, A, V);776    }777  }778 779  // Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"?780  if (!RetVal && rightDistributesOverLeft(TopLevelOpcode, InnerOpcode)) {781    // Does the instruction have the form "(A op' B) op (C op' B)" or, in the782    // commutative case, "(A op' B) op (B op' D)"?783    if (B == D || (InnerCommutative && B == C)) {784      if (B != D)785        std::swap(C, D);786      // Consider forming "(A op C) op' B".787      // If "A op C" simplifies then it can be formed with no cost.788      V = simplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I));789 790      // If "A op C" doesn't simplify then only go on if one of the existing791      // operations "A op' B" and "C op' D" will be zapped as no longer used.792      if (!V && (LHS->hasOneUse() || RHS->hasOneUse()))793        V = Builder.CreateBinOp(TopLevelOpcode, A, C, LHS->getName());794      if (V)795        RetVal = Builder.CreateBinOp(InnerOpcode, V, B);796    }797  }798 799  if (!RetVal)800    return nullptr;801 802  ++NumFactor;803  RetVal->takeName(&I);804 805  // Try to add no-overflow flags to the final value.806  if (isa<BinaryOperator>(RetVal)) {807    bool HasNSW = false;808    bool HasNUW = false;809    if (isa<OverflowingBinaryOperator>(&I)) {810      HasNSW = I.hasNoSignedWrap();811      HasNUW = I.hasNoUnsignedWrap();812    }813    if (auto *LOBO = dyn_cast<OverflowingBinaryOperator>(LHS)) {814      HasNSW &= LOBO->hasNoSignedWrap();815      HasNUW &= LOBO->hasNoUnsignedWrap();816    }817 818    if (auto *ROBO = dyn_cast<OverflowingBinaryOperator>(RHS)) {819      HasNSW &= ROBO->hasNoSignedWrap();820      HasNUW &= ROBO->hasNoUnsignedWrap();821    }822 823    if (TopLevelOpcode == Instruction::Add && InnerOpcode == Instruction::Mul) {824      // We can propagate 'nsw' if we know that825      //  %Y = mul nsw i16 %X, C826      //  %Z = add nsw i16 %Y, %X827      // =>828      //  %Z = mul nsw i16 %X, C+1829      //830      // iff C+1 isn't INT_MIN831      const APInt *CInt;832      if (match(V, m_APInt(CInt)) && !CInt->isMinSignedValue())833        cast<Instruction>(RetVal)->setHasNoSignedWrap(HasNSW);834 835      // nuw can be propagated with any constant or nuw value.836      cast<Instruction>(RetVal)->setHasNoUnsignedWrap(HasNUW);837    }838  }839  return RetVal;840}841 842// If `I` has one Const operand and the other matches `(ctpop (not x))`,843// replace `(ctpop (not x))` with `(sub nuw nsw BitWidth(x), (ctpop x))`.844// This is only useful is the new subtract can fold so we only handle the845// following cases:846//    1) (add/sub/disjoint_or C, (ctpop (not x))847//        -> (add/sub/disjoint_or C', (ctpop x))848//    1) (cmp pred C, (ctpop (not x))849//        -> (cmp pred C', (ctpop x))850Instruction *InstCombinerImpl::tryFoldInstWithCtpopWithNot(Instruction *I) {851  unsigned Opc = I->getOpcode();852  unsigned ConstIdx = 1;853  switch (Opc) {854  default:855    return nullptr;856    // (ctpop (not x)) <-> (sub nuw nsw BitWidth(x) - (ctpop x))857    // We can fold the BitWidth(x) with add/sub/icmp as long the other operand858    // is constant.859  case Instruction::Sub:860    ConstIdx = 0;861    break;862  case Instruction::ICmp:863    // Signed predicates aren't correct in some edge cases like for i2 types, as864    // well since (ctpop x) is known [0, log2(BitWidth(x))] almost all signed865    // comparisons against it are simplfied to unsigned.866    if (cast<ICmpInst>(I)->isSigned())867      return nullptr;868    break;869  case Instruction::Or:870    if (!match(I, m_DisjointOr(m_Value(), m_Value())))871      return nullptr;872    [[fallthrough]];873  case Instruction::Add:874    break;875  }876 877  Value *Op;878  // Find ctpop.879  if (!match(I->getOperand(1 - ConstIdx),880             m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(Op)))))881    return nullptr;882 883  Constant *C;884  // Check other operand is ImmConstant.885  if (!match(I->getOperand(ConstIdx), m_ImmConstant(C)))886    return nullptr;887 888  Type *Ty = Op->getType();889  Constant *BitWidthC = ConstantInt::get(Ty, Ty->getScalarSizeInBits());890  // Need extra check for icmp. Note if this check is true, it generally means891  // the icmp will simplify to true/false.892  if (Opc == Instruction::ICmp && !cast<ICmpInst>(I)->isEquality()) {893    Constant *Cmp =894        ConstantFoldCompareInstOperands(ICmpInst::ICMP_UGT, C, BitWidthC, DL);895    if (!Cmp || !Cmp->isZeroValue())896      return nullptr;897  }898 899  // Check we can invert `(not x)` for free.900  bool Consumes = false;901  if (!isFreeToInvert(Op, Op->hasOneUse(), Consumes) || !Consumes)902    return nullptr;903  Value *NotOp = getFreelyInverted(Op, Op->hasOneUse(), &Builder);904  assert(NotOp != nullptr &&905         "Desync between isFreeToInvert and getFreelyInverted");906 907  Value *CtpopOfNotOp = Builder.CreateIntrinsic(Ty, Intrinsic::ctpop, NotOp);908 909  Value *R = nullptr;910 911  // Do the transformation here to avoid potentially introducing an infinite912  // loop.913  switch (Opc) {914  case Instruction::Sub:915    R = Builder.CreateAdd(CtpopOfNotOp, ConstantExpr::getSub(C, BitWidthC));916    break;917  case Instruction::Or:918  case Instruction::Add:919    R = Builder.CreateSub(ConstantExpr::getAdd(C, BitWidthC), CtpopOfNotOp);920    break;921  case Instruction::ICmp:922    R = Builder.CreateICmp(cast<ICmpInst>(I)->getSwappedPredicate(),923                           CtpopOfNotOp, ConstantExpr::getSub(BitWidthC, C));924    break;925  default:926    llvm_unreachable("Unhandled Opcode");927  }928  assert(R != nullptr);929  return replaceInstUsesWith(*I, R);930}931 932// (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C))933//   IFF934//    1) the logic_shifts match935//    2) either both binops are binops and one is `and` or936//       BinOp1 is `and`937//       (logic_shift (inv_logic_shift C1, C), C) == C1 or938//939//    -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)940//941// (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt))942//   IFF943//    1) the logic_shifts match944//    2) BinOp1 == BinOp2 (if BinOp ==  `add`, then also requires `shl`).945//946//    -> (BinOp (logic_shift (BinOp X, Y)), Mask)947//948// (Binop1 (Binop2 (arithmetic_shift X, Amt), Mask), (arithmetic_shift Y, Amt))949//   IFF950//   1) Binop1 is bitwise logical operator `and`, `or` or `xor`951//   2) Binop2 is `not`952//953//   -> (arithmetic_shift Binop1((not X), Y), Amt)954 955Instruction *InstCombinerImpl::foldBinOpShiftWithShift(BinaryOperator &I) {956  const DataLayout &DL = I.getDataLayout();957  auto IsValidBinOpc = [](unsigned Opc) {958    switch (Opc) {959    default:960      return false;961    case Instruction::And:962    case Instruction::Or:963    case Instruction::Xor:964    case Instruction::Add:965      // Skip Sub as we only match constant masks which will canonicalize to use966      // add.967      return true;968    }969  };970 971  // Check if we can distribute binop arbitrarily. `add` + `lshr` has extra972  // constraints.973  auto IsCompletelyDistributable = [](unsigned BinOpc1, unsigned BinOpc2,974                                      unsigned ShOpc) {975    assert(ShOpc != Instruction::AShr);976    return (BinOpc1 != Instruction::Add && BinOpc2 != Instruction::Add) ||977           ShOpc == Instruction::Shl;978  };979 980  auto GetInvShift = [](unsigned ShOpc) {981    assert(ShOpc != Instruction::AShr);982    return ShOpc == Instruction::LShr ? Instruction::Shl : Instruction::LShr;983  };984 985  auto CanDistributeBinops = [&](unsigned BinOpc1, unsigned BinOpc2,986                                 unsigned ShOpc, Constant *CMask,987                                 Constant *CShift) {988    // If the BinOp1 is `and` we don't need to check the mask.989    if (BinOpc1 == Instruction::And)990      return true;991 992    // For all other possible transfers we need complete distributable993    // binop/shift (anything but `add` + `lshr`).994    if (!IsCompletelyDistributable(BinOpc1, BinOpc2, ShOpc))995      return false;996 997    // If BinOp2 is `and`, any mask works (this only really helps for non-splat998    // vecs, otherwise the mask will be simplified and the following check will999    // handle it).1000    if (BinOpc2 == Instruction::And)1001      return true;1002 1003    // Otherwise, need mask that meets the below requirement.1004    // (logic_shift (inv_logic_shift Mask, ShAmt), ShAmt) == Mask1005    Constant *MaskInvShift =1006        ConstantFoldBinaryOpOperands(GetInvShift(ShOpc), CMask, CShift, DL);1007    return ConstantFoldBinaryOpOperands(ShOpc, MaskInvShift, CShift, DL) ==1008           CMask;1009  };1010 1011  auto MatchBinOp = [&](unsigned ShOpnum) -> Instruction * {1012    Constant *CMask, *CShift;1013    Value *X, *Y, *ShiftedX, *Mask, *Shift;1014    if (!match(I.getOperand(ShOpnum),1015               m_OneUse(m_Shift(m_Value(Y), m_Value(Shift)))))1016      return nullptr;1017    if (!match(I.getOperand(1 - ShOpnum),1018               m_c_BinOp(m_CombineAnd(1019                             m_OneUse(m_Shift(m_Value(X), m_Specific(Shift))),1020                             m_Value(ShiftedX)),1021                         m_Value(Mask))))1022      return nullptr;1023    // Make sure we are matching instruction shifts and not ConstantExpr1024    auto *IY = dyn_cast<Instruction>(I.getOperand(ShOpnum));1025    auto *IX = dyn_cast<Instruction>(ShiftedX);1026    if (!IY || !IX)1027      return nullptr;1028 1029    // LHS and RHS need same shift opcode1030    unsigned ShOpc = IY->getOpcode();1031    if (ShOpc != IX->getOpcode())1032      return nullptr;1033 1034    // Make sure binop is real instruction and not ConstantExpr1035    auto *BO2 = dyn_cast<Instruction>(I.getOperand(1 - ShOpnum));1036    if (!BO2)1037      return nullptr;1038 1039    unsigned BinOpc = BO2->getOpcode();1040    // Make sure we have valid binops.1041    if (!IsValidBinOpc(I.getOpcode()) || !IsValidBinOpc(BinOpc))1042      return nullptr;1043 1044    if (ShOpc == Instruction::AShr) {1045      if (Instruction::isBitwiseLogicOp(I.getOpcode()) &&1046          BinOpc == Instruction::Xor && match(Mask, m_AllOnes())) {1047        Value *NotX = Builder.CreateNot(X);1048        Value *NewBinOp = Builder.CreateBinOp(I.getOpcode(), Y, NotX);1049        return BinaryOperator::Create(1050            static_cast<Instruction::BinaryOps>(ShOpc), NewBinOp, Shift);1051      }1052 1053      return nullptr;1054    }1055 1056    // If BinOp1 == BinOp2 and it's bitwise or shl with add, then just1057    // distribute to drop the shift irrelevant of constants.1058    if (BinOpc == I.getOpcode() &&1059        IsCompletelyDistributable(I.getOpcode(), BinOpc, ShOpc)) {1060      Value *NewBinOp2 = Builder.CreateBinOp(I.getOpcode(), X, Y);1061      Value *NewBinOp1 = Builder.CreateBinOp(1062          static_cast<Instruction::BinaryOps>(ShOpc), NewBinOp2, Shift);1063      return BinaryOperator::Create(I.getOpcode(), NewBinOp1, Mask);1064    }1065 1066    // Otherwise we can only distribute by constant shifting the mask, so1067    // ensure we have constants.1068    if (!match(Shift, m_ImmConstant(CShift)))1069      return nullptr;1070    if (!match(Mask, m_ImmConstant(CMask)))1071      return nullptr;1072 1073    // Check if we can distribute the binops.1074    if (!CanDistributeBinops(I.getOpcode(), BinOpc, ShOpc, CMask, CShift))1075      return nullptr;1076 1077    Constant *NewCMask =1078        ConstantFoldBinaryOpOperands(GetInvShift(ShOpc), CMask, CShift, DL);1079    Value *NewBinOp2 = Builder.CreateBinOp(1080        static_cast<Instruction::BinaryOps>(BinOpc), X, NewCMask);1081    Value *NewBinOp1 = Builder.CreateBinOp(I.getOpcode(), Y, NewBinOp2);1082    return BinaryOperator::Create(static_cast<Instruction::BinaryOps>(ShOpc),1083                                  NewBinOp1, CShift);1084  };1085 1086  if (Instruction *R = MatchBinOp(0))1087    return R;1088  return MatchBinOp(1);1089}1090 1091// (Binop (zext C), (select C, T, F))1092//    -> (select C, (binop 1, T), (binop 0, F))1093//1094// (Binop (sext C), (select C, T, F))1095//    -> (select C, (binop -1, T), (binop 0, F))1096//1097// Attempt to simplify binary operations into a select with folded args, when1098// one operand of the binop is a select instruction and the other operand is a1099// zext/sext extension, whose value is the select condition.1100Instruction *1101InstCombinerImpl::foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I) {1102  // TODO: this simplification may be extended to any speculatable instruction,1103  // not just binops, and would possibly be handled better in FoldOpIntoSelect.1104  Instruction::BinaryOps Opc = I.getOpcode();1105  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);1106  Value *A, *CondVal, *TrueVal, *FalseVal;1107  Value *CastOp;1108 1109  auto MatchSelectAndCast = [&](Value *CastOp, Value *SelectOp) {1110    return match(CastOp, m_ZExtOrSExt(m_Value(A))) &&1111           A->getType()->getScalarSizeInBits() == 1 &&1112           match(SelectOp, m_Select(m_Value(CondVal), m_Value(TrueVal),1113                                    m_Value(FalseVal)));1114  };1115 1116  // Make sure one side of the binop is a select instruction, and the other is a1117  // zero/sign extension operating on a i1.1118  if (MatchSelectAndCast(LHS, RHS))1119    CastOp = LHS;1120  else if (MatchSelectAndCast(RHS, LHS))1121    CastOp = RHS;1122  else1123    return nullptr;1124 1125  auto NewFoldedConst = [&](bool IsTrueArm, Value *V) {1126    bool IsCastOpRHS = (CastOp == RHS);1127    bool IsZExt = isa<ZExtInst>(CastOp);1128    Constant *C;1129 1130    if (IsTrueArm) {1131      C = Constant::getNullValue(V->getType());1132    } else if (IsZExt) {1133      unsigned BitWidth = V->getType()->getScalarSizeInBits();1134      C = Constant::getIntegerValue(V->getType(), APInt(BitWidth, 1));1135    } else {1136      C = Constant::getAllOnesValue(V->getType());1137    }1138 1139    return IsCastOpRHS ? Builder.CreateBinOp(Opc, V, C)1140                       : Builder.CreateBinOp(Opc, C, V);1141  };1142 1143  // If the value used in the zext/sext is the select condition, or the negated1144  // of the select condition, the binop can be simplified.1145  if (CondVal == A) {1146    Value *NewTrueVal = NewFoldedConst(false, TrueVal);1147    return SelectInst::Create(CondVal, NewTrueVal,1148                              NewFoldedConst(true, FalseVal));1149  }1150 1151  if (match(A, m_Not(m_Specific(CondVal)))) {1152    Value *NewTrueVal = NewFoldedConst(true, TrueVal);1153    return SelectInst::Create(CondVal, NewTrueVal,1154                              NewFoldedConst(false, FalseVal));1155  }1156 1157  return nullptr;1158}1159 1160Value *InstCombinerImpl::tryFactorizationFolds(BinaryOperator &I) {1161  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);1162  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);1163  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);1164  Instruction::BinaryOps TopLevelOpcode = I.getOpcode();1165  Value *A, *B, *C, *D;1166  Instruction::BinaryOps LHSOpcode, RHSOpcode;1167 1168  if (Op0)1169    LHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op0, A, B, Op1);1170  if (Op1)1171    RHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op1, C, D, Op0);1172 1173  // The instruction has the form "(A op' B) op (C op' D)".  Try to factorize1174  // a common term.1175  if (Op0 && Op1 && LHSOpcode == RHSOpcode)1176    if (Value *V = tryFactorization(I, SQ, Builder, LHSOpcode, A, B, C, D))1177      return V;1178 1179  // The instruction has the form "(A op' B) op (C)".  Try to factorize common1180  // term.1181  if (Op0)1182    if (Value *Ident = getIdentityValue(LHSOpcode, RHS))1183      if (Value *V =1184              tryFactorization(I, SQ, Builder, LHSOpcode, A, B, RHS, Ident))1185        return V;1186 1187  // The instruction has the form "(B) op (C op' D)".  Try to factorize common1188  // term.1189  if (Op1)1190    if (Value *Ident = getIdentityValue(RHSOpcode, LHS))1191      if (Value *V =1192              tryFactorization(I, SQ, Builder, RHSOpcode, LHS, Ident, C, D))1193        return V;1194 1195  return nullptr;1196}1197 1198/// This tries to simplify binary operations which some other binary operation1199/// distributes over either by factorizing out common terms1200/// (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this results in1201/// simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is a win).1202/// Returns the simplified value, or null if it didn't simplify.1203Value *InstCombinerImpl::foldUsingDistributiveLaws(BinaryOperator &I) {1204  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);1205  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);1206  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);1207  Instruction::BinaryOps TopLevelOpcode = I.getOpcode();1208 1209  // Factorization.1210  if (Value *R = tryFactorizationFolds(I))1211    return R;1212 1213  // Expansion.1214  if (Op0 && rightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) {1215    // The instruction has the form "(A op' B) op C".  See if expanding it out1216    // to "(A op C) op' (B op C)" results in simplifications.1217    Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;1218    Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op'1219 1220    // Disable the use of undef because it's not safe to distribute undef.1221    auto SQDistributive = SQ.getWithInstruction(&I).getWithoutUndef();1222    Value *L = simplifyBinOp(TopLevelOpcode, A, C, SQDistributive);1223    Value *R = simplifyBinOp(TopLevelOpcode, B, C, SQDistributive);1224 1225    // Do "A op C" and "B op C" both simplify?1226    if (L && R) {1227      // They do! Return "L op' R".1228      ++NumExpand;1229      C = Builder.CreateBinOp(InnerOpcode, L, R);1230      C->takeName(&I);1231      return C;1232    }1233 1234    // Does "A op C" simplify to the identity value for the inner opcode?1235    if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) {1236      // They do! Return "B op C".1237      ++NumExpand;1238      C = Builder.CreateBinOp(TopLevelOpcode, B, C);1239      C->takeName(&I);1240      return C;1241    }1242 1243    // Does "B op C" simplify to the identity value for the inner opcode?1244    if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {1245      // They do! Return "A op C".1246      ++NumExpand;1247      C = Builder.CreateBinOp(TopLevelOpcode, A, C);1248      C->takeName(&I);1249      return C;1250    }1251  }1252 1253  if (Op1 && leftDistributesOverRight(TopLevelOpcode, Op1->getOpcode())) {1254    // The instruction has the form "A op (B op' C)".  See if expanding it out1255    // to "(A op B) op' (A op C)" results in simplifications.1256    Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);1257    Instruction::BinaryOps InnerOpcode = Op1->getOpcode(); // op'1258 1259    // Disable the use of undef because it's not safe to distribute undef.1260    auto SQDistributive = SQ.getWithInstruction(&I).getWithoutUndef();1261    Value *L = simplifyBinOp(TopLevelOpcode, A, B, SQDistributive);1262    Value *R = simplifyBinOp(TopLevelOpcode, A, C, SQDistributive);1263 1264    // Do "A op B" and "A op C" both simplify?1265    if (L && R) {1266      // They do! Return "L op' R".1267      ++NumExpand;1268      A = Builder.CreateBinOp(InnerOpcode, L, R);1269      A->takeName(&I);1270      return A;1271    }1272 1273    // Does "A op B" simplify to the identity value for the inner opcode?1274    if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) {1275      // They do! Return "A op C".1276      ++NumExpand;1277      A = Builder.CreateBinOp(TopLevelOpcode, A, C);1278      A->takeName(&I);1279      return A;1280    }1281 1282    // Does "A op C" simplify to the identity value for the inner opcode?1283    if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {1284      // They do! Return "A op B".1285      ++NumExpand;1286      A = Builder.CreateBinOp(TopLevelOpcode, A, B);1287      A->takeName(&I);1288      return A;1289    }1290  }1291 1292  return SimplifySelectsFeedingBinaryOp(I, LHS, RHS);1293}1294 1295static std::optional<std::pair<Value *, Value *>>1296matchSymmetricPhiNodesPair(PHINode *LHS, PHINode *RHS) {1297  if (LHS->getParent() != RHS->getParent())1298    return std::nullopt;1299 1300  if (LHS->getNumIncomingValues() < 2)1301    return std::nullopt;1302 1303  if (!equal(LHS->blocks(), RHS->blocks()))1304    return std::nullopt;1305 1306  Value *L0 = LHS->getIncomingValue(0);1307  Value *R0 = RHS->getIncomingValue(0);1308 1309  for (unsigned I = 1, E = LHS->getNumIncomingValues(); I != E; ++I) {1310    Value *L1 = LHS->getIncomingValue(I);1311    Value *R1 = RHS->getIncomingValue(I);1312 1313    if ((L0 == L1 && R0 == R1) || (L0 == R1 && R0 == L1))1314      continue;1315 1316    return std::nullopt;1317  }1318 1319  return std::optional(std::pair(L0, R0));1320}1321 1322std::optional<std::pair<Value *, Value *>>1323InstCombinerImpl::matchSymmetricPair(Value *LHS, Value *RHS) {1324  Instruction *LHSInst = dyn_cast<Instruction>(LHS);1325  Instruction *RHSInst = dyn_cast<Instruction>(RHS);1326  if (!LHSInst || !RHSInst || LHSInst->getOpcode() != RHSInst->getOpcode())1327    return std::nullopt;1328  switch (LHSInst->getOpcode()) {1329  case Instruction::PHI:1330    return matchSymmetricPhiNodesPair(cast<PHINode>(LHS), cast<PHINode>(RHS));1331  case Instruction::Select: {1332    Value *Cond = LHSInst->getOperand(0);1333    Value *TrueVal = LHSInst->getOperand(1);1334    Value *FalseVal = LHSInst->getOperand(2);1335    if (Cond == RHSInst->getOperand(0) && TrueVal == RHSInst->getOperand(2) &&1336        FalseVal == RHSInst->getOperand(1))1337      return std::pair(TrueVal, FalseVal);1338    return std::nullopt;1339  }1340  case Instruction::Call: {1341    // Match min(a, b) and max(a, b)1342    MinMaxIntrinsic *LHSMinMax = dyn_cast<MinMaxIntrinsic>(LHSInst);1343    MinMaxIntrinsic *RHSMinMax = dyn_cast<MinMaxIntrinsic>(RHSInst);1344    if (LHSMinMax && RHSMinMax &&1345        LHSMinMax->getPredicate() ==1346            ICmpInst::getSwappedPredicate(RHSMinMax->getPredicate()) &&1347        ((LHSMinMax->getLHS() == RHSMinMax->getLHS() &&1348          LHSMinMax->getRHS() == RHSMinMax->getRHS()) ||1349         (LHSMinMax->getLHS() == RHSMinMax->getRHS() &&1350          LHSMinMax->getRHS() == RHSMinMax->getLHS())))1351      return std::pair(LHSMinMax->getLHS(), LHSMinMax->getRHS());1352    return std::nullopt;1353  }1354  default:1355    return std::nullopt;1356  }1357}1358 1359Value *InstCombinerImpl::SimplifySelectsFeedingBinaryOp(BinaryOperator &I,1360                                                        Value *LHS,1361                                                        Value *RHS) {1362  Value *A, *B, *C, *D, *E, *F;1363  bool LHSIsSelect = match(LHS, m_Select(m_Value(A), m_Value(B), m_Value(C)));1364  bool RHSIsSelect = match(RHS, m_Select(m_Value(D), m_Value(E), m_Value(F)));1365  if (!LHSIsSelect && !RHSIsSelect)1366    return nullptr;1367 1368  SelectInst *SI = ProfcheckDisableMetadataFixes1369                       ? nullptr1370                       : cast<SelectInst>(LHSIsSelect ? LHS : RHS);1371 1372  FastMathFlags FMF;1373  BuilderTy::FastMathFlagGuard Guard(Builder);1374  if (isa<FPMathOperator>(&I)) {1375    FMF = I.getFastMathFlags();1376    Builder.setFastMathFlags(FMF);1377  }1378 1379  Instruction::BinaryOps Opcode = I.getOpcode();1380  SimplifyQuery Q = SQ.getWithInstruction(&I);1381 1382  Value *Cond, *True = nullptr, *False = nullptr;1383 1384  // Special-case for add/negate combination. Replace the zero in the negation1385  // with the trailing add operand:1386  // (Cond ? TVal : -N) + Z --> Cond ? True : (Z - N)1387  // (Cond ? -N : FVal) + Z --> Cond ? (Z - N) : False1388  auto foldAddNegate = [&](Value *TVal, Value *FVal, Value *Z) -> Value * {1389    // We need an 'add' and exactly 1 arm of the select to have been simplified.1390    if (Opcode != Instruction::Add || (!True && !False) || (True && False))1391      return nullptr;1392    Value *N;1393    if (True && match(FVal, m_Neg(m_Value(N)))) {1394      Value *Sub = Builder.CreateSub(Z, N);1395      return Builder.CreateSelect(Cond, True, Sub, I.getName(), SI);1396    }1397    if (False && match(TVal, m_Neg(m_Value(N)))) {1398      Value *Sub = Builder.CreateSub(Z, N);1399      return Builder.CreateSelect(Cond, Sub, False, I.getName(), SI);1400    }1401    return nullptr;1402  };1403 1404  if (LHSIsSelect && RHSIsSelect && A == D) {1405    // (A ? B : C) op (A ? E : F) -> A ? (B op E) : (C op F)1406    Cond = A;1407    True = simplifyBinOp(Opcode, B, E, FMF, Q);1408    False = simplifyBinOp(Opcode, C, F, FMF, Q);1409 1410    if (LHS->hasOneUse() && RHS->hasOneUse()) {1411      if (False && !True)1412        True = Builder.CreateBinOp(Opcode, B, E);1413      else if (True && !False)1414        False = Builder.CreateBinOp(Opcode, C, F);1415    }1416  } else if (LHSIsSelect && LHS->hasOneUse()) {1417    // (A ? B : C) op Y -> A ? (B op Y) : (C op Y)1418    Cond = A;1419    True = simplifyBinOp(Opcode, B, RHS, FMF, Q);1420    False = simplifyBinOp(Opcode, C, RHS, FMF, Q);1421    if (Value *NewSel = foldAddNegate(B, C, RHS))1422      return NewSel;1423  } else if (RHSIsSelect && RHS->hasOneUse()) {1424    // X op (D ? E : F) -> D ? (X op E) : (X op F)1425    Cond = D;1426    True = simplifyBinOp(Opcode, LHS, E, FMF, Q);1427    False = simplifyBinOp(Opcode, LHS, F, FMF, Q);1428    if (Value *NewSel = foldAddNegate(E, F, LHS))1429      return NewSel;1430  }1431 1432  if (!True || !False)1433    return nullptr;1434 1435  Value *NewSI = Builder.CreateSelect(Cond, True, False, I.getName(), SI);1436  NewSI->takeName(&I);1437  return NewSI;1438}1439 1440/// Freely adapt every user of V as-if V was changed to !V.1441/// WARNING: only if canFreelyInvertAllUsersOf() said this can be done.1442void InstCombinerImpl::freelyInvertAllUsersOf(Value *I, Value *IgnoredUser) {1443  assert(!isa<Constant>(I) && "Shouldn't invert users of constant");1444  for (User *U : make_early_inc_range(I->users())) {1445    if (U == IgnoredUser)1446      continue; // Don't consider this user.1447    switch (cast<Instruction>(U)->getOpcode()) {1448    case Instruction::Select: {1449      auto *SI = cast<SelectInst>(U);1450      SI->swapValues();1451      SI->swapProfMetadata();1452      break;1453    }1454    case Instruction::Br: {1455      BranchInst *BI = cast<BranchInst>(U);1456      BI->swapSuccessors(); // swaps prof metadata too1457      if (BPI)1458        BPI->swapSuccEdgesProbabilities(BI->getParent());1459      break;1460    }1461    case Instruction::Xor:1462      replaceInstUsesWith(cast<Instruction>(*U), I);1463      // Add to worklist for DCE.1464      addToWorklist(cast<Instruction>(U));1465      break;1466    default:1467      llvm_unreachable("Got unexpected user - out of sync with "1468                       "canFreelyInvertAllUsersOf() ?");1469    }1470  }1471 1472  // Update pre-existing debug value uses.1473  SmallVector<DbgVariableRecord *, 4> DbgVariableRecords;1474  llvm::findDbgValues(I, DbgVariableRecords);1475 1476  for (DbgVariableRecord *DbgVal : DbgVariableRecords) {1477    SmallVector<uint64_t, 1> Ops = {dwarf::DW_OP_not};1478    for (unsigned Idx = 0, End = DbgVal->getNumVariableLocationOps();1479         Idx != End; ++Idx)1480      if (DbgVal->getVariableLocationOp(Idx) == I)1481        DbgVal->setExpression(1482            DIExpression::appendOpsToArg(DbgVal->getExpression(), Ops, Idx));1483  }1484}1485 1486/// Given a 'sub' instruction, return the RHS of the instruction if the LHS is a1487/// constant zero (which is the 'negate' form).1488Value *InstCombinerImpl::dyn_castNegVal(Value *V) const {1489  Value *NegV;1490  if (match(V, m_Neg(m_Value(NegV))))1491    return NegV;1492 1493  // Constants can be considered to be negated values if they can be folded.1494  if (ConstantInt *C = dyn_cast<ConstantInt>(V))1495    return ConstantExpr::getNeg(C);1496 1497  if (ConstantDataVector *C = dyn_cast<ConstantDataVector>(V))1498    if (C->getType()->getElementType()->isIntegerTy())1499      return ConstantExpr::getNeg(C);1500 1501  if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) {1502    for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {1503      Constant *Elt = CV->getAggregateElement(i);1504      if (!Elt)1505        return nullptr;1506 1507      if (isa<UndefValue>(Elt))1508        continue;1509 1510      if (!isa<ConstantInt>(Elt))1511        return nullptr;1512    }1513    return ConstantExpr::getNeg(CV);1514  }1515 1516  // Negate integer vector splats.1517  if (auto *CV = dyn_cast<Constant>(V))1518    if (CV->getType()->isVectorTy() &&1519        CV->getType()->getScalarType()->isIntegerTy() && CV->getSplatValue())1520      return ConstantExpr::getNeg(CV);1521 1522  return nullptr;1523}1524 1525// Try to fold:1526//    1) (fp_binop ({s|u}itofp x), ({s|u}itofp y))1527//        -> ({s|u}itofp (int_binop x, y))1528//    2) (fp_binop ({s|u}itofp x), FpC)1529//        -> ({s|u}itofp (int_binop x, (fpto{s|u}i FpC)))1530//1531// Assuming the sign of the cast for x/y is `OpsFromSigned`.1532Instruction *InstCombinerImpl::foldFBinOpOfIntCastsFromSign(1533    BinaryOperator &BO, bool OpsFromSigned, std::array<Value *, 2> IntOps,1534    Constant *Op1FpC, SmallVectorImpl<WithCache<const Value *>> &OpsKnown) {1535 1536  Type *FPTy = BO.getType();1537  Type *IntTy = IntOps[0]->getType();1538 1539  unsigned IntSz = IntTy->getScalarSizeInBits();1540  // This is the maximum number of inuse bits by the integer where the int -> fp1541  // casts are exact.1542  unsigned MaxRepresentableBits =1543      APFloat::semanticsPrecision(FPTy->getScalarType()->getFltSemantics());1544 1545  // Preserve known number of leading bits. This can allow us to trivial nsw/nuw1546  // checks later on.1547  unsigned NumUsedLeadingBits[2] = {IntSz, IntSz};1548 1549  // NB: This only comes up if OpsFromSigned is true, so there is no need to1550  // cache if between calls to `foldFBinOpOfIntCastsFromSign`.1551  auto IsNonZero = [&](unsigned OpNo) -> bool {1552    if (OpsKnown[OpNo].hasKnownBits() &&1553        OpsKnown[OpNo].getKnownBits(SQ).isNonZero())1554      return true;1555    return isKnownNonZero(IntOps[OpNo], SQ);1556  };1557 1558  auto IsNonNeg = [&](unsigned OpNo) -> bool {1559    // NB: This matches the impl in ValueTracking, we just try to use cached1560    // knownbits here. If we ever start supporting WithCache for1561    // `isKnownNonNegative`, change this to an explicit call.1562    return OpsKnown[OpNo].getKnownBits(SQ).isNonNegative();1563  };1564 1565  // Check if we know for certain that ({s|u}itofp op) is exact.1566  auto IsValidPromotion = [&](unsigned OpNo) -> bool {1567    // Can we treat this operand as the desired sign?1568    if (OpsFromSigned != isa<SIToFPInst>(BO.getOperand(OpNo)) &&1569        !IsNonNeg(OpNo))1570      return false;1571 1572    // If fp precision >= bitwidth(op) then its exact.1573    // NB: This is slightly conservative for `sitofp`. For signed conversion, we1574    // can handle `MaxRepresentableBits == IntSz - 1` as the sign bit will be1575    // handled specially. We can't, however, increase the bound arbitrarily for1576    // `sitofp` as for larger sizes, it won't sign extend.1577    if (MaxRepresentableBits < IntSz) {1578      // Otherwise if its signed cast check that fp precisions >= bitwidth(op) -1579      // numSignBits(op).1580      // TODO: If we add support for `WithCache` in `ComputeNumSignBits`, change1581      // `IntOps[OpNo]` arguments to `KnownOps[OpNo]`.1582      if (OpsFromSigned)1583        NumUsedLeadingBits[OpNo] = IntSz - ComputeNumSignBits(IntOps[OpNo]);1584      // Finally for unsigned check that fp precision >= bitwidth(op) -1585      // numLeadingZeros(op).1586      else {1587        NumUsedLeadingBits[OpNo] =1588            IntSz - OpsKnown[OpNo].getKnownBits(SQ).countMinLeadingZeros();1589      }1590    }1591    // NB: We could also check if op is known to be a power of 2 or zero (which1592    // will always be representable). Its unlikely, however, that is we are1593    // unable to bound op in any way we will be able to pass the overflow checks1594    // later on.1595 1596    if (MaxRepresentableBits < NumUsedLeadingBits[OpNo])1597      return false;1598    // Signed + Mul also requires that op is non-zero to avoid -0 cases.1599    return !OpsFromSigned || BO.getOpcode() != Instruction::FMul ||1600           IsNonZero(OpNo);1601  };1602 1603  // If we have a constant rhs, see if we can losslessly convert it to an int.1604  if (Op1FpC != nullptr) {1605    // Signed + Mul req non-zero1606    if (OpsFromSigned && BO.getOpcode() == Instruction::FMul &&1607        !match(Op1FpC, m_NonZeroFP()))1608      return nullptr;1609 1610    Constant *Op1IntC = ConstantFoldCastOperand(1611        OpsFromSigned ? Instruction::FPToSI : Instruction::FPToUI, Op1FpC,1612        IntTy, DL);1613    if (Op1IntC == nullptr)1614      return nullptr;1615    if (ConstantFoldCastOperand(OpsFromSigned ? Instruction::SIToFP1616                                              : Instruction::UIToFP,1617                                Op1IntC, FPTy, DL) != Op1FpC)1618      return nullptr;1619 1620    // First try to keep sign of cast the same.1621    IntOps[1] = Op1IntC;1622  }1623 1624  // Ensure lhs/rhs integer types match.1625  if (IntTy != IntOps[1]->getType())1626    return nullptr;1627 1628  if (Op1FpC == nullptr) {1629    if (!IsValidPromotion(1))1630      return nullptr;1631  }1632  if (!IsValidPromotion(0))1633    return nullptr;1634 1635  // Final we check if the integer version of the binop will not overflow.1636  BinaryOperator::BinaryOps IntOpc;1637  // Because of the precision check, we can often rule out overflows.1638  bool NeedsOverflowCheck = true;1639  // Try to conservatively rule out overflow based on the already done precision1640  // checks.1641  unsigned OverflowMaxOutputBits = OpsFromSigned ? 2 : 1;1642  unsigned OverflowMaxCurBits =1643      std::max(NumUsedLeadingBits[0], NumUsedLeadingBits[1]);1644  bool OutputSigned = OpsFromSigned;1645  switch (BO.getOpcode()) {1646  case Instruction::FAdd:1647    IntOpc = Instruction::Add;1648    OverflowMaxOutputBits += OverflowMaxCurBits;1649    break;1650  case Instruction::FSub:1651    IntOpc = Instruction::Sub;1652    OverflowMaxOutputBits += OverflowMaxCurBits;1653    break;1654  case Instruction::FMul:1655    IntOpc = Instruction::Mul;1656    OverflowMaxOutputBits += OverflowMaxCurBits * 2;1657    break;1658  default:1659    llvm_unreachable("Unsupported binop");1660  }1661  // The precision check may have already ruled out overflow.1662  if (OverflowMaxOutputBits < IntSz) {1663    NeedsOverflowCheck = false;1664    // We can bound unsigned overflow from sub to in range signed value (this is1665    // what allows us to avoid the overflow check for sub).1666    if (IntOpc == Instruction::Sub)1667      OutputSigned = true;1668  }1669 1670  // Precision check did not rule out overflow, so need to check.1671  // TODO: If we add support for `WithCache` in `willNotOverflow`, change1672  // `IntOps[...]` arguments to `KnownOps[...]`.1673  if (NeedsOverflowCheck &&1674      !willNotOverflow(IntOpc, IntOps[0], IntOps[1], BO, OutputSigned))1675    return nullptr;1676 1677  Value *IntBinOp = Builder.CreateBinOp(IntOpc, IntOps[0], IntOps[1]);1678  if (auto *IntBO = dyn_cast<BinaryOperator>(IntBinOp)) {1679    IntBO->setHasNoSignedWrap(OutputSigned);1680    IntBO->setHasNoUnsignedWrap(!OutputSigned);1681  }1682  if (OutputSigned)1683    return new SIToFPInst(IntBinOp, FPTy);1684  return new UIToFPInst(IntBinOp, FPTy);1685}1686 1687// Try to fold:1688//    1) (fp_binop ({s|u}itofp x), ({s|u}itofp y))1689//        -> ({s|u}itofp (int_binop x, y))1690//    2) (fp_binop ({s|u}itofp x), FpC)1691//        -> ({s|u}itofp (int_binop x, (fpto{s|u}i FpC)))1692Instruction *InstCombinerImpl::foldFBinOpOfIntCasts(BinaryOperator &BO) {1693  // Don't perform the fold on vectors, as the integer operation may be much1694  // more expensive than the float operation in that case.1695  if (BO.getType()->isVectorTy())1696    return nullptr;1697 1698  std::array<Value *, 2> IntOps = {nullptr, nullptr};1699  Constant *Op1FpC = nullptr;1700  // Check for:1701  //    1) (binop ({s|u}itofp x), ({s|u}itofp y))1702  //    2) (binop ({s|u}itofp x), FpC)1703  if (!match(BO.getOperand(0), m_SIToFP(m_Value(IntOps[0]))) &&1704      !match(BO.getOperand(0), m_UIToFP(m_Value(IntOps[0]))))1705    return nullptr;1706 1707  if (!match(BO.getOperand(1), m_Constant(Op1FpC)) &&1708      !match(BO.getOperand(1), m_SIToFP(m_Value(IntOps[1]))) &&1709      !match(BO.getOperand(1), m_UIToFP(m_Value(IntOps[1]))))1710    return nullptr;1711 1712  // Cache KnownBits a bit to potentially save some analysis.1713  SmallVector<WithCache<const Value *>, 2> OpsKnown = {IntOps[0], IntOps[1]};1714 1715  // Try treating x/y as coming from both `uitofp` and `sitofp`. There are1716  // different constraints depending on the sign of the cast.1717  // NB: `(uitofp nneg X)` == `(sitofp nneg X)`.1718  if (Instruction *R = foldFBinOpOfIntCastsFromSign(BO, /*OpsFromSigned=*/false,1719                                                    IntOps, Op1FpC, OpsKnown))1720    return R;1721  return foldFBinOpOfIntCastsFromSign(BO, /*OpsFromSigned=*/true, IntOps,1722                                      Op1FpC, OpsKnown);1723}1724 1725/// A binop with a constant operand and a sign-extended boolean operand may be1726/// converted into a select of constants by applying the binary operation to1727/// the constant with the two possible values of the extended boolean (0 or -1).1728Instruction *InstCombinerImpl::foldBinopOfSextBoolToSelect(BinaryOperator &BO) {1729  // TODO: Handle non-commutative binop (constant is operand 0).1730  // TODO: Handle zext.1731  // TODO: Peek through 'not' of cast.1732  Value *BO0 = BO.getOperand(0);1733  Value *BO1 = BO.getOperand(1);1734  Value *X;1735  Constant *C;1736  if (!match(BO0, m_SExt(m_Value(X))) || !match(BO1, m_ImmConstant(C)) ||1737      !X->getType()->isIntOrIntVectorTy(1))1738    return nullptr;1739 1740  // bo (sext i1 X), C --> select X, (bo -1, C), (bo 0, C)1741  Constant *Ones = ConstantInt::getAllOnesValue(BO.getType());1742  Constant *Zero = ConstantInt::getNullValue(BO.getType());1743  Value *TVal = Builder.CreateBinOp(BO.getOpcode(), Ones, C);1744  Value *FVal = Builder.CreateBinOp(BO.getOpcode(), Zero, C);1745  return createSelectInstWithUnknownProfile(X, TVal, FVal);1746}1747 1748static Value *simplifyOperationIntoSelectOperand(Instruction &I, SelectInst *SI,1749                                                 bool IsTrueArm) {1750  SmallVector<Value *> Ops;1751  for (Value *Op : I.operands()) {1752    Value *V = nullptr;1753    if (Op == SI) {1754      V = IsTrueArm ? SI->getTrueValue() : SI->getFalseValue();1755    } else if (match(SI->getCondition(),1756                     m_SpecificICmp(IsTrueArm ? ICmpInst::ICMP_EQ1757                                              : ICmpInst::ICMP_NE,1758                                    m_Specific(Op), m_Value(V))) &&1759               isGuaranteedNotToBeUndefOrPoison(V)) {1760      // Pass1761    } else if (match(Op, m_ZExt(m_Specific(SI->getCondition())))) {1762      V = IsTrueArm ? ConstantInt::get(Op->getType(), 1)1763                    : ConstantInt::getNullValue(Op->getType());1764    } else {1765      V = Op;1766    }1767    Ops.push_back(V);1768  }1769 1770  return simplifyInstructionWithOperands(&I, Ops, I.getDataLayout());1771}1772 1773static Value *foldOperationIntoSelectOperand(Instruction &I, SelectInst *SI,1774                                             Value *NewOp, InstCombiner &IC) {1775  Instruction *Clone = I.clone();1776  Clone->replaceUsesOfWith(SI, NewOp);1777  Clone->dropUBImplyingAttrsAndMetadata();1778  IC.InsertNewInstBefore(Clone, I.getIterator());1779  return Clone;1780}1781 1782Instruction *InstCombinerImpl::FoldOpIntoSelect(Instruction &Op, SelectInst *SI,1783                                                bool FoldWithMultiUse,1784                                                bool SimplifyBothArms) {1785  // Don't modify shared select instructions unless set FoldWithMultiUse1786  if (!SI->hasOneUse() && !FoldWithMultiUse)1787    return nullptr;1788 1789  Value *TV = SI->getTrueValue();1790  Value *FV = SI->getFalseValue();1791 1792  // Bool selects with constant operands can be folded to logical ops.1793  if (SI->getType()->isIntOrIntVectorTy(1))1794    return nullptr;1795 1796  // Avoid breaking min/max reduction pattern,1797  // which is necessary for vectorization later.1798  if (isa<MinMaxIntrinsic>(&Op))1799    for (Value *IntrinOp : Op.operands())1800      if (auto *PN = dyn_cast<PHINode>(IntrinOp))1801        for (Value *PhiOp : PN->operands())1802          if (PhiOp == &Op)1803            return nullptr;1804 1805  // Test if a FCmpInst instruction is used exclusively by a select as1806  // part of a minimum or maximum operation. If so, refrain from doing1807  // any other folding. This helps out other analyses which understand1808  // non-obfuscated minimum and maximum idioms. And in this case, at1809  // least one of the comparison operands has at least one user besides1810  // the compare (the select), which would often largely negate the1811  // benefit of folding anyway.1812  if (auto *CI = dyn_cast<FCmpInst>(SI->getCondition())) {1813    if (CI->hasOneUse()) {1814      Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);1815      if (((TV == Op0 && FV == Op1) || (FV == Op0 && TV == Op1)) &&1816          !CI->isCommutative())1817        return nullptr;1818    }1819  }1820 1821  // Make sure that one of the select arms folds successfully.1822  Value *NewTV = simplifyOperationIntoSelectOperand(Op, SI, /*IsTrueArm=*/true);1823  Value *NewFV =1824      simplifyOperationIntoSelectOperand(Op, SI, /*IsTrueArm=*/false);1825  if (!NewTV && !NewFV)1826    return nullptr;1827 1828  if (SimplifyBothArms && !(NewTV && NewFV))1829    return nullptr;1830 1831  // Create an instruction for the arm that did not fold.1832  if (!NewTV)1833    NewTV = foldOperationIntoSelectOperand(Op, SI, TV, *this);1834  if (!NewFV)1835    NewFV = foldOperationIntoSelectOperand(Op, SI, FV, *this);1836  return SelectInst::Create(SI->getCondition(), NewTV, NewFV, "", nullptr, SI);1837}1838 1839static Value *simplifyInstructionWithPHI(Instruction &I, PHINode *PN,1840                                         Value *InValue, BasicBlock *InBB,1841                                         const DataLayout &DL,1842                                         const SimplifyQuery SQ) {1843  // NB: It is a precondition of this transform that the operands be1844  // phi translatable!1845  SmallVector<Value *> Ops;1846  for (Value *Op : I.operands()) {1847    if (Op == PN)1848      Ops.push_back(InValue);1849    else1850      Ops.push_back(Op->DoPHITranslation(PN->getParent(), InBB));1851  }1852 1853  // Don't consider the simplification successful if we get back a constant1854  // expression. That's just an instruction in hiding.1855  // Also reject the case where we simplify back to the phi node. We wouldn't1856  // be able to remove it in that case.1857  Value *NewVal = simplifyInstructionWithOperands(1858      &I, Ops, SQ.getWithInstruction(InBB->getTerminator()));1859  if (NewVal && NewVal != PN && !match(NewVal, m_ConstantExpr()))1860    return NewVal;1861 1862  // Check if incoming PHI value can be replaced with constant1863  // based on implied condition.1864  BranchInst *TerminatorBI = dyn_cast<BranchInst>(InBB->getTerminator());1865  const ICmpInst *ICmp = dyn_cast<ICmpInst>(&I);1866  if (TerminatorBI && TerminatorBI->isConditional() &&1867      TerminatorBI->getSuccessor(0) != TerminatorBI->getSuccessor(1) && ICmp) {1868    bool LHSIsTrue = TerminatorBI->getSuccessor(0) == PN->getParent();1869    std::optional<bool> ImpliedCond = isImpliedCondition(1870        TerminatorBI->getCondition(), ICmp->getCmpPredicate(), Ops[0], Ops[1],1871        DL, LHSIsTrue);1872    if (ImpliedCond)1873      return ConstantInt::getBool(I.getType(), ImpliedCond.value());1874  }1875 1876  return nullptr;1877}1878 1879Instruction *InstCombinerImpl::foldOpIntoPhi(Instruction &I, PHINode *PN,1880                                             bool AllowMultipleUses) {1881  unsigned NumPHIValues = PN->getNumIncomingValues();1882  if (NumPHIValues == 0)1883    return nullptr;1884 1885  // We normally only transform phis with a single use.  However, if a PHI has1886  // multiple uses and they are all the same operation, we can fold *all* of the1887  // uses into the PHI.1888  bool OneUse = PN->hasOneUse();1889  bool IdenticalUsers = false;1890  if (!AllowMultipleUses && !OneUse) {1891    // Walk the use list for the instruction, comparing them to I.1892    for (User *U : PN->users()) {1893      Instruction *UI = cast<Instruction>(U);1894      if (UI != &I && !I.isIdenticalTo(UI))1895        return nullptr;1896    }1897    // Otherwise, we can replace *all* users with the new PHI we form.1898    IdenticalUsers = true;1899  }1900 1901  // Check that all operands are phi-translatable.1902  for (Value *Op : I.operands()) {1903    if (Op == PN)1904      continue;1905 1906    // Non-instructions never require phi-translation.1907    auto *I = dyn_cast<Instruction>(Op);1908    if (!I)1909      continue;1910 1911    // Phi-translate can handle phi nodes in the same block.1912    if (isa<PHINode>(I))1913      if (I->getParent() == PN->getParent())1914        continue;1915 1916    // Operand dominates the block, no phi-translation necessary.1917    if (DT.dominates(I, PN->getParent()))1918      continue;1919 1920    // Not phi-translatable, bail out.1921    return nullptr;1922  }1923 1924  // Check to see whether the instruction can be folded into each phi operand.1925  // If there is one operand that does not fold, remember the BB it is in.1926  SmallVector<Value *> NewPhiValues;1927  SmallVector<unsigned int> OpsToMoveUseToIncomingBB;1928  bool SeenNonSimplifiedInVal = false;1929  for (unsigned i = 0; i != NumPHIValues; ++i) {1930    Value *InVal = PN->getIncomingValue(i);1931    BasicBlock *InBB = PN->getIncomingBlock(i);1932 1933    if (auto *NewVal = simplifyInstructionWithPHI(I, PN, InVal, InBB, DL, SQ)) {1934      NewPhiValues.push_back(NewVal);1935      continue;1936    }1937 1938    // Handle some cases that can't be fully simplified, but where we know that1939    // the two instructions will fold into one.1940    auto WillFold = [&]() {1941      if (!InVal->hasUseList() || !InVal->hasOneUser())1942        return false;1943 1944      // icmp of ucmp/scmp with constant will fold to icmp.1945      const APInt *Ignored;1946      if (isa<CmpIntrinsic>(InVal) &&1947          match(&I, m_ICmp(m_Specific(PN), m_APInt(Ignored))))1948        return true;1949 1950      // icmp eq zext(bool), 0 will fold to !bool.1951      if (isa<ZExtInst>(InVal) &&1952          cast<ZExtInst>(InVal)->getSrcTy()->isIntOrIntVectorTy(1) &&1953          match(&I,1954                m_SpecificICmp(ICmpInst::ICMP_EQ, m_Specific(PN), m_Zero())))1955        return true;1956 1957      return false;1958    };1959 1960    if (WillFold()) {1961      OpsToMoveUseToIncomingBB.push_back(i);1962      NewPhiValues.push_back(nullptr);1963      continue;1964    }1965 1966    if (!OneUse && !IdenticalUsers)1967      return nullptr;1968 1969    if (SeenNonSimplifiedInVal)1970      return nullptr; // More than one non-simplified value.1971    SeenNonSimplifiedInVal = true;1972 1973    // If there is exactly one non-simplified value, we can insert a copy of the1974    // operation in that block.  However, if this is a critical edge, we would1975    // be inserting the computation on some other paths (e.g. inside a loop).1976    // Only do this if the pred block is unconditionally branching into the phi1977    // block. Also, make sure that the pred block is not dead code.1978    BranchInst *BI = dyn_cast<BranchInst>(InBB->getTerminator());1979    if (!BI || !BI->isUnconditional() || !DT.isReachableFromEntry(InBB))1980      return nullptr;1981 1982    NewPhiValues.push_back(nullptr);1983    OpsToMoveUseToIncomingBB.push_back(i);1984 1985    // Do not push the operation across a loop backedge. This could result in1986    // an infinite combine loop, and is generally non-profitable (especially1987    // if the operation was originally outside the loop).1988    if (isBackEdge(InBB, PN->getParent()))1989      return nullptr;1990  }1991 1992  // Clone the instruction that uses the phi node and move it into the incoming1993  // BB because we know that the next iteration of InstCombine will simplify it.1994  SmallDenseMap<BasicBlock *, Instruction *> Clones;1995  for (auto OpIndex : OpsToMoveUseToIncomingBB) {1996    Value *Op = PN->getIncomingValue(OpIndex);1997    BasicBlock *OpBB = PN->getIncomingBlock(OpIndex);1998 1999    Instruction *Clone = Clones.lookup(OpBB);2000    if (!Clone) {2001      Clone = I.clone();2002      for (Use &U : Clone->operands()) {2003        if (U == PN)2004          U = Op;2005        else2006          U = U->DoPHITranslation(PN->getParent(), OpBB);2007      }2008      Clone = InsertNewInstBefore(Clone, OpBB->getTerminator()->getIterator());2009      Clones.insert({OpBB, Clone});2010      // We may have speculated the instruction.2011      Clone->dropUBImplyingAttrsAndMetadata();2012    }2013 2014    NewPhiValues[OpIndex] = Clone;2015  }2016 2017  // Okay, we can do the transformation: create the new PHI node.2018  PHINode *NewPN = PHINode::Create(I.getType(), PN->getNumIncomingValues());2019  InsertNewInstBefore(NewPN, PN->getIterator());2020  NewPN->takeName(PN);2021  NewPN->setDebugLoc(PN->getDebugLoc());2022 2023  for (unsigned i = 0; i != NumPHIValues; ++i)2024    NewPN->addIncoming(NewPhiValues[i], PN->getIncomingBlock(i));2025 2026  if (IdenticalUsers) {2027    // Collect and deduplicate users up-front to avoid iterator invalidation.2028    SmallSetVector<Instruction *, 4> ToReplace;2029    for (User *U : PN->users()) {2030      Instruction *User = cast<Instruction>(U);2031      if (User == &I)2032        continue;2033      ToReplace.insert(User);2034    }2035    for (Instruction *I : ToReplace) {2036      replaceInstUsesWith(*I, NewPN);2037      eraseInstFromFunction(*I);2038    }2039    OneUse = true;2040  }2041 2042  if (OneUse) {2043    replaceAllDbgUsesWith(*PN, *NewPN, *PN, DT);2044  }2045  return replaceInstUsesWith(I, NewPN);2046}2047 2048Instruction *InstCombinerImpl::foldBinopWithRecurrence(BinaryOperator &BO) {2049  if (!BO.isAssociative())2050    return nullptr;2051 2052  // Find the interleaved binary ops.2053  auto Opc = BO.getOpcode();2054  auto *BO0 = dyn_cast<BinaryOperator>(BO.getOperand(0));2055  auto *BO1 = dyn_cast<BinaryOperator>(BO.getOperand(1));2056  if (!BO0 || !BO1 || !BO0->hasNUses(2) || !BO1->hasNUses(2) ||2057      BO0->getOpcode() != Opc || BO1->getOpcode() != Opc ||2058      !BO0->isAssociative() || !BO1->isAssociative() ||2059      BO0->getParent() != BO1->getParent())2060    return nullptr;2061 2062  assert(BO.isCommutative() && BO0->isCommutative() && BO1->isCommutative() &&2063         "Expected commutative instructions!");2064 2065  // Find the matching phis, forming the recurrences.2066  PHINode *PN0, *PN1;2067  Value *Start0, *Step0, *Start1, *Step1;2068  if (!matchSimpleRecurrence(BO0, PN0, Start0, Step0) || !PN0->hasOneUse() ||2069      !matchSimpleRecurrence(BO1, PN1, Start1, Step1) || !PN1->hasOneUse() ||2070      PN0->getParent() != PN1->getParent())2071    return nullptr;2072 2073  assert(PN0->getNumIncomingValues() == 2 && PN1->getNumIncomingValues() == 2 &&2074         "Expected PHIs with two incoming values!");2075 2076  // Convert the start and step values to constants.2077  auto *Init0 = dyn_cast<Constant>(Start0);2078  auto *Init1 = dyn_cast<Constant>(Start1);2079  auto *C0 = dyn_cast<Constant>(Step0);2080  auto *C1 = dyn_cast<Constant>(Step1);2081  if (!Init0 || !Init1 || !C0 || !C1)2082    return nullptr;2083 2084  // Fold the recurrence constants.2085  auto *Init = ConstantFoldBinaryInstruction(Opc, Init0, Init1);2086  auto *C = ConstantFoldBinaryInstruction(Opc, C0, C1);2087  if (!Init || !C)2088    return nullptr;2089 2090  // Create the reduced PHI.2091  auto *NewPN = PHINode::Create(PN0->getType(), PN0->getNumIncomingValues(),2092                                "reduced.phi");2093 2094  // Create the new binary op.2095  auto *NewBO = BinaryOperator::Create(Opc, NewPN, C);2096  if (Opc == Instruction::FAdd || Opc == Instruction::FMul) {2097    // Intersect FMF flags for FADD and FMUL.2098    FastMathFlags Intersect = BO0->getFastMathFlags() &2099                              BO1->getFastMathFlags() & BO.getFastMathFlags();2100    NewBO->setFastMathFlags(Intersect);2101  } else {2102    OverflowTracking Flags;2103    Flags.AllKnownNonNegative = false;2104    Flags.AllKnownNonZero = false;2105    Flags.mergeFlags(*BO0);2106    Flags.mergeFlags(*BO1);2107    Flags.mergeFlags(BO);2108    Flags.applyFlags(*NewBO);2109  }2110  NewBO->takeName(&BO);2111 2112  for (unsigned I = 0, E = PN0->getNumIncomingValues(); I != E; ++I) {2113    auto *V = PN0->getIncomingValue(I);2114    auto *BB = PN0->getIncomingBlock(I);2115    if (V == Init0) {2116      assert(((PN1->getIncomingValue(0) == Init1 &&2117               PN1->getIncomingBlock(0) == BB) ||2118              (PN1->getIncomingValue(1) == Init1 &&2119               PN1->getIncomingBlock(1) == BB)) &&2120             "Invalid incoming block!");2121      NewPN->addIncoming(Init, BB);2122    } else if (V == BO0) {2123      assert(((PN1->getIncomingValue(0) == BO1 &&2124               PN1->getIncomingBlock(0) == BB) ||2125              (PN1->getIncomingValue(1) == BO1 &&2126               PN1->getIncomingBlock(1) == BB)) &&2127             "Invalid incoming block!");2128      NewPN->addIncoming(NewBO, BB);2129    } else2130      llvm_unreachable("Unexpected incoming value!");2131  }2132 2133  LLVM_DEBUG(dbgs() << "  Combined " << *PN0 << "\n           " << *BO02134                    << "\n      with " << *PN1 << "\n           " << *BO12135                    << '\n');2136 2137  // Insert the new recurrence and remove the old (dead) ones.2138  InsertNewInstWith(NewPN, PN0->getIterator());2139  InsertNewInstWith(NewBO, BO0->getIterator());2140 2141  eraseInstFromFunction(2142      *replaceInstUsesWith(*BO0, PoisonValue::get(BO0->getType())));2143  eraseInstFromFunction(2144      *replaceInstUsesWith(*BO1, PoisonValue::get(BO1->getType())));2145  eraseInstFromFunction(*PN0);2146  eraseInstFromFunction(*PN1);2147 2148  return replaceInstUsesWith(BO, NewBO);2149}2150 2151Instruction *InstCombinerImpl::foldBinopWithPhiOperands(BinaryOperator &BO) {2152  // Attempt to fold binary operators whose operands are simple recurrences.2153  if (auto *NewBO = foldBinopWithRecurrence(BO))2154    return NewBO;2155 2156  // TODO: This should be similar to the incoming values check in foldOpIntoPhi:2157  //       we are guarding against replicating the binop in >1 predecessor.2158  //       This could miss matching a phi with 2 constant incoming values.2159  auto *Phi0 = dyn_cast<PHINode>(BO.getOperand(0));2160  auto *Phi1 = dyn_cast<PHINode>(BO.getOperand(1));2161  if (!Phi0 || !Phi1 || !Phi0->hasOneUse() || !Phi1->hasOneUse() ||2162      Phi0->getNumOperands() != Phi1->getNumOperands())2163    return nullptr;2164 2165  // TODO: Remove the restriction for binop being in the same block as the phis.2166  if (BO.getParent() != Phi0->getParent() ||2167      BO.getParent() != Phi1->getParent())2168    return nullptr;2169 2170  // Fold if there is at least one specific constant value in phi0 or phi1's2171  // incoming values that comes from the same block and this specific constant2172  // value can be used to do optimization for specific binary operator.2173  // For example:2174  // %phi0 = phi i32 [0, %bb0], [%i, %bb1]2175  // %phi1 = phi i32 [%j, %bb0], [0, %bb1]2176  // %add = add i32 %phi0, %phi12177  // ==>2178  // %add = phi i32 [%j, %bb0], [%i, %bb1]2179  Constant *C = ConstantExpr::getBinOpIdentity(BO.getOpcode(), BO.getType(),2180                                               /*AllowRHSConstant*/ false);2181  if (C) {2182    SmallVector<Value *, 4> NewIncomingValues;2183    auto CanFoldIncomingValuePair = [&](std::tuple<Use &, Use &> T) {2184      auto &Phi0Use = std::get<0>(T);2185      auto &Phi1Use = std::get<1>(T);2186      if (Phi0->getIncomingBlock(Phi0Use) != Phi1->getIncomingBlock(Phi1Use))2187        return false;2188      Value *Phi0UseV = Phi0Use.get();2189      Value *Phi1UseV = Phi1Use.get();2190      if (Phi0UseV == C)2191        NewIncomingValues.push_back(Phi1UseV);2192      else if (Phi1UseV == C)2193        NewIncomingValues.push_back(Phi0UseV);2194      else2195        return false;2196      return true;2197    };2198 2199    if (all_of(zip(Phi0->operands(), Phi1->operands()),2200               CanFoldIncomingValuePair)) {2201      PHINode *NewPhi =2202          PHINode::Create(Phi0->getType(), Phi0->getNumOperands());2203      assert(NewIncomingValues.size() == Phi0->getNumOperands() &&2204             "The number of collected incoming values should equal the number "2205             "of the original PHINode operands!");2206      for (unsigned I = 0; I < Phi0->getNumOperands(); I++)2207        NewPhi->addIncoming(NewIncomingValues[I], Phi0->getIncomingBlock(I));2208      return NewPhi;2209    }2210  }2211 2212  if (Phi0->getNumOperands() != 2 || Phi1->getNumOperands() != 2)2213    return nullptr;2214 2215  // Match a pair of incoming constants for one of the predecessor blocks.2216  BasicBlock *ConstBB, *OtherBB;2217  Constant *C0, *C1;2218  if (match(Phi0->getIncomingValue(0), m_ImmConstant(C0))) {2219    ConstBB = Phi0->getIncomingBlock(0);2220    OtherBB = Phi0->getIncomingBlock(1);2221  } else if (match(Phi0->getIncomingValue(1), m_ImmConstant(C0))) {2222    ConstBB = Phi0->getIncomingBlock(1);2223    OtherBB = Phi0->getIncomingBlock(0);2224  } else {2225    return nullptr;2226  }2227  if (!match(Phi1->getIncomingValueForBlock(ConstBB), m_ImmConstant(C1)))2228    return nullptr;2229 2230  // The block that we are hoisting to must reach here unconditionally.2231  // Otherwise, we could be speculatively executing an expensive or2232  // non-speculative op.2233  auto *PredBlockBranch = dyn_cast<BranchInst>(OtherBB->getTerminator());2234  if (!PredBlockBranch || PredBlockBranch->isConditional() ||2235      !DT.isReachableFromEntry(OtherBB))2236    return nullptr;2237 2238  // TODO: This check could be tightened to only apply to binops (div/rem) that2239  //       are not safe to speculatively execute. But that could allow hoisting2240  //       potentially expensive instructions (fdiv for example).2241  for (auto BBIter = BO.getParent()->begin(); &*BBIter != &BO; ++BBIter)2242    if (!isGuaranteedToTransferExecutionToSuccessor(&*BBIter))2243      return nullptr;2244 2245  // Fold constants for the predecessor block with constant incoming values.2246  Constant *NewC = ConstantFoldBinaryOpOperands(BO.getOpcode(), C0, C1, DL);2247  if (!NewC)2248    return nullptr;2249 2250  // Make a new binop in the predecessor block with the non-constant incoming2251  // values.2252  Builder.SetInsertPoint(PredBlockBranch);2253  Value *NewBO = Builder.CreateBinOp(BO.getOpcode(),2254                                     Phi0->getIncomingValueForBlock(OtherBB),2255                                     Phi1->getIncomingValueForBlock(OtherBB));2256  if (auto *NotFoldedNewBO = dyn_cast<BinaryOperator>(NewBO))2257    NotFoldedNewBO->copyIRFlags(&BO);2258 2259  // Replace the binop with a phi of the new values. The old phis are dead.2260  PHINode *NewPhi = PHINode::Create(BO.getType(), 2);2261  NewPhi->addIncoming(NewBO, OtherBB);2262  NewPhi->addIncoming(NewC, ConstBB);2263  return NewPhi;2264}2265 2266Instruction *InstCombinerImpl::foldBinOpIntoSelectOrPhi(BinaryOperator &I) {2267  bool IsOtherParamConst = isa<Constant>(I.getOperand(1));2268 2269  if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) {2270    if (Instruction *NewSel =2271            FoldOpIntoSelect(I, Sel, false, !IsOtherParamConst))2272      return NewSel;2273  } else if (auto *PN = dyn_cast<PHINode>(I.getOperand(0))) {2274    if (Instruction *NewPhi = foldOpIntoPhi(I, PN))2275      return NewPhi;2276  }2277  return nullptr;2278}2279 2280static bool shouldMergeGEPs(GEPOperator &GEP, GEPOperator &Src) {2281  // If this GEP has only 0 indices, it is the same pointer as2282  // Src. If Src is not a trivial GEP too, don't combine2283  // the indices.2284  if (GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() &&2285      !Src.hasOneUse())2286    return false;2287  return true;2288}2289 2290/// Find a constant NewC that has property:2291///   shuffle(NewC, ShMask) = C2292/// Returns nullptr if such a constant does not exist e.g. ShMask=<0,0> C=<1,2>2293///2294/// A 1-to-1 mapping is not required. Example:2295/// ShMask = <1,1,2,2> and C = <5,5,6,6> --> NewC = <poison,5,6,poison>2296Constant *InstCombinerImpl::unshuffleConstant(ArrayRef<int> ShMask, Constant *C,2297                                              VectorType *NewCTy) {2298  if (isa<ScalableVectorType>(NewCTy)) {2299    Constant *Splat = C->getSplatValue();2300    if (!Splat)2301      return nullptr;2302    return ConstantVector::getSplat(NewCTy->getElementCount(), Splat);2303  }2304 2305  if (cast<FixedVectorType>(NewCTy)->getNumElements() >2306      cast<FixedVectorType>(C->getType())->getNumElements())2307    return nullptr;2308 2309  unsigned NewCNumElts = cast<FixedVectorType>(NewCTy)->getNumElements();2310  PoisonValue *PoisonScalar = PoisonValue::get(C->getType()->getScalarType());2311  SmallVector<Constant *, 16> NewVecC(NewCNumElts, PoisonScalar);2312  unsigned NumElts = cast<FixedVectorType>(C->getType())->getNumElements();2313  for (unsigned I = 0; I < NumElts; ++I) {2314    Constant *CElt = C->getAggregateElement(I);2315    if (ShMask[I] >= 0) {2316      assert(ShMask[I] < (int)NumElts && "Not expecting narrowing shuffle");2317      Constant *NewCElt = NewVecC[ShMask[I]];2318      // Bail out if:2319      // 1. The constant vector contains a constant expression.2320      // 2. The shuffle needs an element of the constant vector that can't2321      //    be mapped to a new constant vector.2322      // 3. This is a widening shuffle that copies elements of V1 into the2323      //    extended elements (extending with poison is allowed).2324      if (!CElt || (!isa<PoisonValue>(NewCElt) && NewCElt != CElt) ||2325          I >= NewCNumElts)2326        return nullptr;2327      NewVecC[ShMask[I]] = CElt;2328    }2329  }2330  return ConstantVector::get(NewVecC);2331}2332 2333// Get the result of `Vector Op Splat` (or Splat Op Vector if \p SplatLHS).2334static Constant *constantFoldBinOpWithSplat(unsigned Opcode, Constant *Vector,2335                                            Constant *Splat, bool SplatLHS,2336                                            const DataLayout &DL) {2337  ElementCount EC = cast<VectorType>(Vector->getType())->getElementCount();2338  Constant *LHS = ConstantVector::getSplat(EC, Splat);2339  Constant *RHS = Vector;2340  if (!SplatLHS)2341    std::swap(LHS, RHS);2342  return ConstantFoldBinaryOpOperands(Opcode, LHS, RHS, DL);2343}2344 2345Instruction *InstCombinerImpl::foldVectorBinop(BinaryOperator &Inst) {2346  if (!isa<VectorType>(Inst.getType()))2347    return nullptr;2348 2349  BinaryOperator::BinaryOps Opcode = Inst.getOpcode();2350  Value *LHS = Inst.getOperand(0), *RHS = Inst.getOperand(1);2351  assert(cast<VectorType>(LHS->getType())->getElementCount() ==2352         cast<VectorType>(Inst.getType())->getElementCount());2353  assert(cast<VectorType>(RHS->getType())->getElementCount() ==2354         cast<VectorType>(Inst.getType())->getElementCount());2355 2356  auto foldConstantsThroughSubVectorInsertSplat =2357      [&](Value *MaybeSubVector, Value *MaybeSplat,2358          bool SplatLHS) -> Instruction * {2359    Value *Idx;2360    Constant *Splat, *SubVector, *Dest;2361    if (!match(MaybeSplat, m_ConstantSplat(m_Constant(Splat))) ||2362        !match(MaybeSubVector,2363               m_VectorInsert(m_Constant(Dest), m_Constant(SubVector),2364                              m_Value(Idx))))2365      return nullptr;2366    SubVector =2367        constantFoldBinOpWithSplat(Opcode, SubVector, Splat, SplatLHS, DL);2368    Dest = constantFoldBinOpWithSplat(Opcode, Dest, Splat, SplatLHS, DL);2369    if (!SubVector || !Dest)2370      return nullptr;2371    auto *InsertVector =2372        Builder.CreateInsertVector(Dest->getType(), Dest, SubVector, Idx);2373    return replaceInstUsesWith(Inst, InsertVector);2374  };2375 2376  // If one operand is a constant splat and the other operand is a2377  // `vector.insert` where both the destination and subvector are constant,2378  // apply the operation to both the destination and subvector, returning a new2379  // constant `vector.insert`. This helps constant folding for scalable vectors.2380  if (Instruction *Folded = foldConstantsThroughSubVectorInsertSplat(2381          /*MaybeSubVector=*/LHS, /*MaybeSplat=*/RHS, /*SplatLHS=*/false))2382    return Folded;2383  if (Instruction *Folded = foldConstantsThroughSubVectorInsertSplat(2384          /*MaybeSubVector=*/RHS, /*MaybeSplat=*/LHS, /*SplatLHS=*/true))2385    return Folded;2386 2387  // If both operands of the binop are vector concatenations, then perform the2388  // narrow binop on each pair of the source operands followed by concatenation2389  // of the results.2390  Value *L0, *L1, *R0, *R1;2391  ArrayRef<int> Mask;2392  if (match(LHS, m_Shuffle(m_Value(L0), m_Value(L1), m_Mask(Mask))) &&2393      match(RHS, m_Shuffle(m_Value(R0), m_Value(R1), m_SpecificMask(Mask))) &&2394      LHS->hasOneUse() && RHS->hasOneUse() &&2395      cast<ShuffleVectorInst>(LHS)->isConcat() &&2396      cast<ShuffleVectorInst>(RHS)->isConcat()) {2397    // This transform does not have the speculative execution constraint as2398    // below because the shuffle is a concatenation. The new binops are2399    // operating on exactly the same elements as the existing binop.2400    // TODO: We could ease the mask requirement to allow different undef lanes,2401    //       but that requires an analysis of the binop-with-undef output value.2402    Value *NewBO0 = Builder.CreateBinOp(Opcode, L0, R0);2403    if (auto *BO = dyn_cast<BinaryOperator>(NewBO0))2404      BO->copyIRFlags(&Inst);2405    Value *NewBO1 = Builder.CreateBinOp(Opcode, L1, R1);2406    if (auto *BO = dyn_cast<BinaryOperator>(NewBO1))2407      BO->copyIRFlags(&Inst);2408    return new ShuffleVectorInst(NewBO0, NewBO1, Mask);2409  }2410 2411  auto createBinOpReverse = [&](Value *X, Value *Y) {2412    Value *V = Builder.CreateBinOp(Opcode, X, Y, Inst.getName());2413    if (auto *BO = dyn_cast<BinaryOperator>(V))2414      BO->copyIRFlags(&Inst);2415    Module *M = Inst.getModule();2416    Function *F = Intrinsic::getOrInsertDeclaration(2417        M, Intrinsic::vector_reverse, V->getType());2418    return CallInst::Create(F, V);2419  };2420 2421  // NOTE: Reverse shuffles don't require the speculative execution protection2422  // below because they don't affect which lanes take part in the computation.2423 2424  Value *V1, *V2;2425  if (match(LHS, m_VecReverse(m_Value(V1)))) {2426    // Op(rev(V1), rev(V2)) -> rev(Op(V1, V2))2427    if (match(RHS, m_VecReverse(m_Value(V2))) &&2428        (LHS->hasOneUse() || RHS->hasOneUse() ||2429         (LHS == RHS && LHS->hasNUses(2))))2430      return createBinOpReverse(V1, V2);2431 2432    // Op(rev(V1), RHSSplat)) -> rev(Op(V1, RHSSplat))2433    if (LHS->hasOneUse() && isSplatValue(RHS))2434      return createBinOpReverse(V1, RHS);2435  }2436  // Op(LHSSplat, rev(V2)) -> rev(Op(LHSSplat, V2))2437  else if (isSplatValue(LHS) && match(RHS, m_OneUse(m_VecReverse(m_Value(V2)))))2438    return createBinOpReverse(LHS, V2);2439 2440  auto createBinOpVPReverse = [&](Value *X, Value *Y, Value *EVL) {2441    Value *V = Builder.CreateBinOp(Opcode, X, Y, Inst.getName());2442    if (auto *BO = dyn_cast<BinaryOperator>(V))2443      BO->copyIRFlags(&Inst);2444 2445    ElementCount EC = cast<VectorType>(V->getType())->getElementCount();2446    Value *AllTrueMask = Builder.CreateVectorSplat(EC, Builder.getTrue());2447    Module *M = Inst.getModule();2448    Function *F = Intrinsic::getOrInsertDeclaration(2449        M, Intrinsic::experimental_vp_reverse, V->getType());2450    return CallInst::Create(F, {V, AllTrueMask, EVL});2451  };2452 2453  Value *EVL;2454  if (match(LHS, m_Intrinsic<Intrinsic::experimental_vp_reverse>(2455                     m_Value(V1), m_AllOnes(), m_Value(EVL)))) {2456    // Op(rev(V1), rev(V2)) -> rev(Op(V1, V2))2457    if (match(RHS, m_Intrinsic<Intrinsic::experimental_vp_reverse>(2458                       m_Value(V2), m_AllOnes(), m_Specific(EVL))) &&2459        (LHS->hasOneUse() || RHS->hasOneUse() ||2460         (LHS == RHS && LHS->hasNUses(2))))2461      return createBinOpVPReverse(V1, V2, EVL);2462 2463    // Op(rev(V1), RHSSplat)) -> rev(Op(V1, RHSSplat))2464    if (LHS->hasOneUse() && isSplatValue(RHS))2465      return createBinOpVPReverse(V1, RHS, EVL);2466  }2467  // Op(LHSSplat, rev(V2)) -> rev(Op(LHSSplat, V2))2468  else if (isSplatValue(LHS) &&2469           match(RHS, m_Intrinsic<Intrinsic::experimental_vp_reverse>(2470                          m_Value(V2), m_AllOnes(), m_Value(EVL))))2471    return createBinOpVPReverse(LHS, V2, EVL);2472 2473  // It may not be safe to reorder shuffles and things like div, urem, etc.2474  // because we may trap when executing those ops on unknown vector elements.2475  // See PR20059.2476  if (!isSafeToSpeculativelyExecuteWithVariableReplaced(&Inst))2477    return nullptr;2478 2479  auto createBinOpShuffle = [&](Value *X, Value *Y, ArrayRef<int> M) {2480    Value *XY = Builder.CreateBinOp(Opcode, X, Y);2481    if (auto *BO = dyn_cast<BinaryOperator>(XY))2482      BO->copyIRFlags(&Inst);2483    return new ShuffleVectorInst(XY, M);2484  };2485 2486  // If both arguments of the binary operation are shuffles that use the same2487  // mask and shuffle within a single vector, move the shuffle after the binop.2488  if (match(LHS, m_Shuffle(m_Value(V1), m_Poison(), m_Mask(Mask))) &&2489      match(RHS, m_Shuffle(m_Value(V2), m_Poison(), m_SpecificMask(Mask))) &&2490      V1->getType() == V2->getType() &&2491      (LHS->hasOneUse() || RHS->hasOneUse() || LHS == RHS)) {2492    // Op(shuffle(V1, Mask), shuffle(V2, Mask)) -> shuffle(Op(V1, V2), Mask)2493    return createBinOpShuffle(V1, V2, Mask);2494  }2495 2496  // If both arguments of a commutative binop are select-shuffles that use the2497  // same mask with commuted operands, the shuffles are unnecessary.2498  if (Inst.isCommutative() &&2499      match(LHS, m_Shuffle(m_Value(V1), m_Value(V2), m_Mask(Mask))) &&2500      match(RHS,2501            m_Shuffle(m_Specific(V2), m_Specific(V1), m_SpecificMask(Mask)))) {2502    auto *LShuf = cast<ShuffleVectorInst>(LHS);2503    auto *RShuf = cast<ShuffleVectorInst>(RHS);2504    // TODO: Allow shuffles that contain undefs in the mask?2505    //       That is legal, but it reduces undef knowledge.2506    // TODO: Allow arbitrary shuffles by shuffling after binop?2507    //       That might be legal, but we have to deal with poison.2508    if (LShuf->isSelect() &&2509        !is_contained(LShuf->getShuffleMask(), PoisonMaskElem) &&2510        RShuf->isSelect() &&2511        !is_contained(RShuf->getShuffleMask(), PoisonMaskElem)) {2512      // Example:2513      // LHS = shuffle V1, V2, <0, 5, 6, 3>2514      // RHS = shuffle V2, V1, <0, 5, 6, 3>2515      // LHS + RHS --> (V10+V20, V21+V11, V22+V12, V13+V23) --> V1 + V22516      Instruction *NewBO = BinaryOperator::Create(Opcode, V1, V2);2517      NewBO->copyIRFlags(&Inst);2518      return NewBO;2519    }2520  }2521 2522  // If one argument is a shuffle within one vector and the other is a constant,2523  // try moving the shuffle after the binary operation. This canonicalization2524  // intends to move shuffles closer to other shuffles and binops closer to2525  // other binops, so they can be folded. It may also enable demanded elements2526  // transforms.2527  Constant *C;2528  if (match(&Inst, m_c_BinOp(m_OneUse(m_Shuffle(m_Value(V1), m_Poison(),2529                                                m_Mask(Mask))),2530                             m_ImmConstant(C)))) {2531    assert(Inst.getType()->getScalarType() == V1->getType()->getScalarType() &&2532           "Shuffle should not change scalar type");2533 2534    bool ConstOp1 = isa<Constant>(RHS);2535    if (Constant *NewC =2536            unshuffleConstant(Mask, C, cast<VectorType>(V1->getType()))) {2537      // For fixed vectors, lanes of NewC not used by the shuffle will be poison2538      // which will cause UB for div/rem. Mask them with a safe constant.2539      if (isa<FixedVectorType>(V1->getType()) && Inst.isIntDivRem())2540        NewC = getSafeVectorConstantForBinop(Opcode, NewC, ConstOp1);2541 2542      // Op(shuffle(V1, Mask), C) -> shuffle(Op(V1, NewC), Mask)2543      // Op(C, shuffle(V1, Mask)) -> shuffle(Op(NewC, V1), Mask)2544      Value *NewLHS = ConstOp1 ? V1 : NewC;2545      Value *NewRHS = ConstOp1 ? NewC : V1;2546      return createBinOpShuffle(NewLHS, NewRHS, Mask);2547    }2548  }2549 2550  // Try to reassociate to sink a splat shuffle after a binary operation.2551  if (Inst.isAssociative() && Inst.isCommutative()) {2552    // Canonicalize shuffle operand as LHS.2553    if (isa<ShuffleVectorInst>(RHS))2554      std::swap(LHS, RHS);2555 2556    Value *X;2557    ArrayRef<int> MaskC;2558    int SplatIndex;2559    Value *Y, *OtherOp;2560    if (!match(LHS,2561               m_OneUse(m_Shuffle(m_Value(X), m_Undef(), m_Mask(MaskC)))) ||2562        !match(MaskC, m_SplatOrPoisonMask(SplatIndex)) ||2563        X->getType() != Inst.getType() ||2564        !match(RHS, m_OneUse(m_BinOp(Opcode, m_Value(Y), m_Value(OtherOp)))))2565      return nullptr;2566 2567    // FIXME: This may not be safe if the analysis allows undef elements. By2568    //        moving 'Y' before the splat shuffle, we are implicitly assuming2569    //        that it is not undef/poison at the splat index.2570    if (isSplatValue(OtherOp, SplatIndex)) {2571      std::swap(Y, OtherOp);2572    } else if (!isSplatValue(Y, SplatIndex)) {2573      return nullptr;2574    }2575 2576    // X and Y are splatted values, so perform the binary operation on those2577    // values followed by a splat followed by the 2nd binary operation:2578    // bo (splat X), (bo Y, OtherOp) --> bo (splat (bo X, Y)), OtherOp2579    Value *NewBO = Builder.CreateBinOp(Opcode, X, Y);2580    SmallVector<int, 8> NewMask(MaskC.size(), SplatIndex);2581    Value *NewSplat = Builder.CreateShuffleVector(NewBO, NewMask);2582    Instruction *R = BinaryOperator::Create(Opcode, NewSplat, OtherOp);2583 2584    // Intersect FMF on both new binops. Other (poison-generating) flags are2585    // dropped to be safe.2586    if (isa<FPMathOperator>(R)) {2587      R->copyFastMathFlags(&Inst);2588      R->andIRFlags(RHS);2589    }2590    if (auto *NewInstBO = dyn_cast<BinaryOperator>(NewBO))2591      NewInstBO->copyIRFlags(R);2592    return R;2593  }2594 2595  return nullptr;2596}2597 2598/// Try to narrow the width of a binop if at least 1 operand is an extend of2599/// of a value. This requires a potentially expensive known bits check to make2600/// sure the narrow op does not overflow.2601Instruction *InstCombinerImpl::narrowMathIfNoOverflow(BinaryOperator &BO) {2602  // We need at least one extended operand.2603  Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1);2604 2605  // If this is a sub, we swap the operands since we always want an extension2606  // on the RHS. The LHS can be an extension or a constant.2607  if (BO.getOpcode() == Instruction::Sub)2608    std::swap(Op0, Op1);2609 2610  Value *X;2611  bool IsSext = match(Op0, m_SExt(m_Value(X)));2612  if (!IsSext && !match(Op0, m_ZExt(m_Value(X))))2613    return nullptr;2614 2615  // If both operands are the same extension from the same source type and we2616  // can eliminate at least one (hasOneUse), this might work.2617  CastInst::CastOps CastOpc = IsSext ? Instruction::SExt : Instruction::ZExt;2618  Value *Y;2619  if (!(match(Op1, m_ZExtOrSExt(m_Value(Y))) && X->getType() == Y->getType() &&2620        cast<Operator>(Op1)->getOpcode() == CastOpc &&2621        (Op0->hasOneUse() || Op1->hasOneUse()))) {2622    // If that did not match, see if we have a suitable constant operand.2623    // Truncating and extending must produce the same constant.2624    Constant *WideC;2625    if (!Op0->hasOneUse() || !match(Op1, m_Constant(WideC)))2626      return nullptr;2627    Constant *NarrowC = getLosslessInvCast(WideC, X->getType(), CastOpc, DL);2628    if (!NarrowC)2629      return nullptr;2630    Y = NarrowC;2631  }2632 2633  // Swap back now that we found our operands.2634  if (BO.getOpcode() == Instruction::Sub)2635    std::swap(X, Y);2636 2637  // Both operands have narrow versions. Last step: the math must not overflow2638  // in the narrow width.2639  if (!willNotOverflow(BO.getOpcode(), X, Y, BO, IsSext))2640    return nullptr;2641 2642  // bo (ext X), (ext Y) --> ext (bo X, Y)2643  // bo (ext X), C       --> ext (bo X, C')2644  Value *NarrowBO = Builder.CreateBinOp(BO.getOpcode(), X, Y, "narrow");2645  if (auto *NewBinOp = dyn_cast<BinaryOperator>(NarrowBO)) {2646    if (IsSext)2647      NewBinOp->setHasNoSignedWrap();2648    else2649      NewBinOp->setHasNoUnsignedWrap();2650  }2651  return CastInst::Create(CastOpc, NarrowBO, BO.getType());2652}2653 2654/// Determine nowrap flags for (gep (gep p, x), y) to (gep p, (x + y))2655/// transform.2656static GEPNoWrapFlags getMergedGEPNoWrapFlags(GEPOperator &GEP1,2657                                              GEPOperator &GEP2) {2658  return GEP1.getNoWrapFlags().intersectForOffsetAdd(GEP2.getNoWrapFlags());2659}2660 2661/// Thread a GEP operation with constant indices through the constant true/false2662/// arms of a select.2663static Instruction *foldSelectGEP(GetElementPtrInst &GEP,2664                                  InstCombiner::BuilderTy &Builder) {2665  if (!GEP.hasAllConstantIndices())2666    return nullptr;2667 2668  Instruction *Sel;2669  Value *Cond;2670  Constant *TrueC, *FalseC;2671  if (!match(GEP.getPointerOperand(), m_Instruction(Sel)) ||2672      !match(Sel,2673             m_Select(m_Value(Cond), m_Constant(TrueC), m_Constant(FalseC))))2674    return nullptr;2675 2676  // gep (select Cond, TrueC, FalseC), IndexC --> select Cond, TrueC', FalseC'2677  // Propagate 'inbounds' and metadata from existing instructions.2678  // Note: using IRBuilder to create the constants for efficiency.2679  SmallVector<Value *, 4> IndexC(GEP.indices());2680  GEPNoWrapFlags NW = GEP.getNoWrapFlags();2681  Type *Ty = GEP.getSourceElementType();2682  Value *NewTrueC = Builder.CreateGEP(Ty, TrueC, IndexC, "", NW);2683  Value *NewFalseC = Builder.CreateGEP(Ty, FalseC, IndexC, "", NW);2684  return SelectInst::Create(Cond, NewTrueC, NewFalseC, "", nullptr, Sel);2685}2686 2687// Canonicalization:2688// gep T, (gep i8, base, C1), (Index + C2) into2689// gep T, (gep i8, base, C1 + C2 * sizeof(T)), Index2690static Instruction *canonicalizeGEPOfConstGEPI8(GetElementPtrInst &GEP,2691                                                GEPOperator *Src,2692                                                InstCombinerImpl &IC) {2693  if (GEP.getNumIndices() != 1)2694    return nullptr;2695  auto &DL = IC.getDataLayout();2696  Value *Base;2697  const APInt *C1;2698  if (!match(Src, m_PtrAdd(m_Value(Base), m_APInt(C1))))2699    return nullptr;2700  Value *VarIndex;2701  const APInt *C2;2702  Type *PtrTy = Src->getType()->getScalarType();2703  unsigned IndexSizeInBits = DL.getIndexTypeSizeInBits(PtrTy);2704  if (!match(GEP.getOperand(1), m_AddLike(m_Value(VarIndex), m_APInt(C2))))2705    return nullptr;2706  if (C1->getBitWidth() != IndexSizeInBits ||2707      C2->getBitWidth() != IndexSizeInBits)2708    return nullptr;2709  Type *BaseType = GEP.getSourceElementType();2710  if (isa<ScalableVectorType>(BaseType))2711    return nullptr;2712  APInt TypeSize(IndexSizeInBits, DL.getTypeAllocSize(BaseType));2713  APInt NewOffset = TypeSize * *C2 + *C1;2714  if (NewOffset.isZero() ||2715      (Src->hasOneUse() && GEP.getOperand(1)->hasOneUse())) {2716    GEPNoWrapFlags Flags = GEPNoWrapFlags::none();2717    if (GEP.hasNoUnsignedWrap() &&2718        cast<GEPOperator>(Src)->hasNoUnsignedWrap() &&2719        match(GEP.getOperand(1), m_NUWAddLike(m_Value(), m_Value()))) {2720      Flags |= GEPNoWrapFlags::noUnsignedWrap();2721      if (GEP.isInBounds() && cast<GEPOperator>(Src)->isInBounds())2722        Flags |= GEPNoWrapFlags::inBounds();2723    }2724 2725    Value *GEPConst =2726        IC.Builder.CreatePtrAdd(Base, IC.Builder.getInt(NewOffset), "", Flags);2727    return GetElementPtrInst::Create(BaseType, GEPConst, VarIndex, Flags);2728  }2729 2730  return nullptr;2731}2732 2733/// Combine constant offsets separated by variable offsets.2734/// ptradd (ptradd (ptradd p, C1), x), C2 -> ptradd (ptradd p, x), C1+C22735static Instruction *combineConstantOffsets(GetElementPtrInst &GEP,2736                                           InstCombinerImpl &IC) {2737  if (!GEP.hasAllConstantIndices())2738    return nullptr;2739 2740  GEPNoWrapFlags NW = GEPNoWrapFlags::all();2741  SmallVector<GetElementPtrInst *> Skipped;2742  auto *InnerGEP = dyn_cast<GetElementPtrInst>(GEP.getPointerOperand());2743  while (true) {2744    if (!InnerGEP)2745      return nullptr;2746 2747    NW = NW.intersectForReassociate(InnerGEP->getNoWrapFlags());2748    if (InnerGEP->hasAllConstantIndices())2749      break;2750 2751    if (!InnerGEP->hasOneUse())2752      return nullptr;2753 2754    Skipped.push_back(InnerGEP);2755    InnerGEP = dyn_cast<GetElementPtrInst>(InnerGEP->getPointerOperand());2756  }2757 2758  // The two constant offset GEPs are directly adjacent: Let normal offset2759  // merging handle it.2760  if (Skipped.empty())2761    return nullptr;2762 2763  // FIXME: This one-use check is not strictly necessary. Consider relaxing it2764  // if profitable.2765  if (!InnerGEP->hasOneUse())2766    return nullptr;2767 2768  // Don't bother with vector splats.2769  Type *Ty = GEP.getType();2770  if (InnerGEP->getType() != Ty)2771    return nullptr;2772 2773  const DataLayout &DL = IC.getDataLayout();2774  APInt Offset(DL.getIndexTypeSizeInBits(Ty), 0);2775  if (!GEP.accumulateConstantOffset(DL, Offset) ||2776      !InnerGEP->accumulateConstantOffset(DL, Offset))2777    return nullptr;2778 2779  IC.replaceOperand(*Skipped.back(), 0, InnerGEP->getPointerOperand());2780  for (GetElementPtrInst *SkippedGEP : Skipped)2781    SkippedGEP->setNoWrapFlags(NW);2782 2783  return IC.replaceInstUsesWith(2784      GEP,2785      IC.Builder.CreatePtrAdd(Skipped.front(), IC.Builder.getInt(Offset), "",2786                              NW.intersectForOffsetAdd(GEP.getNoWrapFlags())));2787}2788 2789Instruction *InstCombinerImpl::visitGEPOfGEP(GetElementPtrInst &GEP,2790                                             GEPOperator *Src) {2791  // Combine Indices - If the source pointer to this getelementptr instruction2792  // is a getelementptr instruction with matching element type, combine the2793  // indices of the two getelementptr instructions into a single instruction.2794  if (!shouldMergeGEPs(*cast<GEPOperator>(&GEP), *Src))2795    return nullptr;2796 2797  if (auto *I = canonicalizeGEPOfConstGEPI8(GEP, Src, *this))2798    return I;2799 2800  if (auto *I = combineConstantOffsets(GEP, *this))2801    return I;2802 2803  if (Src->getResultElementType() != GEP.getSourceElementType())2804    return nullptr;2805 2806  // Find out whether the last index in the source GEP is a sequential idx.2807  bool EndsWithSequential = false;2808  for (gep_type_iterator I = gep_type_begin(*Src), E = gep_type_end(*Src);2809       I != E; ++I)2810    EndsWithSequential = I.isSequential();2811  if (!EndsWithSequential)2812    return nullptr;2813 2814  // Replace: gep (gep %P, long B), long A, ...2815  // With:    T = long A+B; gep %P, T, ...2816  Value *SO1 = Src->getOperand(Src->getNumOperands() - 1);2817  Value *GO1 = GEP.getOperand(1);2818 2819  // If they aren't the same type, then the input hasn't been processed2820  // by the loop above yet (which canonicalizes sequential index types to2821  // intptr_t).  Just avoid transforming this until the input has been2822  // normalized.2823  if (SO1->getType() != GO1->getType())2824    return nullptr;2825 2826  Value *Sum =2827      simplifyAddInst(GO1, SO1, false, false, SQ.getWithInstruction(&GEP));2828  // Only do the combine when we are sure the cost after the2829  // merge is never more than that before the merge.2830  if (Sum == nullptr)2831    return nullptr;2832 2833  SmallVector<Value *, 8> Indices;2834  Indices.append(Src->op_begin() + 1, Src->op_end() - 1);2835  Indices.push_back(Sum);2836  Indices.append(GEP.op_begin() + 2, GEP.op_end());2837 2838  // Don't create GEPs with more than one non-zero index.2839  unsigned NumNonZeroIndices = count_if(Indices, [](Value *Idx) {2840    auto *C = dyn_cast<Constant>(Idx);2841    return !C || !C->isNullValue();2842  });2843  if (NumNonZeroIndices > 1)2844    return nullptr;2845 2846  return replaceInstUsesWith(2847      GEP, Builder.CreateGEP(2848               Src->getSourceElementType(), Src->getOperand(0), Indices, "",2849               getMergedGEPNoWrapFlags(*Src, *cast<GEPOperator>(&GEP))));2850}2851 2852Value *InstCombiner::getFreelyInvertedImpl(Value *V, bool WillInvertAllUses,2853                                           BuilderTy *Builder,2854                                           bool &DoesConsume, unsigned Depth) {2855  static Value *const NonNull = reinterpret_cast<Value *>(uintptr_t(1));2856  // ~(~(X)) -> X.2857  Value *A, *B;2858  if (match(V, m_Not(m_Value(A)))) {2859    DoesConsume = true;2860    return A;2861  }2862 2863  Constant *C;2864  // Constants can be considered to be not'ed values.2865  if (match(V, m_ImmConstant(C)))2866    return ConstantExpr::getNot(C);2867 2868  if (Depth++ >= MaxAnalysisRecursionDepth)2869    return nullptr;2870 2871  // The rest of the cases require that we invert all uses so don't bother2872  // doing the analysis if we know we can't use the result.2873  if (!WillInvertAllUses)2874    return nullptr;2875 2876  // Compares can be inverted if all of their uses are being modified to use2877  // the ~V.2878  if (auto *I = dyn_cast<CmpInst>(V)) {2879    if (Builder != nullptr)2880      return Builder->CreateCmp(I->getInversePredicate(), I->getOperand(0),2881                                I->getOperand(1));2882    return NonNull;2883  }2884 2885  // If `V` is of the form `A + B` then `-1 - V` can be folded into2886  // `(-1 - B) - A` if we are willing to invert all of the uses.2887  if (match(V, m_Add(m_Value(A), m_Value(B)))) {2888    if (auto *BV = getFreelyInvertedImpl(B, B->hasOneUse(), Builder,2889                                         DoesConsume, Depth))2890      return Builder ? Builder->CreateSub(BV, A) : NonNull;2891    if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,2892                                         DoesConsume, Depth))2893      return Builder ? Builder->CreateSub(AV, B) : NonNull;2894    return nullptr;2895  }2896 2897  // If `V` is of the form `A ^ ~B` then `~(A ^ ~B)` can be folded2898  // into `A ^ B` if we are willing to invert all of the uses.2899  if (match(V, m_Xor(m_Value(A), m_Value(B)))) {2900    if (auto *BV = getFreelyInvertedImpl(B, B->hasOneUse(), Builder,2901                                         DoesConsume, Depth))2902      return Builder ? Builder->CreateXor(A, BV) : NonNull;2903    if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,2904                                         DoesConsume, Depth))2905      return Builder ? Builder->CreateXor(AV, B) : NonNull;2906    return nullptr;2907  }2908 2909  // If `V` is of the form `B - A` then `-1 - V` can be folded into2910  // `A + (-1 - B)` if we are willing to invert all of the uses.2911  if (match(V, m_Sub(m_Value(A), m_Value(B)))) {2912    if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,2913                                         DoesConsume, Depth))2914      return Builder ? Builder->CreateAdd(AV, B) : NonNull;2915    return nullptr;2916  }2917 2918  // If `V` is of the form `(~A) s>> B` then `~((~A) s>> B)` can be folded2919  // into `A s>> B` if we are willing to invert all of the uses.2920  if (match(V, m_AShr(m_Value(A), m_Value(B)))) {2921    if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,2922                                         DoesConsume, Depth))2923      return Builder ? Builder->CreateAShr(AV, B) : NonNull;2924    return nullptr;2925  }2926 2927  Value *Cond;2928  // LogicOps are special in that we canonicalize them at the cost of an2929  // instruction.2930  bool IsSelect = match(V, m_Select(m_Value(Cond), m_Value(A), m_Value(B))) &&2931                  !shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(V));2932  // Selects/min/max with invertible operands are freely invertible2933  if (IsSelect || match(V, m_MaxOrMin(m_Value(A), m_Value(B)))) {2934    bool LocalDoesConsume = DoesConsume;2935    if (!getFreelyInvertedImpl(B, B->hasOneUse(), /*Builder*/ nullptr,2936                               LocalDoesConsume, Depth))2937      return nullptr;2938    if (Value *NotA = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,2939                                            LocalDoesConsume, Depth)) {2940      DoesConsume = LocalDoesConsume;2941      if (Builder != nullptr) {2942        Value *NotB = getFreelyInvertedImpl(B, B->hasOneUse(), Builder,2943                                            DoesConsume, Depth);2944        assert(NotB != nullptr &&2945               "Unable to build inverted value for known freely invertable op");2946        if (auto *II = dyn_cast<IntrinsicInst>(V))2947          return Builder->CreateBinaryIntrinsic(2948              getInverseMinMaxIntrinsic(II->getIntrinsicID()), NotA, NotB);2949        return Builder->CreateSelect(Cond, NotA, NotB);2950      }2951      return NonNull;2952    }2953  }2954 2955  if (PHINode *PN = dyn_cast<PHINode>(V)) {2956    bool LocalDoesConsume = DoesConsume;2957    SmallVector<std::pair<Value *, BasicBlock *>, 8> IncomingValues;2958    for (Use &U : PN->operands()) {2959      BasicBlock *IncomingBlock = PN->getIncomingBlock(U);2960      Value *NewIncomingVal = getFreelyInvertedImpl(2961          U.get(), /*WillInvertAllUses=*/false,2962          /*Builder=*/nullptr, LocalDoesConsume, MaxAnalysisRecursionDepth - 1);2963      if (NewIncomingVal == nullptr)2964        return nullptr;2965      // Make sure that we can safely erase the original PHI node.2966      if (NewIncomingVal == V)2967        return nullptr;2968      if (Builder != nullptr)2969        IncomingValues.emplace_back(NewIncomingVal, IncomingBlock);2970    }2971 2972    DoesConsume = LocalDoesConsume;2973    if (Builder != nullptr) {2974      IRBuilderBase::InsertPointGuard Guard(*Builder);2975      Builder->SetInsertPoint(PN);2976      PHINode *NewPN =2977          Builder->CreatePHI(PN->getType(), PN->getNumIncomingValues());2978      for (auto [Val, Pred] : IncomingValues)2979        NewPN->addIncoming(Val, Pred);2980      return NewPN;2981    }2982    return NonNull;2983  }2984 2985  if (match(V, m_SExtLike(m_Value(A)))) {2986    if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,2987                                         DoesConsume, Depth))2988      return Builder ? Builder->CreateSExt(AV, V->getType()) : NonNull;2989    return nullptr;2990  }2991 2992  if (match(V, m_Trunc(m_Value(A)))) {2993    if (auto *AV = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,2994                                         DoesConsume, Depth))2995      return Builder ? Builder->CreateTrunc(AV, V->getType()) : NonNull;2996    return nullptr;2997  }2998 2999  // De Morgan's Laws:3000  // (~(A | B)) -> (~A & ~B)3001  // (~(A & B)) -> (~A | ~B)3002  auto TryInvertAndOrUsingDeMorgan = [&](Instruction::BinaryOps Opcode,3003                                         bool IsLogical, Value *A,3004                                         Value *B) -> Value * {3005    bool LocalDoesConsume = DoesConsume;3006    if (!getFreelyInvertedImpl(B, B->hasOneUse(), /*Builder=*/nullptr,3007                               LocalDoesConsume, Depth))3008      return nullptr;3009    if (auto *NotA = getFreelyInvertedImpl(A, A->hasOneUse(), Builder,3010                                           LocalDoesConsume, Depth)) {3011      auto *NotB = getFreelyInvertedImpl(B, B->hasOneUse(), Builder,3012                                         LocalDoesConsume, Depth);3013      DoesConsume = LocalDoesConsume;3014      if (IsLogical)3015        return Builder ? Builder->CreateLogicalOp(Opcode, NotA, NotB) : NonNull;3016      return Builder ? Builder->CreateBinOp(Opcode, NotA, NotB) : NonNull;3017    }3018 3019    return nullptr;3020  };3021 3022  if (match(V, m_Or(m_Value(A), m_Value(B))))3023    return TryInvertAndOrUsingDeMorgan(Instruction::And, /*IsLogical=*/false, A,3024                                       B);3025 3026  if (match(V, m_And(m_Value(A), m_Value(B))))3027    return TryInvertAndOrUsingDeMorgan(Instruction::Or, /*IsLogical=*/false, A,3028                                       B);3029 3030  if (match(V, m_LogicalOr(m_Value(A), m_Value(B))))3031    return TryInvertAndOrUsingDeMorgan(Instruction::And, /*IsLogical=*/true, A,3032                                       B);3033 3034  if (match(V, m_LogicalAnd(m_Value(A), m_Value(B))))3035    return TryInvertAndOrUsingDeMorgan(Instruction::Or, /*IsLogical=*/true, A,3036                                       B);3037 3038  return nullptr;3039}3040 3041/// Return true if we should canonicalize the gep to an i8 ptradd.3042static bool shouldCanonicalizeGEPToPtrAdd(GetElementPtrInst &GEP) {3043  Value *PtrOp = GEP.getOperand(0);3044  Type *GEPEltType = GEP.getSourceElementType();3045  if (GEPEltType->isIntegerTy(8))3046    return false;3047 3048  // Canonicalize scalable GEPs to an explicit offset using the llvm.vscale3049  // intrinsic. This has better support in BasicAA.3050  if (GEPEltType->isScalableTy())3051    return true;3052 3053  // gep i32 p, mul(O, C) -> gep i8, p, mul(O, C*4) to fold the two multiplies3054  // together.3055  if (GEP.getNumIndices() == 1 &&3056      match(GEP.getOperand(1),3057            m_OneUse(m_CombineOr(m_Mul(m_Value(), m_ConstantInt()),3058                                 m_Shl(m_Value(), m_ConstantInt())))))3059    return true;3060 3061  // gep (gep %p, C1), %x, C2 is expanded so the two constants can3062  // possibly be merged together.3063  auto PtrOpGep = dyn_cast<GEPOperator>(PtrOp);3064  return PtrOpGep && PtrOpGep->hasAllConstantIndices() &&3065         any_of(GEP.indices(), [](Value *V) {3066           const APInt *C;3067           return match(V, m_APInt(C)) && !C->isZero();3068         });3069}3070 3071static Instruction *foldGEPOfPhi(GetElementPtrInst &GEP, PHINode *PN,3072                                 IRBuilderBase &Builder) {3073  auto *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0));3074  if (!Op1)3075    return nullptr;3076 3077  // Don't fold a GEP into itself through a PHI node. This can only happen3078  // through the back-edge of a loop. Folding a GEP into itself means that3079  // the value of the previous iteration needs to be stored in the meantime,3080  // thus requiring an additional register variable to be live, but not3081  // actually achieving anything (the GEP still needs to be executed once per3082  // loop iteration).3083  if (Op1 == &GEP)3084    return nullptr;3085  GEPNoWrapFlags NW = Op1->getNoWrapFlags();3086 3087  int DI = -1;3088 3089  for (auto I = PN->op_begin()+1, E = PN->op_end(); I !=E; ++I) {3090    auto *Op2 = dyn_cast<GetElementPtrInst>(*I);3091    if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands() ||3092        Op1->getSourceElementType() != Op2->getSourceElementType())3093      return nullptr;3094 3095    // As for Op1 above, don't try to fold a GEP into itself.3096    if (Op2 == &GEP)3097      return nullptr;3098 3099    // Keep track of the type as we walk the GEP.3100    Type *CurTy = nullptr;3101 3102    for (unsigned J = 0, F = Op1->getNumOperands(); J != F; ++J) {3103      if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType())3104        return nullptr;3105 3106      if (Op1->getOperand(J) != Op2->getOperand(J)) {3107        if (DI == -1) {3108          // We have not seen any differences yet in the GEPs feeding the3109          // PHI yet, so we record this one if it is allowed to be a3110          // variable.3111 3112          // The first two arguments can vary for any GEP, the rest have to be3113          // static for struct slots3114          if (J > 1) {3115            assert(CurTy && "No current type?");3116            if (CurTy->isStructTy())3117              return nullptr;3118          }3119 3120          DI = J;3121        } else {3122          // The GEP is different by more than one input. While this could be3123          // extended to support GEPs that vary by more than one variable it3124          // doesn't make sense since it greatly increases the complexity and3125          // would result in an R+R+R addressing mode which no backend3126          // directly supports and would need to be broken into several3127          // simpler instructions anyway.3128          return nullptr;3129        }3130      }3131 3132      // Sink down a layer of the type for the next iteration.3133      if (J > 0) {3134        if (J == 1) {3135          CurTy = Op1->getSourceElementType();3136        } else {3137          CurTy =3138              GetElementPtrInst::getTypeAtIndex(CurTy, Op1->getOperand(J));3139        }3140      }3141    }3142 3143    NW &= Op2->getNoWrapFlags();3144  }3145 3146  // If not all GEPs are identical we'll have to create a new PHI node.3147  // Check that the old PHI node has only one use so that it will get3148  // removed.3149  if (DI != -1 && !PN->hasOneUse())3150    return nullptr;3151 3152  auto *NewGEP = cast<GetElementPtrInst>(Op1->clone());3153  NewGEP->setNoWrapFlags(NW);3154 3155  if (DI == -1) {3156    // All the GEPs feeding the PHI are identical. Clone one down into our3157    // BB so that it can be merged with the current GEP.3158  } else {3159    // All the GEPs feeding the PHI differ at a single offset. Clone a GEP3160    // into the current block so it can be merged, and create a new PHI to3161    // set that index.3162    PHINode *NewPN;3163    {3164      IRBuilderBase::InsertPointGuard Guard(Builder);3165      Builder.SetInsertPoint(PN);3166      NewPN = Builder.CreatePHI(Op1->getOperand(DI)->getType(),3167                                PN->getNumOperands());3168    }3169 3170    for (auto &I : PN->operands())3171      NewPN->addIncoming(cast<GEPOperator>(I)->getOperand(DI),3172                         PN->getIncomingBlock(I));3173 3174    NewGEP->setOperand(DI, NewPN);3175  }3176 3177  NewGEP->insertBefore(*GEP.getParent(), GEP.getParent()->getFirstInsertionPt());3178  return NewGEP;3179}3180 3181Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) {3182  Value *PtrOp = GEP.getOperand(0);3183  SmallVector<Value *, 8> Indices(GEP.indices());3184  Type *GEPType = GEP.getType();3185  Type *GEPEltType = GEP.getSourceElementType();3186  if (Value *V =3187          simplifyGEPInst(GEPEltType, PtrOp, Indices, GEP.getNoWrapFlags(),3188                          SQ.getWithInstruction(&GEP)))3189    return replaceInstUsesWith(GEP, V);3190 3191  // For vector geps, use the generic demanded vector support.3192  // Skip if GEP return type is scalable. The number of elements is unknown at3193  // compile-time.3194  if (auto *GEPFVTy = dyn_cast<FixedVectorType>(GEPType)) {3195    auto VWidth = GEPFVTy->getNumElements();3196    APInt PoisonElts(VWidth, 0);3197    APInt AllOnesEltMask(APInt::getAllOnes(VWidth));3198    if (Value *V = SimplifyDemandedVectorElts(&GEP, AllOnesEltMask,3199                                              PoisonElts)) {3200      if (V != &GEP)3201        return replaceInstUsesWith(GEP, V);3202      return &GEP;3203    }3204  }3205 3206  // Eliminate unneeded casts for indices, and replace indices which displace3207  // by multiples of a zero size type with zero.3208  bool MadeChange = false;3209 3210  // Index width may not be the same width as pointer width.3211  // Data layout chooses the right type based on supported integer types.3212  Type *NewScalarIndexTy =3213      DL.getIndexType(GEP.getPointerOperandType()->getScalarType());3214 3215  gep_type_iterator GTI = gep_type_begin(GEP);3216  for (User::op_iterator I = GEP.op_begin() + 1, E = GEP.op_end(); I != E;3217       ++I, ++GTI) {3218    // Skip indices into struct types.3219    if (GTI.isStruct())3220      continue;3221 3222    Type *IndexTy = (*I)->getType();3223    Type *NewIndexType =3224        IndexTy->isVectorTy()3225            ? VectorType::get(NewScalarIndexTy,3226                              cast<VectorType>(IndexTy)->getElementCount())3227            : NewScalarIndexTy;3228 3229    // If the element type has zero size then any index over it is equivalent3230    // to an index of zero, so replace it with zero if it is not zero already.3231    Type *EltTy = GTI.getIndexedType();3232    if (EltTy->isSized() && DL.getTypeAllocSize(EltTy).isZero())3233      if (!isa<Constant>(*I) || !match(I->get(), m_Zero())) {3234        *I = Constant::getNullValue(NewIndexType);3235        MadeChange = true;3236      }3237 3238    if (IndexTy != NewIndexType) {3239      // If we are using a wider index than needed for this platform, shrink3240      // it to what we need.  If narrower, sign-extend it to what we need.3241      // This explicit cast can make subsequent optimizations more obvious.3242      if (IndexTy->getScalarSizeInBits() <3243          NewIndexType->getScalarSizeInBits()) {3244        if (GEP.hasNoUnsignedWrap() && GEP.hasNoUnsignedSignedWrap())3245          *I = Builder.CreateZExt(*I, NewIndexType, "", /*IsNonNeg=*/true);3246        else3247          *I = Builder.CreateSExt(*I, NewIndexType);3248      } else {3249        *I = Builder.CreateTrunc(*I, NewIndexType, "", GEP.hasNoUnsignedWrap(),3250                                 GEP.hasNoUnsignedSignedWrap());3251      }3252      MadeChange = true;3253    }3254  }3255  if (MadeChange)3256    return &GEP;3257 3258  // Canonicalize constant GEPs to i8 type.3259  if (!GEPEltType->isIntegerTy(8) && GEP.hasAllConstantIndices()) {3260    APInt Offset(DL.getIndexTypeSizeInBits(GEPType), 0);3261    if (GEP.accumulateConstantOffset(DL, Offset))3262      return replaceInstUsesWith(3263          GEP, Builder.CreatePtrAdd(PtrOp, Builder.getInt(Offset), "",3264                                    GEP.getNoWrapFlags()));3265  }3266 3267  if (shouldCanonicalizeGEPToPtrAdd(GEP)) {3268    Value *Offset = EmitGEPOffset(cast<GEPOperator>(&GEP));3269    Value *NewGEP =3270        Builder.CreatePtrAdd(PtrOp, Offset, "", GEP.getNoWrapFlags());3271    return replaceInstUsesWith(GEP, NewGEP);3272  }3273 3274  // Strip trailing zero indices.3275  auto *LastIdx = dyn_cast<Constant>(Indices.back());3276  if (LastIdx && LastIdx->isNullValue() && !LastIdx->getType()->isVectorTy()) {3277    return replaceInstUsesWith(3278        GEP, Builder.CreateGEP(GEP.getSourceElementType(), PtrOp,3279                               drop_end(Indices), "", GEP.getNoWrapFlags()));3280  }3281 3282  // Strip leading zero indices.3283  auto *FirstIdx = dyn_cast<Constant>(Indices.front());3284  if (FirstIdx && FirstIdx->isNullValue() &&3285      !FirstIdx->getType()->isVectorTy()) {3286    gep_type_iterator GTI = gep_type_begin(GEP);3287    ++GTI;3288    if (!GTI.isStruct())3289      return replaceInstUsesWith(GEP, Builder.CreateGEP(GTI.getIndexedType(),3290                                                        GEP.getPointerOperand(),3291                                                        drop_begin(Indices), "",3292                                                        GEP.getNoWrapFlags()));3293  }3294 3295  // Scalarize vector operands; prefer splat-of-gep.as canonical form.3296  // Note that this looses information about undef lanes; we run it after3297  // demanded bits to partially mitigate that loss.3298  if (GEPType->isVectorTy() && llvm::any_of(GEP.operands(), [](Value *Op) {3299        return Op->getType()->isVectorTy() && getSplatValue(Op);3300      })) {3301    SmallVector<Value *> NewOps;3302    for (auto &Op : GEP.operands()) {3303      if (Op->getType()->isVectorTy())3304        if (Value *Scalar = getSplatValue(Op)) {3305          NewOps.push_back(Scalar);3306          continue;3307        }3308      NewOps.push_back(Op);3309    }3310 3311    Value *Res = Builder.CreateGEP(GEP.getSourceElementType(), NewOps[0],3312                                   ArrayRef(NewOps).drop_front(), GEP.getName(),3313                                   GEP.getNoWrapFlags());3314    if (!Res->getType()->isVectorTy()) {3315      ElementCount EC = cast<VectorType>(GEPType)->getElementCount();3316      Res = Builder.CreateVectorSplat(EC, Res);3317    }3318    return replaceInstUsesWith(GEP, Res);3319  }3320 3321  bool SeenNonZeroIndex = false;3322  for (auto [IdxNum, Idx] : enumerate(Indices)) {3323    auto *C = dyn_cast<Constant>(Idx);3324    if (C && C->isNullValue())3325      continue;3326 3327    if (!SeenNonZeroIndex) {3328      SeenNonZeroIndex = true;3329      continue;3330    }3331 3332    // GEP has multiple non-zero indices: Split it.3333    ArrayRef<Value *> FrontIndices = ArrayRef(Indices).take_front(IdxNum);3334    Value *FrontGEP =3335        Builder.CreateGEP(GEPEltType, PtrOp, FrontIndices,3336                          GEP.getName() + ".split", GEP.getNoWrapFlags());3337 3338    SmallVector<Value *> BackIndices;3339    BackIndices.push_back(Constant::getNullValue(NewScalarIndexTy));3340    append_range(BackIndices, drop_begin(Indices, IdxNum));3341    return GetElementPtrInst::Create(3342        GetElementPtrInst::getIndexedType(GEPEltType, FrontIndices), FrontGEP,3343        BackIndices, GEP.getNoWrapFlags());3344  }3345 3346  // Check to see if the inputs to the PHI node are getelementptr instructions.3347  if (auto *PN = dyn_cast<PHINode>(PtrOp)) {3348    if (Value *NewPtrOp = foldGEPOfPhi(GEP, PN, Builder))3349      return replaceOperand(GEP, 0, NewPtrOp);3350  }3351 3352  if (auto *Src = dyn_cast<GEPOperator>(PtrOp))3353    if (Instruction *I = visitGEPOfGEP(GEP, Src))3354      return I;3355 3356  if (GEP.getNumIndices() == 1) {3357    unsigned AS = GEP.getPointerAddressSpace();3358    if (GEP.getOperand(1)->getType()->getScalarSizeInBits() ==3359        DL.getIndexSizeInBits(AS)) {3360      uint64_t TyAllocSize = DL.getTypeAllocSize(GEPEltType).getFixedValue();3361 3362      if (TyAllocSize == 1) {3363        // Canonicalize (gep i8* X, (ptrtoint Y)-(ptrtoint X)) to (bitcast Y),3364        // but only if the result pointer is only used as if it were an integer.3365        // (The case where the underlying object is the same is handled by3366        // InstSimplify.)3367        Value *X = GEP.getPointerOperand();3368        Value *Y;3369        if (match(GEP.getOperand(1), m_Sub(m_PtrToIntOrAddr(m_Value(Y)),3370                                           m_PtrToIntOrAddr(m_Specific(X)))) &&3371            GEPType == Y->getType()) {3372          bool HasNonAddressBits =3373              DL.getAddressSizeInBits(AS) != DL.getPointerSizeInBits(AS);3374          bool Changed = false;3375          GEP.replaceUsesWithIf(Y, [&](Use &U) {3376            bool ShouldReplace = isa<PtrToAddrInst>(U.getUser()) ||3377                                 (!HasNonAddressBits &&3378                                  isa<ICmpInst, PtrToIntInst>(U.getUser()));3379            Changed |= ShouldReplace;3380            return ShouldReplace;3381          });3382          return Changed ? &GEP : nullptr;3383        }3384      } else if (auto *ExactIns =3385                     dyn_cast<PossiblyExactOperator>(GEP.getOperand(1))) {3386        // Canonicalize (gep T* X, V / sizeof(T)) to (gep i8* X, V)3387        Value *V;3388        if (ExactIns->isExact()) {3389          if ((has_single_bit(TyAllocSize) &&3390               match(GEP.getOperand(1),3391                     m_Shr(m_Value(V),3392                           m_SpecificInt(countr_zero(TyAllocSize))))) ||3393              match(GEP.getOperand(1),3394                    m_IDiv(m_Value(V), m_SpecificInt(TyAllocSize)))) {3395            return GetElementPtrInst::Create(Builder.getInt8Ty(),3396                                             GEP.getPointerOperand(), V,3397                                             GEP.getNoWrapFlags());3398          }3399        }3400        if (ExactIns->isExact() && ExactIns->hasOneUse()) {3401          // Try to canonicalize non-i8 element type to i8 if the index is an3402          // exact instruction. If the index is an exact instruction (div/shr)3403          // with a constant RHS, we can fold the non-i8 element scale into the3404          // div/shr (similiar to the mul case, just inverted).3405          const APInt *C;3406          std::optional<APInt> NewC;3407          if (has_single_bit(TyAllocSize) &&3408              match(ExactIns, m_Shr(m_Value(V), m_APInt(C))) &&3409              C->uge(countr_zero(TyAllocSize)))3410            NewC = *C - countr_zero(TyAllocSize);3411          else if (match(ExactIns, m_UDiv(m_Value(V), m_APInt(C)))) {3412            APInt Quot;3413            uint64_t Rem;3414            APInt::udivrem(*C, TyAllocSize, Quot, Rem);3415            if (Rem == 0)3416              NewC = Quot;3417          } else if (match(ExactIns, m_SDiv(m_Value(V), m_APInt(C)))) {3418            APInt Quot;3419            int64_t Rem;3420            APInt::sdivrem(*C, TyAllocSize, Quot, Rem);3421            // For sdiv we need to make sure we arent creating INT_MIN / -1.3422            if (!Quot.isAllOnes() && Rem == 0)3423              NewC = Quot;3424          }3425 3426          if (NewC.has_value()) {3427            Value *NewOp = Builder.CreateBinOp(3428                static_cast<Instruction::BinaryOps>(ExactIns->getOpcode()), V,3429                ConstantInt::get(V->getType(), *NewC));3430            cast<BinaryOperator>(NewOp)->setIsExact();3431            return GetElementPtrInst::Create(Builder.getInt8Ty(),3432                                             GEP.getPointerOperand(), NewOp,3433                                             GEP.getNoWrapFlags());3434          }3435        }3436      }3437    }3438  }3439  // We do not handle pointer-vector geps here.3440  if (GEPType->isVectorTy())3441    return nullptr;3442 3443  if (!GEP.isInBounds()) {3444    unsigned IdxWidth =3445        DL.getIndexSizeInBits(PtrOp->getType()->getPointerAddressSpace());3446    APInt BasePtrOffset(IdxWidth, 0);3447    Value *UnderlyingPtrOp =3448        PtrOp->stripAndAccumulateInBoundsConstantOffsets(DL, BasePtrOffset);3449    bool CanBeNull, CanBeFreed;3450    uint64_t DerefBytes = UnderlyingPtrOp->getPointerDereferenceableBytes(3451        DL, CanBeNull, CanBeFreed);3452    if (!CanBeNull && !CanBeFreed && DerefBytes != 0) {3453      if (GEP.accumulateConstantOffset(DL, BasePtrOffset) &&3454          BasePtrOffset.isNonNegative()) {3455        APInt AllocSize(IdxWidth, DerefBytes);3456        if (BasePtrOffset.ule(AllocSize)) {3457          return GetElementPtrInst::CreateInBounds(3458              GEP.getSourceElementType(), PtrOp, Indices, GEP.getName());3459        }3460      }3461    }3462  }3463 3464  // nusw + nneg -> nuw3465  if (GEP.hasNoUnsignedSignedWrap() && !GEP.hasNoUnsignedWrap() &&3466      all_of(GEP.indices(), [&](Value *Idx) {3467        return isKnownNonNegative(Idx, SQ.getWithInstruction(&GEP));3468      })) {3469    GEP.setNoWrapFlags(GEP.getNoWrapFlags() | GEPNoWrapFlags::noUnsignedWrap());3470    return &GEP;3471  }3472 3473  // These rewrites are trying to preserve inbounds/nuw attributes. So we want3474  // to do this after having tried to derive "nuw" above.3475  if (GEP.getNumIndices() == 1) {3476    // Given (gep p, x+y) we want to determine the common nowrap flags for both3477    // geps if transforming into (gep (gep p, x), y).3478    auto GetPreservedNoWrapFlags = [&](bool AddIsNUW) {3479      // We can preserve both "inbounds nuw", "nusw nuw" and "nuw" if we know3480      // that x + y does not have unsigned wrap.3481      if (GEP.hasNoUnsignedWrap() && AddIsNUW)3482        return GEP.getNoWrapFlags();3483      return GEPNoWrapFlags::none();3484    };3485 3486    // Try to replace ADD + GEP with GEP + GEP.3487    Value *Idx1, *Idx2;3488    if (match(GEP.getOperand(1),3489              m_OneUse(m_AddLike(m_Value(Idx1), m_Value(Idx2))))) {3490      //   %idx = add i64 %idx1, %idx23491      //   %gep = getelementptr i32, ptr %ptr, i64 %idx3492      // as:3493      //   %newptr = getelementptr i32, ptr %ptr, i64 %idx13494      //   %newgep = getelementptr i32, ptr %newptr, i64 %idx23495      bool NUW = match(GEP.getOperand(1), m_NUWAddLike(m_Value(), m_Value()));3496      GEPNoWrapFlags NWFlags = GetPreservedNoWrapFlags(NUW);3497      auto *NewPtr =3498          Builder.CreateGEP(GEP.getSourceElementType(), GEP.getPointerOperand(),3499                            Idx1, "", NWFlags);3500      return replaceInstUsesWith(GEP,3501                                 Builder.CreateGEP(GEP.getSourceElementType(),3502                                                   NewPtr, Idx2, "", NWFlags));3503    }3504    ConstantInt *C;3505    if (match(GEP.getOperand(1), m_OneUse(m_SExtLike(m_OneUse(m_NSWAddLike(3506                                     m_Value(Idx1), m_ConstantInt(C))))))) {3507      // %add = add nsw i32 %idx1, idx23508      // %sidx = sext i32 %add to i643509      // %gep = getelementptr i32, ptr %ptr, i64 %sidx3510      // as:3511      // %newptr = getelementptr i32, ptr %ptr, i32 %idx13512      // %newgep = getelementptr i32, ptr %newptr, i32 idx23513      bool NUW = match(GEP.getOperand(1),3514                       m_NNegZExt(m_NUWAddLike(m_Value(), m_Value())));3515      GEPNoWrapFlags NWFlags = GetPreservedNoWrapFlags(NUW);3516      auto *NewPtr = Builder.CreateGEP(3517          GEP.getSourceElementType(), GEP.getPointerOperand(),3518          Builder.CreateSExt(Idx1, GEP.getOperand(1)->getType()), "", NWFlags);3519      return replaceInstUsesWith(3520          GEP,3521          Builder.CreateGEP(GEP.getSourceElementType(), NewPtr,3522                            Builder.CreateSExt(C, GEP.getOperand(1)->getType()),3523                            "", NWFlags));3524    }3525  }3526 3527  if (Instruction *R = foldSelectGEP(GEP, Builder))3528    return R;3529 3530  return nullptr;3531}3532 3533static bool isNeverEqualToUnescapedAlloc(Value *V, const TargetLibraryInfo &TLI,3534                                         Instruction *AI) {3535  if (isa<ConstantPointerNull>(V))3536    return true;3537  if (auto *LI = dyn_cast<LoadInst>(V))3538    return isa<GlobalVariable>(LI->getPointerOperand());3539  // Two distinct allocations will never be equal.3540  return isAllocLikeFn(V, &TLI) && V != AI;3541}3542 3543/// Given a call CB which uses an address UsedV, return true if we can prove the3544/// call's only possible effect is storing to V.3545static bool isRemovableWrite(CallBase &CB, Value *UsedV,3546                             const TargetLibraryInfo &TLI) {3547  if (!CB.use_empty())3548    // TODO: add recursion if returned attribute is present3549    return false;3550 3551  if (CB.isTerminator())3552    // TODO: remove implementation restriction3553    return false;3554 3555  if (!CB.willReturn() || !CB.doesNotThrow())3556    return false;3557 3558  // If the only possible side effect of the call is writing to the alloca,3559  // and the result isn't used, we can safely remove any reads implied by the3560  // call including those which might read the alloca itself.3561  std::optional<MemoryLocation> Dest = MemoryLocation::getForDest(&CB, TLI);3562  return Dest && Dest->Ptr == UsedV;3563}3564 3565static std::optional<ModRefInfo>3566isAllocSiteRemovable(Instruction *AI, SmallVectorImpl<WeakTrackingVH> &Users,3567                     const TargetLibraryInfo &TLI, bool KnowInit) {3568  SmallVector<Instruction*, 4> Worklist;3569  const std::optional<StringRef> Family = getAllocationFamily(AI, &TLI);3570  Worklist.push_back(AI);3571  ModRefInfo Access = KnowInit ? ModRefInfo::NoModRef : ModRefInfo::Mod;3572 3573  do {3574    Instruction *PI = Worklist.pop_back_val();3575    for (User *U : PI->users()) {3576      Instruction *I = cast<Instruction>(U);3577      switch (I->getOpcode()) {3578      default:3579        // Give up the moment we see something we can't handle.3580        return std::nullopt;3581 3582      case Instruction::AddrSpaceCast:3583      case Instruction::BitCast:3584      case Instruction::GetElementPtr:3585        Users.emplace_back(I);3586        Worklist.push_back(I);3587        continue;3588 3589      case Instruction::ICmp: {3590        ICmpInst *ICI = cast<ICmpInst>(I);3591        // We can fold eq/ne comparisons with null to false/true, respectively.3592        // We also fold comparisons in some conditions provided the alloc has3593        // not escaped (see isNeverEqualToUnescapedAlloc).3594        if (!ICI->isEquality())3595          return std::nullopt;3596        unsigned OtherIndex = (ICI->getOperand(0) == PI) ? 1 : 0;3597        if (!isNeverEqualToUnescapedAlloc(ICI->getOperand(OtherIndex), TLI, AI))3598          return std::nullopt;3599 3600        // Do not fold compares to aligned_alloc calls, as they may have to3601        // return null in case the required alignment cannot be satisfied,3602        // unless we can prove that both alignment and size are valid.3603        auto AlignmentAndSizeKnownValid = [](CallBase *CB) {3604          // Check if alignment and size of a call to aligned_alloc is valid,3605          // that is alignment is a power-of-2 and the size is a multiple of the3606          // alignment.3607          const APInt *Alignment;3608          const APInt *Size;3609          return match(CB->getArgOperand(0), m_APInt(Alignment)) &&3610                 match(CB->getArgOperand(1), m_APInt(Size)) &&3611                 Alignment->isPowerOf2() && Size->urem(*Alignment).isZero();3612        };3613        auto *CB = dyn_cast<CallBase>(AI);3614        LibFunc TheLibFunc;3615        if (CB && TLI.getLibFunc(*CB->getCalledFunction(), TheLibFunc) &&3616            TLI.has(TheLibFunc) && TheLibFunc == LibFunc_aligned_alloc &&3617            !AlignmentAndSizeKnownValid(CB))3618          return std::nullopt;3619        Users.emplace_back(I);3620        continue;3621      }3622 3623      case Instruction::Call:3624        // Ignore no-op and store intrinsics.3625        if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {3626          switch (II->getIntrinsicID()) {3627          default:3628            return std::nullopt;3629 3630          case Intrinsic::memmove:3631          case Intrinsic::memcpy:3632          case Intrinsic::memset: {3633            MemIntrinsic *MI = cast<MemIntrinsic>(II);3634            if (MI->isVolatile())3635              return std::nullopt;3636            // Note: this could also be ModRef, but we can still interpret that3637            // as just Mod in that case.3638            ModRefInfo NewAccess =3639                MI->getRawDest() == PI ? ModRefInfo::Mod : ModRefInfo::Ref;3640            if ((Access & ~NewAccess) != ModRefInfo::NoModRef)3641              return std::nullopt;3642            Access |= NewAccess;3643            [[fallthrough]];3644          }3645          case Intrinsic::assume:3646          case Intrinsic::invariant_start:3647          case Intrinsic::invariant_end:3648          case Intrinsic::lifetime_start:3649          case Intrinsic::lifetime_end:3650          case Intrinsic::objectsize:3651            Users.emplace_back(I);3652            continue;3653          case Intrinsic::launder_invariant_group:3654          case Intrinsic::strip_invariant_group:3655            Users.emplace_back(I);3656            Worklist.push_back(I);3657            continue;3658          }3659        }3660 3661        if (Family && getFreedOperand(cast<CallBase>(I), &TLI) == PI &&3662            getAllocationFamily(I, &TLI) == Family) {3663          Users.emplace_back(I);3664          continue;3665        }3666 3667        if (Family && getReallocatedOperand(cast<CallBase>(I)) == PI &&3668            getAllocationFamily(I, &TLI) == Family) {3669          Users.emplace_back(I);3670          Worklist.push_back(I);3671          continue;3672        }3673 3674        if (!isRefSet(Access) &&3675            isRemovableWrite(*cast<CallBase>(I), PI, TLI)) {3676          Access |= ModRefInfo::Mod;3677          Users.emplace_back(I);3678          continue;3679        }3680 3681        return std::nullopt;3682 3683      case Instruction::Store: {3684        StoreInst *SI = cast<StoreInst>(I);3685        if (SI->isVolatile() || SI->getPointerOperand() != PI)3686          return std::nullopt;3687        if (isRefSet(Access))3688          return std::nullopt;3689        Access |= ModRefInfo::Mod;3690        Users.emplace_back(I);3691        continue;3692      }3693 3694      case Instruction::Load: {3695        LoadInst *LI = cast<LoadInst>(I);3696        if (LI->isVolatile() || LI->getPointerOperand() != PI)3697          return std::nullopt;3698        if (isModSet(Access))3699          return std::nullopt;3700        Access |= ModRefInfo::Ref;3701        Users.emplace_back(I);3702        continue;3703      }3704      }3705      llvm_unreachable("missing a return?");3706    }3707  } while (!Worklist.empty());3708 3709  assert(Access != ModRefInfo::ModRef);3710  return Access;3711}3712 3713Instruction *InstCombinerImpl::visitAllocSite(Instruction &MI) {3714  assert(isa<AllocaInst>(MI) || isRemovableAlloc(&cast<CallBase>(MI), &TLI));3715 3716  // If we have a malloc call which is only used in any amount of comparisons to3717  // null and free calls, delete the calls and replace the comparisons with true3718  // or false as appropriate.3719 3720  // This is based on the principle that we can substitute our own allocation3721  // function (which will never return null) rather than knowledge of the3722  // specific function being called. In some sense this can change the permitted3723  // outputs of a program (when we convert a malloc to an alloca, the fact that3724  // the allocation is now on the stack is potentially visible, for example),3725  // but we believe in a permissible manner.3726  SmallVector<WeakTrackingVH, 64> Users;3727 3728  // If we are removing an alloca with a dbg.declare, insert dbg.value calls3729  // before each store.3730  SmallVector<DbgVariableRecord *, 8> DVRs;3731  std::unique_ptr<DIBuilder> DIB;3732  if (isa<AllocaInst>(MI)) {3733    findDbgUsers(&MI, DVRs);3734    DIB.reset(new DIBuilder(*MI.getModule(), /*AllowUnresolved=*/false));3735  }3736 3737  // Determine what getInitialValueOfAllocation would return without actually3738  // allocating the result.3739  bool KnowInitUndef = false;3740  bool KnowInitZero = false;3741  Constant *Init =3742      getInitialValueOfAllocation(&MI, &TLI, Type::getInt8Ty(MI.getContext()));3743  if (Init) {3744    if (isa<UndefValue>(Init))3745      KnowInitUndef = true;3746    else if (Init->isNullValue())3747      KnowInitZero = true;3748  }3749  // The various sanitizers don't actually return undef memory, but rather3750  // memory initialized with special forms of runtime poison3751  auto &F = *MI.getFunction();3752  if (F.hasFnAttribute(Attribute::SanitizeMemory) ||3753      F.hasFnAttribute(Attribute::SanitizeAddress))3754    KnowInitUndef = false;3755 3756  auto Removable =3757      isAllocSiteRemovable(&MI, Users, TLI, KnowInitZero | KnowInitUndef);3758  if (Removable) {3759    for (WeakTrackingVH &User : Users) {3760      // Lowering all @llvm.objectsize and MTI calls first because they may use3761      // a bitcast/GEP of the alloca we are removing.3762      if (!User)3763        continue;3764 3765      Instruction *I = cast<Instruction>(&*User);3766 3767      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {3768        if (II->getIntrinsicID() == Intrinsic::objectsize) {3769          SmallVector<Instruction *> InsertedInstructions;3770          Value *Result = lowerObjectSizeCall(3771              II, DL, &TLI, AA, /*MustSucceed=*/true, &InsertedInstructions);3772          for (Instruction *Inserted : InsertedInstructions)3773            Worklist.add(Inserted);3774          replaceInstUsesWith(*I, Result);3775          eraseInstFromFunction(*I);3776          User = nullptr; // Skip examining in the next loop.3777          continue;3778        }3779        if (auto *MTI = dyn_cast<MemTransferInst>(I)) {3780          if (KnowInitZero && isRefSet(*Removable)) {3781            IRBuilderBase::InsertPointGuard Guard(Builder);3782            Builder.SetInsertPoint(MTI);3783            auto *M = Builder.CreateMemSet(3784                MTI->getRawDest(),3785                ConstantInt::get(Type::getInt8Ty(MI.getContext()), 0),3786                MTI->getLength(), MTI->getDestAlign());3787            M->copyMetadata(*MTI);3788          }3789        }3790      }3791    }3792    for (WeakTrackingVH &User : Users) {3793      if (!User)3794        continue;3795 3796      Instruction *I = cast<Instruction>(&*User);3797 3798      if (ICmpInst *C = dyn_cast<ICmpInst>(I)) {3799        replaceInstUsesWith(*C,3800                            ConstantInt::get(Type::getInt1Ty(C->getContext()),3801                                             C->isFalseWhenEqual()));3802      } else if (auto *SI = dyn_cast<StoreInst>(I)) {3803        for (auto *DVR : DVRs)3804          if (DVR->isAddressOfVariable())3805            ConvertDebugDeclareToDebugValue(DVR, SI, *DIB);3806      } else {3807        // Casts, GEP, or anything else: we're about to delete this instruction,3808        // so it can not have any valid uses.3809        Constant *Replace;3810        if (isa<LoadInst>(I)) {3811          assert(KnowInitZero || KnowInitUndef);3812          Replace = KnowInitUndef ? UndefValue::get(I->getType())3813                                  : Constant::getNullValue(I->getType());3814        } else3815          Replace = PoisonValue::get(I->getType());3816        replaceInstUsesWith(*I, Replace);3817      }3818      eraseInstFromFunction(*I);3819    }3820 3821    if (InvokeInst *II = dyn_cast<InvokeInst>(&MI)) {3822      // Replace invoke with a NOP intrinsic to maintain the original CFG3823      Module *M = II->getModule();3824      Function *F = Intrinsic::getOrInsertDeclaration(M, Intrinsic::donothing);3825      auto *NewII = InvokeInst::Create(3826          F, II->getNormalDest(), II->getUnwindDest(), {}, "", II->getParent());3827      NewII->setDebugLoc(II->getDebugLoc());3828    }3829 3830    // Remove debug intrinsics which describe the value contained within the3831    // alloca. In addition to removing dbg.{declare,addr} which simply point to3832    // the alloca, remove dbg.value(<alloca>, ..., DW_OP_deref)'s as well, e.g.:3833    //3834    // ```3835    //   define void @foo(i32 %0) {3836    //     %a = alloca i32                              ; Deleted.3837    //     store i32 %0, i32* %a3838    //     dbg.value(i32 %0, "arg0")                    ; Not deleted.3839    //     dbg.value(i32* %a, "arg0", DW_OP_deref)      ; Deleted.3840    //     call void @trivially_inlinable_no_op(i32* %a)3841    //     ret void3842    //  }3843    // ```3844    //3845    // This may not be required if we stop describing the contents of allocas3846    // using dbg.value(<alloca>, ..., DW_OP_deref), but we currently do this in3847    // the LowerDbgDeclare utility.3848    //3849    // If there is a dead store to `%a` in @trivially_inlinable_no_op, the3850    // "arg0" dbg.value may be stale after the call. However, failing to remove3851    // the DW_OP_deref dbg.value causes large gaps in location coverage.3852    //3853    // FIXME: the Assignment Tracking project has now likely made this3854    // redundant (and it's sometimes harmful).3855    for (auto *DVR : DVRs)3856      if (DVR->isAddressOfVariable() || DVR->getExpression()->startsWithDeref())3857        DVR->eraseFromParent();3858 3859    return eraseInstFromFunction(MI);3860  }3861  return nullptr;3862}3863 3864/// Move the call to free before a NULL test.3865///3866/// Check if this free is accessed after its argument has been test3867/// against NULL (property 0).3868/// If yes, it is legal to move this call in its predecessor block.3869///3870/// The move is performed only if the block containing the call to free3871/// will be removed, i.e.:3872/// 1. it has only one predecessor P, and P has two successors3873/// 2. it contains the call, noops, and an unconditional branch3874/// 3. its successor is the same as its predecessor's successor3875///3876/// The profitability is out-of concern here and this function should3877/// be called only if the caller knows this transformation would be3878/// profitable (e.g., for code size).3879static Instruction *tryToMoveFreeBeforeNullTest(CallInst &FI,3880                                                const DataLayout &DL) {3881  Value *Op = FI.getArgOperand(0);3882  BasicBlock *FreeInstrBB = FI.getParent();3883  BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor();3884 3885  // Validate part of constraint #1: Only one predecessor3886  // FIXME: We can extend the number of predecessor, but in that case, we3887  //        would duplicate the call to free in each predecessor and it may3888  //        not be profitable even for code size.3889  if (!PredBB)3890    return nullptr;3891 3892  // Validate constraint #2: Does this block contains only the call to3893  //                         free, noops, and an unconditional branch?3894  BasicBlock *SuccBB;3895  Instruction *FreeInstrBBTerminator = FreeInstrBB->getTerminator();3896  if (!match(FreeInstrBBTerminator, m_UnconditionalBr(SuccBB)))3897    return nullptr;3898 3899  // If there are only 2 instructions in the block, at this point,3900  // this is the call to free and unconditional.3901  // If there are more than 2 instructions, check that they are noops3902  // i.e., they won't hurt the performance of the generated code.3903  if (FreeInstrBB->size() != 2) {3904    for (const Instruction &Inst : FreeInstrBB->instructionsWithoutDebug()) {3905      if (&Inst == &FI || &Inst == FreeInstrBBTerminator)3906        continue;3907      auto *Cast = dyn_cast<CastInst>(&Inst);3908      if (!Cast || !Cast->isNoopCast(DL))3909        return nullptr;3910    }3911  }3912  // Validate the rest of constraint #1 by matching on the pred branch.3913  Instruction *TI = PredBB->getTerminator();3914  BasicBlock *TrueBB, *FalseBB;3915  CmpPredicate Pred;3916  if (!match(TI, m_Br(m_ICmp(Pred,3917                             m_CombineOr(m_Specific(Op),3918                                         m_Specific(Op->stripPointerCasts())),3919                             m_Zero()),3920                      TrueBB, FalseBB)))3921    return nullptr;3922  if (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE)3923    return nullptr;3924 3925  // Validate constraint #3: Ensure the null case just falls through.3926  if (SuccBB != (Pred == ICmpInst::ICMP_EQ ? TrueBB : FalseBB))3927    return nullptr;3928  assert(FreeInstrBB == (Pred == ICmpInst::ICMP_EQ ? FalseBB : TrueBB) &&3929         "Broken CFG: missing edge from predecessor to successor");3930 3931  // At this point, we know that everything in FreeInstrBB can be moved3932  // before TI.3933  for (Instruction &Instr : llvm::make_early_inc_range(*FreeInstrBB)) {3934    if (&Instr == FreeInstrBBTerminator)3935      break;3936    Instr.moveBeforePreserving(TI->getIterator());3937  }3938  assert(FreeInstrBB->size() == 1 &&3939         "Only the branch instruction should remain");3940 3941  // Now that we've moved the call to free before the NULL check, we have to3942  // remove any attributes on its parameter that imply it's non-null, because3943  // those attributes might have only been valid because of the NULL check, and3944  // we can get miscompiles if we keep them. This is conservative if non-null is3945  // also implied by something other than the NULL check, but it's guaranteed to3946  // be correct, and the conservativeness won't matter in practice, since the3947  // attributes are irrelevant for the call to free itself and the pointer3948  // shouldn't be used after the call.3949  AttributeList Attrs = FI.getAttributes();3950  Attrs = Attrs.removeParamAttribute(FI.getContext(), 0, Attribute::NonNull);3951  Attribute Dereferenceable = Attrs.getParamAttr(0, Attribute::Dereferenceable);3952  if (Dereferenceable.isValid()) {3953    uint64_t Bytes = Dereferenceable.getDereferenceableBytes();3954    Attrs = Attrs.removeParamAttribute(FI.getContext(), 0,3955                                       Attribute::Dereferenceable);3956    Attrs = Attrs.addDereferenceableOrNullParamAttr(FI.getContext(), 0, Bytes);3957  }3958  FI.setAttributes(Attrs);3959 3960  return &FI;3961}3962 3963Instruction *InstCombinerImpl::visitFree(CallInst &FI, Value *Op) {3964  // free undef -> unreachable.3965  if (isa<UndefValue>(Op)) {3966    // Leave a marker since we can't modify the CFG here.3967    CreateNonTerminatorUnreachable(&FI);3968    return eraseInstFromFunction(FI);3969  }3970 3971  // If we have 'free null' delete the instruction.  This can happen in stl code3972  // when lots of inlining happens.3973  if (isa<ConstantPointerNull>(Op))3974    return eraseInstFromFunction(FI);3975 3976  // If we had free(realloc(...)) with no intervening uses, then eliminate the3977  // realloc() entirely.3978  CallInst *CI = dyn_cast<CallInst>(Op);3979  if (CI && CI->hasOneUse())3980    if (Value *ReallocatedOp = getReallocatedOperand(CI))3981      return eraseInstFromFunction(*replaceInstUsesWith(*CI, ReallocatedOp));3982 3983  // If we optimize for code size, try to move the call to free before the null3984  // test so that simplify cfg can remove the empty block and dead code3985  // elimination the branch. I.e., helps to turn something like:3986  // if (foo) free(foo);3987  // into3988  // free(foo);3989  //3990  // Note that we can only do this for 'free' and not for any flavor of3991  // 'operator delete'; there is no 'operator delete' symbol for which we are3992  // permitted to invent a call, even if we're passing in a null pointer.3993  if (MinimizeSize) {3994    LibFunc Func;3995    if (TLI.getLibFunc(FI, Func) && TLI.has(Func) && Func == LibFunc_free)3996      if (Instruction *I = tryToMoveFreeBeforeNullTest(FI, DL))3997        return I;3998  }3999 4000  return nullptr;4001}4002 4003Instruction *InstCombinerImpl::visitReturnInst(ReturnInst &RI) {4004  Value *RetVal = RI.getReturnValue();4005  if (!RetVal)4006    return nullptr;4007 4008  Function *F = RI.getFunction();4009  Type *RetTy = RetVal->getType();4010  if (RetTy->isPointerTy()) {4011    bool HasDereferenceable =4012        F->getAttributes().getRetDereferenceableBytes() > 0;4013    if (F->hasRetAttribute(Attribute::NonNull) ||4014        (HasDereferenceable &&4015         !NullPointerIsDefined(F, RetTy->getPointerAddressSpace()))) {4016      if (Value *V = simplifyNonNullOperand(RetVal, HasDereferenceable))4017        return replaceOperand(RI, 0, V);4018    }4019  }4020 4021  if (!AttributeFuncs::isNoFPClassCompatibleType(RetTy))4022    return nullptr;4023 4024  FPClassTest ReturnClass = F->getAttributes().getRetNoFPClass();4025  if (ReturnClass == fcNone)4026    return nullptr;4027 4028  KnownFPClass KnownClass;4029  Value *Simplified =4030      SimplifyDemandedUseFPClass(RetVal, ~ReturnClass, KnownClass, &RI);4031  if (!Simplified)4032    return nullptr;4033 4034  return ReturnInst::Create(RI.getContext(), Simplified);4035}4036 4037// WARNING: keep in sync with SimplifyCFGOpt::simplifyUnreachable()!4038bool InstCombinerImpl::removeInstructionsBeforeUnreachable(Instruction &I) {4039  // Try to remove the previous instruction if it must lead to unreachable.4040  // This includes instructions like stores and "llvm.assume" that may not get4041  // removed by simple dead code elimination.4042  bool Changed = false;4043  while (Instruction *Prev = I.getPrevNode()) {4044    // While we theoretically can erase EH, that would result in a block that4045    // used to start with an EH no longer starting with EH, which is invalid.4046    // To make it valid, we'd need to fixup predecessors to no longer refer to4047    // this block, but that changes CFG, which is not allowed in InstCombine.4048    if (Prev->isEHPad())4049      break; // Can not drop any more instructions. We're done here.4050 4051    if (!isGuaranteedToTransferExecutionToSuccessor(Prev))4052      break; // Can not drop any more instructions. We're done here.4053    // Otherwise, this instruction can be freely erased,4054    // even if it is not side-effect free.4055 4056    // A value may still have uses before we process it here (for example, in4057    // another unreachable block), so convert those to poison.4058    replaceInstUsesWith(*Prev, PoisonValue::get(Prev->getType()));4059    eraseInstFromFunction(*Prev);4060    Changed = true;4061  }4062  return Changed;4063}4064 4065Instruction *InstCombinerImpl::visitUnreachableInst(UnreachableInst &I) {4066  removeInstructionsBeforeUnreachable(I);4067  return nullptr;4068}4069 4070Instruction *InstCombinerImpl::visitUnconditionalBranchInst(BranchInst &BI) {4071  assert(BI.isUnconditional() && "Only for unconditional branches.");4072 4073  // If this store is the second-to-last instruction in the basic block4074  // (excluding debug info) and if the block ends with4075  // an unconditional branch, try to move the store to the successor block.4076 4077  auto GetLastSinkableStore = [](BasicBlock::iterator BBI) {4078    BasicBlock::iterator FirstInstr = BBI->getParent()->begin();4079    do {4080      if (BBI != FirstInstr)4081        --BBI;4082    } while (BBI != FirstInstr && BBI->isDebugOrPseudoInst());4083 4084    return dyn_cast<StoreInst>(BBI);4085  };4086 4087  if (StoreInst *SI = GetLastSinkableStore(BasicBlock::iterator(BI)))4088    if (mergeStoreIntoSuccessor(*SI))4089      return &BI;4090 4091  return nullptr;4092}4093 4094void InstCombinerImpl::addDeadEdge(BasicBlock *From, BasicBlock *To,4095                                   SmallVectorImpl<BasicBlock *> &Worklist) {4096  if (!DeadEdges.insert({From, To}).second)4097    return;4098 4099  // Replace phi node operands in successor with poison.4100  for (PHINode &PN : To->phis())4101    for (Use &U : PN.incoming_values())4102      if (PN.getIncomingBlock(U) == From && !isa<PoisonValue>(U)) {4103        replaceUse(U, PoisonValue::get(PN.getType()));4104        addToWorklist(&PN);4105        MadeIRChange = true;4106      }4107 4108  Worklist.push_back(To);4109}4110 4111// Under the assumption that I is unreachable, remove it and following4112// instructions. Changes are reported directly to MadeIRChange.4113void InstCombinerImpl::handleUnreachableFrom(4114    Instruction *I, SmallVectorImpl<BasicBlock *> &Worklist) {4115  BasicBlock *BB = I->getParent();4116  for (Instruction &Inst : make_early_inc_range(4117           make_range(std::next(BB->getTerminator()->getReverseIterator()),4118                      std::next(I->getReverseIterator())))) {4119    if (!Inst.use_empty() && !Inst.getType()->isTokenTy()) {4120      replaceInstUsesWith(Inst, PoisonValue::get(Inst.getType()));4121      MadeIRChange = true;4122    }4123    if (Inst.isEHPad() || Inst.getType()->isTokenTy())4124      continue;4125    // RemoveDIs: erase debug-info on this instruction manually.4126    Inst.dropDbgRecords();4127    eraseInstFromFunction(Inst);4128    MadeIRChange = true;4129  }4130 4131  SmallVector<Value *> Changed;4132  if (handleUnreachableTerminator(BB->getTerminator(), Changed)) {4133    MadeIRChange = true;4134    for (Value *V : Changed)4135      addToWorklist(cast<Instruction>(V));4136  }4137 4138  // Handle potentially dead successors.4139  for (BasicBlock *Succ : successors(BB))4140    addDeadEdge(BB, Succ, Worklist);4141}4142 4143void InstCombinerImpl::handlePotentiallyDeadBlocks(4144    SmallVectorImpl<BasicBlock *> &Worklist) {4145  while (!Worklist.empty()) {4146    BasicBlock *BB = Worklist.pop_back_val();4147    if (!all_of(predecessors(BB), [&](BasicBlock *Pred) {4148          return DeadEdges.contains({Pred, BB}) || DT.dominates(BB, Pred);4149        }))4150      continue;4151 4152    handleUnreachableFrom(&BB->front(), Worklist);4153  }4154}4155 4156void InstCombinerImpl::handlePotentiallyDeadSuccessors(BasicBlock *BB,4157                                                       BasicBlock *LiveSucc) {4158  SmallVector<BasicBlock *> Worklist;4159  for (BasicBlock *Succ : successors(BB)) {4160    // The live successor isn't dead.4161    if (Succ == LiveSucc)4162      continue;4163 4164    addDeadEdge(BB, Succ, Worklist);4165  }4166 4167  handlePotentiallyDeadBlocks(Worklist);4168}4169 4170Instruction *InstCombinerImpl::visitBranchInst(BranchInst &BI) {4171  if (BI.isUnconditional())4172    return visitUnconditionalBranchInst(BI);4173 4174  // Change br (not X), label True, label False to: br X, label False, True4175  Value *Cond = BI.getCondition();4176  Value *X;4177  if (match(Cond, m_Not(m_Value(X))) && !isa<Constant>(X)) {4178    // Swap Destinations and condition...4179    BI.swapSuccessors();4180    if (BPI)4181      BPI->swapSuccEdgesProbabilities(BI.getParent());4182    return replaceOperand(BI, 0, X);4183  }4184 4185  // Canonicalize logical-and-with-invert as logical-or-with-invert.4186  // This is done by inverting the condition and swapping successors:4187  // br (X && !Y), T, F --> br !(X && !Y), F, T --> br (!X || Y), F, T4188  Value *Y;4189  if (isa<SelectInst>(Cond) &&4190      match(Cond,4191            m_OneUse(m_LogicalAnd(m_Value(X), m_OneUse(m_Not(m_Value(Y))))))) {4192    Value *NotX = Builder.CreateNot(X, "not." + X->getName());4193    Value *Or = Builder.CreateLogicalOr(NotX, Y);4194    BI.swapSuccessors();4195    if (BPI)4196      BPI->swapSuccEdgesProbabilities(BI.getParent());4197    return replaceOperand(BI, 0, Or);4198  }4199 4200  // If the condition is irrelevant, remove the use so that other4201  // transforms on the condition become more effective.4202  if (!isa<ConstantInt>(Cond) && BI.getSuccessor(0) == BI.getSuccessor(1))4203    return replaceOperand(BI, 0, ConstantInt::getFalse(Cond->getType()));4204 4205  // Canonicalize, for example, fcmp_one -> fcmp_oeq.4206  CmpPredicate Pred;4207  if (match(Cond, m_OneUse(m_FCmp(Pred, m_Value(), m_Value()))) &&4208      !isCanonicalPredicate(Pred)) {4209    // Swap destinations and condition.4210    auto *Cmp = cast<CmpInst>(Cond);4211    Cmp->setPredicate(CmpInst::getInversePredicate(Pred));4212    BI.swapSuccessors();4213    if (BPI)4214      BPI->swapSuccEdgesProbabilities(BI.getParent());4215    Worklist.push(Cmp);4216    return &BI;4217  }4218 4219  if (isa<UndefValue>(Cond)) {4220    handlePotentiallyDeadSuccessors(BI.getParent(), /*LiveSucc*/ nullptr);4221    return nullptr;4222  }4223  if (auto *CI = dyn_cast<ConstantInt>(Cond)) {4224    handlePotentiallyDeadSuccessors(BI.getParent(),4225                                    BI.getSuccessor(!CI->getZExtValue()));4226    return nullptr;4227  }4228 4229  // Replace all dominated uses of the condition with true/false4230  // Ignore constant expressions to avoid iterating over uses on other4231  // functions.4232  if (!isa<Constant>(Cond) && BI.getSuccessor(0) != BI.getSuccessor(1)) {4233    for (auto &U : make_early_inc_range(Cond->uses())) {4234      BasicBlockEdge Edge0(BI.getParent(), BI.getSuccessor(0));4235      if (DT.dominates(Edge0, U)) {4236        replaceUse(U, ConstantInt::getTrue(Cond->getType()));4237        addToWorklist(cast<Instruction>(U.getUser()));4238        continue;4239      }4240      BasicBlockEdge Edge1(BI.getParent(), BI.getSuccessor(1));4241      if (DT.dominates(Edge1, U)) {4242        replaceUse(U, ConstantInt::getFalse(Cond->getType()));4243        addToWorklist(cast<Instruction>(U.getUser()));4244      }4245    }4246  }4247 4248  DC.registerBranch(&BI);4249  return nullptr;4250}4251 4252// Replaces (switch (select cond, X, C)/(select cond, C, X)) with (switch X) if4253// we can prove that both (switch C) and (switch X) go to the default when cond4254// is false/true.4255static Value *simplifySwitchOnSelectUsingRanges(SwitchInst &SI,4256                                                SelectInst *Select,4257                                                bool IsTrueArm) {4258  unsigned CstOpIdx = IsTrueArm ? 1 : 2;4259  auto *C = dyn_cast<ConstantInt>(Select->getOperand(CstOpIdx));4260  if (!C)4261    return nullptr;4262 4263  BasicBlock *CstBB = SI.findCaseValue(C)->getCaseSuccessor();4264  if (CstBB != SI.getDefaultDest())4265    return nullptr;4266  Value *X = Select->getOperand(3 - CstOpIdx);4267  CmpPredicate Pred;4268  const APInt *RHSC;4269  if (!match(Select->getCondition(),4270             m_ICmp(Pred, m_Specific(X), m_APInt(RHSC))))4271    return nullptr;4272  if (IsTrueArm)4273    Pred = ICmpInst::getInversePredicate(Pred);4274 4275  // See whether we can replace the select with X4276  ConstantRange CR = ConstantRange::makeExactICmpRegion(Pred, *RHSC);4277  for (auto Case : SI.cases())4278    if (!CR.contains(Case.getCaseValue()->getValue()))4279      return nullptr;4280 4281  return X;4282}4283 4284Instruction *InstCombinerImpl::visitSwitchInst(SwitchInst &SI) {4285  Value *Cond = SI.getCondition();4286  Value *Op0;4287  ConstantInt *AddRHS;4288  if (match(Cond, m_Add(m_Value(Op0), m_ConstantInt(AddRHS)))) {4289    // Change 'switch (X+4) case 1:' into 'switch (X) case -3'.4290    for (auto Case : SI.cases()) {4291      Constant *NewCase = ConstantExpr::getSub(Case.getCaseValue(), AddRHS);4292      assert(isa<ConstantInt>(NewCase) &&4293             "Result of expression should be constant");4294      Case.setValue(cast<ConstantInt>(NewCase));4295    }4296    return replaceOperand(SI, 0, Op0);4297  }4298 4299  ConstantInt *SubLHS;4300  if (match(Cond, m_Sub(m_ConstantInt(SubLHS), m_Value(Op0)))) {4301    // Change 'switch (1-X) case 1:' into 'switch (X) case 0'.4302    for (auto Case : SI.cases()) {4303      Constant *NewCase = ConstantExpr::getSub(SubLHS, Case.getCaseValue());4304      assert(isa<ConstantInt>(NewCase) &&4305             "Result of expression should be constant");4306      Case.setValue(cast<ConstantInt>(NewCase));4307    }4308    return replaceOperand(SI, 0, Op0);4309  }4310 4311  uint64_t ShiftAmt;4312  if (match(Cond, m_Shl(m_Value(Op0), m_ConstantInt(ShiftAmt))) &&4313      ShiftAmt < Op0->getType()->getScalarSizeInBits() &&4314      all_of(SI.cases(), [&](const auto &Case) {4315        return Case.getCaseValue()->getValue().countr_zero() >= ShiftAmt;4316      })) {4317    // Change 'switch (X << 2) case 4:' into 'switch (X) case 1:'.4318    OverflowingBinaryOperator *Shl = cast<OverflowingBinaryOperator>(Cond);4319    if (Shl->hasNoUnsignedWrap() || Shl->hasNoSignedWrap() ||4320        Shl->hasOneUse()) {4321      Value *NewCond = Op0;4322      if (!Shl->hasNoUnsignedWrap() && !Shl->hasNoSignedWrap()) {4323        // If the shift may wrap, we need to mask off the shifted bits.4324        unsigned BitWidth = Op0->getType()->getScalarSizeInBits();4325        NewCond = Builder.CreateAnd(4326            Op0, APInt::getLowBitsSet(BitWidth, BitWidth - ShiftAmt));4327      }4328      for (auto Case : SI.cases()) {4329        const APInt &CaseVal = Case.getCaseValue()->getValue();4330        APInt ShiftedCase = Shl->hasNoSignedWrap() ? CaseVal.ashr(ShiftAmt)4331                                                   : CaseVal.lshr(ShiftAmt);4332        Case.setValue(ConstantInt::get(SI.getContext(), ShiftedCase));4333      }4334      return replaceOperand(SI, 0, NewCond);4335    }4336  }4337 4338  // Fold switch(zext/sext(X)) into switch(X) if possible.4339  if (match(Cond, m_ZExtOrSExt(m_Value(Op0)))) {4340    bool IsZExt = isa<ZExtInst>(Cond);4341    Type *SrcTy = Op0->getType();4342    unsigned NewWidth = SrcTy->getScalarSizeInBits();4343 4344    if (all_of(SI.cases(), [&](const auto &Case) {4345          const APInt &CaseVal = Case.getCaseValue()->getValue();4346          return IsZExt ? CaseVal.isIntN(NewWidth)4347                        : CaseVal.isSignedIntN(NewWidth);4348        })) {4349      for (auto &Case : SI.cases()) {4350        APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);4351        Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));4352      }4353      return replaceOperand(SI, 0, Op0);4354    }4355  }4356 4357  // Fold switch(select cond, X, Y) into switch(X/Y) if possible4358  if (auto *Select = dyn_cast<SelectInst>(Cond)) {4359    if (Value *V =4360            simplifySwitchOnSelectUsingRanges(SI, Select, /*IsTrueArm=*/true))4361      return replaceOperand(SI, 0, V);4362    if (Value *V =4363            simplifySwitchOnSelectUsingRanges(SI, Select, /*IsTrueArm=*/false))4364      return replaceOperand(SI, 0, V);4365  }4366 4367  KnownBits Known = computeKnownBits(Cond, &SI);4368  unsigned LeadingKnownZeros = Known.countMinLeadingZeros();4369  unsigned LeadingKnownOnes = Known.countMinLeadingOnes();4370 4371  // Compute the number of leading bits we can ignore.4372  // TODO: A better way to determine this would use ComputeNumSignBits().4373  for (const auto &C : SI.cases()) {4374    LeadingKnownZeros =4375        std::min(LeadingKnownZeros, C.getCaseValue()->getValue().countl_zero());4376    LeadingKnownOnes =4377        std::min(LeadingKnownOnes, C.getCaseValue()->getValue().countl_one());4378  }4379 4380  unsigned NewWidth = Known.getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes);4381 4382  // Shrink the condition operand if the new type is smaller than the old type.4383  // But do not shrink to a non-standard type, because backend can't generate4384  // good code for that yet.4385  // TODO: We can make it aggressive again after fixing PR39569.4386  if (NewWidth > 0 && NewWidth < Known.getBitWidth() &&4387      shouldChangeType(Known.getBitWidth(), NewWidth)) {4388    IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth);4389    Builder.SetInsertPoint(&SI);4390    Value *NewCond = Builder.CreateTrunc(Cond, Ty, "trunc");4391 4392    for (auto Case : SI.cases()) {4393      APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);4394      Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));4395    }4396    return replaceOperand(SI, 0, NewCond);4397  }4398 4399  if (isa<UndefValue>(Cond)) {4400    handlePotentiallyDeadSuccessors(SI.getParent(), /*LiveSucc*/ nullptr);4401    return nullptr;4402  }4403  if (auto *CI = dyn_cast<ConstantInt>(Cond)) {4404    handlePotentiallyDeadSuccessors(SI.getParent(),4405                                    SI.findCaseValue(CI)->getCaseSuccessor());4406    return nullptr;4407  }4408 4409  return nullptr;4410}4411 4412Instruction *4413InstCombinerImpl::foldExtractOfOverflowIntrinsic(ExtractValueInst &EV) {4414  auto *WO = dyn_cast<WithOverflowInst>(EV.getAggregateOperand());4415  if (!WO)4416    return nullptr;4417 4418  Intrinsic::ID OvID = WO->getIntrinsicID();4419  const APInt *C = nullptr;4420  if (match(WO->getRHS(), m_APIntAllowPoison(C))) {4421    if (*EV.idx_begin() == 0 && (OvID == Intrinsic::smul_with_overflow ||4422                                 OvID == Intrinsic::umul_with_overflow)) {4423      // extractvalue (any_mul_with_overflow X, -1), 0 --> -X4424      if (C->isAllOnes())4425        return BinaryOperator::CreateNeg(WO->getLHS());4426      // extractvalue (any_mul_with_overflow X, 2^n), 0 --> X << n4427      if (C->isPowerOf2()) {4428        return BinaryOperator::CreateShl(4429            WO->getLHS(),4430            ConstantInt::get(WO->getLHS()->getType(), C->logBase2()));4431      }4432    }4433  }4434 4435  // We're extracting from an overflow intrinsic. See if we're the only user.4436  // That allows us to simplify multiple result intrinsics to simpler things4437  // that just get one value.4438  if (!WO->hasOneUse())4439    return nullptr;4440 4441  // Check if we're grabbing only the result of a 'with overflow' intrinsic4442  // and replace it with a traditional binary instruction.4443  if (*EV.idx_begin() == 0) {4444    Instruction::BinaryOps BinOp = WO->getBinaryOp();4445    Value *LHS = WO->getLHS(), *RHS = WO->getRHS();4446    // Replace the old instruction's uses with poison.4447    replaceInstUsesWith(*WO, PoisonValue::get(WO->getType()));4448    eraseInstFromFunction(*WO);4449    return BinaryOperator::Create(BinOp, LHS, RHS);4450  }4451 4452  assert(*EV.idx_begin() == 1 && "Unexpected extract index for overflow inst");4453 4454  // (usub LHS, RHS) overflows when LHS is unsigned-less-than RHS.4455  if (OvID == Intrinsic::usub_with_overflow)4456    return new ICmpInst(ICmpInst::ICMP_ULT, WO->getLHS(), WO->getRHS());4457 4458  // smul with i1 types overflows when both sides are set: -1 * -1 == +1, but4459  // +1 is not possible because we assume signed values.4460  if (OvID == Intrinsic::smul_with_overflow &&4461      WO->getLHS()->getType()->isIntOrIntVectorTy(1))4462    return BinaryOperator::CreateAnd(WO->getLHS(), WO->getRHS());4463 4464  // extractvalue (umul_with_overflow X, X), 1 -> X u> 2^(N/2)-14465  if (OvID == Intrinsic::umul_with_overflow && WO->getLHS() == WO->getRHS()) {4466    unsigned BitWidth = WO->getLHS()->getType()->getScalarSizeInBits();4467    // Only handle even bitwidths for performance reasons.4468    if (BitWidth % 2 == 0)4469      return new ICmpInst(4470          ICmpInst::ICMP_UGT, WO->getLHS(),4471          ConstantInt::get(WO->getLHS()->getType(),4472                           APInt::getLowBitsSet(BitWidth, BitWidth / 2)));4473  }4474 4475  // If only the overflow result is used, and the right hand side is a4476  // constant (or constant splat), we can remove the intrinsic by directly4477  // checking for overflow.4478  if (C) {4479    // Compute the no-wrap range for LHS given RHS=C, then construct an4480    // equivalent icmp, potentially using an offset.4481    ConstantRange NWR = ConstantRange::makeExactNoWrapRegion(4482        WO->getBinaryOp(), *C, WO->getNoWrapKind());4483 4484    CmpInst::Predicate Pred;4485    APInt NewRHSC, Offset;4486    NWR.getEquivalentICmp(Pred, NewRHSC, Offset);4487    auto *OpTy = WO->getRHS()->getType();4488    auto *NewLHS = WO->getLHS();4489    if (Offset != 0)4490      NewLHS = Builder.CreateAdd(NewLHS, ConstantInt::get(OpTy, Offset));4491    return new ICmpInst(ICmpInst::getInversePredicate(Pred), NewLHS,4492                        ConstantInt::get(OpTy, NewRHSC));4493  }4494 4495  return nullptr;4496}4497 4498static Value *foldFrexpOfSelect(ExtractValueInst &EV, IntrinsicInst *FrexpCall,4499                                SelectInst *SelectInst,4500                                InstCombiner::BuilderTy &Builder) {4501  // Helper to fold frexp of select to select of frexp.4502 4503  if (!SelectInst->hasOneUse() || !FrexpCall->hasOneUse())4504    return nullptr;4505  Value *Cond = SelectInst->getCondition();4506  Value *TrueVal = SelectInst->getTrueValue();4507  Value *FalseVal = SelectInst->getFalseValue();4508 4509  const APFloat *ConstVal = nullptr;4510  Value *VarOp = nullptr;4511  bool ConstIsTrue = false;4512 4513  if (match(TrueVal, m_APFloat(ConstVal))) {4514    VarOp = FalseVal;4515    ConstIsTrue = true;4516  } else if (match(FalseVal, m_APFloat(ConstVal))) {4517    VarOp = TrueVal;4518    ConstIsTrue = false;4519  } else {4520    return nullptr;4521  }4522 4523  Builder.SetInsertPoint(&EV);4524 4525  CallInst *NewFrexp =4526      Builder.CreateCall(FrexpCall->getCalledFunction(), {VarOp}, "frexp");4527  NewFrexp->copyIRFlags(FrexpCall);4528 4529  Value *NewEV = Builder.CreateExtractValue(NewFrexp, 0, "mantissa");4530 4531  int Exp;4532  APFloat Mantissa = frexp(*ConstVal, Exp, APFloat::rmNearestTiesToEven);4533 4534  Constant *ConstantMantissa = ConstantFP::get(TrueVal->getType(), Mantissa);4535 4536  Value *NewSel = Builder.CreateSelectFMF(4537      Cond, ConstIsTrue ? ConstantMantissa : NewEV,4538      ConstIsTrue ? NewEV : ConstantMantissa, SelectInst, "select.frexp");4539  return NewSel;4540}4541Instruction *InstCombinerImpl::visitExtractValueInst(ExtractValueInst &EV) {4542  Value *Agg = EV.getAggregateOperand();4543 4544  if (!EV.hasIndices())4545    return replaceInstUsesWith(EV, Agg);4546 4547  if (Value *V = simplifyExtractValueInst(Agg, EV.getIndices(),4548                                          SQ.getWithInstruction(&EV)))4549    return replaceInstUsesWith(EV, V);4550 4551  Value *Cond, *TrueVal, *FalseVal;4552  if (match(&EV, m_ExtractValue<0>(m_Intrinsic<Intrinsic::frexp>(m_Select(4553                     m_Value(Cond), m_Value(TrueVal), m_Value(FalseVal)))))) {4554    auto *SelInst =4555        cast<SelectInst>(cast<IntrinsicInst>(Agg)->getArgOperand(0));4556    if (Value *Result =4557            foldFrexpOfSelect(EV, cast<IntrinsicInst>(Agg), SelInst, Builder))4558      return replaceInstUsesWith(EV, Result);4559  }4560  if (InsertValueInst *IV = dyn_cast<InsertValueInst>(Agg)) {4561    // We're extracting from an insertvalue instruction, compare the indices4562    const unsigned *exti, *exte, *insi, *inse;4563    for (exti = EV.idx_begin(), insi = IV->idx_begin(),4564         exte = EV.idx_end(), inse = IV->idx_end();4565         exti != exte && insi != inse;4566         ++exti, ++insi) {4567      if (*insi != *exti)4568        // The insert and extract both reference distinctly different elements.4569        // This means the extract is not influenced by the insert, and we can4570        // replace the aggregate operand of the extract with the aggregate4571        // operand of the insert. i.e., replace4572        // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 14573        // %E = extractvalue { i32, { i32 } } %I, 04574        // with4575        // %E = extractvalue { i32, { i32 } } %A, 04576        return ExtractValueInst::Create(IV->getAggregateOperand(),4577                                        EV.getIndices());4578    }4579    if (exti == exte && insi == inse)4580      // Both iterators are at the end: Index lists are identical. Replace4581      // %B = insertvalue { i32, { i32 } } %A, i32 42, 1, 04582      // %C = extractvalue { i32, { i32 } } %B, 1, 04583      // with "i32 42"4584      return replaceInstUsesWith(EV, IV->getInsertedValueOperand());4585    if (exti == exte) {4586      // The extract list is a prefix of the insert list. i.e. replace4587      // %I = insertvalue { i32, { i32 } } %A, i32 42, 1, 04588      // %E = extractvalue { i32, { i32 } } %I, 14589      // with4590      // %X = extractvalue { i32, { i32 } } %A, 14591      // %E = insertvalue { i32 } %X, i32 42, 04592      // by switching the order of the insert and extract (though the4593      // insertvalue should be left in, since it may have other uses).4594      Value *NewEV = Builder.CreateExtractValue(IV->getAggregateOperand(),4595                                                EV.getIndices());4596      return InsertValueInst::Create(NewEV, IV->getInsertedValueOperand(),4597                                     ArrayRef(insi, inse));4598    }4599    if (insi == inse)4600      // The insert list is a prefix of the extract list4601      // We can simply remove the common indices from the extract and make it4602      // operate on the inserted value instead of the insertvalue result.4603      // i.e., replace4604      // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 14605      // %E = extractvalue { i32, { i32 } } %I, 1, 04606      // with4607      // %E extractvalue { i32 } { i32 42 }, 04608      return ExtractValueInst::Create(IV->getInsertedValueOperand(),4609                                      ArrayRef(exti, exte));4610  }4611 4612  if (Instruction *R = foldExtractOfOverflowIntrinsic(EV))4613    return R;4614 4615  if (LoadInst *L = dyn_cast<LoadInst>(Agg)) {4616    // Bail out if the aggregate contains scalable vector type4617    if (auto *STy = dyn_cast<StructType>(Agg->getType());4618        STy && STy->isScalableTy())4619      return nullptr;4620 4621    // If the (non-volatile) load only has one use, we can rewrite this to a4622    // load from a GEP. This reduces the size of the load. If a load is used4623    // only by extractvalue instructions then this either must have been4624    // optimized before, or it is a struct with padding, in which case we4625    // don't want to do the transformation as it loses padding knowledge.4626    if (L->isSimple() && L->hasOneUse()) {4627      // extractvalue has integer indices, getelementptr has Value*s. Convert.4628      SmallVector<Value*, 4> Indices;4629      // Prefix an i32 0 since we need the first element.4630      Indices.push_back(Builder.getInt32(0));4631      for (unsigned Idx : EV.indices())4632        Indices.push_back(Builder.getInt32(Idx));4633 4634      // We need to insert these at the location of the old load, not at that of4635      // the extractvalue.4636      Builder.SetInsertPoint(L);4637      Value *GEP = Builder.CreateInBoundsGEP(L->getType(),4638                                             L->getPointerOperand(), Indices);4639      Instruction *NL = Builder.CreateLoad(EV.getType(), GEP);4640      // Whatever aliasing information we had for the orignal load must also4641      // hold for the smaller load, so propagate the annotations.4642      NL->setAAMetadata(L->getAAMetadata());4643      // Returning the load directly will cause the main loop to insert it in4644      // the wrong spot, so use replaceInstUsesWith().4645      return replaceInstUsesWith(EV, NL);4646    }4647  }4648 4649  if (auto *PN = dyn_cast<PHINode>(Agg))4650    if (Instruction *Res = foldOpIntoPhi(EV, PN))4651      return Res;4652 4653  // Canonicalize extract (select Cond, TV, FV)4654  // -> select cond, (extract TV), (extract FV)4655  if (auto *SI = dyn_cast<SelectInst>(Agg))4656    if (Instruction *R = FoldOpIntoSelect(EV, SI, /*FoldWithMultiUse=*/true))4657      return R;4658 4659  // We could simplify extracts from other values. Note that nested extracts may4660  // already be simplified implicitly by the above: extract (extract (insert) )4661  // will be translated into extract ( insert ( extract ) ) first and then just4662  // the value inserted, if appropriate. Similarly for extracts from single-use4663  // loads: extract (extract (load)) will be translated to extract (load (gep))4664  // and if again single-use then via load (gep (gep)) to load (gep).4665  // However, double extracts from e.g. function arguments or return values4666  // aren't handled yet.4667  return nullptr;4668}4669 4670/// Return 'true' if the given typeinfo will match anything.4671static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo) {4672  switch (Personality) {4673  case EHPersonality::GNU_C:4674  case EHPersonality::GNU_C_SjLj:4675  case EHPersonality::Rust:4676    // The GCC C EH and Rust personality only exists to support cleanups, so4677    // it's not clear what the semantics of catch clauses are.4678    return false;4679  case EHPersonality::Unknown:4680    return false;4681  case EHPersonality::GNU_Ada:4682    // While __gnat_all_others_value will match any Ada exception, it doesn't4683    // match foreign exceptions (or didn't, before gcc-4.7).4684    return false;4685  case EHPersonality::GNU_CXX:4686  case EHPersonality::GNU_CXX_SjLj:4687  case EHPersonality::GNU_ObjC:4688  case EHPersonality::MSVC_X86SEH:4689  case EHPersonality::MSVC_TableSEH:4690  case EHPersonality::MSVC_CXX:4691  case EHPersonality::CoreCLR:4692  case EHPersonality::Wasm_CXX:4693  case EHPersonality::XL_CXX:4694  case EHPersonality::ZOS_CXX:4695    return TypeInfo->isNullValue();4696  }4697  llvm_unreachable("invalid enum");4698}4699 4700static bool shorter_filter(const Value *LHS, const Value *RHS) {4701  return4702    cast<ArrayType>(LHS->getType())->getNumElements()4703  <4704    cast<ArrayType>(RHS->getType())->getNumElements();4705}4706 4707Instruction *InstCombinerImpl::visitLandingPadInst(LandingPadInst &LI) {4708  // The logic here should be correct for any real-world personality function.4709  // However if that turns out not to be true, the offending logic can always4710  // be conditioned on the personality function, like the catch-all logic is.4711  EHPersonality Personality =4712      classifyEHPersonality(LI.getParent()->getParent()->getPersonalityFn());4713 4714  // Simplify the list of clauses, eg by removing repeated catch clauses4715  // (these are often created by inlining).4716  bool MakeNewInstruction = false; // If true, recreate using the following:4717  SmallVector<Constant *, 16> NewClauses; // - Clauses for the new instruction;4718  bool CleanupFlag = LI.isCleanup();   // - The new instruction is a cleanup.4719 4720  SmallPtrSet<Value *, 16> AlreadyCaught; // Typeinfos known caught already.4721  for (unsigned i = 0, e = LI.getNumClauses(); i != e; ++i) {4722    bool isLastClause = i + 1 == e;4723    if (LI.isCatch(i)) {4724      // A catch clause.4725      Constant *CatchClause = LI.getClause(i);4726      Constant *TypeInfo = CatchClause->stripPointerCasts();4727 4728      // If we already saw this clause, there is no point in having a second4729      // copy of it.4730      if (AlreadyCaught.insert(TypeInfo).second) {4731        // This catch clause was not already seen.4732        NewClauses.push_back(CatchClause);4733      } else {4734        // Repeated catch clause - drop the redundant copy.4735        MakeNewInstruction = true;4736      }4737 4738      // If this is a catch-all then there is no point in keeping any following4739      // clauses or marking the landingpad as having a cleanup.4740      if (isCatchAll(Personality, TypeInfo)) {4741        if (!isLastClause)4742          MakeNewInstruction = true;4743        CleanupFlag = false;4744        break;4745      }4746    } else {4747      // A filter clause.  If any of the filter elements were already caught4748      // then they can be dropped from the filter.  It is tempting to try to4749      // exploit the filter further by saying that any typeinfo that does not4750      // occur in the filter can't be caught later (and thus can be dropped).4751      // However this would be wrong, since typeinfos can match without being4752      // equal (for example if one represents a C++ class, and the other some4753      // class derived from it).4754      assert(LI.isFilter(i) && "Unsupported landingpad clause!");4755      Constant *FilterClause = LI.getClause(i);4756      ArrayType *FilterType = cast<ArrayType>(FilterClause->getType());4757      unsigned NumTypeInfos = FilterType->getNumElements();4758 4759      // An empty filter catches everything, so there is no point in keeping any4760      // following clauses or marking the landingpad as having a cleanup.  By4761      // dealing with this case here the following code is made a bit simpler.4762      if (!NumTypeInfos) {4763        NewClauses.push_back(FilterClause);4764        if (!isLastClause)4765          MakeNewInstruction = true;4766        CleanupFlag = false;4767        break;4768      }4769 4770      bool MakeNewFilter = false; // If true, make a new filter.4771      SmallVector<Constant *, 16> NewFilterElts; // New elements.4772      if (isa<ConstantAggregateZero>(FilterClause)) {4773        // Not an empty filter - it contains at least one null typeinfo.4774        assert(NumTypeInfos > 0 && "Should have handled empty filter already!");4775        Constant *TypeInfo =4776          Constant::getNullValue(FilterType->getElementType());4777        // If this typeinfo is a catch-all then the filter can never match.4778        if (isCatchAll(Personality, TypeInfo)) {4779          // Throw the filter away.4780          MakeNewInstruction = true;4781          continue;4782        }4783 4784        // There is no point in having multiple copies of this typeinfo, so4785        // discard all but the first copy if there is more than one.4786        NewFilterElts.push_back(TypeInfo);4787        if (NumTypeInfos > 1)4788          MakeNewFilter = true;4789      } else {4790        ConstantArray *Filter = cast<ConstantArray>(FilterClause);4791        SmallPtrSet<Value *, 16> SeenInFilter; // For uniquing the elements.4792        NewFilterElts.reserve(NumTypeInfos);4793 4794        // Remove any filter elements that were already caught or that already4795        // occurred in the filter.  While there, see if any of the elements are4796        // catch-alls.  If so, the filter can be discarded.4797        bool SawCatchAll = false;4798        for (unsigned j = 0; j != NumTypeInfos; ++j) {4799          Constant *Elt = Filter->getOperand(j);4800          Constant *TypeInfo = Elt->stripPointerCasts();4801          if (isCatchAll(Personality, TypeInfo)) {4802            // This element is a catch-all.  Bail out, noting this fact.4803            SawCatchAll = true;4804            break;4805          }4806 4807          // Even if we've seen a type in a catch clause, we don't want to4808          // remove it from the filter.  An unexpected type handler may be4809          // set up for a call site which throws an exception of the same4810          // type caught.  In order for the exception thrown by the unexpected4811          // handler to propagate correctly, the filter must be correctly4812          // described for the call site.4813          //4814          // Example:4815          //4816          // void unexpected() { throw 1;}4817          // void foo() throw (int) {4818          //   std::set_unexpected(unexpected);4819          //   try {4820          //     throw 2.0;4821          //   } catch (int i) {}4822          // }4823 4824          // There is no point in having multiple copies of the same typeinfo in4825          // a filter, so only add it if we didn't already.4826          if (SeenInFilter.insert(TypeInfo).second)4827            NewFilterElts.push_back(cast<Constant>(Elt));4828        }4829        // A filter containing a catch-all cannot match anything by definition.4830        if (SawCatchAll) {4831          // Throw the filter away.4832          MakeNewInstruction = true;4833          continue;4834        }4835 4836        // If we dropped something from the filter, make a new one.4837        if (NewFilterElts.size() < NumTypeInfos)4838          MakeNewFilter = true;4839      }4840      if (MakeNewFilter) {4841        FilterType = ArrayType::get(FilterType->getElementType(),4842                                    NewFilterElts.size());4843        FilterClause = ConstantArray::get(FilterType, NewFilterElts);4844        MakeNewInstruction = true;4845      }4846 4847      NewClauses.push_back(FilterClause);4848 4849      // If the new filter is empty then it will catch everything so there is4850      // no point in keeping any following clauses or marking the landingpad4851      // as having a cleanup.  The case of the original filter being empty was4852      // already handled above.4853      if (MakeNewFilter && !NewFilterElts.size()) {4854        assert(MakeNewInstruction && "New filter but not a new instruction!");4855        CleanupFlag = false;4856        break;4857      }4858    }4859  }4860 4861  // If several filters occur in a row then reorder them so that the shortest4862  // filters come first (those with the smallest number of elements).  This is4863  // advantageous because shorter filters are more likely to match, speeding up4864  // unwinding, but mostly because it increases the effectiveness of the other4865  // filter optimizations below.4866  for (unsigned i = 0, e = NewClauses.size(); i + 1 < e; ) {4867    unsigned j;4868    // Find the maximal 'j' s.t. the range [i, j) consists entirely of filters.4869    for (j = i; j != e; ++j)4870      if (!isa<ArrayType>(NewClauses[j]->getType()))4871        break;4872 4873    // Check whether the filters are already sorted by length.  We need to know4874    // if sorting them is actually going to do anything so that we only make a4875    // new landingpad instruction if it does.4876    for (unsigned k = i; k + 1 < j; ++k)4877      if (shorter_filter(NewClauses[k+1], NewClauses[k])) {4878        // Not sorted, so sort the filters now.  Doing an unstable sort would be4879        // correct too but reordering filters pointlessly might confuse users.4880        std::stable_sort(NewClauses.begin() + i, NewClauses.begin() + j,4881                         shorter_filter);4882        MakeNewInstruction = true;4883        break;4884      }4885 4886    // Look for the next batch of filters.4887    i = j + 1;4888  }4889 4890  // If typeinfos matched if and only if equal, then the elements of a filter L4891  // that occurs later than a filter F could be replaced by the intersection of4892  // the elements of F and L.  In reality two typeinfos can match without being4893  // equal (for example if one represents a C++ class, and the other some class4894  // derived from it) so it would be wrong to perform this transform in general.4895  // However the transform is correct and useful if F is a subset of L.  In that4896  // case L can be replaced by F, and thus removed altogether since repeating a4897  // filter is pointless.  So here we look at all pairs of filters F and L where4898  // L follows F in the list of clauses, and remove L if every element of F is4899  // an element of L.  This can occur when inlining C++ functions with exception4900  // specifications.4901  for (unsigned i = 0; i + 1 < NewClauses.size(); ++i) {4902    // Examine each filter in turn.4903    Value *Filter = NewClauses[i];4904    ArrayType *FTy = dyn_cast<ArrayType>(Filter->getType());4905    if (!FTy)4906      // Not a filter - skip it.4907      continue;4908    unsigned FElts = FTy->getNumElements();4909    // Examine each filter following this one.  Doing this backwards means that4910    // we don't have to worry about filters disappearing under us when removed.4911    for (unsigned j = NewClauses.size() - 1; j != i; --j) {4912      Value *LFilter = NewClauses[j];4913      ArrayType *LTy = dyn_cast<ArrayType>(LFilter->getType());4914      if (!LTy)4915        // Not a filter - skip it.4916        continue;4917      // If Filter is a subset of LFilter, i.e. every element of Filter is also4918      // an element of LFilter, then discard LFilter.4919      SmallVectorImpl<Constant *>::iterator J = NewClauses.begin() + j;4920      // If Filter is empty then it is a subset of LFilter.4921      if (!FElts) {4922        // Discard LFilter.4923        NewClauses.erase(J);4924        MakeNewInstruction = true;4925        // Move on to the next filter.4926        continue;4927      }4928      unsigned LElts = LTy->getNumElements();4929      // If Filter is longer than LFilter then it cannot be a subset of it.4930      if (FElts > LElts)4931        // Move on to the next filter.4932        continue;4933      // At this point we know that LFilter has at least one element.4934      if (isa<ConstantAggregateZero>(LFilter)) { // LFilter only contains zeros.4935        // Filter is a subset of LFilter iff Filter contains only zeros (as we4936        // already know that Filter is not longer than LFilter).4937        if (isa<ConstantAggregateZero>(Filter)) {4938          assert(FElts <= LElts && "Should have handled this case earlier!");4939          // Discard LFilter.4940          NewClauses.erase(J);4941          MakeNewInstruction = true;4942        }4943        // Move on to the next filter.4944        continue;4945      }4946      ConstantArray *LArray = cast<ConstantArray>(LFilter);4947      if (isa<ConstantAggregateZero>(Filter)) { // Filter only contains zeros.4948        // Since Filter is non-empty and contains only zeros, it is a subset of4949        // LFilter iff LFilter contains a zero.4950        assert(FElts > 0 && "Should have eliminated the empty filter earlier!");4951        for (unsigned l = 0; l != LElts; ++l)4952          if (LArray->getOperand(l)->isNullValue()) {4953            // LFilter contains a zero - discard it.4954            NewClauses.erase(J);4955            MakeNewInstruction = true;4956            break;4957          }4958        // Move on to the next filter.4959        continue;4960      }4961      // At this point we know that both filters are ConstantArrays.  Loop over4962      // operands to see whether every element of Filter is also an element of4963      // LFilter.  Since filters tend to be short this is probably faster than4964      // using a method that scales nicely.4965      ConstantArray *FArray = cast<ConstantArray>(Filter);4966      bool AllFound = true;4967      for (unsigned f = 0; f != FElts; ++f) {4968        Value *FTypeInfo = FArray->getOperand(f)->stripPointerCasts();4969        AllFound = false;4970        for (unsigned l = 0; l != LElts; ++l) {4971          Value *LTypeInfo = LArray->getOperand(l)->stripPointerCasts();4972          if (LTypeInfo == FTypeInfo) {4973            AllFound = true;4974            break;4975          }4976        }4977        if (!AllFound)4978          break;4979      }4980      if (AllFound) {4981        // Discard LFilter.4982        NewClauses.erase(J);4983        MakeNewInstruction = true;4984      }4985      // Move on to the next filter.4986    }4987  }4988 4989  // If we changed any of the clauses, replace the old landingpad instruction4990  // with a new one.4991  if (MakeNewInstruction) {4992    LandingPadInst *NLI = LandingPadInst::Create(LI.getType(),4993                                                 NewClauses.size());4994    for (Constant *C : NewClauses)4995      NLI->addClause(C);4996    // A landing pad with no clauses must have the cleanup flag set.  It is4997    // theoretically possible, though highly unlikely, that we eliminated all4998    // clauses.  If so, force the cleanup flag to true.4999    if (NewClauses.empty())5000      CleanupFlag = true;5001    NLI->setCleanup(CleanupFlag);5002    return NLI;5003  }5004 5005  // Even if none of the clauses changed, we may nonetheless have understood5006  // that the cleanup flag is pointless.  Clear it if so.5007  if (LI.isCleanup() != CleanupFlag) {5008    assert(!CleanupFlag && "Adding a cleanup, not removing one?!");5009    LI.setCleanup(CleanupFlag);5010    return &LI;5011  }5012 5013  return nullptr;5014}5015 5016Value *5017InstCombinerImpl::pushFreezeToPreventPoisonFromPropagating(FreezeInst &OrigFI) {5018  // Try to push freeze through instructions that propagate but don't produce5019  // poison as far as possible. If an operand of freeze does not produce poison5020  // then push the freeze through to the operands that are not guaranteed5021  // non-poison. The actual transform is as follows.5022  //   Op1 = ...                        ; Op1 can be poison5023  //   Op0 = Inst(Op1, NonPoisonOps...)5024  //   ... = Freeze(Op0)5025  // =>5026  //   Op1 = ...5027  //   Op1.fr = Freeze(Op1)5028  //   ... = Inst(Op1.fr, NonPoisonOps...)5029 5030  auto CanPushFreeze = [](Value *V) {5031    if (!isa<Instruction>(V) || isa<PHINode>(V))5032      return false;5033 5034    // We can't push the freeze through an instruction which can itself create5035    // poison.  If the only source of new poison is flags, we can simply5036    // strip them (since we know the only use is the freeze and nothing can5037    // benefit from them.)5038    return !canCreateUndefOrPoison(cast<Operator>(V),5039                                   /*ConsiderFlagsAndMetadata*/ false);5040  };5041 5042  // Pushing freezes up long instruction chains can be expensive. Instead,5043  // we directly push the freeze all the way to the leaves. However, we leave5044  // deduplication of freezes on the same value for freezeOtherUses().5045  Use *OrigUse = &OrigFI.getOperandUse(0);5046  SmallPtrSet<Instruction *, 8> Visited;5047  SmallVector<Use *, 8> Worklist;5048  Worklist.push_back(OrigUse);5049  while (!Worklist.empty()) {5050    auto *U = Worklist.pop_back_val();5051    Value *V = U->get();5052    if (!CanPushFreeze(V)) {5053      // If we can't push through the original instruction, abort the transform.5054      if (U == OrigUse)5055        return nullptr;5056 5057      auto *UserI = cast<Instruction>(U->getUser());5058      Builder.SetInsertPoint(UserI);5059      Value *Frozen = Builder.CreateFreeze(V, V->getName() + ".fr");5060      U->set(Frozen);5061      continue;5062    }5063 5064    auto *I = cast<Instruction>(V);5065    if (!Visited.insert(I).second)5066      continue;5067 5068    // reverse() to emit freezes in a more natural order.5069    for (Use &Op : reverse(I->operands())) {5070      Value *OpV = Op.get();5071      if (isa<MetadataAsValue>(OpV) || isGuaranteedNotToBeUndefOrPoison(OpV))5072        continue;5073      Worklist.push_back(&Op);5074    }5075 5076    I->dropPoisonGeneratingAnnotations();5077    this->Worklist.add(I);5078  }5079 5080  return OrigUse->get();5081}5082 5083Instruction *InstCombinerImpl::foldFreezeIntoRecurrence(FreezeInst &FI,5084                                                        PHINode *PN) {5085  // Detect whether this is a recurrence with a start value and some number of5086  // backedge values. We'll check whether we can push the freeze through the5087  // backedge values (possibly dropping poison flags along the way) until we5088  // reach the phi again. In that case, we can move the freeze to the start5089  // value.5090  Use *StartU = nullptr;5091  SmallVector<Value *> Worklist;5092  for (Use &U : PN->incoming_values()) {5093    if (DT.dominates(PN->getParent(), PN->getIncomingBlock(U))) {5094      // Add backedge value to worklist.5095      Worklist.push_back(U.get());5096      continue;5097    }5098 5099    // Don't bother handling multiple start values.5100    if (StartU)5101      return nullptr;5102    StartU = &U;5103  }5104 5105  if (!StartU || Worklist.empty())5106    return nullptr; // Not a recurrence.5107 5108  Value *StartV = StartU->get();5109  BasicBlock *StartBB = PN->getIncomingBlock(*StartU);5110  bool StartNeedsFreeze = !isGuaranteedNotToBeUndefOrPoison(StartV);5111  // We can't insert freeze if the start value is the result of the5112  // terminator (e.g. an invoke).5113  if (StartNeedsFreeze && StartBB->getTerminator() == StartV)5114    return nullptr;5115 5116  SmallPtrSet<Value *, 32> Visited;5117  SmallVector<Instruction *> DropFlags;5118  while (!Worklist.empty()) {5119    Value *V = Worklist.pop_back_val();5120    if (!Visited.insert(V).second)5121      continue;5122 5123    if (Visited.size() > 32)5124      return nullptr; // Limit the total number of values we inspect.5125 5126    // Assume that PN is non-poison, because it will be after the transform.5127    if (V == PN || isGuaranteedNotToBeUndefOrPoison(V))5128      continue;5129 5130    Instruction *I = dyn_cast<Instruction>(V);5131    if (!I || canCreateUndefOrPoison(cast<Operator>(I),5132                                     /*ConsiderFlagsAndMetadata*/ false))5133      return nullptr;5134 5135    DropFlags.push_back(I);5136    append_range(Worklist, I->operands());5137  }5138 5139  for (Instruction *I : DropFlags)5140    I->dropPoisonGeneratingAnnotations();5141 5142  if (StartNeedsFreeze) {5143    Builder.SetInsertPoint(StartBB->getTerminator());5144    Value *FrozenStartV = Builder.CreateFreeze(StartV,5145                                               StartV->getName() + ".fr");5146    replaceUse(*StartU, FrozenStartV);5147  }5148  return replaceInstUsesWith(FI, PN);5149}5150 5151bool InstCombinerImpl::freezeOtherUses(FreezeInst &FI) {5152  Value *Op = FI.getOperand(0);5153 5154  if (isa<Constant>(Op) || Op->hasOneUse())5155    return false;5156 5157  // Move the freeze directly after the definition of its operand, so that5158  // it dominates the maximum number of uses. Note that it may not dominate5159  // *all* uses if the operand is an invoke/callbr and the use is in a phi on5160  // the normal/default destination. This is why the domination check in the5161  // replacement below is still necessary.5162  BasicBlock::iterator MoveBefore;5163  if (isa<Argument>(Op)) {5164    MoveBefore =5165        FI.getFunction()->getEntryBlock().getFirstNonPHIOrDbgOrAlloca();5166  } else {5167    auto MoveBeforeOpt = cast<Instruction>(Op)->getInsertionPointAfterDef();5168    if (!MoveBeforeOpt)5169      return false;5170    MoveBefore = *MoveBeforeOpt;5171  }5172 5173  // Re-point iterator to come after any debug-info records.5174  MoveBefore.setHeadBit(false);5175 5176  bool Changed = false;5177  if (&FI != &*MoveBefore) {5178    FI.moveBefore(*MoveBefore->getParent(), MoveBefore);5179    Changed = true;5180  }5181 5182  Op->replaceUsesWithIf(&FI, [&](Use &U) -> bool {5183    bool Dominates = DT.dominates(&FI, U);5184    Changed |= Dominates;5185    return Dominates;5186  });5187 5188  return Changed;5189}5190 5191// Check if any direct or bitcast user of this value is a shuffle instruction.5192static bool isUsedWithinShuffleVector(Value *V) {5193  for (auto *U : V->users()) {5194    if (isa<ShuffleVectorInst>(U))5195      return true;5196    else if (match(U, m_BitCast(m_Specific(V))) && isUsedWithinShuffleVector(U))5197      return true;5198  }5199  return false;5200}5201 5202Instruction *InstCombinerImpl::visitFreeze(FreezeInst &I) {5203  Value *Op0 = I.getOperand(0);5204 5205  if (Value *V = simplifyFreezeInst(Op0, SQ.getWithInstruction(&I)))5206    return replaceInstUsesWith(I, V);5207 5208  // freeze (phi const, x) --> phi const, (freeze x)5209  if (auto *PN = dyn_cast<PHINode>(Op0)) {5210    if (Instruction *NV = foldOpIntoPhi(I, PN))5211      return NV;5212    if (Instruction *NV = foldFreezeIntoRecurrence(I, PN))5213      return NV;5214  }5215 5216  if (Value *NI = pushFreezeToPreventPoisonFromPropagating(I))5217    return replaceInstUsesWith(I, NI);5218 5219  // If I is freeze(undef), check its uses and fold it to a fixed constant.5220  // - or: pick -15221  // - select's condition: if the true value is constant, choose it by making5222  //                       the condition true.5223  // - phi: pick the common constant across operands5224  // - default: pick 05225  //5226  // Note that this transform is intentionally done here rather than5227  // via an analysis in InstSimplify or at individual user sites. That is5228  // because we must produce the same value for all uses of the freeze -5229  // it's the reason "freeze" exists!5230  //5231  // TODO: This could use getBinopAbsorber() / getBinopIdentity() to avoid5232  //       duplicating logic for binops at least.5233  auto getUndefReplacement = [&](Type *Ty) {5234    auto pickCommonConstantFromPHI = [](PHINode &PN) -> Value * {5235      // phi(freeze(undef), C, C). Choose C for freeze so the PHI can be5236      // removed.5237      Constant *BestValue = nullptr;5238      for (Value *V : PN.incoming_values()) {5239        if (match(V, m_Freeze(m_Undef())))5240          continue;5241 5242        Constant *C = dyn_cast<Constant>(V);5243        if (!C)5244          return nullptr;5245 5246        if (!isGuaranteedNotToBeUndefOrPoison(C))5247          return nullptr;5248 5249        if (BestValue && BestValue != C)5250          return nullptr;5251 5252        BestValue = C;5253      }5254      return BestValue;5255    };5256 5257    Value *NullValue = Constant::getNullValue(Ty);5258    Value *BestValue = nullptr;5259    for (auto *U : I.users()) {5260      Value *V = NullValue;5261      if (match(U, m_Or(m_Value(), m_Value())))5262        V = ConstantInt::getAllOnesValue(Ty);5263      else if (match(U, m_Select(m_Specific(&I), m_Constant(), m_Value())))5264        V = ConstantInt::getTrue(Ty);5265      else if (match(U, m_c_Select(m_Specific(&I), m_Value(V)))) {5266        if (V == &I || !isGuaranteedNotToBeUndefOrPoison(V, &AC, &I, &DT))5267          V = NullValue;5268      } else if (auto *PHI = dyn_cast<PHINode>(U)) {5269        if (Value *MaybeV = pickCommonConstantFromPHI(*PHI))5270          V = MaybeV;5271      }5272 5273      if (!BestValue)5274        BestValue = V;5275      else if (BestValue != V)5276        BestValue = NullValue;5277    }5278    assert(BestValue && "Must have at least one use");5279    assert(BestValue != &I && "Cannot replace with itself");5280    return BestValue;5281  };5282 5283  if (match(Op0, m_Undef())) {5284    // Don't fold freeze(undef/poison) if it's used as a vector operand in5285    // a shuffle. This may improve codegen for shuffles that allow5286    // unspecified inputs.5287    if (isUsedWithinShuffleVector(&I))5288      return nullptr;5289    return replaceInstUsesWith(I, getUndefReplacement(I.getType()));5290  }5291 5292  auto getFreezeVectorReplacement = [](Constant *C) -> Constant * {5293    Type *Ty = C->getType();5294    auto *VTy = dyn_cast<FixedVectorType>(Ty);5295    if (!VTy)5296      return nullptr;5297    unsigned NumElts = VTy->getNumElements();5298    Constant *BestValue = Constant::getNullValue(VTy->getScalarType());5299    for (unsigned i = 0; i != NumElts; ++i) {5300      Constant *EltC = C->getAggregateElement(i);5301      if (EltC && !match(EltC, m_Undef())) {5302        BestValue = EltC;5303        break;5304      }5305    }5306    return Constant::replaceUndefsWith(C, BestValue);5307  };5308 5309  Constant *C;5310  if (match(Op0, m_Constant(C)) && C->containsUndefOrPoisonElement() &&5311      !C->containsConstantExpression()) {5312    if (Constant *Repl = getFreezeVectorReplacement(C))5313      return replaceInstUsesWith(I, Repl);5314  }5315 5316  // Replace uses of Op with freeze(Op).5317  if (freezeOtherUses(I))5318    return &I;5319 5320  return nullptr;5321}5322 5323/// Check for case where the call writes to an otherwise dead alloca.  This5324/// shows up for unused out-params in idiomatic C/C++ code.   Note that this5325/// helper *only* analyzes the write; doesn't check any other legality aspect.5326static bool SoleWriteToDeadLocal(Instruction *I, TargetLibraryInfo &TLI) {5327  auto *CB = dyn_cast<CallBase>(I);5328  if (!CB)5329    // TODO: handle e.g. store to alloca here - only worth doing if we extend5330    // to allow reload along used path as described below.  Otherwise, this5331    // is simply a store to a dead allocation which will be removed.5332    return false;5333  std::optional<MemoryLocation> Dest = MemoryLocation::getForDest(CB, TLI);5334  if (!Dest)5335    return false;5336  auto *AI = dyn_cast<AllocaInst>(getUnderlyingObject(Dest->Ptr));5337  if (!AI)5338    // TODO: allow malloc?5339    return false;5340  // TODO: allow memory access dominated by move point?  Note that since AI5341  // could have a reference to itself captured by the call, we would need to5342  // account for cycles in doing so.5343  SmallVector<const User *> AllocaUsers;5344  SmallPtrSet<const User *, 4> Visited;5345  auto pushUsers = [&](const Instruction &I) {5346    for (const User *U : I.users()) {5347      if (Visited.insert(U).second)5348        AllocaUsers.push_back(U);5349    }5350  };5351  pushUsers(*AI);5352  while (!AllocaUsers.empty()) {5353    auto *UserI = cast<Instruction>(AllocaUsers.pop_back_val());5354    if (isa<GetElementPtrInst>(UserI) || isa<AddrSpaceCastInst>(UserI)) {5355      pushUsers(*UserI);5356      continue;5357    }5358    if (UserI == CB)5359      continue;5360    // TODO: support lifetime.start/end here5361    return false;5362  }5363  return true;5364}5365 5366/// Try to move the specified instruction from its current block into the5367/// beginning of DestBlock, which can only happen if it's safe to move the5368/// instruction past all of the instructions between it and the end of its5369/// block.5370bool InstCombinerImpl::tryToSinkInstruction(Instruction *I,5371                                            BasicBlock *DestBlock) {5372  BasicBlock *SrcBlock = I->getParent();5373 5374  // Cannot move control-flow-involving, volatile loads, vaarg, etc.5375  if (isa<PHINode>(I) || I->isEHPad() || I->mayThrow() || !I->willReturn() ||5376      I->isTerminator())5377    return false;5378 5379  // Do not sink static or dynamic alloca instructions. Static allocas must5380  // remain in the entry block, and dynamic allocas must not be sunk in between5381  // a stacksave / stackrestore pair, which would incorrectly shorten its5382  // lifetime.5383  if (isa<AllocaInst>(I))5384    return false;5385 5386  // Do not sink into catchswitch blocks.5387  if (isa<CatchSwitchInst>(DestBlock->getTerminator()))5388    return false;5389 5390  // Do not sink convergent call instructions.5391  if (auto *CI = dyn_cast<CallInst>(I)) {5392    if (CI->isConvergent())5393      return false;5394  }5395 5396  // Unless we can prove that the memory write isn't visibile except on the5397  // path we're sinking to, we must bail.5398  if (I->mayWriteToMemory()) {5399    if (!SoleWriteToDeadLocal(I, TLI))5400      return false;5401  }5402 5403  // We can only sink load instructions if there is nothing between the load and5404  // the end of block that could change the value.5405  if (I->mayReadFromMemory() &&5406      !I->hasMetadata(LLVMContext::MD_invariant_load)) {5407    // We don't want to do any sophisticated alias analysis, so we only check5408    // the instructions after I in I's parent block if we try to sink to its5409    // successor block.5410    if (DestBlock->getUniquePredecessor() != I->getParent())5411      return false;5412    for (BasicBlock::iterator Scan = std::next(I->getIterator()),5413                              E = I->getParent()->end();5414         Scan != E; ++Scan)5415      if (Scan->mayWriteToMemory())5416        return false;5417  }5418 5419  I->dropDroppableUses([&](const Use *U) {5420    auto *I = dyn_cast<Instruction>(U->getUser());5421    if (I && I->getParent() != DestBlock) {5422      Worklist.add(I);5423      return true;5424    }5425    return false;5426  });5427  /// FIXME: We could remove droppable uses that are not dominated by5428  /// the new position.5429 5430  BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt();5431  I->moveBefore(*DestBlock, InsertPos);5432  ++NumSunkInst;5433 5434  // Also sink all related debug uses from the source basic block. Otherwise we5435  // get debug use before the def. Attempt to salvage debug uses first, to5436  // maximise the range variables have location for. If we cannot salvage, then5437  // mark the location undef: we know it was supposed to receive a new location5438  // here, but that computation has been sunk.5439  SmallVector<DbgVariableRecord *, 2> DbgVariableRecords;5440  findDbgUsers(I, DbgVariableRecords);5441  if (!DbgVariableRecords.empty())5442    tryToSinkInstructionDbgVariableRecords(I, InsertPos, SrcBlock, DestBlock,5443                                           DbgVariableRecords);5444 5445  // PS: there are numerous flaws with this behaviour, not least that right now5446  // assignments can be re-ordered past other assignments to the same variable5447  // if they use different Values. Creating more undef assignements can never be5448  // undone. And salvaging all users outside of this block can un-necessarily5449  // alter the lifetime of the live-value that the variable refers to.5450  // Some of these things can be resolved by tolerating debug use-before-defs in5451  // LLVM-IR, however it depends on the instruction-referencing CodeGen backend5452  // being used for more architectures.5453 5454  return true;5455}5456 5457void InstCombinerImpl::tryToSinkInstructionDbgVariableRecords(5458    Instruction *I, BasicBlock::iterator InsertPos, BasicBlock *SrcBlock,5459    BasicBlock *DestBlock,5460    SmallVectorImpl<DbgVariableRecord *> &DbgVariableRecords) {5461  // For all debug values in the destination block, the sunk instruction5462  // will still be available, so they do not need to be dropped.5463 5464  // Fetch all DbgVariableRecords not already in the destination.5465  SmallVector<DbgVariableRecord *, 2> DbgVariableRecordsToSalvage;5466  for (auto &DVR : DbgVariableRecords)5467    if (DVR->getParent() != DestBlock)5468      DbgVariableRecordsToSalvage.push_back(DVR);5469 5470  // Fetch a second collection, of DbgVariableRecords in the source block that5471  // we're going to sink.5472  SmallVector<DbgVariableRecord *> DbgVariableRecordsToSink;5473  for (DbgVariableRecord *DVR : DbgVariableRecordsToSalvage)5474    if (DVR->getParent() == SrcBlock)5475      DbgVariableRecordsToSink.push_back(DVR);5476 5477  // Sort DbgVariableRecords according to their position in the block. This is a5478  // partial order: DbgVariableRecords attached to different instructions will5479  // be ordered by the instruction order, but DbgVariableRecords attached to the5480  // same instruction won't have an order.5481  auto Order = [](DbgVariableRecord *A, DbgVariableRecord *B) -> bool {5482    return B->getInstruction()->comesBefore(A->getInstruction());5483  };5484  llvm::stable_sort(DbgVariableRecordsToSink, Order);5485 5486  // If there are two assignments to the same variable attached to the same5487  // instruction, the ordering between the two assignments is important. Scan5488  // for this (rare) case and establish which is the last assignment.5489  using InstVarPair = std::pair<const Instruction *, DebugVariable>;5490  SmallDenseMap<InstVarPair, DbgVariableRecord *> FilterOutMap;5491  if (DbgVariableRecordsToSink.size() > 1) {5492    SmallDenseMap<InstVarPair, unsigned> CountMap;5493    // Count how many assignments to each variable there is per instruction.5494    for (DbgVariableRecord *DVR : DbgVariableRecordsToSink) {5495      DebugVariable DbgUserVariable =5496          DebugVariable(DVR->getVariable(), DVR->getExpression(),5497                        DVR->getDebugLoc()->getInlinedAt());5498      CountMap[std::make_pair(DVR->getInstruction(), DbgUserVariable)] += 1;5499    }5500 5501    // If there are any instructions with two assignments, add them to the5502    // FilterOutMap to record that they need extra filtering.5503    SmallPtrSet<const Instruction *, 4> DupSet;5504    for (auto It : CountMap) {5505      if (It.second > 1) {5506        FilterOutMap[It.first] = nullptr;5507        DupSet.insert(It.first.first);5508      }5509    }5510 5511    // For all instruction/variable pairs needing extra filtering, find the5512    // latest assignment.5513    for (const Instruction *Inst : DupSet) {5514      for (DbgVariableRecord &DVR :5515           llvm::reverse(filterDbgVars(Inst->getDbgRecordRange()))) {5516        DebugVariable DbgUserVariable =5517            DebugVariable(DVR.getVariable(), DVR.getExpression(),5518                          DVR.getDebugLoc()->getInlinedAt());5519        auto FilterIt =5520            FilterOutMap.find(std::make_pair(Inst, DbgUserVariable));5521        if (FilterIt == FilterOutMap.end())5522          continue;5523        if (FilterIt->second != nullptr)5524          continue;5525        FilterIt->second = &DVR;5526      }5527    }5528  }5529 5530  // Perform cloning of the DbgVariableRecords that we plan on sinking, filter5531  // out any duplicate assignments identified above.5532  SmallVector<DbgVariableRecord *, 2> DVRClones;5533  SmallSet<DebugVariable, 4> SunkVariables;5534  for (DbgVariableRecord *DVR : DbgVariableRecordsToSink) {5535    if (DVR->Type == DbgVariableRecord::LocationType::Declare)5536      continue;5537 5538    DebugVariable DbgUserVariable =5539        DebugVariable(DVR->getVariable(), DVR->getExpression(),5540                      DVR->getDebugLoc()->getInlinedAt());5541 5542    // For any variable where there were multiple assignments in the same place,5543    // ignore all but the last assignment.5544    if (!FilterOutMap.empty()) {5545      InstVarPair IVP = std::make_pair(DVR->getInstruction(), DbgUserVariable);5546      auto It = FilterOutMap.find(IVP);5547 5548      // Filter out.5549      if (It != FilterOutMap.end() && It->second != DVR)5550        continue;5551    }5552 5553    if (!SunkVariables.insert(DbgUserVariable).second)5554      continue;5555 5556    if (DVR->isDbgAssign())5557      continue;5558 5559    DVRClones.emplace_back(DVR->clone());5560    LLVM_DEBUG(dbgs() << "CLONE: " << *DVRClones.back() << '\n');5561  }5562 5563  // Perform salvaging without the clones, then sink the clones.5564  if (DVRClones.empty())5565    return;5566 5567  salvageDebugInfoForDbgValues(*I, DbgVariableRecordsToSalvage);5568 5569  // The clones are in reverse order of original appearance. Assert that the5570  // head bit is set on the iterator as we _should_ have received it via5571  // getFirstInsertionPt. Inserting like this will reverse the clone order as5572  // we'll repeatedly insert at the head, such as:5573  //   DVR-3 (third insertion goes here)5574  //   DVR-2 (second insertion goes here)5575  //   DVR-1 (first insertion goes here)5576  //   Any-Prior-DVRs5577  //   InsertPtInst5578  assert(InsertPos.getHeadBit());5579  for (DbgVariableRecord *DVRClone : DVRClones) {5580    InsertPos->getParent()->insertDbgRecordBefore(DVRClone, InsertPos);5581    LLVM_DEBUG(dbgs() << "SINK: " << *DVRClone << '\n');5582  }5583}5584 5585bool InstCombinerImpl::run() {5586  while (!Worklist.isEmpty()) {5587    // Walk deferred instructions in reverse order, and push them to the5588    // worklist, which means they'll end up popped from the worklist in-order.5589    while (Instruction *I = Worklist.popDeferred()) {5590      // Check to see if we can DCE the instruction. We do this already here to5591      // reduce the number of uses and thus allow other folds to trigger.5592      // Note that eraseInstFromFunction() may push additional instructions on5593      // the deferred worklist, so this will DCE whole instruction chains.5594      if (isInstructionTriviallyDead(I, &TLI)) {5595        eraseInstFromFunction(*I);5596        ++NumDeadInst;5597        continue;5598      }5599 5600      Worklist.push(I);5601    }5602 5603    Instruction *I = Worklist.removeOne();5604    if (I == nullptr) continue;  // skip null values.5605 5606    // Check to see if we can DCE the instruction.5607    if (isInstructionTriviallyDead(I, &TLI)) {5608      eraseInstFromFunction(*I);5609      ++NumDeadInst;5610      continue;5611    }5612 5613    if (!DebugCounter::shouldExecute(VisitCounter))5614      continue;5615 5616    // See if we can trivially sink this instruction to its user if we can5617    // prove that the successor is not executed more frequently than our block.5618    // Return the UserBlock if successful.5619    auto getOptionalSinkBlockForInst =5620        [this](Instruction *I) -> std::optional<BasicBlock *> {5621      if (!EnableCodeSinking)5622        return std::nullopt;5623 5624      BasicBlock *BB = I->getParent();5625      BasicBlock *UserParent = nullptr;5626      unsigned NumUsers = 0;5627 5628      for (Use &U : I->uses()) {5629        User *User = U.getUser();5630        if (User->isDroppable()) {5631          // Do not sink if there are dereferenceable assumes that would be5632          // removed.5633          auto II = dyn_cast<IntrinsicInst>(User);5634          if (II->getIntrinsicID() != Intrinsic::assume ||5635              !II->getOperandBundle("dereferenceable"))5636            continue;5637        }5638 5639        if (NumUsers > MaxSinkNumUsers)5640          return std::nullopt;5641 5642        Instruction *UserInst = cast<Instruction>(User);5643        // Special handling for Phi nodes - get the block the use occurs in.5644        BasicBlock *UserBB = UserInst->getParent();5645        if (PHINode *PN = dyn_cast<PHINode>(UserInst))5646          UserBB = PN->getIncomingBlock(U);5647        // Bail out if we have uses in different blocks. We don't do any5648        // sophisticated analysis (i.e finding NearestCommonDominator of these5649        // use blocks).5650        if (UserParent && UserParent != UserBB)5651          return std::nullopt;5652        UserParent = UserBB;5653 5654        // Make sure these checks are done only once, naturally we do the checks5655        // the first time we get the userparent, this will save compile time.5656        if (NumUsers == 0) {5657          // Try sinking to another block. If that block is unreachable, then do5658          // not bother. SimplifyCFG should handle it.5659          if (UserParent == BB || !DT.isReachableFromEntry(UserParent))5660            return std::nullopt;5661 5662          auto *Term = UserParent->getTerminator();5663          // See if the user is one of our successors that has only one5664          // predecessor, so that we don't have to split the critical edge.5665          // Another option where we can sink is a block that ends with a5666          // terminator that does not pass control to other block (such as5667          // return or unreachable or resume). In this case:5668          //   - I dominates the User (by SSA form);5669          //   - the User will be executed at most once.5670          // So sinking I down to User is always profitable or neutral.5671          if (UserParent->getUniquePredecessor() != BB && !succ_empty(Term))5672            return std::nullopt;5673 5674          assert(DT.dominates(BB, UserParent) && "Dominance relation broken?");5675        }5676 5677        NumUsers++;5678      }5679 5680      // No user or only has droppable users.5681      if (!UserParent)5682        return std::nullopt;5683 5684      return UserParent;5685    };5686 5687    auto OptBB = getOptionalSinkBlockForInst(I);5688    if (OptBB) {5689      auto *UserParent = *OptBB;5690      // Okay, the CFG is simple enough, try to sink this instruction.5691      if (tryToSinkInstruction(I, UserParent)) {5692        LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');5693        MadeIRChange = true;5694        // We'll add uses of the sunk instruction below, but since5695        // sinking can expose opportunities for it's *operands* add5696        // them to the worklist5697        for (Use &U : I->operands())5698          if (Instruction *OpI = dyn_cast<Instruction>(U.get()))5699            Worklist.push(OpI);5700      }5701    }5702 5703    // Now that we have an instruction, try combining it to simplify it.5704    Builder.SetInsertPoint(I);5705    Builder.CollectMetadataToCopy(5706        I, {LLVMContext::MD_dbg, LLVMContext::MD_annotation});5707 5708#ifndef NDEBUG5709    std::string OrigI;5710#endif5711    LLVM_DEBUG(raw_string_ostream SS(OrigI); I->print(SS););5712    LLVM_DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n');5713 5714    if (Instruction *Result = visit(*I)) {5715      ++NumCombined;5716      // Should we replace the old instruction with a new one?5717      if (Result != I) {5718        LLVM_DEBUG(dbgs() << "IC: Old = " << *I << '\n'5719                          << "    New = " << *Result << '\n');5720 5721        // We copy the old instruction's DebugLoc to the new instruction, unless5722        // InstCombine already assigned a DebugLoc to it, in which case we5723        // should trust the more specifically selected DebugLoc.5724        Result->setDebugLoc(Result->getDebugLoc().orElse(I->getDebugLoc()));5725        // We also copy annotation metadata to the new instruction.5726        Result->copyMetadata(*I, LLVMContext::MD_annotation);5727        // Everything uses the new instruction now.5728        I->replaceAllUsesWith(Result);5729 5730        // Move the name to the new instruction first.5731        Result->takeName(I);5732 5733        // Insert the new instruction into the basic block...5734        BasicBlock *InstParent = I->getParent();5735        BasicBlock::iterator InsertPos = I->getIterator();5736 5737        // Are we replace a PHI with something that isn't a PHI, or vice versa?5738        if (isa<PHINode>(Result) != isa<PHINode>(I)) {5739          // We need to fix up the insertion point.5740          if (isa<PHINode>(I)) // PHI -> Non-PHI5741            InsertPos = InstParent->getFirstInsertionPt();5742          else // Non-PHI -> PHI5743            InsertPos = InstParent->getFirstNonPHIIt();5744        }5745 5746        Result->insertInto(InstParent, InsertPos);5747 5748        // Push the new instruction and any users onto the worklist.5749        Worklist.pushUsersToWorkList(*Result);5750        Worklist.push(Result);5751 5752        eraseInstFromFunction(*I);5753      } else {5754        LLVM_DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n'5755                          << "    New = " << *I << '\n');5756 5757        // If the instruction was modified, it's possible that it is now dead.5758        // if so, remove it.5759        if (isInstructionTriviallyDead(I, &TLI)) {5760          eraseInstFromFunction(*I);5761        } else {5762          Worklist.pushUsersToWorkList(*I);5763          Worklist.push(I);5764        }5765      }5766      MadeIRChange = true;5767    }5768  }5769 5770  Worklist.zap();5771  return MadeIRChange;5772}5773 5774// Track the scopes used by !alias.scope and !noalias. In a function, a5775// @llvm.experimental.noalias.scope.decl is only useful if that scope is used5776// by both sets. If not, the declaration of the scope can be safely omitted.5777// The MDNode of the scope can be omitted as well for the instructions that are5778// part of this function. We do not do that at this point, as this might become5779// too time consuming to do.5780class AliasScopeTracker {5781  SmallPtrSet<const MDNode *, 8> UsedAliasScopesAndLists;5782  SmallPtrSet<const MDNode *, 8> UsedNoAliasScopesAndLists;5783 5784public:5785  void analyse(Instruction *I) {5786    // This seems to be faster than checking 'mayReadOrWriteMemory()'.5787    if (!I->hasMetadataOtherThanDebugLoc())5788      return;5789 5790    auto Track = [](Metadata *ScopeList, auto &Container) {5791      const auto *MDScopeList = dyn_cast_or_null<MDNode>(ScopeList);5792      if (!MDScopeList || !Container.insert(MDScopeList).second)5793        return;5794      for (const auto &MDOperand : MDScopeList->operands())5795        if (auto *MDScope = dyn_cast<MDNode>(MDOperand))5796          Container.insert(MDScope);5797    };5798 5799    Track(I->getMetadata(LLVMContext::MD_alias_scope), UsedAliasScopesAndLists);5800    Track(I->getMetadata(LLVMContext::MD_noalias), UsedNoAliasScopesAndLists);5801  }5802 5803  bool isNoAliasScopeDeclDead(Instruction *Inst) {5804    NoAliasScopeDeclInst *Decl = dyn_cast<NoAliasScopeDeclInst>(Inst);5805    if (!Decl)5806      return false;5807 5808    assert(Decl->use_empty() &&5809           "llvm.experimental.noalias.scope.decl in use ?");5810    const MDNode *MDSL = Decl->getScopeList();5811    assert(MDSL->getNumOperands() == 1 &&5812           "llvm.experimental.noalias.scope should refer to a single scope");5813    auto &MDOperand = MDSL->getOperand(0);5814    if (auto *MD = dyn_cast<MDNode>(MDOperand))5815      return !UsedAliasScopesAndLists.contains(MD) ||5816             !UsedNoAliasScopesAndLists.contains(MD);5817 5818    // Not an MDNode ? throw away.5819    return true;5820  }5821};5822 5823/// Populate the IC worklist from a function, by walking it in reverse5824/// post-order and adding all reachable code to the worklist.5825///5826/// This has a couple of tricks to make the code faster and more powerful.  In5827/// particular, we constant fold and DCE instructions as we go, to avoid adding5828/// them to the worklist (this significantly speeds up instcombine on code where5829/// many instructions are dead or constant).  Additionally, if we find a branch5830/// whose condition is a known constant, we only visit the reachable successors.5831bool InstCombinerImpl::prepareWorklist(Function &F) {5832  bool MadeIRChange = false;5833  SmallPtrSet<BasicBlock *, 32> LiveBlocks;5834  SmallVector<Instruction *, 128> InstrsForInstructionWorklist;5835  DenseMap<Constant *, Constant *> FoldedConstants;5836  AliasScopeTracker SeenAliasScopes;5837 5838  auto HandleOnlyLiveSuccessor = [&](BasicBlock *BB, BasicBlock *LiveSucc) {5839    for (BasicBlock *Succ : successors(BB))5840      if (Succ != LiveSucc && DeadEdges.insert({BB, Succ}).second)5841        for (PHINode &PN : Succ->phis())5842          for (Use &U : PN.incoming_values())5843            if (PN.getIncomingBlock(U) == BB && !isa<PoisonValue>(U)) {5844              U.set(PoisonValue::get(PN.getType()));5845              MadeIRChange = true;5846            }5847  };5848 5849  for (BasicBlock *BB : RPOT) {5850    if (!BB->isEntryBlock() && all_of(predecessors(BB), [&](BasicBlock *Pred) {5851          return DeadEdges.contains({Pred, BB}) || DT.dominates(BB, Pred);5852        })) {5853      HandleOnlyLiveSuccessor(BB, nullptr);5854      continue;5855    }5856    LiveBlocks.insert(BB);5857 5858    for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {5859      // ConstantProp instruction if trivially constant.5860      if (!Inst.use_empty() &&5861          (Inst.getNumOperands() == 0 || isa<Constant>(Inst.getOperand(0))))5862        if (Constant *C = ConstantFoldInstruction(&Inst, DL, &TLI)) {5863          LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << Inst5864                            << '\n');5865          Inst.replaceAllUsesWith(C);5866          ++NumConstProp;5867          if (isInstructionTriviallyDead(&Inst, &TLI))5868            Inst.eraseFromParent();5869          MadeIRChange = true;5870          continue;5871        }5872 5873      // See if we can constant fold its operands.5874      for (Use &U : Inst.operands()) {5875        if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U))5876          continue;5877 5878        auto *C = cast<Constant>(U);5879        Constant *&FoldRes = FoldedConstants[C];5880        if (!FoldRes)5881          FoldRes = ConstantFoldConstant(C, DL, &TLI);5882 5883        if (FoldRes != C) {5884          LLVM_DEBUG(dbgs() << "IC: ConstFold operand of: " << Inst5885                            << "\n    Old = " << *C5886                            << "\n    New = " << *FoldRes << '\n');5887          U = FoldRes;5888          MadeIRChange = true;5889        }5890      }5891 5892      // Skip processing debug and pseudo intrinsics in InstCombine. Processing5893      // these call instructions consumes non-trivial amount of time and5894      // provides no value for the optimization.5895      if (!Inst.isDebugOrPseudoInst()) {5896        InstrsForInstructionWorklist.push_back(&Inst);5897        SeenAliasScopes.analyse(&Inst);5898      }5899    }5900 5901    // If this is a branch or switch on a constant, mark only the single5902    // live successor. Otherwise assume all successors are live.5903    Instruction *TI = BB->getTerminator();5904    if (BranchInst *BI = dyn_cast<BranchInst>(TI); BI && BI->isConditional()) {5905      if (isa<UndefValue>(BI->getCondition())) {5906        // Branch on undef is UB.5907        HandleOnlyLiveSuccessor(BB, nullptr);5908        continue;5909      }5910      if (auto *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {5911        bool CondVal = Cond->getZExtValue();5912        HandleOnlyLiveSuccessor(BB, BI->getSuccessor(!CondVal));5913        continue;5914      }5915    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {5916      if (isa<UndefValue>(SI->getCondition())) {5917        // Switch on undef is UB.5918        HandleOnlyLiveSuccessor(BB, nullptr);5919        continue;5920      }5921      if (auto *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {5922        HandleOnlyLiveSuccessor(BB,5923                                SI->findCaseValue(Cond)->getCaseSuccessor());5924        continue;5925      }5926    }5927  }5928 5929  // Remove instructions inside unreachable blocks. This prevents the5930  // instcombine code from having to deal with some bad special cases, and5931  // reduces use counts of instructions.5932  for (BasicBlock &BB : F) {5933    if (LiveBlocks.count(&BB))5934      continue;5935 5936    unsigned NumDeadInstInBB;5937    NumDeadInstInBB = removeAllNonTerminatorAndEHPadInstructions(&BB);5938 5939    MadeIRChange |= NumDeadInstInBB != 0;5940    NumDeadInst += NumDeadInstInBB;5941  }5942 5943  // Once we've found all of the instructions to add to instcombine's worklist,5944  // add them in reverse order.  This way instcombine will visit from the top5945  // of the function down.  This jives well with the way that it adds all uses5946  // of instructions to the worklist after doing a transformation, thus avoiding5947  // some N^2 behavior in pathological cases.5948  Worklist.reserve(InstrsForInstructionWorklist.size());5949  for (Instruction *Inst : reverse(InstrsForInstructionWorklist)) {5950    // DCE instruction if trivially dead. As we iterate in reverse program5951    // order here, we will clean up whole chains of dead instructions.5952    if (isInstructionTriviallyDead(Inst, &TLI) ||5953        SeenAliasScopes.isNoAliasScopeDeclDead(Inst)) {5954      ++NumDeadInst;5955      LLVM_DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');5956      salvageDebugInfo(*Inst);5957      Inst->eraseFromParent();5958      MadeIRChange = true;5959      continue;5960    }5961 5962    Worklist.push(Inst);5963  }5964 5965  return MadeIRChange;5966}5967 5968void InstCombiner::computeBackEdges() {5969  // Collect backedges.5970  SmallPtrSet<BasicBlock *, 16> Visited;5971  for (BasicBlock *BB : RPOT) {5972    Visited.insert(BB);5973    for (BasicBlock *Succ : successors(BB))5974      if (Visited.contains(Succ))5975        BackEdges.insert({BB, Succ});5976  }5977  ComputedBackEdges = true;5978}5979 5980static bool combineInstructionsOverFunction(5981    Function &F, InstructionWorklist &Worklist, AliasAnalysis *AA,5982    AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI,5983    DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI,5984    BranchProbabilityInfo *BPI, ProfileSummaryInfo *PSI,5985    const InstCombineOptions &Opts) {5986  auto &DL = F.getDataLayout();5987  bool VerifyFixpoint = Opts.VerifyFixpoint &&5988                        !F.hasFnAttribute("instcombine-no-verify-fixpoint");5989 5990  /// Builder - This is an IRBuilder that automatically inserts new5991  /// instructions into the worklist when they are created.5992  IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(5993      F.getContext(), TargetFolder(DL),5994      IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) {5995        Worklist.add(I);5996        if (auto *Assume = dyn_cast<AssumeInst>(I))5997          AC.registerAssumption(Assume);5998      }));5999 6000  ReversePostOrderTraversal<BasicBlock *> RPOT(&F.front());6001 6002  // Lower dbg.declare intrinsics otherwise their value may be clobbered6003  // by instcombiner.6004  bool MadeIRChange = false;6005  if (ShouldLowerDbgDeclare)6006    MadeIRChange = LowerDbgDeclare(F);6007 6008  // Iterate while there is work to do.6009  unsigned Iteration = 0;6010  while (true) {6011    if (Iteration >= Opts.MaxIterations && !VerifyFixpoint) {6012      LLVM_DEBUG(dbgs() << "\n\n[IC] Iteration limit #" << Opts.MaxIterations6013                        << " on " << F.getName()6014                        << " reached; stopping without verifying fixpoint\n");6015      break;6016    }6017 6018    ++Iteration;6019    ++NumWorklistIterations;6020    LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "6021                      << F.getName() << "\n");6022 6023    InstCombinerImpl IC(Worklist, Builder, F, AA, AC, TLI, TTI, DT, ORE, BFI,6024                        BPI, PSI, DL, RPOT);6025    IC.MaxArraySizeForCombine = MaxArraySize;6026    bool MadeChangeInThisIteration = IC.prepareWorklist(F);6027    MadeChangeInThisIteration |= IC.run();6028    if (!MadeChangeInThisIteration)6029      break;6030 6031    MadeIRChange = true;6032    if (Iteration > Opts.MaxIterations) {6033      reportFatalUsageError(6034          "Instruction Combining on " + Twine(F.getName()) +6035          " did not reach a fixpoint after " + Twine(Opts.MaxIterations) +6036          " iterations. " +6037          "Use 'instcombine<no-verify-fixpoint>' or function attribute "6038          "'instcombine-no-verify-fixpoint' to suppress this error.");6039    }6040  }6041 6042  if (Iteration == 1)6043    ++NumOneIteration;6044  else if (Iteration == 2)6045    ++NumTwoIterations;6046  else if (Iteration == 3)6047    ++NumThreeIterations;6048  else6049    ++NumFourOrMoreIterations;6050 6051  return MadeIRChange;6052}6053 6054InstCombinePass::InstCombinePass(InstCombineOptions Opts) : Options(Opts) {}6055 6056void InstCombinePass::printPipeline(6057    raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {6058  static_cast<PassInfoMixin<InstCombinePass> *>(this)->printPipeline(6059      OS, MapClassName2PassName);6060  OS << '<';6061  OS << "max-iterations=" << Options.MaxIterations << ";";6062  OS << (Options.VerifyFixpoint ? "" : "no-") << "verify-fixpoint";6063  OS << '>';6064}6065 6066char InstCombinePass::ID = 0;6067 6068PreservedAnalyses InstCombinePass::run(Function &F,6069                                       FunctionAnalysisManager &AM) {6070  auto &LRT = AM.getResult<LastRunTrackingAnalysis>(F);6071  // No changes since last InstCombine pass, exit early.6072  if (LRT.shouldSkip(&ID))6073    return PreservedAnalyses::all();6074 6075  auto &AC = AM.getResult<AssumptionAnalysis>(F);6076  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);6077  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);6078  auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);6079  auto &TTI = AM.getResult<TargetIRAnalysis>(F);6080 6081  auto *AA = &AM.getResult<AAManager>(F);6082  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);6083  ProfileSummaryInfo *PSI =6084      MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());6085  auto *BFI = (PSI && PSI->hasProfileSummary()) ?6086      &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;6087  auto *BPI = AM.getCachedResult<BranchProbabilityAnalysis>(F);6088 6089  if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, TTI, DT, ORE,6090                                       BFI, BPI, PSI, Options)) {6091    // No changes, all analyses are preserved.6092    LRT.update(&ID, /*Changed=*/false);6093    return PreservedAnalyses::all();6094  }6095 6096  // Mark all the analyses that instcombine updates as preserved.6097  PreservedAnalyses PA;6098  LRT.update(&ID, /*Changed=*/true);6099  PA.preserve<LastRunTrackingAnalysis>();6100  PA.preserveSet<CFGAnalyses>();6101  return PA;6102}6103 6104void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const {6105  AU.setPreservesCFG();6106  AU.addRequired<AAResultsWrapperPass>();6107  AU.addRequired<AssumptionCacheTracker>();6108  AU.addRequired<TargetLibraryInfoWrapperPass>();6109  AU.addRequired<TargetTransformInfoWrapperPass>();6110  AU.addRequired<DominatorTreeWrapperPass>();6111  AU.addRequired<OptimizationRemarkEmitterWrapperPass>();6112  AU.addPreserved<DominatorTreeWrapperPass>();6113  AU.addPreserved<AAResultsWrapperPass>();6114  AU.addPreserved<BasicAAWrapperPass>();6115  AU.addPreserved<GlobalsAAWrapperPass>();6116  AU.addRequired<ProfileSummaryInfoWrapperPass>();6117  LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);6118}6119 6120bool InstructionCombiningPass::runOnFunction(Function &F) {6121  if (skipFunction(F))6122    return false;6123 6124  // Required analyses.6125  auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();6126  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);6127  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);6128  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);6129  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();6130  auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();6131 6132  // Optional analyses.6133  ProfileSummaryInfo *PSI =6134      &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();6135  BlockFrequencyInfo *BFI =6136      (PSI && PSI->hasProfileSummary()) ?6137      &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :6138      nullptr;6139  BranchProbabilityInfo *BPI = nullptr;6140  if (auto *WrapperPass =6141          getAnalysisIfAvailable<BranchProbabilityInfoWrapperPass>())6142    BPI = &WrapperPass->getBPI();6143 6144  return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, TTI, DT, ORE,6145                                         BFI, BPI, PSI, InstCombineOptions());6146}6147 6148char InstructionCombiningPass::ID = 0;6149 6150InstructionCombiningPass::InstructionCombiningPass() : FunctionPass(ID) {6151  initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry());6152}6153 6154INITIALIZE_PASS_BEGIN(InstructionCombiningPass, "instcombine",6155                      "Combine redundant instructions", false, false)6156INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)6157INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)6158INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)6159INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)6160INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)6161INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)6162INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)6163INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass)6164INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)6165INITIALIZE_PASS_END(InstructionCombiningPass, "instcombine",6166                    "Combine redundant instructions", false, false)6167 6168// Initialization Routines6169void llvm::initializeInstCombine(PassRegistry &Registry) {6170  initializeInstructionCombiningPassPass(Registry);6171}6172 6173FunctionPass *llvm::createInstructionCombiningPass() {6174  return new InstructionCombiningPass();6175}6176