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