InstCombinePHI.cpp | Explore in Territory

//===- InstCombinePHI.cpp -------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the visitPHINode function.
//
//===----------------------------------------------------------------------===//

#include "InstCombineInternal.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include "llvm/Transforms/Utils/Local.h"
#include <optional>

usingnamespacellvm;
usingnamespacellvm::PatternMatch;

#define DEBUG_TYPE …

static cl::opt<unsigned>
MaxNumPhis("instcombine-max-num-phis", cl::init(512),
           cl::desc("Maximum number phis to handle in intptr/ptrint folding"));

STATISTIC(NumPHIsOfInsertValues,
          "Number of phi-of-insertvalue turned into insertvalue-of-phis");
STATISTIC(NumPHIsOfExtractValues,
          "Number of phi-of-extractvalue turned into extractvalue-of-phi");
STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd");

/// The PHI arguments will be folded into a single operation with a PHI node
/// as input. The debug location of the single operation will be the merged
/// locations of the original PHI node arguments.
void InstCombinerImpl::PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN) { … }

/// If the phi is within a phi web, which is formed by the def-use chain
/// of phis and all the phis in the web are only used in the other phis.
/// In this case, these phis are dead and we will remove all of them.
bool InstCombinerImpl::foldDeadPhiWeb(PHINode &PN) { … }

// Replace Integer typed PHI PN if the PHI's value is used as a pointer value.
// If there is an existing pointer typed PHI that produces the same value as PN,
// replace PN and the IntToPtr operation with it. Otherwise, synthesize a new
// PHI node:
//
// Case-1:
// bb1:
//     int_init = PtrToInt(ptr_init)
//     br label %bb2
// bb2:
//    int_val = PHI([int_init, %bb1], [int_val_inc, %bb2]
//    ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
//    ptr_val2 = IntToPtr(int_val)
//    ...
//    use(ptr_val2)
//    ptr_val_inc = ...
//    inc_val_inc = PtrToInt(ptr_val_inc)
//
// ==>
// bb1:
//     br label %bb2
// bb2:
//    ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
//    ...
//    use(ptr_val)
//    ptr_val_inc = ...
//
// Case-2:
// bb1:
//    int_ptr = BitCast(ptr_ptr)
//    int_init = Load(int_ptr)
//    br label %bb2
// bb2:
//    int_val = PHI([int_init, %bb1], [int_val_inc, %bb2]
//    ptr_val2 = IntToPtr(int_val)
//    ...
//    use(ptr_val2)
//    ptr_val_inc = ...
//    inc_val_inc = PtrToInt(ptr_val_inc)
// ==>
// bb1:
//    ptr_init = Load(ptr_ptr)
//    br label %bb2
// bb2:
//    ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
//    ...
//    use(ptr_val)
//    ptr_val_inc = ...
//    ...
//
bool InstCombinerImpl::foldIntegerTypedPHI(PHINode &PN) { … }

// Remove RoundTrip IntToPtr/PtrToInt Cast on PHI-Operand and
// fold Phi-operand to bitcast.
Instruction *InstCombinerImpl::foldPHIArgIntToPtrToPHI(PHINode &PN) { … }

/// If we have something like phi [insertvalue(a,b,0), insertvalue(c,d,0)],
/// turn this into a phi[a,c] and phi[b,d] and a single insertvalue.
Instruction *
InstCombinerImpl::foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN) { … }

/// If we have something like phi [extractvalue(a,0), extractvalue(b,0)],
/// turn this into a phi[a,b] and a single extractvalue.
Instruction *
InstCombinerImpl::foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN) { … }

/// If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the
/// adds all have a single user, turn this into a phi and a single binop.
Instruction *InstCombinerImpl::foldPHIArgBinOpIntoPHI(PHINode &PN) { … }

Instruction *InstCombinerImpl::foldPHIArgGEPIntoPHI(PHINode &PN) { … }

/// Return true if we know that it is safe to sink the load out of the block
/// that defines it. This means that it must be obvious the value of the load is
/// not changed from the point of the load to the end of the block it is in.
///
/// Finally, it is safe, but not profitable, to sink a load targeting a
/// non-address-taken alloca.  Doing so will cause us to not promote the alloca
/// to a register.
static bool isSafeAndProfitableToSinkLoad(LoadInst *L) { … }

Instruction *InstCombinerImpl::foldPHIArgLoadIntoPHI(PHINode &PN) { … }

/// TODO: This function could handle other cast types, but then it might
/// require special-casing a cast from the 'i1' type. See the comment in
/// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types.
Instruction *InstCombinerImpl::foldPHIArgZextsIntoPHI(PHINode &Phi) { … }

/// If all operands to a PHI node are the same "unary" operator and they all are
/// only used by the PHI, PHI together their inputs, and do the operation once,
/// to the result of the PHI.
Instruction *InstCombinerImpl::foldPHIArgOpIntoPHI(PHINode &PN) { … }

/// Return true if this phi node is always equal to NonPhiInVal.
/// This happens with mutually cyclic phi nodes like:
///   z = some value; x = phi (y, z); y = phi (x, z)
static bool PHIsEqualValue(PHINode *PN, Value *&NonPhiInVal,
                           SmallPtrSetImpl<PHINode *> &ValueEqualPHIs) { … }

/// Return an existing non-zero constant if this phi node has one, otherwise
/// return constant 1.
static ConstantInt *getAnyNonZeroConstInt(PHINode &PN) { … }

namespace {
struct PHIUsageRecord { … };

struct LoweredPHIRecord { … };
} // namespace

namespace llvm {
  template<>
  struct DenseMapInfo<LoweredPHIRecord> { … };
} // namespace llvm


/// This is an integer PHI and we know that it has an illegal type: see if it is
/// only used by trunc or trunc(lshr) operations. If so, we split the PHI into
/// the various pieces being extracted. This sort of thing is introduced when
/// SROA promotes an aggregate to large integer values.
///
/// TODO: The user of the trunc may be an bitcast to float/double/vector or an
/// inttoptr.  We should produce new PHIs in the right type.
///
Instruction *InstCombinerImpl::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) { … }

static Value *simplifyUsingControlFlow(InstCombiner &Self, PHINode &PN,
                                       const DominatorTree &DT) { … }

// Fold  iv = phi(start, iv.next = iv2.next op start)
// where iv2 = phi(iv2.start, iv2.next = iv2 + iv2.step)
// and   iv2.start op start = start
// to    iv = iv2 op start
static Value *foldDependentIVs(PHINode &PN, IRBuilderBase &Builder) { … }

// PHINode simplification
//
Instruction *InstCombinerImpl::visitPHINode(PHINode &PN) { … }
llvm/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp
