diff --git a/llvm/include/llvm/Analysis/ConstraintSystem.h b/llvm/include/llvm/Analysis/ConstraintSystem.h --- a/llvm/include/llvm/Analysis/ConstraintSystem.h +++ b/llvm/include/llvm/Analysis/ConstraintSystem.h @@ -49,6 +49,14 @@ Constraints.push_back(R); } + void addVariableRowFill(const SmallVector &R) { + for (auto &CR : Constraints) { + while (CR.size() != R.size()) + CR.push_back(0); + } + addVariableRow(R); + } + /// Returns true if there may be a solution for the constraints in the system. bool mayHaveSolution(); @@ -62,6 +70,8 @@ } bool isConditionImplied(SmallVector R); + + void popLastConstraint() { Constraints.pop_back(); } }; } // namespace llvm diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -113,6 +113,7 @@ void initializeCodeGenPreparePass(PassRegistry&); void initializeConstantHoistingLegacyPassPass(PassRegistry&); void initializeConstantMergeLegacyPassPass(PassRegistry&); +void initializeConstraintEliminationPass(PassRegistry &); void initializeControlHeightReductionLegacyPassPass(PassRegistry&); void initializeCorrelatedValuePropagationPass(PassRegistry&); void initializeCostModelAnalysisPass(PassRegistry&); diff --git a/llvm/include/llvm/Transforms/Scalar.h b/llvm/include/llvm/Transforms/Scalar.h --- a/llvm/include/llvm/Transforms/Scalar.h +++ b/llvm/include/llvm/Transforms/Scalar.h @@ -340,6 +340,13 @@ // FunctionPass *createConstantHoistingPass(); +//===----------------------------------------------------------------------===// +// +// ConstraintElimination - This pass eliminates conditions based on found +// constraints. +// +FunctionPass *createConstraintEliminationPass(); + //===----------------------------------------------------------------------===// // // Sink - Code Sinking diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -153,6 +153,11 @@ "enable-matrix", cl::init(false), cl::Hidden, cl::desc("Enable lowering of the matrix intrinsics")); +cl::opt EnableConstraintElimination( + "enable-constraint-elimination", cl::init(false), cl::Hidden, + cl::desc( + "Enable pass to eliminate conditions based on linear constraints.")); + cl::opt AttributorRun( "attributor-enable", cl::Hidden, cl::init(AttributorRunOption::NONE), cl::desc("Enable the attributor inter-procedural deduction pass."), @@ -381,6 +386,9 @@ } } + if (EnableConstraintElimination) + MPM.add(createConstraintEliminationPass()); + if (OptLevel > 1) { // Speculative execution if the target has divergent branches; otherwise nop. MPM.add(createSpeculativeExecutionIfHasBranchDivergencePass()); diff --git a/llvm/lib/Transforms/Scalar/CMakeLists.txt b/llvm/lib/Transforms/Scalar/CMakeLists.txt --- a/llvm/lib/Transforms/Scalar/CMakeLists.txt +++ b/llvm/lib/Transforms/Scalar/CMakeLists.txt @@ -4,6 +4,7 @@ BDCE.cpp CallSiteSplitting.cpp ConstantHoisting.cpp + ConstraintElimination.cpp CorrelatedValuePropagation.cpp DCE.cpp DeadStoreElimination.cpp diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -0,0 +1,310 @@ +//===-- ConstraintElimination.cpp - Eliminate conds using constraints. ----===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Eliminate conditions based on constraints collected from dominating +// conditions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/ConstraintSystem.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/DebugCounter.h" +#include "llvm/Transforms/Scalar.h" + +using namespace llvm; +using namespace PatternMatch; + +#define DEBUG_TYPE "constraint-elimination" + +STATISTIC(NumCondsRemoved, "Number of instructions removed"); +DEBUG_COUNTER(EliminatedCounter, "conds-eliminated", + "Controls which conditions are eliminated"); + +static int64_t MaxConstraintValue = std::numeric_limits::max(); + +Optional> decompose(Value *V) { + if (auto *CI = dyn_cast(V)) { + if (CI->isNegative() || CI->uge(MaxConstraintValue)) + return {}; + return {{CI->getSExtValue(), nullptr}}; + } + auto *GEP = dyn_cast(V); + if (GEP && GEP->getNumOperands() == 2 && + isa(GEP->getOperand(GEP->getNumOperands() - 1))) { + return {{cast(GEP->getOperand(GEP->getNumOperands() - 1)) + ->getSExtValue(), + GEP->getPointerOperand()}}; + } + return {{0, V}}; +} + +/// Turn a condition \p CmpI into a constraint vector, using indices from \p +/// Value2Index. If \p ShouldAdd is true, new indices are added for values not +/// yet in \p Value2Index. +static SmallVector +getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, + DenseMap &Value2Index, bool ShouldAdd) { + Value *A, *B; + + int64_t Offset1 = 0; + int64_t Offset2 = 0; + + auto TryToGetIndex = [ShouldAdd, + &Value2Index](Value *V) -> Optional { + if (ShouldAdd) { + Value2Index.insert({V, Value2Index.size() + 1}); + return Value2Index[V]; + } + auto I = Value2Index.find(V); + if (I == Value2Index.end()) + return None; + return I->second; + }; + + if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE) + return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0, + Value2Index, ShouldAdd); + + if (Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT) { + auto ADec = decompose(Op0); + auto BDec = decompose(Op1); + if (!ADec || !BDec) + return {}; + std::tie(Offset1, A) = *ADec; + std::tie(Offset2, B) = *BDec; + Offset1 *= -1; + + if (!A && !B) + return {}; + + auto AIdx = A ? TryToGetIndex(A) : None; + auto BIdx = B ? TryToGetIndex(B) : None; + if ((A && !AIdx) || (B && !BIdx)) + return {}; + + SmallVector R(Value2Index.size() + 1, 0); + if (AIdx) + R[*AIdx] = 1; + if (BIdx) + R[*BIdx] = -1; + R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0); + return R; + } + + return {}; +} + +static SmallVector +getConstraint(CmpInst *Cmp, DenseMap &Value2Index, + bool ShouldAdd) { + return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0), + Cmp->getOperand(1), Value2Index, ShouldAdd); +} + +/// Represents either a condition that holds on entry to a block or a basic +/// block, with their respective Dominator DFS in and out numbers. +struct ConstraintOrBlock { + unsigned NumIn; + unsigned NumOut; + bool IsBlock; + bool Not; + union { + BasicBlock *BB; + CmpInst *Condition; + }; + + ConstraintOrBlock(DomTreeNode *DTN) + : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true), + BB(DTN->getBlock()) {} + ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not) + : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false), + Not(Not), Condition(Condition) {} +}; + +struct StackEntry { + unsigned NumIn; + unsigned NumOut; + CmpInst *Condition; + bool IsNot; + + StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot) + : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {} +}; + +static bool eliminateConstraints(Function &F, DominatorTree &DT) { + bool Changed = false; + DT.updateDFSNumbers(); + ConstraintSystem CS; + + SmallVector WorkList; + + // First, collect conditions implied by branches and blocks with their + // Dominator DFS in and out numbers. + for (BasicBlock &BB : F) { + if (!DT.getNode(&BB)) + continue; + WorkList.emplace_back(DT.getNode(&BB)); + + auto *Br = dyn_cast(BB.getTerminator()); + if (!Br || !Br->isConditional()) + continue; + auto *CmpI = dyn_cast(Br->getCondition()); + if (!CmpI) + continue; + if (Br->getSuccessor(0)->getSinglePredecessor()) + WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false); + if (Br->getSuccessor(1)->getSinglePredecessor()) + WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true); + } + + // Next, sort worklist by dominance, so that dominating blocks and conditions + // come before blocks and conditions dominated by them. If a block and a + // condition have the same numbers, the condition comes before the block, as + // it holds on entry to the block. + sort(WorkList.begin(), WorkList.end(), + [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) { + return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock); + }); + + // Finally, process ordered worklist and eliminate implied conditions. + SmallVector DFSInStack; + DenseMap Value2Index; + for (ConstraintOrBlock &CB : WorkList) { + // First, pop entries from the stack that are out-of-scope for CB. Remove + // the corresponding entry from the constraint system. + while (!DFSInStack.empty()) { + auto &E = DFSInStack.back(); + LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut + << "\n"); + LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n"); + bool IsDom = CB.NumIn >= E.NumIn && CB.NumOut <= E.NumOut; + if (IsDom) + break; + LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot + << "\n"); + DFSInStack.pop_back(); + CS.popLastConstraint(); + } + + LLVM_DEBUG({ + dbgs() << "Processing "; + if (CB.IsBlock) + dbgs() << *CB.BB; + else + dbgs() << *CB.Condition; + dbgs() << "\n"; + }); + + // For a block, check if any CmpInsts become known based on the current set + // of constraints. + if (CB.IsBlock) { + for (Instruction &I : *CB.BB) { + auto *Cmp = dyn_cast(&I); + if (!Cmp) + continue; + auto R = getConstraint(Cmp, Value2Index, false); + if (R.empty()) + continue; + if (CS.isConditionImplied(R)) { + if (!DebugCounter::shouldExecute(EliminatedCounter)) + continue; + + LLVM_DEBUG(dbgs() << "Condition " << *Cmp + << " implied by dominating constraints\n"); + LLVM_DEBUG({ + for (auto &E : reverse(DFSInStack)) + dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n"; + }); + Cmp->replaceAllUsesWith( + ConstantInt::getTrue(F.getParent()->getContext())); + NumCondsRemoved++; + Changed = true; + } + if (CS.isConditionImplied(ConstraintSystem::negate(R))) { + if (!DebugCounter::shouldExecute(EliminatedCounter)) + continue; + + LLVM_DEBUG(dbgs() << "Condition !" << *Cmp + << " implied by dominating constraints\n"); + LLVM_DEBUG({ + for (auto &E : reverse(DFSInStack)) + dbgs() << " C " << *E.Condition << " " << E.IsNot << "\n"; + }); + Cmp->replaceAllUsesWith( + ConstantInt::getFalse(F.getParent()->getContext())); + NumCondsRemoved++; + Changed = true; + } + } + continue; + } + + // Otherwise, add the condition to the system and stack, if we can transform + // it into a constraint. + auto R = getConstraint(CB.Condition, Value2Index, true); + if (R.empty()) + continue; + + LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n"); + if (CB.Not) + R = ConstraintSystem::negate(R); + + CS.addVariableRowFill(R); + DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not); + } + + return Changed; +} + +namespace { + +class ConstraintElimination : public FunctionPass { +public: + static char ID; + + ConstraintElimination() : FunctionPass(ID) { + initializeConstraintEliminationPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override { + auto &DT = getAnalysis().getDomTree(); + return eliminateConstraints(F, DT); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); + } +}; + +} // end anonymous namespace + +char ConstraintElimination::ID = 0; + +INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination", + "Constraint Elimination", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) +INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination", + "Constraint Elimination", false, false) + +FunctionPass *llvm::createConstraintEliminationPass() { + return new ConstraintElimination(); +} diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp --- a/llvm/lib/Transforms/Scalar/Scalar.cpp +++ b/llvm/lib/Transforms/Scalar/Scalar.cpp @@ -38,6 +38,7 @@ initializeAlignmentFromAssumptionsPass(Registry); initializeCallSiteSplittingLegacyPassPass(Registry); initializeConstantHoistingLegacyPassPass(Registry); + initializeConstraintEliminationPass(Registry); initializeCorrelatedValuePropagationPass(Registry); initializeDCELegacyPassPass(Registry); initializeDeadInstEliminationPass(Registry); diff --git a/llvm/test/Transforms/ConstraintElimination/dom.ll b/llvm/test/Transforms/ConstraintElimination/dom.ll --- a/llvm/test/Transforms/ConstraintElimination/dom.ll +++ b/llvm/test/Transforms/ConstraintElimination/dom.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s ; Test cases where both the true and false successors reach the same block, ; dominated by one of them. @@ -13,7 +13,7 @@ ; CHECK-NEXT: br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]] ; CHECK: bb1: ; CHECK-NEXT: [[C_2:%.*]] = icmp ule i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: br label [[BB2]] ; CHECK: bb2: ; CHECK-NEXT: [[C_3:%.*]] = icmp ugt i32 [[X]], 10 @@ -47,7 +47,7 @@ ; CHECK-NEXT: ret i32 20 ; CHECK: bb2: ; CHECK-NEXT: [[C_3:%.*]] = icmp ule i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: br label [[BB1]] ; entry: @@ -80,7 +80,7 @@ ; CHECK-NEXT: ret i32 10 ; CHECK: bb2: ; CHECK-NEXT: [[C_3:%.*]] = icmp ugt i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: ret i32 20 ; entry: @@ -110,7 +110,7 @@ ; CHECK-NEXT: br i1 [[C_1]], label [[BB1:%.*]], label [[BB2]] ; CHECK: bb1: ; CHECK-NEXT: [[C_2:%.*]] = icmp ule i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: ret i32 10 ; CHECK: bb2: ; CHECK-NEXT: [[C_3:%.*]] = icmp ugt i32 [[X]], 10 diff --git a/llvm/test/Transforms/ConstraintElimination/geps.2d.ll b/llvm/test/Transforms/ConstraintElimination/geps.2d.ll --- a/llvm/test/Transforms/ConstraintElimination/geps.2d.ll +++ b/llvm/test/Transforms/ConstraintElimination/geps.2d.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s define void @test.not.uge.ult([10 x i8]* %start, i8* %low, i8* %high) { ; CHECK-LABEL: @test.not.uge.ult( diff --git a/llvm/test/Transforms/ConstraintElimination/geps.ll b/llvm/test/Transforms/ConstraintElimination/geps.ll --- a/llvm/test/Transforms/ConstraintElimination/geps.ll +++ b/llvm/test/Transforms/ConstraintElimination/geps.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s define i32 @test.ult(i32* readonly %src, i32* readnone %min, i32* readnone %max) { ; CHECK-LABEL: @test.ult( @@ -15,7 +15,7 @@ ; CHECK-NEXT: [[L0:%.*]] = load i32, i32* [[SRC]], align 4 ; CHECK-NEXT: [[ADD_PTR_I36:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 3 ; CHECK-NEXT: [[C_3_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I36]], [[MIN]] -; CHECK-NEXT: br i1 [[C_3_MIN]], label [[TRAP]], label [[CHECK_3_MAX:%.*]] +; CHECK-NEXT: br i1 false, label [[TRAP]], label [[CHECK_3_MAX:%.*]] ; CHECK: check.3.max: ; CHECK-NEXT: [[C_3_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I36]], [[MAX]] ; CHECK-NEXT: br i1 [[C_3_MAX]], label [[CHECK_1_MIN:%.*]], label [[TRAP]] @@ -23,18 +23,18 @@ ; CHECK-NEXT: [[L1:%.*]] = load i32, i32* [[ADD_PTR_I36]], align 4 ; CHECK-NEXT: [[ADD_PTR_I29:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 1 ; CHECK-NEXT: [[C_1_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I29]], [[MIN]] -; CHECK-NEXT: br i1 [[C_1_MIN]], label [[TRAP]], label [[CHECK_1_MAX:%.*]] +; CHECK-NEXT: br i1 false, label [[TRAP]], label [[CHECK_1_MAX:%.*]] ; CHECK: check.1.max: ; CHECK-NEXT: [[C_1_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I29]], [[MAX]] -; CHECK-NEXT: br i1 [[C_1_MAX]], label [[CHECK_2_MIN:%.*]], label [[TRAP]] +; CHECK-NEXT: br i1 true, label [[CHECK_2_MIN:%.*]], label [[TRAP]] ; CHECK: check.2.min: ; CHECK-NEXT: [[L2:%.*]] = load i32, i32* [[ADD_PTR_I29]], align 4 ; CHECK-NEXT: [[ADD_PTR_I:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 2 ; CHECK-NEXT: [[C_2_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I]], [[MIN]] -; CHECK-NEXT: br i1 [[C_2_MIN]], label [[TRAP]], label [[CHECK_2_MAX:%.*]] +; CHECK-NEXT: br i1 false, label [[TRAP]], label [[CHECK_2_MAX:%.*]] ; CHECK: check.2.max: ; CHECK-NEXT: [[C_2_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I]], [[MAX]] -; CHECK-NEXT: br i1 [[C_2_MAX]], label [[EXIT:%.*]], label [[TRAP]] +; CHECK-NEXT: br i1 true, label [[EXIT:%.*]], label [[TRAP]] ; CHECK: exit: ; CHECK-NEXT: [[L3:%.*]] = load i32, i32* [[ADD_PTR_I]], align 4 ; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[L1]], [[L0]] @@ -101,16 +101,16 @@ ; CHECK-NEXT: ret void ; CHECK: if.end: ; CHECK-NEXT: [[T_0:%.*]] = icmp ult i8* [[START]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_0]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_1:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 1 ; CHECK-NEXT: [[T_1:%.*]] = icmp ult i8* [[START_1]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_2:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 2 ; CHECK-NEXT: [[T_2:%.*]] = icmp ult i8* [[START_2]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_3:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 3 ; CHECK-NEXT: [[T_3:%.*]] = icmp ult i8* [[START_3]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_4:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 4 ; CHECK-NEXT: [[C_4:%.*]] = icmp ult i8* [[START_4]], [[HIGH]] ; CHECK-NEXT: call void @use(i1 [[C_4]]) @@ -152,19 +152,19 @@ ; CHECK-NEXT: ret void ; CHECK: if.end: ; CHECK-NEXT: [[T_0:%.*]] = icmp ule i8* [[START]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_0]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_1:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 1 ; CHECK-NEXT: [[T_1:%.*]] = icmp ule i8* [[START_1]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_2:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 2 ; CHECK-NEXT: [[T_2:%.*]] = icmp ule i8* [[START_2]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_3:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 3 ; CHECK-NEXT: [[T_3:%.*]] = icmp ule i8* [[START_3]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_4:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 4 ; CHECK-NEXT: [[T_4:%.*]] = icmp ule i8* [[START_4]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[T_4]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[START_5:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 5 ; CHECK-NEXT: [[C_5:%.*]] = icmp ule i8* [[START_5]], [[HIGH]] ; CHECK-NEXT: call void @use(i1 [[C_5]]) @@ -211,19 +211,19 @@ ; CHECK-NEXT: ret void ; CHECK: if.end: ; CHECK-NEXT: [[F_0:%.*]] = icmp ugt i8* [[START]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_0]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_1:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 1 ; CHECK-NEXT: [[F_1:%.*]] = icmp ugt i8* [[START_1]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_2:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 2 ; CHECK-NEXT: [[F_2:%.*]] = icmp ugt i8* [[START_2]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_2]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_3:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 3 ; CHECK-NEXT: [[F_3:%.*]] = icmp ugt i8* [[START_3]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_3]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_4:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 4 ; CHECK-NEXT: [[F_4:%.*]] = icmp ugt i8* [[START_4]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_4]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_5:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 5 ; CHECK-NEXT: [[C_5:%.*]] = icmp ugt i8* [[START_5]], [[HIGH]] ; CHECK-NEXT: call void @use(i1 [[C_5]]) @@ -274,16 +274,16 @@ ; CHECK-NEXT: ret void ; CHECK: if.end: ; CHECK-NEXT: [[F_0:%.*]] = icmp ugt i8* [[START]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_0]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_1:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 1 ; CHECK-NEXT: [[F_1:%.*]] = icmp uge i8* [[START_1]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_2:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 2 ; CHECK-NEXT: [[F_2:%.*]] = icmp uge i8* [[START_2]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_2]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_3:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 3 ; CHECK-NEXT: [[F_3:%.*]] = icmp uge i8* [[START_3]], [[HIGH]] -; CHECK-NEXT: call void @use(i1 [[F_3]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[START_4:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 4 ; CHECK-NEXT: [[C_4:%.*]] = icmp uge i8* [[START_4]], [[HIGH]] ; CHECK-NEXT: call void @use(i1 [[C_4]]) diff --git a/llvm/test/Transforms/ConstraintElimination/i128.ll b/llvm/test/Transforms/ConstraintElimination/i128.ll --- a/llvm/test/Transforms/ConstraintElimination/i128.ll +++ b/llvm/test/Transforms/ConstraintElimination/i128.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s declare void @use(i1) diff --git a/llvm/test/Transforms/ConstraintElimination/loops.ll b/llvm/test/Transforms/ConstraintElimination/loops.ll --- a/llvm/test/Transforms/ConstraintElimination/loops.ll +++ b/llvm/test/Transforms/ConstraintElimination/loops.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s ; Make sure conditions in loops are not used to simplify themselves. diff --git a/llvm/test/Transforms/ConstraintElimination/mixed.ll b/llvm/test/Transforms/ConstraintElimination/mixed.ll --- a/llvm/test/Transforms/ConstraintElimination/mixed.ll +++ b/llvm/test/Transforms/ConstraintElimination/mixed.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s ; Make sure we do not incorrectly add variables to the system. diff --git a/llvm/test/Transforms/ConstraintElimination/uge.ll b/llvm/test/Transforms/ConstraintElimination/uge.ll --- a/llvm/test/Transforms/ConstraintElimination/uge.ll +++ b/llvm/test/Transforms/ConstraintElimination/uge.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s declare void @use(i1) @@ -10,7 +10,7 @@ ; CHECK-NEXT: br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]] ; CHECK: bb1: ; CHECK-NEXT: [[T_1:%.*]] = icmp uge i32 [[X]], [[Y]] -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[C_2:%.*]] = icmp uge i32 [[X]], 10 ; CHECK-NEXT: call void @use(i1 [[C_2]]) ; CHECK-NEXT: [[C_3:%.*]] = icmp uge i32 [[Y]], [[X]] @@ -20,9 +20,9 @@ ; CHECK-NEXT: ret void ; CHECK: bb2: ; CHECK-NEXT: [[T_2:%.*]] = icmp uge i32 [[Y]], [[X]] -; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[F_1:%.*]] = icmp uge i32 [[X]], [[Y]] -; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[C_5:%.*]] = icmp uge i32 [[X]], 10 ; CHECK-NEXT: call void @use(i1 [[C_5]]) ; CHECK-NEXT: [[C_6:%.*]] = icmp uge i32 10, [[X]] @@ -63,9 +63,9 @@ ; CHECK-NEXT: br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]] ; CHECK: bb1: ; CHECK-NEXT: [[T_1:%.*]] = icmp uge i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[T_2:%.*]] = icmp uge i32 [[X]], 9 -; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[C_2:%.*]] = icmp uge i32 [[X]], 11 ; CHECK-NEXT: call void @use(i1 [[C_2]]) ; CHECK-NEXT: [[C_4:%.*]] = icmp uge i32 10, [[X]] @@ -73,11 +73,11 @@ ; CHECK-NEXT: ret void ; CHECK: bb2: ; CHECK-NEXT: [[T_3:%.*]] = icmp uge i32 11, [[X]] -; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[F_1:%.*]] = icmp uge i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[F_1_1:%.*]] = icmp uge i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[F_1_1]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[C_5:%.*]] = icmp uge i32 [[X]], 9 ; CHECK-NEXT: call void @use(i1 [[C_5]]) ; CHECK-NEXT: [[C_6:%.*]] = icmp uge i32 1, [[X]] @@ -125,7 +125,7 @@ ; CHECK-NEXT: br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]] ; CHECK: bb2: ; CHECK-NEXT: [[C_3:%.*]] = icmp uge i32 [[X]], [[Z]] -; CHECK-NEXT: br i1 [[C_3]], label [[BB3:%.*]], label [[EXIT]] +; CHECK-NEXT: br i1 true, label [[BB3:%.*]], label [[EXIT]] ; CHECK: bb3: ; CHECK-NEXT: ret i32 10 ; CHECK: exit: @@ -225,7 +225,7 @@ ; CHECK-NEXT: br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]] ; CHECK: bb2: ; CHECK-NEXT: [[T_1:%.*]] = icmp uge i32 [[X]], [[Z]] -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[U_1:%.*]] = icmp eq i32 [[X]], [[Z]] ; CHECK-NEXT: call void @use(i1 [[U_1]]) ; CHECK-NEXT: ret i32 10 diff --git a/llvm/test/Transforms/ConstraintElimination/ugt-ule.ll b/llvm/test/Transforms/ConstraintElimination/ugt-ule.ll --- a/llvm/test/Transforms/ConstraintElimination/ugt-ule.ll +++ b/llvm/test/Transforms/ConstraintElimination/ugt-ule.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s declare void @use(i1) @@ -10,13 +10,13 @@ ; CHECK-NEXT: br i1 [[CMP_1]], label [[BB_1:%.*]], label [[BB_2:%.*]] ; CHECK: bb.1: ; CHECK-NEXT: [[CMP_2:%.*]] = icmp uge i8* [[M]], [[PTR]] -; CHECK-NEXT: call void @use(i1 [[CMP_2]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: ret void ; CHECK: bb.2: ; CHECK-NEXT: br label [[BB_2_NEXT:%.*]] ; CHECK: bb.2.next: ; CHECK-NEXT: [[CMP_3:%.*]] = icmp uge i8* [[M]], [[PTR]] -; CHECK-NEXT: call void @use(i1 [[CMP_3]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: ret void ; entry: diff --git a/llvm/test/Transforms/ConstraintElimination/ule.ll b/llvm/test/Transforms/ConstraintElimination/ule.ll --- a/llvm/test/Transforms/ConstraintElimination/ule.ll +++ b/llvm/test/Transforms/ConstraintElimination/ule.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S %s | FileCheck %s +; RUN: opt -constraint-elimination -S %s | FileCheck %s declare void @use(i1) @@ -10,7 +10,7 @@ ; CHECK-NEXT: br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]] ; CHECK: bb1: ; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[X]], [[Y]] -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[C_2:%.*]] = icmp ule i32 [[X]], 10 ; CHECK-NEXT: call void @use(i1 [[C_2]]) ; CHECK-NEXT: [[C_3:%.*]] = icmp ule i32 [[Y]], [[X]] @@ -20,9 +20,9 @@ ; CHECK-NEXT: ret void ; CHECK: bb2: ; CHECK-NEXT: [[T_2:%.*]] = icmp ule i32 [[Y]], [[X]] -; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[F_1:%.*]] = icmp ule i32 [[X]], [[Y]] -; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[C_5:%.*]] = icmp ule i32 [[X]], 10 ; CHECK-NEXT: call void @use(i1 [[C_5]]) ; CHECK-NEXT: [[C_6:%.*]] = icmp ule i32 10, [[X]] @@ -63,9 +63,9 @@ ; CHECK-NEXT: br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]] ; CHECK: bb1: ; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[T_2:%.*]] = icmp ule i32 [[X]], 11 -; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[C_2:%.*]] = icmp ule i32 [[X]], 9 ; CHECK-NEXT: call void @use(i1 [[C_2]]) ; CHECK-NEXT: [[C_4:%.*]] = icmp ule i32 10, [[X]] @@ -73,14 +73,14 @@ ; CHECK-NEXT: ret void ; CHECK: bb2: ; CHECK-NEXT: [[T_3:%.*]] = icmp ule i32 10, [[X]] -; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[F_1:%.*]] = icmp ule i32 [[X]], 9 -; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[F_1_1:%.*]] = icmp ule i32 [[X]], 10 -; CHECK-NEXT: call void @use(i1 [[F_1_1]]) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[C_5:%.*]] = icmp ule i32 [[X]], 11 ; CHECK-NEXT: call void @use(i1 [[C_5]]) -; CHECK-NEXT: [[C_6:%.*]] = icmp ule i32 10, [[X]] +; CHECK-NEXT: [[C_6:%.*]] = icmp ule i32 12, [[X]] ; CHECK-NEXT: call void @use(i1 [[C_6]]) ; CHECK-NEXT: ret void ; @@ -110,7 +110,7 @@ call void @use(i1 %f.1.1) %c.5 = icmp ule i32 %x, 11 call void @use(i1 %c.5) - %c.6 = icmp ule i32 10, %x + %c.6 = icmp ule i32 12, %x call void @use(i1 %c.6) ret void } @@ -126,7 +126,7 @@ ; CHECK-NEXT: br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]] ; CHECK: bb2: ; CHECK-NEXT: [[C_3:%.*]] = icmp ule i32 [[X]], [[Z]] -; CHECK-NEXT: br i1 [[C_3]], label [[BB3:%.*]], label [[EXIT]] +; CHECK-NEXT: br i1 true, label [[BB3:%.*]], label [[EXIT]] ; CHECK: bb3: ; CHECK-NEXT: ret i32 10 ; CHECK: exit: @@ -226,7 +226,7 @@ ; CHECK-NEXT: br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]] ; CHECK: bb2: ; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[X]], [[Z]] -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: [[U_1:%.*]] = icmp eq i32 [[X]], [[Z]] ; CHECK-NEXT: call void @use(i1 [[U_1]]) ; CHECK-NEXT: ret i32 10