ShOptimizations.hpp

// Sh: A GPU metaprogramming language.
//
// Copyright 2003-2005 Serious Hack Inc.
// 
// This software is provided 'as-is', without any express or implied
// warranty. In no event will the authors be held liable for any damages
// arising from the use of this software.
// 
// Permission is granted to anyone to use this software for any purpose,
// including commercial applications, and to alter it and redistribute it
// freely, subject to the following restrictions:
// 
// 1. The origin of this software must not be misrepresented; you must
// not claim that you wrote the original software. If you use this
// software in a product, an acknowledgment in the product documentation
// would be appreciated but is not required.
// 
// 2. Altered source versions must be plainly marked as such, and must
// not be misrepresented as being the original software.
// 
// 3. This notice may not be removed or altered from any source
// distribution.
#ifndef SHOPTIMIZATIONS_HPP
#define SHOPTIMIZATIONS_HPP

#include <iosfwd>
#include <vector>
#include <set>
#include <map>
#include "ShProgram.hpp"
#include "ShInfo.hpp"
#include "ShStatement.hpp"

// Uncomment this to turn on optimizer debugging using dot.
// Warning: This is very verbose!
//#define SH_DEBUG_OPTIMIZER

namespace SH {

SH_DLLEXPORT
void optimize(ShProgram& p, int level);
SH_DLLEXPORT
void optimize(const ShProgramNodePtr& p, int level);

SH_DLLEXPORT
void optimize(ShProgram& p);
SH_DLLEXPORT
void optimize(const ShProgramNodePtr& p);

// Internal stuff.

// Add value tracking information to the given program's CFG
// statements.
// If it already exists, overwrite it.
SH_DLLEXPORT
void add_value_tracking(ShProgram& prg);

SH_DLLEXPORT
void insert_branch_instructions(ShProgram& prg);

SH_DLLEXPORT
void remove_branch_instructions(ShProgram& prg);

SH_DLLEXPORT
void straighten(ShProgram& p, bool& changed);

SH_DLLEXPORT
void remove_dead_code(ShProgram& p, bool& changed);

SH_DLLEXPORT
void propagate_constants(ShProgram& p);

/* per statement uddu chains */
struct 
SH_DLLEXPORT
ValueTracking : public ShInfo {
  ValueTracking(ShStatement* stmt);

  ShInfo* clone() const;

  
  struct Def {
    enum Kind {
      INPUT,
      STMT
    };

    Def(ShStatement* stmt, int index)
      : kind(STMT), node(0), stmt(stmt), index(index)
    {
    }

    Def(ShVariableNodePtr node, int index)
      : kind(INPUT), node(node), stmt(0), index(index) 
    {}
    
    Kind kind;
    ShVariableNodePtr node;
    ShStatement* stmt;
    int index; 

    bool operator<(const Def& other) const
    {
      return kind < other.kind ||
             (kind == other.kind && 
             (node < other.node ||
             (node == other.node &&
             (stmt < other.stmt || 
             (stmt == other.stmt && index < other.index)))));
    }

    int absIndex() const
    {
      if(kind == INPUT) return index;
      return stmt->dest.swizzle()[index];
    }

    friend std::ostream& operator<<(std::ostream& out, const Def& def);
  };

  struct Use {
    enum Kind {
      OUTPUT,
      STMT
    };

    Use(ShStatement* stmt, int source, int index)
      : kind(STMT), node(0), stmt(stmt), source(source), index(index)
    {
    }

    Use(ShVariableNodePtr node, int index)
      : kind(OUTPUT), node(node), stmt(0), source(0), index(index)
    {
    }

    bool operator<(const Use& other) const
    {
      return kind < other.kind ||
             (kind == other.kind && 
             (node < other.node ||
             (node == other.node &&
             (stmt < other.stmt || 
             (stmt == other.stmt && 
             (source < other.source ||
             (source == other.source && index < other.index)))))));
    }

    int absIndex() const
    {
      if(kind == OUTPUT) return index;
      return stmt->src[source].swizzle()[index];
    }

    friend std::ostream& operator<<(std::ostream& out, const Use& use);

    Kind kind;
    ShVariableNodePtr node;
    ShStatement* stmt;
    int source; // source variable
    int index; // tuple index (swizzled)
  };

  // For each tuple element, track all of the uses of our definition.
  typedef std::set<Use> DefUseChain;
  typedef std::vector<DefUseChain> TupleDefUseChain;
  TupleDefUseChain uses;

  friend std::ostream& operator<<(std::ostream& out, const TupleDefUseChain& tdu);
  
  // For each tuple element in each of our sources, track all the
  // definition points.
  typedef std::set<Def> UseDefChain;
  typedef std::vector<UseDefChain> TupleUseDefChain;
  typedef std::vector<TupleUseDefChain> TupleUseDefChainVec;
  TupleUseDefChainVec defs;

  friend std::ostream& operator<<(std::ostream& out, const TupleUseDefChain& tud);
};

/* du chains for all inputs in a program */
struct InputValueTracking: public ShInfo 
{
  ShInfo* clone() const;
  
  friend std::ostream& operator<<(std::ostream& out, const InputValueTracking& ivt);

  typedef std::map<ShVariableNodePtr, ValueTracking::TupleDefUseChain> InputTupleDefUseChain; 
  InputTupleDefUseChain inputUses;
};

/* ud chains for all outputs in a program */
struct OutputValueTracking: public ShInfo 
{
  ShInfo* clone() const;

  friend std::ostream& operator<<(std::ostream& out, const OutputValueTracking& ovt);

  typedef std::map<ShVariableNodePtr, ValueTracking::TupleUseDefChain> OutputTupleUseDefChain; 
  OutputTupleUseDefChain outputDefs;
};

}

#endif

---