llvm/lib/Transforms/Scalar/Float2Int.cpp

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