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; @@ -106,6 +107,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) {} @@ -113,9 +116,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; @@ -1017,10 +1018,17 @@ 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 +/// this case offset would be -8. +std::optional isPointerOffset(const Value *Ptr1, const Value *Ptr2, + const DataLayout &DL); } // end namespace llvm #endif // LLVM_ANALYSIS_VALUETRACKING_H Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -56,6 +56,7 @@ DependenceAnalysis.cpp DependenceGraphBuilder.cpp DevelopmentModeInlineAdvisor.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,112 @@ +//===- 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; + +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" @@ -7941,12 +7942,21 @@ const Value *LHS, const Value *RHS, const Instruction *ContextI, - const DataLayout &DL) { + const DataLayout &DL, + const DomConditionInfo *DCI) { + std::optional IsImplied; 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.has_value() && 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/TargetLibraryInfo.h" #include "llvm/IR/Dominators.h" @@ -93,14 +94,14 @@ if (skipFunction(F)) return false; - const DominatorTree *DT = - &getAnalysis().getDomTree(); + DominatorTree *DT = &getAnalysis().getDomTree(); const TargetLibraryInfo *TLI = &getAnalysis().getTLI(F); AssumptionCache *AC = &getAnalysis().getAssumptionCache(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); return runImpl(F, SQ); } }; @@ -126,7 +127,8 @@ auto &TLI = AM.getResult(F); auto &AC = 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); if (!Changed) return PreservedAnalyses::all(); Index: llvm/test/Transforms/InstSimplify/domcondition.ll =================================================================== --- llvm/test/Transforms/InstSimplify/domcondition.ll +++ llvm/test/Transforms/InstSimplify/domcondition.ll @@ -225,11 +225,9 @@ ; CHECK: cond.true: ; CHECK-NEXT: br i1 [[C:%.*]], label [[XORBB:%.*]], label [[COND_END]] ; CHECK: xorbb: -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[X]], [[Y]] ; CHECK-NEXT: br label [[COND_END]] ; CHECK: cond.end: -; CHECK-NEXT: [[COND:%.*]] = phi i32 [ [[XOR]], [[XORBB]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[COND_TRUE]] ] -; CHECK-NEXT: ret i32 [[COND]] +; CHECK-NEXT: ret i32 0 ; entry: %cmp = icmp eq i32 %x, %y @@ -254,9 +252,7 @@ ; CHECK: taken: ; CHECK-NEXT: br i1 [[X:%.*]], label [[SELBB:%.*]], label [[END]] ; CHECK: selbb: -; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i32 [[A]], [[B]] -; CHECK-NEXT: [[C:%.*]] = select i1 [[CMP2]], i32 20, i32 0 -; CHECK-NEXT: call void @foo(i32 [[C]]) +; CHECK-NEXT: call void @foo(i32 20) ; CHECK-NEXT: br label [[END]] ; CHECK: end: ; CHECK-NEXT: ret void