1 | //===- llvm/Transforms/Utils/BypassSlowDivision.h ---------------*- C++ -*-===// |
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 contains an optimization for div and rem on architectures that |
10 | // execute short instructions significantly faster than longer instructions. |
11 | // For example, on Intel Atom 32-bit divides are slow enough that during |
12 | // runtime it is profitable to check the value of the operands, and if they are |
13 | // positive and less than 256 use an unsigned 8-bit divide. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H |
18 | #define LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H |
19 | |
20 | #include "llvm/ADT/DenseMap.h" |
21 | #include "llvm/ADT/DenseMapInfo.h" |
22 | #include "llvm/IR/ValueHandle.h" |
23 | #include <cstdint> |
24 | |
25 | namespace llvm { |
26 | |
27 | class BasicBlock; |
28 | class Value; |
29 | |
30 | struct DivRemMapKey { |
31 | bool SignedOp; |
32 | AssertingVH<Value> Dividend; |
33 | AssertingVH<Value> Divisor; |
34 | |
35 | DivRemMapKey() = default; |
36 | |
37 | DivRemMapKey(bool InSignedOp, Value *InDividend, Value *InDivisor) |
38 | : SignedOp(InSignedOp), Dividend(InDividend), Divisor(InDivisor) {} |
39 | }; |
40 | |
41 | template <> struct DenseMapInfo<DivRemMapKey> { |
42 | static bool isEqual(const DivRemMapKey &Val1, const DivRemMapKey &Val2) { |
43 | return Val1.SignedOp == Val2.SignedOp && Val1.Dividend == Val2.Dividend && |
44 | Val1.Divisor == Val2.Divisor; |
45 | } |
46 | |
47 | static DivRemMapKey getEmptyKey() { |
48 | return DivRemMapKey(false, nullptr, nullptr); |
49 | } |
50 | |
51 | static DivRemMapKey getTombstoneKey() { |
52 | return DivRemMapKey(true, nullptr, nullptr); |
53 | } |
54 | |
55 | static unsigned getHashValue(const DivRemMapKey &Val) { |
56 | return (unsigned)(reinterpret_cast<uintptr_t>( |
57 | static_cast<Value *>(Val.Dividend)) ^ |
58 | reinterpret_cast<uintptr_t>( |
59 | static_cast<Value *>(Val.Divisor))) ^ |
60 | (unsigned)Val.SignedOp; |
61 | } |
62 | }; |
63 | |
64 | /// This optimization identifies DIV instructions in a BB that can be |
65 | /// profitably bypassed and carried out with a shorter, faster divide. |
66 | /// |
67 | /// This optimization may add basic blocks immediately after BB; for obvious |
68 | /// reasons, you shouldn't pass those blocks to bypassSlowDivision. |
69 | bool bypassSlowDivision( |
70 | BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth); |
71 | |
72 | } // end namespace llvm |
73 | |
74 | #endif // LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H |
75 | |