Default lowering for experimental.widenable.condition

[mkazantsev]

Summary

Introduces a pass that provides default lowering strategy for the
experimental.widenable.condition intrinsic, replacing all its uses with i1 true.

[reames]

Why not do this as either a) SelectionDAG or b) CodeGenPrepare? I don't see the value in having the separate pass for this.

[reames]

Per previous comments.

[mkazantsev]

Because we might want to get rid of widenable conditions (and therefore of guards) not right before codegen, but earlier? For example, before vectorization to get rid of control flow inside a loop.

[reames]

In D56096#1375179, @mkazantsev wrote:

Because we might want to get rid of widenable conditions (and therefore of guards) not right before codegen, but earlier? For example, before vectorization to get rid of control flow inside a loop.

Max and I discussed offline. We decided on a "let's do both" approach. We want standard codegen to know how to lower guards, but we also want to be able to experiment easily with doing so earlier in the pipeline.

I've posted https://reviews.llvm.org/D56096 which does the same transform in CGP. We could have just scheduled the extra pass, but doing so seemed slightly ugly when CGP would be obviously the right place for this if we didn't also want the option to lower early.

Given that, LGTM.

lib/Transforms/Scalar/LowerWidenableCondition.cpp

65 ↗

(On Diff #179539)

At some point down the line, we'll probably want to simplify the CFG here, but that's definitely okay to be a followup.

[mkazantsev]

lib/Transforms/Scalar/LowerWidenableCondition.cpp

65 ↗

(On Diff #179539)

Not sure if it's worth doing. The typical use case is br i1 some_cond & WC, label1, label2; we only have CFG update if we have previously proved that some_cond is trivially true. If it's a frequent situation in practice, we can think about it.

llvm/trunk/include/llvm/InitializePasses.h

 void initializeLoopUnswitchPass(PassRegistry&);
 void initializeLoopVectorizePass(PassRegistry&);
 void initializeLoopVersioningLICMPass(PassRegistry&);
 void initializeLoopVersioningPassPass(PassRegistry&);
 void initializeLowerAtomicLegacyPassPass(PassRegistry&);
 void initializeLowerEmuTLSPass(PassRegistry&);
 void initializeLowerExpectIntrinsicPass(PassRegistry&);
 void initializeLowerGuardIntrinsicLegacyPassPass(PassRegistry&);
+void initializeLowerWidenableConditionLegacyPassPass(PassRegistry&);
 void initializeLowerIntrinsicsPass(PassRegistry&);
 void initializeLowerInvokeLegacyPassPass(PassRegistry&);
 void initializeLowerSwitchPass(PassRegistry&);
 void initializeLowerTypeTestsPass(PassRegistry&);
 void initializeMIRCanonicalizerPass(PassRegistry &);
 void initializeMIRPrintingPassPass(PassRegistry&);
 void initializeMachineBlockFrequencyInfoPass(PassRegistry&);
 void initializeMachineBlockPlacementPass(PassRegistry&);

llvm/trunk/include/llvm/Transforms/Scalar.h

 //===----------------------------------------------------------------------===//
 //
 // LowerGuardIntrinsic - Lower guard intrinsics to normal control flow.
 //
 Pass *createLowerGuardIntrinsicPass();
 
 //===----------------------------------------------------------------------===//
 //
+// LowerWidenableCondition - Lower widenable condition to i1 true.
+//
+Pass *createLowerWidenableConditionPass();
+
+//===----------------------------------------------------------------------===//
+//
 // MergeICmps - Merge integer comparison chains into a memcmp
 //
 Pass *createMergeICmpsPass();
 
 //===----------------------------------------------------------------------===//
 //
 // ValuePropagation - Propagate CFG-derived value information
 //

llvm/trunk/include/llvm/Transforms/Scalar/LowerWidenableCondition.h

+//===--- LowerWidenableCondition.h - Lower the guard intrinsic ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass lowers the llvm.widenable.condition intrinsic to default value
+// which is i1 true.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TRANSFORMS_SCALAR_LOWERWIDENABLECONDITION_H
+#define LLVM_TRANSFORMS_SCALAR_LOWERWIDENABLECONDITION_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+struct LowerWidenableConditionPass : PassInfoMixin<LowerWidenableConditionPass> {
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+}
+
+#endif //LLVM_TRANSFORMS_SCALAR_LOWERWIDENABLECONDITION_H

llvm/trunk/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
 #include "llvm/Transforms/Scalar/LoopSink.h"
 #include "llvm/Transforms/Scalar/LoopStrengthReduce.h"
 #include "llvm/Transforms/Scalar/LoopUnrollAndJamPass.h"
 #include "llvm/Transforms/Scalar/LoopUnrollPass.h"
 #include "llvm/Transforms/Scalar/LowerAtomic.h"
 #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h"
 #include "llvm/Transforms/Scalar/LowerGuardIntrinsic.h"
+#include "llvm/Transforms/Scalar/LowerWidenableCondition.h"
 #include "llvm/Transforms/Scalar/MakeGuardsExplicit.h"
 #include "llvm/Transforms/Scalar/MemCpyOptimizer.h"
 #include "llvm/Transforms/Scalar/MergedLoadStoreMotion.h"
 #include "llvm/Transforms/Scalar/NaryReassociate.h"
 #include "llvm/Transforms/Scalar/NewGVN.h"
 #include "llvm/Transforms/Scalar/PartiallyInlineLibCalls.h"
 #include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/Transforms/Scalar/RewriteStatepointsForGC.h"

llvm/trunk/lib/Passes/PassRegistry.def

 FUNCTION_PASS("instsimplify", InstSimplifyPass())
 FUNCTION_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 FUNCTION_PASS("float2int", Float2IntPass())
 FUNCTION_PASS("no-op-function", NoOpFunctionPass())
 FUNCTION_PASS("libcalls-shrinkwrap", LibCallsShrinkWrapPass())
 FUNCTION_PASS("loweratomic", LowerAtomicPass())
 FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass())
 FUNCTION_PASS("lower-guard-intrinsic", LowerGuardIntrinsicPass())
+FUNCTION_PASS("lower-widenable-condition", LowerWidenableConditionPass())
 FUNCTION_PASS("guard-widening", GuardWideningPass())
 FUNCTION_PASS("gvn", GVN())
 FUNCTION_PASS("load-store-vectorizer", LoadStoreVectorizerPass())
 FUNCTION_PASS("loop-simplify", LoopSimplifyPass())
 FUNCTION_PASS("loop-sink", LoopSinkPass())
 FUNCTION_PASS("lowerinvoke", LowerInvokePass())
 FUNCTION_PASS("mem2reg", PromotePass())
 FUNCTION_PASS("memcpyopt", MemCpyOptPass())

llvm/trunk/lib/Transforms/Scalar/CMakeLists.txt

add_llvm_library(LLVMScalarOpts
   LoopStrengthReduce.cpp
   LoopUnrollPass.cpp
   LoopUnrollAndJamPass.cpp
   LoopUnswitch.cpp
   LoopVersioningLICM.cpp
   LowerAtomic.cpp
   LowerExpectIntrinsic.cpp
   LowerGuardIntrinsic.cpp
+  LowerWidenableCondition.cpp
   MakeGuardsExplicit.cpp
   MemCpyOptimizer.cpp
   MergeICmps.cpp
   MergedLoadStoreMotion.cpp
   NaryReassociate.cpp
   NewGVN.cpp
   PartiallyInlineLibCalls.cpp
   PlaceSafepoints.cpp

llvm/trunk/lib/Transforms/Scalar/LowerWidenableCondition.cpp

+//===- LowerWidenableCondition.cpp - Lower the guard intrinsic ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass lowers the llvm.widenable.condition intrinsic to default value
+// which is i1 true.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/LowerWidenableCondition.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/GuardUtils.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/GuardUtils.h"
+
+using namespace llvm;
+
+namespace {
+struct LowerWidenableConditionLegacyPass : public FunctionPass {
+  static char ID;
+  LowerWidenableConditionLegacyPass() : FunctionPass(ID) {
+    initializeLowerWidenableConditionLegacyPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override;
+};
+}
+
+static bool lowerWidenableCondition(Function &F) {
+  // Check if we can cheaply rule out the possibility of not having any work to
+  // do.
+  auto *WCDecl = F.getParent()->getFunction(
+      Intrinsic::getName(Intrinsic::experimental_widenable_condition));
+  if (!WCDecl || WCDecl->use_empty())
+    return false;
+
+  using namespace llvm::PatternMatch;
+  SmallVector<CallInst *, 8> ToLower;
+  for (auto &I : instructions(F))
+    if (match(&I, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
+      ToLower.push_back(cast<CallInst>(&I));
+
+  if (ToLower.empty())
+    return false;
+
+  for (auto *CI : ToLower) {
+    CI->replaceAllUsesWith(ConstantInt::getTrue(CI->getContext()));
+    CI->eraseFromParent();
+  }
+  return true;
+}
+
+bool LowerWidenableConditionLegacyPass::runOnFunction(Function &F) {
+  return lowerWidenableCondition(F);
+}
+
+char LowerWidenableConditionLegacyPass::ID = 0;
+INITIALIZE_PASS(LowerWidenableConditionLegacyPass, "lower-widenable-condition",
+                "Lower the widenable condition to default true value", false,
+                false)
+
+Pass *llvm::createLowerWidenableConditionPass() {
+  return new LowerWidenableConditionLegacyPass();
+}
+
+PreservedAnalyses LowerWidenableConditionPass::run(Function &F,
+                                               FunctionAnalysisManager &AM) {
+  if (lowerWidenableCondition(F))
+    return PreservedAnalyses::none();
+
+  return PreservedAnalyses::all();
+}

llvm/trunk/lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeLoopUnrollAndJamPass(Registry);
   initializeLoopUnswitchPass(Registry);
   initializeWarnMissedTransformationsLegacyPass(Registry);
   initializeLoopVersioningLICMPass(Registry);
   initializeLoopIdiomRecognizeLegacyPassPass(Registry);
   initializeLowerAtomicLegacyPassPass(Registry);
   initializeLowerExpectIntrinsicPass(Registry);
   initializeLowerGuardIntrinsicLegacyPassPass(Registry);
+  initializeLowerWidenableConditionLegacyPassPass(Registry);
   initializeMemCpyOptLegacyPassPass(Registry);
   initializeMergeICmpsPass(Registry);
   initializeMergedLoadStoreMotionLegacyPassPass(Registry);
   initializeNaryReassociateLegacyPassPass(Registry);
   initializePartiallyInlineLibCallsLegacyPassPass(Registry);
   initializeReassociateLegacyPassPass(Registry);
   initializeRegToMemPass(Registry);
   initializeRewriteStatepointsForGCLegacyPassPass(Registry);

llvm/trunk/test/Transforms/LowerWidenableCondition/basic.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -lower-widenable-condition < %s        | FileCheck %s
+; RUN: opt -S -passes=lower-widenable-condition < %s | FileCheck %s
+
+; Basic test case: make sure that all widenable conditions turn into i1 true.
+define void @f_0(i1 %cond_0, i1 %cond_1) {
+; CHECK-LABEL: @f_0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[COND_0:%.*]], true
+; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED:%.*]], label [[DEOPT:%.*]]
+; CHECK:       deopt:
+; CHECK-NEXT:    unreachable
+; CHECK:       guarded:
+; CHECK-NEXT:    [[EXIPLICIT_GUARD_COND4:%.*]] = and i1 [[COND_1:%.*]], true
+; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND4]], label [[GUARDED1:%.*]], label [[DEOPT2:%.*]]
+; CHECK:       deopt2:
+; CHECK-NEXT:    unreachable
+; CHECK:       guarded1:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %widenable_cond = call i1 @llvm.experimental.widenable.condition()
+  %exiplicit_guard_cond = and i1 %cond_0, %widenable_cond
+  br i1 %exiplicit_guard_cond, label %guarded, label %deopt
+
+deopt:                                            ; preds = %entry
+  unreachable
+
+guarded:                                          ; preds = %entry
+  %widenable_cond3 = call i1 @llvm.experimental.widenable.condition()
+  %exiplicit_guard_cond4 = and i1 %cond_1, %widenable_cond3
+  br i1 %exiplicit_guard_cond4, label %guarded1, label %deopt2
+
+deopt2:                                           ; preds = %guarded
+  unreachable
+
+guarded1:                                         ; preds = %guarded
+  ret void
+}
+
+; Function Attrs: inaccessiblememonly nounwind
+declare i1 @llvm.experimental.widenable.condition() #0
+
+attributes #0 = { inaccessiblememonly nounwind }