lib/Transforms/IPO/SimpleStructMutation.cpp

   1 //===- SimpleStructMutation.cpp - Swap structure elements around ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass does a simple transformation that swaps all of the elements of the
  11 // struct types in the program around.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  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"
  21 #include <algorithm>
  22 using std::vector;
  23 using std::set;
  24 using std::pair;
  25
  26 namespace {
  27   struct SimpleStructMutation : public MutateStructTypes {
  28     enum Transform { SwapElements, SortElements };
  29
  30     virtual bool run(Module &M)  = 0;
  31
  32     // getAnalysisUsage - This function needs the results of the
  33     // FindUsedTypes and FindUnsafePointerTypes analysis passes...
  34     //
  35     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  36       AU.addRequired<TargetData>();
  37       AU.addRequired<FindUsedTypes>();
  38       AU.addRequired<FindUnsafePointerTypes>();
  39       MutateStructTypes::getAnalysisUsage(AU);
  40     }
  41
  42   protected:
  43     TransformsType getTransforms(Module &M, enum Transform);
  44   };
  45
  46   struct SwapStructElements : public SimpleStructMutation {
  47     virtual bool run(Module &M) {
  48       setTransforms(getTransforms(M, SwapElements));
  49       bool Changed = MutateStructTypes::run(M);
  50       clearTransforms();
  51       return Changed;
  52     }
  53   };
  54
  55   struct SortStructElements : public SimpleStructMutation {
  56     virtual bool run(Module &M) {
  57       setTransforms(getTransforms(M, SortElements));
  58       bool Changed = MutateStructTypes::run(M);
  59       clearTransforms();
  60       return Changed;
  61     }
  62   };
  63
  64   RegisterOpt<SwapStructElements> X("swapstructs",
  65                                     "Swap structure types around");
  66   RegisterOpt<SortStructElements> Y("sortstructs",
  67                                     "Sort structure elements by size");
  68 }  // end anonymous namespace
  69
  70 Pass *createSwapElementsPass() { return new SwapStructElements(); }
  71 Pass *createSortElementsPass() { return new SortStructElements(); }
  72
  73
  74 // PruneTypes - Given a type Ty, make sure that neither it, or one of its
  75 // subtypes, occur in TypesToModify.
  76 //
  77 static void PruneTypes(const Type *Ty, set<const StructType*> &TypesToModify,
  78                        set<const Type*> &ProcessedTypes) {
  79   if (ProcessedTypes.count(Ty)) return;  // Already been checked
  80   ProcessedTypes.insert(Ty);
  81
  82   // If the element is in TypesToModify, remove it now...
  83   if (const StructType *ST = dyn_cast<StructType>(Ty)) {
  84     TypesToModify.erase(ST);  // This doesn't fail if the element isn't present
  85     std::cerr << "Unable to swap type: " << ST << "\n";
  86   }
  87
  88   // Remove all types that this type contains as well... do not remove types
  89   // that are referenced only through pointers, because we depend on the size of
  90   // the pointer, not on what the structure points to.
  91   //
  92   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
  93        I != E; ++I) {
  94     if (!isa<PointerType>(*I))
  95       PruneTypes(*I, TypesToModify, ProcessedTypes);
  96   }
  97 }
  98
  99 static bool FirstLess(const pair<unsigned, unsigned> &LHS,
 100                       const pair<unsigned, unsigned> &RHS) {
 101   return LHS.second < RHS.second;
 102 }
 103
 104 static unsigned getIndex(const vector<pair<unsigned, unsigned> > &Vec,
 105                          unsigned Field) {
 106   for (unsigned i = 0; ; ++i)
 107     if (Vec[i].first == Field) return i;
 108 }
 109
 110 static inline void GetTransformation(const TargetData &TD, const StructType *ST,
 111                                      vector<int> &Transform,
 112                                    enum SimpleStructMutation::Transform XForm) {
 113   unsigned NumElements = ST->getElementTypes().size();
 114   Transform.reserve(NumElements);
 115
 116   switch (XForm) {
 117   case SimpleStructMutation::SwapElements:
 118     // The transformation to do is: just simply swap the elements
 119     for (unsigned i = 0; i < NumElements; ++i)
 120       Transform.push_back(NumElements-i-1);
 121     break;
 122
 123   case SimpleStructMutation::SortElements: {
 124     vector<pair<unsigned, unsigned> > ElList;
 125
 126     // Build mapping from index to size
 127     for (unsigned i = 0; i < NumElements; ++i)
 128       ElList.push_back(
 129               std::make_pair(i, TD.getTypeSize(ST->getElementTypes()[i])));
 130
 131     sort(ElList.begin(), ElList.end(), ptr_fun(FirstLess));
 132
 133     for (unsigned i = 0; i < NumElements; ++i)
 134       Transform.push_back(getIndex(ElList, i));
 135
 136     break;
 137   }
 138   }
 139 }
 140
 141
 142 SimpleStructMutation::TransformsType
 143   SimpleStructMutation::getTransforms(Module &, enum Transform XForm) {
 144   // We need to know which types to modify, and which types we CAN'T modify
 145   // TODO: Do symbol tables as well
 146
 147   // Get the results out of the analyzers...
 148   FindUsedTypes          &FUT = getAnalysis<FindUsedTypes>();
 149   const set<const Type *> &UsedTypes  = FUT.getTypes();
 150
 151   FindUnsafePointerTypes &FUPT = getAnalysis<FindUnsafePointerTypes>();
 152   const set<PointerType*> &UnsafePTys = FUPT.getUnsafeTypes();
 153
 154
 155
 156   // Combine the two sets, weeding out non structure types.  Closures in C++
 157   // sure would be nice.
 158   set<const StructType*> TypesToModify;
 159   for (set<const Type *>::const_iterator I = UsedTypes.begin(),
 160          E = UsedTypes.end(); I != E; ++I)
 161     if (const StructType *ST = dyn_cast<StructType>(*I))
 162       TypesToModify.insert(ST);
 163
 164
 165   // Go through the Unsafe types and remove all types from TypesToModify that we
 166   // are not allowed to modify, because that would be unsafe.
 167   //
 168   set<const Type*> ProcessedTypes;
 169   for (set<PointerType*>::const_iterator I = UnsafePTys.begin(),
 170          E = UnsafePTys.end(); I != E; ++I) {
 171     //cerr << "Pruning type: " << *I << "\n";
 172     PruneTypes(*I, TypesToModify, ProcessedTypes);
 173   }
 174
 175
 176   // Build up a set of structure types that we are going to modify, and
 177   // information describing how to modify them.
 178   std::map<const StructType*, vector<int> > Transforms;
 179   TargetData &TD = getAnalysis<TargetData>();
 180
 181   for (set<const StructType*>::iterator I = TypesToModify.begin(),
 182          E = TypesToModify.end(); I != E; ++I) {
 183     const StructType *ST = *I;
 184
 185     vector<int> &Transform = Transforms[ST];  // Fill in the map directly
 186     GetTransformation(TD, ST, Transform, XForm);
 187   }
 188
 189   return Transforms;
 190 }