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