Add initial version of TBAA verifier. (WIP)

llvm/include/llvm/Analysis/TypeBasedAliasAnalysisVerifier.h

+//===- TypeBasedAliasAnalysis.h - Type-Based Alias Analysis -----*- 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
+/// This is the interface for a metadata-based TBAA. See the source file for
+/// details on the algorithm.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_TYPEBASEDALIASANALYSISVERIFIER_H
+#define LLVM_ANALYSIS_TYPEBASEDALIASANALYSISVERIFIER_H
+
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Pass.h"
+#include <memory>
+
+namespace llvm {
+
+class CallBase;
+class Function;
+class MDNode;
+class MemoryLocation;
+
+/// Analysis pass providing a never-invalidated alias analysis result.
+class TypeBasedAAVerifierPass
+    : public AnalysisInfoMixin<TypeBasedAAVerifierPass> {
+  friend AnalysisInfoMixin<TypeBasedAAVerifierPass>;
+
+  static AnalysisKey Key;
+
+public:
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+//===--------------------------------------------------------------------===//
+//
+//
+FunctionPass *createTypeBasedAAVerifierLegacyPass();
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_TYPEBASEDALIASANALYSISVERIFIER_H

llvm/include/llvm/InitializePasses.h

 void initializeTailDuplicatePass(PassRegistry&);
 void initializeTargetLibraryInfoWrapperPassPass(PassRegistry&);
 void initializeTargetPassConfigPass(PassRegistry&);
 void initializeTargetTransformInfoWrapperPassPass(PassRegistry&);
 void initializeThreadSanitizerLegacyPassPass(PassRegistry&);
 void initializeTLSVariableHoistLegacyPassPass(PassRegistry &);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAAWrapperPassPass(PassRegistry&);
+void initializeTypeBasedAAVerifierLegacyPassPass(PassRegistry &);
 void initializeTypePromotionPass(PassRegistry&);
 void initializeUnifyFunctionExitNodesLegacyPassPass(PassRegistry &);
 void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &);
 void initializeUnpackMachineBundlesPass(PassRegistry&);
 void initializeUnreachableBlockElimLegacyPassPass(PassRegistry&);
 void initializeUnreachableMachineBlockElimPass(PassRegistry&);
 void initializeVectorCombineLegacyPassPass(PassRegistry&);
 void initializeVerifierLegacyPassPass(PassRegistry&);

llvm/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeSCEVAAWrapperPassPass(Registry);
   initializeScalarEvolutionWrapperPassPass(Registry);
   initializeStackSafetyGlobalInfoWrapperPassPass(Registry);
   initializeStackSafetyInfoWrapperPassPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);
   initializeTypeBasedAAWrapperPassPass(Registry);
+  initializeTypeBasedAAVerifierLegacyPassPass(Registry);
   initializeScopedNoAliasAAWrapperPassPass(Registry);
   initializeLCSSAVerificationPassPass(Registry);
   initializeMemorySSAWrapperPassPass(Registry);
   initializeMemorySSAPrinterLegacyPassPass(Registry);
 }
 
 void LLVMInitializeAnalysis(LLVMPassRegistryRef R) {
   initializeAnalysis(*unwrap(R));

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   StackSafetyAnalysis.cpp
   SyncDependenceAnalysis.cpp
   SyntheticCountsUtils.cpp
   TFUtils.cpp
   TargetLibraryInfo.cpp
   TargetTransformInfo.cpp
   Trace.cpp
   TypeBasedAliasAnalysis.cpp
+  TypeBasedAliasAnalysisVerifier.cpp
   TypeMetadataUtils.cpp
   ScopedNoAliasAA.cpp
   ValueLattice.cpp
   ValueLatticeUtils.cpp
   ValueTracking.cpp
   VectorUtils.cpp
   VFABIDemangling.cpp
   ${GeneratedMLSources}

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp

 #include <cassert>
 #include <cstdint>
 
 using namespace llvm;
 
 // A handy option for disabling TBAA functionality. The same effect can also be
 // achieved by stripping the !tbaa tags from IR, but this option is sometimes
 // more convenient.
-static cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden);
+cl::opt<bool> EnableTBAA("enable-tbaa", cl::init(false), cl::Hidden);
 
 namespace {
 
 /// isNewFormatTypeNode - Return true iff the given type node is in the new
 /// size-aware format.
 static bool isNewFormatTypeNode(const MDNode *N) {
   if (N->getNumOperands() < 3)
     return false;

llvm/lib/Analysis/TypeBasedAliasAnalysisVerifier.cpp

+//===- TypeBasedAliasAnalysisVerifier.cpp - TBAA Verifier -----------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/TypeBasedAliasAnalysisVerifier.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TypeBasedAliasAnalysis.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
+
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <cassert>
+#include <cstdint>
+
+using namespace llvm;
+
+extern cl::opt<bool> EnableTBAA;
+
+static void verifyTBAA(Function &F, DominatorTree &DT, ScalarEvolution &SE,
+                       AAResults &AA) {
+  EnableTBAA = true;
+
+  SmallVector<Instruction *> MemoryInsts;
+  for (Instruction &I : instructions(F)) {
+    if (auto *LI = dyn_cast<LoadInst>(&I))
+      MemoryInsts.push_back(LI);
+    if (auto *SI = dyn_cast<StoreInst>(&I))
+      MemoryInsts.push_back(SI);
+  }
+
+  for (unsigned I = 0; I < MemoryInsts.size(); I++) {
+    for (unsigned J = I + 1; J < MemoryInsts.size(); J++) {
+      auto *Src = MemoryInsts[I];
+      auto *Dst = MemoryInsts[J];
+      auto L1 = MemoryLocation::get(Src);
+      auto L2 = MemoryLocation::get(Dst);
+
+      if (DT.dominates(Dst, Src))
+        std::swap(Src, Dst);
+      else if (!DT.dominates(Src, Dst))
+        continue;
+
+      if (AA.alias(L1, L2) != AliasResult::NoAlias)
+        continue;
+
+      auto CheckPointers = [&SE, Src, Dst, &F](const SCEV *Ptr1Expr,
+                                               const SCEV *Ptr2Expr) {
+        if (SE.getPointerBase(Ptr1Expr) != SE.getPointerBase(Ptr2Expr))
+          return false;
+
+        const SCEV *Off1 = SE.removePointerBase(Ptr1Expr);
+        const SCEV *Off2 = SE.removePointerBase(Ptr2Expr);
+        if (Off1 == Off2) {
+          dbgs() << "Possible strict aliasing violation in " << F.getName()
+                 << " between accesses on ";
+          Src->getDebugLoc().dump();
+          dbgs() << " and ";
+          Dst->getDebugLoc().dump();
+          dbgs() << "\n";
+          return true;
+
+          // report_fatal_error("Strict aliasing violation");
+        }
+
+        auto *Ptr2AddRec = dyn_cast<SCEVAddRecExpr>(Ptr2Expr);
+        if (Ptr2AddRec &&
+            SE.isKnownPredicate(CmpInst::ICMP_EQ, Ptr2AddRec->getStart(),
+                                Ptr1Expr)) {
+
+          dbgs() << "Possible strict aliasing violation in " << F.getName()
+                 << " between accesses on ";
+          Src->getDebugLoc().dump();
+          dbgs() << " and ";
+          Dst->getDebugLoc().dump();
+          dbgs() << "\n";
+          return true;
+        }
+        return false;
+      };
+
+      const SCEV *Ptr1Expr = SE.getSCEV(const_cast<Value *>(L1.Ptr));
+      Value *Ptr2 = const_cast<Value *>(L2.Ptr);
+      const SCEV *Ptr2Expr = SE.getSCEV(Ptr2);
+      if (CheckPointers(Ptr1Expr, Ptr2Expr))
+        break;
+      if (auto *Unknown = dyn_cast<SCEVUnknown>(Ptr2Expr)) {
+        if (auto *PN = dyn_cast<PHINode>(Unknown->getValue())) {
+          if (any_of(PN->incoming_values(),
+                     [&SE, Ptr1Expr, CheckPointers](Value *Inc) {
+                       return CheckPointers(Ptr1Expr, SE.getSCEV(Inc));
+                     }))
+            break;
+        }
+      }
+    }
+  }
+
+  EnableTBAA = false;
+}
+
+PreservedAnalyses TypeBasedAAVerifierPass::run(Function &F,
+                                               FunctionAnalysisManager &AM) {
+  auto &TBAA = AM.getResult<TypeBasedAA>(F);
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
+  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
+
+  AAResults AA(TLI);
+  AA.addAAResult(TBAA);
+  verifyTBAA(F, DT, SE, AA);
+  return PreservedAnalyses::all();
+}
+
+namespace {
+
+/// Legacy wrapper pass to provide the TypeBasedAAResult object.
+struct TypeBasedAAVerifierLegacyPass : public FunctionPass {
+  static char ID;
+
+  TypeBasedAAVerifierLegacyPass() : FunctionPass(ID) {
+    initializeTypeBasedAAVerifierLegacyPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override { return false; }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {}
+};
+
+} // namespace
+
+char TypeBasedAAVerifierLegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(TypeBasedAAVerifierLegacyPass, "tbaa-verify",
+                      "Type-Based Alias Analysis Verifier", false, false)
+INITIALIZE_PASS_END(TypeBasedAAVerifierLegacyPass, "tbaa-verify",
+                    "Type-Based Alias Analysis Verifier", false, false)
+
+FunctionPass *llvm::createTypeBasedAAVerifierLegacyPass() {
+  return new TypeBasedAAVerifierLegacyPass();
+}

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/StackLifetime.h"
 #include "llvm/Analysis/StackSafetyAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
+#include "llvm/Analysis/TypeBasedAliasAnalysisVerifier.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PrintPasses.h"
 #include "llvm/IR/SafepointIRVerifier.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

llvm/lib/Passes/PassBuilderPipelines.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InlineAdvisor.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
+#include "llvm/Analysis/TypeBasedAliasAnalysisVerifier.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Passes/OptimizationLevel.h"
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/PGOOptions.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h"
PassBuilder::buildModuleOptimizationPipeline(OptimizationLevel Level,
   MPM.addPass(ConstantMergePass());
 
   // TODO: Relative look table converter pass caused an issue when full lto is
   // enabled. See https://reviews.llvm.org/D94355 for more details.
   // Until the issue fixed, disable this pass during pre-linking phase.
   if (!LTOPreLink)
     MPM.addPass(RelLookupTableConverterPass());
 
+  MPM.addPass(createModuleToFunctionPassAdaptor(TypeBasedAAVerifierPass()));
   return MPM;
 }
 
 ModulePassManager
 PassBuilder::buildPerModuleDefaultPipeline(OptimizationLevel Level,
                                            bool LTOPreLink) {
   assert(Level != OptimizationLevel::O0 &&
          "Must request optimizations for the default pipeline!");

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("slsr", StraightLineStrengthReducePass())
 FUNCTION_PASS("speculative-execution", SpeculativeExecutionPass())
 FUNCTION_PASS("sroa", SROAPass())
 FUNCTION_PASS("strip-gc-relocates", StripGCRelocates())
 FUNCTION_PASS("structurizecfg", StructurizeCFGPass())
 FUNCTION_PASS("tailcallelim", TailCallElimPass())
 FUNCTION_PASS("unify-loop-exits", UnifyLoopExitsPass())
 FUNCTION_PASS("vector-combine", VectorCombinePass())
+FUNCTION_PASS("tbaa-verify", TypeBasedAAVerifierPass())
 FUNCTION_PASS("verify", VerifierPass())
 FUNCTION_PASS("verify<domtree>", DominatorTreeVerifierPass())
 FUNCTION_PASS("verify<loops>", LoopVerifierPass())
 FUNCTION_PASS("verify<memoryssa>", MemorySSAVerifierPass())
 FUNCTION_PASS("verify<regions>", RegionInfoVerifierPass())
 FUNCTION_PASS("verify<safepoint-ir>", SafepointIRVerifierPass())
 FUNCTION_PASS("verify<scalar-evolution>", ScalarEvolutionVerifierPass())
 FUNCTION_PASS("view-cfg", CFGViewerPass())