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