ValueTracking.cpp revision b9a4ddbbcd668a94fe945f0648010c281e272889
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" 19173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/IntrinsicInst.h" 2076f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson#include "llvm/LLVMContext.h" 21ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman#include "llvm/Operator.h" 220582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling#include "llvm/Target/TargetData.h" 23173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 24173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/MathExtras.h" 2532a9e7a2654c4aab2e617fbe53140492b3d38066Chris Lattner#include <cstring> 26173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerusing namespace llvm; 27173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 28173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeMaskedBits - Determine which of the bits specified in Mask are 29173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// known to be either zero or one and return them in the KnownZero/KnownOne 30173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// bit sets. This code only analyzes bits in Mask, in order to short-circuit 31173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// processing. 32173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that 33173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// we cannot optimize based on the assumption that it is zero without changing 34173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// it to be an explicit zero. If we don't change it to zero, other code could 35173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// optimized based on the contradictory assumption that it is non-zero. 36173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// Because instcombine aggressively folds operations with undef args anyway, 37173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this won't lose us code quality. 38cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// 39cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// This function is defined on values with integer type, values with pointer 40cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// type (but only if TD is non-null), and vectors of integers. In the case 41cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// where V is a vector, the mask, known zero, and known one values are the 42cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// same width as the vector element, and the bit is set only if it is true 43cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// for all of the elements in the vector. 44173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnervoid llvm::ComputeMaskedBits(Value *V, const APInt &Mask, 45173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt &KnownZero, APInt &KnownOne, 46846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman const TargetData *TD, unsigned Depth) { 479004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman const unsigned MaxDepth = 6; 48173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert(V && "No Value?"); 499004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman assert(Depth <= MaxDepth && "Limit Search Depth"); 5079abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned BitWidth = Mask.getBitWidth(); 516de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman assert((V->getType()->isIntOrIntVector() || isa<PointerType>(V->getType())) && 52173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner "Not integer or pointer type!"); 536de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman assert((!TD || 546de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman TD->getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) && 556de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman (!V->getType()->isIntOrIntVector() || 566de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman V->getType()->getScalarSizeInBits() == BitWidth) && 57173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.getBitWidth() == BitWidth && 58173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.getBitWidth() == BitWidth && 59173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner "V, Mask, KnownOne and KnownZero should have same BitWidth"); 60173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 61173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 62173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know all of the bits for a constant! 63173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = CI->getValue() & Mask; 64173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = ~KnownOne & Mask; 65173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 66173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 676de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // Null and aggregate-zero are all-zeros. 686de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman if (isa<ConstantPointerNull>(V) || 696de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman isa<ConstantAggregateZero>(V)) { 70173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 71173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask; 72173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 73173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 746de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // Handle a constant vector by taking the intersection of the known bits of 756de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman // each element. 766de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) { 776de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman KnownZero.set(); KnownOne.set(); 786de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) { 796de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman APInt KnownZero2(BitWidth, 0), KnownOne2(BitWidth, 0); 806de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman ComputeMaskedBits(CV->getOperand(i), Mask, KnownZero2, KnownOne2, 816de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman TD, Depth); 826de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman KnownZero &= KnownZero2; 836de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman KnownOne &= KnownOne2; 846de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman } 856de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman return; 866de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman } 87173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // The address of an aligned GlobalValue has trailing zeros. 88173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 89173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = GV->getAlignment(); 90004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman if (Align == 0 && TD && GV->getType()->getElementType()->isSized()) { 91004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman const Type *ObjectType = GV->getType()->getElementType(); 92004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman // If the object is defined in the current Module, we'll be giving 93004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman // it the preferred alignment. Otherwise, we have to assume that it 94004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman // may only have the minimum ABI alignment. 95004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman if (!GV->isDeclaration() && !GV->mayBeOverridden()) 96004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman Align = TD->getPrefTypeAlignment(ObjectType); 97004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman else 98004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman Align = TD->getABITypeAlignment(ObjectType); 99004072508bfc66159ca09be26f06b8b05c1bac4eDan Gohman } 100173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 101173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 102173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_32(Align)); 103173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 104173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.clear(); 105173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 106173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 107173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 108173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 109173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.clear(); KnownOne.clear(); // Start out not knowing anything. 110173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 1119004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (Depth == MaxDepth || Mask == 0) 112173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Limit search depth. 113173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 114ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *I = dyn_cast<Operator>(V); 115173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!I) return; 116173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 117173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero2(KnownZero), KnownOne2(KnownOne); 118ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman switch (I->getOpcode()) { 119173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 120173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: { 121173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If either the LHS or the RHS are Zero, the result is zero. 122173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 123173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask & ~KnownZero); 124173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 125173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 126173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 127173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 128173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 129173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 bits are only known if set in both the LHS & RHS. 130173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 131173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 are known to be clear if zero in either the LHS | RHS. 132173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= KnownZero2; 133173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 134173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 135173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: { 136173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 137173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask & ~KnownOne); 138173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 139173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 140173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 141173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 142173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 143173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are only known if clear in both the LHS & RHS. 144173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 145173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in either the LHS | RHS. 146173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= KnownOne2; 147173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 148173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 149173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: { 150173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 151173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask, 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 known if clear or set in both the LHS & RHS. 157173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 158173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in only one of the LHS, RHS. 159173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 160173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = KnownZeroOut; 161173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 162173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 163173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Mul: { 164173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getAllOnesValue(BitWidth); 165173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero, KnownOne, TD,Depth+1); 166173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 167173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 168173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 169173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 170173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 171173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If low bits are zero in either operand, output low known-0 bits. 172173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Also compute a conserative estimate for high known-0 bits. 173173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // More trickiness is possible, but this is sufficient for the 174173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // interesting case of alignment computation. 175173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 176173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = KnownZero.countTrailingOnes() + 177173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes(); 178173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 179173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes(), 180173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner BitWidth) - BitWidth; 181173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 182173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, BitWidth); 183173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(LeadZ, BitWidth); 184173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 185173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt::getHighBitsSet(BitWidth, LeadZ); 186173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= Mask; 187173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 188173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 189173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UDiv: { 190173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // For the purposes of computing leading zeros we can conservatively 191173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // treat a udiv as a logical right shift by the power of 2 known to 192173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // be less than the denominator. 193173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 194173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), 195173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllOnes, KnownZero2, KnownOne2, TD, Depth+1); 196173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = KnownZero2.countLeadingOnes(); 197173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 198173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne2.clear(); 199173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.clear(); 200173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), 201173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllOnes, KnownZero2, KnownOne2, TD, Depth+1); 202173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 203173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RHSUnknownLeadingOnes != BitWidth) 204173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(BitWidth, 205173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 206173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 207173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask; 208173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 209173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 210173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 211173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(2), Mask, KnownZero, KnownOne, TD, Depth+1); 212173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero2, KnownOne2, TD, 213173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 214173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 215173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 216173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 217173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Only known if known in both the LHS and RHS. 218173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 219173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 220173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 221173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPTrunc: 222173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPExt: 223173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToUI: 224173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToSI: 225173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SIToFP: 226173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UIToFP: 227173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Can't work with floating point. 228173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PtrToInt: 229173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::IntToPtr: 230173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We can't handle these if we don't know the pointer size. 231173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 232173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FALL THROUGH and handle them the same as zext/trunc. 233173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::ZExt: 234173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: { 235b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner const Type *SrcTy = I->getOperand(0)->getType(); 236b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner 237b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner unsigned SrcBitWidth; 238173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Note that we handle pointer operands here because of inttoptr/ptrtoint 239173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // which fall through here. 240b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner if (isa<PointerType>(SrcTy)) 241b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner SrcBitWidth = TD->getTypeSizeInBits(SrcTy); 242b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner else 243b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner SrcBitWidth = SrcTy->getScalarSizeInBits(); 244b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner 245173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskIn(Mask); 246173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner MaskIn.zextOrTrunc(SrcBitWidth); 247173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zextOrTrunc(SrcBitWidth); 248173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zextOrTrunc(SrcBitWidth); 249173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD, 250173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 251173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zextOrTrunc(BitWidth); 252173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zextOrTrunc(BitWidth); 253173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Any top bits are known to be zero. 254173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (BitWidth > SrcBitWidth) 255173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 256173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 257173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 258173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::BitCast: { 259173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const Type *SrcTy = I->getOperand(0)->getType(); 2600dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner if ((SrcTy->isInteger() || isa<PointerType>(SrcTy)) && 2610dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner // TODO: For now, not handling conversions like: 2620dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner // (bitcast i64 %x to <2 x i32>) 2630dabb0b177089202dae485d085ed15bd41ef29e6Chris Lattner !isa<VectorType>(I->getType())) { 264173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask, KnownZero, KnownOne, TD, 265173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 266173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 267173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 268173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 269173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 270173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: { 271173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the bits in the result that are not present in the input. 272b9a4ddbbcd668a94fe945f0648010c281e272889Chris Lattner unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); 273173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 274173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskIn(Mask); 275173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner MaskIn.trunc(SrcBitWidth); 276173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.trunc(SrcBitWidth); 277173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.trunc(SrcBitWidth); 278173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD, 279173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 280173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 281173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zext(BitWidth); 282173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zext(BitWidth); 283173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 284173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the sign bit of the input is known set or clear, then we know the 285173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // top bits of the result. 286173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[SrcBitWidth-1]) // Input sign bit known zero 287173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 288173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[SrcBitWidth-1]) // Input sign bit known set 289173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 290173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 291173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 292173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 293173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 294173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 295173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 296173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.lshr(ShiftAmt)); 297173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 298173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 299173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 300173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero <<= ShiftAmt; 301173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne <<= ShiftAmt; 302173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 303173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 304173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 305173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 306173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::LShr: 307173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 308173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 309173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 310173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 311173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 312173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Unsigned shift right. 313173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.shl(ShiftAmt)); 314173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero,KnownOne, TD, 315173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 316173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 317173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 318173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 319173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // high bits known zero. 320173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 321173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 322173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 323173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 324173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 325173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 326173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 327173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 328173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 329173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 330173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Signed shift right. 331173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.shl(ShiftAmt)); 332173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 333173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 334173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 335173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 336173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 337173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 338173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 339173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[BitWidth-ShiftAmt-1]) // New bits are known zero. 340173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= HighBits; 341173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. 342173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= HighBits; 343173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 344173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 345173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 346173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: { 347173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(I->getOperand(0))) { 348173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know that the top bits of C-X are clear if X contains less bits 349173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // than C (i.e. no wrap-around can happen). For example, 20-X is 350173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // positive if we can prove that X is >= 0 and < 16. 351173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!CLHS->getValue().isNegative()) { 352173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros(); 353173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // NLZ can't be BitWidth with no sign bit 354173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 355173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), MaskV, KnownZero2, KnownOne2, 356173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 357173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 358173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If all of the MaskV bits are known to be zero, then we know the 359173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // output top bits are zero, because we now know that the output is 360173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // from [0-C]. 361173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero2 & MaskV) == MaskV) { 362173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned NLZ2 = CLHS->getValue().countLeadingZeros(); 363173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Top bits known zero. 364173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask; 365173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 366173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 367173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 368173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 369173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // fall through 370173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: { 3713925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // If one of the operands has trailing zeros, than the bits that the 3723925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // other operand has in those bit positions will be preserved in the 3733925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // result. For an add, this works with either operand. For a subtract, 3743925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // this only works if the known zeros are in the right operand. 3753925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); 3763925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask2 = APInt::getLowBitsSet(BitWidth, 3773925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman BitWidth - Mask.countLeadingZeros()); 3783925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman ComputeMaskedBits(I->getOperand(0), Mask2, LHSKnownZero, LHSKnownOne, TD, 379173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 3803925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman assert((LHSKnownZero & LHSKnownOne) == 0 && 3813925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman "Bits known to be one AND zero?"); 3823925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman unsigned LHSKnownZeroOut = LHSKnownZero.countTrailingOnes(); 383173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 384173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero2, KnownOne2, TD, 385173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 386173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 3873925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman unsigned RHSKnownZeroOut = KnownZero2.countTrailingOnes(); 388173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 3893925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // Determine which operand has more trailing zeros, and use that 3903925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // many bits from the other operand. 3913925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman if (LHSKnownZeroOut > RHSKnownZeroOut) { 392ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman if (I->getOpcode() == Instruction::Add) { 3933925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask = APInt::getLowBitsSet(BitWidth, LHSKnownZeroOut); 3943925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= KnownZero2 & Mask; 3953925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownOne |= KnownOne2 & Mask; 3963925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } else { 3973925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // If the known zeros are in the left operand for a subtract, 3983925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman // fall back to the minimum known zeros in both operands. 3993925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= APInt::getLowBitsSet(BitWidth, 4003925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman std::min(LHSKnownZeroOut, 4013925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman RHSKnownZeroOut)); 4023925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } 4033925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } else if (RHSKnownZeroOut >= LHSKnownZeroOut) { 4043925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman APInt Mask = APInt::getLowBitsSet(BitWidth, RHSKnownZeroOut); 4053925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownZero |= LHSKnownZero & Mask; 4063925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman KnownOne |= LHSKnownOne & Mask; 4073925043af0ecf1f0a6158c5007c1186797a252cbDan Gohman } 408173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 409173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 410173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SRem: 411173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 412173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt RA = Rem->getValue(); 413173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RA.isPowerOf2() || (-RA).isPowerOf2()) { 414173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LowBits = RA.isStrictlyPositive() ? (RA - 1) : ~RA; 415173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 416173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 417173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 418173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 419a60832b0187642d01fd726dc766cd62587f6add0Dan Gohman // If the sign bit of the first operand is zero, the sign bit of 420a60832b0187642d01fd726dc766cd62587f6add0Dan Gohman // the result is zero. If the first operand has no one bits below 421a60832b0187642d01fd726dc766cd62587f6add0Dan Gohman // the second operand's single 1 bit, its sign will be zero. 422173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 423173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2 |= ~LowBits; 424173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 425173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= KnownZero2 & Mask; 426173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 427173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 428173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 429173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 430173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 431173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::URem: { 432173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 433173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt RA = Rem->getValue(); 434173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RA.isPowerOf2()) { 435173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LowBits = (RA - 1); 436173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = LowBits & Mask; 437173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= ~LowBits & Mask; 438173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 439173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 440173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 441173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 442173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 443173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 444173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 445173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Since the result is less than or equal to either operand, any leading 446173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits in either operand must also exist in the result. 447173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 448173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), AllOnes, KnownZero, KnownOne, 449173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 450173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), AllOnes, KnownZero2, KnownOne2, 451173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 452173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 45379abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned Leaders = std::max(KnownZero.countLeadingOnes(), 454173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes()); 455173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 456173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask; 457173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 458173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 459173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 460173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Alloca: 461173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Malloc: { 462173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllocationInst *AI = cast<AllocationInst>(V); 463173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = AI->getAlignment(); 464173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align == 0 && TD) { 465173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (isa<AllocaInst>(AI)) 4660f2831c820151aa6f2cd6a8bd7b6b633b1035524Chris Lattner Align = TD->getABITypeAlignment(AI->getType()->getElementType()); 467173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (isa<MallocInst>(AI)) { 468173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Malloc returns maximally aligned memory. 469173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Align = TD->getABITypeAlignment(AI->getType()->getElementType()); 470173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Align = 471173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner std::max(Align, 4721d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson (unsigned)TD->getABITypeAlignment( 4731d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Type::getDoubleTy(V->getContext()))); 474173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Align = 475173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner std::max(Align, 4761d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson (unsigned)TD->getABITypeAlignment( 4771d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Type::getInt64Ty(V->getContext()))); 478173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 479173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 480173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 481173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 482173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 483173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_32(Align)); 484173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 485173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 486173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::GetElementPtr: { 487173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Analyze all of the subscripts of this getelementptr instruction 488173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // to determine if we can prove known low zero bits. 489173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalMask = APInt::getAllOnesValue(BitWidth); 490173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0); 491173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), LocalMask, 492173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero, LocalKnownOne, TD, Depth+1); 493173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = LocalKnownZero.countTrailingOnes(); 494173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 495173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner gep_type_iterator GTI = gep_type_begin(I); 496173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { 497173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *Index = I->getOperand(i); 498173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 499173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle struct member offset arithmetic. 500173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 501173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const StructLayout *SL = TD->getStructLayout(STy); 502173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Idx = cast<ConstantInt>(Index)->getZExtValue(); 503173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t Offset = SL->getElementOffset(Idx); 504173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 505173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_64(Offset)); 506173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 507173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle array index arithmetic. 508173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const Type *IndexedTy = GTI.getIndexedType(); 509173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!IndexedTy->isSized()) return; 5106de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits(); 511777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1; 512173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalMask = APInt::getAllOnesValue(GEPOpiBits); 513173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0); 514173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(Index, LocalMask, 515173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero, LocalKnownOne, TD, Depth+1); 516173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 51779abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner unsigned(CountTrailingZeros_64(TypeSize) + 51879abedb83a4dd7d3583c7ca6df8283079acc3ba5Chris Lattner LocalKnownZero.countTrailingOnes())); 519173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 520173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 521173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 522173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) & Mask; 523173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 524173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 525173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PHI: { 526173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner PHINode *P = cast<PHINode>(I); 527173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle the case of a simple two-predecessor recurrence PHI. 528173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // There's a lot more that could theoretically be done here, but 529173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // this is sufficient to catch some interesting cases. 530173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (P->getNumIncomingValues() == 2) { 531173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 0; i != 2; ++i) { 532173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *L = P->getIncomingValue(i); 533173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *R = P->getIncomingValue(!i); 534ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *LU = dyn_cast<Operator>(L); 535173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!LU) 536173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner continue; 537ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman unsigned Opcode = LU->getOpcode(); 538173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Check for operations that have the property that if 539173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // both their operands have low zero bits, the result 540173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // will have low zero bits. 541173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Opcode == Instruction::Add || 542173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Sub || 543173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::And || 544173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Or || 545173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Mul) { 546173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LL = LU->getOperand(0); 547173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LR = LU->getOperand(1); 548173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Find a recurrence. 549173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (LL == I) 550173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LR; 551173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (LR == I) 552173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LL; 553173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 554173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 555173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Ok, we have a PHI of the form L op= R. Check for low 556173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits. 557173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getAllOnesValue(BitWidth); 558173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(R, Mask2, KnownZero2, KnownOne2, TD, Depth+1); 559173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask2 = APInt::getLowBitsSet(BitWidth, 560173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes()); 561c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene 562c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene // We need to take the minimum number of known bits 563c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene APInt KnownZero3(KnownZero), KnownOne3(KnownOne); 564c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene ComputeMaskedBits(L, Mask2, KnownZero3, KnownOne3, TD, Depth+1); 565c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene 566173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & 567173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt::getLowBitsSet(BitWidth, 568c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene std::min(KnownZero2.countTrailingOnes(), 569c714f1309049b2fd9e4ab68c8a7b480c63a4be0cDavid Greene KnownZero3.countTrailingOnes())); 570173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 571173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 572173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 573173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 5749004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman 5759004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Otherwise take the unions of the known bit sets of the operands, 5769004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // taking conservative care to avoid excessive recursion. 5779004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { 5789004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero = APInt::getAllOnesValue(BitWidth); 5799004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne = APInt::getAllOnesValue(BitWidth); 5809004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) { 5819004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Skip direct self references. 5829004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (P->getIncomingValue(i) == P) continue; 5839004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman 5849004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero2 = APInt(BitWidth, 0); 5859004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne2 = APInt(BitWidth, 0); 5869004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // Recurse, but cap the recursion to one level, because we don't 5879004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // want to waste time spinning around in loops. 5889004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman ComputeMaskedBits(P->getIncomingValue(i), KnownZero | KnownOne, 5899004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero2, KnownOne2, TD, MaxDepth-1); 5909004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownZero &= KnownZero2; 5919004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman KnownOne &= KnownOne2; 5929004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // If all bits have been ruled out, there's no need to check 5939004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman // more operands. 5949004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman if (!KnownZero && !KnownOne) 5959004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman break; 5969004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman } 5979004c8afd4bf7b3f27f4a4f8fd069379afa97c83Dan Gohman } 598173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 599173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 600173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Call: 601173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 602173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner switch (II->getIntrinsicID()) { 603173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 604173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctpop: 605173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctlz: 606173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::cttz: { 607173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LowBits = Log2_32(BitWidth)+1; 608173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 609173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 610173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 611173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 612173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 613173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 614173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 615173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 616173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 617173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 618173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this predicate to simplify operations downstream. Mask is known to be zero 619173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// for bits that V cannot have. 620cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// 621cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// This function is defined on values with integer type, values with pointer 622cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// type (but only if TD is non-null), and vectors of integers. In the case 623cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// where V is a vector, the mask, known zero, and known one values are the 624cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// same width as the vector element, and the bit is set only if it is true 625cf5128ec01f45d2bf7eadc20b253cb44486e473fChris Lattner/// for all of the elements in the vector. 626173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerbool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, 627846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman const TargetData *TD, unsigned Depth) { 628173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0); 629173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth); 630173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 631173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return (KnownZero & Mask) == Mask; 632173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 633173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 634173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 635173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 636173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeNumSignBits - Return the number of times the sign bit of the 637173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// register is replicated into the other bits. We know that at least 1 bit 638173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// is always equal to the sign bit (itself), but other cases can give us 639173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// information. For example, immediately after an "ashr X, 2", we know that 640173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// the top 3 bits are all equal to each other, so we return 3. 641173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 642173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 'Op' must have a scalar integer type. 643173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 644846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohmanunsigned llvm::ComputeNumSignBits(Value *V, const TargetData *TD, 645846a2f2703f6bb894098274964faf5dce0b68c4dDan Gohman unsigned Depth) { 646bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman assert((TD || V->getType()->isIntOrIntVector()) && 647bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman "ComputeNumSignBits requires a TargetData object to operate " 648bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman "on non-integer values!"); 6496de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman const Type *Ty = V->getType(); 650bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman unsigned TyBits = TD ? TD->getTypeSizeInBits(V->getType()->getScalarType()) : 651bd5ce52740700bb482fb2b5a03bce781acbf2941Dan Gohman Ty->getScalarSizeInBits(); 652173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Tmp, Tmp2; 653173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned FirstAnswer = 1; 654173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 655d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // Note that ConstantInt is handled by the general ComputeMaskedBits case 656d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // below. 657d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner 658173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Depth == 6) 659173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return 1; // Limit search depth. 660173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 661ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman Operator *U = dyn_cast<Operator>(V); 662ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman switch (Operator::getOpcode(V)) { 663173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 664173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: 665173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = TyBits-cast<IntegerType>(U->getOperand(0)->getType())->getBitWidth(); 666173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return ComputeNumSignBits(U->getOperand(0), TD, Depth+1) + Tmp; 667173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 668173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 669173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 670173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ashr X, C -> adds C sign bits. 671173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(U->getOperand(1))) { 672173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp += C->getZExtValue(); 673173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp > TyBits) Tmp = TyBits; 674173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 675173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 676173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 677173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(U->getOperand(1))) { 678173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shl destroys sign bits. 679173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 680173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (C->getZExtValue() >= TyBits || // Bad shift. 681173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner C->getZExtValue() >= Tmp) break; // Shifted all sign bits out. 682173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp - C->getZExtValue(); 683173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 684173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 685173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: 686173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: 687173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: // NOT is handled here. 688173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Logical binary ops preserve the number of sign bits at the worst. 689173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 690173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp != 1) { 691173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 692173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner FirstAnswer = std::min(Tmp, Tmp2); 693173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We computed what we know about the sign bits as our first 694173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // answer. Now proceed to the generic code that uses 695173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ComputeMaskedBits, and pick whichever answer is better. 696173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 697173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 698173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 699173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 700173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 701173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 702173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(2), TD, Depth+1); 703173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2); 704173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 705173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: 706173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Add can have at most one carry bit. Thus we know that the output 707173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 708173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 709173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 710173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 711173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Special case decrementing a value (ADD X, -1): 7120001e56f15215ae4bc5fffb82eec5c4828b888f0Dan Gohman if (ConstantInt *CRHS = dyn_cast<ConstantInt>(U->getOperand(1))) 713173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CRHS->isAllOnesValue()) { 714173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 715173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 716173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(U->getOperand(0), Mask, KnownZero, KnownOne, TD, 717173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 718173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 719173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 720173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 721173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero | APInt(TyBits, 1)) == Mask) 722173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 723173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 724173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If we are subtracting one from a positive number, there is no carry 725173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // out of the result. 726173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 727173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 728173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 729173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 730173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 731173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 732173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2)-1; 733173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 734173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 735173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: 736173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 737173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 738173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 739173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle NEG. 740173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(U->getOperand(0))) 741173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CLHS->isNullValue()) { 742173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 743173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 744173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(U->getOperand(1), Mask, KnownZero, KnownOne, 745173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 746173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 747173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 748173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero | APInt(TyBits, 1)) == Mask) 749173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 750173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 751173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be positive (the sign bit is known clear), 752173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the output of the NEG has the same number of sign bits as the input. 753173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 754173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp2; 755173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 756173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Otherwise, we treat this like a SUB. 757173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 758173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 759173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Sub can have at most one carry bit. Thus we know that the output 760173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 761173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 762173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 763173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2)-1; 764173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 765173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: 766173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FIXME: it's tricky to do anything useful for this, but it is an important 767173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // case for targets like X86. 768173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 769173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 770173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 771173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Finally, if we can prove that the top bits of the result are 0's or 1's, 772173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // use this information. 773173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 774173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 775173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth); 776173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 777173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) { // sign bit is 0 778173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownZero; 779173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else if (KnownOne.isNegative()) { // sign bit is 1; 780173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownOne; 781173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 782173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Nothing known. 783173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return FirstAnswer; 784173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 785173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 786173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 787173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the number of identical bits in the top of the input value. 788173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = ~Mask; 789173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask <<= Mask.getBitWidth()-TyBits; 790173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Return # leading zeros. We use 'min' here in case Val was zero before 791173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shifting. We don't want to return '64' as for an i32 "0". 792173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros())); 793173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 794833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 795833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// CannotBeNegativeZero - Return true if we can prove that the specified FP 796833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// value is never equal to -0.0. 797833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 798833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// NOTE: this function will need to be revisited when we support non-default 799833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// rounding modes! 800833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 801833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattnerbool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { 802833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) 803833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return !CFP->getValueAPF().isNegZero(); 804833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 805833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (Depth == 6) 806833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return 1; // Limit search depth. 807833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 808ca178908c8dc2303a1fb54a8a93bab0f0b964e11Dan Gohman const Operator *I = dyn_cast<Operator>(V); 809833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (I == 0) return false; 810833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 811833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // (add x, 0.0) is guaranteed to return +0.0, not -0.0. 812ae3a0be92e33bc716722aa600983fc1535acb122Dan Gohman if (I->getOpcode() == Instruction::FAdd && 813833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner isa<ConstantFP>(I->getOperand(1)) && 814833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner cast<ConstantFP>(I->getOperand(1))->isNullValue()) 815833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 816833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 817833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sitofp and uitofp turn into +0.0 for zero. 818833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I)) 819833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 820833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 821833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 822833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sqrt(-0.0) = -0.0, no other negative results are possible. 823833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (II->getIntrinsicID() == Intrinsic::sqrt) 824833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return CannotBeNegativeZero(II->getOperand(1), Depth+1); 825833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 826833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const CallInst *CI = dyn_cast<CallInst>(I)) 827833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const Function *F = CI->getCalledFunction()) { 828833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (F->isDeclaration()) { 829f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar // abs(x) != -0.0 830f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar if (F->getName() == "abs") return true; 831f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar // abs[lf](x) != -0.0 832f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar if (F->getName() == "absf") return true; 833f0443c1eb44d737d9bd78962932fc80f74c6113cDaniel Dunbar if (F->getName() == "absl") return true; 834833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 835833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 836833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 837833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return false; 838833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner} 839833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 840b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This is the recursive version of BuildSubAggregate. It takes a few different 841b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// arguments. Idxs is the index within the nested struct From that we are 842b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// looking at now (which is of type IndexedType). IdxSkip is the number of 843b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// indices from Idxs that should be left out when inserting into the resulting 844b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct. To is the result struct built so far, new insertvalue instructions 845b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// build on that. 8467db949df789383acce98ef072f08794fdd5bd04eDan Gohmanstatic Value *BuildSubAggregate(Value *From, Value* To, const Type *IndexedType, 8477db949df789383acce98ef072f08794fdd5bd04eDan Gohman SmallVector<unsigned, 10> &Idxs, 8487db949df789383acce98ef072f08794fdd5bd04eDan Gohman unsigned IdxSkip, 8497db949df789383acce98ef072f08794fdd5bd04eDan Gohman LLVMContext &Context, 8507db949df789383acce98ef072f08794fdd5bd04eDan Gohman Instruction *InsertBefore) { 851b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const llvm::StructType *STy = llvm::dyn_cast<llvm::StructType>(IndexedType); 852b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (STy) { 8530a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Save the original To argument so we can modify it 8540a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Value *OrigTo = To; 855b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // General case, the type indexed by Idxs is a struct 856b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 857b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Process each struct element recursively 858b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.push_back(i); 8590a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Value *PrevTo = To; 860710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip, 86176f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson Context, InsertBefore); 862b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.pop_back(); 8630a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (!To) { 8640a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Couldn't find any inserted value for this index? Cleanup 8650a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman while (PrevTo != OrigTo) { 8660a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman InsertValueInst* Del = cast<InsertValueInst>(PrevTo); 8670a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman PrevTo = Del->getAggregateOperand(); 8680a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Del->eraseFromParent(); 8690a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman } 8700a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Stop processing elements 8710a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman break; 8720a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman } 873b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 8740a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // If we succesfully found a value for each of our subaggregates 8750a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (To) 8760a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return To; 877b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 8780a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Base case, the type indexed by SourceIdxs is not a struct, or not all of 8790a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // the struct's elements had a value that was inserted directly. In the latter 8800a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // case, perhaps we can't determine each of the subelements individually, but 8810a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // we might be able to find the complete struct somewhere. 8820a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 8830a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Find the value that is at that particular spot 88476f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson Value *V = FindInsertedValue(From, Idxs.begin(), Idxs.end(), Context); 8850a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 8860a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman if (!V) 8870a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return NULL; 8880a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman 8890a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // Insert the value in the new (sub) aggregrate 8900a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman return llvm::InsertValueInst::Create(To, V, Idxs.begin() + IdxSkip, 8910a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman Idxs.end(), "tmp", InsertBefore); 892b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 893b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 894b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This helper takes a nested struct and extracts a part of it (which is again a 895b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct) into a new value. For example, given the struct: 896b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { a, { b, { c, d }, e } } 897b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// and the indices "1, 1" this returns 898b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { c, d }. 899b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 9000a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// It does this by inserting an insertvalue for each element in the resulting 9010a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// struct, as opposed to just inserting a single struct. This will only work if 9020a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// each of the elements of the substruct are known (ie, inserted into From by an 9030a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// insertvalue instruction somewhere). 904b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 9050a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman// All inserted insertvalue instructions are inserted before InsertBefore 9067db949df789383acce98ef072f08794fdd5bd04eDan Gohmanstatic Value *BuildSubAggregate(Value *From, const unsigned *idx_begin, 9077db949df789383acce98ef072f08794fdd5bd04eDan Gohman const unsigned *idx_end, LLVMContext &Context, 9087db949df789383acce98ef072f08794fdd5bd04eDan Gohman Instruction *InsertBefore) { 909977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman assert(InsertBefore && "Must have someplace to insert!"); 910710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman const Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), 911710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman idx_begin, 912710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman idx_end); 9139e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson Value *To = UndefValue::get(IndexedType); 914b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman SmallVector<unsigned, 10> Idxs(idx_begin, idx_end); 915b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned IdxSkip = Idxs.size(); 916b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 91776f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, 91876f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson Context, InsertBefore); 919b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 920b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 921710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// FindInsertedValue - Given an aggregrate and an sequence of indices, see if 922710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// the scalar value indexed is already around as a register, for example if it 923710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// were inserted directly into the aggregrate. 9240a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// 9250a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// If InsertBefore is not null, this function will duplicate (modified) 9260a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman/// insertvalues when a part of a nested struct is extracted. 927b23d5adbc8230167e711070b9298985de4580f30Matthijs KooijmanValue *llvm::FindInsertedValue(Value *V, const unsigned *idx_begin, 928e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson const unsigned *idx_end, LLVMContext &Context, 92976f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson Instruction *InsertBefore) { 930b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Nothing to index? Just return V then (this is useful at the end of our 931b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // recursion) 932b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (idx_begin == idx_end) 933b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return V; 934b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // We have indices, so V should have an indexable type 935b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman assert((isa<StructType>(V->getType()) || isa<ArrayType>(V->getType())) 936b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman && "Not looking at a struct or array?"); 937b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman assert(ExtractValueInst::getIndexedType(V->getType(), idx_begin, idx_end) 938b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman && "Invalid indices for type?"); 939b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const CompositeType *PTy = cast<CompositeType>(V->getType()); 94076f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson 941b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (isa<UndefValue>(V)) 9429e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson return UndefValue::get(ExtractValueInst::getIndexedType(PTy, 943b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman idx_begin, 944b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman idx_end)); 945b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman else if (isa<ConstantAggregateZero>(V)) 946a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson return Constant::getNullValue(ExtractValueInst::getIndexedType(PTy, 94776f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson idx_begin, 94876f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson idx_end)); 949b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman else if (Constant *C = dyn_cast<Constant>(V)) { 950b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (isa<ConstantArray>(C) || isa<ConstantStruct>(C)) 951b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Recursively process this constant 95276f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson return FindInsertedValue(C->getOperand(*idx_begin), idx_begin + 1, 95376f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson idx_end, Context, InsertBefore); 954b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) { 955b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Loop the indices for the insertvalue instruction in parallel with the 956b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested indices 957b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const unsigned *req_idx = idx_begin; 958710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 959710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman i != e; ++i, ++req_idx) { 9609954c76f2c89ab3c70bfe8222534621a86f9085aDuncan Sands if (req_idx == idx_end) { 961977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman if (InsertBefore) 9620a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // The requested index identifies a part of a nested aggregate. Handle 9630a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // this specially. For example, 9640a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %A = insertvalue { i32, {i32, i32 } } undef, i32 10, 1, 0 9650a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %B = insertvalue { i32, {i32, i32 } } %A, i32 11, 1, 1 9660a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %C = extractvalue {i32, { i32, i32 } } %B, 1 9670a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // This can be changed into 9680a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %A = insertvalue {i32, i32 } undef, i32 10, 0 9690a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // %C = insertvalue {i32, i32 } %A, i32 11, 1 9700a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // which allows the unused 0,0 element from the nested struct to be 9710a9aaf46bee75540db16603dd60f7d3bc597842dMatthijs Kooijman // removed. 97276f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson return BuildSubAggregate(V, idx_begin, req_idx, 97376f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson Context, InsertBefore); 974977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman else 975977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman // We can't handle this without inserting insertvalues 976977289121996f0afb781592f92a4aee1be3010feMatthijs Kooijman return 0; 9779954c76f2c89ab3c70bfe8222534621a86f9085aDuncan Sands } 978b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 979b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // This insert value inserts something else than what we are looking for. 980b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // See if the (aggregrate) value inserted into has the value we are 981b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // looking for, then. 982b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (*req_idx != *i) 983710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman return FindInsertedValue(I->getAggregateOperand(), idx_begin, idx_end, 98476f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson Context, InsertBefore); 985b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 986b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we end up here, the indices of the insertvalue match with those 987b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested (though possibly only partially). Now we recursively look at 988b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // the inserted value, passing any remaining indices. 989710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman return FindInsertedValue(I->getInsertedValueOperand(), req_idx, idx_end, 99076f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson Context, InsertBefore); 991b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) { 992b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we're extracting a value from an aggregrate that was extracted from 993b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // something else, we can extract from that something else directly instead. 994b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // However, we will need to chain I's indices with the requested indices. 995b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 996b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Calculate the number of indices required 997b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned size = I->getNumIndices() + (idx_end - idx_begin); 998b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Allocate some space to put the new indices in 9993faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman SmallVector<unsigned, 5> Idxs; 10003faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman Idxs.reserve(size); 1001b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add indices from the extract value instruction 1002710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 10033faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman i != e; ++i) 10043faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman Idxs.push_back(*i); 1005b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 1006b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add requested indices 10073faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman for (const unsigned *i = idx_begin, *e = idx_end; i != e; ++i) 10083faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman Idxs.push_back(*i); 1009b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 10103faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman assert(Idxs.size() == size 1011710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman && "Number of indices added not correct?"); 1012b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 10133faf9df08ff389028050bfbccbef571061bf7cc1Matthijs Kooijman return FindInsertedValue(I->getAggregateOperand(), Idxs.begin(), Idxs.end(), 101476f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson Context, InsertBefore); 1015b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 1016b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Otherwise, we don't know (such as, extracting from a function return value 1017b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // or load instruction) 1018b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return 0; 1019b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 10200ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 10210ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// GetConstantStringInfo - This function computes the length of a 10220ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// null-terminated C string pointed to by V. If successful, it returns true 10230ff39b3feb10477c224138156941234f5fa46f58Evan Cheng/// and returns the string in Str. If unsuccessful, it returns false. 10240582ae99ba75a556d6ff63b254da327d32ba036fBill Wendlingbool llvm::GetConstantStringInfo(Value *V, std::string &Str, uint64_t Offset, 10250582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling bool StopAtNul) { 10260582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling // If V is NULL then return false; 10270582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (V == NULL) return false; 10280ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 10290ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Look through bitcast instructions. 10300ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) 10310582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(BCI->getOperand(0), Str, Offset, StopAtNul); 10320582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 10330ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // If the value is not a GEP instruction nor a constant expression with a 10340ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // GEP instruction, then return false because ConstantArray can't occur 10350ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // any other way 10360ff39b3feb10477c224138156941234f5fa46f58Evan Cheng User *GEP = 0; 10370ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(V)) { 10380ff39b3feb10477c224138156941234f5fa46f58Evan Cheng GEP = GEPI; 10390ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 10400ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (CE->getOpcode() == Instruction::BitCast) 10410582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(CE->getOperand(0), Str, Offset, StopAtNul); 10420582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (CE->getOpcode() != Instruction::GetElementPtr) 10430582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 10440ff39b3feb10477c224138156941234f5fa46f58Evan Cheng GEP = CE; 10450ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 10460ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 10470ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (GEP) { 10480ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Make sure the GEP has exactly three arguments. 10490582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (GEP->getNumOperands() != 3) 10500582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 10510582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 10520ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Make sure the index-ee is a pointer to array of i8. 10530ff39b3feb10477c224138156941234f5fa46f58Evan Cheng const PointerType *PT = cast<PointerType>(GEP->getOperand(0)->getType()); 10540ff39b3feb10477c224138156941234f5fa46f58Evan Cheng const ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType()); 10551d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson if (AT == 0 || AT->getElementType() != Type::getInt8Ty(V->getContext())) 10560582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 10570ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 10580ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Check to make sure that the first operand of the GEP is an integer and 10590ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // has value 0 so that we are sure we're indexing into the initializer. 10600ff39b3feb10477c224138156941234f5fa46f58Evan Cheng ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1)); 10610582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (FirstIdx == 0 || !FirstIdx->isZero()) 10620582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 10630ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 10640ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // If the second index isn't a ConstantInt, then this is a variable index 10650ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // into the array. If this occurs, we can't say anything meaningful about 10660ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // the string. 10670ff39b3feb10477c224138156941234f5fa46f58Evan Cheng uint64_t StartIdx = 0; 10680582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) 10690ff39b3feb10477c224138156941234f5fa46f58Evan Cheng StartIdx = CI->getZExtValue(); 10700582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling else 10710582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 10720582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return GetConstantStringInfo(GEP->getOperand(0), Str, StartIdx+Offset, 10730ff39b3feb10477c224138156941234f5fa46f58Evan Cheng StopAtNul); 10740ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 10750ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 1076148843b0ce6774866132821e866a5d2669300401Torok Edwin if (MDString *MDStr = dyn_cast<MDString>(V)) { 1077148843b0ce6774866132821e866a5d2669300401Torok Edwin Str = MDStr->getString(); 1078148843b0ce6774866132821e866a5d2669300401Torok Edwin return true; 1079148843b0ce6774866132821e866a5d2669300401Torok Edwin } 1080148843b0ce6774866132821e866a5d2669300401Torok Edwin 10810ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // The GEP instruction, constant or instruction, must reference a global 10820ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // variable that is a constant and is initialized. The referenced constant 10830ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // initializer is the array that we'll use for optimization. 10840ff39b3feb10477c224138156941234f5fa46f58Evan Cheng GlobalVariable* GV = dyn_cast<GlobalVariable>(V); 10858255573835970e7130ba93271972172fb335f2ecDan Gohman if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) 10860582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 10870ff39b3feb10477c224138156941234f5fa46f58Evan Cheng Constant *GlobalInit = GV->getInitializer(); 10880ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 10890ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Handle the ConstantAggregateZero case 10900582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (isa<ConstantAggregateZero>(GlobalInit)) { 10910ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // This is a degenerate case. The initializer is constant zero so the 10920ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // length of the string must be zero. 10930582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str.clear(); 10940582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; 10950582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling } 10960ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 10970ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Must be a Constant Array 10980ff39b3feb10477c224138156941234f5fa46f58Evan Cheng ConstantArray *Array = dyn_cast<ConstantArray>(GlobalInit); 10991d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson if (Array == 0 || 11001d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Array->getType()->getElementType() != Type::getInt8Ty(V->getContext())) 11010582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 11020ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 11030ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Get the number of elements in the array 11040ff39b3feb10477c224138156941234f5fa46f58Evan Cheng uint64_t NumElts = Array->getType()->getNumElements(); 11050ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 11060582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (Offset > NumElts) 11070582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 11080ff39b3feb10477c224138156941234f5fa46f58Evan Cheng 11090ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // Traverse the constant array from 'Offset' which is the place the GEP refers 11100ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // to in the array. 11110582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str.reserve(NumElts-Offset); 11120ff39b3feb10477c224138156941234f5fa46f58Evan Cheng for (unsigned i = Offset; i != NumElts; ++i) { 11130ff39b3feb10477c224138156941234f5fa46f58Evan Cheng Constant *Elt = Array->getOperand(i); 11140ff39b3feb10477c224138156941234f5fa46f58Evan Cheng ConstantInt *CI = dyn_cast<ConstantInt>(Elt); 11150582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling if (!CI) // This array isn't suitable, non-int initializer. 11160582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return false; 11170ff39b3feb10477c224138156941234f5fa46f58Evan Cheng if (StopAtNul && CI->isZero()) 11180582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; // we found end of string, success! 11190582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling Str += (char)CI->getZExtValue(); 11200ff39b3feb10477c224138156941234f5fa46f58Evan Cheng } 11210582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling 11220ff39b3feb10477c224138156941234f5fa46f58Evan Cheng // The array isn't null terminated, but maybe this is a memcpy, not a strcpy. 11230582ae99ba75a556d6ff63b254da327d32ba036fBill Wendling return true; 11240ff39b3feb10477c224138156941234f5fa46f58Evan Cheng} 1125