ValueTracking.cpp revision 710eb236e67dc021c51ef5cb5d2eb8768840895a
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" 18173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/IntrinsicInst.h" 19173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Target/TargetData.h" 20173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 21173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner#include "llvm/Support/MathExtras.h" 2232a9e7a2654c4aab2e617fbe53140492b3d38066Chris Lattner#include <cstring> 23173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerusing namespace llvm; 24173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 25173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// getOpcode - If this is an Instruction or a ConstantExpr, return the 26173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// opcode value. Otherwise return UserOp1. 27173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerstatic unsigned getOpcode(const Value *V) { 28173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (const Instruction *I = dyn_cast<Instruction>(V)) 29173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return I->getOpcode(); 30173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 31173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return CE->getOpcode(); 32173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Use UserOp1 to mean there's no opcode. 33173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Instruction::UserOp1; 34173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 35173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 36173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 37173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeMaskedBits - Determine which of the bits specified in Mask are 38173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// known to be either zero or one and return them in the KnownZero/KnownOne 39173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// bit sets. This code only analyzes bits in Mask, in order to short-circuit 40173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// processing. 41173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that 42173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// we cannot optimize based on the assumption that it is zero without changing 43173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// it to be an explicit zero. If we don't change it to zero, other code could 44173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// optimized based on the contradictory assumption that it is non-zero. 45173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// Because instcombine aggressively folds operations with undef args anyway, 46173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this won't lose us code quality. 47173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnervoid llvm::ComputeMaskedBits(Value *V, const APInt &Mask, 48173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt &KnownZero, APInt &KnownOne, 49173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TargetData *TD, unsigned Depth) { 50173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert(V && "No Value?"); 51173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert(Depth <= 6 && "Limit Search Depth"); 52173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint32_t BitWidth = Mask.getBitWidth(); 53173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((V->getType()->isInteger() || isa<PointerType>(V->getType())) && 54173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner "Not integer or pointer type!"); 55173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((!TD || TD->getTypeSizeInBits(V->getType()) == BitWidth) && 56173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner (!isa<IntegerType>(V->getType()) || 57173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner V->getType()->getPrimitiveSizeInBits() == BitWidth) && 58173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.getBitWidth() == BitWidth && 59173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.getBitWidth() == BitWidth && 60173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner "V, Mask, KnownOne and KnownZero should have same BitWidth"); 61173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 62173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 63173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know all of the bits for a constant! 64173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = CI->getValue() & Mask; 65173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = ~KnownOne & Mask; 66173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 67173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 68173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Null is all-zeros. 69173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (isa<ConstantPointerNull>(V)) { 70173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 71173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask; 72173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 73173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 74173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // The address of an aligned GlobalValue has trailing zeros. 75173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 76173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = GV->getAlignment(); 77173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align == 0 && TD && GV->getType()->getElementType()->isSized()) 78173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Align = TD->getPrefTypeAlignment(GV->getType()->getElementType()); 79173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 80173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 81173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_32(Align)); 82173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 83173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.clear(); 84173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 85173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 86173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 87173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 88173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.clear(); KnownOne.clear(); // Start out not knowing anything. 89173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 90173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Depth == 6 || Mask == 0) 91173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Limit search depth. 92173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 93173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner User *I = dyn_cast<User>(V); 94173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!I) return; 95173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 96173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero2(KnownZero), KnownOne2(KnownOne); 97173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner switch (getOpcode(I)) { 98173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 99173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: { 100173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If either the LHS or the RHS are Zero, the result is zero. 101173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 102173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask & ~KnownZero); 103173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 104173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 105173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 106173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 107173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 108173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 bits are only known if set in both the LHS & RHS. 109173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 110173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 are known to be clear if zero in either the LHS | RHS. 111173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= KnownZero2; 112173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 113173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 114173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: { 115173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 116173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask & ~KnownOne); 117173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 118173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 119173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 120173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 121173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 122173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are only known if clear in both the LHS & RHS. 123173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 124173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in either the LHS | RHS. 125173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= KnownOne2; 126173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 127173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 128173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: { 129173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1); 130173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask, KnownZero2, KnownOne2, TD, 131173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 132173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 133173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 134173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 135173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are known if clear or set in both the LHS & RHS. 136173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 137173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-1 are known to be set if set in only one of the LHS, RHS. 138173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 139173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = KnownZeroOut; 140173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 141173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 142173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Mul: { 143173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getAllOnesValue(BitWidth); 144173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero, KnownOne, TD,Depth+1); 145173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 146173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 147173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 148173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 149173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 150173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If low bits are zero in either operand, output low known-0 bits. 151173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Also compute a conserative estimate for high known-0 bits. 152173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // More trickiness is possible, but this is sufficient for the 153173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // interesting case of alignment computation. 154173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 155173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = KnownZero.countTrailingOnes() + 156173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes(); 157173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 158173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes(), 159173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner BitWidth) - BitWidth; 160173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 161173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, BitWidth); 162173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(LeadZ, BitWidth); 163173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 164173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt::getHighBitsSet(BitWidth, LeadZ); 165173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= Mask; 166173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 167173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 168173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UDiv: { 169173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // For the purposes of computing leading zeros we can conservatively 170173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // treat a udiv as a logical right shift by the power of 2 known to 171173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // be less than the denominator. 172173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 173173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), 174173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllOnes, KnownZero2, KnownOne2, TD, Depth+1); 175173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LeadZ = KnownZero2.countLeadingOnes(); 176173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 177173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne2.clear(); 178173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.clear(); 179173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), 180173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllOnes, KnownZero2, KnownOne2, TD, Depth+1); 181173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 182173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RHSUnknownLeadingOnes != BitWidth) 183173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ = std::min(BitWidth, 184173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 185173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 186173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask; 187173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 188173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 189173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 190173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(2), Mask, KnownZero, KnownOne, TD, Depth+1); 191173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask, KnownZero2, KnownOne2, TD, 192173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 193173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 194173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 195173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 196173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Only known if known in both the LHS and RHS. 197173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne &= KnownOne2; 198173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero &= KnownZero2; 199173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 200173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPTrunc: 201173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPExt: 202173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToUI: 203173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::FPToSI: 204173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SIToFP: 205173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::UIToFP: 206173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; // Can't work with floating point. 207173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PtrToInt: 208173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::IntToPtr: 209173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We can't handle these if we don't know the pointer size. 210173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 211173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FALL THROUGH and handle them the same as zext/trunc. 212173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::ZExt: 213173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: { 214173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Note that we handle pointer operands here because of inttoptr/ptrtoint 215173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // which fall through here. 216173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const Type *SrcTy = I->getOperand(0)->getType(); 217173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint32_t SrcBitWidth = TD ? 218173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD->getTypeSizeInBits(SrcTy) : 219173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner SrcTy->getPrimitiveSizeInBits(); 220173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskIn(Mask); 221173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner MaskIn.zextOrTrunc(SrcBitWidth); 222173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zextOrTrunc(SrcBitWidth); 223173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zextOrTrunc(SrcBitWidth); 224173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD, 225173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 226173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zextOrTrunc(BitWidth); 227173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zextOrTrunc(BitWidth); 228173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Any top bits are known to be zero. 229173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (BitWidth > SrcBitWidth) 230173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 231173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 232173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 233173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::BitCast: { 234173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const Type *SrcTy = I->getOperand(0)->getType(); 235173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (SrcTy->isInteger() || isa<PointerType>(SrcTy)) { 236173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask, KnownZero, KnownOne, TD, 237173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 238173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 239173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 240173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 241173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 242173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: { 243173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the bits in the result that are not present in the input. 244173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const IntegerType *SrcTy = cast<IntegerType>(I->getOperand(0)->getType()); 245173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint32_t SrcBitWidth = SrcTy->getBitWidth(); 246173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 247173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskIn(Mask); 248173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner MaskIn.trunc(SrcBitWidth); 249173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.trunc(SrcBitWidth); 250173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.trunc(SrcBitWidth); 251173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD, 252173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 253173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 254173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero.zext(BitWidth); 255173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.zext(BitWidth); 256173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 257173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the sign bit of the input is known set or clear, then we know the 258173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // top bits of the result. 259173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[SrcBitWidth-1]) // Input sign bit known zero 260173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 261173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[SrcBitWidth-1]) // Input sign bit known set 262173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); 263173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 264173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 265173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 266173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 267173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 268173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 269173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.lshr(ShiftAmt)); 270173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 271173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 272173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 273173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero <<= ShiftAmt; 274173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne <<= ShiftAmt; 275173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 276173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 277173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 278173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 279173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::LShr: 280173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 281173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 282173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 283173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 284173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 285173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Unsigned shift right. 286173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.shl(ShiftAmt)); 287173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero,KnownOne, TD, 288173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 289173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 290173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 291173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 292173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // high bits known zero. 293173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 294173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 295173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 296173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 297173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 298173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 299173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) { 300173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Compute the new bits that are at the top now. 301173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); 302173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 303173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Signed shift right. 304173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2(Mask.shl(ShiftAmt)); 305173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 306173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 307173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 308173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); 309173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); 310173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 311173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); 312173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero[BitWidth-ShiftAmt-1]) // New bits are known zero. 313173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= HighBits; 314173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. 315173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= HighBits; 316173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 317173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 318173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 319173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: { 320173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(I->getOperand(0))) { 321173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We know that the top bits of C-X are clear if X contains less bits 322173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // than C (i.e. no wrap-around can happen). For example, 20-X is 323173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // positive if we can prove that X is >= 0 and < 16. 324173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!CLHS->getValue().isNegative()) { 325173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros(); 326173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // NLZ can't be BitWidth with no sign bit 327173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 328173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), MaskV, KnownZero2, KnownOne2, 329173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 330173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 331173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If all of the MaskV bits are known to be zero, then we know the 332173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // output top bits are zero, because we now know that the output is 333173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // from [0-C]. 334173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero2 & MaskV) == MaskV) { 335173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned NLZ2 = CLHS->getValue().countLeadingZeros(); 336173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Top bits known zero. 337173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask; 338173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 339173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 340173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 341173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 342173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // fall through 343173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: { 344173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Output known-0 bits are known if clear or set in both the low clear bits 345173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // common to both LHS & RHS. For example, 8+(X<<3) is known to have the 346173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // low 3 bits clear. 347173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getLowBitsSet(BitWidth, Mask.countTrailingOnes()); 348173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 349173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 350173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 351173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned KnownZeroOut = KnownZero2.countTrailingOnes(); 352173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 353173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), Mask2, KnownZero2, KnownOne2, TD, 354173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 355173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 356173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZeroOut = std::min(KnownZeroOut, 357173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes()); 358173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 359173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut); 360173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return; 361173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 362173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SRem: 363173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 364173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt RA = Rem->getValue(); 365173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RA.isPowerOf2() || (-RA).isPowerOf2()) { 366173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LowBits = RA.isStrictlyPositive() ? (RA - 1) : ~RA; 367173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 368173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 369173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 370173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 371173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // The sign of a remainder is equal to the sign of the first 372173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // operand (zero being positive). 373173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 374173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2 |= ~LowBits; 375173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (KnownOne2[BitWidth-1]) 376173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne2 |= ~LowBits; 377173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 378173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= KnownZero2 & Mask; 379173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne |= KnownOne2 & Mask; 380173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 381173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 382173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 383173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 384173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 385173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::URem: { 386173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) { 387173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt RA = Rem->getValue(); 388173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (RA.isPowerOf2()) { 389173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LowBits = (RA - 1); 390173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = LowBits & Mask; 391173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero |= ~LowBits & Mask; 392173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD, 393173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 394173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 395173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 396173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 397173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 398173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 399173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Since the result is less than or equal to either operand, any leading 400173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits in either operand must also exist in the result. 401173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt AllOnes = APInt::getAllOnesValue(BitWidth); 402173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), AllOnes, KnownZero, KnownOne, 403173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 404173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(1), AllOnes, KnownZero2, KnownOne2, 405173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 406173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 407173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint32_t Leaders = std::max(KnownZero.countLeadingOnes(), 408173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countLeadingOnes()); 409173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne.clear(); 410173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask; 411173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 412173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 413173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 414173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Alloca: 415173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Malloc: { 416173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner AllocationInst *AI = cast<AllocationInst>(V); 417173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Align = AI->getAlignment(); 418173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align == 0 && TD) { 419173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (isa<AllocaInst>(AI)) 420173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Align = TD->getPrefTypeAlignment(AI->getType()->getElementType()); 421173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (isa<MallocInst>(AI)) { 422173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Malloc returns maximally aligned memory. 423173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Align = TD->getABITypeAlignment(AI->getType()->getElementType()); 424173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Align = 425173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner std::max(Align, 426173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner (unsigned)TD->getABITypeAlignment(Type::DoubleTy)); 427173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Align = 428173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner std::max(Align, 429173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner (unsigned)TD->getABITypeAlignment(Type::Int64Ty)); 430173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 431173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 432173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 433173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Align > 0) 434173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & APInt::getLowBitsSet(BitWidth, 435173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_32(Align)); 436173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 437173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 438173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::GetElementPtr: { 439173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Analyze all of the subscripts of this getelementptr instruction 440173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // to determine if we can prove known low zero bits. 441173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalMask = APInt::getAllOnesValue(BitWidth); 442173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0); 443173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(I->getOperand(0), LocalMask, 444173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero, LocalKnownOne, TD, Depth+1); 445173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TrailZ = LocalKnownZero.countTrailingOnes(); 446173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 447173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner gep_type_iterator GTI = gep_type_begin(I); 448173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) { 449173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *Index = I->getOperand(i); 450173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 451173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle struct member offset arithmetic. 452173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!TD) return; 453173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const StructLayout *SL = TD->getStructLayout(STy); 454173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Idx = cast<ConstantInt>(Index)->getZExtValue(); 455173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t Offset = SL->getElementOffset(Idx); 456173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 457173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_64(Offset)); 458173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 459173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle array index arithmetic. 460173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const Type *IndexedTy = GTI.getIndexedType(); 461173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!IndexedTy->isSized()) return; 462173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned GEPOpiBits = Index->getType()->getPrimitiveSizeInBits(); 463173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner uint64_t TypeSize = TD ? TD->getABITypeSize(IndexedTy) : 1; 464173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalMask = APInt::getAllOnesValue(GEPOpiBits); 465173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0); 466173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(Index, LocalMask, 467173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero, LocalKnownOne, TD, Depth+1); 468173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TrailZ = std::min(TrailZ, 469173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner CountTrailingZeros_64(TypeSize) + 470173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner LocalKnownZero.countTrailingOnes()); 471173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 472173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 473173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 474173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) & Mask; 475173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 476173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 477173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::PHI: { 478173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner PHINode *P = cast<PHINode>(I); 479173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle the case of a simple two-predecessor recurrence PHI. 480173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // There's a lot more that could theoretically be done here, but 481173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // this is sufficient to catch some interesting cases. 482173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (P->getNumIncomingValues() == 2) { 483173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner for (unsigned i = 0; i != 2; ++i) { 484173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *L = P->getIncomingValue(i); 485173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *R = P->getIncomingValue(!i); 486173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner User *LU = dyn_cast<User>(L); 487173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (!LU) 488173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner continue; 489173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Opcode = getOpcode(LU); 490173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Check for operations that have the property that if 491173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // both their operands have low zero bits, the result 492173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // will have low zero bits. 493173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Opcode == Instruction::Add || 494173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Sub || 495173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::And || 496173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Or || 497173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Opcode == Instruction::Mul) { 498173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LL = LU->getOperand(0); 499173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Value *LR = LU->getOperand(1); 500173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Find a recurrence. 501173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (LL == I) 502173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LR; 503173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else if (LR == I) 504173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner L = LL; 505173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner else 506173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 507173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Ok, we have a PHI of the form L op= R. Check for low 508173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // zero bits. 509173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask2 = APInt::getAllOnesValue(BitWidth); 510173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(R, Mask2, KnownZero2, KnownOne2, TD, Depth+1); 511173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask2 = APInt::getLowBitsSet(BitWidth, 512173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes()); 513173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownOne2.clear(); 514173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.clear(); 515173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(L, Mask2, KnownZero2, KnownOne2, TD, Depth+1); 516173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = Mask & 517173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt::getLowBitsSet(BitWidth, 518173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero2.countTrailingOnes()); 519173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 520173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 521173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 522173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 523173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 524173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 525173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Call: 526173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 527173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner switch (II->getIntrinsicID()) { 528173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 529173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctpop: 530173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::ctlz: 531173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Intrinsic::cttz: { 532173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned LowBits = Log2_32(BitWidth)+1; 533173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 534173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 535173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 536173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 537173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 538173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 539173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 540173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 541173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 542173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 543173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// this predicate to simplify operations downstream. Mask is known to be zero 544173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// for bits that V cannot have. 545173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerbool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, 546173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TargetData *TD, unsigned Depth) { 547173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0); 548173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth); 549173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 550173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return (KnownZero & Mask) == Mask; 551173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 552173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 553173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 554173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 555173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// ComputeNumSignBits - Return the number of times the sign bit of the 556173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// register is replicated into the other bits. We know that at least 1 bit 557173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// is always equal to the sign bit (itself), but other cases can give us 558173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// information. For example, immediately after an "ashr X, 2", we know that 559173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// the top 3 bits are all equal to each other, so we return 3. 560173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 561173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 'Op' must have a scalar integer type. 562173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner/// 563173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattnerunsigned llvm::ComputeNumSignBits(Value *V, TargetData *TD, unsigned Depth) { 564173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner const IntegerType *Ty = cast<IntegerType>(V->getType()); 565173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned TyBits = Ty->getBitWidth(); 566173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned Tmp, Tmp2; 567173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner unsigned FirstAnswer = 1; 568173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 569d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // Note that ConstantInt is handled by the general ComputeMaskedBits case 570d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner // below. 571d82e511aec0ea27ddd4c1e504b37f689796e965fChris Lattner 572173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Depth == 6) 573173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return 1; // Limit search depth. 574173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 575173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner User *U = dyn_cast<User>(V); 576173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner switch (getOpcode(V)) { 577173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner default: break; 578173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::SExt: 579173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = TyBits-cast<IntegerType>(U->getOperand(0)->getType())->getBitWidth(); 580173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return ComputeNumSignBits(U->getOperand(0), TD, Depth+1) + Tmp; 581173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 582173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::AShr: 583173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 584173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ashr X, C -> adds C sign bits. 585173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(U->getOperand(1))) { 586173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp += C->getZExtValue(); 587173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp > TyBits) Tmp = TyBits; 588173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 589173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 590173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Shl: 591173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(U->getOperand(1))) { 592173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shl destroys sign bits. 593173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 594173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (C->getZExtValue() >= TyBits || // Bad shift. 595173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner C->getZExtValue() >= Tmp) break; // Shifted all sign bits out. 596173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp - C->getZExtValue(); 597173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 598173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 599173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::And: 600173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Or: 601173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Xor: // NOT is handled here. 602173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Logical binary ops preserve the number of sign bits at the worst. 603173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 604173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp != 1) { 605173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 606173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner FirstAnswer = std::min(Tmp, Tmp2); 607173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // We computed what we know about the sign bits as our first 608173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // answer. Now proceed to the generic code that uses 609173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // ComputeMaskedBits, and pick whichever answer is better. 610173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 611173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 612173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 613173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Select: 614173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 615173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 616173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(2), TD, Depth+1); 617173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2); 618173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 619173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Add: 620173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Add can have at most one carry bit. Thus we know that the output 621173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 622173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 623173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 624173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 625173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Special case decrementing a value (ADD X, -1): 626173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CRHS = dyn_cast<ConstantInt>(U->getOperand(0))) 627173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CRHS->isAllOnesValue()) { 628173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 629173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 630173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(U->getOperand(0), Mask, KnownZero, KnownOne, TD, 631173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Depth+1); 632173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 633173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 634173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 635173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero | APInt(TyBits, 1)) == Mask) 636173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 637173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 638173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If we are subtracting one from a positive number, there is no carry 639173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // out of the result. 640173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 641173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp; 642173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 643173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 644173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 645173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 646173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2)-1; 647173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 648173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 649173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Sub: 650173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp2 = ComputeNumSignBits(U->getOperand(1), TD, Depth+1); 651173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp2 == 1) return 1; 652173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 653173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Handle NEG. 654173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (ConstantInt *CLHS = dyn_cast<ConstantInt>(U->getOperand(0))) 655173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (CLHS->isNullValue()) { 656173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 657173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 658173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(U->getOperand(1), Mask, KnownZero, KnownOne, 659173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner TD, Depth+1); 660173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be 0 or 1, the output is 0/-1, which is all 661173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // sign bits set. 662173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if ((KnownZero | APInt(TyBits, 1)) == Mask) 663173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return TyBits; 664173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 665173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // If the input is known to be positive (the sign bit is known clear), 666173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the output of the NEG has the same number of sign bits as the input. 667173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) 668173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return Tmp2; 669173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 670173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Otherwise, we treat this like a SUB. 671173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 672173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 673173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Sub can have at most one carry bit. Thus we know that the output 674173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // is, at worst, one more bit than the inputs. 675173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Tmp = ComputeNumSignBits(U->getOperand(0), TD, Depth+1); 676173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (Tmp == 1) return 1; // Early out. 677173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::min(Tmp, Tmp2)-1; 678173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 679173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner case Instruction::Trunc: 680173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // FIXME: it's tricky to do anything useful for this, but it is an important 681173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // case for targets like X86. 682173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner break; 683173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 684173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 685173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Finally, if we can prove that the top bits of the result are 0's or 1's, 686173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // use this information. 687173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0); 688173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner APInt Mask = APInt::getAllOnesValue(TyBits); 689173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth); 690173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 691173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner if (KnownZero.isNegative()) { // sign bit is 0 692173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownZero; 693173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else if (KnownOne.isNegative()) { // sign bit is 1; 694173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = KnownOne; 695173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } else { 696173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Nothing known. 697173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return FirstAnswer; 698173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner } 699173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner 700173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 701173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // the number of identical bits in the top of the input value. 702173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask = ~Mask; 703173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner Mask <<= Mask.getBitWidth()-TyBits; 704173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // Return # leading zeros. We use 'min' here in case Val was zero before 705173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner // shifting. We don't want to return '64' as for an i32 "0". 706173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner return std::max(FirstAnswer, std::min(TyBits, Mask.countLeadingZeros())); 707173234a68fb6ece106e77da443d87f09d5906cb9Chris Lattner} 708833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 709833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// CannotBeNegativeZero - Return true if we can prove that the specified FP 710833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// value is never equal to -0.0. 711833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 712833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// NOTE: this function will need to be revisited when we support non-default 713833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// rounding modes! 714833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner/// 715833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattnerbool llvm::CannotBeNegativeZero(const Value *V, unsigned Depth) { 716833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) 717833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return !CFP->getValueAPF().isNegZero(); 718833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 719833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (Depth == 6) 720833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return 1; // Limit search depth. 721833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 722833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner const Instruction *I = dyn_cast<Instruction>(V); 723833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (I == 0) return false; 724833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 725833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // (add x, 0.0) is guaranteed to return +0.0, not -0.0. 726833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (I->getOpcode() == Instruction::Add && 727833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner isa<ConstantFP>(I->getOperand(1)) && 728833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner cast<ConstantFP>(I->getOperand(1))->isNullValue()) 729833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 730833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 731833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sitofp and uitofp turn into +0.0 for zero. 732833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (isa<SIToFPInst>(I) || isa<UIToFPInst>(I)) 733833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return true; 734833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 735833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 736833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner // sqrt(-0.0) = -0.0, no other negative results are possible. 737833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (II->getIntrinsicID() == Intrinsic::sqrt) 738833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return CannotBeNegativeZero(II->getOperand(1), Depth+1); 739833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 740833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const CallInst *CI = dyn_cast<CallInst>(I)) 741833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (const Function *F = CI->getCalledFunction()) { 742833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (F->isDeclaration()) { 743833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner switch (F->getNameLen()) { 744833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner case 3: // abs(x) != -0.0 745833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (!strcmp(F->getNameStart(), "abs")) return true; 746833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner break; 747833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner case 4: // abs[lf](x) != -0.0 748833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (!strcmp(F->getNameStart(), "absf")) return true; 749833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner if (!strcmp(F->getNameStart(), "absl")) return true; 750833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner break; 751833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 752833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 753833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner } 754833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 755833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner return false; 756833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner} 757833f25d79ee28f1049f9177c3d2f4c9fbad6f643Chris Lattner 758b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This is the recursive version of BuildSubAggregate. It takes a few different 759b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// arguments. Idxs is the index within the nested struct From that we are 760b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// looking at now (which is of type IndexedType). IdxSkip is the number of 761b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// indices from Idxs that should be left out when inserting into the resulting 762b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct. To is the result struct built so far, new insertvalue instructions 763b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// build on that. 764b23d5adbc8230167e711070b9298985de4580f30Matthijs KooijmanValue *BuildSubAggregate(Value *From, Value* To, const Type *IndexedType, 765b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman SmallVector<unsigned, 10> &Idxs, 766b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned IdxSkip, 767b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Instruction &InsertBefore) { 768b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const llvm::StructType *STy = llvm::dyn_cast<llvm::StructType>(IndexedType); 769b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (STy) { 770b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // General case, the type indexed by Idxs is a struct 771b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { 772b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Process each struct element recursively 773b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.push_back(i); 774710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip, 775710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman InsertBefore); 776b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Idxs.pop_back(); 777b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 778b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return To; 779b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else { 780b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Base case, the type indexed by SourceIdxs is not a struct 781b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Load the value from the nested struct into the sub struct (and skip 782b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // IdxSkip indices when indexing the sub struct). 783710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman Instruction *V = llvm::ExtractValueInst::Create(From, Idxs.begin(), 784710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman Idxs.end(), "tmp", 785710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman &InsertBefore); 786710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman Instruction *Ins = llvm::InsertValueInst::Create(To, V, 787710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman Idxs.begin() + IdxSkip, 788710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman Idxs.end(), "tmp", 789710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman &InsertBefore); 790b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return Ins; 791b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 792b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 793b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 794b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// This helper takes a nested struct and extracts a part of it (which is again a 795b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// struct) into a new value. For example, given the struct: 796b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { a, { b, { c, d }, e } } 797b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// and the indices "1, 1" this returns 798b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// { c, d }. 799b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 800b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// It does this by inserting an extractvalue and insertvalue for each element in 801b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// the resulting struct, as opposed to just inserting a single struct. This 802b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// allows for later folding of these individual extractvalue instructions with 803b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// insertvalue instructions that fill the nested struct. 804b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// 805b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman// Any inserted instructions are inserted before InsertBefore 806710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs KooijmanValue *BuildSubAggregate(Value *From, const unsigned *idx_begin, 807710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman const unsigned *idx_end, Instruction &InsertBefore) { 808710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman const Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), 809710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman idx_begin, 810710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman idx_end); 811b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman Value *To = UndefValue::get(IndexedType); 812b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman SmallVector<unsigned, 10> Idxs(idx_begin, idx_end); 813b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned IdxSkip = Idxs.size(); 814b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 815b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); 816b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 817b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 818710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// FindInsertedValue - Given an aggregrate and an sequence of indices, see if 819710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// the scalar value indexed is already around as a register, for example if it 820710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman/// were inserted directly into the aggregrate. 821b23d5adbc8230167e711070b9298985de4580f30Matthijs KooijmanValue *llvm::FindInsertedValue(Value *V, const unsigned *idx_begin, 822b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const unsigned *idx_end, Instruction &InsertBefore) { 823b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Nothing to index? Just return V then (this is useful at the end of our 824b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // recursion) 825b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (idx_begin == idx_end) 826b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return V; 827b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // We have indices, so V should have an indexable type 828b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman assert((isa<StructType>(V->getType()) || isa<ArrayType>(V->getType())) 829b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman && "Not looking at a struct or array?"); 830b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman assert(ExtractValueInst::getIndexedType(V->getType(), idx_begin, idx_end) 831b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman && "Invalid indices for type?"); 832b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const CompositeType *PTy = cast<CompositeType>(V->getType()); 833b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 834b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (isa<UndefValue>(V)) 835b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return UndefValue::get(ExtractValueInst::getIndexedType(PTy, 836b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman idx_begin, 837b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman idx_end)); 838b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman else if (isa<ConstantAggregateZero>(V)) 839b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return Constant::getNullValue(ExtractValueInst::getIndexedType(PTy, 840b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman idx_begin, 841b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman idx_end)); 842b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman else if (Constant *C = dyn_cast<Constant>(V)) { 843b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (isa<ConstantArray>(C) || isa<ConstantStruct>(C)) 844b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Recursively process this constant 845710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman return FindInsertedValue(C->getOperand(*idx_begin), ++idx_begin, idx_end, 846710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman InsertBefore); 847b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else if (InsertValueInst *I = dyn_cast<InsertValueInst>(V)) { 848b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Loop the indices for the insertvalue instruction in parallel with the 849b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested indices 850b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman const unsigned *req_idx = idx_begin; 851710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 852710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman i != e; ++i, ++req_idx) { 853b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (req_idx == idx_end) 854b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // The requested index is a part of a nested aggregate. Handle this 855b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // specially. 856b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return BuildSubAggregate(V, idx_begin, req_idx, InsertBefore); 857b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 858b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // This insert value inserts something else than what we are looking for. 859b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // See if the (aggregrate) value inserted into has the value we are 860b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // looking for, then. 861b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman if (*req_idx != *i) 862710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman return FindInsertedValue(I->getAggregateOperand(), idx_begin, idx_end, 863710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman InsertBefore); 864b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 865b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we end up here, the indices of the insertvalue match with those 866b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // requested (though possibly only partially). Now we recursively look at 867b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // the inserted value, passing any remaining indices. 868710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman return FindInsertedValue(I->getInsertedValueOperand(), req_idx, idx_end, 869710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman InsertBefore); 870b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } else if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) { 871b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // If we're extracting a value from an aggregrate that was extracted from 872b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // something else, we can extract from that something else directly instead. 873b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // However, we will need to chain I's indices with the requested indices. 874b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 875b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Calculate the number of indices required 876b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned size = I->getNumIndices() + (idx_end - idx_begin); 877b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Allocate some space to put the new indices in 878b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned *new_begin = new unsigned[size]; 879b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Auto cleanup this array 880b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman std::auto_ptr<unsigned> newptr(new_begin); 881b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Start inserting at the beginning 882b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman unsigned *new_end = new_begin; 883b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add indices from the extract value instruction 884710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman for (const unsigned *i = I->idx_begin(), *e = I->idx_end(); 885710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman i != e; ++i, ++new_end) 886b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman *new_end = *i; 887b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 888b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Add requested indices 889b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman for (const unsigned *i = idx_begin, *e = idx_end; i != e; ++i, ++new_end) 890b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman *new_end = *i; 891b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 892710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman assert((unsigned)(new_end - new_begin) == size 893710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman && "Number of indices added not correct?"); 894b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman 895710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman return FindInsertedValue(I->getAggregateOperand(), new_begin, new_end, 896710eb236e67dc021c51ef5cb5d2eb8768840895aMatthijs Kooijman InsertBefore); 897b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman } 898b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // Otherwise, we don't know (such as, extracting from a function return value 899b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman // or load instruction) 900b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman return 0; 901b23d5adbc8230167e711070b9298985de4580f30Matthijs Kooijman} 902