[asan] Speed up interesting alloca checks

[zaks.anna]

Summary

We make many redundant calls to isInterestingAlloca in the AddressSanitzier pass. This is especially inefficient for allocas that have many uses. Let's cache the results to speed up compilation.

The compile time improvements depend on the input. I did not see much difference on benchmarks; however, I have a test case where compile time goes from minutes to under a second.

[kcc]

This looks fine, but I would slightly prefer to compute the map beforehand instead of caching, if possible.
I.e. instead of a map of ProcessedAllocas have a set of InterestingAllocas that is computed in visitAllocaInst

lib/Transforms/Instrumentation/AddressSanitizer.cpp

811

we tend to not write {} in such cases

[zaks.anna]

This looks fine, but I would slightly prefer to compute the map beforehand instead of caching, if possible.
I.e. instead of a map of ProcessedAllocas have a set of InterestingAllocas that is computed in visitAllocaInst

In the future, determining if an alloca is interesting or not might depend on visiting all of its uses. For example, if an alloca is promotable but all of it's uses are accessing memory, which is provably in range, it should be marked as non-interesting. The current approach seems to fit that model better than visiting allocas and building a list.

[kcc]

In D8639#147540, @zaks.anna wrote:

This looks fine, but I would slightly prefer to compute the map beforehand instead of caching, if possible.
I.e. instead of a map of ProcessedAllocas have a set of InterestingAllocas that is computed in visitAllocaInst

In the future, determining if an alloca is interesting or not might depend on visiting all of its uses. For example, if an alloca is promotable but all of it's uses are accessing memory, which is provably in range, it should be marked as non-interesting. The current approach seems to fit that model better than visiting allocas and building a list.

But you can also visit all uses in a pre-compute step too.
And having this pre-computed instead of cached will make the code simpler to understand.

[kcc]

Each walk of the use list of the alloca is relatively expensive -- it is a linked list and cache hostile.

But won't we need it anyway regardless of caching-cs-precomputing?

[kcc]

LGTM (with a nit about {})

We currently do not run an instruction visitor in the very beginning of the pass

Yes, indeed.

[zaks.anna]

Thanks for the feedback everyone! Committed in r233397.

lib/Transforms/Instrumentation/AddressSanitizer.cpp

struct AddressSanitizer : public FunctionPass {
   }
   uint64_t getAllocaSizeInBytes(AllocaInst *AI) const {
     Type *Ty = AI->getAllocatedType();
     uint64_t SizeInBytes =
         AI->getModule()->getDataLayout().getTypeAllocSize(Ty);
     return SizeInBytes;
   }
   /// Check if we want (and can) handle this alloca.
-  bool isInterestingAlloca(AllocaInst &AI) const;
+  bool isInterestingAlloca(AllocaInst &AI);
   /// If it is an interesting memory access, return the PointerOperand
   /// and set IsWrite/Alignment. Otherwise return nullptr.
   Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite,
                                    uint64_t *TypeSize,
-                                   unsigned *Alignment) const;
+                                   unsigned *Alignment);
   void instrumentMop(ObjectSizeOffsetVisitor &ObjSizeVis, Instruction *I,
                      bool UseCalls, const DataLayout &DL);
   void instrumentPointerComparisonOrSubtraction(Instruction *I);
   void instrumentAddress(Instruction *OrigIns, Instruction *InsertBefore,
                          Value *Addr, uint32_t TypeSize, bool IsWrite,
                          Value *SizeArgument, bool UseCalls, uint32_t Exp);
   void instrumentUnusualSizeOrAlignment(Instruction *I, Value *Addr,
                                         uint32_t TypeSize, bool IsWrite,
private:
   Function *AsanErrorCallback[2][2][kNumberOfAccessSizes];
   Function *AsanMemoryAccessCallback[2][2][kNumberOfAccessSizes];
   // This array is indexed by AccessIsWrite and Experiment.
   Function *AsanErrorCallbackSized[2][2];
   Function *AsanMemoryAccessCallbackSized[2][2];
   Function *AsanMemmove, *AsanMemcpy, *AsanMemset;
   InlineAsm *EmptyAsm;
   GlobalsMetadata GlobalsMD;
+  DenseMap<AllocaInst *, bool> ProcessedAllocas;
 
   friend struct FunctionStackPoisoner;
 };
 
 class AddressSanitizerModule : public ModulePass {
  public:
   AddressSanitizerModule() : ModulePass(ID) {}
   bool runOnModule(Module &M) override;
IRB.CreateCall3(
         IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
         IRB.CreateIntCast(MI->getOperand(1), IRB.getInt32Ty(), false),
         IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false));
   }
   MI->eraseFromParent();
 }
 
 /// Check if we want (and can) handle this alloca.
-bool AddressSanitizer::isInterestingAlloca(AllocaInst &AI) const {
-  return (AI.getAllocatedType()->isSized() &&
-          // alloca() may be called with 0 size, ignore it.
-          getAllocaSizeInBytes(&AI) > 0 &&
-          // We are only interested in allocas not promotable to registers.
-          // Promotable allocas are common under -O0.
-          (!ClSkipPromotableAllocas || !isAllocaPromotable(&AI)));
+bool AddressSanitizer::isInterestingAlloca(AllocaInst &AI) {
+  auto PreviouslySeenAllocaInfo = ProcessedAllocas.find(&AI);
+
+  if (PreviouslySeenAllocaInfo != ProcessedAllocas.end()) {
+    return PreviouslySeenAllocaInfo->getSecond();
+  }
+
+  bool IsInteresting = (AI.getAllocatedType()->isSized() &&
+
+  ProcessedAllocas[&AI] = IsInteresting;
+  return IsInteresting;
 }
 
 /// If I is an interesting memory access, return the PointerOperand
 /// and set IsWrite/Alignment. Otherwise return nullptr.
 Value *AddressSanitizer::isInterestingMemoryAccess(Instruction *I,
                                                    bool *IsWrite,
                                                    uint64_t *TypeSize,
-                                                   unsigned *Alignment) const {
+                                                   unsigned *Alignment) {
   // Skip memory accesses inserted by another instrumentation.
   if (I->getMetadata("nosanitize")) return nullptr;
 
   Value *PtrOperand = nullptr;
   const DataLayout &DL = I->getModule()->getDataLayout();
   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
     if (!ClInstrumentReads) return nullptr;
     *IsWrite = false;