1//===- Float2Int.cpp - Demote floating point ops to work on integers ------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the Float2Int pass, which aims to demote floating
11// point operations to work on integers, where that is losslessly possible.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "float2int"
16
17#include "llvm/Transforms/Scalar/Float2Int.h"
18#include "llvm/ADT/APInt.h"
19#include "llvm/ADT/APSInt.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/Analysis/GlobalsModRef.h"
23#include "llvm/IR/Constants.h"
24#include "llvm/IR/IRBuilder.h"
25#include "llvm/IR/InstIterator.h"
26#include "llvm/IR/Instructions.h"
27#include "llvm/IR/Module.h"
28#include "llvm/Pass.h"
29#include "llvm/Support/Debug.h"
30#include "llvm/Support/raw_ostream.h"
31#include "llvm/Transforms/Scalar.h"
32#include <deque>
33#include <functional> // For std::function
34using namespace llvm;
35
36// The algorithm is simple. Start at instructions that convert from the
37// float to the int domain: fptoui, fptosi and fcmp. Walk up the def-use
38// graph, using an equivalence datastructure to unify graphs that interfere.
39//
40// Mappable instructions are those with an integer corrollary that, given
41// integer domain inputs, produce an integer output; fadd, for example.
42//
43// If a non-mappable instruction is seen, this entire def-use graph is marked
44// as non-transformable. If we see an instruction that converts from the
45// integer domain to FP domain (uitofp,sitofp), we terminate our walk.
46
47/// The largest integer type worth dealing with.
48static cl::opt<unsigned>
49MaxIntegerBW("float2int-max-integer-bw", cl::init(64), cl::Hidden,
50             cl::desc("Max integer bitwidth to consider in float2int"
51                      "(default=64)"));
52
53namespace {
54  struct Float2IntLegacyPass : public FunctionPass {
55    static char ID; // Pass identification, replacement for typeid
56    Float2IntLegacyPass() : FunctionPass(ID) {
57      initializeFloat2IntLegacyPassPass(*PassRegistry::getPassRegistry());
58    }
59
60    bool runOnFunction(Function &F) override {
61      if (skipFunction(F))
62        return false;
63
64      return Impl.runImpl(F);
65    }
66
67    void getAnalysisUsage(AnalysisUsage &AU) const override {
68      AU.setPreservesCFG();
69      AU.addPreserved<GlobalsAAWrapperPass>();
70    }
71
72  private:
73    Float2IntPass Impl;
74  };
75}
76
77char Float2IntLegacyPass::ID = 0;
78INITIALIZE_PASS(Float2IntLegacyPass, "float2int", "Float to int", false, false)
79
80// Given a FCmp predicate, return a matching ICmp predicate if one
81// exists, otherwise return BAD_ICMP_PREDICATE.
82static CmpInst::Predicate mapFCmpPred(CmpInst::Predicate P) {
83  switch (P) {
84  case CmpInst::FCMP_OEQ:
85  case CmpInst::FCMP_UEQ:
86    return CmpInst::ICMP_EQ;
87  case CmpInst::FCMP_OGT:
88  case CmpInst::FCMP_UGT:
89    return CmpInst::ICMP_SGT;
90  case CmpInst::FCMP_OGE:
91  case CmpInst::FCMP_UGE:
92    return CmpInst::ICMP_SGE;
93  case CmpInst::FCMP_OLT:
94  case CmpInst::FCMP_ULT:
95    return CmpInst::ICMP_SLT;
96  case CmpInst::FCMP_OLE:
97  case CmpInst::FCMP_ULE:
98    return CmpInst::ICMP_SLE;
99  case CmpInst::FCMP_ONE:
100  case CmpInst::FCMP_UNE:
101    return CmpInst::ICMP_NE;
102  default:
103    return CmpInst::BAD_ICMP_PREDICATE;
104  }
105}
106
107// Given a floating point binary operator, return the matching
108// integer version.
109static Instruction::BinaryOps mapBinOpcode(unsigned Opcode) {
110  switch (Opcode) {
111  default: llvm_unreachable("Unhandled opcode!");
112  case Instruction::FAdd: return Instruction::Add;
113  case Instruction::FSub: return Instruction::Sub;
114  case Instruction::FMul: return Instruction::Mul;
115  }
116}
117
118// Find the roots - instructions that convert from the FP domain to
119// integer domain.
120void Float2IntPass::findRoots(Function &F, SmallPtrSet<Instruction*,8> &Roots) {
121  for (auto &I : instructions(F)) {
122    if (isa<VectorType>(I.getType()))
123      continue;
124    switch (I.getOpcode()) {
125    default: break;
126    case Instruction::FPToUI:
127    case Instruction::FPToSI:
128      Roots.insert(&I);
129      break;
130    case Instruction::FCmp:
131      if (mapFCmpPred(cast<CmpInst>(&I)->getPredicate()) !=
132          CmpInst::BAD_ICMP_PREDICATE)
133        Roots.insert(&I);
134      break;
135    }
136  }
137}
138
139// Helper - mark I as having been traversed, having range R.
140ConstantRange Float2IntPass::seen(Instruction *I, ConstantRange R) {
141  DEBUG(dbgs() << "F2I: " << *I << ":" << R << "\n");
142  if (SeenInsts.find(I) != SeenInsts.end())
143    SeenInsts.find(I)->second = R;
144  else
145    SeenInsts.insert(std::make_pair(I, R));
146  return R;
147}
148
149// Helper - get a range representing a poison value.
150ConstantRange Float2IntPass::badRange() {
151  return ConstantRange(MaxIntegerBW + 1, true);
152}
153ConstantRange Float2IntPass::unknownRange() {
154  return ConstantRange(MaxIntegerBW + 1, false);
155}
156ConstantRange Float2IntPass::validateRange(ConstantRange R) {
157  if (R.getBitWidth() > MaxIntegerBW + 1)
158    return badRange();
159  return R;
160}
161
162// The most obvious way to structure the search is a depth-first, eager
163// search from each root. However, that require direct recursion and so
164// can only handle small instruction sequences. Instead, we split the search
165// up into two phases:
166//   - walkBackwards:  A breadth-first walk of the use-def graph starting from
167//                     the roots. Populate "SeenInsts" with interesting
168//                     instructions and poison values if they're obvious and
169//                     cheap to compute. Calculate the equivalance set structure
170//                     while we're here too.
171//   - walkForwards:  Iterate over SeenInsts in reverse order, so we visit
172//                     defs before their uses. Calculate the real range info.
173
174// Breadth-first walk of the use-def graph; determine the set of nodes
175// we care about and eagerly determine if some of them are poisonous.
176void Float2IntPass::walkBackwards(const SmallPtrSetImpl<Instruction*> &Roots) {
177  std::deque<Instruction*> Worklist(Roots.begin(), Roots.end());
178  while (!Worklist.empty()) {
179    Instruction *I = Worklist.back();
180    Worklist.pop_back();
181
182    if (SeenInsts.find(I) != SeenInsts.end())
183      // Seen already.
184      continue;
185
186    switch (I->getOpcode()) {
187      // FIXME: Handle select and phi nodes.
188    default:
189      // Path terminated uncleanly.
190      seen(I, badRange());
191      break;
192
193    case Instruction::UIToFP: {
194      // Path terminated cleanly.
195      unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
196      APInt Min = APInt::getMinValue(BW).zextOrSelf(MaxIntegerBW+1);
197      APInt Max = APInt::getMaxValue(BW).zextOrSelf(MaxIntegerBW+1);
198      seen(I, validateRange(ConstantRange(Min, Max)));
199      continue;
200    }
201
202    case Instruction::SIToFP: {
203      // Path terminated cleanly.
204      unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
205      APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(MaxIntegerBW+1);
206      APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(MaxIntegerBW+1);
207      seen(I, validateRange(ConstantRange(SMin, SMax)));
208      continue;
209    }
210
211    case Instruction::FAdd:
212    case Instruction::FSub:
213    case Instruction::FMul:
214    case Instruction::FPToUI:
215    case Instruction::FPToSI:
216    case Instruction::FCmp:
217      seen(I, unknownRange());
218      break;
219    }
220
221    for (Value *O : I->operands()) {
222      if (Instruction *OI = dyn_cast<Instruction>(O)) {
223        // Unify def-use chains if they interfere.
224        ECs.unionSets(I, OI);
225        if (SeenInsts.find(I)->second != badRange())
226          Worklist.push_back(OI);
227      } else if (!isa<ConstantFP>(O)) {
228        // Not an instruction or ConstantFP? we can't do anything.
229        seen(I, badRange());
230      }
231    }
232  }
233}
234
235// Walk forwards down the list of seen instructions, so we visit defs before
236// uses.
237void Float2IntPass::walkForwards() {
238  for (auto &It : reverse(SeenInsts)) {
239    if (It.second != unknownRange())
240      continue;
241
242    Instruction *I = It.first;
243    std::function<ConstantRange(ArrayRef<ConstantRange>)> Op;
244    switch (I->getOpcode()) {
245      // FIXME: Handle select and phi nodes.
246    default:
247    case Instruction::UIToFP:
248    case Instruction::SIToFP:
249      llvm_unreachable("Should have been handled in walkForwards!");
250
251    case Instruction::FAdd:
252      Op = [](ArrayRef<ConstantRange> Ops) {
253        assert(Ops.size() == 2 && "FAdd is a binary operator!");
254        return Ops[0].add(Ops[1]);
255      };
256      break;
257
258    case Instruction::FSub:
259      Op = [](ArrayRef<ConstantRange> Ops) {
260        assert(Ops.size() == 2 && "FSub is a binary operator!");
261        return Ops[0].sub(Ops[1]);
262      };
263      break;
264
265    case Instruction::FMul:
266      Op = [](ArrayRef<ConstantRange> Ops) {
267        assert(Ops.size() == 2 && "FMul is a binary operator!");
268        return Ops[0].multiply(Ops[1]);
269      };
270      break;
271
272    //
273    // Root-only instructions - we'll only see these if they're the
274    //                          first node in a walk.
275    //
276    case Instruction::FPToUI:
277    case Instruction::FPToSI:
278      Op = [](ArrayRef<ConstantRange> Ops) {
279        assert(Ops.size() == 1 && "FPTo[US]I is a unary operator!");
280        return Ops[0];
281      };
282      break;
283
284    case Instruction::FCmp:
285      Op = [](ArrayRef<ConstantRange> Ops) {
286        assert(Ops.size() == 2 && "FCmp is a binary operator!");
287        return Ops[0].unionWith(Ops[1]);
288      };
289      break;
290    }
291
292    bool Abort = false;
293    SmallVector<ConstantRange,4> OpRanges;
294    for (Value *O : I->operands()) {
295      if (Instruction *OI = dyn_cast<Instruction>(O)) {
296        assert(SeenInsts.find(OI) != SeenInsts.end() &&
297               "def not seen before use!");
298        OpRanges.push_back(SeenInsts.find(OI)->second);
299      } else if (ConstantFP *CF = dyn_cast<ConstantFP>(O)) {
300        // Work out if the floating point number can be losslessly represented
301        // as an integer.
302        // APFloat::convertToInteger(&Exact) purports to do what we want, but
303        // the exactness can be too precise. For example, negative zero can
304        // never be exactly converted to an integer.
305        //
306        // Instead, we ask APFloat to round itself to an integral value - this
307        // preserves sign-of-zero - then compare the result with the original.
308        //
309        const APFloat &F = CF->getValueAPF();
310
311        // First, weed out obviously incorrect values. Non-finite numbers
312        // can't be represented and neither can negative zero, unless
313        // we're in fast math mode.
314        if (!F.isFinite() ||
315            (F.isZero() && F.isNegative() && isa<FPMathOperator>(I) &&
316             !I->hasNoSignedZeros())) {
317          seen(I, badRange());
318          Abort = true;
319          break;
320        }
321
322        APFloat NewF = F;
323        auto Res = NewF.roundToIntegral(APFloat::rmNearestTiesToEven);
324        if (Res != APFloat::opOK || NewF.compare(F) != APFloat::cmpEqual) {
325          seen(I, badRange());
326          Abort = true;
327          break;
328        }
329        // OK, it's representable. Now get it.
330        APSInt Int(MaxIntegerBW+1, false);
331        bool Exact;
332        CF->getValueAPF().convertToInteger(Int,
333                                           APFloat::rmNearestTiesToEven,
334                                           &Exact);
335        OpRanges.push_back(ConstantRange(Int));
336      } else {
337        llvm_unreachable("Should have already marked this as badRange!");
338      }
339    }
340
341    // Reduce the operands' ranges to a single range and return.
342    if (!Abort)
343      seen(I, Op(OpRanges));
344  }
345}
346
347// If there is a valid transform to be done, do it.
348bool Float2IntPass::validateAndTransform() {
349  bool MadeChange = false;
350
351  // Iterate over every disjoint partition of the def-use graph.
352  for (auto It = ECs.begin(), E = ECs.end(); It != E; ++It) {
353    ConstantRange R(MaxIntegerBW + 1, false);
354    bool Fail = false;
355    Type *ConvertedToTy = nullptr;
356
357    // For every member of the partition, union all the ranges together.
358    for (auto MI = ECs.member_begin(It), ME = ECs.member_end();
359         MI != ME; ++MI) {
360      Instruction *I = *MI;
361      auto SeenI = SeenInsts.find(I);
362      if (SeenI == SeenInsts.end())
363        continue;
364
365      R = R.unionWith(SeenI->second);
366      // We need to ensure I has no users that have not been seen.
367      // If it does, transformation would be illegal.
368      //
369      // Don't count the roots, as they terminate the graphs.
370      if (Roots.count(I) == 0) {
371        // Set the type of the conversion while we're here.
372        if (!ConvertedToTy)
373          ConvertedToTy = I->getType();
374        for (User *U : I->users()) {
375          Instruction *UI = dyn_cast<Instruction>(U);
376          if (!UI || SeenInsts.find(UI) == SeenInsts.end()) {
377            DEBUG(dbgs() << "F2I: Failing because of " << *U << "\n");
378            Fail = true;
379            break;
380          }
381        }
382      }
383      if (Fail)
384        break;
385    }
386
387    // If the set was empty, or we failed, or the range is poisonous,
388    // bail out.
389    if (ECs.member_begin(It) == ECs.member_end() || Fail ||
390        R.isFullSet() || R.isSignWrappedSet())
391      continue;
392    assert(ConvertedToTy && "Must have set the convertedtoty by this point!");
393
394    // The number of bits required is the maximum of the upper and
395    // lower limits, plus one so it can be signed.
396    unsigned MinBW = std::max(R.getLower().getMinSignedBits(),
397                              R.getUpper().getMinSignedBits()) + 1;
398    DEBUG(dbgs() << "F2I: MinBitwidth=" << MinBW << ", R: " << R << "\n");
399
400    // If we've run off the realms of the exactly representable integers,
401    // the floating point result will differ from an integer approximation.
402
403    // Do we need more bits than are in the mantissa of the type we converted
404    // to? semanticsPrecision returns the number of mantissa bits plus one
405    // for the sign bit.
406    unsigned MaxRepresentableBits
407      = APFloat::semanticsPrecision(ConvertedToTy->getFltSemantics()) - 1;
408    if (MinBW > MaxRepresentableBits) {
409      DEBUG(dbgs() << "F2I: Value not guaranteed to be representable!\n");
410      continue;
411    }
412    if (MinBW > 64) {
413      DEBUG(dbgs() << "F2I: Value requires more than 64 bits to represent!\n");
414      continue;
415    }
416
417    // OK, R is known to be representable. Now pick a type for it.
418    // FIXME: Pick the smallest legal type that will fit.
419    Type *Ty = (MinBW > 32) ? Type::getInt64Ty(*Ctx) : Type::getInt32Ty(*Ctx);
420
421    for (auto MI = ECs.member_begin(It), ME = ECs.member_end();
422         MI != ME; ++MI)
423      convert(*MI, Ty);
424    MadeChange = true;
425  }
426
427  return MadeChange;
428}
429
430Value *Float2IntPass::convert(Instruction *I, Type *ToTy) {
431  if (ConvertedInsts.find(I) != ConvertedInsts.end())
432    // Already converted this instruction.
433    return ConvertedInsts[I];
434
435  SmallVector<Value*,4> NewOperands;
436  for (Value *V : I->operands()) {
437    // Don't recurse if we're an instruction that terminates the path.
438    if (I->getOpcode() == Instruction::UIToFP ||
439        I->getOpcode() == Instruction::SIToFP) {
440      NewOperands.push_back(V);
441    } else if (Instruction *VI = dyn_cast<Instruction>(V)) {
442      NewOperands.push_back(convert(VI, ToTy));
443    } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
444      APSInt Val(ToTy->getPrimitiveSizeInBits(), /*IsUnsigned=*/false);
445      bool Exact;
446      CF->getValueAPF().convertToInteger(Val,
447                                         APFloat::rmNearestTiesToEven,
448                                         &Exact);
449      NewOperands.push_back(ConstantInt::get(ToTy, Val));
450    } else {
451      llvm_unreachable("Unhandled operand type?");
452    }
453  }
454
455  // Now create a new instruction.
456  IRBuilder<> IRB(I);
457  Value *NewV = nullptr;
458  switch (I->getOpcode()) {
459  default: llvm_unreachable("Unhandled instruction!");
460
461  case Instruction::FPToUI:
462    NewV = IRB.CreateZExtOrTrunc(NewOperands[0], I->getType());
463    break;
464
465  case Instruction::FPToSI:
466    NewV = IRB.CreateSExtOrTrunc(NewOperands[0], I->getType());
467    break;
468
469  case Instruction::FCmp: {
470    CmpInst::Predicate P = mapFCmpPred(cast<CmpInst>(I)->getPredicate());
471    assert(P != CmpInst::BAD_ICMP_PREDICATE && "Unhandled predicate!");
472    NewV = IRB.CreateICmp(P, NewOperands[0], NewOperands[1], I->getName());
473    break;
474  }
475
476  case Instruction::UIToFP:
477    NewV = IRB.CreateZExtOrTrunc(NewOperands[0], ToTy);
478    break;
479
480  case Instruction::SIToFP:
481    NewV = IRB.CreateSExtOrTrunc(NewOperands[0], ToTy);
482    break;
483
484  case Instruction::FAdd:
485  case Instruction::FSub:
486  case Instruction::FMul:
487    NewV = IRB.CreateBinOp(mapBinOpcode(I->getOpcode()),
488                           NewOperands[0], NewOperands[1],
489                           I->getName());
490    break;
491  }
492
493  // If we're a root instruction, RAUW.
494  if (Roots.count(I))
495    I->replaceAllUsesWith(NewV);
496
497  ConvertedInsts[I] = NewV;
498  return NewV;
499}
500
501// Perform dead code elimination on the instructions we just modified.
502void Float2IntPass::cleanup() {
503  for (auto &I : reverse(ConvertedInsts))
504    I.first->eraseFromParent();
505}
506
507bool Float2IntPass::runImpl(Function &F) {
508  DEBUG(dbgs() << "F2I: Looking at function " << F.getName() << "\n");
509  // Clear out all state.
510  ECs = EquivalenceClasses<Instruction*>();
511  SeenInsts.clear();
512  ConvertedInsts.clear();
513  Roots.clear();
514
515  Ctx = &F.getParent()->getContext();
516
517  findRoots(F, Roots);
518
519  walkBackwards(Roots);
520  walkForwards();
521
522  bool Modified = validateAndTransform();
523  if (Modified)
524    cleanup();
525  return Modified;
526}
527
528namespace llvm {
529FunctionPass *createFloat2IntPass() { return new Float2IntLegacyPass(); }
530
531PreservedAnalyses Float2IntPass::run(Function &F, FunctionAnalysisManager &) {
532  if (!runImpl(F))
533    return PreservedAnalyses::all();
534  else {
535    // FIXME: This should also 'preserve the CFG'.
536    PreservedAnalyses PA;
537    PA.preserve<GlobalsAA>();
538    return PA;
539  }
540}
541} // End namespace llvm
542