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