ConstantFold.cpp revision 61c70e98ac3c7504d31dd9bc81c4e9cb998e9984
12898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek//===- ConstantFold.cpp - LLVM constant folder ----------------------------===// 22898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// 32898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// The LLVM Compiler Infrastructure 42898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// 52898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// This file is distributed under the University of Illinois Open Source 62898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// License. See LICENSE.TXT for details. 72898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// 82898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek//===----------------------------------------------------------------------===// 92898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// 102898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// This file implements folding of constants for LLVM. This implements the 112898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// (internal) ConstantFold.h interface, which is used by the 122898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// ConstantExpr::get* methods to automatically fold constants when possible. 132898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// 142898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// The current constant folding implementation is implemented in two pieces: the 152898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// pieces that don't need TargetData, and the pieces that do. This is to avoid 162898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// a dependence in VMCore on Target. 172898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// 182898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek//===----------------------------------------------------------------------===// 192898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 202898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek#include "ConstantFold.h" 212898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek#include "llvm/Constants.h" 228be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek#include "llvm/Instructions.h" 232898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek#include "llvm/DerivedTypes.h" 242898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek#include "llvm/Function.h" 252898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek#include "llvm/GlobalAlias.h" 268be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek#include "llvm/GlobalVariable.h" 278be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek#include "llvm/ADT/SmallVector.h" 288be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek#include "llvm/Support/Compiler.h" 298be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek#include "llvm/Support/ErrorHandling.h" 308be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek#include "llvm/Support/GetElementPtrTypeIterator.h" 318be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek#include "llvm/Support/ManagedStatic.h" 328be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek#include "llvm/Support/MathExtras.h" 332898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek#include <limits> 342898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenekusing namespace llvm; 352898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 362898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek//===----------------------------------------------------------------------===// 372898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek// ConstantFold*Instruction Implementations 382898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek//===----------------------------------------------------------------------===// 392898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 402898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek/// BitCastConstantVector - Convert the specified ConstantVector node to the 412898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek/// specified vector type. At this point, we know that the elements of the 422898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek/// input vector constant are all simple integer or FP values. 432898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenekstatic Constant *BitCastConstantVector(ConstantVector *CV, 442898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek const VectorType *DstTy) { 452898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // If this cast changes element count then we can't handle it here: 462898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // doing so requires endianness information. This should be handled by 472898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // Analysis/ConstantFolding.cpp 482898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek unsigned NumElts = DstTy->getNumElements(); 492898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (NumElts != CV->getNumOperands()) 502898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek return 0; 512898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 522898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // Check to verify that all elements of the input are simple. 532898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek for (unsigned i = 0; i != NumElts; ++i) { 542898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (!isa<ConstantInt>(CV->getOperand(i)) && 552898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek !isa<ConstantFP>(CV->getOperand(i))) 562898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek return 0; 572898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek } 582898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 592898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // Bitcast each element now. 602898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek std::vector<Constant*> Result; 612898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek const Type *DstEltTy = DstTy->getElementType(); 622898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek for (unsigned i = 0; i != NumElts; ++i) 632898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek Result.push_back(ConstantExpr::getBitCast(CV->getOperand(i), 642898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek DstEltTy)); 652898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek return ConstantVector::get(Result); 662898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek} 672898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 682898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek/// This function determines which opcode to use to fold two constant cast 692898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek/// expressions together. It uses CastInst::isEliminableCastPair to determine 702898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek/// the opcode. Consequently its just a wrapper around that function. 712898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek/// @brief Determine if it is valid to fold a cast of a cast 722898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenekstatic unsigned 732898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted KremenekfoldConstantCastPair( 742898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek unsigned opc, ///< opcode of the second cast constant expression 752898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek ConstantExpr *Op, ///< the first cast constant expression 762898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek const Type *DstTy ///< desintation type of the first cast 772898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek) { 782898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!"); 798be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type"); 802898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek assert(CastInst::isCast(opc) && "Invalid cast opcode"); 812898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 822898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // The the types and opcodes for the two Cast constant expressions 832898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek const Type *SrcTy = Op->getOperand(0)->getType(); 842898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek const Type *MidTy = Op->getType(); 852898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode()); 862898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek Instruction::CastOps secondOp = Instruction::CastOps(opc); 872898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 882898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // Let CastInst::isEliminableCastPair do the heavy lifting. 892898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy, 902898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek Type::getInt64Ty(DstTy->getContext())); 912898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek} 922898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 932898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenekstatic Constant *FoldBitCast(Constant *V, const Type *DestTy) { 948be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek const Type *SrcTy = V->getType(); 952898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (SrcTy == DestTy) 968be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek return V; // no-op cast 972898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 982898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // Check to see if we are casting a pointer to an aggregate to a pointer to 992898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // the first element. If so, return the appropriate GEP instruction. 1002898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) 1012898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (const PointerType *DPTy = dyn_cast<PointerType>(DestTy)) 1022898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (PTy->getAddressSpace() == DPTy->getAddressSpace()) { 1032898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek SmallVector<Value*, 8> IdxList; 1042898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek Value *Zero = 1052898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek Constant::getNullValue(Type::getInt32Ty(DPTy->getContext())); 1062898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek IdxList.push_back(Zero); 1072898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek const Type *ElTy = PTy->getElementType(); 1082898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek while (ElTy != DPTy->getElementType()) { 1092898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (const StructType *STy = dyn_cast<StructType>(ElTy)) { 1102898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (STy->getNumElements() == 0) break; 1112898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek ElTy = STy->getElementType(0); 1122898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek IdxList.push_back(Zero); 1132898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek } else if (const SequentialType *STy = 1142898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek dyn_cast<SequentialType>(ElTy)) { 1152898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (ElTy->isPointerTy()) break; // Can't index into pointers! 1162898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek ElTy = STy->getElementType(); 1172898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek IdxList.push_back(Zero); 1182898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek } else { 1192898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek break; 1202898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek } 1212898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek } 1222898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek 1232898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (ElTy == DPTy->getElementType()) 1242898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek // This GEP is inbounds because all indices are zero. 1258be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek return ConstantExpr::getInBoundsGetElementPtr(V, &IdxList[0], 1268be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek IdxList.size()); 1278be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek } 1288be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek 1298be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek // Handle casts from one vector constant to another. We know that the src 1308be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek // and dest type have the same size (otherwise its an illegal cast). 1318be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek if (const VectorType *DestPTy = dyn_cast<VectorType>(DestTy)) { 1328be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek if (const VectorType *SrcTy = dyn_cast<VectorType>(V->getType())) { 1338be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek assert(DestPTy->getBitWidth() == SrcTy->getBitWidth() && 1348be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek "Not cast between same sized vectors!"); 1358be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek SrcTy = NULL; 1368be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek // First, check for null. Undef is already handled. 1378be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek if (isa<ConstantAggregateZero>(V)) 1388be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek return Constant::getNullValue(DestTy); 1398be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek 1408be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) 1418be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek return BitCastConstantVector(CV, DestPTy); 1428be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek } 1438be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek 1448be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek // Canonicalize scalar-to-vector bitcasts into vector-to-vector bitcasts 1458be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek // This allows for other simplifications (although some of them 1468be51eab5ad34515d2a40dcdc8558128ca1800adTed Kremenek // can only be handled by Analysis/ConstantFolding.cpp). 1472898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek if (isa<ConstantInt>(V) || isa<ConstantFP>(V)) 1482898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek return ConstantExpr::getBitCast(ConstantVector::get(&V, 1), DestPTy); 1492898d4f7648e6ed5e9047068f1e8ee2f3c2bcd75Ted Kremenek } 150 151 // Finally, implement bitcast folding now. The code below doesn't handle 152 // bitcast right. 153 if (isa<ConstantPointerNull>(V)) // ptr->ptr cast. 154 return ConstantPointerNull::get(cast<PointerType>(DestTy)); 155 156 // Handle integral constant input. 157 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 158 if (DestTy->isIntegerTy()) 159 // Integral -> Integral. This is a no-op because the bit widths must 160 // be the same. Consequently, we just fold to V. 161 return V; 162 163 if (DestTy->isFloatingPointTy()) 164 return ConstantFP::get(DestTy->getContext(), 165 APFloat(CI->getValue(), 166 !DestTy->isPPC_FP128Ty())); 167 168 // Otherwise, can't fold this (vector?) 169 return 0; 170 } 171 172 // Handle ConstantFP input: FP -> Integral. 173 if (ConstantFP *FP = dyn_cast<ConstantFP>(V)) 174 return ConstantInt::get(FP->getContext(), 175 FP->getValueAPF().bitcastToAPInt()); 176 177 return 0; 178} 179 180 181/// ExtractConstantBytes - V is an integer constant which only has a subset of 182/// its bytes used. The bytes used are indicated by ByteStart (which is the 183/// first byte used, counting from the least significant byte) and ByteSize, 184/// which is the number of bytes used. 185/// 186/// This function analyzes the specified constant to see if the specified byte 187/// range can be returned as a simplified constant. If so, the constant is 188/// returned, otherwise null is returned. 189/// 190static Constant *ExtractConstantBytes(Constant *C, unsigned ByteStart, 191 unsigned ByteSize) { 192 assert(C->getType()->isIntegerTy() && 193 (cast<IntegerType>(C->getType())->getBitWidth() & 7) == 0 && 194 "Non-byte sized integer input"); 195 unsigned CSize = cast<IntegerType>(C->getType())->getBitWidth()/8; 196 assert(ByteSize && "Must be accessing some piece"); 197 assert(ByteStart+ByteSize <= CSize && "Extracting invalid piece from input"); 198 assert(ByteSize != CSize && "Should not extract everything"); 199 200 // Constant Integers are simple. 201 if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) { 202 APInt V = CI->getValue(); 203 if (ByteStart) 204 V = V.lshr(ByteStart*8); 205 V.trunc(ByteSize*8); 206 return ConstantInt::get(CI->getContext(), V); 207 } 208 209 // In the input is a constant expr, we might be able to recursively simplify. 210 // If not, we definitely can't do anything. 211 ConstantExpr *CE = dyn_cast<ConstantExpr>(C); 212 if (CE == 0) return 0; 213 214 switch (CE->getOpcode()) { 215 default: return 0; 216 case Instruction::Or: { 217 Constant *RHS = ExtractConstantBytes(CE->getOperand(1), ByteStart,ByteSize); 218 if (RHS == 0) 219 return 0; 220 221 // X | -1 -> -1. 222 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS)) 223 if (RHSC->isAllOnesValue()) 224 return RHSC; 225 226 Constant *LHS = ExtractConstantBytes(CE->getOperand(0), ByteStart,ByteSize); 227 if (LHS == 0) 228 return 0; 229 return ConstantExpr::getOr(LHS, RHS); 230 } 231 case Instruction::And: { 232 Constant *RHS = ExtractConstantBytes(CE->getOperand(1), ByteStart,ByteSize); 233 if (RHS == 0) 234 return 0; 235 236 // X & 0 -> 0. 237 if (RHS->isNullValue()) 238 return RHS; 239 240 Constant *LHS = ExtractConstantBytes(CE->getOperand(0), ByteStart,ByteSize); 241 if (LHS == 0) 242 return 0; 243 return ConstantExpr::getAnd(LHS, RHS); 244 } 245 case Instruction::LShr: { 246 ConstantInt *Amt = dyn_cast<ConstantInt>(CE->getOperand(1)); 247 if (Amt == 0) 248 return 0; 249 unsigned ShAmt = Amt->getZExtValue(); 250 // Cannot analyze non-byte shifts. 251 if ((ShAmt & 7) != 0) 252 return 0; 253 ShAmt >>= 3; 254 255 // If the extract is known to be all zeros, return zero. 256 if (ByteStart >= CSize-ShAmt) 257 return Constant::getNullValue(IntegerType::get(CE->getContext(), 258 ByteSize*8)); 259 // If the extract is known to be fully in the input, extract it. 260 if (ByteStart+ByteSize+ShAmt <= CSize) 261 return ExtractConstantBytes(CE->getOperand(0), ByteStart+ShAmt, ByteSize); 262 263 // TODO: Handle the 'partially zero' case. 264 return 0; 265 } 266 267 case Instruction::Shl: { 268 ConstantInt *Amt = dyn_cast<ConstantInt>(CE->getOperand(1)); 269 if (Amt == 0) 270 return 0; 271 unsigned ShAmt = Amt->getZExtValue(); 272 // Cannot analyze non-byte shifts. 273 if ((ShAmt & 7) != 0) 274 return 0; 275 ShAmt >>= 3; 276 277 // If the extract is known to be all zeros, return zero. 278 if (ByteStart+ByteSize <= ShAmt) 279 return Constant::getNullValue(IntegerType::get(CE->getContext(), 280 ByteSize*8)); 281 // If the extract is known to be fully in the input, extract it. 282 if (ByteStart >= ShAmt) 283 return ExtractConstantBytes(CE->getOperand(0), ByteStart-ShAmt, ByteSize); 284 285 // TODO: Handle the 'partially zero' case. 286 return 0; 287 } 288 289 case Instruction::ZExt: { 290 unsigned SrcBitSize = 291 cast<IntegerType>(CE->getOperand(0)->getType())->getBitWidth(); 292 293 // If extracting something that is completely zero, return 0. 294 if (ByteStart*8 >= SrcBitSize) 295 return Constant::getNullValue(IntegerType::get(CE->getContext(), 296 ByteSize*8)); 297 298 // If exactly extracting the input, return it. 299 if (ByteStart == 0 && ByteSize*8 == SrcBitSize) 300 return CE->getOperand(0); 301 302 // If extracting something completely in the input, if if the input is a 303 // multiple of 8 bits, recurse. 304 if ((SrcBitSize&7) == 0 && (ByteStart+ByteSize)*8 <= SrcBitSize) 305 return ExtractConstantBytes(CE->getOperand(0), ByteStart, ByteSize); 306 307 // Otherwise, if extracting a subset of the input, which is not multiple of 308 // 8 bits, do a shift and trunc to get the bits. 309 if ((ByteStart+ByteSize)*8 < SrcBitSize) { 310 assert((SrcBitSize&7) && "Shouldn't get byte sized case here"); 311 Constant *Res = CE->getOperand(0); 312 if (ByteStart) 313 Res = ConstantExpr::getLShr(Res, 314 ConstantInt::get(Res->getType(), ByteStart*8)); 315 return ConstantExpr::getTrunc(Res, IntegerType::get(C->getContext(), 316 ByteSize*8)); 317 } 318 319 // TODO: Handle the 'partially zero' case. 320 return 0; 321 } 322 } 323} 324 325/// getFoldedSizeOf - Return a ConstantExpr with type DestTy for sizeof 326/// on Ty, with any known factors factored out. If Folded is false, 327/// return null if no factoring was possible, to avoid endlessly 328/// bouncing an unfoldable expression back into the top-level folder. 329/// 330static Constant *getFoldedSizeOf(const Type *Ty, const Type *DestTy, 331 bool Folded) { 332 if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 333 Constant *N = ConstantInt::get(DestTy, ATy->getNumElements()); 334 Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true); 335 return ConstantExpr::getNUWMul(E, N); 336 } 337 338 if (const StructType *STy = dyn_cast<StructType>(Ty)) 339 if (!STy->isPacked()) { 340 unsigned NumElems = STy->getNumElements(); 341 // An empty struct has size zero. 342 if (NumElems == 0) 343 return ConstantExpr::getNullValue(DestTy); 344 // Check for a struct with all members having the same size. 345 Constant *MemberSize = 346 getFoldedSizeOf(STy->getElementType(0), DestTy, true); 347 bool AllSame = true; 348 for (unsigned i = 1; i != NumElems; ++i) 349 if (MemberSize != 350 getFoldedSizeOf(STy->getElementType(i), DestTy, true)) { 351 AllSame = false; 352 break; 353 } 354 if (AllSame) { 355 Constant *N = ConstantInt::get(DestTy, NumElems); 356 return ConstantExpr::getNUWMul(MemberSize, N); 357 } 358 } 359 360 // Pointer size doesn't depend on the pointee type, so canonicalize them 361 // to an arbitrary pointee. 362 if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) 363 if (!PTy->getElementType()->isIntegerTy(1)) 364 return 365 getFoldedSizeOf(PointerType::get(IntegerType::get(PTy->getContext(), 1), 366 PTy->getAddressSpace()), 367 DestTy, true); 368 369 // If there's no interesting folding happening, bail so that we don't create 370 // a constant that looks like it needs folding but really doesn't. 371 if (!Folded) 372 return 0; 373 374 // Base case: Get a regular sizeof expression. 375 Constant *C = ConstantExpr::getSizeOf(Ty); 376 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 377 DestTy, false), 378 C, DestTy); 379 return C; 380} 381 382/// getFoldedAlignOf - Return a ConstantExpr with type DestTy for alignof 383/// on Ty, with any known factors factored out. If Folded is false, 384/// return null if no factoring was possible, to avoid endlessly 385/// bouncing an unfoldable expression back into the top-level folder. 386/// 387static Constant *getFoldedAlignOf(const Type *Ty, const Type *DestTy, 388 bool Folded) { 389 // The alignment of an array is equal to the alignment of the 390 // array element. Note that this is not always true for vectors. 391 if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 392 Constant *C = ConstantExpr::getAlignOf(ATy->getElementType()); 393 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 394 DestTy, 395 false), 396 C, DestTy); 397 return C; 398 } 399 400 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 401 // Packed structs always have an alignment of 1. 402 if (STy->isPacked()) 403 return ConstantInt::get(DestTy, 1); 404 405 // Otherwise, struct alignment is the maximum alignment of any member. 406 // Without target data, we can't compare much, but we can check to see 407 // if all the members have the same alignment. 408 unsigned NumElems = STy->getNumElements(); 409 // An empty struct has minimal alignment. 410 if (NumElems == 0) 411 return ConstantInt::get(DestTy, 1); 412 // Check for a struct with all members having the same alignment. 413 Constant *MemberAlign = 414 getFoldedAlignOf(STy->getElementType(0), DestTy, true); 415 bool AllSame = true; 416 for (unsigned i = 1; i != NumElems; ++i) 417 if (MemberAlign != getFoldedAlignOf(STy->getElementType(i), DestTy, true)) { 418 AllSame = false; 419 break; 420 } 421 if (AllSame) 422 return MemberAlign; 423 } 424 425 // Pointer alignment doesn't depend on the pointee type, so canonicalize them 426 // to an arbitrary pointee. 427 if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) 428 if (!PTy->getElementType()->isIntegerTy(1)) 429 return 430 getFoldedAlignOf(PointerType::get(IntegerType::get(PTy->getContext(), 431 1), 432 PTy->getAddressSpace()), 433 DestTy, true); 434 435 // If there's no interesting folding happening, bail so that we don't create 436 // a constant that looks like it needs folding but really doesn't. 437 if (!Folded) 438 return 0; 439 440 // Base case: Get a regular alignof expression. 441 Constant *C = ConstantExpr::getAlignOf(Ty); 442 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 443 DestTy, false), 444 C, DestTy); 445 return C; 446} 447 448/// getFoldedOffsetOf - Return a ConstantExpr with type DestTy for offsetof 449/// on Ty and FieldNo, with any known factors factored out. If Folded is false, 450/// return null if no factoring was possible, to avoid endlessly 451/// bouncing an unfoldable expression back into the top-level folder. 452/// 453static Constant *getFoldedOffsetOf(const Type *Ty, Constant *FieldNo, 454 const Type *DestTy, 455 bool Folded) { 456 if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 457 Constant *N = ConstantExpr::getCast(CastInst::getCastOpcode(FieldNo, false, 458 DestTy, false), 459 FieldNo, DestTy); 460 Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true); 461 return ConstantExpr::getNUWMul(E, N); 462 } 463 464 if (const StructType *STy = dyn_cast<StructType>(Ty)) 465 if (!STy->isPacked()) { 466 unsigned NumElems = STy->getNumElements(); 467 // An empty struct has no members. 468 if (NumElems == 0) 469 return 0; 470 // Check for a struct with all members having the same size. 471 Constant *MemberSize = 472 getFoldedSizeOf(STy->getElementType(0), DestTy, true); 473 bool AllSame = true; 474 for (unsigned i = 1; i != NumElems; ++i) 475 if (MemberSize != 476 getFoldedSizeOf(STy->getElementType(i), DestTy, true)) { 477 AllSame = false; 478 break; 479 } 480 if (AllSame) { 481 Constant *N = ConstantExpr::getCast(CastInst::getCastOpcode(FieldNo, 482 false, 483 DestTy, 484 false), 485 FieldNo, DestTy); 486 return ConstantExpr::getNUWMul(MemberSize, N); 487 } 488 } 489 490 // If there's no interesting folding happening, bail so that we don't create 491 // a constant that looks like it needs folding but really doesn't. 492 if (!Folded) 493 return 0; 494 495 // Base case: Get a regular offsetof expression. 496 Constant *C = ConstantExpr::getOffsetOf(Ty, FieldNo); 497 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 498 DestTy, false), 499 C, DestTy); 500 return C; 501} 502 503Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V, 504 const Type *DestTy) { 505 if (isa<UndefValue>(V)) { 506 // zext(undef) = 0, because the top bits will be zero. 507 // sext(undef) = 0, because the top bits will all be the same. 508 // [us]itofp(undef) = 0, because the result value is bounded. 509 if (opc == Instruction::ZExt || opc == Instruction::SExt || 510 opc == Instruction::UIToFP || opc == Instruction::SIToFP) 511 return Constant::getNullValue(DestTy); 512 return UndefValue::get(DestTy); 513 } 514 // No compile-time operations on this type yet. 515 if (V->getType()->isPPC_FP128Ty() || DestTy->isPPC_FP128Ty()) 516 return 0; 517 518 // If the cast operand is a constant expression, there's a few things we can 519 // do to try to simplify it. 520 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 521 if (CE->isCast()) { 522 // Try hard to fold cast of cast because they are often eliminable. 523 if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy)) 524 return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy); 525 } else if (CE->getOpcode() == Instruction::GetElementPtr) { 526 // If all of the indexes in the GEP are null values, there is no pointer 527 // adjustment going on. We might as well cast the source pointer. 528 bool isAllNull = true; 529 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) 530 if (!CE->getOperand(i)->isNullValue()) { 531 isAllNull = false; 532 break; 533 } 534 if (isAllNull) 535 // This is casting one pointer type to another, always BitCast 536 return ConstantExpr::getPointerCast(CE->getOperand(0), DestTy); 537 } 538 } 539 540 // If the cast operand is a constant vector, perform the cast by 541 // operating on each element. In the cast of bitcasts, the element 542 // count may be mismatched; don't attempt to handle that here. 543 if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) 544 if (DestTy->isVectorTy() && 545 cast<VectorType>(DestTy)->getNumElements() == 546 CV->getType()->getNumElements()) { 547 std::vector<Constant*> res; 548 const VectorType *DestVecTy = cast<VectorType>(DestTy); 549 const Type *DstEltTy = DestVecTy->getElementType(); 550 for (unsigned i = 0, e = CV->getType()->getNumElements(); i != e; ++i) 551 res.push_back(ConstantExpr::getCast(opc, 552 CV->getOperand(i), DstEltTy)); 553 return ConstantVector::get(DestVecTy, res); 554 } 555 556 // We actually have to do a cast now. Perform the cast according to the 557 // opcode specified. 558 switch (opc) { 559 default: 560 llvm_unreachable("Failed to cast constant expression"); 561 case Instruction::FPTrunc: 562 case Instruction::FPExt: 563 if (ConstantFP *FPC = dyn_cast<ConstantFP>(V)) { 564 bool ignored; 565 APFloat Val = FPC->getValueAPF(); 566 Val.convert(DestTy->isFloatTy() ? APFloat::IEEEsingle : 567 DestTy->isDoubleTy() ? APFloat::IEEEdouble : 568 DestTy->isX86_FP80Ty() ? APFloat::x87DoubleExtended : 569 DestTy->isFP128Ty() ? APFloat::IEEEquad : 570 APFloat::Bogus, 571 APFloat::rmNearestTiesToEven, &ignored); 572 return ConstantFP::get(V->getContext(), Val); 573 } 574 return 0; // Can't fold. 575 case Instruction::FPToUI: 576 case Instruction::FPToSI: 577 if (ConstantFP *FPC = dyn_cast<ConstantFP>(V)) { 578 const APFloat &V = FPC->getValueAPF(); 579 bool ignored; 580 uint64_t x[2]; 581 uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth(); 582 (void) V.convertToInteger(x, DestBitWidth, opc==Instruction::FPToSI, 583 APFloat::rmTowardZero, &ignored); 584 APInt Val(DestBitWidth, 2, x); 585 return ConstantInt::get(FPC->getContext(), Val); 586 } 587 return 0; // Can't fold. 588 case Instruction::IntToPtr: //always treated as unsigned 589 if (V->isNullValue()) // Is it an integral null value? 590 return ConstantPointerNull::get(cast<PointerType>(DestTy)); 591 return 0; // Other pointer types cannot be casted 592 case Instruction::PtrToInt: // always treated as unsigned 593 // Is it a null pointer value? 594 if (V->isNullValue()) 595 return ConstantInt::get(DestTy, 0); 596 // If this is a sizeof-like expression, pull out multiplications by 597 // known factors to expose them to subsequent folding. If it's an 598 // alignof-like expression, factor out known factors. 599 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 600 if (CE->getOpcode() == Instruction::GetElementPtr && 601 CE->getOperand(0)->isNullValue()) { 602 const Type *Ty = 603 cast<PointerType>(CE->getOperand(0)->getType())->getElementType(); 604 if (CE->getNumOperands() == 2) { 605 // Handle a sizeof-like expression. 606 Constant *Idx = CE->getOperand(1); 607 bool isOne = isa<ConstantInt>(Idx) && cast<ConstantInt>(Idx)->isOne(); 608 if (Constant *C = getFoldedSizeOf(Ty, DestTy, !isOne)) { 609 Idx = ConstantExpr::getCast(CastInst::getCastOpcode(Idx, true, 610 DestTy, false), 611 Idx, DestTy); 612 return ConstantExpr::getMul(C, Idx); 613 } 614 } else if (CE->getNumOperands() == 3 && 615 CE->getOperand(1)->isNullValue()) { 616 // Handle an alignof-like expression. 617 if (const StructType *STy = dyn_cast<StructType>(Ty)) 618 if (!STy->isPacked()) { 619 ConstantInt *CI = cast<ConstantInt>(CE->getOperand(2)); 620 if (CI->isOne() && 621 STy->getNumElements() == 2 && 622 STy->getElementType(0)->isIntegerTy(1)) { 623 return getFoldedAlignOf(STy->getElementType(1), DestTy, false); 624 } 625 } 626 // Handle an offsetof-like expression. 627 if (Ty->isStructTy() || Ty->isArrayTy()) { 628 if (Constant *C = getFoldedOffsetOf(Ty, CE->getOperand(2), 629 DestTy, false)) 630 return C; 631 } 632 } 633 } 634 // Other pointer types cannot be casted 635 return 0; 636 case Instruction::UIToFP: 637 case Instruction::SIToFP: 638 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 639 APInt api = CI->getValue(); 640 const uint64_t zero[] = {0, 0}; 641 APFloat apf = APFloat(APInt(DestTy->getPrimitiveSizeInBits(), 642 2, zero)); 643 (void)apf.convertFromAPInt(api, 644 opc==Instruction::SIToFP, 645 APFloat::rmNearestTiesToEven); 646 return ConstantFP::get(V->getContext(), apf); 647 } 648 return 0; 649 case Instruction::ZExt: 650 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 651 uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth(); 652 APInt Result(CI->getValue()); 653 Result.zext(BitWidth); 654 return ConstantInt::get(V->getContext(), Result); 655 } 656 return 0; 657 case Instruction::SExt: 658 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 659 uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth(); 660 APInt Result(CI->getValue()); 661 Result.sext(BitWidth); 662 return ConstantInt::get(V->getContext(), Result); 663 } 664 return 0; 665 case Instruction::Trunc: { 666 uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth(); 667 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 668 APInt Result(CI->getValue()); 669 Result.trunc(DestBitWidth); 670 return ConstantInt::get(V->getContext(), Result); 671 } 672 673 // The input must be a constantexpr. See if we can simplify this based on 674 // the bytes we are demanding. Only do this if the source and dest are an 675 // even multiple of a byte. 676 if ((DestBitWidth & 7) == 0 && 677 (cast<IntegerType>(V->getType())->getBitWidth() & 7) == 0) 678 if (Constant *Res = ExtractConstantBytes(V, 0, DestBitWidth / 8)) 679 return Res; 680 681 return 0; 682 } 683 case Instruction::BitCast: 684 return FoldBitCast(V, DestTy); 685 } 686} 687 688Constant *llvm::ConstantFoldSelectInstruction(Constant *Cond, 689 Constant *V1, Constant *V2) { 690 if (ConstantInt *CB = dyn_cast<ConstantInt>(Cond)) 691 return CB->getZExtValue() ? V1 : V2; 692 693 if (isa<UndefValue>(V1)) return V2; 694 if (isa<UndefValue>(V2)) return V1; 695 if (isa<UndefValue>(Cond)) return V1; 696 if (V1 == V2) return V1; 697 return 0; 698} 699 700Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val, 701 Constant *Idx) { 702 if (isa<UndefValue>(Val)) // ee(undef, x) -> undef 703 return UndefValue::get(cast<VectorType>(Val->getType())->getElementType()); 704 if (Val->isNullValue()) // ee(zero, x) -> zero 705 return Constant::getNullValue( 706 cast<VectorType>(Val->getType())->getElementType()); 707 708 if (ConstantVector *CVal = dyn_cast<ConstantVector>(Val)) { 709 if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx)) { 710 return CVal->getOperand(CIdx->getZExtValue()); 711 } else if (isa<UndefValue>(Idx)) { 712 // ee({w,x,y,z}, undef) -> w (an arbitrary value). 713 return CVal->getOperand(0); 714 } 715 } 716 return 0; 717} 718 719Constant *llvm::ConstantFoldInsertElementInstruction(Constant *Val, 720 Constant *Elt, 721 Constant *Idx) { 722 ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx); 723 if (!CIdx) return 0; 724 APInt idxVal = CIdx->getValue(); 725 if (isa<UndefValue>(Val)) { 726 // Insertion of scalar constant into vector undef 727 // Optimize away insertion of undef 728 if (isa<UndefValue>(Elt)) 729 return Val; 730 // Otherwise break the aggregate undef into multiple undefs and do 731 // the insertion 732 unsigned numOps = 733 cast<VectorType>(Val->getType())->getNumElements(); 734 std::vector<Constant*> Ops; 735 Ops.reserve(numOps); 736 for (unsigned i = 0; i < numOps; ++i) { 737 Constant *Op = 738 (idxVal == i) ? Elt : UndefValue::get(Elt->getType()); 739 Ops.push_back(Op); 740 } 741 return ConstantVector::get(Ops); 742 } 743 if (isa<ConstantAggregateZero>(Val)) { 744 // Insertion of scalar constant into vector aggregate zero 745 // Optimize away insertion of zero 746 if (Elt->isNullValue()) 747 return Val; 748 // Otherwise break the aggregate zero into multiple zeros and do 749 // the insertion 750 unsigned numOps = 751 cast<VectorType>(Val->getType())->getNumElements(); 752 std::vector<Constant*> Ops; 753 Ops.reserve(numOps); 754 for (unsigned i = 0; i < numOps; ++i) { 755 Constant *Op = 756 (idxVal == i) ? Elt : Constant::getNullValue(Elt->getType()); 757 Ops.push_back(Op); 758 } 759 return ConstantVector::get(Ops); 760 } 761 if (ConstantVector *CVal = dyn_cast<ConstantVector>(Val)) { 762 // Insertion of scalar constant into vector constant 763 std::vector<Constant*> Ops; 764 Ops.reserve(CVal->getNumOperands()); 765 for (unsigned i = 0; i < CVal->getNumOperands(); ++i) { 766 Constant *Op = 767 (idxVal == i) ? Elt : cast<Constant>(CVal->getOperand(i)); 768 Ops.push_back(Op); 769 } 770 return ConstantVector::get(Ops); 771 } 772 773 return 0; 774} 775 776/// GetVectorElement - If C is a ConstantVector, ConstantAggregateZero or Undef 777/// return the specified element value. Otherwise return null. 778static Constant *GetVectorElement(Constant *C, unsigned EltNo) { 779 if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) 780 return CV->getOperand(EltNo); 781 782 const Type *EltTy = cast<VectorType>(C->getType())->getElementType(); 783 if (isa<ConstantAggregateZero>(C)) 784 return Constant::getNullValue(EltTy); 785 if (isa<UndefValue>(C)) 786 return UndefValue::get(EltTy); 787 return 0; 788} 789 790Constant *llvm::ConstantFoldShuffleVectorInstruction(Constant *V1, 791 Constant *V2, 792 Constant *Mask) { 793 // Undefined shuffle mask -> undefined value. 794 if (isa<UndefValue>(Mask)) return UndefValue::get(V1->getType()); 795 796 unsigned MaskNumElts = cast<VectorType>(Mask->getType())->getNumElements(); 797 unsigned SrcNumElts = cast<VectorType>(V1->getType())->getNumElements(); 798 const Type *EltTy = cast<VectorType>(V1->getType())->getElementType(); 799 800 // Loop over the shuffle mask, evaluating each element. 801 SmallVector<Constant*, 32> Result; 802 for (unsigned i = 0; i != MaskNumElts; ++i) { 803 Constant *InElt = GetVectorElement(Mask, i); 804 if (InElt == 0) return 0; 805 806 if (isa<UndefValue>(InElt)) 807 InElt = UndefValue::get(EltTy); 808 else if (ConstantInt *CI = dyn_cast<ConstantInt>(InElt)) { 809 unsigned Elt = CI->getZExtValue(); 810 if (Elt >= SrcNumElts*2) 811 InElt = UndefValue::get(EltTy); 812 else if (Elt >= SrcNumElts) 813 InElt = GetVectorElement(V2, Elt - SrcNumElts); 814 else 815 InElt = GetVectorElement(V1, Elt); 816 if (InElt == 0) return 0; 817 } else { 818 // Unknown value. 819 return 0; 820 } 821 Result.push_back(InElt); 822 } 823 824 return ConstantVector::get(&Result[0], Result.size()); 825} 826 827Constant *llvm::ConstantFoldExtractValueInstruction(Constant *Agg, 828 const unsigned *Idxs, 829 unsigned NumIdx) { 830 // Base case: no indices, so return the entire value. 831 if (NumIdx == 0) 832 return Agg; 833 834 if (isa<UndefValue>(Agg)) // ev(undef, x) -> undef 835 return UndefValue::get(ExtractValueInst::getIndexedType(Agg->getType(), 836 Idxs, 837 Idxs + NumIdx)); 838 839 if (isa<ConstantAggregateZero>(Agg)) // ev(0, x) -> 0 840 return 841 Constant::getNullValue(ExtractValueInst::getIndexedType(Agg->getType(), 842 Idxs, 843 Idxs + NumIdx)); 844 845 // Otherwise recurse. 846 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Agg)) 847 return ConstantFoldExtractValueInstruction(CS->getOperand(*Idxs), 848 Idxs+1, NumIdx-1); 849 850 if (ConstantArray *CA = dyn_cast<ConstantArray>(Agg)) 851 return ConstantFoldExtractValueInstruction(CA->getOperand(*Idxs), 852 Idxs+1, NumIdx-1); 853 ConstantVector *CV = cast<ConstantVector>(Agg); 854 return ConstantFoldExtractValueInstruction(CV->getOperand(*Idxs), 855 Idxs+1, NumIdx-1); 856} 857 858Constant *llvm::ConstantFoldInsertValueInstruction(Constant *Agg, 859 Constant *Val, 860 const unsigned *Idxs, 861 unsigned NumIdx) { 862 // Base case: no indices, so replace the entire value. 863 if (NumIdx == 0) 864 return Val; 865 866 if (isa<UndefValue>(Agg)) { 867 // Insertion of constant into aggregate undef 868 // Optimize away insertion of undef. 869 if (isa<UndefValue>(Val)) 870 return Agg; 871 872 // Otherwise break the aggregate undef into multiple undefs and do 873 // the insertion. 874 const CompositeType *AggTy = cast<CompositeType>(Agg->getType()); 875 unsigned numOps; 876 if (const ArrayType *AR = dyn_cast<ArrayType>(AggTy)) 877 numOps = AR->getNumElements(); 878 else 879 numOps = cast<StructType>(AggTy)->getNumElements(); 880 881 std::vector<Constant*> Ops(numOps); 882 for (unsigned i = 0; i < numOps; ++i) { 883 const Type *MemberTy = AggTy->getTypeAtIndex(i); 884 Constant *Op = 885 (*Idxs == i) ? 886 ConstantFoldInsertValueInstruction(UndefValue::get(MemberTy), 887 Val, Idxs+1, NumIdx-1) : 888 UndefValue::get(MemberTy); 889 Ops[i] = Op; 890 } 891 892 if (const StructType* ST = dyn_cast<StructType>(AggTy)) 893 return ConstantStruct::get(ST->getContext(), Ops, ST->isPacked()); 894 return ConstantArray::get(cast<ArrayType>(AggTy), Ops); 895 } 896 897 if (isa<ConstantAggregateZero>(Agg)) { 898 // Insertion of constant into aggregate zero 899 // Optimize away insertion of zero. 900 if (Val->isNullValue()) 901 return Agg; 902 903 // Otherwise break the aggregate zero into multiple zeros and do 904 // the insertion. 905 const CompositeType *AggTy = cast<CompositeType>(Agg->getType()); 906 unsigned numOps; 907 if (const ArrayType *AR = dyn_cast<ArrayType>(AggTy)) 908 numOps = AR->getNumElements(); 909 else 910 numOps = cast<StructType>(AggTy)->getNumElements(); 911 912 std::vector<Constant*> Ops(numOps); 913 for (unsigned i = 0; i < numOps; ++i) { 914 const Type *MemberTy = AggTy->getTypeAtIndex(i); 915 Constant *Op = 916 (*Idxs == i) ? 917 ConstantFoldInsertValueInstruction(Constant::getNullValue(MemberTy), 918 Val, Idxs+1, NumIdx-1) : 919 Constant::getNullValue(MemberTy); 920 Ops[i] = Op; 921 } 922 923 if (const StructType *ST = dyn_cast<StructType>(AggTy)) 924 return ConstantStruct::get(ST->getContext(), Ops, ST->isPacked()); 925 return ConstantArray::get(cast<ArrayType>(AggTy), Ops); 926 } 927 928 if (isa<ConstantStruct>(Agg) || isa<ConstantArray>(Agg)) { 929 // Insertion of constant into aggregate constant. 930 std::vector<Constant*> Ops(Agg->getNumOperands()); 931 for (unsigned i = 0; i < Agg->getNumOperands(); ++i) { 932 Constant *Op = cast<Constant>(Agg->getOperand(i)); 933 if (*Idxs == i) 934 Op = ConstantFoldInsertValueInstruction(Op, Val, Idxs+1, NumIdx-1); 935 Ops[i] = Op; 936 } 937 938 if (const StructType* ST = dyn_cast<StructType>(Agg->getType())) 939 return ConstantStruct::get(ST->getContext(), Ops, ST->isPacked()); 940 return ConstantArray::get(cast<ArrayType>(Agg->getType()), Ops); 941 } 942 943 return 0; 944} 945 946 947Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, 948 Constant *C1, Constant *C2) { 949 // No compile-time operations on this type yet. 950 if (C1->getType()->isPPC_FP128Ty()) 951 return 0; 952 953 // Handle UndefValue up front. 954 if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) { 955 switch (Opcode) { 956 case Instruction::Xor: 957 if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) 958 // Handle undef ^ undef -> 0 special case. This is a common 959 // idiom (misuse). 960 return Constant::getNullValue(C1->getType()); 961 // Fallthrough 962 case Instruction::Add: 963 case Instruction::Sub: 964 return UndefValue::get(C1->getType()); 965 case Instruction::Mul: 966 case Instruction::And: 967 return Constant::getNullValue(C1->getType()); 968 case Instruction::UDiv: 969 case Instruction::SDiv: 970 case Instruction::URem: 971 case Instruction::SRem: 972 if (!isa<UndefValue>(C2)) // undef / X -> 0 973 return Constant::getNullValue(C1->getType()); 974 return C2; // X / undef -> undef 975 case Instruction::Or: // X | undef -> -1 976 if (const VectorType *PTy = dyn_cast<VectorType>(C1->getType())) 977 return Constant::getAllOnesValue(PTy); 978 return Constant::getAllOnesValue(C1->getType()); 979 case Instruction::LShr: 980 if (isa<UndefValue>(C2) && isa<UndefValue>(C1)) 981 return C1; // undef lshr undef -> undef 982 return Constant::getNullValue(C1->getType()); // X lshr undef -> 0 983 // undef lshr X -> 0 984 case Instruction::AShr: 985 if (!isa<UndefValue>(C2)) 986 return C1; // undef ashr X --> undef 987 else if (isa<UndefValue>(C1)) 988 return C1; // undef ashr undef -> undef 989 else 990 return C1; // X ashr undef --> X 991 case Instruction::Shl: 992 // undef << X -> 0 or X << undef -> 0 993 return Constant::getNullValue(C1->getType()); 994 } 995 } 996 997 // Handle simplifications when the RHS is a constant int. 998 if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) { 999 switch (Opcode) { 1000 case Instruction::Add: 1001 if (CI2->equalsInt(0)) return C1; // X + 0 == X 1002 break; 1003 case Instruction::Sub: 1004 if (CI2->equalsInt(0)) return C1; // X - 0 == X 1005 break; 1006 case Instruction::Mul: 1007 if (CI2->equalsInt(0)) return C2; // X * 0 == 0 1008 if (CI2->equalsInt(1)) 1009 return C1; // X * 1 == X 1010 break; 1011 case Instruction::UDiv: 1012 case Instruction::SDiv: 1013 if (CI2->equalsInt(1)) 1014 return C1; // X / 1 == X 1015 if (CI2->equalsInt(0)) 1016 return UndefValue::get(CI2->getType()); // X / 0 == undef 1017 break; 1018 case Instruction::URem: 1019 case Instruction::SRem: 1020 if (CI2->equalsInt(1)) 1021 return Constant::getNullValue(CI2->getType()); // X % 1 == 0 1022 if (CI2->equalsInt(0)) 1023 return UndefValue::get(CI2->getType()); // X % 0 == undef 1024 break; 1025 case Instruction::And: 1026 if (CI2->isZero()) return C2; // X & 0 == 0 1027 if (CI2->isAllOnesValue()) 1028 return C1; // X & -1 == X 1029 1030 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) { 1031 // (zext i32 to i64) & 4294967295 -> (zext i32 to i64) 1032 if (CE1->getOpcode() == Instruction::ZExt) { 1033 unsigned DstWidth = CI2->getType()->getBitWidth(); 1034 unsigned SrcWidth = 1035 CE1->getOperand(0)->getType()->getPrimitiveSizeInBits(); 1036 APInt PossiblySetBits(APInt::getLowBitsSet(DstWidth, SrcWidth)); 1037 if ((PossiblySetBits & CI2->getValue()) == PossiblySetBits) 1038 return C1; 1039 } 1040 1041 // If and'ing the address of a global with a constant, fold it. 1042 if (CE1->getOpcode() == Instruction::PtrToInt && 1043 isa<GlobalValue>(CE1->getOperand(0))) { 1044 GlobalValue *GV = cast<GlobalValue>(CE1->getOperand(0)); 1045 1046 // Functions are at least 4-byte aligned. 1047 unsigned GVAlign = GV->getAlignment(); 1048 if (isa<Function>(GV)) 1049 GVAlign = std::max(GVAlign, 4U); 1050 1051 if (GVAlign > 1) { 1052 unsigned DstWidth = CI2->getType()->getBitWidth(); 1053 unsigned SrcWidth = std::min(DstWidth, Log2_32(GVAlign)); 1054 APInt BitsNotSet(APInt::getLowBitsSet(DstWidth, SrcWidth)); 1055 1056 // If checking bits we know are clear, return zero. 1057 if ((CI2->getValue() & BitsNotSet) == CI2->getValue()) 1058 return Constant::getNullValue(CI2->getType()); 1059 } 1060 } 1061 } 1062 break; 1063 case Instruction::Or: 1064 if (CI2->equalsInt(0)) return C1; // X | 0 == X 1065 if (CI2->isAllOnesValue()) 1066 return C2; // X | -1 == -1 1067 break; 1068 case Instruction::Xor: 1069 if (CI2->equalsInt(0)) return C1; // X ^ 0 == X 1070 1071 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) { 1072 switch (CE1->getOpcode()) { 1073 default: break; 1074 case Instruction::ICmp: 1075 case Instruction::FCmp: 1076 // cmp pred ^ true -> cmp !pred 1077 assert(CI2->equalsInt(1)); 1078 CmpInst::Predicate pred = (CmpInst::Predicate)CE1->getPredicate(); 1079 pred = CmpInst::getInversePredicate(pred); 1080 return ConstantExpr::getCompare(pred, CE1->getOperand(0), 1081 CE1->getOperand(1)); 1082 } 1083 } 1084 break; 1085 case Instruction::AShr: 1086 // ashr (zext C to Ty), C2 -> lshr (zext C, CSA), C2 1087 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) 1088 if (CE1->getOpcode() == Instruction::ZExt) // Top bits known zero. 1089 return ConstantExpr::getLShr(C1, C2); 1090 break; 1091 } 1092 } else if (isa<ConstantInt>(C1)) { 1093 // If C1 is a ConstantInt and C2 is not, swap the operands. 1094 if (Instruction::isCommutative(Opcode)) 1095 return ConstantExpr::get(Opcode, C2, C1); 1096 } 1097 1098 // At this point we know neither constant is an UndefValue. 1099 if (ConstantInt *CI1 = dyn_cast<ConstantInt>(C1)) { 1100 if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) { 1101 using namespace APIntOps; 1102 const APInt &C1V = CI1->getValue(); 1103 const APInt &C2V = CI2->getValue(); 1104 switch (Opcode) { 1105 default: 1106 break; 1107 case Instruction::Add: 1108 return ConstantInt::get(CI1->getContext(), C1V + C2V); 1109 case Instruction::Sub: 1110 return ConstantInt::get(CI1->getContext(), C1V - C2V); 1111 case Instruction::Mul: 1112 return ConstantInt::get(CI1->getContext(), C1V * C2V); 1113 case Instruction::UDiv: 1114 assert(!CI2->isNullValue() && "Div by zero handled above"); 1115 return ConstantInt::get(CI1->getContext(), C1V.udiv(C2V)); 1116 case Instruction::SDiv: 1117 assert(!CI2->isNullValue() && "Div by zero handled above"); 1118 if (C2V.isAllOnesValue() && C1V.isMinSignedValue()) 1119 return UndefValue::get(CI1->getType()); // MIN_INT / -1 -> undef 1120 return ConstantInt::get(CI1->getContext(), C1V.sdiv(C2V)); 1121 case Instruction::URem: 1122 assert(!CI2->isNullValue() && "Div by zero handled above"); 1123 return ConstantInt::get(CI1->getContext(), C1V.urem(C2V)); 1124 case Instruction::SRem: 1125 assert(!CI2->isNullValue() && "Div by zero handled above"); 1126 if (C2V.isAllOnesValue() && C1V.isMinSignedValue()) 1127 return UndefValue::get(CI1->getType()); // MIN_INT % -1 -> undef 1128 return ConstantInt::get(CI1->getContext(), C1V.srem(C2V)); 1129 case Instruction::And: 1130 return ConstantInt::get(CI1->getContext(), C1V & C2V); 1131 case Instruction::Or: 1132 return ConstantInt::get(CI1->getContext(), C1V | C2V); 1133 case Instruction::Xor: 1134 return ConstantInt::get(CI1->getContext(), C1V ^ C2V); 1135 case Instruction::Shl: { 1136 uint32_t shiftAmt = C2V.getZExtValue(); 1137 if (shiftAmt < C1V.getBitWidth()) 1138 return ConstantInt::get(CI1->getContext(), C1V.shl(shiftAmt)); 1139 else 1140 return UndefValue::get(C1->getType()); // too big shift is undef 1141 } 1142 case Instruction::LShr: { 1143 uint32_t shiftAmt = C2V.getZExtValue(); 1144 if (shiftAmt < C1V.getBitWidth()) 1145 return ConstantInt::get(CI1->getContext(), C1V.lshr(shiftAmt)); 1146 else 1147 return UndefValue::get(C1->getType()); // too big shift is undef 1148 } 1149 case Instruction::AShr: { 1150 uint32_t shiftAmt = C2V.getZExtValue(); 1151 if (shiftAmt < C1V.getBitWidth()) 1152 return ConstantInt::get(CI1->getContext(), C1V.ashr(shiftAmt)); 1153 else 1154 return UndefValue::get(C1->getType()); // too big shift is undef 1155 } 1156 } 1157 } 1158 1159 switch (Opcode) { 1160 case Instruction::SDiv: 1161 case Instruction::UDiv: 1162 case Instruction::URem: 1163 case Instruction::SRem: 1164 case Instruction::LShr: 1165 case Instruction::AShr: 1166 case Instruction::Shl: 1167 if (CI1->equalsInt(0)) return C1; 1168 break; 1169 default: 1170 break; 1171 } 1172 } else if (ConstantFP *CFP1 = dyn_cast<ConstantFP>(C1)) { 1173 if (ConstantFP *CFP2 = dyn_cast<ConstantFP>(C2)) { 1174 APFloat C1V = CFP1->getValueAPF(); 1175 APFloat C2V = CFP2->getValueAPF(); 1176 APFloat C3V = C1V; // copy for modification 1177 switch (Opcode) { 1178 default: 1179 break; 1180 case Instruction::FAdd: 1181 (void)C3V.add(C2V, APFloat::rmNearestTiesToEven); 1182 return ConstantFP::get(C1->getContext(), C3V); 1183 case Instruction::FSub: 1184 (void)C3V.subtract(C2V, APFloat::rmNearestTiesToEven); 1185 return ConstantFP::get(C1->getContext(), C3V); 1186 case Instruction::FMul: 1187 (void)C3V.multiply(C2V, APFloat::rmNearestTiesToEven); 1188 return ConstantFP::get(C1->getContext(), C3V); 1189 case Instruction::FDiv: 1190 (void)C3V.divide(C2V, APFloat::rmNearestTiesToEven); 1191 return ConstantFP::get(C1->getContext(), C3V); 1192 case Instruction::FRem: 1193 (void)C3V.mod(C2V, APFloat::rmNearestTiesToEven); 1194 return ConstantFP::get(C1->getContext(), C3V); 1195 } 1196 } 1197 } else if (const VectorType *VTy = dyn_cast<VectorType>(C1->getType())) { 1198 ConstantVector *CP1 = dyn_cast<ConstantVector>(C1); 1199 ConstantVector *CP2 = dyn_cast<ConstantVector>(C2); 1200 if ((CP1 != NULL || isa<ConstantAggregateZero>(C1)) && 1201 (CP2 != NULL || isa<ConstantAggregateZero>(C2))) { 1202 std::vector<Constant*> Res; 1203 const Type* EltTy = VTy->getElementType(); 1204 Constant *C1 = 0; 1205 Constant *C2 = 0; 1206 switch (Opcode) { 1207 default: 1208 break; 1209 case Instruction::Add: 1210 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1211 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1212 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1213 Res.push_back(ConstantExpr::getAdd(C1, C2)); 1214 } 1215 return ConstantVector::get(Res); 1216 case Instruction::FAdd: 1217 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1218 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1219 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1220 Res.push_back(ConstantExpr::getFAdd(C1, C2)); 1221 } 1222 return ConstantVector::get(Res); 1223 case Instruction::Sub: 1224 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1225 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1226 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1227 Res.push_back(ConstantExpr::getSub(C1, C2)); 1228 } 1229 return ConstantVector::get(Res); 1230 case Instruction::FSub: 1231 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1232 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1233 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1234 Res.push_back(ConstantExpr::getFSub(C1, C2)); 1235 } 1236 return ConstantVector::get(Res); 1237 case Instruction::Mul: 1238 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1239 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1240 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1241 Res.push_back(ConstantExpr::getMul(C1, C2)); 1242 } 1243 return ConstantVector::get(Res); 1244 case Instruction::FMul: 1245 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1246 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1247 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1248 Res.push_back(ConstantExpr::getFMul(C1, C2)); 1249 } 1250 return ConstantVector::get(Res); 1251 case Instruction::UDiv: 1252 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1253 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1254 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1255 Res.push_back(ConstantExpr::getUDiv(C1, C2)); 1256 } 1257 return ConstantVector::get(Res); 1258 case Instruction::SDiv: 1259 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1260 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1261 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1262 Res.push_back(ConstantExpr::getSDiv(C1, C2)); 1263 } 1264 return ConstantVector::get(Res); 1265 case Instruction::FDiv: 1266 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1267 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1268 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1269 Res.push_back(ConstantExpr::getFDiv(C1, C2)); 1270 } 1271 return ConstantVector::get(Res); 1272 case Instruction::URem: 1273 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1274 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1275 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1276 Res.push_back(ConstantExpr::getURem(C1, C2)); 1277 } 1278 return ConstantVector::get(Res); 1279 case Instruction::SRem: 1280 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1281 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1282 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1283 Res.push_back(ConstantExpr::getSRem(C1, C2)); 1284 } 1285 return ConstantVector::get(Res); 1286 case Instruction::FRem: 1287 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1288 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1289 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1290 Res.push_back(ConstantExpr::getFRem(C1, C2)); 1291 } 1292 return ConstantVector::get(Res); 1293 case Instruction::And: 1294 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1295 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1296 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1297 Res.push_back(ConstantExpr::getAnd(C1, C2)); 1298 } 1299 return ConstantVector::get(Res); 1300 case Instruction::Or: 1301 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1302 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1303 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1304 Res.push_back(ConstantExpr::getOr(C1, C2)); 1305 } 1306 return ConstantVector::get(Res); 1307 case Instruction::Xor: 1308 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1309 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1310 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1311 Res.push_back(ConstantExpr::getXor(C1, C2)); 1312 } 1313 return ConstantVector::get(Res); 1314 case Instruction::LShr: 1315 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1316 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1317 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1318 Res.push_back(ConstantExpr::getLShr(C1, C2)); 1319 } 1320 return ConstantVector::get(Res); 1321 case Instruction::AShr: 1322 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1323 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1324 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1325 Res.push_back(ConstantExpr::getAShr(C1, C2)); 1326 } 1327 return ConstantVector::get(Res); 1328 case Instruction::Shl: 1329 for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) { 1330 C1 = CP1 ? CP1->getOperand(i) : Constant::getNullValue(EltTy); 1331 C2 = CP2 ? CP2->getOperand(i) : Constant::getNullValue(EltTy); 1332 Res.push_back(ConstantExpr::getShl(C1, C2)); 1333 } 1334 return ConstantVector::get(Res); 1335 } 1336 } 1337 } 1338 1339 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) { 1340 // There are many possible foldings we could do here. We should probably 1341 // at least fold add of a pointer with an integer into the appropriate 1342 // getelementptr. This will improve alias analysis a bit. 1343 1344 // Given ((a + b) + c), if (b + c) folds to something interesting, return 1345 // (a + (b + c)). 1346 if (Instruction::isAssociative(Opcode, C1->getType()) && 1347 CE1->getOpcode() == Opcode) { 1348 Constant *T = ConstantExpr::get(Opcode, CE1->getOperand(1), C2); 1349 if (!isa<ConstantExpr>(T) || cast<ConstantExpr>(T)->getOpcode() != Opcode) 1350 return ConstantExpr::get(Opcode, CE1->getOperand(0), T); 1351 } 1352 } else if (isa<ConstantExpr>(C2)) { 1353 // If C2 is a constant expr and C1 isn't, flop them around and fold the 1354 // other way if possible. 1355 if (Instruction::isCommutative(Opcode)) 1356 return ConstantFoldBinaryInstruction(Opcode, C2, C1); 1357 } 1358 1359 // i1 can be simplified in many cases. 1360 if (C1->getType()->isIntegerTy(1)) { 1361 switch (Opcode) { 1362 case Instruction::Add: 1363 case Instruction::Sub: 1364 return ConstantExpr::getXor(C1, C2); 1365 case Instruction::Mul: 1366 return ConstantExpr::getAnd(C1, C2); 1367 case Instruction::Shl: 1368 case Instruction::LShr: 1369 case Instruction::AShr: 1370 // We can assume that C2 == 0. If it were one the result would be 1371 // undefined because the shift value is as large as the bitwidth. 1372 return C1; 1373 case Instruction::SDiv: 1374 case Instruction::UDiv: 1375 // We can assume that C2 == 1. If it were zero the result would be 1376 // undefined through division by zero. 1377 return C1; 1378 case Instruction::URem: 1379 case Instruction::SRem: 1380 // We can assume that C2 == 1. If it were zero the result would be 1381 // undefined through division by zero. 1382 return ConstantInt::getFalse(C1->getContext()); 1383 default: 1384 break; 1385 } 1386 } 1387 1388 // We don't know how to fold this. 1389 return 0; 1390} 1391 1392/// isZeroSizedType - This type is zero sized if its an array or structure of 1393/// zero sized types. The only leaf zero sized type is an empty structure. 1394static bool isMaybeZeroSizedType(const Type *Ty) { 1395 if (Ty->isOpaqueTy()) return true; // Can't say. 1396 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 1397 1398 // If all of elements have zero size, this does too. 1399 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) 1400 if (!isMaybeZeroSizedType(STy->getElementType(i))) return false; 1401 return true; 1402 1403 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 1404 return isMaybeZeroSizedType(ATy->getElementType()); 1405 } 1406 return false; 1407} 1408 1409/// IdxCompare - Compare the two constants as though they were getelementptr 1410/// indices. This allows coersion of the types to be the same thing. 1411/// 1412/// If the two constants are the "same" (after coersion), return 0. If the 1413/// first is less than the second, return -1, if the second is less than the 1414/// first, return 1. If the constants are not integral, return -2. 1415/// 1416static int IdxCompare(Constant *C1, Constant *C2, const Type *ElTy) { 1417 if (C1 == C2) return 0; 1418 1419 // Ok, we found a different index. If they are not ConstantInt, we can't do 1420 // anything with them. 1421 if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2)) 1422 return -2; // don't know! 1423 1424 // Ok, we have two differing integer indices. Sign extend them to be the same 1425 // type. Long is always big enough, so we use it. 1426 if (!C1->getType()->isIntegerTy(64)) 1427 C1 = ConstantExpr::getSExt(C1, Type::getInt64Ty(C1->getContext())); 1428 1429 if (!C2->getType()->isIntegerTy(64)) 1430 C2 = ConstantExpr::getSExt(C2, Type::getInt64Ty(C1->getContext())); 1431 1432 if (C1 == C2) return 0; // They are equal 1433 1434 // If the type being indexed over is really just a zero sized type, there is 1435 // no pointer difference being made here. 1436 if (isMaybeZeroSizedType(ElTy)) 1437 return -2; // dunno. 1438 1439 // If they are really different, now that they are the same type, then we 1440 // found a difference! 1441 if (cast<ConstantInt>(C1)->getSExtValue() < 1442 cast<ConstantInt>(C2)->getSExtValue()) 1443 return -1; 1444 else 1445 return 1; 1446} 1447 1448/// evaluateFCmpRelation - This function determines if there is anything we can 1449/// decide about the two constants provided. This doesn't need to handle simple 1450/// things like ConstantFP comparisons, but should instead handle ConstantExprs. 1451/// If we can determine that the two constants have a particular relation to 1452/// each other, we should return the corresponding FCmpInst predicate, 1453/// otherwise return FCmpInst::BAD_FCMP_PREDICATE. This is used below in 1454/// ConstantFoldCompareInstruction. 1455/// 1456/// To simplify this code we canonicalize the relation so that the first 1457/// operand is always the most "complex" of the two. We consider ConstantFP 1458/// to be the simplest, and ConstantExprs to be the most complex. 1459static FCmpInst::Predicate evaluateFCmpRelation(Constant *V1, Constant *V2) { 1460 assert(V1->getType() == V2->getType() && 1461 "Cannot compare values of different types!"); 1462 1463 // No compile-time operations on this type yet. 1464 if (V1->getType()->isPPC_FP128Ty()) 1465 return FCmpInst::BAD_FCMP_PREDICATE; 1466 1467 // Handle degenerate case quickly 1468 if (V1 == V2) return FCmpInst::FCMP_OEQ; 1469 1470 if (!isa<ConstantExpr>(V1)) { 1471 if (!isa<ConstantExpr>(V2)) { 1472 // We distilled thisUse the standard constant folder for a few cases 1473 ConstantInt *R = 0; 1474 R = dyn_cast<ConstantInt>( 1475 ConstantExpr::getFCmp(FCmpInst::FCMP_OEQ, V1, V2)); 1476 if (R && !R->isZero()) 1477 return FCmpInst::FCMP_OEQ; 1478 R = dyn_cast<ConstantInt>( 1479 ConstantExpr::getFCmp(FCmpInst::FCMP_OLT, V1, V2)); 1480 if (R && !R->isZero()) 1481 return FCmpInst::FCMP_OLT; 1482 R = dyn_cast<ConstantInt>( 1483 ConstantExpr::getFCmp(FCmpInst::FCMP_OGT, V1, V2)); 1484 if (R && !R->isZero()) 1485 return FCmpInst::FCMP_OGT; 1486 1487 // Nothing more we can do 1488 return FCmpInst::BAD_FCMP_PREDICATE; 1489 } 1490 1491 // If the first operand is simple and second is ConstantExpr, swap operands. 1492 FCmpInst::Predicate SwappedRelation = evaluateFCmpRelation(V2, V1); 1493 if (SwappedRelation != FCmpInst::BAD_FCMP_PREDICATE) 1494 return FCmpInst::getSwappedPredicate(SwappedRelation); 1495 } else { 1496 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a 1497 // constantexpr or a simple constant. 1498 ConstantExpr *CE1 = cast<ConstantExpr>(V1); 1499 switch (CE1->getOpcode()) { 1500 case Instruction::FPTrunc: 1501 case Instruction::FPExt: 1502 case Instruction::UIToFP: 1503 case Instruction::SIToFP: 1504 // We might be able to do something with these but we don't right now. 1505 break; 1506 default: 1507 break; 1508 } 1509 } 1510 // There are MANY other foldings that we could perform here. They will 1511 // probably be added on demand, as they seem needed. 1512 return FCmpInst::BAD_FCMP_PREDICATE; 1513} 1514 1515/// evaluateICmpRelation - This function determines if there is anything we can 1516/// decide about the two constants provided. This doesn't need to handle simple 1517/// things like integer comparisons, but should instead handle ConstantExprs 1518/// and GlobalValues. If we can determine that the two constants have a 1519/// particular relation to each other, we should return the corresponding ICmp 1520/// predicate, otherwise return ICmpInst::BAD_ICMP_PREDICATE. 1521/// 1522/// To simplify this code we canonicalize the relation so that the first 1523/// operand is always the most "complex" of the two. We consider simple 1524/// constants (like ConstantInt) to be the simplest, followed by 1525/// GlobalValues, followed by ConstantExpr's (the most complex). 1526/// 1527static ICmpInst::Predicate evaluateICmpRelation(Constant *V1, Constant *V2, 1528 bool isSigned) { 1529 assert(V1->getType() == V2->getType() && 1530 "Cannot compare different types of values!"); 1531 if (V1 == V2) return ICmpInst::ICMP_EQ; 1532 1533 if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1) && 1534 !isa<BlockAddress>(V1)) { 1535 if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2) && 1536 !isa<BlockAddress>(V2)) { 1537 // We distilled this down to a simple case, use the standard constant 1538 // folder. 1539 ConstantInt *R = 0; 1540 ICmpInst::Predicate pred = ICmpInst::ICMP_EQ; 1541 R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2)); 1542 if (R && !R->isZero()) 1543 return pred; 1544 pred = isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 1545 R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2)); 1546 if (R && !R->isZero()) 1547 return pred; 1548 pred = isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1549 R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2)); 1550 if (R && !R->isZero()) 1551 return pred; 1552 1553 // If we couldn't figure it out, bail. 1554 return ICmpInst::BAD_ICMP_PREDICATE; 1555 } 1556 1557 // If the first operand is simple, swap operands. 1558 ICmpInst::Predicate SwappedRelation = 1559 evaluateICmpRelation(V2, V1, isSigned); 1560 if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) 1561 return ICmpInst::getSwappedPredicate(SwappedRelation); 1562 1563 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V1)) { 1564 if (isa<ConstantExpr>(V2)) { // Swap as necessary. 1565 ICmpInst::Predicate SwappedRelation = 1566 evaluateICmpRelation(V2, V1, isSigned); 1567 if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) 1568 return ICmpInst::getSwappedPredicate(SwappedRelation); 1569 return ICmpInst::BAD_ICMP_PREDICATE; 1570 } 1571 1572 // Now we know that the RHS is a GlobalValue, BlockAddress or simple 1573 // constant (which, since the types must match, means that it's a 1574 // ConstantPointerNull). 1575 if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) { 1576 // Don't try to decide equality of aliases. 1577 if (!isa<GlobalAlias>(GV) && !isa<GlobalAlias>(GV2)) 1578 if (!GV->hasExternalWeakLinkage() || !GV2->hasExternalWeakLinkage()) 1579 return ICmpInst::ICMP_NE; 1580 } else if (isa<BlockAddress>(V2)) { 1581 return ICmpInst::ICMP_NE; // Globals never equal labels. 1582 } else { 1583 assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!"); 1584 // GlobalVals can never be null unless they have external weak linkage. 1585 // We don't try to evaluate aliases here. 1586 if (!GV->hasExternalWeakLinkage() && !isa<GlobalAlias>(GV)) 1587 return ICmpInst::ICMP_NE; 1588 } 1589 } else if (const BlockAddress *BA = dyn_cast<BlockAddress>(V1)) { 1590 if (isa<ConstantExpr>(V2)) { // Swap as necessary. 1591 ICmpInst::Predicate SwappedRelation = 1592 evaluateICmpRelation(V2, V1, isSigned); 1593 if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE) 1594 return ICmpInst::getSwappedPredicate(SwappedRelation); 1595 return ICmpInst::BAD_ICMP_PREDICATE; 1596 } 1597 1598 // Now we know that the RHS is a GlobalValue, BlockAddress or simple 1599 // constant (which, since the types must match, means that it is a 1600 // ConstantPointerNull). 1601 if (const BlockAddress *BA2 = dyn_cast<BlockAddress>(V2)) { 1602 // Block address in another function can't equal this one, but block 1603 // addresses in the current function might be the same if blocks are 1604 // empty. 1605 if (BA2->getFunction() != BA->getFunction()) 1606 return ICmpInst::ICMP_NE; 1607 } else { 1608 // Block addresses aren't null, don't equal the address of globals. 1609 assert((isa<ConstantPointerNull>(V2) || isa<GlobalValue>(V2)) && 1610 "Canonicalization guarantee!"); 1611 return ICmpInst::ICMP_NE; 1612 } 1613 } else { 1614 // Ok, the LHS is known to be a constantexpr. The RHS can be any of a 1615 // constantexpr, a global, block address, or a simple constant. 1616 ConstantExpr *CE1 = cast<ConstantExpr>(V1); 1617 Constant *CE1Op0 = CE1->getOperand(0); 1618 1619 switch (CE1->getOpcode()) { 1620 case Instruction::Trunc: 1621 case Instruction::FPTrunc: 1622 case Instruction::FPExt: 1623 case Instruction::FPToUI: 1624 case Instruction::FPToSI: 1625 break; // We can't evaluate floating point casts or truncations. 1626 1627 case Instruction::UIToFP: 1628 case Instruction::SIToFP: 1629 case Instruction::BitCast: 1630 case Instruction::ZExt: 1631 case Instruction::SExt: 1632 // If the cast is not actually changing bits, and the second operand is a 1633 // null pointer, do the comparison with the pre-casted value. 1634 if (V2->isNullValue() && 1635 (CE1->getType()->isPointerTy() || CE1->getType()->isIntegerTy())) { 1636 if (CE1->getOpcode() == Instruction::ZExt) isSigned = false; 1637 if (CE1->getOpcode() == Instruction::SExt) isSigned = true; 1638 return evaluateICmpRelation(CE1Op0, 1639 Constant::getNullValue(CE1Op0->getType()), 1640 isSigned); 1641 } 1642 break; 1643 1644 case Instruction::GetElementPtr: 1645 // Ok, since this is a getelementptr, we know that the constant has a 1646 // pointer type. Check the various cases. 1647 if (isa<ConstantPointerNull>(V2)) { 1648 // If we are comparing a GEP to a null pointer, check to see if the base 1649 // of the GEP equals the null pointer. 1650 if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) { 1651 if (GV->hasExternalWeakLinkage()) 1652 // Weak linkage GVals could be zero or not. We're comparing that 1653 // to null pointer so its greater-or-equal 1654 return isSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; 1655 else 1656 // If its not weak linkage, the GVal must have a non-zero address 1657 // so the result is greater-than 1658 return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1659 } else if (isa<ConstantPointerNull>(CE1Op0)) { 1660 // If we are indexing from a null pointer, check to see if we have any 1661 // non-zero indices. 1662 for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i) 1663 if (!CE1->getOperand(i)->isNullValue()) 1664 // Offsetting from null, must not be equal. 1665 return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1666 // Only zero indexes from null, must still be zero. 1667 return ICmpInst::ICMP_EQ; 1668 } 1669 // Otherwise, we can't really say if the first operand is null or not. 1670 } else if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) { 1671 if (isa<ConstantPointerNull>(CE1Op0)) { 1672 if (GV2->hasExternalWeakLinkage()) 1673 // Weak linkage GVals could be zero or not. We're comparing it to 1674 // a null pointer, so its less-or-equal 1675 return isSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; 1676 else 1677 // If its not weak linkage, the GVal must have a non-zero address 1678 // so the result is less-than 1679 return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 1680 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) { 1681 if (GV == GV2) { 1682 // If this is a getelementptr of the same global, then it must be 1683 // different. Because the types must match, the getelementptr could 1684 // only have at most one index, and because we fold getelementptr's 1685 // with a single zero index, it must be nonzero. 1686 assert(CE1->getNumOperands() == 2 && 1687 !CE1->getOperand(1)->isNullValue() && 1688 "Suprising getelementptr!"); 1689 return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1690 } else { 1691 // If they are different globals, we don't know what the value is, 1692 // but they can't be equal. 1693 return ICmpInst::ICMP_NE; 1694 } 1695 } 1696 } else { 1697 ConstantExpr *CE2 = cast<ConstantExpr>(V2); 1698 Constant *CE2Op0 = CE2->getOperand(0); 1699 1700 // There are MANY other foldings that we could perform here. They will 1701 // probably be added on demand, as they seem needed. 1702 switch (CE2->getOpcode()) { 1703 default: break; 1704 case Instruction::GetElementPtr: 1705 // By far the most common case to handle is when the base pointers are 1706 // obviously to the same or different globals. 1707 if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) { 1708 if (CE1Op0 != CE2Op0) // Don't know relative ordering, but not equal 1709 return ICmpInst::ICMP_NE; 1710 // Ok, we know that both getelementptr instructions are based on the 1711 // same global. From this, we can precisely determine the relative 1712 // ordering of the resultant pointers. 1713 unsigned i = 1; 1714 1715 // The logic below assumes that the result of the comparison 1716 // can be determined by finding the first index that differs. 1717 // This doesn't work if there is over-indexing in any 1718 // subsequent indices, so check for that case first. 1719 if (!CE1->isGEPWithNoNotionalOverIndexing() || 1720 !CE2->isGEPWithNoNotionalOverIndexing()) 1721 return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. 1722 1723 // Compare all of the operands the GEP's have in common. 1724 gep_type_iterator GTI = gep_type_begin(CE1); 1725 for (;i != CE1->getNumOperands() && i != CE2->getNumOperands(); 1726 ++i, ++GTI) 1727 switch (IdxCompare(CE1->getOperand(i), 1728 CE2->getOperand(i), GTI.getIndexedType())) { 1729 case -1: return isSigned ? ICmpInst::ICMP_SLT:ICmpInst::ICMP_ULT; 1730 case 1: return isSigned ? ICmpInst::ICMP_SGT:ICmpInst::ICMP_UGT; 1731 case -2: return ICmpInst::BAD_ICMP_PREDICATE; 1732 } 1733 1734 // Ok, we ran out of things they have in common. If any leftovers 1735 // are non-zero then we have a difference, otherwise we are equal. 1736 for (; i < CE1->getNumOperands(); ++i) 1737 if (!CE1->getOperand(i)->isNullValue()) { 1738 if (isa<ConstantInt>(CE1->getOperand(i))) 1739 return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; 1740 else 1741 return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. 1742 } 1743 1744 for (; i < CE2->getNumOperands(); ++i) 1745 if (!CE2->getOperand(i)->isNullValue()) { 1746 if (isa<ConstantInt>(CE2->getOperand(i))) 1747 return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; 1748 else 1749 return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal. 1750 } 1751 return ICmpInst::ICMP_EQ; 1752 } 1753 } 1754 } 1755 default: 1756 break; 1757 } 1758 } 1759 1760 return ICmpInst::BAD_ICMP_PREDICATE; 1761} 1762 1763Constant *llvm::ConstantFoldCompareInstruction(unsigned short pred, 1764 Constant *C1, Constant *C2) { 1765 const Type *ResultTy; 1766 if (const VectorType *VT = dyn_cast<VectorType>(C1->getType())) 1767 ResultTy = VectorType::get(Type::getInt1Ty(C1->getContext()), 1768 VT->getNumElements()); 1769 else 1770 ResultTy = Type::getInt1Ty(C1->getContext()); 1771 1772 // Fold FCMP_FALSE/FCMP_TRUE unconditionally. 1773 if (pred == FCmpInst::FCMP_FALSE) 1774 return Constant::getNullValue(ResultTy); 1775 1776 if (pred == FCmpInst::FCMP_TRUE) 1777 return Constant::getAllOnesValue(ResultTy); 1778 1779 // Handle some degenerate cases first 1780 if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) { 1781 // For EQ and NE, we can always pick a value for the undef to make the 1782 // predicate pass or fail, so we can return undef. 1783 if (ICmpInst::isEquality(ICmpInst::Predicate(pred))) 1784 return UndefValue::get(ResultTy); 1785 // Otherwise, pick the same value as the non-undef operand, and fold 1786 // it to true or false. 1787 return ConstantInt::get(ResultTy, CmpInst::isTrueWhenEqual(pred)); 1788 } 1789 1790 // No compile-time operations on this type yet. 1791 if (C1->getType()->isPPC_FP128Ty()) 1792 return 0; 1793 1794 // icmp eq/ne(null,GV) -> false/true 1795 if (C1->isNullValue()) { 1796 if (const GlobalValue *GV = dyn_cast<GlobalValue>(C2)) 1797 // Don't try to evaluate aliases. External weak GV can be null. 1798 if (!isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage()) { 1799 if (pred == ICmpInst::ICMP_EQ) 1800 return ConstantInt::getFalse(C1->getContext()); 1801 else if (pred == ICmpInst::ICMP_NE) 1802 return ConstantInt::getTrue(C1->getContext()); 1803 } 1804 // icmp eq/ne(GV,null) -> false/true 1805 } else if (C2->isNullValue()) { 1806 if (const GlobalValue *GV = dyn_cast<GlobalValue>(C1)) 1807 // Don't try to evaluate aliases. External weak GV can be null. 1808 if (!isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage()) { 1809 if (pred == ICmpInst::ICMP_EQ) 1810 return ConstantInt::getFalse(C1->getContext()); 1811 else if (pred == ICmpInst::ICMP_NE) 1812 return ConstantInt::getTrue(C1->getContext()); 1813 } 1814 } 1815 1816 // If the comparison is a comparison between two i1's, simplify it. 1817 if (C1->getType()->isIntegerTy(1)) { 1818 switch(pred) { 1819 case ICmpInst::ICMP_EQ: 1820 if (isa<ConstantInt>(C2)) 1821 return ConstantExpr::getXor(C1, ConstantExpr::getNot(C2)); 1822 return ConstantExpr::getXor(ConstantExpr::getNot(C1), C2); 1823 case ICmpInst::ICMP_NE: 1824 return ConstantExpr::getXor(C1, C2); 1825 default: 1826 break; 1827 } 1828 } 1829 1830 if (isa<ConstantInt>(C1) && isa<ConstantInt>(C2)) { 1831 APInt V1 = cast<ConstantInt>(C1)->getValue(); 1832 APInt V2 = cast<ConstantInt>(C2)->getValue(); 1833 switch (pred) { 1834 default: llvm_unreachable("Invalid ICmp Predicate"); return 0; 1835 case ICmpInst::ICMP_EQ: return ConstantInt::get(ResultTy, V1 == V2); 1836 case ICmpInst::ICMP_NE: return ConstantInt::get(ResultTy, V1 != V2); 1837 case ICmpInst::ICMP_SLT: return ConstantInt::get(ResultTy, V1.slt(V2)); 1838 case ICmpInst::ICMP_SGT: return ConstantInt::get(ResultTy, V1.sgt(V2)); 1839 case ICmpInst::ICMP_SLE: return ConstantInt::get(ResultTy, V1.sle(V2)); 1840 case ICmpInst::ICMP_SGE: return ConstantInt::get(ResultTy, V1.sge(V2)); 1841 case ICmpInst::ICMP_ULT: return ConstantInt::get(ResultTy, V1.ult(V2)); 1842 case ICmpInst::ICMP_UGT: return ConstantInt::get(ResultTy, V1.ugt(V2)); 1843 case ICmpInst::ICMP_ULE: return ConstantInt::get(ResultTy, V1.ule(V2)); 1844 case ICmpInst::ICMP_UGE: return ConstantInt::get(ResultTy, V1.uge(V2)); 1845 } 1846 } else if (isa<ConstantFP>(C1) && isa<ConstantFP>(C2)) { 1847 APFloat C1V = cast<ConstantFP>(C1)->getValueAPF(); 1848 APFloat C2V = cast<ConstantFP>(C2)->getValueAPF(); 1849 APFloat::cmpResult R = C1V.compare(C2V); 1850 switch (pred) { 1851 default: llvm_unreachable("Invalid FCmp Predicate"); return 0; 1852 case FCmpInst::FCMP_FALSE: return Constant::getNullValue(ResultTy); 1853 case FCmpInst::FCMP_TRUE: return Constant::getAllOnesValue(ResultTy); 1854 case FCmpInst::FCMP_UNO: 1855 return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered); 1856 case FCmpInst::FCMP_ORD: 1857 return ConstantInt::get(ResultTy, R!=APFloat::cmpUnordered); 1858 case FCmpInst::FCMP_UEQ: 1859 return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || 1860 R==APFloat::cmpEqual); 1861 case FCmpInst::FCMP_OEQ: 1862 return ConstantInt::get(ResultTy, R==APFloat::cmpEqual); 1863 case FCmpInst::FCMP_UNE: 1864 return ConstantInt::get(ResultTy, R!=APFloat::cmpEqual); 1865 case FCmpInst::FCMP_ONE: 1866 return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan || 1867 R==APFloat::cmpGreaterThan); 1868 case FCmpInst::FCMP_ULT: 1869 return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || 1870 R==APFloat::cmpLessThan); 1871 case FCmpInst::FCMP_OLT: 1872 return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan); 1873 case FCmpInst::FCMP_UGT: 1874 return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered || 1875 R==APFloat::cmpGreaterThan); 1876 case FCmpInst::FCMP_OGT: 1877 return ConstantInt::get(ResultTy, R==APFloat::cmpGreaterThan); 1878 case FCmpInst::FCMP_ULE: 1879 return ConstantInt::get(ResultTy, R!=APFloat::cmpGreaterThan); 1880 case FCmpInst::FCMP_OLE: 1881 return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan || 1882 R==APFloat::cmpEqual); 1883 case FCmpInst::FCMP_UGE: 1884 return ConstantInt::get(ResultTy, R!=APFloat::cmpLessThan); 1885 case FCmpInst::FCMP_OGE: 1886 return ConstantInt::get(ResultTy, R==APFloat::cmpGreaterThan || 1887 R==APFloat::cmpEqual); 1888 } 1889 } else if (C1->getType()->isVectorTy()) { 1890 SmallVector<Constant*, 16> C1Elts, C2Elts; 1891 C1->getVectorElements(C1Elts); 1892 C2->getVectorElements(C2Elts); 1893 if (C1Elts.empty() || C2Elts.empty()) 1894 return 0; 1895 1896 // If we can constant fold the comparison of each element, constant fold 1897 // the whole vector comparison. 1898 SmallVector<Constant*, 4> ResElts; 1899 for (unsigned i = 0, e = C1Elts.size(); i != e; ++i) { 1900 // Compare the elements, producing an i1 result or constant expr. 1901 ResElts.push_back(ConstantExpr::getCompare(pred, C1Elts[i], C2Elts[i])); 1902 } 1903 return ConstantVector::get(&ResElts[0], ResElts.size()); 1904 } 1905 1906 if (C1->getType()->isFloatingPointTy()) { 1907 int Result = -1; // -1 = unknown, 0 = known false, 1 = known true. 1908 switch (evaluateFCmpRelation(C1, C2)) { 1909 default: llvm_unreachable("Unknown relation!"); 1910 case FCmpInst::FCMP_UNO: 1911 case FCmpInst::FCMP_ORD: 1912 case FCmpInst::FCMP_UEQ: 1913 case FCmpInst::FCMP_UNE: 1914 case FCmpInst::FCMP_ULT: 1915 case FCmpInst::FCMP_UGT: 1916 case FCmpInst::FCMP_ULE: 1917 case FCmpInst::FCMP_UGE: 1918 case FCmpInst::FCMP_TRUE: 1919 case FCmpInst::FCMP_FALSE: 1920 case FCmpInst::BAD_FCMP_PREDICATE: 1921 break; // Couldn't determine anything about these constants. 1922 case FCmpInst::FCMP_OEQ: // We know that C1 == C2 1923 Result = (pred == FCmpInst::FCMP_UEQ || pred == FCmpInst::FCMP_OEQ || 1924 pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE || 1925 pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE); 1926 break; 1927 case FCmpInst::FCMP_OLT: // We know that C1 < C2 1928 Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE || 1929 pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT || 1930 pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE); 1931 break; 1932 case FCmpInst::FCMP_OGT: // We know that C1 > C2 1933 Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE || 1934 pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT || 1935 pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE); 1936 break; 1937 case FCmpInst::FCMP_OLE: // We know that C1 <= C2 1938 // We can only partially decide this relation. 1939 if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT) 1940 Result = 0; 1941 else if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT) 1942 Result = 1; 1943 break; 1944 case FCmpInst::FCMP_OGE: // We known that C1 >= C2 1945 // We can only partially decide this relation. 1946 if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT) 1947 Result = 0; 1948 else if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT) 1949 Result = 1; 1950 break; 1951 case ICmpInst::ICMP_NE: // We know that C1 != C2 1952 // We can only partially decide this relation. 1953 if (pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_UEQ) 1954 Result = 0; 1955 else if (pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_UNE) 1956 Result = 1; 1957 break; 1958 } 1959 1960 // If we evaluated the result, return it now. 1961 if (Result != -1) 1962 return ConstantInt::get(ResultTy, Result); 1963 1964 } else { 1965 // Evaluate the relation between the two constants, per the predicate. 1966 int Result = -1; // -1 = unknown, 0 = known false, 1 = known true. 1967 switch (evaluateICmpRelation(C1, C2, CmpInst::isSigned(pred))) { 1968 default: llvm_unreachable("Unknown relational!"); 1969 case ICmpInst::BAD_ICMP_PREDICATE: 1970 break; // Couldn't determine anything about these constants. 1971 case ICmpInst::ICMP_EQ: // We know the constants are equal! 1972 // If we know the constants are equal, we can decide the result of this 1973 // computation precisely. 1974 Result = ICmpInst::isTrueWhenEqual((ICmpInst::Predicate)pred); 1975 break; 1976 case ICmpInst::ICMP_ULT: 1977 switch (pred) { 1978 case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_ULE: 1979 Result = 1; break; 1980 case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_UGE: 1981 Result = 0; break; 1982 } 1983 break; 1984 case ICmpInst::ICMP_SLT: 1985 switch (pred) { 1986 case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SLE: 1987 Result = 1; break; 1988 case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SGE: 1989 Result = 0; break; 1990 } 1991 break; 1992 case ICmpInst::ICMP_UGT: 1993 switch (pred) { 1994 case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_UGE: 1995 Result = 1; break; 1996 case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_ULE: 1997 Result = 0; break; 1998 } 1999 break; 2000 case ICmpInst::ICMP_SGT: 2001 switch (pred) { 2002 case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SGE: 2003 Result = 1; break; 2004 case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SLE: 2005 Result = 0; break; 2006 } 2007 break; 2008 case ICmpInst::ICMP_ULE: 2009 if (pred == ICmpInst::ICMP_UGT) Result = 0; 2010 if (pred == ICmpInst::ICMP_ULT || pred == ICmpInst::ICMP_ULE) Result = 1; 2011 break; 2012 case ICmpInst::ICMP_SLE: 2013 if (pred == ICmpInst::ICMP_SGT) Result = 0; 2014 if (pred == ICmpInst::ICMP_SLT || pred == ICmpInst::ICMP_SLE) Result = 1; 2015 break; 2016 case ICmpInst::ICMP_UGE: 2017 if (pred == ICmpInst::ICMP_ULT) Result = 0; 2018 if (pred == ICmpInst::ICMP_UGT || pred == ICmpInst::ICMP_UGE) Result = 1; 2019 break; 2020 case ICmpInst::ICMP_SGE: 2021 if (pred == ICmpInst::ICMP_SLT) Result = 0; 2022 if (pred == ICmpInst::ICMP_SGT || pred == ICmpInst::ICMP_SGE) Result = 1; 2023 break; 2024 case ICmpInst::ICMP_NE: 2025 if (pred == ICmpInst::ICMP_EQ) Result = 0; 2026 if (pred == ICmpInst::ICMP_NE) Result = 1; 2027 break; 2028 } 2029 2030 // If we evaluated the result, return it now. 2031 if (Result != -1) 2032 return ConstantInt::get(ResultTy, Result); 2033 2034 // If the right hand side is a bitcast, try using its inverse to simplify 2035 // it by moving it to the left hand side. We can't do this if it would turn 2036 // a vector compare into a scalar compare or visa versa. 2037 if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(C2)) { 2038 Constant *CE2Op0 = CE2->getOperand(0); 2039 if (CE2->getOpcode() == Instruction::BitCast && 2040 CE2->getType()->isVectorTy() == CE2Op0->getType()->isVectorTy()) { 2041 Constant *Inverse = ConstantExpr::getBitCast(C1, CE2Op0->getType()); 2042 return ConstantExpr::getICmp(pred, Inverse, CE2Op0); 2043 } 2044 } 2045 2046 // If the left hand side is an extension, try eliminating it. 2047 if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) { 2048 if ((CE1->getOpcode() == Instruction::SExt && ICmpInst::isSigned(pred)) || 2049 (CE1->getOpcode() == Instruction::ZExt && !ICmpInst::isSigned(pred))){ 2050 Constant *CE1Op0 = CE1->getOperand(0); 2051 Constant *CE1Inverse = ConstantExpr::getTrunc(CE1, CE1Op0->getType()); 2052 if (CE1Inverse == CE1Op0) { 2053 // Check whether we can safely truncate the right hand side. 2054 Constant *C2Inverse = ConstantExpr::getTrunc(C2, CE1Op0->getType()); 2055 if (ConstantExpr::getZExt(C2Inverse, C2->getType()) == C2) { 2056 return ConstantExpr::getICmp(pred, CE1Inverse, C2Inverse); 2057 } 2058 } 2059 } 2060 } 2061 2062 if ((!isa<ConstantExpr>(C1) && isa<ConstantExpr>(C2)) || 2063 (C1->isNullValue() && !C2->isNullValue())) { 2064 // If C2 is a constant expr and C1 isn't, flip them around and fold the 2065 // other way if possible. 2066 // Also, if C1 is null and C2 isn't, flip them around. 2067 pred = ICmpInst::getSwappedPredicate((ICmpInst::Predicate)pred); 2068 return ConstantExpr::getICmp(pred, C2, C1); 2069 } 2070 } 2071 return 0; 2072} 2073 2074/// isInBoundsIndices - Test whether the given sequence of *normalized* indices 2075/// is "inbounds". 2076static bool isInBoundsIndices(Constant *const *Idxs, size_t NumIdx) { 2077 // No indices means nothing that could be out of bounds. 2078 if (NumIdx == 0) return true; 2079 2080 // If the first index is zero, it's in bounds. 2081 if (Idxs[0]->isNullValue()) return true; 2082 2083 // If the first index is one and all the rest are zero, it's in bounds, 2084 // by the one-past-the-end rule. 2085 if (!cast<ConstantInt>(Idxs[0])->isOne()) 2086 return false; 2087 for (unsigned i = 1, e = NumIdx; i != e; ++i) 2088 if (!Idxs[i]->isNullValue()) 2089 return false; 2090 return true; 2091} 2092 2093Constant *llvm::ConstantFoldGetElementPtr(Constant *C, 2094 bool inBounds, 2095 Constant* const *Idxs, 2096 unsigned NumIdx) { 2097 if (NumIdx == 0 || 2098 (NumIdx == 1 && Idxs[0]->isNullValue())) 2099 return C; 2100 2101 if (isa<UndefValue>(C)) { 2102 const PointerType *Ptr = cast<PointerType>(C->getType()); 2103 const Type *Ty = GetElementPtrInst::getIndexedType(Ptr, 2104 (Value **)Idxs, 2105 (Value **)Idxs+NumIdx); 2106 assert(Ty != 0 && "Invalid indices for GEP!"); 2107 return UndefValue::get(PointerType::get(Ty, Ptr->getAddressSpace())); 2108 } 2109 2110 Constant *Idx0 = Idxs[0]; 2111 if (C->isNullValue()) { 2112 bool isNull = true; 2113 for (unsigned i = 0, e = NumIdx; i != e; ++i) 2114 if (!Idxs[i]->isNullValue()) { 2115 isNull = false; 2116 break; 2117 } 2118 if (isNull) { 2119 const PointerType *Ptr = cast<PointerType>(C->getType()); 2120 const Type *Ty = GetElementPtrInst::getIndexedType(Ptr, 2121 (Value**)Idxs, 2122 (Value**)Idxs+NumIdx); 2123 assert(Ty != 0 && "Invalid indices for GEP!"); 2124 return ConstantPointerNull::get( 2125 PointerType::get(Ty,Ptr->getAddressSpace())); 2126 } 2127 } 2128 2129 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 2130 // Combine Indices - If the source pointer to this getelementptr instruction 2131 // is a getelementptr instruction, combine the indices of the two 2132 // getelementptr instructions into a single instruction. 2133 // 2134 if (CE->getOpcode() == Instruction::GetElementPtr) { 2135 const Type *LastTy = 0; 2136 for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE); 2137 I != E; ++I) 2138 LastTy = *I; 2139 2140 if ((LastTy && LastTy->isArrayTy()) || Idx0->isNullValue()) { 2141 SmallVector<Value*, 16> NewIndices; 2142 NewIndices.reserve(NumIdx + CE->getNumOperands()); 2143 for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i) 2144 NewIndices.push_back(CE->getOperand(i)); 2145 2146 // Add the last index of the source with the first index of the new GEP. 2147 // Make sure to handle the case when they are actually different types. 2148 Constant *Combined = CE->getOperand(CE->getNumOperands()-1); 2149 // Otherwise it must be an array. 2150 if (!Idx0->isNullValue()) { 2151 const Type *IdxTy = Combined->getType(); 2152 if (IdxTy != Idx0->getType()) { 2153 const Type *Int64Ty = Type::getInt64Ty(IdxTy->getContext()); 2154 Constant *C1 = ConstantExpr::getSExtOrBitCast(Idx0, Int64Ty); 2155 Constant *C2 = ConstantExpr::getSExtOrBitCast(Combined, Int64Ty); 2156 Combined = ConstantExpr::get(Instruction::Add, C1, C2); 2157 } else { 2158 Combined = 2159 ConstantExpr::get(Instruction::Add, Idx0, Combined); 2160 } 2161 } 2162 2163 NewIndices.push_back(Combined); 2164 NewIndices.append(Idxs+1, Idxs+NumIdx); 2165 return (inBounds && cast<GEPOperator>(CE)->isInBounds()) ? 2166 ConstantExpr::getInBoundsGetElementPtr(CE->getOperand(0), 2167 &NewIndices[0], 2168 NewIndices.size()) : 2169 ConstantExpr::getGetElementPtr(CE->getOperand(0), 2170 &NewIndices[0], 2171 NewIndices.size()); 2172 } 2173 } 2174 2175 // Implement folding of: 2176 // int* getelementptr ([2 x int]* bitcast ([3 x int]* %X to [2 x int]*), 2177 // long 0, long 0) 2178 // To: int* getelementptr ([3 x int]* %X, long 0, long 0) 2179 // 2180 if (CE->isCast() && NumIdx > 1 && Idx0->isNullValue()) { 2181 if (const PointerType *SPT = 2182 dyn_cast<PointerType>(CE->getOperand(0)->getType())) 2183 if (const ArrayType *SAT = dyn_cast<ArrayType>(SPT->getElementType())) 2184 if (const ArrayType *CAT = 2185 dyn_cast<ArrayType>(cast<PointerType>(C->getType())->getElementType())) 2186 if (CAT->getElementType() == SAT->getElementType()) 2187 return inBounds ? 2188 ConstantExpr::getInBoundsGetElementPtr( 2189 (Constant*)CE->getOperand(0), Idxs, NumIdx) : 2190 ConstantExpr::getGetElementPtr( 2191 (Constant*)CE->getOperand(0), Idxs, NumIdx); 2192 } 2193 } 2194 2195 // Check to see if any array indices are not within the corresponding 2196 // notional array bounds. If so, try to determine if they can be factored 2197 // out into preceding dimensions. 2198 bool Unknown = false; 2199 SmallVector<Constant *, 8> NewIdxs; 2200 const Type *Ty = C->getType(); 2201 const Type *Prev = 0; 2202 for (unsigned i = 0; i != NumIdx; 2203 Prev = Ty, Ty = cast<CompositeType>(Ty)->getTypeAtIndex(Idxs[i]), ++i) { 2204 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idxs[i])) { 2205 if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) 2206 if (ATy->getNumElements() <= INT64_MAX && 2207 ATy->getNumElements() != 0 && 2208 CI->getSExtValue() >= (int64_t)ATy->getNumElements()) { 2209 if (isa<SequentialType>(Prev)) { 2210 // It's out of range, but we can factor it into the prior 2211 // dimension. 2212 NewIdxs.resize(NumIdx); 2213 ConstantInt *Factor = ConstantInt::get(CI->getType(), 2214 ATy->getNumElements()); 2215 NewIdxs[i] = ConstantExpr::getSRem(CI, Factor); 2216 2217 Constant *PrevIdx = Idxs[i-1]; 2218 Constant *Div = ConstantExpr::getSDiv(CI, Factor); 2219 2220 // Before adding, extend both operands to i64 to avoid 2221 // overflow trouble. 2222 if (!PrevIdx->getType()->isIntegerTy(64)) 2223 PrevIdx = ConstantExpr::getSExt(PrevIdx, 2224 Type::getInt64Ty(Div->getContext())); 2225 if (!Div->getType()->isIntegerTy(64)) 2226 Div = ConstantExpr::getSExt(Div, 2227 Type::getInt64Ty(Div->getContext())); 2228 2229 NewIdxs[i-1] = ConstantExpr::getAdd(PrevIdx, Div); 2230 } else { 2231 // It's out of range, but the prior dimension is a struct 2232 // so we can't do anything about it. 2233 Unknown = true; 2234 } 2235 } 2236 } else { 2237 // We don't know if it's in range or not. 2238 Unknown = true; 2239 } 2240 } 2241 2242 // If we did any factoring, start over with the adjusted indices. 2243 if (!NewIdxs.empty()) { 2244 for (unsigned i = 0; i != NumIdx; ++i) 2245 if (!NewIdxs[i]) NewIdxs[i] = Idxs[i]; 2246 return inBounds ? 2247 ConstantExpr::getInBoundsGetElementPtr(C, NewIdxs.data(), 2248 NewIdxs.size()) : 2249 ConstantExpr::getGetElementPtr(C, NewIdxs.data(), NewIdxs.size()); 2250 } 2251 2252 // If all indices are known integers and normalized, we can do a simple 2253 // check for the "inbounds" property. 2254 if (!Unknown && !inBounds && 2255 isa<GlobalVariable>(C) && isInBoundsIndices(Idxs, NumIdx)) 2256 return ConstantExpr::getInBoundsGetElementPtr(C, Idxs, NumIdx); 2257 2258 return 0; 2259} 2260