blob: ec1981929e82e34e0e71dbc9850a1292a7e25a98 [file] [log] [blame]
Chris Lattnerf57b8452002-04-27 06:56:12 +00001//===- SimpleStructMutation.cpp - Swap structure elements around -*- C++ -*--=//
Chris Lattner7546c212001-11-10 07:28:25 +00002//
3// This pass does a simple transformation that swaps all of the elements of the
4// struct types in the program around.
5//
6//===----------------------------------------------------------------------===//
7
Chris Lattner568ddab2002-07-24 17:12:05 +00008#include "llvm/Transforms/IPO.h"
Chris Lattnere6aa3732002-11-19 20:49:40 +00009#include "llvm/Transforms/MutateStructTypes.h"
Chris Lattner7546c212001-11-10 07:28:25 +000010#include "llvm/Analysis/FindUsedTypes.h"
11#include "llvm/Analysis/FindUnsafePointerTypes.h"
Chris Lattner497c60c2002-05-07 18:12:18 +000012#include "llvm/Target/TargetData.h"
13#include "llvm/DerivedTypes.h"
Chris Lattner12739d92001-11-26 16:59:10 +000014#include <algorithm>
Chris Lattner697954c2002-01-20 22:54:45 +000015using std::vector;
16using std::set;
17using std::pair;
Chris Lattner7546c212001-11-10 07:28:25 +000018
Chris Lattnerbd0ef772002-02-26 21:46:54 +000019namespace {
Chris Lattner96c466b2002-04-29 14:57:45 +000020 struct SimpleStructMutation : public MutateStructTypes {
Chris Lattnere9754ef2002-07-23 18:03:11 +000021 enum Transform { SwapElements, SortElements };
Chris Lattnerbd0ef772002-02-26 21:46:54 +000022
Chris Lattnere9754ef2002-07-23 18:03:11 +000023 virtual bool run(Module &M) = 0;
24
Chris Lattnerf57b8452002-04-27 06:56:12 +000025 // getAnalysisUsage - This function needs the results of the
Chris Lattnerbd0ef772002-02-26 21:46:54 +000026 // FindUsedTypes and FindUnsafePointerTypes analysis passes...
27 //
Chris Lattnerf57b8452002-04-27 06:56:12 +000028 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
Chris Lattner3a15d702002-09-26 00:17:21 +000029 AU.addRequired<TargetData>();
Chris Lattner5f0eb8d2002-08-08 19:01:30 +000030 AU.addRequired<FindUsedTypes>();
31 AU.addRequired<FindUnsafePointerTypes>();
Chris Lattnerf57b8452002-04-27 06:56:12 +000032 MutateStructTypes::getAnalysisUsage(AU);
Chris Lattnerbd0ef772002-02-26 21:46:54 +000033 }
34
Chris Lattnere9754ef2002-07-23 18:03:11 +000035 protected:
Chris Lattner0b12b5f2002-06-25 16:13:21 +000036 TransformsType getTransforms(Module &M, enum Transform);
Chris Lattnerbd0ef772002-02-26 21:46:54 +000037 };
Chris Lattnere9754ef2002-07-23 18:03:11 +000038
39 struct SwapStructElements : public SimpleStructMutation {
Chris Lattnere9754ef2002-07-23 18:03:11 +000040 virtual bool run(Module &M) {
41 setTransforms(getTransforms(M, SwapElements));
42 bool Changed = MutateStructTypes::run(M);
43 clearTransforms();
44 return Changed;
45 }
46 };
47
48 struct SortStructElements : public SimpleStructMutation {
Chris Lattnere9754ef2002-07-23 18:03:11 +000049 virtual bool run(Module &M) {
50 setTransforms(getTransforms(M, SortElements));
51 bool Changed = MutateStructTypes::run(M);
52 clearTransforms();
53 return Changed;
54 }
55 };
Chris Lattner3a15d702002-09-26 00:17:21 +000056
57 RegisterOpt<SwapStructElements> X("swapstructs",
58 "Swap structure types around");
59 RegisterOpt<SortStructElements> Y("sortstructs",
60 "Sort structure elements by size");
Chris Lattnerbd0ef772002-02-26 21:46:54 +000061} // end anonymous namespace
62
Chris Lattner3a15d702002-09-26 00:17:21 +000063Pass *createSwapElementsPass() { return new SwapStructElements(); }
64Pass *createSortElementsPass() { return new SortStructElements(); }
Chris Lattnerbd0ef772002-02-26 21:46:54 +000065
Chris Lattner697954c2002-01-20 22:54:45 +000066
Chris Lattner7546c212001-11-10 07:28:25 +000067// PruneTypes - Given a type Ty, make sure that neither it, or one of its
68// subtypes, occur in TypesToModify.
69//
70static void PruneTypes(const Type *Ty, set<const StructType*> &TypesToModify,
71 set<const Type*> &ProcessedTypes) {
72 if (ProcessedTypes.count(Ty)) return; // Already been checked
73 ProcessedTypes.insert(Ty);
74
75 // If the element is in TypesToModify, remove it now...
Chris Lattnerd5b48ca2001-11-14 11:02:49 +000076 if (const StructType *ST = dyn_cast<StructType>(Ty)) {
Chris Lattner7546c212001-11-10 07:28:25 +000077 TypesToModify.erase(ST); // This doesn't fail if the element isn't present
Chris Lattner697954c2002-01-20 22:54:45 +000078 std::cerr << "Unable to swap type: " << ST << "\n";
Chris Lattnerd5b48ca2001-11-14 11:02:49 +000079 }
Chris Lattner7546c212001-11-10 07:28:25 +000080
Chris Lattnerd5b48ca2001-11-14 11:02:49 +000081 // Remove all types that this type contains as well... do not remove types
82 // that are referenced only through pointers, because we depend on the size of
83 // the pointer, not on what the structure points to.
Chris Lattner7546c212001-11-10 07:28:25 +000084 //
85 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
Chris Lattnerd5b48ca2001-11-14 11:02:49 +000086 I != E; ++I) {
87 if (!isa<PointerType>(*I))
88 PruneTypes(*I, TypesToModify, ProcessedTypes);
89 }
Chris Lattner7546c212001-11-10 07:28:25 +000090}
91
Chris Lattner12739d92001-11-26 16:59:10 +000092static bool FirstLess(const pair<unsigned, unsigned> &LHS,
93 const pair<unsigned, unsigned> &RHS) {
94 return LHS.second < RHS.second;
95}
Chris Lattner7546c212001-11-10 07:28:25 +000096
Chris Lattner12739d92001-11-26 16:59:10 +000097static unsigned getIndex(const vector<pair<unsigned, unsigned> > &Vec,
98 unsigned Field) {
99 for (unsigned i = 0; ; ++i)
100 if (Vec[i].first == Field) return i;
101}
102
Chris Lattnere9754ef2002-07-23 18:03:11 +0000103static inline void GetTransformation(const TargetData &TD, const StructType *ST,
Chris Lattner12739d92001-11-26 16:59:10 +0000104 vector<int> &Transform,
Chris Lattner497c60c2002-05-07 18:12:18 +0000105 enum SimpleStructMutation::Transform XForm) {
Chris Lattner12739d92001-11-26 16:59:10 +0000106 unsigned NumElements = ST->getElementTypes().size();
107 Transform.reserve(NumElements);
108
109 switch (XForm) {
Chris Lattnerf4de63f2002-01-21 07:31:50 +0000110 case SimpleStructMutation::SwapElements:
Chris Lattner12739d92001-11-26 16:59:10 +0000111 // The transformation to do is: just simply swap the elements
112 for (unsigned i = 0; i < NumElements; ++i)
113 Transform.push_back(NumElements-i-1);
114 break;
115
Chris Lattnerf4de63f2002-01-21 07:31:50 +0000116 case SimpleStructMutation::SortElements: {
Chris Lattner12739d92001-11-26 16:59:10 +0000117 vector<pair<unsigned, unsigned> > ElList;
118
119 // Build mapping from index to size
120 for (unsigned i = 0; i < NumElements; ++i)
Chris Lattner697954c2002-01-20 22:54:45 +0000121 ElList.push_back(
122 std::make_pair(i, TD.getTypeSize(ST->getElementTypes()[i])));
Chris Lattner12739d92001-11-26 16:59:10 +0000123
124 sort(ElList.begin(), ElList.end(), ptr_fun(FirstLess));
125
126 for (unsigned i = 0; i < NumElements; ++i)
127 Transform.push_back(getIndex(ElList, i));
128
129 break;
130 }
131 }
132}
Chris Lattner7546c212001-11-10 07:28:25 +0000133
Chris Lattnerbd0ef772002-02-26 21:46:54 +0000134
Chris Lattnerf4de63f2002-01-21 07:31:50 +0000135SimpleStructMutation::TransformsType
Chris Lattner0b12b5f2002-06-25 16:13:21 +0000136 SimpleStructMutation::getTransforms(Module &, enum Transform XForm) {
Chris Lattner7546c212001-11-10 07:28:25 +0000137 // We need to know which types to modify, and which types we CAN'T modify
Chris Lattner793c6b82002-01-31 00:45:11 +0000138 // TODO: Do symbol tables as well
Chris Lattner7546c212001-11-10 07:28:25 +0000139
140 // Get the results out of the analyzers...
Chris Lattner793c6b82002-01-31 00:45:11 +0000141 FindUsedTypes &FUT = getAnalysis<FindUsedTypes>();
142 const set<const Type *> &UsedTypes = FUT.getTypes();
143
144 FindUnsafePointerTypes &FUPT = getAnalysis<FindUnsafePointerTypes>();
145 const set<PointerType*> &UnsafePTys = FUPT.getUnsafeTypes();
146
Chris Lattner7546c212001-11-10 07:28:25 +0000147
148
Chris Lattnerd5b48ca2001-11-14 11:02:49 +0000149 // Combine the two sets, weeding out non structure types. Closures in C++
150 // sure would be nice.
Chris Lattner7546c212001-11-10 07:28:25 +0000151 set<const StructType*> TypesToModify;
152 for (set<const Type *>::const_iterator I = UsedTypes.begin(),
153 E = UsedTypes.end(); I != E; ++I)
154 if (const StructType *ST = dyn_cast<StructType>(*I))
155 TypesToModify.insert(ST);
156
157
158 // Go through the Unsafe types and remove all types from TypesToModify that we
159 // are not allowed to modify, because that would be unsafe.
160 //
161 set<const Type*> ProcessedTypes;
162 for (set<PointerType*>::const_iterator I = UnsafePTys.begin(),
Chris Lattnerd5b48ca2001-11-14 11:02:49 +0000163 E = UnsafePTys.end(); I != E; ++I) {
Chris Lattner697954c2002-01-20 22:54:45 +0000164 //cerr << "Pruning type: " << *I << "\n";
Chris Lattner7546c212001-11-10 07:28:25 +0000165 PruneTypes(*I, TypesToModify, ProcessedTypes);
Chris Lattnerd5b48ca2001-11-14 11:02:49 +0000166 }
Chris Lattner7546c212001-11-10 07:28:25 +0000167
168
169 // Build up a set of structure types that we are going to modify, and
170 // information describing how to modify them.
Chris Lattner697954c2002-01-20 22:54:45 +0000171 std::map<const StructType*, vector<int> > Transforms;
Chris Lattner3a15d702002-09-26 00:17:21 +0000172 TargetData &TD = getAnalysis<TargetData>();
Chris Lattner7546c212001-11-10 07:28:25 +0000173
174 for (set<const StructType*>::iterator I = TypesToModify.begin(),
175 E = TypesToModify.end(); I != E; ++I) {
176 const StructType *ST = *I;
Chris Lattner7546c212001-11-10 07:28:25 +0000177
178 vector<int> &Transform = Transforms[ST]; // Fill in the map directly
Chris Lattnere9754ef2002-07-23 18:03:11 +0000179 GetTransformation(TD, ST, Transform, XForm);
Chris Lattner7546c212001-11-10 07:28:25 +0000180 }
181
Chris Lattner12739d92001-11-26 16:59:10 +0000182 return Transforms;
Chris Lattner7546c212001-11-10 07:28:25 +0000183}