diff --git a/llvm/include/llvm/IR/TBAA.h b/llvm/include/llvm/IR/TBAA.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/IR/TBAA.h @@ -0,0 +1,206 @@ +//===---- llvm/TBAA.h - Wrapper for LLVM TBAA metadata ----------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines wrapper classes for making reasoning about the structure of +// TBAA metadata easier. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_IR_TBAA_H +#define LLVM_IR_TBAA_H + +#include "llvm/IR/Metadata.h" +#include + +namespace llvm { + +/// 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; + // In the old format the first operand is a string. + if (!isa(N->getOperand(0))) + return false; + return true; +} + +/// This is a simple wrapper around an MDNode which provides a higher-level +/// interface by hiding the details of how alias analysis information is encoded +/// in its operands. +template +class TBAANodeImpl { + MDNodeTy *Node = nullptr; + +public: + TBAANodeImpl() = default; + explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {} + + /// getNode - Get the MDNode for this TBAANode. + MDNodeTy *getNode() const { return Node; } + + /// isNewFormat - Return true iff the wrapped type node is in the new + /// size-aware format. + bool isNewFormat() const { return isNewFormatTypeNode(Node); } + + /// getParent - Get this TBAANode's Alias tree parent. + TBAANodeImpl getParent() const { + if (isNewFormat()) + return TBAANodeImpl(cast(Node->getOperand(0))); + + if (Node->getNumOperands() < 2) + return TBAANodeImpl(); + MDNodeTy *P = dyn_cast_or_null(Node->getOperand(1)); + if (!P) + return TBAANodeImpl(); + // Ok, this node has a valid parent. Return it. + return TBAANodeImpl(P); + } + + /// Test if this TBAANode represents a type for objects which are + /// not modified (by any means) in the context where this + /// AliasAnalysis is relevant. + bool isTypeImmutable() const { + if (Node->getNumOperands() < 3) + return false; + ConstantInt *CI = mdconst::dyn_extract(Node->getOperand(2)); + if (!CI) + return false; + return CI->getValue()[0]; + } +}; + +/// \name Specializations of \c TBAANodeImpl for const and non const qualified +/// \c MDNode. +/// @{ +using TBAANode = TBAANodeImpl; +using MutableTBAANode = TBAANodeImpl; +/// @} + +/// This is a simple wrapper around an MDNode which provides a +/// higher-level interface by hiding the details of how alias analysis +/// information is encoded in its operands. +template +class TBAAStructTagNodeImpl { + /// This node should be created with createTBAAAccessTag(). + MDNodeTy *Node; + +public: + explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {} + + /// Get the MDNode for this TBAAStructTagNode. + MDNodeTy *getNode() const { return Node; } + + /// isNewFormat - Return true iff the wrapped access tag is in the new + /// size-aware format. + bool isNewFormat() const { + if (Node->getNumOperands() < 4) + return false; + if (MDNodeTy *AccessType = getAccessType()) + if (!TBAANodeImpl(AccessType).isNewFormat()) + return false; + return true; + } + + MDNodeTy *getBaseType() const { + return dyn_cast_or_null(Node->getOperand(0)); + } + + MDNodeTy *getAccessType() const { + return dyn_cast_or_null(Node->getOperand(1)); + } + + uint64_t getOffset() const { + return mdconst::extract(Node->getOperand(2))->getZExtValue(); + } + + uint64_t getSize() const { + if (!isNewFormat()) + return UINT64_MAX; + return mdconst::extract(Node->getOperand(3))->getZExtValue(); + } + + /// 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 isTypeImmutable() const { + unsigned OpNo = isNewFormat() ? 4 : 3; + if (Node->getNumOperands() < OpNo + 1) + return false; + ConstantInt *CI = mdconst::dyn_extract(Node->getOperand(OpNo)); + if (!CI) + return false; + return CI->getValue()[0]; + } +}; + +/// \name Specializations of \c TBAAStructTagNodeImpl for const and non const +/// qualified \c MDNods. +/// @{ +using TBAAStructTagNode = TBAAStructTagNodeImpl; +using MutableTBAAStructTagNode = TBAAStructTagNodeImpl; +/// @} + +/// This is a simple wrapper around an MDNode which provides a +/// higher-level interface by hiding the details of how alias analysis +/// information is encoded in its operands. +class TBAAStructTypeNode { + /// This node should be created with createTBAATypeNode(). + const MDNode *Node = nullptr; + +public: + TBAAStructTypeNode() = default; + explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} + + /// Get the MDNode for this TBAAStructTypeNode. + const MDNode *getNode() const { return Node; } + + /// isNewFormat - Return true iff the wrapped type node is in the new + /// size-aware format. + bool isNewFormat() const { return isNewFormatTypeNode(Node); } + + bool operator==(const TBAAStructTypeNode &Other) const { + return getNode() == Other.getNode(); + } + + /// getId - Return type identifier. + Metadata *getId() const { + return Node->getOperand(isNewFormat() ? 2 : 0); + } + + unsigned getNumFields() const { + unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1; + unsigned NumOpsPerField = isNewFormat() ? 3 : 2; + return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField; + } + + TBAAStructTypeNode getFieldType(unsigned FieldIndex) const { + unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1; + unsigned NumOpsPerField = isNewFormat() ? 3 : 2; + unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField; + auto *TypeNode = cast(getNode()->getOperand(OpIndex)); + return TBAAStructTypeNode(TypeNode); + } + + /// Get this TBAAStructTypeNode's field in the type DAG with + /// given offset. Update the offset to be relative to the field type. + TBAAStructTypeNode getField(uint64_t &Offset) const; +}; + +/// Check the first operand of the tbaa tag node, if it is a MDNode, we treat +/// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA +/// format. +static bool isStructPathTBAA(const MDNode *MD) { + // Anonymous TBAA root starts with a MDNode and dragonegg uses it as + // a TBAA tag. + return isa(MD->getOperand(0)) && MD->getNumOperands() >= 3; +} + +} // end namespace llvm + +#endif 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 @@ -114,6 +114,7 @@ #include "llvm/IR/InstrTypes.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" +#include "llvm/IR/TBAA.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" @@ -129,242 +130,58 @@ // more convenient. static cl::opt EnableTBAA("enable-tbaa", cl::init(true), 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; - // In the old format the first operand is a string. - if (!isa(N->getOperand(0))) - return false; - return true; -} - -/// This is a simple wrapper around an MDNode which provides a higher-level -/// interface by hiding the details of how alias analysis information is encoded -/// in its operands. -template -class TBAANodeImpl { - MDNodeTy *Node = nullptr; - -public: - TBAANodeImpl() = default; - explicit TBAANodeImpl(MDNodeTy *N) : Node(N) {} - - /// getNode - Get the MDNode for this TBAANode. - MDNodeTy *getNode() const { return Node; } - - /// isNewFormat - Return true iff the wrapped type node is in the new - /// size-aware format. - bool isNewFormat() const { return isNewFormatTypeNode(Node); } - - /// getParent - Get this TBAANode's Alias tree parent. - TBAANodeImpl getParent() const { - if (isNewFormat()) - return TBAANodeImpl(cast(Node->getOperand(0))); - +TBAAStructTypeNode TBAAStructTypeNode::getField(uint64_t &Offset) const { + bool NewFormat = isNewFormat(); + if (NewFormat) { + // New-format root and scalar type nodes have no fields. + if (Node->getNumOperands() < 6) + return TBAAStructTypeNode(); + } else { + // Parent can be omitted for the root node. if (Node->getNumOperands() < 2) - return TBAANodeImpl(); - MDNodeTy *P = dyn_cast_or_null(Node->getOperand(1)); - if (!P) - return TBAANodeImpl(); - // Ok, this node has a valid parent. Return it. - return TBAANodeImpl(P); - } - - /// Test if this TBAANode represents a type for objects which are - /// not modified (by any means) in the context where this - /// AliasAnalysis is relevant. - bool isTypeImmutable() const { - if (Node->getNumOperands() < 3) - return false; - ConstantInt *CI = mdconst::dyn_extract(Node->getOperand(2)); - if (!CI) - return false; - return CI->getValue()[0]; - } -}; - -/// \name Specializations of \c TBAANodeImpl for const and non const qualified -/// \c MDNode. -/// @{ -using TBAANode = TBAANodeImpl; -using MutableTBAANode = TBAANodeImpl; -/// @} - -/// This is a simple wrapper around an MDNode which provides a -/// higher-level interface by hiding the details of how alias analysis -/// information is encoded in its operands. -template -class TBAAStructTagNodeImpl { - /// This node should be created with createTBAAAccessTag(). - MDNodeTy *Node; - -public: - explicit TBAAStructTagNodeImpl(MDNodeTy *N) : Node(N) {} - - /// Get the MDNode for this TBAAStructTagNode. - MDNodeTy *getNode() const { return Node; } - - /// isNewFormat - Return true iff the wrapped access tag is in the new - /// size-aware format. - bool isNewFormat() const { - if (Node->getNumOperands() < 4) - return false; - if (MDNodeTy *AccessType = getAccessType()) - if (!TBAANodeImpl(AccessType).isNewFormat()) - return false; - return true; - } - - MDNodeTy *getBaseType() const { - return dyn_cast_or_null(Node->getOperand(0)); - } - - MDNodeTy *getAccessType() const { - return dyn_cast_or_null(Node->getOperand(1)); - } - - uint64_t getOffset() const { - return mdconst::extract(Node->getOperand(2))->getZExtValue(); - } - - uint64_t getSize() const { - if (!isNewFormat()) - return UINT64_MAX; - return mdconst::extract(Node->getOperand(3))->getZExtValue(); - } - - /// 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 isTypeImmutable() const { - unsigned OpNo = isNewFormat() ? 4 : 3; - if (Node->getNumOperands() < OpNo + 1) - return false; - ConstantInt *CI = mdconst::dyn_extract(Node->getOperand(OpNo)); - if (!CI) - return false; - return CI->getValue()[0]; - } -}; - -/// \name Specializations of \c TBAAStructTagNodeImpl for const and non const -/// qualified \c MDNods. -/// @{ -using TBAAStructTagNode = TBAAStructTagNodeImpl; -using MutableTBAAStructTagNode = TBAAStructTagNodeImpl; -/// @} - -/// This is a simple wrapper around an MDNode which provides a -/// higher-level interface by hiding the details of how alias analysis -/// information is encoded in its operands. -class TBAAStructTypeNode { - /// This node should be created with createTBAATypeNode(). - const MDNode *Node = nullptr; - -public: - TBAAStructTypeNode() = default; - explicit TBAAStructTypeNode(const MDNode *N) : Node(N) {} - - /// Get the MDNode for this TBAAStructTypeNode. - const MDNode *getNode() const { return Node; } - - /// isNewFormat - Return true iff the wrapped type node is in the new - /// size-aware format. - bool isNewFormat() const { return isNewFormatTypeNode(Node); } - - bool operator==(const TBAAStructTypeNode &Other) const { - return getNode() == Other.getNode(); - } - - /// getId - Return type identifier. - Metadata *getId() const { - return Node->getOperand(isNewFormat() ? 2 : 0); - } - - unsigned getNumFields() const { - unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1; - unsigned NumOpsPerField = isNewFormat() ? 3 : 2; - return (getNode()->getNumOperands() - FirstFieldOpNo) / NumOpsPerField; - } - - TBAAStructTypeNode getFieldType(unsigned FieldIndex) const { - unsigned FirstFieldOpNo = isNewFormat() ? 3 : 1; - unsigned NumOpsPerField = isNewFormat() ? 3 : 2; - unsigned OpIndex = FirstFieldOpNo + FieldIndex * NumOpsPerField; - auto *TypeNode = cast(getNode()->getOperand(OpIndex)); - return TBAAStructTypeNode(TypeNode); - } + return TBAAStructTypeNode(); - /// Get this TBAAStructTypeNode's field in the type DAG with - /// given offset. Update the offset to be relative to the field type. - TBAAStructTypeNode getField(uint64_t &Offset) const { - bool NewFormat = isNewFormat(); - if (NewFormat) { - // New-format root and scalar type nodes have no fields. - if (Node->getNumOperands() < 6) + // Fast path for a scalar type node and a struct type node with a single + // field. + if (Node->getNumOperands() <= 3) { + uint64_t Cur = Node->getNumOperands() == 2 + ? 0 + : mdconst::extract(Node->getOperand(2)) + ->getZExtValue(); + Offset -= Cur; + MDNode *P = dyn_cast_or_null(Node->getOperand(1)); + if (!P) return TBAAStructTypeNode(); - } else { - // Parent can be omitted for the root node. - if (Node->getNumOperands() < 2) - return TBAAStructTypeNode(); - - // Fast path for a scalar type node and a struct type node with a single - // field. - if (Node->getNumOperands() <= 3) { - uint64_t Cur = Node->getNumOperands() == 2 - ? 0 - : mdconst::extract(Node->getOperand(2)) - ->getZExtValue(); - Offset -= Cur; - MDNode *P = dyn_cast_or_null(Node->getOperand(1)); - if (!P) - return TBAAStructTypeNode(); - return TBAAStructTypeNode(P); - } + 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 FirstFieldOpNo = NewFormat ? 3 : 1; - unsigned NumOpsPerField = NewFormat ? 3 : 2; - unsigned TheIdx = 0; - for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands(); - Idx += NumOpsPerField) { - uint64_t Cur = mdconst::extract(Node->getOperand(Idx + 1)) - ->getZExtValue(); - if (Cur > Offset) { - assert(Idx >= FirstFieldOpNo + NumOpsPerField && - "TBAAStructTypeNode::getField should have an offset match!"); - TheIdx = Idx - NumOpsPerField; - break; - } + // Assume the offsets are in order. We return the previous field if + // the current offset is bigger than the given offset. + unsigned FirstFieldOpNo = NewFormat ? 3 : 1; + unsigned NumOpsPerField = NewFormat ? 3 : 2; + unsigned TheIdx = 0; + for (unsigned Idx = FirstFieldOpNo; Idx < Node->getNumOperands(); + Idx += NumOpsPerField) { + uint64_t Cur = mdconst::extract(Node->getOperand(Idx + 1)) + ->getZExtValue(); + if (Cur > Offset) { + assert(Idx >= FirstFieldOpNo + NumOpsPerField && + "TBAAStructTypeNode::getField should have an offset match!"); + TheIdx = Idx - NumOpsPerField; + break; } - // Move along the last field. - if (TheIdx == 0) - TheIdx = Node->getNumOperands() - NumOpsPerField; - uint64_t Cur = mdconst::extract(Node->getOperand(TheIdx + 1)) - ->getZExtValue(); - Offset -= Cur; - MDNode *P = dyn_cast_or_null(Node->getOperand(TheIdx)); - if (!P) - return TBAAStructTypeNode(); - return TBAAStructTypeNode(P); } -}; - -} // end anonymous namespace - -/// Check the first operand of the tbaa tag node, if it is a MDNode, we treat -/// it as struct-path aware TBAA format, otherwise, we treat it as scalar TBAA -/// format. -static bool isStructPathTBAA(const MDNode *MD) { - // Anonymous TBAA root starts with a MDNode and dragonegg uses it as - // a TBAA tag. - return isa(MD->getOperand(0)) && MD->getNumOperands() >= 3; + // Move along the last field. + if (TheIdx == 0) + TheIdx = Node->getNumOperands() - NumOpsPerField; + uint64_t Cur = mdconst::extract(Node->getOperand(TheIdx + 1)) + ->getZExtValue(); + Offset -= Cur; + MDNode *P = dyn_cast_or_null(Node->getOperand(TheIdx)); + if (!P) + return TBAAStructTypeNode(); + return TBAAStructTypeNode(P); } AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA,