InstructionSimplify.cpp revision cd81d94322a39503e4a3e87b6ee03d4fcb3465fb
1753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner//===- InstructionSimplify.cpp - Fold instruction operands ----------------===// 2753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// 3753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// The LLVM Compiler Infrastructure 4753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// 5753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// This file is distributed under the University of Illinois Open Source 6753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// License. See LICENSE.TXT for details. 7753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// 8753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner//===----------------------------------------------------------------------===// 9753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// 10753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// This file implements routines for folding instructions into simpler forms 11753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// that do not require creating new instructions. This does constant folding 12753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// ("add i32 1, 1" -> "2") but can also handle non-constant operands, either 13753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// returning a constant ("and i32 %x, 0" -> "0") or an already existing value 14753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// ("and i32 %x, %x" -> "%x"). All operands are assumed to have already been 1563f932ca3c91ea8ac5b592158f5e8ef7de550547Meador Inge// simplified: This is usually true and assuming it simplifies the logic (if 16753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner// they have not been simplified then results are correct but maybe suboptimal). 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth//===----------------------------------------------------------------------===// 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2027ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher#include "llvm/Analysis/InstructionSimplify.h" 21687140c818ba4b896329a83324714140b6580ef8Chris Lattner#include "llvm/ADT/SetVector.h" 22753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner#include "llvm/ADT/Statistic.h" 238ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman#include "llvm/Analysis/ConstantFolding.h" 24753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner#include "llvm/Analysis/MemoryBuiltins.h" 25dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Analysis/ValueTracking.h" 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/IR/ConstantRange.h" 2763f932ca3c91ea8ac5b592158f5e8ef7de550547Meador Inge#include "llvm/IR/DataLayout.h" 2863f932ca3c91ea8ac5b592158f5e8ef7de550547Meador Inge#include "llvm/IR/Dominators.h" 29753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner#include "llvm/IR/GetElementPtrTypeIterator.h" 30753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner#include "llvm/IR/GlobalAlias.h" 31db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner#include "llvm/IR/Operator.h" 32db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner#include "llvm/IR/PatternMatch.h" 33753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner#include "llvm/IR/ValueHandle.h" 34753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerusing namespace llvm; 35753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerusing namespace llvm::PatternMatch; 36753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 37753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner#define DEBUG_TYPE "instsimplify" 38753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 39ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohmanenum { RecursionLimit = 3 }; 40ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman 41ce52bc53538df8e5412ec507f2da3661c991baf1Dan GohmanSTATISTIC(NumExpand, "Number of expansions"); 42ce52bc53538df8e5412ec507f2da3661c991baf1Dan GohmanSTATISTIC(NumReassoc, "Number of reassociations"); 43ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman 44ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohmanstruct Query { 45ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman const DataLayout *DL; 46ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman const TargetLibraryInfo *TLI; 47ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman const DominatorTree *DT; 48ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman 49ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman Query(const DataLayout *DL, const TargetLibraryInfo *tli, 50ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman const DominatorTree *dt) : DL(DL), TLI(tli), DT(dt) {} 51ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman}; 52ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman 53ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohmanstatic Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned); 54ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohmanstatic Value *SimplifyBinOp(unsigned, Value *, Value *, const Query &, 55ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman unsigned); 56ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohmanstatic Value *SimplifyCmpInst(unsigned, Value *, Value *, const Query &, 57ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman unsigned); 58ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohmanstatic Value *SimplifyOrInst(Value *, Value *, const Query &, unsigned); 59753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *SimplifyXorInst(Value *, Value *, const Query &, unsigned); 60753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *SimplifyTruncInst(Value *, Type *, const Query &, unsigned); 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// getFalse - For a boolean type, or a vector of boolean type, return false, or 63753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// a vector with every element false, as appropriate for the type. 64753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Constant *getFalse(Type *Ty) { 65753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner assert(Ty->getScalarType()->isIntegerTy(1) && 66753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner "Expected i1 type or a vector of i1!"); 6700e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return Constant::getNullValue(Ty); 68753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 69753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 70753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// getTrue - For a boolean type, or a vector of boolean type, return true, or 7100e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach/// a vector with every element true, as appropriate for the type. 72753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Constant *getTrue(Type *Ty) { 73753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner assert(Ty->getScalarType()->isIntegerTy(1) && 74bcda85c74304ffada586a9c58ce9bcff93b69a86Gabor Greif "Expected i1 type or a vector of i1!"); 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Constant::getAllOnesValue(Ty); 7600e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach} 77753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 78753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"? 79753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS, 80753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *RHS) { 819441ad0b6e02ee9558168b37a9620ef1afe79388Michael Liao CmpInst *Cmp = dyn_cast<CmpInst>(V); 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!Cmp) 8300e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return false; 84753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner CmpInst::Predicate CPred = Cmp->getPredicate(); 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1); 8600e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (CPred == Pred && CLHS == LHS && CRHS == RHS) 87753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return true; 8820adc9dc4650313f017b27d9818eb2176238113dMon P Wang return CPred == CmpInst::getSwappedPredicate(Pred) && CLHS == RHS && 89bcda85c74304ffada586a9c58ce9bcff93b69a86Gabor Greif CRHS == LHS; 904ec2258ffb495d7ce00177e447740ef1123a27dbGabor Greif} 91bcda85c74304ffada586a9c58ce9bcff93b69a86Gabor Greif 9220adc9dc4650313f017b27d9818eb2176238113dMon P Wang/// ValueDominatesPHI - Does the given value dominate the specified phi node? 93db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattnerstatic bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { 9420adc9dc4650313f017b27d9818eb2176238113dMon P Wang Instruction *I = dyn_cast<Instruction>(V); 9520adc9dc4650313f017b27d9818eb2176238113dMon P Wang if (!I) 9600e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach // Arguments and constants dominate all instructions. 97753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return true; 98753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 99753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If we are processing instructions (and/or basic blocks) that have not been 100753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // fully added to a function, the parent nodes may still be null. Simply 101753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // return the conservative answer in these cases. 102753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!I->getParent() || !P->getParent() || !I->getParent()->getParent()) 103cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif return false; 104dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 105cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif // If we have a DominatorTree then do a precise test. 106db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (DT) { 107753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!DT->isReachableFromEntry(P->getParent())) 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 109753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!DT->isReachableFromEntry(I->getParent())) 110753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return false; 111ce52bc53538df8e5412ec507f2da3661c991baf1Dan Gohman return DT->dominates(I, P); 11200e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach } 11320adc9dc4650313f017b27d9818eb2176238113dMon P Wang 11420adc9dc4650313f017b27d9818eb2176238113dMon P Wang // Otherwise, if the instruction is in the entry block, and is not an invoke, 11520adc9dc4650313f017b27d9818eb2176238113dMon P Wang // then it obviously dominates all phi nodes. 116b998913ff4aa58c3c342e167c785029cb331078eDan Gohman if (I->getParent() == &I->getParent()->getParent()->getEntryBlock() && 117b998913ff4aa58c3c342e167c785029cb331078eDan Gohman !isa<InvokeInst>(I)) 118b998913ff4aa58c3c342e167c785029cb331078eDan Gohman return true; 119b998913ff4aa58c3c342e167c785029cb331078eDan Gohman 120b998913ff4aa58c3c342e167c785029cb331078eDan Gohman return false; 1215e01f80bf85b9a68352d4c146caa9ddcf6af6dcfNick Lewycky} 122b998913ff4aa58c3c342e167c785029cb331078eDan Gohman 123b998913ff4aa58c3c342e167c785029cb331078eDan Gohman/// ExpandBinOp - Simplify "A op (B op' C)" by distributing op over op', turning 1245e01f80bf85b9a68352d4c146caa9ddcf6af6dcfNick Lewycky/// it into "(A op B) op' (A op C)". Here "op" is given by Opcode and "op'" is 125b998913ff4aa58c3c342e167c785029cb331078eDan Gohman/// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS. 126b998913ff4aa58c3c342e167c785029cb331078eDan Gohman/// Also performs the transform "(A op' B) op C" -> "(A op C) op' (B op C)". 1275e01f80bf85b9a68352d4c146caa9ddcf6af6dcfNick Lewycky/// Returns the simplified value, or null if no simplification was performed. 128b998913ff4aa58c3c342e167c785029cb331078eDan Gohmanstatic Value *ExpandBinOp(unsigned Opcode, Value *LHS, Value *RHS, 129b998913ff4aa58c3c342e167c785029cb331078eDan Gohman unsigned OpcToExpand, const Query &Q, 130b998913ff4aa58c3c342e167c785029cb331078eDan Gohman unsigned MaxRecurse) { 13120adc9dc4650313f017b27d9818eb2176238113dMon P Wang Instruction::BinaryOps OpcodeToExpand = (Instruction::BinaryOps)OpcToExpand; 132753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Recursion is always used, so bail out at once if we already hit the limit. 133753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!MaxRecurse--) 13400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return nullptr; 135753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 136753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Check whether the expression has the form "(A op' B) op C". 137753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS)) 138753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Op0->getOpcode() == OpcodeToExpand) { 13900e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach // It does! Try turning it into "(A op C) op' (B op C)". 1409c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS; 1419c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif // Do "A op C" and "B op C" both simplify? 14259f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman if (Value *L = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) 14359f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman if (Value *R = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { 144b998913ff4aa58c3c342e167c785029cb331078eDan Gohman // They do! Return "L op' R" if it simplifies or is already available. 145b998913ff4aa58c3c342e167c785029cb331078eDan Gohman // If "L op' R" equals "A op' B" then "L op' R" is just the LHS. 14659f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman if ((L == A && R == B) || (Instruction::isCommutative(OpcodeToExpand) 14759f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman && L == B && R == A)) { 148b998913ff4aa58c3c342e167c785029cb331078eDan Gohman ++NumExpand; 149b998913ff4aa58c3c342e167c785029cb331078eDan Gohman return LHS; 150753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 151753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Otherwise return "L op' R" if it simplifies. 152a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { 153753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner ++NumExpand; 154753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 155753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 156753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 158753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 159753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Check whether the expression has the form "A op (B op' C)". 160753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS)) 161753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Op1->getOpcode() == OpcodeToExpand) { 162753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // It does! Try turning it into "(A op B) op' (A op C)". 16300e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1); 164753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Do "A op B" and "A op C" both simplify? 165753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *L = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) 166753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *R = SimplifyBinOp(Opcode, A, C, Q, MaxRecurse)) { 167b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands // They do! Return "L op' R" if it simplifies or is already available. 168dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If "L op' R" equals "B op' C" then "L op' R" is just the RHS. 1699441ad0b6e02ee9558168b37a9620ef1afe79388Michael Liao if ((L == B && R == C) || (Instruction::isCommutative(OpcodeToExpand) 170753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner && L == C && R == B)) { 1719441ad0b6e02ee9558168b37a9620ef1afe79388Michael Liao ++NumExpand; 17200e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return RHS; 173753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 174753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Otherwise return "L op' R" if it simplifies. 175db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (Value *V = SimplifyBinOp(OpcodeToExpand, L, R, Q, MaxRecurse)) { 17600e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach ++NumExpand; 177753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 17855fb9b0fcf89501a0abe74808f4e08e0b3a17207Mon P Wang } 17955fb9b0fcf89501a0abe74808f4e08e0b3a17207Mon P Wang } 18055fb9b0fcf89501a0abe74808f4e08e0b3a17207Mon P Wang } 181753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 182753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 183753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 18400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach 185753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifyAssociativeBinOp - Generic simplifications for associative binary 186753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// operations. Returns the simpler value, or null if none was found. 18759f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedmanstatic Value *SimplifyAssociativeBinOp(unsigned Opc, Value *LHS, Value *RHS, 18859f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman const Query &Q, unsigned MaxRecurse) { 18959f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman Instruction::BinaryOps Opcode = (Instruction::BinaryOps)Opc; 19000e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach assert(Instruction::isAssociative(Opcode) && "Not an associative operation!"); 191753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 192753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Recursion is always used, so bail out at once if we already hit the limit. 193753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!MaxRecurse--) 194753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 195753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 196dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS); 197753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS); 198753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 19900e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach // Transform: "(A op B) op C" ==> "A op (B op C)" if it simplifies completely. 200753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Op0 && Op0->getOpcode() == Opcode) { 201753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *A = Op0->getOperand(0); 202753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *B = Op0->getOperand(1); 203753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *C = RHS; 2048e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 205753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Does "B op C" simplify? 206753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = SimplifyBinOp(Opcode, B, C, Q, MaxRecurse)) { 207753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // It does! Return "A op V" if it simplifies or is already available. 208753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If V equals B then "A op V" is just the LHS. 209753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (V == B) return LHS; 210753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Otherwise return "A op V" if it simplifies. 211753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *W = SimplifyBinOp(Opcode, A, V, Q, MaxRecurse)) { 212753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner ++NumReassoc; 213753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return W; 21400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach } 215753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 216753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 217cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif 218753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Transform: "A op (B op C)" ==> "(A op B) op C" if it simplifies completely. 219753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Op1 && Op1->getOpcode() == Opcode) { 220753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *A = LHS; 221753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *B = Op1->getOperand(0); 222753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *C = Op1->getOperand(1); 223753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 224753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Does "A op B" simplify? 2256eff75104e660bae5b28963190a6940eeecb7484Chris Lattner if (Value *V = SimplifyBinOp(Opcode, A, B, Q, MaxRecurse)) { 2266eff75104e660bae5b28963190a6940eeecb7484Chris Lattner // It does! Return "V op C" if it simplifies or is already available. 227753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If V equals B then "V op C" is just the RHS. 228753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (V == B) return RHS; 229753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Otherwise return "V op C" if it simplifies. 230753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *W = SimplifyBinOp(Opcode, V, C, Q, MaxRecurse)) { 231753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner ++NumReassoc; 232753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return W; 233753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 234753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 23500e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach } 2366eff75104e660bae5b28963190a6940eeecb7484Chris Lattner 2376eff75104e660bae5b28963190a6940eeecb7484Chris Lattner // The remaining transforms require commutativity as well as associativity. 238dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Instruction::isCommutative(Opcode)) 239753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 240753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 241753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Transform: "(A op B) op C" ==> "(C op A) op B" if it simplifies completely. 242753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Op0 && Op0->getOpcode() == Opcode) { 243753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *A = Op0->getOperand(0); 244753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *B = Op0->getOperand(1); 245753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *C = RHS; 246551754c4958086cc6910da7c950f2875e212f5cfEric Christopher 247753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Does "C op A" simplify? 2485fdd6c8793462549e3593890ec61573da06e3346Jay Foad if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { 2495fdd6c8793462549e3593890ec61573da06e3346Jay Foad // It does! Return "V op B" if it simplifies or is already available. 2505fdd6c8793462549e3593890ec61573da06e3346Jay Foad // If V equals A then "V op B" is just the LHS. 251eb9a85f09e18b3fe88499710404b38d3a9128f62Benjamin Kramer if (V == A) return LHS; 252753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Otherwise return "V op B" if it simplifies. 253753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *W = SimplifyBinOp(Opcode, V, B, Q, MaxRecurse)) { 254753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner ++NumReassoc; 255753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return W; 256753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 257753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 258753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 259753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 260551754c4958086cc6910da7c950f2875e212f5cfEric Christopher // Transform: "A op (B op C)" ==> "B op (C op A)" if it simplifies completely. 261753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Op1 && Op1->getOpcode() == Opcode) { 262551754c4958086cc6910da7c950f2875e212f5cfEric Christopher Value *A = LHS; 263551754c4958086cc6910da7c950f2875e212f5cfEric Christopher Value *B = Op1->getOperand(0); 264551754c4958086cc6910da7c950f2875e212f5cfEric Christopher Value *C = Op1->getOperand(1); 265551754c4958086cc6910da7c950f2875e212f5cfEric Christopher 266753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Does "C op A" simplify? 267753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = SimplifyBinOp(Opcode, C, A, Q, MaxRecurse)) { 268753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // It does! Return "B op V" if it simplifies or is already available. 269753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If V equals C then "B op V" is just the RHS. 270753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (V == C) return RHS; 271c310fcc909c21c94d1e5b05a97763911568a3ed8Gabor Greif // Otherwise return "B op V" if it simplifies. 272753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *W = SimplifyBinOp(Opcode, B, V, Q, MaxRecurse)) { 273753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner ++NumReassoc; 27400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return W; 275753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 276753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 277415326b4edcc967dfb03c5ab41923b195e7c3cb1Eric Christopher } 2789e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return nullptr; 2809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes} 281dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 282415326b4edcc967dfb03c5ab41923b195e7c3cb1Eric Christopher/// ThreadBinOpOverSelect - In the case of a binary operation with a select 2838ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman/// instruction as an operand, try to simplify the binop by seeing whether 2848ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman/// evaluating it on both branches of the select results in the same value. 285dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Returns the common value if so, otherwise returns null. 2868ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilsemanstatic Value *ThreadBinOpOverSelect(unsigned Opcode, Value *LHS, Value *RHS, 287753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const Query &Q, unsigned MaxRecurse) { 2888ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman // Recursion is always used, so bail out at once if we already hit the limit. 2898ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman if (!MaxRecurse--) 29000e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return nullptr; 291753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 2928ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman SelectInst *SI; 2938ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman if (isa<SelectInst>(LHS)) { 2948ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman SI = cast<SelectInst>(LHS); 2958ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman } else { 2968ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman assert(isa<SelectInst>(RHS) && "No select instruction operand!"); 2978ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman SI = cast<SelectInst>(RHS); 298753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 299753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 3008ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman // Evaluate the BinOp on the true and false branches of the select. 3018ad435fa4809b5a4ad1043435cbafd5c9ddf2d93Michael Ilseman Value *TV; 302753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *FV; 303cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif if (SI == LHS) { 304753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner TV = SimplifyBinOp(Opcode, SI->getTrueValue(), RHS, Q, MaxRecurse); 305753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner FV = SimplifyBinOp(Opcode, SI->getFalseValue(), RHS, Q, MaxRecurse); 306753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } else { 307753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner TV = SimplifyBinOp(Opcode, LHS, SI->getTrueValue(), Q, MaxRecurse); 308753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner FV = SimplifyBinOp(Opcode, LHS, SI->getFalseValue(), Q, MaxRecurse); 309cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif } 310753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 311753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If they simplified to the same value, then return the common value. 312753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If they both failed to simplify then return null. 313cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif if (TV == FV) 314753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return TV; 315753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 316753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If one branch simplified to undef, return the other one. 317753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (TV && isa<UndefValue>(TV)) 318753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return FV; 319db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (FV && isa<UndefValue>(FV)) 320f1ac465b67d5fc11a0d9cd09b98ceb4ffa75dd97Owen Anderson return TV; 321f1ac465b67d5fc11a0d9cd09b98ceb4ffa75dd97Owen Anderson 322753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If applying the operation did not change the true and false select values, 323753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // then the result of the binop is the select itself. 324753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (TV == SI->getTrueValue() && FV == SI->getFalseValue()) 325dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return SI; 326753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 327753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If one branch simplified and the other did not, and the simplified 328753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // value is equal to the unsimplified one, return the simplified value. 329753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // For example, select (cond, X, X & Z) & Z -> X & Z. 330753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if ((FV && !TV) || (TV && !FV)) { 33100e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach // Check that the simplified value has the form "X op Y" where "op" is the 332753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // same as the original operation. 333753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Instruction *Simplified = dyn_cast<Instruction>(FV ? FV : TV); 334753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Simplified && Simplified->getOpcode() == Opcode) { 335753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // The value that didn't simplify is "UnsimplifiedLHS op UnsimplifiedRHS". 336753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // We already know that "op" is the same as for the simplified value. See 337db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner // if the operands match too. If so, return the simplified value. 338f1ac465b67d5fc11a0d9cd09b98ceb4ffa75dd97Owen Anderson Value *UnsimplifiedBranch = FV ? SI->getTrueValue() : SI->getFalseValue(); 339f1ac465b67d5fc11a0d9cd09b98ceb4ffa75dd97Owen Anderson Value *UnsimplifiedLHS = SI == LHS ? UnsimplifiedBranch : LHS; 340753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *UnsimplifiedRHS = SI == LHS ? RHS : UnsimplifiedBranch; 341753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Simplified->getOperand(0) == UnsimplifiedLHS && 342753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Simplified->getOperand(1) == UnsimplifiedRHS) 343dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Simplified; 344753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Simplified->isCommutative() && 345753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Simplified->getOperand(1) == UnsimplifiedLHS && 346753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Simplified->getOperand(0) == UnsimplifiedRHS) 347753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Simplified; 348753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 34900e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach } 350753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 351753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 352753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 353cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif 354db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner/// ThreadCmpOverSelect - In the case of a comparison with a select instruction, 355753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// try to simplify the comparison by seeing whether both branches of the select 356753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// result in the same value. Returns the common value if so, otherwise returns 357753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// null. 358dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic Value *ThreadCmpOverSelect(CmpInst::Predicate Pred, Value *LHS, 359753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *RHS, const Query &Q, 360753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner unsigned MaxRecurse) { 361753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Recursion is always used, so bail out at once if we already hit the limit. 362753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!MaxRecurse--) 363753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 364753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 365dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Make sure the select is on the LHS. 366753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!isa<SelectInst>(LHS)) { 367753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner std::swap(LHS, RHS); 368753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Pred = CmpInst::getSwappedPredicate(Pred); 369753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 370753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner assert(isa<SelectInst>(LHS) && "Not comparing with a select instruction!"); 37159f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman SelectInst *SI = cast<SelectInst>(LHS); 37259f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman Value *Cond = SI->getCondition(); 373753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *TV = SI->getTrueValue(); 37459f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman Value *FV = SI->getFalseValue(); 37559f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman 376753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Now that we have "cmp select(Cond, TV, FV), RHS", analyse it. 377db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner // Does "cmp TV, RHS" simplify? 378b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner Value *TCmp = SimplifyCmpInst(Pred, TV, RHS, Q, MaxRecurse); 379753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (TCmp == Cond) { 380753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // It not only simplified, it simplified to the select condition. Replace 38159f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman // it with 'true'. 382753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner TCmp = getTrue(Cond->getType()); 383753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } else if (!TCmp) { 384753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // It didn't simplify. However if "cmp TV, RHS" is equal to the select 38559f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman // condition then we can replace it with 'true'. Otherwise give up. 38659f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman if (!isSameCompare(Cond, Pred, TV, RHS)) 387753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 388753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner TCmp = getTrue(Cond->getType()); 389753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 390753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 391db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner // Does "cmp FV, RHS" simplify? 392b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner Value *FCmp = SimplifyCmpInst(Pred, FV, RHS, Q, MaxRecurse); 393753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (FCmp == Cond) { 394753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // It not only simplified, it simplified to the select condition. Replace 395753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // it with 'false'. 396753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner FCmp = getFalse(Cond->getType()); 397753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } else if (!FCmp) { 398753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // It didn't simplify. However if "cmp FV, RHS" is equal to the select 399753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // condition then we can replace it with 'false'. Otherwise give up. 400a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif if (!isSameCompare(Cond, Pred, FV, RHS)) 401a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif return nullptr; 402a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif FCmp = getFalse(Cond->getType()); 403a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif } 404a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif 405753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If both sides simplified to the same value, then use it as the result of 406753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // the original comparison. 407753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (TCmp == FCmp) 408753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return TCmp; 4099c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif 410753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // The remaining cases only make sense if the select condition has the same 41100e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach // type as the result of the comparison, so bail out if this is not so. 4129c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy()) 413753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 414753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If the false value simplified to false, then the result of the compare 415753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // is equal to "Cond && TCmp". This also catches the case when the false 4164fffb345ed20bd144a31c1c1724cffb6f519b814Eli Friedman // value simplified to false and the true value to true, returning "Cond". 417753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(FCmp, m_Zero())) 418753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = SimplifyAndInst(Cond, TCmp, Q, MaxRecurse)) 419b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner return V; 420b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner // If the true value simplified to true, then the result of the compare 421cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif // is equal to "Cond || FCmp". 422753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(TCmp, m_One())) 423753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = SimplifyOrInst(Cond, FCmp, Q, MaxRecurse)) 424cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return V; 425cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Finally, if the false value simplified to true and the true value to 426cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // false, then the result of the compare is equal to "!Cond". 427cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (match(FCmp, m_One()) && match(TCmp, m_Zero())) 428cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Value *V = 429cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SimplifyXorInst(Cond, Constant::getAllOnesValue(Cond->getType()), 430cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Q, MaxRecurse)) 431cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return V; 432cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 433cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return nullptr; 434cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 435cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 436cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// ThreadBinOpOverPHI - In the case of a binary operation with an operand that 437cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// is a PHI instruction, try to simplify the binop by seeing whether evaluating 438cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// it on the incoming phi values yields the same result for every value. If so 439753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// returns the common value, otherwise returns null. 440753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *ThreadBinOpOverPHI(unsigned Opcode, Value *LHS, Value *RHS, 441753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const Query &Q, unsigned MaxRecurse) { 442753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Recursion is always used, so bail out at once if we already hit the limit. 443753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!MaxRecurse--) 4449c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif return nullptr; 4459c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif 446753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner PHINode *PI; 44700e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (isa<PHINode>(LHS)) { 4489c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif PI = cast<PHINode>(LHS); 449753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Bail out if RHS and the phi may be mutually interdependent due to a loop. 450753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!ValueDominatesPHI(RHS, PI, Q.DT)) 451753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 4529c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif } else { 453753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner assert(isa<PHINode>(RHS) && "No PHI instruction operand!"); 454753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner PI = cast<PHINode>(RHS); 45500e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach // Bail out if LHS and the phi may be mutually interdependent due to a loop. 456b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner if (!ValueDominatesPHI(LHS, PI, Q.DT)) 4579c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif return nullptr; 458753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 459753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 460753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Evaluate the BinOp on the incoming phi values. 4616b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer Value *CommonValue = nullptr; 4626b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 4636b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer Value *Incoming = PI->getIncomingValue(i); 4646b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer // If the incoming value is the phi node itself, it can safely be skipped. 4656b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer if (Incoming == PI) continue; 4666b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer Value *V = PI == LHS ? 467dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SimplifyBinOp(Opcode, Incoming, RHS, Q, MaxRecurse) : 4686b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer SimplifyBinOp(Opcode, LHS, Incoming, Q, MaxRecurse); 4696b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer // If the operation failed to simplify, or simplified to a different value 470dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // to previously, then give up. 4716b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer if (!V || (CommonValue && V != CommonValue)) 472d655e6e9dc0d21c3a2d76494dec255bb027572aeBenjamin Kramer return nullptr; 473d655e6e9dc0d21c3a2d76494dec255bb027572aeBenjamin Kramer CommonValue = V; 474d655e6e9dc0d21c3a2d76494dec255bb027572aeBenjamin Kramer } 4756b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer 4766b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer return CommonValue; 4776b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer} 478d655e6e9dc0d21c3a2d76494dec255bb027572aeBenjamin Kramer 479d655e6e9dc0d21c3a2d76494dec255bb027572aeBenjamin Kramer/// ThreadCmpOverPHI - In the case of a comparison with a PHI instruction, try 480d655e6e9dc0d21c3a2d76494dec255bb027572aeBenjamin Kramer/// try to simplify the comparison by seeing whether comparing with all of the 4816b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer/// incoming phi values yields the same result every time. If so returns the 4826b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer/// common result, otherwise returns null. 4836b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramerstatic Value *ThreadCmpOverPHI(CmpInst::Predicate Pred, Value *LHS, Value *RHS, 4846b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer const Query &Q, unsigned MaxRecurse) { 4856b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer // Recursion is always used, so bail out at once if we already hit the limit. 486b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner if (!MaxRecurse--) 4876b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer return nullptr; 4886b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer 4896b96fe7e146f7eb594e67210c6bef511ad0a2058Benjamin Kramer // Make sure the phi is on the LHS. 490753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!isa<PHINode>(LHS)) { 491753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner std::swap(LHS, RHS); 492a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif Pred = CmpInst::getSwappedPredicate(Pred); 493a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif } 494a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif assert(isa<PHINode>(LHS) && "Not comparing with a phi instruction!"); 495a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif PHINode *PI = cast<PHINode>(LHS); 496a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif 497753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Bail out if RHS and the phi may be mutually interdependent due to a loop. 498753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!ValueDominatesPHI(RHS, PI, Q.DT)) 499753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 500753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 5019c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif // Evaluate the BinOp on the incoming phi values. 502753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *CommonValue = nullptr; 50300e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach for (unsigned i = 0, e = PI->getNumIncomingValues(); i != e; ++i) { 5049c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif Value *Incoming = PI->getIncomingValue(i); 505753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If the incoming value is the phi node itself, it can safely be skipped. 506753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Incoming == PI) continue; 507753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *V = SimplifyCmpInst(Pred, Incoming, RHS, Q, MaxRecurse); 50800e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach // If the operation failed to simplify, or simplified to a different value 509753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // to previously, then give up. 510753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!V || (CommonValue && V != CommonValue)) 511753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 512cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif CommonValue = V; 513753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 514753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 51500e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return CommonValue; 516b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner} 517cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif 518753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifyAddInst - Given operands for an Add, see if we can 519753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// fold the result. If not, this returns null. 520753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 521753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const Query &Q, unsigned MaxRecurse) { 522753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 523f93f7b2446bec3febc30b7136e18704664bd98ccBill Wendling if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 52436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *Ops[] = { CLHS, CRHS }; 525cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif return ConstantFoldInstOperands(Instruction::Add, CLHS->getType(), Ops, 526753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Q.DL, Q.TLI); 527753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 528753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 529753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Canonicalize the constant to the RHS. 530753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner std::swap(Op0, Op1); 531753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 532753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 53336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // X + undef -> undef 53400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (match(Op1, m_Undef())) 5352f1ab74e763ba7f10a058f62393d0987f6f7e298Gabor Greif return Op1; 5362f1ab74e763ba7f10a058f62393d0987f6f7e298Gabor Greif 5372f1ab74e763ba7f10a058f62393d0987f6f7e298Gabor Greif // X + 0 -> X 538753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Zero())) 539753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 540753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 541753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X + (Y - X) -> Y 542753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // (Y - X) + X -> Y 543753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Eg: X + -X -> 0 54436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Y = nullptr; 54500e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) || 5462f1ab74e763ba7f10a058f62393d0987f6f7e298Gabor Greif match(Op0, m_Sub(m_Value(Y), m_Specific(Op1)))) 5472f1ab74e763ba7f10a058f62393d0987f6f7e298Gabor Greif return Y; 5482f1ab74e763ba7f10a058f62393d0987f6f7e298Gabor Greif 549753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X + ~X -> -1 since ~X = -X-1 550753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_Not(m_Specific(Op1))) || 5519cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth match(Op1, m_Not(m_Specific(Op0)))) 5529cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth return Constant::getAllOnesValue(Op0->getType()); 5539cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth 5549cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth /// i1 add -> xor. 5559cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 5569cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) 5579cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth return V; 5589cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth 5599cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth // Try some generic simplifications for associative operations. 5609cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth if (Value *V = SimplifyAssociativeBinOp(Instruction::Add, Op0, Op1, Q, 561753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner MaxRecurse)) 562753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 5639c68a7bb45ebf71cec5ab4eab7c73aacdfce16dfGabor Greif 564753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Threading Add over selects and phi nodes is pointless, so don't bother. 565753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Threading over the select in "A + select(cond, B, C)" means evaluating 566a399781289092fcdceb58b21174229f4373c4191Gabor Greif // "A+B" and "A+C" and seeing if they are equal; but they are equal if and 567a399781289092fcdceb58b21174229f4373c4191Gabor Greif // only if B and C are equal. If B and C are equal then (since we assume 568a90c5c7605e0d8df96e61d4bf0cc47a7eaea92cfGabor Greif // that operands have already been simplified) "select(cond, B, C)" should 569753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // have been simplified to the common value of B and C already. Analysing 570753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // "A+B" and "A+C" thus gains nothing, but costs compile time. Similarly 571753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // for threading over phi nodes. 572753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 5739cc9f50abc28f08fb6082b5ee4f5cc7e1af4969bChandler Carruth return nullptr; 574dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 575dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 576dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesValue *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 577dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DataLayout *DL, const TargetLibraryInfo *TLI, 578dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DominatorTree *DT) { 579dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query (DL, TLI, DT), 580dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RecursionLimit); 581dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 582dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 583dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Compute the base pointer and cumulative constant offsets for V. 584dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 585dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// This strips all constant offsets off of V, leaving it the base pointer, and 586dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// accumulates the total constant offset applied in the returned constant. It 587dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// returns 0 if V is not a pointer, and returns the constant '0' if there are 588dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// no constant offsets applied. 589dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 590dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// This is very similar to GetPointerBaseWithConstantOffset except it doesn't 591dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc. 592dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// folding. 593dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic Constant *stripAndComputeConstantOffsets(const DataLayout *DL, 594dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *&V, 595dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool AllowNonInbounds = false) { 596dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(V->getType()->getScalarType()->isPointerTy()); 597dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 598dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Without DataLayout, just be conservative for now. Theoretically, more could 599dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // be done in this case. 600dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!DL) 601dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ConstantInt::get(IntegerType::get(V->getContext(), 64), 0); 602dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 603dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Type *IntPtrTy = DL->getIntPtrType(V->getType())->getScalarType(); 604dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines APInt Offset = APInt::getNullValue(IntPtrTy->getIntegerBitWidth()); 605dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 606dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Even though we don't look through PHI nodes, we could be called on an 607dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // instruction in an unreachable block, which may be on a cycle. 608dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallPtrSet<Value *, 4> Visited; 609dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Visited.insert(V); 610dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines do { 611dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 612dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if ((!AllowNonInbounds && !GEP->isInBounds()) || 613dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines !GEP->accumulateConstantOffset(*DL, Offset)) 614dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 615dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines V = GEP->getPointerOperand(); 616dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } else if (Operator::getOpcode(V) == Instruction::BitCast) { 617dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines V = cast<Operator>(V)->getOperand(0); 618dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 619dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (GA->mayBeOverridden()) 620dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 621dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines V = GA->getAliasee(); 622dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } else { 623dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 624dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 625dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(V->getType()->getScalarType()->isPointerTy() && 626dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "Unexpected operand type!"); 627dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } while (Visited.insert(V)); 628dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 629dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset); 630dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (V->getType()->isVectorTy()) 631dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ConstantVector::getSplat(V->getType()->getVectorNumElements(), 632dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines OffsetIntPtr); 633dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return OffsetIntPtr; 634dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 635dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 636dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Compute the constant difference between two pointer values. 637dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// If the difference is not a constant, returns zero. 638dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic Constant *computePointerDifference(const DataLayout *DL, 639dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *LHS, Value *RHS) { 640dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); 641dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); 642dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 643dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If LHS and RHS are not related via constant offsets to the same base 644dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // value, there is nothing we can do here. 645dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (LHS != RHS) 646dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 647ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings 648ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings // Otherwise, the difference of LHS - RHS can be computed as: 649ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings // LHS - RHS 650ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings // = (LHSOffset + Base) - (RHSOffset + Base) 651ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings // = LHSOffset - RHSOffset 652ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings return ConstantExpr::getSub(LHSOffset, RHSOffset); 653ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings} 654aaa7f499c1a2d46491a98d978ef45b0a06d73d31Evan Cheng 655ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings/// SimplifySubInst - Given operands for a Sub, see if we can 656ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings/// fold the result. If not, this returns null. 657ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastingsstatic Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 658d116611e0a884e53ea1524de3a1306c1eb447228Stuart Hastings const Query &Q, unsigned MaxRecurse) { 659ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings if (Constant *CLHS = dyn_cast<Constant>(Op0)) 660ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 661ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings Constant *Ops[] = { CLHS, CRHS }; 662ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings return ConstantFoldInstOperands(Instruction::Sub, CLHS->getType(), 663ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings Ops, Q.DL, Q.TLI); 664ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings } 665ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings 666ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings // X - undef -> undef 667ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings // undef - X -> undef 668ca1ef485854d668f794bf389154aa371aa2ed535Stuart Hastings if (match(Op0, m_Undef()) || match(Op1, m_Undef())) 669dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return UndefValue::get(Op0->getType()); 670dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 671dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // X - 0 -> X 672dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op1, m_Zero())) 673dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Op0; 674dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 675dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // X - X -> 0 676dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Op0 == Op1) 677dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Constant::getNullValue(Op0->getType()); 678dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 679dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies. 680dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // For example, (X + Y) - Y -> X; (Y + X) - Y -> X 681dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *X = nullptr, *Y = nullptr, *Z = Op1; 682dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z 683dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // See if "V === Y - Z" simplifies. 684dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1)) 685dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does! Now see if "X + V" simplifies. 686dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) { 687dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does, we successfully reassociated! 688dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++NumReassoc; 689dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return W; 690dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 691dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // See if "V === X - Z" simplifies. 692dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) 693dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does! Now see if "Y + V" simplifies. 694dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *W = SimplifyBinOp(Instruction::Add, Y, V, Q, MaxRecurse-1)) { 695dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does, we successfully reassociated! 696dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++NumReassoc; 697dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return W; 698dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 699dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 700dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 701dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // X - (Y + Z) -> (X - Y) - Z or (X - Z) - Y if everything simplifies. 702dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // For example, X - (X + 1) -> -1 703dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines X = Op0; 704dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (MaxRecurse && match(Op1, m_Add(m_Value(Y), m_Value(Z)))) { // X - (Y + Z) 705dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // See if "V === X - Y" simplifies. 706dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) 707dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does! Now see if "V - Z" simplifies. 708dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *W = SimplifyBinOp(Instruction::Sub, V, Z, Q, MaxRecurse-1)) { 709dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does, we successfully reassociated! 710dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++NumReassoc; 711dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return W; 712dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 713dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // See if "V === X - Z" simplifies. 714dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyBinOp(Instruction::Sub, X, Z, Q, MaxRecurse-1)) 715dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does! Now see if "V - Y" simplifies. 716dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *W = SimplifyBinOp(Instruction::Sub, V, Y, Q, MaxRecurse-1)) { 717dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does, we successfully reassociated! 718dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++NumReassoc; 719dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return W; 720dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 721dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 722dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 723dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Z - (X - Y) -> (Z - X) + Y if everything simplifies. 724dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // For example, X - (X - Y) -> Y. 725dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Z = Op0; 726dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (MaxRecurse && match(Op1, m_Sub(m_Value(X), m_Value(Y)))) // Z - (X - Y) 727dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // See if "V === Z - X" simplifies. 728dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyBinOp(Instruction::Sub, Z, X, Q, MaxRecurse-1)) 729dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does! Now see if "V + Y" simplifies. 730dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *W = SimplifyBinOp(Instruction::Add, V, Y, Q, MaxRecurse-1)) { 731dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does, we successfully reassociated! 732dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++NumReassoc; 733dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return W; 734dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 735dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 736dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // trunc(X) - trunc(Y) -> trunc(X - Y) if everything simplifies. 737dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (MaxRecurse && match(Op0, m_Trunc(m_Value(X))) && 738dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines match(Op1, m_Trunc(m_Value(Y)))) 739dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (X->getType() == Y->getType()) 740dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // See if "V === X - Y" simplifies. 741dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyBinOp(Instruction::Sub, X, Y, Q, MaxRecurse-1)) 742dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does! Now see if "trunc V" simplifies. 743dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *W = SimplifyTruncInst(V, Op0->getType(), Q, MaxRecurse-1)) 744dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // It does, return the simplified "trunc V". 745dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return W; 746dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 747dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...). 748dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op0, m_PtrToInt(m_Value(X))) && 749dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines match(Op1, m_PtrToInt(m_Value(Y)))) 750dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Constant *Result = computePointerDifference(Q.DL, X, Y)) 751dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); 752dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 753dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // i1 sub -> xor. 754dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 755dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyXorInst(Op0, Op1, Q, MaxRecurse-1)) 756dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return V; 757dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 758dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Threading Sub over selects and phi nodes is pointless, so don't bother. 759dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Threading over the select in "A - select(cond, B, C)" means evaluating 760dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // "A-B" and "A-C" and seeing if they are equal; but they are equal if and 761dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // only if B and C are equal. If B and C are equal then (since we assume 762dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // that operands have already been simplified) "select(cond, B, C)" should 763dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // have been simplified to the common value of B and C already. Analysing 764dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // "A-B" and "A-C" thus gains nothing, but costs compile time. Similarly 765dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // for threading over phi nodes. 766dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 767dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 768dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 769dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 770dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesValue *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 771dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DataLayout *DL, const TargetLibraryInfo *TLI, 772dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DominatorTree *DT) { 773dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query (DL, TLI, DT), 774dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RecursionLimit); 775dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 776dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 777dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Given operands for an FAdd, see if we can fold the result. If not, this 778dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// returns null. 779dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, 780dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const Query &Q, unsigned MaxRecurse) { 781dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 782dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 783dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Constant *Ops[] = { CLHS, CRHS }; 784dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ConstantFoldInstOperands(Instruction::FAdd, CLHS->getType(), 785dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Ops, Q.DL, Q.TLI); 786dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 787dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 788dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Canonicalize the constant to the RHS. 789dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::swap(Op0, Op1); 790dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 791dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 792dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // fadd X, -0 ==> X 793dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op1, m_NegZero())) 794dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Op0; 795dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 796dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // fadd X, 0 ==> X, when we know X is not -0 797dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op1, m_Zero()) && 798dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) 799dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Op0; 800dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 801dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0 802dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // where nnan and ninf have to occur at least once somewhere in this 803dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // expression 804dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *SubOp = nullptr; 805dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0)))) 806dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SubOp = Op1; 807dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1)))) 808dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SubOp = Op0; 809dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (SubOp) { 810dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Instruction *FSub = cast<Instruction>(SubOp); 811dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if ((FMF.noNaNs() || FSub->hasNoNaNs()) && 812dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (FMF.noInfs() || FSub->hasNoInfs())) 813dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Constant::getNullValue(Op0->getType()); 814dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 815dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 816753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 817753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 818cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 819cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// Given operands for an FSub, see if we can fold the result. If not, this 820cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// returns null. 821cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesstatic Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, 822cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const Query &Q, unsigned MaxRecurse) { 823a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 824a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 825a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Constant *Ops[] = { CLHS, CRHS }; 82600e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return ConstantFoldInstOperands(Instruction::FSub, CLHS->getType(), 827753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Ops, Q.DL, Q.TLI); 828753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 829753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 830a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner 831dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // fsub X, 0 ==> X 832753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Zero())) 833753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 834753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 835753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // fsub X, -0 ==> X, when we know X is not -0 83600e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (match(Op1, m_NegZero()) && 837753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) 838753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 839a399781289092fcdceb58b21174229f4373c4191Gabor Greif 840a399781289092fcdceb58b21174229f4373c4191Gabor Greif // fsub 0, (fsub -0.0, X) ==> X 841a399781289092fcdceb58b21174229f4373c4191Gabor Greif Value *X; 842a399781289092fcdceb58b21174229f4373c4191Gabor Greif if (match(Op0, m_AnyZero())) { 843753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_FSub(m_NegZero(), m_Value(X)))) 84400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return X; 845753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (FMF.noSignedZeros() && match(Op1, m_FSub(m_AnyZero(), m_Value(X)))) 846753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return X; 847753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 84800e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach 849753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // fsub nnan ninf x, x ==> 0.0 850a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (FMF.noNaNs() && FMF.noInfs() && Op0 == Op1) 851753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 85200e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach 853a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner return nullptr; 854753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 855cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 856cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// Given the operands for an FMul, see if we can fold the result 85700e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbachstatic Value *SimplifyFMulInst(Value *Op0, Value *Op1, 858dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines FastMathFlags FMF, 859cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const Query &Q, 860cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned MaxRecurse) { 86100e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 862cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 863a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer Constant *Ops[] = { CLHS, CRHS }; 864753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ConstantFoldInstOperands(Instruction::FMul, CLHS->getType(), 86500e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach Ops, Q.DL, Q.TLI); 866753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 867753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 868a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer // Canonicalize the constant to the RHS. 869753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner std::swap(Op0, Op1); 870753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 871753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 872753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // fmul X, 1.0 ==> X 873753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_FPOne())) 874753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 875364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson 876364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson // fmul nnan nsz X, 0 ==> 0 877364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero())) 878364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson return Op1; 879364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson 880364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson return nullptr; 881364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson} 882364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson 883364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson/// SimplifyMulInst - Given operands for a Mul, see if we can 884364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson/// fold the result. If not, this returns null. 885364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilsonstatic Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q, 886364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson unsigned MaxRecurse) { 887364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 888364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 88936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Constant *Ops[] = { CLHS, CRHS }; 890364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson return ConstantFoldInstOperands(Instruction::Mul, CLHS->getType(), 891364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson Ops, Q.DL, Q.TLI); 892364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson } 893364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson 894364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson // Canonicalize the constant to the RHS. 895364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson std::swap(Op0, Op1); 896364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson } 897364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson 898364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson // X * undef -> 0 899364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson if (match(Op1, m_Undef())) 900364f17c47162a657bb0c3516588cdfc5297664f0Bob Wilson return Constant::getNullValue(Op0->getType()); 901973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames 90236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // X * 0 -> 0 903dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op1, m_Zero())) 904dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Op1; 905973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames 906973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames // X * 1 -> X 907973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames if (match(Op1, m_One())) 908973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames return Op0; 909973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames 910973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames // (X / Y) * Y -> X if the division is exact. 911973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames Value *X = nullptr; 912973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y 913973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y) 91436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return X; 915dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 916973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames // i1 mul -> and. 91736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (MaxRecurse && Op0->getType()->isIntegerTy(1)) 91836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *V = SimplifyAndInst(Op0, Op1, Q, MaxRecurse-1)) 91936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return V; 92036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 92136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Try some generic simplifications for associative operations. 92236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *V = SimplifyAssociativeBinOp(Instruction::Mul, Op0, Op1, Q, 923973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames MaxRecurse)) 924973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames return V; 92536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 926973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames // Mul distributes over Add. Try some generic simplifications based on this. 927973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames if (Value *V = ExpandBinOp(Instruction::Mul, Op0, Op1, Instruction::Add, 928973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames Q, MaxRecurse)) 929973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames return V; 93036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 931973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames // If the operation is with the result of a select instruction, check whether 93236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // operating on either branch of the select always yields the same value. 93336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 93436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Value *V = ThreadBinOpOverSelect(Instruction::Mul, Op0, Op1, Q, 93536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MaxRecurse)) 936973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames return V; 937973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames 938973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames // If the operation is with the result of a phi instruction, check whether 939973f72a29aeafb1fdc4f8dafc3f6c6651cbb0c99Lang Hames // operating on all incoming values of the phi always yields the same value. 940cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 941cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Value *V = ThreadBinOpOverPHI(Instruction::Mul, Op0, Op1, Q, 942cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines MaxRecurse)) 943cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return V; 944cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 945cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return nullptr; 946cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 947cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 948cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesValue *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, 949cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const DataLayout *DL, const TargetLibraryInfo *TLI, 950cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const DominatorTree *DT) { 951cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return ::SimplifyFAddInst(Op0, Op1, FMF, Query (DL, TLI, DT), RecursionLimit); 952cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 953cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 954753a2b464d0628231bd3dce645edd05dfbaa3a06Chris LattnerValue *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, 955753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DataLayout *DL, const TargetLibraryInfo *TLI, 956753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DominatorTree *DT) { 957cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif return ::SimplifyFSubInst(Op0, Op1, FMF, Query (DL, TLI, DT), RecursionLimit); 958753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 959753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 960753a2b464d0628231bd3dce645edd05dfbaa3a06Chris LattnerValue *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, 961753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner FastMathFlags FMF, 962753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DataLayout *DL, 963753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const TargetLibraryInfo *TLI, 96400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach const DominatorTree *DT) { 965753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ::SimplifyFMulInst(Op0, Op1, FMF, Query (DL, TLI, DT), RecursionLimit); 966753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 967753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 968753a2b464d0628231bd3dce645edd05dfbaa3a06Chris LattnerValue *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout *DL, 969753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const TargetLibraryInfo *TLI, 970753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DominatorTree *DT) { 9719e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return ::SimplifyMulInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 972753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 973753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 974753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifyDiv - Given operands for an SDiv or UDiv, see if we can 975753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// fold the result. If not, this returns null. 976753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *SimplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 977753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const Query &Q, unsigned MaxRecurse) { 978753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *C0 = dyn_cast<Constant>(Op0)) { 979753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *C1 = dyn_cast<Constant>(Op1)) { 980753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Constant *Ops[] = { C0, C1 }; 981753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 982753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 983753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 984753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 985753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner bool isSigned = Opcode == Instruction::SDiv; 986753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 987753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X / undef -> undef 988753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Undef())) 98900e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return Op1; 990dccc03b2423fe65efb5963ae816b99c24fc53374Bill Wendling 991dccc03b2423fe65efb5963ae816b99c24fc53374Bill Wendling // undef / X -> 0 992dccc03b2423fe65efb5963ae816b99c24fc53374Bill Wendling if (match(Op0, m_Undef())) 993aa5abe88d6aa445afa593476a665e3ab14b3524cBill Wendling return Constant::getNullValue(Op0->getType()); 994753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 995753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // 0 / X -> 0, we don't need to preserve faults! 996753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_Zero())) 997753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 998753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 999753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X / 1 -> X 1000753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_One())) 1001753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 1002753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1003753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Op0->getType()->isIntegerTy(1)) 1004753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // It can't be division by zero, hence it must be division by one. 1005753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 1006753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1007753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X / X -> 1 100800e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (Op0 == Op1) 1009753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ConstantInt::get(Op0->getType(), 1); 1010753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1011753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // (X * Y) / Y -> X if the multiplication does not overflow. 101236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *X = nullptr, *Y = nullptr; 1013753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_Mul(m_Value(X), m_Value(Y))) && (X == Op1 || Y == Op1)) { 1014753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Y != Op1) std::swap(X, Y); // Ensure expression is (X * Y) / Y, Y = Op1 1015753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner OverflowingBinaryOperator *Mul = cast<OverflowingBinaryOperator>(Op0); 1016753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If the Mul knows it does not overflow, then we are good to go. 101736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if ((isSigned && Mul->hasNoSignedWrap()) || 1018753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner (!isSigned && Mul->hasNoUnsignedWrap())) 1019753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return X; 102036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If X has the form X = A / Y then X * Y cannot overflow. 1021753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (BinaryOperator *Div = dyn_cast<BinaryOperator>(X)) 1022753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Div->getOpcode() == Opcode && Div->getOperand(1) == Y) 102300e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return X; 1024753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1025db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner 1026753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // (X rem Y) / Y -> 0 1027753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if ((isSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) || 102836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (!isSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1))))) 1029753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 1030753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1031753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If the operation is with the result of a select instruction, check whether 1032753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // operating on either branch of the select always yields the same value. 103327ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 103400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 103527ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher return V; 103627ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher 103736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If the operation is with the result of a phi instruction, check whether 1038dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // operating on all incoming values of the phi always yields the same value. 103927ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 104063f932ca3c91ea8ac5b592158f5e8ef7de550547Meador Inge if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 104163f932ca3c91ea8ac5b592158f5e8ef7de550547Meador Inge return V; 1042a241b58f8d5d71eebfb2cb9be3689fe72b454474Meador Inge 104363f932ca3c91ea8ac5b592158f5e8ef7de550547Meador Inge return nullptr; 10445e8904576a5260cfd5b14596e338a4bb25b9817eMeador Inge} 1045dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 104627ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher/// SimplifySDivInst - Given operands for an SDiv, see if we can 104727ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher/// fold the result. If not, this returns null. 10484a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sandsstatic Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q, 10494a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands unsigned MaxRecurse) { 10504a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (Value *V = SimplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse)) 10514a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return V; 10524a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 105336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return nullptr; 1054dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 10554a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 1056dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesValue *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout *DL, 10574a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands const TargetLibraryInfo *TLI, 1058dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DominatorTree *DT) { 105936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return ::SimplifySDivInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 106036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 10614a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 1062dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// SimplifyUDivInst - Given operands for a UDiv, see if we can 10634a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands/// fold the result. If not, this returns null. 10644a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sandsstatic Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q, 10654a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands unsigned MaxRecurse) { 1066dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Value *V = SimplifyDiv(Instruction::UDiv, Op0, Op1, Q, MaxRecurse)) 10674a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return V; 10684a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 10694a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return nullptr; 10704a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands} 10714a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 10724a544a79bd735967f1d33fe675ae4566dbd17813Duncan SandsValue *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout *DL, 1073dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const TargetLibraryInfo *TLI, 10744a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands const DominatorTree *DT) { 10754a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return ::SimplifyUDivInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 10764a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands} 10774a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 1078dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic Value *SimplifyFDivInst(Value *Op0, Value *Op1, const Query &Q, 10794a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands unsigned) { 10804a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands // undef / X -> undef (the undef could be a snan). 10814a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (match(Op0, m_Undef())) 1082dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Op0; 10834a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 10844a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands // X / undef -> undef 10854a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (match(Op1, m_Undef())) 10864a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return Op1; 10874a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 10884a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return nullptr; 10894a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands} 10904a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 10914a544a79bd735967f1d33fe675ae4566dbd17813Duncan SandsValue *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const DataLayout *DL, 10924a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands const TargetLibraryInfo *TLI, 10934a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands const DominatorTree *DT) { 10944a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return ::SimplifyFDivInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 10954a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands} 10964a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 10974a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands/// SimplifyRem - Given operands for an SRem or URem, see if we can 10984a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands/// fold the result. If not, this returns null. 1099dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic Value *SimplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, 11004a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands const Query &Q, unsigned MaxRecurse) { 1101dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Constant *C0 = dyn_cast<Constant>(Op0)) { 11024a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (Constant *C1 = dyn_cast<Constant>(Op1)) { 11034a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands Constant *Ops[] = { C0, C1 }; 11044a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 11054a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands } 11064a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands } 11074a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 11084a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands // X % undef -> undef 11094a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (match(Op1, m_Undef())) 11104a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return Op1; 11114a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 11124a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands // undef % X -> 0 1113dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op0, m_Undef())) 11144a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return Constant::getNullValue(Op0->getType()); 11154a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 11164a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands // 0 % X -> 0, we don't need to preserve faults! 11174a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (match(Op0, m_Zero())) 11184a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return Op0; 11194a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 11204a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands // X % 0 -> undef, we don't need to preserve faults! 1121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op1, m_Zero())) 11224a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return UndefValue::get(Op0->getType()); 11234a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 1124753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X % 1 -> 0 1125753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_One())) 1126753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 11278e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 112878f8ef42173a3a9867ed789073d4ddc652fb7ff2Nuno Lopes if (Op0->getType()->isIntegerTy(1)) 11292b3e9580536dfb5666b9d91e99baebf6d45bfa5fNuno Lopes // It can't be remainder by zero, hence it must be remainder by one. 1130753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 1131753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1132ab215bc371677cdeac6eacb3e890e5af666d1ab4Chris Lattner // X % X -> 0 1133ab215bc371677cdeac6eacb3e890e5af666d1ab4Chris Lattner if (Op0 == Op1) 1134753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 1135ab215bc371677cdeac6eacb3e890e5af666d1ab4Chris Lattner 1136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If the operation is with the result of a select instruction, check whether 1137753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // operating on either branch of the select always yields the same value. 1138753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1139d569561835b0fa4dbbb0fca1b1f0a8de6c01439aChris Lattner if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1140d569561835b0fa4dbbb0fca1b1f0a8de6c01439aChris Lattner return V; 1141d569561835b0fa4dbbb0fca1b1f0a8de6c01439aChris Lattner 1142d569561835b0fa4dbbb0fca1b1f0a8de6c01439aChris Lattner // If the operation is with the result of a phi instruction, check whether 1143d569561835b0fa4dbbb0fca1b1f0a8de6c01439aChris Lattner // operating on all incoming values of the phi always yields the same value. 1144d569561835b0fa4dbbb0fca1b1f0a8de6c01439aChris Lattner if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1145d569561835b0fa4dbbb0fca1b1f0a8de6c01439aChris Lattner if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1146753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 1147753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 114800e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return nullptr; 1149753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 11500fabd08066a29f4e5060539d0d0605cbfe2760b8Chad Rosier 1151753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifySRemInst - Given operands for an SRem, see if we can 1152753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// fold the result. If not, this returns null. 11533e22cb9ec30cd9b1be9b0f50e400f512124997e5Eli Friedmanstatic Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q, 1154830f3f205d8a77acbf8838fe78c2c733ca924d9cChris Lattner unsigned MaxRecurse) { 1155753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = SimplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse)) 115600e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return V; 1157830f3f205d8a77acbf8838fe78c2c733ca924d9cChris Lattner 1158830f3f205d8a77acbf8838fe78c2c733ca924d9cChris Lattner return nullptr; 1159654c06f6457f80428e40810ad251c412462731e4Gabor Greif} 1160830f3f205d8a77acbf8838fe78c2c733ca924d9cChris Lattner 1161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesValue *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout *DL, 1162753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const TargetLibraryInfo *TLI, 1163753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DominatorTree *DT) { 1164753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ::SimplifySRemInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 1165cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif} 1166753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1167753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifyURemInst - Given operands for a URem, see if we can 11683e22cb9ec30cd9b1be9b0f50e400f512124997e5Eli Friedman/// fold the result. If not, this returns null. 11693e22cb9ec30cd9b1be9b0f50e400f512124997e5Eli Friedmanstatic Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q, 1170753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner unsigned MaxRecurse) { 1171f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes if (Value *V = SimplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse)) 1172f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes return V; 1173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1174753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 1175f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes} 1176f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes 1177f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno LopesValue *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout *DL, 1178f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes const TargetLibraryInfo *TLI, 1179f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes const DominatorTree *DT) { 1180f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes return ::SimplifyURemInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 1181f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes} 1182f1fb6c836940d1b92c0e3df27f4c9ca6569ff968Nuno Lopes 1183753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *SimplifyFRemInst(Value *Op0, Value *Op1, const Query &, 1184753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner unsigned) { 1185753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // undef % X -> undef (the undef could be a snan). 11864a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (match(Op0, m_Undef())) 11874a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return Op0; 1188753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1189db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner // X % undef -> undef 1190db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (match(Op1, m_Undef())) 1191753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op1; 1192ba78c883d4c89bd807fa7ebea7ac6f22f3503223Eli Friedman 1193753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 1194753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 11951bde770ccd35b27e0421e54fcdde1f33cdba0f7aMatt Arsenault 1196753a2b464d0628231bd3dce645edd05dfbaa3a06Chris LattnerValue *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const DataLayout *DL, 1197753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const TargetLibraryInfo *TLI, 119836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DominatorTree *DT) { 1199753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ::SimplifyFRemInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 1200753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1201753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1202753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// isUndefShift - Returns true if a shift by \c Amount always yields undef. 1203753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic bool isUndefShift(Value *Amount) { 1204753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Constant *C = dyn_cast<Constant>(Amount); 1205753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!C) 1206753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return false; 1207753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1208753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X shift by undef -> undef because it may shift by the bitwidth. 1209753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (isa<UndefValue>(C)) 1210753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return true; 12113574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow 121227ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher // Shifting by the bitwidth or more is undefined. 121327ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 121427ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher if (CI->getValue().getLimitedValue() >= 121536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CI->getType()->getScalarSizeInBits()) 12167b323a34fa034389e9e439f6c02eeb73e87ab9dbEric Christopher return true; 12177b323a34fa034389e9e439f6c02eeb73e87ab9dbEric Christopher 12187b323a34fa034389e9e439f6c02eeb73e87ab9dbEric Christopher // If all lanes of a vector shift are undefined the whole shift is. 121927ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) { 122027ceaa13f820e33c44e29adc2095dd3e1e69d09fEric Christopher for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; ++I) 1221dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!isUndefShift(C->getAggregateElement(I))) 1222753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return false; 1223753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return true; 1224753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1225753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1226753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return false; 1227753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1228ab215bc371677cdeac6eacb3e890e5af666d1ab4Chris Lattner 1229ab215bc371677cdeac6eacb3e890e5af666d1ab4Chris Lattner/// SimplifyShift - Given operands for an Shl, LShr or AShr, see if we can 1230dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// fold the result. If not, this returns null. 1231753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *SimplifyShift(unsigned Opcode, Value *Op0, Value *Op1, 1232753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const Query &Q, unsigned MaxRecurse) { 123399faa3b4ec6d03ac7808fe4ff3fbf3d04e375502Bill Wendling if (Constant *C0 = dyn_cast<Constant>(Op0)) { 1234753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *C1 = dyn_cast<Constant>(Op1)) { 1235753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Constant *Ops[] = { C0, C1 }; 1236753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ConstantFoldInstOperands(Opcode, C0->getType(), Ops, Q.DL, Q.TLI); 1237753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1238753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1239db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner 1240db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner // 0 shift by X -> 0 1241db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (match(Op0, m_Zero())) 1242753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 1243753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1244753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X shift by 0 -> X 124536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op1, m_Zero())) 124636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Op0; 124736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 124836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Fold undefined shifts. 12493e1c40de7f33db639698982bb58d8c2c8d7d5780Matt Arsenault if (isUndefShift(Op1)) 12503e1c40de7f33db639698982bb58d8c2c8d7d5780Matt Arsenault return UndefValue::get(Op0->getType()); 12513e1c40de7f33db639698982bb58d8c2c8d7d5780Matt Arsenault 1252753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If the operation is with the result of a select instruction, check whether 12533e1c40de7f33db639698982bb58d8c2c8d7d5780Matt Arsenault // operating on either branch of the select always yields the same value. 12543e1c40de7f33db639698982bb58d8c2c8d7d5780Matt Arsenault if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 12553e1c40de7f33db639698982bb58d8c2c8d7d5780Matt Arsenault if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse)) 1256753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 12573e1c40de7f33db639698982bb58d8c2c8d7d5780Matt Arsenault 1258753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If the operation is with the result of a phi instruction, check whether 1259753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // operating on all incoming values of the phi always yields the same value. 12601b0c54f1c5dd61e56cb7cbc435fcb3319cff628fBill Wendling if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1261e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse)) 1262e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling return V; 1263e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling 1264e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling return nullptr; 1265753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1266753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1267753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifyShlInst - Given operands for an Shl, see if we can 1268753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// fold the result. If not, this returns null. 1269753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1270753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const Query &Q, unsigned MaxRecurse) { 1271753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = SimplifyShift(Instruction::Shl, Op0, Op1, Q, MaxRecurse)) 1272753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 1273753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 127436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // undef << X -> 0 127536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (match(Op0, m_Undef())) 1276753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 1277753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1278753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // (X >> A) << A -> X 1279753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *X; 1280753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1))))) 12811bde770ccd35b27e0421e54fcdde1f33cdba0f7aMatt Arsenault return X; 1282753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 1283753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1284753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1285753a2b464d0628231bd3dce645edd05dfbaa3a06Chris LattnerValue *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, 1286db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const DataLayout *DL, const TargetLibraryInfo *TLI, 1287db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner const DominatorTree *DT) { 1288753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query (DL, TLI, DT), 12893e1c40de7f33db639698982bb58d8c2c8d7d5780Matt Arsenault RecursionLimit); 1290753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1291753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 129228d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling/// SimplifyLShrInst - Given operands for an LShr, see if we can 1293e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling/// fold the result. If not, this returns null. 1294e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendlingstatic Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1295753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const Query &Q, unsigned MaxRecurse) { 129600e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, Q, MaxRecurse)) 129736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return V; 129836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 129936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // X >> X -> 0 13002b9375e44b0e99ce23d2cef8de78f66347eef88aChris Lattner if (Op0 == Op1) 13012b9375e44b0e99ce23d2cef8de78f66347eef88aChris Lattner return Constant::getNullValue(Op0->getType()); 130228d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling 130328d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling // undef >>l X -> 0 130428d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling if (match(Op0, m_Undef())) 1305db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner return Constant::getNullValue(Op0->getType()); 1306dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 13072b9375e44b0e99ce23d2cef8de78f66347eef88aChris Lattner // (X << A) >> A -> X 130800e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach Value *X; 1309b060a46b0de75d6ab711b60d123ab42a9a6d7b3cMatt Arsenault if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 131036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap()) 131136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return X; 13122b9375e44b0e99ce23d2cef8de78f66347eef88aChris Lattner 13132b9375e44b0e99ce23d2cef8de78f66347eef88aChris Lattner return nullptr; 1314753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1315753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1316091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris LattnerValue *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, 1317091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner const DataLayout *DL, 1318091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner const TargetLibraryInfo *TLI, 1319091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner const DominatorTree *DT) { 1320091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner return ::SimplifyLShrInst(Op0, Op1, isExact, Query (DL, TLI, DT), 1321091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner RecursionLimit); 1322091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner} 1323091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner 1324db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner/// SimplifyAShrInst - Given operands for an AShr, see if we can 1325091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner/// fold the result. If not, this returns null. 1326091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattnerstatic Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1327f374486659822e93054363bef05e781acee16f3bJim Grosbach const Query &Q, unsigned MaxRecurse) { 1328f374486659822e93054363bef05e781acee16f3bJim Grosbach if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, Q, MaxRecurse)) 1329f374486659822e93054363bef05e781acee16f3bJim Grosbach return V; 1330f374486659822e93054363bef05e781acee16f3bJim Grosbach 1331871a2051f7d49827259d719a97b8cc86163edbd9Jim Grosbach // X >> X -> 0 1332871a2051f7d49827259d719a97b8cc86163edbd9Jim Grosbach if (Op0 == Op1) 1333871a2051f7d49827259d719a97b8cc86163edbd9Jim Grosbach return Constant::getNullValue(Op0->getType()); 1334f374486659822e93054363bef05e781acee16f3bJim Grosbach 1335f374486659822e93054363bef05e781acee16f3bJim Grosbach // all ones >>a X -> all ones 1336091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner if (match(Op0, m_AllOnes())) 133700e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach return Op0; 1338d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim Grosbach 1339d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim Grosbach // undef >>a X -> all ones 1340d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim Grosbach if (match(Op0, m_Undef())) 1341d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim Grosbach return Constant::getAllOnesValue(Op0->getType()); 1342d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim Grosbach 1343d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim Grosbach // (X << A) >> A -> X 13448e47daf2858e980210f3e1f007036b24da342c29Bill Wendling Value *X; 13458e47daf2858e980210f3e1f007036b24da342c29Bill Wendling if (match(Op0, m_Shl(m_Value(X), m_Specific(Op1))) && 1346d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim Grosbach cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap()) 13478e47daf2858e980210f3e1f007036b24da342c29Bill Wendling return X; 13481d3dcfe4246b4d45fa78a8dfd0a11c7fff842c15Bill Wendling 13498e47daf2858e980210f3e1f007036b24da342c29Bill Wendling return nullptr; 13508e47daf2858e980210f3e1f007036b24da342c29Bill Wendling} 1351d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim Grosbach 1352d5917f0b4d8f87985bfdf130c269e1929d0085d1Jim GrosbachValue *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, 1353753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DataLayout *DL, 135400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach const TargetLibraryInfo *TLI, 1355753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DominatorTree *DT) { 1356091b1e3c74fee17e33aa87478ab07bfbba0a2f78Chris Lattner return ::SimplifyAShrInst(Op0, Op1, isExact, Query (DL, TLI, DT), 1357753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner RecursionLimit); 1358753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1359ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling 1360753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifyAndInst - Given operands for an And, see if we can 1361753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// fold the result. If not, this returns null. 1362753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q, 13631b0c54f1c5dd61e56cb7cbc435fcb3319cff628fBill Wendling unsigned MaxRecurse) { 1364753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1365753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1366753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 1367e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling return ConstantFoldInstOperands(Instruction::And, CLHS->getType(), 1368e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling Ops, Q.DL, Q.TLI); 1369e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling } 1370e74365462a39529ae48ef4d34ec76b4543b8ea29Bill Wendling 1371753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Canonicalize the constant to the RHS. 1372753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner std::swap(Op0, Op1); 13738831c0605bbc0c82ce56c2fb85bd681d1c013925Bill Wendling } 1374ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling 1375ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling // X & undef -> 0 1376753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Undef())) 1377753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 1378753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1379db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner // X & X = X 1380f34dc428fa577d6d5d71ab3a1f9765b4e5da5a4fMatt Arsenault if (Op0 == Op1) 1381753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 1382753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1383753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X & 0 = 0 1384f34dc428fa577d6d5d71ab3a1f9765b4e5da5a4fMatt Arsenault if (match(Op1, m_Zero())) 1385753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op1; 1386753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1387753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X & -1 = X 138828d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling if (match(Op1, m_AllOnes())) 13897be7848e17f60825f5fbc177b8a25909a30ddb00Bill Wendling return Op0; 1390ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling 1391ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling // A & ~A = ~A & A = 0 1392753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_Not(m_Specific(Op1))) || 1393753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner match(Op1, m_Not(m_Specific(Op0)))) 1394753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 1395753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1396753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // (A | ?) & A = A 1397753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *A = nullptr, *B = nullptr; 1398753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_Or(m_Value(A), m_Value(B))) && 1399753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner (A == Op1 || B == Op1)) 1400753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op1; 14011dec62ed43fef82b1cafbcc1fc3d63cacd90cad9Nick Lewycky 14021dec62ed43fef82b1cafbcc1fc3d63cacd90cad9Nick Lewycky // A & (A | ?) = A 1403753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Or(m_Value(A), m_Value(B))) && 1404753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner (A == Op0 || B == Op0)) 1405db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner return Op0; 1406753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1407753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // A & (-A) = A if A is a power of two or zero. 1408753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_Neg(m_Specific(Op1))) || 1409753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner match(Op1, m_Neg(m_Specific(Op0)))) { 1410a9390a4d5f5d568059a80970d22194b165d097a7Benjamin Kramer if (isKnownToBeAPowerOfTwo(Op0, /*OrZero*/true)) 1411753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 1412753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/true)) 1413753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op1; 1414753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1415753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 141628d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling // Try some generic simplifications for associative operations. 14177be7848e17f60825f5fbc177b8a25909a30ddb00Bill Wendling if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q, 1418ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling MaxRecurse)) 1419ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling return V; 1420753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1421753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // And distributes over Or. Try some generic simplifications based on this. 1422753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or, 1423753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Q, MaxRecurse)) 1424c5f1bc88a2eb7ad9ff924ca90cf88494e5f947b9Bill Wendling return V; 1425956f13440a4aa0297606a4412f4aa091d931592aBill Wendling 1426ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling // And distributes over Xor. Try some generic simplifications based on this. 1427753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Xor, 1428753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Q, MaxRecurse)) 1429753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 1430753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 143199faa3b4ec6d03ac7808fe4ff3fbf3d04e375502Bill Wendling // If the operation is with the result of a select instruction, check whether 1432c5f1bc88a2eb7ad9ff924ca90cf88494e5f947b9Bill Wendling // operating on either branch of the select always yields the same value. 1433753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1434753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = ThreadBinOpOverSelect(Instruction::And, Op0, Op1, Q, 1435753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner MaxRecurse)) 1436ef819d0ed8c9df3da633e8c1240e582a7879bb94Eli Friedman return V; 1437a3efbb15ddd5aa9006564cd79086723640084878Jay Foad 1438ef819d0ed8c9df3da633e8c1240e582a7879bb94Eli Friedman // If the operation is with the result of a phi instruction, check whether 1439753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // operating on all incoming values of the phi always yields the same value. 1440753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1441753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = ThreadBinOpOverPHI(Instruction::And, Op0, Op1, Q, 1442753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner MaxRecurse)) 1443a3efbb15ddd5aa9006564cd79086723640084878Jay Foad return V; 1444ef819d0ed8c9df3da633e8c1240e582a7879bb94Eli Friedman 1445753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 1446753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1447753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1448753a2b464d0628231bd3dce645edd05dfbaa3a06Chris LattnerValue *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout *DL, 1449753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const TargetLibraryInfo *TLI, 1450753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DominatorTree *DT) { 1451753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ::SimplifyAndInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 1452753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1453753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1454753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifyOrInst - Given operands for an Or, see if we can 1455f34dc428fa577d6d5d71ab3a1f9765b4e5da5a4fMatt Arsenault/// fold the result. If not, this returns null. 1456a311c34d2af7c750f016ef5e4c41bee77a1dfac7Eli Friedmanstatic Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q, 1457753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner unsigned MaxRecurse) { 1458753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1459753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1460753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 146189d4411cef736898047aa7e3bc159da39cacf8e6Bill Wendling return ConstantFoldInstOperands(Instruction::Or, CLHS->getType(), 1462753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Ops, Q.DL, Q.TLI); 1463753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1464ab215bc371677cdeac6eacb3e890e5af666d1ab4Chris Lattner 1465753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Canonicalize the constant to the RHS. 1466753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner std::swap(Op0, Op1); 1467753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1468753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1469753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X | undef -> -1 1470753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Undef())) 1471753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 1472753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1473753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X | X = X 14743e22cb9ec30cd9b1be9b0f50e400f512124997e5Eli Friedman if (Op0 == Op1) 147536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Op0; 147636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14773e22cb9ec30cd9b1be9b0f50e400f512124997e5Eli Friedman // X | 0 = X 1478753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Zero())) 1479753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 1480753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1481753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // X | -1 = -1 14824a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (match(Op1, m_AllOnes())) 14834a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return Op1; 14844a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 1485753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // A | ~A = ~A | A = -1 14864a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands if (match(Op0, m_Not(m_Specific(Op1))) || 14874a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands match(Op1, m_Not(m_Specific(Op0)))) 14884a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return Constant::getAllOnesValue(Op0->getType()); 1489753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1490db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner // (A & ?) | A = A 1491db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Value *A = nullptr, *B = nullptr; 149299faa3b4ec6d03ac7808fe4ff3fbf3d04e375502Bill Wendling if (match(Op0, m_And(m_Value(A), m_Value(B))) && 1493753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner (A == Op1 || B == Op1)) 1494753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op1; 1495753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 14969d30e7208e6b2bc3fa48305e3ae371188f643425Bill Wendling // A | (A & ?) = A 1497dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (match(Op1, m_And(m_Value(A), m_Value(B))) && 1498753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner (A == Op0 || B == Op0)) 14994a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands return Op0; 15004a544a79bd735967f1d33fe675ae4566dbd17813Duncan Sands 1501753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // ~(A & ?) | A = -1 1502a399781289092fcdceb58b21174229f4373c4191Gabor Greif if (match(Op0, m_Not(m_And(m_Value(A), m_Value(B)))) && 1503db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner (A == Op1 || B == Op1)) 1504db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner return Constant::getAllOnesValue(Op1->getType()); 1505753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 150699faa3b4ec6d03ac7808fe4ff3fbf3d04e375502Bill Wendling // A | ~(A & ?) = -1 1507753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) && 1508753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner (A == Op0 || B == Op0)) 1509dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Constant::getAllOnesValue(Op0->getType()); 151028d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling 1511753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Try some generic simplifications for associative operations. 1512753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = SimplifyAssociativeBinOp(Instruction::Or, Op0, Op1, Q, 1513753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner MaxRecurse)) 1514753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 151528d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling 1516753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Or distributes over And. Try some generic simplifications based on this. 1517753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = ExpandBinOp(Instruction::Or, Op0, Op1, Instruction::And, Q, 1518753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner MaxRecurse)) 1519753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 1520753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1521753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // If the operation is with the result of a select instruction, check whether 1522753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // operating on either branch of the select always yields the same value. 1523753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1)) 1524753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = ThreadBinOpOverSelect(Instruction::Or, Op0, Op1, Q, 15251bde770ccd35b27e0421e54fcdde1f33cdba0f7aMatt Arsenault MaxRecurse)) 1526753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 1527ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling 1528753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // (A & C)|(B & D) 1529753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *C = nullptr, *D = nullptr; 1530753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_And(m_Value(A), m_Value(C))) && 1531753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner match(Op1, m_And(m_Value(B), m_Value(D)))) { 1532753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner ConstantInt *C1 = dyn_cast<ConstantInt>(C); 1533753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner ConstantInt *C2 = dyn_cast<ConstantInt>(D); 15341b0c54f1c5dd61e56cb7cbc435fcb3319cff628fBill Wendling if (C1 && C2 && (C1->getValue() == ~C2->getValue())) { 1535ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling // (A & C1)|(B & C2) 1536ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling // If we have: ((V + N) & C1) | (V & C2) 1537753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // .. and C2 = ~C1 and C2 is 0+1+ and (N & C2) == 0 1538753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // replace with V+N. 1539753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *V1, *V2; 1540753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if ((C2->getValue() & (C2->getValue() + 1)) == 0 && // C2 == 0+1+ 1541753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner match(A, m_Add(m_Value(V1), m_Value(V2)))) { 1542753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Add commutes, try both ways. 1543753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (V1 == B && MaskedValueIsZero(V2, C2->getValue())) 1544cea7ac7c01c6a15eccb2cb7a181df1baf915de0dGabor Greif return A; 1545753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (V2 == B && MaskedValueIsZero(V1, C2->getValue())) 1546e6f364b6c44eda14cd4ad54366ea5cc7246b9500Eli Friedman return A; 1547753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1548ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling // Or commutes, try both ways. 1549ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling if ((C1->getValue() & (C1->getValue() + 1)) == 0 && 1550753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner match(B, m_Add(m_Value(V1), m_Value(V2)))) { 1551753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Add commutes, try both ways. 1552753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (V1 == A && MaskedValueIsZero(V2, C1->getValue())) 1553753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return B; 1554753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (V2 == A && MaskedValueIsZero(V1, C1->getValue())) 1555753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return B; 1556753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 155728d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling } 155828d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling } 1559ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling 1560ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling // If the operation is with the result of a phi instruction, check whether 1561ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling // operating on all incoming values of the phi always yields the same value. 156228d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling if (isa<PHINode>(Op0) || isa<PHINode>(Op1)) 1563753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Value *V = ThreadBinOpOverPHI(Instruction::Or, Op0, Op1, Q, MaxRecurse)) 1564753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return V; 1565753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1566753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 1567753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1568753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1569956f13440a4aa0297606a4412f4aa091d931592aBill WendlingValue *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout *DL, 1570ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling const TargetLibraryInfo *TLI, 1571ac90696722bef3993e5fb9f72a6fa4209bbc8763Bill Wendling const DominatorTree *DT) { 1572753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ::SimplifyOrInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 1573753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1574753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1575753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// SimplifyXorInst - Given operands for a Xor, see if we can 1576753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// fold the result. If not, this returns null. 15775fdd6c8793462549e3593890ec61573da06e3346Jay Foadstatic Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q, 1578753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner unsigned MaxRecurse) { 1579753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *CLHS = dyn_cast<Constant>(Op0)) { 1580753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Constant *CRHS = dyn_cast<Constant>(Op1)) { 1581753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Constant *Ops[] = { CLHS, CRHS }; 1582753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ConstantFoldInstOperands(Instruction::Xor, CLHS->getType(), 1583753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Ops, Q.DL, Q.TLI); 1584753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1585753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1586753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Canonicalize the constant to the RHS. 1587753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner std::swap(Op0, Op1); 1588753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner } 1589753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1590753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // A ^ undef -> undef 1591753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Undef())) 1592753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op1; 1593753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1594753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // A ^ 0 = A 1595753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op1, m_Zero())) 1596753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Op0; 1597753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1598753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // A ^ A = 0 1599753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (Op0 == Op1) 1600753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getNullValue(Op0->getType()); 1601753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1602753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // A ^ ~A = ~A ^ A = -1 1603753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (match(Op0, m_Not(m_Specific(Op1))) || 160400e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach match(Op1, m_Not(m_Specific(Op0)))) 1605753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return Constant::getAllOnesValue(Op0->getType()); 1606753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1607753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Try some generic simplifications for associative operations. 160800e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbach if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q, 1609753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner MaxRecurse)) 161003fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach return V; 161103fceff6f69a0261a767aab8e62de8aa9301b86cJim Grosbach 1612753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Threading Xor over selects and phi nodes is pointless, so don't bother. 1613753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // Threading over the select in "A ^ select(cond, B, C)" means evaluating 1614753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // "A^B" and "A^C" and seeing if they are equal; but they are equal if and 1615753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // only if B and C are equal. If B and C are equal then (since we assume 1616753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // that operands have already been simplified) "select(cond, B, C)" should 1617a3efbb15ddd5aa9006564cd79086723640084878Jay Foad // have been simplified to the common value of B and C already. Analysing 1618753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // "A^B" and "A^C" thus gains nothing, but costs compile time. Similarly 1619753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner // for threading over phi nodes. 1620753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1621a3efbb15ddd5aa9006564cd79086723640084878Jay Foad return nullptr; 1622753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1623753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1624753a2b464d0628231bd3dce645edd05dfbaa3a06Chris LattnerValue *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout *DL, 1625753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const TargetLibraryInfo *TLI, 1626753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner const DominatorTree *DT) { 1627753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return ::SimplifyXorInst(Op0, Op1, Query (DL, TLI, DT), RecursionLimit); 162859f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman} 162959f15918c28ad340bb9f0ef78e43c2952a5b5c1cEli Friedman 1630753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattnerstatic Type *GetCompareTy(Value *Op) { 1631753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return CmpInst::makeCmpResultType(Op->getType()); 1632753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner} 1633753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner 1634753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// ExtractEquivalentCondition - Rummage around inside V looking for something 1635753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// equivalent to the comparison "LHS Pred RHS". Return such a value if found, 1636753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner/// otherwise return null. Helper function for analyzing max/min idioms. 163700e403abe384b8f61dd012242d3d81a23541ca25Jim Grosbachstatic Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, 1638753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner Value *LHS, Value *RHS) { 1639753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner SelectInst *SI = dyn_cast<SelectInst>(V); 1640753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner if (!SI) 1641753a2b464d0628231bd3dce645edd05dfbaa3a06Chris Lattner return nullptr; 1642 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition()); 1643 if (!Cmp) 1644 return nullptr; 1645 Value *CmpLHS = Cmp->getOperand(0), *CmpRHS = Cmp->getOperand(1); 1646 if (Pred == Cmp->getPredicate() && LHS == CmpLHS && RHS == CmpRHS) 1647 return Cmp; 1648 if (Pred == CmpInst::getSwappedPredicate(Cmp->getPredicate()) && 1649 LHS == CmpRHS && RHS == CmpLHS) 1650 return Cmp; 1651 return nullptr; 1652} 1653 1654// A significant optimization not implemented here is assuming that alloca 1655// addresses are not equal to incoming argument values. They don't *alias*, 1656// as we say, but that doesn't mean they aren't equal, so we take a 1657// conservative approach. 1658// 1659// This is inspired in part by C++11 5.10p1: 1660// "Two pointers of the same type compare equal if and only if they are both 1661// null, both point to the same function, or both represent the same 1662// address." 1663// 1664// This is pretty permissive. 1665// 1666// It's also partly due to C11 6.5.9p6: 1667// "Two pointers compare equal if and only if both are null pointers, both are 1668// pointers to the same object (including a pointer to an object and a 1669// subobject at its beginning) or function, both are pointers to one past the 1670// last element of the same array object, or one is a pointer to one past the 1671// end of one array object and the other is a pointer to the start of a 1672// different array object that happens to immediately follow the first array 1673// object in the address space.) 1674// 1675// C11's version is more restrictive, however there's no reason why an argument 1676// couldn't be a one-past-the-end value for a stack object in the caller and be 1677// equal to the beginning of a stack object in the callee. 1678// 1679// If the C and C++ standards are ever made sufficiently restrictive in this 1680// area, it may be possible to update LLVM's semantics accordingly and reinstate 1681// this optimization. 1682static Constant *computePointerICmp(const DataLayout *DL, 1683 const TargetLibraryInfo *TLI, 1684 CmpInst::Predicate Pred, 1685 Value *LHS, Value *RHS) { 1686 // First, skip past any trivial no-ops. 1687 LHS = LHS->stripPointerCasts(); 1688 RHS = RHS->stripPointerCasts(); 1689 1690 // A non-null pointer is not equal to a null pointer. 1691 if (llvm::isKnownNonNull(LHS, TLI) && isa<ConstantPointerNull>(RHS) && 1692 (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE)) 1693 return ConstantInt::get(GetCompareTy(LHS), 1694 !CmpInst::isTrueWhenEqual(Pred)); 1695 1696 // We can only fold certain predicates on pointer comparisons. 1697 switch (Pred) { 1698 default: 1699 return nullptr; 1700 1701 // Equality comaprisons are easy to fold. 1702 case CmpInst::ICMP_EQ: 1703 case CmpInst::ICMP_NE: 1704 break; 1705 1706 // We can only handle unsigned relational comparisons because 'inbounds' on 1707 // a GEP only protects against unsigned wrapping. 1708 case CmpInst::ICMP_UGT: 1709 case CmpInst::ICMP_UGE: 1710 case CmpInst::ICMP_ULT: 1711 case CmpInst::ICMP_ULE: 1712 // However, we have to switch them to their signed variants to handle 1713 // negative indices from the base pointer. 1714 Pred = ICmpInst::getSignedPredicate(Pred); 1715 break; 1716 } 1717 1718 // Strip off any constant offsets so that we can reason about them. 1719 // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets 1720 // here and compare base addresses like AliasAnalysis does, however there are 1721 // numerous hazards. AliasAnalysis and its utilities rely on special rules 1722 // governing loads and stores which don't apply to icmps. Also, AliasAnalysis 1723 // doesn't need to guarantee pointer inequality when it says NoAlias. 1724 Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS); 1725 Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS); 1726 1727 // If LHS and RHS are related via constant offsets to the same base 1728 // value, we can replace it with an icmp which just compares the offsets. 1729 if (LHS == RHS) 1730 return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset); 1731 1732 // Various optimizations for (in)equality comparisons. 1733 if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) { 1734 // Different non-empty allocations that exist at the same time have 1735 // different addresses (if the program can tell). Global variables always 1736 // exist, so they always exist during the lifetime of each other and all 1737 // allocas. Two different allocas usually have different addresses... 1738 // 1739 // However, if there's an @llvm.stackrestore dynamically in between two 1740 // allocas, they may have the same address. It's tempting to reduce the 1741 // scope of the problem by only looking at *static* allocas here. That would 1742 // cover the majority of allocas while significantly reducing the likelihood 1743 // of having an @llvm.stackrestore pop up in the middle. However, it's not 1744 // actually impossible for an @llvm.stackrestore to pop up in the middle of 1745 // an entry block. Also, if we have a block that's not attached to a 1746 // function, we can't tell if it's "static" under the current definition. 1747 // Theoretically, this problem could be fixed by creating a new kind of 1748 // instruction kind specifically for static allocas. Such a new instruction 1749 // could be required to be at the top of the entry block, thus preventing it 1750 // from being subject to a @llvm.stackrestore. Instcombine could even 1751 // convert regular allocas into these special allocas. It'd be nifty. 1752 // However, until then, this problem remains open. 1753 // 1754 // So, we'll assume that two non-empty allocas have different addresses 1755 // for now. 1756 // 1757 // With all that, if the offsets are within the bounds of their allocations 1758 // (and not one-past-the-end! so we can't use inbounds!), and their 1759 // allocations aren't the same, the pointers are not equal. 1760 // 1761 // Note that it's not necessary to check for LHS being a global variable 1762 // address, due to canonicalization and constant folding. 1763 if (isa<AllocaInst>(LHS) && 1764 (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) { 1765 ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset); 1766 ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(RHSOffset); 1767 uint64_t LHSSize, RHSSize; 1768 if (LHSOffsetCI && RHSOffsetCI && 1769 getObjectSize(LHS, LHSSize, DL, TLI) && 1770 getObjectSize(RHS, RHSSize, DL, TLI)) { 1771 const APInt &LHSOffsetValue = LHSOffsetCI->getValue(); 1772 const APInt &RHSOffsetValue = RHSOffsetCI->getValue(); 1773 if (!LHSOffsetValue.isNegative() && 1774 !RHSOffsetValue.isNegative() && 1775 LHSOffsetValue.ult(LHSSize) && 1776 RHSOffsetValue.ult(RHSSize)) { 1777 return ConstantInt::get(GetCompareTy(LHS), 1778 !CmpInst::isTrueWhenEqual(Pred)); 1779 } 1780 } 1781 1782 // Repeat the above check but this time without depending on DataLayout 1783 // or being able to compute a precise size. 1784 if (!cast<PointerType>(LHS->getType())->isEmptyTy() && 1785 !cast<PointerType>(RHS->getType())->isEmptyTy() && 1786 LHSOffset->isNullValue() && 1787 RHSOffset->isNullValue()) 1788 return ConstantInt::get(GetCompareTy(LHS), 1789 !CmpInst::isTrueWhenEqual(Pred)); 1790 } 1791 1792 // Even if an non-inbounds GEP occurs along the path we can still optimize 1793 // equality comparisons concerning the result. We avoid walking the whole 1794 // chain again by starting where the last calls to 1795 // stripAndComputeConstantOffsets left off and accumulate the offsets. 1796 Constant *LHSNoBound = stripAndComputeConstantOffsets(DL, LHS, true); 1797 Constant *RHSNoBound = stripAndComputeConstantOffsets(DL, RHS, true); 1798 if (LHS == RHS) 1799 return ConstantExpr::getICmp(Pred, 1800 ConstantExpr::getAdd(LHSOffset, LHSNoBound), 1801 ConstantExpr::getAdd(RHSOffset, RHSNoBound)); 1802 } 1803 1804 // Otherwise, fail. 1805 return nullptr; 1806} 1807 1808/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can 1809/// fold the result. If not, this returns null. 1810static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 1811 const Query &Q, unsigned MaxRecurse) { 1812 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 1813 assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!"); 1814 1815 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 1816 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1817 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); 1818 1819 // If we have a constant, make sure it is on the RHS. 1820 std::swap(LHS, RHS); 1821 Pred = CmpInst::getSwappedPredicate(Pred); 1822 } 1823 1824 Type *ITy = GetCompareTy(LHS); // The return type. 1825 Type *OpTy = LHS->getType(); // The operand type. 1826 1827 // icmp X, X -> true/false 1828 // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false 1829 // because X could be 0. 1830 if (LHS == RHS || isa<UndefValue>(RHS)) 1831 return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred)); 1832 1833 // Special case logic when the operands have i1 type. 1834 if (OpTy->getScalarType()->isIntegerTy(1)) { 1835 switch (Pred) { 1836 default: break; 1837 case ICmpInst::ICMP_EQ: 1838 // X == 1 -> X 1839 if (match(RHS, m_One())) 1840 return LHS; 1841 break; 1842 case ICmpInst::ICMP_NE: 1843 // X != 0 -> X 1844 if (match(RHS, m_Zero())) 1845 return LHS; 1846 break; 1847 case ICmpInst::ICMP_UGT: 1848 // X >u 0 -> X 1849 if (match(RHS, m_Zero())) 1850 return LHS; 1851 break; 1852 case ICmpInst::ICMP_UGE: 1853 // X >=u 1 -> X 1854 if (match(RHS, m_One())) 1855 return LHS; 1856 break; 1857 case ICmpInst::ICMP_SLT: 1858 // X <s 0 -> X 1859 if (match(RHS, m_Zero())) 1860 return LHS; 1861 break; 1862 case ICmpInst::ICMP_SLE: 1863 // X <=s -1 -> X 1864 if (match(RHS, m_One())) 1865 return LHS; 1866 break; 1867 } 1868 } 1869 1870 // If we are comparing with zero then try hard since this is a common case. 1871 if (match(RHS, m_Zero())) { 1872 bool LHSKnownNonNegative, LHSKnownNegative; 1873 switch (Pred) { 1874 default: llvm_unreachable("Unknown ICmp predicate!"); 1875 case ICmpInst::ICMP_ULT: 1876 return getFalse(ITy); 1877 case ICmpInst::ICMP_UGE: 1878 return getTrue(ITy); 1879 case ICmpInst::ICMP_EQ: 1880 case ICmpInst::ICMP_ULE: 1881 if (isKnownNonZero(LHS, Q.DL)) 1882 return getFalse(ITy); 1883 break; 1884 case ICmpInst::ICMP_NE: 1885 case ICmpInst::ICMP_UGT: 1886 if (isKnownNonZero(LHS, Q.DL)) 1887 return getTrue(ITy); 1888 break; 1889 case ICmpInst::ICMP_SLT: 1890 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL); 1891 if (LHSKnownNegative) 1892 return getTrue(ITy); 1893 if (LHSKnownNonNegative) 1894 return getFalse(ITy); 1895 break; 1896 case ICmpInst::ICMP_SLE: 1897 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL); 1898 if (LHSKnownNegative) 1899 return getTrue(ITy); 1900 if (LHSKnownNonNegative && isKnownNonZero(LHS, Q.DL)) 1901 return getFalse(ITy); 1902 break; 1903 case ICmpInst::ICMP_SGE: 1904 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL); 1905 if (LHSKnownNegative) 1906 return getFalse(ITy); 1907 if (LHSKnownNonNegative) 1908 return getTrue(ITy); 1909 break; 1910 case ICmpInst::ICMP_SGT: 1911 ComputeSignBit(LHS, LHSKnownNonNegative, LHSKnownNegative, Q.DL); 1912 if (LHSKnownNegative) 1913 return getFalse(ITy); 1914 if (LHSKnownNonNegative && isKnownNonZero(LHS, Q.DL)) 1915 return getTrue(ITy); 1916 break; 1917 } 1918 } 1919 1920 // See if we are doing a comparison with a constant integer. 1921 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 1922 // Rule out tautological comparisons (eg., ult 0 or uge 0). 1923 ConstantRange RHS_CR = ICmpInst::makeConstantRange(Pred, CI->getValue()); 1924 if (RHS_CR.isEmptySet()) 1925 return ConstantInt::getFalse(CI->getContext()); 1926 if (RHS_CR.isFullSet()) 1927 return ConstantInt::getTrue(CI->getContext()); 1928 1929 // Many binary operators with constant RHS have easy to compute constant 1930 // range. Use them to check whether the comparison is a tautology. 1931 unsigned Width = CI->getBitWidth(); 1932 APInt Lower = APInt(Width, 0); 1933 APInt Upper = APInt(Width, 0); 1934 ConstantInt *CI2; 1935 if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) { 1936 // 'urem x, CI2' produces [0, CI2). 1937 Upper = CI2->getValue(); 1938 } else if (match(LHS, m_SRem(m_Value(), m_ConstantInt(CI2)))) { 1939 // 'srem x, CI2' produces (-|CI2|, |CI2|). 1940 Upper = CI2->getValue().abs(); 1941 Lower = (-Upper) + 1; 1942 } else if (match(LHS, m_UDiv(m_ConstantInt(CI2), m_Value()))) { 1943 // 'udiv CI2, x' produces [0, CI2]. 1944 Upper = CI2->getValue() + 1; 1945 } else if (match(LHS, m_UDiv(m_Value(), m_ConstantInt(CI2)))) { 1946 // 'udiv x, CI2' produces [0, UINT_MAX / CI2]. 1947 APInt NegOne = APInt::getAllOnesValue(Width); 1948 if (!CI2->isZero()) 1949 Upper = NegOne.udiv(CI2->getValue()) + 1; 1950 } else if (match(LHS, m_SDiv(m_ConstantInt(CI2), m_Value()))) { 1951 if (CI2->isMinSignedValue()) { 1952 // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2]. 1953 Lower = CI2->getValue(); 1954 Upper = Lower.lshr(1) + 1; 1955 } else { 1956 // 'sdiv CI2, x' produces [-|CI2|, |CI2|]. 1957 Upper = CI2->getValue().abs() + 1; 1958 Lower = (-Upper) + 1; 1959 } 1960 } else if (match(LHS, m_SDiv(m_Value(), m_ConstantInt(CI2)))) { 1961 // 'sdiv x, CI2' produces [INT_MIN / CI2, INT_MAX / CI2]. 1962 APInt IntMin = APInt::getSignedMinValue(Width); 1963 APInt IntMax = APInt::getSignedMaxValue(Width); 1964 APInt Val = CI2->getValue().abs(); 1965 if (!Val.isMinValue()) { 1966 Lower = IntMin.sdiv(Val); 1967 Upper = IntMax.sdiv(Val) + 1; 1968 } 1969 } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) { 1970 // 'lshr x, CI2' produces [0, UINT_MAX >> CI2]. 1971 APInt NegOne = APInt::getAllOnesValue(Width); 1972 if (CI2->getValue().ult(Width)) 1973 Upper = NegOne.lshr(CI2->getValue()) + 1; 1974 } else if (match(LHS, m_LShr(m_ConstantInt(CI2), m_Value()))) { 1975 // 'lshr CI2, x' produces [CI2 >> (Width-1), CI2]. 1976 unsigned ShiftAmount = Width - 1; 1977 if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact()) 1978 ShiftAmount = CI2->getValue().countTrailingZeros(); 1979 Lower = CI2->getValue().lshr(ShiftAmount); 1980 Upper = CI2->getValue() + 1; 1981 } else if (match(LHS, m_AShr(m_Value(), m_ConstantInt(CI2)))) { 1982 // 'ashr x, CI2' produces [INT_MIN >> CI2, INT_MAX >> CI2]. 1983 APInt IntMin = APInt::getSignedMinValue(Width); 1984 APInt IntMax = APInt::getSignedMaxValue(Width); 1985 if (CI2->getValue().ult(Width)) { 1986 Lower = IntMin.ashr(CI2->getValue()); 1987 Upper = IntMax.ashr(CI2->getValue()) + 1; 1988 } 1989 } else if (match(LHS, m_AShr(m_ConstantInt(CI2), m_Value()))) { 1990 unsigned ShiftAmount = Width - 1; 1991 if (!CI2->isZero() && cast<BinaryOperator>(LHS)->isExact()) 1992 ShiftAmount = CI2->getValue().countTrailingZeros(); 1993 if (CI2->isNegative()) { 1994 // 'ashr CI2, x' produces [CI2, CI2 >> (Width-1)] 1995 Lower = CI2->getValue(); 1996 Upper = CI2->getValue().ashr(ShiftAmount) + 1; 1997 } else { 1998 // 'ashr CI2, x' produces [CI2 >> (Width-1), CI2] 1999 Lower = CI2->getValue().ashr(ShiftAmount); 2000 Upper = CI2->getValue() + 1; 2001 } 2002 } else if (match(LHS, m_Or(m_Value(), m_ConstantInt(CI2)))) { 2003 // 'or x, CI2' produces [CI2, UINT_MAX]. 2004 Lower = CI2->getValue(); 2005 } else if (match(LHS, m_And(m_Value(), m_ConstantInt(CI2)))) { 2006 // 'and x, CI2' produces [0, CI2]. 2007 Upper = CI2->getValue() + 1; 2008 } 2009 if (Lower != Upper) { 2010 ConstantRange LHS_CR = ConstantRange(Lower, Upper); 2011 if (RHS_CR.contains(LHS_CR)) 2012 return ConstantInt::getTrue(RHS->getContext()); 2013 if (RHS_CR.inverse().contains(LHS_CR)) 2014 return ConstantInt::getFalse(RHS->getContext()); 2015 } 2016 } 2017 2018 // Compare of cast, for example (zext X) != 0 -> X != 0 2019 if (isa<CastInst>(LHS) && (isa<Constant>(RHS) || isa<CastInst>(RHS))) { 2020 Instruction *LI = cast<CastInst>(LHS); 2021 Value *SrcOp = LI->getOperand(0); 2022 Type *SrcTy = SrcOp->getType(); 2023 Type *DstTy = LI->getType(); 2024 2025 // Turn icmp (ptrtoint x), (ptrtoint/constant) into a compare of the input 2026 // if the integer type is the same size as the pointer type. 2027 if (MaxRecurse && Q.DL && isa<PtrToIntInst>(LI) && 2028 Q.DL->getTypeSizeInBits(SrcTy) == DstTy->getPrimitiveSizeInBits()) { 2029 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 2030 // Transfer the cast to the constant. 2031 if (Value *V = SimplifyICmpInst(Pred, SrcOp, 2032 ConstantExpr::getIntToPtr(RHSC, SrcTy), 2033 Q, MaxRecurse-1)) 2034 return V; 2035 } else if (PtrToIntInst *RI = dyn_cast<PtrToIntInst>(RHS)) { 2036 if (RI->getOperand(0)->getType() == SrcTy) 2037 // Compare without the cast. 2038 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 2039 Q, MaxRecurse-1)) 2040 return V; 2041 } 2042 } 2043 2044 if (isa<ZExtInst>(LHS)) { 2045 // Turn icmp (zext X), (zext Y) into a compare of X and Y if they have the 2046 // same type. 2047 if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) { 2048 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 2049 // Compare X and Y. Note that signed predicates become unsigned. 2050 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 2051 SrcOp, RI->getOperand(0), Q, 2052 MaxRecurse-1)) 2053 return V; 2054 } 2055 // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended 2056 // too. If not, then try to deduce the result of the comparison. 2057 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2058 // Compute the constant that would happen if we truncated to SrcTy then 2059 // reextended to DstTy. 2060 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 2061 Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy); 2062 2063 // If the re-extended constant didn't change then this is effectively 2064 // also a case of comparing two zero-extended values. 2065 if (RExt == CI && MaxRecurse) 2066 if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred), 2067 SrcOp, Trunc, Q, MaxRecurse-1)) 2068 return V; 2069 2070 // Otherwise the upper bits of LHS are zero while RHS has a non-zero bit 2071 // there. Use this to work out the result of the comparison. 2072 if (RExt != CI) { 2073 switch (Pred) { 2074 default: llvm_unreachable("Unknown ICmp predicate!"); 2075 // LHS <u RHS. 2076 case ICmpInst::ICMP_EQ: 2077 case ICmpInst::ICMP_UGT: 2078 case ICmpInst::ICMP_UGE: 2079 return ConstantInt::getFalse(CI->getContext()); 2080 2081 case ICmpInst::ICMP_NE: 2082 case ICmpInst::ICMP_ULT: 2083 case ICmpInst::ICMP_ULE: 2084 return ConstantInt::getTrue(CI->getContext()); 2085 2086 // LHS is non-negative. If RHS is negative then LHS >s LHS. If RHS 2087 // is non-negative then LHS <s RHS. 2088 case ICmpInst::ICMP_SGT: 2089 case ICmpInst::ICMP_SGE: 2090 return CI->getValue().isNegative() ? 2091 ConstantInt::getTrue(CI->getContext()) : 2092 ConstantInt::getFalse(CI->getContext()); 2093 2094 case ICmpInst::ICMP_SLT: 2095 case ICmpInst::ICMP_SLE: 2096 return CI->getValue().isNegative() ? 2097 ConstantInt::getFalse(CI->getContext()) : 2098 ConstantInt::getTrue(CI->getContext()); 2099 } 2100 } 2101 } 2102 } 2103 2104 if (isa<SExtInst>(LHS)) { 2105 // Turn icmp (sext X), (sext Y) into a compare of X and Y if they have the 2106 // same type. 2107 if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) { 2108 if (MaxRecurse && SrcTy == RI->getOperand(0)->getType()) 2109 // Compare X and Y. Note that the predicate does not change. 2110 if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0), 2111 Q, MaxRecurse-1)) 2112 return V; 2113 } 2114 // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended 2115 // too. If not, then try to deduce the result of the comparison. 2116 else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2117 // Compute the constant that would happen if we truncated to SrcTy then 2118 // reextended to DstTy. 2119 Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy); 2120 Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy); 2121 2122 // If the re-extended constant didn't change then this is effectively 2123 // also a case of comparing two sign-extended values. 2124 if (RExt == CI && MaxRecurse) 2125 if (Value *V = SimplifyICmpInst(Pred, SrcOp, Trunc, Q, MaxRecurse-1)) 2126 return V; 2127 2128 // Otherwise the upper bits of LHS are all equal, while RHS has varying 2129 // bits there. Use this to work out the result of the comparison. 2130 if (RExt != CI) { 2131 switch (Pred) { 2132 default: llvm_unreachable("Unknown ICmp predicate!"); 2133 case ICmpInst::ICMP_EQ: 2134 return ConstantInt::getFalse(CI->getContext()); 2135 case ICmpInst::ICMP_NE: 2136 return ConstantInt::getTrue(CI->getContext()); 2137 2138 // If RHS is non-negative then LHS <s RHS. If RHS is negative then 2139 // LHS >s RHS. 2140 case ICmpInst::ICMP_SGT: 2141 case ICmpInst::ICMP_SGE: 2142 return CI->getValue().isNegative() ? 2143 ConstantInt::getTrue(CI->getContext()) : 2144 ConstantInt::getFalse(CI->getContext()); 2145 case ICmpInst::ICMP_SLT: 2146 case ICmpInst::ICMP_SLE: 2147 return CI->getValue().isNegative() ? 2148 ConstantInt::getFalse(CI->getContext()) : 2149 ConstantInt::getTrue(CI->getContext()); 2150 2151 // If LHS is non-negative then LHS <u RHS. If LHS is negative then 2152 // LHS >u RHS. 2153 case ICmpInst::ICMP_UGT: 2154 case ICmpInst::ICMP_UGE: 2155 // Comparison is true iff the LHS <s 0. 2156 if (MaxRecurse) 2157 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SLT, SrcOp, 2158 Constant::getNullValue(SrcTy), 2159 Q, MaxRecurse-1)) 2160 return V; 2161 break; 2162 case ICmpInst::ICMP_ULT: 2163 case ICmpInst::ICMP_ULE: 2164 // Comparison is true iff the LHS >=s 0. 2165 if (MaxRecurse) 2166 if (Value *V = SimplifyICmpInst(ICmpInst::ICMP_SGE, SrcOp, 2167 Constant::getNullValue(SrcTy), 2168 Q, MaxRecurse-1)) 2169 return V; 2170 break; 2171 } 2172 } 2173 } 2174 } 2175 } 2176 2177 // If a bit is known to be zero for A and known to be one for B, 2178 // then A and B cannot be equal. 2179 if (ICmpInst::isEquality(Pred)) { 2180 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) { 2181 uint32_t BitWidth = CI->getBitWidth(); 2182 APInt LHSKnownZero(BitWidth, 0); 2183 APInt LHSKnownOne(BitWidth, 0); 2184 computeKnownBits(LHS, LHSKnownZero, LHSKnownOne); 2185 APInt RHSKnownZero(BitWidth, 0); 2186 APInt RHSKnownOne(BitWidth, 0); 2187 computeKnownBits(RHS, RHSKnownZero, RHSKnownOne); 2188 if (((LHSKnownOne & RHSKnownZero) != 0) || 2189 ((LHSKnownZero & RHSKnownOne) != 0)) 2190 return (Pred == ICmpInst::ICMP_EQ) 2191 ? ConstantInt::getFalse(CI->getContext()) 2192 : ConstantInt::getTrue(CI->getContext()); 2193 } 2194 } 2195 2196 // Special logic for binary operators. 2197 BinaryOperator *LBO = dyn_cast<BinaryOperator>(LHS); 2198 BinaryOperator *RBO = dyn_cast<BinaryOperator>(RHS); 2199 if (MaxRecurse && (LBO || RBO)) { 2200 // Analyze the case when either LHS or RHS is an add instruction. 2201 Value *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr; 2202 // LHS = A + B (or A and B are null); RHS = C + D (or C and D are null). 2203 bool NoLHSWrapProblem = false, NoRHSWrapProblem = false; 2204 if (LBO && LBO->getOpcode() == Instruction::Add) { 2205 A = LBO->getOperand(0); B = LBO->getOperand(1); 2206 NoLHSWrapProblem = ICmpInst::isEquality(Pred) || 2207 (CmpInst::isUnsigned(Pred) && LBO->hasNoUnsignedWrap()) || 2208 (CmpInst::isSigned(Pred) && LBO->hasNoSignedWrap()); 2209 } 2210 if (RBO && RBO->getOpcode() == Instruction::Add) { 2211 C = RBO->getOperand(0); D = RBO->getOperand(1); 2212 NoRHSWrapProblem = ICmpInst::isEquality(Pred) || 2213 (CmpInst::isUnsigned(Pred) && RBO->hasNoUnsignedWrap()) || 2214 (CmpInst::isSigned(Pred) && RBO->hasNoSignedWrap()); 2215 } 2216 2217 // icmp (X+Y), X -> icmp Y, 0 for equalities or if there is no overflow. 2218 if ((A == RHS || B == RHS) && NoLHSWrapProblem) 2219 if (Value *V = SimplifyICmpInst(Pred, A == RHS ? B : A, 2220 Constant::getNullValue(RHS->getType()), 2221 Q, MaxRecurse-1)) 2222 return V; 2223 2224 // icmp X, (X+Y) -> icmp 0, Y for equalities or if there is no overflow. 2225 if ((C == LHS || D == LHS) && NoRHSWrapProblem) 2226 if (Value *V = SimplifyICmpInst(Pred, 2227 Constant::getNullValue(LHS->getType()), 2228 C == LHS ? D : C, Q, MaxRecurse-1)) 2229 return V; 2230 2231 // icmp (X+Y), (X+Z) -> icmp Y,Z for equalities or if there is no overflow. 2232 if (A && C && (A == C || A == D || B == C || B == D) && 2233 NoLHSWrapProblem && NoRHSWrapProblem) { 2234 // Determine Y and Z in the form icmp (X+Y), (X+Z). 2235 Value *Y, *Z; 2236 if (A == C) { 2237 // C + B == C + D -> B == D 2238 Y = B; 2239 Z = D; 2240 } else if (A == D) { 2241 // D + B == C + D -> B == C 2242 Y = B; 2243 Z = C; 2244 } else if (B == C) { 2245 // A + C == C + D -> A == D 2246 Y = A; 2247 Z = D; 2248 } else { 2249 assert(B == D); 2250 // A + D == C + D -> A == C 2251 Y = A; 2252 Z = C; 2253 } 2254 if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1)) 2255 return V; 2256 } 2257 } 2258 2259 // 0 - (zext X) pred C 2260 if (!CmpInst::isUnsigned(Pred) && match(LHS, m_Neg(m_ZExt(m_Value())))) { 2261 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) { 2262 if (RHSC->getValue().isStrictlyPositive()) { 2263 if (Pred == ICmpInst::ICMP_SLT) 2264 return ConstantInt::getTrue(RHSC->getContext()); 2265 if (Pred == ICmpInst::ICMP_SGE) 2266 return ConstantInt::getFalse(RHSC->getContext()); 2267 if (Pred == ICmpInst::ICMP_EQ) 2268 return ConstantInt::getFalse(RHSC->getContext()); 2269 if (Pred == ICmpInst::ICMP_NE) 2270 return ConstantInt::getTrue(RHSC->getContext()); 2271 } 2272 if (RHSC->getValue().isNonNegative()) { 2273 if (Pred == ICmpInst::ICMP_SLE) 2274 return ConstantInt::getTrue(RHSC->getContext()); 2275 if (Pred == ICmpInst::ICMP_SGT) 2276 return ConstantInt::getFalse(RHSC->getContext()); 2277 } 2278 } 2279 } 2280 2281 // icmp pred (urem X, Y), Y 2282 if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) { 2283 bool KnownNonNegative, KnownNegative; 2284 switch (Pred) { 2285 default: 2286 break; 2287 case ICmpInst::ICMP_SGT: 2288 case ICmpInst::ICMP_SGE: 2289 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL); 2290 if (!KnownNonNegative) 2291 break; 2292 // fall-through 2293 case ICmpInst::ICMP_EQ: 2294 case ICmpInst::ICMP_UGT: 2295 case ICmpInst::ICMP_UGE: 2296 return getFalse(ITy); 2297 case ICmpInst::ICMP_SLT: 2298 case ICmpInst::ICMP_SLE: 2299 ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.DL); 2300 if (!KnownNonNegative) 2301 break; 2302 // fall-through 2303 case ICmpInst::ICMP_NE: 2304 case ICmpInst::ICMP_ULT: 2305 case ICmpInst::ICMP_ULE: 2306 return getTrue(ITy); 2307 } 2308 } 2309 2310 // icmp pred X, (urem Y, X) 2311 if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) { 2312 bool KnownNonNegative, KnownNegative; 2313 switch (Pred) { 2314 default: 2315 break; 2316 case ICmpInst::ICMP_SGT: 2317 case ICmpInst::ICMP_SGE: 2318 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL); 2319 if (!KnownNonNegative) 2320 break; 2321 // fall-through 2322 case ICmpInst::ICMP_NE: 2323 case ICmpInst::ICMP_UGT: 2324 case ICmpInst::ICMP_UGE: 2325 return getTrue(ITy); 2326 case ICmpInst::ICMP_SLT: 2327 case ICmpInst::ICMP_SLE: 2328 ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.DL); 2329 if (!KnownNonNegative) 2330 break; 2331 // fall-through 2332 case ICmpInst::ICMP_EQ: 2333 case ICmpInst::ICMP_ULT: 2334 case ICmpInst::ICMP_ULE: 2335 return getFalse(ITy); 2336 } 2337 } 2338 2339 // x udiv y <=u x. 2340 if (LBO && match(LBO, m_UDiv(m_Specific(RHS), m_Value()))) { 2341 // icmp pred (X /u Y), X 2342 if (Pred == ICmpInst::ICMP_UGT) 2343 return getFalse(ITy); 2344 if (Pred == ICmpInst::ICMP_ULE) 2345 return getTrue(ITy); 2346 } 2347 2348 if (MaxRecurse && LBO && RBO && LBO->getOpcode() == RBO->getOpcode() && 2349 LBO->getOperand(1) == RBO->getOperand(1)) { 2350 switch (LBO->getOpcode()) { 2351 default: break; 2352 case Instruction::UDiv: 2353 case Instruction::LShr: 2354 if (ICmpInst::isSigned(Pred)) 2355 break; 2356 // fall-through 2357 case Instruction::SDiv: 2358 case Instruction::AShr: 2359 if (!LBO->isExact() || !RBO->isExact()) 2360 break; 2361 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2362 RBO->getOperand(0), Q, MaxRecurse-1)) 2363 return V; 2364 break; 2365 case Instruction::Shl: { 2366 bool NUW = LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap(); 2367 bool NSW = LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap(); 2368 if (!NUW && !NSW) 2369 break; 2370 if (!NSW && ICmpInst::isSigned(Pred)) 2371 break; 2372 if (Value *V = SimplifyICmpInst(Pred, LBO->getOperand(0), 2373 RBO->getOperand(0), Q, MaxRecurse-1)) 2374 return V; 2375 break; 2376 } 2377 } 2378 } 2379 2380 // Simplify comparisons involving max/min. 2381 Value *A, *B; 2382 CmpInst::Predicate P = CmpInst::BAD_ICMP_PREDICATE; 2383 CmpInst::Predicate EqP; // Chosen so that "A == max/min(A,B)" iff "A EqP B". 2384 2385 // Signed variants on "max(a,b)>=a -> true". 2386 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2387 if (A != RHS) std::swap(A, B); // smax(A, B) pred A. 2388 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2389 // We analyze this as smax(A, B) pred A. 2390 P = Pred; 2391 } else if (match(RHS, m_SMax(m_Value(A), m_Value(B))) && 2392 (A == LHS || B == LHS)) { 2393 if (A != LHS) std::swap(A, B); // A pred smax(A, B). 2394 EqP = CmpInst::ICMP_SGE; // "A == smax(A, B)" iff "A sge B". 2395 // We analyze this as smax(A, B) swapped-pred A. 2396 P = CmpInst::getSwappedPredicate(Pred); 2397 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2398 (A == RHS || B == RHS)) { 2399 if (A != RHS) std::swap(A, B); // smin(A, B) pred A. 2400 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2401 // We analyze this as smax(-A, -B) swapped-pred -A. 2402 // Note that we do not need to actually form -A or -B thanks to EqP. 2403 P = CmpInst::getSwappedPredicate(Pred); 2404 } else if (match(RHS, m_SMin(m_Value(A), m_Value(B))) && 2405 (A == LHS || B == LHS)) { 2406 if (A != LHS) std::swap(A, B); // A pred smin(A, B). 2407 EqP = CmpInst::ICMP_SLE; // "A == smin(A, B)" iff "A sle B". 2408 // We analyze this as smax(-A, -B) pred -A. 2409 // Note that we do not need to actually form -A or -B thanks to EqP. 2410 P = Pred; 2411 } 2412 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2413 // Cases correspond to "max(A, B) p A". 2414 switch (P) { 2415 default: 2416 break; 2417 case CmpInst::ICMP_EQ: 2418 case CmpInst::ICMP_SLE: 2419 // Equivalent to "A EqP B". This may be the same as the condition tested 2420 // in the max/min; if so, we can just return that. 2421 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2422 return V; 2423 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2424 return V; 2425 // Otherwise, see if "A EqP B" simplifies. 2426 if (MaxRecurse) 2427 if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1)) 2428 return V; 2429 break; 2430 case CmpInst::ICMP_NE: 2431 case CmpInst::ICMP_SGT: { 2432 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2433 // Equivalent to "A InvEqP B". This may be the same as the condition 2434 // tested in the max/min; if so, we can just return that. 2435 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2436 return V; 2437 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2438 return V; 2439 // Otherwise, see if "A InvEqP B" simplifies. 2440 if (MaxRecurse) 2441 if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1)) 2442 return V; 2443 break; 2444 } 2445 case CmpInst::ICMP_SGE: 2446 // Always true. 2447 return getTrue(ITy); 2448 case CmpInst::ICMP_SLT: 2449 // Always false. 2450 return getFalse(ITy); 2451 } 2452 } 2453 2454 // Unsigned variants on "max(a,b)>=a -> true". 2455 P = CmpInst::BAD_ICMP_PREDICATE; 2456 if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && (A == RHS || B == RHS)) { 2457 if (A != RHS) std::swap(A, B); // umax(A, B) pred A. 2458 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2459 // We analyze this as umax(A, B) pred A. 2460 P = Pred; 2461 } else if (match(RHS, m_UMax(m_Value(A), m_Value(B))) && 2462 (A == LHS || B == LHS)) { 2463 if (A != LHS) std::swap(A, B); // A pred umax(A, B). 2464 EqP = CmpInst::ICMP_UGE; // "A == umax(A, B)" iff "A uge B". 2465 // We analyze this as umax(A, B) swapped-pred A. 2466 P = CmpInst::getSwappedPredicate(Pred); 2467 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2468 (A == RHS || B == RHS)) { 2469 if (A != RHS) std::swap(A, B); // umin(A, B) pred A. 2470 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2471 // We analyze this as umax(-A, -B) swapped-pred -A. 2472 // Note that we do not need to actually form -A or -B thanks to EqP. 2473 P = CmpInst::getSwappedPredicate(Pred); 2474 } else if (match(RHS, m_UMin(m_Value(A), m_Value(B))) && 2475 (A == LHS || B == LHS)) { 2476 if (A != LHS) std::swap(A, B); // A pred umin(A, B). 2477 EqP = CmpInst::ICMP_ULE; // "A == umin(A, B)" iff "A ule B". 2478 // We analyze this as umax(-A, -B) pred -A. 2479 // Note that we do not need to actually form -A or -B thanks to EqP. 2480 P = Pred; 2481 } 2482 if (P != CmpInst::BAD_ICMP_PREDICATE) { 2483 // Cases correspond to "max(A, B) p A". 2484 switch (P) { 2485 default: 2486 break; 2487 case CmpInst::ICMP_EQ: 2488 case CmpInst::ICMP_ULE: 2489 // Equivalent to "A EqP B". This may be the same as the condition tested 2490 // in the max/min; if so, we can just return that. 2491 if (Value *V = ExtractEquivalentCondition(LHS, EqP, A, B)) 2492 return V; 2493 if (Value *V = ExtractEquivalentCondition(RHS, EqP, A, B)) 2494 return V; 2495 // Otherwise, see if "A EqP B" simplifies. 2496 if (MaxRecurse) 2497 if (Value *V = SimplifyICmpInst(EqP, A, B, Q, MaxRecurse-1)) 2498 return V; 2499 break; 2500 case CmpInst::ICMP_NE: 2501 case CmpInst::ICMP_UGT: { 2502 CmpInst::Predicate InvEqP = CmpInst::getInversePredicate(EqP); 2503 // Equivalent to "A InvEqP B". This may be the same as the condition 2504 // tested in the max/min; if so, we can just return that. 2505 if (Value *V = ExtractEquivalentCondition(LHS, InvEqP, A, B)) 2506 return V; 2507 if (Value *V = ExtractEquivalentCondition(RHS, InvEqP, A, B)) 2508 return V; 2509 // Otherwise, see if "A InvEqP B" simplifies. 2510 if (MaxRecurse) 2511 if (Value *V = SimplifyICmpInst(InvEqP, A, B, Q, MaxRecurse-1)) 2512 return V; 2513 break; 2514 } 2515 case CmpInst::ICMP_UGE: 2516 // Always true. 2517 return getTrue(ITy); 2518 case CmpInst::ICMP_ULT: 2519 // Always false. 2520 return getFalse(ITy); 2521 } 2522 } 2523 2524 // Variants on "max(x,y) >= min(x,z)". 2525 Value *C, *D; 2526 if (match(LHS, m_SMax(m_Value(A), m_Value(B))) && 2527 match(RHS, m_SMin(m_Value(C), m_Value(D))) && 2528 (A == C || A == D || B == C || B == D)) { 2529 // max(x, ?) pred min(x, ?). 2530 if (Pred == CmpInst::ICMP_SGE) 2531 // Always true. 2532 return getTrue(ITy); 2533 if (Pred == CmpInst::ICMP_SLT) 2534 // Always false. 2535 return getFalse(ITy); 2536 } else if (match(LHS, m_SMin(m_Value(A), m_Value(B))) && 2537 match(RHS, m_SMax(m_Value(C), m_Value(D))) && 2538 (A == C || A == D || B == C || B == D)) { 2539 // min(x, ?) pred max(x, ?). 2540 if (Pred == CmpInst::ICMP_SLE) 2541 // Always true. 2542 return getTrue(ITy); 2543 if (Pred == CmpInst::ICMP_SGT) 2544 // Always false. 2545 return getFalse(ITy); 2546 } else if (match(LHS, m_UMax(m_Value(A), m_Value(B))) && 2547 match(RHS, m_UMin(m_Value(C), m_Value(D))) && 2548 (A == C || A == D || B == C || B == D)) { 2549 // max(x, ?) pred min(x, ?). 2550 if (Pred == CmpInst::ICMP_UGE) 2551 // Always true. 2552 return getTrue(ITy); 2553 if (Pred == CmpInst::ICMP_ULT) 2554 // Always false. 2555 return getFalse(ITy); 2556 } else if (match(LHS, m_UMin(m_Value(A), m_Value(B))) && 2557 match(RHS, m_UMax(m_Value(C), m_Value(D))) && 2558 (A == C || A == D || B == C || B == D)) { 2559 // min(x, ?) pred max(x, ?). 2560 if (Pred == CmpInst::ICMP_ULE) 2561 // Always true. 2562 return getTrue(ITy); 2563 if (Pred == CmpInst::ICMP_UGT) 2564 // Always false. 2565 return getFalse(ITy); 2566 } 2567 2568 // Simplify comparisons of related pointers using a powerful, recursive 2569 // GEP-walk when we have target data available.. 2570 if (LHS->getType()->isPointerTy()) 2571 if (Constant *C = computePointerICmp(Q.DL, Q.TLI, Pred, LHS, RHS)) 2572 return C; 2573 2574 if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) { 2575 if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) { 2576 if (GLHS->getPointerOperand() == GRHS->getPointerOperand() && 2577 GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() && 2578 (ICmpInst::isEquality(Pred) || 2579 (GLHS->isInBounds() && GRHS->isInBounds() && 2580 Pred == ICmpInst::getSignedPredicate(Pred)))) { 2581 // The bases are equal and the indices are constant. Build a constant 2582 // expression GEP with the same indices and a null base pointer to see 2583 // what constant folding can make out of it. 2584 Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType()); 2585 SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end()); 2586 Constant *NewLHS = ConstantExpr::getGetElementPtr(Null, IndicesLHS); 2587 2588 SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end()); 2589 Constant *NewRHS = ConstantExpr::getGetElementPtr(Null, IndicesRHS); 2590 return ConstantExpr::getICmp(Pred, NewLHS, NewRHS); 2591 } 2592 } 2593 } 2594 2595 // If the comparison is with the result of a select instruction, check whether 2596 // comparing with either branch of the select always yields the same value. 2597 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2598 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) 2599 return V; 2600 2601 // If the comparison is with the result of a phi instruction, check whether 2602 // doing the compare with each incoming phi value yields a common result. 2603 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2604 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) 2605 return V; 2606 2607 return nullptr; 2608} 2609 2610Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2611 const DataLayout *DL, 2612 const TargetLibraryInfo *TLI, 2613 const DominatorTree *DT) { 2614 return ::SimplifyICmpInst(Predicate, LHS, RHS, Query (DL, TLI, DT), 2615 RecursionLimit); 2616} 2617 2618/// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can 2619/// fold the result. If not, this returns null. 2620static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2621 const Query &Q, unsigned MaxRecurse) { 2622 CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate; 2623 assert(CmpInst::isFPPredicate(Pred) && "Not an FP compare!"); 2624 2625 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 2626 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 2627 return ConstantFoldCompareInstOperands(Pred, CLHS, CRHS, Q.DL, Q.TLI); 2628 2629 // If we have a constant, make sure it is on the RHS. 2630 std::swap(LHS, RHS); 2631 Pred = CmpInst::getSwappedPredicate(Pred); 2632 } 2633 2634 // Fold trivial predicates. 2635 if (Pred == FCmpInst::FCMP_FALSE) 2636 return ConstantInt::get(GetCompareTy(LHS), 0); 2637 if (Pred == FCmpInst::FCMP_TRUE) 2638 return ConstantInt::get(GetCompareTy(LHS), 1); 2639 2640 if (isa<UndefValue>(RHS)) // fcmp pred X, undef -> undef 2641 return UndefValue::get(GetCompareTy(LHS)); 2642 2643 // fcmp x,x -> true/false. Not all compares are foldable. 2644 if (LHS == RHS) { 2645 if (CmpInst::isTrueWhenEqual(Pred)) 2646 return ConstantInt::get(GetCompareTy(LHS), 1); 2647 if (CmpInst::isFalseWhenEqual(Pred)) 2648 return ConstantInt::get(GetCompareTy(LHS), 0); 2649 } 2650 2651 // Handle fcmp with constant RHS 2652 if (Constant *RHSC = dyn_cast<Constant>(RHS)) { 2653 // If the constant is a nan, see if we can fold the comparison based on it. 2654 if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) { 2655 if (CFP->getValueAPF().isNaN()) { 2656 if (FCmpInst::isOrdered(Pred)) // True "if ordered and foo" 2657 return ConstantInt::getFalse(CFP->getContext()); 2658 assert(FCmpInst::isUnordered(Pred) && 2659 "Comparison must be either ordered or unordered!"); 2660 // True if unordered. 2661 return ConstantInt::getTrue(CFP->getContext()); 2662 } 2663 // Check whether the constant is an infinity. 2664 if (CFP->getValueAPF().isInfinity()) { 2665 if (CFP->getValueAPF().isNegative()) { 2666 switch (Pred) { 2667 case FCmpInst::FCMP_OLT: 2668 // No value is ordered and less than negative infinity. 2669 return ConstantInt::getFalse(CFP->getContext()); 2670 case FCmpInst::FCMP_UGE: 2671 // All values are unordered with or at least negative infinity. 2672 return ConstantInt::getTrue(CFP->getContext()); 2673 default: 2674 break; 2675 } 2676 } else { 2677 switch (Pred) { 2678 case FCmpInst::FCMP_OGT: 2679 // No value is ordered and greater than infinity. 2680 return ConstantInt::getFalse(CFP->getContext()); 2681 case FCmpInst::FCMP_ULE: 2682 // All values are unordered with and at most infinity. 2683 return ConstantInt::getTrue(CFP->getContext()); 2684 default: 2685 break; 2686 } 2687 } 2688 } 2689 } 2690 } 2691 2692 // If the comparison is with the result of a select instruction, check whether 2693 // comparing with either branch of the select always yields the same value. 2694 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2695 if (Value *V = ThreadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse)) 2696 return V; 2697 2698 // If the comparison is with the result of a phi instruction, check whether 2699 // doing the compare with each incoming phi value yields a common result. 2700 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2701 if (Value *V = ThreadCmpOverPHI(Pred, LHS, RHS, Q, MaxRecurse)) 2702 return V; 2703 2704 return nullptr; 2705} 2706 2707Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2708 const DataLayout *DL, 2709 const TargetLibraryInfo *TLI, 2710 const DominatorTree *DT) { 2711 return ::SimplifyFCmpInst(Predicate, LHS, RHS, Query (DL, TLI, DT), 2712 RecursionLimit); 2713} 2714 2715/// SimplifySelectInst - Given operands for a SelectInst, see if we can fold 2716/// the result. If not, this returns null. 2717static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, 2718 Value *FalseVal, const Query &Q, 2719 unsigned MaxRecurse) { 2720 // select true, X, Y -> X 2721 // select false, X, Y -> Y 2722 if (Constant *CB = dyn_cast<Constant>(CondVal)) { 2723 if (CB->isAllOnesValue()) 2724 return TrueVal; 2725 if (CB->isNullValue()) 2726 return FalseVal; 2727 } 2728 2729 // select C, X, X -> X 2730 if (TrueVal == FalseVal) 2731 return TrueVal; 2732 2733 if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y 2734 if (isa<Constant>(TrueVal)) 2735 return TrueVal; 2736 return FalseVal; 2737 } 2738 if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X 2739 return FalseVal; 2740 if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X 2741 return TrueVal; 2742 2743 return nullptr; 2744} 2745 2746Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, 2747 const DataLayout *DL, 2748 const TargetLibraryInfo *TLI, 2749 const DominatorTree *DT) { 2750 return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Query (DL, TLI, DT), 2751 RecursionLimit); 2752} 2753 2754/// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can 2755/// fold the result. If not, this returns null. 2756static Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const Query &Q, unsigned) { 2757 // The type of the GEP pointer operand. 2758 PointerType *PtrTy = cast<PointerType>(Ops[0]->getType()->getScalarType()); 2759 2760 // getelementptr P -> P. 2761 if (Ops.size() == 1) 2762 return Ops[0]; 2763 2764 if (isa<UndefValue>(Ops[0])) { 2765 // Compute the (pointer) type returned by the GEP instruction. 2766 Type *LastType = GetElementPtrInst::getIndexedType(PtrTy, Ops.slice(1)); 2767 Type *GEPTy = PointerType::get(LastType, PtrTy->getAddressSpace()); 2768 if (VectorType *VT = dyn_cast<VectorType>(Ops[0]->getType())) 2769 GEPTy = VectorType::get(GEPTy, VT->getNumElements()); 2770 return UndefValue::get(GEPTy); 2771 } 2772 2773 if (Ops.size() == 2) { 2774 // getelementptr P, 0 -> P. 2775 if (match(Ops[1], m_Zero())) 2776 return Ops[0]; 2777 // getelementptr P, N -> P if P points to a type of zero size. 2778 if (Q.DL) { 2779 Type *Ty = PtrTy->getElementType(); 2780 if (Ty->isSized() && Q.DL->getTypeAllocSize(Ty) == 0) 2781 return Ops[0]; 2782 } 2783 } 2784 2785 // Check to see if this is constant foldable. 2786 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 2787 if (!isa<Constant>(Ops[i])) 2788 return nullptr; 2789 2790 return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1)); 2791} 2792 2793Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *DL, 2794 const TargetLibraryInfo *TLI, 2795 const DominatorTree *DT) { 2796 return ::SimplifyGEPInst(Ops, Query (DL, TLI, DT), RecursionLimit); 2797} 2798 2799/// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we 2800/// can fold the result. If not, this returns null. 2801static Value *SimplifyInsertValueInst(Value *Agg, Value *Val, 2802 ArrayRef<unsigned> Idxs, const Query &Q, 2803 unsigned) { 2804 if (Constant *CAgg = dyn_cast<Constant>(Agg)) 2805 if (Constant *CVal = dyn_cast<Constant>(Val)) 2806 return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs); 2807 2808 // insertvalue x, undef, n -> x 2809 if (match(Val, m_Undef())) 2810 return Agg; 2811 2812 // insertvalue x, (extractvalue y, n), n 2813 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Val)) 2814 if (EV->getAggregateOperand()->getType() == Agg->getType() && 2815 EV->getIndices() == Idxs) { 2816 // insertvalue undef, (extractvalue y, n), n -> y 2817 if (match(Agg, m_Undef())) 2818 return EV->getAggregateOperand(); 2819 2820 // insertvalue y, (extractvalue y, n), n -> y 2821 if (Agg == EV->getAggregateOperand()) 2822 return Agg; 2823 } 2824 2825 return nullptr; 2826} 2827 2828Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val, 2829 ArrayRef<unsigned> Idxs, 2830 const DataLayout *DL, 2831 const TargetLibraryInfo *TLI, 2832 const DominatorTree *DT) { 2833 return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query (DL, TLI, DT), 2834 RecursionLimit); 2835} 2836 2837/// SimplifyPHINode - See if we can fold the given phi. If not, returns null. 2838static Value *SimplifyPHINode(PHINode *PN, const Query &Q) { 2839 // If all of the PHI's incoming values are the same then replace the PHI node 2840 // with the common value. 2841 Value *CommonValue = nullptr; 2842 bool HasUndefInput = false; 2843 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 2844 Value *Incoming = PN->getIncomingValue(i); 2845 // If the incoming value is the phi node itself, it can safely be skipped. 2846 if (Incoming == PN) continue; 2847 if (isa<UndefValue>(Incoming)) { 2848 // Remember that we saw an undef value, but otherwise ignore them. 2849 HasUndefInput = true; 2850 continue; 2851 } 2852 if (CommonValue && Incoming != CommonValue) 2853 return nullptr; // Not the same, bail out. 2854 CommonValue = Incoming; 2855 } 2856 2857 // If CommonValue is null then all of the incoming values were either undef or 2858 // equal to the phi node itself. 2859 if (!CommonValue) 2860 return UndefValue::get(PN->getType()); 2861 2862 // If we have a PHI node like phi(X, undef, X), where X is defined by some 2863 // instruction, we cannot return X as the result of the PHI node unless it 2864 // dominates the PHI block. 2865 if (HasUndefInput) 2866 return ValueDominatesPHI(CommonValue, PN, Q.DT) ? CommonValue : nullptr; 2867 2868 return CommonValue; 2869} 2870 2871static Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) { 2872 if (Constant *C = dyn_cast<Constant>(Op)) 2873 return ConstantFoldInstOperands(Instruction::Trunc, Ty, C, Q.DL, Q.TLI); 2874 2875 return nullptr; 2876} 2877 2878Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *DL, 2879 const TargetLibraryInfo *TLI, 2880 const DominatorTree *DT) { 2881 return ::SimplifyTruncInst(Op, Ty, Query (DL, TLI, DT), RecursionLimit); 2882} 2883 2884//=== Helper functions for higher up the class hierarchy. 2885 2886/// SimplifyBinOp - Given operands for a BinaryOperator, see if we can 2887/// fold the result. If not, this returns null. 2888static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 2889 const Query &Q, unsigned MaxRecurse) { 2890 switch (Opcode) { 2891 case Instruction::Add: 2892 return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2893 Q, MaxRecurse); 2894 case Instruction::FAdd: 2895 return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 2896 2897 case Instruction::Sub: 2898 return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2899 Q, MaxRecurse); 2900 case Instruction::FSub: 2901 return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); 2902 2903 case Instruction::Mul: return SimplifyMulInst (LHS, RHS, Q, MaxRecurse); 2904 case Instruction::FMul: 2905 return SimplifyFMulInst (LHS, RHS, FastMathFlags(), Q, MaxRecurse); 2906 case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse); 2907 case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse); 2908 case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, Q, MaxRecurse); 2909 case Instruction::SRem: return SimplifySRemInst(LHS, RHS, Q, MaxRecurse); 2910 case Instruction::URem: return SimplifyURemInst(LHS, RHS, Q, MaxRecurse); 2911 case Instruction::FRem: return SimplifyFRemInst(LHS, RHS, Q, MaxRecurse); 2912 case Instruction::Shl: 2913 return SimplifyShlInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, 2914 Q, MaxRecurse); 2915 case Instruction::LShr: 2916 return SimplifyLShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse); 2917 case Instruction::AShr: 2918 return SimplifyAShrInst(LHS, RHS, /*isExact*/false, Q, MaxRecurse); 2919 case Instruction::And: return SimplifyAndInst(LHS, RHS, Q, MaxRecurse); 2920 case Instruction::Or: return SimplifyOrInst (LHS, RHS, Q, MaxRecurse); 2921 case Instruction::Xor: return SimplifyXorInst(LHS, RHS, Q, MaxRecurse); 2922 default: 2923 if (Constant *CLHS = dyn_cast<Constant>(LHS)) 2924 if (Constant *CRHS = dyn_cast<Constant>(RHS)) { 2925 Constant *COps[] = {CLHS, CRHS}; 2926 return ConstantFoldInstOperands(Opcode, LHS->getType(), COps, Q.DL, 2927 Q.TLI); 2928 } 2929 2930 // If the operation is associative, try some generic simplifications. 2931 if (Instruction::isAssociative(Opcode)) 2932 if (Value *V = SimplifyAssociativeBinOp(Opcode, LHS, RHS, Q, MaxRecurse)) 2933 return V; 2934 2935 // If the operation is with the result of a select instruction check whether 2936 // operating on either branch of the select always yields the same value. 2937 if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS)) 2938 if (Value *V = ThreadBinOpOverSelect(Opcode, LHS, RHS, Q, MaxRecurse)) 2939 return V; 2940 2941 // If the operation is with the result of a phi instruction, check whether 2942 // operating on all incoming values of the phi always yields the same value. 2943 if (isa<PHINode>(LHS) || isa<PHINode>(RHS)) 2944 if (Value *V = ThreadBinOpOverPHI(Opcode, LHS, RHS, Q, MaxRecurse)) 2945 return V; 2946 2947 return nullptr; 2948 } 2949} 2950 2951Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, 2952 const DataLayout *DL, const TargetLibraryInfo *TLI, 2953 const DominatorTree *DT) { 2954 return ::SimplifyBinOp(Opcode, LHS, RHS, Query (DL, TLI, DT), RecursionLimit); 2955} 2956 2957/// SimplifyCmpInst - Given operands for a CmpInst, see if we can 2958/// fold the result. 2959static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2960 const Query &Q, unsigned MaxRecurse) { 2961 if (CmpInst::isIntPredicate((CmpInst::Predicate)Predicate)) 2962 return SimplifyICmpInst(Predicate, LHS, RHS, Q, MaxRecurse); 2963 return SimplifyFCmpInst(Predicate, LHS, RHS, Q, MaxRecurse); 2964} 2965 2966Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, 2967 const DataLayout *DL, const TargetLibraryInfo *TLI, 2968 const DominatorTree *DT) { 2969 return ::SimplifyCmpInst(Predicate, LHS, RHS, Query (DL, TLI, DT), 2970 RecursionLimit); 2971} 2972 2973static bool IsIdempotent(Intrinsic::ID ID) { 2974 switch (ID) { 2975 default: return false; 2976 2977 // Unary idempotent: f(f(x)) = f(x) 2978 case Intrinsic::fabs: 2979 case Intrinsic::floor: 2980 case Intrinsic::ceil: 2981 case Intrinsic::trunc: 2982 case Intrinsic::rint: 2983 case Intrinsic::nearbyint: 2984 case Intrinsic::round: 2985 return true; 2986 } 2987} 2988 2989template <typename IterTy> 2990static Value *SimplifyIntrinsic(Intrinsic::ID IID, IterTy ArgBegin, IterTy ArgEnd, 2991 const Query &Q, unsigned MaxRecurse) { 2992 // Perform idempotent optimizations 2993 if (!IsIdempotent(IID)) 2994 return nullptr; 2995 2996 // Unary Ops 2997 if (std::distance(ArgBegin, ArgEnd) == 1) 2998 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(*ArgBegin)) 2999 if (II->getIntrinsicID() == IID) 3000 return II; 3001 3002 return nullptr; 3003} 3004 3005template <typename IterTy> 3006static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd, 3007 const Query &Q, unsigned MaxRecurse) { 3008 Type *Ty = V->getType(); 3009 if (PointerType *PTy = dyn_cast<PointerType>(Ty)) 3010 Ty = PTy->getElementType(); 3011 FunctionType *FTy = cast<FunctionType>(Ty); 3012 3013 // call undef -> undef 3014 if (isa<UndefValue>(V)) 3015 return UndefValue::get(FTy->getReturnType()); 3016 3017 Function *F = dyn_cast<Function>(V); 3018 if (!F) 3019 return nullptr; 3020 3021 if (unsigned IID = F->getIntrinsicID()) 3022 if (Value *Ret = 3023 SimplifyIntrinsic((Intrinsic::ID) IID, ArgBegin, ArgEnd, Q, MaxRecurse)) 3024 return Ret; 3025 3026 if (!canConstantFoldCallTo(F)) 3027 return nullptr; 3028 3029 SmallVector<Constant *, 4> ConstantArgs; 3030 ConstantArgs.reserve(ArgEnd - ArgBegin); 3031 for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) { 3032 Constant *C = dyn_cast<Constant>(*I); 3033 if (!C) 3034 return nullptr; 3035 ConstantArgs.push_back(C); 3036 } 3037 3038 return ConstantFoldCall(F, ConstantArgs, Q.TLI); 3039} 3040 3041Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin, 3042 User::op_iterator ArgEnd, const DataLayout *DL, 3043 const TargetLibraryInfo *TLI, 3044 const DominatorTree *DT) { 3045 return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(DL, TLI, DT), 3046 RecursionLimit); 3047} 3048 3049Value *llvm::SimplifyCall(Value *V, ArrayRef<Value *> Args, 3050 const DataLayout *DL, const TargetLibraryInfo *TLI, 3051 const DominatorTree *DT) { 3052 return ::SimplifyCall(V, Args.begin(), Args.end(), Query(DL, TLI, DT), 3053 RecursionLimit); 3054} 3055 3056/// SimplifyInstruction - See if we can compute a simplified version of this 3057/// instruction. If not, this returns null. 3058Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *DL, 3059 const TargetLibraryInfo *TLI, 3060 const DominatorTree *DT) { 3061 Value *Result; 3062 3063 switch (I->getOpcode()) { 3064 default: 3065 Result = ConstantFoldInstruction(I, DL, TLI); 3066 break; 3067 case Instruction::FAdd: 3068 Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1), 3069 I->getFastMathFlags(), DL, TLI, DT); 3070 break; 3071 case Instruction::Add: 3072 Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), 3073 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3074 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 3075 DL, TLI, DT); 3076 break; 3077 case Instruction::FSub: 3078 Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1), 3079 I->getFastMathFlags(), DL, TLI, DT); 3080 break; 3081 case Instruction::Sub: 3082 Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), 3083 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3084 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 3085 DL, TLI, DT); 3086 break; 3087 case Instruction::FMul: 3088 Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1), 3089 I->getFastMathFlags(), DL, TLI, DT); 3090 break; 3091 case Instruction::Mul: 3092 Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3093 break; 3094 case Instruction::SDiv: 3095 Result = SimplifySDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3096 break; 3097 case Instruction::UDiv: 3098 Result = SimplifyUDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3099 break; 3100 case Instruction::FDiv: 3101 Result = SimplifyFDivInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3102 break; 3103 case Instruction::SRem: 3104 Result = SimplifySRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3105 break; 3106 case Instruction::URem: 3107 Result = SimplifyURemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3108 break; 3109 case Instruction::FRem: 3110 Result = SimplifyFRemInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3111 break; 3112 case Instruction::Shl: 3113 Result = SimplifyShlInst(I->getOperand(0), I->getOperand(1), 3114 cast<BinaryOperator>(I)->hasNoSignedWrap(), 3115 cast<BinaryOperator>(I)->hasNoUnsignedWrap(), 3116 DL, TLI, DT); 3117 break; 3118 case Instruction::LShr: 3119 Result = SimplifyLShrInst(I->getOperand(0), I->getOperand(1), 3120 cast<BinaryOperator>(I)->isExact(), 3121 DL, TLI, DT); 3122 break; 3123 case Instruction::AShr: 3124 Result = SimplifyAShrInst(I->getOperand(0), I->getOperand(1), 3125 cast<BinaryOperator>(I)->isExact(), 3126 DL, TLI, DT); 3127 break; 3128 case Instruction::And: 3129 Result = SimplifyAndInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3130 break; 3131 case Instruction::Or: 3132 Result = SimplifyOrInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3133 break; 3134 case Instruction::Xor: 3135 Result = SimplifyXorInst(I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3136 break; 3137 case Instruction::ICmp: 3138 Result = SimplifyICmpInst(cast<ICmpInst>(I)->getPredicate(), 3139 I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3140 break; 3141 case Instruction::FCmp: 3142 Result = SimplifyFCmpInst(cast<FCmpInst>(I)->getPredicate(), 3143 I->getOperand(0), I->getOperand(1), DL, TLI, DT); 3144 break; 3145 case Instruction::Select: 3146 Result = SimplifySelectInst(I->getOperand(0), I->getOperand(1), 3147 I->getOperand(2), DL, TLI, DT); 3148 break; 3149 case Instruction::GetElementPtr: { 3150 SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end()); 3151 Result = SimplifyGEPInst(Ops, DL, TLI, DT); 3152 break; 3153 } 3154 case Instruction::InsertValue: { 3155 InsertValueInst *IV = cast<InsertValueInst>(I); 3156 Result = SimplifyInsertValueInst(IV->getAggregateOperand(), 3157 IV->getInsertedValueOperand(), 3158 IV->getIndices(), DL, TLI, DT); 3159 break; 3160 } 3161 case Instruction::PHI: 3162 Result = SimplifyPHINode(cast<PHINode>(I), Query (DL, TLI, DT)); 3163 break; 3164 case Instruction::Call: { 3165 CallSite CS(cast<CallInst>(I)); 3166 Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), 3167 DL, TLI, DT); 3168 break; 3169 } 3170 case Instruction::Trunc: 3171 Result = SimplifyTruncInst(I->getOperand(0), I->getType(), DL, TLI, DT); 3172 break; 3173 } 3174 3175 /// If called on unreachable code, the above logic may report that the 3176 /// instruction simplified to itself. Make life easier for users by 3177 /// detecting that case here, returning a safe value instead. 3178 return Result == I ? UndefValue::get(I->getType()) : Result; 3179} 3180 3181/// \brief Implementation of recursive simplification through an instructions 3182/// uses. 3183/// 3184/// This is the common implementation of the recursive simplification routines. 3185/// If we have a pre-simplified value in 'SimpleV', that is forcibly used to 3186/// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of 3187/// instructions to process and attempt to simplify it using 3188/// InstructionSimplify. 3189/// 3190/// This routine returns 'true' only when *it* simplifies something. The passed 3191/// in simplified value does not count toward this. 3192static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV, 3193 const DataLayout *DL, 3194 const TargetLibraryInfo *TLI, 3195 const DominatorTree *DT) { 3196 bool Simplified = false; 3197 SmallSetVector<Instruction *, 8> Worklist; 3198 3199 // If we have an explicit value to collapse to, do that round of the 3200 // simplification loop by hand initially. 3201 if (SimpleV) { 3202 for (User *U : I->users()) 3203 if (U != I) 3204 Worklist.insert(cast<Instruction>(U)); 3205 3206 // Replace the instruction with its simplified value. 3207 I->replaceAllUsesWith(SimpleV); 3208 3209 // Gracefully handle edge cases where the instruction is not wired into any 3210 // parent block. 3211 if (I->getParent()) 3212 I->eraseFromParent(); 3213 } else { 3214 Worklist.insert(I); 3215 } 3216 3217 // Note that we must test the size on each iteration, the worklist can grow. 3218 for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) { 3219 I = Worklist[Idx]; 3220 3221 // See if this instruction simplifies. 3222 SimpleV = SimplifyInstruction(I, DL, TLI, DT); 3223 if (!SimpleV) 3224 continue; 3225 3226 Simplified = true; 3227 3228 // Stash away all the uses of the old instruction so we can check them for 3229 // recursive simplifications after a RAUW. This is cheaper than checking all 3230 // uses of To on the recursive step in most cases. 3231 for (User *U : I->users()) 3232 Worklist.insert(cast<Instruction>(U)); 3233 3234 // Replace the instruction with its simplified value. 3235 I->replaceAllUsesWith(SimpleV); 3236 3237 // Gracefully handle edge cases where the instruction is not wired into any 3238 // parent block. 3239 if (I->getParent()) 3240 I->eraseFromParent(); 3241 } 3242 return Simplified; 3243} 3244 3245bool llvm::recursivelySimplifyInstruction(Instruction *I, 3246 const DataLayout *DL, 3247 const TargetLibraryInfo *TLI, 3248 const DominatorTree *DT) { 3249 return replaceAndRecursivelySimplifyImpl(I, nullptr, DL, TLI, DT); 3250} 3251 3252bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, 3253 const DataLayout *DL, 3254 const TargetLibraryInfo *TLI, 3255 const DominatorTree *DT) { 3256 assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!"); 3257 assert(SimpleV && "Must provide a simplified value."); 3258 return replaceAndRecursivelySimplifyImpl(I, SimpleV, DL, TLI, DT); 3259} 3260