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