diff --git a/llvm/include/llvm/Analysis/TypeBasedAliasAnalysisVerifier.h b/llvm/include/llvm/Analysis/TypeBasedAliasAnalysisVerifier.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/TypeBasedAliasAnalysisVerifier.h @@ -0,0 +1,48 @@ +//===- 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 + +namespace llvm { + +class CallBase; +class Function; +class MDNode; +class MemoryLocation; + +/// Analysis pass providing a never-invalidated alias analysis result. +class TypeBasedAAVerifierPass + : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + + static AnalysisKey Key; + +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +//===--------------------------------------------------------------------===// +// +// +FunctionPass *createTypeBasedAAVerifierLegacyPass(); + +} // end namespace llvm + +#endif // LLVM_ANALYSIS_TYPEBASEDALIASANALYSISVERIFIER_H diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -450,6 +450,7 @@ void initializeTLSVariableHoistLegacyPassPass(PassRegistry &); void initializeTwoAddressInstructionPassPass(PassRegistry&); void initializeTypeBasedAAWrapperPassPass(PassRegistry&); +void initializeTypeBasedAAVerifierLegacyPassPass(PassRegistry &); void initializeTypePromotionPass(PassRegistry&); void initializeUnifyFunctionExitNodesLegacyPassPass(PassRegistry &); void initializeUnifyLoopExitsLegacyPassPass(PassRegistry &); diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -83,6 +83,7 @@ initializeStackSafetyInfoWrapperPassPass(Registry); initializeTargetTransformInfoWrapperPassPass(Registry); initializeTypeBasedAAWrapperPassPass(Registry); + initializeTypeBasedAAVerifierLegacyPassPass(Registry); initializeScopedNoAliasAAWrapperPassPass(Registry); initializeLCSSAVerificationPassPass(Registry); initializeMemorySSAWrapperPassPass(Registry); diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -135,6 +135,7 @@ TargetTransformInfo.cpp Trace.cpp TypeBasedAliasAnalysis.cpp + TypeBasedAliasAnalysisVerifier.cpp TypeMetadataUtils.cpp ScopedNoAliasAA.cpp ValueLattice.cpp diff --git a/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp b/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp --- a/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -127,7 +127,7 @@ // 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 EnableTBAA("enable-tbaa", cl::init(true), cl::Hidden); +cl::opt EnableTBAA("enable-tbaa", cl::init(false), cl::Hidden); namespace { diff --git a/llvm/lib/Analysis/TypeBasedAliasAnalysisVerifier.cpp b/llvm/lib/Analysis/TypeBasedAliasAnalysisVerifier.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/TypeBasedAliasAnalysisVerifier.cpp @@ -0,0 +1,160 @@ +//===- 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 +#include + +using namespace llvm; + +extern cl::opt EnableTBAA; + +static void verifyTBAA(Function &F, DominatorTree &DT, ScalarEvolution &SE, + AAResults &AA) { + EnableTBAA = true; + + SmallVector MemoryInsts; + for (Instruction &I : instructions(F)) { + if (auto *LI = dyn_cast(&I)) + MemoryInsts.push_back(LI); + if (auto *SI = dyn_cast(&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(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(L1.Ptr)); + Value *Ptr2 = const_cast(L2.Ptr); + const SCEV *Ptr2Expr = SE.getSCEV(Ptr2); + if (CheckPointers(Ptr1Expr, Ptr2Expr)) + break; + if (auto *Unknown = dyn_cast(Ptr2Expr)) { + if (auto *PN = dyn_cast(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(F); + auto &DT = AM.getResult(F); + auto &SE = AM.getResult(F); + auto &TLI = AM.getResult(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(); +} diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -71,6 +71,7 @@ #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" diff --git a/llvm/lib/Passes/PassBuilderPipelines.cpp b/llvm/lib/Passes/PassBuilderPipelines.cpp --- a/llvm/lib/Passes/PassBuilderPipelines.cpp +++ b/llvm/lib/Passes/PassBuilderPipelines.cpp @@ -23,6 +23,7 @@ #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" @@ -1276,6 +1277,7 @@ if (!LTOPreLink) MPM.addPass(RelLookupTableConverterPass()); + MPM.addPass(createModuleToFunctionPassAdaptor(TypeBasedAAVerifierPass())); return MPM; } diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -354,6 +354,7 @@ 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", DominatorTreeVerifierPass()) FUNCTION_PASS("verify", LoopVerifierPass())