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