Add a pass to lower is.constant intrinsics

[void]

Summary

THIS IS A WORK IN PROGRESS. NOT FOR SUBMISSION.

This pass lowers the is.constant intrinsics into 'true' or 'false'. We
want to convert to 'true' early in the pipeline and 'false' late in the
pipeline. In other words, if right before code generation we cannot
definitively prove that the argument is constant, then we will lower to
'false'.

[void]

Remove other commit.

[joerg]

lib/Transforms/Scalar/LowerIsConstantIntrinsic.cpp

9

Fundamentally, we don't have to care too much about the 'true' part. That's handled by normal constant folding well enough already. It's only a fallback for the -O0 pass really.

44

RAUW is not good enough here. We want to have at least replaceAndRecursivelySimplify, but even that is not good enough as it still leaves conditional branches on constant conditions. D62025 depended on SimplifyCFG for that, but that doesn't work for the -O0 chain. That said, is there a reason for not handling that in InstructionSimplify.cpp explicitly?

[void]

lib/Transforms/Scalar/LowerIsConstantIntrinsic.cpp

9

I was mostly thinking about the -O0 pass, as you mentioned. But yeah we don't need to worry too much about it. Though I agree with Chandler (I think he was the one who mentioned it) that we would like to convert to false as late as possible and true as early as possible.

44

Not handling which case in InstructionSimplify.cpp?

I can change the call, but I want to be wary of "separation of concerns". Normally, we just change the instruction and let other passes do the clean up. I don't want to put a whole lot of logic in here to DCE, simplify, etc., unless we know those passes won't run afterwards.

[joerg]

lib/Transforms/Scalar/LowerIsConstantIntrinsic.cpp

9

For the -O0 pipeline, we never run any of the normal instruction simplification passes. That's where the true case is normally handled. I think it is in the spirit of the -O0 pipeline to run only one instance of the pass at all, so that would naturally mean a single late folding. When I look at CodeGen/AArch64/O0-pipeline.ll, it can't be run much earlier anyway, so it shouldn't make much of a difference in this case anyway.

44

Remember, in the -O0 pass chain SimplifyCFG is never run. That seems to be the only pass that changes conditional branches into unconditional branches. We always run DCE, so exploiting that one is fine. In D65280, one option of extending instruction simplify is implemented, but that one certainly needs some thoughts on whether it is the correct way forward.

[void]

lib/Transforms/Scalar/LowerIsConstantIntrinsic.cpp

9

Okay. I think the comment can stand as is though, unless you want to explicitly call out the -O0 case.

44

Right. So I'm not sure about your comment that replaceAndRecursivelySimplify not being good enough matters, since -O0 has no guarantees about performance. The only way it could matter is if code that's expected to be dead, and would otherwise cause a compilation error of some sort, is left over.

[joerg]

lib/Transforms/Scalar/LowerIsConstantIntrinsic.cpp

44

Exactly, the inline asm statements that triggered the original case. If they are left around, they can trigger the I-want-immediate-operands checks.

[void]

lib/Transforms/Scalar/LowerIsConstantIntrinsic.cpp

44

God bless inline asm. :-)

bindings/ocaml/transforms/scalar_opts/llvm_scalar_opts.mli

external add_early_cse
   : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit
   = "llvm_add_early_cse"
 
 (** See the [llvm::createLowerExpectIntrinsicPass] function. *)
 external add_lower_expect_intrinsic
   : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit
   = "llvm_add_lower_expect_intrinsic"
 
+(** See the [llvm::createLowerIsConstantIntrinsicPass] function. *)
+external add_lower_is_constant_intrinsic
+  : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit
+  = "llvm_add_lower_is_constant_intrinsic"
+
 (** See the [llvm::createTypeBasedAliasAnalysisPass] function. *)
 external add_type_based_alias_analysis
   : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit
   = "llvm_add_type_based_alias_analysis"
 
 (** See the [llvm::createScopedNoAliasAAPass] function. *)
 external add_scoped_no_alias_alias_analysis
   : [< Llvm.PassManager.any ] Llvm.PassManager.t -> unit

bindings/ocaml/transforms/scalar_opts/scalar_opts_ocaml.c

 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 CAMLprim value llvm_add_lower_expect_intrinsic(LLVMPassManagerRef PM) {
   LLVMAddLowerExpectIntrinsicPass(PM);
   return Val_unit;
 }
 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
+CAMLprim value llvm_add_lower_is_constant_intrinsic(LLVMPassManagerRef PM) {
+  LLVMAddLowerIsConstantIntrinsicPass(PM);
+  return Val_unit;
+}
+
+/* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 CAMLprim value llvm_add_type_based_alias_analysis(LLVMPassManagerRef PM) {
   LLVMAddTypeBasedAliasAnalysisPass(PM);
   return Val_unit;
 }
 
 /* [<Llvm.PassManager.any] Llvm.PassManager.t -> unit */
 CAMLprim value llvm_add_scoped_no_alias_aa(LLVMPassManagerRef PM) {
   LLVMAddScopedNoAliasAAPass(PM);

include/llvm-c/Transforms/Scalar.h

 void LLVMAddEarlyCSEPass(LLVMPassManagerRef PM);
 
 /** See llvm::createEarlyCSEPass function */
 void LLVMAddEarlyCSEMemSSAPass(LLVMPassManagerRef PM);
 
 /** See llvm::createLowerExpectIntrinsicPass function */
 void LLVMAddLowerExpectIntrinsicPass(LLVMPassManagerRef PM);
 
+/** See llvm::createLowerIsConstantIntrinsicPass function */
+void LLVMAddLowerIsConstantIntrinsicPass(LLVMPassManagerRef PM);
+
 /** See llvm::createTypeBasedAliasAnalysisPass function */
 void LLVMAddTypeBasedAliasAnalysisPass(LLVMPassManagerRef PM);
 
 /** See llvm::createScopedNoAliasAAPass function */
 void LLVMAddScopedNoAliasAAPass(LLVMPassManagerRef PM);
 
 /** See llvm::createBasicAliasAnalysisPass function */
 void LLVMAddBasicAliasAnalysisPass(LLVMPassManagerRef PM);

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 initializeLowerIsConstantIntrinsicPass(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&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createLoopRerollPass();
       (void) llvm::createLoopUnrollPass();
       (void) llvm::createLoopUnrollAndJamPass();
       (void) llvm::createLoopUnswitchPass();
       (void) llvm::createLoopVersioningLICMPass();
       (void) llvm::createLoopIdiomPass();
       (void) llvm::createLoopRotatePass();
       (void) llvm::createLowerExpectIntrinsicPass();
+      (void) llvm::createLowerIsConstantIntrinsicPass();
       (void) llvm::createLowerInvokePass();
       (void) llvm::createLowerSwitchPass();
       (void) llvm::createNaryReassociatePass();
       (void) llvm::createObjCARCAAWrapperPass();
       (void) llvm::createObjCARCAPElimPass();
       (void) llvm::createObjCARCExpandPass();
       (void) llvm::createObjCARCContractPass();
       (void) llvm::createObjCARCOptPass();

include/llvm/Transforms/Scalar.h

 //===----------------------------------------------------------------------===//
 //
 // LowerExpectIntrinsics - Removes llvm.expect intrinsics and creates
 // "block_weights" metadata.
 FunctionPass *createLowerExpectIntrinsicPass();
 
 //===----------------------------------------------------------------------===//
 //
+// LowerIsConstantIntrinsics - Converts llvm.is.constant intrinsics into 'true'
+// or 'false'.
+//
+FunctionPass *createLowerIsConstantIntrinsicPass(bool Final = false);
+
+//===----------------------------------------------------------------------===//
+//
 // PartiallyInlineLibCalls - Tries to inline the fast path of library
 // calls such as sqrt.
 //
 FunctionPass *createPartiallyInlineLibCallsPass();
 
 //===----------------------------------------------------------------------===//
 //
 // SeparateConstOffsetFromGEP - Split GEPs for better CSE

include/llvm/Transforms/Scalar/LowerIsConstantIntrinsic.h

+//===- LowerIsConstantIntrinsic.h - Lower is.constant int. 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
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// The header file for the LowerIsConstantIntrinsic pass as used by the new pass
+/// manager.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_LOWERISCONSTANTINTRINSIC_H
+#define LLVM_TRANSFORMS_SCALAR_LOWERISCONSTANTINTRINSIC_H
+
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+struct LowerIsConstantIntrinsicPass :
+    PassInfoMixin<LowerIsConstantIntrinsicPass> {
+private:
+  bool Final;
+public:
+  explicit LowerIsConstantIntrinsicPass(bool Final = false)
+      : Final(Final) {}
+
+  /// Run the pass over the function.
+  ///
+  /// This will lower all of the 'is.constant'` intrinsic calls in this function
+  /// into 'true' or 'false'. We want to resolve to 'true' as early as possible
+  /// and 'false' as late as possible.
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
+};
+
+}
+
+#endif

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/LowerIsConstantIntrinsic.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/MergeICmps.h"
 #include "llvm/Transforms/Scalar/NaryReassociate.h"
 #include "llvm/Transforms/Scalar/NewGVN.h"
 #include "llvm/Transforms/Scalar/PartiallyInlineLibCalls.h"

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-is-constant", LowerIsConstantIntrinsicPass())
 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())

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
+  LowerIsConstantIntrinsic.cpp
   LowerWidenableCondition.cpp
   MakeGuardsExplicit.cpp
   MemCpyOptimizer.cpp
   MergeICmps.cpp
   MergedLoadStoreMotion.cpp
   NaryReassociate.cpp
   NewGVN.cpp
   PartiallyInlineLibCalls.cpp

lib/Transforms/Scalar/LowerIsConstantIntrinsic.cpp

+//===- LowerIsConstantIntrinsic.cpp - Lower is.constant intrinsic ---------===//
+//
+// 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 pass lowers the 'is.constant' intrinsic to 'true' or 'false'.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Scalar/LowerIsConstantIntrinsic.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "lower-is-constant-intrinsic"
+
+STATISTIC(IsConstantIntrinsicsHandled,
+          "Number of 'is.constant' intrinsic instructions handled");
+
+static bool handleIsConstantIntrinsic(IntrinsicInst *II, bool Final) {
+  Value *Op = II->getOperand(0);
+  Value *Exp = nullptr;
+
+  if (isa<Constant>(Op))
+    Exp = ConstantInt::getTrue(II->getType());
+  else if (Final)
+    Exp = ConstantInt::getFalse(II->getType());
+
+  if (Exp) {
+    II->replaceAllUsesWith(Exp);
+    II->eraseFromParent();
+    return true;
+  }
+
+  return false;
+}
+
+static bool lowerIsConstantIntrinsic(Function &F, bool Final,
+                                     const TargetLibraryInfo *TLI) {
+  bool Changed = false;
+
+  for (BasicBlock &BB : F) {
+    bool Handled = false;
+    for (auto BI = BB.begin(), BE = BB.end(); BI != BE;) {
+      Instruction *I = &*BI++;
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+        if (II->getIntrinsicID() != Intrinsic::is_constant)
+          continue;
+        Handled |= handleIsConstantIntrinsic(II, Final);
+        IsConstantIntrinsicsHandled++;
+      }
+    }
+    Changed |= Handled && SimplifyInstructionsInBlock(&BB, TLI);
+  }
+
+  return Changed;
+}
+
+PreservedAnalyses LowerIsConstantIntrinsicPass::run(
+    Function &F, FunctionAnalysisManager &AM) {
+  if (lowerIsConstantIntrinsic(F, Final,
+                               AM.getCachedResult<TargetLibraryAnalysis>(F)))
+    return PreservedAnalyses::none();
+
+  return PreservedAnalyses::all();
+}
+
+
+namespace {
+/// Legacy pass for lowering is.constant intrinsics out of the IR.
+///
+/// When this pass is run over a function it converts is.constant intrinsics
+/// into 'true' or 'false'. We want to convert to 'true' as early in the
+/// pipeline as possible and 'false' as late as possible.
+class LowerIsConstantIntrinsic : public FunctionPass {
+  bool Final;
+public:
+  static char ID;
+  LowerIsConstantIntrinsic(bool Final = false)
+      : FunctionPass(ID), Final(Final) {
+    initializeLowerIsConstantIntrinsicPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
+    const TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
+    return lowerIsConstantIntrinsic(F, Final, TLI);
+  }
+};
+}
+
+char LowerIsConstantIntrinsic::ID = 0;
+INITIALIZE_PASS(LowerIsConstantIntrinsic, "lower-is-constant",
+                "Lower 'is.constant' Intrinsics", false, false)
+
+FunctionPass *llvm::createLowerIsConstantIntrinsicPass(bool Final) {
+  return new LowerIsConstantIntrinsic(Final);
+}

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);
+  initializeLowerIsConstantIntrinsicPass(Registry);
   initializeLowerWidenableConditionLegacyPassPass(Registry);
   initializeMemCpyOptLegacyPassPass(Registry);
   initializeMergeICmpsLegacyPassPass(Registry);
   initializeMergedLoadStoreMotionLegacyPassPass(Registry);
   initializeNaryReassociateLegacyPassPass(Registry);
   initializePartiallyInlineLibCallsLegacyPassPass(Registry);
   initializeReassociateLegacyPassPass(Registry);
   initializeRegToMemPass(Registry);

 void LLVMAddBasicAliasAnalysisPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createBasicAAWrapperPass());
 }
 
 void LLVMAddLowerExpectIntrinsicPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createLowerExpectIntrinsicPass());
 }
 
+void LLVMAddLowerIsConstantIntrinsicPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createLowerIsConstantIntrinsicPass());
+}
+
 void LLVMAddUnifyFunctionExitNodesPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createUnifyFunctionExitNodesPass());
 }

utils/gn/secondary/llvm/lib/Transforms/Scalar/BUILD.gn

sources = [
     "LoopStrengthReduce.cpp",
     "LoopUnrollAndJamPass.cpp",
     "LoopUnrollPass.cpp",
     "LoopUnswitch.cpp",
     "LoopVersioningLICM.cpp",
     "LowerAtomic.cpp",
     "LowerExpectIntrinsic.cpp",
     "LowerGuardIntrinsic.cpp",
+    "LowerIsConstantIntrinsic.cpp",
     "LowerWidenableCondition.cpp",
     "MakeGuardsExplicit.cpp",
     "MemCpyOptimizer.cpp",
     "MergeICmps.cpp",
     "MergedLoadStoreMotion.cpp",
     "NaryReassociate.cpp",
     "NewGVN.cpp",
     "PartiallyInlineLibCalls.cpp",