ValueTracking.cpp revision 0af20d847ac89f797d613a8a4fc3e7127ccb0b36
1173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner//===- ValueTracking.cpp - Walk computations to compute properties --------===// 2173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 3173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// The LLVM Compiler Infrastructure 4173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 5173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// This file is distributed under the University of Illinois Open Source 6173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// License. See LICENSE.TXT for details. 7173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 8173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner//===----------------------------------------------------------------------===// 9173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 10173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// This file contains routines that help analyze properties that chains of 11173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// computations have. 12173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner// 13173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner//===----------------------------------------------------------------------===// 14173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 15173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Analysis/ValueTracking.h" 16173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Constants.h" 17173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Instructions.h" 180ff39b3feb10477c224138156941234f5fa46f58Evan Cheng#include "llvm/GlobalVariable.h" 19307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman#include "llvm/GlobalAlias.h" 20173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/IntrinsicInst.h" 2176f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson#include "llvm/LLVMContext.h" 22ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman#include "llvm/Operator.h" 230582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling#include "llvm/Target/TargetData.h" 24173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 25173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/MathExtras.h" 2625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher#include "llvm/ADT/SmallPtrSet.h" 2732a9e7a2654c4aab2e617fbe53140492b3d38066Chris Lattner#include <cstring> 28173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerusing namespace llvm; 29173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 30173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeMaskedBits - Determine which of the bits specified in Mask are 31173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// known to be either zero or one and return them in the KnownZero/KnownOne 32173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// bit sets. This code only analyzes bits in Mask, in order to short-circuit 33173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// processing. 34173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that 35173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// we cannot optimize based on the assumption that it is zero without changing 36173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// it to be an explicit zero. If we don't change it to zero, other code could 37173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// optimized based on the contradictory assumption that it is non-zero. 38173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// Because instcombine aggressively folds operations with undef args anyway, 39173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this won't lose us code quality. 40cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// 41cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// This function is defined on values with integer type, values with pointer 42cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// type (but only if TD is non-null), and vectors of integers. In the case 43cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// where V is a vector, the mask, known zero, and known one values are the 44cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// same width as the vector element, and the bit is set only if it is true 45cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// for all of the elements in the vector. 46173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnervoid llvm::ComputeMaskedBits(Value *V, const APInt &Mask, 47173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt &KnownZero, APInt &KnownOne, 48846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman const TargetData *TD, unsigned Depth) { 499004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman const unsigned MaxDepth = 6; 50173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert(V && "No Value?"); 519004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman assert(Depth <= MaxDepth && "Limit Search Depth"); 5279abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned BitWidth = Mask.getBitWidth(); 531df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands assert((V->getType()->isIntOrIntVectorTy() || V->getType()->isPointerTy()) 54b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands && "Not integer or pointer type!"); 556de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman assert((!TD || 566de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman TD->getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) && 57b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands (!V->getType()->isIntOrIntVectorTy() || 586de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman V->getType()->getScalarSizeInBits() == BitWidth) && 59173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.getBitWidth() == BitWidth && 60173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.getBitWidth() == BitWidth && 61173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner "V, Mask, KnownOne and KnownZero should have same BitWidth"); 62173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 63173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 64173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know all of the bits for a constant! 65173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = CI->getValue() & Mask; 66173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = ~KnownOne & Mask; 67173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 68173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 696de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // Null and aggregate-zero are all-zeros. 706de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman if (isa<ConstantPointerNull>(V) || 716de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman isa<ConstantAggregateZero>(V)) { 72173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 73173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask; 74173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 75173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 766de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // Handle a constant vector by taking the intersection of the known bits of 776de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // each element. 786de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) { 796de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman KnownZero.set(); KnownOne.set(); 806de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) { 816de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0); 826de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman ComputeMaskedBits(CV->getOperand(i), Mask, KnownZero2, KnownOne2, 836de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman TD, Depth); 846de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman KnownZero &= KnownZero2; 856de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman KnownOne &= KnownOne2; 866de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman } 876de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman return; 886de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman } 89173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // The address of an aligned GlobalValue has trailing zeros. 90173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 91173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = GV->getAlignment(); 92004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman if (Align == 0 && TD && GV->getType()->getElementType()->isSized()) { 93004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman const Type *ObjectType = GV->getType()->getElementType(); 94004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman // If the object is defined in the current Module, we'll be giving 95004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman // it the preferred alignment. Otherwise, we have to assume that it 96004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman // may only have the minimum ABI alignment. 97004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman if (!GV->isDeclaration() && !GV->mayBeOverridden()) 98004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman Align = TD->getPrefTypeAlignment(ObjectType); 99004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman else 100004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman Align = TD->getABITypeAlignment(ObjectType); 101004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman } 102173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 103173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 104173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_32(Align)); 105173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 106173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.clear(); 107173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 108173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 109173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 110307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has 111307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman // the bits of its aliasee. 112307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 113307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman if (GA->mayBeOverridden()) { 114307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman KnownZero.clear(); KnownOne.clear(); 115307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } else { 116307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman ComputeMaskedBits(GA->getAliasee(), Mask, KnownZero, KnownOne, 117307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman TD, Depth+1); 118307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } 119307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman return; 120307a7c48f15b087663b60d600d23afffb9e211e6Dan Gohman } 121173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 122173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.clear(); KnownOne.clear(); // Start out not knowing anything. 123173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1249004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (Depth == MaxDepth || Mask == 0) 125173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Limit search depth. 126173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 127ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *I = dyn_cast<Operator>(V); 128173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!I) return; 129173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 130173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero2(KnownZero), KnownOne2(KnownOne); 131ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman switch (I->getOpcode()) { 132173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 133173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: { 134173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If either the LHS or the RHS are Zero, the result is zero. 135173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 136173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask & ~KnownZero); 137173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 138173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 139173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 140173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 141173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 142173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 bits are only known if set in both the LHS & RHS. 143173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 144173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 are known to be clear if zero in either the LHS | RHS. 145173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= KnownZero2; 146173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 147173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 148173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: { 149173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 150173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask & ~KnownOne); 151173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 152173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 153173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 154173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 155173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 156173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are only known if clear in both the LHS & RHS. 157173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 158173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in either the LHS | RHS. 159173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= KnownOne2; 160173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 161173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 162173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: { 163173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 164173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask, KnownZero2, KnownOne2, TD, 165173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 166173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 167173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 168173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 169173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are known if clear or set in both the LHS & RHS. 170173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 171173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in only one of the LHS, RHS. 172173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 173173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = KnownZeroOut; 174173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 175173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 176173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Mul: { 177173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getAllOnesValue(BitWidth); 178173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero, KnownOne, TD,Depth+1); 179173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 180173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 181173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 182173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 183173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 184173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If low bits are zero in either operand, output low known-0 bits. 185173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Also compute a conserative estimate for high known-0 bits. 186173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // More trickiness is possible, but this is sufficient for the 187173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // interesting case of alignment computation. 188173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 189173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = KnownZero.countTrailingOnes() + 190173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes(); 191173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 192173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes(), 193173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner BitWidth) - BitWidth; 194173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 195173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, BitWidth); 196173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(LeadZ, BitWidth); 197173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 198173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt::getHighBitsSet(BitWidth, LeadZ); 199173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= Mask; 200173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 201173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 202173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UDiv: { 203173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // For the purposes of computing leading zeros we can conservatively 204173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // treat a udiv as a logical right shift by the power of 2 known to 205173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // be less than the denominator. 206173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 207173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), 208173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllOnes, KnownZero2, KnownOne2, TD, Depth+1); 209173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = KnownZero2.countLeadingOnes(); 210173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 211173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne2.clear(); 212173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.clear(); 213173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), 214173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllOnes, KnownZero2, KnownOne2, TD, Depth+1); 215173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 216173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RHSUnknownLeadingOnes != BitWidth) 217173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(BitWidth, 218173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 219173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 220173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask; 221173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 222173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 223173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 224173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(2), Mask, KnownZero, KnownOne, TD, Depth+1); 225173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero2, KnownOne2, TD, 226173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 227173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 228173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 229173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 230173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Only known if known in both the LHS and RHS. 231173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 232173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 233173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 234173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPTrunc: 235173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPExt: 236173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToUI: 237173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToSI: 238173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SIToFP: 239173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UIToFP: 240173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Can't work with floating point. 241173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PtrToInt: 242173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::IntToPtr: 243173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We can't handle these if we don't know the pointer size. 244173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 245173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FALL THROUGH and handle them the same as zext/trunc. 246173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::ZExt: 247173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: { 248b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner const Type *SrcTy = I->getOperand(0)->getType(); 249b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner 250b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner unsigned SrcBitWidth; 251173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Note that we handle pointer operands here because of inttoptr/ptrtoint 252173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // which fall through here. 2531df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (SrcTy->isPointerTy()) 254b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner SrcBitWidth = TD->getTypeSizeInBits(SrcTy); 255b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner else 256b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner SrcBitWidth = SrcTy->getScalarSizeInBits(); 257b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner 258173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskIn(Mask); 259173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner MaskIn.zextOrTrunc(SrcBitWidth); 260173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zextOrTrunc(SrcBitWidth); 261173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zextOrTrunc(SrcBitWidth); 262173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD, 263173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 264173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zextOrTrunc(BitWidth); 265173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zextOrTrunc(BitWidth); 266173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Any top bits are known to be zero. 267173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (BitWidth > SrcBitWidth) 268173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 269173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 270173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 271173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::BitCast: { 272173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const Type *SrcTy = I->getOperand(0)->getType(); 2731df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if ((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) && 2740dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner // TODO: For now, not handling conversions like: 2750dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner // (bitcast i64 %x to <2 x i32>) 2761df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands !I->getType()->isVectorTy()) { 277173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask, KnownZero, KnownOne, TD, 278173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 279173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 280173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 281173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 282173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 283173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: { 284173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the bits in the result that are not present in the input. 285b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); 286173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 287173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskIn(Mask); 288173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner MaskIn.trunc(SrcBitWidth); 289173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.trunc(SrcBitWidth); 290173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.trunc(SrcBitWidth); 291173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD, 292173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 293173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 294173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zext(BitWidth); 295173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zext(BitWidth); 296173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 297173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the sign bit of the input is known set or clear, then we know the 298173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // top bits of the result. 299173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[SrcBitWidth-1]) // Input sign bit known zero 300173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 301173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[SrcBitWidth-1]) // Input sign bit known set 302173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 303173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 304173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 305173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 306173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 307173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 308173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 309173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.lshr(ShiftAmt)); 310173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 311173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 312173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 313173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero <<= ShiftAmt; 314173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne <<= ShiftAmt; 315173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 316173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 317173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 318173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 319173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::LShr: 320173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 321173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 322173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 323173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 324173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 325173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Unsigned shift right. 326173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.shl(ShiftAmt)); 327173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero,KnownOne, TD, 328173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 329ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 330173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 331173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 332173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // high bits known zero. 333173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 334173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 335173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 336173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 337173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 338173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 339173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 340173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 341173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 342173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 343173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Signed shift right. 344173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.shl(ShiftAmt)); 345173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 346173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 347ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 348173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 349173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 350173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 351173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 352173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[BitWidth-ShiftAmt-1]) // New bits are known zero. 353173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= HighBits; 354173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. 355173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= HighBits; 356173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 357173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 358173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 359173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: { 360173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(I->getOperand(0))) { 361173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know that the top bits of C-X are clear if X contains less bits 362173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // than C (i.e. no wrap-around can happen). For example, 20-X is 363173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // positive if we can prove that X is >= 0 and < 16. 364173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!CLHS->getValue().isNegative()) { 365173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros(); 366173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // NLZ can't be BitWidth with no sign bit 367173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 368173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), MaskV, KnownZero2, KnownOne2, 369173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 370173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 371173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If all of the MaskV bits are known to be zero, then we know the 372173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // output top bits are zero, because we now know that the output is 373173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // from [0-C]. 374173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero2 & MaskV) == MaskV) { 375173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned NLZ2 = CLHS->getValue().countLeadingZeros(); 376173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Top bits known zero. 377173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask; 378173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 379173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 380173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 381173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 382173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // fall through 383173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: { 384ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky // If one of the operands has trailing zeros, then the bits that the 3853925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // other operand has in those bit positions will be preserved in the 3863925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // result. For an add, this works with either operand. For a subtract, 3873925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // this only works if the known zeros are in the right operand. 3883925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 3893925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask2 = APInt::getLowBitsSet(BitWidth, 3903925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman BitWidth - Mask.countLeadingZeros()); 3913925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman ComputeMaskedBits(I->getOperand(0), Mask2, LHSKnownZero, LHSKnownOne, TD, 392173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 3933925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman assert((LHSKnownZero & LHSKnownOne) == 0 && 3943925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman "Bits known to be one AND zero?"); 3953925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman unsigned LHSKnownZeroOut = LHSKnownZero.countTrailingOnes(); 396173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 397173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero2, KnownOne2, TD, 398173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 399173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 4003925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman unsigned RHSKnownZeroOut = KnownZero2.countTrailingOnes(); 401173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 4023925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // Determine which operand has more trailing zeros, and use that 4033925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // many bits from the other operand. 4043925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman if (LHSKnownZeroOut > RHSKnownZeroOut) { 405ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman if (I->getOpcode() == Instruction::Add) { 4063925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask = APInt::getLowBitsSet(BitWidth, LHSKnownZeroOut); 4073925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= KnownZero2 & Mask; 4083925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownOne |= KnownOne2 & Mask; 4093925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } else { 4103925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // If the known zeros are in the left operand for a subtract, 4113925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // fall back to the minimum known zeros in both operands. 4123925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= APInt::getLowBitsSet(BitWidth, 4133925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman std::min(LHSKnownZeroOut, 4143925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman RHSKnownZeroOut)); 4153925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } 4163925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } else if (RHSKnownZeroOut >= LHSKnownZeroOut) { 4173925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask = APInt::getLowBitsSet(BitWidth, RHSKnownZeroOut); 4183925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= LHSKnownZero & Mask; 4193925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownOne |= LHSKnownOne & Mask; 4203925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } 421173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 422173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 423173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SRem: 424173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 425cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands APInt RA = Rem->getValue().abs(); 426cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands if (RA.isPowerOf2()) { 427cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands APInt LowBits = RA - 1; 428173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 429173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 430173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 431173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 432cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // The low bits of the first operand are unchanged by the srem. 433cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownZero = KnownZero2 & LowBits; 434cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownOne = KnownOne2 & LowBits; 435cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands 436cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // If the first operand is non-negative or has all low bits zero, then 437cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // the upper bits are all zero. 438173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 439cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownZero |= ~LowBits; 440173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 441cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // If the first operand is negative and not all low bits are zero, then 442cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands // the upper bits are all one. 443cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0)) 444cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownOne |= ~LowBits; 445cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands 446cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownZero &= Mask; 447cfd54181a44db5ac75cd4a7d0a3c6a199ab01c29Duncan Sands KnownOne &= Mask; 448173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 449ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 450173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 451173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 452173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 453173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::URem: { 454173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 455173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt RA = Rem->getValue(); 456173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RA.isPowerOf2()) { 457173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LowBits = (RA - 1); 458173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = LowBits & Mask; 459173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= ~LowBits & Mask; 460173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 461173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 462ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 463173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 464173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 465173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 466173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 467173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Since the result is less than or equal to either operand, any leading 468173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits in either operand must also exist in the result. 469173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 470173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), AllOnes, KnownZero, KnownOne, 471173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 472173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), AllOnes, KnownZero2, KnownOne2, 473173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 474173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 47579abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned Leaders = std::max(KnownZero.countLeadingOnes(), 476173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes()); 477173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 478173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask; 479173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 480173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 481173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 482a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez case Instruction::Alloca: { 4837b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez AllocaInst *AI = cast<AllocaInst>(V); 484173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = AI->getAlignment(); 485a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez if (Align == 0 && TD) 486a276c603b82a11b0bf0b59f0517a69e4b63adeabVictor Hernandez Align = TD->getABITypeAlignment(AI->getType()->getElementType()); 487173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 488173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 489173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 490173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_32(Align)); 491173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 492173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 493173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::GetElementPtr: { 494173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Analyze all of the subscripts of this getelementptr instruction 495173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // to determine if we can prove known low zero bits. 496173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalMask = APInt::getAllOnesValue(BitWidth); 497173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0); 498173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), LocalMask, 499173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero, LocalKnownOne, TD, Depth+1); 500173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = LocalKnownZero.countTrailingOnes(); 501173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 502173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner gep_type_iterator GTI = gep_type_begin(I); 503173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { 504173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *Index = I->getOperand(i); 505173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 506173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle struct member offset arithmetic. 507173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 508173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const StructLayout *SL = TD->getStructLayout(STy); 509173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Idx = cast<ConstantInt>(Index)->getZExtValue(); 510173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t Offset = SL->getElementOffset(Idx); 511173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 512173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_64(Offset)); 513173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 514173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle array index arithmetic. 515173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const Type *IndexedTy = GTI.getIndexedType(); 516173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!IndexedTy->isSized()) return; 5176de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits(); 518777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1; 519173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalMask = APInt::getAllOnesValue(GEPOpiBits); 520173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0); 521173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(Index, LocalMask, 522173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero, LocalKnownOne, TD, Depth+1); 523173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 52479abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned(CountTrailingZeros_64(TypeSize) + 52579abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner LocalKnownZero.countTrailingOnes())); 526173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 527173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 528173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 529173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) & Mask; 530173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 531173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 532173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PHI: { 533173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner PHINode *P = cast<PHINode>(I); 534173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle the case of a simple two-predecessor recurrence PHI. 535173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // There's a lot more that could theoretically be done here, but 536173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // this is sufficient to catch some interesting cases. 537173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (P->getNumIncomingValues() == 2) { 538173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 0; i != 2; ++i) { 539173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *L = P->getIncomingValue(i); 540173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *R = P->getIncomingValue(!i); 541ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *LU = dyn_cast<Operator>(L); 542173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!LU) 543173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner continue; 544ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman unsigned Opcode = LU->getOpcode(); 545173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Check for operations that have the property that if 546173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // both their operands have low zero bits, the result 547173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // will have low zero bits. 548173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Opcode == Instruction::Add || 549173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Sub || 550173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::And || 551173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Or || 552173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Mul) { 553173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LL = LU->getOperand(0); 554173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LR = LU->getOperand(1); 555173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Find a recurrence. 556173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (LL == I) 557173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LR; 558173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (LR == I) 559173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LL; 560173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 561173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 562173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Ok, we have a PHI of the form L op= R. Check for low 563173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits. 564173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getAllOnesValue(BitWidth); 565173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(R, Mask2, KnownZero2, KnownOne2, TD, Depth+1); 566173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask2 = APInt::getLowBitsSet(BitWidth, 567173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes()); 568c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene 569c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene // We need to take the minimum number of known bits 570c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene APInt KnownZero3(KnownZero), KnownOne3(KnownOne); 571c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene ComputeMaskedBits(L, Mask2, KnownZero3, KnownOne3, TD, Depth+1); 572c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene 573173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & 574173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt::getLowBitsSet(BitWidth, 575c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene std::min(KnownZero2.countTrailingOnes(), 576c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene KnownZero3.countTrailingOnes())); 577173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 578173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 579173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 580173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 5819004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman 5829004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Otherwise take the unions of the known bit sets of the operands, 5839004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // taking conservative care to avoid excessive recursion. 5849004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { 5859004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero = APInt::getAllOnesValue(BitWidth); 5869004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne = APInt::getAllOnesValue(BitWidth); 5879004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { 5889004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Skip direct self references. 5899004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (P->getIncomingValue(i) == P) continue; 5909004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman 5919004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero2 = APInt(BitWidth, 0); 5929004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne2 = APInt(BitWidth, 0); 5939004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Recurse, but cap the recursion to one level, because we don't 5949004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // want to waste time spinning around in loops. 5959004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman ComputeMaskedBits(P->getIncomingValue(i), KnownZero | KnownOne, 5969004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero2, KnownOne2, TD, MaxDepth-1); 5979004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero &= KnownZero2; 5989004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne &= KnownOne2; 5999004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // If all bits have been ruled out, there's no need to check 6009004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // more operands. 6019004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (!KnownZero && !KnownOne) 6029004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman break; 6039004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman } 6049004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman } 605173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 606173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 607173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Call: 608173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 609173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner switch (II->getIntrinsicID()) { 610173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 611173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctpop: 612173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctlz: 613173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::cttz: { 614173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LowBits = Log2_32(BitWidth)+1; 615173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 616173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 617173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 618173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 619173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 620173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 621173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 622173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 623173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 624173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 625173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this predicate to simplify operations downstream. Mask is known to be zero 626173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// for bits that V cannot have. 627cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// 628cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// This function is defined on values with integer type, values with pointer 629cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// type (but only if TD is non-null), and vectors of integers. In the case 630cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// where V is a vector, the mask, known zero, and known one values are the 631cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// same width as the vector element, and the bit is set only if it is true 632cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// for all of the elements in the vector. 633173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerbool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, 634846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman const TargetData *TD, unsigned Depth) { 635173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0); 636173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth); 637173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 638173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return (KnownZero & Mask) == Mask; 639173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 640173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 641173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 642173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 643173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeNumSignBits - Return the number of times the sign bit of the 644173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// register is replicated into the other bits. We know that at least 1 bit 645173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// is always equal to the sign bit (itself), but other cases can give us 646173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// information. For example, immediately after an "ashr X, 2", we know that 647173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// the top 3 bits are all equal to each other, so we return 3. 648173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 649173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 'Op' must have a scalar integer type. 650173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 651846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohmanunsigned llvm::ComputeNumSignBits(Value *V, const TargetData *TD, 652846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman unsigned Depth) { 653b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands assert((TD || V->getType()->isIntOrIntVectorTy()) && 654bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman "ComputeNumSignBits requires a TargetData object to operate " 655bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman "on non-integer values!"); 6566de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman const Type *Ty = V->getType(); 657bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman unsigned TyBits = TD ? TD->getTypeSizeInBits(V->getType()->getScalarType()) : 658bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman Ty->getScalarSizeInBits(); 659173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Tmp, Tmp2; 660173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned FirstAnswer = 1; 661173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 662d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // Note that ConstantInt is handled by the general ComputeMaskedBits case 663d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // below. 664d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner 665173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Depth == 6) 666173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return 1; // Limit search depth. 667173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 668ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *U = dyn_cast<Operator>(V); 669ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman switch (Operator::getOpcode(V)) { 670173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 671173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: 67269a008075b29fbe0644ccbeecf1418ef8cca5e24Mon P Wang Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits(); 673173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return ComputeNumSignBits(U->getOperand(0), TD, Depth+1) + Tmp; 674173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 675173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 676173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 677173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ashr X, C -> adds C sign bits. 678173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(U->getOperand(1))) { 679173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp += C->getZExtValue(); 680173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp > TyBits) Tmp = TyBits; 681173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 682173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 683173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 684173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(U->getOperand(1))) { 685173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shl destroys sign bits. 686173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 687173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (C->getZExtValue() >= TyBits || // Bad shift. 688173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner C->getZExtValue() >= Tmp) break; // Shifted all sign bits out. 689173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp - C->getZExtValue(); 690173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 691173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 692173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: 693173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: 694173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: // NOT is handled here. 695173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Logical binary ops preserve the number of sign bits at the worst. 696173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 697173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp != 1) { 698173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 699173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner FirstAnswer = std::min(Tmp, Tmp2); 700173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We computed what we know about the sign bits as our first 701173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // answer. Now proceed to the generic code that uses 702173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ComputeMaskedBits, and pick whichever answer is better. 703173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 704173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 705173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 706173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 707173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 708173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 709173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(2), TD, Depth+1); 710173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2); 711173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 712173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: 713173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Add can have at most one carry bit. Thus we know that the output 714173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 715173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 716173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 717173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 718173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Special case decrementing a value (ADD X, -1): 7190001e56f15215ae4bc5fffb82eec5c4828b888f0Dan Gohman if (ConstantInt *CRHS = dyn_cast<ConstantInt>(U->getOperand(1))) 720173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CRHS->isAllOnesValue()) { 721173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 722173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 723173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(U->getOperand(0), Mask, KnownZero, KnownOne, TD, 724173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 725173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 726173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 727173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 728173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero | APInt(TyBits, 1)) == Mask) 729173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 730173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 731173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If we are subtracting one from a positive number, there is no carry 732173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // out of the result. 733173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 734173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 735173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 736173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 737173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 738173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 7398d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return std::min(Tmp, Tmp2)-1; 740173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 741173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: 742173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 743173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 744173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 745173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle NEG. 746173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(U->getOperand(0))) 747173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CLHS->isNullValue()) { 748173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 749173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 750173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(U->getOperand(1), Mask, KnownZero, KnownOne, 751173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 752173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 753173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 754173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero | APInt(TyBits, 1)) == Mask) 755173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 756173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 757173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be positive (the sign bit is known clear), 758173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the output of the NEG has the same number of sign bits as the input. 759173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 760173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp2; 761173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 762173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Otherwise, we treat this like a SUB. 763173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 764173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 765173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Sub can have at most one carry bit. Thus we know that the output 766173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 767173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 768173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 7698d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return std::min(Tmp, Tmp2)-1; 7708d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner 7718d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner case Instruction::PHI: { 7728d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner PHINode *PN = cast<PHINode>(U); 7738d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // Don't analyze large in-degree PHIs. 7748d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner if (PN->getNumIncomingValues() > 4) break; 7758d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner 7768d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // Take the minimum of all incoming values. This can't infinitely loop 7778d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner // because of our depth threshold. 7788d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner Tmp = ComputeNumSignBits(PN->getIncomingValue(0), TD, Depth+1); 7798d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 7808d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner if (Tmp == 1) return Tmp; 7818d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner Tmp = std::min(Tmp, 7820af20d847ac89f797d613a8a4fc3e7127ccb0b36Evan Cheng ComputeNumSignBits(PN->getIncomingValue(i), TD, Depth+1)); 7838d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner } 7848d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner return Tmp; 7858d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner } 7868d10f9d4a836907d7bf048be507787a9233959c9Chris Lattner 787173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: 788173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FIXME: it's tricky to do anything useful for this, but it is an important 789173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // case for targets like X86. 790173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 791173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 792173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 793173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Finally, if we can prove that the top bits of the result are 0's or 1's, 794173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // use this information. 795173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 796173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 797173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth); 798173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 799173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) { // sign bit is 0 800173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownZero; 801173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else if (KnownOne.isNegative()) { // sign bit is 1; 802173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownOne; 803173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 804173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Nothing known. 805173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return FirstAnswer; 806173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 807173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 808173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 809173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the number of identical bits in the top of the input value. 810173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = ~Mask; 811173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask <<= Mask.getBitWidth()-TyBits; 812173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Return # leading zeros. We use 'min' here in case Val was zero before 813173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shifting. We don't want to return '64' as for an i32 "0". 814173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros())); 815173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 816833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 8172b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// ComputeMultiple - This function computes the integer multiple of Base that 8182b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// equals V. If successful, it returns true and returns the multiple in 8193dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman/// Multiple. If unsuccessful, it returns false. It looks 8202b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez/// through SExt instructions only if LookThroughSExt is true. 8212b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandezbool llvm::ComputeMultiple(Value *V, unsigned Base, Value *&Multiple, 8223dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman bool LookThroughSExt, unsigned Depth) { 8232b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez const unsigned MaxDepth = 6; 8242b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8253dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman assert(V && "No Value?"); 8262b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez assert(Depth <= MaxDepth && "Limit Search Depth"); 827b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands assert(V->getType()->isIntegerTy() && "Not integer or pointer type!"); 8282b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8292b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez const Type *T = V->getType(); 8302b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8313dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman ConstantInt *CI = dyn_cast<ConstantInt>(V); 8322b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8332b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Base == 0) 8342b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return false; 8352b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8362b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Base == 1) { 8372b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = V; 8382b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 8392b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 8402b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8412b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez ConstantExpr *CO = dyn_cast<ConstantExpr>(V); 8422b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Constant *BaseVal = ConstantInt::get(T, Base); 8432b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (CO && CO == BaseVal) { 8442b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // Multiple is 1. 8452b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = ConstantInt::get(T, 1); 8462b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 8472b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 8482b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8492b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (CI && CI->getZExtValue() % Base == 0) { 8502b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = ConstantInt::get(T, CI->getZExtValue() / Base); 8512b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 8522b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 8532b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8542b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Depth == MaxDepth) return false; // Limit search depth. 8552b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8562b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Operator *I = dyn_cast<Operator>(V); 8572b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!I) return false; 8582b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8592b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez switch (I->getOpcode()) { 8602b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez default: break; 86111fe72661dac17efa1564ef6fc212acae4f0c07eChris Lattner case Instruction::SExt: 8622b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!LookThroughSExt) return false; 8632b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // otherwise fall through to ZExt 86411fe72661dac17efa1564ef6fc212acae4f0c07eChris Lattner case Instruction::ZExt: 8653dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman return ComputeMultiple(I->getOperand(0), Base, Multiple, 8663dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman LookThroughSExt, Depth+1); 8672b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez case Instruction::Shl: 8682b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez case Instruction::Mul: { 8692b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Op0 = I->getOperand(0); 8702b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Op1 = I->getOperand(1); 8712b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8722b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (I->getOpcode() == Instruction::Shl) { 8732b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1); 8742b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (!Op1CI) return false; 8752b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // Turn Op0 << Op1 into Op0 * 2^Op1 8762b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez APInt Op1Int = Op1CI->getValue(); 8772b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1); 8782b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Op1 = ConstantInt::get(V->getContext(), 8792b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez APInt(Op1Int.getBitWidth(), 0).set(BitToSet)); 8802b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 8812b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8822b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Mul0 = NULL; 8832b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Value *Mul1 = NULL; 8843dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman bool M0 = ComputeMultiple(Op0, Base, Mul0, 8853dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman LookThroughSExt, Depth+1); 8863dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman bool M1 = ComputeMultiple(Op1, Base, Mul1, 8873dbb9e64d6e9d1e8bf16f75ebe4fe59ffdf93dd3Dan Gohman LookThroughSExt, Depth+1); 8882b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8892b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (M0) { 8902b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (isa<Constant>(Op1) && isa<Constant>(Mul0)) { 8912b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // V == Base * (Mul0 * Op1), so return (Mul0 * Op1) 8922b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = ConstantExpr::getMul(cast<Constant>(Mul0), 8932b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez cast<Constant>(Op1)); 8942b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 8952b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 8962b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 8972b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (ConstantInt *Mul0CI = dyn_cast<ConstantInt>(Mul0)) 8982b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Mul0CI->getValue() == 1) { 8992b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // V == Base * Op1, so return Op1 9002b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = Op1; 9012b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 9022b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 9032b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 9042b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 9052b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (M1) { 9062b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (isa<Constant>(Op0) && isa<Constant>(Mul1)) { 9072b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // V == Base * (Mul1 * Op0), so return (Mul1 * Op0) 9082b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = ConstantExpr::getMul(cast<Constant>(Mul1), 9092b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez cast<Constant>(Op0)); 9102b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 9112b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 9122b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 9132b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (ConstantInt *Mul1CI = dyn_cast<ConstantInt>(Mul1)) 9142b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez if (Mul1CI->getValue() == 1) { 9152b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // V == Base * Op0, so return Op0 9162b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez Multiple = Op0; 9172b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return true; 9182b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 9192b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 9202b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 9212b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez } 9222b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 9232b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez // We could not determine if V is a multiple of Base. 9242b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez return false; 9252b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez} 9262b6705f5e7c7624bd7fe486298c400f1afc15f6cVictor Hernandez 927833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// CannotBeNegativeZero - Return true if we can prove that the specified FP 928833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// value is never equal to -0.0. 929833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 930833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// NOTE: this function will need to be revisited when we support non-default 931833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// rounding modes! 932833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 933833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattnerbool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { 934833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) 935833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return !CFP->getValueAPF().isNegZero(); 936833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 937833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (Depth == 6) 938833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return 1; // Limit search depth. 939833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 940ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman const Operator *I = dyn_cast<Operator>(V); 941833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (I == 0) return false; 942833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 943833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // (add x, 0.0) is guaranteed to return +0.0, not -0.0. 944ae3a0be92e33bc716722aa600983fc1535acb122Dan Gohman if (I->getOpcode() == Instruction::FAdd && 945833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner isa<ConstantFP>(I->getOperand(1)) && 946833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner cast<ConstantFP>(I->getOperand(1))->isNullValue()) 947833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 948833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 949833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sitofp and uitofp turn into +0.0 for zero. 950833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I)) 951833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 952833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 953833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 954833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sqrt(-0.0) = -0.0, no other negative results are possible. 955833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (II->getIntrinsicID() == Intrinsic::sqrt) 956833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return CannotBeNegativeZero(II->getOperand(1), Depth+1); 957833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 958833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const CallInst *CI = dyn_cast<CallInst>(I)) 959833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const Function *F = CI->getCalledFunction()) { 960833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (F->isDeclaration()) { 961f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar // abs(x) != -0.0 962f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar if (F->getName() == "abs") return true; 9639d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen // fabs[lf](x) != -0.0 9649d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabs") return true; 9659d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabsf") return true; 9669d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "fabsl") return true; 9679d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen if (F->getName() == "sqrt" || F->getName() == "sqrtf" || 9689d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen F->getName() == "sqrtl") 9699d06175a15a61b977ebbabd0d9cc738ebfa7870cDale Johannesen return CannotBeNegativeZero(CI->getOperand(1), Depth+1); 970833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 971833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 972833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 973833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return false; 974833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner} 975833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 976e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 977e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// GetLinearExpression - Analyze the specified value as a linear expression: 9781ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// "A*V + B", where A and B are constant integers. Return the scale and offset 9791ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// values as APInts and return V as a Value*. The incoming Value is known to 9801ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// have IntegerType. Note that this looks through extends, so the high bits 9811ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// may not be represented in the result. 982e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattnerstatic Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, 983a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner const TargetData *TD, unsigned Depth) { 9841df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands assert(V->getType()->isIntegerTy() && "Not an integer value"); 985a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner 986a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner // Limit our recursion depth. 987a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner if (Depth == 6) { 988a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner Scale = 1; 989a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner Offset = 0; 990a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner return V; 991a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner } 992e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 993e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 994e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 995e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner switch (BOp->getOpcode()) { 996e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner default: break; 997e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner case Instruction::Or: 998e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 999e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // analyze it. 1000e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), TD)) 1001e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner break; 1002e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // FALL THROUGH. 1003e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner case Instruction::Add: 1004a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1); 1005e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Offset += RHSC->getValue(); 1006e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner return V; 1007e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner case Instruction::Mul: 1008a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1); 1009e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Offset *= RHSC->getValue(); 1010e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Scale *= RHSC->getValue(); 1011e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner return V; 1012e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner case Instruction::Shl: 1013a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, TD, Depth+1); 1014e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Offset <<= RHSC->getValue().getLimitedValue(); 1015e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Scale <<= RHSC->getValue().getLimitedValue(); 1016e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner return V; 1017e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1018e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1019e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1020e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 10211ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner // Since clients don't care about the high bits of the value, just scales and 10221ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner // offsets, we can look through extensions. 10231ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner if (isa<SExtInst>(V) || isa<ZExtInst>(V)) { 10241ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner Value *CastOp = cast<CastInst>(V)->getOperand(0); 10251ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner unsigned OldWidth = Scale.getBitWidth(); 10261ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 10271ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner Scale.trunc(SmallWidth); 10281ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner Offset.trunc(SmallWidth); 1029a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner Value *Result = GetLinearExpression(CastOp, Scale, Offset, TD, Depth+1); 10301ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner Scale.zext(OldWidth); 10311ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner Offset.zext(OldWidth); 10321ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner return Result; 10331ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner } 10341ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner 1035e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Scale = 1; 1036e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Offset = 0; 1037e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner return V; 1038e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner} 1039e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1040e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it 1041e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// into a base pointer with a constant offset and a number of scaled symbolic 1042e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// offsets. 1043e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// 10441ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in 10451ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// the VarIndices vector) are Value*'s that are known to be scaled by the 10461ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// specified amount, but which may have other unrepresented high bits. As such, 10471ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// the gep cannot necessarily be reconstructed from its decomposed form. 10481ce0eaa25fc6ecead5f9bba3c17b8af612d830efChris Lattner/// 1049e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// When TargetData is around, this function is capable of analyzing everything 1050e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// that Value::getUnderlyingObject() can look through. When not, it just looks 1051e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// through pointer casts. 1052e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner/// 1053e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattnerconst Value *llvm::DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, 1054e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner SmallVectorImpl<std::pair<const Value*, int64_t> > &VarIndices, 1055e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner const TargetData *TD) { 1056ab9530ee5d8fec9ed822a82fa21b588952269897Chris Lattner // Limit recursion depth to limit compile time in crazy cases. 1057ab9530ee5d8fec9ed822a82fa21b588952269897Chris Lattner unsigned MaxLookup = 6; 1058ab9530ee5d8fec9ed822a82fa21b588952269897Chris Lattner 1059e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner BaseOffs = 0; 1060ab9530ee5d8fec9ed822a82fa21b588952269897Chris Lattner do { 1061e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // See if this is a bitcast or GEP. 1062e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner const Operator *Op = dyn_cast<Operator>(V); 1063e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (Op == 0) { 1064e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // The only non-operator case we can handle are GlobalAliases. 1065e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 1066e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (!GA->mayBeOverridden()) { 1067e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner V = GA->getAliasee(); 1068e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner continue; 1069e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1070e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1071e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner return V; 1072e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1073e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1074e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (Op->getOpcode() == Instruction::BitCast) { 1075e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner V = Op->getOperand(0); 1076e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner continue; 1077e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1078e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1079e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 1080e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (GEPOp == 0) 1081e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner return V; 1082e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1083e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // Don't attempt to analyze GEPs over unsized objects. 1084e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (!cast<PointerType>(GEPOp->getOperand(0)->getType()) 1085e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner ->getElementType()->isSized()) 1086e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner return V; 1087e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1088e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // If we are lacking TargetData information, we can't compute the offets of 1089e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // elements computed by GEPs. However, we can handle bitcast equivalent 1090e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // GEPs. 1091e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (!TD) { 1092e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (!GEPOp->hasAllZeroIndices()) 1093e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner return V; 1094e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner V = GEPOp->getOperand(0); 1095e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner continue; 1096e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1097e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1098e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 1099e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner gep_type_iterator GTI = gep_type_begin(GEPOp); 1100e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner for (User::const_op_iterator I = GEPOp->op_begin()+1, 1101e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner E = GEPOp->op_end(); I != E; ++I) { 1102e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Value *Index = *I; 1103e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // Compute the (potentially symbolic) offset in bytes for this index. 1104e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI++)) { 1105e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // For a struct, add the member offset. 1106e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 1107e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (FieldNo == 0) continue; 1108e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1109e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo); 1110e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner continue; 1111e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1112e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1113e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // For an array/pointer, add the element offset, explicitly scaled. 1114e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 1115e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (CIdx->isZero()) continue; 1116e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue(); 1117e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner continue; 1118e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1119e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1120e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner uint64_t Scale = TD->getTypeAllocSize(*GTI); 1121e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1122b18004c13c0c494305b0ce1d748049f8c580bd99Chris Lattner // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 1123e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth(); 1124e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner APInt IndexScale(Width, 0), IndexOffset(Width, 0); 1125a650f770d4cfc9aabacddf41851d23c55f23cb8cChris Lattner Index = GetLinearExpression(Index, IndexScale, IndexOffset, TD, 0); 1126e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1127b18004c13c0c494305b0ce1d748049f8c580bd99Chris Lattner // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 1128b18004c13c0c494305b0ce1d748049f8c580bd99Chris Lattner // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 1129e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner BaseOffs += IndexOffset.getZExtValue()*Scale; 1130b18004c13c0c494305b0ce1d748049f8c580bd99Chris Lattner Scale *= IndexScale.getZExtValue(); 1131e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1132e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1133e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // If we already had an occurrance of this index variable, merge this 1134e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // scale into it. For example, we want to handle: 1135e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // A[x][x] -> x*16 + x*4 -> x*20 1136e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // This also ensures that 'x' only appears in the index list once. 1137e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 1138e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (VarIndices[i].first == Index) { 1139e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Scale += VarIndices[i].second; 1140e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner VarIndices.erase(VarIndices.begin()+i); 1141e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner break; 1142e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1143e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1144e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1145e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // Make sure that we have a scale that makes sense for this target's 1146e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // pointer size. 1147e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (unsigned ShiftBits = 64-TD->getPointerSizeInBits()) { 1148e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Scale <<= ShiftBits; 1149e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner Scale >>= ShiftBits; 1150e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1151e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1152e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner if (Scale) 1153e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner VarIndices.push_back(std::make_pair(Index, Scale)); 1154e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner } 1155e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1156e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner // Analyze the base pointer next. 1157e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner V = GEPOp->getOperand(0); 1158ab9530ee5d8fec9ed822a82fa21b588952269897Chris Lattner } while (--MaxLookup); 1159ab9530ee5d8fec9ed822a82fa21b588952269897Chris Lattner 1160ab9530ee5d8fec9ed822a82fa21b588952269897Chris Lattner // If the chain of expressions is too deep, just return early. 1161ab9530ee5d8fec9ed822a82fa21b588952269897Chris Lattner return V; 1162e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner} 1163e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1164e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner 1165b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This is the recursive version of BuildSubAggregate. It takes a few different 1166b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// arguments. Idxs is the index within the nested struct From that we are 1167b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// looking at now (which is of type IndexedType). IdxSkip is the number of 1168b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// indices from Idxs that should be left out when inserting into the resulting 1169b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct. To is the result struct built so far, new insertvalue instructions 1170b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// build on that. 11717db949df789383acce98ef072f08794fdd5bd04eDan Gohmanstatic Value *BuildSubAggregate(Value *From, Value* To, const Type *IndexedType, 11727db949df789383acce98ef072f08794fdd5bd04eDan Gohman SmallVector<unsigned, 10> &Idxs, 11737db949df789383acce98ef072f08794fdd5bd04eDan Gohman unsigned IdxSkip, 11747db949df789383acce98ef072f08794fdd5bd04eDan Gohman Instruction *InsertBefore) { 1175b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const llvm::StructType *STy = llvm::dyn_cast<llvm::StructType>(IndexedType); 1176b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (STy) { 11770a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Save the original To argument so we can modify it 11780a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Value *OrigTo = To; 1179b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // General case, the type indexed by Idxs is a struct 1180b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 1181b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Process each struct element recursively 1182b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.push_back(i); 11830a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Value *PrevTo = To; 1184710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip, 1185ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1186b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.pop_back(); 11870a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (!To) { 11880a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Couldn't find any inserted value for this index? Cleanup 11890a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman while (PrevTo != OrigTo) { 11900a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman InsertValueInst* Del = cast<InsertValueInst>(PrevTo); 11910a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman PrevTo = Del->getAggregateOperand(); 11920a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Del->eraseFromParent(); 11930a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman } 11940a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Stop processing elements 11950a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman break; 11960a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman } 1197b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 11980a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // If we succesfully found a value for each of our subaggregates 11990a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (To) 12000a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return To; 1201b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 12020a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Base case, the type indexed by SourceIdxs is not a struct, or not all of 12030a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // the struct's elements had a value that was inserted directly. In the latter 12040a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // case, perhaps we can't determine each of the subelements individually, but 12050a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // we might be able to find the complete struct somewhere. 12060a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 12070a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Find the value that is at that particular spot 1208ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky Value *V = FindInsertedValue(From, Idxs.begin(), Idxs.end()); 12090a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 12100a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (!V) 12110a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return NULL; 12120a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 12130a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Insert the value in the new (sub) aggregrate 12140a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return llvm::InsertValueInst::Create(To, V, Idxs.begin() + IdxSkip, 12150a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Idxs.end(), "tmp", InsertBefore); 1216b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 1217b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1218b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This helper takes a nested struct and extracts a part of it (which is again a 1219b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct) into a new value. For example, given the struct: 1220b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { a, { b, { c, d }, e } } 1221b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// and the indices "1, 1" this returns 1222b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { c, d }. 1223b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 12240a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// It does this by inserting an insertvalue for each element in the resulting 12250a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// struct, as opposed to just inserting a single struct. This will only work if 12260a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// each of the elements of the substruct are known (ie, inserted into From by an 12270a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// insertvalue instruction somewhere). 1228b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 12290a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// All inserted insertvalue instructions are inserted before InsertBefore 12307db949df789383acce98ef072f08794fdd5bd04eDan Gohmanstatic Value *BuildSubAggregate(Value *From, const unsigned *idx_begin, 1231ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky const unsigned *idx_end, 12327db949df789383acce98ef072f08794fdd5bd04eDan Gohman Instruction *InsertBefore) { 1233977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman assert(InsertBefore && "Must have someplace to insert!"); 1234710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman const Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), 1235710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman idx_begin, 1236710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman idx_end); 12379e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *To = UndefValue::get(IndexedType); 1238b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman SmallVector<unsigned, 10> Idxs(idx_begin, idx_end); 1239b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned IdxSkip = Idxs.size(); 1240b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1241ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); 1242b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 1243b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1244710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// FindInsertedValue - Given an aggregrate and an sequence of indices, see if 1245710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// the scalar value indexed is already around as a register, for example if it 1246710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// were inserted directly into the aggregrate. 12470a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// 12480a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// If InsertBefore is not null, this function will duplicate (modified) 12490a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// insertvalues when a part of a nested struct is extracted. 1250b23d5adbc8230167e711070b9298985de4580f30Matthijs KooijmanValue *llvm::FindInsertedValue(Value *V, const unsigned *idx_begin, 1251ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky const unsigned *idx_end, Instruction *InsertBefore) { 1252b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Nothing to index? Just return V then (this is useful at the end of our 1253b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // recursion) 1254b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (idx_begin == idx_end) 1255b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return V; 1256b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // We have indices, so V should have an indexable type 12571df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) 1258b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman && "Not looking at a struct or array?"); 1259b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman assert(ExtractValueInst::getIndexedType(V->getType(), idx_begin, idx_end) 1260b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman && "Invalid indices for type?"); 1261b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const CompositeType *PTy = cast<CompositeType>(V->getType()); 126276f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson 1263b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (isa<UndefValue>(V)) 12649e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson return UndefValue::get(ExtractValueInst::getIndexedType(PTy, 1265b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman idx_begin, 1266b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman idx_end)); 1267b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman else if (isa<ConstantAggregateZero>(V)) 1268a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson return Constant::getNullValue(ExtractValueInst::getIndexedType(PTy, 126976f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson idx_begin, 127076f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson idx_end)); 1271b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman else if (Constant *C = dyn_cast<Constant>(V)) { 1272b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (isa<ConstantArray>(C) || isa<ConstantStruct>(C)) 1273b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Recursively process this constant 127476f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson return FindInsertedValue(C->getOperand(*idx_begin), idx_begin + 1, 1275ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky idx_end, InsertBefore); 1276b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) { 1277b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Loop the indices for the insertvalue instruction in parallel with the 1278b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested indices 1279b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const unsigned *req_idx = idx_begin; 1280710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 1281710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman i != e; ++i, ++req_idx) { 12829954c76f2c89ab3c70bfe8222534621a86f9085aDuncan Sands if (req_idx == idx_end) { 1283977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman if (InsertBefore) 12840a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // The requested index identifies a part of a nested aggregate. Handle 12850a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // this specially. For example, 12860a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0 12870a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1 12880a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %C = extractvalue {i32, { i32, i32 } } %B, 1 12890a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // This can be changed into 12900a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %A = insertvalue {i32, i32 } undef, i32 10, 0 12910a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %C = insertvalue {i32, i32 } %A, i32 11, 1 12920a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // which allows the unused 0,0 element from the nested struct to be 12930a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // removed. 1294ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky return BuildSubAggregate(V, idx_begin, req_idx, InsertBefore); 1295977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman else 1296977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman // We can't handle this without inserting insertvalues 1297977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman return 0; 12989954c76f2c89ab3c70bfe8222534621a86f9085aDuncan Sands } 1299b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1300b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // This insert value inserts something else than what we are looking for. 1301b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // See if the (aggregrate) value inserted into has the value we are 1302b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // looking for, then. 1303b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (*req_idx != *i) 1304710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman return FindInsertedValue(I->getAggregateOperand(), idx_begin, idx_end, 1305ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1306b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 1307b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we end up here, the indices of the insertvalue match with those 1308b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested (though possibly only partially). Now we recursively look at 1309b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // the inserted value, passing any remaining indices. 1310710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman return FindInsertedValue(I->getInsertedValueOperand(), req_idx, idx_end, 1311ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1312b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) { 1313b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we're extracting a value from an aggregrate that was extracted from 1314b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // something else, we can extract from that something else directly instead. 1315b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // However, we will need to chain I's indices with the requested indices. 1316b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1317b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Calculate the number of indices required 1318b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned size = I->getNumIndices() + (idx_end - idx_begin); 1319b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Allocate some space to put the new indices in 13203faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman SmallVector<unsigned, 5> Idxs; 13213faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman Idxs.reserve(size); 1322b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add indices from the extract value instruction 1323710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 13243faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman i != e; ++i) 13253faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman Idxs.push_back(*i); 1326b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1327b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add requested indices 13283faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman for (const unsigned *i = idx_begin, *e = idx_end; i != e; ++i) 13293faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman Idxs.push_back(*i); 1330b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 13313faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman assert(Idxs.size() == size 1332710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman && "Number of indices added not correct?"); 1333b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 13343faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman return FindInsertedValue(I->getAggregateOperand(), Idxs.begin(), Idxs.end(), 1335ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky InsertBefore); 1336b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 1337b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Otherwise, we don't know (such as, extracting from a function return value 1338b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // or load instruction) 1339b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return 0; 1340b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 13410ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 13420ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// GetConstantStringInfo - This function computes the length of a 13430ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// null-terminated C string pointed to by V. If successful, it returns true 13440ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// and returns the string in Str. If unsuccessful, it returns false. 13450582ae99ba75a556d6ff63b254da327d32ba036fBill Wendlingbool llvm::GetConstantStringInfo(Value *V, std::string &Str, uint64_t Offset, 13460582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling bool StopAtNul) { 13470582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling // If V is NULL then return false; 13480582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (V == NULL) return false; 13490ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 13500ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Look through bitcast instructions. 13510ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) 13520582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(BCI->getOperand(0), Str, Offset, StopAtNul); 13530582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 13540ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // If the value is not a GEP instruction nor a constant expression with a 13550ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // GEP instruction, then return false because ConstantArray can't occur 13560ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // any other way 13570ff39b3feb10477c224138156941234f5fa46f58Evan Cheng User *GEP = 0; 13580ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) { 13590ff39b3feb10477c224138156941234f5fa46f58Evan Cheng GEP = GEPI; 13600ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 13610ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (CE->getOpcode() == Instruction::BitCast) 13620582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(CE->getOperand(0), Str, Offset, StopAtNul); 13630582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (CE->getOpcode() != Instruction::GetElementPtr) 13640582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 13650ff39b3feb10477c224138156941234f5fa46f58Evan Cheng GEP = CE; 13660ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 13670ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 13680ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (GEP) { 13690ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Make sure the GEP has exactly three arguments. 13700582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (GEP->getNumOperands() != 3) 13710582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 13720582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 13730ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Make sure the index-ee is a pointer to array of i8. 13740ff39b3feb10477c224138156941234f5fa46f58Evan Cheng const PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType()); 13750ff39b3feb10477c224138156941234f5fa46f58Evan Cheng const ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType()); 1376b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (AT == 0 || !AT->getElementType()->isIntegerTy(8)) 13770582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 13780ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 13790ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Check to make sure that the first operand of the GEP is an integer and 13800ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // has value 0 so that we are sure we're indexing into the initializer. 13810ff39b3feb10477c224138156941234f5fa46f58Evan Cheng ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1)); 13820582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (FirstIdx == 0 || !FirstIdx->isZero()) 13830582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 13840ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 13850ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // If the second index isn't a ConstantInt, then this is a variable index 13860ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // into the array. If this occurs, we can't say anything meaningful about 13870ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // the string. 13880ff39b3feb10477c224138156941234f5fa46f58Evan Cheng uint64_t StartIdx = 0; 13890582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 13900ff39b3feb10477c224138156941234f5fa46f58Evan Cheng StartIdx = CI->getZExtValue(); 13910582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling else 13920582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 13930582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset, 13940ff39b3feb10477c224138156941234f5fa46f58Evan Cheng StopAtNul); 13950ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 13960ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 13970ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // The GEP instruction, constant or instruction, must reference a global 13980ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // variable that is a constant and is initialized. The referenced constant 13990ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // initializer is the array that we'll use for optimization. 14000ff39b3feb10477c224138156941234f5fa46f58Evan Cheng GlobalVariable* GV = dyn_cast<GlobalVariable>(V); 14018255573835970e7130ba93271972172fb335f2ecDan Gohman if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) 14020582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 14030ff39b3feb10477c224138156941234f5fa46f58Evan Cheng Constant *GlobalInit = GV->getInitializer(); 14040ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 14050ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Handle the ConstantAggregateZero case 14060582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (isa<ConstantAggregateZero>(GlobalInit)) { 14070ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // This is a degenerate case. The initializer is constant zero so the 14080ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // length of the string must be zero. 14090582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str.clear(); 14100582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; 14110582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling } 14120ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 14130ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Must be a Constant Array 14140ff39b3feb10477c224138156941234f5fa46f58Evan Cheng ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit); 1415b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands if (Array == 0 || !Array->getType()->getElementType()->isIntegerTy(8)) 14160582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 14170ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 14180ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Get the number of elements in the array 14190ff39b3feb10477c224138156941234f5fa46f58Evan Cheng uint64_t NumElts = Array->getType()->getNumElements(); 14200ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 14210582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (Offset > NumElts) 14220582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 14230ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 14240ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Traverse the constant array from 'Offset' which is the place the GEP refers 14250ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // to in the array. 14260582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str.reserve(NumElts-Offset); 14270ff39b3feb10477c224138156941234f5fa46f58Evan Cheng for (unsigned i = Offset; i != NumElts; ++i) { 14280ff39b3feb10477c224138156941234f5fa46f58Evan Cheng Constant *Elt = Array->getOperand(i); 14290ff39b3feb10477c224138156941234f5fa46f58Evan Cheng ConstantInt *CI = dyn_cast<ConstantInt>(Elt); 14300582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (!CI) // This array isn't suitable, non-int initializer. 14310582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 14320ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (StopAtNul && CI->isZero()) 14330582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; // we found end of string, success! 14340582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str += (char)CI->getZExtValue(); 14350ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 14360582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 14370ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // The array isn't null terminated, but maybe this is a memcpy, not a strcpy. 14380582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; 14390ff39b3feb10477c224138156941234f5fa46f58Evan Cheng} 144025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 144125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// These next two are very similar to the above, but also look through PHI 144225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// nodes. 144325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher// TODO: See if we can integrate these two together. 144425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 144525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// GetStringLengthH - If we can compute the length of the string pointed to by 144625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// the specified pointer, return 'len+1'. If we can't, return 0. 144725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopherstatic uint64_t GetStringLengthH(Value *V, SmallPtrSet<PHINode*, 32> &PHIs) { 144825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Look through noop bitcast instructions. 144925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) 145025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return GetStringLengthH(BCI->getOperand(0), PHIs); 145125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 145225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If this is a PHI node, there are two cases: either we have already seen it 145325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // or we haven't. 145425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (PHINode *PN = dyn_cast<PHINode>(V)) { 145525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!PHIs.insert(PN)) 145625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return ~0ULL; // already in the set. 145725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 145825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If it was new, see if all the input strings are the same length. 145925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t LenSoFar = ~0ULL; 146025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 146125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len = GetStringLengthH(PN->getIncomingValue(i), PHIs); 146225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len == 0) return 0; // Unknown length -> unknown. 146325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 146425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len == ~0ULL) continue; 146525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 146625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len != LenSoFar && LenSoFar != ~0ULL) 146725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; // Disagree -> unknown. 146825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher LenSoFar = Len; 146925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 147025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 147125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Success, all agree. 147225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return LenSoFar; 147325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 147425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 147525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y) 147625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 147725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs); 147825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 == 0) return 0; 147925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs); 148025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len2 == 0) return 0; 148125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 == ~0ULL) return Len2; 148225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len2 == ~0ULL) return Len1; 148325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (Len1 != Len2) return 0; 148425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return Len1; 148525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 148625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 148725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If the value is not a GEP instruction nor a constant expression with a 148825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // GEP instruction, then return unknown. 148925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher User *GEP = 0; 149025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) { 149125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher GEP = GEPI; 149225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 149325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (CE->getOpcode() != Instruction::GetElementPtr) 149425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 149525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher GEP = CE; 149625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } else { 149725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 149825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 149925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 150025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Make sure the GEP has exactly three arguments. 150125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (GEP->getNumOperands() != 3) 150225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 150325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 150425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Check to make sure that the first operand of the GEP is an integer and 150525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // has value 0 so that we are sure we're indexing into the initializer. 150625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (ConstantInt *Idx = dyn_cast<ConstantInt>(GEP->getOperand(1))) { 150725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!Idx->isZero()) 150825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 150925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } else 151025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 151125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 151225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If the second index isn't a ConstantInt, then this is a variable index 151325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // into the array. If this occurs, we can't say anything meaningful about 151425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // the string. 151525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t StartIdx = 0; 151625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 151725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher StartIdx = CI->getZExtValue(); 151825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher else 151925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 152025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 152125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // The GEP instruction, constant or instruction, must reference a global 152225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // variable that is a constant and is initialized. The referenced constant 152325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // initializer is the array that we'll use for optimization. 152425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher GlobalVariable* GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)); 152525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!GV || !GV->isConstant() || !GV->hasInitializer() || 152625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher GV->mayBeOverridden()) 152725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 152825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher Constant *GlobalInit = GV->getInitializer(); 152925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 153025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Handle the ConstantAggregateZero case, which is a degenerate case. The 153125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // initializer is constant zero so the length of the string must be zero. 153225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (isa<ConstantAggregateZero>(GlobalInit)) 153325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 1; // Len = 0 offset by 1. 153425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 153525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Must be a Constant Array 153625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit); 153725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!Array || !Array->getType()->getElementType()->isIntegerTy(8)) 153825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return false; 153925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 154025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Get the number of elements in the array 154125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t NumElts = Array->getType()->getNumElements(); 154225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 154325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // Traverse the constant array from StartIdx (derived above) which is 154425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // the place the GEP refers to in the array. 154525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher for (unsigned i = StartIdx; i != NumElts; ++i) { 154625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher Constant *Elt = Array->getOperand(i); 154725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher ConstantInt *CI = dyn_cast<ConstantInt>(Elt); 154825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!CI) // This array isn't suitable, non-int initializer. 154925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; 155025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (CI->isZero()) 155125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return i-StartIdx+1; // We found end of string, success! 155225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher } 155325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 155425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return 0; // The array isn't null terminated, conservatively return 'unknown'. 155525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher} 155625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 155725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// GetStringLength - If we can compute the length of the string pointed to by 155825ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher/// the specified pointer, return 'len+1'. If we can't, return 0. 155925ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopheruint64_t llvm::GetStringLength(Value *V) { 156025ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher if (!V->getType()->isPointerTy()) return 0; 156125ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher 156225ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher SmallPtrSet<PHINode*, 32> PHIs; 156325ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher uint64_t Len = GetStringLengthH(V, PHIs); 156425ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return 156525ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher // an empty string as a length. 156625ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher return Len == ~0ULL ? 1 : Len; 156725ec483cfca8d3a3ba8728a4a126e04b92789069Eric Christopher} 1568