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