File: | lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp |
Location: | line 1090, column 7 |
Description: | Value stored to 'Ratio' is never read |
1 | //===- InstCombineSimplifyDemanded.cpp ------------------------------------===// |
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 logic for simplifying instructions based on information |
11 | // about how they are used. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #include "InstCombineInternal.h" |
16 | #include "llvm/Analysis/ValueTracking.h" |
17 | #include "llvm/IR/IntrinsicInst.h" |
18 | #include "llvm/IR/PatternMatch.h" |
19 | |
20 | using namespace llvm; |
21 | using namespace llvm::PatternMatch; |
22 | |
23 | #define DEBUG_TYPE"instcombine" "instcombine" |
24 | |
25 | /// ShrinkDemandedConstant - Check to see if the specified operand of the |
26 | /// specified instruction is a constant integer. If so, check to see if there |
27 | /// are any bits set in the constant that are not demanded. If so, shrink the |
28 | /// constant and return true. |
29 | static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, |
30 | APInt Demanded) { |
31 | assert(I && "No instruction?")((I && "No instruction?") ? static_cast<void> ( 0) : __assert_fail ("I && \"No instruction?\"", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 31, __PRETTY_FUNCTION__)); |
32 | assert(OpNo < I->getNumOperands() && "Operand index too large")((OpNo < I->getNumOperands() && "Operand index too large" ) ? static_cast<void> (0) : __assert_fail ("OpNo < I->getNumOperands() && \"Operand index too large\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 32, __PRETTY_FUNCTION__)); |
33 | |
34 | // If the operand is not a constant integer, nothing to do. |
35 | ConstantInt *OpC = dyn_cast<ConstantInt>(I->getOperand(OpNo)); |
36 | if (!OpC) return false; |
37 | |
38 | // If there are no bits set that aren't demanded, nothing to do. |
39 | Demanded = Demanded.zextOrTrunc(OpC->getValue().getBitWidth()); |
40 | if ((~Demanded & OpC->getValue()) == 0) |
41 | return false; |
42 | |
43 | // This instruction is producing bits that are not demanded. Shrink the RHS. |
44 | Demanded &= OpC->getValue(); |
45 | I->setOperand(OpNo, ConstantInt::get(OpC->getType(), Demanded)); |
46 | |
47 | return true; |
48 | } |
49 | |
50 | |
51 | |
52 | /// SimplifyDemandedInstructionBits - Inst is an integer instruction that |
53 | /// SimplifyDemandedBits knows about. See if the instruction has any |
54 | /// properties that allow us to simplify its operands. |
55 | bool InstCombiner::SimplifyDemandedInstructionBits(Instruction &Inst) { |
56 | unsigned BitWidth = Inst.getType()->getScalarSizeInBits(); |
57 | APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); |
58 | APInt DemandedMask(APInt::getAllOnesValue(BitWidth)); |
59 | |
60 | Value *V = SimplifyDemandedUseBits(&Inst, DemandedMask, KnownZero, KnownOne, |
61 | 0, &Inst); |
62 | if (!V) return false; |
63 | if (V == &Inst) return true; |
64 | ReplaceInstUsesWith(Inst, V); |
65 | return true; |
66 | } |
67 | |
68 | /// SimplifyDemandedBits - This form of SimplifyDemandedBits simplifies the |
69 | /// specified instruction operand if possible, updating it in place. It returns |
70 | /// true if it made any change and false otherwise. |
71 | bool InstCombiner::SimplifyDemandedBits(Use &U, APInt DemandedMask, |
72 | APInt &KnownZero, APInt &KnownOne, |
73 | unsigned Depth) { |
74 | auto *UserI = dyn_cast<Instruction>(U.getUser()); |
75 | Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask, KnownZero, |
76 | KnownOne, Depth, UserI); |
77 | if (!NewVal) return false; |
78 | U = NewVal; |
79 | return true; |
80 | } |
81 | |
82 | |
83 | /// SimplifyDemandedUseBits - This function attempts to replace V with a simpler |
84 | /// value based on the demanded bits. When this function is called, it is known |
85 | /// that only the bits set in DemandedMask of the result of V are ever used |
86 | /// downstream. Consequently, depending on the mask and V, it may be possible |
87 | /// to replace V with a constant or one of its operands. In such cases, this |
88 | /// function does the replacement and returns true. In all other cases, it |
89 | /// returns false after analyzing the expression and setting KnownOne and known |
90 | /// to be one in the expression. KnownZero contains all the bits that are known |
91 | /// to be zero in the expression. These are provided to potentially allow the |
92 | /// caller (which might recursively be SimplifyDemandedBits itself) to simplify |
93 | /// the expression. KnownOne and KnownZero always follow the invariant that |
94 | /// KnownOne & KnownZero == 0. That is, a bit can't be both 1 and 0. Note that |
95 | /// the bits in KnownOne and KnownZero may only be accurate for those bits set |
96 | /// in DemandedMask. Note also that the bitwidth of V, DemandedMask, KnownZero |
97 | /// and KnownOne must all be the same. |
98 | /// |
99 | /// This returns null if it did not change anything and it permits no |
100 | /// simplification. This returns V itself if it did some simplification of V's |
101 | /// operands based on the information about what bits are demanded. This returns |
102 | /// some other non-null value if it found out that V is equal to another value |
103 | /// in the context where the specified bits are demanded, but not for all users. |
104 | Value *InstCombiner::SimplifyDemandedUseBits(Value *V, APInt DemandedMask, |
105 | APInt &KnownZero, APInt &KnownOne, |
106 | unsigned Depth, |
107 | Instruction *CxtI) { |
108 | assert(V != nullptr && "Null pointer of Value???")((V != nullptr && "Null pointer of Value???") ? static_cast <void> (0) : __assert_fail ("V != nullptr && \"Null pointer of Value???\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 108, __PRETTY_FUNCTION__)); |
109 | assert(Depth <= 6 && "Limit Search Depth")((Depth <= 6 && "Limit Search Depth") ? static_cast <void> (0) : __assert_fail ("Depth <= 6 && \"Limit Search Depth\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 109, __PRETTY_FUNCTION__)); |
110 | uint32_t BitWidth = DemandedMask.getBitWidth(); |
111 | Type *VTy = V->getType(); |
112 | assert((((!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits () == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && "Value *V, DemandedMask, KnownZero and KnownOne " "must have same BitWidth") ? static_cast<void> (0) : __assert_fail ("(!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && \"Value *V, DemandedMask, KnownZero and KnownOne \" \"must have same BitWidth\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 117, __PRETTY_FUNCTION__)) |
113 | (!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) &&(((!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits () == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && "Value *V, DemandedMask, KnownZero and KnownOne " "must have same BitWidth") ? static_cast<void> (0) : __assert_fail ("(!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && \"Value *V, DemandedMask, KnownZero and KnownOne \" \"must have same BitWidth\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 117, __PRETTY_FUNCTION__)) |
114 | KnownZero.getBitWidth() == BitWidth &&(((!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits () == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && "Value *V, DemandedMask, KnownZero and KnownOne " "must have same BitWidth") ? static_cast<void> (0) : __assert_fail ("(!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && \"Value *V, DemandedMask, KnownZero and KnownOne \" \"must have same BitWidth\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 117, __PRETTY_FUNCTION__)) |
115 | KnownOne.getBitWidth() == BitWidth &&(((!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits () == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && "Value *V, DemandedMask, KnownZero and KnownOne " "must have same BitWidth") ? static_cast<void> (0) : __assert_fail ("(!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && \"Value *V, DemandedMask, KnownZero and KnownOne \" \"must have same BitWidth\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 117, __PRETTY_FUNCTION__)) |
116 | "Value *V, DemandedMask, KnownZero and KnownOne "(((!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits () == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && "Value *V, DemandedMask, KnownZero and KnownOne " "must have same BitWidth") ? static_cast<void> (0) : __assert_fail ("(!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && \"Value *V, DemandedMask, KnownZero and KnownOne \" \"must have same BitWidth\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 117, __PRETTY_FUNCTION__)) |
117 | "must have same BitWidth")(((!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits () == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && "Value *V, DemandedMask, KnownZero and KnownOne " "must have same BitWidth") ? static_cast<void> (0) : __assert_fail ("(!VTy->isIntOrIntVectorTy() || VTy->getScalarSizeInBits() == BitWidth) && KnownZero.getBitWidth() == BitWidth && KnownOne.getBitWidth() == BitWidth && \"Value *V, DemandedMask, KnownZero and KnownOne \" \"must have same BitWidth\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 117, __PRETTY_FUNCTION__)); |
118 | if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { |
119 | // We know all of the bits for a constant! |
120 | KnownOne = CI->getValue() & DemandedMask; |
121 | KnownZero = ~KnownOne & DemandedMask; |
122 | return nullptr; |
123 | } |
124 | if (isa<ConstantPointerNull>(V)) { |
125 | // We know all of the bits for a constant! |
126 | KnownOne.clearAllBits(); |
127 | KnownZero = DemandedMask; |
128 | return nullptr; |
129 | } |
130 | |
131 | KnownZero.clearAllBits(); |
132 | KnownOne.clearAllBits(); |
133 | if (DemandedMask == 0) { // Not demanding any bits from V. |
134 | if (isa<UndefValue>(V)) |
135 | return nullptr; |
136 | return UndefValue::get(VTy); |
137 | } |
138 | |
139 | if (Depth == 6) // Limit search depth. |
140 | return nullptr; |
141 | |
142 | APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); |
143 | APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); |
144 | |
145 | Instruction *I = dyn_cast<Instruction>(V); |
146 | if (!I) { |
147 | computeKnownBits(V, KnownZero, KnownOne, Depth, CxtI); |
148 | return nullptr; // Only analyze instructions. |
149 | } |
150 | |
151 | // If there are multiple uses of this value and we aren't at the root, then |
152 | // we can't do any simplifications of the operands, because DemandedMask |
153 | // only reflects the bits demanded by *one* of the users. |
154 | if (Depth != 0 && !I->hasOneUse()) { |
155 | // Despite the fact that we can't simplify this instruction in all User's |
156 | // context, we can at least compute the knownzero/knownone bits, and we can |
157 | // do simplifications that apply to *just* the one user if we know that |
158 | // this instruction has a simpler value in that context. |
159 | if (I->getOpcode() == Instruction::And) { |
160 | // If either the LHS or the RHS are Zero, the result is zero. |
161 | computeKnownBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth + 1, |
162 | CxtI); |
163 | computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth + 1, |
164 | CxtI); |
165 | |
166 | // If all of the demanded bits are known 1 on one side, return the other. |
167 | // These bits cannot contribute to the result of the 'and' in this |
168 | // context. |
169 | if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == |
170 | (DemandedMask & ~LHSKnownZero)) |
171 | return I->getOperand(0); |
172 | if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == |
173 | (DemandedMask & ~RHSKnownZero)) |
174 | return I->getOperand(1); |
175 | |
176 | // If all of the demanded bits in the inputs are known zeros, return zero. |
177 | if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) |
178 | return Constant::getNullValue(VTy); |
179 | |
180 | } else if (I->getOpcode() == Instruction::Or) { |
181 | // We can simplify (X|Y) -> X or Y in the user's context if we know that |
182 | // only bits from X or Y are demanded. |
183 | |
184 | // If either the LHS or the RHS are One, the result is One. |
185 | computeKnownBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth + 1, |
186 | CxtI); |
187 | computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth + 1, |
188 | CxtI); |
189 | |
190 | // If all of the demanded bits are known zero on one side, return the |
191 | // other. These bits cannot contribute to the result of the 'or' in this |
192 | // context. |
193 | if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == |
194 | (DemandedMask & ~LHSKnownOne)) |
195 | return I->getOperand(0); |
196 | if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == |
197 | (DemandedMask & ~RHSKnownOne)) |
198 | return I->getOperand(1); |
199 | |
200 | // If all of the potentially set bits on one side are known to be set on |
201 | // the other side, just use the 'other' side. |
202 | if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == |
203 | (DemandedMask & (~RHSKnownZero))) |
204 | return I->getOperand(0); |
205 | if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == |
206 | (DemandedMask & (~LHSKnownZero))) |
207 | return I->getOperand(1); |
208 | } else if (I->getOpcode() == Instruction::Xor) { |
209 | // We can simplify (X^Y) -> X or Y in the user's context if we know that |
210 | // only bits from X or Y are demanded. |
211 | |
212 | computeKnownBits(I->getOperand(1), RHSKnownZero, RHSKnownOne, Depth + 1, |
213 | CxtI); |
214 | computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth + 1, |
215 | CxtI); |
216 | |
217 | // If all of the demanded bits are known zero on one side, return the |
218 | // other. |
219 | if ((DemandedMask & RHSKnownZero) == DemandedMask) |
220 | return I->getOperand(0); |
221 | if ((DemandedMask & LHSKnownZero) == DemandedMask) |
222 | return I->getOperand(1); |
223 | } |
224 | |
225 | // Compute the KnownZero/KnownOne bits to simplify things downstream. |
226 | computeKnownBits(I, KnownZero, KnownOne, Depth, CxtI); |
227 | return nullptr; |
228 | } |
229 | |
230 | // If this is the root being simplified, allow it to have multiple uses, |
231 | // just set the DemandedMask to all bits so that we can try to simplify the |
232 | // operands. This allows visitTruncInst (for example) to simplify the |
233 | // operand of a trunc without duplicating all the logic below. |
234 | if (Depth == 0 && !V->hasOneUse()) |
235 | DemandedMask = APInt::getAllOnesValue(BitWidth); |
236 | |
237 | switch (I->getOpcode()) { |
238 | default: |
239 | computeKnownBits(I, KnownZero, KnownOne, Depth, CxtI); |
240 | break; |
241 | case Instruction::And: |
242 | // If either the LHS or the RHS are Zero, the result is zero. |
243 | if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, RHSKnownZero, |
244 | RHSKnownOne, Depth + 1) || |
245 | SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownZero, |
246 | LHSKnownZero, LHSKnownOne, Depth + 1)) |
247 | return I; |
248 | assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?")((!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(RHSKnownZero & RHSKnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 248, __PRETTY_FUNCTION__)); |
249 | assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?")((!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(LHSKnownZero & LHSKnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 249, __PRETTY_FUNCTION__)); |
250 | |
251 | // If the client is only demanding bits that we know, return the known |
252 | // constant. |
253 | if ((DemandedMask & ((RHSKnownZero | LHSKnownZero)| |
254 | (RHSKnownOne & LHSKnownOne))) == DemandedMask) |
255 | return Constant::getIntegerValue(VTy, RHSKnownOne & LHSKnownOne); |
256 | |
257 | // If all of the demanded bits are known 1 on one side, return the other. |
258 | // These bits cannot contribute to the result of the 'and'. |
259 | if ((DemandedMask & ~LHSKnownZero & RHSKnownOne) == |
260 | (DemandedMask & ~LHSKnownZero)) |
261 | return I->getOperand(0); |
262 | if ((DemandedMask & ~RHSKnownZero & LHSKnownOne) == |
263 | (DemandedMask & ~RHSKnownZero)) |
264 | return I->getOperand(1); |
265 | |
266 | // If all of the demanded bits in the inputs are known zeros, return zero. |
267 | if ((DemandedMask & (RHSKnownZero|LHSKnownZero)) == DemandedMask) |
268 | return Constant::getNullValue(VTy); |
269 | |
270 | // If the RHS is a constant, see if we can simplify it. |
271 | if (ShrinkDemandedConstant(I, 1, DemandedMask & ~LHSKnownZero)) |
272 | return I; |
273 | |
274 | // Output known-1 bits are only known if set in both the LHS & RHS. |
275 | KnownOne = RHSKnownOne & LHSKnownOne; |
276 | // Output known-0 are known to be clear if zero in either the LHS | RHS. |
277 | KnownZero = RHSKnownZero | LHSKnownZero; |
278 | break; |
279 | case Instruction::Or: |
280 | // If either the LHS or the RHS are One, the result is One. |
281 | if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, RHSKnownZero, |
282 | RHSKnownOne, Depth + 1) || |
283 | SimplifyDemandedBits(I->getOperandUse(0), DemandedMask & ~RHSKnownOne, |
284 | LHSKnownZero, LHSKnownOne, Depth + 1)) |
285 | return I; |
286 | assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?")((!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(RHSKnownZero & RHSKnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 286, __PRETTY_FUNCTION__)); |
287 | assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?")((!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(LHSKnownZero & LHSKnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 287, __PRETTY_FUNCTION__)); |
288 | |
289 | // If the client is only demanding bits that we know, return the known |
290 | // constant. |
291 | if ((DemandedMask & ((RHSKnownZero & LHSKnownZero)| |
292 | (RHSKnownOne | LHSKnownOne))) == DemandedMask) |
293 | return Constant::getIntegerValue(VTy, RHSKnownOne | LHSKnownOne); |
294 | |
295 | // If all of the demanded bits are known zero on one side, return the other. |
296 | // These bits cannot contribute to the result of the 'or'. |
297 | if ((DemandedMask & ~LHSKnownOne & RHSKnownZero) == |
298 | (DemandedMask & ~LHSKnownOne)) |
299 | return I->getOperand(0); |
300 | if ((DemandedMask & ~RHSKnownOne & LHSKnownZero) == |
301 | (DemandedMask & ~RHSKnownOne)) |
302 | return I->getOperand(1); |
303 | |
304 | // If all of the potentially set bits on one side are known to be set on |
305 | // the other side, just use the 'other' side. |
306 | if ((DemandedMask & (~RHSKnownZero) & LHSKnownOne) == |
307 | (DemandedMask & (~RHSKnownZero))) |
308 | return I->getOperand(0); |
309 | if ((DemandedMask & (~LHSKnownZero) & RHSKnownOne) == |
310 | (DemandedMask & (~LHSKnownZero))) |
311 | return I->getOperand(1); |
312 | |
313 | // If the RHS is a constant, see if we can simplify it. |
314 | if (ShrinkDemandedConstant(I, 1, DemandedMask)) |
315 | return I; |
316 | |
317 | // Output known-0 bits are only known if clear in both the LHS & RHS. |
318 | KnownZero = RHSKnownZero & LHSKnownZero; |
319 | // Output known-1 are known to be set if set in either the LHS | RHS. |
320 | KnownOne = RHSKnownOne | LHSKnownOne; |
321 | break; |
322 | case Instruction::Xor: { |
323 | if (SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, RHSKnownZero, |
324 | RHSKnownOne, Depth + 1) || |
325 | SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, LHSKnownZero, |
326 | LHSKnownOne, Depth + 1)) |
327 | return I; |
328 | assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?")((!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(RHSKnownZero & RHSKnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 328, __PRETTY_FUNCTION__)); |
329 | assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?")((!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(LHSKnownZero & LHSKnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 329, __PRETTY_FUNCTION__)); |
330 | |
331 | // Output known-0 bits are known if clear or set in both the LHS & RHS. |
332 | APInt IKnownZero = (RHSKnownZero & LHSKnownZero) | |
333 | (RHSKnownOne & LHSKnownOne); |
334 | // Output known-1 are known to be set if set in only one of the LHS, RHS. |
335 | APInt IKnownOne = (RHSKnownZero & LHSKnownOne) | |
336 | (RHSKnownOne & LHSKnownZero); |
337 | |
338 | // If the client is only demanding bits that we know, return the known |
339 | // constant. |
340 | if ((DemandedMask & (IKnownZero|IKnownOne)) == DemandedMask) |
341 | return Constant::getIntegerValue(VTy, IKnownOne); |
342 | |
343 | // If all of the demanded bits are known zero on one side, return the other. |
344 | // These bits cannot contribute to the result of the 'xor'. |
345 | if ((DemandedMask & RHSKnownZero) == DemandedMask) |
346 | return I->getOperand(0); |
347 | if ((DemandedMask & LHSKnownZero) == DemandedMask) |
348 | return I->getOperand(1); |
349 | |
350 | // If all of the demanded bits are known to be zero on one side or the |
351 | // other, turn this into an *inclusive* or. |
352 | // e.g. (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0 |
353 | if ((DemandedMask & ~RHSKnownZero & ~LHSKnownZero) == 0) { |
354 | Instruction *Or = |
355 | BinaryOperator::CreateOr(I->getOperand(0), I->getOperand(1), |
356 | I->getName()); |
357 | return InsertNewInstWith(Or, *I); |
358 | } |
359 | |
360 | // If all of the demanded bits on one side are known, and all of the set |
361 | // bits on that side are also known to be set on the other side, turn this |
362 | // into an AND, as we know the bits will be cleared. |
363 | // e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2 |
364 | if ((DemandedMask & (RHSKnownZero|RHSKnownOne)) == DemandedMask) { |
365 | // all known |
366 | if ((RHSKnownOne & LHSKnownOne) == RHSKnownOne) { |
367 | Constant *AndC = Constant::getIntegerValue(VTy, |
368 | ~RHSKnownOne & DemandedMask); |
369 | Instruction *And = BinaryOperator::CreateAnd(I->getOperand(0), AndC); |
370 | return InsertNewInstWith(And, *I); |
371 | } |
372 | } |
373 | |
374 | // If the RHS is a constant, see if we can simplify it. |
375 | // FIXME: for XOR, we prefer to force bits to 1 if they will make a -1. |
376 | if (ShrinkDemandedConstant(I, 1, DemandedMask)) |
377 | return I; |
378 | |
379 | // If our LHS is an 'and' and if it has one use, and if any of the bits we |
380 | // are flipping are known to be set, then the xor is just resetting those |
381 | // bits to zero. We can just knock out bits from the 'and' and the 'xor', |
382 | // simplifying both of them. |
383 | if (Instruction *LHSInst = dyn_cast<Instruction>(I->getOperand(0))) |
384 | if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() && |
385 | isa<ConstantInt>(I->getOperand(1)) && |
386 | isa<ConstantInt>(LHSInst->getOperand(1)) && |
387 | (LHSKnownOne & RHSKnownOne & DemandedMask) != 0) { |
388 | ConstantInt *AndRHS = cast<ConstantInt>(LHSInst->getOperand(1)); |
389 | ConstantInt *XorRHS = cast<ConstantInt>(I->getOperand(1)); |
390 | APInt NewMask = ~(LHSKnownOne & RHSKnownOne & DemandedMask); |
391 | |
392 | Constant *AndC = |
393 | ConstantInt::get(I->getType(), NewMask & AndRHS->getValue()); |
394 | Instruction *NewAnd = BinaryOperator::CreateAnd(I->getOperand(0), AndC); |
395 | InsertNewInstWith(NewAnd, *I); |
396 | |
397 | Constant *XorC = |
398 | ConstantInt::get(I->getType(), NewMask & XorRHS->getValue()); |
399 | Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC); |
400 | return InsertNewInstWith(NewXor, *I); |
401 | } |
402 | |
403 | // Output known-0 bits are known if clear or set in both the LHS & RHS. |
404 | KnownZero= (RHSKnownZero & LHSKnownZero) | (RHSKnownOne & LHSKnownOne); |
405 | // Output known-1 are known to be set if set in only one of the LHS, RHS. |
406 | KnownOne = (RHSKnownZero & LHSKnownOne) | (RHSKnownOne & LHSKnownZero); |
407 | break; |
408 | } |
409 | case Instruction::Select: |
410 | // If this is a select as part of a min/max pattern, don't simplify any |
411 | // further in case we break the structure. |
412 | Value *LHS, *RHS; |
413 | if (matchSelectPattern(I, LHS, RHS).Flavor != SPF_UNKNOWN) |
414 | return nullptr; |
415 | |
416 | if (SimplifyDemandedBits(I->getOperandUse(2), DemandedMask, RHSKnownZero, |
417 | RHSKnownOne, Depth + 1) || |
418 | SimplifyDemandedBits(I->getOperandUse(1), DemandedMask, LHSKnownZero, |
419 | LHSKnownOne, Depth + 1)) |
420 | return I; |
421 | assert(!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?")((!(RHSKnownZero & RHSKnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(RHSKnownZero & RHSKnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 421, __PRETTY_FUNCTION__)); |
422 | assert(!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?")((!(LHSKnownZero & LHSKnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(LHSKnownZero & LHSKnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 422, __PRETTY_FUNCTION__)); |
423 | |
424 | // If the operands are constants, see if we can simplify them. |
425 | if (ShrinkDemandedConstant(I, 1, DemandedMask) || |
426 | ShrinkDemandedConstant(I, 2, DemandedMask)) |
427 | return I; |
428 | |
429 | // Only known if known in both the LHS and RHS. |
430 | KnownOne = RHSKnownOne & LHSKnownOne; |
431 | KnownZero = RHSKnownZero & LHSKnownZero; |
432 | break; |
433 | case Instruction::Trunc: { |
434 | unsigned truncBf = I->getOperand(0)->getType()->getScalarSizeInBits(); |
435 | DemandedMask = DemandedMask.zext(truncBf); |
436 | KnownZero = KnownZero.zext(truncBf); |
437 | KnownOne = KnownOne.zext(truncBf); |
438 | if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, KnownZero, |
439 | KnownOne, Depth + 1)) |
440 | return I; |
441 | DemandedMask = DemandedMask.trunc(BitWidth); |
442 | KnownZero = KnownZero.trunc(BitWidth); |
443 | KnownOne = KnownOne.trunc(BitWidth); |
444 | assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?")((!(KnownZero & KnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(KnownZero & KnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 444, __PRETTY_FUNCTION__)); |
445 | break; |
446 | } |
447 | case Instruction::BitCast: |
448 | if (!I->getOperand(0)->getType()->isIntOrIntVectorTy()) |
449 | return nullptr; // vector->int or fp->int? |
450 | |
451 | if (VectorType *DstVTy = dyn_cast<VectorType>(I->getType())) { |
452 | if (VectorType *SrcVTy = |
453 | dyn_cast<VectorType>(I->getOperand(0)->getType())) { |
454 | if (DstVTy->getNumElements() != SrcVTy->getNumElements()) |
455 | // Don't touch a bitcast between vectors of different element counts. |
456 | return nullptr; |
457 | } else |
458 | // Don't touch a scalar-to-vector bitcast. |
459 | return nullptr; |
460 | } else if (I->getOperand(0)->getType()->isVectorTy()) |
461 | // Don't touch a vector-to-scalar bitcast. |
462 | return nullptr; |
463 | |
464 | if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, KnownZero, |
465 | KnownOne, Depth + 1)) |
466 | return I; |
467 | assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?")((!(KnownZero & KnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(KnownZero & KnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 467, __PRETTY_FUNCTION__)); |
468 | break; |
469 | case Instruction::ZExt: { |
470 | // Compute the bits in the result that are not present in the input. |
471 | unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); |
472 | |
473 | DemandedMask = DemandedMask.trunc(SrcBitWidth); |
474 | KnownZero = KnownZero.trunc(SrcBitWidth); |
475 | KnownOne = KnownOne.trunc(SrcBitWidth); |
476 | if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMask, KnownZero, |
477 | KnownOne, Depth + 1)) |
478 | return I; |
479 | DemandedMask = DemandedMask.zext(BitWidth); |
480 | KnownZero = KnownZero.zext(BitWidth); |
481 | KnownOne = KnownOne.zext(BitWidth); |
482 | assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?")((!(KnownZero & KnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(KnownZero & KnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 482, __PRETTY_FUNCTION__)); |
483 | // The top bits are known to be zero. |
484 | KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); |
485 | break; |
486 | } |
487 | case Instruction::SExt: { |
488 | // Compute the bits in the result that are not present in the input. |
489 | unsigned SrcBitWidth =I->getOperand(0)->getType()->getScalarSizeInBits(); |
490 | |
491 | APInt InputDemandedBits = DemandedMask & |
492 | APInt::getLowBitsSet(BitWidth, SrcBitWidth); |
493 | |
494 | APInt NewBits(APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth)); |
495 | // If any of the sign extended bits are demanded, we know that the sign |
496 | // bit is demanded. |
497 | if ((NewBits & DemandedMask) != 0) |
498 | InputDemandedBits.setBit(SrcBitWidth-1); |
499 | |
500 | InputDemandedBits = InputDemandedBits.trunc(SrcBitWidth); |
501 | KnownZero = KnownZero.trunc(SrcBitWidth); |
502 | KnownOne = KnownOne.trunc(SrcBitWidth); |
503 | if (SimplifyDemandedBits(I->getOperandUse(0), InputDemandedBits, KnownZero, |
504 | KnownOne, Depth + 1)) |
505 | return I; |
506 | InputDemandedBits = InputDemandedBits.zext(BitWidth); |
507 | KnownZero = KnownZero.zext(BitWidth); |
508 | KnownOne = KnownOne.zext(BitWidth); |
509 | assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?")((!(KnownZero & KnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(KnownZero & KnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 509, __PRETTY_FUNCTION__)); |
510 | |
511 | // If the sign bit of the input is known set or clear, then we know the |
512 | // top bits of the result. |
513 | |
514 | // If the input sign bit is known zero, or if the NewBits are not demanded |
515 | // convert this into a zero extension. |
516 | if (KnownZero[SrcBitWidth-1] || (NewBits & ~DemandedMask) == NewBits) { |
517 | // Convert to ZExt cast |
518 | CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName()); |
519 | return InsertNewInstWith(NewCast, *I); |
520 | } else if (KnownOne[SrcBitWidth-1]) { // Input sign bit known set |
521 | KnownOne |= NewBits; |
522 | } |
523 | break; |
524 | } |
525 | case Instruction::Add: |
526 | case Instruction::Sub: { |
527 | /// If the high-bits of an ADD/SUB are not demanded, then we do not care |
528 | /// about the high bits of the operands. |
529 | unsigned NLZ = DemandedMask.countLeadingZeros(); |
530 | if (NLZ > 0) { |
531 | // Right fill the mask of bits for this ADD/SUB to demand the most |
532 | // significant bit and all those below it. |
533 | APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ)); |
534 | if (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps, |
535 | LHSKnownZero, LHSKnownOne, Depth + 1) || |
536 | ShrinkDemandedConstant(I, 1, DemandedFromOps) || |
537 | SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps, |
538 | LHSKnownZero, LHSKnownOne, Depth + 1)) { |
539 | // Disable the nsw and nuw flags here: We can no longer guarantee that |
540 | // we won't wrap after simplification. Removing the nsw/nuw flags is |
541 | // legal here because the top bit is not demanded. |
542 | BinaryOperator &BinOP = *cast<BinaryOperator>(I); |
543 | BinOP.setHasNoSignedWrap(false); |
544 | BinOP.setHasNoUnsignedWrap(false); |
545 | return I; |
546 | } |
547 | } |
548 | |
549 | // Otherwise just hand the add/sub off to computeKnownBits to fill in |
550 | // the known zeros and ones. |
551 | computeKnownBits(V, KnownZero, KnownOne, Depth, CxtI); |
552 | break; |
553 | } |
554 | case Instruction::Shl: |
555 | if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { |
556 | { |
557 | Value *VarX; ConstantInt *C1; |
558 | if (match(I->getOperand(0), m_Shr(m_Value(VarX), m_ConstantInt(C1)))) { |
559 | Instruction *Shr = cast<Instruction>(I->getOperand(0)); |
560 | Value *R = SimplifyShrShlDemandedBits(Shr, I, DemandedMask, |
561 | KnownZero, KnownOne); |
562 | if (R) |
563 | return R; |
564 | } |
565 | } |
566 | |
567 | uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); |
568 | APInt DemandedMaskIn(DemandedMask.lshr(ShiftAmt)); |
569 | |
570 | // If the shift is NUW/NSW, then it does demand the high bits. |
571 | ShlOperator *IOp = cast<ShlOperator>(I); |
572 | if (IOp->hasNoSignedWrap()) |
573 | DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1); |
574 | else if (IOp->hasNoUnsignedWrap()) |
575 | DemandedMaskIn |= APInt::getHighBitsSet(BitWidth, ShiftAmt); |
576 | |
577 | if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, KnownZero, |
578 | KnownOne, Depth + 1)) |
579 | return I; |
580 | assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?")((!(KnownZero & KnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(KnownZero & KnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 580, __PRETTY_FUNCTION__)); |
581 | KnownZero <<= ShiftAmt; |
582 | KnownOne <<= ShiftAmt; |
583 | // low bits known zero. |
584 | if (ShiftAmt) |
585 | KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); |
586 | } |
587 | break; |
588 | case Instruction::LShr: |
589 | // For a logical shift right |
590 | if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { |
591 | uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); |
592 | |
593 | // Unsigned shift right. |
594 | APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); |
595 | |
596 | // If the shift is exact, then it does demand the low bits (and knows that |
597 | // they are zero). |
598 | if (cast<LShrOperator>(I)->isExact()) |
599 | DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); |
600 | |
601 | if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, KnownZero, |
602 | KnownOne, Depth + 1)) |
603 | return I; |
604 | assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?")((!(KnownZero & KnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(KnownZero & KnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 604, __PRETTY_FUNCTION__)); |
605 | KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); |
606 | KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); |
607 | if (ShiftAmt) { |
608 | // Compute the new bits that are at the top now. |
609 | APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); |
610 | KnownZero |= HighBits; // high bits known zero. |
611 | } |
612 | } |
613 | break; |
614 | case Instruction::AShr: |
615 | // If this is an arithmetic shift right and only the low-bit is set, we can |
616 | // always convert this into a logical shr, even if the shift amount is |
617 | // variable. The low bit of the shift cannot be an input sign bit unless |
618 | // the shift amount is >= the size of the datatype, which is undefined. |
619 | if (DemandedMask == 1) { |
620 | // Perform the logical shift right. |
621 | Instruction *NewVal = BinaryOperator::CreateLShr( |
622 | I->getOperand(0), I->getOperand(1), I->getName()); |
623 | return InsertNewInstWith(NewVal, *I); |
624 | } |
625 | |
626 | // If the sign bit is the only bit demanded by this ashr, then there is no |
627 | // need to do it, the shift doesn't change the high bit. |
628 | if (DemandedMask.isSignBit()) |
629 | return I->getOperand(0); |
630 | |
631 | if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { |
632 | uint32_t ShiftAmt = SA->getLimitedValue(BitWidth-1); |
633 | |
634 | // Signed shift right. |
635 | APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt)); |
636 | // If any of the "high bits" are demanded, we should set the sign bit as |
637 | // demanded. |
638 | if (DemandedMask.countLeadingZeros() <= ShiftAmt) |
639 | DemandedMaskIn.setBit(BitWidth-1); |
640 | |
641 | // If the shift is exact, then it does demand the low bits (and knows that |
642 | // they are zero). |
643 | if (cast<AShrOperator>(I)->isExact()) |
644 | DemandedMaskIn |= APInt::getLowBitsSet(BitWidth, ShiftAmt); |
645 | |
646 | if (SimplifyDemandedBits(I->getOperandUse(0), DemandedMaskIn, KnownZero, |
647 | KnownOne, Depth + 1)) |
648 | return I; |
649 | assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?")((!(KnownZero & KnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(KnownZero & KnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 649, __PRETTY_FUNCTION__)); |
650 | // Compute the new bits that are at the top now. |
651 | APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); |
652 | KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); |
653 | KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); |
654 | |
655 | // Handle the sign bits. |
656 | APInt SignBit(APInt::getSignBit(BitWidth)); |
657 | // Adjust to where it is now in the mask. |
658 | SignBit = APIntOps::lshr(SignBit, ShiftAmt); |
659 | |
660 | // If the input sign bit is known to be zero, or if none of the top bits |
661 | // are demanded, turn this into an unsigned shift right. |
662 | if (BitWidth <= ShiftAmt || KnownZero[BitWidth-ShiftAmt-1] || |
663 | (HighBits & ~DemandedMask) == HighBits) { |
664 | // Perform the logical shift right. |
665 | BinaryOperator *NewVal = BinaryOperator::CreateLShr(I->getOperand(0), |
666 | SA, I->getName()); |
667 | NewVal->setIsExact(cast<BinaryOperator>(I)->isExact()); |
668 | return InsertNewInstWith(NewVal, *I); |
669 | } else if ((KnownOne & SignBit) != 0) { // New bits are known one. |
670 | KnownOne |= HighBits; |
671 | } |
672 | } |
673 | break; |
674 | case Instruction::SRem: |
675 | if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { |
676 | // X % -1 demands all the bits because we don't want to introduce |
677 | // INT_MIN % -1 (== undef) by accident. |
678 | if (Rem->isAllOnesValue()) |
679 | break; |
680 | APInt RA = Rem->getValue().abs(); |
681 | if (RA.isPowerOf2()) { |
682 | if (DemandedMask.ult(RA)) // srem won't affect demanded bits |
683 | return I->getOperand(0); |
684 | |
685 | APInt LowBits = RA - 1; |
686 | APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); |
687 | if (SimplifyDemandedBits(I->getOperandUse(0), Mask2, LHSKnownZero, |
688 | LHSKnownOne, Depth + 1)) |
689 | return I; |
690 | |
691 | // The low bits of LHS are unchanged by the srem. |
692 | KnownZero = LHSKnownZero & LowBits; |
693 | KnownOne = LHSKnownOne & LowBits; |
694 | |
695 | // If LHS is non-negative or has all low bits zero, then the upper bits |
696 | // are all zero. |
697 | if (LHSKnownZero[BitWidth-1] || ((LHSKnownZero & LowBits) == LowBits)) |
698 | KnownZero |= ~LowBits; |
699 | |
700 | // If LHS is negative and not all low bits are zero, then the upper bits |
701 | // are all one. |
702 | if (LHSKnownOne[BitWidth-1] && ((LHSKnownOne & LowBits) != 0)) |
703 | KnownOne |= ~LowBits; |
704 | |
705 | assert(!(KnownZero & KnownOne) && "Bits known to be one AND zero?")((!(KnownZero & KnownOne) && "Bits known to be one AND zero?" ) ? static_cast<void> (0) : __assert_fail ("!(KnownZero & KnownOne) && \"Bits known to be one AND zero?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 705, __PRETTY_FUNCTION__)); |
706 | } |
707 | } |
708 | |
709 | // The sign bit is the LHS's sign bit, except when the result of the |
710 | // remainder is zero. |
711 | if (DemandedMask.isNegative() && KnownZero.isNonNegative()) { |
712 | APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); |
713 | computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, Depth + 1, |
714 | CxtI); |
715 | // If it's known zero, our sign bit is also zero. |
716 | if (LHSKnownZero.isNegative()) |
717 | KnownZero.setBit(KnownZero.getBitWidth() - 1); |
718 | } |
719 | break; |
720 | case Instruction::URem: { |
721 | APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0); |
722 | APInt AllOnes = APInt::getAllOnesValue(BitWidth); |
723 | if (SimplifyDemandedBits(I->getOperandUse(0), AllOnes, KnownZero2, |
724 | KnownOne2, Depth + 1) || |
725 | SimplifyDemandedBits(I->getOperandUse(1), AllOnes, KnownZero2, |
726 | KnownOne2, Depth + 1)) |
727 | return I; |
728 | |
729 | unsigned Leaders = KnownZero2.countLeadingOnes(); |
730 | Leaders = std::max(Leaders, |
731 | KnownZero2.countLeadingOnes()); |
732 | KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask; |
733 | break; |
734 | } |
735 | case Instruction::Call: |
736 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { |
737 | switch (II->getIntrinsicID()) { |
738 | default: break; |
739 | case Intrinsic::bswap: { |
740 | // If the only bits demanded come from one byte of the bswap result, |
741 | // just shift the input byte into position to eliminate the bswap. |
742 | unsigned NLZ = DemandedMask.countLeadingZeros(); |
743 | unsigned NTZ = DemandedMask.countTrailingZeros(); |
744 | |
745 | // Round NTZ down to the next byte. If we have 11 trailing zeros, then |
746 | // we need all the bits down to bit 8. Likewise, round NLZ. If we |
747 | // have 14 leading zeros, round to 8. |
748 | NLZ &= ~7; |
749 | NTZ &= ~7; |
750 | // If we need exactly one byte, we can do this transformation. |
751 | if (BitWidth-NLZ-NTZ == 8) { |
752 | unsigned ResultBit = NTZ; |
753 | unsigned InputBit = BitWidth-NTZ-8; |
754 | |
755 | // Replace this with either a left or right shift to get the byte into |
756 | // the right place. |
757 | Instruction *NewVal; |
758 | if (InputBit > ResultBit) |
759 | NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0), |
760 | ConstantInt::get(I->getType(), InputBit-ResultBit)); |
761 | else |
762 | NewVal = BinaryOperator::CreateShl(II->getArgOperand(0), |
763 | ConstantInt::get(I->getType(), ResultBit-InputBit)); |
764 | NewVal->takeName(I); |
765 | return InsertNewInstWith(NewVal, *I); |
766 | } |
767 | |
768 | // TODO: Could compute known zero/one bits based on the input. |
769 | break; |
770 | } |
771 | case Intrinsic::x86_sse42_crc32_64_64: |
772 | KnownZero = APInt::getHighBitsSet(64, 32); |
773 | return nullptr; |
774 | } |
775 | } |
776 | computeKnownBits(V, KnownZero, KnownOne, Depth, CxtI); |
777 | break; |
778 | } |
779 | |
780 | // If the client is only demanding bits that we know, return the known |
781 | // constant. |
782 | if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) |
783 | return Constant::getIntegerValue(VTy, KnownOne); |
784 | return nullptr; |
785 | } |
786 | |
787 | /// Helper routine of SimplifyDemandedUseBits. It tries to simplify |
788 | /// "E1 = (X lsr C1) << C2", where the C1 and C2 are constant, into |
789 | /// "E2 = X << (C2 - C1)" or "E2 = X >> (C1 - C2)", depending on the sign |
790 | /// of "C2-C1". |
791 | /// |
792 | /// Suppose E1 and E2 are generally different in bits S={bm, bm+1, |
793 | /// ..., bn}, without considering the specific value X is holding. |
794 | /// This transformation is legal iff one of following conditions is hold: |
795 | /// 1) All the bit in S are 0, in this case E1 == E2. |
796 | /// 2) We don't care those bits in S, per the input DemandedMask. |
797 | /// 3) Combination of 1) and 2). Some bits in S are 0, and we don't care the |
798 | /// rest bits. |
799 | /// |
800 | /// Currently we only test condition 2). |
801 | /// |
802 | /// As with SimplifyDemandedUseBits, it returns NULL if the simplification was |
803 | /// not successful. |
804 | Value *InstCombiner::SimplifyShrShlDemandedBits(Instruction *Shr, |
805 | Instruction *Shl, APInt DemandedMask, APInt &KnownZero, APInt &KnownOne) { |
806 | |
807 | const APInt &ShlOp1 = cast<ConstantInt>(Shl->getOperand(1))->getValue(); |
808 | const APInt &ShrOp1 = cast<ConstantInt>(Shr->getOperand(1))->getValue(); |
809 | if (!ShlOp1 || !ShrOp1) |
810 | return nullptr; // Noop. |
811 | |
812 | Value *VarX = Shr->getOperand(0); |
813 | Type *Ty = VarX->getType(); |
814 | unsigned BitWidth = Ty->getIntegerBitWidth(); |
815 | if (ShlOp1.uge(BitWidth) || ShrOp1.uge(BitWidth)) |
816 | return nullptr; // Undef. |
817 | |
818 | unsigned ShlAmt = ShlOp1.getZExtValue(); |
819 | unsigned ShrAmt = ShrOp1.getZExtValue(); |
820 | |
821 | KnownOne.clearAllBits(); |
822 | KnownZero = APInt::getBitsSet(KnownZero.getBitWidth(), 0, ShlAmt-1); |
823 | KnownZero &= DemandedMask; |
824 | |
825 | APInt BitMask1(APInt::getAllOnesValue(BitWidth)); |
826 | APInt BitMask2(APInt::getAllOnesValue(BitWidth)); |
827 | |
828 | bool isLshr = (Shr->getOpcode() == Instruction::LShr); |
829 | BitMask1 = isLshr ? (BitMask1.lshr(ShrAmt) << ShlAmt) : |
830 | (BitMask1.ashr(ShrAmt) << ShlAmt); |
831 | |
832 | if (ShrAmt <= ShlAmt) { |
833 | BitMask2 <<= (ShlAmt - ShrAmt); |
834 | } else { |
835 | BitMask2 = isLshr ? BitMask2.lshr(ShrAmt - ShlAmt): |
836 | BitMask2.ashr(ShrAmt - ShlAmt); |
837 | } |
838 | |
839 | // Check if condition-2 (see the comment to this function) is satified. |
840 | if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) { |
841 | if (ShrAmt == ShlAmt) |
842 | return VarX; |
843 | |
844 | if (!Shr->hasOneUse()) |
845 | return nullptr; |
846 | |
847 | BinaryOperator *New; |
848 | if (ShrAmt < ShlAmt) { |
849 | Constant *Amt = ConstantInt::get(VarX->getType(), ShlAmt - ShrAmt); |
850 | New = BinaryOperator::CreateShl(VarX, Amt); |
851 | BinaryOperator *Orig = cast<BinaryOperator>(Shl); |
852 | New->setHasNoSignedWrap(Orig->hasNoSignedWrap()); |
853 | New->setHasNoUnsignedWrap(Orig->hasNoUnsignedWrap()); |
854 | } else { |
855 | Constant *Amt = ConstantInt::get(VarX->getType(), ShrAmt - ShlAmt); |
856 | New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) : |
857 | BinaryOperator::CreateAShr(VarX, Amt); |
858 | if (cast<BinaryOperator>(Shr)->isExact()) |
859 | New->setIsExact(true); |
860 | } |
861 | |
862 | return InsertNewInstWith(New, *Shl); |
863 | } |
864 | |
865 | return nullptr; |
866 | } |
867 | |
868 | /// SimplifyDemandedVectorElts - The specified value produces a vector with |
869 | /// any number of elements. DemandedElts contains the set of elements that are |
870 | /// actually used by the caller. This method analyzes which elements of the |
871 | /// operand are undef and returns that information in UndefElts. |
872 | /// |
873 | /// If the information about demanded elements can be used to simplify the |
874 | /// operation, the operation is simplified, then the resultant value is |
875 | /// returned. This returns null if no change was made. |
876 | Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, |
877 | APInt &UndefElts, |
878 | unsigned Depth) { |
879 | unsigned VWidth = cast<VectorType>(V->getType())->getNumElements(); |
880 | APInt EltMask(APInt::getAllOnesValue(VWidth)); |
881 | assert((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!")(((DemandedElts & ~EltMask) == 0 && "Invalid DemandedElts!" ) ? static_cast<void> (0) : __assert_fail ("(DemandedElts & ~EltMask) == 0 && \"Invalid DemandedElts!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 881, __PRETTY_FUNCTION__)); |
882 | |
883 | if (isa<UndefValue>(V)) { |
884 | // If the entire vector is undefined, just return this info. |
885 | UndefElts = EltMask; |
886 | return nullptr; |
887 | } |
888 | |
889 | if (DemandedElts == 0) { // If nothing is demanded, provide undef. |
890 | UndefElts = EltMask; |
891 | return UndefValue::get(V->getType()); |
892 | } |
893 | |
894 | UndefElts = 0; |
895 | |
896 | // Handle ConstantAggregateZero, ConstantVector, ConstantDataSequential. |
897 | if (Constant *C = dyn_cast<Constant>(V)) { |
898 | // Check if this is identity. If so, return 0 since we are not simplifying |
899 | // anything. |
900 | if (DemandedElts.isAllOnesValue()) |
901 | return nullptr; |
902 | |
903 | Type *EltTy = cast<VectorType>(V->getType())->getElementType(); |
904 | Constant *Undef = UndefValue::get(EltTy); |
905 | |
906 | SmallVector<Constant*, 16> Elts; |
907 | for (unsigned i = 0; i != VWidth; ++i) { |
908 | if (!DemandedElts[i]) { // If not demanded, set to undef. |
909 | Elts.push_back(Undef); |
910 | UndefElts.setBit(i); |
911 | continue; |
912 | } |
913 | |
914 | Constant *Elt = C->getAggregateElement(i); |
915 | if (!Elt) return nullptr; |
916 | |
917 | if (isa<UndefValue>(Elt)) { // Already undef. |
918 | Elts.push_back(Undef); |
919 | UndefElts.setBit(i); |
920 | } else { // Otherwise, defined. |
921 | Elts.push_back(Elt); |
922 | } |
923 | } |
924 | |
925 | // If we changed the constant, return it. |
926 | Constant *NewCV = ConstantVector::get(Elts); |
927 | return NewCV != C ? NewCV : nullptr; |
928 | } |
929 | |
930 | // Limit search depth. |
931 | if (Depth == 10) |
932 | return nullptr; |
933 | |
934 | // If multiple users are using the root value, proceed with |
935 | // simplification conservatively assuming that all elements |
936 | // are needed. |
937 | if (!V->hasOneUse()) { |
938 | // Quit if we find multiple users of a non-root value though. |
939 | // They'll be handled when it's their turn to be visited by |
940 | // the main instcombine process. |
941 | if (Depth != 0) |
942 | // TODO: Just compute the UndefElts information recursively. |
943 | return nullptr; |
944 | |
945 | // Conservatively assume that all elements are needed. |
946 | DemandedElts = EltMask; |
947 | } |
948 | |
949 | Instruction *I = dyn_cast<Instruction>(V); |
950 | if (!I) return nullptr; // Only analyze instructions. |
951 | |
952 | bool MadeChange = false; |
953 | APInt UndefElts2(VWidth, 0); |
954 | Value *TmpV; |
955 | switch (I->getOpcode()) { |
956 | default: break; |
957 | |
958 | case Instruction::InsertElement: { |
959 | // If this is a variable index, we don't know which element it overwrites. |
960 | // demand exactly the same input as we produce. |
961 | ConstantInt *Idx = dyn_cast<ConstantInt>(I->getOperand(2)); |
962 | if (!Idx) { |
963 | // Note that we can't propagate undef elt info, because we don't know |
964 | // which elt is getting updated. |
965 | TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, |
966 | UndefElts2, Depth + 1); |
967 | if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } |
968 | break; |
969 | } |
970 | |
971 | // If this is inserting an element that isn't demanded, remove this |
972 | // insertelement. |
973 | unsigned IdxNo = Idx->getZExtValue(); |
974 | if (IdxNo >= VWidth || !DemandedElts[IdxNo]) { |
975 | Worklist.Add(I); |
976 | return I->getOperand(0); |
977 | } |
978 | |
979 | // Otherwise, the element inserted overwrites whatever was there, so the |
980 | // input demanded set is simpler than the output set. |
981 | APInt DemandedElts2 = DemandedElts; |
982 | DemandedElts2.clearBit(IdxNo); |
983 | TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts2, |
984 | UndefElts, Depth + 1); |
985 | if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } |
986 | |
987 | // The inserted element is defined. |
988 | UndefElts.clearBit(IdxNo); |
989 | break; |
990 | } |
991 | case Instruction::ShuffleVector: { |
992 | ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(I); |
993 | uint64_t LHSVWidth = |
994 | cast<VectorType>(Shuffle->getOperand(0)->getType())->getNumElements(); |
995 | APInt LeftDemanded(LHSVWidth, 0), RightDemanded(LHSVWidth, 0); |
996 | for (unsigned i = 0; i < VWidth; i++) { |
997 | if (DemandedElts[i]) { |
998 | unsigned MaskVal = Shuffle->getMaskValue(i); |
999 | if (MaskVal != -1u) { |
1000 | assert(MaskVal < LHSVWidth * 2 &&((MaskVal < LHSVWidth * 2 && "shufflevector mask index out of range!" ) ? static_cast<void> (0) : __assert_fail ("MaskVal < LHSVWidth * 2 && \"shufflevector mask index out of range!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 1001, __PRETTY_FUNCTION__)) |
1001 | "shufflevector mask index out of range!")((MaskVal < LHSVWidth * 2 && "shufflevector mask index out of range!" ) ? static_cast<void> (0) : __assert_fail ("MaskVal < LHSVWidth * 2 && \"shufflevector mask index out of range!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 1001, __PRETTY_FUNCTION__)); |
1002 | if (MaskVal < LHSVWidth) |
1003 | LeftDemanded.setBit(MaskVal); |
1004 | else |
1005 | RightDemanded.setBit(MaskVal - LHSVWidth); |
1006 | } |
1007 | } |
1008 | } |
1009 | |
1010 | APInt UndefElts4(LHSVWidth, 0); |
1011 | TmpV = SimplifyDemandedVectorElts(I->getOperand(0), LeftDemanded, |
1012 | UndefElts4, Depth + 1); |
1013 | if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } |
1014 | |
1015 | APInt UndefElts3(LHSVWidth, 0); |
1016 | TmpV = SimplifyDemandedVectorElts(I->getOperand(1), RightDemanded, |
1017 | UndefElts3, Depth + 1); |
1018 | if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } |
1019 | |
1020 | bool NewUndefElts = false; |
1021 | for (unsigned i = 0; i < VWidth; i++) { |
1022 | unsigned MaskVal = Shuffle->getMaskValue(i); |
1023 | if (MaskVal == -1u) { |
1024 | UndefElts.setBit(i); |
1025 | } else if (!DemandedElts[i]) { |
1026 | NewUndefElts = true; |
1027 | UndefElts.setBit(i); |
1028 | } else if (MaskVal < LHSVWidth) { |
1029 | if (UndefElts4[MaskVal]) { |
1030 | NewUndefElts = true; |
1031 | UndefElts.setBit(i); |
1032 | } |
1033 | } else { |
1034 | if (UndefElts3[MaskVal - LHSVWidth]) { |
1035 | NewUndefElts = true; |
1036 | UndefElts.setBit(i); |
1037 | } |
1038 | } |
1039 | } |
1040 | |
1041 | if (NewUndefElts) { |
1042 | // Add additional discovered undefs. |
1043 | SmallVector<Constant*, 16> Elts; |
1044 | for (unsigned i = 0; i < VWidth; ++i) { |
1045 | if (UndefElts[i]) |
1046 | Elts.push_back(UndefValue::get(Type::getInt32Ty(I->getContext()))); |
1047 | else |
1048 | Elts.push_back(ConstantInt::get(Type::getInt32Ty(I->getContext()), |
1049 | Shuffle->getMaskValue(i))); |
1050 | } |
1051 | I->setOperand(2, ConstantVector::get(Elts)); |
1052 | MadeChange = true; |
1053 | } |
1054 | break; |
1055 | } |
1056 | case Instruction::Select: { |
1057 | APInt LeftDemanded(DemandedElts), RightDemanded(DemandedElts); |
1058 | if (ConstantVector* CV = dyn_cast<ConstantVector>(I->getOperand(0))) { |
1059 | for (unsigned i = 0; i < VWidth; i++) { |
1060 | if (CV->getAggregateElement(i)->isNullValue()) |
1061 | LeftDemanded.clearBit(i); |
1062 | else |
1063 | RightDemanded.clearBit(i); |
1064 | } |
1065 | } |
1066 | |
1067 | TmpV = SimplifyDemandedVectorElts(I->getOperand(1), LeftDemanded, UndefElts, |
1068 | Depth + 1); |
1069 | if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } |
1070 | |
1071 | TmpV = SimplifyDemandedVectorElts(I->getOperand(2), RightDemanded, |
1072 | UndefElts2, Depth + 1); |
1073 | if (TmpV) { I->setOperand(2, TmpV); MadeChange = true; } |
1074 | |
1075 | // Output elements are undefined if both are undefined. |
1076 | UndefElts &= UndefElts2; |
1077 | break; |
1078 | } |
1079 | case Instruction::BitCast: { |
1080 | // Vector->vector casts only. |
1081 | VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType()); |
1082 | if (!VTy) break; |
1083 | unsigned InVWidth = VTy->getNumElements(); |
1084 | APInt InputDemandedElts(InVWidth, 0); |
1085 | unsigned Ratio; |
1086 | |
1087 | if (VWidth == InVWidth) { |
1088 | // If we are converting from <4 x i32> -> <4 x f32>, we demand the same |
1089 | // elements as are demanded of us. |
1090 | Ratio = 1; |
Value stored to 'Ratio' is never read | |
1091 | InputDemandedElts = DemandedElts; |
1092 | } else if (VWidth > InVWidth) { |
1093 | // Untested so far. |
1094 | break; |
1095 | |
1096 | // If there are more elements in the result than there are in the source, |
1097 | // then an input element is live if any of the corresponding output |
1098 | // elements are live. |
1099 | Ratio = VWidth/InVWidth; |
1100 | for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) { |
1101 | if (DemandedElts[OutIdx]) |
1102 | InputDemandedElts.setBit(OutIdx/Ratio); |
1103 | } |
1104 | } else { |
1105 | // Untested so far. |
1106 | break; |
1107 | |
1108 | // If there are more elements in the source than there are in the result, |
1109 | // then an input element is live if the corresponding output element is |
1110 | // live. |
1111 | Ratio = InVWidth/VWidth; |
1112 | for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) |
1113 | if (DemandedElts[InIdx/Ratio]) |
1114 | InputDemandedElts.setBit(InIdx); |
1115 | } |
1116 | |
1117 | // div/rem demand all inputs, because they don't want divide by zero. |
1118 | TmpV = SimplifyDemandedVectorElts(I->getOperand(0), InputDemandedElts, |
1119 | UndefElts2, Depth + 1); |
1120 | if (TmpV) { |
1121 | I->setOperand(0, TmpV); |
1122 | MadeChange = true; |
1123 | } |
1124 | |
1125 | UndefElts = UndefElts2; |
1126 | if (VWidth > InVWidth) { |
1127 | llvm_unreachable("Unimp")::llvm::llvm_unreachable_internal("Unimp", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 1127); |
1128 | // If there are more elements in the result than there are in the source, |
1129 | // then an output element is undef if the corresponding input element is |
1130 | // undef. |
1131 | for (unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) |
1132 | if (UndefElts2[OutIdx/Ratio]) |
1133 | UndefElts.setBit(OutIdx); |
1134 | } else if (VWidth < InVWidth) { |
1135 | llvm_unreachable("Unimp")::llvm::llvm_unreachable_internal("Unimp", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 1135); |
1136 | // If there are more elements in the source than there are in the result, |
1137 | // then a result element is undef if all of the corresponding input |
1138 | // elements are undef. |
1139 | UndefElts = ~0ULL >> (64-VWidth); // Start out all undef. |
1140 | for (unsigned InIdx = 0; InIdx != InVWidth; ++InIdx) |
1141 | if (!UndefElts2[InIdx]) // Not undef? |
1142 | UndefElts.clearBit(InIdx/Ratio); // Clear undef bit. |
1143 | } |
1144 | break; |
1145 | } |
1146 | case Instruction::And: |
1147 | case Instruction::Or: |
1148 | case Instruction::Xor: |
1149 | case Instruction::Add: |
1150 | case Instruction::Sub: |
1151 | case Instruction::Mul: |
1152 | // div/rem demand all inputs, because they don't want divide by zero. |
1153 | TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, UndefElts, |
1154 | Depth + 1); |
1155 | if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } |
1156 | TmpV = SimplifyDemandedVectorElts(I->getOperand(1), DemandedElts, |
1157 | UndefElts2, Depth + 1); |
1158 | if (TmpV) { I->setOperand(1, TmpV); MadeChange = true; } |
1159 | |
1160 | // Output elements are undefined if both are undefined. Consider things |
1161 | // like undef&0. The result is known zero, not undef. |
1162 | UndefElts &= UndefElts2; |
1163 | break; |
1164 | case Instruction::FPTrunc: |
1165 | case Instruction::FPExt: |
1166 | TmpV = SimplifyDemandedVectorElts(I->getOperand(0), DemandedElts, UndefElts, |
1167 | Depth + 1); |
1168 | if (TmpV) { I->setOperand(0, TmpV); MadeChange = true; } |
1169 | break; |
1170 | |
1171 | case Instruction::Call: { |
1172 | IntrinsicInst *II = dyn_cast<IntrinsicInst>(I); |
1173 | if (!II) break; |
1174 | switch (II->getIntrinsicID()) { |
1175 | default: break; |
1176 | |
1177 | // Binary vector operations that work column-wise. A dest element is a |
1178 | // function of the corresponding input elements from the two inputs. |
1179 | case Intrinsic::x86_sse_sub_ss: |
1180 | case Intrinsic::x86_sse_mul_ss: |
1181 | case Intrinsic::x86_sse_min_ss: |
1182 | case Intrinsic::x86_sse_max_ss: |
1183 | case Intrinsic::x86_sse2_sub_sd: |
1184 | case Intrinsic::x86_sse2_mul_sd: |
1185 | case Intrinsic::x86_sse2_min_sd: |
1186 | case Intrinsic::x86_sse2_max_sd: |
1187 | TmpV = SimplifyDemandedVectorElts(II->getArgOperand(0), DemandedElts, |
1188 | UndefElts, Depth + 1); |
1189 | if (TmpV) { II->setArgOperand(0, TmpV); MadeChange = true; } |
1190 | TmpV = SimplifyDemandedVectorElts(II->getArgOperand(1), DemandedElts, |
1191 | UndefElts2, Depth + 1); |
1192 | if (TmpV) { II->setArgOperand(1, TmpV); MadeChange = true; } |
1193 | |
1194 | // If only the low elt is demanded and this is a scalarizable intrinsic, |
1195 | // scalarize it now. |
1196 | if (DemandedElts == 1) { |
1197 | switch (II->getIntrinsicID()) { |
1198 | default: break; |
1199 | case Intrinsic::x86_sse_sub_ss: |
1200 | case Intrinsic::x86_sse_mul_ss: |
1201 | case Intrinsic::x86_sse2_sub_sd: |
1202 | case Intrinsic::x86_sse2_mul_sd: |
1203 | // TODO: Lower MIN/MAX/ABS/etc |
1204 | Value *LHS = II->getArgOperand(0); |
1205 | Value *RHS = II->getArgOperand(1); |
1206 | // Extract the element as scalars. |
1207 | LHS = InsertNewInstWith(ExtractElementInst::Create(LHS, |
1208 | ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); |
1209 | RHS = InsertNewInstWith(ExtractElementInst::Create(RHS, |
1210 | ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U)), *II); |
1211 | |
1212 | switch (II->getIntrinsicID()) { |
1213 | default: llvm_unreachable("Case stmts out of sync!")::llvm::llvm_unreachable_internal("Case stmts out of sync!", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp" , 1213); |
1214 | case Intrinsic::x86_sse_sub_ss: |
1215 | case Intrinsic::x86_sse2_sub_sd: |
1216 | TmpV = InsertNewInstWith(BinaryOperator::CreateFSub(LHS, RHS, |
1217 | II->getName()), *II); |
1218 | break; |
1219 | case Intrinsic::x86_sse_mul_ss: |
1220 | case Intrinsic::x86_sse2_mul_sd: |
1221 | TmpV = InsertNewInstWith(BinaryOperator::CreateFMul(LHS, RHS, |
1222 | II->getName()), *II); |
1223 | break; |
1224 | } |
1225 | |
1226 | Instruction *New = |
1227 | InsertElementInst::Create( |
1228 | UndefValue::get(II->getType()), TmpV, |
1229 | ConstantInt::get(Type::getInt32Ty(I->getContext()), 0U, false), |
1230 | II->getName()); |
1231 | InsertNewInstWith(New, *II); |
1232 | return New; |
1233 | } |
1234 | } |
1235 | |
1236 | // Output elements are undefined if both are undefined. Consider things |
1237 | // like undef&0. The result is known zero, not undef. |
1238 | UndefElts &= UndefElts2; |
1239 | break; |
1240 | } |
1241 | break; |
1242 | } |
1243 | } |
1244 | return MadeChange ? I : nullptr; |
1245 | } |