lib/VMCore/StandardPasses.cpp

   1 //===-- lib/Support/StandardPasses.cpp - Standard pass lists -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines utility functions for creating a "standard" set of
  11 // optimization passes, so that compilers and tools which use optimization
  12 // passes use the same set of standard passes.
  13 //
  14 // This allows the creation of multiple standard sets, and their later
  15 // modification by plugins and front ends.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/PassManager.h"
  20 #include "llvm/Support/ErrorHandling.h"
  21 #include "llvm/Support/ManagedStatic.h"
  22 #include "llvm/DefaultPasses.h"
  23 #include "llvm/Support/Mutex.h"
  24
  25 using namespace llvm::DefaultStandardPasses;
  26 using namespace llvm;
  27
  28 namespace {
  29
  30 /// Entry in the standard passes list.
  31 struct StandardPassEntry {
  32   /// Function called to create the pass
  33   PassInfo::NormalCtor_t createPass;
  34   /// Unique identifier for this pass
  35   unsigned char *passID;
  36   /// Flags specifying when this pass should be run
  37   unsigned flags;
  38
  39   StandardPassEntry(PassInfo::NormalCtor_t constructor, unsigned char *ID,
  40       unsigned f) : createPass(constructor), passID(ID), flags(f) {}
  41 };
  42
  43 /// Standard alias analysis passes
  44 static llvm::SmallVector<StandardPassEntry, 4> AAPasses;
  45 /// Standard function passes
  46 static llvm::SmallVector<StandardPassEntry, 32> FunctionPasses;
  47 /// Standard module passes
  48 static llvm::SmallVector<StandardPassEntry, 32> ModulePasses;
  49 /// Standard link-time optimization passes
  50 static llvm::SmallVector<StandardPassEntry, 32> LTOPasses;
  51
  52 /// Entry in the unresolved standard pass list.  IF a pass is inserted in front
  53 /// of a pass that is not yet registered in the standard pass list then it is
  54 /// stored in a separate list and resolved later.
  55 struct UnresolvedStandardPass : public StandardPassEntry {
  56   /// The set into which this is stored
  57   StandardPass::StandardSet set;
  58   /// The unique ID of the pass that should follow this one in the sequence
  59   unsigned char *next;
  60   UnresolvedStandardPass(PassInfo::NormalCtor_t constructor,
  61                          unsigned char *newPass,
  62                          unsigned char *oldPass,
  63                          StandardPass::StandardSet s,
  64                          unsigned f) :
  65     StandardPassEntry(constructor, newPass, f), set(s), next(oldPass) {}
  66 };
  67
  68 /// The passes that can not be inserted into the correct lists yet because of
  69 /// their place in the sequence.
  70 static llvm::SmallVector<UnresolvedStandardPass, 16> UnresolvedPasses;
  71
  72 /// Returns a reference to the pass list for the corresponding set of
  73 /// optimisations.
  74 llvm::SmallVectorImpl<StandardPassEntry>&
  75 PassList(StandardPass::StandardSet set) {
  76   switch (set) {
  77     case StandardPass::AliasAnalysis: return AAPasses;
  78     case StandardPass::Function: return FunctionPasses;
  79     case StandardPass::Module: return ModulePasses;
  80     case StandardPass::LTO: return LTOPasses;
  81   }
  82   // We could use a map of standard pass lists to allow definition of new
  83   // default sets
  84   llvm_unreachable("Invalid standard optimization set requested");
  85 }
  86
  87 static ManagedStatic<sys::SmartMutex<true> > Lock;
  88
  89 /// Registers the default set of standard passes.  This is called lazily when
  90 /// an attempt is made to read or modify the standard pass list
  91 void RegisterDefaultStandardPasses(void(*doRegister)(void)) {
  92   // Only initialize the standard passes once
  93   static volatile bool initialized = false;
  94   if (initialized) return;
  95
  96   llvm::sys::SmartScopedLock<true> Guard(*Lock);
  97   if (initialized) return;
  98   if (doRegister) {
  99     assert("No passes registered before setting default passes" &&
 100             AAPasses.size() == 0 &&
 101             FunctionPasses.size() == 0 &&
 102             LTOPasses.size() == 0 &&
 103             ModulePasses.size() == 0);
 104
 105     // We must set initialized to true before calling this function, because
 106     // the doRegister() function will probably call RegisterDefaultPasses(),
 107     // which will call this function, and we'd end up with infinite recursion
 108     // and breakage if we didn't.
 109     initialized = true;
 110     doRegister();
 111   }
 112 }
 113
 114 } // Anonymous namespace
 115
 116 void (*StandardPass::RegisterDefaultPasses)(void);
 117 Pass* (*StandardPass::CreateVerifierPass)(void);
 118
 119 void StandardPass::RegisterDefaultPass(PassInfo::NormalCtor_t constructor,
 120                                        unsigned char *newPass,
 121                                        unsigned char *oldPass,
 122                                        StandardPass::StandardSet set,
 123                                        unsigned flags) {
 124   // Make sure that the standard sets are already regstered
 125   RegisterDefaultStandardPasses(RegisterDefaultPasses);
 126   // Get the correct list to modify
 127   llvm::SmallVectorImpl<StandardPassEntry>& passList = PassList(set);
 128
 129   // If there is no old pass specified, then we are adding a new final pass, so
 130   // just push it onto the end.
 131   if (!oldPass) {
 132     StandardPassEntry pass(constructor, newPass, flags);
 133     passList.push_back(pass);
 134     return;
 135   }
 136
 137   // Find the correct place to insert the pass.  This is a linear search, but
 138   // this shouldn't be too slow since the SmallVector will store the values in
 139   // a contiguous block of memory.  Each entry is just three words of memory, so
 140   // in most cases we are only going to be looking in one or two cache lines.
 141   // The extra memory accesses from a more complex search structure would
 142   // offset any performance gain (unless someone decides to add an insanely
 143   // large set of standard passes to a set)
 144   for (SmallVectorImpl<StandardPassEntry>::iterator i=passList.begin(),
 145        e=passList.end() ; i!=e ; ++i) {
 146     if (i->passID == oldPass) {
 147       StandardPassEntry pass(constructor, newPass, flags);
 148       passList.insert(i, pass);
 149       // If we've added a new pass, then there may have gained the ability to
 150       // insert one of the previously unresolved ones.  If so, insert the new
 151       // one.
 152       for (SmallVectorImpl<UnresolvedStandardPass>::iterator
 153           u=UnresolvedPasses.begin(), eu=UnresolvedPasses.end() ; u!=eu ; ++u){
 154         if (u->next == newPass && u->set == set) {
 155           UnresolvedStandardPass p = *u;
 156           UnresolvedPasses.erase(u);
 157           RegisterDefaultPass(p.createPass, p.passID, p.next, p.set, p.flags);
 158         }
 159       }
 160       return;
 161     }
 162   }
 163   // If we get to here, then we didn't find the correct place to insert the new
 164   // pass
 165   UnresolvedStandardPass pass(constructor, newPass, oldPass, set, flags);
 166   UnresolvedPasses.push_back(pass);
 167 }
 168
 169 void StandardPass::AddPassesFromSet(PassManagerBase *PM,
 170                                     StandardSet set,
 171                                     unsigned flags,
 172                                     bool VerifyEach,
 173                                     Pass *inliner) {
 174   RegisterDefaultStandardPasses(RegisterDefaultPasses);
 175   unsigned level = OptimizationLevel(flags);
 176   flags = RequiredFlags(flags);
 177   llvm::SmallVectorImpl<StandardPassEntry>& passList = PassList(set);
 178
 179   // Add all of the passes from this set
 180   for (SmallVectorImpl<StandardPassEntry>::iterator i=passList.begin(),
 181        e=passList.end() ; i!=e ; ++i) {
 182     // Skip passes that don't have conditions that match the ones specified
 183     // here.  For a pass to match:
 184     // - Its minimum optimisation level must be less than or equal to the
 185     //   specified level.
 186     // - Its maximum optimisation level must be greater than or equal to the
 187     //   specified level
 188     // - All of its required flags must be set
 189     // - None of its disallowed flags may be set
 190     if ((level >= OptimizationLevel(i->flags)) &&
 191         ((level <= MaxOptimizationLevel(i->flags))
 192           || MaxOptimizationLevel(i->flags) == 0)  &&
 193         ((RequiredFlags(i->flags) & flags) == RequiredFlags(i->flags)) &&
 194         ((DisallowedFlags(i->flags) & flags) == 0)) {
 195       // This is quite an ugly way of allowing us to specify an inliner pass to
 196       // insert.  Ideally, we'd replace this with a general mechanism allowing
 197       // callers to replace arbitrary passes in the list.
 198       Pass *p = 0;
 199       if (&InlinerPlaceholderID == i->passID) {
 200           p = inliner;
 201       } else if (i->createPass)
 202         p = i->createPass();
 203       if (p) {
 204         PM->add(p);
 205         if (VerifyEach)
 206           PM->add(CreateVerifierPass());
 207       }
 208     }
 209   }
 210 }
 211
 212 unsigned char DefaultStandardPasses::AggressiveDCEID;
 213 unsigned char DefaultStandardPasses::ArgumentPromotionID;
 214 unsigned char DefaultStandardPasses::BasicAliasAnalysisID;
 215 unsigned char DefaultStandardPasses::CFGSimplificationID;
 216 unsigned char DefaultStandardPasses::ConstantMergeID;
 217 unsigned char DefaultStandardPasses::CorrelatedValuePropagationID;
 218 unsigned char DefaultStandardPasses::DeadArgEliminationID;
 219 unsigned char DefaultStandardPasses::DeadStoreEliminationID;
 220 unsigned char DefaultStandardPasses::DeadTypeEliminationID;
 221 unsigned char DefaultStandardPasses::EarlyCSEID;
 222 unsigned char DefaultStandardPasses::FunctionAttrsID;
 223 unsigned char DefaultStandardPasses::FunctionInliningID;
 224 unsigned char DefaultStandardPasses::GVNID;
 225 unsigned char DefaultStandardPasses::GlobalDCEID;
 226 unsigned char DefaultStandardPasses::GlobalOptimizerID;
 227 unsigned char DefaultStandardPasses::GlobalsModRefID;
 228 unsigned char DefaultStandardPasses::IPSCCPID;
 229 unsigned char DefaultStandardPasses::IndVarSimplifyID;
 230 unsigned char DefaultStandardPasses::InlinerPlaceholderID;
 231 unsigned char DefaultStandardPasses::InstructionCombiningID;
 232 unsigned char DefaultStandardPasses::JumpThreadingID;
 233 unsigned char DefaultStandardPasses::LICMID;
 234 unsigned char DefaultStandardPasses::LoopDeletionID;
 235 unsigned char DefaultStandardPasses::LoopIdiomID;
 236 unsigned char DefaultStandardPasses::LoopRotateID;
 237 unsigned char DefaultStandardPasses::LoopUnrollID;
 238 unsigned char DefaultStandardPasses::LoopUnswitchID;
 239 unsigned char DefaultStandardPasses::MemCpyOptID;
 240 unsigned char DefaultStandardPasses::PruneEHID;
 241 unsigned char DefaultStandardPasses::ReassociateID;
 242 unsigned char DefaultStandardPasses::SCCPID;
 243 unsigned char DefaultStandardPasses::ScalarReplAggregatesID;
 244 unsigned char DefaultStandardPasses::SimplifyLibCallsID;
 245 unsigned char DefaultStandardPasses::StripDeadPrototypesID;
 246 unsigned char DefaultStandardPasses::TailCallEliminationID;
 247 unsigned char DefaultStandardPasses::TypeBasedAliasAnalysisID;