Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 1 | //===- SwapStructContents.cpp - Swap structure elements around ---*- C++ -*--=// |
| 2 | // |
| 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 | |
| 8 | |
| 9 | #include "llvm/Transforms/SwapStructContents.h" |
| 10 | #include "llvm/Transforms/MutateStructTypes.h" |
| 11 | #include "llvm/Analysis/FindUsedTypes.h" |
| 12 | #include "llvm/Analysis/FindUnsafePointerTypes.h" |
Chris Lattner | 12739d9 | 2001-11-26 16:59:10 +0000 | [diff] [blame] | 13 | #include "TransformInternals.h" |
| 14 | #include <algorithm> |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 15 | |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 16 | #include "llvm/Assembly/Writer.h" |
| 17 | |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 18 | // PruneTypes - Given a type Ty, make sure that neither it, or one of its |
| 19 | // subtypes, occur in TypesToModify. |
| 20 | // |
| 21 | static void PruneTypes(const Type *Ty, set<const StructType*> &TypesToModify, |
| 22 | set<const Type*> &ProcessedTypes) { |
| 23 | if (ProcessedTypes.count(Ty)) return; // Already been checked |
| 24 | ProcessedTypes.insert(Ty); |
| 25 | |
| 26 | // If the element is in TypesToModify, remove it now... |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 27 | if (const StructType *ST = dyn_cast<StructType>(Ty)) { |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 28 | TypesToModify.erase(ST); // This doesn't fail if the element isn't present |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 29 | cerr << "Unable to swap type: " << ST << endl; |
| 30 | } |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 31 | |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 32 | // Remove all types that this type contains as well... do not remove types |
| 33 | // that are referenced only through pointers, because we depend on the size of |
| 34 | // the pointer, not on what the structure points to. |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 35 | // |
| 36 | for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 37 | I != E; ++I) { |
| 38 | if (!isa<PointerType>(*I)) |
| 39 | PruneTypes(*I, TypesToModify, ProcessedTypes); |
| 40 | } |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 41 | } |
| 42 | |
Chris Lattner | 12739d9 | 2001-11-26 16:59:10 +0000 | [diff] [blame] | 43 | static bool FirstLess(const pair<unsigned, unsigned> &LHS, |
| 44 | const pair<unsigned, unsigned> &RHS) { |
| 45 | return LHS.second < RHS.second; |
| 46 | } |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 47 | |
Chris Lattner | 12739d9 | 2001-11-26 16:59:10 +0000 | [diff] [blame] | 48 | static unsigned getIndex(const vector<pair<unsigned, unsigned> > &Vec, |
| 49 | unsigned Field) { |
| 50 | for (unsigned i = 0; ; ++i) |
| 51 | if (Vec[i].first == Field) return i; |
| 52 | } |
| 53 | |
| 54 | static inline void GetTransformation(const StructType *ST, |
| 55 | vector<int> &Transform, |
| 56 | enum PrebuiltStructMutation::Transform XForm) { |
| 57 | unsigned NumElements = ST->getElementTypes().size(); |
| 58 | Transform.reserve(NumElements); |
| 59 | |
| 60 | switch (XForm) { |
| 61 | case PrebuiltStructMutation::SwapElements: |
| 62 | // The transformation to do is: just simply swap the elements |
| 63 | for (unsigned i = 0; i < NumElements; ++i) |
| 64 | Transform.push_back(NumElements-i-1); |
| 65 | break; |
| 66 | |
| 67 | case PrebuiltStructMutation::SortElements: { |
| 68 | vector<pair<unsigned, unsigned> > ElList; |
| 69 | |
| 70 | // Build mapping from index to size |
| 71 | for (unsigned i = 0; i < NumElements; ++i) |
| 72 | ElList.push_back(make_pair(i, TD.getTypeSize(ST->getElementTypes()[i]))); |
| 73 | |
| 74 | sort(ElList.begin(), ElList.end(), ptr_fun(FirstLess)); |
| 75 | |
| 76 | for (unsigned i = 0; i < NumElements; ++i) |
| 77 | Transform.push_back(getIndex(ElList, i)); |
| 78 | |
| 79 | break; |
| 80 | } |
| 81 | } |
| 82 | } |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 83 | |
| 84 | // doPassInitialization - This does all of the work of the pass |
| 85 | // |
Chris Lattner | 12739d9 | 2001-11-26 16:59:10 +0000 | [diff] [blame] | 86 | PrebuiltStructMutation::TransformsType |
| 87 | PrebuiltStructMutation::getTransforms(Module *M, enum Transform XForm) { |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 88 | // We need to know which types to modify, and which types we CAN'T modify |
| 89 | FindUsedTypes FUT/*(true)*/; // TODO: Do symbol tables as well |
| 90 | FindUnsafePointerTypes FUPT; |
| 91 | |
| 92 | // Simutaneously find all of the types used, and all of the types that aren't |
| 93 | // safe. |
| 94 | // |
| 95 | vector<Pass*> Analyses; |
| 96 | Analyses.push_back(&FUT); |
| 97 | Analyses.push_back(&FUPT); |
| 98 | Pass::runAllPasses(M, Analyses); // Do analyses |
| 99 | |
| 100 | |
| 101 | // Get the results out of the analyzers... |
| 102 | const set<PointerType*> &UnsafePTys = FUPT.getUnsafeTypes(); |
| 103 | const set<const Type *> &UsedTypes = FUT.getTypes(); |
| 104 | |
| 105 | |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 106 | // Combine the two sets, weeding out non structure types. Closures in C++ |
| 107 | // sure would be nice. |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 108 | set<const StructType*> TypesToModify; |
| 109 | for (set<const Type *>::const_iterator I = UsedTypes.begin(), |
| 110 | E = UsedTypes.end(); I != E; ++I) |
| 111 | if (const StructType *ST = dyn_cast<StructType>(*I)) |
| 112 | TypesToModify.insert(ST); |
| 113 | |
| 114 | |
| 115 | // Go through the Unsafe types and remove all types from TypesToModify that we |
| 116 | // are not allowed to modify, because that would be unsafe. |
| 117 | // |
| 118 | set<const Type*> ProcessedTypes; |
| 119 | for (set<PointerType*>::const_iterator I = UnsafePTys.begin(), |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 120 | E = UnsafePTys.end(); I != E; ++I) { |
Chris Lattner | e81dc1d | 2001-11-26 19:14:16 +0000 | [diff] [blame] | 121 | //cerr << "Pruning type: " << *I << endl; |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 122 | PruneTypes(*I, TypesToModify, ProcessedTypes); |
Chris Lattner | d5b48ca | 2001-11-14 11:02:49 +0000 | [diff] [blame] | 123 | } |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 124 | |
| 125 | |
| 126 | // Build up a set of structure types that we are going to modify, and |
| 127 | // information describing how to modify them. |
| 128 | map<const StructType*, vector<int> > Transforms; |
| 129 | |
| 130 | for (set<const StructType*>::iterator I = TypesToModify.begin(), |
| 131 | E = TypesToModify.end(); I != E; ++I) { |
| 132 | const StructType *ST = *I; |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 133 | |
| 134 | vector<int> &Transform = Transforms[ST]; // Fill in the map directly |
Chris Lattner | 12739d9 | 2001-11-26 16:59:10 +0000 | [diff] [blame] | 135 | GetTransformation(ST, Transform, XForm); |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 136 | } |
| 137 | |
Chris Lattner | 12739d9 | 2001-11-26 16:59:10 +0000 | [diff] [blame] | 138 | return Transforms; |
Chris Lattner | 7546c21 | 2001-11-10 07:28:25 +0000 | [diff] [blame] | 139 | } |
| 140 | |