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 #define DEBUG_TYPE "float2int"
  15
  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/AliasAnalysis.h"
  21 #include "llvm/Analysis/GlobalsModRef.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/IRBuilder.h"
  24 #include "llvm/IR/InstIterator.h"
  25 #include "llvm/IR/Instructions.h"
  26 #include "llvm/IR/Module.h"
  27 #include "llvm/Pass.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/Transforms/Scalar.h"
  31 #include <deque>
  32 #include <functional> // For std::function
  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 Float2IntLegacyPass : public FunctionPass {
  54     static char ID; // Pass identification, replacement for typeid
  55     Float2IntLegacyPass() : FunctionPass(ID) {
  56       initializeFloat2IntLegacyPassPass(*PassRegistry::getPassRegistry());
  57     }
  58
  59     bool runOnFunction(Function &F) override {
  60       if (skipFunction(F))
  61         return false;
  62
  63       const DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  64       return Impl.runImpl(F, DT);
  65     }
  66
  67     void getAnalysisUsage(AnalysisUsage &AU) const override {
  68       AU.setPreservesCFG();
  69       AU.addRequired<DominatorTreeWrapperPass>();
  70       AU.addPreserved<GlobalsAAWrapperPass>();
  71     }
  72
  73   private:
  74     Float2IntPass Impl;
  75   };
  76 }
  77
  78 char Float2IntLegacyPass::ID = 0;
  79 INITIALIZE_PASS(Float2IntLegacyPass, "float2int", "Float to int", false, false)
  80
  81 // Given a FCmp predicate, return a matching ICmp predicate if one
  82 // exists, otherwise return BAD_ICMP_PREDICATE.
  83 static CmpInst::Predicate mapFCmpPred(CmpInst::Predicate P) {
  84   switch (P) {
  85   case CmpInst::FCMP_OEQ:
  86   case CmpInst::FCMP_UEQ:
  87     return CmpInst::ICMP_EQ;
  88   case CmpInst::FCMP_OGT:
  89   case CmpInst::FCMP_UGT:
  90     return CmpInst::ICMP_SGT;
  91   case CmpInst::FCMP_OGE:
  92   case CmpInst::FCMP_UGE:
  93     return CmpInst::ICMP_SGE;
  94   case CmpInst::FCMP_OLT:
  95   case CmpInst::FCMP_ULT:
  96     return CmpInst::ICMP_SLT;
  97   case CmpInst::FCMP_OLE:
  98   case CmpInst::FCMP_ULE:
  99     return CmpInst::ICMP_SLE;
 100   case CmpInst::FCMP_ONE:
 101   case CmpInst::FCMP_UNE:
 102     return CmpInst::ICMP_NE;
 103   default:
 104     return CmpInst::BAD_ICMP_PREDICATE;
 105   }
 106 }
 107
 108 // Given a floating point binary operator, return the matching
 109 // integer version.
 110 static Instruction::BinaryOps mapBinOpcode(unsigned Opcode) {
 111   switch (Opcode) {
 112   default: llvm_unreachable("Unhandled opcode!");
 113   case Instruction::FAdd: return Instruction::Add;
 114   case Instruction::FSub: return Instruction::Sub;
 115   case Instruction::FMul: return Instruction::Mul;
 116   }
 117 }
 118
 119 // Find the roots - instructions that convert from the FP domain to
 120 // integer domain.
 121 void Float2IntPass::findRoots(Function &F, const DominatorTree &DT,
 122                               SmallPtrSet<Instruction*,8> &Roots) {
 123   for (BasicBlock &BB : F) {
 124     // Unreachable code can take on strange forms that we are not prepared to
 125     // handle. For example, an instruction may have itself as an operand.
 126     if (!DT.isReachableFromEntry(&BB))
 127       continue;
 128
 129     for (Instruction &I : BB) {
 130       if (isa<VectorType>(I.getType()))
 131         continue;
 132       switch (I.getOpcode()) {
 133       default: break;
 134       case Instruction::FPToUI:
 135       case Instruction::FPToSI:
 136         Roots.insert(&I);
 137         break;
 138       case Instruction::FCmp:
 139         if (mapFCmpPred(cast<CmpInst>(&I)->getPredicate()) !=
 140             CmpInst::BAD_ICMP_PREDICATE)
 141           Roots.insert(&I);
 142         break;
 143       }
 144     }
 145   }
 146 }
 147
 148 // Helper - mark I as having been traversed, having range R.
 149 void Float2IntPass::seen(Instruction *I, ConstantRange R) {
 150   LLVM_DEBUG(dbgs() << "F2I: " << *I << ":" << R << "\n");
 151   auto IT = SeenInsts.find(I);
 152   if (IT != SeenInsts.end())
 153     IT->second = std::move(R);
 154   else
 155     SeenInsts.insert(std::make_pair(I, std::move(R)));
 156 }
 157
 158 // Helper - get a range representing a poison value.
 159 ConstantRange Float2IntPass::badRange() {
 160   return ConstantRange::getFull(MaxIntegerBW + 1);
 161 }
 162 ConstantRange Float2IntPass::unknownRange() {
 163   return ConstantRange::getEmpty(MaxIntegerBW + 1);
 164 }
 165 ConstantRange Float2IntPass::validateRange(ConstantRange R) {
 166   if (R.getBitWidth() > MaxIntegerBW + 1)
 167     return badRange();
 168   return R;
 169 }
 170
 171 // The most obvious way to structure the search is a depth-first, eager
 172 // search from each root. However, that require direct recursion and so
 173 // can only handle small instruction sequences. Instead, we split the search
 174 // up into two phases:
 175 //   - walkBackwards:  A breadth-first walk of the use-def graph starting from
 176 //                     the roots. Populate "SeenInsts" with interesting
 177 //                     instructions and poison values if they're obvious and
 178 //                     cheap to compute. Calculate the equivalance set structure
 179 //                     while we're here too.
 180 //   - walkForwards:  Iterate over SeenInsts in reverse order, so we visit
 181 //                     defs before their uses. Calculate the real range info.
 182
 183 // Breadth-first walk of the use-def graph; determine the set of nodes
 184 // we care about and eagerly determine if some of them are poisonous.
 185 void Float2IntPass::walkBackwards(const SmallPtrSetImpl<Instruction*> &Roots) {
 186   std::deque<Instruction*> Worklist(Roots.begin(), Roots.end());
 187   while (!Worklist.empty()) {
 188     Instruction *I = Worklist.back();
 189     Worklist.pop_back();
 190
 191     if (SeenInsts.find(I) != SeenInsts.end())
 192       // Seen already.
 193       continue;
 194
 195     switch (I->getOpcode()) {
 196       // FIXME: Handle select and phi nodes.
 197     default:
 198       // Path terminated uncleanly.
 199       seen(I, badRange());
 200       break;
 201
 202     case Instruction::UIToFP:
 203     case Instruction::SIToFP: {
 204       // Path terminated cleanly - use the type of the integer input to seed
 205       // the analysis.
 206       unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
 207       auto Input = ConstantRange::getFull(BW);
 208       auto CastOp = (Instruction::CastOps)I->getOpcode();
 209       seen(I, validateRange(Input.castOp(CastOp, MaxIntegerBW+1)));
 210       continue;
 211     }
 212
 213     case Instruction::FNeg:
 214     case Instruction::FAdd:
 215     case Instruction::FSub:
 216     case Instruction::FMul:
 217     case Instruction::FPToUI:
 218     case Instruction::FPToSI:
 219     case Instruction::FCmp:
 220       seen(I, unknownRange());
 221       break;
 222     }
 223
 224     for (Value *O : I->operands()) {
 225       if (Instruction *OI = dyn_cast<Instruction>(O)) {
 226         // Unify def-use chains if they interfere.
 227         ECs.unionSets(I, OI);
 228         if (SeenInsts.find(I)->second != badRange())
 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       }
 234     }
 235   }
 236 }
 237
 238 // Walk forwards down the list of seen instructions, so we visit defs before
 239 // uses.
 240 void Float2IntPass::walkForwards() {
 241   for (auto &It : reverse(SeenInsts)) {
 242     if (It.second != unknownRange())
 243       continue;
 244
 245     Instruction *I = It.first;
 246     std::function<ConstantRange(ArrayRef<ConstantRange>)> Op;
 247     switch (I->getOpcode()) {
 248       // FIXME: Handle select and phi nodes.
 249     default:
 250     case Instruction::UIToFP:
 251     case Instruction::SIToFP:
 252       llvm_unreachable("Should have been handled in walkForwards!");
 253
 254     case Instruction::FNeg:
 255       Op = [](ArrayRef<ConstantRange> Ops) {
 256         assert(Ops.size() == 1 && "FNeg is a unary operator!");
 257         unsigned Size = Ops[0].getBitWidth();
 258         auto Zero = ConstantRange(APInt::getNullValue(Size));
 259         return Zero.sub(Ops[0]);
 260       };
 261       break;
 262
 263     case Instruction::FAdd:
 264     case Instruction::FSub:
 265     case Instruction::FMul:
 266       Op = [I](ArrayRef<ConstantRange> Ops) {
 267         assert(Ops.size() == 2 && "its a binary operator!");
 268         auto BinOp = (Instruction::BinaryOps) I->getOpcode();
 269         return Ops[0].binaryOp(BinOp, Ops[1]);
 270       };
 271       break;
 272
 273     //
 274     // Root-only instructions - we'll only see these if they're the
 275     //                          first node in a walk.
 276     //
 277     case Instruction::FPToUI:
 278     case Instruction::FPToSI:
 279       Op = [I](ArrayRef<ConstantRange> Ops) {
 280         assert(Ops.size() == 1 && "FPTo[US]I is a unary operator!");
 281         // Note: We're ignoring the casts output size here as that's what the
 282         // caller expects.
 283         auto CastOp = (Instruction::CastOps)I->getOpcode();
 284         return Ops[0].castOp(CastOp, MaxIntegerBW+1);
 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         const 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 Float2IntPass::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       if (SeenI == SeenInsts.end())
 367         continue;
 368
 369       R = R.unionWith(SeenI->second);
 370       // We need to ensure I has no users that have not been seen.
 371       // If it does, transformation would be illegal.
 372       //
 373       // Don't count the roots, as they terminate the graphs.
 374       if (Roots.count(I) == 0) {
 375         // Set the type of the conversion while we're here.
 376         if (!ConvertedToTy)
 377           ConvertedToTy = I->getType();
 378         for (User *U : I->users()) {
 379           Instruction *UI = dyn_cast<Instruction>(U);
 380           if (!UI || SeenInsts.find(UI) == SeenInsts.end()) {
 381             LLVM_DEBUG(dbgs() << "F2I: Failing because of " << *U << "\n");
 382             Fail = true;
 383             break;
 384           }
 385         }
 386       }
 387       if (Fail)
 388         break;
 389     }
 390
 391     // If the set was empty, or we failed, or the range is poisonous,
 392     // bail out.
 393     if (ECs.member_begin(It) == ECs.member_end() || Fail ||
 394         R.isFullSet() || R.isSignWrappedSet())
 395       continue;
 396     assert(ConvertedToTy && "Must have set the convertedtoty by this point!");
 397
 398     // The number of bits required is the maximum of the upper and
 399     // lower limits, plus one so it can be signed.
 400     unsigned MinBW = std::max(R.getLower().getMinSignedBits(),
 401                               R.getUpper().getMinSignedBits()) + 1;
 402     LLVM_DEBUG(dbgs() << "F2I: MinBitwidth=" << MinBW << ", R: " << R << "\n");
 403
 404     // If we've run off the realms of the exactly representable integers,
 405     // the floating point result will differ from an integer approximation.
 406
 407     // Do we need more bits than are in the mantissa of the type we converted
 408     // to? semanticsPrecision returns the number of mantissa bits plus one
 409     // for the sign bit.
 410     unsigned MaxRepresentableBits
 411       = APFloat::semanticsPrecision(ConvertedToTy->getFltSemantics()) - 1;
 412     if (MinBW > MaxRepresentableBits) {
 413       LLVM_DEBUG(dbgs() << "F2I: Value not guaranteed to be representable!\n");
 414       continue;
 415     }
 416     if (MinBW > 64) {
 417       LLVM_DEBUG(
 418           dbgs() << "F2I: Value requires more than 64 bits to represent!\n");
 419       continue;
 420     }
 421
 422     // OK, R is known to be representable. Now pick a type for it.
 423     // FIXME: Pick the smallest legal type that will fit.
 424     Type *Ty = (MinBW > 32) ? Type::getInt64Ty(*Ctx) : Type::getInt32Ty(*Ctx);
 425
 426     for (auto MI = ECs.member_begin(It), ME = ECs.member_end();
 427          MI != ME; ++MI)
 428       convert(*MI, Ty);
 429     MadeChange = true;
 430   }
 431
 432   return MadeChange;
 433 }
 434
 435 Value *Float2IntPass::convert(Instruction *I, Type *ToTy) {
 436   if (ConvertedInsts.find(I) != ConvertedInsts.end())
 437     // Already converted this instruction.
 438     return ConvertedInsts[I];
 439
 440   SmallVector<Value*,4> NewOperands;
 441   for (Value *V : I->operands()) {
 442     // Don't recurse if we're an instruction that terminates the path.
 443     if (I->getOpcode() == Instruction::UIToFP ||
 444         I->getOpcode() == Instruction::SIToFP) {
 445       NewOperands.push_back(V);
 446     } else if (Instruction *VI = dyn_cast<Instruction>(V)) {
 447       NewOperands.push_back(convert(VI, ToTy));
 448     } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
 449       APSInt Val(ToTy->getPrimitiveSizeInBits(), /*isUnsigned=*/false);
 450       bool Exact;
 451       CF->getValueAPF().convertToInteger(Val,
 452                                          APFloat::rmNearestTiesToEven,
 453                                          &Exact);
 454       NewOperands.push_back(ConstantInt::get(ToTy, Val));
 455     } else {
 456       llvm_unreachable("Unhandled operand type?");
 457     }
 458   }
 459
 460   // Now create a new instruction.
 461   IRBuilder<> IRB(I);
 462   Value *NewV = nullptr;
 463   switch (I->getOpcode()) {
 464   default: llvm_unreachable("Unhandled instruction!");
 465
 466   case Instruction::FPToUI:
 467     NewV = IRB.CreateZExtOrTrunc(NewOperands[0], I->getType());
 468     break;
 469
 470   case Instruction::FPToSI:
 471     NewV = IRB.CreateSExtOrTrunc(NewOperands[0], I->getType());
 472     break;
 473
 474   case Instruction::FCmp: {
 475     CmpInst::Predicate P = mapFCmpPred(cast<CmpInst>(I)->getPredicate());
 476     assert(P != CmpInst::BAD_ICMP_PREDICATE && "Unhandled predicate!");
 477     NewV = IRB.CreateICmp(P, NewOperands[0], NewOperands[1], I->getName());
 478     break;
 479   }
 480
 481   case Instruction::UIToFP:
 482     NewV = IRB.CreateZExtOrTrunc(NewOperands[0], ToTy);
 483     break;
 484
 485   case Instruction::SIToFP:
 486     NewV = IRB.CreateSExtOrTrunc(NewOperands[0], ToTy);
 487     break;
 488
 489   case Instruction::FNeg:
 490     NewV = IRB.CreateNeg(NewOperands[0], I->getName());
 491     break;
 492
 493   case Instruction::FAdd:
 494   case Instruction::FSub:
 495   case Instruction::FMul:
 496     NewV = IRB.CreateBinOp(mapBinOpcode(I->getOpcode()),
 497                            NewOperands[0], NewOperands[1],
 498                            I->getName());
 499     break;
 500   }
 501
 502   // If we're a root instruction, RAUW.
 503   if (Roots.count(I))
 504     I->replaceAllUsesWith(NewV);
 505
 506   ConvertedInsts[I] = NewV;
 507   return NewV;
 508 }
 509
 510 // Perform dead code elimination on the instructions we just modified.
 511 void Float2IntPass::cleanup() {
 512   for (auto &I : reverse(ConvertedInsts))
 513     I.first->eraseFromParent();
 514 }
 515
 516 bool Float2IntPass::runImpl(Function &F, const DominatorTree &DT) {
 517   LLVM_DEBUG(dbgs() << "F2I: Looking at function " << F.getName() << "\n");
 518   // Clear out all state.
 519   ECs = EquivalenceClasses<Instruction*>();
 520   SeenInsts.clear();
 521   ConvertedInsts.clear();
 522   Roots.clear();
 523
 524   Ctx = &F.getParent()->getContext();
 525
 526   findRoots(F, DT, Roots);
 527
 528   walkBackwards(Roots);
 529   walkForwards();
 530
 531   bool Modified = validateAndTransform();
 532   if (Modified)
 533     cleanup();
 534   return Modified;
 535 }
 536
 537 namespace llvm {
 538 FunctionPass *createFloat2IntPass() { return new Float2IntLegacyPass(); }
 539
 540 PreservedAnalyses Float2IntPass::run(Function &F, FunctionAnalysisManager &AM) {
 541   const DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
 542   if (!runImpl(F, DT))
 543     return PreservedAnalyses::all();
 544
 545   PreservedAnalyses PA;
 546   PA.preserveSet<CFGAnalyses>();
 547   PA.preserve<GlobalsAA>();
 548   return PA;
 549 }
 550 } // End namespace llvm