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