InstructionSimplify.cpp revision 7cf85e74e3885005ca8e5fdb155fa5351e255b85
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" 25d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner#include "llvm/Support/PatternMatch.h" 261845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Support/ValueHandle.h" 27e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands#include "llvm/Target/TargetData.h" 289f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattnerusing namespace llvm; 29d06094f0682f2ede03caff4892b1a57469896d48Chris Lattnerusing namespace llvm::PatternMatch; 309f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 317cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands#define RecursionLimit 4 32a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 33a3c44a5280042dbc0cde995675c225ede4528c6eDuncan SandsSTATISTIC(NumExpand, "Number of expansions"); 34a3c44a5280042dbc0cde995675c225ede4528c6eDuncan SandsSTATISTIC(NumFactor , "Number of factorizations"); 35a3c44a5280042dbc0cde995675c225ede4528c6eDuncan SandsSTATISTIC(NumReassoc, "Number of reassociations"); 36a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands 3782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyAndInst(Value *, Value *, const TargetData *, 3882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 39a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 401845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 41a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 421845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 4382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyOrInst(Value *, Value *, const TargetData *, 4482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 4582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyXorInst(Value *, Value *, const TargetData *, 4682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 471845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 487cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands/// equal - Return true if the given values are known to be equal, false if they 497cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands/// are not equal or it is not clear whether they are equal or not. 507cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sandsstatic bool equal(Value *A, Value *B, unsigned MaxRecurse) { 517cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // If the pointers are equal then the values are! 527cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (A == B) 537cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return true; 547cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // From this point on either recursion is used or the result is false, so bail 557cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // out at once if we already hit the recursion limit. 567cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (!MaxRecurse--) 577cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return false; 587cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // If these are instructions, see if they compute the same value. 597cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands Instruction *AI = dyn_cast<Instruction>(A), *BI = dyn_cast<Instruction>(B); 607cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (!AI || !BI) 617cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return false; 627cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // If one of the instructions has extra flags attached then be conservative 637cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // and say that the instructions differ. 647cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (!AI->hasSameSubclassOptionalData(BI)) 657cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return false; 667cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // For some reason alloca's are not considered to read or write memory, yet 677cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // each one nonetheless manages to return a different value... 687cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (isa<AllocaInst>(AI)) 697cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return false; 707cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // Do not consider instructions to be equal if they may access memory. 717cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (AI->mayReadFromMemory() || AI->mayWriteToMemory()) 727cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return false; 737cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // If the instructions do not perform the same computation then bail out. 747cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (!BI->isSameOperationAs(AI)) 757cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return false; 767cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands 777cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // Check whether all operands are equal. If they are then the instructions 787cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // have the same value. 797cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands bool AllOperandsEqual = true; 807cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands for (unsigned i = 0, e = AI->getNumOperands(); i != e; ++i) 817cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (!equal(AI->getOperand(i), BI->getOperand(i), MaxRecurse)) { 827cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands AllOperandsEqual = false; 837cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands break; 847cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands } 857cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (AllOperandsEqual) 867cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return true; 877cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands 887cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // If the instructions are commutative and their operands are equal when 897cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // swapped then the instructions have the same value. 907cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return AI->isCommutative() && 917cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(AI->getOperand(0), BI->getOperand(1), MaxRecurse) && 927cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(AI->getOperand(1), BI->getOperand(0), MaxRecurse); 937cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands} 947cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands 951845009290e4d804ad377927bd8a08cca3036adcDuncan Sands/// ValueDominatesPHI - Does the given value dominate the specified phi node? 961845009290e4d804ad377927bd8a08cca3036adcDuncan Sandsstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 971845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Instruction *I = dyn_cast<Instruction>(V); 981845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!I) 991845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Arguments and constants dominate all instructions. 1001845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 1011845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 1021845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // If we have a DominatorTree then do a precise test. 1031845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (DT) 1041845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return DT->dominates(I, P); 1051845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 1061845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Otherwise, if the instruction is in the entry block, and is not an invoke, 1071845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // then it obviously dominates all phi nodes. 1081845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 1091845009290e4d804ad377927bd8a08cca3036adcDuncan Sands !isa<InvokeInst>(I)) 1101845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 1111845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 1121845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return false; 1131845009290e4d804ad377927bd8a08cca3036adcDuncan Sands} 114a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1153421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 1163421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 1173421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 1183421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 1193421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Returns the simplified value, or null if no simplification was performed. 1203421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sandsstatic Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 121e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer unsigned OpcToExpand, const TargetData *TD, 1223421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 123e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand; 1243421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 1253421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!MaxRecurse--) 1263421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1273421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1283421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Check whether the expression has the form "(A op' B) op C". 1293421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 1303421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Op0->getOpcode() == OpcodeToExpand) { 1313421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Try turning it into "(A op C) op' (B op C)". 1323421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 1333421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Do "A op C" and "B op C" both simplify? 1343421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *L = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) 1353421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *R = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 1363421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // They do! Return "L op' R" if it simplifies or is already available. 1373421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 1387cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if ((equal(L, A, MaxRecurse) && equal(R, B, MaxRecurse)) || 1397cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (Instruction::isCommutative(OpcodeToExpand) && 1407cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(L, B, MaxRecurse) && equal(R, A, MaxRecurse))) { 141a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1423421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return LHS; 143a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1443421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "L op' R" if it simplifies. 145a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT, 146a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands MaxRecurse)) { 147a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1483421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 149a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1503421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1513421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1523421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1533421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Check whether the expression has the form "A op (B op' C)". 1543421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 1553421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Op1->getOpcode() == OpcodeToExpand) { 1563421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Try turning it into "(A op B) op' (A op C)". 1573421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 1583421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Do "A op B" and "A op C" both simplify? 1593421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *L = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) 1603421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *R = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) { 1613421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // They do! Return "L op' R" if it simplifies or is already available. 1623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 1637cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if ((equal(L, B, MaxRecurse) && equal(R, C, MaxRecurse)) || 1647cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (Instruction::isCommutative(OpcodeToExpand) && 1657cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(L, C, MaxRecurse) && equal(R, B, MaxRecurse))) { 166a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1673421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return RHS; 168a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1693421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "L op' R" if it simplifies. 170a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT, 171a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands MaxRecurse)) { 172a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1733421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 174a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1753421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1763421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1773421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1783421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1793421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands} 1803421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1813421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term 1823421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// using the operation OpCodeToExtract. For example, when Opcode is Add and 1833421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)". 1843421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Returns the simplified value, or null if no simplification was performed. 1853421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sandsstatic Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 186e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer unsigned OpcToExtract, const TargetData *TD, 1873421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 188e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer Instruction::BinaryOps OpcodeToExtract = (Instruction::BinaryOps)OpcToExtract; 1893421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 1903421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!MaxRecurse--) 1913421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1923421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1933421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 1943421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 1953421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1963421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!Op0 || Op0->getOpcode() != OpcodeToExtract || 1973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands !Op1 || Op1->getOpcode() != OpcodeToExtract) 1983421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1993421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 2003421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // The expression has the form "(A op' B) op (C op' D)". 20182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); 20282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); 2033421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 2043421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)". 2053421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does the instruction have the form "(A op' B) op (A op' D)" or, in the 2063421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // commutative case, "(A op' B) op (C op' A)"? 2077cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands bool AEqualsC = equal(A, C, MaxRecurse); 2087cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (AEqualsC || (Instruction::isCommutative(OpcodeToExtract) && 2097cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(A, D, MaxRecurse))) { 2107cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands Value *DD = AEqualsC ? D : C; 2113421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Form "A op' (B op DD)" if it simplifies completely. 2123421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does "B op DD" simplify? 2133421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, DT, MaxRecurse)) { 2143421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Return "A op' V" if it simplifies or is already available. 2151cd05bb605e3c3eee9197d3f10b628c60d0cc07aDuncan Sands // If V equals B then "A op' V" is just the LHS. If V equals DD then 2161cd05bb605e3c3eee9197d3f10b628c60d0cc07aDuncan Sands // "A op' V" is just the RHS. 2177cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(V, B, MaxRecurse)) { 218a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 2197cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return LHS; 2207cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands } 2217cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(V, DD, MaxRecurse)) { 2227cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands ++NumFactor; 2237cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return RHS; 224a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 2253421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "A op' V" if it simplifies. 226a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, DT, MaxRecurse)) { 227a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 2283421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return W; 229a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 2303421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 2313421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 2323421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 2333421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)". 2343421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does the instruction have the form "(A op' B) op (C op' B)" or, in the 2353421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // commutative case, "(A op' B) op (B op' D)"? 2367cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands bool BEqualsD = equal(B, D, MaxRecurse); 2377cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (BEqualsD || (Instruction::isCommutative(OpcodeToExtract) && 2387cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(B, C, MaxRecurse))) { 2397cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands Value *CC = BEqualsD ? C : D; 2403421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Form "(A op CC) op' B" if it simplifies completely.. 2413421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does "A op CC" simplify? 2423421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, DT, MaxRecurse)) { 2433421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Return "V op' B" if it simplifies or is already available. 2441cd05bb605e3c3eee9197d3f10b628c60d0cc07aDuncan Sands // If V equals A then "V op' B" is just the LHS. If V equals CC then 2451cd05bb605e3c3eee9197d3f10b628c60d0cc07aDuncan Sands // "V op' B" is just the RHS. 2467cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(V, A, MaxRecurse)) { 247a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 2487cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return LHS; 2497cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands } 2507cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(V, CC, MaxRecurse)) { 2517cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands ++NumFactor; 2527cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return RHS; 253a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 2543421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "V op' B" if it simplifies. 255a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, DT, MaxRecurse)) { 256a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 2573421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return W; 258a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 2593421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 2603421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 2613421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 2623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 2633421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands} 2643421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 2653421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// SimplifyAssociativeBinOp - Generic simplifications for associative binary 2663421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// operations. Returns the simpler value, or null if none was found. 267e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramerstatic Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, 268566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const TargetData *TD, 269566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const DominatorTree *DT, 270566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands unsigned MaxRecurse) { 271e21083aa3a79506f896d95d7147c3c4627a77ef0Benjamin Kramer Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; 272566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 273566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 274566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 275566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!MaxRecurse--) 276566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 277566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 278566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 279566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 280566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 281566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 282566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 283566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 284566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 285566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 286566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 287566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "B op C" simplify? 288566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 289566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "A op V" if it simplifies or is already available. 290566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "A op V" is just the LHS. 2917cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(V, B, MaxRecurse)) return LHS; 292566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "A op V" if it simplifies. 293a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) { 294a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 295566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 296a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 297566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 298566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 299566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 300566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 301566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 302566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 303566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 304566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 305566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 306566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "A op B" simplify? 307566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) { 308566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op C" if it simplifies or is already available. 309566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "V op C" is just the RHS. 3107cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(V, B, MaxRecurse)) return RHS; 311566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op C" if it simplifies. 312a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) { 313a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 314566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 315a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 316566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 317566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 318566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 319566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // The remaining transforms require commutativity as well as associativity. 320566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!Instruction::isCommutative(Opcode)) 321566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 322566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 323566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 324566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 325566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 326566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 327566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 328566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 329566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 330566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 331566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op B" if it simplifies or is already available. 332566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals A then "V op B" is just the LHS. 3337cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(V, A, MaxRecurse)) return LHS; 334566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op B" if it simplifies. 335a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) { 336a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 337566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 338a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 339566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 340566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 341566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 342566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 343566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 344566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 345566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 346566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 347566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 348566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 349566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 350566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "B op V" if it simplifies or is already available. 351566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals C then "B op V" is just the RHS. 3527cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(V, C, MaxRecurse)) return RHS; 353566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "B op V" if it simplifies. 354a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) { 355a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 356566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 357a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 358566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 359566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 360566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 361566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 362566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands} 363566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 364b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadBinOpOverSelect - In the case of a binary operation with a select 365b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// instruction as an operand, try to simplify the binop by seeing whether 366b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// evaluating it on both branches of the select results in the same value. 367b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// Returns the common value if so, otherwise returns null. 368b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 3691845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, 3701845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 3711845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 3720312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 3730312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 3740312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 3750312a93693abc2eb682b2b101c889959888fd883Duncan Sands 376b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI; 377b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (isa<SelectInst>(LHS)) { 378b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(LHS); 379b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 380b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 381b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(RHS); 382b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 383b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 384b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Evaluate the BinOp on the true and false branches of the select. 385b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *TV; 386b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *FV; 387b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (SI == LHS) { 3881845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse); 3891845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse); 390b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 3911845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse); 3921845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse); 393b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 394b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 395b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they both failed to simplify then return null. 3967cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (!TV && !FV) 3977cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return 0; 3987cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands 3997cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands // If they simplified to the same value, then return the common value. 4007cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (TV && FV && equal(TV, FV, MaxRecurse)) 401b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 402b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 403b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified to undef, return the other one. 404b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV && isa<UndefValue>(TV)) 405b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return FV; 406b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (FV && isa<UndefValue>(FV)) 407b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 408b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 409b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If applying the operation did not change the true and false select values, 410b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // then the result of the binop is the select itself. 4117cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (TV && equal(TV, SI->getTrueValue(), MaxRecurse) && 4127cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands FV && equal(FV, SI->getFalseValue(), MaxRecurse)) 413b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return SI; 414b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 415b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified and the other did not, and the simplified 416b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // value is equal to the unsimplified one, return the simplified value. 417b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // For example, select (cond, X, X & Z) & Z -> X & Z. 418b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if ((FV && !TV) || (TV && !FV)) { 419b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Check that the simplified value has the form "X op Y" where "op" is the 420b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // same as the original operation. 421b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 422b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified && Simplified->getOpcode() == Opcode) { 423b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 424b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // We already know that "op" is the same as for the simplified value. See 425b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // if the operands match too. If so, return the simplified value. 426b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 427b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 428b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 4297cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(Simplified->getOperand(0), UnsimplifiedLHS, MaxRecurse) && 4307cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(Simplified->getOperand(1), UnsimplifiedRHS, MaxRecurse)) 431b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 432b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->isCommutative() && 4337cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(Simplified->getOperand(1), UnsimplifiedLHS, MaxRecurse) && 4347cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands equal(Simplified->getOperand(0), UnsimplifiedRHS, MaxRecurse)) 435b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 436b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 437b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 438b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 439b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 440b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 441b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 442b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 443b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// try to simplify the comparison by seeing whether both branches of the select 444b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// result in the same value. Returns the common value if so, otherwise returns 445b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// null. 446b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 447a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *RHS, const TargetData *TD, 4481845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 449a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 4500312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 4510312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 4520312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 4530312a93693abc2eb682b2b101c889959888fd883Duncan Sands 454b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Make sure the select is on the LHS. 455b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (!isa<SelectInst>(LHS)) { 456b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands std::swap(LHS, RHS); 457b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 458b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 459b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 460b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI = cast<SelectInst>(LHS); 461b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 462b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Now that we have "cmp select(cond, TV, FV), RHS", analyse it. 463b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Does "cmp TV, RHS" simplify? 4641845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT, 465a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 466b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! Does "cmp FV, RHS" simplify? 4671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT, 468a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 469b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! If they simplified to the same value, then use it as the 470b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // result of the original comparison. 4717cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(TCmp, FCmp, MaxRecurse)) 472b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TCmp; 473b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 474b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 475b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 476a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 477a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 478a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// it on the incoming phi values yields the same result for every value. If so 479a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// returns the common value, otherwise returns null. 480a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 4811845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 4821845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 4830312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 4840312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 4850312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 4860312a93693abc2eb682b2b101c889959888fd883Duncan Sands 487a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI; 488a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (isa<PHINode>(LHS)) { 489a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(LHS); 4901845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 4911845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 4921845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 493a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } else { 494a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 495a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(RHS); 4961845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if LHS and the phi may be mutually interdependent due to a loop. 4971845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(LHS, PI, DT)) 4981845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 499a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 500a74a58c83be492b7d5b7383656f049909394cff4Duncan 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; 507a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *V = PI == LHS ? 5081845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 5091845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 510a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 511a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 512a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 513a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 514a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 515a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 516a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 517a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 518a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 519a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 520a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 521a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// try to simplify the comparison by seeing whether comparing with all of the 522a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// incoming phi values yields the same result every time. If so returns the 523a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// common result, otherwise returns null. 524a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 5251845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 5261845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 5270312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 5280312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 5290312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 5300312a93693abc2eb682b2b101c889959888fd883Duncan Sands 531a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Make sure the phi is on the LHS. 532a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!isa<PHINode>(LHS)) { 533a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands std::swap(LHS, RHS); 534a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 535a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 536a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 537a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI = cast<PHINode>(LHS); 538a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 5391845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 5401845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 5411845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 5421845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 543a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 544a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 545a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 546552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 547ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 548552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 5491845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 550a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 551a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 552a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 553a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 554a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 555a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 556a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 557a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 558a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 559a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 5608aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 561d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 562ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 563ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT, 564ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 565d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 566d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 567d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 5688aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 5698aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Ops, 2, TD); 5708aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 57112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 5728aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // Canonicalize the constant to the RHS. 5738aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner std::swap(Op0, Op1); 5748aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 57512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 576fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + undef -> undef 577fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (isa<UndefValue>(Op1)) 578fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op1; 57912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 580fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + 0 -> X 581fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 582fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 583fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 584fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + (Y - X) -> Y 585fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y - X) + X -> Y 586ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands // Eg: X + -X -> 0 5877cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands Value *X = 0, *Y = 0; 5887cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if ((match(Op1, m_Sub(m_Value(Y), m_Value(X))) && equal(X, Op0, MaxRecurse))|| 5897cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (match(Op0, m_Sub(m_Value(Y), m_Value(X))) && equal(X, Op1, MaxRecurse))) 590fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Y; 591fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 592fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + ~X -> -1 since ~X = -X-1 5937cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if ((match(Op0, m_Not(m_Value(X))) && equal(X, Op1, MaxRecurse)) || 5947cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (match(Op1, m_Not(m_Value(X))) && equal(X, Op0, MaxRecurse))) 595fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getAllOnesValue(Op0->getType()); 59687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 59782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 add -> xor. 59875d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 59907f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 60007f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 60182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 602566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 603566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT, 604566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 605566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 606566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 6073421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Mul distributes over Add. Try some generic simplifications based on this. 6083421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, 6093421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 6103421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 6113421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 61287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Add over selects and phi nodes is pointless, so don't bother. 61387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A + select(cond, B, C)" means evaluating 61487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 61587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 61687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 61787689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 61887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 61987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 62087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 6218aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return 0; 6228aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner} 6238aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner 624ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 625ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 626ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 627ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 628ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 629fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// SimplifySubInst - Given operands for a Sub, see if we can 630fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// fold the result. If not, this returns null. 631ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 6323421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const TargetData *TD, const DominatorTree *DT, 633ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 634fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) 635fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 636fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Constant *Ops[] = { CLHS, CRHS }; 637fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 638fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Ops, 2, TD); 639fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands } 640fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 641fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - undef -> undef 642fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // undef - X -> undef 643fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1)) 644fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return UndefValue::get(Op0->getType()); 645fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 646fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - 0 -> X 647fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 648fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 649fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 650fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - X -> 0 6517cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(Op0, Op1, MaxRecurse)) 652fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getNullValue(Op0->getType()); 653fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 654fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (X + Y) - Y -> X 655fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y + X) - Y -> X 6567cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands Value *X = 0, *Y = 0; 6577cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if ((match(Op0, m_Add(m_Value(X), m_Value(Y))) && equal(Y, Op1, MaxRecurse))|| 6587cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (match(Op0, m_Add(m_Value(Y), m_Value(X))) && equal(Y, Op1, MaxRecurse))) 659fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return X; 660fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 66182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 sub -> xor. 66275d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 66307f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 66407f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 66582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 6663421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Mul distributes over Sub. Try some generic simplifications based on this. 6673421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, 6683421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 6693421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 6703421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 671fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading Sub over selects and phi nodes is pointless, so don't bother. 672fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading over the select in "A - select(cond, B, C)" means evaluating 673fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 674fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 675fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 676fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // have been simplified to the common value of B and C already. Analysing 677fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 678fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // for threading over phi nodes. 679fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 680fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return 0; 681fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands} 682fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 683ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 684ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 685ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 686ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 687ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 68882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands/// SimplifyMulInst - Given operands for a Mul, see if we can 68982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands/// fold the result. If not, this returns null. 69082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 69182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 69282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 69382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 69482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 69582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 69682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Ops, 2, TD); 69782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands } 69882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 69982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Canonicalize the constant to the RHS. 70082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands std::swap(Op0, Op1); 70182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands } 70282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 70382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * undef -> 0 70482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<UndefValue>(Op1)) 70582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Constant::getNullValue(Op0->getType()); 70682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 70782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * 0 -> 0 70882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (match(Op1, m_Zero())) 70982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Op1; 71082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 71182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * 1 -> X 71282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (match(Op1, m_One())) 71382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Op0; 71482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 71582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 mul -> and. 71675d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 71707f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1)) 71807f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 71982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 72082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Try some generic simplifications for associative operations. 72182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT, 72282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 72382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 72482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 72582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Mul distributes over Add. Try some generic simplifications based on this. 72682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 72782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands TD, DT, MaxRecurse)) 72882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 72982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 73082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // If the operation is with the result of a select instruction, check whether 73182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // operating on either branch of the select always yields the same value. 73282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 73382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT, 73482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 73582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 73682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 73782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // If the operation is with the result of a phi instruction, check whether 73882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // operating on all incoming values of the phi always yields the same value. 73982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 74082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT, 74182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 74282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 74382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 74482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return 0; 74582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands} 74682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 74782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan SandsValue *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 74882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *DT) { 74982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit); 75082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands} 75182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 7528aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 7538aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// fold the result. If not, this returns null. 754a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 7551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 7568aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 7578aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 7588aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 759d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 760d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 761d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 76212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 763d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 764d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 765d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 76612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 767d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & undef -> 0 768d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 769d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 77012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 771d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & X = X 7727cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(Op0, Op1, MaxRecurse)) 773d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 77412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 7752b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & 0 = 0 7762b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 777d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 77812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 7792b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & -1 = X 7802b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 7812b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 78212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 783d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & ~A = ~A & A = 0 784e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 7857cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if ((match(Op0, m_Not(m_Value(A))) && equal(A, Op1, MaxRecurse)) || 7867cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (match(Op1, m_Not(m_Value(A))) && equal(A, Op0, MaxRecurse))) 787d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 78812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 789d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A | ?) & A = A 790d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 7917cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (equal(A, Op1, MaxRecurse) || equal(B, Op1, MaxRecurse))) 792d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 79312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 794d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & (A | ?) = A 795d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 7967cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (equal(A, Op0, MaxRecurse) || equal(B, Op0, MaxRecurse))) 797d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 79812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 799566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 800566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT, 801566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 802566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 8036844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 8043421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Or. Try some generic simplifications based on this. 8053421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 8063421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 8073421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 8083421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 8093421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Xor. Try some generic simplifications based on this. 8103421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 8113421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 8123421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 8133421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 8143421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Or distributes over And. Try some generic simplifications based on this. 8153421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, 8163421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 8173421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 8183421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 819b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 820b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 8210312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 8221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 8230312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 824a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 825a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 826a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 827a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 8280312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 8291845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 8300312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 831b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 832b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 833d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 834d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 8359f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 8361845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 8371845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 8381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 839a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 840a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 841d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 8429f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner/// fold the result. If not, this returns null. 843a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 8441845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 845d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 846d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 847d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 848d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 849d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 850d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 85112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 852d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 853d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 854d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 85512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 856d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | undef -> -1 857d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 858d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 85912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 860d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | X = X 8617cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(Op0, Op1, MaxRecurse)) 862d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 863d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 8642b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | 0 = X 8652b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 866d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 86712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 8682b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | -1 = -1 8692b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 8702b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op1; 87112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 872d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | ~A = ~A | A = -1 873e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 8747cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if ((match(Op0, m_Not(m_Value(A))) && equal(A, Op1, MaxRecurse)) || 8757cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (match(Op1, m_Not(m_Value(A))) && equal(A, Op0, MaxRecurse))) 876d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 87712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 878d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A & ?) | A = A 879d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(B))) && 8807cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (equal(A, Op1, MaxRecurse) || equal(B, Op1, MaxRecurse))) 881d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 88212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 883d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | (A & ?) = A 884d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_And(m_Value(A), m_Value(B))) && 8857cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (equal(A, Op0, MaxRecurse) || equal(B, Op0, MaxRecurse))) 886d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 88712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 888566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 889566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT, 890566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 891566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 8926844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 8933421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Or distributes over And. Try some generic simplifications based on this. 8943421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, 8953421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 8963421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 8973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 8983421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Or. Try some generic simplifications based on this. 8993421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, 9003421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 9013421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 9023421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 903b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 904b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 9050312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 9061845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 9070312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 908a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 909a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 910a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 911a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 9120312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 9131845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 9140312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 915b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 916b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 9179f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 9189f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 9199f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 9201845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 9211845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 9221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 923a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 924d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 9252b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// SimplifyXorInst - Given operands for a Xor, see if we can 9262b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// fold the result. If not, this returns null. 9272b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sandsstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 9282b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 9292b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 9302b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 9312b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 9322b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 9332b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Ops, 2, TD); 9342b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 9352b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9362b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // Canonicalize the constant to the RHS. 9372b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands std::swap(Op0, Op1); 9382b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 9392b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9402b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ undef -> undef 9412b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (isa<UndefValue>(Op1)) 942f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Op1; 9432b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9442b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ 0 = A 9452b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 9462b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 9472b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9482b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ A = 0 9497cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(Op0, Op1, MaxRecurse)) 9502b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getNullValue(Op0->getType()); 9512b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9522b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ ~A = ~A ^ A = -1 953566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = 0; 9547cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if ((match(Op0, m_Not(m_Value(A))) && equal(A, Op1, MaxRecurse)) || 9557cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands (match(Op1, m_Not(m_Value(A))) && equal(A, Op0, MaxRecurse))) 9562b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getAllOnesValue(Op0->getType()); 9572b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 958566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 959566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT, 960566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 961566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 9622b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9633421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Xor. Try some generic simplifications based on this. 9643421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, 9653421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 9663421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 9673421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 96887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Xor over selects and phi nodes is pointless, so don't bother. 96987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A ^ select(cond, B, C)" means evaluating 97087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 97187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 97287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 97387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 97487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 97587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 9762b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9772b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return 0; 9782b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 9792b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9802b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan SandsValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 9812b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT) { 9822b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 9832b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 9842b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 985210c5d4880b525e064088b6fec713260128c16ebChris Lattnerstatic const Type *GetCompareTy(Value *Op) { 986210c5d4880b525e064088b6fec713260128c16ebChris Lattner return CmpInst::makeCmpResultType(Op->getType()); 987210c5d4880b525e064088b6fec713260128c16ebChris Lattner} 988210c5d4880b525e064088b6fec713260128c16ebChris Lattner 9899dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 9909dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 991a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 9921845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 9931845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 9949f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 9959dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 99612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 997d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 9988f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 9998f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 1000d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 1001d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 1002d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 1003d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 1004d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 100512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1006210c5d4880b525e064088b6fec713260128c16ebChris Lattner // ITy - This is the return type of the compare we're considering. 1007210c5d4880b525e064088b6fec713260128c16ebChris Lattner const Type *ITy = GetCompareTy(LHS); 100812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1009210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp X, X -> true/false 1010c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 1011c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // because X could be 0. 10127cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (isa<UndefValue>(RHS) || equal(LHS, RHS, MaxRecurse)) 1013210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 101412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1015210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 1016210c5d4880b525e064088b6fec713260128c16ebChris Lattner // addresses never equal each other! We already know that Op0 != Op1. 101712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 1018210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(LHS)) && 101912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 1020210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(RHS))) 1021210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 102212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1023210c5d4880b525e064088b6fec713260128c16ebChris Lattner // See if we are doing a comparison with a constant. 1024210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1025210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If we have an icmp le or icmp ge instruction, turn it into the 1026210c5d4880b525e064088b6fec713260128c16ebChris Lattner // appropriate icmp lt or icmp gt instruction. This allows us to rely on 1027210c5d4880b525e064088b6fec713260128c16ebChris Lattner // them being folded in the code below. 1028210c5d4880b525e064088b6fec713260128c16ebChris Lattner switch (Pred) { 1029210c5d4880b525e064088b6fec713260128c16ebChris Lattner default: break; 1030210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_ULE: 1031210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 1032210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 1033210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 1034210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SLE: 1035210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 1036210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 1037210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 1038210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_UGE: 1039210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(false)) // A >=u MIN -> TRUE 1040210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 1041210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 1042210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SGE: 1043210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(true)) // A >=s MIN -> TRUE 1044210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 1045210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 1046210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 1047210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 10481ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 10491ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // If the comparison is with the result of a select instruction, check whether 10501ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // comparing with either branch of the select always yields the same value. 10510312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 10520312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1053a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1054a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1055a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 1056a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 10570312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 10580312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 10593bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 10601ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 10619dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return 0; 10629dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 10639dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1064a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 10651845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 10661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1067a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1068a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 10699dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 10709dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 1071a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 10721845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 10731845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 10749dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 10759dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 10769dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1077d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 10789dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 10799dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 108012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1081d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 1082d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 1083d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 1084d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 108512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1086210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Fold trivial predicates. 1087210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_FALSE) 1088210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 1089210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_TRUE) 1090210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 1091210c5d4880b525e064088b6fec713260128c16ebChris Lattner 1092210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 1093210c5d4880b525e064088b6fec713260128c16ebChris Lattner return UndefValue::get(GetCompareTy(LHS)); 1094210c5d4880b525e064088b6fec713260128c16ebChris Lattner 1095210c5d4880b525e064088b6fec713260128c16ebChris Lattner // fcmp x,x -> true/false. Not all compares are foldable. 10967cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(LHS, RHS, MaxRecurse)) { 1097210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isTrueWhenEqual(Pred)) 1098210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 1099210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isFalseWhenEqual(Pred)) 1100210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 1101210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 110212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1103210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Handle fcmp with constant RHS 1104210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1105210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If the constant is a nan, see if we can fold the comparison based on it. 1106210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 1107210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CFP->getValueAPF().isNaN()) { 1108210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 1109210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getFalse(CFP->getContext()); 1110210c5d4880b525e064088b6fec713260128c16ebChris Lattner assert(FCmpInst::isUnordered(Pred) && 1111210c5d4880b525e064088b6fec713260128c16ebChris Lattner "Comparison must be either ordered or unordered!"); 1112210c5d4880b525e064088b6fec713260128c16ebChris Lattner // True if unordered. 1113210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CFP->getContext()); 1114210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 11156b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // Check whether the constant is an infinity. 11166b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isInfinity()) { 11176b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isNegative()) { 11186b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 11196b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OLT: 11206b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and less than negative infinity. 11216b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 11226b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_UGE: 11236b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with or at least negative infinity. 11246b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 11256b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 11266b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 11276b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 11286b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } else { 11296b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 11306b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OGT: 11316b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and greater than infinity. 11326b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 11336b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_ULE: 11346b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with and at most infinity. 11356b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 11366b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 11376b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 11386b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 11396b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 11406b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 1141210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 1142210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 114312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 114492826def593df7a422c7b07f09342febce81ddd3Duncan Sands // If the comparison is with the result of a select instruction, check whether 114592826def593df7a422c7b07f09342febce81ddd3Duncan Sands // comparing with either branch of the select always yields the same value. 11460312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 11470312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1148a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1149a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1150a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 1151a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 11520312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 11530312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 11543bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 115592826def593df7a422c7b07f09342febce81ddd3Duncan Sands 11569f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 11579f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 11589f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 1159a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 11601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 11611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1162a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1163a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1164047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 1165047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// the result. If not, this returns null. 11667cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sandsstatic Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 11677cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands const TargetData *TD, const DominatorTree *, 11687cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands unsigned MaxRecurse) { 1169047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select true, X, Y -> X 1170047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select false, X, Y -> Y 1171047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 1172047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return CB->getZExtValue() ? TrueVal : FalseVal; 117312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1174047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select C, X, X -> X 11757cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands if (equal(TrueVal, FalseVal, MaxRecurse)) 1176047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 117712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1178047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 1179047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 1180047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 1181047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 1182047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 1183047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<Constant>(TrueVal)) 1184047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 1185047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 1186047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner } 118712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1188047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return 0; 1189047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner} 1190047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 11917cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan SandsValue *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 11927cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands const TargetData *TD, const DominatorTree *DT) { 11937cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands return ::SimplifySelectInst(CondVal, TrueVal, FalseVal, TD, DT, 11947cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands RecursionLimit); 11957cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands} 11967cf85e74e3885005ca8e5fdb155fa5351e255b85Duncan Sands 1197c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 1198c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// fold the result. If not, this returns null. 1199c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris LattnerValue *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 12001845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 120185bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // The type of the GEP pointer operand. 120285bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()); 120385bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands 1204c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P -> P. 1205c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 1) 1206c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 1207c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 120885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands if (isa<UndefValue>(Ops[0])) { 120985bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // Compute the (pointer) type returned by the GEP instruction. 121085bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1], 121185bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands NumOps-1); 121285bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 121385bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands return UndefValue::get(GEPTy); 121485bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands } 1215c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1216e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (NumOps == 2) { 1217e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, 0 -> P. 1218c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 1219c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (C->isZero()) 1220c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 1221e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, N -> P if P points to a type of zero size. 1222e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (TD) { 122385bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *Ty = PtrTy->getElementType(); 1224a63395a30f9227bde826749d3480046301b47332Duncan Sands if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 1225e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands return Ops[0]; 1226e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 1227e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 122812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1229c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // Check to see if this is constant foldable. 1230c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner for (unsigned i = 0; i != NumOps; ++i) 1231c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (!isa<Constant>(Ops[i])) 1232c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return 0; 123312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1234c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 1235c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner (Constant *const*)Ops+1, NumOps-1); 1236c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner} 1237c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1238ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 1239ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sandsstatic Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 1240ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If all of the PHI's incoming values are the same then replace the PHI node 1241ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // with the common value. 1242ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *CommonValue = 0; 1243ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands bool HasUndefInput = false; 1244ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1245ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *Incoming = PN->getIncomingValue(i); 1246ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 1247ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (Incoming == PN) continue; 1248ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (isa<UndefValue>(Incoming)) { 1249ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // Remember that we saw an undef value, but otherwise ignore them. 1250ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands HasUndefInput = true; 1251ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands continue; 1252ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 1253ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (CommonValue && Incoming != CommonValue) 1254ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return 0; // Not the same, bail out. 1255ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands CommonValue = Incoming; 1256ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 1257ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1258ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If CommonValue is null then all of the incoming values were either undef or 1259ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // equal to the phi node itself. 1260ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (!CommonValue) 1261ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return UndefValue::get(PN->getType()); 1262ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1263ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If we have a PHI node like phi(X, undef, X), where X is defined by some 1264ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // instruction, we cannot return X as the result of the PHI node unless it 1265ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // dominates the PHI block. 1266ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (HasUndefInput) 1267ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 1268ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1269ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return CommonValue; 1270ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands} 1271ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1272c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1273d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner//=== Helper functions for higher up the class hierarchy. 12749dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1275d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 1276d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 1277a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 12781845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 12791845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 1280d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner switch (Opcode) { 1281ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false, 1282ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands /* isNUW */ false, TD, DT, 1283ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands MaxRecurse); 1284ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false, 1285ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands /* isNUW */ false, TD, DT, 1286ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands MaxRecurse); 128782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse); 128882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 128982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse); 129082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse); 1291d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner default: 1292d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1293d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 1294d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *COps[] = {CLHS, CRHS}; 1295d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 1296d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 1297b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1298566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If the operation is associative, try some generic simplifications. 1299566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Instruction::isAssociative(Opcode)) 1300566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT, 1301566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 1302566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 1303566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 1304b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 1305b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 13060312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 13071845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 13080312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 1309a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1310a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1311a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 1312a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 13130312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 13140312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse)) 1315b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 1316b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1317d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 1318d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 1319d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 13209dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 132112a86f5b3199e72e6d967781acc76340f5920e46Duncan SandsValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 13221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 13231845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 1324a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1325a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 13269dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 13279dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. 1328a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 13291845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 13301845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 13319dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 13321845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 13331845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 13349dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 13359dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1336a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 13371845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 13381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1339a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1340e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 1341e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// SimplifyInstruction - See if we can compute a simplified version of this 1342e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// instruction. If not, this returns null. 1343eff0581583ef10e2872e9baf537a04b67d992101Duncan SandsValue *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 1344eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 1345d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Value *Result; 1346d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1347e34537856a544c83513e390ac9552a8bc3823346Chris Lattner switch (I->getOpcode()) { 1348e34537856a544c83513e390ac9552a8bc3823346Chris Lattner default: 1349d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = ConstantFoldInstruction(I, TD); 1350d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 13518aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner case Instruction::Add: 1352d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 1353d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1354d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1355d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands TD, DT); 1356d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1357fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands case Instruction::Sub: 1358fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 1359fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1360fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1361fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands TD, DT); 1362fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands break; 136382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Mul: 136482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT); 136582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands break; 1366e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::And: 1367d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 1368d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1369e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::Or: 1370d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1371d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 13722b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands case Instruction::Xor: 13732b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 13742b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands break; 1375e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::ICmp: 1376d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 1377d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1378d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1379e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::FCmp: 1380d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 1381d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1382d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1383047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner case Instruction::Select: 1384d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 1385d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(2), TD, DT); 1386d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1387c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner case Instruction::GetElementPtr: { 1388c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 1389d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 1390d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1391c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner } 1392cd6636c737a82949ad13db2d0d918af6424fb78bDuncan Sands case Instruction::PHI: 1393d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyPHINode(cast<PHINode>(I), DT); 1394d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1395e34537856a544c83513e390ac9552a8bc3823346Chris Lattner } 1396d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1397d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// If called on unreachable code, the above logic may report that the 1398d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// instruction simplified to itself. Make life easier for users by 1399f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands /// detecting that case here, returning a safe value instead. 1400f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Result == I ? UndefValue::get(I->getType()) : Result; 1401e34537856a544c83513e390ac9552a8bc3823346Chris Lattner} 1402e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 140340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 140440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// delete the From instruction. In addition to a basic RAUW, this does a 140540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursive simplification of the newly formed instructions. This catches 140640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// things where one simplification exposes other opportunities. This only 140740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// simplifies and deletes scalar operations, it does not change the CFG. 140840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 140940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 1410eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const TargetData *TD, 1411eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 141240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 141312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1414d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 1415d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // we can know if it gets deleted out from under us or replaced in a 1416d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // recursive simplification. 141740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH FromHandle(From); 1418d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner WeakVH ToHandle(To); 141912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 142040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (!From->use_empty()) { 142140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Update the instruction to use the new value. 1422d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Use &TheUse = From->use_begin().getUse(); 1423d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Instruction *User = cast<Instruction>(TheUse.getUser()); 1424d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner TheUse = To; 1425d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner 1426d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Check to see if the instruction can be folded due to the operand 1427d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // replacement. For example changing (or X, Y) into (or X, -1) can replace 1428d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // the 'or' with -1. 1429d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Value *SimplifiedVal; 1430d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner { 1431d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Sanity check to make sure 'User' doesn't dangle across 1432d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // SimplifyInstruction. 1433d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner AssertingVH<> UserHandle(User); 143412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1435eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands SimplifiedVal = SimplifyInstruction(User, TD, DT); 1436d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (SimplifiedVal == 0) continue; 143740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 143812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1439d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Recursively simplify this user to the new value. 1440eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 1441d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 1442d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner To = ToHandle; 144312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1444d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner assert(ToHandle && "To value deleted by recursive simplification?"); 144512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1446d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If the recursive simplification ended up revisiting and deleting 1447d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // 'From' then we're done. 1448d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (From == 0) 1449d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner return; 145040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 145112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1452d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If 'From' has value handles referring to it, do a real RAUW to update them. 1453d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From->replaceAllUsesWith(To); 145412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 145540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner From->eraseFromParent(); 145640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 1457