lib/Transforms/Scalar/Float2Int.cpp

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