lib/Transforms/IPO/SimpleStructMutation.cpp

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