LLVM  13.0.0git
BypassSlowDivision.h
Go to the documentation of this file.
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;
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 
48  return DivRemMapKey(false, nullptr, nullptr);
49  }
50 
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.
70  BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth);
71 
72 } // end namespace llvm
73 
74 #endif // LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H
llvm::bypassSlowDivision
bool bypassSlowDivision(BasicBlock *BB, const DenseMap< unsigned int, unsigned int > &BypassWidth)
This optimization identifies DIV instructions in a BB that can be profitably bypassed and carried out...
llvm
Definition: AllocatorList.h:23
llvm::DenseMapInfo< DivRemMapKey >::getHashValue
static unsigned getHashValue(const DivRemMapKey &Val)
Definition: BypassSlowDivision.h:55
DenseMap.h
llvm::DivRemMapKey::SignedOp
bool SignedOp
Definition: BypassSlowDivision.h:31
llvm::DivRemMapKey::Divisor
AssertingVH< Value > Divisor
Definition: BypassSlowDivision.h:33
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::DivRemMapKey::DivRemMapKey
DivRemMapKey(bool InSignedOp, Value *InDividend, Value *InDivisor)
Definition: BypassSlowDivision.h:37
llvm::DenseMapInfo< DivRemMapKey >::isEqual
static bool isEqual(const DivRemMapKey &Val1, const DivRemMapKey &Val2)
Definition: BypassSlowDivision.h:42
llvm::DenseMapInfo< DivRemMapKey >::getTombstoneKey
static DivRemMapKey getTombstoneKey()
Definition: BypassSlowDivision.h:51
llvm::DenseMapInfo< DivRemMapKey >::getEmptyKey
static DivRemMapKey getEmptyKey()
Definition: BypassSlowDivision.h:47
llvm::DivRemMapKey::Dividend
AssertingVH< Value > Dividend
Definition: BypassSlowDivision.h:32
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
ValueHandle.h
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::DivRemMapKey::DivRemMapKey
DivRemMapKey()=default
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
llvm::DivRemMapKey
Definition: BypassSlowDivision.h:30
DenseMapInfo.h
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Value
LLVM Value Representation.
Definition: Value.h:75