InstructionSimplify.cpp revision f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3e
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 114cd2ad15b43f21d641330b4b09961af08646445eDuncan Sands// that do not require creating new instructions. This does constant folding 124cd2ad15b43f21d641330b4b09961af08646445eDuncan Sands// ("add i32 1, 1" -> "2") but can also handle non-constant operands, either 134cd2ad15b43f21d641330b4b09961af08646445eDuncan Sands// returning a constant ("and i32 %x, 0" -> "0") or an already existing value 144cd2ad15b43f21d641330b4b09961af08646445eDuncan Sands// ("and i32 %x, %x" -> "%x"). 159f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 169f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner//===----------------------------------------------------------------------===// 179f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 189f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/InstructionSimplify.h" 199f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/ConstantFolding.h" 201845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Analysis/Dominators.h" 21d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner#include "llvm/Support/PatternMatch.h" 221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Support/ValueHandle.h" 23e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands#include "llvm/Target/TargetData.h" 249f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattnerusing namespace llvm; 25d06094f0682f2ede03caff4892b1a57469896d48Chris Lattnerusing namespace llvm::PatternMatch; 269f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 271845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#define RecursionLimit 3 28a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 29a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 301845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 31a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 321845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 331845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 341845009290e4d804ad377927bd8a08cca3036adcDuncan Sands/// ValueDominatesPHI - Does the given value dominate the specified phi node? 351845009290e4d804ad377927bd8a08cca3036adcDuncan Sandsstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 361845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Instruction *I = dyn_cast<Instruction>(V); 371845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!I) 381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Arguments and constants dominate all instructions. 391845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 401845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 411845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // If we have a DominatorTree then do a precise test. 421845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (DT) 431845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return DT->dominates(I, P); 441845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Otherwise, if the instruction is in the entry block, and is not an invoke, 461845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // then it obviously dominates all phi nodes. 471845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 481845009290e4d804ad377927bd8a08cca3036adcDuncan Sands !isa<InvokeInst>(I)) 491845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 501845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return false; 521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands} 53a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 54b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadBinOpOverSelect - In the case of a binary operation with a select 55b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// instruction as an operand, try to simplify the binop by seeing whether 56b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// evaluating it on both branches of the select results in the same value. 57b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// Returns the common value if so, otherwise returns null. 58b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 591845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, 601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 62b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI; 63b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (isa<SelectInst>(LHS)) { 64b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(LHS); 65b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 66b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 67b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(RHS); 68b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 69b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 70b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Evaluate the BinOp on the true and false branches of the select. 71b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *TV; 72b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *FV; 73b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (SI == LHS) { 741845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse); 751845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse); 76b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 771845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse); 781845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse); 79b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 80b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 81b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they simplified to the same value, then return the common value. 82b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they both failed to simplify then return null. 83b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == FV) 84b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 85b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 86b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified to undef, return the other one. 87b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV && isa<UndefValue>(TV)) 88b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return FV; 89b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (FV && isa<UndefValue>(FV)) 90b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 91b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 92b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If applying the operation did not change the true and false select values, 93b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // then the result of the binop is the select itself. 94b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 95b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return SI; 96b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 97b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified and the other did not, and the simplified 98b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // value is equal to the unsimplified one, return the simplified value. 99b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // For example, select (cond, X, X & Z) & Z -> X & Z. 100b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if ((FV && !TV) || (TV && !FV)) { 101b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Check that the simplified value has the form "X op Y" where "op" is the 102b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // same as the original operation. 103b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 104b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified && Simplified->getOpcode() == Opcode) { 105b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 106b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // We already know that "op" is the same as for the simplified value. See 107b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // if the operands match too. If so, return the simplified value. 108b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 109b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 110b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 111b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->getOperand(0) == UnsimplifiedLHS && 112b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedRHS) 113b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 114b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->isCommutative() && 115b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedLHS && 116b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(0) == UnsimplifiedRHS) 117b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 118b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 119b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 120b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 121b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 122b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 123b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 124b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 125b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// try to simplify the comparison by seeing whether both branches of the select 126b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// result in the same value. Returns the common value if so, otherwise returns 127b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// null. 128b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 129a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *RHS, const TargetData *TD, 1301845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 131a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 132b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Make sure the select is on the LHS. 133b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (!isa<SelectInst>(LHS)) { 134b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands std::swap(LHS, RHS); 135b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 136b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 137b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 138b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI = cast<SelectInst>(LHS); 139b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 140b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Now that we have "cmp select(cond, TV, FV), RHS", analyse it. 141b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Does "cmp TV, RHS" simplify? 1421845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT, 143a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 144b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! Does "cmp FV, RHS" simplify? 1451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT, 146a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 147b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! If they simplified to the same value, then use it as the 148b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // result of the original comparison. 149b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TCmp == FCmp) 150b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TCmp; 151b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 152b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 153b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 154a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 155a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 156a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// it on the incoming phi values yields the same result for every value. If so 157a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// returns the common value, otherwise returns null. 158a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 1591845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 1601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 161a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI; 162a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (isa<PHINode>(LHS)) { 163a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(LHS); 1641845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 1651845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 1661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 167a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } else { 168a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 169a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(RHS); 1701845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if LHS and the phi may be mutually interdependent due to a loop. 1711845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(LHS, PI, DT)) 1721845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 173a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 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); 179ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 180552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 181a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *V = PI == LHS ? 1821845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 1831845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 184a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 185a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 186a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 187a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 188a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 189a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 190a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 191a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 192a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 193a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 194a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 195a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// try to simplify the comparison by seeing whether comparing with all of the 196a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// incoming phi values yields the same result every time. If so returns the 197a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// common result, otherwise returns null. 198a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 1991845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 2001845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 201a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Make sure the phi is on the LHS. 202a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!isa<PHINode>(LHS)) { 203a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands std::swap(LHS, RHS); 204a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 205a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 206a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 207a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI = cast<PHINode>(LHS); 208a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 2091845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 2101845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 2111845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 2121845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 213a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 214a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 215a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 216552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 217ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 218552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 2191845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 220a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 221a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 222a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 223a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 224a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 225a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 226a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 227a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 228a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 229a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 2308aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 231d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 2328aee8efc0c2e387faa7dae39fdf613a22889b566Chris LattnerValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 2331845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 234d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 235d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 236d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 2378aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 2388aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Ops, 2, TD); 2398aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 24012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2418aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // Canonicalize the constant to the RHS. 2428aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner std::swap(Op0, Op1); 2438aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 24412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2458aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 2468aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // X + undef -> undef 2478aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (isa<UndefValue>(Op1C)) 2488aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return Op1C; 24912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2508aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // X + 0 --> X 2518aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Op1C->isNullValue()) 2528aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return Op0; 2538aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 25412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2558aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // FIXME: Could pull several more out of instcombine. 25687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 25787689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Add over selects and phi nodes is pointless, so don't bother. 25887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A + select(cond, B, C)" means evaluating 25987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 26087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 26187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 26287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 26387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 26487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 26587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 2668aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return 0; 2678aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner} 2688aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner 2698aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 2708aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// fold the result. If not, this returns null. 271a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 2721845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 2738aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 2748aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 2758aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 276d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 277d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 278d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 27912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 280d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 281d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 282d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 28312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 284d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & undef -> 0 285d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 286d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 28712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 288d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & X = X 289d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 290d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 29112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2922b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & 0 = 0 2932b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 294d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 29512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2962b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & -1 = X 2972b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 2982b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 29912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 300d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & ~A = ~A & A = 0 301e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 30270ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 30370ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 304d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 30512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 306d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A | ?) & A = A 307d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 308d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 309d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 31012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 311d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & (A | ?) = A 312d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 313d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 314d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 31512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 3166844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // (A & B) & A -> A & B 3176844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op0, m_And(m_Value(A), m_Value(B))) && 3186844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op1 || B == Op1)) 3196844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op0; 3206844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 3216844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // A & (A & B) -> A & B 3226844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op1, m_And(m_Value(A), m_Value(B))) && 3236844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op0 || B == Op0)) 3246844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op1; 3256844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 326b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 327b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 328a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 3291845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 330a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 331a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 332a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 333a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 334a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 335a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 3361845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 337a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 338b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 339b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 340d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 341d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 3429f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 3431845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 3441845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 3451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 346a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 347a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 348d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 3499f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner/// fold the result. If not, this returns null. 350a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 3511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 352d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 353d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 354d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 355d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 356d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 357d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 35812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 359d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 360d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 361d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 36212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 363d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | undef -> -1 364d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 365d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 36612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 367d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | X = X 368d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 369d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 370d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 3712b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | 0 = X 3722b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 373d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 37412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 3752b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | -1 = -1 3762b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 3772b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op1; 37812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 379d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | ~A = ~A | A = -1 380e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 38170ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 38270ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 383d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 38412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 385d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A & ?) | A = A 386d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(B))) && 387d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 388d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 38912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 390d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | (A & ?) = A 391d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_And(m_Value(A), m_Value(B))) && 392d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 393d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 39412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 3956844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // (A | B) | A -> A | B 3966844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 3976844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op1 || B == Op1)) 3986844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op0; 3996844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 4006844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer // A | (A | B) -> A | B 4016844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 4026844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer (A == Op0 || B == Op0)) 4036844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer return Op1; 4046844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 405b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 406b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 407a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 4081845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 409a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 410a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 411a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 412a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 413a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 414a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 4151845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 416a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 417b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 418b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 4199f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 4209f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 4219f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 4221845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 4231845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 4241845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 425a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 426d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 4272b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// SimplifyXorInst - Given operands for a Xor, see if we can 4282b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// fold the result. If not, this returns null. 4292b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sandsstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 4302b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 4312b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 4322b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 4332b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 4342b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 4352b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Ops, 2, TD); 4362b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 4372b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4382b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // Canonicalize the constant to the RHS. 4392b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands std::swap(Op0, Op1); 4402b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 4412b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4422b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ undef -> undef 4432b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (isa<UndefValue>(Op1)) 444f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Op1; 4452b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4462b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ 0 = A 4472b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 4482b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 4492b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4502b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ A = 0 4512b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Op0 == Op1) 4522b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getNullValue(Op0->getType()); 4532b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4542b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ ~A = ~A ^ A = -1 455e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 4562b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 4572b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (match(Op1, m_Not(m_Value(A))) && A == Op0)) 4582b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getAllOnesValue(Op0->getType()); 4592b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4602b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // (A ^ B) ^ A = B 4612b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op0, m_Xor(m_Value(A), m_Value(B))) && 4622b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (A == Op1 || B == Op1)) 4632b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return A == Op1 ? B : A; 4642b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4652b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ (A ^ B) = B 4662b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Xor(m_Value(A), m_Value(B))) && 4672b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (A == Op0 || B == Op0)) 4682b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return A == Op0 ? B : A; 4692b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 47087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Xor over selects and phi nodes is pointless, so don't bother. 47187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A ^ select(cond, B, C)" means evaluating 47287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 47387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 47487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 47587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 47687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 47787689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 4782b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4792b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return 0; 4802b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 4812b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 4822b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan SandsValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 4832b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT) { 4842b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 4852b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 4862b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 487210c5d4880b525e064088b6fec713260128c16ebChris Lattnerstatic const Type *GetCompareTy(Value *Op) { 488210c5d4880b525e064088b6fec713260128c16ebChris Lattner return CmpInst::makeCmpResultType(Op->getType()); 489210c5d4880b525e064088b6fec713260128c16ebChris Lattner} 490210c5d4880b525e064088b6fec713260128c16ebChris Lattner 4919dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 4929dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 493a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 4941845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 4951845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 4969f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 4979dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 49812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 499d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 5008f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 5018f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 502d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 503d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 504d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 505d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 506d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 50712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 508210c5d4880b525e064088b6fec713260128c16ebChris Lattner // ITy - This is the return type of the compare we're considering. 509210c5d4880b525e064088b6fec713260128c16ebChris Lattner const Type *ITy = GetCompareTy(LHS); 51012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 511210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp X, X -> true/false 512c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 513c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // because X could be 0. 514c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner if (LHS == RHS || isa<UndefValue>(RHS)) 515210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 51612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 517210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 518210c5d4880b525e064088b6fec713260128c16ebChris Lattner // addresses never equal each other! We already know that Op0 != Op1. 51912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 520210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(LHS)) && 52112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 522210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(RHS))) 523210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 52412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 525210c5d4880b525e064088b6fec713260128c16ebChris Lattner // See if we are doing a comparison with a constant. 526210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 527210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If we have an icmp le or icmp ge instruction, turn it into the 528210c5d4880b525e064088b6fec713260128c16ebChris Lattner // appropriate icmp lt or icmp gt instruction. This allows us to rely on 529210c5d4880b525e064088b6fec713260128c16ebChris Lattner // them being folded in the code below. 530210c5d4880b525e064088b6fec713260128c16ebChris Lattner switch (Pred) { 531210c5d4880b525e064088b6fec713260128c16ebChris Lattner default: break; 532210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_ULE: 533210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 534210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 535210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 536210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SLE: 537210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 538210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 539210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 540210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_UGE: 541210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(false)) // A >=u MIN -> TRUE 542210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 543210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 544210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SGE: 545210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(true)) // A >=s MIN -> TRUE 546210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 547210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 548210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 549210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 5501ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 5511ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // If the comparison is with the result of a select instruction, check whether 5521ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // comparing with either branch of the select always yields the same value. 553a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 5541845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 555a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 556a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 557a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 558a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 559a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 5601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 5613bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 5621ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 5639dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return 0; 5649dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 5659dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 566a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 5671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 5681845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 569a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 570a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 5719dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 5729dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 573a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 5741845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 5751845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 5769dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 5779dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 5789dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 579d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 5809dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 5819dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 58212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 583d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 584d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 585d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 586d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 58712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 588210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Fold trivial predicates. 589210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_FALSE) 590210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 591210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_TRUE) 592210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 593210c5d4880b525e064088b6fec713260128c16ebChris Lattner 594210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 595210c5d4880b525e064088b6fec713260128c16ebChris Lattner return UndefValue::get(GetCompareTy(LHS)); 596210c5d4880b525e064088b6fec713260128c16ebChris Lattner 597210c5d4880b525e064088b6fec713260128c16ebChris Lattner // fcmp x,x -> true/false. Not all compares are foldable. 598210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (LHS == RHS) { 599210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isTrueWhenEqual(Pred)) 600210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 601210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isFalseWhenEqual(Pred)) 602210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 603210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 60412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 605210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Handle fcmp with constant RHS 606210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 607210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If the constant is a nan, see if we can fold the comparison based on it. 608210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 609210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CFP->getValueAPF().isNaN()) { 610210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 611210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getFalse(CFP->getContext()); 612210c5d4880b525e064088b6fec713260128c16ebChris Lattner assert(FCmpInst::isUnordered(Pred) && 613210c5d4880b525e064088b6fec713260128c16ebChris Lattner "Comparison must be either ordered or unordered!"); 614210c5d4880b525e064088b6fec713260128c16ebChris Lattner // True if unordered. 615210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CFP->getContext()); 616210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 6176b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // Check whether the constant is an infinity. 6186b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isInfinity()) { 6196b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isNegative()) { 6206b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 6216b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OLT: 6226b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and less than negative infinity. 6236b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 6246b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_UGE: 6256b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with or at least negative infinity. 6266b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 6276b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 6286b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 6296b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 6306b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } else { 6316b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 6326b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OGT: 6336b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and greater than infinity. 6346b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 6356b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_ULE: 6366b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with and at most infinity. 6376b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 6386b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 6396b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 6406b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 6416b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 6426b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 643210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 644210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 64512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 64692826def593df7a422c7b07f09342febce81ddd3Duncan Sands // If the comparison is with the result of a select instruction, check whether 64792826def593df7a422c7b07f09342febce81ddd3Duncan Sands // comparing with either branch of the select always yields the same value. 648a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 6491845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 650a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 651a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 652a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 653a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 654a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 6551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 6563bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 65792826def593df7a422c7b07f09342febce81ddd3Duncan Sands 6589f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 6599f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 6609f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 661a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 6621845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 6631845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 664a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 665a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 666047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 667047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// the result. If not, this returns null. 668047542669a20505fc7c5f2d93caa5610aa3db2c5Chris LattnerValue *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 6691845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 670047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select true, X, Y -> X 671047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select false, X, Y -> Y 672047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 673047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return CB->getZExtValue() ? TrueVal : FalseVal; 67412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 675047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select C, X, X -> X 676047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (TrueVal == FalseVal) 677047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 67812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 679047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 680047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 681047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 682047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 683047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 684047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<Constant>(TrueVal)) 685047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 686047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 687047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner } 68812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 689047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return 0; 690047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner} 691047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 692c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 693c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// fold the result. If not, this returns null. 694c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris LattnerValue *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 6951845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 69685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // The type of the GEP pointer operand. 69785bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()); 69885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands 699c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P -> P. 700c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 1) 701c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 702c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 70385bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands if (isa<UndefValue>(Ops[0])) { 70485bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // Compute the (pointer) type returned by the GEP instruction. 70585bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1], 70685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands NumOps-1); 70785bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 70885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands return UndefValue::get(GEPTy); 70985bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands } 710c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 711e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (NumOps == 2) { 712e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, 0 -> P. 713c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 714c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (C->isZero()) 715c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 716e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, N -> P if P points to a type of zero size. 717e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (TD) { 71885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *Ty = PtrTy->getElementType(); 719a63395a30f9227bde826749d3480046301b47332Duncan Sands if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 720e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands return Ops[0]; 721e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 722e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 72312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 724c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // Check to see if this is constant foldable. 725c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner for (unsigned i = 0; i != NumOps; ++i) 726c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (!isa<Constant>(Ops[i])) 727c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return 0; 72812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 729c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 730c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner (Constant *const*)Ops+1, NumOps-1); 731c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner} 732c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 733ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 734ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sandsstatic Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 735ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If all of the PHI's incoming values are the same then replace the PHI node 736ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // with the common value. 737ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *CommonValue = 0; 738ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands bool HasUndefInput = false; 739ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 740ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *Incoming = PN->getIncomingValue(i); 741ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 742ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (Incoming == PN) continue; 743ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (isa<UndefValue>(Incoming)) { 744ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // Remember that we saw an undef value, but otherwise ignore them. 745ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands HasUndefInput = true; 746ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands continue; 747ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 748ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (CommonValue && Incoming != CommonValue) 749ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return 0; // Not the same, bail out. 750ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands CommonValue = Incoming; 751ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 752ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 753ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If CommonValue is null then all of the incoming values were either undef or 754ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // equal to the phi node itself. 755ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (!CommonValue) 756ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return UndefValue::get(PN->getType()); 757ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 758ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If we have a PHI node like phi(X, undef, X), where X is defined by some 759ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // instruction, we cannot return X as the result of the PHI node unless it 760ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // dominates the PHI block. 761ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (HasUndefInput) 762ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 763ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 764ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return CommonValue; 765ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands} 766ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 767c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 768d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner//=== Helper functions for higher up the class hierarchy. 7699dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 770d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 771d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 772a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 7731845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 7741845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 775d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner switch (Opcode) { 7761845009290e4d804ad377927bd8a08cca3036adcDuncan Sands case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 7771845009290e4d804ad377927bd8a08cca3036adcDuncan Sands case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse); 778d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner default: 779d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) 780d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 781d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *COps[] = {CLHS, CRHS}; 782d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 783d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 784b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 785b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 786b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 787a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 7881845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 7891845009290e4d804ad377927bd8a08cca3036adcDuncan Sands MaxRecurse-1)) 790a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 791a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 792a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 793a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 794a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 7951845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1)) 796b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 797b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 798d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 799d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 800d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 8019dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 80212a86f5b3199e72e6d967781acc76340f5920e46Duncan SandsValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 8031845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 8041845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 805a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 806a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 8079dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 8089dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. 809a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 8101845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 8111845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 8129dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 8131845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 8141845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 8159dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 8169dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 817a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 8181845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 8191845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 820a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 821e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 822e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// SimplifyInstruction - See if we can compute a simplified version of this 823e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// instruction. If not, this returns null. 824eff0581583ef10e2872e9baf537a04b67d992101Duncan SandsValue *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 825eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 826d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Value *Result; 827d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 828e34537856a544c83513e390ac9552a8bc3823346Chris Lattner switch (I->getOpcode()) { 829e34537856a544c83513e390ac9552a8bc3823346Chris Lattner default: 830d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = ConstantFoldInstruction(I, TD); 831d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 8328aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner case Instruction::Add: 833d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 834d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 835d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 836d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands TD, DT); 837d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 838e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::And: 839d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 840d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 841e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::Or: 842d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 843d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 8442b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands case Instruction::Xor: 8452b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 8462b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands break; 847e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::ICmp: 848d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 849d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 850d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 851e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::FCmp: 852d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 853d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 854d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 855047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner case Instruction::Select: 856d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 857d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(2), TD, DT); 858d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 859c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner case Instruction::GetElementPtr: { 860c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 861d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 862d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 863c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner } 864cd6636c737a82949ad13db2d0d918af6424fb78bDuncan Sands case Instruction::PHI: 865d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyPHINode(cast<PHINode>(I), DT); 866d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 867e34537856a544c83513e390ac9552a8bc3823346Chris Lattner } 868d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 869d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// If called on unreachable code, the above logic may report that the 870d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// instruction simplified to itself. Make life easier for users by 871f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands /// detecting that case here, returning a safe value instead. 872f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Result == I ? UndefValue::get(I->getType()) : Result; 873e34537856a544c83513e390ac9552a8bc3823346Chris Lattner} 874e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 87540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 87640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// delete the From instruction. In addition to a basic RAUW, this does a 87740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursive simplification of the newly formed instructions. This catches 87840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// things where one simplification exposes other opportunities. This only 87940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// simplifies and deletes scalar operations, it does not change the CFG. 88040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 88140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 882eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const TargetData *TD, 883eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 88440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 88512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 886d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 887d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // we can know if it gets deleted out from under us or replaced in a 888d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // recursive simplification. 88940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH FromHandle(From); 890d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner WeakVH ToHandle(To); 89112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 89240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (!From->use_empty()) { 89340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Update the instruction to use the new value. 894d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Use &TheUse = From->use_begin().getUse(); 895d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Instruction *User = cast<Instruction>(TheUse.getUser()); 896d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner TheUse = To; 897d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner 898d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Check to see if the instruction can be folded due to the operand 899d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // replacement. For example changing (or X, Y) into (or X, -1) can replace 900d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // the 'or' with -1. 901d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Value *SimplifiedVal; 902d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner { 903d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Sanity check to make sure 'User' doesn't dangle across 904d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // SimplifyInstruction. 905d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner AssertingVH<> UserHandle(User); 90612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 907eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands SimplifiedVal = SimplifyInstruction(User, TD, DT); 908d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (SimplifiedVal == 0) continue; 90940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 91012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 911d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Recursively simplify this user to the new value. 912eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 913d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 914d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner To = ToHandle; 91512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 916d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner assert(ToHandle && "To value deleted by recursive simplification?"); 91712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 918d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If the recursive simplification ended up revisiting and deleting 919d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // 'From' then we're done. 920d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (From == 0) 921d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner return; 92240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 92312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 924d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If 'From' has value handles referring to it, do a real RAUW to update them. 925d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From->replaceAllUsesWith(To); 92612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 92740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner From->eraseFromParent(); 92840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 929