blob: 022d6d822c5294b477347f92c5463e94aa9ae45a [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 Lattner04c85dc2002-01-21 07:52:35 +00009#include "llvm/Transforms/IPO/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 +000015#include <iostream>
16using std::vector;
17using std::set;
18using std::pair;
Chris Lattner7546c212001-11-10 07:28:25 +000019
Chris Lattnerbd0ef772002-02-26 21:46:54 +000020namespace {
Chris Lattner96c466b2002-04-29 14:57:45 +000021 struct SimpleStructMutation : public MutateStructTypes {
Chris Lattnere9754ef2002-07-23 18:03:11 +000022 enum Transform { SwapElements, SortElements };
23 const TargetData &TD;
24 SimpleStructMutation(const TargetData &td) : TD(td) {}
Chris Lattnerbd0ef772002-02-26 21:46:54 +000025
Chris Lattnere9754ef2002-07-23 18:03:11 +000026 virtual bool run(Module &M) = 0;
27
Chris Lattnerf57b8452002-04-27 06:56:12 +000028 // getAnalysisUsage - This function needs the results of the
Chris Lattnerbd0ef772002-02-26 21:46:54 +000029 // FindUsedTypes and FindUnsafePointerTypes analysis passes...
30 //
Chris Lattnerf57b8452002-04-27 06:56:12 +000031 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
Chris Lattner5f0eb8d2002-08-08 19:01:30 +000032 AU.addRequired<FindUsedTypes>();
33 AU.addRequired<FindUnsafePointerTypes>();
Chris Lattnerf57b8452002-04-27 06:56:12 +000034 MutateStructTypes::getAnalysisUsage(AU);
Chris Lattnerbd0ef772002-02-26 21:46:54 +000035 }
36
Chris Lattnere9754ef2002-07-23 18:03:11 +000037 protected:
Chris Lattner0b12b5f2002-06-25 16:13:21 +000038 TransformsType getTransforms(Module &M, enum Transform);
Chris Lattnerbd0ef772002-02-26 21:46:54 +000039 };
Chris Lattnere9754ef2002-07-23 18:03:11 +000040
41 struct SwapStructElements : public SimpleStructMutation {
42 SwapStructElements(const TargetData &TD) : SimpleStructMutation(TD) {}
43
44 virtual bool run(Module &M) {
45 setTransforms(getTransforms(M, SwapElements));
46 bool Changed = MutateStructTypes::run(M);
47 clearTransforms();
48 return Changed;
49 }
50 };
51
52 struct SortStructElements : public SimpleStructMutation {
53 SortStructElements(const TargetData &TD) : SimpleStructMutation(TD) {}
54
55 virtual bool run(Module &M) {
56 setTransforms(getTransforms(M, SortElements));
57 bool Changed = MutateStructTypes::run(M);
58 clearTransforms();
59 return Changed;
60 }
61 };
Chris Lattnerbd0ef772002-02-26 21:46:54 +000062} // end anonymous namespace
63
64
Chris Lattner697954c2002-01-20 22:54:45 +000065
Chris Lattner7546c212001-11-10 07:28:25 +000066// PruneTypes - Given a type Ty, make sure that neither it, or one of its
67// subtypes, occur in TypesToModify.
68//
69static 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);
73
74 // If the element is in TypesToModify, remove it now...
Chris Lattnerd5b48ca2001-11-14 11:02:49 +000075 if (const StructType *ST = dyn_cast<StructType>(Ty)) {
Chris Lattner7546c212001-11-10 07:28:25 +000076 TypesToModify.erase(ST); // This doesn't fail if the element isn't present
Chris Lattner697954c2002-01-20 22:54:45 +000077 std::cerr << "Unable to swap type: " << ST << "\n";
Chris Lattnerd5b48ca2001-11-14 11:02:49 +000078 }
Chris Lattner7546c212001-11-10 07:28:25 +000079
Chris Lattnerd5b48ca2001-11-14 11:02:49 +000080 // 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.
Chris Lattner7546c212001-11-10 07:28:25 +000083 //
84 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
Chris Lattnerd5b48ca2001-11-14 11:02:49 +000085 I != E; ++I) {
86 if (!isa<PointerType>(*I))
87 PruneTypes(*I, TypesToModify, ProcessedTypes);
88 }
Chris Lattner7546c212001-11-10 07:28:25 +000089}
90
Chris Lattner12739d92001-11-26 16:59:10 +000091static bool FirstLess(const pair<unsigned, unsigned> &LHS,
92 const pair<unsigned, unsigned> &RHS) {
93 return LHS.second < RHS.second;
94}
Chris Lattner7546c212001-11-10 07:28:25 +000095
Chris Lattner12739d92001-11-26 16:59:10 +000096static unsigned getIndex(const vector<pair<unsigned, unsigned> > &Vec,
97 unsigned Field) {
98 for (unsigned i = 0; ; ++i)
99 if (Vec[i].first == Field) return i;
100}
101
Chris Lattnere9754ef2002-07-23 18:03:11 +0000102static inline void GetTransformation(const TargetData &TD, const StructType *ST,
Chris Lattner12739d92001-11-26 16:59:10 +0000103 vector<int> &Transform,
Chris Lattner497c60c2002-05-07 18:12:18 +0000104 enum SimpleStructMutation::Transform XForm) {
Chris Lattner12739d92001-11-26 16:59:10 +0000105 unsigned NumElements = ST->getElementTypes().size();
106 Transform.reserve(NumElements);
107
108 switch (XForm) {
Chris Lattnerf4de63f2002-01-21 07:31:50 +0000109 case SimpleStructMutation::SwapElements:
Chris Lattner12739d92001-11-26 16:59:10 +0000110 // 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);
113 break;
114
Chris Lattnerf4de63f2002-01-21 07:31:50 +0000115 case SimpleStructMutation::SortElements: {
Chris Lattner12739d92001-11-26 16:59:10 +0000116 vector<pair<unsigned, unsigned> > ElList;
117
118 // Build mapping from index to size
119 for (unsigned i = 0; i < NumElements; ++i)
Chris Lattner697954c2002-01-20 22:54:45 +0000120 ElList.push_back(
121 std::make_pair(i, TD.getTypeSize(ST->getElementTypes()[i])));
Chris Lattner12739d92001-11-26 16:59:10 +0000122
123 sort(ElList.begin(), ElList.end(), ptr_fun(FirstLess));
124
125 for (unsigned i = 0; i < NumElements; ++i)
126 Transform.push_back(getIndex(ElList, i));
127
128 break;
129 }
130 }
131}
Chris Lattner7546c212001-11-10 07:28:25 +0000132
Chris Lattnerbd0ef772002-02-26 21:46:54 +0000133
Chris Lattnerf4de63f2002-01-21 07:31:50 +0000134SimpleStructMutation::TransformsType
Chris Lattner0b12b5f2002-06-25 16:13:21 +0000135 SimpleStructMutation::getTransforms(Module &, enum Transform XForm) {
Chris Lattner7546c212001-11-10 07:28:25 +0000136 // We need to know which types to modify, and which types we CAN'T modify
Chris Lattner793c6b82002-01-31 00:45:11 +0000137 // TODO: Do symbol tables as well
Chris Lattner7546c212001-11-10 07:28:25 +0000138
139 // Get the results out of the analyzers...
Chris Lattner793c6b82002-01-31 00:45:11 +0000140 FindUsedTypes &FUT = getAnalysis<FindUsedTypes>();
141 const set<const Type *> &UsedTypes = FUT.getTypes();
142
143 FindUnsafePointerTypes &FUPT = getAnalysis<FindUnsafePointerTypes>();
144 const set<PointerType*> &UnsafePTys = FUPT.getUnsafeTypes();
145
Chris Lattner7546c212001-11-10 07:28:25 +0000146
147
Chris Lattnerd5b48ca2001-11-14 11:02:49 +0000148 // Combine the two sets, weeding out non structure types. Closures in C++
149 // sure would be nice.
Chris Lattner7546c212001-11-10 07:28:25 +0000150 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);
155
156
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.
159 //
160 set<const Type*> ProcessedTypes;
161 for (set<PointerType*>::const_iterator I = UnsafePTys.begin(),
Chris Lattnerd5b48ca2001-11-14 11:02:49 +0000162 E = UnsafePTys.end(); I != E; ++I) {
Chris Lattner697954c2002-01-20 22:54:45 +0000163 //cerr << "Pruning type: " << *I << "\n";
Chris Lattner7546c212001-11-10 07:28:25 +0000164 PruneTypes(*I, TypesToModify, ProcessedTypes);
Chris Lattnerd5b48ca2001-11-14 11:02:49 +0000165 }
Chris Lattner7546c212001-11-10 07:28:25 +0000166
167
168 // Build up a set of structure types that we are going to modify, and
169 // information describing how to modify them.
Chris Lattner697954c2002-01-20 22:54:45 +0000170 std::map<const StructType*, vector<int> > Transforms;
Chris Lattner7546c212001-11-10 07:28:25 +0000171
172 for (set<const StructType*>::iterator I = TypesToModify.begin(),
173 E = TypesToModify.end(); I != E; ++I) {
174 const StructType *ST = *I;
Chris Lattner7546c212001-11-10 07:28:25 +0000175
176 vector<int> &Transform = Transforms[ST]; // Fill in the map directly
Chris Lattnere9754ef2002-07-23 18:03:11 +0000177 GetTransformation(TD, ST, Transform, XForm);
Chris Lattner7546c212001-11-10 07:28:25 +0000178 }
179
Chris Lattner12739d92001-11-26 16:59:10 +0000180 return Transforms;
Chris Lattner7546c212001-11-10 07:28:25 +0000181}
182
Chris Lattner793c6b82002-01-31 00:45:11 +0000183
Chris Lattnere9754ef2002-07-23 18:03:11 +0000184Pass *createSwapElementsPass(const TargetData &TD) {
185 return new SwapStructElements(TD);
Chris Lattner793c6b82002-01-31 00:45:11 +0000186}
Chris Lattnere9754ef2002-07-23 18:03:11 +0000187Pass *createSortElementsPass(const TargetData &TD) {
188 return new SortStructElements(TD);
Chris Lattnerbd0ef772002-02-26 21:46:54 +0000189}
190
Chris Lattnere9754ef2002-07-23 18:03:11 +0000191namespace {
Chris Lattner1e435162002-07-26 21:12:44 +0000192 RegisterOpt<SwapStructElements> X("swapstructs",
193 "Swap structure types around",
194 createSwapElementsPass);
195 RegisterOpt<SortStructElements> Y("sortstructs",
196 "Sort structure elements by size",
197 createSortElementsPass);
Chris Lattnere9754ef2002-07-23 18:03:11 +0000198}