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