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->hasPoisonGeneratingAttributes() ||
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 =
113 SL->getElementOffset(Idx: OpC->getValue().getLoBits(numBits: 32).getZExtValue());
114 } else {
115 assert(GTI.isSequential() && "should be sequencial");
116 /// If the index isn't known, we take 1 because it is the index that will
117 /// give the worse alignment of the offset.
118 const uint64_t ElemCount = OpC ? OpC->getLimitedValue() : 1;
119 Offset = GTI.getSequentialElementStride(DL) * ElemCount;
120 }
121 Result = Align(MinAlign(A: Offset, B: Result.value()));
122 }
123 return Result;
124}
125
126bool GEPOperator::accumulateConstantOffset(
127 const DataLayout &DL, APInt &Offset,
128 function_ref<bool(Value &, APInt &)> ExternalAnalysis) const {
129 assert(Offset.getBitWidth() ==
130 DL.getIndexSizeInBits(getPointerAddressSpace()) &&
131 "The offset bit width does not match DL specification.");
132 SmallVector<const Value *> Index(llvm::drop_begin(RangeOrContainer: operand_values()));
133 return GEPOperator::accumulateConstantOffset(SourceType: getSourceElementType(), Index,
134 DL, Offset, ExternalAnalysis);
135}
136
137bool GEPOperator::accumulateConstantOffset(
138 Type *SourceType, ArrayRef<const Value *> Index, const DataLayout &DL,
139 APInt &Offset, function_ref<bool(Value &, APInt &)> ExternalAnalysis) {
140 // Fast path for canonical getelementptr i8 form.
141 if (SourceType->isIntegerTy(BitWidth: 8) && !Index.empty() && !ExternalAnalysis) {
142 auto *CI = dyn_cast<ConstantInt>(Val: Index.front());
143 if (CI && CI->getType()->isIntegerTy()) {
144 Offset += CI->getValue().sextOrTrunc(width: Offset.getBitWidth());
145 return true;
146 }
147 return false;
148 }
149
150 bool UsedExternalAnalysis = false;
151 auto AccumulateOffset = [&](APInt Index, uint64_t Size) -> bool {
152 Index = Index.sextOrTrunc(width: Offset.getBitWidth());
153 // Truncate if type size exceeds index space.
154 APInt IndexedSize(Offset.getBitWidth(), Size, /*isSigned=*/false,
155 /*implcitTrunc=*/true);
156 // For array or vector indices, scale the index by the size of the type.
157 if (!UsedExternalAnalysis) {
158 Offset += Index * IndexedSize;
159 } else {
160 // External Analysis can return a result higher/lower than the value
161 // represents. We need to detect overflow/underflow.
162 bool Overflow = false;
163 APInt OffsetPlus = Index.smul_ov(RHS: IndexedSize, Overflow);
164 if (Overflow)
165 return false;
166 Offset = Offset.sadd_ov(RHS: OffsetPlus, Overflow);
167 if (Overflow)
168 return false;
169 }
170 return true;
171 };
172 auto begin = generic_gep_type_iterator<decltype(Index.begin())>::begin(
173 Ty: SourceType, It: Index.begin());
174 auto end = generic_gep_type_iterator<decltype(Index.end())>::end(It: Index.end());
175 for (auto GTI = begin, GTE = end; GTI != GTE; ++GTI) {
176 // Scalable vectors are multiplied by a runtime constant.
177 bool ScalableType = GTI.getIndexedType()->isScalableTy();
178
179 Value *V = GTI.getOperand();
180 StructType *STy = GTI.getStructTypeOrNull();
181 // Handle ConstantInt if possible.
182 auto *ConstOffset = dyn_cast<ConstantInt>(Val: V);
183 if (ConstOffset && ConstOffset->getType()->isIntegerTy()) {
184 if (ConstOffset->isZero())
185 continue;
186 // if the type is scalable and the constant is not zero (vscale * n * 0 =
187 // 0) bailout.
188 if (ScalableType)
189 return false;
190 // Handle a struct index, which adds its field offset to the pointer.
191 if (STy) {
192 unsigned ElementIdx = ConstOffset->getZExtValue();
193 const StructLayout *SL = DL.getStructLayout(Ty: STy);
194 // Element offset is in bytes.
195 if (!AccumulateOffset(APInt(Offset.getBitWidth(),
196 SL->getElementOffset(Idx: ElementIdx),
197 /*isSigned=*/false, /*implicitTrunc=*/true),
198 1))
199 return false;
200 continue;
201 }
202 if (!AccumulateOffset(ConstOffset->getValue(),
203 GTI.getSequentialElementStride(DL)))
204 return false;
205 continue;
206 }
207
208 // The operand is not constant, check if an external analysis was provided.
209 // External analsis is not applicable to a struct type.
210 if (!ExternalAnalysis || STy || ScalableType)
211 return false;
212 APInt AnalysisIndex;
213 if (!ExternalAnalysis(*V, AnalysisIndex))
214 return false;
215 UsedExternalAnalysis = true;
216 if (!AccumulateOffset(AnalysisIndex, GTI.getSequentialElementStride(DL)))
217 return false;
218 }
219 return true;
220}
221
222bool GEPOperator::collectOffset(
223 const DataLayout &DL, unsigned BitWidth,
224 SmallMapVector<Value *, APInt, 4> &VariableOffsets,
225 APInt &ConstantOffset) const {
226 assert(BitWidth == DL.getIndexSizeInBits(getPointerAddressSpace()) &&
227 "The offset bit width does not match DL specification.");
228
229 auto CollectConstantOffset = [&](APInt Index, uint64_t Size) {
230 Index = Index.sextOrTrunc(width: BitWidth);
231 // Truncate if type size exceeds index space.
232 APInt IndexedSize(BitWidth, Size, /*isSigned=*/false,
233 /*implcitTrunc=*/true);
234 ConstantOffset += Index * IndexedSize;
235 };
236
237 for (gep_type_iterator GTI = gep_type_begin(GEP: this), GTE = gep_type_end(GEP: this);
238 GTI != GTE; ++GTI) {
239 // Scalable vectors are multiplied by a runtime constant.
240 bool ScalableType = GTI.getIndexedType()->isScalableTy();
241
242 Value *V = GTI.getOperand();
243 StructType *STy = GTI.getStructTypeOrNull();
244 // Handle ConstantInt if possible.
245 auto *ConstOffset = dyn_cast<ConstantInt>(Val: V);
246 if (ConstOffset && ConstOffset->getType()->isIntegerTy()) {
247 if (ConstOffset->isZero())
248 continue;
249 // If the type is scalable and the constant is not zero (vscale * n * 0 =
250 // 0) bailout.
251 // TODO: If the runtime value is accessible at any point before DWARF
252 // emission, then we could potentially keep a forward reference to it
253 // in the debug value to be filled in later.
254 if (ScalableType)
255 return false;
256 // Handle a struct index, which adds its field offset to the pointer.
257 if (STy) {
258 unsigned ElementIdx = ConstOffset->getZExtValue();
259 const StructLayout *SL = DL.getStructLayout(Ty: STy);
260 // Element offset is in bytes.
261 CollectConstantOffset(APInt(BitWidth, SL->getElementOffset(Idx: ElementIdx),
262 /*isSigned=*/false, /*implicitTrunc=*/true),
263 1);
264 continue;
265 }
266 CollectConstantOffset(ConstOffset->getValue(),
267 GTI.getSequentialElementStride(DL));
268 continue;
269 }
270
271 if (STy || ScalableType)
272 return false;
273 // Truncate if type size exceeds index space.
274 APInt IndexedSize(BitWidth, GTI.getSequentialElementStride(DL),
275 /*isSigned=*/false, /*implicitTrunc=*/true);
276 // Insert an initial offset of 0 for V iff none exists already, then
277 // increment the offset by IndexedSize.
278 if (!IndexedSize.isZero()) {
279 auto *It = VariableOffsets.insert(KV: {V, APInt(BitWidth, 0)}).first;
280 It->second += IndexedSize;
281 }
282 }
283 return true;
284}
285
286void FastMathFlags::print(raw_ostream &O) const {
287 if (all())
288 O << " fast";
289 else {
290 if (allowReassoc())
291 O << " reassoc";
292 if (noNaNs())
293 O << " nnan";
294 if (noInfs())
295 O << " ninf";
296 if (noSignedZeros())
297 O << " nsz";
298 if (allowReciprocal())
299 O << " arcp";
300 if (allowContract())
301 O << " contract";
302 if (approxFunc())
303 O << " afn";
304 }
305}
306
307FastMathFlags &FPMathOperator::getFastMathFlagsImpl() {
308 auto *I = cast<Instruction>(Val: this);
309
310 if (FastMathFlagsStorage *Op = dyn_cast<FPUnaryOperator>(Val: I))
311 return Op->FMF;
312 if (FastMathFlagsStorage *Op = dyn_cast<FPBinaryOperator>(Val: I))
313 return Op->FMF;
314 if (FastMathFlagsStorage *Op = dyn_cast<FPTruncInst>(Val: I))
315 return Op->FMF;
316 if (FastMathFlagsStorage *Op = dyn_cast<FPExtInst>(Val: I))
317 return Op->FMF;
318 if (FastMathFlagsStorage *Op = dyn_cast<FCmpInst>(Val: I))
319 return Op->FMF;
320 if (FastMathFlagsStorage *Op = dyn_cast<PHINode>(Val: I))
321 return Op->FMF;
322 if (FastMathFlagsStorage *Op = dyn_cast<SelectInst>(Val: I))
323 return Op->FMF;
324 if (FastMathFlagsStorage *Op = dyn_cast<CallInst>(Val: I))
325 return Op->FMF;
326 if (FastMathFlagsStorage *Op = dyn_cast<UIToFPInst>(Val: I))
327 return Op->FMF;
328 if (FastMathFlagsStorage *Op = dyn_cast<SIToFPInst>(Val: I))
329 return Op->FMF;
330
331 llvm_unreachable("Unknown FPMathOperator!");
332}
333