contrib/llvm/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
  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
  34 using 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.
  48 static cl::opt<unsigned>
  49 MaxIntegerBW("float2int-max-integer-bw", cl::init(64), cl::Hidden,
  50              cl::desc("Max integer bitwidth to consider in float2int"
  51                       "(default=64)"));
  52
  53 namespace {
  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
  77 char Float2IntLegacyPass::ID = 0;
  78 INITIALIZE_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.
  82 static 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.
 109 static 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.
 120 void 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.
 140 void Float2IntPass::seen(Instruction *I, ConstantRange R) {
 141   LLVM_DEBUG(dbgs() << "F2I: " << *I << ":" << R << "\n");
 142   auto IT = SeenInsts.find(I);
 143   if (IT != SeenInsts.end())
 144     IT->second = std::move(R);
 145   else
 146     SeenInsts.insert(std::make_pair(I, std::move(R)));
 147 }
 148
 149 // Helper - get a range representing a poison value.
 150 ConstantRange Float2IntPass::badRange() {
 151   return ConstantRange(MaxIntegerBW + 1, true);
 152 }
 153 ConstantRange Float2IntPass::unknownRange() {
 154   return ConstantRange(MaxIntegerBW + 1, false);
 155 }
 156 ConstantRange 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.
 176 void 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     case Instruction::SIToFP: {
 195       // Path terminated cleanly - use the type of the integer input to seed
 196       // the analysis.
 197       unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
 198       auto Input = ConstantRange(BW, true);
 199       auto CastOp = (Instruction::CastOps)I->getOpcode();
 200       seen(I, validateRange(Input.castOp(CastOp, MaxIntegerBW+1)));
 201       continue;
 202     }
 203
 204     case Instruction::FAdd:
 205     case Instruction::FSub:
 206     case Instruction::FMul:
 207     case Instruction::FPToUI:
 208     case Instruction::FPToSI:
 209     case Instruction::FCmp:
 210       seen(I, unknownRange());
 211       break;
 212     }
 213
 214     for (Value *O : I->operands()) {
 215       if (Instruction *OI = dyn_cast<Instruction>(O)) {
 216         // Unify def-use chains if they interfere.
 217         ECs.unionSets(I, OI);
 218         if (SeenInsts.find(I)->second != badRange())
 219           Worklist.push_back(OI);
 220       } else if (!isa<ConstantFP>(O)) {
 221         // Not an instruction or ConstantFP? we can't do anything.
 222         seen(I, badRange());
 223       }
 224     }
 225   }
 226 }
 227
 228 // Walk forwards down the list of seen instructions, so we visit defs before
 229 // uses.
 230 void Float2IntPass::walkForwards() {
 231   for (auto &It : reverse(SeenInsts)) {
 232     if (It.second != unknownRange())
 233       continue;
 234
 235     Instruction *I = It.first;
 236     std::function<ConstantRange(ArrayRef<ConstantRange>)> Op;
 237     switch (I->getOpcode()) {
 238       // FIXME: Handle select and phi nodes.
 239     default:
 240     case Instruction::UIToFP:
 241     case Instruction::SIToFP:
 242       llvm_unreachable("Should have been handled in walkForwards!");
 243
 244     case Instruction::FAdd:
 245     case Instruction::FSub:
 246     case Instruction::FMul:
 247       Op = [I](ArrayRef<ConstantRange> Ops) {
 248         assert(Ops.size() == 2 && "its a binary operator!");
 249         auto BinOp = (Instruction::BinaryOps) I->getOpcode();
 250         return Ops[0].binaryOp(BinOp, Ops[1]);
 251       };
 252       break;
 253
 254     //
 255     // Root-only instructions - we'll only see these if they're the
 256     //                          first node in a walk.
 257     //
 258     case Instruction::FPToUI:
 259     case Instruction::FPToSI:
 260       Op = [I](ArrayRef<ConstantRange> Ops) {
 261         assert(Ops.size() == 1 && "FPTo[US]I is a unary operator!");
 262         // Note: We're ignoring the casts output size here as that's what the
 263         // caller expects.
 264         auto CastOp = (Instruction::CastOps)I->getOpcode();
 265         return Ops[0].castOp(CastOp, MaxIntegerBW+1);
 266       };
 267       break;
 268
 269     case Instruction::FCmp:
 270       Op = [](ArrayRef<ConstantRange> Ops) {
 271         assert(Ops.size() == 2 && "FCmp is a binary operator!");
 272         return Ops[0].unionWith(Ops[1]);
 273       };
 274       break;
 275     }
 276
 277     bool Abort = false;
 278     SmallVector<ConstantRange,4> OpRanges;
 279     for (Value *O : I->operands()) {
 280       if (Instruction *OI = dyn_cast<Instruction>(O)) {
 281         assert(SeenInsts.find(OI) != SeenInsts.end() &&
 282                "def not seen before use!");
 283         OpRanges.push_back(SeenInsts.find(OI)->second);
 284       } else if (ConstantFP *CF = dyn_cast<ConstantFP>(O)) {
 285         // Work out if the floating point number can be losslessly represented
 286         // as an integer.
 287         // APFloat::convertToInteger(&Exact) purports to do what we want, but
 288         // the exactness can be too precise. For example, negative zero can
 289         // never be exactly converted to an integer.
 290         //
 291         // Instead, we ask APFloat to round itself to an integral value - this
 292         // preserves sign-of-zero - then compare the result with the original.
 293         //
 294         const APFloat &F = CF->getValueAPF();
 295
 296         // First, weed out obviously incorrect values. Non-finite numbers
 297         // can't be represented and neither can negative zero, unless
 298         // we're in fast math mode.
 299         if (!F.isFinite() ||
 300             (F.isZero() && F.isNegative() && isa<FPMathOperator>(I) &&
 301              !I->hasNoSignedZeros())) {
 302           seen(I, badRange());
 303           Abort = true;
 304           break;
 305         }
 306
 307         APFloat NewF = F;
 308         auto Res = NewF.roundToIntegral(APFloat::rmNearestTiesToEven);
 309         if (Res != APFloat::opOK || NewF.compare(F) != APFloat::cmpEqual) {
 310           seen(I, badRange());
 311           Abort = true;
 312           break;
 313         }
 314         // OK, it's representable. Now get it.
 315         APSInt Int(MaxIntegerBW+1, false);
 316         bool Exact;
 317         CF->getValueAPF().convertToInteger(Int,
 318                                            APFloat::rmNearestTiesToEven,
 319                                            &Exact);
 320         OpRanges.push_back(ConstantRange(Int));
 321       } else {
 322         llvm_unreachable("Should have already marked this as badRange!");
 323       }
 324     }
 325
 326     // Reduce the operands' ranges to a single range and return.
 327     if (!Abort)
 328       seen(I, Op(OpRanges));
 329   }
 330 }
 331
 332 // If there is a valid transform to be done, do it.
 333 bool Float2IntPass::validateAndTransform() {
 334   bool MadeChange = false;
 335
 336   // Iterate over every disjoint partition of the def-use graph.
 337   for (auto It = ECs.begin(), E = ECs.end(); It != E; ++It) {
 338     ConstantRange R(MaxIntegerBW + 1, false);
 339     bool Fail = false;
 340     Type *ConvertedToTy = nullptr;
 341
 342     // For every member of the partition, union all the ranges together.
 343     for (auto MI = ECs.member_begin(It), ME = ECs.member_end();
 344          MI != ME; ++MI) {
 345       Instruction *I = *MI;
 346       auto SeenI = SeenInsts.find(I);
 347       if (SeenI == SeenInsts.end())
 348         continue;
 349
 350       R = R.unionWith(SeenI->second);
 351       // We need to ensure I has no users that have not been seen.
 352       // If it does, transformation would be illegal.
 353       //
 354       // Don't count the roots, as they terminate the graphs.
 355       if (Roots.count(I) == 0) {
 356         // Set the type of the conversion while we're here.
 357         if (!ConvertedToTy)
 358           ConvertedToTy = I->getType();
 359         for (User *U : I->users()) {
 360           Instruction *UI = dyn_cast<Instruction>(U);
 361           if (!UI || SeenInsts.find(UI) == SeenInsts.end()) {
 362             LLVM_DEBUG(dbgs() << "F2I: Failing because of " << *U << "\n");
 363             Fail = true;
 364             break;
 365           }
 366         }
 367       }
 368       if (Fail)
 369         break;
 370     }
 371
 372     // If the set was empty, or we failed, or the range is poisonous,
 373     // bail out.
 374     if (ECs.member_begin(It) == ECs.member_end() || Fail ||
 375         R.isFullSet() || R.isSignWrappedSet())
 376       continue;
 377     assert(ConvertedToTy && "Must have set the convertedtoty by this point!");
 378
 379     // The number of bits required is the maximum of the upper and
 380     // lower limits, plus one so it can be signed.
 381     unsigned MinBW = std::max(R.getLower().getMinSignedBits(),
 382                               R.getUpper().getMinSignedBits()) + 1;
 383     LLVM_DEBUG(dbgs() << "F2I: MinBitwidth=" << MinBW << ", R: " << R << "\n");
 384
 385     // If we've run off the realms of the exactly representable integers,
 386     // the floating point result will differ from an integer approximation.
 387
 388     // Do we need more bits than are in the mantissa of the type we converted
 389     // to? semanticsPrecision returns the number of mantissa bits plus one
 390     // for the sign bit.
 391     unsigned MaxRepresentableBits
 392       = APFloat::semanticsPrecision(ConvertedToTy->getFltSemantics()) - 1;
 393     if (MinBW > MaxRepresentableBits) {
 394       LLVM_DEBUG(dbgs() << "F2I: Value not guaranteed to be representable!\n");
 395       continue;
 396     }
 397     if (MinBW > 64) {
 398       LLVM_DEBUG(
 399           dbgs() << "F2I: Value requires more than 64 bits to represent!\n");
 400       continue;
 401     }
 402
 403     // OK, R is known to be representable. Now pick a type for it.
 404     // FIXME: Pick the smallest legal type that will fit.
 405     Type *Ty = (MinBW > 32) ? Type::getInt64Ty(*Ctx) : Type::getInt32Ty(*Ctx);
 406
 407     for (auto MI = ECs.member_begin(It), ME = ECs.member_end();
 408          MI != ME; ++MI)
 409       convert(*MI, Ty);
 410     MadeChange = true;
 411   }
 412
 413   return MadeChange;
 414 }
 415
 416 Value *Float2IntPass::convert(Instruction *I, Type *ToTy) {
 417   if (ConvertedInsts.find(I) != ConvertedInsts.end())
 418     // Already converted this instruction.
 419     return ConvertedInsts[I];
 420
 421   SmallVector<Value*,4> NewOperands;
 422   for (Value *V : I->operands()) {
 423     // Don't recurse if we're an instruction that terminates the path.
 424     if (I->getOpcode() == Instruction::UIToFP ||
 425         I->getOpcode() == Instruction::SIToFP) {
 426       NewOperands.push_back(V);
 427     } else if (Instruction *VI = dyn_cast<Instruction>(V)) {
 428       NewOperands.push_back(convert(VI, ToTy));
 429     } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
 430       APSInt Val(ToTy->getPrimitiveSizeInBits(), /*IsUnsigned=*/false);
 431       bool Exact;
 432       CF->getValueAPF().convertToInteger(Val,
 433                                          APFloat::rmNearestTiesToEven,
 434                                          &Exact);
 435       NewOperands.push_back(ConstantInt::get(ToTy, Val));
 436     } else {
 437       llvm_unreachable("Unhandled operand type?");
 438     }
 439   }
 440
 441   // Now create a new instruction.
 442   IRBuilder<> IRB(I);
 443   Value *NewV = nullptr;
 444   switch (I->getOpcode()) {
 445   default: llvm_unreachable("Unhandled instruction!");
 446
 447   case Instruction::FPToUI:
 448     NewV = IRB.CreateZExtOrTrunc(NewOperands[0], I->getType());
 449     break;
 450
 451   case Instruction::FPToSI:
 452     NewV = IRB.CreateSExtOrTrunc(NewOperands[0], I->getType());
 453     break;
 454
 455   case Instruction::FCmp: {
 456     CmpInst::Predicate P = mapFCmpPred(cast<CmpInst>(I)->getPredicate());
 457     assert(P != CmpInst::BAD_ICMP_PREDICATE && "Unhandled predicate!");
 458     NewV = IRB.CreateICmp(P, NewOperands[0], NewOperands[1], I->getName());
 459     break;
 460   }
 461
 462   case Instruction::UIToFP:
 463     NewV = IRB.CreateZExtOrTrunc(NewOperands[0], ToTy);
 464     break;
 465
 466   case Instruction::SIToFP:
 467     NewV = IRB.CreateSExtOrTrunc(NewOperands[0], ToTy);
 468     break;
 469
 470   case Instruction::FAdd:
 471   case Instruction::FSub:
 472   case Instruction::FMul:
 473     NewV = IRB.CreateBinOp(mapBinOpcode(I->getOpcode()),
 474                            NewOperands[0], NewOperands[1],
 475                            I->getName());
 476     break;
 477   }
 478
 479   // If we're a root instruction, RAUW.
 480   if (Roots.count(I))
 481     I->replaceAllUsesWith(NewV);
 482
 483   ConvertedInsts[I] = NewV;
 484   return NewV;
 485 }
 486
 487 // Perform dead code elimination on the instructions we just modified.
 488 void Float2IntPass::cleanup() {
 489   for (auto &I : reverse(ConvertedInsts))
 490     I.first->eraseFromParent();
 491 }
 492
 493 bool Float2IntPass::runImpl(Function &F) {
 494   LLVM_DEBUG(dbgs() << "F2I: Looking at function " << F.getName() << "\n");
 495   // Clear out all state.
 496   ECs = EquivalenceClasses<Instruction*>();
 497   SeenInsts.clear();
 498   ConvertedInsts.clear();
 499   Roots.clear();
 500
 501   Ctx = &F.getParent()->getContext();
 502
 503   findRoots(F, Roots);
 504
 505   walkBackwards(Roots);
 506   walkForwards();
 507
 508   bool Modified = validateAndTransform();
 509   if (Modified)
 510     cleanup();
 511   return Modified;
 512 }
 513
 514 namespace llvm {
 515 FunctionPass *createFloat2IntPass() { return new Float2IntLegacyPass(); }
 516
 517 PreservedAnalyses Float2IntPass::run(Function &F, FunctionAnalysisManager &) {
 518   if (!runImpl(F))
 519     return PreservedAnalyses::all();
 520
 521   PreservedAnalyses PA;
 522   PA.preserveSet<CFGAnalyses>();
 523   PA.preserve<GlobalsAA>();
 524   return PA;
 525 }
 526 } // End namespace llvm