LLVM  13.0.0git
Operator.cpp
Go to the documentation of this file.
1 //===-- Operator.cpp - Implement the LLVM operators -----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the non-inline methods for the LLVM Operator classes.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/IR/Operator.h"
14 #include "llvm/IR/DataLayout.h"
16 #include "llvm/IR/Instructions.h"
17 #include "llvm/IR/Type.h"
18 
19 #include "ConstantsContext.h"
20 
21 namespace llvm {
23  if (auto *I = dyn_cast<GetElementPtrInst>(this))
24  return I->getSourceElementType();
25  return cast<GetElementPtrConstantExpr>(this)->getSourceElementType();
26 }
27 
29  if (auto *I = dyn_cast<GetElementPtrInst>(this))
30  return I->getResultElementType();
31  return cast<GetElementPtrConstantExpr>(this)->getResultElementType();
32 }
33 
35  /// compute the worse possible offset for every level of the GEP et accumulate
36  /// the minimum alignment into Result.
37 
39  for (gep_type_iterator GTI = gep_type_begin(this), GTE = gep_type_end(this);
40  GTI != GTE; ++GTI) {
41  int64_t Offset = 1;
42  ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
43 
44  if (StructType *STy = GTI.getStructTypeOrNull()) {
45  const StructLayout *SL = DL.getStructLayout(STy);
46  Offset = SL->getElementOffset(OpC->getZExtValue());
47  } else {
48  assert(GTI.isSequential() && "should be sequencial");
49  /// If the index isn't know we take 1 because it is the index that will
50  /// give the worse alignment of the offset.
51  int64_t ElemCount = 1;
52  if (OpC)
53  ElemCount = OpC->getZExtValue();
54  Offset = DL.getTypeAllocSize(GTI.getIndexedType()) * ElemCount;
55  }
56  Result = Align(MinAlign(Offset, Result.value()));
57  }
58  return Result;
59 }
60 
62  const DataLayout &DL, APInt &Offset,
63  function_ref<bool(Value &, APInt &)> ExternalAnalysis) const {
64  assert(Offset.getBitWidth() ==
65  DL.getIndexSizeInBits(getPointerAddressSpace()) &&
66  "The offset bit width does not match DL specification.");
69  DL, Offset, ExternalAnalysis);
70 }
71 
73  Type *SourceType, ArrayRef<const Value *> Index, const DataLayout &DL,
74  APInt &Offset, function_ref<bool(Value &, APInt &)> ExternalAnalysis) {
75  bool UsedExternalAnalysis = false;
76  auto AccumulateOffset = [&](APInt Index, uint64_t Size) -> bool {
77  Index = Index.sextOrTrunc(Offset.getBitWidth());
78  APInt IndexedSize = APInt(Offset.getBitWidth(), Size);
79  // For array or vector indices, scale the index by the size of the type.
80  if (!UsedExternalAnalysis) {
81  Offset += Index * IndexedSize;
82  } else {
83  // External Analysis can return a result higher/lower than the value
84  // represents. We need to detect overflow/underflow.
85  bool Overflow = false;
86  APInt OffsetPlus = Index.smul_ov(IndexedSize, Overflow);
87  if (Overflow)
88  return false;
89  Offset = Offset.sadd_ov(OffsetPlus, Overflow);
90  if (Overflow)
91  return false;
92  }
93  return true;
94  };
95  auto begin = generic_gep_type_iterator<decltype(Index.begin())>::begin(
96  SourceType, Index.begin());
97  auto end = generic_gep_type_iterator<decltype(Index.end())>::end(Index.end());
98  for (auto GTI = begin, GTE = end; GTI != GTE; ++GTI) {
99  // Scalable vectors are multiplied by a runtime constant.
100  bool ScalableType = false;
101  if (isa<ScalableVectorType>(GTI.getIndexedType()))
102  ScalableType = true;
103 
104  Value *V = GTI.getOperand();
105  StructType *STy = GTI.getStructTypeOrNull();
106  // Handle ConstantInt if possible.
107  if (auto ConstOffset = dyn_cast<ConstantInt>(V)) {
108  if (ConstOffset->isZero())
109  continue;
110  // if the type is scalable and the constant is not zero (vscale * n * 0 =
111  // 0) bailout.
112  if (ScalableType)
113  return false;
114  // Handle a struct index, which adds its field offset to the pointer.
115  if (STy) {
116  unsigned ElementIdx = ConstOffset->getZExtValue();
117  const StructLayout *SL = DL.getStructLayout(STy);
118  // Element offset is in bytes.
119  if (!AccumulateOffset(
120  APInt(Offset.getBitWidth(), SL->getElementOffset(ElementIdx)),
121  1))
122  return false;
123  continue;
124  }
125  if (!AccumulateOffset(ConstOffset->getValue(),
126  DL.getTypeAllocSize(GTI.getIndexedType())))
127  return false;
128  continue;
129  }
130 
131  // The operand is not constant, check if an external analysis was provided.
132  // External analsis is not applicable to a struct type.
133  if (!ExternalAnalysis || STy || ScalableType)
134  return false;
135  APInt AnalysisIndex;
136  if (!ExternalAnalysis(*V, AnalysisIndex))
137  return false;
138  UsedExternalAnalysis = true;
139  if (!AccumulateOffset(AnalysisIndex,
140  DL.getTypeAllocSize(GTI.getIndexedType())))
141  return false;
142  }
143  return true;
144 }
145 
147  const DataLayout &DL, unsigned BitWidth,
148  SmallDenseMap<Value *, APInt, 8> &VariableOffsets,
149  APInt &ConstantOffset) const {
150  assert(BitWidth == DL.getIndexSizeInBits(getPointerAddressSpace()) &&
151  "The offset bit width does not match DL specification.");
152 
153  auto CollectConstantOffset = [&](APInt Index, uint64_t Size) {
154  Index = Index.sextOrTrunc(BitWidth);
155  APInt IndexedSize = APInt(BitWidth, Size);
156  ConstantOffset += Index * IndexedSize;
157  };
158 
159  for (gep_type_iterator GTI = gep_type_begin(this), GTE = gep_type_end(this);
160  GTI != GTE; ++GTI) {
161  // Scalable vectors are multiplied by a runtime constant.
162  bool ScalableType = isa<ScalableVectorType>(GTI.getIndexedType());
163 
164  Value *V = GTI.getOperand();
165  StructType *STy = GTI.getStructTypeOrNull();
166  // Handle ConstantInt if possible.
167  if (auto ConstOffset = dyn_cast<ConstantInt>(V)) {
168  if (ConstOffset->isZero())
169  continue;
170  // If the type is scalable and the constant is not zero (vscale * n * 0 =
171  // 0) bailout.
172  // TODO: If the runtime value is accessible at any point before DWARF
173  // emission, then we could potentially keep a forward reference to it
174  // in the debug value to be filled in later.
175  if (ScalableType)
176  return false;
177  // Handle a struct index, which adds its field offset to the pointer.
178  if (STy) {
179  unsigned ElementIdx = ConstOffset->getZExtValue();
180  const StructLayout *SL = DL.getStructLayout(STy);
181  // Element offset is in bytes.
182  CollectConstantOffset(APInt(BitWidth, SL->getElementOffset(ElementIdx)),
183  1);
184  continue;
185  }
186  CollectConstantOffset(ConstOffset->getValue(),
187  DL.getTypeAllocSize(GTI.getIndexedType()));
188  continue;
189  }
190 
191  if (STy || ScalableType)
192  return false;
193  // Insert an initial offset of 0 for V iff none exists already, then
194  // increment the offset by IndexedSize.
195  VariableOffsets.try_emplace(V, BitWidth, 0);
196  APInt IndexedSize =
197  APInt(BitWidth, DL.getTypeAllocSize(GTI.getIndexedType()));
198  VariableOffsets[V] += IndexedSize;
199  }
200  return true;
201 }
202 } // namespace llvm
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm
Definition: AllocatorList.h:23
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::generic_gep_type_iterator
Definition: GetElementPtrTypeIterator.h:31
GetElementPtrTypeIterator.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::GEPOperator::collectOffset
bool collectOffset(const DataLayout &DL, unsigned BitWidth, SmallDenseMap< Value *, APInt, 8 > &VariableOffsets, APInt &ConstantOffset) const
Collect the offset of this GEP as a map of Values to their associated APInt multipliers,...
Definition: Operator.cpp:146
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::User::value_op_begin
value_op_iterator value_op_begin()
Definition: User.h:260
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
Operator.h
llvm::gep_type_begin
gep_type_iterator gep_type_begin(const User *GEP)
Definition: GetElementPtrTypeIterator.h:139
llvm::gep_type_end
gep_type_iterator gep_type_end(const User *GEP)
Definition: GetElementPtrTypeIterator.h:146
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::MinAlign
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:672
llvm::GEPOperator::getResultElementType
Type * getResultElementType() const
Definition: Operator.cpp:28
llvm::GEPOperator::getMaxPreservedAlignment
Align getMaxPreservedAlignment(const DataLayout &DL) const
Compute the maximum alignment that this GEP is garranteed to preserve.
Definition: Operator.cpp:34
Align
uint64_t Align
Definition: ELFObjHandler.cpp:83
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
Type.h
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::StructLayout
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:604
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::Value::MaximumAlignment
static const unsigned MaximumAlignment
Definition: Value.h:785
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ConstantsContext.h
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::ConstantInt::getZExtValue
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:140
llvm::GEPOperator::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Method to return the address space of the pointer operand.
Definition: Operator.h:509
llvm::User::value_op_end
value_op_iterator value_op_end()
Definition: User.h:263
llvm::StructLayout::getElementOffset
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:634
llvm::GEPOperator::accumulateConstantOffset
bool accumulateConstantOffset(const DataLayout &DL, APInt &Offset, function_ref< bool(Value &, APInt &)> ExternalAnalysis=nullptr) const
Accumulate the constant address offset of this GEP if possible.
Definition: Operator.cpp:61
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
Instructions.h
llvm::GEPOperator::getSourceElementType
Type * getSourceElementType() const
Definition: Operator.cpp:22
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::try_emplace
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:222
llvm::Value
LLVM Value Representation.
Definition: Value.h:75