LLVM API Documentation
00001 //===- ExprTypeConvert.cpp - Code to change an LLVM Expr Type -------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the part of level raising that checks to see if it is 00011 // possible to coerce an entire expression tree into a different type. If 00012 // convertible, other routines from this file will do the conversion. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "TransformInternals.h" 00017 #include "llvm/Constants.h" 00018 #include "llvm/Instructions.h" 00019 #include "llvm/ADT/STLExtras.h" 00020 #include "llvm/Support/Debug.h" 00021 #include <algorithm> 00022 #include <iostream> 00023 using namespace llvm; 00024 00025 static bool OperandConvertibleToType(User *U, Value *V, const Type *Ty, 00026 ValueTypeCache &ConvertedTypes, 00027 const TargetData &TD); 00028 00029 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal, 00030 ValueMapCache &VMC, const TargetData &TD); 00031 00032 00033 // ExpressionConvertibleToType - Return true if it is possible 00034 bool llvm::ExpressionConvertibleToType(Value *V, const Type *Ty, 00035 ValueTypeCache &CTMap, const TargetData &TD) { 00036 // Expression type must be holdable in a register. 00037 if (!Ty->isFirstClassType()) 00038 return false; 00039 00040 ValueTypeCache::iterator CTMI = CTMap.find(V); 00041 if (CTMI != CTMap.end()) return CTMI->second == Ty; 00042 00043 // If it's a constant... all constants can be converted to a different 00044 // type. 00045 // 00046 if (isa<Constant>(V) && !isa<GlobalValue>(V)) 00047 return true; 00048 00049 CTMap[V] = Ty; 00050 if (V->getType() == Ty) return true; // Expression already correct type! 00051 00052 Instruction *I = dyn_cast<Instruction>(V); 00053 if (I == 0) return false; // Otherwise, we can't convert! 00054 00055 switch (I->getOpcode()) { 00056 case Instruction::Cast: 00057 // We can convert the expr if the cast destination type is losslessly 00058 // convertible to the requested type. 00059 if (!Ty->isLosslesslyConvertibleTo(I->getType())) return false; 00060 00061 // We also do not allow conversion of a cast that casts from a ptr to array 00062 // of X to a *X. For example: cast [4 x %List *] * %val to %List * * 00063 // 00064 if (const PointerType *SPT = 00065 dyn_cast<PointerType>(I->getOperand(0)->getType())) 00066 if (const PointerType *DPT = dyn_cast<PointerType>(I->getType())) 00067 if (const ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType())) 00068 if (AT->getElementType() == DPT->getElementType()) 00069 return false; 00070 break; 00071 00072 case Instruction::Add: 00073 case Instruction::Sub: 00074 if (!Ty->isInteger() && !Ty->isFloatingPoint()) return false; 00075 if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD) || 00076 !ExpressionConvertibleToType(I->getOperand(1), Ty, CTMap, TD)) 00077 return false; 00078 break; 00079 case Instruction::Shr: 00080 if (!Ty->isInteger()) return false; 00081 if (Ty->isSigned() != V->getType()->isSigned()) return false; 00082 // FALL THROUGH 00083 case Instruction::Shl: 00084 if (!Ty->isInteger()) return false; 00085 if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD)) 00086 return false; 00087 break; 00088 00089 case Instruction::Load: { 00090 LoadInst *LI = cast<LoadInst>(I); 00091 if (!ExpressionConvertibleToType(LI->getPointerOperand(), 00092 PointerType::get(Ty), CTMap, TD)) 00093 return false; 00094 break; 00095 } 00096 case Instruction::PHI: { 00097 PHINode *PN = cast<PHINode>(I); 00098 // Be conservative if we find a giant PHI node. 00099 if (PN->getNumIncomingValues() > 32) return false; 00100 00101 for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) 00102 if (!ExpressionConvertibleToType(PN->getIncomingValue(i), Ty, CTMap, TD)) 00103 return false; 00104 break; 00105 } 00106 00107 case Instruction::GetElementPtr: { 00108 // GetElementPtr's are directly convertible to a pointer type if they have 00109 // a number of zeros at the end. Because removing these values does not 00110 // change the logical offset of the GEP, it is okay and fair to remove them. 00111 // This can change this: 00112 // %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0 ; <%List **> 00113 // %t2 = cast %List * * %t1 to %List * 00114 // into 00115 // %t2 = getelementptr %Hosp * %hosp, ubyte 4 ; <%List *> 00116 // 00117 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I); 00118 const PointerType *PTy = dyn_cast<PointerType>(Ty); 00119 if (!PTy) return false; // GEP must always return a pointer... 00120 const Type *PVTy = PTy->getElementType(); 00121 00122 // Check to see if there are zero elements that we can remove from the 00123 // index array. If there are, check to see if removing them causes us to 00124 // get to the right type... 00125 // 00126 std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end()); 00127 const Type *BaseType = GEP->getPointerOperand()->getType(); 00128 const Type *ElTy = 0; 00129 00130 while (!Indices.empty() && 00131 Indices.back() == Constant::getNullValue(Indices.back()->getType())){ 00132 Indices.pop_back(); 00133 ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices, true); 00134 if (ElTy == PVTy) 00135 break; // Found a match!! 00136 ElTy = 0; 00137 } 00138 00139 if (ElTy) break; // Found a number of zeros we can strip off! 00140 00141 // Otherwise, it could be that we have something like this: 00142 // getelementptr [[sbyte] *] * %reg115, long %reg138 ; [sbyte]** 00143 // and want to convert it into something like this: 00144 // getelemenptr [[int] *] * %reg115, long %reg138 ; [int]** 00145 // 00146 if (GEP->getNumOperands() == 2 && 00147 PTy->getElementType()->isSized() && 00148 TD.getTypeSize(PTy->getElementType()) == 00149 TD.getTypeSize(GEP->getType()->getElementType())) { 00150 const PointerType *NewSrcTy = PointerType::get(PVTy); 00151 if (!ExpressionConvertibleToType(I->getOperand(0), NewSrcTy, CTMap, TD)) 00152 return false; 00153 break; 00154 } 00155 00156 return false; // No match, maybe next time. 00157 } 00158 00159 case Instruction::Call: { 00160 if (isa<Function>(I->getOperand(0))) 00161 return false; // Don't even try to change direct calls. 00162 00163 // If this is a function pointer, we can convert the return type if we can 00164 // convert the source function pointer. 00165 // 00166 const PointerType *PT = cast<PointerType>(I->getOperand(0)->getType()); 00167 const FunctionType *FT = cast<FunctionType>(PT->getElementType()); 00168 std::vector<const Type *> ArgTys(FT->param_begin(), FT->param_end()); 00169 const FunctionType *NewTy = 00170 FunctionType::get(Ty, ArgTys, FT->isVarArg()); 00171 if (!ExpressionConvertibleToType(I->getOperand(0), 00172 PointerType::get(NewTy), CTMap, TD)) 00173 return false; 00174 break; 00175 } 00176 default: 00177 return false; 00178 } 00179 00180 // Expressions are only convertible if all of the users of the expression can 00181 // have this value converted. This makes use of the map to avoid infinite 00182 // recursion. 00183 // 00184 for (Value::use_iterator It = I->use_begin(), E = I->use_end(); It != E; ++It) 00185 if (!OperandConvertibleToType(*It, I, Ty, CTMap, TD)) 00186 return false; 00187 00188 return true; 00189 } 00190 00191 00192 Value *llvm::ConvertExpressionToType(Value *V, const Type *Ty, 00193 ValueMapCache &VMC, const TargetData &TD) { 00194 if (V->getType() == Ty) return V; // Already where we need to be? 00195 00196 ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V); 00197 if (VMCI != VMC.ExprMap.end()) { 00198 assert(VMCI->second->getType() == Ty); 00199 00200 if (Instruction *I = dyn_cast<Instruction>(V)) 00201 ValueHandle IHandle(VMC, I); // Remove I if it is unused now! 00202 00203 return VMCI->second; 00204 } 00205 00206 DEBUG(std::cerr << "CETT: " << (void*)V << " " << *V); 00207 00208 Instruction *I = dyn_cast<Instruction>(V); 00209 if (I == 0) { 00210 Constant *CPV = cast<Constant>(V); 00211 // Constants are converted by constant folding the cast that is required. 00212 // We assume here that all casts are implemented for constant prop. 00213 Value *Result = ConstantExpr::getCast(CPV, Ty); 00214 // Add the instruction to the expression map 00215 //VMC.ExprMap[V] = Result; 00216 return Result; 00217 } 00218 00219 00220 BasicBlock *BB = I->getParent(); 00221 std::string Name = I->getName(); if (!Name.empty()) I->setName(""); 00222 Instruction *Res; // Result of conversion 00223 00224 ValueHandle IHandle(VMC, I); // Prevent I from being removed! 00225 00226 Constant *Dummy = Constant::getNullValue(Ty); 00227 00228 switch (I->getOpcode()) { 00229 case Instruction::Cast: 00230 assert(VMC.NewCasts.count(ValueHandle(VMC, I)) == 0); 00231 Res = new CastInst(I->getOperand(0), Ty, Name); 00232 VMC.NewCasts.insert(ValueHandle(VMC, Res)); 00233 break; 00234 00235 case Instruction::Add: 00236 case Instruction::Sub: 00237 Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(), 00238 Dummy, Dummy, Name); 00239 VMC.ExprMap[I] = Res; // Add node to expression eagerly 00240 00241 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC, TD)); 00242 Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC, TD)); 00243 break; 00244 00245 case Instruction::Shl: 00246 case Instruction::Shr: 00247 Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy, 00248 I->getOperand(1), Name); 00249 VMC.ExprMap[I] = Res; 00250 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC, TD)); 00251 break; 00252 00253 case Instruction::Load: { 00254 LoadInst *LI = cast<LoadInst>(I); 00255 00256 Res = new LoadInst(Constant::getNullValue(PointerType::get(Ty)), Name); 00257 VMC.ExprMap[I] = Res; 00258 Res->setOperand(0, ConvertExpressionToType(LI->getPointerOperand(), 00259 PointerType::get(Ty), VMC, TD)); 00260 assert(Res->getOperand(0)->getType() == PointerType::get(Ty)); 00261 assert(Ty == Res->getType()); 00262 assert(Res->getType()->isFirstClassType() && "Load of structure or array!"); 00263 break; 00264 } 00265 00266 case Instruction::PHI: { 00267 PHINode *OldPN = cast<PHINode>(I); 00268 PHINode *NewPN = new PHINode(Ty, Name); 00269 00270 VMC.ExprMap[I] = NewPN; // Add node to expression eagerly 00271 while (OldPN->getNumOperands()) { 00272 BasicBlock *BB = OldPN->getIncomingBlock(0); 00273 Value *OldVal = OldPN->getIncomingValue(0); 00274 ValueHandle OldValHandle(VMC, OldVal); 00275 OldPN->removeIncomingValue(BB, false); 00276 Value *V = ConvertExpressionToType(OldVal, Ty, VMC, TD); 00277 NewPN->addIncoming(V, BB); 00278 } 00279 Res = NewPN; 00280 break; 00281 } 00282 00283 case Instruction::GetElementPtr: { 00284 // GetElementPtr's are directly convertible to a pointer type if they have 00285 // a number of zeros at the end. Because removing these values does not 00286 // change the logical offset of the GEP, it is okay and fair to remove them. 00287 // This can change this: 00288 // %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0 ; <%List **> 00289 // %t2 = cast %List * * %t1 to %List * 00290 // into 00291 // %t2 = getelementptr %Hosp * %hosp, ubyte 4 ; <%List *> 00292 // 00293 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I); 00294 00295 // Check to see if there are zero elements that we can remove from the 00296 // index array. If there are, check to see if removing them causes us to 00297 // get to the right type... 00298 // 00299 std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end()); 00300 const Type *BaseType = GEP->getPointerOperand()->getType(); 00301 const Type *PVTy = cast<PointerType>(Ty)->getElementType(); 00302 Res = 0; 00303 while (!Indices.empty() && 00304 Indices.back() == Constant::getNullValue(Indices.back()->getType())){ 00305 Indices.pop_back(); 00306 if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) { 00307 if (Indices.size() == 0) 00308 Res = new CastInst(GEP->getPointerOperand(), BaseType); // NOOP CAST 00309 else 00310 Res = new GetElementPtrInst(GEP->getPointerOperand(), Indices, Name); 00311 break; 00312 } 00313 } 00314 00315 // Otherwise, it could be that we have something like this: 00316 // getelementptr [[sbyte] *] * %reg115, uint %reg138 ; [sbyte]** 00317 // and want to convert it into something like this: 00318 // getelemenptr [[int] *] * %reg115, uint %reg138 ; [int]** 00319 // 00320 if (Res == 0) { 00321 const PointerType *NewSrcTy = PointerType::get(PVTy); 00322 std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end()); 00323 Res = new GetElementPtrInst(Constant::getNullValue(NewSrcTy), 00324 Indices, Name); 00325 VMC.ExprMap[I] = Res; 00326 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), 00327 NewSrcTy, VMC, TD)); 00328 } 00329 00330 00331 assert(Res && "Didn't find match!"); 00332 break; 00333 } 00334 00335 case Instruction::Call: { 00336 assert(!isa<Function>(I->getOperand(0))); 00337 00338 // If this is a function pointer, we can convert the return type if we can 00339 // convert the source function pointer. 00340 // 00341 const PointerType *PT = cast<PointerType>(I->getOperand(0)->getType()); 00342 const FunctionType *FT = cast<FunctionType>(PT->getElementType()); 00343 std::vector<const Type *> ArgTys(FT->param_begin(), FT->param_end()); 00344 const FunctionType *NewTy = 00345 FunctionType::get(Ty, ArgTys, FT->isVarArg()); 00346 const PointerType *NewPTy = PointerType::get(NewTy); 00347 if (Ty == Type::VoidTy) 00348 Name = ""; // Make sure not to name calls that now return void! 00349 00350 Res = new CallInst(Constant::getNullValue(NewPTy), 00351 std::vector<Value*>(I->op_begin()+1, I->op_end()), 00352 Name); 00353 if (cast<CallInst>(I)->isTailCall()) 00354 cast<CallInst>(Res)->setTailCall(); 00355 cast<CallInst>(Res)->setCallingConv(cast<CallInst>(I)->getCallingConv()); 00356 VMC.ExprMap[I] = Res; 00357 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),NewPTy,VMC,TD)); 00358 break; 00359 } 00360 default: 00361 assert(0 && "Expression convertible, but don't know how to convert?"); 00362 return 0; 00363 } 00364 00365 assert(Res->getType() == Ty && "Didn't convert expr to correct type!"); 00366 00367 BB->getInstList().insert(I, Res); 00368 00369 // Add the instruction to the expression map 00370 VMC.ExprMap[I] = Res; 00371 00372 00373 //// WTF is this code! FIXME: remove this. 00374 unsigned NumUses = I->getNumUses(); 00375 for (unsigned It = 0; It < NumUses; ) { 00376 unsigned OldSize = NumUses; 00377 Value::use_iterator UI = I->use_begin(); 00378 std::advance(UI, It); 00379 ConvertOperandToType(*UI, I, Res, VMC, TD); 00380 NumUses = I->getNumUses(); 00381 if (NumUses == OldSize) ++It; 00382 } 00383 00384 DEBUG(std::cerr << "ExpIn: " << (void*)I << " " << *I 00385 << "ExpOut: " << (void*)Res << " " << *Res); 00386 00387 return Res; 00388 } 00389 00390 00391 00392 // ValueConvertibleToType - Return true if it is possible 00393 bool llvm::ValueConvertibleToType(Value *V, const Type *Ty, 00394 ValueTypeCache &ConvertedTypes, 00395 const TargetData &TD) { 00396 ValueTypeCache::iterator I = ConvertedTypes.find(V); 00397 if (I != ConvertedTypes.end()) return I->second == Ty; 00398 ConvertedTypes[V] = Ty; 00399 00400 // It is safe to convert the specified value to the specified type IFF all of 00401 // the uses of the value can be converted to accept the new typed value. 00402 // 00403 if (V->getType() != Ty) { 00404 for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) 00405 if (!OperandConvertibleToType(*I, V, Ty, ConvertedTypes, TD)) 00406 return false; 00407 } 00408 00409 return true; 00410 } 00411 00412 00413 00414 00415 00416 // OperandConvertibleToType - Return true if it is possible to convert operand 00417 // V of User (instruction) U to the specified type. This is true iff it is 00418 // possible to change the specified instruction to accept this. CTMap is a map 00419 // of converted types, so that circular definitions will see the future type of 00420 // the expression, not the static current type. 00421 // 00422 static bool OperandConvertibleToType(User *U, Value *V, const Type *Ty, 00423 ValueTypeCache &CTMap, 00424 const TargetData &TD) { 00425 // if (V->getType() == Ty) return true; // Operand already the right type? 00426 00427 // Expression type must be holdable in a register. 00428 if (!Ty->isFirstClassType()) 00429 return false; 00430 00431 Instruction *I = dyn_cast<Instruction>(U); 00432 if (I == 0) return false; // We can't convert! 00433 00434 switch (I->getOpcode()) { 00435 case Instruction::Cast: 00436 assert(I->getOperand(0) == V); 00437 // We can convert the expr if the cast destination type is losslessly 00438 // convertible to the requested type. 00439 // Also, do not change a cast that is a noop cast. For all intents and 00440 // purposes it should be eliminated. 00441 if (!Ty->isLosslesslyConvertibleTo(I->getOperand(0)->getType()) || 00442 I->getType() == I->getOperand(0)->getType()) 00443 return false; 00444 00445 // Do not allow a 'cast ushort %V to uint' to have it's first operand be 00446 // converted to a 'short' type. Doing so changes the way sign promotion 00447 // happens, and breaks things. Only allow the cast to take place if the 00448 // signedness doesn't change... or if the current cast is not a lossy 00449 // conversion. 00450 // 00451 if (!I->getType()->isLosslesslyConvertibleTo(I->getOperand(0)->getType()) && 00452 I->getOperand(0)->getType()->isSigned() != Ty->isSigned()) 00453 return false; 00454 00455 // We also do not allow conversion of a cast that casts from a ptr to array 00456 // of X to a *X. For example: cast [4 x %List *] * %val to %List * * 00457 // 00458 if (const PointerType *SPT = 00459 dyn_cast<PointerType>(I->getOperand(0)->getType())) 00460 if (const PointerType *DPT = dyn_cast<PointerType>(I->getType())) 00461 if (const ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType())) 00462 if (AT->getElementType() == DPT->getElementType()) 00463 return false; 00464 return true; 00465 00466 case Instruction::Add: 00467 case Instruction::Sub: { 00468 if (!Ty->isInteger() && !Ty->isFloatingPoint()) return false; 00469 00470 Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0); 00471 return ValueConvertibleToType(I, Ty, CTMap, TD) && 00472 ExpressionConvertibleToType(OtherOp, Ty, CTMap, TD); 00473 } 00474 case Instruction::SetEQ: 00475 case Instruction::SetNE: { 00476 Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0); 00477 return ExpressionConvertibleToType(OtherOp, Ty, CTMap, TD); 00478 } 00479 case Instruction::Shr: 00480 if (Ty->isSigned() != V->getType()->isSigned()) return false; 00481 // FALL THROUGH 00482 case Instruction::Shl: 00483 if (I->getOperand(1) == V) return false; // Cannot change shift amount type 00484 if (!Ty->isInteger()) return false; 00485 return ValueConvertibleToType(I, Ty, CTMap, TD); 00486 00487 case Instruction::Free: 00488 assert(I->getOperand(0) == V); 00489 return isa<PointerType>(Ty); // Free can free any pointer type! 00490 00491 case Instruction::Load: 00492 // Cannot convert the types of any subscripts... 00493 if (I->getOperand(0) != V) return false; 00494 00495 if (const PointerType *PT = dyn_cast<PointerType>(Ty)) { 00496 LoadInst *LI = cast<LoadInst>(I); 00497 00498 const Type *LoadedTy = PT->getElementType(); 00499 00500 // They could be loading the first element of a composite type... 00501 if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) { 00502 unsigned Offset = 0; // No offset, get first leaf. 00503 std::vector<Value*> Indices; // Discarded... 00504 LoadedTy = getStructOffsetType(CT, Offset, Indices, TD, false); 00505 assert(Offset == 0 && "Offset changed from zero???"); 00506 } 00507 00508 if (!LoadedTy->isFirstClassType()) 00509 return false; 00510 00511 if (TD.getTypeSize(LoadedTy) != TD.getTypeSize(LI->getType())) 00512 return false; 00513 00514 return ValueConvertibleToType(LI, LoadedTy, CTMap, TD); 00515 } 00516 return false; 00517 00518 case Instruction::Store: { 00519 if (V == I->getOperand(0)) { 00520 ValueTypeCache::iterator CTMI = CTMap.find(I->getOperand(1)); 00521 if (CTMI != CTMap.end()) { // Operand #1 is in the table already? 00522 // If so, check to see if it's Ty*, or, more importantly, if it is a 00523 // pointer to a structure where the first element is a Ty... this code 00524 // is necessary because we might be trying to change the source and 00525 // destination type of the store (they might be related) and the dest 00526 // pointer type might be a pointer to structure. Below we allow pointer 00527 // to structures where the 0th element is compatible with the value, 00528 // now we have to support the symmetrical part of this. 00529 // 00530 const Type *ElTy = cast<PointerType>(CTMI->second)->getElementType(); 00531 00532 // Already a pointer to what we want? Trivially accept... 00533 if (ElTy == Ty) return true; 00534 00535 // Tricky case now, if the destination is a pointer to structure, 00536 // obviously the source is not allowed to be a structure (cannot copy 00537 // a whole structure at a time), so the level raiser must be trying to 00538 // store into the first field. Check for this and allow it now: 00539 // 00540 if (const StructType *SElTy = dyn_cast<StructType>(ElTy)) { 00541 unsigned Offset = 0; 00542 std::vector<Value*> Indices; 00543 ElTy = getStructOffsetType(ElTy, Offset, Indices, TD, false); 00544 assert(Offset == 0 && "Offset changed!"); 00545 if (ElTy == 0) // Element at offset zero in struct doesn't exist! 00546 return false; // Can only happen for {}* 00547 00548 if (ElTy == Ty) // Looks like the 0th element of structure is 00549 return true; // compatible! Accept now! 00550 00551 // Otherwise we know that we can't work, so just stop trying now. 00552 return false; 00553 } 00554 } 00555 00556 // Can convert the store if we can convert the pointer operand to match 00557 // the new value type... 00558 return ExpressionConvertibleToType(I->getOperand(1), PointerType::get(Ty), 00559 CTMap, TD); 00560 } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) { 00561 const Type *ElTy = PT->getElementType(); 00562 assert(V == I->getOperand(1)); 00563 00564 if (isa<StructType>(ElTy)) { 00565 // We can change the destination pointer if we can store our first 00566 // argument into the first element of the structure... 00567 // 00568 unsigned Offset = 0; 00569 std::vector<Value*> Indices; 00570 ElTy = getStructOffsetType(ElTy, Offset, Indices, TD, false); 00571 assert(Offset == 0 && "Offset changed!"); 00572 if (ElTy == 0) // Element at offset zero in struct doesn't exist! 00573 return false; // Can only happen for {}* 00574 } 00575 00576 // Must move the same amount of data... 00577 if (!ElTy->isSized() || 00578 TD.getTypeSize(ElTy) != TD.getTypeSize(I->getOperand(0)->getType())) 00579 return false; 00580 00581 // Can convert store if the incoming value is convertible and if the 00582 // result will preserve semantics... 00583 const Type *Op0Ty = I->getOperand(0)->getType(); 00584 if (!(Op0Ty->isIntegral() ^ ElTy->isIntegral()) && 00585 !(Op0Ty->isFloatingPoint() ^ ElTy->isFloatingPoint())) 00586 return ExpressionConvertibleToType(I->getOperand(0), ElTy, CTMap, TD); 00587 } 00588 return false; 00589 } 00590 00591 case Instruction::PHI: { 00592 PHINode *PN = cast<PHINode>(I); 00593 // Be conservative if we find a giant PHI node. 00594 if (PN->getNumIncomingValues() > 32) return false; 00595 00596 for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) 00597 if (!ExpressionConvertibleToType(PN->getIncomingValue(i), Ty, CTMap, TD)) 00598 return false; 00599 return ValueConvertibleToType(PN, Ty, CTMap, TD); 00600 } 00601 00602 case Instruction::Call: { 00603 User::op_iterator OI = std::find(I->op_begin(), I->op_end(), V); 00604 assert (OI != I->op_end() && "Not using value!"); 00605 unsigned OpNum = OI - I->op_begin(); 00606 00607 // Are we trying to change the function pointer value to a new type? 00608 if (OpNum == 0) { 00609 const PointerType *PTy = dyn_cast<PointerType>(Ty); 00610 if (PTy == 0) return false; // Can't convert to a non-pointer type... 00611 const FunctionType *FTy = dyn_cast<FunctionType>(PTy->getElementType()); 00612 if (FTy == 0) return false; // Can't convert to a non ptr to function... 00613 00614 // Do not allow converting to a call where all of the operands are ...'s 00615 if (FTy->getNumParams() == 0 && FTy->isVarArg()) 00616 return false; // Do not permit this conversion! 00617 00618 // Perform sanity checks to make sure that new function type has the 00619 // correct number of arguments... 00620 // 00621 unsigned NumArgs = I->getNumOperands()-1; // Don't include function ptr 00622 00623 // Cannot convert to a type that requires more fixed arguments than 00624 // the call provides... 00625 // 00626 if (NumArgs < FTy->getNumParams()) return false; 00627 00628 // Unless this is a vararg function type, we cannot provide more arguments 00629 // than are desired... 00630 // 00631 if (!FTy->isVarArg() && NumArgs > FTy->getNumParams()) 00632 return false; 00633 00634 // Okay, at this point, we know that the call and the function type match 00635 // number of arguments. Now we see if we can convert the arguments 00636 // themselves. Note that we do not require operands to be convertible, 00637 // we can insert casts if they are convertible but not compatible. The 00638 // reason for this is that we prefer to have resolved functions but casted 00639 // arguments if possible. 00640 // 00641 for (unsigned i = 0, NA = FTy->getNumParams(); i < NA; ++i) 00642 if (!FTy->getParamType(i)->isLosslesslyConvertibleTo(I->getOperand(i+1)->getType())) 00643 return false; // Operands must have compatible types! 00644 00645 // Okay, at this point, we know that all of the arguments can be 00646 // converted. We succeed if we can change the return type if 00647 // necessary... 00648 // 00649 return ValueConvertibleToType(I, FTy->getReturnType(), CTMap, TD); 00650 } 00651 00652 const PointerType *MPtr = cast<PointerType>(I->getOperand(0)->getType()); 00653 const FunctionType *FTy = cast<FunctionType>(MPtr->getElementType()); 00654 if (!FTy->isVarArg()) return false; 00655 00656 if ((OpNum-1) < FTy->getNumParams()) 00657 return false; // It's not in the varargs section... 00658 00659 // If we get this far, we know the value is in the varargs section of the 00660 // function! We can convert if we don't reinterpret the value... 00661 // 00662 return Ty->isLosslesslyConvertibleTo(V->getType()); 00663 } 00664 } 00665 return false; 00666 } 00667 00668 00669 void llvm::ConvertValueToNewType(Value *V, Value *NewVal, ValueMapCache &VMC, 00670 const TargetData &TD) { 00671 ValueHandle VH(VMC, V); 00672 00673 // FIXME: This is horrible! 00674 unsigned NumUses = V->getNumUses(); 00675 for (unsigned It = 0; It < NumUses; ) { 00676 unsigned OldSize = NumUses; 00677 Value::use_iterator UI = V->use_begin(); 00678 std::advance(UI, It); 00679 ConvertOperandToType(*UI, V, NewVal, VMC, TD); 00680 NumUses = V->getNumUses(); 00681 if (NumUses == OldSize) ++It; 00682 } 00683 } 00684 00685 00686 00687 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal, 00688 ValueMapCache &VMC, const TargetData &TD) { 00689 if (isa<ValueHandle>(U)) return; // Valuehandles don't let go of operands... 00690 00691 if (VMC.OperandsMapped.count(U)) return; 00692 VMC.OperandsMapped.insert(U); 00693 00694 ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U); 00695 if (VMCI != VMC.ExprMap.end()) 00696 return; 00697 00698 00699 Instruction *I = cast<Instruction>(U); // Only Instructions convertible 00700 00701 BasicBlock *BB = I->getParent(); 00702 assert(BB != 0 && "Instruction not embedded in basic block!"); 00703 std::string Name = I->getName(); 00704 I->setName(""); 00705 Instruction *Res; // Result of conversion 00706 00707 //std::cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I 00708 // << "BB Before: " << BB << endl; 00709 00710 // Prevent I from being removed... 00711 ValueHandle IHandle(VMC, I); 00712 00713 const Type *NewTy = NewVal->getType(); 00714 Constant *Dummy = (NewTy != Type::VoidTy) ? 00715 Constant::getNullValue(NewTy) : 0; 00716 00717 switch (I->getOpcode()) { 00718 case Instruction::Cast: 00719 if (VMC.NewCasts.count(ValueHandle(VMC, I))) { 00720 // This cast has already had it's value converted, causing a new cast to 00721 // be created. We don't want to create YET ANOTHER cast instruction 00722 // representing the original one, so just modify the operand of this cast 00723 // instruction, which we know is newly created. 00724 I->setOperand(0, NewVal); 00725 I->setName(Name); // give I its name back 00726 return; 00727 00728 } else { 00729 Res = new CastInst(NewVal, I->getType(), Name); 00730 } 00731 break; 00732 00733 case Instruction::Add: 00734 case Instruction::Sub: 00735 case Instruction::SetEQ: 00736 case Instruction::SetNE: { 00737 Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(), 00738 Dummy, Dummy, Name); 00739 VMC.ExprMap[I] = Res; // Add node to expression eagerly 00740 00741 unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0; 00742 Value *OtherOp = I->getOperand(OtherIdx); 00743 Res->setOperand(!OtherIdx, NewVal); 00744 Value *NewOther = ConvertExpressionToType(OtherOp, NewTy, VMC, TD); 00745 Res->setOperand(OtherIdx, NewOther); 00746 break; 00747 } 00748 case Instruction::Shl: 00749 case Instruction::Shr: 00750 assert(I->getOperand(0) == OldVal); 00751 Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal, 00752 I->getOperand(1), Name); 00753 break; 00754 00755 case Instruction::Free: // Free can free any pointer type! 00756 assert(I->getOperand(0) == OldVal); 00757 Res = new FreeInst(NewVal); 00758 break; 00759 00760 00761 case Instruction::Load: { 00762 assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType())); 00763 const Type *LoadedTy = 00764 cast<PointerType>(NewVal->getType())->getElementType(); 00765 00766 Value *Src = NewVal; 00767 00768 if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) { 00769 std::vector<Value*> Indices; 00770 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00771 00772 unsigned Offset = 0; // No offset, get first leaf. 00773 LoadedTy = getStructOffsetType(CT, Offset, Indices, TD, false); 00774 assert(LoadedTy->isFirstClassType()); 00775 00776 if (Indices.size() != 1) { // Do not generate load X, 0 00777 // Insert the GEP instruction before this load. 00778 Src = new GetElementPtrInst(Src, Indices, Name+".idx", I); 00779 } 00780 } 00781 00782 Res = new LoadInst(Src, Name); 00783 assert(Res->getType()->isFirstClassType() && "Load of structure or array!"); 00784 break; 00785 } 00786 00787 case Instruction::Store: { 00788 if (I->getOperand(0) == OldVal) { // Replace the source value 00789 // Check to see if operand #1 has already been converted... 00790 ValueMapCache::ExprMapTy::iterator VMCI = 00791 VMC.ExprMap.find(I->getOperand(1)); 00792 if (VMCI != VMC.ExprMap.end()) { 00793 // Comments describing this stuff are in the OperandConvertibleToType 00794 // switch statement for Store... 00795 // 00796 const Type *ElTy = 00797 cast<PointerType>(VMCI->second->getType())->getElementType(); 00798 00799 Value *SrcPtr = VMCI->second; 00800 00801 if (ElTy != NewTy) { 00802 // We check that this is a struct in the initial scan... 00803 const StructType *SElTy = cast<StructType>(ElTy); 00804 00805 std::vector<Value*> Indices; 00806 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00807 00808 unsigned Offset = 0; 00809 const Type *Ty = getStructOffsetType(ElTy, Offset, Indices, TD,false); 00810 assert(Offset == 0 && "Offset changed!"); 00811 assert(NewTy == Ty && "Did not convert to correct type!"); 00812 00813 // Insert the GEP instruction before this store. 00814 SrcPtr = new GetElementPtrInst(SrcPtr, Indices, 00815 SrcPtr->getName()+".idx", I); 00816 } 00817 Res = new StoreInst(NewVal, SrcPtr); 00818 00819 VMC.ExprMap[I] = Res; 00820 } else { 00821 // Otherwise, we haven't converted Operand #1 over yet... 00822 const PointerType *NewPT = PointerType::get(NewTy); 00823 Res = new StoreInst(NewVal, Constant::getNullValue(NewPT)); 00824 VMC.ExprMap[I] = Res; 00825 Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), 00826 NewPT, VMC, TD)); 00827 } 00828 } else { // Replace the source pointer 00829 const Type *ValTy = cast<PointerType>(NewTy)->getElementType(); 00830 00831 Value *SrcPtr = NewVal; 00832 00833 if (isa<StructType>(ValTy)) { 00834 std::vector<Value*> Indices; 00835 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 00836 00837 unsigned Offset = 0; 00838 ValTy = getStructOffsetType(ValTy, Offset, Indices, TD, false); 00839 00840 assert(Offset == 0 && ValTy); 00841 00842 // Insert the GEP instruction before this store. 00843 SrcPtr = new GetElementPtrInst(SrcPtr, Indices, 00844 SrcPtr->getName()+".idx", I); 00845 } 00846 00847 Res = new StoreInst(Constant::getNullValue(ValTy), SrcPtr); 00848 VMC.ExprMap[I] = Res; 00849 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), 00850 ValTy, VMC, TD)); 00851 } 00852 break; 00853 } 00854 00855 case Instruction::PHI: { 00856 PHINode *OldPN = cast<PHINode>(I); 00857 PHINode *NewPN = new PHINode(NewTy, Name); 00858 VMC.ExprMap[I] = NewPN; 00859 00860 while (OldPN->getNumOperands()) { 00861 BasicBlock *BB = OldPN->getIncomingBlock(0); 00862 Value *OldVal = OldPN->getIncomingValue(0); 00863 ValueHandle OldValHandle(VMC, OldVal); 00864 OldPN->removeIncomingValue(BB, false); 00865 Value *V = ConvertExpressionToType(OldVal, NewTy, VMC, TD); 00866 NewPN->addIncoming(V, BB); 00867 } 00868 Res = NewPN; 00869 break; 00870 } 00871 00872 case Instruction::Call: { 00873 Value *Meth = I->getOperand(0); 00874 std::vector<Value*> Params(I->op_begin()+1, I->op_end()); 00875 00876 if (Meth == OldVal) { // Changing the function pointer? 00877 const PointerType *NewPTy = cast<PointerType>(NewVal->getType()); 00878 const FunctionType *NewTy = cast<FunctionType>(NewPTy->getElementType()); 00879 00880 if (NewTy->getReturnType() == Type::VoidTy) 00881 Name = ""; // Make sure not to name a void call! 00882 00883 // Get an iterator to the call instruction so that we can insert casts for 00884 // operands if need be. Note that we do not require operands to be 00885 // convertible, we can insert casts if they are convertible but not 00886 // compatible. The reason for this is that we prefer to have resolved 00887 // functions but casted arguments if possible. 00888 // 00889 BasicBlock::iterator It = I; 00890 00891 // Convert over all of the call operands to their new types... but only 00892 // convert over the part that is not in the vararg section of the call. 00893 // 00894 for (unsigned i = 0; i != NewTy->getNumParams(); ++i) 00895 if (Params[i]->getType() != NewTy->getParamType(i)) { 00896 // Create a cast to convert it to the right type, we know that this 00897 // is a lossless cast... 00898 // 00899 Params[i] = new CastInst(Params[i], NewTy->getParamType(i), 00900 "callarg.cast." + 00901 Params[i]->getName(), It); 00902 } 00903 Meth = NewVal; // Update call destination to new value 00904 00905 } else { // Changing an argument, must be in vararg area 00906 std::vector<Value*>::iterator OI = 00907 std::find(Params.begin(), Params.end(), OldVal); 00908 assert (OI != Params.end() && "Not using value!"); 00909 00910 *OI = NewVal; 00911 } 00912 00913 Res = new CallInst(Meth, Params, Name); 00914 if (cast<CallInst>(I)->isTailCall()) 00915 cast<CallInst>(Res)->setTailCall(); 00916 cast<CallInst>(Res)->setCallingConv(cast<CallInst>(I)->getCallingConv()); 00917 break; 00918 } 00919 default: 00920 assert(0 && "Expression convertible, but don't know how to convert?"); 00921 return; 00922 } 00923 00924 // If the instruction was newly created, insert it into the instruction 00925 // stream. 00926 // 00927 BasicBlock::iterator It = I; 00928 assert(It != BB->end() && "Instruction not in own basic block??"); 00929 BB->getInstList().insert(It, Res); // Keep It pointing to old instruction 00930 00931 DEBUG(std::cerr << "COT CREATED: " << (void*)Res << " " << *Res 00932 << "In: " << (void*)I << " " << *I << "Out: " << (void*)Res 00933 << " " << *Res); 00934 00935 // Add the instruction to the expression map 00936 VMC.ExprMap[I] = Res; 00937 00938 if (I->getType() != Res->getType()) 00939 ConvertValueToNewType(I, Res, VMC, TD); 00940 else { 00941 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00942 UI != E; ) 00943 if (isa<ValueHandle>(*UI)) { 00944 ++UI; 00945 } else { 00946 Use &U = UI.getUse(); 00947 ++UI; // Do not invalidate UI. 00948 U.set(Res); 00949 } 00950 } 00951 } 00952 00953 00954 ValueHandle::ValueHandle(ValueMapCache &VMC, Value *V) 00955 : Instruction(Type::VoidTy, UserOp1, &Op, 1, ""), Op(V, this), Cache(VMC) { 00956 //DEBUG(std::cerr << "VH AQUIRING: " << (void*)V << " " << V); 00957 } 00958 00959 ValueHandle::ValueHandle(const ValueHandle &VH) 00960 : Instruction(Type::VoidTy, UserOp1, &Op, 1, ""), 00961 Op(VH.Op, this), Cache(VH.Cache) { 00962 //DEBUG(std::cerr << "VH AQUIRING: " << (void*)V << " " << V); 00963 } 00964 00965 static void RecursiveDelete(ValueMapCache &Cache, Instruction *I) { 00966 if (!I || !I->use_empty()) return; 00967 00968 assert(I->getParent() && "Inst not in basic block!"); 00969 00970 //DEBUG(std::cerr << "VH DELETING: " << (void*)I << " " << I); 00971 00972 for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); 00973 OI != OE; ++OI) 00974 if (Instruction *U = dyn_cast<Instruction>(OI)) { 00975 *OI = 0; 00976 RecursiveDelete(Cache, U); 00977 } 00978 00979 I->getParent()->getInstList().remove(I); 00980 00981 Cache.OperandsMapped.erase(I); 00982 Cache.ExprMap.erase(I); 00983 delete I; 00984 } 00985 00986 ValueHandle::~ValueHandle() { 00987 if (Op->hasOneUse()) { 00988 Value *V = Op; 00989 Op.set(0); // Drop use! 00990 00991 // Now we just need to remove the old instruction so we don't get infinite 00992 // loops. Note that we cannot use DCE because DCE won't remove a store 00993 // instruction, for example. 00994 // 00995 RecursiveDelete(Cache, dyn_cast<Instruction>(V)); 00996 } else { 00997 //DEBUG(std::cerr << "VH RELEASING: " << (void*)Operands[0].get() << " " 00998 // << Operands[0]->getNumUses() << " " << Operands[0]); 00999 } 01000 } 01001