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"
15#include "llvm/IR/GetElementPtrTypeIterator.h"
16#include "llvm/IR/Instructions.h"
17#include "llvm/IR/IntrinsicInst.h"
18
19#include "ConstantsContext.h"
20
21using namespace llvm;
22
23bool Operator::hasPoisonGeneratingFlags() const {
24 switch (getOpcode()) {
25 case Instruction::Add:
26 case Instruction::Sub:
27 case Instruction::Mul:
28 case Instruction::Shl: {
29 auto *OBO = cast<OverflowingBinaryOperator>(Val: this);
30 return OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap();
31 }
32 case Instruction::Trunc: {
33 if (auto *TI = dyn_cast<TruncInst>(Val: this))
34 return TI->hasNoUnsignedWrap() || TI->hasNoSignedWrap();
35 return false;
36 }
37 case Instruction::UDiv:
38 case Instruction::SDiv:
39 case Instruction::AShr:
40 case Instruction::LShr:
41 return cast<PossiblyExactOperator>(Val: this)->isExact();
42 case Instruction::Or:
43 return cast<PossiblyDisjointInst>(Val: this)->isDisjoint();
44 case Instruction::GetElementPtr: {
45 auto *GEP = cast<GEPOperator>(Val: this);
46 // Note: inrange exists on constexpr only
47 return GEP->getNoWrapFlags() != GEPNoWrapFlags::none() ||
48 GEP->getInRange() != std::nullopt;
49 }
50 case Instruction::UIToFP:
51 case Instruction::ZExt:
52 if (auto *NNI = dyn_cast<PossiblyNonNegInst>(Val: this))
53 return NNI->hasNonNeg();
54 return false;
55 case Instruction::ICmp:
56 return cast<ICmpInst>(Val: this)->hasSameSign();
57 case Instruction::Call:
58 if (auto *II = dyn_cast<IntrinsicInst>(Val: this)) {
59 switch (II->getIntrinsicID()) {
60 case Intrinsic::ctlz:
61 case Intrinsic::cttz:
62 case Intrinsic::abs:
63 return cast<ConstantInt>(Val: II->getArgOperand(i: 1))->isOneValue();
64 }
65 }
66 [[fallthrough]];
67 default:
68 if (const auto *FP = dyn_cast<FPMathOperator>(Val: this))
69 return FP->hasNoNaNs() || FP->hasNoInfs();
70 return false;
71 }
72}
73
74bool Operator::hasPoisonGeneratingAnnotations() const {
75 if (hasPoisonGeneratingFlags())
76 return true;
77 auto *I = dyn_cast<Instruction>(Val: this);
78 return I && (I->hasPoisonGeneratingReturnAttributes() ||
79 I->hasPoisonGeneratingMetadata());
80}
81
82Type *GEPOperator::getSourceElementType() const {
83 if (auto *I = dyn_cast<GetElementPtrInst>(Val: this))
84 return I->getSourceElementType();
85 return cast<GetElementPtrConstantExpr>(Val: this)->getSourceElementType();
86}
87
88Type *GEPOperator::getResultElementType() const {
89 if (auto *I = dyn_cast<GetElementPtrInst>(Val: this))
90 return I->getResultElementType();
91 return cast<GetElementPtrConstantExpr>(Val: this)->getResultElementType();
92}
93
94std::optional<ConstantRange> GEPOperator::getInRange() const {
95 if (auto *CE = dyn_cast<GetElementPtrConstantExpr>(Val: this))
96 return CE->getInRange();
97 return std::nullopt;
98}
99
100Align GEPOperator::getMaxPreservedAlignment(const DataLayout &DL) const {
101 /// compute the worse possible offset for every level of the GEP et accumulate
102 /// the minimum alignment into Result.
103
104 Align Result = Align(llvm::Value::MaximumAlignment);
105 for (gep_type_iterator GTI = gep_type_begin(GEP: this), GTE = gep_type_end(GEP: this);
106 GTI != GTE; ++GTI) {
107 uint64_t Offset;
108 ConstantInt *OpC = dyn_cast<ConstantInt>(Val: GTI.getOperand());
109
110 if (StructType *STy = GTI.getStructTypeOrNull()) {
111 const StructLayout *SL = DL.getStructLayout(Ty: STy);
112 Offset = SL->getElementOffset(Idx: OpC->getZExtValue());
113 } else {
114 assert(GTI.isSequential() && "should be sequencial");
115 /// If the index isn't known, we take 1 because it is the index that will
116 /// give the worse alignment of the offset.
117 const uint64_t ElemCount = OpC ? OpC->getZExtValue() : 1;
118 Offset = GTI.getSequentialElementStride(DL) * ElemCount;
119 }
120 Result = Align(MinAlign(A: Offset, B: Result.value()));
121 }
122 return Result;
123}
124
125bool GEPOperator::accumulateConstantOffset(
126 const DataLayout &DL, APInt &Offset,
127 function_ref<bool(Value &, APInt &)> ExternalAnalysis) const {
128 assert(Offset.getBitWidth() ==
129 DL.getIndexSizeInBits(getPointerAddressSpace()) &&
130 "The offset bit width does not match DL specification.");
131 SmallVector<const Value *> Index(llvm::drop_begin(RangeOrContainer: operand_values()));
132 return GEPOperator::accumulateConstantOffset(SourceType: getSourceElementType(), Index,
133 DL, Offset, ExternalAnalysis);
134}
135
136bool GEPOperator::accumulateConstantOffset(
137 Type *SourceType, ArrayRef<const Value *> Index, const DataLayout &DL,
138 APInt &Offset, function_ref<bool(Value &, APInt &)> ExternalAnalysis) {
139 // Fast path for canonical getelementptr i8 form.
140 if (SourceType->isIntegerTy(Bitwidth: 8) && !Index.empty() && !ExternalAnalysis) {
141 auto *CI = dyn_cast<ConstantInt>(Val: Index.front());
142 if (CI && CI->getType()->isIntegerTy()) {
143 Offset += CI->getValue().sextOrTrunc(width: Offset.getBitWidth());
144 return true;
145 }
146 return false;
147 }
148
149 bool UsedExternalAnalysis = false;
150 auto AccumulateOffset = [&](APInt Index, uint64_t Size) -> bool {
151 Index = Index.sextOrTrunc(width: Offset.getBitWidth());
152 // Truncate if type size exceeds index space.
153 APInt IndexedSize(Offset.getBitWidth(), Size, /*isSigned=*/false,
154 /*implcitTrunc=*/true);
155 // For array or vector indices, scale the index by the size of the type.
156 if (!UsedExternalAnalysis) {
157 Offset += Index * IndexedSize;
158 } else {
159 // External Analysis can return a result higher/lower than the value
160 // represents. We need to detect overflow/underflow.
161 bool Overflow = false;
162 APInt OffsetPlus = Index.smul_ov(RHS: IndexedSize, Overflow);
163 if (Overflow)
164 return false;
165 Offset = Offset.sadd_ov(RHS: OffsetPlus, Overflow);
166 if (Overflow)
167 return false;
168 }
169 return true;
170 };
171 auto begin = generic_gep_type_iterator<decltype(Index.begin())>::begin(
172 Ty: SourceType, It: Index.begin());
173 auto end = generic_gep_type_iterator<decltype(Index.end())>::end(It: Index.end());
174 for (auto GTI = begin, GTE = end; GTI != GTE; ++GTI) {
175 // Scalable vectors are multiplied by a runtime constant.
176 bool ScalableType = GTI.getIndexedType()->isScalableTy();
177
178 Value *V = GTI.getOperand();
179 StructType *STy = GTI.getStructTypeOrNull();
180 // Handle ConstantInt if possible.
181 auto *ConstOffset = dyn_cast<ConstantInt>(Val: V);
182 if (ConstOffset && ConstOffset->getType()->isIntegerTy()) {
183 if (ConstOffset->isZero())
184 continue;
185 // if the type is scalable and the constant is not zero (vscale * n * 0 =
186 // 0) bailout.
187 if (ScalableType)
188 return false;
189 // Handle a struct index, which adds its field offset to the pointer.
190 if (STy) {
191 unsigned ElementIdx = ConstOffset->getZExtValue();
192 const StructLayout *SL = DL.getStructLayout(Ty: STy);
193 // Element offset is in bytes.
194 if (!AccumulateOffset(
195 APInt(Offset.getBitWidth(), SL->getElementOffset(Idx: ElementIdx)),
196 1))
197 return false;
198 continue;
199 }
200 if (!AccumulateOffset(ConstOffset->getValue(),
201 GTI.getSequentialElementStride(DL)))
202 return false;
203 continue;
204 }
205
206 // The operand is not constant, check if an external analysis was provided.
207 // External analsis is not applicable to a struct type.
208 if (!ExternalAnalysis || STy || ScalableType)
209 return false;
210 APInt AnalysisIndex;
211 if (!ExternalAnalysis(*V, AnalysisIndex))
212 return false;
213 UsedExternalAnalysis = true;
214 if (!AccumulateOffset(AnalysisIndex, GTI.getSequentialElementStride(DL)))
215 return false;
216 }
217 return true;
218}
219
220bool GEPOperator::collectOffset(
221 const DataLayout &DL, unsigned BitWidth,
222 SmallMapVector<Value *, APInt, 4> &VariableOffsets,
223 APInt &ConstantOffset) const {
224 assert(BitWidth == DL.getIndexSizeInBits(getPointerAddressSpace()) &&
225 "The offset bit width does not match DL specification.");
226
227 auto CollectConstantOffset = [&](APInt Index, uint64_t Size) {
228 Index = Index.sextOrTrunc(width: BitWidth);
229 // Truncate if type size exceeds index space.
230 APInt IndexedSize(BitWidth, Size, /*isSigned=*/false,
231 /*implcitTrunc=*/true);
232 ConstantOffset += Index * IndexedSize;
233 };
234
235 for (gep_type_iterator GTI = gep_type_begin(GEP: this), GTE = gep_type_end(GEP: this);
236 GTI != GTE; ++GTI) {
237 // Scalable vectors are multiplied by a runtime constant.
238 bool ScalableType = GTI.getIndexedType()->isScalableTy();
239
240 Value *V = GTI.getOperand();
241 StructType *STy = GTI.getStructTypeOrNull();
242 // Handle ConstantInt if possible.
243 auto *ConstOffset = dyn_cast<ConstantInt>(Val: V);
244 if (ConstOffset && ConstOffset->getType()->isIntegerTy()) {
245 if (ConstOffset->isZero())
246 continue;
247 // If the type is scalable and the constant is not zero (vscale * n * 0 =
248 // 0) bailout.
249 // TODO: If the runtime value is accessible at any point before DWARF
250 // emission, then we could potentially keep a forward reference to it
251 // in the debug value to be filled in later.
252 if (ScalableType)
253 return false;
254 // Handle a struct index, which adds its field offset to the pointer.
255 if (STy) {
256 unsigned ElementIdx = ConstOffset->getZExtValue();
257 const StructLayout *SL = DL.getStructLayout(Ty: STy);
258 // Element offset is in bytes.
259 CollectConstantOffset(APInt(BitWidth, SL->getElementOffset(Idx: ElementIdx)),
260 1);
261 continue;
262 }
263 CollectConstantOffset(ConstOffset->getValue(),
264 GTI.getSequentialElementStride(DL));
265 continue;
266 }
267
268 if (STy || ScalableType)
269 return false;
270 // Truncate if type size exceeds index space.
271 APInt IndexedSize(BitWidth, GTI.getSequentialElementStride(DL),
272 /*isSigned=*/false, /*implicitTrunc=*/true);
273 // Insert an initial offset of 0 for V iff none exists already, then
274 // increment the offset by IndexedSize.
275 if (!IndexedSize.isZero()) {
276 auto *It = VariableOffsets.insert(KV: {V, APInt(BitWidth, 0)}).first;
277 It->second += IndexedSize;
278 }
279 }
280 return true;
281}
282
283void FastMathFlags::print(raw_ostream &O) const {
284 if (all())
285 O << " fast";
286 else {
287 if (allowReassoc())
288 O << " reassoc";
289 if (noNaNs())
290 O << " nnan";
291 if (noInfs())
292 O << " ninf";
293 if (noSignedZeros())
294 O << " nsz";
295 if (allowReciprocal())
296 O << " arcp";
297 if (allowContract())
298 O << " contract";
299 if (approxFunc())
300 O << " afn";
301 }
302}
303