Index: llvm/include/llvm/Analysis/DomConditionAnalysis.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/DomConditionAnalysis.h @@ -0,0 +1,53 @@ +//===- 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; + + void InsertDomCondition(DominatorTree &DT, BasicBlock *BB, Instruction *Term, + Instruction *Cond, bool TrueEdge, bool FalseEdge); + +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,103 @@ +//===- 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/IR/PatternMatch.h" + +using namespace llvm; +using namespace PatternMatch; + +void DomConditionInfo::InsertDomCondition(DominatorTree &DT, BasicBlock *BB, + Instruction *Term, Instruction *Cond, + bool TrueEdge, bool FalseEdge) { + const auto *IDomBB = Term->getParent(); + + 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)) + DomCondMap[BB].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)) + DomCondMap[BB].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)) + InsertDomCondition(DT, BB, Term, I, true, false); + if (auto *I = dyn_cast(Y)) + InsertDomCondition(DT, BB, Term, I, true, false); + } else if (match(Cond, m_LogicalOr(m_Value(X), m_Value(Y)))) { + if (auto *I = dyn_cast(X)) + InsertDomCondition(DT, BB, Term, I, false, true); + if (auto *I = dyn_cast(Y)) + InsertDomCondition(DT, BB, Term, I, false, true); + } +} + +DomConditionInfo::DomConditionInfo(Function &F, DominatorTree &DT) { + 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 *IDomTerm = IDomBB->getTerminator(); + if (IDomTerm->getNumSuccessors() != 2) + break; + + if (auto *I = dyn_cast(IDomTerm->getOperand(0))) + InsertDomCondition(DT, &BB, IDomTerm, I, true, true); + DTNode = IDom; + continue; + } + } +} + +void DomConditionInfo::print(raw_ostream &OS) const { + for (const auto &Entry : DomCondMap) { + OS << "BB: " << Entry.first->getName() << ": "; + for (const auto &Cond : Entry.second) { + OS << "(" << *Cond.LHS << ", " << *Cond.RHS << ", " + << CmpInst::getPredicateName(Cond.Pred) << ") "; + } + } +} + +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) { @@ -3968,7 +3968,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,11 +7600,22 @@ const Value *LHS, const Value *RHS, const Instruction *ContextI, - const DataLayout &DL) { + const DataLayout &DL, + const DomConditionInfo *DCI) { auto PredCond = getDomPredecessorCondition(ContextI); if (PredCond.first) return isImpliedCondition(PredCond.first, Pred, LHS, RHS, DL, PredCond.second); + + if (DCI) { + if (!ContextI || !ContextI->getParent()) + return std::nullopt; + + const BasicBlock *BB = ContextI->getParent(); + auto DomCond = DCI->getDominatingCondition(BB, LHS, RHS); + if (DomCond.first) + return isImpliedCondMatchingOperands(DomCond.second, Pred, false); + } return std::nullopt; } 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();