InstructionSimplify.cpp revision a3c44a5280042dbc0cde995675c225ede4528c6e
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 311845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#define RecursionLimit 3 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 481845009290e4d804ad377927bd8a08cca3036adcDuncan Sands/// ValueDominatesPHI - Does the given value dominate the specified phi node? 491845009290e4d804ad377927bd8a08cca3036adcDuncan Sandsstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 501845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Instruction *I = dyn_cast<Instruction>(V); 511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!I) 521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Arguments and constants dominate all instructions. 531845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 541845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // If we have a DominatorTree then do a precise test. 561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (DT) 571845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return DT->dominates(I, P); 581845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 591845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Otherwise, if the instruction is in the entry block, and is not an invoke, 601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // then it obviously dominates all phi nodes. 611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 621845009290e4d804ad377927bd8a08cca3036adcDuncan Sands !isa<InvokeInst>(I)) 631845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 641845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 651845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return false; 661845009290e4d804ad377927bd8a08cca3036adcDuncan Sands} 67a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 683421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 693421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 703421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 713421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 723421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Returns the simplified value, or null if no simplification was performed. 733421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sandsstatic Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 743421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands unsigned OpcodeToExpand, const TargetData *TD, 753421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 763421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 773421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!MaxRecurse--) 783421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 793421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 803421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Check whether the expression has the form "(A op' B) op C". 813421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 823421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Op0->getOpcode() == OpcodeToExpand) { 833421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Try turning it into "(A op C) op' (B op C)". 843421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 853421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Do "A op C" and "B op C" both simplify? 863421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *L = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) 873421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *R = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 883421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // They do! Return "L op' R" if it simplifies or is already available. 893421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 90a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) 91a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands && L == B && R == A)) { 92a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 933421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return LHS; 94a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 953421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "L op' R" if it simplifies. 96a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT, 97a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands MaxRecurse)) { 98a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 993421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 100a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1013421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1023421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1033421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1043421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Check whether the expression has the form "A op (B op' C)". 1053421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 1063421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Op1->getOpcode() == OpcodeToExpand) { 1073421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Try turning it into "(A op B) op' (A op C)". 1083421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 1093421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Do "A op B" and "A op C" both simplify? 1103421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *L = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) 1113421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *R = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) { 1123421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // They do! Return "L op' R" if it simplifies or is already available. 1133421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 114a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) 115a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands && L == C && R == B)) { 116a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1173421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return RHS; 118a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1193421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "L op' R" if it simplifies. 120a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT, 121a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands MaxRecurse)) { 122a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumExpand; 1233421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 124a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1253421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1263421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1273421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1283421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1293421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands} 1303421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1313421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term 1323421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// using the operation OpCodeToExtract. For example, when Opcode is Add and 1333421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)". 1343421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Returns the simplified value, or null if no simplification was performed. 1353421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sandsstatic Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 1363421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands unsigned OpcodeToExtract, const TargetData *TD, 1373421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 1383421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 1393421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!MaxRecurse--) 1403421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1413421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1423421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 1433421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 1443421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1453421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!Op0 || Op0->getOpcode() != OpcodeToExtract || 1463421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands !Op1 || Op1->getOpcode() != OpcodeToExtract) 1473421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1483421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1493421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // The expression has the form "(A op' B) op (C op' D)". 15082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); 15182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); 1523421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1533421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)". 1543421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does the instruction have the form "(A op' B) op (A op' D)" or, in the 1553421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // commutative case, "(A op' B) op (C op' A)"? 1563421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) { 1573421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *DD = A == C ? D : C; 1583421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Form "A op' (B op DD)" if it simplifies completely. 1593421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does "B op DD" simplify? 1603421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, DT, MaxRecurse)) { 1613421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Return "A op' V" if it simplifies or is already available. 1623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If V equals B then "A op' V" is just the LHS. 163a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (V == B) { 164a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 165a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands return LHS; 166a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1673421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "A op' V" if it simplifies. 168a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, DT, MaxRecurse)) { 169a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 1703421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return W; 171a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1723421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1733421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1743421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1753421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)". 1763421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does the instruction have the form "(A op' B) op (C op' B)" or, in the 1773421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // commutative case, "(A op' B) op (B op' D)"? 1783421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) { 1793421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *CC = B == D ? C : D; 1803421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Form "(A op CC) op' B" if it simplifies completely.. 1813421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does "A op CC" simplify? 1823421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, DT, MaxRecurse)) { 1833421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Return "V op' B" if it simplifies or is already available. 1843421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If V equals A then "V op' B" is just the LHS. 185a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (V == B) { 186a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 187a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands return LHS; 188a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1893421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "V op' B" if it simplifies. 190a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, DT, MaxRecurse)) { 191a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumFactor; 1923421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return W; 193a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 1943421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1953421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1963421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1983421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands} 1993421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 2003421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// SimplifyAssociativeBinOp - Generic simplifications for associative binary 2013421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// operations. Returns the simpler value, or null if none was found. 202566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sandsstatic Value *SimplifyAssociativeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 203566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const TargetData *TD, 204566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const DominatorTree *DT, 205566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands unsigned MaxRecurse) { 206566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 207566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 208566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 209566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!MaxRecurse--) 210566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 211566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 212566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 213566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 214566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 215566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 216566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 217566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 218566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 219566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 220566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 221566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "B op C" simplify? 222566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 223566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "A op V" if it simplifies or is already available. 224566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "A op V" is just the LHS. 2253421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == B) return LHS; 226566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "A op V" if it simplifies. 227a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) { 228a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 229566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 230a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 231566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 232566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 233566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 234566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 235566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 236566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 237566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 238566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 239566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 240566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "A op B" simplify? 241566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) { 242566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op C" if it simplifies or is already available. 243566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "V op C" is just the RHS. 2443421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == B) return RHS; 245566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op C" if it simplifies. 246a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) { 247a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 248566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 249a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 250566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 251566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 252566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 253566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // The remaining transforms require commutativity as well as associativity. 254566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!Instruction::isCommutative(Opcode)) 255566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 256566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 257566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 258566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 259566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 260566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 261566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 262566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 263566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 264566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 265566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op B" if it simplifies or is already available. 266566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals A then "V op B" is just the LHS. 2673421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == A) return LHS; 268566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op B" if it simplifies. 269a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) { 270a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 271566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 272a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 273566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 274566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 275566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 276566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 277566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 278566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 279566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 280566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 281566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 282566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 283566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 284566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "B op V" if it simplifies or is already available. 285566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals C then "B op V" is just the RHS. 2863421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == C) return RHS; 287566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "B op V" if it simplifies. 288a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) { 289a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands ++NumReassoc; 290566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 291a3c44a5280042dbc0cde995675c225ede4528c6eDuncan Sands } 292566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 293566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 294566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 295566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 296566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands} 297566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 298b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadBinOpOverSelect - In the case of a binary operation with a select 299b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// instruction as an operand, try to simplify the binop by seeing whether 300b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// evaluating it on both branches of the select results in the same value. 301b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// Returns the common value if so, otherwise returns null. 302b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 3031845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, 3041845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 3051845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 3060312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 3070312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 3080312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 3090312a93693abc2eb682b2b101c889959888fd883Duncan Sands 310b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI; 311b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (isa<SelectInst>(LHS)) { 312b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(LHS); 313b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 314b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 315b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(RHS); 316b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 317b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 318b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Evaluate the BinOp on the true and false branches of the select. 319b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *TV; 320b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *FV; 321b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (SI == LHS) { 3221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse); 3231845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse); 324b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 3251845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse); 3261845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse); 327b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 328b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 329b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they simplified to the same value, then return the common value. 330b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they both failed to simplify then return null. 331b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == FV) 332b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 333b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 334b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified to undef, return the other one. 335b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV && isa<UndefValue>(TV)) 336b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return FV; 337b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (FV && isa<UndefValue>(FV)) 338b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 339b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 340b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If applying the operation did not change the true and false select values, 341b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // then the result of the binop is the select itself. 342b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 343b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return SI; 344b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 345b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified and the other did not, and the simplified 346b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // value is equal to the unsimplified one, return the simplified value. 347b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // For example, select (cond, X, X & Z) & Z -> X & Z. 348b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if ((FV && !TV) || (TV && !FV)) { 349b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Check that the simplified value has the form "X op Y" where "op" is the 350b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // same as the original operation. 351b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 352b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified && Simplified->getOpcode() == Opcode) { 353b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 354b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // We already know that "op" is the same as for the simplified value. See 355b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // if the operands match too. If so, return the simplified value. 356b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 357b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 358b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 359b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->getOperand(0) == UnsimplifiedLHS && 360b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedRHS) 361b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 362b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->isCommutative() && 363b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedLHS && 364b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(0) == UnsimplifiedRHS) 365b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 366b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 367b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 368b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 369b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 370b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 371b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 372b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 373b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// try to simplify the comparison by seeing whether both branches of the select 374b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// result in the same value. Returns the common value if so, otherwise returns 375b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// null. 376b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 377a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *RHS, const TargetData *TD, 3781845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 379a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 3800312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 3810312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 3820312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 3830312a93693abc2eb682b2b101c889959888fd883Duncan Sands 384b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Make sure the select is on the LHS. 385b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (!isa<SelectInst>(LHS)) { 386b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands std::swap(LHS, RHS); 387b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 388b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 389b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 390b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI = cast<SelectInst>(LHS); 391b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 392b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Now that we have "cmp select(cond, TV, FV), RHS", analyse it. 393b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Does "cmp TV, RHS" simplify? 3941845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT, 395a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 396b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! Does "cmp FV, RHS" simplify? 3971845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT, 398a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 399b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! If they simplified to the same value, then use it as the 400b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // result of the original comparison. 401b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TCmp == FCmp) 402b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TCmp; 403b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 404b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 405b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 406a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 407a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 408a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// it on the incoming phi values yields the same result for every value. If so 409a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// returns the common value, otherwise returns null. 410a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 4111845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 4121845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 4130312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 4140312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 4150312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 4160312a93693abc2eb682b2b101c889959888fd883Duncan Sands 417a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI; 418a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (isa<PHINode>(LHS)) { 419a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(LHS); 4201845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 4211845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 4221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 423a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } else { 424a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 425a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(RHS); 4261845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if LHS and the phi may be mutually interdependent due to a loop. 4271845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(LHS, PI, DT)) 4281845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 429a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 430a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 431a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 432a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 433a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 434552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 435ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 436552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 437a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *V = PI == LHS ? 4381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 4391845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 440a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 441a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 442a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 443a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 444a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 445a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 446a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 447a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 448a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 449a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 450a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 451a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// try to simplify the comparison by seeing whether comparing with all of the 452a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// incoming phi values yields the same result every time. If so returns the 453a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// common result, otherwise returns null. 454a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 4551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 4561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 4570312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 4580312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 4590312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 4600312a93693abc2eb682b2b101c889959888fd883Duncan Sands 461a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Make sure the phi is on the LHS. 462a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!isa<PHINode>(LHS)) { 463a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands std::swap(LHS, RHS); 464a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 465a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 466a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 467a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI = cast<PHINode>(LHS); 468a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 4691845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 4701845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 4711845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 4721845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 473a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 474a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 475a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 476552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 477ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 478552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 4791845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 480a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 481a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 482a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 483a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 484a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 485a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 486a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 487a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 488a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 489a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 4908aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 491d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 492ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 493ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT, 494ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 495d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 496d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 497d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 4988aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 4998aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Ops, 2, TD); 5008aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 50112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 5028aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // Canonicalize the constant to the RHS. 5038aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner std::swap(Op0, Op1); 5048aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 50512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 506fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + undef -> undef 507fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (isa<UndefValue>(Op1)) 508fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op1; 50912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 510fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + 0 -> X 511fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 512fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 513fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 514fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + (Y - X) -> Y 515fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y - X) + X -> Y 516ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands // Eg: X + -X -> 0 517fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Value *Y = 0; 518fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 519fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 520fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Y; 521fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 522fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + ~X -> -1 since ~X = -X-1 523fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op0, m_Not(m_Specific(Op1))) || 524fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op1, m_Not(m_Specific(Op0)))) 525fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getAllOnesValue(Op0->getType()); 52687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 52782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 add -> xor. 52875d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 52907f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 53007f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 53182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 532566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 533566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT, 534566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 535566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 536566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 5373421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Mul distributes over Add. Try some generic simplifications based on this. 5383421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, 5393421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 5403421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 5413421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 54287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Add over selects and phi nodes is pointless, so don't bother. 54387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A + select(cond, B, C)" means evaluating 54487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 54587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 54687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 54787689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 54887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 54987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 55087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 5518aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return 0; 5528aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner} 5538aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner 554ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 555ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 556ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 557ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 558ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 559fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// SimplifySubInst - Given operands for a Sub, see if we can 560fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// fold the result. If not, this returns null. 561ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 5623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const TargetData *TD, const DominatorTree *DT, 563ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 564fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) 565fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 566fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Constant *Ops[] = { CLHS, CRHS }; 567fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 568fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Ops, 2, TD); 569fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands } 570fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 571fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - undef -> undef 572fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // undef - X -> undef 573fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1)) 574fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return UndefValue::get(Op0->getType()); 575fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 576fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - 0 -> X 577fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 578fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 579fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 580fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - X -> 0 581fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Op0 == Op1) 582fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getNullValue(Op0->getType()); 583fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 584fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (X + Y) - Y -> X 585fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y + X) - Y -> X 586fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Value *X = 0; 587fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op0, m_Add(m_Value(X), m_Specific(Op1))) || 588fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op0, m_Add(m_Specific(Op1), m_Value(X)))) 589fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return X; 590fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 59182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 sub -> xor. 59275d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 59307f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 59407f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 59582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 5963421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Mul distributes over Sub. Try some generic simplifications based on this. 5973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, 5983421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 5993421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 6003421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 601fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading Sub over selects and phi nodes is pointless, so don't bother. 602fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading over the select in "A - select(cond, B, C)" means evaluating 603fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 604fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 605fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 606fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // have been simplified to the common value of B and C already. Analysing 607fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 608fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // for threading over phi nodes. 609fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 610fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return 0; 611fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands} 612fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 613ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 614ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 615ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 616ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 617ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 61882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands/// SimplifyMulInst - Given operands for a Mul, see if we can 61982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands/// fold the result. If not, this returns null. 62082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 62182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 62282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 62382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 62482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 62582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 62682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Ops, 2, TD); 62782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands } 62882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 62982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Canonicalize the constant to the RHS. 63082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands std::swap(Op0, Op1); 63182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands } 63282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 63382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * undef -> 0 63482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<UndefValue>(Op1)) 63582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Constant::getNullValue(Op0->getType()); 63682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 63782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * 0 -> 0 63882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (match(Op1, m_Zero())) 63982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Op1; 64082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 64182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * 1 -> X 64282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (match(Op1, m_One())) 64382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Op0; 64482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 64582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 mul -> and. 64675d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 64707f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1)) 64807f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 64982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 65082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Try some generic simplifications for associative operations. 65182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT, 65282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 65382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 65482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 65582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Mul distributes over Add. Try some generic simplifications based on this. 65682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 65782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands TD, DT, MaxRecurse)) 65882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 65982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 66082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // If the operation is with the result of a select instruction, check whether 66182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // operating on either branch of the select always yields the same value. 66282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 66382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT, 66482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 66582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 66682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 66782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // If the operation is with the result of a phi instruction, check whether 66882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // operating on all incoming values of the phi always yields the same value. 66982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 67082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT, 67182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 67282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 67382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 67482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return 0; 67582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands} 67682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 67782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan SandsValue *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 67882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *DT) { 67982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit); 68082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands} 68182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 6828aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 6838aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// fold the result. If not, this returns null. 684a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 6851845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 6868aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 6878aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 6888aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 689d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 690d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 691d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 69212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 693d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 694d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 695d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 69612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 697d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & undef -> 0 698d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 699d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 70012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 701d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & X = X 702d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 703d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 70412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 7052b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & 0 = 0 7062b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 707d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 70812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 7092b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & -1 = X 7102b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 7112b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 71212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 713d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & ~A = ~A & A = 0 714e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 71570ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 71670ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 717d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 71812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 719d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A | ?) & A = A 720d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 721d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 722d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 72312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 724d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & (A | ?) = A 725d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 726d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 727d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 72812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 729566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 730566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT, 731566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 732566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 7336844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 7343421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Or. Try some generic simplifications based on this. 7353421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 7363421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 7373421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 7383421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 7393421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Xor. Try some generic simplifications based on this. 7403421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 7413421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 7423421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 7433421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 7443421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Or distributes over And. Try some generic simplifications based on this. 7453421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, 7463421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 7473421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 7483421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 749b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 750b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 7510312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 7521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 7530312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 754a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 755a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 756a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 757a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 7580312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 7591845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 7600312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 761b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 762b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 763d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 764d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 7659f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 7661845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 7671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 7681845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 769a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 770a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 771d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 7729f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner/// fold the result. If not, this returns null. 773a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 7741845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 775d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 776d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 777d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 778d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 779d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 780d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 78112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 782d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 783d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 784d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 78512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 786d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | undef -> -1 787d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 788d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 78912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 790d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | X = X 791d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 792d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 793d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 7942b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | 0 = X 7952b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 796d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 79712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 7982b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | -1 = -1 7992b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 8002b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op1; 80112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 802d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | ~A = ~A | A = -1 803e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 80470ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 80570ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 806d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 80712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 808d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A & ?) | A = A 809d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(B))) && 810d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 811d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 81212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 813d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | (A & ?) = A 814d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_And(m_Value(A), m_Value(B))) && 815d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 816d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 81712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 818566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 819566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT, 820566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 821566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 8226844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 8233421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Or distributes over And. Try some generic simplifications based on this. 8243421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, 8253421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 8263421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 8273421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 8283421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Or. Try some generic simplifications based on this. 8293421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, 8303421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 8313421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 8323421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 833b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 834b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 8350312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 8361845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 8370312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 838a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 839a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 840a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 841a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 8420312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 8431845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 8440312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 845b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 846b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 8479f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 8489f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 8499f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 8501845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 8511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 8521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 853a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 854d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 8552b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// SimplifyXorInst - Given operands for a Xor, see if we can 8562b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// fold the result. If not, this returns null. 8572b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sandsstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 8582b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 8592b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 8602b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 8612b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 8622b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 8632b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Ops, 2, TD); 8642b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 8652b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8662b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // Canonicalize the constant to the RHS. 8672b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands std::swap(Op0, Op1); 8682b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 8692b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8702b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ undef -> undef 8712b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (isa<UndefValue>(Op1)) 872f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Op1; 8732b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8742b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ 0 = A 8752b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 8762b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 8772b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8782b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ A = 0 8792b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Op0 == Op1) 8802b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getNullValue(Op0->getType()); 8812b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8822b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ ~A = ~A ^ A = -1 883566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = 0; 8842b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 8852b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (match(Op1, m_Not(m_Value(A))) && A == Op0)) 8862b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getAllOnesValue(Op0->getType()); 8872b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 888566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 889566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT, 890566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 891566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 8922b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8933421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Xor. Try some generic simplifications based on this. 8943421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, 8953421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 8963421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 8973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 89887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Xor over selects and phi nodes is pointless, so don't bother. 89987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A ^ select(cond, B, C)" means evaluating 90087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 90187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 90287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 90387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 90487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 90587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 9062b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9072b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return 0; 9082b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 9092b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 9102b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan SandsValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 9112b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT) { 9122b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 9132b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 9142b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 915210c5d4880b525e064088b6fec713260128c16ebChris Lattnerstatic const Type *GetCompareTy(Value *Op) { 916210c5d4880b525e064088b6fec713260128c16ebChris Lattner return CmpInst::makeCmpResultType(Op->getType()); 917210c5d4880b525e064088b6fec713260128c16ebChris Lattner} 918210c5d4880b525e064088b6fec713260128c16ebChris Lattner 9199dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 9209dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 921a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 9221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 9231845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 9249f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 9259dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 92612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 927d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 9288f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 9298f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 930d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 931d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 932d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 933d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 934d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 93512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 936210c5d4880b525e064088b6fec713260128c16ebChris Lattner // ITy - This is the return type of the compare we're considering. 937210c5d4880b525e064088b6fec713260128c16ebChris Lattner const Type *ITy = GetCompareTy(LHS); 93812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 939210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp X, X -> true/false 940c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 941c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // because X could be 0. 942c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner if (LHS == RHS || isa<UndefValue>(RHS)) 943210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 94412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 945210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 946210c5d4880b525e064088b6fec713260128c16ebChris Lattner // addresses never equal each other! We already know that Op0 != Op1. 94712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 948210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(LHS)) && 94912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 950210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(RHS))) 951210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 95212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 953210c5d4880b525e064088b6fec713260128c16ebChris Lattner // See if we are doing a comparison with a constant. 954210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 955210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If we have an icmp le or icmp ge instruction, turn it into the 956210c5d4880b525e064088b6fec713260128c16ebChris Lattner // appropriate icmp lt or icmp gt instruction. This allows us to rely on 957210c5d4880b525e064088b6fec713260128c16ebChris Lattner // them being folded in the code below. 958210c5d4880b525e064088b6fec713260128c16ebChris Lattner switch (Pred) { 959210c5d4880b525e064088b6fec713260128c16ebChris Lattner default: break; 960210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_ULE: 961210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 962210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 963210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 964210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SLE: 965210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 966210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 967210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 968210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_UGE: 969210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(false)) // A >=u MIN -> TRUE 970210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 971210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 972210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SGE: 973210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(true)) // A >=s MIN -> TRUE 974210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 975210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 976210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 977210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 9781ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 9791ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // If the comparison is with the result of a select instruction, check whether 9801ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // comparing with either branch of the select always yields the same value. 9810312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 9820312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 983a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 984a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 985a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 986a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 9870312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 9880312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 9893bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 9901ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 9919dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return 0; 9929dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 9939dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 994a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 9951845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 9961845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 997a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 998a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 9999dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 10009dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 1001a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 10021845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 10031845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 10049dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 10059dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 10069dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1007d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 10089dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 10099dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 101012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1011d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 1012d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 1013d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 1014d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 101512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1016210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Fold trivial predicates. 1017210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_FALSE) 1018210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 1019210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_TRUE) 1020210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 1021210c5d4880b525e064088b6fec713260128c16ebChris Lattner 1022210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 1023210c5d4880b525e064088b6fec713260128c16ebChris Lattner return UndefValue::get(GetCompareTy(LHS)); 1024210c5d4880b525e064088b6fec713260128c16ebChris Lattner 1025210c5d4880b525e064088b6fec713260128c16ebChris Lattner // fcmp x,x -> true/false. Not all compares are foldable. 1026210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (LHS == RHS) { 1027210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isTrueWhenEqual(Pred)) 1028210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 1029210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isFalseWhenEqual(Pred)) 1030210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 1031210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 103212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1033210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Handle fcmp with constant RHS 1034210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1035210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If the constant is a nan, see if we can fold the comparison based on it. 1036210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 1037210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CFP->getValueAPF().isNaN()) { 1038210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 1039210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getFalse(CFP->getContext()); 1040210c5d4880b525e064088b6fec713260128c16ebChris Lattner assert(FCmpInst::isUnordered(Pred) && 1041210c5d4880b525e064088b6fec713260128c16ebChris Lattner "Comparison must be either ordered or unordered!"); 1042210c5d4880b525e064088b6fec713260128c16ebChris Lattner // True if unordered. 1043210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CFP->getContext()); 1044210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 10456b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // Check whether the constant is an infinity. 10466b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isInfinity()) { 10476b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isNegative()) { 10486b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 10496b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OLT: 10506b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and less than negative infinity. 10516b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 10526b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_UGE: 10536b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with or at least negative infinity. 10546b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 10556b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 10566b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 10576b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 10586b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } else { 10596b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 10606b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OGT: 10616b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and greater than infinity. 10626b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 10636b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_ULE: 10646b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with and at most infinity. 10656b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 10666b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 10676b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 10686b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 10696b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 10706b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 1071210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 1072210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 107312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 107492826def593df7a422c7b07f09342febce81ddd3Duncan Sands // If the comparison is with the result of a select instruction, check whether 107592826def593df7a422c7b07f09342febce81ddd3Duncan Sands // comparing with either branch of the select always yields the same value. 10760312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 10770312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1078a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1079a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1080a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 1081a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 10820312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 10830312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 10843bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 108592826def593df7a422c7b07f09342febce81ddd3Duncan Sands 10869f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 10879f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 10889f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 1089a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 10901845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 10911845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1092a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1093a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1094047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 1095047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// the result. If not, this returns null. 1096047542669a20505fc7c5f2d93caa5610aa3db2c5Chris LattnerValue *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 10971845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 1098047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select true, X, Y -> X 1099047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select false, X, Y -> Y 1100047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 1101047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return CB->getZExtValue() ? TrueVal : FalseVal; 110212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1103047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select C, X, X -> X 1104047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (TrueVal == FalseVal) 1105047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 110612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1107047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 1108047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 1109047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 1110047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 1111047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 1112047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<Constant>(TrueVal)) 1113047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 1114047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 1115047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner } 111612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1117047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return 0; 1118047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner} 1119047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 1120c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 1121c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// fold the result. If not, this returns null. 1122c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris LattnerValue *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 11231845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 112485bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // The type of the GEP pointer operand. 112585bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()); 112685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands 1127c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P -> P. 1128c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 1) 1129c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 1130c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 113185bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands if (isa<UndefValue>(Ops[0])) { 113285bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // Compute the (pointer) type returned by the GEP instruction. 113385bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1], 113485bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands NumOps-1); 113585bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 113685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands return UndefValue::get(GEPTy); 113785bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands } 1138c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1139e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (NumOps == 2) { 1140e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, 0 -> P. 1141c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 1142c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (C->isZero()) 1143c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 1144e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, N -> P if P points to a type of zero size. 1145e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (TD) { 114685bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *Ty = PtrTy->getElementType(); 1147a63395a30f9227bde826749d3480046301b47332Duncan Sands if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 1148e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands return Ops[0]; 1149e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 1150e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 115112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1152c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // Check to see if this is constant foldable. 1153c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner for (unsigned i = 0; i != NumOps; ++i) 1154c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (!isa<Constant>(Ops[i])) 1155c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return 0; 115612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1157c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 1158c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner (Constant *const*)Ops+1, NumOps-1); 1159c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner} 1160c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1161ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 1162ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sandsstatic Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 1163ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If all of the PHI's incoming values are the same then replace the PHI node 1164ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // with the common value. 1165ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *CommonValue = 0; 1166ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands bool HasUndefInput = false; 1167ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1168ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *Incoming = PN->getIncomingValue(i); 1169ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 1170ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (Incoming == PN) continue; 1171ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (isa<UndefValue>(Incoming)) { 1172ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // Remember that we saw an undef value, but otherwise ignore them. 1173ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands HasUndefInput = true; 1174ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands continue; 1175ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 1176ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (CommonValue && Incoming != CommonValue) 1177ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return 0; // Not the same, bail out. 1178ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands CommonValue = Incoming; 1179ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 1180ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1181ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If CommonValue is null then all of the incoming values were either undef or 1182ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // equal to the phi node itself. 1183ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (!CommonValue) 1184ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return UndefValue::get(PN->getType()); 1185ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1186ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If we have a PHI node like phi(X, undef, X), where X is defined by some 1187ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // instruction, we cannot return X as the result of the PHI node unless it 1188ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // dominates the PHI block. 1189ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (HasUndefInput) 1190ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 1191ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1192ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return CommonValue; 1193ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands} 1194ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1195c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1196d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner//=== Helper functions for higher up the class hierarchy. 11979dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1198d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 1199d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 1200a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 12011845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 12021845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 1203d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner switch (Opcode) { 1204ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false, 1205ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands /* isNUW */ false, TD, DT, 1206ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands MaxRecurse); 1207ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false, 1208ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands /* isNUW */ false, TD, DT, 1209ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands MaxRecurse); 121082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse); 121182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 121282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse); 121382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse); 1214d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner default: 1215d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1216d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 1217d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *COps[] = {CLHS, CRHS}; 1218d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 1219d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 1220b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1221566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If the operation is associative, try some generic simplifications. 1222566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Instruction::isAssociative(Opcode)) 1223566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT, 1224566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 1225566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 1226566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 1227b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 1228b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 12290312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 12301845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 12310312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 1232a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1233a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1234a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 1235a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 12360312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 12370312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse)) 1238b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 1239b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1240d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 1241d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 1242d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 12439dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 124412a86f5b3199e72e6d967781acc76340f5920e46Duncan SandsValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 12451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 12461845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 1247a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1248a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 12499dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 12509dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. 1251a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 12521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 12531845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 12549dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 12551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 12561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 12579dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 12589dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1259a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 12601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 12611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1262a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1263e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 1264e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// SimplifyInstruction - See if we can compute a simplified version of this 1265e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// instruction. If not, this returns null. 1266eff0581583ef10e2872e9baf537a04b67d992101Duncan SandsValue *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 1267eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 1268d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Value *Result; 1269d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1270e34537856a544c83513e390ac9552a8bc3823346Chris Lattner switch (I->getOpcode()) { 1271e34537856a544c83513e390ac9552a8bc3823346Chris Lattner default: 1272d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = ConstantFoldInstruction(I, TD); 1273d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 12748aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner case Instruction::Add: 1275d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 1276d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1277d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1278d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands TD, DT); 1279d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1280fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands case Instruction::Sub: 1281fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 1282fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1283fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1284fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands TD, DT); 1285fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands break; 128682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Mul: 128782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT); 128882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands break; 1289e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::And: 1290d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 1291d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1292e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::Or: 1293d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1294d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 12952b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands case Instruction::Xor: 12962b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 12972b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands break; 1298e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::ICmp: 1299d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 1300d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1301d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1302e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::FCmp: 1303d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 1304d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1305d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1306047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner case Instruction::Select: 1307d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 1308d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(2), TD, DT); 1309d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1310c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner case Instruction::GetElementPtr: { 1311c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 1312d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 1313d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1314c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner } 1315cd6636c737a82949ad13db2d0d918af6424fb78bDuncan Sands case Instruction::PHI: 1316d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyPHINode(cast<PHINode>(I), DT); 1317d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1318e34537856a544c83513e390ac9552a8bc3823346Chris Lattner } 1319d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1320d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// If called on unreachable code, the above logic may report that the 1321d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// instruction simplified to itself. Make life easier for users by 1322f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands /// detecting that case here, returning a safe value instead. 1323f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Result == I ? UndefValue::get(I->getType()) : Result; 1324e34537856a544c83513e390ac9552a8bc3823346Chris Lattner} 1325e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 132640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 132740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// delete the From instruction. In addition to a basic RAUW, this does a 132840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursive simplification of the newly formed instructions. This catches 132940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// things where one simplification exposes other opportunities. This only 133040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// simplifies and deletes scalar operations, it does not change the CFG. 133140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 133240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 1333eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const TargetData *TD, 1334eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 133540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 133612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1337d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 1338d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // we can know if it gets deleted out from under us or replaced in a 1339d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // recursive simplification. 134040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH FromHandle(From); 1341d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner WeakVH ToHandle(To); 134212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 134340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (!From->use_empty()) { 134440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Update the instruction to use the new value. 1345d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Use &TheUse = From->use_begin().getUse(); 1346d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Instruction *User = cast<Instruction>(TheUse.getUser()); 1347d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner TheUse = To; 1348d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner 1349d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Check to see if the instruction can be folded due to the operand 1350d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // replacement. For example changing (or X, Y) into (or X, -1) can replace 1351d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // the 'or' with -1. 1352d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Value *SimplifiedVal; 1353d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner { 1354d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Sanity check to make sure 'User' doesn't dangle across 1355d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // SimplifyInstruction. 1356d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner AssertingVH<> UserHandle(User); 135712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1358eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands SimplifiedVal = SimplifyInstruction(User, TD, DT); 1359d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (SimplifiedVal == 0) continue; 136040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 136112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1362d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Recursively simplify this user to the new value. 1363eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 1364d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 1365d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner To = ToHandle; 136612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1367d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner assert(ToHandle && "To value deleted by recursive simplification?"); 136812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1369d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If the recursive simplification ended up revisiting and deleting 1370d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // 'From' then we're done. 1371d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (From == 0) 1372d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner return; 137340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 137412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1375d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If 'From' has value handles referring to it, do a real RAUW to update them. 1376d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From->replaceAllUsesWith(To); 137712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 137840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner From->eraseFromParent(); 137940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 1380