1 //===- Float2Int.cpp - Demote floating point ops to work on integers ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the Float2Int pass, which aims to demote floating
11 // point operations to work on integers, where that is losslessly possible.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "float2int"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/APSInt.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/EquivalenceClasses.h"
20 #include "llvm/ADT/MapVector.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/Analysis/GlobalsModRef.h"
24 #include "llvm/IR/ConstantRange.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/InstIterator.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/Module.h"
30 #include "llvm/Pass.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include "llvm/Transforms/Scalar.h"
35 #include <functional> // For std::function
38 // The algorithm is simple. Start at instructions that convert from the
39 // float to the int domain: fptoui, fptosi and fcmp. Walk up the def-use
40 // graph, using an equivalence datastructure to unify graphs that interfere.
42 // Mappable instructions are those with an integer corrollary that, given
43 // integer domain inputs, produce an integer output; fadd, for example.
45 // If a non-mappable instruction is seen, this entire def-use graph is marked
46 // as non-transformable. If we see an instruction that converts from the
47 // integer domain to FP domain (uitofp,sitofp), we terminate our walk.
49 /// The largest integer type worth dealing with.
50 static cl::opt<unsigned>
51 MaxIntegerBW("float2int-max-integer-bw", cl::init(64), cl::Hidden,
52 cl::desc("Max integer bitwidth to consider in float2int"
56 struct Float2Int : public FunctionPass {
57 static char ID; // Pass identification, replacement for typeid
58 Float2Int() : FunctionPass(ID) {
59 initializeFloat2IntPass(*PassRegistry::getPassRegistry());
62 bool runOnFunction(Function &F) override;
63 void getAnalysisUsage(AnalysisUsage &AU) const override {
65 AU.addPreserved<GlobalsAAWrapperPass>();
68 void findRoots(Function &F, SmallPtrSet<Instruction*,8> &Roots);
69 ConstantRange seen(Instruction *I, ConstantRange R);
70 ConstantRange badRange();
71 ConstantRange unknownRange();
72 ConstantRange validateRange(ConstantRange R);
73 void walkBackwards(const SmallPtrSetImpl<Instruction*> &Roots);
75 bool validateAndTransform();
76 Value *convert(Instruction *I, Type *ToTy);
79 MapVector<Instruction*, ConstantRange > SeenInsts;
80 SmallPtrSet<Instruction*,8> Roots;
81 EquivalenceClasses<Instruction*> ECs;
82 MapVector<Instruction*, Value*> ConvertedInsts;
87 char Float2Int::ID = 0;
88 INITIALIZE_PASS_BEGIN(Float2Int, "float2int", "Float to int", false, false)
89 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
90 INITIALIZE_PASS_END(Float2Int, "float2int", "Float to int", false, false)
92 // Given a FCmp predicate, return a matching ICmp predicate if one
93 // exists, otherwise return BAD_ICMP_PREDICATE.
94 static CmpInst::Predicate mapFCmpPred(CmpInst::Predicate P) {
96 case CmpInst::FCMP_OEQ:
97 case CmpInst::FCMP_UEQ:
98 return CmpInst::ICMP_EQ;
99 case CmpInst::FCMP_OGT:
100 case CmpInst::FCMP_UGT:
101 return CmpInst::ICMP_SGT;
102 case CmpInst::FCMP_OGE:
103 case CmpInst::FCMP_UGE:
104 return CmpInst::ICMP_SGE;
105 case CmpInst::FCMP_OLT:
106 case CmpInst::FCMP_ULT:
107 return CmpInst::ICMP_SLT;
108 case CmpInst::FCMP_OLE:
109 case CmpInst::FCMP_ULE:
110 return CmpInst::ICMP_SLE;
111 case CmpInst::FCMP_ONE:
112 case CmpInst::FCMP_UNE:
113 return CmpInst::ICMP_NE;
115 return CmpInst::BAD_ICMP_PREDICATE;
119 // Given a floating point binary operator, return the matching
121 static Instruction::BinaryOps mapBinOpcode(unsigned Opcode) {
123 default: llvm_unreachable("Unhandled opcode!");
124 case Instruction::FAdd: return Instruction::Add;
125 case Instruction::FSub: return Instruction::Sub;
126 case Instruction::FMul: return Instruction::Mul;
130 // Find the roots - instructions that convert from the FP domain to
132 void Float2Int::findRoots(Function &F, SmallPtrSet<Instruction*,8> &Roots) {
133 for (auto &I : instructions(F)) {
134 if (isa<VectorType>(I.getType()))
136 switch (I.getOpcode()) {
138 case Instruction::FPToUI:
139 case Instruction::FPToSI:
142 case Instruction::FCmp:
143 if (mapFCmpPred(cast<CmpInst>(&I)->getPredicate()) !=
144 CmpInst::BAD_ICMP_PREDICATE)
151 // Helper - mark I as having been traversed, having range R.
152 ConstantRange Float2Int::seen(Instruction *I, ConstantRange R) {
153 DEBUG(dbgs() << "F2I: " << *I << ":" << R << "\n");
154 if (SeenInsts.find(I) != SeenInsts.end())
155 SeenInsts.find(I)->second = R;
157 SeenInsts.insert(std::make_pair(I, R));
161 // Helper - get a range representing a poison value.
162 ConstantRange Float2Int::badRange() {
163 return ConstantRange(MaxIntegerBW + 1, true);
165 ConstantRange Float2Int::unknownRange() {
166 return ConstantRange(MaxIntegerBW + 1, false);
168 ConstantRange Float2Int::validateRange(ConstantRange R) {
169 if (R.getBitWidth() > MaxIntegerBW + 1)
174 // The most obvious way to structure the search is a depth-first, eager
175 // search from each root. However, that require direct recursion and so
176 // can only handle small instruction sequences. Instead, we split the search
177 // up into two phases:
178 // - walkBackwards: A breadth-first walk of the use-def graph starting from
179 // the roots. Populate "SeenInsts" with interesting
180 // instructions and poison values if they're obvious and
181 // cheap to compute. Calculate the equivalance set structure
182 // while we're here too.
183 // - walkForwards: Iterate over SeenInsts in reverse order, so we visit
184 // defs before their uses. Calculate the real range info.
186 // Breadth-first walk of the use-def graph; determine the set of nodes
187 // we care about and eagerly determine if some of them are poisonous.
188 void Float2Int::walkBackwards(const SmallPtrSetImpl<Instruction*> &Roots) {
189 std::deque<Instruction*> Worklist(Roots.begin(), Roots.end());
190 while (!Worklist.empty()) {
191 Instruction *I = Worklist.back();
194 if (SeenInsts.find(I) != SeenInsts.end())
198 switch (I->getOpcode()) {
199 // FIXME: Handle select and phi nodes.
201 // Path terminated uncleanly.
205 case Instruction::UIToFP: {
206 // Path terminated cleanly.
207 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
208 APInt Min = APInt::getMinValue(BW).zextOrSelf(MaxIntegerBW+1);
209 APInt Max = APInt::getMaxValue(BW).zextOrSelf(MaxIntegerBW+1);
210 seen(I, validateRange(ConstantRange(Min, Max)));
214 case Instruction::SIToFP: {
215 // Path terminated cleanly.
216 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
217 APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(MaxIntegerBW+1);
218 APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(MaxIntegerBW+1);
219 seen(I, validateRange(ConstantRange(SMin, SMax)));
223 case Instruction::FAdd:
224 case Instruction::FSub:
225 case Instruction::FMul:
226 case Instruction::FPToUI:
227 case Instruction::FPToSI:
228 case Instruction::FCmp:
229 seen(I, unknownRange());
233 for (Value *O : I->operands()) {
234 if (Instruction *OI = dyn_cast<Instruction>(O)) {
235 // Unify def-use chains if they interfere.
236 ECs.unionSets(I, OI);
237 if (SeenInsts.find(I)->second != badRange())
238 Worklist.push_back(OI);
239 } else if (!isa<ConstantFP>(O)) {
240 // Not an instruction or ConstantFP? we can't do anything.
247 // Walk forwards down the list of seen instructions, so we visit defs before
249 void Float2Int::walkForwards() {
250 for (auto &It : make_range(SeenInsts.rbegin(), SeenInsts.rend())) {
251 if (It.second != unknownRange())
254 Instruction *I = It.first;
255 std::function<ConstantRange(ArrayRef<ConstantRange>)> Op;
256 switch (I->getOpcode()) {
257 // FIXME: Handle select and phi nodes.
259 case Instruction::UIToFP:
260 case Instruction::SIToFP:
261 llvm_unreachable("Should have been handled in walkForwards!");
263 case Instruction::FAdd:
264 Op = [](ArrayRef<ConstantRange> Ops) {
265 assert(Ops.size() == 2 && "FAdd is a binary operator!");
266 return Ops[0].add(Ops[1]);
270 case Instruction::FSub:
271 Op = [](ArrayRef<ConstantRange> Ops) {
272 assert(Ops.size() == 2 && "FSub is a binary operator!");
273 return Ops[0].sub(Ops[1]);
277 case Instruction::FMul:
278 Op = [](ArrayRef<ConstantRange> Ops) {
279 assert(Ops.size() == 2 && "FMul is a binary operator!");
280 return Ops[0].multiply(Ops[1]);
285 // Root-only instructions - we'll only see these if they're the
286 // first node in a walk.
288 case Instruction::FPToUI:
289 case Instruction::FPToSI:
290 Op = [](ArrayRef<ConstantRange> Ops) {
291 assert(Ops.size() == 1 && "FPTo[US]I is a unary operator!");
296 case Instruction::FCmp:
297 Op = [](ArrayRef<ConstantRange> Ops) {
298 assert(Ops.size() == 2 && "FCmp is a binary operator!");
299 return Ops[0].unionWith(Ops[1]);
305 SmallVector<ConstantRange,4> OpRanges;
306 for (Value *O : I->operands()) {
307 if (Instruction *OI = dyn_cast<Instruction>(O)) {
308 assert(SeenInsts.find(OI) != SeenInsts.end() &&
309 "def not seen before use!");
310 OpRanges.push_back(SeenInsts.find(OI)->second);
311 } else if (ConstantFP *CF = dyn_cast<ConstantFP>(O)) {
312 // Work out if the floating point number can be losslessly represented
314 // APFloat::convertToInteger(&Exact) purports to do what we want, but
315 // the exactness can be too precise. For example, negative zero can
316 // never be exactly converted to an integer.
318 // Instead, we ask APFloat to round itself to an integral value - this
319 // preserves sign-of-zero - then compare the result with the original.
321 APFloat F = CF->getValueAPF();
323 // First, weed out obviously incorrect values. Non-finite numbers
324 // can't be represented and neither can negative zero, unless
325 // we're in fast math mode.
327 (F.isZero() && F.isNegative() && isa<FPMathOperator>(I) &&
328 !I->hasNoSignedZeros())) {
335 auto Res = NewF.roundToIntegral(APFloat::rmNearestTiesToEven);
336 if (Res != APFloat::opOK || NewF.compare(F) != APFloat::cmpEqual) {
341 // OK, it's representable. Now get it.
342 APSInt Int(MaxIntegerBW+1, false);
344 CF->getValueAPF().convertToInteger(Int,
345 APFloat::rmNearestTiesToEven,
347 OpRanges.push_back(ConstantRange(Int));
349 llvm_unreachable("Should have already marked this as badRange!");
353 // Reduce the operands' ranges to a single range and return.
355 seen(I, Op(OpRanges));
359 // If there is a valid transform to be done, do it.
360 bool Float2Int::validateAndTransform() {
361 bool MadeChange = false;
363 // Iterate over every disjoint partition of the def-use graph.
364 for (auto It = ECs.begin(), E = ECs.end(); It != E; ++It) {
365 ConstantRange R(MaxIntegerBW + 1, false);
367 Type *ConvertedToTy = nullptr;
369 // For every member of the partition, union all the ranges together.
370 for (auto MI = ECs.member_begin(It), ME = ECs.member_end();
372 Instruction *I = *MI;
373 auto SeenI = SeenInsts.find(I);
374 if (SeenI == SeenInsts.end())
377 R = R.unionWith(SeenI->second);
378 // We need to ensure I has no users that have not been seen.
379 // If it does, transformation would be illegal.
381 // Don't count the roots, as they terminate the graphs.
382 if (Roots.count(I) == 0) {
383 // Set the type of the conversion while we're here.
385 ConvertedToTy = I->getType();
386 for (User *U : I->users()) {
387 Instruction *UI = dyn_cast<Instruction>(U);
388 if (!UI || SeenInsts.find(UI) == SeenInsts.end()) {
389 DEBUG(dbgs() << "F2I: Failing because of " << *U << "\n");
399 // If the set was empty, or we failed, or the range is poisonous,
401 if (ECs.member_begin(It) == ECs.member_end() || Fail ||
402 R.isFullSet() || R.isSignWrappedSet())
404 assert(ConvertedToTy && "Must have set the convertedtoty by this point!");
406 // The number of bits required is the maximum of the upper and
407 // lower limits, plus one so it can be signed.
408 unsigned MinBW = std::max(R.getLower().getMinSignedBits(),
409 R.getUpper().getMinSignedBits()) + 1;
410 DEBUG(dbgs() << "F2I: MinBitwidth=" << MinBW << ", R: " << R << "\n");
412 // If we've run off the realms of the exactly representable integers,
413 // the floating point result will differ from an integer approximation.
415 // Do we need more bits than are in the mantissa of the type we converted
416 // to? semanticsPrecision returns the number of mantissa bits plus one
418 unsigned MaxRepresentableBits
419 = APFloat::semanticsPrecision(ConvertedToTy->getFltSemantics()) - 1;
420 if (MinBW > MaxRepresentableBits) {
421 DEBUG(dbgs() << "F2I: Value not guaranteed to be representable!\n");
425 DEBUG(dbgs() << "F2I: Value requires more than 64 bits to represent!\n");
429 // OK, R is known to be representable. Now pick a type for it.
430 // FIXME: Pick the smallest legal type that will fit.
431 Type *Ty = (MinBW > 32) ? Type::getInt64Ty(*Ctx) : Type::getInt32Ty(*Ctx);
433 for (auto MI = ECs.member_begin(It), ME = ECs.member_end();
442 Value *Float2Int::convert(Instruction *I, Type *ToTy) {
443 if (ConvertedInsts.find(I) != ConvertedInsts.end())
444 // Already converted this instruction.
445 return ConvertedInsts[I];
447 SmallVector<Value*,4> NewOperands;
448 for (Value *V : I->operands()) {
449 // Don't recurse if we're an instruction that terminates the path.
450 if (I->getOpcode() == Instruction::UIToFP ||
451 I->getOpcode() == Instruction::SIToFP) {
452 NewOperands.push_back(V);
453 } else if (Instruction *VI = dyn_cast<Instruction>(V)) {
454 NewOperands.push_back(convert(VI, ToTy));
455 } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
456 APSInt Val(ToTy->getPrimitiveSizeInBits(), /*IsUnsigned=*/false);
458 CF->getValueAPF().convertToInteger(Val,
459 APFloat::rmNearestTiesToEven,
461 NewOperands.push_back(ConstantInt::get(ToTy, Val));
463 llvm_unreachable("Unhandled operand type?");
467 // Now create a new instruction.
469 Value *NewV = nullptr;
470 switch (I->getOpcode()) {
471 default: llvm_unreachable("Unhandled instruction!");
473 case Instruction::FPToUI:
474 NewV = IRB.CreateZExtOrTrunc(NewOperands[0], I->getType());
477 case Instruction::FPToSI:
478 NewV = IRB.CreateSExtOrTrunc(NewOperands[0], I->getType());
481 case Instruction::FCmp: {
482 CmpInst::Predicate P = mapFCmpPred(cast<CmpInst>(I)->getPredicate());
483 assert(P != CmpInst::BAD_ICMP_PREDICATE && "Unhandled predicate!");
484 NewV = IRB.CreateICmp(P, NewOperands[0], NewOperands[1], I->getName());
488 case Instruction::UIToFP:
489 NewV = IRB.CreateZExtOrTrunc(NewOperands[0], ToTy);
492 case Instruction::SIToFP:
493 NewV = IRB.CreateSExtOrTrunc(NewOperands[0], ToTy);
496 case Instruction::FAdd:
497 case Instruction::FSub:
498 case Instruction::FMul:
499 NewV = IRB.CreateBinOp(mapBinOpcode(I->getOpcode()),
500 NewOperands[0], NewOperands[1],
505 // If we're a root instruction, RAUW.
507 I->replaceAllUsesWith(NewV);
509 ConvertedInsts[I] = NewV;
513 // Perform dead code elimination on the instructions we just modified.
514 void Float2Int::cleanup() {
515 for (auto &I : make_range(ConvertedInsts.rbegin(), ConvertedInsts.rend()))
516 I.first->eraseFromParent();
519 bool Float2Int::runOnFunction(Function &F) {
520 if (skipOptnoneFunction(F))
523 DEBUG(dbgs() << "F2I: Looking at function " << F.getName() << "\n");
524 // Clear out all state.
525 ECs = EquivalenceClasses<Instruction*>();
527 ConvertedInsts.clear();
530 Ctx = &F.getParent()->getContext();
534 walkBackwards(Roots);
537 bool Modified = validateAndTransform();
543 FunctionPass *llvm::createFloat2IntPass() { return new Float2Int(); }