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