InstructionSimplify.cpp revision 552008946530e01efdad15044e1f621883d14a3a
19f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner//===- InstructionSimplify.cpp - Fold instruction operands ----------------===// 29f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 39f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// The LLVM Compiler Infrastructure 49f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 59f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// This file is distributed under the University of Illinois Open Source 69f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// License. See LICENSE.TXT for details. 79f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 89f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner//===----------------------------------------------------------------------===// 99f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 109f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// This file implements routines for folding instructions into simpler forms 119f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// that do not require creating new instructions. For example, this does 129f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// constant folding, and can handle identities like (X&0)->0. 139f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 149f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner//===----------------------------------------------------------------------===// 159f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 169f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/InstructionSimplify.h" 179f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/ConstantFolding.h" 1840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner#include "llvm/Support/ValueHandle.h" 199f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Instructions.h" 20d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner#include "llvm/Support/PatternMatch.h" 219f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattnerusing namespace llvm; 22d06094f0682f2ede03caff4892b1a57469896d48Chris Lattnerusing namespace llvm::PatternMatch; 239f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 24bc68d71d2a858c748dbb1539201010bbc5758dc6Duncan Sands#define MaxRecursionDepth 3 25a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 26a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 27a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned); 28a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 29a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned); 30a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 31b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadBinOpOverSelect - In the case of a binary operation with a select 32b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// instruction as an operand, try to simplify the binop by seeing whether 33b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// evaluating it on both branches of the select results in the same value. 34b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// Returns the common value if so, otherwise returns null. 35b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 36a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD, unsigned MaxRecurse) { 37b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI; 38b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (isa<SelectInst>(LHS)) { 39b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(LHS); 40b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 41b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 42b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(RHS); 43b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 44b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 45b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Evaluate the BinOp on the true and false branches of the select. 46b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *TV; 47b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *FV; 48b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (SI == LHS) { 49a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, MaxRecurse); 50a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, MaxRecurse); 51b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 52a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, MaxRecurse); 53a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, MaxRecurse); 54b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 55b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 56b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they simplified to the same value, then return the common value. 57b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they both failed to simplify then return null. 58b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == FV) 59b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 60b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 61b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified to undef, return the other one. 62b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV && isa<UndefValue>(TV)) 63b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return FV; 64b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (FV && isa<UndefValue>(FV)) 65b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 66b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 67b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If applying the operation did not change the true and false select values, 68b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // then the result of the binop is the select itself. 69b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 70b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return SI; 71b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 72b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified and the other did not, and the simplified 73b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // value is equal to the unsimplified one, return the simplified value. 74b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // For example, select (cond, X, X & Z) & Z -> X & Z. 75b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if ((FV && !TV) || (TV && !FV)) { 76b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Check that the simplified value has the form "X op Y" where "op" is the 77b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // same as the original operation. 78b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 79b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified && Simplified->getOpcode() == Opcode) { 80b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 81b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // We already know that "op" is the same as for the simplified value. See 82b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // if the operands match too. If so, return the simplified value. 83b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 84b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 85b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 86b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->getOperand(0) == UnsimplifiedLHS && 87b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedRHS) 88b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 89b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->isCommutative() && 90b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedLHS && 91b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(0) == UnsimplifiedRHS) 92b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 93b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 94b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 95b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 96b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 97b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 98b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 99b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 100b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// try to simplify the comparison by seeing whether both branches of the select 101b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// result in the same value. Returns the common value if so, otherwise returns 102b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// null. 103b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 104a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *RHS, const TargetData *TD, 105a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 106b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Make sure the select is on the LHS. 107b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (!isa<SelectInst>(LHS)) { 108b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands std::swap(LHS, RHS); 109b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 110b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 111b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 112b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI = cast<SelectInst>(LHS); 113b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 114b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Now that we have "cmp select(cond, TV, FV), RHS", analyse it. 115b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Does "cmp TV, RHS" simplify? 116a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, 117a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 118b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! Does "cmp FV, RHS" simplify? 119a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, 120a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 121b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! If they simplified to the same value, then use it as the 122b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // result of the original comparison. 123b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TCmp == FCmp) 124b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TCmp; 125b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 126b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 127b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 128a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 129a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 130a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// it on the incoming phi values yields the same result for every value. If so 131a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// returns the common value, otherwise returns null. 132a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 133a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD, unsigned MaxRecurse) { 134a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI; 135a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (isa<PHINode>(LHS)) { 136a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(LHS); 137a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } else { 138a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 139a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(RHS); 140a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 141a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 142a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 143a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 144a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 145552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 146552008946530e01efdad15044e1f621883d14a3aDuncan Sands // If the incoming value is the phi node itself, it can be safely skipped. 147552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 148a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *V = PI == LHS ? 149552008946530e01efdad15044e1f621883d14a3aDuncan Sands SimplifyBinOp(Opcode, Incoming, RHS, TD, MaxRecurse) : 150552008946530e01efdad15044e1f621883d14a3aDuncan Sands SimplifyBinOp(Opcode, LHS, Incoming, TD, MaxRecurse); 151a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 152a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 153a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 154a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 155a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 156a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 157a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 158a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 159a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 160a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 161a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 162a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// try to simplify the comparison by seeing whether comparing with all of the 163a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// incoming phi values yields the same result every time. If so returns the 164a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// common result, otherwise returns null. 165a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 166a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD, unsigned MaxRecurse) { 167a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Make sure the phi is on the LHS. 168a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!isa<PHINode>(LHS)) { 169a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands std::swap(LHS, RHS); 170a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 171a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 172a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 173a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI = cast<PHINode>(LHS); 174a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 175a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 176a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 177a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 178552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 179552008946530e01efdad15044e1f621883d14a3aDuncan Sands // If the incoming value is the phi node itself, it can be safely skipped. 180552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 181552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, MaxRecurse); 182a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 183a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 184a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 185a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 186a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 187a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 188a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 189a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 190a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 191a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1928aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 193d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 1948aee8efc0c2e387faa7dae39fdf613a22889b566Chris LattnerValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 195d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner const TargetData *TD) { 196d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 197d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 198d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 1998aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 2008aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Ops, 2, TD); 2018aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 20212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2038aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // Canonicalize the constant to the RHS. 2048aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner std::swap(Op0, Op1); 2058aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 20612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2078aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 2088aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // X + undef -> undef 2098aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (isa<UndefValue>(Op1C)) 2108aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return Op1C; 21112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2128aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // X + 0 --> X 2138aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Op1C->isNullValue()) 2148aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return Op0; 2158aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 21612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2178aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // FIXME: Could pull several more out of instcombine. 2188aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return 0; 2198aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner} 2208aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner 2218aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 2228aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// fold the result. If not, this returns null. 223a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 224a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 2258aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 2268aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 2278aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 228d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 229d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 230d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 23112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 232d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 233d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 234d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 23512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 236d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & undef -> 0 237d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 238d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 23912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 240d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & X = X 241d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 242d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 24312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 244d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & <0,0> = <0,0> 245d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<ConstantAggregateZero>(Op1)) 246d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 24712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 248d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & <-1,-1> = X 249d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) 250d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (CP->isAllOnesValue()) 251d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 25212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 253d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { 254d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & 0 = 0 255d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op1CI->isZero()) 256d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1CI; 257d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & -1 = X 258d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op1CI->isAllOnesValue()) 259d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 260d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 26112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 262d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & ~A = ~A & A = 0 263d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Value *A, *B; 26470ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 26570ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 266d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 26712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 268d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A | ?) & A = A 269d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 270d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 271d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 27212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 273d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & (A | ?) = A 274d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 275d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 276d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 27712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2786844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // (A & B) & A -> A & B 2796844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op0, m_And(m_Value(A), m_Value(B))) && 2806844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op1 || B == Op1)) 2816844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op0; 2826844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 2836844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // A & (A & B) -> A & B 2846844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op1, m_And(m_Value(A), m_Value(B))) && 2856844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op0 || B == Op0)) 2866844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op1; 2876844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 288b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 289b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 290a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 291a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, 292a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 293a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 294a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 295a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 296a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 297a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 298a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, 299a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 300b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 301b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 302d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 303d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 3049f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 305a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD) { 306a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return ::SimplifyAndInst(Op0, Op1, TD, MaxRecursionDepth); 307a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 308a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 309d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 3109f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner/// fold the result. If not, this returns null. 311a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 312a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 313d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 314d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 315d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 316d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 317d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 318d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 31912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 320d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 321d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 322d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 32312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 324d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | undef -> -1 325d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 326d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 32712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 328d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | X = X 329d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 330d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 331d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 332d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | <0,0> = X 333d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<ConstantAggregateZero>(Op1)) 334d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 33512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 336d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | <-1,-1> = <-1,-1> 337d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) 33812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands if (CP->isAllOnesValue()) 339d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 34012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 341d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1)) { 342d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | 0 = X 343d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op1CI->isZero()) 344d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 345d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | -1 = -1 346d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op1CI->isAllOnesValue()) 347d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1CI; 348d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 34912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 350d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | ~A = ~A | A = -1 351d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Value *A, *B; 35270ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 35370ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 354d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 35512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 356d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A & ?) | A = A 357d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(B))) && 358d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 359d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 36012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 361d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | (A & ?) = A 362d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_And(m_Value(A), m_Value(B))) && 363d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 364d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 36512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 3666844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // (A | B) | A -> A | B 3676844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 3686844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op1 || B == Op1)) 3696844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op0; 3706844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 3716844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // A | (A | B) -> A | B 3726844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 3736844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op0 || B == Op0)) 3746844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op1; 3756844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 376b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 377b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 378a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 379a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, 380a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 381a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 382a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 383a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 384a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 385a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 386a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, 387a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 388b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 389b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 3909f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 3919f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 3929f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 393a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD) { 394a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return ::SimplifyOrInst(Op0, Op1, TD, MaxRecursionDepth); 395a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 396d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 397210c5d4880b525e064088b6fec713260128c16ebChris Lattnerstatic const Type *GetCompareTy(Value *Op) { 398210c5d4880b525e064088b6fec713260128c16ebChris Lattner return CmpInst::makeCmpResultType(Op->getType()); 399210c5d4880b525e064088b6fec713260128c16ebChris Lattner} 400210c5d4880b525e064088b6fec713260128c16ebChris Lattner 4019dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 4029dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 403a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 404a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD, unsigned MaxRecurse) { 4059f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 4069dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 40712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 408d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 4098f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 4108f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 411d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 412d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 413d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 414d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 415d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 41612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 417210c5d4880b525e064088b6fec713260128c16ebChris Lattner // ITy - This is the return type of the compare we're considering. 418210c5d4880b525e064088b6fec713260128c16ebChris Lattner const Type *ITy = GetCompareTy(LHS); 41912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 420210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp X, X -> true/false 421c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 422c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // because X could be 0. 423c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner if (LHS == RHS || isa<UndefValue>(RHS)) 424210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 42512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 426210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 427210c5d4880b525e064088b6fec713260128c16ebChris Lattner // addresses never equal each other! We already know that Op0 != Op1. 42812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 429210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(LHS)) && 43012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 431210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(RHS))) 432210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 43312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 434210c5d4880b525e064088b6fec713260128c16ebChris Lattner // See if we are doing a comparison with a constant. 435210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 436210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If we have an icmp le or icmp ge instruction, turn it into the 437210c5d4880b525e064088b6fec713260128c16ebChris Lattner // appropriate icmp lt or icmp gt instruction. This allows us to rely on 438210c5d4880b525e064088b6fec713260128c16ebChris Lattner // them being folded in the code below. 439210c5d4880b525e064088b6fec713260128c16ebChris Lattner switch (Pred) { 440210c5d4880b525e064088b6fec713260128c16ebChris Lattner default: break; 441210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_ULE: 442210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 443210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 444210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 445210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SLE: 446210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 447210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 448210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 449210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_UGE: 450210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(false)) // A >=u MIN -> TRUE 451210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 452210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 453210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SGE: 454210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(true)) // A >=s MIN -> TRUE 455210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 456210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 457210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 458210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 4591ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 4601ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // If the comparison is with the result of a select instruction, check whether 4611ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // comparing with either branch of the select always yields the same value. 462a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 463a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1)) 464a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 465a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 466a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 467a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 468a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 469a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1)) 4703bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 4711ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 4729dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return 0; 4739dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 4749dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 475a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 476a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD) { 477a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth); 478a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 479a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 4809dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 4819dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 482a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 483a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD, unsigned MaxRecurse) { 4849dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 4859dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 4869dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 487d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 4889dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 4899dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 49012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 491d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 492d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 493d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 494d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 49512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 496210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Fold trivial predicates. 497210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_FALSE) 498210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 499210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_TRUE) 500210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 501210c5d4880b525e064088b6fec713260128c16ebChris Lattner 502210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 503210c5d4880b525e064088b6fec713260128c16ebChris Lattner return UndefValue::get(GetCompareTy(LHS)); 504210c5d4880b525e064088b6fec713260128c16ebChris Lattner 505210c5d4880b525e064088b6fec713260128c16ebChris Lattner // fcmp x,x -> true/false. Not all compares are foldable. 506210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (LHS == RHS) { 507210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isTrueWhenEqual(Pred)) 508210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 509210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isFalseWhenEqual(Pred)) 510210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 511210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 51212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 513210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Handle fcmp with constant RHS 514210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 515210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If the constant is a nan, see if we can fold the comparison based on it. 516210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 517210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CFP->getValueAPF().isNaN()) { 518210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 519210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getFalse(CFP->getContext()); 520210c5d4880b525e064088b6fec713260128c16ebChris Lattner assert(FCmpInst::isUnordered(Pred) && 521210c5d4880b525e064088b6fec713260128c16ebChris Lattner "Comparison must be either ordered or unordered!"); 522210c5d4880b525e064088b6fec713260128c16ebChris Lattner // True if unordered. 523210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CFP->getContext()); 524210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 5256b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // Check whether the constant is an infinity. 5266b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isInfinity()) { 5276b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isNegative()) { 5286b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 5296b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OLT: 5306b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and less than negative infinity. 5316b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 5326b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_UGE: 5336b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with or at least negative infinity. 5346b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 5356b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 5366b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 5376b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 5386b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } else { 5396b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 5406b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OGT: 5416b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and greater than infinity. 5426b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 5436b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_ULE: 5446b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with and at most infinity. 5456b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 5466b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 5476b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 5486b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 5496b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 5506b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 551210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 552210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 55312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 55492826def593df7a422c7b07f09342febce81ddd3Duncan Sands // If the comparison is with the result of a select instruction, check whether 55592826def593df7a422c7b07f09342febce81ddd3Duncan Sands // comparing with either branch of the select always yields the same value. 556a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 557a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, MaxRecurse-1)) 558a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 559a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 560a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 561a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 562a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 563a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, MaxRecurse-1)) 5643bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 56592826def593df7a422c7b07f09342febce81ddd3Duncan Sands 5669f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 5679f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 5689f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 569a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 570a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD) { 571a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth); 572a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 573a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 574047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 575047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// the result. If not, this returns null. 576047542669a20505fc7c5f2d93caa5610aa3db2c5Chris LattnerValue *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 577047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner const TargetData *TD) { 578047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select true, X, Y -> X 579047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select false, X, Y -> Y 580047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 581047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return CB->getZExtValue() ? TrueVal : FalseVal; 58212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 583047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select C, X, X -> X 584047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (TrueVal == FalseVal) 585047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 58612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 587047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 588047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 589047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 590047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 591047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 592047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<Constant>(TrueVal)) 593047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 594047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 595047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner } 59612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 597047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return 0; 598047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner} 599047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 600047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 601c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 602c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// fold the result. If not, this returns null. 603c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris LattnerValue *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 604c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner const TargetData *TD) { 605c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P -> P. 606c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 1) 607c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 608c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 609c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // TODO. 610c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner //if (isa<UndefValue>(Ops[0])) 611c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // return UndefValue::get(GEP.getType()); 612c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 613c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P, 0 -> P. 614c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 2) 615c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 616c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (C->isZero()) 617c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 61812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 619c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // Check to see if this is constant foldable. 620c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner for (unsigned i = 0; i != NumOps; ++i) 621c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (!isa<Constant>(Ops[i])) 622c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return 0; 62312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 624c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 625c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner (Constant *const*)Ops+1, NumOps-1); 626c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner} 627c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 628c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 629d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner//=== Helper functions for higher up the class hierarchy. 6309dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 631d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 632d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 633a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 634a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD, unsigned MaxRecurse) { 635d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner switch (Opcode) { 636a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, MaxRecurse); 637a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, MaxRecurse); 638d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner default: 639d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) 640d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 641d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *COps[] = {CLHS, CRHS}; 642d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 643d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 644b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 645b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 646b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 647a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 648a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, MaxRecurse-1)) 649a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 650a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 651a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 652a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 653a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 654a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, MaxRecurse-1)) 655b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 656b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 657d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 658d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 659d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 6609dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 66112a86f5b3199e72e6d967781acc76340f5920e46Duncan SandsValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 662a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD) { 663a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return ::SimplifyBinOp(Opcode, LHS, RHS, TD, MaxRecursionDepth); 664a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 665a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 6669dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 6679dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. 668a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 669a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD, unsigned MaxRecurse) { 6709dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 671a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return SimplifyICmpInst(Predicate, LHS, RHS, TD, MaxRecurse); 672a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return SimplifyFCmpInst(Predicate, LHS, RHS, TD, MaxRecurse); 6739dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 6749dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 675a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 676a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands const TargetData *TD) { 677a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, MaxRecursionDepth); 678a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 679e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 680e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// SimplifyInstruction - See if we can compute a simplified version of this 681e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// instruction. If not, this returns null. 682eff0581583ef10e2872e9baf537a04b67d992101Duncan SandsValue *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 683eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 684e34537856a544c83513e390ac9552a8bc3823346Chris Lattner switch (I->getOpcode()) { 685e34537856a544c83513e390ac9552a8bc3823346Chris Lattner default: 686e34537856a544c83513e390ac9552a8bc3823346Chris Lattner return ConstantFoldInstruction(I, TD); 6878aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner case Instruction::Add: 6884e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson return SimplifyAddInst(I->getOperand(0), I->getOperand(1), 6894e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson cast<BinaryOperator>(I)->hasNoSignedWrap(), 6904e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson cast<BinaryOperator>(I)->hasNoUnsignedWrap(), TD); 691e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::And: 6924e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson return SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD); 693e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::Or: 6944e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson return SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD); 695e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::ICmp: 6964e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson return SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 6974e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson I->getOperand(0), I->getOperand(1), TD); 698e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::FCmp: 6994e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson return SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 7004e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson I->getOperand(0), I->getOperand(1), TD); 701047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner case Instruction::Select: 7024e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson return SimplifySelectInst(I->getOperand(0), I->getOperand(1), 703047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner I->getOperand(2), TD); 704c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner case Instruction::GetElementPtr: { 705c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 7064e282decf3960bfa6b1fe3fd77bb51ff96121515Owen Anderson return SimplifyGEPInst(&Ops[0], Ops.size(), TD); 707c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner } 708cd6636c737a82949ad13db2d0d918af6424fb78bDuncan Sands case Instruction::PHI: 709eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands return cast<PHINode>(I)->hasConstantValue(DT); 710e34537856a544c83513e390ac9552a8bc3823346Chris Lattner } 711e34537856a544c83513e390ac9552a8bc3823346Chris Lattner} 712e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 71340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 71440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// delete the From instruction. In addition to a basic RAUW, this does a 71540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursive simplification of the newly formed instructions. This catches 71640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// things where one simplification exposes other opportunities. This only 71740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// simplifies and deletes scalar operations, it does not change the CFG. 71840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 71940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 720eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const TargetData *TD, 721eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 72240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 72312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 724d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 725d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // we can know if it gets deleted out from under us or replaced in a 726d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // recursive simplification. 72740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH FromHandle(From); 728d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner WeakVH ToHandle(To); 72912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 73040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (!From->use_empty()) { 73140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Update the instruction to use the new value. 732d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Use &TheUse = From->use_begin().getUse(); 733d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Instruction *User = cast<Instruction>(TheUse.getUser()); 734d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner TheUse = To; 735d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner 736d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Check to see if the instruction can be folded due to the operand 737d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // replacement. For example changing (or X, Y) into (or X, -1) can replace 738d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // the 'or' with -1. 739d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Value *SimplifiedVal; 740d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner { 741d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Sanity check to make sure 'User' doesn't dangle across 742d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // SimplifyInstruction. 743d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner AssertingVH<> UserHandle(User); 74412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 745eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands SimplifiedVal = SimplifyInstruction(User, TD, DT); 746d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (SimplifiedVal == 0) continue; 74740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 74812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 749d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Recursively simplify this user to the new value. 750eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 751d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 752d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner To = ToHandle; 75312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 754d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner assert(ToHandle && "To value deleted by recursive simplification?"); 75512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 756d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If the recursive simplification ended up revisiting and deleting 757d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // 'From' then we're done. 758d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (From == 0) 759d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner return; 76040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 76112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 762d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If 'From' has value handles referring to it, do a real RAUW to update them. 763d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From->replaceAllUsesWith(To); 76412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 76540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner From->eraseFromParent(); 76640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 767