1
//===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
3
// The LLVM Compiler Infrastructure
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
8
//===----------------------------------------------------------------------===//
10
// This file implements routines for folding instructions into simpler forms
11
// that do not require creating new instructions. For example, this does
12
// constant folding, and can handle identities like (X&0)->0.
14
//===----------------------------------------------------------------------===//
16
#include "llvm/Analysis/InstructionSimplify.h"
17
#include "llvm/Analysis/ConstantFolding.h"
18
#include "llvm/Support/ValueHandle.h"
19
#include "llvm/Instructions.h"
20
#include "llvm/Support/PatternMatch.h"
22
using namespace llvm::PatternMatch;
24
/// SimplifyAddInst - Given operands for an Add, see if we can
25
/// fold the result. If not, this returns null.
26
Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
27
const TargetData *TD) {
28
if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
29
if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
30
Constant *Ops[] = { CLHS, CRHS };
31
return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(),
35
// Canonicalize the constant to the RHS.
39
if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
41
if (isa<UndefValue>(Op1C))
45
if (Op1C->isNullValue())
49
// FIXME: Could pull several more out of instcombine.
53
/// SimplifyAndInst - Given operands for an And, see if we can
54
/// fold the result. If not, this returns null.
55
Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) {
56
if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
57
if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
58
Constant *Ops[] = { CLHS, CRHS };
59
return ConstantFoldInstOperands(Instruction::And, CLHS->getType(),
63
// Canonicalize the constant to the RHS.
68
if (isa<UndefValue>(Op1))
69
return Constant::getNullValue(Op0->getType());
76
if (isa<ConstantAggregateZero>(Op1))
80
if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
81
if (CP->isAllOnesValue())
84
if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
89
if (Op1CI->isAllOnesValue())
93
// A & ~A = ~A & A = 0
95
if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
96
(match(Op1, m_Not(m_Value(A))) && A == Op0))
97
return Constant::getNullValue(Op0->getType());
100
if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
101
(A == Op1 || B == Op1))
105
if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
106
(A == Op0 || B == Op0))
112
/// SimplifyOrInst - Given operands for an Or, see if we can
113
/// fold the result. If not, this returns null.
114
Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) {
115
if (Constant *CLHS = dyn_cast<Constant>(Op0)) {
116
if (Constant *CRHS = dyn_cast<Constant>(Op1)) {
117
Constant *Ops[] = { CLHS, CRHS };
118
return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(),
122
// Canonicalize the constant to the RHS.
127
if (isa<UndefValue>(Op1))
128
return Constant::getAllOnesValue(Op0->getType());
135
if (isa<ConstantAggregateZero>(Op1))
138
// X | <-1,-1> = <-1,-1>
139
if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1))
140
if (CP->isAllOnesValue())
143
if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) {
148
if (Op1CI->isAllOnesValue())
152
// A | ~A = ~A | A = -1
154
if ((match(Op0, m_Not(m_Value(A))) && A == Op1) ||
155
(match(Op1, m_Not(m_Value(A))) && A == Op0))
156
return Constant::getAllOnesValue(Op0->getType());
159
if (match(Op0, m_And(m_Value(A), m_Value(B))) &&
160
(A == Op1 || B == Op1))
164
if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
165
(A == Op0 || B == Op0))
172
static const Type *GetCompareTy(Value *Op) {
173
return CmpInst::makeCmpResultType(Op->getType());
177
/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
178
/// fold the result. If not, this returns null.
179
Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
180
const TargetData *TD) {
181
CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
182
assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
184
if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
185
if (Constant *CRHS = dyn_cast<Constant>(RHS))
186
return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
188
// If we have a constant, make sure it is on the RHS.
190
Pred = CmpInst::getSwappedPredicate(Pred);
193
// ITy - This is the return type of the compare we're considering.
194
const Type *ITy = GetCompareTy(LHS);
196
// icmp X, X -> true/false
197
// X icmp undef -> true/false. For example, icmp ugt %X, undef -> false
198
// because X could be 0.
199
if (LHS == RHS || isa<UndefValue>(RHS))
200
return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
202
// icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
203
// addresses never equal each other! We already know that Op0 != Op1.
204
if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) ||
205
isa<ConstantPointerNull>(LHS)) &&
206
(isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
207
isa<ConstantPointerNull>(RHS)))
208
return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
210
// See if we are doing a comparison with a constant.
211
if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
212
// If we have an icmp le or icmp ge instruction, turn it into the
213
// appropriate icmp lt or icmp gt instruction. This allows us to rely on
214
// them being folded in the code below.
217
case ICmpInst::ICMP_ULE:
218
if (CI->isMaxValue(false)) // A <=u MAX -> TRUE
219
return ConstantInt::getTrue(CI->getContext());
221
case ICmpInst::ICMP_SLE:
222
if (CI->isMaxValue(true)) // A <=s MAX -> TRUE
223
return ConstantInt::getTrue(CI->getContext());
225
case ICmpInst::ICMP_UGE:
226
if (CI->isMinValue(false)) // A >=u MIN -> TRUE
227
return ConstantInt::getTrue(CI->getContext());
229
case ICmpInst::ICMP_SGE:
230
if (CI->isMinValue(true)) // A >=s MIN -> TRUE
231
return ConstantInt::getTrue(CI->getContext());
240
/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
241
/// fold the result. If not, this returns null.
242
Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
243
const TargetData *TD) {
244
CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
245
assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!");
247
if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
248
if (Constant *CRHS = dyn_cast<Constant>(RHS))
249
return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD);
251
// If we have a constant, make sure it is on the RHS.
253
Pred = CmpInst::getSwappedPredicate(Pred);
256
// Fold trivial predicates.
257
if (Pred == FCmpInst::FCMP_FALSE)
258
return ConstantInt::get(GetCompareTy(LHS), 0);
259
if (Pred == FCmpInst::FCMP_TRUE)
260
return ConstantInt::get(GetCompareTy(LHS), 1);
262
if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef
263
return UndefValue::get(GetCompareTy(LHS));
265
// fcmp x,x -> true/false. Not all compares are foldable.
267
if (CmpInst::isTrueWhenEqual(Pred))
268
return ConstantInt::get(GetCompareTy(LHS), 1);
269
if (CmpInst::isFalseWhenEqual(Pred))
270
return ConstantInt::get(GetCompareTy(LHS), 0);
273
// Handle fcmp with constant RHS
274
if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
275
// If the constant is a nan, see if we can fold the comparison based on it.
276
if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
277
if (CFP->getValueAPF().isNaN()) {
278
if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo"
279
return ConstantInt::getFalse(CFP->getContext());
280
assert(FCmpInst::isUnordered(Pred) &&
281
"Comparison must be either ordered or unordered!");
282
// True if unordered.
283
return ConstantInt::getTrue(CFP->getContext());
285
// Check whether the constant is an infinity.
286
if (CFP->getValueAPF().isInfinity()) {
287
if (CFP->getValueAPF().isNegative()) {
289
case FCmpInst::FCMP_OLT:
290
// No value is ordered and less than negative infinity.
291
return ConstantInt::getFalse(CFP->getContext());
292
case FCmpInst::FCMP_UGE:
293
// All values are unordered with or at least negative infinity.
294
return ConstantInt::getTrue(CFP->getContext());
300
case FCmpInst::FCMP_OGT:
301
// No value is ordered and greater than infinity.
302
return ConstantInt::getFalse(CFP->getContext());
303
case FCmpInst::FCMP_ULE:
304
// All values are unordered with and at most infinity.
305
return ConstantInt::getTrue(CFP->getContext());
317
/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
318
/// the result. If not, this returns null.
319
Value *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal,
320
const TargetData *TD) {
321
// select true, X, Y -> X
322
// select false, X, Y -> Y
323
if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal))
324
return CB->getZExtValue() ? TrueVal : FalseVal;
326
// select C, X, X -> X
327
if (TrueVal == FalseVal)
330
if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
332
if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
334
if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
335
if (isa<Constant>(TrueVal))
346
/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
347
/// fold the result. If not, this returns null.
348
Value *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps,
349
const TargetData *TD) {
350
// getelementptr P -> P.
355
//if (isa<UndefValue>(Ops[0]))
356
// return UndefValue::get(GEP.getType());
358
// getelementptr P, 0 -> P.
360
if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1]))
364
// Check to see if this is constant foldable.
365
for (unsigned i = 0; i != NumOps; ++i)
366
if (!isa<Constant>(Ops[i]))
369
return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]),
370
(Constant *const*)Ops+1, NumOps-1);
374
//=== Helper functions for higher up the class hierarchy.
376
/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
377
/// fold the result. If not, this returns null.
378
Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
379
const TargetData *TD) {
381
case Instruction::And: return SimplifyAndInst(LHS, RHS, TD);
382
case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD);
384
if (Constant *CLHS = dyn_cast<Constant>(LHS))
385
if (Constant *CRHS = dyn_cast<Constant>(RHS)) {
386
Constant *COps[] = {CLHS, CRHS};
387
return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD);
393
/// SimplifyCmpInst - Given operands for a CmpInst, see if we can
395
Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
396
const TargetData *TD) {
397
if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate))
398
return SimplifyICmpInst(Predicate, LHS, RHS, TD);
399
return SimplifyFCmpInst(Predicate, LHS, RHS, TD);
403
/// SimplifyInstruction - See if we can compute a simplified version of this
404
/// instruction. If not, this returns null.
405
Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD) {
406
switch (I->getOpcode()) {
408
return ConstantFoldInstruction(I, TD);
409
case Instruction::Add:
410
return SimplifyAddInst(I->getOperand(0), I->getOperand(1),
411
cast<BinaryOperator>(I)->hasNoSignedWrap(),
412
cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD);
413
case Instruction::And:
414
return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD);
415
case Instruction::Or:
416
return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD);
417
case Instruction::ICmp:
418
return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(),
419
I->getOperand(0), I->getOperand(1), TD);
420
case Instruction::FCmp:
421
return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(),
422
I->getOperand(0), I->getOperand(1), TD);
423
case Instruction::Select:
424
return SimplifySelectInst(I->getOperand(0), I->getOperand(1),
425
I->getOperand(2), TD);
426
case Instruction::GetElementPtr: {
427
SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
428
return SimplifyGEPInst(&Ops[0], Ops.size(), TD);
433
/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
434
/// delete the From instruction. In addition to a basic RAUW, this does a
435
/// recursive simplification of the newly formed instructions. This catches
436
/// things where one simplification exposes other opportunities. This only
437
/// simplifies and deletes scalar operations, it does not change the CFG.
439
void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
440
const TargetData *TD) {
441
assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!");
443
// FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that
444
// we can know if it gets deleted out from under us or replaced in a
445
// recursive simplification.
446
WeakVH FromHandle(From);
449
while (!From->use_empty()) {
450
// Update the instruction to use the new value.
451
Use &TheUse = From->use_begin().getUse();
452
Instruction *User = cast<Instruction>(TheUse.getUser());
455
// Check to see if the instruction can be folded due to the operand
456
// replacement. For example changing (or X, Y) into (or X, -1) can replace
458
Value *SimplifiedVal;
460
// Sanity check to make sure 'User' doesn't dangle across
461
// SimplifyInstruction.
462
AssertingVH<> UserHandle(User);
464
SimplifiedVal = SimplifyInstruction(User, TD);
465
if (SimplifiedVal == 0) continue;
468
// Recursively simplify this user to the new value.
469
ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD);
470
From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
473
assert(ToHandle && "To value deleted by recursive simplification?");
475
// If the recursive simplification ended up revisiting and deleting
476
// 'From' then we're done.
481
// If 'From' has value handles referring to it, do a real RAUW to update them.
482
From->replaceAllUsesWith(To);
484
From->eraseFromParent();