Index: llvm/include/llvm/Analysis/DomConditionAnalysis.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/DomConditionAnalysis.h @@ -0,0 +1,50 @@ +//===- DomConditionAnalysis.cpp - ------------------------------*- C++ -*-===// +// +// 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 DomConditionAnalysis class +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_DOMCONDITIONANALYSIS_H +#define LLVM_ANALYSIS_DOMCONDITIONANALYSIS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" + +namespace llvm { + +struct DomCondition { + const BasicBlock *DomBB; + Value *LHS; + Value *RHS; + CmpInst::Predicate Pred; +}; + +class DomConditionInfo { + typedef SmallVector DomCondVector; + +private: + // Map from basic block to the list of conditions that dominate it. + SmallDenseMap DomCondMap; + +public: + DomConditionInfo() {} + DomConditionInfo(Function &F, DominatorTree &DT); + + std::pair + getDominatingCondition(const BasicBlock *BB, const Value *LHS, + const Value *RHS) const; + void print(raw_ostream &OS) const; + void clear() { DomCondMap.clear(); } +}; + +} // namespace llvm + +#endif // LLVM_ANALYSIS_DOMCONDITIONANALYSIS_H \ No newline at end of file Index: llvm/include/llvm/Analysis/InstructionSimplify.h =================================================================== --- llvm/include/llvm/Analysis/InstructionSimplify.h +++ llvm/include/llvm/Analysis/InstructionSimplify.h @@ -45,6 +45,7 @@ class BinaryOperator; class CallBase; class DataLayout; +class DomConditionInfo; class DominatorTree; class Function; class Instruction; @@ -107,6 +108,8 @@ /// allowed to assume a particular value for a use of undef for example. bool CanUseUndef = true; + const DomConditionInfo *DCI = nullptr; + SimplifyQuery(const DataLayout &DL, const Instruction *CXTI = nullptr) : DL(DL), CxtI(CXTI) {} @@ -114,9 +117,9 @@ const DominatorTree *DT = nullptr, AssumptionCache *AC = nullptr, const Instruction *CXTI = nullptr, bool UseInstrInfo = true, - bool CanUseUndef = true) + bool CanUseUndef = true, const DomConditionInfo *DCI = nullptr) : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI), IIQ(UseInstrInfo), - CanUseUndef(CanUseUndef) {} + CanUseUndef(CanUseUndef), DCI(DCI) {} SimplifyQuery getWithInstruction(Instruction *I) const { SimplifyQuery Copy(*this); Copy.CxtI = I; Index: llvm/include/llvm/Analysis/ValueTracking.h =================================================================== --- llvm/include/llvm/Analysis/ValueTracking.h +++ llvm/include/llvm/Analysis/ValueTracking.h @@ -30,6 +30,7 @@ class AllocaInst; class APInt; class AssumptionCache; +class DomConditionInfo; class DominatorTree; class GEPOperator; class LoadInst; @@ -963,10 +964,11 @@ std::optional isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL); -std::optional isImpliedByDomCondition(CmpInst::Predicate Pred, - const Value *LHS, const Value *RHS, - const Instruction *ContextI, - const DataLayout &DL); +std::optional +isImpliedByDomCondition(CmpInst::Predicate Pred, const Value *LHS, + const Value *RHS, const Instruction *ContextI, + const DataLayout &DL, + const DomConditionInfo *DCI = nullptr); /// If Ptr1 is provably equal to Ptr2 plus a constant offset, return that /// offset. For example, Ptr1 might be &A[42], and Ptr2 might be &A[40]. In Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -57,6 +57,7 @@ DependenceGraphBuilder.cpp DevelopmentModeInlineAdvisor.cpp DivergenceAnalysis.cpp + DomConditionAnalysis.cpp DomPrinter.cpp DomTreeUpdater.cpp DominanceFrontier.cpp Index: llvm/lib/Analysis/DomConditionAnalysis.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/DomConditionAnalysis.cpp @@ -0,0 +1,113 @@ +//===- DomConditionAnalysis.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 +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/DomConditionAnalysis.h" +#include "llvm/ADT/BreadthFirstIterator.h" +#include "llvm/IR/PatternMatch.h" + +using namespace llvm; +using namespace PatternMatch; + +DomConditionInfo::DomConditionInfo(Function &F, DominatorTree &DT) { + DT.updateDFSNumbers(); + + for (auto &BB : F) { + if (BB.isEntryBlock()) + continue; + + auto *DTNode = DT.getNode(&BB); + if (!DTNode) + continue; + + while (DTNode->getIDom()) { + auto *IDom = DTNode->getIDom(); + auto *IDomBB = IDom->getBlock(); + + // We only handle the case where the terminator has two successors for + // now. + auto *Term = IDomBB->getTerminator(); + if (Term->getNumSuccessors() != 2) + break; + + auto &CurrentVec = DomCondMap[&BB]; + if (auto *I = dyn_cast(Term->getOperand(0))) { + std::function GenDomCondMap; + GenDomCondMap = [&](Instruction *Cond, bool TrueEdge, bool FalseEdge) { + Value *X, *Y; + // We only handle the case where the terminator is an icmp for now. + if (const auto *Cmp = dyn_cast(Cond)) { + if (TrueEdge) { + auto *TrueBB = Term->getSuccessor(0); + BasicBlockEdge TrueEdge(IDomBB, TrueBB); + if (DT.dominates(TrueEdge, &BB)) + CurrentVec.push_back({IDomBB, Cmp->getOperand(0), + Cmp->getOperand(1), Cmp->getPredicate()}); + } + if (FalseEdge) { + auto *FalseBB = Term->getSuccessor(1); + BasicBlockEdge FalseEdge(IDomBB, FalseBB); + if (DT.dominates(FalseEdge, &BB)) + CurrentVec.push_back({IDomBB, Cmp->getOperand(0), + Cmp->getOperand(1), + Cmp->getInversePredicate()}); + } + } else if (match(Cond, m_LogicalAnd(m_Value(X), m_Value(Y)))) { + if (auto *I = dyn_cast(X)) + GenDomCondMap(I, true, false); + if (auto *I = dyn_cast(Y)) + GenDomCondMap(I, true, false); + } else if (match(Cond, m_LogicalOr(m_Value(X), m_Value(Y)))) { + if (auto *I = dyn_cast(X)) + GenDomCondMap(I, false, true); + if (auto *I = dyn_cast(Y)) + GenDomCondMap(I, false, true); + } + }; + GenDomCondMap(I, true, true); + } + + auto DomVec = DomCondMap.find(IDomBB); + if (DomVec != DomCondMap.end()) { + CurrentVec.append(DomVec->second.begin(), DomVec->second.end()); + break; + } + DTNode = IDom; + continue; + } + } +} + +void DomConditionInfo::print(raw_ostream &OS) const { + OS << "Basic Block Dominate Conditions:\n"; + for (const auto &Entry : DomCondMap) { + OS << Entry.first->getName() << ":\n"; + for (const auto &Cond : Entry.second) { + Cond.LHS->printAsOperand(OS, false); + OS << " " << CmpInst::getPredicateName(Cond.Pred) << " "; + Cond.RHS->printAsOperand(OS, false); + } + OS << "\n"; + } +} + +std::pair +DomConditionInfo::getDominatingCondition(const BasicBlock *BB, const Value *LHS, + const Value *RHS) const { + auto It = DomCondMap.find(BB); + if (It == DomCondMap.end()) + return {nullptr, CmpInst::BAD_ICMP_PREDICATE}; + + for (const auto &Cond : It->second) { + if (Cond.LHS == LHS && Cond.RHS == RHS) + return {Cond.DomBB, Cond.Pred}; + + if (Cond.LHS == RHS && Cond.RHS == LHS) + return {Cond.DomBB, CmpInst::getSwappedPredicate(Cond.Pred)}; + } + return {nullptr, CmpInst::BAD_ICMP_PREDICATE}; +} Index: llvm/lib/Analysis/InstructionSimplify.cpp =================================================================== --- llvm/lib/Analysis/InstructionSimplify.cpp +++ llvm/lib/Analysis/InstructionSimplify.cpp @@ -757,7 +757,7 @@ return nullptr; std::optional Imp = - isImpliedByDomCondition(CmpInst::ICMP_EQ, Op0, Op1, Q.CxtI, Q.DL); + isImpliedByDomCondition(CmpInst::ICMP_EQ, Op0, Op1, Q.CxtI, Q.DL, Q.DCI); if (Imp && *Imp) { Type *Ty = Op0->getType(); switch (Opcode) { @@ -3972,7 +3972,7 @@ return V; if (std::optional Res = - isImpliedByDomCondition(Pred, LHS, RHS, Q.CxtI, Q.DL)) + isImpliedByDomCondition(Pred, LHS, RHS, Q.CxtI, Q.DL, Q.DCI)) return ConstantInt::getBool(ITy, *Res); // Simplify comparisons of related pointers using a powerful, recursive Index: llvm/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/lib/Analysis/ValueTracking.cpp +++ llvm/lib/Analysis/ValueTracking.cpp @@ -26,6 +26,7 @@ #include "llvm/Analysis/AssumeBundleQueries.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/ConstantFolding.h" +#include "llvm/Analysis/DomConditionAnalysis.h" #include "llvm/Analysis/GuardUtils.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/Loads.h" @@ -7599,12 +7600,21 @@ const Value *LHS, const Value *RHS, const Instruction *ContextI, - const DataLayout &DL) { + const DataLayout &DL, + const DomConditionInfo *DCI) { + std::optional IsImplied = std::nullopt; auto PredCond = getDomPredecessorCondition(ContextI); if (PredCond.first) - return isImpliedCondition(PredCond.first, Pred, LHS, RHS, DL, - PredCond.second); - return std::nullopt; + IsImplied = + isImpliedCondition(PredCond.first, Pred, LHS, RHS, DL, PredCond.second); + + if (DCI && IsImplied == std::nullopt && ContextI && ContextI->getParent()) { + const BasicBlock *BB = ContextI->getParent(); + auto DomCond = DCI->getDominatingCondition(BB, LHS, RHS); + if (DomCond.first) + IsImplied = isImpliedCondMatchingOperands(DomCond.second, Pred, false); + } + return IsImplied; } static void setLimitsForBinOp(const BinaryOperator &BO, APInt &Lower, Index: llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp =================================================================== --- llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp +++ llvm/lib/Transforms/Scalar/InstSimplifyPass.cpp @@ -10,6 +10,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/DomConditionAnalysis.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/TargetLibraryInfo.h" @@ -96,8 +97,7 @@ if (skipFunction(F)) return false; - const DominatorTree *DT = - &getAnalysis().getDomTree(); + DominatorTree *DT = &getAnalysis().getDomTree(); const TargetLibraryInfo *TLI = &getAnalysis().getTLI(F); AssumptionCache *AC = @@ -105,7 +105,8 @@ OptimizationRemarkEmitter *ORE = &getAnalysis().getORE(); const DataLayout &DL = F.getParent()->getDataLayout(); - const SimplifyQuery SQ(DL, TLI, DT, AC); + DomConditionInfo DCI(F, *DT); + const SimplifyQuery SQ(DL, TLI, DT, AC, nullptr, true, true, &DCI); return runImpl(F, SQ, ORE); } }; @@ -133,7 +134,8 @@ auto &AC = AM.getResult(F); auto &ORE = AM.getResult(F); const DataLayout &DL = F.getParent()->getDataLayout(); - const SimplifyQuery SQ(DL, &TLI, &DT, &AC); + DomConditionInfo DCI(F, DT); + const SimplifyQuery SQ(DL, &TLI, &DT, &AC, nullptr, true, true, &DCI); bool Changed = runImpl(F, SQ, &ORE); if (!Changed) return PreservedAnalyses::all(); Index: llvm/test/Transforms/InstSimplify/domcondition.ll =================================================================== --- llvm/test/Transforms/InstSimplify/domcondition.ll +++ llvm/test/Transforms/InstSimplify/domcondition.ll @@ -216,3 +216,61 @@ %cond = phi i32 [ %xor, %cond.true ], [ 0, %entry ] ret i32 %cond } + +define i32 @xor_simplify_by_dci(i32 %x, i32 %y, i1 %c) { +; CHECK-LABEL: @xor_simplify_by_dci( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]] +; CHECK: cond.true: +; CHECK-NEXT: br i1 [[C:%.*]], label [[XORBB:%.*]], label [[COND_END]] +; CHECK: xorbb: +; CHECK-NEXT: br label [[COND_END]] +; CHECK: cond.end: +; CHECK-NEXT: ret i32 0 +; +entry: + %cmp = icmp eq i32 %x, %y + br i1 %cmp, label %cond.true, label %cond.end + +cond.true: + br i1 %c, label %xorbb, label %cond.end + +xorbb: + %xor = xor i32 %x, %y + br label %cond.end + +cond.end: + %cond = phi i32 [ %xor, %xorbb ], [ 0, %entry ], [0, %cond.true] + ret i32 %cond +} + +define void @icmp_simplify_by_dci(i32 %a, i32 %b, i1 %x) { +; CHECK-LABEL: @icmp_simplify_by_dci( +; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]] +; CHECK: taken: +; CHECK-NEXT: br i1 [[X:%.*]], label [[SELBB:%.*]], label [[END]] +; CHECK: selbb: +; CHECK-NEXT: call void @foo(i32 20) +; CHECK-NEXT: br label [[END]] +; CHECK: end: +; CHECK-NEXT: ret void +; + %cmp1 = icmp eq i32 %a, %b + br i1 %cmp1, label %end, label %taken + +taken: + br i1 %x, label %selbb, label %end + +selbb: + %cmp2 = icmp ne i32 %a, %b + %c = select i1 %cmp2, i32 20, i32 0 + call void @foo(i32 %c) + br label %end + +end: + ret void +} + +declare void @foo(i32)