//===----------------- QtmInst.cpp ----------------------===//
// This file implements the Scaffold Quantum Instruction Class
//
//
//
//        This file was created by Scaffold Compiler Working Group
//
//
//
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "QtmInst"
#include <vector>
#include "llvm/Pass.h"
#include "llvm/Function.h"
#include "llvm/Module.h"
#include "llvm/BasicBlock.h"
#include "llvm/Instruction.h"
#include "llvm/Instructions.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/PassAnalysisSupport.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Support/CFG.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/Argument.h"
#include "llvm/ADT/ilist.h"
#include "llvm/Constants.h"
#include "llvm/IntrinsicInst.h"
#include "scaffold/QtmGateArg.h"


using namespace llvm;
using namespace std;

#define MAX_GATE_ARGS 30
#define MAX_BT_COUNT 15 //max backtrace allowed - to avoid infinite recursive loops

bool debugQtmInst = false;

namespace {
  
  struct qArgInfo{
    string name;
    int index;
    qArgInfo(): name("none"), index(-1){ }
  };
  
  struct qGate{
    Function* qFunc;
    int numArgs;
    qArgInfo args[MAX_GATE_ARGS];
    double angle;
    qGate():qFunc(NULL), numArgs(0), angle(0.0) { }
  };

  struct QtmInst : public ModulePass {
    static char ID; // Pass identification
    
    vector<QtmGateArg> tmpDepQbit;
    
    int btCount; //backtrace count

    QtmInst() : ModulePass(ID) {}
    
    bool checkIfQbitOrCbit(Type* varType);

    bool backtraceOperand(Value* opd, int opOrIndex);
    void analyzeCallInst(Function* F,Instruction* pinst);

    void print_qgate(qGate qg);

    
    bool runOnModule (Module &M);    
    
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesAll();  
      AU.addRequired<CallGraph>();    
    }
    
  }; // End of struct QtmInst
} // End of anonymous namespace

char QtmInst::ID = 0;
static RegisterPass<QtmInst> X("QtmInst", "Get gate and operands for a Qtm Inst");


bool QtmInst::checkIfQbitOrCbit(Type* varType)
{
  if(varType->isPointerTy()){
    Type *elementType = varType->getPointerElementType();
    if (elementType->isIntegerTy(16) || elementType->isIntegerTy(1)){ //qbit* or cbit*
      return true;	      
    }
  }
  else if (varType->isIntegerTy(16) || varType->isIntegerTy(1)){ //qbit or cbit
    return true;
  }
  return false;
}

bool QtmInst::backtraceOperand(Value* opd, int opOrIndex)
{
  if(opOrIndex == 0) //backtrace for operand
    {

      if(Argument *fArg = dyn_cast<Argument>(opd))
	{
	  Type* argType = fArg->getType();
	  bool isQtm = checkIfQbitOrCbit(argType);
	  if(isQtm){
	    tmpDepQbit[0].argPtr = opd;
	    return true;
	  } 
	}

      if (AllocaInst *AI = dyn_cast<AllocaInst>(opd)) {
	Type *allocatedType = AI->getAllocatedType();
    
	if(ArrayType *arrayType = dyn_cast<ArrayType>(allocatedType)) {      
	  Type *elementType = arrayType->getElementType();
	  bool isQtm = checkIfQbitOrCbit(elementType);
	  if(isQtm){
	    tmpDepQbit[0].argPtr = opd;
	    return true;
	  }
	}
      }

      if(btCount>MAX_BT_COUNT)
	return false;
      
      if(isa<GetElementPtrInst>(opd))
	{
	  Instruction* pInst = dyn_cast<Instruction>(opd);
	  backtraceOperand(pInst->getOperand(0),0);
	  unsigned numOps = pInst->getNumOperands();

	  //NOTE: getelemptr instruction can have multiple indices. Currently considering last operand as desired index for qubit. This may not be true for multi-dimensional qubit arrays 
	  if(ConstantInt *CI = dyn_cast<ConstantInt>(pInst->getOperand(numOps-1))){
	    if(tmpDepQbit.size()==1){
	      tmpDepQbit[0].valOrIndex = CI->getZExtValue();
	    }
	  }
	  else{

	    if(tmpDepQbit[0].isQbit && !(tmpDepQbit[0].isPtr)){
     	      //NOTE: getelemptr instruction can have multiple indices. consider last operand as desired index for qubit. This may not be true for multi-dimensional qubit arrays
	      backtraceOperand(pInst->getOperand(numOps-1),1);
	      
	    }

	  }	 
	  /*
	    //For multi-dimensional qubit array, we may need to backtrace multiple pointer values
	    for(unsigned iop=1;iop<numOps;iop++){ //first opd was already backtraced
	      backtraceOperand(pInst->getOperand(iop),0);

	    }*/
	  return true;
	}
      
      if(Instruction* pInst = dyn_cast<Instruction>(opd)){
	unsigned numOps = pInst->getNumOperands();
	for(unsigned iop=0;iop<numOps;iop++){
	  btCount++;
	  backtraceOperand(pInst->getOperand(iop),0);
	  btCount--;
	}
	return true;
      }
      else{
	return true;
      }
    }
  else if(opOrIndex == 0){ //opOrIndex == 1; i.e. Backtracing for Index    
    if(btCount>MAX_BT_COUNT) //prevent infinite backtracing
      return true;

    if(ConstantInt *CI = dyn_cast<ConstantInt>(opd)){
      tmpDepQbit[0].valOrIndex = CI->getZExtValue();
      return true;
    }      

    if(Instruction* pInst = dyn_cast<Instruction>(opd)){
      unsigned numOps = pInst->getNumOperands();
      for(unsigned iop=0;iop<numOps;iop++){
	btCount++;
	backtraceOperand(pInst->getOperand(iop),1);
	btCount--;
      }
    }

  }
  else{ //opOrIndex == 2: backtracing to call inst MeasZ
    if(CallInst *endCI = dyn_cast<CallInst>(opd)){
      if(endCI->getCalledFunction()->getName().find("llvm.Meas") != string::npos){
	tmpDepQbit[0].argPtr = opd;

	return true;
      }
      else{
	if(Instruction* pInst = dyn_cast<Instruction>(opd)){
	  unsigned numOps = pInst->getNumOperands();
	  bool foundOne=false;
	  for(unsigned iop=0;(iop<numOps && !foundOne);iop++){
	    btCount++;
	    foundOne = foundOne || backtraceOperand(pInst->getOperand(iop),2);
	    btCount--;
	  }
	  return foundOne;
	}
      }
    }
    else{
      if(Instruction* pInst = dyn_cast<Instruction>(opd)){
	unsigned numOps = pInst->getNumOperands();
	bool foundOne=false;
	for(unsigned iop=0;(iop<numOps && !foundOne);iop++){
	  btCount++;
	  foundOne = foundOne || backtraceOperand(pInst->getOperand(iop),2);
	  btCount--;
	}
	return foundOne;
      }
    }
  }
  return false;
}


void QtmInst::print_qgate(qGate qg){
  errs() << qg.qFunc->getName() << " : ";
  for(int i=0;i<qg.numArgs;i++){
    errs() << qg.args[i].name << "[" << qg.args[i].index << "], "  ;
  }
  errs() << "\n";
}

void QtmInst::analyzeCallInst(Function* F, Instruction* pInst){
  if(CallInst *CI = dyn_cast<CallInst>(pInst))
    {      
      if(debugQtmInst)
	errs() << "Call inst: " << CI->getCalledFunction()->getName() << "\n";

      if(CI->getCalledFunction()->getName() == "store_cbit"){	//trace return values
	return;
      }      

      vector<QtmGateArg> allDepQbit;                                  
      
      bool tracked_operand = false;

      int myPrepState = -1;
      double myRotationAngle = 0.0;
      
      for(unsigned iop=0;iop<CI->getNumArgOperands();iop++){
	tmpDepQbit.clear();
	
	QtmGateArg tmpQGateArg;
	btCount=0;
	
	tmpQGateArg.argNum = iop;
		
	if(isa<UndefValue>(CI->getArgOperand(iop))){
	  errs() << "WARNING: LLVM IR code has UNDEF values. \n";
	  tmpQGateArg.isUndef = true;	
	  //exit(1);
	}
	
	Type* argType = CI->getArgOperand(iop)->getType();
	if(argType->isPointerTy()){
	  tmpQGateArg.isPtr = true;
	  Type *argElemType = argType->getPointerElementType();
	  if(argElemType->isIntegerTy(16))
	    tmpQGateArg.isQbit = true;
	  if(argElemType->isIntegerTy(1))
	    tmpQGateArg.isCbit = true;
	}
	else if(argType->isIntegerTy(16)){
	  tmpQGateArg.isQbit = true;
	  tmpQGateArg.valOrIndex = 0;	 
	}	  	
	else if(argType->isIntegerTy(1)){
	  tmpQGateArg.isCbit = true;
	  tmpQGateArg.valOrIndex = 0;	 
	}


	//check if argument is constant int
	if(ConstantInt *CInt = dyn_cast<ConstantInt>(CI->getArgOperand(iop))){
	  myPrepState = CInt->getZExtValue();	  
	}
	
	//check if argument is constant float
	if(ConstantFP *CFP = dyn_cast<ConstantFP>(CI->getArgOperand(iop))){
	  myRotationAngle = CFP->getValueAPF().convertToDouble();
	}	  	
	
        //if(tmpQGateArg.isQbit || tmpQGateArg.isCbit){
	if(tmpQGateArg.isQbit){
            tmpDepQbit.push_back(tmpQGateArg);	
            tracked_operand = backtraceOperand(CI->getArgOperand(iop),0);
	}

        if(tmpDepQbit.size()>0){	  
	  allDepQbit.push_back(tmpDepQbit[0]);
	  assert(tmpDepQbit.size() == 1 && "tmpDepQbit SIZE GT 1");
	  tmpDepQbit.clear();
	}
	
      }
      
      if(allDepQbit.size() > 0){
	if(debugQtmInst)
	{
	    errs() << "\nCall inst: " << CI->getCalledFunction()->getName();	    
	    errs() << ": Found all arguments: ";       
	    for(unsigned int vb=0; vb<allDepQbit.size(); vb++){
	      if(allDepQbit[vb].argPtr)
		errs() << allDepQbit[vb].argPtr->getName() <<" Index: ";
                                
	      //else
		errs() << allDepQbit[vb].valOrIndex <<" ";
	    }
	    errs()<<"\n";
	    
	}

          
       string fname =  CI->getCalledFunction()->getName();  
       qGate thisGate;
       thisGate.qFunc =  CI->getCalledFunction();

       if(myPrepState!=-1) thisGate.angle = (float)myPrepState;
       if(myRotationAngle!=0.0) thisGate.angle = myRotationAngle;

       for(unsigned int vb=0; vb<allDepQbit.size(); vb++){
            if(allDepQbit[vb].argPtr){
	      //errs() << allDepQbit[vb].argPtr->getName() <<" Index: ";
	      //errs() << allDepQbit[vb].valOrIndex <<"\n";
	      QtmGateArg param =  allDepQbit[vb];       
                thisGate.args[thisGate.numArgs].name = param.argPtr->getName();
		if(!param.isPtr)
		  thisGate.args[thisGate.numArgs].index = param.valOrIndex;
                thisGate.numArgs++;
	    }
       }

       print_qgate(thisGate);

      }    
      allDepQbit.erase(allDepQbit.begin(),allDepQbit.end());
    }
}

bool QtmInst::runOnModule (Module &M) {
  
  // iterate over all functions, and over all instructions in those functions
  CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot();
  
  //Post-order
  for (scc_iterator<CallGraphNode*> sccIb = scc_begin(rootNode), E = scc_end(rootNode); sccIb != E; ++sccIb) {
    const std::vector<CallGraphNode*> &nextSCC = *sccIb;
    for (std::vector<CallGraphNode*>::const_iterator nsccI = nextSCC.begin(), E = nextSCC.end(); nsccI != E; ++nsccI) {
      Function *F = (*nsccI)->getFunction();	  
            
      if(F && !F->isDeclaration()){
	errs() << "\n#Function " << F->getName() << "\n";      
       	
	for (inst_iterator I = inst_begin(*F), E = inst_end(*F); I != E; ++I) {
	  Instruction *Inst = &*I;                            // Grab pointer to instruction reference
	  if(isa<CallInst>(Inst))
	    analyzeCallInst(F,Inst);	

	}
	
      }
      else{
	    if(debugQtmInst)
	      errs() << "WARNING: Ignoring external node or dummy function.\n";
	  }
    }
  }

  return false;
} // End runOnModule