lib/Transforms/IPO/SimpleStructMutation.cpp

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