Port ConstraintElimination to the new pass manager

[MaskRay]

Summary

If -enable-constraint-elimination is specified, add it to the -O2/-O3 pipeline.
(-O1 uses a separate function now.)

[aeubanks]

thanks!

llvm/include/llvm/Transforms/Scalar/ConstraintElimination.h

17

this shouldn't be needed

[MaskRay]

Delete unneeded 'Function' declaration

[MaskRay]

llvm/lib/Passes/PassBuilder.cpp

611

I add it here to emulate to legacy pass manager builder's behavior.

I wonder whether the intention is to move some stuff from CorrelatedValuePropagationPass to ConstraintEliminationPass. Does it make sense to place ConstraintEliminationPass before/after CorrelatedValuePropagationPass?

[fhahn]

Thanks for adding NPM support! Not sure if all tests should be also updated to add NPM run-lines.

llvm/lib/Passes/PassBuilder.cpp

611

The pass is quite new and not too much experimenting went into finding he ideal position in the pipeline. I expect the position to be adjusted as it evolves. It currently works best when most original conditions are still exposed and branches are used.

There is some overlap with CVP, but the main use case is handling cases that are not handled by CVP (or any other pass).

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

14

IIRC clang-format will sort the includes, so it might be best to move it to the final position?

[MaskRay]

llvm/lib/Passes/PassBuilder.cpp

611

Thanks for the reply. I'll keep it as is (having a consistent position with the legacy PM)

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

14

This is the final position. The coding standard prefers the main header as the first. clang-format does this (the main header gets the category 0 and has the highest priority).

llvm/include/llvm/Transforms/Scalar/ConstraintElimination.h

+//===- ConstraintElimination.h - Constraint elimination pass ----*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_CONSTRAINTELIMINATION_H
+#define LLVM_TRANSFORMS_SCALAR_CONSTRAINTELIMINATION_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class ConstraintEliminationPass
+    : public PassInfoMixin<ConstraintEliminationPass> {
+public:
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_SCALAR_CONSTRAINTELIMINATION_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Instrumentation/SanitizerCoverage.h"
 #include "llvm/Transforms/Instrumentation/ThreadSanitizer.h"
 #include "llvm/Transforms/ObjCARC.h"
 #include "llvm/Transforms/Scalar/ADCE.h"
 #include "llvm/Transforms/Scalar/AlignmentFromAssumptions.h"
 #include "llvm/Transforms/Scalar/BDCE.h"
 #include "llvm/Transforms/Scalar/CallSiteSplitting.h"
 #include "llvm/Transforms/Scalar/ConstantHoisting.h"
+#include "llvm/Transforms/Scalar/ConstraintElimination.h"
 #include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
 #include "llvm/Transforms/Scalar/DCE.h"
 #include "llvm/Transforms/Scalar/DeadStoreElimination.h"
 #include "llvm/Transforms/Scalar/DivRemPairs.h"
 #include "llvm/Transforms/Scalar/EarlyCSE.h"
 #include "llvm/Transforms/Scalar/Float2Int.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/GuardWidening.h"
PipelineTuningOptions::PipelineTuningOptions() {
   LoopUnrolling = true;
   ForgetAllSCEVInLoopUnroll = ForgetSCEVInLoopUnroll;
   Coroutines = false;
   LicmMssaOptCap = SetLicmMssaOptCap;
   LicmMssaNoAccForPromotionCap = SetLicmMssaNoAccForPromotionCap;
   CallGraphProfile = true;
 }
 
+extern cl::opt<bool> EnableConstraintElimination;
 extern cl::opt<bool> EnableHotColdSplit;
 extern cl::opt<bool> EnableOrderFileInstrumentation;
 
 extern cl::opt<bool> FlattenedProfileUsed;
 
 extern cl::opt<AttributorRunOption> AttributorRun;
 extern cl::opt<bool> EnableKnowledgeRetention;
 
if (EnableGVNHoist)
     FPM.addPass(GVNHoistPass());
 
   // Global value numbering based sinking.
   if (EnableGVNSink) {
     FPM.addPass(GVNSinkPass());
     FPM.addPass(SimplifyCFGPass());
   }
 
+  if (EnableConstraintElimination)
+    FPM.addPass(ConstraintEliminationPass());
+
   // Speculative execution if the target has divergent branches; otherwise nop.
   FPM.addPass(SpeculativeExecutionPass(/* OnlyIfDivergentTarget =*/true));
 
   // Optimize based on known information about branches, and cleanup afterward.
   FPM.addPass(JumpThreadingPass());
   FPM.addPass(CorrelatedValuePropagationPass());
 
   FPM.addPass(SimplifyCFGPass());

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("assume-builder", AssumeBuilderPass())
 FUNCTION_PASS("assume-simplify", AssumeSimplifyPass())
 FUNCTION_PASS("alignment-from-assumptions", AlignmentFromAssumptionsPass())
 FUNCTION_PASS("bdce", BDCEPass())
 FUNCTION_PASS("bounds-checking", BoundsCheckingPass())
 FUNCTION_PASS("break-crit-edges", BreakCriticalEdgesPass())
 FUNCTION_PASS("callsite-splitting", CallSiteSplittingPass())
 FUNCTION_PASS("consthoist", ConstantHoistingPass())
+FUNCTION_PASS("constraint-elimination", ConstraintEliminationPass())
 FUNCTION_PASS("chr", ControlHeightReductionPass())
 FUNCTION_PASS("coro-early", CoroEarlyPass())
 FUNCTION_PASS("coro-elide", CoroElidePass())
 FUNCTION_PASS("coro-cleanup", CoroCleanupPass())
 FUNCTION_PASS("correlated-propagation", CorrelatedValuePropagationPass())
 FUNCTION_PASS("dce", DCEPass())
 FUNCTION_PASS("div-rem-pairs", DivRemPairsPass())
 FUNCTION_PASS("dse", DSEPass())

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 //===-- 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/Transforms/Scalar/ConstraintElimination.h"
 #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"
for (ConstraintOrBlock &CB : WorkList) {
 
     CS.addVariableRowFill(R);
     DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
   }
 
   return Changed;
 }
 
+PreservedAnalyses ConstraintEliminationPass::run(Function &F,
+                                                 FunctionAnalysisManager &AM) {
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  if (!eliminateConstraints(F, DT))
+    return PreservedAnalyses::all();
+
+  PreservedAnalyses PA;
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<GlobalsAA>();
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
+}
+
 namespace {
 
 class ConstraintElimination : public FunctionPass {
 public:
   static char ID;
 
   ConstraintElimination() : FunctionPass(ID) {
     initializeConstraintEliminationPass(*PassRegistry::getPassRegistry());

llvm/test/Transforms/ConstraintElimination/dom.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -constraint-elimination -S %s | FileCheck %s
+; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
 
 ; Test cases where both the true and false successors reach the same block,
 ; dominated by one of them.
 
 declare void @use(i1)
 
 define i32 @test1(i32 %x) {
 ; CHECK-LABEL: @test1(