InstructionSimplify.cpp revision 81a0dc911586c77421c2255aa417dc9b350b9e20
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 20a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands#define DEBUG_TYPE "instsimplify" 21a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands#include "llvm/ADT/Statistic.h" 229f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/InstructionSimplify.h" 239f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/ConstantFolding.h" 241845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Analysis/Dominators.h" 25d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands#include "llvm/Analysis/ValueTracking.h" 26d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner#include "llvm/Support/PatternMatch.h" 271845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Support/ValueHandle.h" 28e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands#include "llvm/Target/TargetData.h" 299f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattnerusing namespace llvm; 30d06094f0682f2ede03caff4892b1a57469896d48Chris Lattnerusing namespace llvm::PatternMatch; 319f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 3281a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattnerenum { RecursionLimit = 3 }; 33a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 34a3c44a5280042dbc0cde995675c225ede4528c6eDuncan SandsSTATISTIC(NumExpand, "Number of expansions"); 35a3c44a5280042dbc0cde995675c225ede4528c6eDuncan SandsSTATISTIC(NumFactor , "Number of factorizations"); 36a3c44a5280042dbc0cde995675c225ede4528c6eDuncan SandsSTATISTIC(NumReassoc, "Number of reassociations"); 37a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands 3882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyAndInst(Value *, Value *, const TargetData *, 3982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 40a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 411845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 42a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 431845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 4482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyOrInst(Value *, Value *, const TargetData *, 4582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 4682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyXorInst(Value *, Value *, const TargetData *, 4782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 481845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 491845009290e4d804ad377927bd8a08cca3036adcDuncan Sands/// ValueDominatesPHI - Does the given value dominate the specified phi node? 501845009290e4d804ad377927bd8a08cca3036adcDuncan Sandsstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Instruction *I = dyn_cast<Instruction>(V); 521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!I) 531845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Arguments and constants dominate all instructions. 541845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // If we have a DominatorTree then do a precise test. 571845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (DT) 581845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return DT->dominates(I, P); 591845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Otherwise, if the instruction is in the entry block, and is not an invoke, 611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // then it obviously dominates all phi nodes. 621845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 631845009290e4d804ad377927bd8a08cca3036adcDuncan Sands !isa<InvokeInst>(I)) 641845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 651845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return false; 671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands} 68a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 693421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 703421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 713421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 723421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 733421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Returns the simplified value, or null if no simplification was performed. 743421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sandsstatic Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 75e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer unsigned OpcToExpand, const TargetData *TD, 763421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 77e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand; 783421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 793421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!MaxRecurse--) 803421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 813421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 823421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Check whether the expression has the form "(A op' B) op C". 833421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 843421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Op0->getOpcode() == OpcodeToExpand) { 853421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Try turning it into "(A op C) op' (B op C)". 863421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 873421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Do "A op C" and "B op C" both simplify? 883421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *L = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) 893421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *R = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 903421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // They do! Return "L op' R" if it simplifies or is already available. 913421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 92124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) 93124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands && L == B && R == A)) { 94a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 953421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return LHS; 96a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "L op' R" if it simplifies. 98a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT, 99a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands MaxRecurse)) { 100a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1013421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 102a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1033421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1043421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1053421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1063421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Check whether the expression has the form "A op (B op' C)". 1073421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 1083421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Op1->getOpcode() == OpcodeToExpand) { 1093421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Try turning it into "(A op B) op' (A op C)". 1103421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 1113421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Do "A op B" and "A op C" both simplify? 1123421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *L = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) 1133421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *R = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) { 1143421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // They do! Return "L op' R" if it simplifies or is already available. 1153421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 116124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) 117124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands && L == C && R == B)) { 118a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1193421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return RHS; 120a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1213421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "L op' R" if it simplifies. 122a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT, 123a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands MaxRecurse)) { 124a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1253421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 126a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1273421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1283421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1293421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1303421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1313421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands} 1323421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1333421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term 1343421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// using the operation OpCodeToExtract. For example, when Opcode is Add and 1353421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)". 1363421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Returns the simplified value, or null if no simplification was performed. 1373421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sandsstatic Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 138e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer unsigned OpcToExtract, const TargetData *TD, 1393421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 140e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract; 1413421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 1423421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!MaxRecurse--) 1433421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1443421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1453421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 1463421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 1473421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1483421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!Op0 || Op0->getOpcode() != OpcodeToExtract || 1493421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands !Op1 || Op1->getOpcode() != OpcodeToExtract) 1503421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1513421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1523421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // The expression has the form "(A op' B) op (C op' D)". 15382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); 15482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); 1553421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1563421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)". 1573421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does the instruction have the form "(A op' B) op (A op' D)" or, in the 1583421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // commutative case, "(A op' B) op (C op' A)"? 159124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) { 160124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands Value *DD = A == C ? D : C; 1613421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Form "A op' (B op DD)" if it simplifies completely. 1623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does "B op DD" simplify? 1633421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, DT, MaxRecurse)) { 1643421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Return "A op' V" if it simplifies or is already available. 1651cd05bb605e3c3eee9197d3f10b628c60d0cc07aDuncan Sands // If V equals B then "A op' V" is just the LHS. If V equals DD then 1661cd05bb605e3c3eee9197d3f10b628c60d0cc07aDuncan Sands // "A op' V" is just the RHS. 167124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (V == B || V == DD) { 168a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 169124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands return V == B ? LHS : RHS; 170a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1713421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "A op' V" if it simplifies. 172a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, DT, MaxRecurse)) { 173a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 1743421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return W; 175a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1763421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1773421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1783421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1793421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)". 1803421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does the instruction have the form "(A op' B) op (C op' B)" or, in the 1813421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // commutative case, "(A op' B) op (B op' D)"? 182124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) { 183124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands Value *CC = B == D ? C : D; 1843421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Form "(A op CC) op' B" if it simplifies completely.. 1853421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does "A op CC" simplify? 1863421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, DT, MaxRecurse)) { 1873421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Return "V op' B" if it simplifies or is already available. 1881cd05bb605e3c3eee9197d3f10b628c60d0cc07aDuncan Sands // If V equals A then "V op' B" is just the LHS. If V equals CC then 1891cd05bb605e3c3eee9197d3f10b628c60d0cc07aDuncan Sands // "V op' B" is just the RHS. 190124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (V == A || V == CC) { 191a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 192124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands return V == A ? LHS : RHS; 193a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1943421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "V op' B" if it simplifies. 195a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, DT, MaxRecurse)) { 196a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 1973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return W; 198a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1993421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 2003421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 2013421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 2023421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 2033421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands} 2043421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 2053421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// SimplifyAssociativeBinOp - Generic simplifications for associative binary 2063421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// operations. Returns the simpler value, or null if none was found. 207e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramerstatic Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, 208566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const TargetData *TD, 209566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const DominatorTree *DT, 210566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands unsigned MaxRecurse) { 211e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; 212566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 213566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 214566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 215566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!MaxRecurse--) 216566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 217566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 218566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 219566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 220566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 221566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 222566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 223566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 224566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 225566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 226566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 227566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "B op C" simplify? 228566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 229566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "A op V" if it simplifies or is already available. 230566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "A op V" is just the LHS. 231124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (V == B) return LHS; 232566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "A op V" if it simplifies. 233a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) { 234a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 235566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 236a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 237566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 238566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 239566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 240566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 241566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 242566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 243566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 244566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 245566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 246566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "A op B" simplify? 247566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) { 248566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op C" if it simplifies or is already available. 249566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "V op C" is just the RHS. 250124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (V == B) return RHS; 251566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op C" if it simplifies. 252a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) { 253a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 254566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 255a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 256566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 257566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 258566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 259566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // The remaining transforms require commutativity as well as associativity. 260566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!Instruction::isCommutative(Opcode)) 261566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 262566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 263566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 264566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 265566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 266566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 267566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 268566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 269566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 270566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 271566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op B" if it simplifies or is already available. 272566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals A then "V op B" is just the LHS. 273124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (V == A) return LHS; 274566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op B" if it simplifies. 275a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) { 276a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 277566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 278a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 279566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 280566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 281566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 282566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 283566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 284566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 285566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 286566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 287566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 288566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 289566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 290566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "B op V" if it simplifies or is already available. 291566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals C then "B op V" is just the RHS. 292124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (V == C) return RHS; 293566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "B op V" if it simplifies. 294a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) { 295a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 296566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 297a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 298566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 299566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 300566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 301566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 302566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands} 303566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 304b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadBinOpOverSelect - In the case of a binary operation with a select 305b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// instruction as an operand, try to simplify the binop by seeing whether 306b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// evaluating it on both branches of the select results in the same value. 307b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// Returns the common value if so, otherwise returns null. 308b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 3091845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, 3101845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 3111845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 3120312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 3130312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 3140312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 3150312a93693abc2eb682b2b101c889959888fd883Duncan Sands 316b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI; 317b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (isa<SelectInst>(LHS)) { 318b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(LHS); 319b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 320b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 321b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(RHS); 322b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 323b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 324b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Evaluate the BinOp on the true and false branches of the select. 325b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *TV; 326b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *FV; 327b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (SI == LHS) { 3281845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse); 3291845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse); 330b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 3311845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse); 3321845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse); 333b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 334b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 3357cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // If they simplified to the same value, then return the common value. 336124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands // If they both failed to simplify then return null. 337124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (TV == FV) 338b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 339b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 340b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified to undef, return the other one. 341b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV && isa<UndefValue>(TV)) 342b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return FV; 343b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (FV && isa<UndefValue>(FV)) 344b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 345b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 346b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If applying the operation did not change the true and false select values, 347b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // then the result of the binop is the select itself. 348124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 349b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return SI; 350b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 351b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified and the other did not, and the simplified 352b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // value is equal to the unsimplified one, return the simplified value. 353b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // For example, select (cond, X, X & Z) & Z -> X & Z. 354b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if ((FV && !TV) || (TV && !FV)) { 355b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Check that the simplified value has the form "X op Y" where "op" is the 356b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // same as the original operation. 357b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 358b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified && Simplified->getOpcode() == Opcode) { 359b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 360b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // We already know that "op" is the same as for the simplified value. See 361b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // if the operands match too. If so, return the simplified value. 362b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 363b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 364b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 365124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (Simplified->getOperand(0) == UnsimplifiedLHS && 366124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands Simplified->getOperand(1) == UnsimplifiedRHS) 367b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 368b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->isCommutative() && 369124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands Simplified->getOperand(1) == UnsimplifiedLHS && 370124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands Simplified->getOperand(0) == UnsimplifiedRHS) 371b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 372b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 373b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 374b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 375b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 376b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 377b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 378b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 379b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// try to simplify the comparison by seeing whether both branches of the select 380b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// result in the same value. Returns the common value if so, otherwise returns 381b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// null. 382b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 383a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *RHS, const TargetData *TD, 3841845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 385a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 3860312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 3870312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 3880312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 3890312a93693abc2eb682b2b101c889959888fd883Duncan Sands 390b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Make sure the select is on the LHS. 391b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (!isa<SelectInst>(LHS)) { 392b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands std::swap(LHS, RHS); 393b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 394b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 395b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 396b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI = cast<SelectInst>(LHS); 397b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 39850ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. 399b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Does "cmp TV, RHS" simplify? 4001845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT, 40150ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands MaxRecurse)) { 402b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! Does "cmp FV, RHS" simplify? 4031845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT, 40450ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands MaxRecurse)) { 405b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! If they simplified to the same value, then use it as the 406b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // result of the original comparison. 407124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (TCmp == FCmp) 408b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TCmp; 40950ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands Value *Cond = SI->getCondition(); 41050ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands // If the false value simplified to false, then the result of the compare 41150ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands // is equal to "Cond && TCmp". This also catches the case when the false 41250ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands // value simplified to false and the true value to true, returning "Cond". 41350ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands if (match(FCmp, m_Zero())) 41450ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands if (Value *V = SimplifyAndInst(Cond, TCmp, TD, DT, MaxRecurse)) 41550ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands return V; 41650ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands // If the true value simplified to true, then the result of the compare 41750ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands // is equal to "Cond || FCmp". 41850ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands if (match(TCmp, m_One())) 41950ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands if (Value *V = SimplifyOrInst(Cond, FCmp, TD, DT, MaxRecurse)) 42050ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands return V; 42150ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands // Finally, if the false value simplified to true and the true value to 42250ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands // false, then the result of the compare is equal to "!Cond". 42350ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands if (match(FCmp, m_One()) && match(TCmp, m_Zero())) 42450ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands if (Value *V = 42550ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), 42650ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands TD, DT, MaxRecurse)) 42750ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands return V; 42850ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands } 42950ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands } 43050ca4d37f7f3b460c6441eb5ad14625a7d86b5d9Duncan Sands 431b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 432b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 433b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 434a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 435a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 436a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// it on the incoming phi values yields the same result for every value. If so 437a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// returns the common value, otherwise returns null. 438a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 4391845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 4401845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 4410312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 4420312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 4430312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 4440312a93693abc2eb682b2b101c889959888fd883Duncan Sands 445a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI; 446a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (isa<PHINode>(LHS)) { 447a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(LHS); 4481845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 4491845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 4501845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 451a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } else { 452a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 453a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(RHS); 4541845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if LHS and the phi may be mutually interdependent due to a loop. 4551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(LHS, PI, DT)) 4561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 457a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 458a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 459a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 460a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 461a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 462552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 463ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 464552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 465a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *V = PI == LHS ? 4661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 4671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 468a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 469a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 470a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 471a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 472a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 473a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 474a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 475a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 476a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 477a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 478a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 479a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// try to simplify the comparison by seeing whether comparing with all of the 480a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// incoming phi values yields the same result every time. If so returns the 481a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// common result, otherwise returns null. 482a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 4831845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 4841845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 4850312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 4860312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 4870312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 4880312a93693abc2eb682b2b101c889959888fd883Duncan Sands 489a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Make sure the phi is on the LHS. 490a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!isa<PHINode>(LHS)) { 491a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands std::swap(LHS, RHS); 492a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 493a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 494a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 495a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI = cast<PHINode>(LHS); 496a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 4971845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 4981845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 4991845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 5001845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 501a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 502a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 503a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 504552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 505ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 506552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 5071845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 508a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 509a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 510a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 511a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 512a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 513a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 514a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 515a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 516a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 517a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 5188aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 519d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 520ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 521ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT, 522ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 523d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 524d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 525d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 5268aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 5278aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Ops, 2, TD); 5288aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 52912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 5308aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // Canonicalize the constant to the RHS. 5318aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner std::swap(Op0, Op1); 5328aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 53312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 534fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + undef -> undef 535f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op1, m_Undef())) 536fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op1; 53712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 538fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + 0 -> X 539fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 540fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 541fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 542fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + (Y - X) -> Y 543fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y - X) + X -> Y 544ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands // Eg: X + -X -> 0 545124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands Value *Y = 0; 546124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 547124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 548fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Y; 549fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 550fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + ~X -> -1 since ~X = -X-1 551124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (match(Op0, m_Not(m_Specific(Op1))) || 552124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands match(Op1, m_Not(m_Specific(Op0)))) 553fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getAllOnesValue(Op0->getType()); 55487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 55582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 add -> xor. 55675d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 55707f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 55807f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 55982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 560566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 561566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT, 562566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 563566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 564566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 5653421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Mul distributes over Add. Try some generic simplifications based on this. 5663421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, 5673421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 5683421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 5693421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 57087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Add over selects and phi nodes is pointless, so don't bother. 57187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A + select(cond, B, C)" means evaluating 57287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 57387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 57487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 57587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 57687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 57787689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 57887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 5798aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return 0; 5808aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner} 5818aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner 582ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 583ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 584ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 585ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 586ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 587fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// SimplifySubInst - Given operands for a Sub, see if we can 588fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// fold the result. If not, this returns null. 589ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 5903421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const TargetData *TD, const DominatorTree *DT, 591ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 592fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) 593fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 594fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Constant *Ops[] = { CLHS, CRHS }; 595fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 596fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Ops, 2, TD); 597fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands } 598fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 599fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - undef -> undef 600fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // undef - X -> undef 601f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op0, m_Undef()) || match(Op1, m_Undef())) 602fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return UndefValue::get(Op0->getType()); 603fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 604fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - 0 -> X 605fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 606fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 607fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 608fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - X -> 0 609124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (Op0 == Op1) 610fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getNullValue(Op0->getType()); 611fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 612fe02c69f84ad52d42be934e4fe702f03e4991a6aDuncan Sands // (X*2) - X -> X 613fe02c69f84ad52d42be934e4fe702f03e4991a6aDuncan Sands // (X<<1) - X -> X 614b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands Value *X = 0; 615fe02c69f84ad52d42be934e4fe702f03e4991a6aDuncan Sands if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())) || 616fe02c69f84ad52d42be934e4fe702f03e4991a6aDuncan Sands match(Op0, m_Shl(m_Specific(Op1), m_One()))) 617fe02c69f84ad52d42be934e4fe702f03e4991a6aDuncan Sands return Op1; 618fe02c69f84ad52d42be934e4fe702f03e4991a6aDuncan Sands 619b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. 620b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // For example, (X + Y) - Y -> X; (Y + X) - Y -> X 621b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands Value *Y = 0, *Z = Op1; 622b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z 623b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // See if "V === Y - Z" simplifies. 624b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, TD, DT, MaxRecurse-1)) 625b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does! Now see if "X + V" simplifies. 626b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *W = SimplifyBinOp(Instruction::Add, X, V, TD, DT, 627b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands MaxRecurse-1)) { 628b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does, we successfully reassociated! 629b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands ++NumReassoc; 630b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands return W; 631b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands } 632b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // See if "V === X - Z" simplifies. 633b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1)) 634b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does! Now see if "Y + V" simplifies. 635b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, TD, DT, 636b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands MaxRecurse-1)) { 637b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does, we successfully reassociated! 638b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands ++NumReassoc; 639b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands return W; 640b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands } 641b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands } 64282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 643b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. 644b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // For example, X - (X + 1) -> -1 645b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands X = Op0; 646b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) 647b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // See if "V === X - Y" simplifies. 648b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, TD, DT, MaxRecurse-1)) 649b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does! Now see if "V - Z" simplifies. 650b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, TD, DT, 651b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands MaxRecurse-1)) { 652b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does, we successfully reassociated! 653b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands ++NumReassoc; 654b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands return W; 655b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands } 656b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // See if "V === X - Z" simplifies. 657b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, TD, DT, MaxRecurse-1)) 658b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does! Now see if "V - Y" simplifies. 659b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, TD, DT, 660b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands MaxRecurse-1)) { 661b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does, we successfully reassociated! 662b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands ++NumReassoc; 663b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands return W; 664b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands } 665b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands } 666b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands 667b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // Z - (X - Y) -> (Z - X) + Y if everything simplifies. 668b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // For example, X - (X - Y) -> Y. 669b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands Z = Op0; 670c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) 671c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands // See if "V === Z - X" simplifies. 672c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, TD, DT, MaxRecurse-1)) 673b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // It does! Now see if "V + Y" simplifies. 674c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, TD, DT, 675c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands MaxRecurse-1)) { 676c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands // It does, we successfully reassociated! 677c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands ++NumReassoc; 678c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands return W; 679c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands } 680c087e20331c8a4c3b77d96a73588e80c06d89e3dDuncan Sands 6813421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Mul distributes over Sub. Try some generic simplifications based on this. 6823421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, 6833421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 6843421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 6853421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 686b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands // i1 sub -> xor. 687b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 688b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 689b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands return V; 690b2f3c383ec62b959ee27d0a5fb890894c4e49e86Duncan Sands 691fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading Sub over selects and phi nodes is pointless, so don't bother. 692fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading over the select in "A - select(cond, B, C)" means evaluating 693fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 694fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 695fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 696fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // have been simplified to the common value of B and C already. Analysing 697fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 698fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // for threading over phi nodes. 699fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 700fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return 0; 701fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands} 702fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 703ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 704ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 705ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 706ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 707ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 70882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands/// SimplifyMulInst - Given operands for a Mul, see if we can 70982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands/// fold the result. If not, this returns null. 71082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 71182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 71282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 71382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 71482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 71582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 71682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Ops, 2, TD); 71782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands } 71882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 71982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Canonicalize the constant to the RHS. 72082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands std::swap(Op0, Op1); 72182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands } 72282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 72382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * undef -> 0 724f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op1, m_Undef())) 72582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Constant::getNullValue(Op0->getType()); 72682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 72782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * 0 -> 0 72882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (match(Op1, m_Zero())) 72982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Op1; 73082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 73182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * 1 -> X 73282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (match(Op1, m_One())) 73382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Op0; 73482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 7351895e98ef38afbe011575cc25f4889d96e37421bDuncan Sands // (X / Y) * Y -> X if the division is exact. 7361895e98ef38afbe011575cc25f4889d96e37421bDuncan Sands Value *X = 0, *Y = 0; 737aeaf3d484b4d4c35e8794378c4b6cfbbde718dd1Chris Lattner if ((match(Op0, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op1) || // (X / Y) * Y 738aeaf3d484b4d4c35e8794378c4b6cfbbde718dd1Chris Lattner (match(Op1, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op0)) { // Y * (X / Y) 739c6ee9181a51fdfa3c07e1e53695681c55aa98ce4Chris Lattner BinaryOperator *Div = cast<BinaryOperator>(Y == Op1 ? Op0 : Op1); 740c6ee9181a51fdfa3c07e1e53695681c55aa98ce4Chris Lattner if (Div->isExact()) 7411895e98ef38afbe011575cc25f4889d96e37421bDuncan Sands return X; 7421895e98ef38afbe011575cc25f4889d96e37421bDuncan Sands } 7431895e98ef38afbe011575cc25f4889d96e37421bDuncan Sands 7445413880654585f01ea9880f24f07f27c8da56ba8Nick Lewycky // i1 mul -> and. 74575d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 74607f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1)) 74707f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 74882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 74982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Try some generic simplifications for associative operations. 75082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT, 75182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 75282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 75382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 75482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Mul distributes over Add. Try some generic simplifications based on this. 75582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 75682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands TD, DT, MaxRecurse)) 75782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 75882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 75982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // If the operation is with the result of a select instruction, check whether 76082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // operating on either branch of the select always yields the same value. 76182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 76282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT, 76382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 76482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 76582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 76682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // If the operation is with the result of a phi instruction, check whether 76782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // operating on all incoming values of the phi always yields the same value. 76882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 76982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT, 77082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 77182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 77282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 77382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return 0; 77482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands} 77582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 77682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan SandsValue *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 77782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *DT) { 77882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit); 77982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands} 78082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 781593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can 782593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands/// fold the result. If not, this returns null. 783479b4b9ef06dd84097202ffa6aea07913cdf651cAnders Carlssonstatic Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 784593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands const TargetData *TD, const DominatorTree *DT, 785593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands unsigned MaxRecurse) { 786593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Constant *C0 = dyn_cast<Constant>(Op0)) { 787593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Constant *C1 = dyn_cast<Constant>(Op1)) { 788593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands Constant *Ops[] = { C0, C1 }; 789593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD); 790593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands } 791593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands } 792593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 793a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands bool isSigned = Opcode == Instruction::SDiv; 794a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands 795593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // X / undef -> undef 796f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op1, m_Undef())) 797593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return Op1; 798593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 799593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // undef / X -> 0 800f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op0, m_Undef())) 801593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return Constant::getNullValue(Op0->getType()); 802593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 803593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // 0 / X -> 0, we don't need to preserve faults! 804593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (match(Op0, m_Zero())) 805593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return Op0; 806593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 807593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // X / 1 -> X 808593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (match(Op1, m_One())) 809593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return Op0; 810593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 811593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Op0->getType()->isIntegerTy(1)) 812593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // It can't be division by zero, hence it must be division by one. 813593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return Op0; 814593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 815593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // X / X -> 1 816593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Op0 == Op1) 817593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return ConstantInt::get(Op0->getType(), 1); 818593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 819593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // (X * Y) / Y -> X if the multiplication does not overflow. 820593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands Value *X = 0, *Y = 0; 821593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 822593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 8234b720718fbda1194f925e0a9d931bc220e8b0e3aDuncan Sands BinaryOperator *Mul = cast<BinaryOperator>(Op0); 8244b720718fbda1194f925e0a9d931bc220e8b0e3aDuncan Sands // If the Mul knows it does not overflow, then we are good to go. 8254b720718fbda1194f925e0a9d931bc220e8b0e3aDuncan Sands if ((isSigned && Mul->hasNoSignedWrap()) || 8264b720718fbda1194f925e0a9d931bc220e8b0e3aDuncan Sands (!isSigned && Mul->hasNoUnsignedWrap())) 8274b720718fbda1194f925e0a9d931bc220e8b0e3aDuncan Sands return X; 828593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands // If X has the form X = A / Y then X * Y cannot overflow. 829593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 830593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 831593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return X; 832593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands } 833593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 834a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands // (X rem Y) / Y -> 0 835a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 836a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 837a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands return Constant::getNullValue(Op0->getType()); 838a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands 839a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands // If the operation is with the result of a select instruction, check whether 840a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands // operating on either branch of the select always yields the same value. 841a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 842a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 843a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands return V; 844a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands 845a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands // If the operation is with the result of a phi instruction, check whether 846a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands // operating on all incoming values of the phi always yields the same value. 847a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 848a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 849a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands return V; 850a3e292c7e85efb33899f08238f57a85996a05a0bDuncan Sands 851593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return 0; 852593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands} 853593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 854593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands/// SimplifySDivInst - Given operands for an SDiv, see if we can 855593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands/// fold the result. If not, this returns null. 856593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sandsstatic Value *SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 857593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 858593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, TD, DT, MaxRecurse)) 859593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return V; 860593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 861593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return 0; 862593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands} 863593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 864593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan SandsValue *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, 8651fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel const DominatorTree *DT) { 866593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return ::SimplifySDivInst(Op0, Op1, TD, DT, RecursionLimit); 867593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands} 868593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 869593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands/// SimplifyUDivInst - Given operands for a UDiv, see if we can 870593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands/// fold the result. If not, this returns null. 871593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sandsstatic Value *SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 872593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 873593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, TD, DT, MaxRecurse)) 874593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return V; 875593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 876593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return 0; 877593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands} 878593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 879593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan SandsValue *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, 8801fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel const DominatorTree *DT) { 881593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands return ::SimplifyUDivInst(Op0, Op1, TD, DT, RecursionLimit); 882593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands} 883593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands 884f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sandsstatic Value *SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *, 885f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands const DominatorTree *, unsigned) { 8861fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel // undef / X -> undef (the undef could be a snan). 887f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op0, m_Undef())) 8881fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel return Op0; 8891fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel 8901fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel // X / undef -> undef 891f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op1, m_Undef())) 8921fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel return Op1; 8931fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel 8941fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel return 0; 8951fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel} 8961fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel 8971fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van BommelValue *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *TD, 8981fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel const DominatorTree *DT) { 8991fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel return ::SimplifyFDivInst(Op0, Op1, TD, DT, RecursionLimit); 9001fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel} 9011fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel 902cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can 903c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands/// fold the result. If not, this returns null. 904cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sandsstatic Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 905cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands const TargetData *TD, const DominatorTree *DT, 906cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands unsigned MaxRecurse) { 907c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands if (Constant *C0 = dyn_cast<Constant>(Op0)) { 908c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands if (Constant *C1 = dyn_cast<Constant>(Op1)) { 909c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands Constant *Ops[] = { C0, C1 }; 910cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, 2, TD); 911c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands } 912c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands } 913c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 914cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands // 0 shift by X -> 0 915c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands if (match(Op0, m_Zero())) 916c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return Op0; 917c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 918cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands // X shift by 0 -> X 919c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands if (match(Op1, m_Zero())) 920c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return Op0; 921c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 922cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands // X shift by undef -> undef because it may shift by the bitwidth. 923f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op1, m_Undef())) 924c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return Op1; 925c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 926c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands // Shifting by the bitwidth or more is undefined. 927c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) 928c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands if (CI->getValue().getLimitedValue() >= 929c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands Op0->getType()->getScalarSizeInBits()) 930c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return UndefValue::get(Op0->getType()); 931c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 932cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands // If the operation is with the result of a select instruction, check whether 933cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands // operating on either branch of the select always yields the same value. 934cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 935cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 936cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands return V; 937cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands 938cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands // If the operation is with the result of a phi instruction, check whether 939cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands // operating on all incoming values of the phi always yields the same value. 940cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 941cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, TD, DT, MaxRecurse)) 942cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands return V; 943cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands 944cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands return 0; 945cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands} 946cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands 947cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands/// SimplifyShlInst - Given operands for an Shl, see if we can 948cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands/// fold the result. If not, this returns null. 94981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattnerstatic Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 95081a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner const TargetData *TD, const DominatorTree *DT, 95181a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner unsigned MaxRecurse) { 952cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, TD, DT, MaxRecurse)) 953cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands return V; 954cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands 955cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands // undef << X -> 0 956f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op0, m_Undef())) 957cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands return Constant::getNullValue(Op0->getType()); 958cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands 95981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner // (X >> A) << A -> X 96081a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner Value *X; 96181a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1))) && 96281a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner cast<PossiblyExactOperator>(Op0)->isExact()) 96381a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return X; 964c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return 0; 965c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands} 966c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 96781a0dc911586c77421c2255aa417dc9b350b9e20Chris LattnerValue *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 96881a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner const TargetData *TD, const DominatorTree *DT) { 96981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 970c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands} 971c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 972c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands/// SimplifyLShrInst - Given operands for an LShr, see if we can 973c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands/// fold the result. If not, this returns null. 97481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattnerstatic Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 97581a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner const TargetData *TD, const DominatorTree *DT, 97681a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner unsigned MaxRecurse) { 977cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, TD, DT, MaxRecurse)) 978cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands return V; 979c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 980c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands // undef >>l X -> 0 981f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op0, m_Undef())) 982c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return Constant::getNullValue(Op0->getType()); 983c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 98481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner // (X << A) >> A -> X 98581a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner Value *X; 98681a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 98781a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap()) 98881a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return X; 98981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner 990c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return 0; 991c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands} 992c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 99381a0dc911586c77421c2255aa417dc9b350b9e20Chris LattnerValue *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 99481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner const TargetData *TD, const DominatorTree *DT) { 99581a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return ::SimplifyLShrInst(Op0, Op1, isExact, TD, DT, RecursionLimit); 996c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands} 997c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 998c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands/// SimplifyAShrInst - Given operands for an AShr, see if we can 999c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands/// fold the result. If not, this returns null. 100081a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattnerstatic Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 100181a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner const TargetData *TD, const DominatorTree *DT, 100281a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner unsigned MaxRecurse) { 1003cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, TD, DT, MaxRecurse)) 1004cf80bc1d4ac741620641c2bf48c25993bd478bd0Duncan Sands return V; 1005c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 1006c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands // all ones >>a X -> all ones 1007c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands if (match(Op0, m_AllOnes())) 1008c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return Op0; 1009c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 1010c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands // undef >>a X -> all ones 1011f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op0, m_Undef())) 1012c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return Constant::getAllOnesValue(Op0->getType()); 1013c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 101481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner // (X << A) >> A -> X 101581a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner Value *X; 101681a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 101781a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()) 101881a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return X; 101981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner 1020c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands return 0; 1021c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands} 1022c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 102381a0dc911586c77421c2255aa417dc9b350b9e20Chris LattnerValue *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 102481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner const TargetData *TD, const DominatorTree *DT) { 102581a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return ::SimplifyAShrInst(Op0, Op1, isExact, TD, DT, RecursionLimit); 1026c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands} 1027c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands 10288aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 10298aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// fold the result. If not, this returns null. 1030a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 10311845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 10328aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 10338aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 10348aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 1035d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 1036d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 1037d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 103812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1039d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 1040d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 1041d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 104212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1043d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & undef -> 0 1044f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op1, m_Undef())) 1045d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 104612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1047d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & X = X 1048124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (Op0 == Op1) 1049d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 105012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 10512b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & 0 = 0 10522b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 1053d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 105412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 10552b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & -1 = X 10562b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 10572b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 105812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1059d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & ~A = ~A & A = 0 106081a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner if (match(Op0, m_Not(m_Specific(Op1))) || 106181a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner match(Op1, m_Not(m_Specific(Op0)))) 1062d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 106312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1064d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A | ?) & A = A 106581a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner Value *A = 0, *B = 0; 1066d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1067124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands (A == Op1 || B == Op1)) 1068d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 106912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1070d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & (A | ?) = A 1071d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1072124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands (A == Op0 || B == Op0)) 1073d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 107412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1075566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 1076566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT, 1077566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 1078566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 10796844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 10803421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Or. Try some generic simplifications based on this. 10813421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 10823421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 10833421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 10843421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 10853421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Xor. Try some generic simplifications based on this. 10863421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 10873421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 10883421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 10893421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 10903421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Or distributes over And. Try some generic simplifications based on this. 10913421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, 10923421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 10933421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 10943421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1095b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 1096b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 10970312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 10981845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 10990312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 1100a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1101a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1102a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 1103a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 11040312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 11051845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 11060312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 1107b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 1108b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1109d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 1110d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 11119f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 11121845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 11131845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 11141845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 1115a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1116a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1117d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 11189f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner/// fold the result. If not, this returns null. 1119a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 11201845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 1121d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1122d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1123d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 1124d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1125d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 1126d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 112712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1128d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 1129d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 1130d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 113112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1132d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | undef -> -1 1133f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op1, m_Undef())) 1134d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 113512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1136d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | X = X 1137124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (Op0 == Op1) 1138d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 1139d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 11402b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | 0 = X 11412b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 1142d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 114312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 11442b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | -1 = -1 11452b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 11462b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op1; 114712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1148d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | ~A = ~A | A = -1 114981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner if (match(Op0, m_Not(m_Specific(Op1))) || 115081a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner match(Op1, m_Not(m_Specific(Op0)))) 1151d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 115212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1153d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A & ?) | A = A 115481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner Value *A = 0, *B = 0; 1155d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1156124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands (A == Op1 || B == Op1)) 1157d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 115812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1159d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | (A & ?) = A 1160d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1161124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands (A == Op0 || B == Op0)) 1162d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 116312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1164566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 1165566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT, 1166566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 1167566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 11686844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 11693421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Or distributes over And. Try some generic simplifications based on this. 11703421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, 11713421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 11723421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 11733421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 11743421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Or. Try some generic simplifications based on this. 11753421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, 11763421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 11773421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 11783421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1179b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 1180b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 11810312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 11821845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 11830312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 1184a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1185a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1186a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 1187a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 11880312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 11891845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 11900312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 1191b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 1192b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 11939f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 11949f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 11959f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 11961845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 11971845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 11981845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 1199a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1200d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 12012b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// SimplifyXorInst - Given operands for a Xor, see if we can 12022b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// fold the result. If not, this returns null. 12032b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sandsstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 12042b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 12052b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 12062b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 12072b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 12082b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 12092b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Ops, 2, TD); 12102b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 12112b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 12122b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // Canonicalize the constant to the RHS. 12132b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands std::swap(Op0, Op1); 12142b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 12152b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 12162b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ undef -> undef 1217f9e4a986c03fe3af7dbc9de0b0a9251280fbdf41Duncan Sands if (match(Op1, m_Undef())) 1218f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Op1; 12192b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 12202b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ 0 = A 12212b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 12222b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 12232b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 12242b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ A = 0 1225124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (Op0 == Op1) 12262b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getNullValue(Op0->getType()); 12272b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 12282b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ ~A = ~A ^ A = -1 122981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner if (match(Op0, m_Not(m_Specific(Op1))) || 123081a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner match(Op1, m_Not(m_Specific(Op0)))) 12312b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getAllOnesValue(Op0->getType()); 12322b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 1233566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 1234566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT, 1235566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 1236566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 12372b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 12383421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Xor. Try some generic simplifications based on this. 12393421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, 12403421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 12413421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 12423421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 124387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Xor over selects and phi nodes is pointless, so don't bother. 124487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A ^ select(cond, B, C)" means evaluating 124587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 124687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 124787689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 124887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 124987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 125087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 12512b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 12522b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return 0; 12532b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 12542b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 12552b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan SandsValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 12562b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT) { 12572b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 12582b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 12592b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 1260210c5d4880b525e064088b6fec713260128c16ebChris Lattnerstatic const Type *GetCompareTy(Value *Op) { 1261210c5d4880b525e064088b6fec713260128c16ebChris Lattner return CmpInst::makeCmpResultType(Op->getType()); 1262210c5d4880b525e064088b6fec713260128c16ebChris Lattner} 1263210c5d4880b525e064088b6fec713260128c16ebChris Lattner 12649dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 12659dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 1266a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 12671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 12681845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 12699f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 12709dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 127112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1272d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 12738f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 12748f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 1275d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 1276d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 1277d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 1278d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 1279d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 128012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 12816dc91253ab1872e118b08511a09d5c934988354eDuncan Sands const Type *ITy = GetCompareTy(LHS); // The return type. 12826dc91253ab1872e118b08511a09d5c934988354eDuncan Sands const Type *OpTy = LHS->getType(); // The operand type. 128312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1284210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp X, X -> true/false 1285c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 1286c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // because X could be 0. 1287124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (LHS == RHS || isa<UndefValue>(RHS)) 1288210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 128912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 12906dc91253ab1872e118b08511a09d5c934988354eDuncan Sands // Special case logic when the operands have i1 type. 12916dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (OpTy->isIntegerTy(1) || (OpTy->isVectorTy() && 12926dc91253ab1872e118b08511a09d5c934988354eDuncan Sands cast<VectorType>(OpTy)->getElementType()->isIntegerTy(1))) { 12936dc91253ab1872e118b08511a09d5c934988354eDuncan Sands switch (Pred) { 12946dc91253ab1872e118b08511a09d5c934988354eDuncan Sands default: break; 12956dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_EQ: 12966dc91253ab1872e118b08511a09d5c934988354eDuncan Sands // X == 1 -> X 12976dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (match(RHS, m_One())) 12986dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return LHS; 12996dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 13006dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_NE: 13016dc91253ab1872e118b08511a09d5c934988354eDuncan Sands // X != 0 -> X 13026dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (match(RHS, m_Zero())) 13036dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return LHS; 13046dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 13056dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_UGT: 13066dc91253ab1872e118b08511a09d5c934988354eDuncan Sands // X >u 0 -> X 13076dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (match(RHS, m_Zero())) 13086dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return LHS; 13096dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 13106dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_UGE: 13116dc91253ab1872e118b08511a09d5c934988354eDuncan Sands // X >=u 1 -> X 13126dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (match(RHS, m_One())) 13136dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return LHS; 13146dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 13156dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_SLT: 13166dc91253ab1872e118b08511a09d5c934988354eDuncan Sands // X <s 0 -> X 13176dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (match(RHS, m_Zero())) 13186dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return LHS; 13196dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 13206dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_SLE: 13216dc91253ab1872e118b08511a09d5c934988354eDuncan Sands // X <=s -1 -> X 13226dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (match(RHS, m_One())) 13236dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return LHS; 13246dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 13256dc91253ab1872e118b08511a09d5c934988354eDuncan Sands } 13266dc91253ab1872e118b08511a09d5c934988354eDuncan Sands } 132712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1328d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // icmp <alloca*>, <global/alloca*/null> - Different stack variables have 1329d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // different addresses, and what's more the address of a stack variable is 1330d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // never null or equal to the address of a global. Note that generalizing 1331d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // to the case where LHS is a global variable address or null is pointless, 1332d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // since if both LHS and RHS are constants then we already constant folded 1333d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // the compare, and if only one of them is then we moved it to RHS already. 1334d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isa<AllocaInst>(LHS) && (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 1335d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands isa<ConstantPointerNull>(RHS))) 1336d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // We already know that LHS != LHS. 1337d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 1338d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 1339d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // If we are comparing with zero then try hard since this is a common case. 1340d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (match(RHS, m_Zero())) { 1341d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands bool LHSKnownNonNegative, LHSKnownNegative; 1342d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands switch (Pred) { 1343d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands default: 1344d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands assert(false && "Unknown ICmp predicate!"); 1345d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_ULT: 1346d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getFalse(LHS->getContext()); 1347d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_UGE: 1348d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getTrue(LHS->getContext()); 1349d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_EQ: 1350d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_ULE: 1351d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isKnownNonZero(LHS, TD)) 1352d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getFalse(LHS->getContext()); 1353d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands break; 1354d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_NE: 1355d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_UGT: 1356d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (isKnownNonZero(LHS, TD)) 1357d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getTrue(LHS->getContext()); 1358d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands break; 1359d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_SLT: 1360d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1361d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (LHSKnownNegative) 1362d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getTrue(LHS->getContext()); 1363d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (LHSKnownNonNegative) 1364d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getFalse(LHS->getContext()); 1365d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands break; 1366d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_SLE: 1367d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1368d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (LHSKnownNegative) 1369d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getTrue(LHS->getContext()); 1370d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1371d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getFalse(LHS->getContext()); 1372d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands break; 1373d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_SGE: 1374d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1375d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (LHSKnownNegative) 1376d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getFalse(LHS->getContext()); 1377d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (LHSKnownNonNegative) 1378d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getTrue(LHS->getContext()); 1379d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands break; 1380d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands case ICmpInst::ICMP_SGT: 1381d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, TD); 1382d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (LHSKnownNegative) 1383d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getFalse(LHS->getContext()); 1384d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands if (LHSKnownNonNegative && isKnownNonZero(LHS, TD)) 1385d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands return ConstantInt::getTrue(LHS->getContext()); 1386d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands break; 1387d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 1388d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands } 1389d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands 1390d70d1a5c44609af091f6fc3e29193f9f4756a74fDuncan Sands // See if we are doing a comparison with a constant integer. 1391210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1392210c5d4880b525e064088b6fec713260128c16ebChris Lattner switch (Pred) { 1393210c5d4880b525e064088b6fec713260128c16ebChris Lattner default: break; 13946dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_UGT: 13956dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (CI->isMaxValue(false)) // A >u MAX -> FALSE 13966dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return ConstantInt::getFalse(CI->getContext()); 1397210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 1398210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_UGE: 1399210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(false)) // A >=u MIN -> TRUE 1400210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 1401210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 14026dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_ULT: 14036dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (CI->isMinValue(false)) // A <u MIN -> FALSE 14046dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return ConstantInt::getFalse(CI->getContext()); 14056dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 14066dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_ULE: 14076dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 14086dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return ConstantInt::getTrue(CI->getContext()); 14096dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 14106dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_SGT: 14116dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (CI->isMaxValue(true)) // A >s MAX -> FALSE 14126dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return ConstantInt::getFalse(CI->getContext()); 14136dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 1414210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SGE: 1415210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(true)) // A >=s MIN -> TRUE 1416210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 1417210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 14186dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_SLT: 14196dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (CI->isMinValue(true)) // A <s MIN -> FALSE 14206dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return ConstantInt::getFalse(CI->getContext()); 14216dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 14226dc91253ab1872e118b08511a09d5c934988354eDuncan Sands case ICmpInst::ICMP_SLE: 14236dc91253ab1872e118b08511a09d5c934988354eDuncan Sands if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 14246dc91253ab1872e118b08511a09d5c934988354eDuncan Sands return ConstantInt::getTrue(CI->getContext()); 14256dc91253ab1872e118b08511a09d5c934988354eDuncan Sands break; 1426210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 1427210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 14281ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 14299d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Compare of cast, for example (zext X) != 0 -> X != 0 14309d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 14319d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands Instruction *LI = cast<CastInst>(LHS); 14329d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands Value *SrcOp = LI->getOperand(0); 14339d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands const Type *SrcTy = SrcOp->getType(); 14349d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands const Type *DstTy = LI->getType(); 14359d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 14369d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 14379d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // if the integer type is the same size as the pointer type. 14389d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (MaxRecurse && TD && isa<PtrToIntInst>(LI) && 14399d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands TD->getPointerSizeInBits() == DstTy->getPrimitiveSizeInBits()) { 14409d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 14419d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Transfer the cast to the constant. 14429d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Value *V = SimplifyICmpInst(Pred, SrcOp, 14439d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantExpr::getIntToPtr(RHSC, SrcTy), 14449d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands TD, DT, MaxRecurse-1)) 14459d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return V; 14469d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 14479d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (RI->getOperand(0)->getType() == SrcTy) 14489d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Compare without the cast. 14499d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 14509d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands TD, DT, MaxRecurse-1)) 14519d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return V; 14529d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 14539d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 14549d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 14559d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (isa<ZExtInst>(LHS)) { 14569d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 14579d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // same type. 14589d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 14599d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 14609d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Compare X and Y. Note that signed predicates become unsigned. 14619d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 14629d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands SrcOp, RI->getOperand(0), TD, DT, 14639d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands MaxRecurse-1)) 14649d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return V; 14659d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 14669d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 14679d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // too. If not, then try to deduce the result of the comparison. 14689d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 14699d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Compute the constant that would happen if we truncated to SrcTy then 14709d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // reextended to DstTy. 14719d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 14729d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 14739d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 14749d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // If the re-extended constant didn't change then this is effectively 14759d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // also a case of comparing two zero-extended values. 14769d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (RExt == CI && MaxRecurse) 14779d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 14789d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands SrcOp, Trunc, TD, DT, MaxRecurse-1)) 14799d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return V; 14809d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 14819d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 14829d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // there. Use this to work out the result of the comparison. 14839d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (RExt != CI) { 14849d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands switch (Pred) { 14859d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands default: 14869d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands assert(false && "Unknown ICmp predicate!"); 14879d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // LHS <u RHS. 14889d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_EQ: 14899d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_UGT: 14909d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_UGE: 14919d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return ConstantInt::getFalse(CI->getContext()); 14929d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 14939d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_NE: 14949d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_ULT: 14959d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_ULE: 14969d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return ConstantInt::getTrue(CI->getContext()); 14979d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 14989d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 14999d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // is non-negative then LHS <s RHS. 15009d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_SGT: 15019d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_SGE: 15029d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return CI->getValue().isNegative() ? 15039d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantInt::getTrue(CI->getContext()) : 15049d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantInt::getFalse(CI->getContext()); 15059d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 15069d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_SLT: 15079d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_SLE: 15089d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return CI->getValue().isNegative() ? 15099d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantInt::getFalse(CI->getContext()) : 15109d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantInt::getTrue(CI->getContext()); 15119d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15129d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15139d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15149d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15159d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 15169d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (isa<SExtInst>(LHS)) { 15179d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 15189d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // same type. 15199d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 15209d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 15219d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Compare X and Y. Note that the predicate does not change. 15229d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 15239d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands TD, DT, MaxRecurse-1)) 15249d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return V; 15259d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15269d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 15279d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // too. If not, then try to deduce the result of the comparison. 15289d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 15299d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Compute the constant that would happen if we truncated to SrcTy then 15309d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // reextended to DstTy. 15319d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 15329d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 15339d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 15349d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // If the re-extended constant didn't change then this is effectively 15359d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // also a case of comparing two sign-extended values. 15369d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (RExt == CI && MaxRecurse) 15379d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, TD, DT, 15389d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands MaxRecurse-1)) 15399d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return V; 15409d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 15419d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Otherwise the upper bits of LHS are all equal, while RHS has varying 15429d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // bits there. Use this to work out the result of the comparison. 15439d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (RExt != CI) { 15449d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands switch (Pred) { 15459d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands default: 15469d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands assert(false && "Unknown ICmp predicate!"); 15479d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_EQ: 15489d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return ConstantInt::getFalse(CI->getContext()); 15499d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_NE: 15509d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return ConstantInt::getTrue(CI->getContext()); 15519d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 15529d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // If RHS is non-negative then LHS <s RHS. If RHS is negative then 15539d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // LHS >s RHS. 15549d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_SGT: 15559d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_SGE: 15569d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return CI->getValue().isNegative() ? 15579d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantInt::getTrue(CI->getContext()) : 15589d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantInt::getFalse(CI->getContext()); 15599d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_SLT: 15609d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_SLE: 15619d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return CI->getValue().isNegative() ? 15629d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantInt::getFalse(CI->getContext()) : 15639d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands ConstantInt::getTrue(CI->getContext()); 15649d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 15659d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // If LHS is non-negative then LHS <u RHS. If LHS is negative then 15669d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // LHS >u RHS. 15679d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_UGT: 15689d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_UGE: 15699d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Comparison is true iff the LHS <s 0. 15709d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (MaxRecurse) 15719d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 15729d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands Constant::getNullValue(SrcTy), 15739d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands TD, DT, MaxRecurse-1)) 15749d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return V; 15759d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands break; 15769d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_ULT: 15779d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands case ICmpInst::ICMP_ULE: 15789d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands // Comparison is true iff the LHS >=s 0. 15799d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (MaxRecurse) 15809d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 15819d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands Constant::getNullValue(SrcTy), 15829d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands TD, DT, MaxRecurse-1)) 15839d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands return V; 15849d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands break; 15859d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15869d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15879d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15889d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15899d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands } 15909d32f60a6f7dbd8e83187481cd2ae0a2f3e726ceDuncan Sands 15911ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // If the comparison is with the result of a select instruction, check whether 15921ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // comparing with either branch of the select always yields the same value. 15930312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 15940312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1595a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1596a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1597a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 1598a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 15990312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 16000312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 16013bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 16021ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 16039dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return 0; 16049dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 16059dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1606a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 16071845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 16081845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1609a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1610a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 16119dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 16129dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 1613a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 16141845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 16151845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 16169dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 16179dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 16189dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1619d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 16209dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 16219dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 162212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1623d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 1624d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 1625d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 1626d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 162712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1628210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Fold trivial predicates. 1629210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_FALSE) 1630210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 1631210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_TRUE) 1632210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 1633210c5d4880b525e064088b6fec713260128c16ebChris Lattner 1634210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 1635210c5d4880b525e064088b6fec713260128c16ebChris Lattner return UndefValue::get(GetCompareTy(LHS)); 1636210c5d4880b525e064088b6fec713260128c16ebChris Lattner 1637210c5d4880b525e064088b6fec713260128c16ebChris Lattner // fcmp x,x -> true/false. Not all compares are foldable. 1638124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (LHS == RHS) { 1639210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isTrueWhenEqual(Pred)) 1640210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 1641210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isFalseWhenEqual(Pred)) 1642210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 1643210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 164412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1645210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Handle fcmp with constant RHS 1646210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1647210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If the constant is a nan, see if we can fold the comparison based on it. 1648210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 1649210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CFP->getValueAPF().isNaN()) { 1650210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 1651210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getFalse(CFP->getContext()); 1652210c5d4880b525e064088b6fec713260128c16ebChris Lattner assert(FCmpInst::isUnordered(Pred) && 1653210c5d4880b525e064088b6fec713260128c16ebChris Lattner "Comparison must be either ordered or unordered!"); 1654210c5d4880b525e064088b6fec713260128c16ebChris Lattner // True if unordered. 1655210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CFP->getContext()); 1656210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 16576b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // Check whether the constant is an infinity. 16586b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isInfinity()) { 16596b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isNegative()) { 16606b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 16616b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OLT: 16626b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and less than negative infinity. 16636b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 16646b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_UGE: 16656b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with or at least negative infinity. 16666b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 16676b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 16686b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 16696b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 16706b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } else { 16716b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 16726b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OGT: 16736b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and greater than infinity. 16746b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 16756b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_ULE: 16766b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with and at most infinity. 16776b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 16786b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 16796b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 16806b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 16816b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 16826b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 1683210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 1684210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 168512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 168692826def593df7a422c7b07f09342febce81ddd3Duncan Sands // If the comparison is with the result of a select instruction, check whether 168792826def593df7a422c7b07f09342febce81ddd3Duncan Sands // comparing with either branch of the select always yields the same value. 16880312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 16890312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1690a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1691a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1692a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 1693a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 16940312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 16950312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 16963bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 169792826def593df7a422c7b07f09342febce81ddd3Duncan Sands 16989f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 16999f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 17009f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 1701a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 17021845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 17031845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1704a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1705a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1706047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 1707047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// the result. If not, this returns null. 1708124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan SandsValue *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 1709124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands const TargetData *TD, const DominatorTree *) { 1710047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select true, X, Y -> X 1711047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select false, X, Y -> Y 1712047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 1713047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return CB->getZExtValue() ? TrueVal : FalseVal; 171412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1715047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select C, X, X -> X 1716124708d9b47cc53cb11d8bfed75b241b6eec86d4Duncan Sands if (TrueVal == FalseVal) 1717047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 171812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1719047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 1720047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 1721047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 1722047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 1723047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 1724047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<Constant>(TrueVal)) 1725047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 1726047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 1727047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner } 172812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1729047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return 0; 1730047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner} 1731047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 1732c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 1733c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// fold the result. If not, this returns null. 1734c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris LattnerValue *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 17351845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 173685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // The type of the GEP pointer operand. 173785bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()); 173885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands 1739c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P -> P. 1740c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 1) 1741c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 1742c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 174385bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands if (isa<UndefValue>(Ops[0])) { 174485bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // Compute the (pointer) type returned by the GEP instruction. 174585bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1], 174685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands NumOps-1); 174785bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 174885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands return UndefValue::get(GEPTy); 174985bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands } 1750c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1751e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (NumOps == 2) { 1752e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, 0 -> P. 1753c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 1754c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (C->isZero()) 1755c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 1756e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, N -> P if P points to a type of zero size. 1757e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (TD) { 175885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *Ty = PtrTy->getElementType(); 1759a63395a30f9227bde826749d3480046301b47332Duncan Sands if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 1760e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands return Ops[0]; 1761e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 1762e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 176312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1764c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // Check to see if this is constant foldable. 1765c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner for (unsigned i = 0; i != NumOps; ++i) 1766c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (!isa<Constant>(Ops[i])) 1767c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return 0; 176812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1769c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 1770c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner (Constant *const*)Ops+1, NumOps-1); 1771c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner} 1772c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1773ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 1774ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sandsstatic Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 1775ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If all of the PHI's incoming values are the same then replace the PHI node 1776ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // with the common value. 1777ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *CommonValue = 0; 1778ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands bool HasUndefInput = false; 1779ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1780ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *Incoming = PN->getIncomingValue(i); 1781ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 1782ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (Incoming == PN) continue; 1783ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (isa<UndefValue>(Incoming)) { 1784ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // Remember that we saw an undef value, but otherwise ignore them. 1785ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands HasUndefInput = true; 1786ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands continue; 1787ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 1788ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (CommonValue && Incoming != CommonValue) 1789ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return 0; // Not the same, bail out. 1790ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands CommonValue = Incoming; 1791ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 1792ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1793ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If CommonValue is null then all of the incoming values were either undef or 1794ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // equal to the phi node itself. 1795ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (!CommonValue) 1796ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return UndefValue::get(PN->getType()); 1797ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1798ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If we have a PHI node like phi(X, undef, X), where X is defined by some 1799ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // instruction, we cannot return X as the result of the PHI node unless it 1800ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // dominates the PHI block. 1801ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (HasUndefInput) 1802ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 1803ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1804ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return CommonValue; 1805ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands} 1806ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1807c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1808d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner//=== Helper functions for higher up the class hierarchy. 18099dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1810d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 1811d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 1812a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 18131845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 18141845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 1815d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner switch (Opcode) { 181681a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner case Instruction::Add: 181781a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return SimplifyAddInst(LHS, RHS, /* isNSW */ false, /* isNUW */ false, 181881a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner TD, DT, MaxRecurse); 181981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner case Instruction::Sub: 182081a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return SimplifySubInst(LHS, RHS, /* isNSW */ false, /* isNUW */ false, 182181a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner TD, DT, MaxRecurse); 182281a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner case Instruction::Mul: return SimplifyMulInst (LHS, RHS, TD, DT, MaxRecurse); 1823593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, TD, DT, MaxRecurse); 1824593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, TD, DT, MaxRecurse); 18251fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, TD, DT, MaxRecurse); 182681a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner case Instruction::Shl: 182781a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return SimplifyShlInst(LHS, RHS, /*NSW*/false, /*NUW*/false, 182881a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner TD, DT, MaxRecurse); 182981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner case Instruction::LShr: 183081a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return SimplifyLShrInst(LHS, RHS, /*isexact*/ false, TD, DT, MaxRecurse); 183181a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner case Instruction::AShr: 183281a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner return SimplifyAShrInst(LHS, RHS, /*isexact*/false, TD, DT, MaxRecurse); 183382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 183481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner case Instruction::Or: return SimplifyOrInst (LHS, RHS, TD, DT, MaxRecurse); 183582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse); 1836d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner default: 1837d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1838d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 1839d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *COps[] = {CLHS, CRHS}; 1840d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 1841d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 1842b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1843566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If the operation is associative, try some generic simplifications. 1844566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Instruction::isAssociative(Opcode)) 1845566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT, 1846566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 1847566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 1848566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 1849b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 1850b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 18510312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 18521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 18530312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 1854a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1855a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1856a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 1857a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 18580312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 18590312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse)) 1860b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 1861b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1862d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 1863d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 1864d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 18659dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 186612a86f5b3199e72e6d967781acc76340f5920e46Duncan SandsValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 18671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 18681845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 1869a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1870a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 18719dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 18729dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. 1873a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 18741845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 18751845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 18769dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 18771845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 18781845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 18799dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 18809dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1881a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 18821845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 18831845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1884a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1885e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 1886e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// SimplifyInstruction - See if we can compute a simplified version of this 1887e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// instruction. If not, this returns null. 1888eff0581583ef10e2872e9baf537a04b67d992101Duncan SandsValue *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 1889eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 1890d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Value *Result; 1891d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1892e34537856a544c83513e390ac9552a8bc3823346Chris Lattner switch (I->getOpcode()) { 1893e34537856a544c83513e390ac9552a8bc3823346Chris Lattner default: 1894d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = ConstantFoldInstruction(I, TD); 1895d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 18968aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner case Instruction::Add: 1897d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 1898d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1899d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1900d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands TD, DT); 1901d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1902fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands case Instruction::Sub: 1903fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 1904fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1905fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1906fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands TD, DT); 1907fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands break; 190882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Mul: 190982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT); 191082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands break; 1911593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands case Instruction::SDiv: 1912593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 1913593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands break; 1914593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands case Instruction::UDiv: 1915593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 1916593faa53fa6d89841e601cc4571d143a6a05f0b4Duncan Sands break; 19171fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel case Instruction::FDiv: 19181fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), TD, DT); 19191fca2c32cc99197215d3fd32a4ad05214c74edd1Frits van Bommel break; 1920c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands case Instruction::Shl: 192181a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), 192281a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner cast<BinaryOperator>(I)->hasNoSignedWrap(), 192381a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 192481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner TD, DT); 1925c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands break; 1926c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands case Instruction::LShr: 192781a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), 192881a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner cast<BinaryOperator>(I)->isExact(), 192981a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner TD, DT); 1930c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands break; 1931c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands case Instruction::AShr: 193281a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), 193381a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner cast<BinaryOperator>(I)->isExact(), 193481a0dc911586c77421c2255aa417dc9b350b9e20Chris Lattner TD, DT); 1935c43cee3fbb3098f0647e50dd2c13bc55b027a228Duncan Sands break; 1936e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::And: 1937d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 1938d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1939e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::Or: 1940d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1941d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 19422b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands case Instruction::Xor: 19432b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 19442b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands break; 1945e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::ICmp: 1946d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 1947d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1948d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1949e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::FCmp: 1950d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 1951d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1952d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1953047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner case Instruction::Select: 1954d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 1955d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(2), TD, DT); 1956d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1957c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner case Instruction::GetElementPtr: { 1958c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 1959d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 1960d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1961c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner } 1962cd6636c737a82949ad13db2d0d918af6424fb78bDuncan Sands case Instruction::PHI: 1963d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyPHINode(cast<PHINode>(I), DT); 1964d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1965e34537856a544c83513e390ac9552a8bc3823346Chris Lattner } 1966d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1967d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// If called on unreachable code, the above logic may report that the 1968d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// instruction simplified to itself. Make life easier for users by 1969f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands /// detecting that case here, returning a safe value instead. 1970f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Result == I ? UndefValue::get(I->getType()) : Result; 1971e34537856a544c83513e390ac9552a8bc3823346Chris Lattner} 1972e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 197340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 197440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// delete the From instruction. In addition to a basic RAUW, this does a 197540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursive simplification of the newly formed instructions. This catches 197640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// things where one simplification exposes other opportunities. This only 197740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// simplifies and deletes scalar operations, it does not change the CFG. 197840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 197940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 1980eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const TargetData *TD, 1981eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 198240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 198312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1984d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 1985d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // we can know if it gets deleted out from under us or replaced in a 1986d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // recursive simplification. 198740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH FromHandle(From); 1988d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner WeakVH ToHandle(To); 198912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 199040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (!From->use_empty()) { 199140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Update the instruction to use the new value. 1992d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Use &TheUse = From->use_begin().getUse(); 1993d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Instruction *User = cast<Instruction>(TheUse.getUser()); 1994d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner TheUse = To; 1995d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner 1996d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Check to see if the instruction can be folded due to the operand 1997d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // replacement. For example changing (or X, Y) into (or X, -1) can replace 1998d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // the 'or' with -1. 1999d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Value *SimplifiedVal; 2000d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner { 2001d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Sanity check to make sure 'User' doesn't dangle across 2002d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // SimplifyInstruction. 2003d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner AssertingVH<> UserHandle(User); 200412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2005eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands SimplifiedVal = SimplifyInstruction(User, TD, DT); 2006d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (SimplifiedVal == 0) continue; 200740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 200812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2009d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Recursively simplify this user to the new value. 2010eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 2011d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 2012d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner To = ToHandle; 201312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2014d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner assert(ToHandle && "To value deleted by recursive simplification?"); 201512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2016d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If the recursive simplification ended up revisiting and deleting 2017d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // 'From' then we're done. 2018d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (From == 0) 2019d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner return; 202040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 202112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 2022d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If 'From' has value handles referring to it, do a real RAUW to update them. 2023d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From->replaceAllUsesWith(To); 202412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 202540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner From->eraseFromParent(); 202640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 2027