1 //===- SimpleStructMutation.cpp - Swap structure elements around ----------===//
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 does a simple transformation that swaps all of the elements of the
11 // struct types in the program around.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/IPO.h"
16 #include "llvm/Transforms/MutateStructTypes.h"
17 #include "llvm/Analysis/FindUsedTypes.h"
18 #include "llvm/Analysis/FindUnsafePointerTypes.h"
19 #include "llvm/Target/TargetData.h"
20 #include "llvm/DerivedTypes.h"
25 struct SimpleStructMutation : public MutateStructTypes {
26 enum Transform { SwapElements, SortElements };
28 virtual bool run(Module &M) = 0;
30 // getAnalysisUsage - This function needs the results of the
31 // FindUsedTypes and FindUnsafePointerTypes analysis passes...
33 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
34 AU.addRequired<TargetData>();
35 AU.addRequired<FindUsedTypes>();
36 AU.addRequired<FindUnsafePointerTypes>();
37 MutateStructTypes::getAnalysisUsage(AU);
41 TransformsType getTransforms(Module &M, enum Transform);
44 struct SwapStructElements : public SimpleStructMutation {
45 virtual bool run(Module &M) {
46 setTransforms(getTransforms(M, SwapElements));
47 bool Changed = MutateStructTypes::run(M);
53 struct SortStructElements : public SimpleStructMutation {
54 virtual bool run(Module &M) {
55 setTransforms(getTransforms(M, SortElements));
56 bool Changed = MutateStructTypes::run(M);
62 RegisterOpt<SwapStructElements> X("swapstructs",
63 "Swap structure types around");
64 RegisterOpt<SortStructElements> Y("sortstructs",
65 "Sort structure elements by size");
66 } // end anonymous namespace
68 Pass *createSwapElementsPass() { return new SwapStructElements(); }
69 Pass *createSortElementsPass() { return new SortStructElements(); }
72 // PruneTypes - Given a type Ty, make sure that neither it, or one of its
73 // subtypes, occur in TypesToModify.
75 static void PruneTypes(const Type *Ty,
76 std::set<const StructType*> &TypesToModify,
77 std::set<const Type*> &ProcessedTypes) {
78 if (ProcessedTypes.count(Ty)) return; // Already been checked
79 ProcessedTypes.insert(Ty);
81 // If the element is in TypesToModify, remove it now...
82 if (const StructType *ST = dyn_cast<StructType>(Ty)) {
83 TypesToModify.erase(ST); // This doesn't fail if the element isn't present
84 std::cerr << "Unable to swap type: " << ST << "\n";
87 // Remove all types that this type contains as well... do not remove types
88 // that are referenced only through pointers, because we depend on the size of
89 // the pointer, not on what the structure points to.
91 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
93 if (!isa<PointerType>(I->get()))
94 PruneTypes(*I, TypesToModify, ProcessedTypes);
98 static bool FirstLess(const std::pair<unsigned, unsigned> &LHS,
99 const std::pair<unsigned, unsigned> &RHS) {
100 return LHS.second < RHS.second;
103 static unsigned getIndex(const std::vector<std::pair<unsigned, unsigned> > &Vec,
105 for (unsigned i = 0; ; ++i)
106 if (Vec[i].first == Field) return i;
109 static inline void GetTransformation(const TargetData &TD, const StructType *ST,
110 std::vector<int> &Transform,
111 enum SimpleStructMutation::Transform XForm) {
112 unsigned NumElements = ST->getNumElements();
113 Transform.reserve(NumElements);
116 case SimpleStructMutation::SwapElements:
117 // The transformation to do is: just simply swap the elements
118 for (unsigned i = 0; i < NumElements; ++i)
119 Transform.push_back(NumElements-i-1);
122 case SimpleStructMutation::SortElements: {
123 std::vector<std::pair<unsigned, unsigned> > ElList;
125 // Build mapping from index to size
126 for (unsigned i = 0; i < NumElements; ++i)
127 ElList.push_back(std::make_pair(i,TD.getTypeSize(ST->getElementType(i))));
129 sort(ElList.begin(), ElList.end(), ptr_fun(FirstLess));
131 for (unsigned i = 0; i < NumElements; ++i)
132 Transform.push_back(getIndex(ElList, i));
140 SimpleStructMutation::TransformsType
141 SimpleStructMutation::getTransforms(Module &, enum Transform XForm) {
142 // We need to know which types to modify, and which types we CAN'T modify
143 // TODO: Do symbol tables as well
145 // Get the results out of the analyzers...
146 FindUsedTypes &FUT = getAnalysis<FindUsedTypes>();
147 const std::set<const Type *> &UsedTypes = FUT.getTypes();
149 FindUnsafePointerTypes &FUPT = getAnalysis<FindUnsafePointerTypes>();
150 const std::set<PointerType*> &UnsafePTys = FUPT.getUnsafeTypes();
153 // Combine the two sets, weeding out non structure types. Closures in C++
154 // sure would be nice.
155 std::set<const StructType*> TypesToModify;
156 for (std::set<const Type *>::const_iterator I = UsedTypes.begin(),
157 E = UsedTypes.end(); I != E; ++I)
158 if (const StructType *ST = dyn_cast<StructType>(*I))
159 TypesToModify.insert(ST);
162 // Go through the Unsafe types and remove all types from TypesToModify that we
163 // are not allowed to modify, because that would be unsafe.
165 std::set<const Type*> ProcessedTypes;
166 for (std::set<PointerType*>::const_iterator I = UnsafePTys.begin(),
167 E = UnsafePTys.end(); I != E; ++I) {
168 //cerr << "Pruning type: " << *I << "\n";
169 PruneTypes(*I, TypesToModify, ProcessedTypes);
173 // Build up a set of structure types that we are going to modify, and
174 // information describing how to modify them.
175 std::map<const StructType*, std::vector<int> > Transforms;
176 TargetData &TD = getAnalysis<TargetData>();
178 for (std::set<const StructType*>::iterator I = TypesToModify.begin(),
179 E = TypesToModify.end(); I != E; ++I) {
180 const StructType *ST = *I;
182 std::vector<int> &Transform = Transforms[ST]; // Fill in the map directly
183 GetTransformation(TD, ST, Transform, XForm);