[Module] Track intrinsic IDs in module to skip unnecessary lowering.

[fhahn]

Summary

There are various intrinsic lowering passes and they currently all
require iterating over the whole function, even if there are no calls to
the intrinsics they are interested in.

This patch extends Module with a way to query if an intrinsic ID has any
declarations in the module. This can be used as a relatively cheap proxy
to bail out early from a lowering pass.

It adds a new optional map IntrinsicsInModule to Module and an
containsIntrinsicDeclaration helper. IntrinsicsInModule is initialized
the first time containsIntrinsicDeclaration is called and
getOrInsertFunction & Function::eraseFromParent() are updated to
update the map.

One thing that should probably be added as well is a way for lowering
pass to ensure they do not miss an intrinsic check if the add support
for new intrinsics.

[efriedma]

llvm/include/llvm/IR/Module.h

196

Hmm, this just stores the count, not the actual declarations? I guess that's okay, depending on how you expect to use it.

llvm/lib/IR/Function.cpp

246

We should probably try to detect mutation on the list directly. See SymbolTableListTraits.

[efriedma]

In terms of the general approach, this seems reasonable. But maybe bring it up on llvmdev to see if anyone else has thoughts on it.

[fhahn]

llvm/include/llvm/IR/Module.h

196

I am not sure if the list of declarations would be helpful during the actual lowering, because the lowering passes are function passes. And some require lowering/visiting them in a particular oder.

llvm/lib/IR/Function.cpp

246

Thanks I'll take a look

llvm/include/llvm/IR/Module.h

 /// Module.h This file contains the declarations for the Module class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_MODULE_H
 #define LLVM_IR_MODULE_H
 
 #include "llvm-c/Types.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Comdat.h"
 #include "llvm/IR/DataLayout.h"
private:
   std::string ModuleID;           ///< Human readable identifier for the module
   std::string SourceFileName;     ///< Original source file name for module,
                                   ///< recorded in bitcode.
   std::string TargetTriple;       ///< Platform target triple Module compiled on
                                   ///< Format: (arch)(sub)-(vendor)-(sys0-(abi)
   NamedMDSymTabType NamedMDSymTab;  ///< NamedMDNode names.
   DataLayout DL;                  ///< DataLayout associated with the module
 
+  Optional<DenseMap<unsigned, unsigned>> IntrinsicsInModule = None;
+
   friend class Constant;
 
 /// @}
 /// @name Constructors
 /// @{
 public:
   /// The Module constructor. Note that there is no default constructor. You
   /// must provide a name for the module upon construction.
/// @{
   FunctionCallee
   getOrInsertFunction(StringRef Name, AttributeList AttributeList,
                       FunctionType *Invalid, ArgsTy... Args) = delete;
 
   /// Look up the specified function in the module symbol table. If it does not
   /// exist, return null.
   Function *getFunction(StringRef Name) const;
 
+  bool containsIntrinsicDeclaration(unsigned ID);
+  void intrinsicDeclarationRemoved(unsigned ID);
+
   /// @}
   /// @name Global Variable Accessors
   /// @{
 
   /// Look up the specified global variable in the module symbol table. If it
   /// does not exist, return null. If AllowInternal is set to true, this
   /// function will return types that have InternalLinkage. By default, these
   /// types are not returned.
   GlobalVariable *getGlobalVariable(StringRef Name) const {
     return getGlobalVariable(Name, false);
   }

llvm/lib/CodeGen/ScalarizeMaskedMemIntrin.cpp

if ((Idx + 1) != VectorWidth) {
       Ptr = PtrPhi;
     }
   }
   CI->eraseFromParent();
 
   ModifiedDT = true;
 }
 
+bool shouldRunMaskedMemLowering(Function &F) {
+  Module *M = F.getParent();
+  return M->containsIntrinsicDeclaration(Intrinsic::masked_load) ||
+         M->containsIntrinsicDeclaration(Intrinsic::masked_store) ||
+         M->containsIntrinsicDeclaration(Intrinsic::masked_gather) ||
+         M->containsIntrinsicDeclaration(Intrinsic::masked_scatter) ||
+         M->containsIntrinsicDeclaration(Intrinsic::masked_expandload) ||
+         M->containsIntrinsicDeclaration(Intrinsic::masked_compressstore);
+}
+
 bool ScalarizeMaskedMemIntrin::runOnFunction(Function &F) {
+  if (!shouldRunMaskedMemLowering(F))
+    return false;
+
   bool EverMadeChange = false;
 
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 
   bool MadeChange = true;
   while (MadeChange) {
     MadeChange = false;
     for (Function::iterator I = F.begin(); I != F.end();) {

llvm/lib/IR/Function.cpp

Function *Function::Create(FunctionType *Ty, LinkageTypes Linkage,
   return Create(Ty, Linkage, M.getDataLayout().getProgramAddressSpace(), N, &M);
 }
 
 void Function::removeFromParent() {
   getParent()->getFunctionList().remove(getIterator());
 }
 
 void Function::eraseFromParent() {
+  if (isIntrinsic())
+    getParent()->intrinsicDeclarationRemoved(getIntrinsicID());
   getParent()->getFunctionList().erase(getIterator());
 }
 
 //===----------------------------------------------------------------------===//
 // Function Implementation
 //===----------------------------------------------------------------------===//
 
 static unsigned computeAddrSpace(unsigned AddrSpace, Module *M) {

llvm/lib/IR/Module.cpp

FunctionCallee Module::getOrInsertFunction(StringRef Name, FunctionType *Ty,
   // See if we have a definition for the specified function already.
   GlobalValue *F = getNamedValue(Name);
   if (!F) {
     // Nope, add it
     Function *New = Function::Create(Ty, GlobalVariable::ExternalLinkage,
                                      DL.getProgramAddressSpace(), Name);
     if (!New->isIntrinsic())       // Intrinsics get attrs set on construction
       New->setAttributes(AttributeList);
+    else {
+      if (IntrinsicsInModule) {
+        auto I = IntrinsicsInModule->insert({New->getIntrinsicID(), 0});
+        I.first->second++;
+      }
+    }
+
     FunctionList.push_back(New);
     return {Ty, New}; // Return the new prototype.
   }
 
   // If the function exists but has the wrong type, return a bitcast to the
   // right type.
   auto *PTy = PointerType::get(Ty, F->getAddressSpace());
   if (F->getType() != PTy)

 
 // getFunction - Look up the specified function in the module symbol table.
 // If it does not exist, return null.
 //
 Function *Module::getFunction(StringRef Name) const {
   return dyn_cast_or_null<Function>(getNamedValue(Name));
 }
 
+bool Module::containsIntrinsicDeclaration(unsigned ID) {
+  if (!IntrinsicsInModule) {
+    DenseMap<unsigned, unsigned> Map;
+    IntrinsicsInModule = {Map};
+    for (const Function &Fn : FunctionList)
+      if (Fn.isIntrinsic()) {
+        auto I = IntrinsicsInModule->insert({Fn.getIntrinsicID(), 0});
+        I.first->second++;
+      }
+  }
+  return IntrinsicsInModule->find(ID) != IntrinsicsInModule->end();
+}
+
+void Module::intrinsicDeclarationRemoved(unsigned ID) {
+  if (!IntrinsicsInModule)
+    return;
+  auto I = IntrinsicsInModule->find(ID);
+  assert(I != IntrinsicsInModule->end());
+  if (--I->second)
+    IntrinsicsInModule->erase(ID);
+}
+
 //===----------------------------------------------------------------------===//
 // Methods for easy access to the global variables in the module.
 //
 
 /// getGlobalVariable - Look up the specified global variable in the module
 /// symbol table.  If it does not exist, return null.  The type argument
 /// should be the underlying type of the global, i.e., it should not have
 /// the top-level PointerType, which represents the address of the global.

llvm/lib/Transforms/Scalar/LowerConstantIntrinsics.cpp

for (WeakTrackingVH &VH: Worklist) {
     }
     HasDeadBlocks |= replaceConditionalBranchesOnConstant(II, NewValue);
   }
   if (HasDeadBlocks)
     removeUnreachableBlocks(F);
   return !Worklist.empty();
 }
 
+static bool shouldRunConstantLowering(Function &F) {
+  Module *M = F.getParent();
+  return M->containsIntrinsicDeclaration(Intrinsic::is_constant) ||
+         M->containsIntrinsicDeclaration(Intrinsic::objectsize);
+}
+
 PreservedAnalyses
 LowerConstantIntrinsicsPass::run(Function &F, FunctionAnalysisManager &AM) {
+  if (!shouldRunConstantLowering(F))
+    return PreservedAnalyses::all();
+
   if (lowerConstantIntrinsics(F, 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'. This is completements the normal constand folding
 /// to 'true' as part of Instruction Simplify passes.
 class LowerConstantIntrinsics : public FunctionPass {
 public:
   static char ID;
   LowerConstantIntrinsics() : FunctionPass(ID) {
     initializeLowerConstantIntrinsicsPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
+    if (!shouldRunConstantLowering(F))
+      return false;
+
     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
     const TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
     return lowerConstantIntrinsics(F, TLI);
   }
 };
 } // namespace
 
 char LowerConstantIntrinsics::ID = 0;
 INITIALIZE_PASS(LowerConstantIntrinsics, "lower-constant-intrinsics",
                 "Lower constant intrinsics", false, false)
 
 FunctionPass *llvm::createLowerConstantIntrinsicsPass() {
   return new LowerConstantIntrinsics();
 }

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

for (auto BI = BB.rbegin(), BE = BB.rend(); BI != BE;) {
         Changed = true;
       }
     }
   }
 
   return Changed;
 }
 
+static bool shouldRunExpectLowering(Function &F) {
+  Module *M = F.getParent();
+  return M->containsIntrinsicDeclaration(Intrinsic::expect);
+}
+
 PreservedAnalyses LowerExpectIntrinsicPass::run(Function &F,
                                                 FunctionAnalysisManager &) {
+  if (!shouldRunExpectLowering(F))
+    return PreservedAnalyses::all();
+
   if (lowerExpectIntrinsic(F))
     return PreservedAnalyses::none();
 
   return PreservedAnalyses::all();
 }
 
 namespace {
 /// Legacy pass for lowering expect intrinsics out of the IR.
 ///
 /// When this pass is run over a function it uses expect intrinsics which feed
 /// branches and switches to provide branch weight metadata for those
 /// terminators. It then removes the expect intrinsics from the IR so the rest
 /// of the optimizer can ignore them.
 class LowerExpectIntrinsic : public FunctionPass {
 public:
   static char ID;
   LowerExpectIntrinsic() : FunctionPass(ID) {
     initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry());
   }
 
-  bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); }
+  bool runOnFunction(Function &F) override {
+    if (!shouldRunExpectLowering(F))
+      return false;
+
+    return lowerExpectIntrinsic(F);
+  }
 };
 }
 
 char LowerExpectIntrinsic::ID = 0;
 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect",
                 "Lower 'expect' Intrinsics", false, false)
 
 FunctionPass *llvm::createLowerExpectIntrinsicPass() {
   return new LowerExpectIntrinsic();
 }