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