InstructionSimplify.cpp revision 07f30fbd734069b80b90c6aeea0ae645ce3880c0
19f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner//===- InstructionSimplify.cpp - Fold instruction operands ----------------===// 29f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 39f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// The LLVM Compiler Infrastructure 49f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 59f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// This file is distributed under the University of Illinois Open Source 69f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// License. See LICENSE.TXT for details. 79f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 89f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner//===----------------------------------------------------------------------===// 99f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 109f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// This file implements routines for folding instructions into simpler forms 114cd2ad15b43f21d641330b4b09961af08646445eDuncan Sands// that do not require creating new instructions. This does constant folding 124cd2ad15b43f21d641330b4b09961af08646445eDuncan Sands// ("add i32 1, 1" -> "2") but can also handle non-constant operands, either 134cd2ad15b43f21d641330b4b09961af08646445eDuncan Sands// returning a constant ("and i32 %x, 0" -> "0") or an already existing value 14ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands// ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been 15ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands// simplified: This is usually true and assuming it simplifies the logic (if 16ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands// they have not been simplified then results are correct but maybe suboptimal). 179f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner// 189f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner//===----------------------------------------------------------------------===// 199f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 209f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/InstructionSimplify.h" 219f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner#include "llvm/Analysis/ConstantFolding.h" 221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Analysis/Dominators.h" 23d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner#include "llvm/Support/PatternMatch.h" 241845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#include "llvm/Support/ValueHandle.h" 25e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands#include "llvm/Target/TargetData.h" 269f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattnerusing namespace llvm; 27d06094f0682f2ede03caff4892b1a57469896d48Chris Lattnerusing namespace llvm::PatternMatch; 289f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 291845009290e4d804ad377927bd8a08cca3036adcDuncan Sands#define RecursionLimit 3 30a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 3182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyAndInst(Value *, Value *, const TargetData *, 3282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 33a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const TargetData *, 341845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 35a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const TargetData *, 361845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *, unsigned); 3782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyOrInst(Value *, Value *, const TargetData *, 3882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 3982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyXorInst(Value *, Value *, const TargetData *, 4082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *, unsigned); 411845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 421845009290e4d804ad377927bd8a08cca3036adcDuncan Sands/// ValueDominatesPHI - Does the given value dominate the specified phi node? 431845009290e4d804ad377927bd8a08cca3036adcDuncan Sandsstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 441845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Instruction *I = dyn_cast<Instruction>(V); 451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!I) 461845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Arguments and constants dominate all instructions. 471845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 481845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 491845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // If we have a DominatorTree then do a precise test. 501845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (DT) 511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return DT->dominates(I, P); 521845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 531845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Otherwise, if the instruction is in the entry block, and is not an invoke, 541845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // then it obviously dominates all phi nodes. 551845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands !isa<InvokeInst>(I)) 571845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return true; 581845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 591845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return false; 601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands} 61a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 633421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 643421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 653421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 663421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Returns the simplified value, or null if no simplification was performed. 673421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sandsstatic Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 683421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands unsigned OpcodeToExpand, const TargetData *TD, 693421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 703421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 713421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!MaxRecurse--) 723421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 733421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 743421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Check whether the expression has the form "(A op' B) op C". 753421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 763421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Op0->getOpcode() == OpcodeToExpand) { 773421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Try turning it into "(A op C) op' (B op C)". 783421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 793421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Do "A op C" and "B op C" both simplify? 803421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *L = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) 813421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *R = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 823421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // They do! Return "L op' R" if it simplifies or is already available. 833421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 843421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if ((L == A && R == B) || 853421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands (Instruction::isCommutative(OpcodeToExpand) && L == B && R == A)) 863421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return LHS; 873421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "L op' R" if it simplifies. 883421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT,MaxRecurse)) 893421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 903421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 913421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 923421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 933421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Check whether the expression has the form "A op (B op' C)". 943421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 953421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Op1->getOpcode() == OpcodeToExpand) { 963421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Try turning it into "(A op B) op' (A op C)". 973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 983421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Do "A op B" and "A op C" both simplify? 993421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *L = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) 1003421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *R = SimplifyBinOp(Opcode, A, C, TD, DT, MaxRecurse)) { 1013421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // They do! Return "L op' R" if it simplifies or is already available. 1023421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 1033421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if ((L == B && R == C) || 1043421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands (Instruction::isCommutative(OpcodeToExpand) && L == C && R == B)) 1053421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return RHS; 1063421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "L op' R" if it simplifies. 1073421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, TD, DT,MaxRecurse)) 1083421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 1093421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1103421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1113421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1123421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1133421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands} 1143421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1153421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// FactorizeBinOp - Simplify "LHS Opcode RHS" by factorizing out a common term 1163421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// using the operation OpCodeToExtract. For example, when Opcode is Add and 1173421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// OpCodeToExtract is Mul then this tries to turn "(A*B)+(A*C)" into "A*(B+C)". 1183421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// Returns the simplified value, or null if no simplification was performed. 1193421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sandsstatic Value *FactorizeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 1203421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands unsigned OpcodeToExtract, const TargetData *TD, 1213421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 1223421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 1233421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!MaxRecurse--) 1243421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1253421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1263421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 1273421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 1283421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1293421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (!Op0 || Op0->getOpcode() != OpcodeToExtract || 1303421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands !Op1 || Op1->getOpcode() != OpcodeToExtract) 1313421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1323421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1333421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // The expression has the form "(A op' B) op (C op' D)". 13482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Value *A = Op0->getOperand(0), *B = Op0->getOperand(1); 13582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Value *C = Op1->getOperand(0), *D = Op1->getOperand(1); 1363421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1373421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Use left distributivity, i.e. "X op' (Y op Z) = (X op' Y) op (X op' Z)". 1383421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does the instruction have the form "(A op' B) op (A op' D)" or, in the 1393421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // commutative case, "(A op' B) op (C op' A)"? 1403421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (A == C || (Instruction::isCommutative(OpcodeToExtract) && A == D)) { 1413421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *DD = A == C ? D : C; 1423421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Form "A op' (B op DD)" if it simplifies completely. 1433421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does "B op DD" simplify? 1443421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(Opcode, B, DD, TD, DT, MaxRecurse)) { 1453421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Return "A op' V" if it simplifies or is already available. 1463421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If V equals B then "A op' V" is just the LHS. 1473421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == B) return LHS; 1483421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "A op' V" if it simplifies. 1493421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *W = SimplifyBinOp(OpcodeToExtract, A, V, TD, DT, MaxRecurse)) 1503421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return W; 1513421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1523421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1533421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1543421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Use right distributivity, i.e. "(X op Y) op' Z = (X op' Z) op (Y op' Z)". 1553421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does the instruction have the form "(A op' B) op (C op' B)" or, in the 1563421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // commutative case, "(A op' B) op (B op' D)"? 1573421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (B == D || (Instruction::isCommutative(OpcodeToExtract) && B == C)) { 1583421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands Value *CC = B == D ? C : D; 1593421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Form "(A op CC) op' B" if it simplifies completely.. 1603421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Does "A op CC" simplify? 1613421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = SimplifyBinOp(Opcode, A, CC, TD, DT, MaxRecurse)) { 1623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // It does! Return "V op' B" if it simplifies or is already available. 1633421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // If V equals A then "V op' B" is just the LHS. 1643421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == B) return LHS; 1653421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Otherwise return "V op' B" if it simplifies. 1663421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *W = SimplifyBinOp(OpcodeToExtract, V, B, TD, DT, MaxRecurse)) 1673421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return W; 1683421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1693421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands } 1703421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1713421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return 0; 1723421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands} 1733421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 1743421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// SimplifyAssociativeBinOp - Generic simplifications for associative binary 1753421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands/// operations. Returns the simpler value, or null if none was found. 176566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sandsstatic Value *SimplifyAssociativeBinOp(unsigned Opcode, Value *LHS, Value *RHS, 177566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const TargetData *TD, 178566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands const DominatorTree *DT, 179566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands unsigned MaxRecurse) { 180566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 181566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 182566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 183566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!MaxRecurse--) 184566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 185566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 186566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 187566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 188566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 189566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 190566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 191566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 192566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 193566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 194566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 195566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "B op C" simplify? 196566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, B, C, TD, DT, MaxRecurse)) { 197566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "A op V" if it simplifies or is already available. 198566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "A op V" is just the LHS. 1993421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == B) return LHS; 200566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "A op V" if it simplifies. 201566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *W = SimplifyBinOp(Opcode, A, V, TD, DT, MaxRecurse)) 202566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 203566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 204566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 205566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 206566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 207566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 208566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 209566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 210566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 211566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 212566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "A op B" simplify? 213566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, A, B, TD, DT, MaxRecurse)) { 214566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op C" if it simplifies or is already available. 215566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals B then "V op C" is just the RHS. 2163421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == B) return RHS; 217566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op C" if it simplifies. 218566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *W = SimplifyBinOp(Opcode, V, C, TD, DT, MaxRecurse)) 219566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 220566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 221566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 222566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 223566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // The remaining transforms require commutativity as well as associativity. 224566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (!Instruction::isCommutative(Opcode)) 225566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 226566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 227566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 228566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op0 && Op0->getOpcode() == Opcode) { 229566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = Op0->getOperand(0); 230566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op0->getOperand(1); 231566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = RHS; 232566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 233566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 234566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 235566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "V op B" if it simplifies or is already available. 236566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals A then "V op B" is just the LHS. 2373421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == A) return LHS; 238566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "V op B" if it simplifies. 239566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *W = SimplifyBinOp(Opcode, V, B, TD, DT, MaxRecurse)) 240566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 241566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 242566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 243566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 244566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 245566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Op1 && Op1->getOpcode() == Opcode) { 246566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = LHS; 247566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *B = Op1->getOperand(0); 248566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *C = Op1->getOperand(1); 249566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 250566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Does "C op A" simplify? 251566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyBinOp(Opcode, C, A, TD, DT, MaxRecurse)) { 252566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // It does! Return "B op V" if it simplifies or is already available. 253566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If V equals C then "B op V" is just the RHS. 2543421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (V == C) return RHS; 255566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Otherwise return "B op V" if it simplifies. 256566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *W = SimplifyBinOp(Opcode, B, V, TD, DT, MaxRecurse)) 257566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return W; 258566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 259566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands } 260566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 261566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return 0; 262566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands} 263566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 264b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadBinOpOverSelect - In the case of a binary operation with a select 265b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// instruction as an operand, try to simplify the binop by seeing whether 266b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// evaluating it on both branches of the select results in the same value. 267b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// Returns the common value if so, otherwise returns null. 268b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 2691845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, 2701845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 2711845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 2720312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 2730312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 2740312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 2750312a93693abc2eb682b2b101c889959888fd883Duncan Sands 276b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI; 277b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (isa<SelectInst>(LHS)) { 278b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(LHS); 279b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 280b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 281b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SI = cast<SelectInst>(RHS); 282b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 283b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 284b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Evaluate the BinOp on the true and false branches of the select. 285b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *TV; 286b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *FV; 287b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (SI == LHS) { 2881845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, TD, DT, MaxRecurse); 2891845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, TD, DT, MaxRecurse); 290b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } else { 2911845009290e4d804ad377927bd8a08cca3036adcDuncan Sands TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), TD, DT, MaxRecurse); 2921845009290e4d804ad377927bd8a08cca3036adcDuncan Sands FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), TD, DT, MaxRecurse); 293b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 294b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 295b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they simplified to the same value, then return the common value. 296b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If they both failed to simplify then return null. 297b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == FV) 298b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 299b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 300b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified to undef, return the other one. 301b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV && isa<UndefValue>(TV)) 302b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return FV; 303b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (FV && isa<UndefValue>(FV)) 304b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TV; 305b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 306b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If applying the operation did not change the true and false select values, 307b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // then the result of the binop is the select itself. 308b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 309b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return SI; 310b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 311b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If one branch simplified and the other did not, and the simplified 312b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // value is equal to the unsimplified one, return the simplified value. 313b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // For example, select (cond, X, X & Z) & Z -> X & Z. 314b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if ((FV && !TV) || (TV && !FV)) { 315b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Check that the simplified value has the form "X op Y" where "op" is the 316b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // same as the original operation. 317b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 318b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified && Simplified->getOpcode() == Opcode) { 319b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 320b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // We already know that "op" is the same as for the simplified value. See 321b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // if the operands match too. If so, return the simplified value. 322b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 323b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 324b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 325b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->getOperand(0) == UnsimplifiedLHS && 326b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedRHS) 327b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 328b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (Simplified->isCommutative() && 329b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(1) == UnsimplifiedLHS && 330b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Simplified->getOperand(0) == UnsimplifiedRHS) 331b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return Simplified; 332b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 333b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 334b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 335b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 336b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 337b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 338b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 339b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// try to simplify the comparison by seeing whether both branches of the select 340b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// result in the same value. Returns the common value if so, otherwise returns 341b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands/// null. 342b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sandsstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 343a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *RHS, const TargetData *TD, 3441845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, 345a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands unsigned MaxRecurse) { 3460312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 3470312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 3480312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 3490312a93693abc2eb682b2b101c889959888fd883Duncan Sands 350b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Make sure the select is on the LHS. 351b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (!isa<SelectInst>(LHS)) { 352b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands std::swap(LHS, RHS); 353b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 354b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands } 355b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 356b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands SelectInst *SI = cast<SelectInst>(LHS); 357b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 358b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Now that we have "cmp select(cond, TV, FV), RHS", analyse it. 359b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // Does "cmp TV, RHS" simplify? 3601845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *TCmp = SimplifyCmpInst(Pred, SI->getTrueValue(), RHS, TD, DT, 361a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 362b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! Does "cmp FV, RHS" simplify? 3631845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *FCmp = SimplifyCmpInst(Pred, SI->getFalseValue(), RHS, TD, DT, 364a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands MaxRecurse)) 365b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // It does! If they simplified to the same value, then use it as the 366b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // result of the original comparison. 367b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands if (TCmp == FCmp) 368b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return TCmp; 369b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return 0; 370b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands} 371b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 372a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 373a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 374a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// it on the incoming phi values yields the same result for every value. If so 375a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// returns the common value, otherwise returns null. 376a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 3771845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 3781845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 3790312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 3800312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 3810312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 3820312a93693abc2eb682b2b101c889959888fd883Duncan Sands 383a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI; 384a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (isa<PHINode>(LHS)) { 385a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(LHS); 3861845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 3871845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 3881845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 389a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } else { 390a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 391a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PI = cast<PHINode>(RHS); 3921845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if LHS and the phi may be mutually interdependent due to a loop. 3931845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(LHS, PI, DT)) 3941845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 395a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 396a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 397a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 398a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 399a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 400552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 401ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 402552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 403a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *V = PI == LHS ? 4041845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, Incoming, RHS, TD, DT, MaxRecurse) : 4051845009290e4d804ad377927bd8a08cca3036adcDuncan Sands SimplifyBinOp(Opcode, LHS, Incoming, TD, DT, MaxRecurse); 406a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 407a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 408a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 409a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 410a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 411a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 412a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 413a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 414a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 415a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 416a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 417a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// try to simplify the comparison by seeing whether comparing with all of the 418a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// incoming phi values yields the same result every time. If so returns the 419a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands/// common result, otherwise returns null. 420a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 4211845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 4221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 4230312a93693abc2eb682b2b101c889959888fd883Duncan Sands // Recursion is always used, so bail out at once if we already hit the limit. 4240312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (!MaxRecurse--) 4250312a93693abc2eb682b2b101c889959888fd883Duncan Sands return 0; 4260312a93693abc2eb682b2b101c889959888fd883Duncan Sands 427a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Make sure the phi is on the LHS. 428a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!isa<PHINode>(LHS)) { 429a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands std::swap(LHS, RHS); 430a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Pred = CmpInst::getSwappedPredicate(Pred); 431a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 432a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 433a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands PHINode *PI = cast<PHINode>(LHS); 434a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 4351845009290e4d804ad377927bd8a08cca3036adcDuncan Sands // Bail out if RHS and the phi may be mutually interdependent due to a loop. 4361845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (!ValueDominatesPHI(RHS, PI, DT)) 4371845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return 0; 4381845009290e4d804ad377927bd8a08cca3036adcDuncan Sands 439a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // Evaluate the BinOp on the incoming phi values. 440a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands Value *CommonValue = 0; 441a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 442552008946530e01efdad15044e1f621883d14a3aDuncan Sands Value *Incoming = PI->getIncomingValue(i); 443ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 444552008946530e01efdad15044e1f621883d14a3aDuncan Sands if (Incoming == PI) continue; 4451845009290e4d804ad377927bd8a08cca3036adcDuncan Sands Value *V = SimplifyCmpInst(Pred, Incoming, RHS, TD, DT, MaxRecurse); 446a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation failed to simplify, or simplified to a different value 447a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // to previously, then give up. 448a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands if (!V || (CommonValue && V != CommonValue)) 449a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return 0; 450a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands CommonValue = V; 451a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands } 452a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 453a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return CommonValue; 454a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 455a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 4568aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 457d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 458ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 459ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT, 460ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 461d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 462d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 463d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 4648aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), 4658aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Ops, 2, TD); 4668aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 46712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 4688aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner // Canonicalize the constant to the RHS. 4698aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner std::swap(Op0, Op1); 4708aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner } 47112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 472fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + undef -> undef 473fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (isa<UndefValue>(Op1)) 474fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op1; 47512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 476fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + 0 -> X 477fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 478fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 479fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 480fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + (Y - X) -> Y 481fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y - X) + X -> Y 482ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands // Eg: X + -X -> 0 483fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Value *Y = 0; 484fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 485fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 486fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Y; 487fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 488fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X + ~X -> -1 since ~X = -X-1 489fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op0, m_Not(m_Specific(Op1))) || 490fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op1, m_Not(m_Specific(Op0)))) 491fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getAllOnesValue(Op0->getType()); 49287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 49382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 add -> xor. 49475d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 49507f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 49607f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 49782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 498566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 499566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, TD, DT, 500566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 501566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 502566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 5033421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Mul distributes over Add. Try some generic simplifications based on this. 5043421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Add, Op0, Op1, Instruction::Mul, 5053421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 5063421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 5073421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 50887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Add over selects and phi nodes is pointless, so don't bother. 50987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A + select(cond, B, C)" means evaluating 51087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 51187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 51287689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 51387689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 51487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 51587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 51687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands 5178aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner return 0; 5188aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner} 5198aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner 520ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 521ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 522ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 523ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 524ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 525fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// SimplifySubInst - Given operands for a Sub, see if we can 526fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands/// fold the result. If not, this returns null. 527ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sandsstatic Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 5283421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands const TargetData *TD, const DominatorTree *DT, 529ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands unsigned MaxRecurse) { 530fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) 531fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 532fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Constant *Ops[] = { CLHS, CRHS }; 533fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 534fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Ops, 2, TD); 535fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands } 536fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 537fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - undef -> undef 538fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // undef - X -> undef 539fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1)) 540fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return UndefValue::get(Op0->getType()); 541fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 542fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - 0 -> X 543fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op1, m_Zero())) 544fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Op0; 545fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 546fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // X - X -> 0 547fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (Op0 == Op1) 548fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return Constant::getNullValue(Op0->getType()); 549fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 550fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (X + Y) - Y -> X 551fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // (Y + X) - Y -> X 552fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Value *X = 0; 553fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands if (match(Op0, m_Add(m_Value(X), m_Specific(Op1))) || 554fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands match(Op0, m_Add(m_Specific(Op1), m_Value(X)))) 555fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return X; 556fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 55782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 sub -> xor. 55875d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 55907f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyXorInst(Op0, Op1, TD, DT, MaxRecurse-1)) 56007f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 56182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 5623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Mul distributes over Sub. Try some generic simplifications based on this. 5633421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Sub, Op0, Op1, Instruction::Mul, 5643421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 5653421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 5663421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 567fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading Sub over selects and phi nodes is pointless, so don't bother. 568fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // Threading over the select in "A - select(cond, B, C)" means evaluating 569fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 570fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 571fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 572fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // have been simplified to the common value of B and C already. Analysing 573fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 574fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands // for threading over phi nodes. 575fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 576fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands return 0; 577fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands} 578fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands 579ee9a2e322af96accc9e55ed6373c0057453714b1Duncan SandsValue *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 580ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands const TargetData *TD, const DominatorTree *DT) { 581ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, TD, DT, RecursionLimit); 582ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands} 583ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands 58482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands/// SimplifyMulInst - Given operands for a Mul, see if we can 58582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands/// fold the result. If not, this returns null. 58682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sandsstatic Value *SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 58782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 58882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 58982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 59082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 59182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 59282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Ops, 2, TD); 59382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands } 59482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 59582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Canonicalize the constant to the RHS. 59682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands std::swap(Op0, Op1); 59782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands } 59882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 59982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * undef -> 0 60082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<UndefValue>(Op1)) 60182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Constant::getNullValue(Op0->getType()); 60282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 60382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * 0 -> 0 60482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (match(Op1, m_Zero())) 60582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Op1; 60682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 60782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // X * 1 -> X 60882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (match(Op1, m_One())) 60982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return Op0; 61082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 61182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands /// i1 mul -> and. 61275d289ed6201e82718343d7a36d2a2fa082f6217Duncan Sands if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 61307f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands if (Value *V = SimplifyAndInst(Op0, Op1, TD, DT, MaxRecurse-1)) 61407f30fbd734069b80b90c6aeea0ae645ce3880c0Duncan Sands return V; 61582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 61682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Try some generic simplifications for associative operations. 61782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, TD, DT, 61882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 61982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 62082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 62182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // Mul distributes over Add. Try some generic simplifications based on this. 62282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 62382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands TD, DT, MaxRecurse)) 62482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 62582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 62682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // If the operation is with the result of a select instruction, check whether 62782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // operating on either branch of the select always yields the same value. 62882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 62982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, TD, DT, 63082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 63182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 63282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 63382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // If the operation is with the result of a phi instruction, check whether 63482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands // operating on all incoming values of the phi always yields the same value. 63582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 63682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, TD, DT, 63782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands MaxRecurse)) 63882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return V; 63982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 64082fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return 0; 64182fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands} 64282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 64382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan SandsValue *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, 64482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands const DominatorTree *DT) { 64582fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands return ::SimplifyMulInst(Op0, Op1, TD, DT, RecursionLimit); 64682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands} 64782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands 6488aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 6498aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner/// fold the result. If not, this returns null. 650a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 6511845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 6528aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 6538aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 6548aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 655d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 656d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 657d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 65812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 659d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 660d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 661d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 66212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 663d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & undef -> 0 664d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 665d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 66612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 667d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X & X = X 668d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 669d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 67012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 6712b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & 0 = 0 6722b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 673d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 67412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 6752b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X & -1 = X 6762b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 6772b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 67812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 679d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & ~A = ~A & A = 0 680e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 68170ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 68270ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 683d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getNullValue(Op0->getType()); 68412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 685d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A | ?) & A = A 686d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 687d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 688d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 68912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 690d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A & (A | ?) = A 691d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 692d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 693d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 69412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 695566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 696566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, TD, DT, 697566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 698566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 6996844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 7003421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Or. Try some generic simplifications based on this. 7013421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 7023421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 7033421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 7043421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 7053421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Xor. Try some generic simplifications based on this. 7063421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 7073421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 7083421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 7093421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 7103421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Or distributes over And. Try some generic simplifications based on this. 7113421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::And, Op0, Op1, Instruction::Or, 7123421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 7133421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 7143421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 715b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 716b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 7170312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 7181845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, TD, DT, 7190312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 720a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 721a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 722a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 723a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 7240312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 7251845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, TD, DT, 7260312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 727b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 728b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 729d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 730d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 7319f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 7321845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, 7331845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 7341845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyAndInst(Op0, Op1, TD, DT, RecursionLimit); 735a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 736a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 737d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 7389f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner/// fold the result. If not, this returns null. 739a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 7401845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 741d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 742d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 743d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 744d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 745d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Ops, 2, TD); 746d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 74712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 748d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // Canonicalize the constant to the RHS. 749d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(Op0, Op1); 750d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 75112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 752d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | undef -> -1 753d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (isa<UndefValue>(Op1)) 754d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 75512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 756d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // X | X = X 757d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Op0 == Op1) 758d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 759d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 7602b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | 0 = X 7612b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 762d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 76312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 7642b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // X | -1 = -1 7652b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_AllOnes())) 7662b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op1; 76712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 768d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | ~A = ~A | A = -1 769e89ada98a6ed803ca865843678c4dd4cf77b14eeChandler Carruth Value *A = 0, *B = 0; 77070ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 77170ce6d0819ffd5822bb176fffe94bcf29a1deda4Chris Lattner (match(Op1, m_Not(m_Value(A))) && A == Op0)) 772d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 77312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 774d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // (A & ?) | A = A 775d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(B))) && 776d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op1 || B == Op1)) 777d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op1; 77812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 779d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // A | (A & ?) = A 780d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (match(Op1, m_And(m_Value(A), m_Value(B))) && 781d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner (A == Op0 || B == Op0)) 782d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return Op0; 78312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 784566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 785566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, TD, DT, 786566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 787566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 7886844c8ea5a67e551be7106d6b7b9e1a64eecbe51Benjamin Kramer 7893421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // Or distributes over And. Try some generic simplifications based on this. 7903421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, 7913421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 7923421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 7933421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 7943421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Or. Try some generic simplifications based on this. 7953421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Or, Op0, Op1, Instruction::And, 7963421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 7973421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 7983421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 799b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 800b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 8010312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 8021845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, TD, DT, 8030312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 804a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 805a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 806a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 807a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 8080312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 8091845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, TD, DT, 8100312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 811b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 812b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 8139f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 8149f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 8159f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 8161845009290e4d804ad377927bd8a08cca3036adcDuncan SandsValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, 8171845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const DominatorTree *DT) { 8181845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyOrInst(Op0, Op1, TD, DT, RecursionLimit); 819a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 820d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 8212b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// SimplifyXorInst - Given operands for a Xor, see if we can 8222b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands/// fold the result. If not, this returns null. 8232b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sandsstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 8242b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT, unsigned MaxRecurse) { 8252b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 8262b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 8272b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Constant *Ops[] = { CLHS, CRHS }; 8282b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 8292b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Ops, 2, TD); 8302b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 8312b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8322b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // Canonicalize the constant to the RHS. 8332b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands std::swap(Op0, Op1); 8342b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands } 8352b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8362b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ undef -> undef 8372b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (isa<UndefValue>(Op1)) 838f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Op1; 8392b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8402b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ 0 = A 8412b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (match(Op1, m_Zero())) 8422b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Op0; 8432b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8442b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ A = 0 8452b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if (Op0 == Op1) 8462b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getNullValue(Op0->getType()); 8472b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8482b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands // A ^ ~A = ~A ^ A = -1 849566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands Value *A = 0; 8502b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands if ((match(Op0, m_Not(m_Value(A))) && A == Op1) || 8512b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands (match(Op1, m_Not(m_Value(A))) && A == Op0)) 8522b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return Constant::getAllOnesValue(Op0->getType()); 8532b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 854566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // Try some generic simplifications for associative operations. 855566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, TD, DT, 856566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 857566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 8582b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8593421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands // And distributes over Xor. Try some generic simplifications based on this. 8603421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands if (Value *V = FactorizeBinOp(Instruction::Xor, Op0, Op1, Instruction::And, 8613421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands TD, DT, MaxRecurse)) 8623421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands return V; 8633421d908539cc489d2b1dac67d8cbc07160b01dbDuncan Sands 86487689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading Xor over selects and phi nodes is pointless, so don't bother. 86587689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // Threading over the select in "A ^ select(cond, B, C)" means evaluating 86687689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 86787689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // only if B and C are equal. If B and C are equal then (since we assume 86887689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // that operands have already been simplified) "select(cond, B, C)" should 86987689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // have been simplified to the common value of B and C already. Analysing 87087689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 87187689cfc54993959adb20b89a56bc58aad18ca56Duncan Sands // for threading over phi nodes. 8722b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8732b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return 0; 8742b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 8752b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 8762b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan SandsValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, 8772b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands const DominatorTree *DT) { 8782b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands return ::SimplifyXorInst(Op0, Op1, TD, DT, RecursionLimit); 8792b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands} 8802b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands 881210c5d4880b525e064088b6fec713260128c16ebChris Lattnerstatic const Type *GetCompareTy(Value *Op) { 882210c5d4880b525e064088b6fec713260128c16ebChris Lattner return CmpInst::makeCmpResultType(Op->getType()); 883210c5d4880b525e064088b6fec713260128c16ebChris Lattner} 884210c5d4880b525e064088b6fec713260128c16ebChris Lattner 8859dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 8869dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 887a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 8881845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 8891845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 8909f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 8919dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 89212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 893d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 8948f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 8958f73deaa8732a556046bf4ac6207be55972e3b74Chris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 896d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner 897d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 898d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 899d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 900d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 90112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 902210c5d4880b525e064088b6fec713260128c16ebChris Lattner // ITy - This is the return type of the compare we're considering. 903210c5d4880b525e064088b6fec713260128c16ebChris Lattner const Type *ITy = GetCompareTy(LHS); 90412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 905210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp X, X -> true/false 906c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 907c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner // because X could be 0. 908c8e14b3d37b80abb6adb4b831af0452d9ecbf2b2Chris Lattner if (LHS == RHS || isa<UndefValue>(RHS)) 909210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 91012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 911210c5d4880b525e064088b6fec713260128c16ebChris Lattner // icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value 912210c5d4880b525e064088b6fec713260128c16ebChris Lattner // addresses never equal each other! We already know that Op0 != Op1. 91312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands if ((isa<GlobalValue>(LHS) || isa<AllocaInst>(LHS) || 914210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(LHS)) && 91512a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) || 916210c5d4880b525e064088b6fec713260128c16ebChris Lattner isa<ConstantPointerNull>(RHS))) 917210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred)); 91812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 919210c5d4880b525e064088b6fec713260128c16ebChris Lattner // See if we are doing a comparison with a constant. 920210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 921210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If we have an icmp le or icmp ge instruction, turn it into the 922210c5d4880b525e064088b6fec713260128c16ebChris Lattner // appropriate icmp lt or icmp gt instruction. This allows us to rely on 923210c5d4880b525e064088b6fec713260128c16ebChris Lattner // them being folded in the code below. 924210c5d4880b525e064088b6fec713260128c16ebChris Lattner switch (Pred) { 925210c5d4880b525e064088b6fec713260128c16ebChris Lattner default: break; 926210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_ULE: 927210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(false)) // A <=u MAX -> TRUE 928210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 929210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 930210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SLE: 931210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMaxValue(true)) // A <=s MAX -> TRUE 932210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 933210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 934210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_UGE: 935210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(false)) // A >=u MIN -> TRUE 936210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 937210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 938210c5d4880b525e064088b6fec713260128c16ebChris Lattner case ICmpInst::ICMP_SGE: 939210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CI->isMinValue(true)) // A >=s MIN -> TRUE 940210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CI->getContext()); 941210c5d4880b525e064088b6fec713260128c16ebChris Lattner break; 942210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 943210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 9441ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 9451ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // If the comparison is with the result of a select instruction, check whether 9461ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands // comparing with either branch of the select always yields the same value. 9470312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 9480312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 949a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 950a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 951a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 952a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 9530312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 9540312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 9553bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 9561ac7c9979a2d723ff4649ffad58df02732872a5fDuncan Sands 9579dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return 0; 9589dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 9599dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 960a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 9611845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 9621845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 963a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 964a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 9659dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 9669dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. If not, this returns null. 967a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 9681845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 9691845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 9709dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 9719dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 9729dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 973d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 9749dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) 9759dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, TD); 97612a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 977d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner // If we have a constant, make sure it is on the RHS. 978d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner std::swap(LHS, RHS); 979d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 980d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 98112a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 982210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Fold trivial predicates. 983210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_FALSE) 984210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 985210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Pred == FCmpInst::FCMP_TRUE) 986210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 987210c5d4880b525e064088b6fec713260128c16ebChris Lattner 988210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 989210c5d4880b525e064088b6fec713260128c16ebChris Lattner return UndefValue::get(GetCompareTy(LHS)); 990210c5d4880b525e064088b6fec713260128c16ebChris Lattner 991210c5d4880b525e064088b6fec713260128c16ebChris Lattner // fcmp x,x -> true/false. Not all compares are foldable. 992210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (LHS == RHS) { 993210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isTrueWhenEqual(Pred)) 994210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 1); 995210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CmpInst::isFalseWhenEqual(Pred)) 996210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::get(GetCompareTy(LHS), 0); 997210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 99812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 999210c5d4880b525e064088b6fec713260128c16ebChris Lattner // Handle fcmp with constant RHS 1000210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 1001210c5d4880b525e064088b6fec713260128c16ebChris Lattner // If the constant is a nan, see if we can fold the comparison based on it. 1002210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 1003210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (CFP->getValueAPF().isNaN()) { 1004210c5d4880b525e064088b6fec713260128c16ebChris Lattner if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 1005210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getFalse(CFP->getContext()); 1006210c5d4880b525e064088b6fec713260128c16ebChris Lattner assert(FCmpInst::isUnordered(Pred) && 1007210c5d4880b525e064088b6fec713260128c16ebChris Lattner "Comparison must be either ordered or unordered!"); 1008210c5d4880b525e064088b6fec713260128c16ebChris Lattner // True if unordered. 1009210c5d4880b525e064088b6fec713260128c16ebChris Lattner return ConstantInt::getTrue(CFP->getContext()); 1010210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 10116b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // Check whether the constant is an infinity. 10126b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isInfinity()) { 10136b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman if (CFP->getValueAPF().isNegative()) { 10146b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 10156b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OLT: 10166b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and less than negative infinity. 10176b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 10186b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_UGE: 10196b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with or at least negative infinity. 10206b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 10216b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 10226b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 10236b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 10246b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } else { 10256b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman switch (Pred) { 10266b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_OGT: 10276b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // No value is ordered and greater than infinity. 10286b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getFalse(CFP->getContext()); 10296b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman case FCmpInst::FCMP_ULE: 10306b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman // All values are unordered with and at most infinity. 10316b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman return ConstantInt::getTrue(CFP->getContext()); 10326b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman default: 10336b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman break; 10346b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 10356b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 10366b617a7213e159097a7e5c7216ed9b04921de4e1Dan Gohman } 1037210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 1038210c5d4880b525e064088b6fec713260128c16ebChris Lattner } 103912a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 104092826def593df7a422c7b07f09342febce81ddd3Duncan Sands // If the comparison is with the result of a select instruction, check whether 104192826def593df7a422c7b07f09342febce81ddd3Duncan Sands // comparing with either branch of the select always yields the same value. 10420312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 10430312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, TD, DT, MaxRecurse)) 1044a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1045a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1046a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the comparison is with the result of a phi instruction, check whether 1047a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // doing the compare with each incoming phi value yields a common result. 10480312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 10490312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, TD, DT, MaxRecurse)) 10503bbb0cc42b67b4bf2c488285666999963bab0f7eDuncan Sands return V; 105192826def593df7a422c7b07f09342febce81ddd3Duncan Sands 10529f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner return 0; 10539f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner} 10549f3c25aeb3df77a336693308dc0f19a4983c99afChris Lattner 1055a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 10561845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 10571845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1058a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1059a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1060047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 1061047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner/// the result. If not, this returns null. 1062047542669a20505fc7c5f2d93caa5610aa3db2c5Chris LattnerValue *llvm::SimplifySelectInst(Value *CondVal, Value *TrueVal, Value *FalseVal, 10631845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 1064047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select true, X, Y -> X 1065047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select false, X, Y -> Y 1066047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (ConstantInt *CB = dyn_cast<ConstantInt>(CondVal)) 1067047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return CB->getZExtValue() ? TrueVal : FalseVal; 106812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1069047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner // select C, X, X -> X 1070047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (TrueVal == FalseVal) 1071047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 107212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1073047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 1074047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 1075047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 1076047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 1077047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 1078047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner if (isa<Constant>(TrueVal)) 1079047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return TrueVal; 1080047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return FalseVal; 1081047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner } 108212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1083047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner return 0; 1084047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner} 1085047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner 1086c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 1087c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner/// fold the result. If not, this returns null. 1088c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris LattnerValue *llvm::SimplifyGEPInst(Value *const *Ops, unsigned NumOps, 10891845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *) { 109085bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // The type of the GEP pointer operand. 109185bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()); 109285bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands 1093c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // getelementptr P -> P. 1094c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (NumOps == 1) 1095c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 1096c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 109785bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands if (isa<UndefValue>(Ops[0])) { 109885bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands // Compute the (pointer) type returned by the GEP instruction. 109985bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, &Ops[1], 110085bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands NumOps-1); 110185bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 110285bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands return UndefValue::get(GEPTy); 110385bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands } 1104c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1105e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (NumOps == 2) { 1106e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, 0 -> P. 1107c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Ops[1])) 1108c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (C->isZero()) 1109c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return Ops[0]; 1110e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands // getelementptr P, N -> P if P points to a type of zero size. 1111e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands if (TD) { 111285bbff6c94695f07cc1a9765b4d384ed18d2fd7cDuncan Sands const Type *Ty = PtrTy->getElementType(); 1113a63395a30f9227bde826749d3480046301b47332Duncan Sands if (Ty->isSized() && TD->getTypeAllocSize(Ty) == 0) 1114e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands return Ops[0]; 1115e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 1116e60d79faf7ef7bc4847f9e5d067af00b98dced7bDuncan Sands } 111712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1118c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner // Check to see if this is constant foldable. 1119c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner for (unsigned i = 0; i != NumOps; ++i) 1120c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner if (!isa<Constant>(Ops[i])) 1121c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return 0; 112212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1123c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), 1124c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner (Constant *const*)Ops+1, NumOps-1); 1125c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner} 1126c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1127ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 1128ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sandsstatic Value *SimplifyPHINode(PHINode *PN, const DominatorTree *DT) { 1129ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If all of the PHI's incoming values are the same then replace the PHI node 1130ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // with the common value. 1131ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *CommonValue = 0; 1132ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands bool HasUndefInput = false; 1133ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1134ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands Value *Incoming = PN->getIncomingValue(i); 1135ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If the incoming value is the phi node itself, it can safely be skipped. 1136ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (Incoming == PN) continue; 1137ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (isa<UndefValue>(Incoming)) { 1138ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // Remember that we saw an undef value, but otherwise ignore them. 1139ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands HasUndefInput = true; 1140ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands continue; 1141ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 1142ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (CommonValue && Incoming != CommonValue) 1143ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return 0; // Not the same, bail out. 1144ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands CommonValue = Incoming; 1145ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands } 1146ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1147ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If CommonValue is null then all of the incoming values were either undef or 1148ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // equal to the phi node itself. 1149ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (!CommonValue) 1150ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return UndefValue::get(PN->getType()); 1151ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1152ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // If we have a PHI node like phi(X, undef, X), where X is defined by some 1153ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // instruction, we cannot return X as the result of the PHI node unless it 1154ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands // dominates the PHI block. 1155ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands if (HasUndefInput) 1156ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return ValueDominatesPHI(CommonValue, PN, DT) ? CommonValue : 0; 1157ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1158ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands return CommonValue; 1159ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands} 1160ff10341183adf74760e6118a55cbd1debf50f90fDuncan Sands 1161c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner 1162d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner//=== Helper functions for higher up the class hierarchy. 11639dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1164d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 1165d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner/// fold the result. If not, this returns null. 1166a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 11671845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 11681845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 1169d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner switch (Opcode) { 1170ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Add: return SimplifyAddInst(LHS, RHS, /* isNSW */ false, 1171ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands /* isNUW */ false, TD, DT, 1172ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands MaxRecurse); 1173ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands case Instruction::Sub: return SimplifySubInst(LHS, RHS, /* isNSW */ false, 1174ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands /* isNUW */ false, TD, DT, 1175ee9a2e322af96accc9e55ed6373c0057453714b1Duncan Sands MaxRecurse); 117682fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Mul: return SimplifyMulInst(LHS, RHS, TD, DT, MaxRecurse); 117782fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::And: return SimplifyAndInst(LHS, RHS, TD, DT, MaxRecurse); 117882fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Or: return SimplifyOrInst(LHS, RHS, TD, DT, MaxRecurse); 117982fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Xor: return SimplifyXorInst(LHS, RHS, TD, DT, MaxRecurse); 1180d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner default: 1181d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1182d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 1183d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner Constant *COps[] = {CLHS, CRHS}; 1184d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, 2, TD); 1185d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 1186b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1187566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands // If the operation is associative, try some generic simplifications. 1188566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Instruction::isAssociative(Opcode)) 1189566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, TD, DT, 1190566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands MaxRecurse)) 1191566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands return V; 1192566edb04b890cebca8f2eefa37af7371a1e756c9Duncan Sands 1193b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // If the operation is with the result of a select instruction, check whether 1194b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands // operating on either branch of the select always yields the same value. 11950312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 11961845009290e4d804ad377927bd8a08cca3036adcDuncan Sands if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, TD, DT, 11970312a93693abc2eb682b2b101c889959888fd883Duncan Sands MaxRecurse)) 1198a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands return V; 1199a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 1200a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // If the operation is with the result of a phi instruction, check whether 1201a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands // operating on all incoming values of the phi always yields the same value. 12020312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 12030312a93693abc2eb682b2b101c889959888fd883Duncan Sands if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, TD, DT, MaxRecurse)) 1204b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands return V; 1205b2cbdc35ba85c04df15b0e991d9be371691ab08cDuncan Sands 1206d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner return 0; 1207d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner } 1208d06094f0682f2ede03caff4892b1a57469896d48Chris Lattner} 12099dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 121012a86f5b3199e72e6d967781acc76340f5920e46Duncan SandsValue *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 12111845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 12121845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyBinOp(Opcode, LHS, RHS, TD, DT, RecursionLimit); 1213a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1214a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands 12159dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 12169dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner/// fold the result. 1217a74a58c83be492b7d5b7383656f049909394cff4Duncan Sandsstatic Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 12181845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT, 12191845009290e4d804ad377927bd8a08cca3036adcDuncan Sands unsigned MaxRecurse) { 12209dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 12211845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyICmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 12221845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return SimplifyFCmpInst(Predicate, LHS, RHS, TD, DT, MaxRecurse); 12239dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner} 12249dbb42944c4d7caddab21016b24cca31019a3fafChris Lattner 1225a74a58c83be492b7d5b7383656f049909394cff4Duncan SandsValue *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 12261845009290e4d804ad377927bd8a08cca3036adcDuncan Sands const TargetData *TD, const DominatorTree *DT) { 12271845009290e4d804ad377927bd8a08cca3036adcDuncan Sands return ::SimplifyCmpInst(Predicate, LHS, RHS, TD, DT, RecursionLimit); 1228a74a58c83be492b7d5b7383656f049909394cff4Duncan Sands} 1229e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 1230e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// SimplifyInstruction - See if we can compute a simplified version of this 1231e34537856a544c83513e390ac9552a8bc3823346Chris Lattner/// instruction. If not, this returns null. 1232eff0581583ef10e2872e9baf537a04b67d992101Duncan SandsValue *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, 1233eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 1234d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Value *Result; 1235d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1236e34537856a544c83513e390ac9552a8bc3823346Chris Lattner switch (I->getOpcode()) { 1237e34537856a544c83513e390ac9552a8bc3823346Chris Lattner default: 1238d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = ConstantFoldInstruction(I, TD); 1239d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 12408aee8efc0c2e387faa7dae39fdf613a22889b566Chris Lattner case Instruction::Add: 1241d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 1242d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1243d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1244d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands TD, DT); 1245d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1246fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands case Instruction::Sub: 1247fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 1248fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoSignedWrap(), 1249fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 1250fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands TD, DT); 1251fea3b218d61708ea3577f4ef14c8f7677a94db95Duncan Sands break; 125282fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands case Instruction::Mul: 125382fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, DT); 125482fdab335881cd90f8f7ab3ad1f1ca0bb3ee886aDuncan Sands break; 1255e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::And: 1256d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), TD, DT); 1257d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1258e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::Or: 1259d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), TD, DT); 1260d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 12612b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands case Instruction::Xor: 12622b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), TD, DT); 12632b749870d0488c3b049edf5d0c8875f56f5b1bedDuncan Sands break; 1264e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::ICmp: 1265d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 1266d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1267d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1268e34537856a544c83513e390ac9552a8bc3823346Chris Lattner case Instruction::FCmp: 1269d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 1270d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(0), I->getOperand(1), TD, DT); 1271d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1272047542669a20505fc7c5f2d93caa5610aa3db2c5Chris Lattner case Instruction::Select: 1273d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 1274d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands I->getOperand(2), TD, DT); 1275d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1276c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner case Instruction::GetElementPtr: { 1277c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 1278d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyGEPInst(&Ops[0], Ops.size(), TD, DT); 1279d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1280c514c1f5218b8fe7499a0b9a4737860344cf4c43Chris Lattner } 1281cd6636c737a82949ad13db2d0d918af6424fb78bDuncan Sands case Instruction::PHI: 1282d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands Result = SimplifyPHINode(cast<PHINode>(I), DT); 1283d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands break; 1284e34537856a544c83513e390ac9552a8bc3823346Chris Lattner } 1285d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands 1286d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// If called on unreachable code, the above logic may report that the 1287d261dc650a01ac5c51ab10f97f1e35aa6a770721Duncan Sands /// instruction simplified to itself. Make life easier for users by 1288f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands /// detecting that case here, returning a safe value instead. 1289f8b1a5ea9602bb65a5cf59d3d34f2851a08cdc3eDuncan Sands return Result == I ? UndefValue::get(I->getType()) : Result; 1290e34537856a544c83513e390ac9552a8bc3823346Chris Lattner} 1291e34537856a544c83513e390ac9552a8bc3823346Chris Lattner 129240d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then 129340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// delete the From instruction. In addition to a basic RAUW, this does a 129440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// recursive simplification of the newly formed instructions. This catches 129540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// things where one simplification exposes other opportunities. This only 129640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// simplifies and deletes scalar operations, it does not change the CFG. 129740d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner/// 129840d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnervoid llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, 1299eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const TargetData *TD, 1300eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands const DominatorTree *DT) { 130140d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); 130212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1303d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that 1304d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // we can know if it gets deleted out from under us or replaced in a 1305d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // recursive simplification. 130640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner WeakVH FromHandle(From); 1307d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner WeakVH ToHandle(To); 130812a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 130940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner while (!From->use_empty()) { 131040d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner // Update the instruction to use the new value. 1311d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Use &TheUse = From->use_begin().getUse(); 1312d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Instruction *User = cast<Instruction>(TheUse.getUser()); 1313d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner TheUse = To; 1314d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner 1315d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Check to see if the instruction can be folded due to the operand 1316d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // replacement. For example changing (or X, Y) into (or X, -1) can replace 1317d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // the 'or' with -1. 1318d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner Value *SimplifiedVal; 1319d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner { 1320d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Sanity check to make sure 'User' doesn't dangle across 1321d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // SimplifyInstruction. 1322d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner AssertingVH<> UserHandle(User); 132312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1324eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands SimplifiedVal = SimplifyInstruction(User, TD, DT); 1325d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (SimplifiedVal == 0) continue; 132640d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 132712a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1328d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // Recursively simplify this user to the new value. 1329eff0581583ef10e2872e9baf537a04b67d992101Duncan Sands ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, DT); 1330d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From = dyn_cast_or_null<Instruction>((Value*)FromHandle); 1331d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner To = ToHandle; 133212a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1333d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner assert(ToHandle && "To value deleted by recursive simplification?"); 133412a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1335d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If the recursive simplification ended up revisiting and deleting 1336d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // 'From' then we're done. 1337d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner if (From == 0) 1338d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner return; 133940d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner } 134012a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 1341d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner // If 'From' has value handles referring to it, do a real RAUW to update them. 1342d2bfe54b0a9f28c021d4f0790bdb5224d5579447Chris Lattner From->replaceAllUsesWith(To); 134312a86f5b3199e72e6d967781acc76340f5920e46Duncan Sands 134440d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner From->eraseFromParent(); 134540d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattner} 1346