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"
20 #include "llvm/Assembly/Writer.h"
23 // PruneTypes - Given a type Ty, make sure that neither it, or one of its
24 // subtypes, occur in TypesToModify.
26 static void PruneTypes(const Type *Ty, set<const StructType*> &TypesToModify,
27 set<const Type*> &ProcessedTypes) {
28 if (ProcessedTypes.count(Ty)) return; // Already been checked
29 ProcessedTypes.insert(Ty);
31 // If the element is in TypesToModify, remove it now...
32 if (const StructType *ST = dyn_cast<StructType>(Ty)) {
33 TypesToModify.erase(ST); // This doesn't fail if the element isn't present
34 std::cerr << "Unable to swap type: " << ST << "\n";
37 // Remove all types that this type contains as well... do not remove types
38 // that are referenced only through pointers, because we depend on the size of
39 // the pointer, not on what the structure points to.
41 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
43 if (!isa<PointerType>(*I))
44 PruneTypes(*I, TypesToModify, ProcessedTypes);
48 static bool FirstLess(const pair<unsigned, unsigned> &LHS,
49 const pair<unsigned, unsigned> &RHS) {
50 return LHS.second < RHS.second;
53 static unsigned getIndex(const vector<pair<unsigned, unsigned> > &Vec,
55 for (unsigned i = 0; ; ++i)
56 if (Vec[i].first == Field) return i;
59 static inline void GetTransformation(const StructType *ST,
60 vector<int> &Transform,
61 enum SimpleStructMutation::Transform XForm) {
62 unsigned NumElements = ST->getElementTypes().size();
63 Transform.reserve(NumElements);
66 case SimpleStructMutation::SwapElements:
67 // The transformation to do is: just simply swap the elements
68 for (unsigned i = 0; i < NumElements; ++i)
69 Transform.push_back(NumElements-i-1);
72 case SimpleStructMutation::SortElements: {
73 vector<pair<unsigned, unsigned> > ElList;
75 // Build mapping from index to size
76 for (unsigned i = 0; i < NumElements; ++i)
78 std::make_pair(i, TD.getTypeSize(ST->getElementTypes()[i])));
80 sort(ElList.begin(), ElList.end(), ptr_fun(FirstLess));
82 for (unsigned i = 0; i < NumElements; ++i)
83 Transform.push_back(getIndex(ElList, i));
90 SimpleStructMutation::TransformsType
91 SimpleStructMutation::getTransforms(Module *M, enum Transform XForm) {
93 // FIXME: These should be calculated by the Pass framework!
95 // We need to know which types to modify, and which types we CAN'T modify
96 FindUsedTypes *FUT = new FindUsedTypes(/*true*/); // TODO: Do symbol tables as well
97 FindUnsafePointerTypes *FUPT = new FindUnsafePointerTypes();
99 // Simutaneously find all of the types used, and all of the types that aren't
102 PassManager Analyses;
105 Analyses.run(M); // Do analyses
107 // Get the results out of the analyzers...
108 const set<PointerType*> &UnsafePTys = FUPT->getUnsafeTypes();
109 const set<const Type *> &UsedTypes = FUT->getTypes();
112 // Combine the two sets, weeding out non structure types. Closures in C++
113 // sure would be nice.
114 set<const StructType*> TypesToModify;
115 for (set<const Type *>::const_iterator I = UsedTypes.begin(),
116 E = UsedTypes.end(); I != E; ++I)
117 if (const StructType *ST = dyn_cast<StructType>(*I))
118 TypesToModify.insert(ST);
121 // Go through the Unsafe types and remove all types from TypesToModify that we
122 // are not allowed to modify, because that would be unsafe.
124 set<const Type*> ProcessedTypes;
125 for (set<PointerType*>::const_iterator I = UnsafePTys.begin(),
126 E = UnsafePTys.end(); I != E; ++I) {
127 //cerr << "Pruning type: " << *I << "\n";
128 PruneTypes(*I, TypesToModify, ProcessedTypes);
132 // Build up a set of structure types that we are going to modify, and
133 // information describing how to modify them.
134 std::map<const StructType*, vector<int> > Transforms;
136 for (set<const StructType*>::iterator I = TypesToModify.begin(),
137 E = TypesToModify.end(); I != E; ++I) {
138 const StructType *ST = *I;
140 vector<int> &Transform = Transforms[ST]; // Fill in the map directly
141 GetTransformation(ST, Transform, XForm);