//===- MatrixOperations.h - A common place for matrix operations ----------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a set of interfaces for matrix operations. It is built
// on top of integer math library - IMath to represent the rationals.
//
//===----------------------------------------------------------------------===//
//====  Copyright (c) 2015 Advanced Micro Devices, Inc.  All rights reserved.
//
//               Developed by: Advanced Micro Devices, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal 
// with the Software without restriction, including without limitation the 
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 
// sell copies of the Software, and to permit persons to whom the Software is 
// furnished to do so, subject to the following conditions:
//
// Redistributions of source code must retain the above copyright notice, this 
// list of conditions and the following disclaimers.
//
// Redistributions in binary form must reproduce the above copyright notice, 
// this list of conditions and the following disclaimers in the documentation 
// and/or other materials provided with the distribution.
//
// Neither the names of Advanced Micro Devices, Inc., nor the names of its 
// contributors may be used to endorse or promote products derived from this 
// Software without specific prior written permission.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
// CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH 
// THE SOFTWARE.
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_LOOP_MATH_H
#define LLVM_TRANSFORMS_LOOP_MATH_H

#include <assert.h>
#include <cstdlib>
#include <vector>

#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/imath.h"
#include "llvm/Transforms/Utils/imrat.h"

namespace MatOp {

// A wrapper around the mpq_t type provided by ISL's imath library.
class Rational {
  mpq_t rat[1];
  mp_rat pq = rat;

public:
  Rational() { mp_rat_init (pq); };

  Rational(int p) {
    mp_rat_init(pq);
    setFromInt(p);
  }

  Rational(int p, int q) {
    mp_rat_init(pq);
    setFromInt(p, q);
  }

  Rational(const Rational &rhs) {
    mp_rat_init(pq);
    mp_rat_init_copy(pq, rhs.pq);
  }

  Rational &operator= (const Rational &rhs) {
    mp_rat_init_copy(pq, rhs.pq);
    return (*this);
  }

  ~Rational() { mp_rat_clear(pq); };

  void setFromInt(long p);
  void setFromInt(long p, long q);

  // Is the denominator == 1?
  bool isInteger(void) const;

  // Return the numerator when denominator == 1
  // assert(isInt()).
  long getIntegerLong(void) const;

  // Return the numerator and denominator as
  // integers. If cannot be represented as integer
  // return false and num and den will be unset then.
  bool getNumDenInt(long *num, long *den) const;

  // Get the lcm of the denominators:
  static Rational getDenomLCM(const Rational &a, const Rational &b);

  // Binary operations
  Rational operator+ (const Rational &rhs) const;
  Rational operator- (const Rational &rhs) const;
  Rational operator* (const Rational &rhs) const;
  Rational operator/ (const Rational &rhs) const;

  // Unary - operator
  Rational operator- (void) const;

  // TODO: Implement other operators too.

  // New comparisons
  bool operator== (const Rational &rhs) const;
  bool operator!= (const Rational &rhs) const;
  bool operator> (const Rational &rhs) const;
  bool operator>= (const Rational &rhs) const;
  bool operator< (const Rational &rhs) const;
  bool operator<= (const Rational &rhs) const;

  // Compare directly with integers.
  bool operator== (int p) const;
  bool operator!= (int p) const;
  bool operator< (int p) const;
  bool operator<= (int p) const;
  bool operator> (int p) const;
  bool operator>= (int p) const;

  // Debug.
  void print(llvm::raw_ostream &O) const;
};

llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Rational &V);

typedef std::vector<Rational> RationalVector_t;
typedef std::vector<RationalVector_t> RationalMatrix_t;

void printRationalMatrix (llvm::raw_ostream &OS, RationalMatrix_t &M);
void printRationalVector (llvm::raw_ostream &OS, RationalVector_t &V);

// Check if the matrix is an identity matrix.
bool isIdentityMatrix(RationalMatrix_t &mat);

// Allocate "mat" to be a m x n matrix. Initialize to 0s if identity = false.
void newMatrix (RationalMatrix_t &mat, int m, int n, bool identity=false);

// Add two matrices
void addMatrix (RationalMatrix_t &res, RationalMatrix_t &A, RationalMatrix_t &B);

// Negate a vector, in place
void negVector (RationalVector_t &V);

// Negate a matrix, in place
void negMatrix (RationalMatrix_t &A);

// Do A = A*c; where A*c means multiplying all elements of A with scalar c.
void mulVecBy(RationalVector_t &A, const Rational &c);

// Do A = A*c - B; where A*c means multiplying all elements of A with scalar c.
void mulVecByAndSub(RationalVector_t &A, const Rational &c, const RationalVector_t &B);

// Do A = A + (B*c)
void addMultipliedVec(RationalVector_t &A, const RationalVector_t &B, const Rational &c);

// C = A x B.
void mulMatrix(RationalMatrix_t &C, const RationalMatrix_t &A, const RationalMatrix_t &B);

// Compute the inverse of a non-singular square matrix A, in place.
// The result is indeterminate if A is singular
void invMatrix (RationalMatrix_t &A);

// Compute the transpose of matrix, in place.
void transMatrix(RationalMatrix_t &A);

// Get a sub matrix starting from iLow,jLow till (including) iUp,jUp;
void subMatrix (RationalMatrix_t &subA, const RationalMatrix_t &A,
                unsigned iLow, unsigned iUp, unsigned jLow, unsigned jUp);

// Append the columns of B, to A. Assumes A.size() == B.size().
void appColumns (RationalMatrix_t &A, const RationalMatrix_t &B);

// Given a list of rationals, find the lcm of the
// denominators, multiply the fractions with the lcm
// and RETURN the reciprocal of the lcm.
// Example: Given {(1/2),(1/3)}
// The input list is changed to {3,2} and 1/6 is returned.
// Essentially, multiplying the returned value with the
// modified vector will give the original input vector.
Rational makeCommonDenom(RationalVector_t &ratList);

// This function performs fourier-motzkin elimination of variables,
// starting from "firstProject" till 0.
// assert (height(B) == height(b)).
// The assumed canonical form is Bi <= b, where 'i' is the vector of
// loop indices followed by loop invariants (but not constants). 'i'
// here is implicit, and would be as long as width(B).
// assert(firstProject <= width(B)). firstProject is considered to
// be the last loop index variable. The rest are loop invariants, such
// as 'n' that we commonly have as loop bound.
// RETURN VALUE: return true if there is a solution to the set of bounds,
//               i.e. there is at least one point in the polyhedra.
// Computed value: The computed bounds (projected bounds) are returned
// in pB and pb, where two consecutive slots are assigned for each index
// variable, first for lower bounds and second for upper bounds. i.e.
// upon returning, pB.size() == pb.size() == (2*firstProject). For example,
// if i0 is the first index variable, then
//     i0 >= pB[0](i) + pb[0] && i0 <= pB[1](i) + pb[1]
// where 'i' is the set of index and invariant variables in the same order
// as was implicit in the input B and b.
bool doFourierMotzkin(const RationalMatrix_t &B, const RationalVector_t &b,
                       int firstProject, std::vector<RationalMatrix_t> &pB,
                       std::vector<RationalVector_t> &pb);

} // end namespace::Math
#endif // LLVM_TRANSFORMS_LOOP_MATH_H
