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