lib/Transforms/IPO/SimpleStructMutation.cpp

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