Diff 410759

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombineInternal.h

Show All 17 Lines
#include "llvm/ADT/MapVector.h"		#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallVector.h"		#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ValueTracking.h"		#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Support/KnownBits.h"		#include "llvm/Support/KnownBits.h"

using namespace llvm;		using namespace llvm;

//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
// TruncInstCombine - looks for expression dags dominated by trunc instructions		// TruncInstCombine - looks for expression graphs dominated by trunc
// and for each eligible dag, it will create a reduced bit-width expression and		// instructions and for each eligible graph, it will create a reduced bit-width
// replace the old expression with this new one and remove the old one.		// expression and replace the old expression with this new one and remove the
// Eligible expression dag is such that:		// old one. Eligible expression graph is such that:
// 1. Contains only supported instructions.		// 1. Contains only supported instructions.
// 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.		// 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
// 3. Can be evaluated into type with reduced legal bit-width (or Trunc type).		// 3. Can be evaluated into type with reduced legal bit-width (or Trunc type).
// 4. All instructions in the dag must not have users outside the dag.		// 4. All instructions in the graph must not have users outside the graph.
// Only exception is for {ZExt, SExt}Inst with operand type equal to the		// Only exception is for {ZExt, SExt}Inst with operand type equal to the
// new reduced type chosen in (3).		// new reduced type chosen in (3).
//		//
// The motivation for this optimization is that evaluating and expression using		// The motivation for this optimization is that evaluating and expression using
// smaller bit-width is preferable, especially for vectorization where we can		// smaller bit-width is preferable, especially for vectorization where we can
// fit more values in one vectorized instruction. In addition, this optimization		// fit more values in one vectorized instruction. In addition, this optimization
// may decrease the number of cast instructions, but will not increase it.		// may decrease the number of cast instructions, but will not increase it.
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
Show All 16 Lines	class TruncInstCombine {
const DominatorTree &DT;		const DominatorTree &DT;

/// List of all TruncInst instructions to be processed.		/// List of all TruncInst instructions to be processed.
SmallVector<TruncInst *, 4> Worklist;		SmallVector<TruncInst *, 4> Worklist;

/// Current processed TruncInst instruction.		/// Current processed TruncInst instruction.
TruncInst *CurrentTruncInst = nullptr;		TruncInst *CurrentTruncInst = nullptr;

/// Information per each instruction in the expression dag.		/// Information per each instruction in the expression graph.
struct Info {		struct Info {
/// Number of LSBs that are needed to generate a valid expression.		/// Number of LSBs that are needed to generate a valid expression.
unsigned ValidBitWidth = 0;		unsigned ValidBitWidth = 0;
/// Minimum number of LSBs needed to generate the ValidBitWidth.		/// Minimum number of LSBs needed to generate the ValidBitWidth.
unsigned MinBitWidth = 0;		unsigned MinBitWidth = 0;
/// The reduced value generated to replace the old instruction.		/// The reduced value generated to replace the old instruction.
Value *NewValue = nullptr;		Value *NewValue = nullptr;
};		};
/// An ordered map representing expression dag post-dominated by current		/// An ordered map representing expression graph post-dominated by current
/// processed TruncInst. It maps each instruction in the dag to its Info		/// processed TruncInst. It maps each instruction in the graph to its Info
/// structure. The map is ordered such that each instruction appears before		/// structure. The map is ordered such that each instruction appears before
/// all other instructions in the dag that uses it.		/// all other instructions in the graph that uses it.
MapVector<Instruction *, Info> InstInfoMap;		MapVector<Instruction *, Info> InstInfoMap;

public:		public:
TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI,		TruncInstCombine(AssumptionCache &AC, TargetLibraryInfo &TLI,
const DataLayout &DL, const DominatorTree &DT)		const DataLayout &DL, const DominatorTree &DT)
: AC(AC), TLI(TLI), DL(DL), DT(DT) {}		: AC(AC), TLI(TLI), DL(DL), DT(DT) {}

/// Perform TruncInst pattern optimization on given function.		/// Perform TruncInst pattern optimization on given function.
bool run(Function &F);		bool run(Function &F);

private:		private:
/// Build expression dag dominated by the /p CurrentTruncInst and append it to		/// Build expression graph dominated by the /p CurrentTruncInst and append it
/// the InstInfoMap container.		/// to the InstInfoMap container.
///		///
/// \return true only if succeed to generate an eligible sub expression dag.		/// \return true only if succeed to generate an eligible sub expression graph.
bool buildTruncExpressionDag();		bool buildTruncExpressionGraph();

/// Calculate the minimal allowed bit-width of the chain ending with the		/// Calculate the minimal allowed bit-width of the chain ending with the
/// currently visited truncate's operand.		/// currently visited truncate's operand.
///		///
/// \return minimum number of bits to which the chain ending with the		/// \return minimum number of bits to which the chain ending with the
/// truncate's operand can be shrunk to.		/// truncate's operand can be shrunk to.
unsigned getMinBitWidth();		unsigned getMinBitWidth();

/// Build an expression dag dominated by the current processed TruncInst and		/// Build an expression graph dominated by the current processed TruncInst and
/// Check if it is eligible to be reduced to a smaller type.		/// Check if it is eligible to be reduced to a smaller type.
///		///
/// \return the scalar version of the new type to be used for the reduced		/// \return the scalar version of the new type to be used for the reduced
/// expression dag, or nullptr if the expression dag is not eligible		/// expression graph, or nullptr if the expression graph is not
/// to be reduced.		/// eligible to be reduced.
Type *getBestTruncatedType();		Type *getBestTruncatedType();

KnownBits computeKnownBits(const Value *V) const {		KnownBits computeKnownBits(const Value *V) const {
return llvm::computeKnownBits(V, DL, /Depth=/0, &AC,		return llvm::computeKnownBits(V, DL, /Depth=/0, &AC,
/CtxI=/cast<Instruction>(CurrentTruncInst),		/CtxI=/cast<Instruction>(CurrentTruncInst),
&DT);		&DT);
}		}

unsigned ComputeNumSignBits(const Value *V) const {		unsigned ComputeNumSignBits(const Value *V) const {
return llvm::ComputeNumSignBits(		return llvm::ComputeNumSignBits(
V, DL, /Depth=/0, &AC, /CtxI=/cast<Instruction>(CurrentTruncInst),		V, DL, /Depth=/0, &AC, /CtxI=/cast<Instruction>(CurrentTruncInst),
&DT);		&DT);
}		}

/// Given a \p V value and a \p SclTy scalar type return the generated reduced		/// Given a \p V value and a \p SclTy scalar type return the generated reduced
/// value of \p V based on the type \p SclTy.		/// value of \p V based on the type \p SclTy.
///		///
/// \param V value to be reduced.		/// \param V value to be reduced.
/// \param SclTy scalar version of new type to reduce to.		/// \param SclTy scalar version of new type to reduce to.
/// \return the new reduced value.		/// \return the new reduced value.
Value getReducedOperand(Value V, Type *SclTy);		Value getReducedOperand(Value V, Type *SclTy);

/// Create a new expression dag using the reduced /p SclTy type and replace		/// Create a new expression graph using the reduced /p SclTy type and replace
/// the old expression dag with it. Also erase all instructions in the old		/// the old expression graph with it. Also erase all instructions in the old
/// dag, except those that are still needed outside the dag.		/// graph, except those that are still needed outside the graph.
///		///
/// \param SclTy scalar version of new type to reduce expression dag into.		/// \param SclTy scalar version of new type to reduce expression graph into.
void ReduceExpressionDag(Type *SclTy);		void ReduceExpressionGraph(Type *SclTy);
};		};
} // end namespace llvm.		} // end namespace llvm.

#endif		#endif

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

//===- TruncInstCombine.cpp -----------------------------------------------===//		//===- TruncInstCombine.cpp -----------------------------------------------===//
//		//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.		// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.		// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception		// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
//		//
// TruncInstCombine - looks for expression dags post-dominated by TruncInst and		// TruncInstCombine - looks for expression graphs post-dominated by TruncInst
// for each eligible dag, it will create a reduced bit-width expression, replace		// and for each eligible graph, it will create a reduced bit-width expression,
// the old expression with this new one and remove the old expression.		// replace the old expression with this new one and remove the old expression.
// Eligible expression dag is such that:		// Eligible expression graph is such that:
// 1. Contains only supported instructions.		// 1. Contains only supported instructions.
// 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.		// 2. Supported leaves: ZExtInst, SExtInst, TruncInst and Constant value.
// 3. Can be evaluated into type with reduced legal bit-width.		// 3. Can be evaluated into type with reduced legal bit-width.
// 4. All instructions in the dag must not have users outside the dag.		// 4. All instructions in the graph must not have users outside the graph.
// The only exception is for {ZExt, SExt}Inst with operand type equal to		// The only exception is for {ZExt, SExt}Inst with operand type equal to
// the new reduced type evaluated in (3).		// the new reduced type evaluated in (3).
//		//
// The motivation for this optimization is that evaluating and expression using		// The motivation for this optimization is that evaluating and expression using
// smaller bit-width is preferable, especially for vectorization where we can		// smaller bit-width is preferable, especially for vectorization where we can
// fit more values in one vectorized instruction. In addition, this optimization		// fit more values in one vectorized instruction. In addition, this optimization
// may decrease the number of cast instructions, but will not increase it.		// may decrease the number of cast instructions, but will not increase it.
//		//
Show All 9 Lines
#include "llvm/IR/IRBuilder.h"		#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instruction.h"		#include "llvm/IR/Instruction.h"
#include "llvm/Support/KnownBits.h"		#include "llvm/Support/KnownBits.h"

using namespace llvm;		using namespace llvm;

#define DEBUG_TYPE "aggressive-instcombine"		#define DEBUG_TYPE "aggressive-instcombine"

STATISTIC(		STATISTIC(NumExprsReduced, "Number of truncations eliminated by reducing bit "
NumDAGsReduced,		"width of expression graph");
"Number of truncations eliminated by reducing bit width of expression DAG");
STATISTIC(NumInstrsReduced,		STATISTIC(NumInstrsReduced,
"Number of instructions whose bit width was reduced");		"Number of instructions whose bit width was reduced");

/// Given an instruction and a container, it fills all the relevant operands of		/// Given an instruction and a container, it fills all the relevant operands of
/// that instruction, with respect to the Trunc expression dag optimizaton.		/// that instruction, with respect to the Trunc expression graph optimizaton.
static void getRelevantOperands(Instruction I, SmallVectorImpl<Value > &Ops) {		static void getRelevantOperands(Instruction I, SmallVectorImpl<Value > &Ops) {
unsigned Opc = I->getOpcode();		unsigned Opc = I->getOpcode();
switch (Opc) {		switch (Opc) {
case Instruction::Trunc:		case Instruction::Trunc:
case Instruction::ZExt:		case Instruction::ZExt:
case Instruction::SExt:		case Instruction::SExt:
// These CastInst are considered leaves of the evaluated expression, thus,		// These CastInst are considered leaves of the evaluated expression, thus,
// their operands are not relevent.		// their operands are not relevent.
Show All 15 Lines	case Instruction::InsertElement:
break;		break;
case Instruction::ExtractElement:		case Instruction::ExtractElement:
Ops.push_back(I->getOperand(0));		Ops.push_back(I->getOperand(0));
break;		break;
case Instruction::Select:		case Instruction::Select:
Ops.push_back(I->getOperand(1));		Ops.push_back(I->getOperand(1));
Ops.push_back(I->getOperand(2));		Ops.push_back(I->getOperand(2));
break;		break;
		case Instruction::PHI:
		for (Value *V : cast<PHINode>(I)->incoming_values())
		Ops.push_back(V);
		break;
default:		default:
llvm_unreachable("Unreachable!");		llvm_unreachable("Unreachable!");
}		}
}		}

bool TruncInstCombine::buildTruncExpressionDag() {		bool TruncInstCombine::buildTruncExpressionGraph() {
SmallVector<Value *, 8> Worklist;		SmallVector<Value *, 8> Worklist;
SmallVector<Instruction *, 8> Stack;		SmallVector<Instruction *, 8> Stack;
// Clear old expression dag.		// Clear old instructions info.
InstInfoMap.clear();		InstInfoMap.clear();

Worklist.push_back(CurrentTruncInst->getOperand(0));		Worklist.push_back(CurrentTruncInst->getOperand(0));

while (!Worklist.empty()) {		while (!Worklist.empty()) {
Value *Curr = Worklist.back();		Value *Curr = Worklist.back();

if (isa<Constant>(Curr)) {		if (isa<Constant>(Curr)) {
▲ Show 20 Lines • Show All 47 Lines • ▼ Show 20 Lines	while (!Worklist.empty()) {
case Instruction::InsertElement:		case Instruction::InsertElement:
case Instruction::ExtractElement:		case Instruction::ExtractElement:
case Instruction::Select: {		case Instruction::Select: {
SmallVector<Value *, 2> Operands;		SmallVector<Value *, 2> Operands;
getRelevantOperands(I, Operands);		getRelevantOperands(I, Operands);
append_range(Worklist, Operands);		append_range(Worklist, Operands);
break;		break;
}		}
		case Instruction::PHI: {
		SmallVector<Value *, 2> Operands;
		getRelevantOperands(I, Operands);
		// Add only operands not in Stack to prevent cycle
		for (auto *Op : Operands)
		lebedev.riUnsubmitted Done Reply Inline Actions `Stack` should be a SetVector then. Also, could use a comment. lebedev.ri: `Stack` should be a SetVector then. Also, could use a comment.
		anton-afanasyevAuthorUnsubmitted Done Reply Inline Actions `Stack` is already used as stack, we need to push/pop from it. Added comment. anton-afanasyev: `Stack` is already used as stack, we need to push/pop from it. Added comment.
		if (all_of(Stack, [Op](Value *V) { return Op != V; }))
		Worklist.push_back(Op);
		break;
		}
default:		default:
// TODO: Can handle more cases here:		// TODO: Can handle more cases here:
// 1. shufflevector		// 1. shufflevector
// 2. sdiv, srem		// 2. sdiv, srem
// 3. phi node(and loop handling)
// ...		// ...
return false;		return false;
}		}
}		}
return true;		return true;
}		}

unsigned TruncInstCombine::getMinBitWidth() {		unsigned TruncInstCombine::getMinBitWidth() {
▲ Show 20 Lines • Show All 83 Lines • ▼ Show 20 Lines	if (MinBitWidth > TruncBitWidth) {
bool ToLegal = MinBitWidth == 1 \|\| DL.isLegalInteger(MinBitWidth);		bool ToLegal = MinBitWidth == 1 \|\| DL.isLegalInteger(MinBitWidth);
if (!DstTy->isVectorTy() && FromLegal && !ToLegal)		if (!DstTy->isVectorTy() && FromLegal && !ToLegal)
return OrigBitWidth;		return OrigBitWidth;
}		}
return MinBitWidth;		return MinBitWidth;
}		}

Type *TruncInstCombine::getBestTruncatedType() {		Type *TruncInstCombine::getBestTruncatedType() {
if (!buildTruncExpressionDag())		if (!buildTruncExpressionGraph())
return nullptr;		return nullptr;

// We don't want to duplicate instructions, which isn't profitable. Thus, we		// We don't want to duplicate instructions, which isn't profitable. Thus, we
// can't shrink something that has multiple users, unless all users are		// can't shrink something that has multiple users, unless all users are
// post-dominated by the trunc instruction, i.e., were visited during the		// post-dominated by the trunc instruction, i.e., were visited during the
// expression evaluation.		// expression evaluation.
unsigned DesiredBitWidth = 0;		unsigned DesiredBitWidth = 0;
for (auto Itr : InstInfoMap) {		for (auto Itr : InstInfoMap) {
▲ Show 20 Lines • Show All 96 Lines • ▼ Show 20 Lines	Value TruncInstCombine::getReducedOperand(Value V, Type *SclTy) {
}		}

auto *I = cast<Instruction>(V);		auto *I = cast<Instruction>(V);
Info Entry = InstInfoMap.lookup(I);		Info Entry = InstInfoMap.lookup(I);
assert(Entry.NewValue);		assert(Entry.NewValue);
return Entry.NewValue;		return Entry.NewValue;
}		}

void TruncInstCombine::ReduceExpressionDag(Type *SclTy) {		void TruncInstCombine::ReduceExpressionGraph(Type *SclTy) {
NumInstrsReduced += InstInfoMap.size();		NumInstrsReduced += InstInfoMap.size();
		// Pairs of old and new phi-nodes
		SmallVector<std::pair<PHINode , PHINode >, 2> OldNewPHINodes;
for (auto &Itr : InstInfoMap) { // Forward		for (auto &Itr : InstInfoMap) { // Forward
Instruction *I = Itr.first;		Instruction *I = Itr.first;
TruncInstCombine::Info &NodeInfo = Itr.second;		TruncInstCombine::Info &NodeInfo = Itr.second;

assert(!NodeInfo.NewValue && "Instruction has been evaluated");		assert(!NodeInfo.NewValue && "Instruction has been evaluated");

IRBuilder<> Builder(I);		IRBuilder<> Builder(I);
Value *Res = nullptr;		Value *Res = nullptr;
▲ Show 20 Lines • Show All 66 Lines • ▼ Show 20 Lines	for (auto &Itr : InstInfoMap) { // Forward
}		}
case Instruction::Select: {		case Instruction::Select: {
Value *Op0 = I->getOperand(0);		Value *Op0 = I->getOperand(0);
Value *LHS = getReducedOperand(I->getOperand(1), SclTy);		Value *LHS = getReducedOperand(I->getOperand(1), SclTy);
Value *RHS = getReducedOperand(I->getOperand(2), SclTy);		Value *RHS = getReducedOperand(I->getOperand(2), SclTy);
Res = Builder.CreateSelect(Op0, LHS, RHS);		Res = Builder.CreateSelect(Op0, LHS, RHS);
break;		break;
}		}
		case Instruction::PHI: {
		Res = Builder.CreatePHI(getReducedType(I, SclTy), I->getNumOperands());
		OldNewPHINodes.push_back(
		std::make_pair(cast<PHINode>(I), cast<PHINode>(Res)));
		break;
		}
default:		default:
llvm_unreachable("Unhandled instruction");		llvm_unreachable("Unhandled instruction");
}		}

NodeInfo.NewValue = Res;		NodeInfo.NewValue = Res;
if (auto *ResI = dyn_cast<Instruction>(Res))		if (auto *ResI = dyn_cast<Instruction>(Res))
ResI->takeName(I);		ResI->takeName(I);
}		}

		for (auto &Node : OldNewPHINodes) {
		PHINode *OldPN = Node.first;
		PHINode *NewPN = Node.second;
		for (auto Incoming : zip(OldPN->incoming_values(), OldPN->blocks()))
		NewPN->addIncoming(getReducedOperand(std::get<0>(Incoming), SclTy),
		std::get<1>(Incoming));
		}

Value *Res = getReducedOperand(CurrentTruncInst->getOperand(0), SclTy);		Value *Res = getReducedOperand(CurrentTruncInst->getOperand(0), SclTy);
Type *DstTy = CurrentTruncInst->getType();		Type *DstTy = CurrentTruncInst->getType();
if (Res->getType() != DstTy) {		if (Res->getType() != DstTy) {
IRBuilder<> Builder(CurrentTruncInst);		IRBuilder<> Builder(CurrentTruncInst);
Res = Builder.CreateIntCast(Res, DstTy, false);		Res = Builder.CreateIntCast(Res, DstTy, false);
if (auto *ResI = dyn_cast<Instruction>(Res))		if (auto *ResI = dyn_cast<Instruction>(Res))
ResI->takeName(CurrentTruncInst);		ResI->takeName(CurrentTruncInst);
}		}
CurrentTruncInst->replaceAllUsesWith(Res);		CurrentTruncInst->replaceAllUsesWith(Res);

// Erase old expression dag, which was replaced by the reduced expression dag.		// Erase old expression graph, which was replaced by the reduced expression
// We iterate backward, which means we visit the instruction before we visit		// graph.
// any of its operands, this way, when we get to the operand, we already
// removed the instructions (from the expression dag) that uses it.
CurrentTruncInst->eraseFromParent();		CurrentTruncInst->eraseFromParent();
		// First, erase old phi-nodes and its uses
		for (auto &Node : OldNewPHINodes) {
		PHINode *OldPN = Node.first;
		OldPN->replaceAllUsesWith(PoisonValue::get(OldPN->getType()));
		OldPN->eraseFromParent();
		}
		// Now we have expression graph turned into dag.
		// We iterate backward, which means we visit the instruction before we
		// visit any of its operands, this way, when we get to the operand, we already
		// removed the instructions (from the expression dag) that uses it.
for (auto &I : llvm::reverse(InstInfoMap)) {		for (auto &I : llvm::reverse(InstInfoMap)) {
		// Skip phi-nodes since they were erased before
		if (isa<PHINode>(I.first))
		continue;
// We still need to check that the instruction has no users before we erase		// We still need to check that the instruction has no users before we erase
// it, because {SExt, ZExt}Inst Instruction might have other users that was		// it, because {SExt, ZExt}Inst Instruction might have other users that was
// not reduced, in such case, we need to keep that instruction.		// not reduced, in such case, we need to keep that instruction.
if (I.first->use_empty())		if (I.first->use_empty())
I.first->eraseFromParent();		I.first->eraseFromParent();
		else
		assert((isa<SExtInst>(I.first) \|\| isa<ZExtInst>(I.first)) &&
		"Only {SExt, ZExt}Inst might have unreduced users");
}		}
}		}

bool TruncInstCombine::run(Function &F) {		bool TruncInstCombine::run(Function &F) {
bool MadeIRChange = false;		bool MadeIRChange = false;

// Collect all TruncInst in the function into the Worklist for evaluating.		// Collect all TruncInst in the function into the Worklist for evaluating.
for (auto &BB : F) {		for (auto &BB : F) {
// Ignore unreachable basic block.		// Ignore unreachable basic block.
if (!DT.isReachableFromEntry(&BB))		if (!DT.isReachableFromEntry(&BB))
continue;		continue;
for (auto &I : BB)		for (auto &I : BB)
if (auto *CI = dyn_cast<TruncInst>(&I))		if (auto *CI = dyn_cast<TruncInst>(&I))
Worklist.push_back(CI);		Worklist.push_back(CI);
}		}

// Process all TruncInst in the Worklist, for each instruction:		// Process all TruncInst in the Worklist, for each instruction:
// 1. Check if it dominates an eligible expression dag to be reduced.		// 1. Check if it dominates an eligible expression graph to be reduced.
// 2. Create a reduced expression dag and replace the old one with it.		// 2. Create a reduced expression graph and replace the old one with it.
while (!Worklist.empty()) {		while (!Worklist.empty()) {
CurrentTruncInst = Worklist.pop_back_val();		CurrentTruncInst = Worklist.pop_back_val();

if (Type *NewDstSclTy = getBestTruncatedType()) {		if (Type *NewDstSclTy = getBestTruncatedType()) {
LLVM_DEBUG(		LLVM_DEBUG(
dbgs() << "ICE: TruncInstCombine reducing type of expression dag "		dbgs() << "ICE: TruncInstCombine reducing type of expression graph "
"dominated by: "		"dominated by: "
<< CurrentTruncInst << '\n');		<< CurrentTruncInst << '\n');
ReduceExpressionDag(NewDstSclTy);		ReduceExpressionGraph(NewDstSclTy);
++NumDAGsReduced;		++NumExprsReduced;
MadeIRChange = true;		MadeIRChange = true;
}		}
}		}

return MadeIRChange;		return MadeIRChange;
}		}

llvm/test/Transforms/AggressiveInstCombine/trunc_phi.ll

	; NOTE: Assertions have been autogenerated by utils/update_test_checks.py			; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
	; RUN: opt < %s -aggressive-instcombine -S \| FileCheck %s			; RUN: opt < %s -aggressive-instcombine -S \| FileCheck %s

	define i16 @trunc_phi(i8 %x) {			define i16 @trunc_phi(i8 %x) {
	; CHECK-LABEL: @trunc_phi(			; CHECK-LABEL: @trunc_phi(
	; CHECK-NEXT: LoopHeader:			; CHECK-NEXT: LoopHeader:
	; CHECK-NEXT: [[ZEXT:%.]] = zext i8 [[X:%.]] to i32			; CHECK-NEXT: [[ZEXT:%.]] = zext i8 [[X:%.]] to i16
	; CHECK-NEXT: br label [[LOOP:%.*]]			; CHECK-NEXT: br label [[LOOP:%.*]]
	; CHECK: Loop:			; CHECK: Loop:
	; CHECK-NEXT: [[ZEXT2:%.]] = phi i32 [ [[ZEXT]], [[LOOPHEADER:%.]] ], [ [[SHL:%.*]], [[LOOP]] ]			; CHECK-NEXT: [[ZEXT2:%.]] = phi i16 [ [[ZEXT]], [[LOOPHEADER:%.]] ], [ [[SHL:%.*]], [[LOOP]] ]
	; CHECK-NEXT: [[J:%.]] = phi i32 [ 0, [[LOOPHEADER]] ], [ [[I:%.]], [[LOOP]] ]			; CHECK-NEXT: [[J:%.]] = phi i32 [ 0, [[LOOPHEADER]] ], [ [[I:%.]], [[LOOP]] ]
	; CHECK-NEXT: [[SHL]] = shl i32 [[ZEXT2]], 1			; CHECK-NEXT: [[SHL]] = shl i16 [[ZEXT2]], 1
	; CHECK-NEXT: [[TRUNC:%.*]] = trunc i32 [[SHL]] to i16
	; CHECK-NEXT: [[I]] = add i32 [[J]], 1			; CHECK-NEXT: [[I]] = add i32 [[J]], 1
	; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[I]], 10			; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[I]], 10
	; CHECK-NEXT: br i1 [[CMP]], label [[LOOPEND:%.*]], label [[LOOP]]			; CHECK-NEXT: br i1 [[CMP]], label [[LOOPEND:%.*]], label [[LOOP]]
	; CHECK: LoopEnd:			; CHECK: LoopEnd:
	; CHECK-NEXT: ret i16 [[TRUNC]]			; CHECK-NEXT: ret i16 [[SHL]]
	;			;
	LoopHeader:			LoopHeader:
	%zext = zext i8 %x to i32			%zext = zext i8 %x to i32
	br label %Loop			br label %Loop

	Loop:			Loop:
	%zext2 = phi i32 [%zext, %LoopHeader], [%shl, %Loop]			%zext2 = phi i32 [%zext, %LoopHeader], [%shl, %Loop]
	%j = phi i32 [0, %LoopHeader], [%i, %Loop]			%j = phi i32 [0, %LoopHeader], [%i, %Loop]
	%shl = shl i32 %zext2, 1			%shl = shl i32 %zext2, 1
	%trunc = trunc i32 %shl to i16			%trunc = trunc i32 %shl to i16
	%i = add i32 %j, 1			%i = add i32 %j, 1
	%cmp = icmp eq i32 %i, 10			%cmp = icmp eq i32 %i, 10
	br i1 %cmp, label %LoopEnd, label %Loop			br i1 %cmp, label %LoopEnd, label %Loop

	LoopEnd:			LoopEnd:
	ret i16 %trunc			ret i16 %trunc
	}			}

	define i16 @trunc_phi2(i8 %x, i32 %sw) {			define i16 @trunc_phi2(i8 %x, i32 %sw) {
	; CHECK-LABEL: @trunc_phi2(			; CHECK-LABEL: @trunc_phi2(
	; CHECK-NEXT: LoopHeader:			; CHECK-NEXT: LoopHeader:
	; CHECK-NEXT: [[ZEXT:%.]] = zext i8 [[X:%.]] to i32			; CHECK-NEXT: [[ZEXT:%.]] = zext i8 [[X:%.]] to i16
	; CHECK-NEXT: switch i32 [[SW:%.]], label [[LOOPEND:%.]] [			; CHECK-NEXT: switch i32 [[SW:%.]], label [[LOOPEND:%.]] [
	; CHECK-NEXT: i32 0, label [[LOOP:%.*]]			; CHECK-NEXT: i32 0, label [[LOOP:%.*]]
	; CHECK-NEXT: i32 1, label [[LOOP]]			; CHECK-NEXT: i32 1, label [[LOOP]]
	; CHECK-NEXT: ]			; CHECK-NEXT: ]
	; CHECK: Loop:			; CHECK: Loop:
	; CHECK-NEXT: [[ZEXT2:%.]] = phi i32 [ [[ZEXT]], [[LOOPHEADER:%.]] ], [ [[ZEXT]], [[LOOPHEADER]] ], [ [[SHL:%.*]], [[LOOP]] ]			; CHECK-NEXT: [[ZEXT2:%.]] = phi i16 [ [[ZEXT]], [[LOOPHEADER:%.]] ], [ [[ZEXT]], [[LOOPHEADER]] ], [ [[SHL:%.*]], [[LOOP]] ]
	; CHECK-NEXT: [[J:%.]] = phi i32 [ 0, [[LOOPHEADER]] ], [ 0, [[LOOPHEADER]] ], [ [[I:%.]], [[LOOP]] ]			; CHECK-NEXT: [[J:%.]] = phi i32 [ 0, [[LOOPHEADER]] ], [ 0, [[LOOPHEADER]] ], [ [[I:%.]], [[LOOP]] ]
	; CHECK-NEXT: [[SHL]] = shl i32 [[ZEXT2]], 1			; CHECK-NEXT: [[SHL]] = shl i16 [[ZEXT2]], 1
	; CHECK-NEXT: [[I]] = add i32 [[J]], 1			; CHECK-NEXT: [[I]] = add i32 [[J]], 1
	; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[I]], 10			; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[I]], 10
	; CHECK-NEXT: br i1 [[CMP]], label [[LOOPEND]], label [[LOOP]]			; CHECK-NEXT: br i1 [[CMP]], label [[LOOPEND]], label [[LOOP]]
	; CHECK: LoopEnd:			; CHECK: LoopEnd:
	; CHECK-NEXT: [[ZEXT3:%.*]] = phi i32 [ [[ZEXT]], [[LOOPHEADER]] ], [ [[ZEXT2]], [[LOOP]] ]			; CHECK-NEXT: [[ZEXT3:%.*]] = phi i16 [ [[ZEXT]], [[LOOPHEADER]] ], [ [[ZEXT2]], [[LOOP]] ]
	; CHECK-NEXT: [[TRUNC:%.*]] = trunc i32 [[ZEXT3]] to i16			; CHECK-NEXT: ret i16 [[ZEXT3]]
	; CHECK-NEXT: ret i16 [[TRUNC]]
	;			;
	LoopHeader:			LoopHeader:
	%zext = zext i8 %x to i32			%zext = zext i8 %x to i32
	switch i32 %sw, label %LoopEnd [ i32 0, label %Loop			switch i32 %sw, label %LoopEnd [ i32 0, label %Loop
	i32 1, label %Loop ]			i32 1, label %Loop ]

	Loop:			Loop:
	%zext2 = phi i32 [%zext, %LoopHeader], [%zext, %LoopHeader], [%shl, %Loop]			%zext2 = phi i32 [%zext, %LoopHeader], [%zext, %LoopHeader], [%shl, %Loop]
	Show All 11 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[AggressiveInstCombine] Add `phi` nodes support to `TruncInstCombine`
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 410759

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombineInternal.h

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

llvm/test/Transforms/AggressiveInstCombine/trunc_phi.ll

This is an archive of the discontinued LLVM Phabricator instance.

[AggressiveInstCombine] Add `phi` nodes support to `TruncInstCombine`ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 410759

llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombineInternal.h

llvm/lib/Transforms/AggressiveInstCombine/TruncInstCombine.cpp

llvm/test/Transforms/AggressiveInstCombine/trunc_phi.ll

[AggressiveInstCombine] Add `phi` nodes support to `TruncInstCombine`
ClosedPublic