1 //===- SwapStructContents.cpp - Swap structure elements around ---*- C++ -*--=//
3 // This pass does a simple transformation that swaps all of the elements of the
4 // struct types in the program around.
6 //===----------------------------------------------------------------------===//
9 #include "llvm/Transforms/SwapStructContents.h"
10 #include "llvm/Transforms/MutateStructTypes.h"
11 #include "llvm/Analysis/FindUsedTypes.h"
12 #include "llvm/Analysis/FindUnsafePointerTypes.h"
13 #include "TransformInternals.h"
16 #include "llvm/Assembly/Writer.h"
18 // PruneTypes - Given a type Ty, make sure that neither it, or one of its
19 // subtypes, occur in TypesToModify.
21 static void PruneTypes(const Type *Ty, set<const StructType*> &TypesToModify,
22 set<const Type*> &ProcessedTypes) {
23 if (ProcessedTypes.count(Ty)) return; // Already been checked
24 ProcessedTypes.insert(Ty);
26 // If the element is in TypesToModify, remove it now...
27 if (const StructType *ST = dyn_cast<StructType>(Ty)) {
28 TypesToModify.erase(ST); // This doesn't fail if the element isn't present
29 cerr << "Unable to swap type: " << ST << endl;
32 // Remove all types that this type contains as well... do not remove types
33 // that are referenced only through pointers, because we depend on the size of
34 // the pointer, not on what the structure points to.
36 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
38 if (!isa<PointerType>(*I))
39 PruneTypes(*I, TypesToModify, ProcessedTypes);
43 static bool FirstLess(const pair<unsigned, unsigned> &LHS,
44 const pair<unsigned, unsigned> &RHS) {
45 return LHS.second < RHS.second;
48 static unsigned getIndex(const vector<pair<unsigned, unsigned> > &Vec,
50 for (unsigned i = 0; ; ++i)
51 if (Vec[i].first == Field) return i;
54 static inline void GetTransformation(const StructType *ST,
55 vector<int> &Transform,
56 enum PrebuiltStructMutation::Transform XForm) {
57 unsigned NumElements = ST->getElementTypes().size();
58 Transform.reserve(NumElements);
61 case PrebuiltStructMutation::SwapElements:
62 // The transformation to do is: just simply swap the elements
63 for (unsigned i = 0; i < NumElements; ++i)
64 Transform.push_back(NumElements-i-1);
67 case PrebuiltStructMutation::SortElements: {
68 vector<pair<unsigned, unsigned> > ElList;
70 // Build mapping from index to size
71 for (unsigned i = 0; i < NumElements; ++i)
72 ElList.push_back(make_pair(i, TD.getTypeSize(ST->getElementTypes()[i])));
74 sort(ElList.begin(), ElList.end(), ptr_fun(FirstLess));
76 for (unsigned i = 0; i < NumElements; ++i)
77 Transform.push_back(getIndex(ElList, i));
84 // doPassInitialization - This does all of the work of the pass
86 PrebuiltStructMutation::TransformsType
87 PrebuiltStructMutation::getTransforms(Module *M, enum Transform XForm) {
88 // We need to know which types to modify, and which types we CAN'T modify
89 FindUsedTypes FUT/*(true)*/; // TODO: Do symbol tables as well
90 FindUnsafePointerTypes FUPT;
92 // Simutaneously find all of the types used, and all of the types that aren't
95 vector<Pass*> Analyses;
96 Analyses.push_back(&FUT);
97 Analyses.push_back(&FUPT);
98 Pass::runAllPasses(M, Analyses); // Do analyses
101 // Get the results out of the analyzers...
102 const set<PointerType*> &UnsafePTys = FUPT.getUnsafeTypes();
103 const set<const Type *> &UsedTypes = FUT.getTypes();
106 // Combine the two sets, weeding out non structure types. Closures in C++
107 // sure would be nice.
108 set<const StructType*> TypesToModify;
109 for (set<const Type *>::const_iterator I = UsedTypes.begin(),
110 E = UsedTypes.end(); I != E; ++I)
111 if (const StructType *ST = dyn_cast<StructType>(*I))
112 TypesToModify.insert(ST);
115 // Go through the Unsafe types and remove all types from TypesToModify that we
116 // are not allowed to modify, because that would be unsafe.
118 set<const Type*> ProcessedTypes;
119 for (set<PointerType*>::const_iterator I = UnsafePTys.begin(),
120 E = UnsafePTys.end(); I != E; ++I) {
121 cerr << "Pruning type: " << *I << endl;
122 PruneTypes(*I, TypesToModify, ProcessedTypes);
126 // Build up a set of structure types that we are going to modify, and
127 // information describing how to modify them.
128 map<const StructType*, vector<int> > Transforms;
130 for (set<const StructType*>::iterator I = TypesToModify.begin(),
131 E = TypesToModify.end(); I != E; ++I) {
132 const StructType *ST = *I;
134 vector<int> &Transform = Transforms[ST]; // Fill in the map directly
135 GetTransformation(ST, Transform, XForm);