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