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(
196 APInt(Offset.getBitWidth(), SL->getElementOffset(Idx: ElementIdx)),
197 1))
198 return false;
199 continue;
200 }
201 if (!AccumulateOffset(ConstOffset->getValue(),
202 GTI.getSequentialElementStride(DL)))
203 return false;
204 continue;
205 }
206
207 // The operand is not constant, check if an external analysis was provided.
208 // External analsis is not applicable to a struct type.
209 if (!ExternalAnalysis || STy || ScalableType)
210 return false;
211 APInt AnalysisIndex;
212 if (!ExternalAnalysis(*V, AnalysisIndex))
213 return false;
214 UsedExternalAnalysis = true;
215 if (!AccumulateOffset(AnalysisIndex, GTI.getSequentialElementStride(DL)))
216 return false;
217 }
218 return true;
219}
220
221bool GEPOperator::collectOffset(
222 const DataLayout &DL, unsigned BitWidth,
223 SmallMapVector<Value *, APInt, 4> &VariableOffsets,
224 APInt &ConstantOffset) const {
225 assert(BitWidth == DL.getIndexSizeInBits(getPointerAddressSpace()) &&
226 "The offset bit width does not match DL specification.");
227
228 auto CollectConstantOffset = [&](APInt Index, uint64_t Size) {
229 Index = Index.sextOrTrunc(width: BitWidth);
230 // Truncate if type size exceeds index space.
231 APInt IndexedSize(BitWidth, Size, /*isSigned=*/false,
232 /*implcitTrunc=*/true);
233 ConstantOffset += Index * IndexedSize;
234 };
235
236 for (gep_type_iterator GTI = gep_type_begin(GEP: this), GTE = gep_type_end(GEP: this);
237 GTI != GTE; ++GTI) {
238 // Scalable vectors are multiplied by a runtime constant.
239 bool ScalableType = GTI.getIndexedType()->isScalableTy();
240
241 Value *V = GTI.getOperand();
242 StructType *STy = GTI.getStructTypeOrNull();
243 // Handle ConstantInt if possible.
244 auto *ConstOffset = dyn_cast<ConstantInt>(Val: V);
245 if (ConstOffset && ConstOffset->getType()->isIntegerTy()) {
246 if (ConstOffset->isZero())
247 continue;
248 // If the type is scalable and the constant is not zero (vscale * n * 0 =
249 // 0) bailout.
250 // TODO: If the runtime value is accessible at any point before DWARF
251 // emission, then we could potentially keep a forward reference to it
252 // in the debug value to be filled in later.
253 if (ScalableType)
254 return false;
255 // Handle a struct index, which adds its field offset to the pointer.
256 if (STy) {
257 unsigned ElementIdx = ConstOffset->getZExtValue();
258 const StructLayout *SL = DL.getStructLayout(Ty: STy);
259 // Element offset is in bytes.
260 CollectConstantOffset(APInt(BitWidth, SL->getElementOffset(Idx: ElementIdx)),
261 1);
262 continue;
263 }
264 CollectConstantOffset(ConstOffset->getValue(),
265 GTI.getSequentialElementStride(DL));
266 continue;
267 }
268
269 if (STy || ScalableType)
270 return false;
271 // Truncate if type size exceeds index space.
272 APInt IndexedSize(BitWidth, GTI.getSequentialElementStride(DL),
273 /*isSigned=*/false, /*implicitTrunc=*/true);
274 // Insert an initial offset of 0 for V iff none exists already, then
275 // increment the offset by IndexedSize.
276 if (!IndexedSize.isZero()) {
277 auto *It = VariableOffsets.insert(KV: {V, APInt(BitWidth, 0)}).first;
278 It->second += IndexedSize;
279 }
280 }
281 return true;
282}
283
284void FastMathFlags::print(raw_ostream &O) const {
285 if (all())
286 O << " fast";
287 else {
288 if (allowReassoc())
289 O << " reassoc";
290 if (noNaNs())
291 O << " nnan";
292 if (noInfs())
293 O << " ninf";
294 if (noSignedZeros())
295 O << " nsz";
296 if (allowReciprocal())
297 O << " arcp";
298 if (allowContract())
299 O << " contract";
300 if (approxFunc())
301 O << " afn";
302 }
303}
304
305FastMathFlags &FPMathOperator::getFastMathFlagsImpl() {
306 auto *I = cast<Instruction>(Val: this);
307
308 if (FastMathFlagsStorage *Op = dyn_cast<FPUnaryOperator>(Val: I))
309 return Op->FMF;
310 if (FastMathFlagsStorage *Op = dyn_cast<FPBinaryOperator>(Val: I))
311 return Op->FMF;
312 if (FastMathFlagsStorage *Op = dyn_cast<FPTruncInst>(Val: I))
313 return Op->FMF;
314 if (FastMathFlagsStorage *Op = dyn_cast<FPExtInst>(Val: I))
315 return Op->FMF;
316 if (FastMathFlagsStorage *Op = dyn_cast<FCmpInst>(Val: I))
317 return Op->FMF;
318 if (FastMathFlagsStorage *Op = dyn_cast<PHINode>(Val: I))
319 return Op->FMF;
320 if (FastMathFlagsStorage *Op = dyn_cast<SelectInst>(Val: I))
321 return Op->FMF;
322 if (FastMathFlagsStorage *Op = dyn_cast<CallInst>(Val: I))
323 return Op->FMF;
324 if (FastMathFlagsStorage *Op = dyn_cast<UIToFPInst>(Val: I))
325 return Op->FMF;
326 if (FastMathFlagsStorage *Op = dyn_cast<SIToFPInst>(Val: I))
327 return Op->FMF;
328
329 llvm_unreachable("Unknown FPMathOperator!");
330}
331