1 //===- MutateStructTypes.cpp - Change struct defns ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass is used to change structure accesses and type definitions in some
11 // way. It can be used to arbitrarily permute structure fields, safely, without
12 // breaking code. A transformation may only be done on a type if that type has
13 // been found to be "safe" by the 'FindUnsafePointerTypes' pass. This pass will
14 // assert and die if you try to do an illegal transformation.
16 // This is an interprocedural pass that requires the entire program to do a
19 //===----------------------------------------------------------------------===//
21 #include "llvm/Transforms/MutateStructTypes.h"
22 #include "llvm/DerivedTypes.h"
23 #include "llvm/Module.h"
24 #include "llvm/SymbolTable.h"
25 #include "llvm/Instructions.h"
26 #include "llvm/Constants.h"
27 #include "Support/STLExtras.h"
28 #include "Support/Debug.h"
33 // ValuePlaceHolder - A stupid little marker value. It appears as an
34 // instruction of type Instruction::UserOp1.
36 struct ValuePlaceHolder : public Instruction {
37 ValuePlaceHolder(const Type *Ty) : Instruction(Ty, UserOp1, "") {}
39 virtual Instruction *clone() const { abort(); return 0; }
40 virtual const char *getOpcodeName() const { return "placeholder"; }
44 // ConvertType - Convert from the old type system to the new one...
45 const Type *MutateStructTypes::ConvertType(const Type *Ty) {
46 if (Ty->isPrimitiveType() ||
47 isa<OpaqueType>(Ty)) return Ty; // Don't convert primitives
49 std::map<const Type *, PATypeHolder>::iterator I = TypeMap.find(Ty);
50 if (I != TypeMap.end()) return I->second;
52 const Type *DestTy = 0;
54 PATypeHolder PlaceHolder = OpaqueType::get();
55 TypeMap.insert(std::make_pair(Ty, PlaceHolder.get()));
57 switch (Ty->getTypeID()) {
58 case Type::FunctionTyID: {
59 const FunctionType *FT = cast<FunctionType>(Ty);
60 const Type *RetTy = ConvertType(FT->getReturnType());
61 std::vector<const Type*> ArgTypes;
63 for (FunctionType::param_iterator I = FT->param_begin(),
64 E = FT->param_end(); I != E; ++I)
65 ArgTypes.push_back(ConvertType(*I));
67 DestTy = FunctionType::get(RetTy, ArgTypes, FT->isVarArg());
70 case Type::StructTyID: {
71 const StructType *ST = cast<StructType>(Ty);
72 std::vector<const Type *> Types;
74 for (StructType::element_iterator I = ST->element_begin(),
75 E = ST->element_end(); I != E; ++I)
76 Types.push_back(ConvertType(*I));
77 DestTy = StructType::get(Types);
81 DestTy = ArrayType::get(ConvertType(cast<ArrayType>(Ty)->getElementType()),
82 cast<ArrayType>(Ty)->getNumElements());
85 case Type::PointerTyID:
86 DestTy = PointerType::get(
87 ConvertType(cast<PointerType>(Ty)->getElementType()));
90 assert(0 && "Unknown type!");
94 assert(DestTy && "Type didn't get created!?!?");
96 // Refine our little placeholder value into a real type...
97 ((DerivedType*)PlaceHolder.get())->refineAbstractTypeTo(DestTy);
98 TypeMap.insert(std::make_pair(Ty, PlaceHolder.get()));
100 return PlaceHolder.get();
104 // AdjustIndices - Convert the indices specified by Idx to the new changed form
105 // using the specified OldTy as the base type being indexed into.
107 void MutateStructTypes::AdjustIndices(const CompositeType *OldTy,
108 std::vector<Value*> &Idx,
110 assert(i < Idx.size() && "i out of range!");
111 const CompositeType *NewCT = cast<CompositeType>(ConvertType(OldTy));
112 if (NewCT == OldTy) return; // No adjustment unless type changes
114 if (const StructType *OldST = dyn_cast<StructType>(OldTy)) {
115 // Figure out what the current index is...
116 unsigned ElNum = cast<ConstantUInt>(Idx[i])->getValue();
117 assert(ElNum < OldST->getNumElements());
119 std::map<const StructType*, TransformType>::iterator
120 I = Transforms.find(OldST);
121 if (I != Transforms.end()) {
122 assert(ElNum < I->second.second.size());
123 // Apply the XForm specified by Transforms map...
124 unsigned NewElNum = I->second.second[ElNum];
125 Idx[i] = ConstantUInt::get(Idx[i]->getType(), NewElNum);
129 // Recursively process subtypes...
130 if (i+1 < Idx.size())
131 AdjustIndices(cast<CompositeType>(OldTy->getTypeAtIndex(Idx[i])), Idx, i+1);
135 // ConvertValue - Convert from the old value in the old type system to the new
138 Value *MutateStructTypes::ConvertValue(const Value *V) {
139 // Ignore null values and simple constants..
140 if (V == 0) return 0;
142 if (const Constant *CPV = dyn_cast<Constant>(V)) {
143 if (V->getType()->isPrimitiveType())
146 if (isa<ConstantPointerNull>(CPV))
147 return ConstantPointerNull::get(
148 cast<PointerType>(ConvertType(V->getType())));
149 assert(0 && "Unable to convert constpool val of this type!");
152 // Check to see if this is an out of function reference first...
153 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
154 // Check to see if the value is in the map...
155 std::map<const GlobalValue*, GlobalValue*>::iterator I = GlobalMap.find(GV);
156 if (I == GlobalMap.end())
157 return (Value*)GV; // Not mapped, just return value itself
161 std::map<const Value*, Value*>::iterator I = LocalValueMap.find(V);
162 if (I != LocalValueMap.end()) return I->second;
164 if (const BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
165 // Create placeholder block to represent the basic block we haven't seen yet
166 // This will be used when the block gets created.
168 return LocalValueMap[V] = new BasicBlock(BB->getName());
171 DEBUG(std::cerr << "NPH: " << V << "\n");
173 // Otherwise make a constant to represent it
174 return LocalValueMap[V] = new ValuePlaceHolder(ConvertType(V->getType()));
178 // setTransforms - Take a map that specifies what transformation to do for each
179 // field of the specified structure types. There is one element of the vector
180 // for each field of the structure. The value specified indicates which slot of
181 // the destination structure the field should end up in. A negative value
182 // indicates that the field should be deleted entirely.
184 void MutateStructTypes::setTransforms(const TransformsType &XForm) {
186 // Loop over the types and insert dummy entries into the type map so that
187 // recursive types are resolved properly...
188 for (std::map<const StructType*, std::vector<int> >::const_iterator
189 I = XForm.begin(), E = XForm.end(); I != E; ++I) {
190 const StructType *OldTy = I->first;
191 TypeMap.insert(std::make_pair(OldTy, OpaqueType::get()));
194 // Loop over the type specified and figure out what types they should become
195 for (std::map<const StructType*, std::vector<int> >::const_iterator
196 I = XForm.begin(), E = XForm.end(); I != E; ++I) {
197 const StructType *OldTy = I->first;
198 const std::vector<int> &InVec = I->second;
200 assert(OldTy->getNumElements() == InVec.size() &&
201 "Action not specified for every element of structure type!");
203 std::vector<const Type *> NewType;
205 // Convert the elements of the type over, including the new position mapping
207 std::vector<int>::const_iterator TI = find(InVec.begin(), InVec.end(), Idx);
208 while (TI != InVec.end()) {
209 unsigned Offset = TI-InVec.begin();
210 const Type *NewEl = ConvertType(OldTy->getContainedType(Offset));
211 assert(NewEl && "Element not found!");
212 NewType.push_back(NewEl);
214 TI = find(InVec.begin(), InVec.end(), ++Idx);
217 // Create a new type that corresponds to the destination type
218 PATypeHolder NSTy = StructType::get(NewType);
220 // Refine the old opaque type to the new type to properly handle recursive
223 const Type *OldTypeStub = TypeMap.find(OldTy)->second.get();
224 ((DerivedType*)OldTypeStub)->refineAbstractTypeTo(NSTy);
226 // Add the transformation to the Transforms map.
227 Transforms.insert(std::make_pair(OldTy,
228 std::make_pair(cast<StructType>(NSTy.get()), InVec)));
230 DEBUG(std::cerr << "Mutate " << OldTy << "\nTo " << NSTy << "\n");
234 void MutateStructTypes::clearTransforms() {
238 assert(LocalValueMap.empty() &&
239 "Local Value Map should always be empty between transformations!");
242 // processGlobals - This loops over global constants defined in the
243 // module, converting them to their new type.
245 void MutateStructTypes::processGlobals(Module &M) {
246 // Loop through the functions in the module and create a new version of the
247 // function to contained the transformed code. Also, be careful to not
248 // process the values that we add.
250 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
251 if (!I->isExternal()) {
252 const FunctionType *NewMTy =
253 cast<FunctionType>(ConvertType(I->getFunctionType()));
255 // Create a new function to put stuff into...
256 Function *NewMeth = new Function(NewMTy, I->getLinkage(), I->getName());
258 I->setName("OLD."+I->getName());
260 // Insert the new function into the function list... to be filled in later
261 M.getFunctionList().push_back(NewMeth);
263 // Keep track of the association...
264 GlobalMap[I] = NewMeth;
267 // TODO: HANDLE GLOBAL VARIABLES
269 // Remap the symbol table to refer to the types in a nice way
271 SymbolTable &ST = M.getSymbolTable();
272 SymbolTable::type_iterator TI = ST.type_begin();
273 SymbolTable::type_iterator TE = ST.type_end();
274 for ( ; TI != TE; ++TI ) {
275 // FIXME: This is gross, I'm reaching right into a symbol table and
276 // mucking around with it's internals... but oh well.
278 TI->second = const_cast<Type*>(ConvertType(TI->second));
283 // removeDeadGlobals - For this pass, all this does is remove the old versions
284 // of the functions and global variables that we no longer need.
285 void MutateStructTypes::removeDeadGlobals(Module &M) {
286 // Prepare for deletion of globals by dropping their interdependencies...
287 for(Module::iterator I = M.begin(); I != M.end(); ++I) {
288 if (GlobalMap.find(I) != GlobalMap.end())
289 I->dropAllReferences();
292 // Run through and delete the functions and global variables...
293 #if 0 // TODO: HANDLE GLOBAL VARIABLES
294 M->getGlobalList().delete_span(M.gbegin(), M.gbegin()+NumGVars/2);
296 for(Module::iterator I = M.begin(); I != M.end();) {
297 if (GlobalMap.find(I) != GlobalMap.end())
298 I = M.getFunctionList().erase(I);
306 // transformFunction - This transforms the instructions of the function to use
309 void MutateStructTypes::transformFunction(Function *m) {
310 const Function *M = m;
311 std::map<const GlobalValue*, GlobalValue*>::iterator GMI = GlobalMap.find(M);
312 if (GMI == GlobalMap.end())
313 return; // Do not affect one of our new functions that we are creating
315 Function *NewMeth = cast<Function>(GMI->second);
317 // Okay, first order of business, create the arguments...
318 for (Function::aiterator I = m->abegin(), E = m->aend(),
319 DI = NewMeth->abegin(); I != E; ++I, ++DI) {
320 DI->setName(I->getName());
321 LocalValueMap[I] = DI; // Keep track of value mapping
325 // Loop over all of the basic blocks copying instructions over...
326 for (Function::const_iterator BB = M->begin(), BBE = M->end(); BB != BBE;
328 // Create a new basic block and establish a mapping between the old and new
329 BasicBlock *NewBB = cast<BasicBlock>(ConvertValue(BB));
330 NewMeth->getBasicBlockList().push_back(NewBB); // Add block to function
332 // Copy over all of the instructions in the basic block...
333 for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
336 const Instruction &I = *II; // Get the current instruction...
337 Instruction *NewI = 0;
339 switch (I.getOpcode()) {
340 // Terminator Instructions
341 case Instruction::Ret:
342 NewI = new ReturnInst(
343 ConvertValue(cast<ReturnInst>(I).getReturnValue()));
345 case Instruction::Br: {
346 const BranchInst &BI = cast<BranchInst>(I);
347 if (BI.isConditional()) {
349 new BranchInst(cast<BasicBlock>(ConvertValue(BI.getSuccessor(0))),
350 cast<BasicBlock>(ConvertValue(BI.getSuccessor(1))),
351 ConvertValue(BI.getCondition()));
354 new BranchInst(cast<BasicBlock>(ConvertValue(BI.getSuccessor(0))));
358 case Instruction::Switch:
359 case Instruction::Invoke:
360 case Instruction::Unwind:
361 assert(0 && "Insn not implemented!");
363 // Binary Instructions
364 case Instruction::Add:
365 case Instruction::Sub:
366 case Instruction::Mul:
367 case Instruction::Div:
368 case Instruction::Rem:
369 // Logical Operations
370 case Instruction::And:
371 case Instruction::Or:
372 case Instruction::Xor:
374 // Binary Comparison Instructions
375 case Instruction::SetEQ:
376 case Instruction::SetNE:
377 case Instruction::SetLE:
378 case Instruction::SetGE:
379 case Instruction::SetLT:
380 case Instruction::SetGT:
381 NewI = BinaryOperator::create((Instruction::BinaryOps)I.getOpcode(),
382 ConvertValue(I.getOperand(0)),
383 ConvertValue(I.getOperand(1)));
386 case Instruction::Shr:
387 case Instruction::Shl:
388 NewI = new ShiftInst(cast<ShiftInst>(I).getOpcode(),
389 ConvertValue(I.getOperand(0)),
390 ConvertValue(I.getOperand(1)));
394 // Memory Instructions
395 case Instruction::Alloca:
398 ConvertType(cast<PointerType>(I.getType())->getElementType()),
399 I.getNumOperands() ? ConvertValue(I.getOperand(0)) :0);
401 case Instruction::Malloc:
404 ConvertType(cast<PointerType>(I.getType())->getElementType()),
405 I.getNumOperands() ? ConvertValue(I.getOperand(0)) :0);
408 case Instruction::Free:
409 NewI = new FreeInst(ConvertValue(I.getOperand(0)));
412 case Instruction::Load:
413 NewI = new LoadInst(ConvertValue(I.getOperand(0)));
415 case Instruction::Store:
416 NewI = new StoreInst(ConvertValue(I.getOperand(0)),
417 ConvertValue(I.getOperand(1)));
419 case Instruction::GetElementPtr: {
420 const GetElementPtrInst &GEP = cast<GetElementPtrInst>(I);
421 std::vector<Value*> Indices(GEP.idx_begin(), GEP.idx_end());
422 if (!Indices.empty()) {
424 cast<PointerType>(GEP.getOperand(0)->getType())->getElementType();
425 AdjustIndices(cast<CompositeType>(PTy), Indices);
428 NewI = new GetElementPtrInst(ConvertValue(GEP.getOperand(0)), Indices);
432 // Miscellaneous Instructions
433 case Instruction::PHI: {
434 const PHINode &OldPN = cast<PHINode>(I);
435 PHINode *PN = new PHINode(ConvertType(OldPN.getType()));
436 for (unsigned i = 0; i < OldPN.getNumIncomingValues(); ++i)
437 PN->addIncoming(ConvertValue(OldPN.getIncomingValue(i)),
438 cast<BasicBlock>(ConvertValue(OldPN.getIncomingBlock(i))));
442 case Instruction::Cast:
443 NewI = new CastInst(ConvertValue(I.getOperand(0)),
444 ConvertType(I.getType()));
446 case Instruction::Call: {
447 Value *Meth = ConvertValue(I.getOperand(0));
448 std::vector<Value*> Operands;
449 for (unsigned i = 1; i < I.getNumOperands(); ++i)
450 Operands.push_back(ConvertValue(I.getOperand(i)));
451 NewI = new CallInst(Meth, Operands);
456 assert(0 && "UNKNOWN INSTRUCTION ENCOUNTERED!\n");
460 NewI->setName(I.getName());
461 NewBB->getInstList().push_back(NewI);
463 // Check to see if we had to make a placeholder for this value...
464 std::map<const Value*,Value*>::iterator LVMI = LocalValueMap.find(&I);
465 if (LVMI != LocalValueMap.end()) {
466 // Yup, make sure it's a placeholder...
467 Instruction *I = cast<Instruction>(LVMI->second);
468 assert(I->getOpcode() == Instruction::UserOp1 && "Not a placeholder!");
470 // Replace all uses of the place holder with the real deal...
471 I->replaceAllUsesWith(NewI);
472 delete I; // And free the placeholder memory
475 // Keep track of the fact the the local implementation of this instruction
477 LocalValueMap[&I] = NewI;
481 LocalValueMap.clear();
485 bool MutateStructTypes::run(Module &M) {
488 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
489 transformFunction(I);
491 removeDeadGlobals(M);