InstructionSimplify.cpp revision 566edb04b890cebca8f2eefa37af7371a1e756c9
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 14ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands// ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been 15ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands// simplified: This is usually true and assuming it simplifies the logic (if 16ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands// they have not been simplified then results are correct but maybe suboptimal). 179f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 189f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner//===----------------------------------------------------------------------===// 199f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 209f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/InstructionSimplify.h" 219f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/ConstantFolding.h" 221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Analysis/Dominators.h" 23d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner#include "llvm/Support/PatternMatch.h" 241845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Support/ValueHandle.h" 25e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands#include "llvm/Target/TargetData.h" 269f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattnerusing namespace llvm; 27d06094f0682f2ede03caff4892b1a57469896d48Chris Lattnerusing namespace llvm::PatternMatch; 289f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 291845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#define RecursionLimit 3 30a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 31a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 321845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 33a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 341845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 351845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 361845009290e4d804ad377927bd8a08cca3036adcDuncan Sands/// ValueDominatesPHI - Does the given value dominate the specified phi node? 371845009290e4d804ad377927bd8a08cca3036adcDuncan Sandsstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Instruction *I = dyn_cast<Instruction>(V); 391845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!I) 401845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Arguments and constants dominate all instructions. 411845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 421845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 431845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // If we have a DominatorTree then do a precise test. 441845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (DT) 451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return DT->dominates(I, P); 461845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 471845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Otherwise, if the instruction is in the entry block, and is not an invoke, 481845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // then it obviously dominates all phi nodes. 491845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 501845009290e4d804ad377927bd8a08cca3036adcDuncan Sands !isa<InvokeInst>(I)) 511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 531845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return false; 541845009290e4d804ad377927bd8a08cca3036adcDuncan Sands} 55a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 56566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands// SimplifyAssociativeBinOp - Generic simplifications for associative binary 57566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands// operations. Returns the simpler value, or null if none was found. 58566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sandsstatic Value *SimplifyAssociativeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 59566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const TargetData *TD, 60566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const DominatorTree *DT, 61566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands unsigned MaxRecurse) { 62566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 63566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 64566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 65566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!MaxRecurse--) 66566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 67566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 68566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 69566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 70566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 71566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 72566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 73566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 74566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 75566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 76566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 77566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "B op C" simplify? 78566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 79566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "A op V" if it simplifies or is already available. 80566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "A op V" is just the LHS. 81566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (V == B) 82566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return LHS; 83566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "A op V" if it simplifies. 84566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) 85566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 86566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 87566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 88566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 89566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 90566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 91566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 92566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 93566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 94566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 95566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "A op B" simplify? 96566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) { 97566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op C" if it simplifies or is already available. 98566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "V op C" is just the RHS. 99566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (V == B) 100566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return RHS; 101566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op C" if it simplifies. 102566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) 103566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 104566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 105566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 106566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 107566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // The remaining transforms require commutativity as well as associativity. 108566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!Instruction::isCommutative(Opcode)) 109566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 110566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 111566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 112566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 113566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 114566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 115566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 116566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 117566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 118566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 119566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op B" if it simplifies or is already available. 120566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals A then "V op B" is just the LHS. 121566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (V == A) 122566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return LHS; 123566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op B" if it simplifies. 124566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) 125566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 126566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 127566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 128566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 129566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 130566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 131566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 132566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 133566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 134566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 135566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 136566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 137566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "B op V" if it simplifies or is already available. 138566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals C then "B op V" is just the RHS. 139566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (V == C) 140566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return RHS; 141566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "B op V" if it simplifies. 142566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) 143566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 144566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 145566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 146566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 147566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 148566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands} 149566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 150b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadBinOpOverSelect - In the case of a binary operation with a select 151b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// instruction as an operand, try to simplify the binop by seeing whether 152b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// evaluating it on both branches of the select results in the same value. 153b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// Returns the common value if so, otherwise returns null. 154b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 1551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, 1561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 1571845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 158b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI; 159b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (isa<SelectInst>(LHS)) { 160b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(LHS); 161b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 162b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 163b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(RHS); 164b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 165b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 166b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Evaluate the BinOp on the true and false branches of the select. 167b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *TV; 168b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *FV; 169b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (SI == LHS) { 1701845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse); 1711845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse); 172b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 1731845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse); 1741845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse); 175b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 176b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 177b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they simplified to the same value, then return the common value. 178b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they both failed to simplify then return null. 179b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == FV) 180b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 181b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 182b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified to undef, return the other one. 183b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV && isa<UndefValue>(TV)) 184b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return FV; 185b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (FV && isa<UndefValue>(FV)) 186b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 187b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 188b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If applying the operation did not change the true and false select values, 189b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // then the result of the binop is the select itself. 190b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 191b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return SI; 192b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 193b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified and the other did not, and the simplified 194b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // value is equal to the unsimplified one, return the simplified value. 195b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // For example, select (cond, X, X & Z) & Z -> X & Z. 196b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if ((FV && !TV) || (TV && !FV)) { 197b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Check that the simplified value has the form "X op Y" where "op" is the 198b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // same as the original operation. 199b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 200b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified && Simplified->getOpcode() == Opcode) { 201b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 202b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // We already know that "op" is the same as for the simplified value. See 203b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // if the operands match too. If so, return the simplified value. 204b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 205b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 206b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 207b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->getOperand(0) == UnsimplifiedLHS && 208b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedRHS) 209b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 210b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->isCommutative() && 211b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedLHS && 212b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(0) == UnsimplifiedRHS) 213b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 214b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 215b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 216b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 217b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 218b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 219b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 220b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 221b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// try to simplify the comparison by seeing whether both branches of the select 222b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// result in the same value. Returns the common value if so, otherwise returns 223b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// null. 224b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 225a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *RHS, const TargetData *TD, 2261845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 227a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 228b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Make sure the select is on the LHS. 229b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (!isa<SelectInst>(LHS)) { 230b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands std::swap(LHS, RHS); 231b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 232b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 233b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 234b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI = cast<SelectInst>(LHS); 235b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 236b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Now that we have "cmp select(cond, TV, FV), RHS", analyse it. 237b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Does "cmp TV, RHS" simplify? 2381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT, 239a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 240b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! Does "cmp FV, RHS" simplify? 2411845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT, 242a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 243b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! If they simplified to the same value, then use it as the 244b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // result of the original comparison. 245b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TCmp == FCmp) 246b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TCmp; 247b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 248b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 249b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 250a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 251a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 252a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// it on the incoming phi values yields the same result for every value. If so 253a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// returns the common value, otherwise returns null. 254a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 2551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 2561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 257a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI; 258a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (isa<PHINode>(LHS)) { 259a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(LHS); 2601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 2611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 2621845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 263a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } else { 264a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 265a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(RHS); 2661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if LHS and the phi may be mutually interdependent due to a loop. 2671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(LHS, PI, DT)) 2681845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 269a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 270a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 271a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 272a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 273a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 274552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 275ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 276552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 277a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *V = PI == LHS ? 2781845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 2791845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 280a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 281a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 282a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 283a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 284a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 285a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 286a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 287a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 288a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 289a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 290a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 291a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// try to simplify the comparison by seeing whether comparing with all of the 292a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// incoming phi values yields the same result every time. If so returns the 293a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// common result, otherwise returns null. 294a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 2951845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 2961845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 297a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Make sure the phi is on the LHS. 298a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!isa<PHINode>(LHS)) { 299a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands std::swap(LHS, RHS); 300a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 301a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 302a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 303a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI = cast<PHINode>(LHS); 304a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 3051845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 3061845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 3071845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 3081845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 309a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 310a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 311a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 312552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 313ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 314552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 3151845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 316a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 317a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 318a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 319a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 320a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 321a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 322a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 323a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 324a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 325a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 3268aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 327d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 328ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 329ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT, 330ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 331d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 332d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 333d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 3348aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 3358aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Ops, 2, TD); 3368aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 33712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 3388aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // Canonicalize the constant to the RHS. 3398aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner std::swap(Op0, Op1); 3408aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 34112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 342fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + undef -> undef 343fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (isa<UndefValue>(Op1)) 344fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op1; 34512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 346fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + 0 -> X 347fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 348fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 349fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 350fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + (Y - X) -> Y 351fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y - X) + X -> Y 352ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands // Eg: X + -X -> 0 353fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Value *Y = 0; 354fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 355fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 356fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Y; 357fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 358fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + ~X -> -1 since ~X = -X-1 359fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op0, m_Not(m_Specific(Op1))) || 360fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op1, m_Not(m_Specific(Op0)))) 361fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getAllOnesValue(Op0->getType()); 36287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 363566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 364566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT, 365566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 366566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 367566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 36887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Add over selects and phi nodes is pointless, so don't bother. 36987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A + select(cond, B, C)" means evaluating 37087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 37187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 37287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 37387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 37487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 37587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 37687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 3778aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return 0; 3788aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner} 3798aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner 380ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 381ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 382ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 383ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 384ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 385fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// SimplifySubInst - Given operands for a Sub, see if we can 386fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// fold the result. If not, this returns null. 387ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 388ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *, 389ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 390fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) 391fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 392fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Constant *Ops[] = { CLHS, CRHS }; 393fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 394fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Ops, 2, TD); 395fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands } 396fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 397fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - undef -> undef 398fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // undef - X -> undef 399fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1)) 400fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return UndefValue::get(Op0->getType()); 401fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 402fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - 0 -> X 403fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 404fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 405fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 406fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - X -> 0 407fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Op0 == Op1) 408fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getNullValue(Op0->getType()); 409fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 410fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (X + Y) - Y -> X 411fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y + X) - Y -> X 412fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Value *X = 0; 413fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op0, m_Add(m_Value(X), m_Specific(Op1))) || 414fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op0, m_Add(m_Specific(Op1), m_Value(X)))) 415fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return X; 416fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 417fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading Sub over selects and phi nodes is pointless, so don't bother. 418fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading over the select in "A - select(cond, B, C)" means evaluating 419fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 420fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 421fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 422fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // have been simplified to the common value of B and C already. Analysing 423fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 424fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // for threading over phi nodes. 425fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 426fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return 0; 427fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands} 428fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 429ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 430ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 431ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 432ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 433ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 4348aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 4358aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// fold the result. If not, this returns null. 436a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 4371845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 4388aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 4398aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 4408aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 441d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 442d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 443d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 44412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 445d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 446d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 447d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 44812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 449d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & undef -> 0 450d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 451d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 45212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 453d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & X = X 454d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 455d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 45612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 4572b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & 0 = 0 4582b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 459d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 46012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 4612b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & -1 = X 4622b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 4632b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 46412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 465d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & ~A = ~A & A = 0 466e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 46770ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 46870ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 469d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 47012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 471d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A | ?) & A = A 472d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 473d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 474d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 47512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 476d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & (A | ?) = A 477d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 478d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 479d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 48012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 481566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 482566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT, 483566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 484566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 4856844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 486b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 487b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 488a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 4891845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 490a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 491a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 492a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 493a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 494a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 495a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 4961845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 497a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 498b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 499b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 500d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 501d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 5029f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 5031845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 5041845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 5051845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 506a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 507a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 508d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 5099f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner/// fold the result. If not, this returns null. 510a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 5111845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 512d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 513d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 514d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 515d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 516d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 517d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 51812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 519d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 520d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 521d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 52212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 523d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | undef -> -1 524d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 525d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 52612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 527d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | X = X 528d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 529d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 530d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 5312b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | 0 = X 5322b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 533d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 53412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 5352b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | -1 = -1 5362b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 5372b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op1; 53812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 539d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | ~A = ~A | A = -1 540e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 54170ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 54270ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 543d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 54412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 545d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A & ?) | A = A 546d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(B))) && 547d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 548d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 54912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 550d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | (A & ?) = A 551d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_And(m_Value(A), m_Value(B))) && 552d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 553d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 55412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 555566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 556566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT, 557566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 558566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 5596844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 560b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 561b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 562a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))) 5631845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 564a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 565a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 566a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 567a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 568a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 569a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(Op0) || isa<PHINode>(Op1))) 5701845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 571a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse-1)) 572b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 573b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 5749f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 5759f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 5769f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 5771845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 5781845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 5791845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 580a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 581d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 5822b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// SimplifyXorInst - Given operands for a Xor, see if we can 5832b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// fold the result. If not, this returns null. 5842b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sandsstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 5852b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 5862b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 5872b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 5882b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 5892b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 5902b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Ops, 2, TD); 5912b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 5922b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 5932b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // Canonicalize the constant to the RHS. 5942b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands std::swap(Op0, Op1); 5952b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 5962b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 5972b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ undef -> undef 5982b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (isa<UndefValue>(Op1)) 599f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Op1; 6002b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 6012b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ 0 = A 6022b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 6032b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 6042b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 6052b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ A = 0 6062b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Op0 == Op1) 6072b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getNullValue(Op0->getType()); 6082b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 6092b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ ~A = ~A ^ A = -1 610566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = 0; 6112b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 6122b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (match(Op1, m_Not(m_Value(A))) && A == Op0)) 6132b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getAllOnesValue(Op0->getType()); 6142b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 615566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 616566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT, 617566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 618566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 6192b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 62087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Xor over selects and phi nodes is pointless, so don't bother. 62187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A ^ select(cond, B, C)" means evaluating 62287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 62387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 62487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 62587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 62687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 62787689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 6282b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 6292b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return 0; 6302b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 6312b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 6322b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan SandsValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 6332b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT) { 6342b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 6352b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 6362b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 637210c5d4880b525e064088b6fec713260128c16ebChris Lattnerstatic const Type *GetCompareTy(Value *Op) { 638210c5d4880b525e064088b6fec713260128c16ebChris Lattner return CmpInst::makeCmpResultType(Op->getType()); 639210c5d4880b525e064088b6fec713260128c16ebChris Lattner} 640210c5d4880b525e064088b6fec713260128c16ebChris Lattner 6419dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 6429dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 643a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 6441845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 6451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 6469f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 6479dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 64812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 649d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 6508f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 6518f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 652d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 653d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 654d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 655d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 656d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 65712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 658210c5d4880b525e064088b6fec713260128c16ebChris Lattner // ITy - This is the return type of the compare we're considering. 659210c5d4880b525e064088b6fec713260128c16ebChris Lattner const Type *ITy = GetCompareTy(LHS); 66012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 661210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp X, X -> true/false 662c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 663c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // because X could be 0. 664c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner if (LHS == RHS || isa<UndefValue>(RHS)) 665210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 66612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 667210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 668210c5d4880b525e064088b6fec713260128c16ebChris Lattner // addresses never equal each other! We already know that Op0 != Op1. 66912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 670210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(LHS)) && 67112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 672210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(RHS))) 673210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 67412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 675210c5d4880b525e064088b6fec713260128c16ebChris Lattner // See if we are doing a comparison with a constant. 676210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 677210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If we have an icmp le or icmp ge instruction, turn it into the 678210c5d4880b525e064088b6fec713260128c16ebChris Lattner // appropriate icmp lt or icmp gt instruction. This allows us to rely on 679210c5d4880b525e064088b6fec713260128c16ebChris Lattner // them being folded in the code below. 680210c5d4880b525e064088b6fec713260128c16ebChris Lattner switch (Pred) { 681210c5d4880b525e064088b6fec713260128c16ebChris Lattner default: break; 682210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_ULE: 683210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 684210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 685210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 686210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SLE: 687210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 688210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 689210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 690210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_UGE: 691210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(false)) // A >=u MIN -> TRUE 692210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 693210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 694210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SGE: 695210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(true)) // A >=s MIN -> TRUE 696210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 697210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 698210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 699210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 7001ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 7011ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // If the comparison is with the result of a select instruction, check whether 7021ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // comparing with either branch of the select always yields the same value. 703a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 7041845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 705a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 706a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 707a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 708a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 709a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 7101845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 7113bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 7121ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 7139dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return 0; 7149dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 7159dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 716a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 7171845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 7181845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 719a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 720a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 7219dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 7229dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 723a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 7241845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 7251845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 7269dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 7279dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 7289dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 729d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 7309dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 7319dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 73212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 733d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 734d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 735d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 736d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 73712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 738210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Fold trivial predicates. 739210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_FALSE) 740210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 741210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_TRUE) 742210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 743210c5d4880b525e064088b6fec713260128c16ebChris Lattner 744210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 745210c5d4880b525e064088b6fec713260128c16ebChris Lattner return UndefValue::get(GetCompareTy(LHS)); 746210c5d4880b525e064088b6fec713260128c16ebChris Lattner 747210c5d4880b525e064088b6fec713260128c16ebChris Lattner // fcmp x,x -> true/false. Not all compares are foldable. 748210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (LHS == RHS) { 749210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isTrueWhenEqual(Pred)) 750210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 751210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isFalseWhenEqual(Pred)) 752210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 753210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 75412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 755210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Handle fcmp with constant RHS 756210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 757210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If the constant is a nan, see if we can fold the comparison based on it. 758210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 759210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CFP->getValueAPF().isNaN()) { 760210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 761210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getFalse(CFP->getContext()); 762210c5d4880b525e064088b6fec713260128c16ebChris Lattner assert(FCmpInst::isUnordered(Pred) && 763210c5d4880b525e064088b6fec713260128c16ebChris Lattner "Comparison must be either ordered or unordered!"); 764210c5d4880b525e064088b6fec713260128c16ebChris Lattner // True if unordered. 765210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CFP->getContext()); 766210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 7676b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // Check whether the constant is an infinity. 7686b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isInfinity()) { 7696b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isNegative()) { 7706b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 7716b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OLT: 7726b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and less than negative infinity. 7736b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 7746b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_UGE: 7756b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with or at least negative infinity. 7766b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 7776b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 7786b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 7796b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 7806b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } else { 7816b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 7826b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OGT: 7836b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and greater than infinity. 7846b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 7856b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_ULE: 7866b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with and at most infinity. 7876b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 7886b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 7896b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 7906b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 7916b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 7926b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 793210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 794210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 79512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 79692826def593df7a422c7b07f09342febce81ddd3Duncan Sands // If the comparison is with the result of a select instruction, check whether 79792826def593df7a422c7b07f09342febce81ddd3Duncan Sands // comparing with either branch of the select always yields the same value. 798a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 7991845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 800a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 801a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 802a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 803a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 804a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 8051845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse-1)) 8063bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 80792826def593df7a422c7b07f09342febce81ddd3Duncan Sands 8089f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 8099f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 8109f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 811a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 8121845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 8131845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 814a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 815a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 816047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 817047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// the result. If not, this returns null. 818047542669a20505fc7c5f2d93caa5610aa3db2c5Chris LattnerValue *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 8191845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 820047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select true, X, Y -> X 821047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select false, X, Y -> Y 822047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 823047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return CB->getZExtValue() ? TrueVal : FalseVal; 82412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 825047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select C, X, X -> X 826047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (TrueVal == FalseVal) 827047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 82812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 829047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 830047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 831047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 832047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 833047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 834047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<Constant>(TrueVal)) 835047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 836047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 837047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner } 83812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 839047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return 0; 840047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner} 841047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 842c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 843c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// fold the result. If not, this returns null. 844c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris LattnerValue *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 8451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 84685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // The type of the GEP pointer operand. 84785bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()); 84885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands 849c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P -> P. 850c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 1) 851c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 852c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 85385bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands if (isa<UndefValue>(Ops[0])) { 85485bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // Compute the (pointer) type returned by the GEP instruction. 85585bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1], 85685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands NumOps-1); 85785bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 85885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands return UndefValue::get(GEPTy); 85985bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands } 860c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 861e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (NumOps == 2) { 862e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, 0 -> P. 863c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 864c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (C->isZero()) 865c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 866e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, N -> P if P points to a type of zero size. 867e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (TD) { 86885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *Ty = PtrTy->getElementType(); 869a63395a30f9227bde826749d3480046301b47332Duncan Sands if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 870e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands return Ops[0]; 871e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 872e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 87312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 874c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // Check to see if this is constant foldable. 875c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner for (unsigned i = 0; i != NumOps; ++i) 876c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (!isa<Constant>(Ops[i])) 877c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return 0; 87812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 879c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 880c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner (Constant *const*)Ops+1, NumOps-1); 881c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner} 882c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 883ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 884ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sandsstatic Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 885ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If all of the PHI's incoming values are the same then replace the PHI node 886ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // with the common value. 887ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *CommonValue = 0; 888ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands bool HasUndefInput = false; 889ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 890ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *Incoming = PN->getIncomingValue(i); 891ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 892ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (Incoming == PN) continue; 893ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (isa<UndefValue>(Incoming)) { 894ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // Remember that we saw an undef value, but otherwise ignore them. 895ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands HasUndefInput = true; 896ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands continue; 897ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 898ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (CommonValue && Incoming != CommonValue) 899ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return 0; // Not the same, bail out. 900ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands CommonValue = Incoming; 901ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 902ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 903ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If CommonValue is null then all of the incoming values were either undef or 904ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // equal to the phi node itself. 905ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (!CommonValue) 906ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return UndefValue::get(PN->getType()); 907ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 908ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If we have a PHI node like phi(X, undef, X), where X is defined by some 909ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // instruction, we cannot return X as the result of the PHI node unless it 910ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // dominates the PHI block. 911ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (HasUndefInput) 912ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 913ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 914ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return CommonValue; 915ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands} 916ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 917c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 918d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner//=== Helper functions for higher up the class hierarchy. 9199dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 920d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 921d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 922a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 9231845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 9241845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 925d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner switch (Opcode) { 9261845009290e4d804ad377927bd8a08cca3036adcDuncan Sands case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 9271845009290e4d804ad377927bd8a08cca3036adcDuncan Sands case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse); 928ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse); 929ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false, 930ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands /* isNUW */ false, TD, DT, 931ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands MaxRecurse); 932ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false, 933ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands /* isNUW */ false, TD, DT, 934ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands MaxRecurse); 935d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner default: 936d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) 937d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 938d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *COps[] = {CLHS, CRHS}; 939d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 940d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 941b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 942566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If the operation is associative, try some generic simplifications. 943566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Instruction::isAssociative(Opcode)) 944566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT, 945566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 946566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 947566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 948b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 949b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 950a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))) 9511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 9521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands MaxRecurse-1)) 953a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 954a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 955a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 956a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 957a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (MaxRecurse && (isa<PHINode>(LHS) || isa<PHINode>(RHS))) 9581845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse-1)) 959b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 960b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 961d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 962d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 963d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 9649dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 96512a86f5b3199e72e6d967781acc76340f5920e46Duncan SandsValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 9661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 9671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 968a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 969a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 9709dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 9719dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. 972a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 9731845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 9741845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 9759dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 9761845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 9771845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 9789dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 9799dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 980a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 9811845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 9821845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 983a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 984e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 985e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// SimplifyInstruction - See if we can compute a simplified version of this 986e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// instruction. If not, this returns null. 987eff0581583ef10e2872e9baf537a04b67d992101Duncan SandsValue *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 988eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 989d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Value *Result; 990d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 991e34537856a544c83513e390ac9552a8bc3823346Chris Lattner switch (I->getOpcode()) { 992e34537856a544c83513e390ac9552a8bc3823346Chris Lattner default: 993d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = ConstantFoldInstruction(I, TD); 994d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 9958aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner case Instruction::Add: 996d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 997d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 998d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 999d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands TD, DT); 1000d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1001fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands case Instruction::Sub: 1002fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 1003fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1004fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1005fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands TD, DT); 1006fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands break; 1007e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::And: 1008d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 1009d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1010e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::Or: 1011d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1012d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 10132b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands case Instruction::Xor: 10142b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 10152b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands break; 1016e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::ICmp: 1017d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 1018d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1019d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1020e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::FCmp: 1021d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 1022d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1023d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1024047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner case Instruction::Select: 1025d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 1026d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(2), TD, DT); 1027d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1028c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner case Instruction::GetElementPtr: { 1029c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 1030d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 1031d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1032c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner } 1033cd6636c737a82949ad13db2d0d918af6424fb78bDuncan Sands case Instruction::PHI: 1034d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyPHINode(cast<PHINode>(I), DT); 1035d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1036e34537856a544c83513e390ac9552a8bc3823346Chris Lattner } 1037d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1038d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// If called on unreachable code, the above logic may report that the 1039d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// instruction simplified to itself. Make life easier for users by 1040f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands /// detecting that case here, returning a safe value instead. 1041f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Result == I ? UndefValue::get(I->getType()) : Result; 1042e34537856a544c83513e390ac9552a8bc3823346Chris Lattner} 1043e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 104440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 104540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// delete the From instruction. In addition to a basic RAUW, this does a 104640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursive simplification of the newly formed instructions. This catches 104740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// things where one simplification exposes other opportunities. This only 104840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// simplifies and deletes scalar operations, it does not change the CFG. 104940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 105040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 1051eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const TargetData *TD, 1052eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 105340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 105412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1055d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 1056d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // we can know if it gets deleted out from under us or replaced in a 1057d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // recursive simplification. 105840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH FromHandle(From); 1059d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner WeakVH ToHandle(To); 106012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 106140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (!From->use_empty()) { 106240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Update the instruction to use the new value. 1063d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Use &TheUse = From->use_begin().getUse(); 1064d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Instruction *User = cast<Instruction>(TheUse.getUser()); 1065d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner TheUse = To; 1066d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner 1067d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Check to see if the instruction can be folded due to the operand 1068d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // replacement. For example changing (or X, Y) into (or X, -1) can replace 1069d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // the 'or' with -1. 1070d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Value *SimplifiedVal; 1071d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner { 1072d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Sanity check to make sure 'User' doesn't dangle across 1073d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // SimplifyInstruction. 1074d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner AssertingVH<> UserHandle(User); 107512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1076eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands SimplifiedVal = SimplifyInstruction(User, TD, DT); 1077d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (SimplifiedVal == 0) continue; 107840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 107912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1080d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Recursively simplify this user to the new value. 1081eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 1082d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 1083d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner To = ToHandle; 108412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1085d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner assert(ToHandle && "To value deleted by recursive simplification?"); 108612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1087d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If the recursive simplification ended up revisiting and deleting 1088d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // 'From' then we're done. 1089d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (From == 0) 1090d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner return; 109140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 109212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1093d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If 'From' has value handles referring to it, do a real RAUW to update them. 1094d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From->replaceAllUsesWith(To); 109512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 109640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner From->eraseFromParent(); 109740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 1098