516 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the Float2Int pass, which aims to demote floating10// 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 30using namespace llvm;31 32// The algorithm is simple. Start at instructions that convert from the33// float to the int domain: fptoui, fptosi and fcmp. Walk up the def-use34// graph, using an equivalence datastructure to unify graphs that interfere.35//36// Mappable instructions are those with an integer corrollary that, given37// 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 marked40// as non-transformable. If we see an instruction that converts from the41// integer domain to FP domain (uitofp,sitofp), we terminate our walk.42 43/// The largest integer type worth dealing with.44static cl::opt<unsigned>45MaxIntegerBW("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 one50// exists, otherwise return BAD_ICMP_PREDICATE.51static 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 matching77// integer version.78static 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 to88// integer domain.89void 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 to92 // 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.116void 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.122ConstantRange Float2IntPass::badRange() {123 return ConstantRange::getFull(MaxIntegerBW + 1);124}125ConstantRange Float2IntPass::unknownRange() {126 return ConstantRange::getEmpty(MaxIntegerBW + 1);127}128ConstantRange 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, eager135// search from each root. However, that require direct recursion and so136// can only handle small instruction sequences. Instead, we split the search137// up into two phases:138// - walkBackwards: A breadth-first walk of the use-def graph starting from139// the roots. Populate "SeenInsts" with interesting140// instructions and poison values if they're obvious and141// cheap to compute. Calculate the equivalance set structure142// while we're here too.143// - walkForwards: Iterate over SeenInsts in reverse order, so we visit144// defs before their uses. Calculate the real range info.145 146// Breadth-first walk of the use-def graph; determine the set of nodes147// we care about and eagerly determine if some of them are poisonous.148void 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 seed168 // 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.203std::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 represented214 // as an integer.215 // APFloat::convertToInteger(&Exact) purports to do what we want, but216 // the exactness can be too precise. For example, negative zero can217 // never be exactly converted to an integer.218 //219 // Instead, we ask APFloat to round itself to an integral value - this220 // 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 numbers225 // can't be represented and neither can negative zero, unless226 // 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 APFloat::opStatus Status = CF->getValueAPF().convertToInteger(241 Int, APFloat::rmNearestTiesToEven, &Exact);242 // Although the round above is loseless, we still need to check if the243 // floating-point value can be represented in the integer type.244 if (Status == APFloat::opOK || Status == APFloat::opInexact)245 OpRanges.push_back(ConstantRange(Int));246 else247 return badRange();248 } else {249 llvm_unreachable("Should have already marked this as badRange!");250 }251 }252 253 switch (I->getOpcode()) {254 // FIXME: Handle select and phi nodes.255 default:256 case Instruction::UIToFP:257 case Instruction::SIToFP:258 llvm_unreachable("Should have been handled in walkForwards!");259 260 case Instruction::FNeg: {261 assert(OpRanges.size() == 1 && "FNeg is a unary operator!");262 unsigned Size = OpRanges[0].getBitWidth();263 auto Zero = ConstantRange(APInt::getZero(Size));264 return Zero.sub(OpRanges[0]);265 }266 267 case Instruction::FAdd:268 case Instruction::FSub:269 case Instruction::FMul: {270 assert(OpRanges.size() == 2 && "its a binary operator!");271 auto BinOp = (Instruction::BinaryOps) I->getOpcode();272 return OpRanges[0].binaryOp(BinOp, OpRanges[1]);273 }274 275 //276 // Root-only instructions - we'll only see these if they're the277 // first node in a walk.278 //279 case Instruction::FPToUI:280 case Instruction::FPToSI: {281 assert(OpRanges.size() == 1 && "FPTo[US]I is a unary operator!");282 // Note: We're ignoring the casts output size here as that's what the283 // caller expects.284 auto CastOp = (Instruction::CastOps)I->getOpcode();285 return OpRanges[0].castOp(CastOp, MaxIntegerBW+1);286 }287 288 case Instruction::FCmp:289 assert(OpRanges.size() == 2 && "FCmp is a binary operator!");290 return OpRanges[0].unionWith(OpRanges[1]);291 }292}293 294// Walk forwards down the list of seen instructions, so we visit defs before295// uses.296void Float2IntPass::walkForwards() {297 std::deque<Instruction *> Worklist;298 for (const auto &Pair : SeenInsts)299 if (Pair.second == unknownRange())300 Worklist.push_back(Pair.first);301 302 while (!Worklist.empty()) {303 Instruction *I = Worklist.back();304 Worklist.pop_back();305 306 if (std::optional<ConstantRange> Range = calcRange(I))307 seen(I, *Range);308 else309 Worklist.push_front(I); // Reprocess later.310 }311}312 313// If there is a valid transform to be done, do it.314bool Float2IntPass::validateAndTransform(const DataLayout &DL) {315 bool MadeChange = false;316 317 // Iterate over every disjoint partition of the def-use graph.318 for (const auto &E : ECs) {319 if (!E->isLeader())320 continue;321 322 ConstantRange R(MaxIntegerBW + 1, false);323 bool Fail = false;324 Type *ConvertedToTy = nullptr;325 326 // For every member of the partition, union all the ranges together.327 for (Instruction *I : ECs.members(*E)) {328 auto *SeenI = SeenInsts.find(I);329 if (SeenI == SeenInsts.end())330 continue;331 332 R = R.unionWith(SeenI->second);333 // We need to ensure I has no users that have not been seen.334 // If it does, transformation would be illegal.335 //336 // Don't count the roots, as they terminate the graphs.337 if (!Roots.contains(I)) {338 // Set the type of the conversion while we're here.339 if (!ConvertedToTy)340 ConvertedToTy = I->getType();341 for (User *U : I->users()) {342 Instruction *UI = dyn_cast<Instruction>(U);343 if (!UI || !SeenInsts.contains(UI)) {344 LLVM_DEBUG(dbgs() << "F2I: Failing because of " << *U << "\n");345 Fail = true;346 break;347 }348 }349 }350 if (Fail)351 break;352 }353 354 // If the set was empty, or we failed, or the range is poisonous,355 // bail out.356 if (ECs.member_begin(*E) == ECs.member_end() || Fail || R.isFullSet() ||357 R.isSignWrappedSet())358 continue;359 assert(ConvertedToTy && "Must have set the convertedtoty by this point!");360 361 // The number of bits required is the maximum of the upper and362 // lower limits, plus one so it can be signed.363 unsigned MinBW = R.getMinSignedBits() + 1;364 LLVM_DEBUG(dbgs() << "F2I: MinBitwidth=" << MinBW << ", R: " << R << "\n");365 366 // If we've run off the realms of the exactly representable integers,367 // the floating point result will differ from an integer approximation.368 369 // Do we need more bits than are in the mantissa of the type we converted370 // to? semanticsPrecision returns the number of mantissa bits plus one371 // for the sign bit.372 unsigned MaxRepresentableBits373 = APFloat::semanticsPrecision(ConvertedToTy->getFltSemantics()) - 1;374 if (MinBW > MaxRepresentableBits) {375 LLVM_DEBUG(dbgs() << "F2I: Value not guaranteed to be representable!\n");376 continue;377 }378 379 // OK, R is known to be representable.380 // Pick the smallest legal type that will fit.381 Type *Ty = DL.getSmallestLegalIntType(*Ctx, MinBW);382 if (!Ty) {383 // Every supported target supports 64-bit and 32-bit integers,384 // so fallback to a 32 or 64-bit integer if the value fits.385 if (MinBW <= 32) {386 Ty = Type::getInt32Ty(*Ctx);387 } else if (MinBW <= 64) {388 Ty = Type::getInt64Ty(*Ctx);389 } else {390 LLVM_DEBUG(dbgs() << "F2I: Value requires more bits to represent than "391 "the target supports!\n");392 continue;393 }394 }395 396 for (Instruction *I : ECs.members(*E))397 convert(I, Ty);398 MadeChange = true;399 }400 401 return MadeChange;402}403 404Value *Float2IntPass::convert(Instruction *I, Type *ToTy) {405 if (auto It = ConvertedInsts.find(I); It != ConvertedInsts.end())406 // Already converted this instruction.407 return It->second;408 409 SmallVector<Value*,4> NewOperands;410 for (Value *V : I->operands()) {411 // Don't recurse if we're an instruction that terminates the path.412 if (I->getOpcode() == Instruction::UIToFP ||413 I->getOpcode() == Instruction::SIToFP) {414 NewOperands.push_back(V);415 } else if (Instruction *VI = dyn_cast<Instruction>(V)) {416 NewOperands.push_back(convert(VI, ToTy));417 } else if (ConstantFP *CF = dyn_cast<ConstantFP>(V)) {418 APSInt Val(ToTy->getPrimitiveSizeInBits(), /*isUnsigned=*/false);419 bool Exact;420 CF->getValueAPF().convertToInteger(Val,421 APFloat::rmNearestTiesToEven,422 &Exact);423 NewOperands.push_back(ConstantInt::get(ToTy, Val));424 } else {425 llvm_unreachable("Unhandled operand type?");426 }427 }428 429 // Now create a new instruction.430 IRBuilder<> IRB(I);431 Value *NewV = nullptr;432 switch (I->getOpcode()) {433 default: llvm_unreachable("Unhandled instruction!");434 435 case Instruction::FPToUI:436 NewV = IRB.CreateZExtOrTrunc(NewOperands[0], I->getType());437 break;438 439 case Instruction::FPToSI:440 NewV = IRB.CreateSExtOrTrunc(NewOperands[0], I->getType());441 break;442 443 case Instruction::FCmp: {444 CmpInst::Predicate P = mapFCmpPred(cast<CmpInst>(I)->getPredicate());445 assert(P != CmpInst::BAD_ICMP_PREDICATE && "Unhandled predicate!");446 NewV = IRB.CreateICmp(P, NewOperands[0], NewOperands[1], I->getName());447 break;448 }449 450 case Instruction::UIToFP:451 NewV = IRB.CreateZExtOrTrunc(NewOperands[0], ToTy);452 break;453 454 case Instruction::SIToFP:455 NewV = IRB.CreateSExtOrTrunc(NewOperands[0], ToTy);456 break;457 458 case Instruction::FNeg:459 NewV = IRB.CreateNeg(NewOperands[0], I->getName());460 break;461 462 case Instruction::FAdd:463 case Instruction::FSub:464 case Instruction::FMul:465 NewV = IRB.CreateBinOp(mapBinOpcode(I->getOpcode()),466 NewOperands[0], NewOperands[1],467 I->getName());468 break;469 }470 471 // If we're a root instruction, RAUW.472 if (Roots.count(I))473 I->replaceAllUsesWith(NewV);474 475 ConvertedInsts[I] = NewV;476 return NewV;477}478 479// Perform dead code elimination on the instructions we just modified.480void Float2IntPass::cleanup() {481 for (auto &I : reverse(ConvertedInsts))482 I.first->eraseFromParent();483}484 485bool Float2IntPass::runImpl(Function &F, const DominatorTree &DT) {486 LLVM_DEBUG(dbgs() << "F2I: Looking at function " << F.getName() << "\n");487 // Clear out all state.488 ECs = EquivalenceClasses<Instruction*>();489 SeenInsts.clear();490 ConvertedInsts.clear();491 Roots.clear();492 493 Ctx = &F.getParent()->getContext();494 495 findRoots(F, DT);496 497 walkBackwards();498 walkForwards();499 500 const DataLayout &DL = F.getDataLayout();501 bool Modified = validateAndTransform(DL);502 if (Modified)503 cleanup();504 return Modified;505}506 507PreservedAnalyses Float2IntPass::run(Function &F, FunctionAnalysisManager &AM) {508 const DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);509 if (!runImpl(F, DT))510 return PreservedAnalyses::all();511 512 PreservedAnalyses PA;513 PA.preserveSet<CFGAnalyses>();514 return PA;515}516