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