[nfc][msan] Group checks per instruction

[vitalybuka]

Summary

It's a preparation of to combine shadow checks of the same instruction

[kda]

test?

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

1308

I think this yields a stable sort. Is that what you want?
Is there any possibility items could be added in different orders in different runs?
If both are true, then the code generation is non-deterministic.

1319

I wonder if making an implementation that materializes one check would avoid this awkward slicing.

I think you could cook all the logic from materializeInstructionChecks into materializeOneCheck and be done.

[vitalybuka]

In D133065#3762778, @kda wrote:

test?

It's NFC

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

1308

No, they added in the same order

1319

Not sure what are you asking, the point is to materialize them in batches, so we can combine checks

[vitalybuka]

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

1319

Not sure what are you asking, the point is to materialize them in batches, so we can combine checks

D133071 is the reason for slicing

[kstoimenov]

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

1305–1324

You are trying to dedupe members of the list, right? Isn't it more efficient to use a hash table instead? Wherever you consume this have a hash table, add elements to it and check check if it is already present then just skip over it.

[vitalybuka]

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

1305–1324

Not exactly. I need to handle them together.
For mostly unique items, like here, pretty sure sorting is faster.
However I am concerned with non-determinism of sorting by pointer.

llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp

if (AsCall && SizeIndex < kNumberOfAccessSizes && !MS.CompileKernel) {
       LLVM_DEBUG(dbgs() << "  CHECK: " << *Cmp << "\n");
     }
   }
 
   void materializeInstructionChecks(
       bool InstrumentWithCalls,
       ArrayRef<ShadowOriginAndInsertPoint> InstructionChecks) {
     const DataLayout &DL = F.getParent()->getDataLayout();
+    Instruction *Instruction = InstructionChecks.front().OrigIns;
     for (const auto &ShadowData : InstructionChecks) {
-      IRBuilder<> IRB(ShadowData.OrigIns);
+      assert(ShadowData.OrigIns == Instruction);
+      IRBuilder<> IRB(Instruction);
 
       LLVM_DEBUG(dbgs() << "  SHAD0 : " << *ShadowData.Shadow << "\n");
       Value *ConvertedShadow = convertShadowToScalar(ShadowData.Shadow, IRB);
       LLVM_DEBUG(dbgs() << "  SHAD1 : " << *ConvertedShadow << "\n");
 
       if (auto *ConstantShadow = dyn_cast<Constant>(ConvertedShadow)) {
         if (!ClCheckConstantShadow || ConstantShadow->isZeroValue()) {
           // Skip, value is initialized or const shadow is ignored.
           continue;
         }
         if (llvm::isKnownNonZero(ConvertedShadow, DL)) {
           // Report as the value is definitely uninitialized.
           insertWarningFn(IRB, ShadowData.Origin);
           // Skip entire instruction,
           continue;
         }
         // Fallback to runtime check, which still can be optimized out later.
       }
       materializeOneCheck(IRB, ConvertedShadow, ShadowData.Origin,
                           InstrumentWithCalls);
     }
   }
 
   void materializeChecks(bool InstrumentWithCalls) {
-    materializeInstructionChecks(InstrumentWithCalls, InstrumentationList);
+    llvm::stable_sort(InstrumentationList,
+                      [](const ShadowOriginAndInsertPoint &L,
+                         const ShadowOriginAndInsertPoint &R) {
+                        return L.OrigIns < R.OrigIns;
+                      });
+
+    for (auto I = InstrumentationList.begin();
+         I != InstrumentationList.end();) {
+      auto J =
+          std::find_if(I + 1, InstrumentationList.end(),
+                       [L = I->OrigIns](const ShadowOriginAndInsertPoint &R) {
+                         return L != R.OrigIns;
+                       });
+      // Process all checks of instruction at once.
+      materializeInstructionChecks(InstrumentWithCalls,
+                                   ArrayRef<ShadowOriginAndInsertPoint>(I, J));
+      I = J;
+    }
+
     LLVM_DEBUG(dbgs() << "DONE:\n" << F);
   }
 
   // Returns the last instruction in the new prologue
   void insertKmsanPrologue(IRBuilder<> &IRB) {
     Value *ContextState = IRB.CreateCall(MS.MsanGetContextStateFn, {});
     Constant *Zero = IRB.getInt32(0);
     MS.ParamTLS = IRB.CreateGEP(MS.MsanContextStateTy, ContextState,
                                 {Zero, IRB.getInt32(0)}, "param_shadow");