InstructionSimplify.cpp revision 2b749870d0488c3b049edf5d0c8875f56f5b1bed
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" 181845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Analysis/Dominators.h" 19d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner#include "llvm/Support/PatternMatch.h" 201845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Support/ValueHandle.h" 219f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattnerusing namespace llvm; 22d06094f0682f2ede03caff4892b1a57469896d48Chris Lattnerusing namespace llvm::PatternMatch; 239f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 241845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#define RecursionLimit 3 25a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 26a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 271845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 28a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 291845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 301845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 311845009290e4d804ad377927bd8a08cca3036adcDuncan Sands/// ValueDominatesPHI - Does the given value dominate the specified phi node? 321845009290e4d804ad377927bd8a08cca3036adcDuncan Sandsstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 331845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Instruction *I = dyn_cast<Instruction>(V); 341845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!I) 351845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Arguments and constants dominate all instructions. 361845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 371845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // If we have a DominatorTree then do a precise test. 391845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (DT) 401845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return DT->dominates(I, P); 411845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 421845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Otherwise, if the instruction is in the entry block, and is not an invoke, 431845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // then it obviously dominates all phi nodes. 441845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands !isa<InvokeInst>(I)) 461845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 471845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 481845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return false; 491845009290e4d804ad377927bd8a08cca3036adcDuncan Sands} 50a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 51b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadBinOpOverSelect - In the case of a binary operation with a select 52b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// instruction as an operand, try to simplify the binop by seeing whether 53b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// evaluating it on both branches of the select results in the same value. 54b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// Returns the common value if so, otherwise returns null. 55b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, 571845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 581845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 59b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI; 60b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (isa<SelectInst>(LHS)) { 61b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(LHS); 62b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 63b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 64b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(RHS); 65b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 66b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 67b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Evaluate the BinOp on the true and false branches of the select. 68b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *TV; 69b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *FV; 70b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (SI == LHS) { 711845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse); 721845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse); 73b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 741845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse); 751845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse); 76b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 77b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 78b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they simplified to the same value, then return the common value. 79b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they both failed to simplify then return null. 80b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == FV) 81b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 82b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 83b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified to undef, return the other one. 84b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV && isa<UndefValue>(TV)) 85b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return FV; 86b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (FV && isa<UndefValue>(FV)) 87b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 88b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 89b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If applying the operation did not change the true and false select values, 90b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // then the result of the binop is the select itself. 91b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 92b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return SI; 93b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 94b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified and the other did not, and the simplified 95b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // value is equal to the unsimplified one, return the simplified value. 96b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // For example, select (cond, X, X & Z) & Z -> X & Z. 97b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if ((FV && !TV) || (TV && !FV)) { 98b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Check that the simplified value has the form "X op Y" where "op" is the 99b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // same as the original operation. 100b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 101b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified && Simplified->getOpcode() == Opcode) { 102b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 103b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // We already know that "op" is the same as for the simplified value. See 104b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // if the operands match too. If so, return the simplified value. 105b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 106b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 107b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 108b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->getOperand(0) == UnsimplifiedLHS && 109b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedRHS) 110b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 111b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->isCommutative() && 112b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedLHS && 113b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(0) == UnsimplifiedRHS) 114b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 115b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 116b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 117b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 118b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 119b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 120b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 121b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 122b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// try to simplify the comparison by seeing whether both branches of the select 123b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// result in the same value. Returns the common value if so, otherwise returns 124b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// null. 125b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 126a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *RHS, const TargetData *TD, 1271845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 128a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 129b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Make sure the select is on the LHS. 130b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (!isa<SelectInst>(LHS)) { 131b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands std::swap(LHS, RHS); 132b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 133b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 134b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 135b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI = cast<SelectInst>(LHS); 136b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 137b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Now that we have "cmp select(cond, TV, FV), RHS", analyse it. 138b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Does "cmp TV, RHS" simplify? 1391845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT, 140a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 141b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! Does "cmp FV, RHS" simplify? 1421845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT, 143a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 144b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! If they simplified to the same value, then use it as the 145b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // result of the original comparison. 146b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TCmp == FCmp) 147b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TCmp; 148b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 149b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 150b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 151a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 152a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 153a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// it on the incoming phi values yields the same result for every value. If so 154a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// returns the common value, otherwise returns null. 155a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 1561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 1571845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 158a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI; 159a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (isa<PHINode>(LHS)) { 160a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(LHS); 1611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 1621845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 1631845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 164a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } else { 165a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 166a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(RHS); 1671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if LHS and the phi may be mutually interdependent due to a loop. 1681845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(LHS, PI, DT)) 1691845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 170a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 171a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 172a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 173a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 174a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 175552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 176ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 177552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 178a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *V = PI == LHS ? 1791845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 1801845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 181a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 182a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 183a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 184a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 185a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 186a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 187a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 188a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 189a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 190a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 191a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 192a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// try to simplify the comparison by seeing whether comparing with all of the 193a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// incoming phi values yields the same result every time. If so returns the 194a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// common result, otherwise returns null. 195a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 1961845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 1971845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 198a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Make sure the phi is on the LHS. 199a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!isa<PHINode>(LHS)) { 200a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands std::swap(LHS, RHS); 201a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 202a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 203a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 204a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI = cast<PHINode>(LHS); 205a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 2061845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 2071845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 2081845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 2091845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 210a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 211a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 212a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 213552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 214ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 215552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 2161845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 217a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 218a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 219a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 220a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 221a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 222a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 223a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 224a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 225a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 226a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 2278aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 228d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 2298aee8efc0c2e387faa7dae39fdf613a22889b566Chris LattnerValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 2301845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 231d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 232d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 233d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 2348aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 2358aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Ops, 2, TD); 2368aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 23712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2388aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // Canonicalize the constant to the RHS. 2398aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner std::swap(Op0, Op1); 2408aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 24112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2428aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 2438aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // X + undef -> undef 2448aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (isa<UndefValue>(Op1C)) 2458aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return Op1C; 24612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2478aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // X + 0 --> X 2488aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Op1C->isNullValue()) 2498aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return Op0; 2508aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 25112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2528aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // FIXME: Could pull several more out of instcombine. 2538aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return 0; 2548aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner} 2558aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner 2568aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 2578aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// fold the result. If not, this returns null. 258a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 2591845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 2608aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 2618aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 2628aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 263d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 264d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 265d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 26612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 267d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 268d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 269d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 27012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 271d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & undef -> 0 272d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 273d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 27412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 275d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & X = X 276d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 277d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 27812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2792b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & 0 = 0 2802b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 281d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 28212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2832b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & -1 = X 2842b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 2852b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 28612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 287d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & ~A = ~A & A = 0 288d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Value *A, *B; 28970ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 29070ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 291d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 29212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 293d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A | ?) & A = A 294d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 295d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 296d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 29712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 298d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & (A | ?) = A 299d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 300d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 301d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 30212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 3036844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // (A & B) & A -> A & B 3046844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op0, m_And(m_Value(A), m_Value(B))) && 3056844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op1 || B == Op1)) 3066844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op0; 3076844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 3086844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // A & (A & B) -> A & B 3096844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op1, m_And(m_Value(A), m_Value(B))) && 3106844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op0 || B == Op0)) 3116844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op1; 3126844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 313b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 314b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 315a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 3161845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 317a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 318a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 319a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 320a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 321a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 322a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 3231845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 324a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 325b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 326b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 327d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 328d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 3299f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 3301845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 3311845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 3321845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 333a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 334a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 335d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 3369f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner/// fold the result. If not, this returns null. 337a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 3381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 339d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 340d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 341d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 342d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 343d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 344d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 34512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 346d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 347d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 348d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 34912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 350d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | undef -> -1 351d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 352d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 35312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 354d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | X = X 355d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 356d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 357d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 3582b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | 0 = X 3592b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 360d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 36112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 3622b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | -1 = -1 3632b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 3642b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op1; 36512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 366d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | ~A = ~A | A = -1 367d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Value *A, *B; 36870ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 36970ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 370d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 37112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 372d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A & ?) | A = A 373d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(B))) && 374d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 375d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 37612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 377d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | (A & ?) = A 378d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_And(m_Value(A), m_Value(B))) && 379d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 380d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 38112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 3826844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // (A | B) | A -> A | B 3836844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 3846844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op1 || B == Op1)) 3856844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op0; 3866844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 3876844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // A | (A | B) -> A | B 3886844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 3896844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op0 || B == Op0)) 3906844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op1; 3916844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 392b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 393b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 394a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 3951845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 396a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 397a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 398a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 399a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 400a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 401a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 4021845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 403a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 404b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 405b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 4069f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 4079f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 4089f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 4091845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 4101845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 4111845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 412a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 413d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 4142b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// SimplifyXorInst - Given operands for a Xor, see if we can 4152b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// fold the result. If not, this returns null. 4162b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sandsstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 4172b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 4182b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 4192b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 4202b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 4212b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 4222b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Ops, 2, TD); 4232b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 4242b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4252b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // Canonicalize the constant to the RHS. 4262b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands std::swap(Op0, Op1); 4272b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 4282b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4292b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ undef -> undef 4302b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (isa<UndefValue>(Op1)) 4312b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return UndefValue::get(Op0->getType()); 4322b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4332b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ 0 = A 4342b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 4352b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 4362b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4372b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ A = 0 4382b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Op0 == Op1) 4392b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getNullValue(Op0->getType()); 4402b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4412b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ ~A = ~A ^ A = -1 4422b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Value *A, *B; 4432b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 4442b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (match(Op1, m_Not(m_Value(A))) && A == Op0)) 4452b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getAllOnesValue(Op0->getType()); 4462b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4472b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // (A ^ B) ^ A = B 4482b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op0, m_Xor(m_Value(A), m_Value(B))) && 4492b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (A == Op1 || B == Op1)) 4502b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return A == Op1 ? B : A; 4512b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4522b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ (A ^ B) = B 4532b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Xor(m_Value(A), m_Value(B))) && 4542b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (A == Op0 || B == Op0)) 4552b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return A == Op0 ? B : A; 4562b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4572b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // If the operation is with the result of a select instruction, check whether 4582b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // operating on either branch of the select always yields the same value. 4592b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 4602b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Xor, Op0, Op1, TD, DT, 4612b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands MaxRecurse-1)) 4622b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return V; 4632b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4642b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // If the operation is with the result of a phi instruction, check whether 4652b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // operating on all incoming values of the phi always yields the same value. 4662b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 4672b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Xor, Op0, Op1, TD, DT, 4682b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands MaxRecurse-1)) 4692b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return V; 4702b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4712b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return 0; 4722b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 4732b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4742b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan SandsValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 4752b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT) { 4762b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 4772b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 4782b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 479210c5d4880b525e064088b6fec713260128c16ebChris Lattnerstatic const Type *GetCompareTy(Value *Op) { 480210c5d4880b525e064088b6fec713260128c16ebChris Lattner return CmpInst::makeCmpResultType(Op->getType()); 481210c5d4880b525e064088b6fec713260128c16ebChris Lattner} 482210c5d4880b525e064088b6fec713260128c16ebChris Lattner 4839dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 4849dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 485a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 4861845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 4871845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 4889f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 4899dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 49012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 491d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 4928f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 4938f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 494d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 495d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 496d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 497d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 498d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 49912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 500210c5d4880b525e064088b6fec713260128c16ebChris Lattner // ITy - This is the return type of the compare we're considering. 501210c5d4880b525e064088b6fec713260128c16ebChris Lattner const Type *ITy = GetCompareTy(LHS); 50212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 503210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp X, X -> true/false 504c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 505c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // because X could be 0. 506c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner if (LHS == RHS || isa<UndefValue>(RHS)) 507210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 50812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 509210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 510210c5d4880b525e064088b6fec713260128c16ebChris Lattner // addresses never equal each other! We already know that Op0 != Op1. 51112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 512210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(LHS)) && 51312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 514210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(RHS))) 515210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 51612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 517210c5d4880b525e064088b6fec713260128c16ebChris Lattner // See if we are doing a comparison with a constant. 518210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 519210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If we have an icmp le or icmp ge instruction, turn it into the 520210c5d4880b525e064088b6fec713260128c16ebChris Lattner // appropriate icmp lt or icmp gt instruction. This allows us to rely on 521210c5d4880b525e064088b6fec713260128c16ebChris Lattner // them being folded in the code below. 522210c5d4880b525e064088b6fec713260128c16ebChris Lattner switch (Pred) { 523210c5d4880b525e064088b6fec713260128c16ebChris Lattner default: break; 524210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_ULE: 525210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 526210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 527210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 528210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SLE: 529210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 530210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 531210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 532210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_UGE: 533210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(false)) // A >=u MIN -> TRUE 534210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 535210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 536210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SGE: 537210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(true)) // A >=s MIN -> TRUE 538210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 539210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 540210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 541210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 5421ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 5431ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // If the comparison is with the result of a select instruction, check whether 5441ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // comparing with either branch of the select always yields the same value. 545a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 5461845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 547a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 548a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 549a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 550a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 551a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 5521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 5533bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 5541ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 5559dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return 0; 5569dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 5579dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 558a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 5591845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 5601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 561a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 562a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 5639dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 5649dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 565a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 5661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 5671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 5689dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 5699dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 5709dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 571d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 5729dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 5739dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 57412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 575d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 576d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 577d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 578d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 57912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 580210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Fold trivial predicates. 581210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_FALSE) 582210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 583210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_TRUE) 584210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 585210c5d4880b525e064088b6fec713260128c16ebChris Lattner 586210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 587210c5d4880b525e064088b6fec713260128c16ebChris Lattner return UndefValue::get(GetCompareTy(LHS)); 588210c5d4880b525e064088b6fec713260128c16ebChris Lattner 589210c5d4880b525e064088b6fec713260128c16ebChris Lattner // fcmp x,x -> true/false. Not all compares are foldable. 590210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (LHS == RHS) { 591210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isTrueWhenEqual(Pred)) 592210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 593210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isFalseWhenEqual(Pred)) 594210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 595210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 59612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 597210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Handle fcmp with constant RHS 598210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 599210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If the constant is a nan, see if we can fold the comparison based on it. 600210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 601210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CFP->getValueAPF().isNaN()) { 602210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 603210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getFalse(CFP->getContext()); 604210c5d4880b525e064088b6fec713260128c16ebChris Lattner assert(FCmpInst::isUnordered(Pred) && 605210c5d4880b525e064088b6fec713260128c16ebChris Lattner "Comparison must be either ordered or unordered!"); 606210c5d4880b525e064088b6fec713260128c16ebChris Lattner // True if unordered. 607210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CFP->getContext()); 608210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 6096b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // Check whether the constant is an infinity. 6106b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isInfinity()) { 6116b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isNegative()) { 6126b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 6136b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OLT: 6146b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and less than negative infinity. 6156b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 6166b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_UGE: 6176b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with or at least negative infinity. 6186b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 6196b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 6206b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 6216b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 6226b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } else { 6236b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 6246b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OGT: 6256b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and greater than infinity. 6266b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 6276b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_ULE: 6286b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with and at most infinity. 6296b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 6306b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 6316b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 6326b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 6336b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 6346b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 635210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 636210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 63712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 63892826def593df7a422c7b07f09342febce81ddd3Duncan Sands // If the comparison is with the result of a select instruction, check whether 63992826def593df7a422c7b07f09342febce81ddd3Duncan Sands // comparing with either branch of the select always yields the same value. 640a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 6411845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 642a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 643a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 644a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 645a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 646a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 6471845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 6483bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 64992826def593df7a422c7b07f09342febce81ddd3Duncan Sands 6509f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 6519f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 6529f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 653a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 6541845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 6551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 656a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 657a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 658047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 659047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// the result. If not, this returns null. 660047542669a20505fc7c5f2d93caa5610aa3db2c5Chris LattnerValue *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 6611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 662047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select true, X, Y -> X 663047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select false, X, Y -> Y 664047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 665047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return CB->getZExtValue() ? TrueVal : FalseVal; 66612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 667047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select C, X, X -> X 668047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (TrueVal == FalseVal) 669047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 67012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 671047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 672047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 673047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 674047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 675047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 676047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<Constant>(TrueVal)) 677047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 678047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 679047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner } 68012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 681047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return 0; 682047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner} 683047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 684c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 685c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// fold the result. If not, this returns null. 686c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris LattnerValue *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 6871845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 688c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P -> P. 689c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 1) 690c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 691c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 692c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // TODO. 693c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner //if (isa<UndefValue>(Ops[0])) 694c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // return UndefValue::get(GEP.getType()); 695c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 696c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P, 0 -> P. 697c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 2) 698c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 699c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (C->isZero()) 700c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 70112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 702c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // Check to see if this is constant foldable. 703c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner for (unsigned i = 0; i != NumOps; ++i) 704c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (!isa<Constant>(Ops[i])) 705c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return 0; 70612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 707c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 708c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner (Constant *const*)Ops+1, NumOps-1); 709c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner} 710c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 711ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 712ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sandsstatic Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 713ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If all of the PHI's incoming values are the same then replace the PHI node 714ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // with the common value. 715ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *CommonValue = 0; 716ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands bool HasUndefInput = false; 717ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 718ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *Incoming = PN->getIncomingValue(i); 719ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 720ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (Incoming == PN) continue; 721ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (isa<UndefValue>(Incoming)) { 722ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // Remember that we saw an undef value, but otherwise ignore them. 723ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands HasUndefInput = true; 724ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands continue; 725ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 726ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (CommonValue && Incoming != CommonValue) 727ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return 0; // Not the same, bail out. 728ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands CommonValue = Incoming; 729ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 730ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 731ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If CommonValue is null then all of the incoming values were either undef or 732ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // equal to the phi node itself. 733ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (!CommonValue) 734ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return UndefValue::get(PN->getType()); 735ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 736ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If we have a PHI node like phi(X, undef, X), where X is defined by some 737ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // instruction, we cannot return X as the result of the PHI node unless it 738ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // dominates the PHI block. 739ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (HasUndefInput) 740ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 741ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 742ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return CommonValue; 743ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands} 744ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 745c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 746d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner//=== Helper functions for higher up the class hierarchy. 7479dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 748d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 749d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 750a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 7511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 7521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 753d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner switch (Opcode) { 7541845009290e4d804ad377927bd8a08cca3036adcDuncan Sands case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 7551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse); 756d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner default: 757d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) 758d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 759d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *COps[] = {CLHS, CRHS}; 760d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 761d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 762b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 763b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 764b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 765a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 7661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 7671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands MaxRecurse-1)) 768a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 769a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 770a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 771a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 772a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 7731845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1)) 774b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 775b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 776d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 777d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 778d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 7799dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 78012a86f5b3199e72e6d967781acc76340f5920e46Duncan SandsValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 7811845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 7821845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 783a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 784a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 7859dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 7869dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. 787a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 7881845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 7891845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 7909dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 7911845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 7921845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 7939dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 7949dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 795a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 7961845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 7971845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 798a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 799e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 800e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// SimplifyInstruction - See if we can compute a simplified version of this 801e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// instruction. If not, this returns null. 802eff0581583ef10e2872e9baf537a04b67d992101Duncan SandsValue *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 803eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 804d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Value *Result; 805d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 806e34537856a544c83513e390ac9552a8bc3823346Chris Lattner switch (I->getOpcode()) { 807e34537856a544c83513e390ac9552a8bc3823346Chris Lattner default: 808d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = ConstantFoldInstruction(I, TD); 809d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 8108aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner case Instruction::Add: 811d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 812d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 813d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 814d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands TD, DT); 815d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 816e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::And: 817d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 818d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 819e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::Or: 820d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 821d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 8222b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands case Instruction::Xor: 8232b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 8242b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands break; 825e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::ICmp: 826d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 827d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 828d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 829e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::FCmp: 830d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 831d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 832d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 833047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner case Instruction::Select: 834d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 835d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(2), TD, DT); 836d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 837c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner case Instruction::GetElementPtr: { 838c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 839d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 840d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 841c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner } 842cd6636c737a82949ad13db2d0d918af6424fb78bDuncan Sands case Instruction::PHI: 843d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyPHINode(cast<PHINode>(I), DT); 844d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 845e34537856a544c83513e390ac9552a8bc3823346Chris Lattner } 846d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 847d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// If called on unreachable code, the above logic may report that the 848d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// instruction simplified to itself. Make life easier for users by 849d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// detecting that case here, returning null if it occurs. 850d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands return Result == I ? 0 : Result; 851e34537856a544c83513e390ac9552a8bc3823346Chris Lattner} 852e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 85340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 85440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// delete the From instruction. In addition to a basic RAUW, this does a 85540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursive simplification of the newly formed instructions. This catches 85640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// things where one simplification exposes other opportunities. This only 85740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// simplifies and deletes scalar operations, it does not change the CFG. 85840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 85940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 860eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const TargetData *TD, 861eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 86240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 86312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 864d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 865d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // we can know if it gets deleted out from under us or replaced in a 866d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // recursive simplification. 86740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH FromHandle(From); 868d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner WeakVH ToHandle(To); 86912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 87040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (!From->use_empty()) { 87140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Update the instruction to use the new value. 872d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Use &TheUse = From->use_begin().getUse(); 873d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Instruction *User = cast<Instruction>(TheUse.getUser()); 874d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner TheUse = To; 875d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner 876d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Check to see if the instruction can be folded due to the operand 877d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // replacement. For example changing (or X, Y) into (or X, -1) can replace 878d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // the 'or' with -1. 879d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Value *SimplifiedVal; 880d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner { 881d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Sanity check to make sure 'User' doesn't dangle across 882d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // SimplifyInstruction. 883d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner AssertingVH<> UserHandle(User); 88412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 885eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands SimplifiedVal = SimplifyInstruction(User, TD, DT); 886d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (SimplifiedVal == 0) continue; 88740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 88812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 889d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Recursively simplify this user to the new value. 890eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 891d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 892d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner To = ToHandle; 89312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 894d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner assert(ToHandle && "To value deleted by recursive simplification?"); 89512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 896d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If the recursive simplification ended up revisiting and deleting 897d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // 'From' then we're done. 898d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (From == 0) 899d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner return; 90040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 90112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 902d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If 'From' has value handles referring to it, do a real RAUW to update them. 903d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From->replaceAllUsesWith(To); 90412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 90540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner From->eraseFromParent(); 90640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 907