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/Analysis/Expressions.h" 00020 #include "llvm/ADT/STLExtras.h" 00021 #include "llvm/Support/Debug.h" 00022 #include <algorithm> 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 // Peephole Malloc instructions: we take a look at the use chain of the 00033 // malloc instruction, and try to find out if the following conditions hold: 00034 // 1. The malloc is of the form: 'malloc [sbyte], uint <constant>' 00035 // 2. The only users of the malloc are cast & add instructions 00036 // 3. Of the cast instructions, there is only one destination pointer type 00037 // [RTy] where the size of the pointed to object is equal to the number 00038 // of bytes allocated. 00039 // 00040 // If these conditions hold, we convert the malloc to allocate an [RTy] 00041 // element. TODO: This comment is out of date WRT arrays 00042 // 00043 static bool MallocConvertibleToType(MallocInst *MI, const Type *Ty, 00044 ValueTypeCache &CTMap, 00045 const TargetData &TD) { 00046 if (!isa<PointerType>(Ty)) return false; // Malloc always returns pointers 00047 00048 // Deal with the type to allocate, not the pointer type... 00049 Ty = cast<PointerType>(Ty)->getElementType(); 00050 if (!Ty->isSized()) return false; // Can only alloc something with a size 00051 00052 // Analyze the number of bytes allocated... 00053 ExprType Expr = ClassifyExpr(MI->getArraySize()); 00054 00055 // Get information about the base datatype being allocated, before & after 00056 int ReqTypeSize = TD.getTypeSize(Ty); 00057 if (ReqTypeSize == 0) return false; 00058 unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType()); 00059 00060 // Must have a scale or offset to analyze it... 00061 if (!Expr.Offset && !Expr.Scale && OldTypeSize == 1) return false; 00062 00063 // Get the offset and scale of the allocation... 00064 int64_t OffsetVal = Expr.Offset ? getConstantValue(Expr.Offset) : 0; 00065 int64_t ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) :(Expr.Var != 0); 00066 00067 // The old type might not be of unit size, take old size into consideration 00068 // here... 00069 int64_t Offset = OffsetVal * OldTypeSize; 00070 int64_t Scale = ScaleVal * OldTypeSize; 00071 00072 // In order to be successful, both the scale and the offset must be a multiple 00073 // of the requested data type's size. 00074 // 00075 if (Offset/ReqTypeSize*ReqTypeSize != Offset || 00076 Scale/ReqTypeSize*ReqTypeSize != Scale) 00077 return false; // Nope. 00078 00079 return true; 00080 } 00081 00082 static Instruction *ConvertMallocToType(MallocInst *MI, const Type *Ty, 00083 const std::string &Name, 00084 ValueMapCache &VMC, 00085 const TargetData &TD){ 00086 BasicBlock *BB = MI->getParent(); 00087 BasicBlock::iterator It = BB->end(); 00088 00089 // Analyze the number of bytes allocated... 00090 ExprType Expr = ClassifyExpr(MI->getArraySize()); 00091 00092 const PointerType *AllocTy = cast<PointerType>(Ty); 00093 const Type *ElType = AllocTy->getElementType(); 00094 00095 unsigned DataSize = TD.getTypeSize(ElType); 00096 unsigned OldTypeSize = TD.getTypeSize(MI->getType()->getElementType()); 00097 00098 // Get the offset and scale coefficients that we are allocating... 00099 int64_t OffsetVal = (Expr.Offset ? getConstantValue(Expr.Offset) : 0); 00100 int64_t ScaleVal = Expr.Scale ? getConstantValue(Expr.Scale) : (Expr.Var !=0); 00101 00102 // The old type might not be of unit size, take old size into consideration 00103 // here... 00104 unsigned Offset = (uint64_t)OffsetVal * OldTypeSize / DataSize; 00105 unsigned Scale = (uint64_t)ScaleVal * OldTypeSize / DataSize; 00106 00107 // Locate the malloc instruction, because we may be inserting instructions 00108 It = MI; 00109 00110 // If we have a scale, apply it first... 00111 if (Expr.Var) { 00112 // Expr.Var is not necessarily unsigned right now, insert a cast now. 00113 if (Expr.Var->getType() != Type::UIntTy) 00114 Expr.Var = new CastInst(Expr.Var, Type::UIntTy, 00115 Expr.Var->getName()+"-uint", It); 00116 00117 if (Scale != 1) 00118 Expr.Var = BinaryOperator::create(Instruction::Mul, Expr.Var, 00119 ConstantUInt::get(Type::UIntTy, Scale), 00120 Expr.Var->getName()+"-scl", It); 00121 00122 } else { 00123 // If we are not scaling anything, just make the offset be the "var"... 00124 Expr.Var = ConstantUInt::get(Type::UIntTy, Offset); 00125 Offset = 0; Scale = 1; 00126 } 00127 00128 // If we have an offset now, add it in... 00129 if (Offset != 0) { 00130 assert(Expr.Var && "Var must be nonnull by now!"); 00131 Expr.Var = BinaryOperator::create(Instruction::Add, Expr.Var, 00132 ConstantUInt::get(Type::UIntTy, Offset), 00133 Expr.Var->getName()+"-off", It); 00134 } 00135 00136 assert(AllocTy == Ty); 00137 return new MallocInst(AllocTy->getElementType(), Expr.Var, Name); 00138 } 00139 00140 00141 // ExpressionConvertibleToType - Return true if it is possible 00142 bool llvm::ExpressionConvertibleToType(Value *V, const Type *Ty, 00143 ValueTypeCache &CTMap, const TargetData &TD) { 00144 // Expression type must be holdable in a register. 00145 if (!Ty->isFirstClassType()) 00146 return false; 00147 00148 ValueTypeCache::iterator CTMI = CTMap.find(V); 00149 if (CTMI != CTMap.end()) return CTMI->second == Ty; 00150 00151 // If it's a constant... all constants can be converted to a different 00152 // type. 00153 // 00154 if (isa<Constant>(V) && !isa<GlobalValue>(V)) 00155 return true; 00156 00157 CTMap[V] = Ty; 00158 if (V->getType() == Ty) return true; // Expression already correct type! 00159 00160 Instruction *I = dyn_cast<Instruction>(V); 00161 if (I == 0) return false; // Otherwise, we can't convert! 00162 00163 switch (I->getOpcode()) { 00164 case Instruction::Cast: 00165 // We can convert the expr if the cast destination type is losslessly 00166 // convertible to the requested type. 00167 if (!Ty->isLosslesslyConvertibleTo(I->getType())) return false; 00168 00169 // We also do not allow conversion of a cast that casts from a ptr to array 00170 // of X to a *X. For example: cast [4 x %List *] * %val to %List * * 00171 // 00172 if (const PointerType *SPT = 00173 dyn_cast<PointerType>(I->getOperand(0)->getType())) 00174 if (const PointerType *DPT = dyn_cast<PointerType>(I->getType())) 00175 if (const ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType())) 00176 if (AT->getElementType() == DPT->getElementType()) 00177 return false; 00178 break; 00179 00180 case Instruction::Add: 00181 case Instruction::Sub: 00182 if (!Ty->isInteger() && !Ty->isFloatingPoint()) return false; 00183 if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD) || 00184 !ExpressionConvertibleToType(I->getOperand(1), Ty, CTMap, TD)) 00185 return false; 00186 break; 00187 case Instruction::Shr: 00188 if (!Ty->isInteger()) return false; 00189 if (Ty->isSigned() != V->getType()->isSigned()) return false; 00190 // FALL THROUGH 00191 case Instruction::Shl: 00192 if (!Ty->isInteger()) return false; 00193 if (!ExpressionConvertibleToType(I->getOperand(0), Ty, CTMap, TD)) 00194 return false; 00195 break; 00196 00197 case Instruction::Load: { 00198 LoadInst *LI = cast<LoadInst>(I); 00199 if (!ExpressionConvertibleToType(LI->getPointerOperand(), 00200 PointerType::get(Ty), CTMap, TD)) 00201 return false; 00202 break; 00203 } 00204 case Instruction::PHI: { 00205 PHINode *PN = cast<PHINode>(I); 00206 // Be conservative if we find a giant PHI node. 00207 if (PN->getNumIncomingValues() > 32) return false; 00208 00209 for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) 00210 if (!ExpressionConvertibleToType(PN->getIncomingValue(i), Ty, CTMap, TD)) 00211 return false; 00212 break; 00213 } 00214 00215 case Instruction::Malloc: 00216 if (!MallocConvertibleToType(cast<MallocInst>(I), Ty, CTMap, TD)) 00217 return false; 00218 break; 00219 00220 case Instruction::GetElementPtr: { 00221 // GetElementPtr's are directly convertible to a pointer type if they have 00222 // a number of zeros at the end. Because removing these values does not 00223 // change the logical offset of the GEP, it is okay and fair to remove them. 00224 // This can change this: 00225 // %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0 ; <%List **> 00226 // %t2 = cast %List * * %t1 to %List * 00227 // into 00228 // %t2 = getelementptr %Hosp * %hosp, ubyte 4 ; <%List *> 00229 // 00230 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I); 00231 const PointerType *PTy = dyn_cast<PointerType>(Ty); 00232 if (!PTy) return false; // GEP must always return a pointer... 00233 const Type *PVTy = PTy->getElementType(); 00234 00235 // Check to see if there are zero elements that we can remove from the 00236 // index array. If there are, check to see if removing them causes us to 00237 // get to the right type... 00238 // 00239 std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end()); 00240 const Type *BaseType = GEP->getPointerOperand()->getType(); 00241 const Type *ElTy = 0; 00242 00243 while (!Indices.empty() && 00244 Indices.back() == Constant::getNullValue(Indices.back()->getType())){ 00245 Indices.pop_back(); 00246 ElTy = GetElementPtrInst::getIndexedType(BaseType, Indices, true); 00247 if (ElTy == PVTy) 00248 break; // Found a match!! 00249 ElTy = 0; 00250 } 00251 00252 if (ElTy) break; // Found a number of zeros we can strip off! 00253 00254 // Otherwise, we can convert a GEP from one form to the other iff the 00255 // current gep is of the form 'getelementptr sbyte*, long N 00256 // and we could convert this to an appropriate GEP for the new type. 00257 // 00258 if (GEP->getNumOperands() == 2 && 00259 GEP->getType() == PointerType::get(Type::SByteTy)) { 00260 00261 // Do not Check to see if our incoming pointer can be converted 00262 // to be a ptr to an array of the right type... because in more cases than 00263 // not, it is simply not analyzable because of pointer/array 00264 // discrepancies. To fix this, we will insert a cast before the GEP. 00265 // 00266 00267 // Check to see if 'N' is an expression that can be converted to 00268 // the appropriate size... if so, allow it. 00269 // 00270 std::vector<Value*> Indices; 00271 const Type *ElTy = ConvertibleToGEP(PTy, I->getOperand(1), Indices, TD); 00272 if (ElTy == PVTy) { 00273 if (!ExpressionConvertibleToType(I->getOperand(0), 00274 PointerType::get(ElTy), CTMap, TD)) 00275 return false; // Can't continue, ExConToTy might have polluted set! 00276 break; 00277 } 00278 } 00279 00280 // Otherwise, it could be that we have something like this: 00281 // getelementptr [[sbyte] *] * %reg115, long %reg138 ; [sbyte]** 00282 // and want to convert it into something like this: 00283 // getelemenptr [[int] *] * %reg115, long %reg138 ; [int]** 00284 // 00285 if (GEP->getNumOperands() == 2 && 00286 PTy->getElementType()->isSized() && 00287 TD.getTypeSize(PTy->getElementType()) == 00288 TD.getTypeSize(GEP->getType()->getElementType())) { 00289 const PointerType *NewSrcTy = PointerType::get(PVTy); 00290 if (!ExpressionConvertibleToType(I->getOperand(0), NewSrcTy, CTMap, TD)) 00291 return false; 00292 break; 00293 } 00294 00295 return false; // No match, maybe next time. 00296 } 00297 00298 case Instruction::Call: { 00299 if (isa<Function>(I->getOperand(0))) 00300 return false; // Don't even try to change direct calls. 00301 00302 // If this is a function pointer, we can convert the return type if we can 00303 // convert the source function pointer. 00304 // 00305 const PointerType *PT = cast<PointerType>(I->getOperand(0)->getType()); 00306 const FunctionType *FT = cast<FunctionType>(PT->getElementType()); 00307 std::vector<const Type *> ArgTys(FT->param_begin(), FT->param_end()); 00308 const FunctionType *NewTy = 00309 FunctionType::get(Ty, ArgTys, FT->isVarArg()); 00310 if (!ExpressionConvertibleToType(I->getOperand(0), 00311 PointerType::get(NewTy), CTMap, TD)) 00312 return false; 00313 break; 00314 } 00315 default: 00316 return false; 00317 } 00318 00319 // Expressions are only convertible if all of the users of the expression can 00320 // have this value converted. This makes use of the map to avoid infinite 00321 // recursion. 00322 // 00323 for (Value::use_iterator It = I->use_begin(), E = I->use_end(); It != E; ++It) 00324 if (!OperandConvertibleToType(*It, I, Ty, CTMap, TD)) 00325 return false; 00326 00327 return true; 00328 } 00329 00330 00331 Value *llvm::ConvertExpressionToType(Value *V, const Type *Ty, 00332 ValueMapCache &VMC, const TargetData &TD) { 00333 if (V->getType() == Ty) return V; // Already where we need to be? 00334 00335 ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V); 00336 if (VMCI != VMC.ExprMap.end()) { 00337 const Value *GV = VMCI->second; 00338 const Type *GTy = VMCI->second->getType(); 00339 assert(VMCI->second->getType() == Ty); 00340 00341 if (Instruction *I = dyn_cast<Instruction>(V)) 00342 ValueHandle IHandle(VMC, I); // Remove I if it is unused now! 00343 00344 return VMCI->second; 00345 } 00346 00347 DEBUG(std::cerr << "CETT: " << (void*)V << " " << *V); 00348 00349 Instruction *I = dyn_cast<Instruction>(V); 00350 if (I == 0) { 00351 Constant *CPV = cast<Constant>(V); 00352 // Constants are converted by constant folding the cast that is required. 00353 // We assume here that all casts are implemented for constant prop. 00354 Value *Result = ConstantExpr::getCast(CPV, Ty); 00355 // Add the instruction to the expression map 00356 //VMC.ExprMap[V] = Result; 00357 return Result; 00358 } 00359 00360 00361 BasicBlock *BB = I->getParent(); 00362 std::string Name = I->getName(); if (!Name.empty()) I->setName(""); 00363 Instruction *Res; // Result of conversion 00364 00365 ValueHandle IHandle(VMC, I); // Prevent I from being removed! 00366 00367 Constant *Dummy = Constant::getNullValue(Ty); 00368 00369 switch (I->getOpcode()) { 00370 case Instruction::Cast: 00371 assert(VMC.NewCasts.count(ValueHandle(VMC, I)) == 0); 00372 Res = new CastInst(I->getOperand(0), Ty, Name); 00373 VMC.NewCasts.insert(ValueHandle(VMC, Res)); 00374 break; 00375 00376 case Instruction::Add: 00377 case Instruction::Sub: 00378 Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(), 00379 Dummy, Dummy, Name); 00380 VMC.ExprMap[I] = Res; // Add node to expression eagerly 00381 00382 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC, TD)); 00383 Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), Ty, VMC, TD)); 00384 break; 00385 00386 case Instruction::Shl: 00387 case Instruction::Shr: 00388 Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), Dummy, 00389 I->getOperand(1), Name); 00390 VMC.ExprMap[I] = Res; 00391 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), Ty, VMC, TD)); 00392 break; 00393 00394 case Instruction::Load: { 00395 LoadInst *LI = cast<LoadInst>(I); 00396 00397 Res = new LoadInst(Constant::getNullValue(PointerType::get(Ty)), Name); 00398 VMC.ExprMap[I] = Res; 00399 Res->setOperand(0, ConvertExpressionToType(LI->getPointerOperand(), 00400 PointerType::get(Ty), VMC, TD)); 00401 assert(Res->getOperand(0)->getType() == PointerType::get(Ty)); 00402 assert(Ty == Res->getType()); 00403 assert(Res->getType()->isFirstClassType() && "Load of structure or array!"); 00404 break; 00405 } 00406 00407 case Instruction::PHI: { 00408 PHINode *OldPN = cast<PHINode>(I); 00409 PHINode *NewPN = new PHINode(Ty, Name); 00410 00411 VMC.ExprMap[I] = NewPN; // Add node to expression eagerly 00412 while (OldPN->getNumOperands()) { 00413 BasicBlock *BB = OldPN->getIncomingBlock(0); 00414 Value *OldVal = OldPN->getIncomingValue(0); 00415 ValueHandle OldValHandle(VMC, OldVal); 00416 OldPN->removeIncomingValue(BB, false); 00417 Value *V = ConvertExpressionToType(OldVal, Ty, VMC, TD); 00418 NewPN->addIncoming(V, BB); 00419 } 00420 Res = NewPN; 00421 break; 00422 } 00423 00424 case Instruction::Malloc: { 00425 Res = ConvertMallocToType(cast<MallocInst>(I), Ty, Name, VMC, TD); 00426 break; 00427 } 00428 00429 case Instruction::GetElementPtr: { 00430 // GetElementPtr's are directly convertible to a pointer type if they have 00431 // a number of zeros at the end. Because removing these values does not 00432 // change the logical offset of the GEP, it is okay and fair to remove them. 00433 // This can change this: 00434 // %t1 = getelementptr %Hosp * %hosp, ubyte 4, ubyte 0 ; <%List **> 00435 // %t2 = cast %List * * %t1 to %List * 00436 // into 00437 // %t2 = getelementptr %Hosp * %hosp, ubyte 4 ; <%List *> 00438 // 00439 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I); 00440 00441 // Check to see if there are zero elements that we can remove from the 00442 // index array. If there are, check to see if removing them causes us to 00443 // get to the right type... 00444 // 00445 std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end()); 00446 const Type *BaseType = GEP->getPointerOperand()->getType(); 00447 const Type *PVTy = cast<PointerType>(Ty)->getElementType(); 00448 Res = 0; 00449 while (!Indices.empty() && 00450 Indices.back() == Constant::getNullValue(Indices.back()->getType())){ 00451 Indices.pop_back(); 00452 if (GetElementPtrInst::getIndexedType(BaseType, Indices, true) == PVTy) { 00453 if (Indices.size() == 0) 00454 Res = new CastInst(GEP->getPointerOperand(), BaseType); // NOOP CAST 00455 else 00456 Res = new GetElementPtrInst(GEP->getPointerOperand(), Indices, Name); 00457 break; 00458 } 00459 } 00460 00461 if (Res == 0 && GEP->getNumOperands() == 2 && 00462 GEP->getType() == PointerType::get(Type::SByteTy)) { 00463 00464 // Otherwise, we can convert a GEP from one form to the other iff the 00465 // current gep is of the form 'getelementptr sbyte*, unsigned N 00466 // and we could convert this to an appropriate GEP for the new type. 00467 // 00468 const PointerType *NewSrcTy = PointerType::get(PVTy); 00469 BasicBlock::iterator It = I; 00470 00471 // Check to see if 'N' is an expression that can be converted to 00472 // the appropriate size... if so, allow it. 00473 // 00474 std::vector<Value*> Indices; 00475 const Type *ElTy = ConvertibleToGEP(NewSrcTy, I->getOperand(1), 00476 Indices, TD, &It); 00477 if (ElTy) { 00478 assert(ElTy == PVTy && "Internal error, setup wrong!"); 00479 Res = new GetElementPtrInst(Constant::getNullValue(NewSrcTy), 00480 Indices, Name); 00481 VMC.ExprMap[I] = Res; 00482 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), 00483 NewSrcTy, VMC, TD)); 00484 } 00485 } 00486 00487 // Otherwise, it could be that we have something like this: 00488 // getelementptr [[sbyte] *] * %reg115, uint %reg138 ; [sbyte]** 00489 // and want to convert it into something like this: 00490 // getelemenptr [[int] *] * %reg115, uint %reg138 ; [int]** 00491 // 00492 if (Res == 0) { 00493 const PointerType *NewSrcTy = PointerType::get(PVTy); 00494 std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end()); 00495 Res = new GetElementPtrInst(Constant::getNullValue(NewSrcTy), 00496 Indices, Name); 00497 VMC.ExprMap[I] = Res; 00498 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), 00499 NewSrcTy, VMC, TD)); 00500 } 00501 00502 00503 assert(Res && "Didn't find match!"); 00504 break; 00505 } 00506 00507 case Instruction::Call: { 00508 assert(!isa<Function>(I->getOperand(0))); 00509 00510 // If this is a function pointer, we can convert the return type if we can 00511 // convert the source function pointer. 00512 // 00513 const PointerType *PT = cast<PointerType>(I->getOperand(0)->getType()); 00514 const FunctionType *FT = cast<FunctionType>(PT->getElementType()); 00515 std::vector<const Type *> ArgTys(FT->param_begin(), FT->param_end()); 00516 const FunctionType *NewTy = 00517 FunctionType::get(Ty, ArgTys, FT->isVarArg()); 00518 const PointerType *NewPTy = PointerType::get(NewTy); 00519 if (Ty == Type::VoidTy) 00520 Name = ""; // Make sure not to name calls that now return void! 00521 00522 Res = new CallInst(Constant::getNullValue(NewPTy), 00523 std::vector<Value*>(I->op_begin()+1, I->op_end()), 00524 Name); 00525 VMC.ExprMap[I] = Res; 00526 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0),NewPTy,VMC,TD)); 00527 break; 00528 } 00529 default: 00530 assert(0 && "Expression convertible, but don't know how to convert?"); 00531 return 0; 00532 } 00533 00534 assert(Res->getType() == Ty && "Didn't convert expr to correct type!"); 00535 00536 BB->getInstList().insert(I, Res); 00537 00538 // Add the instruction to the expression map 00539 VMC.ExprMap[I] = Res; 00540 00541 00542 unsigned NumUses = I->use_size(); 00543 for (unsigned It = 0; It < NumUses; ) { 00544 unsigned OldSize = NumUses; 00545 Value::use_iterator UI = I->use_begin(); 00546 std::advance(UI, It); 00547 ConvertOperandToType(*UI, I, Res, VMC, TD); 00548 NumUses = I->use_size(); 00549 if (NumUses == OldSize) ++It; 00550 } 00551 00552 DEBUG(std::cerr << "ExpIn: " << (void*)I << " " << *I 00553 << "ExpOut: " << (void*)Res << " " << *Res); 00554 00555 return Res; 00556 } 00557 00558 00559 00560 // ValueConvertibleToType - Return true if it is possible 00561 bool llvm::ValueConvertibleToType(Value *V, const Type *Ty, 00562 ValueTypeCache &ConvertedTypes, 00563 const TargetData &TD) { 00564 ValueTypeCache::iterator I = ConvertedTypes.find(V); 00565 if (I != ConvertedTypes.end()) return I->second == Ty; 00566 ConvertedTypes[V] = Ty; 00567 00568 // It is safe to convert the specified value to the specified type IFF all of 00569 // the uses of the value can be converted to accept the new typed value. 00570 // 00571 if (V->getType() != Ty) { 00572 for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) 00573 if (!OperandConvertibleToType(*I, V, Ty, ConvertedTypes, TD)) 00574 return false; 00575 } 00576 00577 return true; 00578 } 00579 00580 00581 00582 00583 00584 // OperandConvertibleToType - Return true if it is possible to convert operand 00585 // V of User (instruction) U to the specified type. This is true iff it is 00586 // possible to change the specified instruction to accept this. CTMap is a map 00587 // of converted types, so that circular definitions will see the future type of 00588 // the expression, not the static current type. 00589 // 00590 static bool OperandConvertibleToType(User *U, Value *V, const Type *Ty, 00591 ValueTypeCache &CTMap, 00592 const TargetData &TD) { 00593 // if (V->getType() == Ty) return true; // Operand already the right type? 00594 00595 // Expression type must be holdable in a register. 00596 if (!Ty->isFirstClassType()) 00597 return false; 00598 00599 Instruction *I = dyn_cast<Instruction>(U); 00600 if (I == 0) return false; // We can't convert! 00601 00602 switch (I->getOpcode()) { 00603 case Instruction::Cast: 00604 assert(I->getOperand(0) == V); 00605 // We can convert the expr if the cast destination type is losslessly 00606 // convertible to the requested type. 00607 // Also, do not change a cast that is a noop cast. For all intents and 00608 // purposes it should be eliminated. 00609 if (!Ty->isLosslesslyConvertibleTo(I->getOperand(0)->getType()) || 00610 I->getType() == I->getOperand(0)->getType()) 00611 return false; 00612 00613 // Do not allow a 'cast ushort %V to uint' to have it's first operand be 00614 // converted to a 'short' type. Doing so changes the way sign promotion 00615 // happens, and breaks things. Only allow the cast to take place if the 00616 // signedness doesn't change... or if the current cast is not a lossy 00617 // conversion. 00618 // 00619 if (!I->getType()->isLosslesslyConvertibleTo(I->getOperand(0)->getType()) && 00620 I->getOperand(0)->getType()->isSigned() != Ty->isSigned()) 00621 return false; 00622 00623 // We also do not allow conversion of a cast that casts from a ptr to array 00624 // of X to a *X. For example: cast [4 x %List *] * %val to %List * * 00625 // 00626 if (const PointerType *SPT = 00627 dyn_cast<PointerType>(I->getOperand(0)->getType())) 00628 if (const PointerType *DPT = dyn_cast<PointerType>(I->getType())) 00629 if (const ArrayType *AT = dyn_cast<ArrayType>(SPT->getElementType())) 00630 if (AT->getElementType() == DPT->getElementType()) 00631 return false; 00632 return true; 00633 00634 case Instruction::Add: 00635 if (isa<PointerType>(Ty)) { 00636 Value *IndexVal = I->getOperand(V == I->getOperand(0) ? 1 : 0); 00637 std::vector<Value*> Indices; 00638 if (const Type *ETy = ConvertibleToGEP(Ty, IndexVal, Indices, TD)) { 00639 const Type *RetTy = PointerType::get(ETy); 00640 00641 // Only successful if we can convert this type to the required type 00642 if (ValueConvertibleToType(I, RetTy, CTMap, TD)) { 00643 CTMap[I] = RetTy; 00644 return true; 00645 } 00646 // We have to return failure here because ValueConvertibleToType could 00647 // have polluted our map 00648 return false; 00649 } 00650 } 00651 // FALLTHROUGH 00652 case Instruction::Sub: { 00653 if (!Ty->isInteger() && !Ty->isFloatingPoint()) return false; 00654 00655 Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0); 00656 return ValueConvertibleToType(I, Ty, CTMap, TD) && 00657 ExpressionConvertibleToType(OtherOp, Ty, CTMap, TD); 00658 } 00659 case Instruction::SetEQ: 00660 case Instruction::SetNE: { 00661 Value *OtherOp = I->getOperand((V == I->getOperand(0)) ? 1 : 0); 00662 return ExpressionConvertibleToType(OtherOp, Ty, CTMap, TD); 00663 } 00664 case Instruction::Shr: 00665 if (Ty->isSigned() != V->getType()->isSigned()) return false; 00666 // FALL THROUGH 00667 case Instruction::Shl: 00668 if (I->getOperand(1) == V) return false; // Cannot change shift amount type 00669 if (!Ty->isInteger()) return false; 00670 return ValueConvertibleToType(I, Ty, CTMap, TD); 00671 00672 case Instruction::Free: 00673 assert(I->getOperand(0) == V); 00674 return isa<PointerType>(Ty); // Free can free any pointer type! 00675 00676 case Instruction::Load: 00677 // Cannot convert the types of any subscripts... 00678 if (I->getOperand(0) != V) return false; 00679 00680 if (const PointerType *PT = dyn_cast<PointerType>(Ty)) { 00681 LoadInst *LI = cast<LoadInst>(I); 00682 00683 const Type *LoadedTy = PT->getElementType(); 00684 00685 // They could be loading the first element of a composite type... 00686 if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) { 00687 unsigned Offset = 0; // No offset, get first leaf. 00688 std::vector<Value*> Indices; // Discarded... 00689 LoadedTy = getStructOffsetType(CT, Offset, Indices, TD, false); 00690 assert(Offset == 0 && "Offset changed from zero???"); 00691 } 00692 00693 if (!LoadedTy->isFirstClassType()) 00694 return false; 00695 00696 if (TD.getTypeSize(LoadedTy) != TD.getTypeSize(LI->getType())) 00697 return false; 00698 00699 return ValueConvertibleToType(LI, LoadedTy, CTMap, TD); 00700 } 00701 return false; 00702 00703 case Instruction::Store: { 00704 StoreInst *SI = cast<StoreInst>(I); 00705 00706 if (V == I->getOperand(0)) { 00707 ValueTypeCache::iterator CTMI = CTMap.find(I->getOperand(1)); 00708 if (CTMI != CTMap.end()) { // Operand #1 is in the table already? 00709 // If so, check to see if it's Ty*, or, more importantly, if it is a 00710 // pointer to a structure where the first element is a Ty... this code 00711 // is necessary because we might be trying to change the source and 00712 // destination type of the store (they might be related) and the dest 00713 // pointer type might be a pointer to structure. Below we allow pointer 00714 // to structures where the 0th element is compatible with the value, 00715 // now we have to support the symmetrical part of this. 00716 // 00717 const Type *ElTy = cast<PointerType>(CTMI->second)->getElementType(); 00718 00719 // Already a pointer to what we want? Trivially accept... 00720 if (ElTy == Ty) return true; 00721 00722 // Tricky case now, if the destination is a pointer to structure, 00723 // obviously the source is not allowed to be a structure (cannot copy 00724 // a whole structure at a time), so the level raiser must be trying to 00725 // store into the first field. Check for this and allow it now: 00726 // 00727 if (const StructType *SElTy = dyn_cast<StructType>(ElTy)) { 00728 unsigned Offset = 0; 00729 std::vector<Value*> Indices; 00730 ElTy = getStructOffsetType(ElTy, Offset, Indices, TD, false); 00731 assert(Offset == 0 && "Offset changed!"); 00732 if (ElTy == 0) // Element at offset zero in struct doesn't exist! 00733 return false; // Can only happen for {}* 00734 00735 if (ElTy == Ty) // Looks like the 0th element of structure is 00736 return true; // compatible! Accept now! 00737 00738 // Otherwise we know that we can't work, so just stop trying now. 00739 return false; 00740 } 00741 } 00742 00743 // Can convert the store if we can convert the pointer operand to match 00744 // the new value type... 00745 return ExpressionConvertibleToType(I->getOperand(1), PointerType::get(Ty), 00746 CTMap, TD); 00747 } else if (const PointerType *PT = dyn_cast<PointerType>(Ty)) { 00748 const Type *ElTy = PT->getElementType(); 00749 assert(V == I->getOperand(1)); 00750 00751 if (isa<StructType>(ElTy)) { 00752 // We can change the destination pointer if we can store our first 00753 // argument into the first element of the structure... 00754 // 00755 unsigned Offset = 0; 00756 std::vector<Value*> Indices; 00757 ElTy = getStructOffsetType(ElTy, Offset, Indices, TD, false); 00758 assert(Offset == 0 && "Offset changed!"); 00759 if (ElTy == 0) // Element at offset zero in struct doesn't exist! 00760 return false; // Can only happen for {}* 00761 } 00762 00763 // Must move the same amount of data... 00764 if (!ElTy->isSized() || 00765 TD.getTypeSize(ElTy) != TD.getTypeSize(I->getOperand(0)->getType())) 00766 return false; 00767 00768 // Can convert store if the incoming value is convertible and if the 00769 // result will preserve semantics... 00770 const Type *Op0Ty = I->getOperand(0)->getType(); 00771 if (!(Op0Ty->isIntegral() ^ ElTy->isIntegral()) && 00772 !(Op0Ty->isFloatingPoint() ^ ElTy->isFloatingPoint())) 00773 return ExpressionConvertibleToType(I->getOperand(0), ElTy, CTMap, TD); 00774 } 00775 return false; 00776 } 00777 00778 case Instruction::GetElementPtr: 00779 if (V != I->getOperand(0) || !isa<PointerType>(Ty)) return false; 00780 00781 // If we have a two operand form of getelementptr, this is really little 00782 // more than a simple addition. As with addition, check to see if the 00783 // getelementptr instruction can be changed to index into the new type. 00784 // 00785 if (I->getNumOperands() == 2) { 00786 const Type *OldElTy = cast<PointerType>(I->getType())->getElementType(); 00787 unsigned DataSize = TD.getTypeSize(OldElTy); 00788 Value *Index = I->getOperand(1); 00789 Instruction *TempScale = 0; 00790 00791 // If the old data element is not unit sized, we have to create a scale 00792 // instruction so that ConvertibleToGEP will know the REAL amount we are 00793 // indexing by. Note that this is never inserted into the instruction 00794 // stream, so we have to delete it when we're done. 00795 // 00796 if (DataSize != 1) { 00797 Value *CST; 00798 if (Index->getType()->isSigned()) 00799 CST = ConstantSInt::get(Index->getType(), DataSize); 00800 else 00801 CST = ConstantUInt::get(Index->getType(), DataSize); 00802 00803 TempScale = BinaryOperator::create(Instruction::Mul, Index, CST); 00804 Index = TempScale; 00805 } 00806 00807 // Check to see if the second argument is an expression that can 00808 // be converted to the appropriate size... if so, allow it. 00809 // 00810 std::vector<Value*> Indices; 00811 const Type *ElTy = ConvertibleToGEP(Ty, Index, Indices, TD); 00812 delete TempScale; // Free our temporary multiply if we made it 00813 00814 if (ElTy == 0) return false; // Cannot make conversion... 00815 return ValueConvertibleToType(I, PointerType::get(ElTy), CTMap, TD); 00816 } 00817 return false; 00818 00819 case Instruction::PHI: { 00820 PHINode *PN = cast<PHINode>(I); 00821 // Be conservative if we find a giant PHI node. 00822 if (PN->getNumIncomingValues() > 32) return false; 00823 00824 for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) 00825 if (!ExpressionConvertibleToType(PN->getIncomingValue(i), Ty, CTMap, TD)) 00826 return false; 00827 return ValueConvertibleToType(PN, Ty, CTMap, TD); 00828 } 00829 00830 case Instruction::Call: { 00831 User::op_iterator OI = std::find(I->op_begin(), I->op_end(), V); 00832 assert (OI != I->op_end() && "Not using value!"); 00833 unsigned OpNum = OI - I->op_begin(); 00834 00835 // Are we trying to change the function pointer value to a new type? 00836 if (OpNum == 0) { 00837 const PointerType *PTy = dyn_cast<PointerType>(Ty); 00838 if (PTy == 0) return false; // Can't convert to a non-pointer type... 00839 const FunctionType *FTy = dyn_cast<FunctionType>(PTy->getElementType()); 00840 if (FTy == 0) return false; // Can't convert to a non ptr to function... 00841 00842 // Do not allow converting to a call where all of the operands are ...'s 00843 if (FTy->getNumParams() == 0 && FTy->isVarArg()) 00844 return false; // Do not permit this conversion! 00845 00846 // Perform sanity checks to make sure that new function type has the 00847 // correct number of arguments... 00848 // 00849 unsigned NumArgs = I->getNumOperands()-1; // Don't include function ptr 00850 00851 // Cannot convert to a type that requires more fixed arguments than 00852 // the call provides... 00853 // 00854 if (NumArgs < FTy->getNumParams()) return false; 00855 00856 // Unless this is a vararg function type, we cannot provide more arguments 00857 // than are desired... 00858 // 00859 if (!FTy->isVarArg() && NumArgs > FTy->getNumParams()) 00860 return false; 00861 00862 // Okay, at this point, we know that the call and the function type match 00863 // number of arguments. Now we see if we can convert the arguments 00864 // themselves. Note that we do not require operands to be convertible, 00865 // we can insert casts if they are convertible but not compatible. The 00866 // reason for this is that we prefer to have resolved functions but casted 00867 // arguments if possible. 00868 // 00869 for (unsigned i = 0, NA = FTy->getNumParams(); i < NA; ++i) 00870 if (!FTy->getParamType(i)->isLosslesslyConvertibleTo(I->getOperand(i+1)->getType())) 00871 return false; // Operands must have compatible types! 00872 00873 // Okay, at this point, we know that all of the arguments can be 00874 // converted. We succeed if we can change the return type if 00875 // necessary... 00876 // 00877 return ValueConvertibleToType(I, FTy->getReturnType(), CTMap, TD); 00878 } 00879 00880 const PointerType *MPtr = cast<PointerType>(I->getOperand(0)->getType()); 00881 const FunctionType *FTy = cast<FunctionType>(MPtr->getElementType()); 00882 if (!FTy->isVarArg()) return false; 00883 00884 if ((OpNum-1) < FTy->getNumParams()) 00885 return false; // It's not in the varargs section... 00886 00887 // If we get this far, we know the value is in the varargs section of the 00888 // function! We can convert if we don't reinterpret the value... 00889 // 00890 return Ty->isLosslesslyConvertibleTo(V->getType()); 00891 } 00892 } 00893 return false; 00894 } 00895 00896 00897 void llvm::ConvertValueToNewType(Value *V, Value *NewVal, ValueMapCache &VMC, 00898 const TargetData &TD) { 00899 ValueHandle VH(VMC, V); 00900 00901 unsigned NumUses = V->use_size(); 00902 for (unsigned It = 0; It < NumUses; ) { 00903 unsigned OldSize = NumUses; 00904 Value::use_iterator UI = V->use_begin(); 00905 std::advance(UI, It); 00906 ConvertOperandToType(*UI, V, NewVal, VMC, TD); 00907 NumUses = V->use_size(); 00908 if (NumUses == OldSize) ++It; 00909 } 00910 } 00911 00912 00913 00914 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal, 00915 ValueMapCache &VMC, const TargetData &TD) { 00916 if (isa<ValueHandle>(U)) return; // Valuehandles don't let go of operands... 00917 00918 if (VMC.OperandsMapped.count(U)) return; 00919 VMC.OperandsMapped.insert(U); 00920 00921 ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(U); 00922 if (VMCI != VMC.ExprMap.end()) 00923 return; 00924 00925 00926 Instruction *I = cast<Instruction>(U); // Only Instructions convertible 00927 00928 BasicBlock *BB = I->getParent(); 00929 assert(BB != 0 && "Instruction not embedded in basic block!"); 00930 std::string Name = I->getName(); 00931 I->setName(""); 00932 Instruction *Res; // Result of conversion 00933 00934 //std::cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I 00935 // << "BB Before: " << BB << endl; 00936 00937 // Prevent I from being removed... 00938 ValueHandle IHandle(VMC, I); 00939 00940 const Type *NewTy = NewVal->getType(); 00941 Constant *Dummy = (NewTy != Type::VoidTy) ? 00942 Constant::getNullValue(NewTy) : 0; 00943 00944 switch (I->getOpcode()) { 00945 case Instruction::Cast: 00946 if (VMC.NewCasts.count(ValueHandle(VMC, I))) { 00947 // This cast has already had it's value converted, causing a new cast to 00948 // be created. We don't want to create YET ANOTHER cast instruction 00949 // representing the original one, so just modify the operand of this cast 00950 // instruction, which we know is newly created. 00951 I->setOperand(0, NewVal); 00952 I->setName(Name); // give I its name back 00953 return; 00954 00955 } else { 00956 Res = new CastInst(NewVal, I->getType(), Name); 00957 } 00958 break; 00959 00960 case Instruction::Add: 00961 if (isa<PointerType>(NewTy)) { 00962 Value *IndexVal = I->getOperand(OldVal == I->getOperand(0) ? 1 : 0); 00963 std::vector<Value*> Indices; 00964 BasicBlock::iterator It = I; 00965 00966 if (const Type *ETy = ConvertibleToGEP(NewTy, IndexVal, Indices, TD,&It)){ 00967 // If successful, convert the add to a GEP 00968 //const Type *RetTy = PointerType::get(ETy); 00969 // First operand is actually the given pointer... 00970 Res = new GetElementPtrInst(NewVal, Indices, Name); 00971 assert(cast<PointerType>(Res->getType())->getElementType() == ETy && 00972 "ConvertibleToGEP broken!"); 00973 break; 00974 } 00975 } 00976 // FALLTHROUGH 00977 00978 case Instruction::Sub: 00979 case Instruction::SetEQ: 00980 case Instruction::SetNE: { 00981 Res = BinaryOperator::create(cast<BinaryOperator>(I)->getOpcode(), 00982 Dummy, Dummy, Name); 00983 VMC.ExprMap[I] = Res; // Add node to expression eagerly 00984 00985 unsigned OtherIdx = (OldVal == I->getOperand(0)) ? 1 : 0; 00986 Value *OtherOp = I->getOperand(OtherIdx); 00987 Res->setOperand(!OtherIdx, NewVal); 00988 Value *NewOther = ConvertExpressionToType(OtherOp, NewTy, VMC, TD); 00989 Res->setOperand(OtherIdx, NewOther); 00990 break; 00991 } 00992 case Instruction::Shl: 00993 case Instruction::Shr: 00994 assert(I->getOperand(0) == OldVal); 00995 Res = new ShiftInst(cast<ShiftInst>(I)->getOpcode(), NewVal, 00996 I->getOperand(1), Name); 00997 break; 00998 00999 case Instruction::Free: // Free can free any pointer type! 01000 assert(I->getOperand(0) == OldVal); 01001 Res = new FreeInst(NewVal); 01002 break; 01003 01004 01005 case Instruction::Load: { 01006 assert(I->getOperand(0) == OldVal && isa<PointerType>(NewVal->getType())); 01007 const Type *LoadedTy = 01008 cast<PointerType>(NewVal->getType())->getElementType(); 01009 01010 Value *Src = NewVal; 01011 01012 if (const CompositeType *CT = dyn_cast<CompositeType>(LoadedTy)) { 01013 std::vector<Value*> Indices; 01014 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 01015 01016 unsigned Offset = 0; // No offset, get first leaf. 01017 LoadedTy = getStructOffsetType(CT, Offset, Indices, TD, false); 01018 assert(LoadedTy->isFirstClassType()); 01019 01020 if (Indices.size() != 1) { // Do not generate load X, 0 01021 // Insert the GEP instruction before this load. 01022 Src = new GetElementPtrInst(Src, Indices, Name+".idx", I); 01023 } 01024 } 01025 01026 Res = new LoadInst(Src, Name); 01027 assert(Res->getType()->isFirstClassType() && "Load of structure or array!"); 01028 break; 01029 } 01030 01031 case Instruction::Store: { 01032 if (I->getOperand(0) == OldVal) { // Replace the source value 01033 // Check to see if operand #1 has already been converted... 01034 ValueMapCache::ExprMapTy::iterator VMCI = 01035 VMC.ExprMap.find(I->getOperand(1)); 01036 if (VMCI != VMC.ExprMap.end()) { 01037 // Comments describing this stuff are in the OperandConvertibleToType 01038 // switch statement for Store... 01039 // 01040 const Type *ElTy = 01041 cast<PointerType>(VMCI->second->getType())->getElementType(); 01042 01043 Value *SrcPtr = VMCI->second; 01044 01045 if (ElTy != NewTy) { 01046 // We check that this is a struct in the initial scan... 01047 const StructType *SElTy = cast<StructType>(ElTy); 01048 01049 std::vector<Value*> Indices; 01050 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 01051 01052 unsigned Offset = 0; 01053 const Type *Ty = getStructOffsetType(ElTy, Offset, Indices, TD,false); 01054 assert(Offset == 0 && "Offset changed!"); 01055 assert(NewTy == Ty && "Did not convert to correct type!"); 01056 01057 // Insert the GEP instruction before this store. 01058 SrcPtr = new GetElementPtrInst(SrcPtr, Indices, 01059 SrcPtr->getName()+".idx", I); 01060 } 01061 Res = new StoreInst(NewVal, SrcPtr); 01062 01063 VMC.ExprMap[I] = Res; 01064 } else { 01065 // Otherwise, we haven't converted Operand #1 over yet... 01066 const PointerType *NewPT = PointerType::get(NewTy); 01067 Res = new StoreInst(NewVal, Constant::getNullValue(NewPT)); 01068 VMC.ExprMap[I] = Res; 01069 Res->setOperand(1, ConvertExpressionToType(I->getOperand(1), 01070 NewPT, VMC, TD)); 01071 } 01072 } else { // Replace the source pointer 01073 const Type *ValTy = cast<PointerType>(NewTy)->getElementType(); 01074 01075 Value *SrcPtr = NewVal; 01076 01077 if (isa<StructType>(ValTy)) { 01078 std::vector<Value*> Indices; 01079 Indices.push_back(Constant::getNullValue(Type::UIntTy)); 01080 01081 unsigned Offset = 0; 01082 ValTy = getStructOffsetType(ValTy, Offset, Indices, TD, false); 01083 01084 assert(Offset == 0 && ValTy); 01085 01086 // Insert the GEP instruction before this store. 01087 SrcPtr = new GetElementPtrInst(SrcPtr, Indices, 01088 SrcPtr->getName()+".idx", I); 01089 } 01090 01091 Res = new StoreInst(Constant::getNullValue(ValTy), SrcPtr); 01092 VMC.ExprMap[I] = Res; 01093 Res->setOperand(0, ConvertExpressionToType(I->getOperand(0), 01094 ValTy, VMC, TD)); 01095 } 01096 break; 01097 } 01098 01099 01100 case Instruction::GetElementPtr: { 01101 // Convert a one index getelementptr into just about anything that is 01102 // desired. 01103 // 01104 BasicBlock::iterator It = I; 01105 const Type *OldElTy = cast<PointerType>(I->getType())->getElementType(); 01106 unsigned DataSize = TD.getTypeSize(OldElTy); 01107 Value *Index = I->getOperand(1); 01108 01109 if (DataSize != 1) { 01110 // Insert a multiply of the old element type is not a unit size... 01111 Value *CST; 01112 if (Index->getType()->isSigned()) 01113 CST = ConstantSInt::get(Index->getType(), DataSize); 01114 else 01115 CST = ConstantUInt::get(Index->getType(), DataSize); 01116 01117 Index = BinaryOperator::create(Instruction::Mul, Index, CST, "scale", It); 01118 } 01119 01120 // Perform the conversion now... 01121 // 01122 std::vector<Value*> Indices; 01123 const Type *ElTy = ConvertibleToGEP(NewVal->getType(),Index,Indices,TD,&It); 01124 assert(ElTy != 0 && "GEP Conversion Failure!"); 01125 Res = new GetElementPtrInst(NewVal, Indices, Name); 01126 assert(Res->getType() == PointerType::get(ElTy) && 01127 "ConvertibleToGet failed!"); 01128 } 01129 #if 0 01130 if (I->getType() == PointerType::get(Type::SByteTy)) { 01131 // Convert a getelementptr sbyte * %reg111, uint 16 freely back to 01132 // anything that is a pointer type... 01133 // 01134 BasicBlock::iterator It = I; 01135 01136 // Check to see if the second argument is an expression that can 01137 // be converted to the appropriate size... if so, allow it. 01138 // 01139 std::vector<Value*> Indices; 01140 const Type *ElTy = ConvertibleToGEP(NewVal->getType(), I->getOperand(1), 01141 Indices, TD, &It); 01142 assert(ElTy != 0 && "GEP Conversion Failure!"); 01143 01144 Res = new GetElementPtrInst(NewVal, Indices, Name); 01145 } else { 01146 // Convert a getelementptr ulong * %reg123, uint %N 01147 // to getelementptr long * %reg123, uint %N 01148 // ... where the type must simply stay the same size... 01149 // 01150 GetElementPtrInst *GEP = cast<GetElementPtrInst>(I); 01151 std::vector<Value*> Indices(GEP->idx_begin(), GEP->idx_end()); 01152 Res = new GetElementPtrInst(NewVal, Indices, Name); 01153 } 01154 #endif 01155 break; 01156 01157 case Instruction::PHI: { 01158 PHINode *OldPN = cast<PHINode>(I); 01159 PHINode *NewPN = new PHINode(NewTy, Name); 01160 VMC.ExprMap[I] = NewPN; 01161 01162 while (OldPN->getNumOperands()) { 01163 BasicBlock *BB = OldPN->getIncomingBlock(0); 01164 Value *OldVal = OldPN->getIncomingValue(0); 01165 ValueHandle OldValHandle(VMC, OldVal); 01166 OldPN->removeIncomingValue(BB, false); 01167 Value *V = ConvertExpressionToType(OldVal, NewTy, VMC, TD); 01168 NewPN->addIncoming(V, BB); 01169 } 01170 Res = NewPN; 01171 break; 01172 } 01173 01174 case Instruction::Call: { 01175 Value *Meth = I->getOperand(0); 01176 std::vector<Value*> Params(I->op_begin()+1, I->op_end()); 01177 01178 if (Meth == OldVal) { // Changing the function pointer? 01179 const PointerType *NewPTy = cast<PointerType>(NewVal->getType()); 01180 const FunctionType *NewTy = cast<FunctionType>(NewPTy->getElementType()); 01181 01182 if (NewTy->getReturnType() == Type::VoidTy) 01183 Name = ""; // Make sure not to name a void call! 01184 01185 // Get an iterator to the call instruction so that we can insert casts for 01186 // operands if need be. Note that we do not require operands to be 01187 // convertible, we can insert casts if they are convertible but not 01188 // compatible. The reason for this is that we prefer to have resolved 01189 // functions but casted arguments if possible. 01190 // 01191 BasicBlock::iterator It = I; 01192 01193 // Convert over all of the call operands to their new types... but only 01194 // convert over the part that is not in the vararg section of the call. 01195 // 01196 for (unsigned i = 0; i != NewTy->getNumParams(); ++i) 01197 if (Params[i]->getType() != NewTy->getParamType(i)) { 01198 // Create a cast to convert it to the right type, we know that this 01199 // is a lossless cast... 01200 // 01201 Params[i] = new CastInst(Params[i], NewTy->getParamType(i), 01202 "callarg.cast." + 01203 Params[i]->getName(), It); 01204 } 01205 Meth = NewVal; // Update call destination to new value 01206 01207 } else { // Changing an argument, must be in vararg area 01208 std::vector<Value*>::iterator OI = 01209 std::find(Params.begin(), Params.end(), OldVal); 01210 assert (OI != Params.end() && "Not using value!"); 01211 01212 *OI = NewVal; 01213 } 01214 01215 Res = new CallInst(Meth, Params, Name); 01216 break; 01217 } 01218 default: 01219 assert(0 && "Expression convertible, but don't know how to convert?"); 01220 return; 01221 } 01222 01223 // If the instruction was newly created, insert it into the instruction 01224 // stream. 01225 // 01226 BasicBlock::iterator It = I; 01227 assert(It != BB->end() && "Instruction not in own basic block??"); 01228 BB->getInstList().insert(It, Res); // Keep It pointing to old instruction 01229 01230 DEBUG(std::cerr << "COT CREATED: " << (void*)Res << " " << *Res 01231 << "In: " << (void*)I << " " << *I << "Out: " << (void*)Res 01232 << " " << *Res); 01233 01234 // Add the instruction to the expression map 01235 VMC.ExprMap[I] = Res; 01236 01237 if (I->getType() != Res->getType()) 01238 ConvertValueToNewType(I, Res, VMC, TD); 01239 else { 01240 bool FromStart = true; 01241 Value::use_iterator UI; 01242 while (1) { 01243 if (FromStart) UI = I->use_begin(); 01244 if (UI == I->use_end()) break; 01245 01246 if (isa<ValueHandle>(*UI)) { 01247 ++UI; 01248 FromStart = false; 01249 } else { 01250 User *U = *UI; 01251 if (!FromStart) --UI; 01252 U->replaceUsesOfWith(I, Res); 01253 if (!FromStart) ++UI; 01254 } 01255 } 01256 } 01257 } 01258 01259 01260 ValueHandle::ValueHandle(ValueMapCache &VMC, Value *V) 01261 : Instruction(Type::VoidTy, UserOp1, ""), Cache(VMC) { 01262 //DEBUG(std::cerr << "VH AQUIRING: " << (void*)V << " " << V); 01263 Operands.push_back(Use(V, this)); 01264 } 01265 01266 ValueHandle::ValueHandle(const ValueHandle &VH) 01267 : Instruction(Type::VoidTy, UserOp1, ""), Cache(VH.Cache) { 01268 //DEBUG(std::cerr << "VH AQUIRING: " << (void*)V << " " << V); 01269 Operands.push_back(Use((Value*)VH.getOperand(0), this)); 01270 } 01271 01272 static void RecursiveDelete(ValueMapCache &Cache, Instruction *I) { 01273 if (!I || !I->use_empty()) return; 01274 01275 assert(I->getParent() && "Inst not in basic block!"); 01276 01277 //DEBUG(std::cerr << "VH DELETING: " << (void*)I << " " << I); 01278 01279 for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); 01280 OI != OE; ++OI) 01281 if (Instruction *U = dyn_cast<Instruction>(OI)) { 01282 *OI = 0; 01283 RecursiveDelete(Cache, U); 01284 } 01285 01286 I->getParent()->getInstList().remove(I); 01287 01288 Cache.OperandsMapped.erase(I); 01289 Cache.ExprMap.erase(I); 01290 delete I; 01291 } 01292 01293 ValueHandle::~ValueHandle() { 01294 if (Operands[0]->hasOneUse()) { 01295 Value *V = Operands[0]; 01296 Operands[0] = 0; // Drop use! 01297 01298 // Now we just need to remove the old instruction so we don't get infinite 01299 // loops. Note that we cannot use DCE because DCE won't remove a store 01300 // instruction, for example. 01301 // 01302 RecursiveDelete(Cache, dyn_cast<Instruction>(V)); 01303 } else { 01304 //DEBUG(std::cerr << "VH RELEASING: " << (void*)Operands[0].get() << " " 01305 // << Operands[0]->use_size() << " " << Operands[0]); 01306 } 01307 } 01308