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 #define DEBUG_TYPE "float2int" 17 18 #include "llvm/Transforms/Scalar/Float2Int.h" 19 #include "llvm/ADT/APInt.h" 20 #include "llvm/ADT/APSInt.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/Analysis/AliasAnalysis.h" 23 #include "llvm/Analysis/GlobalsModRef.h" 24 #include "llvm/IR/Constants.h" 25 #include "llvm/IR/IRBuilder.h" 26 #include "llvm/IR/InstIterator.h" 27 #include "llvm/IR/Instructions.h" 28 #include "llvm/IR/Module.h" 29 #include "llvm/Pass.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/raw_ostream.h" 32 #include "llvm/Transforms/Scalar.h" 33 #include <deque> 34 #include <functional> // For std::function 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 SmallPtrSet<Instruction*,8> &Roots) { 125 for (BasicBlock &BB : F) { 126 // Unreachable code can take on strange forms that we are not prepared to 127 // handle. For example, an instruction may have itself as an operand. 128 if (!DT.isReachableFromEntry(&BB)) 129 continue; 130 131 for (Instruction &I : BB) { 132 if (isa<VectorType>(I.getType())) 133 continue; 134 switch (I.getOpcode()) { 135 default: break; 136 case Instruction::FPToUI: 137 case Instruction::FPToSI: 138 Roots.insert(&I); 139 break; 140 case Instruction::FCmp: 141 if (mapFCmpPred(cast<CmpInst>(&I)->getPredicate()) != 142 CmpInst::BAD_ICMP_PREDICATE) 143 Roots.insert(&I); 144 break; 145 } 146 } 147 } 148 } 149 150 // Helper - mark I as having been traversed, having range R. 151 void Float2IntPass::seen(Instruction *I, ConstantRange R) { 152 LLVM_DEBUG(dbgs() << "F2I: " << *I << ":" << R << "\n"); 153 auto IT = SeenInsts.find(I); 154 if (IT != SeenInsts.end()) 155 IT->second = std::move(R); 156 else 157 SeenInsts.insert(std::make_pair(I, std::move(R))); 158 } 159 160 // Helper - get a range representing a poison value. 161 ConstantRange Float2IntPass::badRange() { 162 return ConstantRange::getFull(MaxIntegerBW + 1); 163 } 164 ConstantRange Float2IntPass::unknownRange() { 165 return ConstantRange::getEmpty(MaxIntegerBW + 1); 166 } 167 ConstantRange Float2IntPass::validateRange(ConstantRange R) { 168 if (R.getBitWidth() > MaxIntegerBW + 1) 169 return badRange(); 170 return R; 171 } 172 173 // The most obvious way to structure the search is a depth-first, eager 174 // search from each root. However, that require direct recursion and so 175 // can only handle small instruction sequences. Instead, we split the search 176 // up into two phases: 177 // - walkBackwards: A breadth-first walk of the use-def graph starting from 178 // the roots. Populate "SeenInsts" with interesting 179 // instructions and poison values if they're obvious and 180 // cheap to compute. Calculate the equivalance set structure 181 // while we're here too. 182 // - walkForwards: Iterate over SeenInsts in reverse order, so we visit 183 // defs before their uses. Calculate the real range info. 184 185 // Breadth-first walk of the use-def graph; determine the set of nodes 186 // we care about and eagerly determine if some of them are poisonous. 187 void Float2IntPass::walkBackwards(const SmallPtrSetImpl<Instruction*> &Roots) { 188 std::deque<Instruction*> Worklist(Roots.begin(), Roots.end()); 189 while (!Worklist.empty()) { 190 Instruction *I = Worklist.back(); 191 Worklist.pop_back(); 192 193 if (SeenInsts.find(I) != SeenInsts.end()) 194 // Seen already. 195 continue; 196 197 switch (I->getOpcode()) { 198 // FIXME: Handle select and phi nodes. 199 default: 200 // Path terminated uncleanly. 201 seen(I, badRange()); 202 break; 203 204 case Instruction::UIToFP: 205 case Instruction::SIToFP: { 206 // Path terminated cleanly - use the type of the integer input to seed 207 // the analysis. 208 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits(); 209 auto Input = ConstantRange::getFull(BW); 210 auto CastOp = (Instruction::CastOps)I->getOpcode(); 211 seen(I, validateRange(Input.castOp(CastOp, MaxIntegerBW+1))); 212 continue; 213 } 214 215 case Instruction::FNeg: 216 case Instruction::FAdd: 217 case Instruction::FSub: 218 case Instruction::FMul: 219 case Instruction::FPToUI: 220 case Instruction::FPToSI: 221 case Instruction::FCmp: 222 seen(I, unknownRange()); 223 break; 224 } 225 226 for (Value *O : I->operands()) { 227 if (Instruction *OI = dyn_cast<Instruction>(O)) { 228 // Unify def-use chains if they interfere. 229 ECs.unionSets(I, OI); 230 if (SeenInsts.find(I)->second != badRange()) 231 Worklist.push_back(OI); 232 } else if (!isa<ConstantFP>(O)) { 233 // Not an instruction or ConstantFP? we can't do anything. 234 seen(I, badRange()); 235 } 236 } 237 } 238 } 239 240 // Walk forwards down the list of seen instructions, so we visit defs before 241 // uses. 242 void Float2IntPass::walkForwards() { 243 for (auto &It : reverse(SeenInsts)) { 244 if (It.second != unknownRange()) 245 continue; 246 247 Instruction *I = It.first; 248 std::function<ConstantRange(ArrayRef<ConstantRange>)> Op; 249 switch (I->getOpcode()) { 250 // FIXME: Handle select and phi nodes. 251 default: 252 case Instruction::UIToFP: 253 case Instruction::SIToFP: 254 llvm_unreachable("Should have been handled in walkForwards!"); 255 256 case Instruction::FNeg: 257 Op = [](ArrayRef<ConstantRange> Ops) { 258 assert(Ops.size() == 1 && "FNeg is a unary operator!"); 259 unsigned Size = Ops[0].getBitWidth(); 260 auto Zero = ConstantRange(APInt::getNullValue(Size)); 261 return Zero.sub(Ops[0]); 262 }; 263 break; 264 265 case Instruction::FAdd: 266 case Instruction::FSub: 267 case Instruction::FMul: 268 Op = [I](ArrayRef<ConstantRange> Ops) { 269 assert(Ops.size() == 2 && "its a binary operator!"); 270 auto BinOp = (Instruction::BinaryOps) I->getOpcode(); 271 return Ops[0].binaryOp(BinOp, Ops[1]); 272 }; 273 break; 274 275 // 276 // Root-only instructions - we'll only see these if they're the 277 // first node in a walk. 278 // 279 case Instruction::FPToUI: 280 case Instruction::FPToSI: 281 Op = [I](ArrayRef<ConstantRange> Ops) { 282 assert(Ops.size() == 1 && "FPTo[US]I is a unary operator!"); 283 // Note: We're ignoring the casts output size here as that's what the 284 // caller expects. 285 auto CastOp = (Instruction::CastOps)I->getOpcode(); 286 return Ops[0].castOp(CastOp, MaxIntegerBW+1); 287 }; 288 break; 289 290 case Instruction::FCmp: 291 Op = [](ArrayRef<ConstantRange> Ops) { 292 assert(Ops.size() == 2 && "FCmp is a binary operator!"); 293 return Ops[0].unionWith(Ops[1]); 294 }; 295 break; 296 } 297 298 bool Abort = false; 299 SmallVector<ConstantRange,4> OpRanges; 300 for (Value *O : I->operands()) { 301 if (Instruction *OI = dyn_cast<Instruction>(O)) { 302 assert(SeenInsts.find(OI) != SeenInsts.end() && 303 "def not seen before use!"); 304 OpRanges.push_back(SeenInsts.find(OI)->second); 305 } else if (ConstantFP *CF = dyn_cast<ConstantFP>(O)) { 306 // Work out if the floating point number can be losslessly represented 307 // as an integer. 308 // APFloat::convertToInteger(&Exact) purports to do what we want, but 309 // the exactness can be too precise. For example, negative zero can 310 // never be exactly converted to an integer. 311 // 312 // Instead, we ask APFloat to round itself to an integral value - this 313 // preserves sign-of-zero - then compare the result with the original. 314 // 315 const APFloat &F = CF->getValueAPF(); 316 317 // First, weed out obviously incorrect values. Non-finite numbers 318 // can't be represented and neither can negative zero, unless 319 // we're in fast math mode. 320 if (!F.isFinite() || 321 (F.isZero() && F.isNegative() && isa<FPMathOperator>(I) && 322 !I->hasNoSignedZeros())) { 323 seen(I, badRange()); 324 Abort = true; 325 break; 326 } 327 328 APFloat NewF = F; 329 auto Res = NewF.roundToIntegral(APFloat::rmNearestTiesToEven); 330 if (Res != APFloat::opOK || NewF.compare(F) != APFloat::cmpEqual) { 331 seen(I, badRange()); 332 Abort = true; 333 break; 334 } 335 // OK, it's representable. Now get it. 336 APSInt Int(MaxIntegerBW+1, false); 337 bool Exact; 338 CF->getValueAPF().convertToInteger(Int, 339 APFloat::rmNearestTiesToEven, 340 &Exact); 341 OpRanges.push_back(ConstantRange(Int)); 342 } else { 343 llvm_unreachable("Should have already marked this as badRange!"); 344 } 345 } 346 347 // Reduce the operands' ranges to a single range and return. 348 if (!Abort) 349 seen(I, Op(OpRanges)); 350 } 351 } 352 353 // If there is a valid transform to be done, do it. 354 bool Float2IntPass::validateAndTransform() { 355 bool MadeChange = false; 356 357 // Iterate over every disjoint partition of the def-use graph. 358 for (auto It = ECs.begin(), E = ECs.end(); It != E; ++It) { 359 ConstantRange R(MaxIntegerBW + 1, false); 360 bool Fail = false; 361 Type *ConvertedToTy = nullptr; 362 363 // For every member of the partition, union all the ranges together. 364 for (auto MI = ECs.member_begin(It), ME = ECs.member_end(); 365 MI != ME; ++MI) { 366 Instruction *I = *MI; 367 auto SeenI = SeenInsts.find(I); 368 if (SeenI == SeenInsts.end()) 369 continue; 370 371 R = R.unionWith(SeenI->second); 372 // We need to ensure I has no users that have not been seen. 373 // If it does, transformation would be illegal. 374 // 375 // Don't count the roots, as they terminate the graphs. 376 if (Roots.count(I) == 0) { 377 // Set the type of the conversion while we're here. 378 if (!ConvertedToTy) 379 ConvertedToTy = I->getType(); 380 for (User *U : I->users()) { 381 Instruction *UI = dyn_cast<Instruction>(U); 382 if (!UI || SeenInsts.find(UI) == SeenInsts.end()) { 383 LLVM_DEBUG(dbgs() << "F2I: Failing because of " << *U << "\n"); 384 Fail = true; 385 break; 386 } 387 } 388 } 389 if (Fail) 390 break; 391 } 392 393 // If the set was empty, or we failed, or the range is poisonous, 394 // bail out. 395 if (ECs.member_begin(It) == ECs.member_end() || Fail || 396 R.isFullSet() || R.isSignWrappedSet()) 397 continue; 398 assert(ConvertedToTy && "Must have set the convertedtoty by this point!"); 399 400 // The number of bits required is the maximum of the upper and 401 // lower limits, plus one so it can be signed. 402 unsigned MinBW = std::max(R.getLower().getMinSignedBits(), 403 R.getUpper().getMinSignedBits()) + 1; 404 LLVM_DEBUG(dbgs() << "F2I: MinBitwidth=" << MinBW << ", R: " << R << "\n"); 405 406 // If we've run off the realms of the exactly representable integers, 407 // the floating point result will differ from an integer approximation. 408 409 // Do we need more bits than are in the mantissa of the type we converted 410 // to? semanticsPrecision returns the number of mantissa bits plus one 411 // for the sign bit. 412 unsigned MaxRepresentableBits 413 = APFloat::semanticsPrecision(ConvertedToTy->getFltSemantics()) - 1; 414 if (MinBW > MaxRepresentableBits) { 415 LLVM_DEBUG(dbgs() << "F2I: Value not guaranteed to be representable!\n"); 416 continue; 417 } 418 if (MinBW > 64) { 419 LLVM_DEBUG( 420 dbgs() << "F2I: Value requires more than 64 bits to represent!\n"); 421 continue; 422 } 423 424 // OK, R is known to be representable. Now pick a type for it. 425 // FIXME: Pick the smallest legal type that will fit. 426 Type *Ty = (MinBW > 32) ? Type::getInt64Ty(*Ctx) : Type::getInt32Ty(*Ctx); 427 428 for (auto MI = ECs.member_begin(It), ME = ECs.member_end(); 429 MI != ME; ++MI) 430 convert(*MI, Ty); 431 MadeChange = true; 432 } 433 434 return MadeChange; 435 } 436 437 Value *Float2IntPass::convert(Instruction *I, Type *ToTy) { 438 if (ConvertedInsts.find(I) != ConvertedInsts.end()) 439 // Already converted this instruction. 440 return ConvertedInsts[I]; 441 442 SmallVector<Value*,4> NewOperands; 443 for (Value *V : I->operands()) { 444 // Don't recurse if we're an instruction that terminates the path. 445 if (I->getOpcode() == Instruction::UIToFP || 446 I->getOpcode() == Instruction::SIToFP) { 447 NewOperands.push_back(V); 448 } else if (Instruction *VI = dyn_cast<Instruction>(V)) { 449 NewOperands.push_back(convert(VI, ToTy)); 450 } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) { 451 APSInt Val(ToTy->getPrimitiveSizeInBits(), /*isUnsigned=*/false); 452 bool Exact; 453 CF->getValueAPF().convertToInteger(Val, 454 APFloat::rmNearestTiesToEven, 455 &Exact); 456 NewOperands.push_back(ConstantInt::get(ToTy, Val)); 457 } else { 458 llvm_unreachable("Unhandled operand type?"); 459 } 460 } 461 462 // Now create a new instruction. 463 IRBuilder<> IRB(I); 464 Value *NewV = nullptr; 465 switch (I->getOpcode()) { 466 default: llvm_unreachable("Unhandled instruction!"); 467 468 case Instruction::FPToUI: 469 NewV = IRB.CreateZExtOrTrunc(NewOperands[0], I->getType()); 470 break; 471 472 case Instruction::FPToSI: 473 NewV = IRB.CreateSExtOrTrunc(NewOperands[0], I->getType()); 474 break; 475 476 case Instruction::FCmp: { 477 CmpInst::Predicate P = mapFCmpPred(cast<CmpInst>(I)->getPredicate()); 478 assert(P != CmpInst::BAD_ICMP_PREDICATE && "Unhandled predicate!"); 479 NewV = IRB.CreateICmp(P, NewOperands[0], NewOperands[1], I->getName()); 480 break; 481 } 482 483 case Instruction::UIToFP: 484 NewV = IRB.CreateZExtOrTrunc(NewOperands[0], ToTy); 485 break; 486 487 case Instruction::SIToFP: 488 NewV = IRB.CreateSExtOrTrunc(NewOperands[0], ToTy); 489 break; 490 491 case Instruction::FNeg: 492 NewV = IRB.CreateNeg(NewOperands[0], I->getName()); 493 break; 494 495 case Instruction::FAdd: 496 case Instruction::FSub: 497 case Instruction::FMul: 498 NewV = IRB.CreateBinOp(mapBinOpcode(I->getOpcode()), 499 NewOperands[0], NewOperands[1], 500 I->getName()); 501 break; 502 } 503 504 // If we're a root instruction, RAUW. 505 if (Roots.count(I)) 506 I->replaceAllUsesWith(NewV); 507 508 ConvertedInsts[I] = NewV; 509 return NewV; 510 } 511 512 // Perform dead code elimination on the instructions we just modified. 513 void Float2IntPass::cleanup() { 514 for (auto &I : reverse(ConvertedInsts)) 515 I.first->eraseFromParent(); 516 } 517 518 bool Float2IntPass::runImpl(Function &F, const DominatorTree &DT) { 519 LLVM_DEBUG(dbgs() << "F2I: Looking at function " << F.getName() << "\n"); 520 // Clear out all state. 521 ECs = EquivalenceClasses<Instruction*>(); 522 SeenInsts.clear(); 523 ConvertedInsts.clear(); 524 Roots.clear(); 525 526 Ctx = &F.getParent()->getContext(); 527 528 findRoots(F, DT, Roots); 529 530 walkBackwards(Roots); 531 walkForwards(); 532 533 bool Modified = validateAndTransform(); 534 if (Modified) 535 cleanup(); 536 return Modified; 537 } 538 539 namespace llvm { 540 FunctionPass *createFloat2IntPass() { return new Float2IntLegacyPass(); } 541 542 PreservedAnalyses Float2IntPass::run(Function &F, FunctionAnalysisManager &AM) { 543 const DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F); 544 if (!runImpl(F, DT)) 545 return PreservedAnalyses::all(); 546 547 PreservedAnalyses PA; 548 PA.preserveSet<CFGAnalyses>(); 549 PA.preserve<GlobalsAA>(); 550 return PA; 551 } 552 } // End namespace llvm 553