lib/Transforms/IPO/SimpleStructMutation.cpp

   1 //===- SimpleStructMutation.cpp - Swap structure elements around ----------===//
   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 #include "llvm/Transforms/IPO.h"
   9 #include "llvm/Transforms/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"
  14 #include <algorithm>
  15 using std::vector;
  16 using std::set;
  17 using std::pair;
  18
  19 namespace {
  20   struct SimpleStructMutation : public MutateStructTypes {
  21     enum Transform { SwapElements, SortElements };
  22
  23     virtual bool run(Module &M)  = 0;
  24
  25     // getAnalysisUsage - This function needs the results of the
  26     // FindUsedTypes and FindUnsafePointerTypes analysis passes...
  27     //
  28     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  29       AU.addRequired<TargetData>();
  30       AU.addRequired<FindUsedTypes>();
  31       AU.addRequired<FindUnsafePointerTypes>();
  32       MutateStructTypes::getAnalysisUsage(AU);
  33     }
  34
  35   protected:
  36     TransformsType getTransforms(Module &M, enum Transform);
  37   };
  38
  39   struct SwapStructElements : public SimpleStructMutation {
  40     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 {
  49     virtual bool run(Module &M) {
  50       setTransforms(getTransforms(M, SortElements));
  51       bool Changed = MutateStructTypes::run(M);
  52       clearTransforms();
  53       return Changed;
  54     }
  55   };
  56
  57   RegisterOpt<SwapStructElements> X("swapstructs",
  58                                     "Swap structure types around");
  59   RegisterOpt<SortStructElements> Y("sortstructs",
  60                                     "Sort structure elements by size");
  61 }  // end anonymous namespace
  62
  63 Pass *createSwapElementsPass() { return new SwapStructElements(); }
  64 Pass *createSortElementsPass() { return new SortStructElements(); }
  65
  66
  67 // PruneTypes - Given a type Ty, make sure that neither it, or one of its
  68 // subtypes, occur in TypesToModify.
  69 //
  70 static 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...
  76   if (const StructType *ST = dyn_cast<StructType>(Ty)) {
  77     TypesToModify.erase(ST);  // This doesn't fail if the element isn't present
  78     std::cerr << "Unable to swap type: " << ST << "\n";
  79   }
  80
  81   // 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.
  84   //
  85   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
  86        I != E; ++I) {
  87     if (!isa<PointerType>(*I))
  88       PruneTypes(*I, TypesToModify, ProcessedTypes);
  89   }
  90 }
  91
  92 static bool FirstLess(const pair<unsigned, unsigned> &LHS,
  93                       const pair<unsigned, unsigned> &RHS) {
  94   return LHS.second < RHS.second;
  95 }
  96
  97 static 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
 103 static inline void GetTransformation(const TargetData &TD, const StructType *ST,
 104                                      vector<int> &Transform,
 105                                    enum SimpleStructMutation::Transform XForm) {
 106   unsigned NumElements = ST->getElementTypes().size();
 107   Transform.reserve(NumElements);
 108
 109   switch (XForm) {
 110   case SimpleStructMutation::SwapElements:
 111     // 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
 116   case SimpleStructMutation::SortElements: {
 117     vector<pair<unsigned, unsigned> > ElList;
 118
 119     // Build mapping from index to size
 120     for (unsigned i = 0; i < NumElements; ++i)
 121       ElList.push_back(
 122               std::make_pair(i, TD.getTypeSize(ST->getElementTypes()[i])));
 123
 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 }
 133
 134
 135 SimpleStructMutation::TransformsType
 136   SimpleStructMutation::getTransforms(Module &, enum Transform XForm) {
 137   // We need to know which types to modify, and which types we CAN'T modify
 138   // TODO: Do symbol tables as well
 139
 140   // Get the results out of the analyzers...
 141   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
 147
 148
 149   // Combine the two sets, weeding out non structure types.  Closures in C++
 150   // sure would be nice.
 151   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(),
 163          E = UnsafePTys.end(); I != E; ++I) {
 164     //cerr << "Pruning type: " << *I << "\n";
 165     PruneTypes(*I, TypesToModify, ProcessedTypes);
 166   }
 167
 168
 169   // Build up a set of structure types that we are going to modify, and
 170   // information describing how to modify them.
 171   std::map<const StructType*, vector<int> > Transforms;
 172   TargetData &TD = getAnalysis<TargetData>();
 173
 174   for (set<const StructType*>::iterator I = TypesToModify.begin(),
 175          E = TypesToModify.end(); I != E; ++I) {
 176     const StructType *ST = *I;
 177
 178     vector<int> &Transform = Transforms[ST];  // Fill in the map directly
 179     GetTransformation(TD, ST, Transform, XForm);
 180   }
 181
 182   return Transforms;
 183 }