1 //===- SimpleStructMutation.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 //===----------------------------------------------------------------------===//
8 #include "llvm/Transforms/IPO.h"
9 #include "llvm/Transforms/IPO/MutateStructTypes.h"
10 #include "llvm/Analysis/FindUsedTypes.h"
11 #include "llvm/Analysis/FindUnsafePointerTypes.h"
12 #include "llvm/Target/TargetData.h"
13 #include "llvm/DerivedTypes.h"
21 struct SimpleStructMutation : public MutateStructTypes {
22 enum Transform { SwapElements, SortElements };
24 SimpleStructMutation(const TargetData &td) : TD(td) {}
26 virtual bool run(Module &M) = 0;
28 // getAnalysisUsage - This function needs the results of the
29 // FindUsedTypes and FindUnsafePointerTypes analysis passes...
31 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
32 AU.addRequired(FindUsedTypes::ID);
33 AU.addRequired(FindUnsafePointerTypes::ID);
34 MutateStructTypes::getAnalysisUsage(AU);
38 TransformsType getTransforms(Module &M, enum Transform);
41 struct SwapStructElements : public SimpleStructMutation {
42 SwapStructElements(const TargetData &TD) : SimpleStructMutation(TD) {}
44 virtual bool run(Module &M) {
45 setTransforms(getTransforms(M, SwapElements));
46 bool Changed = MutateStructTypes::run(M);
52 struct SortStructElements : public SimpleStructMutation {
53 SortStructElements(const TargetData &TD) : SimpleStructMutation(TD) {}
55 virtual bool run(Module &M) {
56 setTransforms(getTransforms(M, SortElements));
57 bool Changed = MutateStructTypes::run(M);
62 } // end anonymous namespace
66 // PruneTypes - Given a type Ty, make sure that neither it, or one of its
67 // subtypes, occur in TypesToModify.
69 static void PruneTypes(const Type *Ty, set<const StructType*> &TypesToModify,
70 set<const Type*> &ProcessedTypes) {
71 if (ProcessedTypes.count(Ty)) return; // Already been checked
72 ProcessedTypes.insert(Ty);
74 // If the element is in TypesToModify, remove it now...
75 if (const StructType *ST = dyn_cast<StructType>(Ty)) {
76 TypesToModify.erase(ST); // This doesn't fail if the element isn't present
77 std::cerr << "Unable to swap type: " << ST << "\n";
80 // Remove all types that this type contains as well... do not remove types
81 // that are referenced only through pointers, because we depend on the size of
82 // the pointer, not on what the structure points to.
84 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
86 if (!isa<PointerType>(*I))
87 PruneTypes(*I, TypesToModify, ProcessedTypes);
91 static bool FirstLess(const pair<unsigned, unsigned> &LHS,
92 const pair<unsigned, unsigned> &RHS) {
93 return LHS.second < RHS.second;
96 static unsigned getIndex(const vector<pair<unsigned, unsigned> > &Vec,
98 for (unsigned i = 0; ; ++i)
99 if (Vec[i].first == Field) return i;
102 static inline void GetTransformation(const TargetData &TD, const StructType *ST,
103 vector<int> &Transform,
104 enum SimpleStructMutation::Transform XForm) {
105 unsigned NumElements = ST->getElementTypes().size();
106 Transform.reserve(NumElements);
109 case SimpleStructMutation::SwapElements:
110 // The transformation to do is: just simply swap the elements
111 for (unsigned i = 0; i < NumElements; ++i)
112 Transform.push_back(NumElements-i-1);
115 case SimpleStructMutation::SortElements: {
116 vector<pair<unsigned, unsigned> > ElList;
118 // Build mapping from index to size
119 for (unsigned i = 0; i < NumElements; ++i)
121 std::make_pair(i, TD.getTypeSize(ST->getElementTypes()[i])));
123 sort(ElList.begin(), ElList.end(), ptr_fun(FirstLess));
125 for (unsigned i = 0; i < NumElements; ++i)
126 Transform.push_back(getIndex(ElList, i));
134 SimpleStructMutation::TransformsType
135 SimpleStructMutation::getTransforms(Module &, enum Transform XForm) {
136 // We need to know which types to modify, and which types we CAN'T modify
137 // TODO: Do symbol tables as well
139 // Get the results out of the analyzers...
140 FindUsedTypes &FUT = getAnalysis<FindUsedTypes>();
141 const set<const Type *> &UsedTypes = FUT.getTypes();
143 FindUnsafePointerTypes &FUPT = getAnalysis<FindUnsafePointerTypes>();
144 const set<PointerType*> &UnsafePTys = FUPT.getUnsafeTypes();
148 // Combine the two sets, weeding out non structure types. Closures in C++
149 // sure would be nice.
150 set<const StructType*> TypesToModify;
151 for (set<const Type *>::const_iterator I = UsedTypes.begin(),
152 E = UsedTypes.end(); I != E; ++I)
153 if (const StructType *ST = dyn_cast<StructType>(*I))
154 TypesToModify.insert(ST);
157 // Go through the Unsafe types and remove all types from TypesToModify that we
158 // are not allowed to modify, because that would be unsafe.
160 set<const Type*> ProcessedTypes;
161 for (set<PointerType*>::const_iterator I = UnsafePTys.begin(),
162 E = UnsafePTys.end(); I != E; ++I) {
163 //cerr << "Pruning type: " << *I << "\n";
164 PruneTypes(*I, TypesToModify, ProcessedTypes);
168 // Build up a set of structure types that we are going to modify, and
169 // information describing how to modify them.
170 std::map<const StructType*, vector<int> > Transforms;
172 for (set<const StructType*>::iterator I = TypesToModify.begin(),
173 E = TypesToModify.end(); I != E; ++I) {
174 const StructType *ST = *I;
176 vector<int> &Transform = Transforms[ST]; // Fill in the map directly
177 GetTransformation(TD, ST, Transform, XForm);
184 Pass *createSwapElementsPass(const TargetData &TD) {
185 return new SwapStructElements(TD);
187 Pass *createSortElementsPass(const TargetData &TD) {
188 return new SortStructElements(TD);
192 RegisterPass<SwapStructElements> X("swapstructs",
193 "Swap structure types around",
194 createSwapElementsPass);
195 RegisterPass<SortStructElements> Y("sortstructs",
196 "Sort structure elements by size",
197 createSortElementsPass);