This file implements transforms for initial VPlan construction. More...

#include "LoopVectorizationPlanner.h"
#include "VPlan.h"
#include "VPlanAnalysis.h"
#include "VPlanCFG.h"
#include "VPlanDominatorTree.h"
#include "VPlanHelpers.h"
#include "VPlanPatternMatch.h"
#include "VPlanTransforms.h"
#include "VPlanUtils.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/LoopVersioning.h"

Macros
#define	DEBUG_TYPE "vplan"

Functions
static bool	isHeaderBB (BasicBlock BB, Loop L)
static bool	canonicalHeaderAndLatch (VPBlockBase *HeaderVPB, const VPDominatorTree &VPDT)
	Checks if `HeaderVPB` is a loop header block in the plain CFG; that is, it has exactly 2 predecessors (preheader and latch), where the block dominates the latch and the preheader dominates the block.
static void	createLoopRegion (VPlan &Plan, VPBlockBase *HeaderVPB)
	Create a new VPRegionBlock for the loop starting at `HeaderVPB`.
static void	addCanonicalIVRecipes (VPlan &Plan, VPBasicBlock HeaderVPBB, VPBasicBlock LatchVPBB, Type *IdxTy, DebugLoc DL)
static void	createExtractsForLiveOuts (VPlan &Plan, VPBasicBlock *MiddleVPBB)
	Creates extracts for values in `Plan` defined in a loop region and used outside a loop region.
static auto	getMatchingPhisForScalarLoop (VPBasicBlock Header, VPBasicBlock ScalarHeader)
	Return an iterator range to iterate over pairs of matching phi nodes in `Header` and `ScalarHeader`, skipping the canonical IV in the former.
static void	addInitialSkeleton (VPlan &Plan, Type InductionTy, DebugLoc IVDL, PredicatedScalarEvolution &PSE, Loop TheLoop)
static void	simplifyLiveInsWithSCEV (VPlan &Plan, PredicatedScalarEvolution &PSE)
	Check `Plan's` live-in and replace them with constants, if they can be simplified via SCEV.
static void	printAfterInitialConstruction (VPlan &)
	To make RUN_VPLAN_PASS print initial VPlan.
static VPHeaderPHIRecipe *	createWidenInductionRecipe (PHINode Phi, VPPhi PhiR, VPIRValue *Start, const InductionDescriptor &IndDesc, VPlan &Plan, PredicatedScalarEvolution &PSE, Loop &OrigLoop, DebugLoc DL)
	Creates a VPWidenIntOrFpInductionRecipe or VPWidenPointerInductionRecipe for `Phi` based on `IndDesc`.
static bool	areAllLoadsDereferenceable (VPBasicBlock HeaderVPBB, VPBasicBlock MiddleVPBB, Loop TheLoop, PredicatedScalarEvolution &PSE, DominatorTree &DT, AssumptionCache AC)
	Check if all loads in the loop are dereferenceable.
static void	insertCheckBlockBeforeVectorLoop (VPlan &Plan, VPBasicBlock *CheckBlockVPBB)
	Insert `CheckBlockVPBB` on the edge leading to the vector preheader, connecting it to both vector and scalar preheaders.
static void	addBypassBranch (VPlan &Plan, VPBasicBlock CheckBlockVPBB, VPValue Cond, bool AddBranchWeights)
	Create a BranchOnCond terminator in `CheckBlockVPBB`.
static VPInstruction *	findFindIVSelect (VPValue *BackedgeVal)
	Find and return the final select instruction of the FindIV result pattern for the given `BackedgeVal:` select(icmp ne ComputeReductionResult(ReducedIV), Sentinel), ComputeReductionResult(ReducedIV), Start.
static bool	handleFirstArgMinOrMax (VPlan &Plan, VPReductionPHIRecipe MinOrMaxPhiR, VPReductionPHIRecipe FindLastIVPhiR, VPWidenIntOrFpInductionRecipe WideIV, VPInstruction MinOrMaxResult, VPInstruction FindIVSelect, VPRecipeBase FindIVCmp, VPInstruction *FindIVRdxResult)
	Given a first argmin/argmax pattern with strict predicate consisting of 1) a MinOrMax reduction `MinOrMaxPhiR` producing `MinOrMaxResult`, 2) a wide induction `WideIV`, 3) a FindLastIV reduction `FindLastIVPhiR` using `WideIV`, return the smallest index of the FindLastIV reduction result using UMin, unless `MinOrMaxResult` equals the start value of its MinOrMax reduction.

Variables
static constexpr uint32_t	CheckBypassWeights [] = {1, 127}

Detailed Description

This file implements transforms for initial VPlan construction.

Definition in file VPlanConstruction.cpp.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "vplan"

Definition at line 36 of file VPlanConstruction.cpp.

Function Documentation

◆ addBypassBranch()

void addBypassBranch	(	VPlan &	Plan,
		VPBasicBlock *	CheckBlockVPBB,
		VPValue *	Cond,
		bool	AddBranchWeights )

static

Create a BranchOnCond terminator in CheckBlockVPBB.

Optionally adds branch weights.

Definition at line 1197 of file VPlanConstruction.cpp.

References llvm::VPInstruction::BranchOnCond, CheckBypassWeights, Cond, llvm::MDBuilder::createBranchWeights(), llvm::VPBuilder::createNaryOp(), DL, llvm::VPRegionBlock::getCanonicalIV(), llvm::VPlan::getContext(), llvm::VPRecipeBase::getDebugLoc(), and llvm::VPlan::getVectorLoopRegion().

Referenced by llvm::VPlanTransforms::attachCheckBlock().

◆ addCanonicalIVRecipes()

void addCanonicalIVRecipes	(	VPlan &	Plan,
		VPBasicBlock *	HeaderVPBB,
		VPBasicBlock *	LatchVPBB,
		Type *	IdxTy,
		DebugLoc	DL )

static

Definition at line 461 of file VPlanConstruction.cpp.

References llvm::VPBasicBlock::back(), llvm::VPBasicBlock::begin(), llvm::VPInstruction::BranchOnCount, DL, llvm::VPBasicBlock::empty(), llvm::VPRecipeBase::eraseFromParent(), llvm::VPlan::getConstantInt(), llvm::VPRecipeBase::getDebugLoc(), llvm::VPBasicBlock::getTerminator(), llvm::VPlan::getVectorTripCount(), llvm::VPlan::getVFxUF(), llvm::VPBasicBlock::insert(), llvm::VPlanPatternMatch::m_BranchOnCond(), and llvm::PatternMatch::match().

Referenced by addInitialSkeleton().

◆ addInitialSkeleton()

void addInitialSkeleton	(	VPlan &	Plan,
		Type *	InductionTy,
		DebugLoc	IVDL,
		PredicatedScalarEvolution &	PSE,
		Loop *	TheLoop )

static

Definition at line 519 of file VPlanConstruction.cpp.

References addCanonicalIVRecipes(), llvm::VPUser::addOperand(), assert(), canonicalHeaderAndLatch(), llvm::cast(), llvm::VPBlockUtils::connectBlocks(), createExtractsForLiveOuts(), llvm::VPBuilder::createNaryOp(), llvm::VPBuilder::createScalarPhi(), llvm::VPlan::createVPBasicBlock(), llvm::equal(), llvm::VPInstruction::ExtractLastLane, llvm::VPInstruction::ExtractLastPart, llvm::VPlan::getEntry(), llvm::VPBasicBlock::getFirstNonPhi(), getMatchingPhisForScalarLoop(), llvm::vputils::getOrCreateVPValueForSCEVExpr(), llvm::VPBlockBase::getPredecessors(), llvm::VPlan::getScalarHeader(), llvm::PredicatedScalarEvolution::getSE(), llvm::VPBlockBase::getSingleSuccessor(), llvm::VPBlockBase::getSuccessors(), llvm::PredicatedScalarEvolution::getSymbolicMaxBackedgeTakenCount(), llvm::ScalarEvolution::getTripCountFromExitCount(), llvm::VPBlockUtils::insertBlockAfter(), llvm::VPBlockUtils::insertOnEdge(), llvm::isa(), llvm::VPlan::setTripCount(), and llvm::VPBlockBase::swapSuccessors().

Referenced by llvm::VPlanTransforms::buildVPlan0().

◆ areAllLoadsDereferenceable()

bool areAllLoadsDereferenceable	(	VPBasicBlock *	HeaderVPBB,
		VPBasicBlock *	MiddleVPBB,
		Loop *	TheLoop,
		PredicatedScalarEvolution &	PSE,
		DominatorTree &	DT,
		AssumptionCache *	AC )

static

Check if all loads in the loop are dereferenceable.

Iterates over all blocks reachable from HeaderVPBB, skipping MiddleVPBB. Returns false if any non-dereferenceable load is found.

Definition at line 945 of file VPlanConstruction.cpp.

References llvm::VPBlockUtils::blocksOnly(), llvm::cast(), llvm::dbgs(), DL, llvm::dyn_cast(), llvm::BasicBlock::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::vputils::getSCEVExprForVPValue(), llvm::PredicatedScalarEvolution::getSE(), llvm::ScalarEvolution::getStoreSizeOfExpr(), llvm::SCEV::getType(), llvm::isa(), llvm::isDereferenceableAndAlignedInLoop(), LLVM_DEBUG, and llvm::vp_depth_first_shallow().

Referenced by llvm::VPlanTransforms::handleEarlyExits().

◆ canonicalHeaderAndLatch()

bool canonicalHeaderAndLatch	(	VPBlockBase *	HeaderVPB,
		const VPDominatorTree &	VPDT )

static

Checks if HeaderVPB is a loop header block in the plain CFG; that is, it has exactly 2 predecessors (preheader and latch), where the block dominates the latch and the preheader dominates the block.

If it is a header block return true and canonicalize the predecessors of the header (making sure the preheader appears first and the latch second) and the successors of the latch (making sure the loop exit comes first). Otherwise return false.

Definition at line 386 of file VPlanConstruction.cpp.

References assert(), llvm::VPInstruction::BranchOnCond, llvm::cast(), llvm::DominatorTreeBase< NodeT, IsPostDom >::dominates(), getOpcode(), llvm::VPBlockBase::getPredecessors(), llvm::VPInstruction::Not, llvm::ArrayRef< T >::size(), std::swap(), and llvm::VPBlockBase::swapPredecessors().

Referenced by addInitialSkeleton(), and llvm::VPlanTransforms::createLoopRegions().

◆ createExtractsForLiveOuts()

void createExtractsForLiveOuts	(	VPlan &	Plan,
		VPBasicBlock *	MiddleVPBB )

static

Creates extracts for values in Plan defined in a loop region and used outside a loop region.

Definition at line 494 of file VPlanConstruction.cpp.

References B(), llvm::cast(), llvm::VPInstruction::ExtractLastLane, llvm::VPInstruction::ExtractLastPart, llvm::VPlan::getExitBlocks(), llvm::VPBasicBlock::getFirstNonPhi(), llvm::is_contained(), and llvm::isa().

Referenced by addInitialSkeleton().

◆ createLoopRegion()

void createLoopRegion	(	VPlan &	Plan,
		VPBlockBase *	HeaderVPB )

static

Create a new VPRegionBlock for the loop starting at HeaderVPB.

Definition at line 433 of file VPlanConstruction.cpp.

References llvm::VPBlockUtils::connectBlocks(), llvm::VPlan::createLoopRegion(), llvm::VPBlockUtils::disconnectBlocks(), llvm::VPBlockBase::getPredecessors(), llvm::VPBlockBase::setParent(), llvm::VPBlockUtils::transferSuccessors(), and llvm::vp_depth_first_shallow().

Referenced by llvm::VPlanTransforms::createLoopRegions().

◆ createWidenInductionRecipe()

VPHeaderPHIRecipe * createWidenInductionRecipe	(	PHINode *	Phi,
		VPPhi *	PhiR,
		VPIRValue *	Start,
		const InductionDescriptor &	IndDesc,
		VPlan &	Plan,
		PredicatedScalarEvolution &	PSE,
		Loop &	OrigLoop,
		DebugLoc	DL )

static

Creates a VPWidenIntOrFpInductionRecipe or VPWidenPointerInductionRecipe for Phi based on IndDesc.

Definition at line 631 of file VPlanConstruction.cpp.

References assert(), llvm::cast(), DL, llvm::VPInstruction::ExitingIVValue, llvm::VPValue::getDefiningRecipe(), llvm::vputils::getFlagsFromIndDesc(), llvm::InductionDescriptor::getKind(), llvm::VPlan::getLiveIn(), llvm::VPUser::getOperand(), llvm::vputils::getOrCreateVPValueForSCEVExpr(), llvm::VPlan::getScalarPreheader(), llvm::ScalarEvolution::getSCEV(), llvm::vputils::getSCEVExprForVPValue(), llvm::PredicatedScalarEvolution::getSE(), llvm::InductionDescriptor::getStartValue(), llvm::InductionDescriptor::getStep(), llvm::Value::getType(), llvm::VPlan::getVF(), llvm::VPlan::getVFxUF(), llvm::InductionDescriptor::IK_FpInduction, llvm::InductionDescriptor::IK_IntInduction, llvm::InductionDescriptor::IK_PtrInduction, llvm::is_contained(), llvm::ScalarEvolution::isLoopInvariant(), llvm::ScalarEvolution::isSCEVable(), llvm::PatternMatch::m_Add(), llvm::VPlanPatternMatch::m_ExtractLastLane(), llvm::VPlanPatternMatch::m_ExtractLastPart(), llvm::PatternMatch::m_Specific(), llvm::VPlanPatternMatch::m_VPValue(), llvm::PatternMatch::match(), llvm::VPUser::setOperand(), llvm::to_vector(), and llvm::VPValue::users().

Referenced by llvm::VPlanTransforms::createHeaderPhiRecipes().

◆ findFindIVSelect()

VPInstruction * findFindIVSelect ( VPValue * BackedgeVal )

static

Find and return the final select instruction of the FindIV result pattern for the given BackedgeVal: select(icmp ne ComputeReductionResult(ReducedIV), Sentinel), ComputeReductionResult(ReducedIV), Start.

Definition at line 1323 of file VPlanConstruction.cpp.

References llvm::cast(), llvm::dyn_cast(), llvm::vputils::findRecipe(), llvm::PatternMatch::m_Specific(), llvm::VPlanPatternMatch::m_VPValue(), and llvm::VPlanPatternMatch::matchFindIVResult().

Referenced by llvm::VPlanTransforms::handleMultiUseReductions().

◆ getMatchingPhisForScalarLoop()

auto getMatchingPhisForScalarLoop	(	VPBasicBlock *	Header,
		VPBasicBlock *	ScalarHeader )

static

Return an iterator range to iterate over pairs of matching phi nodes in Header and ScalarHeader, skipping the canonical IV in the former.

Definition at line 514 of file VPlanConstruction.cpp.

References llvm::drop_begin(), llvm::VPBasicBlock::phis(), and llvm::zip_equal().

Referenced by addInitialSkeleton(), and llvm::VPlanTransforms::createHeaderPhiRecipes().

◆ handleFirstArgMinOrMax()

bool handleFirstArgMinOrMax	(	VPlan &	Plan,
		VPReductionPHIRecipe *	MinOrMaxPhiR,
		VPReductionPHIRecipe *	FindLastIVPhiR,
		VPWidenIntOrFpInductionRecipe *	WideIV,
		VPInstruction *	MinOrMaxResult,
		VPInstruction *	FindIVSelect,
		VPRecipeBase *	FindIVCmp,
		VPInstruction *	FindIVRdxResult )

static

Given a first argmin/argmax pattern with strict predicate consisting of 1) a MinOrMax reduction MinOrMaxPhiR producing MinOrMaxResult, 2) a wide induction WideIV, 3) a FindLastIV reduction FindLastIVPhiR using WideIV, return the smallest index of the FindLastIV reduction result using UMin, unless MinOrMaxResult equals the start value of its MinOrMax reduction.

In that case, return the start value of the FindLastIV reduction instead. If WideIV is not canonical, a new canonical wide IV is added, and the final result is scaled back to the non-canonical WideIV. The final value of the FindLastIV reduction is originally computed using FindIVSelect, FindIVCmp, and FindIVRdxResult, which are replaced and removed. Returns true if the pattern was handled successfully, false otherwise.

Definition at line 1633 of file VPlanConstruction.cpp.

References assert(), llvm::cast(), llvm::VPInstruction::ComputeReductionResult, llvm::VPRecipeBase::eraseFromParent(), llvm::PoisonValue::get(), llvm::VPHeaderPHIRecipe::getBackedgeValue(), llvm::VPRegionBlock::getCanonicalIVType(), llvm::VPlan::getConstantInt(), llvm::VPRecipeBase::getDebugLoc(), llvm::VPValue::getDefiningRecipe(), llvm::VPWidenInductionRecipe::getInductionDescriptor(), llvm::APInt::getMaxValue(), llvm::VPUser::getOperand(), llvm::VPlan::getOrAddLiveIn(), llvm::VPHeaderPHIRecipe::getStartValue(), llvm::VPWidenIntOrFpInductionRecipe::getStartValue(), llvm::VPWidenInductionRecipe::getStepValue(), llvm::VPlan::getVectorLoopRegion(), llvm::VPReductionPHIRecipe::getVFScaleFactor(), llvm::VPWidenInductionRecipe::getVFValue(), llvm::CmpInst::ICMP_EQ, llvm::InductionDescriptor::IK_IntInduction, llvm::VPWidenIntOrFpInductionRecipe::isCanonical(), llvm::VPReductionPHIRecipe::isInLoop(), llvm::VPReductionPHIRecipe::isOrdered(), llvm::PatternMatch::m_Select(), llvm::VPlanPatternMatch::m_VPValue(), llvm::PatternMatch::match(), llvm::VPValue::replaceAllUsesWith(), llvm::VPUser::setOperand(), and llvm::UMin.

Referenced by llvm::VPlanTransforms::handleMultiUseReductions().

◆ insertCheckBlockBeforeVectorLoop()

void insertCheckBlockBeforeVectorLoop	(	VPlan &	Plan,
		VPBasicBlock *	CheckBlockVPBB )

static

Insert CheckBlockVPBB on the edge leading to the vector preheader, connecting it to both vector and scalar preheaders.

Updates scalar preheader phis to account for the new predecessor.

Definition at line 1174 of file VPlanConstruction.cpp.

References assert(), llvm::cast(), llvm::VPBlockUtils::connectBlocks(), llvm::VPlan::getScalarPreheader(), llvm::VPBlockBase::getSinglePredecessor(), llvm::VPlan::getVectorPreheader(), llvm::VPBlockUtils::insertOnEdge(), and llvm::VPBlockBase::swapSuccessors().

Referenced by llvm::VPlanTransforms::attachCheckBlock().

◆ isHeaderBB()

bool isHeaderBB	(	BasicBlock *	BB,
		Loop *	L )

static

Definition at line 99 of file VPlanConstruction.cpp.

◆ printAfterInitialConstruction()

void printAfterInitialConstruction ( VPlan & )

static

To make RUN_VPLAN_PASS print initial VPlan.

Definition at line 613 of file VPlanConstruction.cpp.

Referenced by llvm::VPlanTransforms::buildVPlan0().

◆ simplifyLiveInsWithSCEV()

void simplifyLiveInsWithSCEV	(	VPlan &	Plan,
		PredicatedScalarEvolution &	PSE )

static

Check Plan's live-in and replace them with constants, if they can be simplified via SCEV.

Definition at line 597 of file VPlanConstruction.cpp.

References llvm::CallingConv::C, llvm::dyn_cast(), llvm::VPlan::getLiveIns(), llvm::VPlan::getOrAddLiveIn(), llvm::vputils::getSCEVExprForVPValue(), and llvm::to_vector().

Referenced by llvm::VPlanTransforms::buildVPlan0().

Variable Documentation

◆ CheckBypassWeights

uint32_t CheckBypassWeights[] = {1, 127}

staticconstexpr

Definition at line 1193 of file VPlanConstruction.cpp.

Referenced by addBypassBranch().

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ addBypassBranch()

◆ addCanonicalIVRecipes()

◆ addInitialSkeleton()

◆ areAllLoadsDereferenceable()

◆ canonicalHeaderAndLatch()

◆ createExtractsForLiveOuts()

◆ createLoopRegion()

◆ createWidenInductionRecipe()

◆ findFindIVSelect()

◆ getMatchingPhisForScalarLoop()

◆ handleFirstArgMinOrMax()

◆ insertCheckBlockBeforeVectorLoop()

◆ isHeaderBB()

◆ printAfterInitialConstruction()

◆ simplifyLiveInsWithSCEV()

Variable Documentation

◆ CheckBypassWeights