From a5b314c27a585b979ac9c9da944aa3cec27d22a6 Mon Sep 17 00:00:00 2001 From: Manman Ren Date: Sat, 27 Apr 2013 00:26:11 +0000 Subject: [PATCH] Struct-path aware TBAA: change the format of TBAAStructType node. We switch the order of offset and field type to make TBAAStructType node (name, parent node, offset) similar to scalar TBAA node (name, parent node). TypeIsImmutable is added to TBAAStructTag node. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180654 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/MDBuilder.h | 14 +++--- lib/Analysis/TypeBasedAliasAnalysis.cpp | 43 +++++++++++++------ .../TypeBasedAliasAnalysis/tbaa-path.ll | 22 +++++----- 3 files changed, 48 insertions(+), 31 deletions(-) diff --git a/include/llvm/IR/MDBuilder.h b/include/llvm/IR/MDBuilder.h index 074db78a767..ce81b5498f5 100644 --- a/include/llvm/IR/MDBuilder.h +++ b/include/llvm/IR/MDBuilder.h @@ -159,26 +159,26 @@ public: /// \brief Return metadata for a TBAA struct node in the type DAG /// with the given name, a list of pairs (offset, field type in the type DAG). MDNode *createTBAAStructTypeNode(StringRef Name, - ArrayRef > Fields) { + ArrayRef > Fields) { SmallVector Ops(Fields.size() * 2 + 1); Type *Int64 = IntegerType::get(Context, 64); Ops[0] = createString(Name); for (unsigned i = 0, e = Fields.size(); i != e; ++i) { - Ops[i * 2 + 1] = ConstantInt::get(Int64, Fields[i].first); - Ops[i * 2 + 2] = Fields[i].second; + Ops[i * 2 + 1] = Fields[i].first; + Ops[i * 2 + 2] = ConstantInt::get(Int64, Fields[i].second); } return MDNode::get(Context, Ops); } /// \brief Return metadata for a TBAA scalar type node with the /// given name, an offset and a parent in the TBAA type DAG. - MDNode *createTBAAScalarTypeNode(StringRef Name, uint64_t Offset, - MDNode *Parent) { + MDNode *createTBAAScalarTypeNode(StringRef Name, MDNode *Parent, + uint64_t Offset = 0) { SmallVector Ops(3); Type *Int64 = IntegerType::get(Context, 64); Ops[0] = createString(Name); - Ops[1] = ConstantInt::get(Int64, Offset); - Ops[2] = Parent; + Ops[1] = Parent; + Ops[2] = ConstantInt::get(Int64, Offset); return MDNode::get(Context, Ops); } diff --git a/lib/Analysis/TypeBasedAliasAnalysis.cpp b/lib/Analysis/TypeBasedAliasAnalysis.cpp index 442145f5966..bbf3c3a2a5c 100644 --- a/lib/Analysis/TypeBasedAliasAnalysis.cpp +++ b/lib/Analysis/TypeBasedAliasAnalysis.cpp @@ -134,6 +134,17 @@ namespace { uint64_t getOffset() const { return cast(Node->getOperand(2))->getZExtValue(); } + /// TypeIsImmutable - Test if this TBAAStructTagNode represents a type for + /// objects which are not modified (by any means) in the context where this + /// AliasAnalysis is relevant. + bool TypeIsImmutable() const { + if (Node->getNumOperands() < 4) + return false; + ConstantInt *CI = dyn_cast(Node->getOperand(3)); + if (!CI) + return false; + return CI->getValue()[0]; + } }; /// This is a simple wrapper around an MDNode which provides a @@ -153,14 +164,24 @@ namespace { /// Get this TBAAStructTypeNode's field in the type DAG with /// given offset. Update the offset to be relative to the field type. TBAAStructTypeNode getParent(uint64_t &Offset) const { + // Parent can be omitted for the root node. if (Node->getNumOperands() < 2) return TBAAStructTypeNode(); + // Special handling for a scalar type node. + if (Node->getNumOperands() <= 3) { + MDNode *P = dyn_cast_or_null(Node->getOperand(1)); + if (!P) + return TBAAStructTypeNode(); + return TBAAStructTypeNode(P); + } + // Assume the offsets are in order. We return the previous field if // the current offset is bigger than the given offset. unsigned TheIdx = 0; for (unsigned Idx = 1; Idx < Node->getNumOperands(); Idx += 2) { - uint64_t Cur = cast(Node->getOperand(Idx))->getZExtValue(); + uint64_t Cur = cast(Node->getOperand(Idx + 1))-> + getZExtValue(); if (Cur > Offset) { assert(Idx >= 3 && "TBAAStructTypeNode::getParent should have an offset match!"); @@ -171,10 +192,10 @@ namespace { // Move along the last field. if (TheIdx == 0) TheIdx = Node->getNumOperands() - 2; - uint64_t Cur = cast(Node->getOperand(TheIdx))-> + uint64_t Cur = cast(Node->getOperand(TheIdx + 1))-> getZExtValue(); Offset -= Cur; - MDNode *P = dyn_cast_or_null(Node->getOperand(TheIdx + 1)); + MDNode *P = dyn_cast_or_null(Node->getOperand(TheIdx)); if (!P) return TBAAStructTypeNode(); return TBAAStructTypeNode(P); @@ -376,7 +397,8 @@ bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Location &Loc, // If this is an "immutable" type, we can assume the pointer is pointing // to constant memory. - if (!EnableStructPathTBAA && TBAANode(M).TypeIsImmutable()) + if ((!EnableStructPathTBAA && TBAANode(M).TypeIsImmutable()) || + (EnableStructPathTBAA && TBAAStructTagNode(M).TypeIsImmutable())) return true; return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); @@ -392,7 +414,8 @@ TypeBasedAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { // If this is an "immutable" type, we can assume the call doesn't write // to memory. if (const MDNode *M = CS.getInstruction()->getMetadata(LLVMContext::MD_tbaa)) - if (!EnableStructPathTBAA && TBAANode(M).TypeIsImmutable()) + if ((!EnableStructPathTBAA && TBAANode(M).TypeIsImmutable()) || + (EnableStructPathTBAA && TBAAStructTagNode(M).TypeIsImmutable())) Min = OnlyReadsMemory; return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); @@ -454,20 +477,14 @@ MDNode *MDNode::getMostGenericTBAA(MDNode *A, MDNode *B) { MDNode *T = A; while (T) { PathA.push_back(T); - if (EnableStructPathTBAA) - T = T->getNumOperands() >= 3 ? cast_or_null(T->getOperand(2)) : 0; - else - T = T->getNumOperands() >= 2 ? cast_or_null(T->getOperand(1)) : 0; + T = T->getNumOperands() >= 2 ? cast_or_null(T->getOperand(1)) : 0; } SmallVector PathB; T = B; while (T) { PathB.push_back(T); - if (EnableStructPathTBAA) - T = T->getNumOperands() >= 3 ? cast_or_null(T->getOperand(2)) : 0; - else - T = T->getNumOperands() >= 2 ? cast_or_null(T->getOperand(1)) : 0; + T = T->getNumOperands() >= 2 ? cast_or_null(T->getOperand(1)) : 0; } int IA = PathA.size() - 1; diff --git a/test/Analysis/TypeBasedAliasAnalysis/tbaa-path.ll b/test/Analysis/TypeBasedAliasAnalysis/tbaa-path.ll index c63abca3885..ee527639b3d 100644 --- a/test/Analysis/TypeBasedAliasAnalysis/tbaa-path.ll +++ b/test/Analysis/TypeBasedAliasAnalysis/tbaa-path.ll @@ -364,29 +364,29 @@ entry: attributes #0 = { nounwind "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-frame-pointer-elim-non-leaf"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "unsafe-fp-math"="false" "use-soft-float"="false" } !0 = metadata !{metadata !1, metadata !1, i64 0} -!1 = metadata !{metadata !"any pointer", i64 0, metadata !2} -!2 = metadata !{metadata !"omnipotent char", i64 0, metadata !3} +!1 = metadata !{metadata !"any pointer", metadata !2} +!2 = metadata !{metadata !"omnipotent char", metadata !3} !3 = metadata !{metadata !"Simple C/C++ TBAA"} !4 = metadata !{metadata !5, metadata !5, i64 0} -!5 = metadata !{metadata !"long long", i64 0, metadata !2} +!5 = metadata !{metadata !"long long", metadata !2} !6 = metadata !{metadata !7, metadata !7, i64 0} -!7 = metadata !{metadata !"int", i64 0, metadata !2} +!7 = metadata !{metadata !"int", metadata !2} !8 = metadata !{metadata !9, metadata !7, i64 4} -!9 = metadata !{metadata !"_ZTS7StructA", i64 0, metadata !10, i64 4, metadata !7, i64 8, metadata !10, i64 12, metadata !7} -!10 = metadata !{metadata !"short", i64 0, metadata !2} +!9 = metadata !{metadata !"_ZTS7StructA", metadata !10, i64 0, metadata !7, i64 4, metadata !10, i64 8, metadata !7, i64 12} +!10 = metadata !{metadata !"short", metadata !2} !11 = metadata !{metadata !9, metadata !10, i64 0} !12 = metadata !{metadata !13, metadata !7, i64 8} -!13 = metadata !{metadata !"_ZTS7StructB", i64 0, metadata !10, i64 4, metadata !9, i64 20, metadata !7} +!13 = metadata !{metadata !"_ZTS7StructB", metadata !10, i64 0, metadata !9, i64 4, metadata !7, i64 20} !14 = metadata !{metadata !13, metadata !10, i64 4} !15 = metadata !{metadata !13, metadata !7, i64 20} !16 = metadata !{metadata !13, metadata !7, i64 16} !17 = metadata !{metadata !18, metadata !7, i64 4} -!18 = metadata !{metadata !"_ZTS7StructS", i64 0, metadata !10, i64 4, metadata !7} +!18 = metadata !{metadata !"_ZTS7StructS", metadata !10, i64 0, metadata !7, i64 4} !19 = metadata !{metadata !18, metadata !10, i64 0} !20 = metadata !{metadata !21, metadata !7, i64 4} -!21 = metadata !{metadata !"_ZTS8StructS2", i64 0, metadata !10, i64 4, metadata !7} +!21 = metadata !{metadata !"_ZTS8StructS2", metadata !10, i64 0, metadata !7, i64 4} !22 = metadata !{metadata !21, metadata !10, i64 0} !23 = metadata !{metadata !24, metadata !7, i64 12} -!24 = metadata !{metadata !"_ZTS7StructC", i64 0, metadata !10, i64 4, metadata !13, i64 28, metadata !7} +!24 = metadata !{metadata !"_ZTS7StructC", metadata !10, i64 0, metadata !13, i64 4, metadata !7, i64 28} !25 = metadata !{metadata !26, metadata !7, i64 12} -!26 = metadata !{metadata !"_ZTS7StructD", i64 0, metadata !10, i64 4, metadata !13, i64 28, metadata !7, i64 32, metadata !2} +!26 = metadata !{metadata !"_ZTS7StructD", metadata !10, i64 0, metadata !13, i64 4, metadata !7, i64 28, metadata !2, i64 32} -- 2.34.1