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