safecode/include/AffineExpressions.h

//===- AffineExpressions.h  - Expression Analysis Utils ----------*- C++ -*--=//
// 
//                          The SAFECode Compiler 
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
//
// This file defines a package of expression analysis utilties.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_C_EXPRESSIONS_H
#define LLVM_C_EXPRESSIONS_H

#include <assert.h>
#include <map>
#include <list>
#include <string>
#include <strstream>

#include "llvm/Instruction.h"
#include "llvm/Instructions.h"
#include "llvm/InstrTypes.h"
#include "llvm/Constants.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Target/Mangler.h"
#include "llvm/DerivedTypes.h"

using namespace std;
namespace llvm {


namespace cfg { class LoopInfo; }

typedef std::map<const PHINode *, Value *> IndVarMap;
typedef std::map<const Function *,BasicBlock *> ExitNodeMap;
typedef std::map<const Function *, PostDominanceFrontier *> PostDominanceFrontierMap;

typedef std::map<const Value*,int> CoefficientMap;
typedef std::map<const Value*,string> ValStringMap;
typedef std::list<const Value*> VarList;
typedef std::list<const Value*>::const_iterator VarListIt;
typedef std::list<const CallInst*> CallInstList;
typedef std::list<const CallInst*>::const_iterator CallInstListIt;
typedef std::map<Instruction*, bool> MemAccessInstListType;
typedef std::map<Instruction*, bool>::const_iterator  MemAccessInstListIt;

//
// Function: makeNameProper()
//
// Description:
//  This function transforms a name to meet two requirements:
//    o) There are no invalid symbols.
//    o) The string length is 18 characters or less.
//  To do this, we replace symbols such as period, underscore, minus, etc.
//  with a letter followed by an underscore.
//
// Notes:
//  FIXME: This function always converts "in" to "in__1."  I am not sure why
//         this is.
//
static inline string
makeNameProper (string x) {
  string tmp;
  int len = 0;
  for (string::iterator sI = x.begin(), sEnd = x.end(); sI != sEnd; sI++) {
    if (len > 18) return tmp; //have to do something more meaningful
    len++;
    switch (*sI) {
      case '.': tmp += "d_"; len++;break;
      case ' ': tmp += "s_"; len++;break;
      case '-': tmp += "D_"; len++;break;
      case '_': tmp += "l_"; len++;break;
      default:  tmp += *sI;
    }
  }

  if (tmp == "in") return "in__1";
  return tmp;
}

//
// Class: OmegaMangler
//
// Description:
//  This class can be used in place of the LLVM Mangler for mangling LLVM value
//  names into strings that can be used as variable names in the Omega
//  calculator.
//
// Notes:
//  Having a single method that properly converts an LLVM Value's name into an
//  Omega calculator name is less error-prone than having the code call
//  makeNameProper() directly.
//
// TODO:
//  This mangler class needs to be expanded to include functionality that was
//  present in the LLVM 2.6 Mangler class.  This class has been removed in
//  LLVM 2.7, and this code is currently unused, so it's modified just enough
//  to keep compilation working.  Eventually, we should either get this code
//  working or remove it entirely.
//
class OmegaMangler {
  public:
    OmegaMangler (Module & M) {
    }

    std::string getValueName (const Value *V) {
      // Counter for making unique value names for unnamed values
      static unsigned id_counter = 0;

      //
      // The LLVM name mangler doesn't work on regular LLVM values any more,
      // so we must replicate the functionality here.
      //
      if (V->hasName()) {
        return (makeNameProper ((V->getName())));
      }

      std::ostrstream intstr;
      intstr << "noname" << (++id_counter);
      return (makeNameProper ((intstr.str())));
    }
};

//
// Class: LinearExpr
//
// Description:
//  Represent an expression of the form CONST*VAR1 + CONST*VAR2 + ...
//
class LinearExpr {
    int offSet;
    VarList* vList;
    CoefficientMap* cMap;
    ValStringMap* vsMap;

  public:
    enum ExpressionType {
        Linear,        // Expression is linear
        Unknown        // Expression is some unknown type of expression
    } exprTy;

    inline int getOffSet() { return offSet; };
    inline void setOffSet(int offset) {  offSet = offset; };
    inline ExpressionType getExprType() { return exprTy; };
    inline VarList* getVarList() { return vList; };
    inline CoefficientMap* getCMap() { return cMap; };
    inline ValStringMap* getVSMap() { return vsMap; };

    // Create a linear expression
    LinearExpr(const Value *Val, OmegaMangler *Mang);
    void negate();
    void addLinearExpr(LinearExpr *);
    LinearExpr * mulLinearExpr(LinearExpr *);
    void mulByConstant(int);
    void print(ostream &out);
    void printOmegaSymbols(ostream &out);
};

//
// Class: Constraint
//
// Description:
//  This class represents a constaint of the form <var> <rel> <expr> where:
//    <var>  : is a variable
//    <rel>  : is one of the following relations: <, >, <=, >=
//    <expr> : is a linear expression
//
class Constraint {
    string var;
    LinearExpr *le;

    // The relation: can be < ,  >, <=, >= for now
    string rel;

    // Flags whether the left-hand value is constant 
    bool leConstant_;

  public :
    Constraint(string v, LinearExpr *l, string r, bool leConstant = false ) {
      assert(l != 0 && "the rhs for this constraint is null");
      var = v;
      le = l;
      rel = r;
      leConstant_ = leConstant;
    }
    void print(ostream &out);
    void printOmegaSymbols(ostream &out);
};

//
// Class: ABCExprTree
//
// Description:
//  This class represents a set of relations that are connected together with
//  boolean AND and OR.  It represents the entire expression as a tree.  Each
//  node has a left and right subtree and either an AND or OR relation that
//  specified the relationship between the two subtrees.
//
class ABCExprTree {
    Constraint *constraint;
    ABCExprTree *right;
    ABCExprTree *left;
    string logOp; // can be && or || or
  public:
    ABCExprTree(Constraint *c) {
      constraint = c;
      left  = 0;
      right = 0;
      logOp = "&&";
    };

    ABCExprTree(ABCExprTree *l, ABCExprTree *r, string op) {
      constraint = 0;
      assert( l && " l is null \n");
      assert( r && " r is null \n");
      left = l;
      right = r;
      logOp = op;
    }
    void dump();
    void print(ostream &out);
    void printOmegaSymbols(ostream &out);
};

typedef std::map<const Value *, ABCExprTree *> InstConstraintMapType;

//
// Class: FuncLocalInfo
//
// Description:
//  This class retains constraint information collected for a function.
//
class FuncLocalInfo {
    // Local cache for constraints
    InstConstraintMapType FuncLocalConstraints;

    // Storing all constraints which need proving 
    InstConstraintMapType FuncSafetyConstraints;

    // All array accesses in a function 
    MemAccessInstListType maiList;

    // This stores the Or of the arguments at
    // various call sites, so that can be computed only once for
    // different array accesses. 
    ABCExprTree *argConstraints;

  public :
    FuncLocalInfo() {
      argConstraints = 0;
    }

    inline void addMemAccessInst(Instruction *MAI, bool reqArg) {
      maiList[MAI] = reqArg;
    }

    inline void addLocalConstraint(const Value *v, ABCExprTree *aet) {
      FuncLocalConstraints[v] = aet;
    }

    inline bool inLocalConstraints(const Value *v) {
      return (FuncLocalConstraints.count(v) > 0);
    }

    inline ABCExprTree * getLocalConstraint(const Value *v) {
      if (FuncLocalConstraints.count(v)) return FuncLocalConstraints[v];
      else return 0;
    }

    inline void addSafetyConstraint(const Value *v, ABCExprTree *aet) {
      FuncSafetyConstraints[v] = aet;
    }

    inline ABCExprTree* getSafetyConstraint(const Value *v) {
      return (FuncSafetyConstraints[v]);
    }

    inline MemAccessInstListType getMemAccessInstList() {
      return maiList;
    }

    inline void addArgumentConstraints(ABCExprTree *aet) {
      argConstraints = aet;
    }

    inline ABCExprTree * getArgumentConstraints() {
      return argConstraints;
    }
};

#if 0
static string getValueNames(const Value *V, Mangler *Mang) {
  if (const Constant *CPI = dyn_cast<Constant>(V)) {
    if (const ConstantSInt *CPI = dyn_cast<ConstantSInt>(V)) {
      return itostr(CPI->getValue());
    } else if (const ConstantUInt *CPI = dyn_cast<ConstantUInt>(V)) {
      return utostr(CPI->getValue());
    }
  }
  if (V->hasName()) {
    return makeNameProper(V->getName());
  }
  else {
    return Mang->getValueName(V);
  }
};
#endif
}

#endif