1/*
2 * Copyright (C) 2016 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 * This contains code taken from LLVM's APInt class. That code implements finding the magic
26 * numbers for strength-reducing division. The LLVM code on which this code is based was
27 * implemented using "Hacker's Delight", Henry S. Warren, Jr., chapter 10.
28 *
29 * ==============================================================================
30 * LLVM Release License
31 * ==============================================================================
32 * University of Illinois/NCSA
33 * Open Source License
34 *
35 * Copyright (c) 2003-2014 University of Illinois at Urbana-Champaign.
36 * All rights reserved.
37 *
38 * Developed by:
39 *
40 * LLVM Team
41 *
42 * University of Illinois at Urbana-Champaign
43 *
44 * http://llvm.org
45 *
46 * Permission is hereby granted, free of charge, to any person obtaining a copy of
47 * this software and associated documentation files (the "Software"), to deal with
48 * the Software without restriction, including without limitation the rights to
49 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
50 * of the Software, and to permit persons to whom the Software is furnished to do
51 * so, subject to the following conditions:
52 *
53 * * Redistributions of source code must retain the above copyright notice,
54 * this list of conditions and the following disclaimers.
55 *
56 * * Redistributions in binary form must reproduce the above copyright notice,
57 * this list of conditions and the following disclaimers in the
58 * documentation and/or other materials provided with the distribution.
59 *
60 * * Neither the names of the LLVM Team, University of Illinois at
61 * Urbana-Champaign, nor the names of its contributors may be used to
62 * endorse or promote products derived from this Software without specific
63 * prior written permission.
64 *
65 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
66 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
67 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
68 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
69 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
70 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
71 * SOFTWARE.
72 */
73
74#pragma once
75
76#if ENABLE(B3_JIT)
77
78namespace JSC { namespace B3 {
79
80template<typename T>
81struct DivisionMagic {
82 T magicMultiplier;
83 unsigned shift;
84};
85
86// This contains code taken from LLVM's APInt::magic(). It's modestly adapted to our style, but
87// not completely, to make it easier to apply their changes in the future.
88template<typename T>
89DivisionMagic<T> computeDivisionMagic(T divisor)
90{
91 typedef typename std::make_unsigned<T>::type UnsignedT;
92 UnsignedT d = divisor;
93 unsigned p;
94 UnsignedT ad, anc, delta, q1, r1, q2, r2, t;
95 UnsignedT signedMin = static_cast<UnsignedT>(std::numeric_limits<T>::min());
96 DivisionMagic<T> mag;
97 unsigned bitWidth = sizeof(divisor) * 8;
98
99 // This code doesn't like to think of signedness as a type. Instead it likes to think that
100 // operations have signedness. This is how we generally do it in B3 as well. For this reason,
101 // we cast all the operated values once to unsigned. And later, we convert it to signed.
102 // Only `divisor` have signedness here.
103
104 ad = divisor < 0 ? -divisor : divisor; // -(signed min value) < signed max value. So there is no loss.
105 t = signedMin + (d >> (bitWidth - 1));
106 anc = t - 1 - (t % ad); // absolute value of nc
107 p = bitWidth - 1; // initialize p
108 q1 = signedMin / anc; // initialize q1 = 2p/abs(nc)
109 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
110 q2 = signedMin / ad; // initialize q2 = 2p/abs(d)
111 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
112 do {
113 p = p + 1;
114 q1 = q1 << 1; // update q1 = 2p/abs(nc)
115 r1 = r1 << 1; // update r1 = rem(2p/abs(nc))
116 if (r1 >= anc) { // must be unsigned comparison
117 q1 = q1 + 1;
118 r1 = r1 - anc;
119 }
120 q2 = q2 << 1; // update q2 = 2p/abs(d)
121 r2 = r2 << 1; // update r2 = rem(2p/abs(d))
122 if (r2 >= ad) { // must be unsigned comparison
123 q2 = q2 + 1;
124 r2 = r2 - ad;
125 }
126 delta = ad - r2;
127 } while (q1 < delta || (q1 == delta && r1 == 0));
128
129 mag.magicMultiplier = q2 + 1;
130 if (divisor < 0)
131 mag.magicMultiplier = -mag.magicMultiplier; // resulting magic number
132 mag.shift = p - bitWidth; // resulting shift
133
134 return mag;
135}
136
137} } // namespace JSC::B3
138
139#endif // ENABLE(B3_JIT)
140