/********************************************************************************
 *
 * Example Usage:
 * 	opt -load /home/yancai/Research/llvm/build362/lib/LLVMDFixer.so -dfixer -dlkFile=deadlock.dlk -cmdFile=./fixingCmd  < ./deadlock.bc
 * 	or,
 * 	opt -load LLVMDFixer.so -dfixer -dlkFile=deadlock.dlk -cmdFile=./fixingCmd  ./deadlock.bc
 *
 * 	where, '-load LLVMDFixer.so -dfixer' tells LLVM.opt to load DFixer library, and
 * 			'-dlkFile=deadlock.dlk -cmdFile=./fixingCmd' tells DFixer the deadlock description file
 * 			and the fixing command file (output file), respectively.
 *
 *
 * Example Compile and Link (g++ or clang++):
 *   clang++ -g -pthread -I/home/yancai/Research/llvm/dfixer/dfixer_lib/ -c -o  deadlock2.o ./deadlock2.cpp
 *   clang++ -g -pthread deadlock2.o /home/yancai/Research/llvm/dfixer/dfixer_lib/dfixer_lib.o -o deadlock2.out
 *
 ********************************************************************************/


#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Support/CommandLine.h"

#include "llvm/IR/CFG.h"
#include "llvm/Support/raw_ostream.h"

#include <stack>
#include <set>
#include <list>
#include <vector>
#include <fstream>
#include <string>
#include <iostream>
#include <sstream>


using namespace llvm;
using namespace std;
using namespace cl;


namespace
{

enum Color
{
	NotVisited,
	Visiting,
	Visited
};

typedef DenseMap<const BasicBlock *, Color> BBColorMap;


//default synchronization primitives
string acqName("pthread_mutex_lock");
string relName("pthread_mutex_unlock");
string waitName("pthread_cond_wait");
string notifyName("pthread_cond_signal");
string preAcqName("preAcq_pthread_mutex_lock");
string tryAcqName("pthread_mutex_trylock");


//DFixer options
cl::opt<string> dlkFile("dlkFile", cl::desc("Specify deadlock description filename"), cl::value_desc("filename"));
cl::opt<string> cmdFile("cmdFile", cl::desc("Specify fixing command filename"), cl::value_desc("cmdFilename"));


struct PerThread;

std::list<PerThread*> allThreads;

struct PerThread
{
	public:
		string wLock;
		string hLock;
		string wAcqFile;
		string wRelFile;
		string hAcqFile;
		string hRelFile;

		int wAcqRow, wAcqCol, wRelRow, wRelCol;
		int hAcqRow, hAcqCol, hRelRow, hRelCol;

		const CallInst* wInst;
		const CallInst* hInst;

		//Currently, DFixer searches for call stack (i.e., path). It may also be specified by users.
		std::vector<const BasicBlock*> path;

		std::vector<const BasicBlock*> bbInLoop;
		const Instruction* firstCallInPath;

		std::vector<const llvm::CallInst*> Lp;
		std::vector<const llvm::CallInst*> WNk;

		bool isSingleEntry	= true;
		bool isSingleExit	= true;
		bool hasLoop		= false;

		/** if wInst and hInst are in two different functions, callingBlock is the last one in hFunc from path **/
		const BasicBlock* callingBlock = NULL;


		string fixingCmd = "";


		void read(string aLine)
		{
			//aline is: "wLock	wFile1.cpp	wAcqRow wAcqCol wFile2.cpp wRelRow wRelCol	hLock hFile.cpp hAcqRow hAcqCol hFile2.cpp hRelRow hRelCol"
			istringstream parseLine(aLine);

			parseLine >> wLock >> wAcqFile >> wAcqRow >> wAcqCol >> wRelFile >> wRelRow >> wRelCol;
			parseLine >> hLock >> hAcqFile >> hAcqRow >> hAcqCol >> hRelFile >> hRelRow >> hRelCol;

			print();
		}

		//debug
		void print()
		{
			errs() <<"wait for lock: "<< wLock << " at " << wAcqFile << ", " << wAcqRow << ":" << wAcqCol << " (release at: " << wRelFile <<", " <<wRelRow <<":" <<wRelCol <<'\n';
			errs() <<"hold lock: "	  << hLock << " at " << hAcqFile << ", " << hAcqRow << ":" << hAcqCol << " (release at: " << hRelFile <<", " <<hRelRow <<":" <<hRelCol <<'\n';
		}

		//debug
		void printHSite()
		{
			if(hInst != NULL)
			{
				errs() <<"------------------.\n";

				DILocation loc( hInst->getMetadata("dbg") );

				errs() <<"HSite is: line-"<< loc.getLineNumber()<<", col-"<<loc.getColumnNumber()<<'\n' ;
				errs() <<"hold lock: "	  << hLock << " at file "<<hAcqFile<< ", "<<hAcqRow<<":"<<hAcqCol<<"\n";

				hInst->dump();

				errs() <<"------------------.\n";
			}
			else
				errs() <<"hInst is null.\n";
		}

		//debug
		void printPath()
		{
			errs() <<"-------------------- Path -----------------------------\n";
			for(auto bb: path)
			{
				errs()<<"from function: "<< bb->getParent()->getName()<<'\n';
				bb->dump();
			}
			errs() <<"-------------------------------------------------------\n";
		}

		bool isWCallIns(const CallInst* inst)
		{
			DILocation loc(inst->getMetadata("dbg"));

			if(loc.getLineNumber() != wAcqRow  || loc.getColumnNumber() != wAcqCol) return false;

			if(loc.getFilename().endswith(wAcqFile))
			{
				assert(inst->getNumOperands() >1 && inst->getOperand( inst->getNumOperands() - 1 )->getName().str() == acqName);
				assert(inst->getNumArgOperands() >0 && inst->getArgOperand(0)->getName().equals(wLock));

				errs() <<"Found wLock site.\n";

				loc.dump();
				wInst = inst;

				return true;
			}

			return false;
		}

		bool isHCallIns(const CallInst* inst)
		{
			DILocation loc( inst->getMetadata("dbg") );

			if(loc.getLineNumber() != hAcqRow  || loc.getColumnNumber() != hAcqCol) return false;

			//file name
			if(loc.getFilename().endswith(hAcqFile))
			{
				assert(inst->getNumOperands() >1 && inst->getOperand( inst->getNumOperands() - 1 )->getName().str() == acqName);
				assert(inst->getNumArgOperands() >0 && inst->getArgOperand(0)->getName().equals(hLock));

				errs() <<"Found hLock site.\n";

				loc.dump();
				hInst = inst;

 				return true;
			}

			return false;
		}

		bool ignoreCallIns(const llvm::CallInst* callIns)
		{
			const StringRef calledName = callIns->getCalledFunction()->getName();

//			errs()<<"Ignore call "<< calledName <<"?\n";

			//TODO: add more if necessary

			if(	calledName.startswith("llvm.")  ||
				calledName.startswith("printf")
			)
			{
				errs()<<"Ignored call "<< calledName <<"\n";
				return true;
			}

			return false;
		}

		bool findPath()
		{
			bool foundPath = findPathDFS(hInst->getParent());
			colorMap.clear();

			if(foundPath)
			{
				printPath();
			}

			return foundPath;
		}

		BBColorMap colorMap;

		//recursive find basic blocks of paths, may enter a called function.
		bool findPathDFS(const BasicBlock* aBlock)
		{
			if(colorMap.find(aBlock) != colorMap.end()) return false;

//			errs() <<"Enter findPathDFS, BB: "<<B->getName()<<'\n';

			colorMap[aBlock] = Visiting;

			path.push_back(aBlock);

			//search current Block
			for(auto it= aBlock->begin();it!= aBlock->end(); it++)
			{
//				errs()<<"Inst: ";
//				(*it).dump();
				if (auto callIns = llvm::dyn_cast<llvm::CallInst>(&(*it)))
				{
//					errs() <<"call at: ";
//					callIns->getDebugLoc().dump();

					if(ignoreCallIns(callIns)) continue;

					if(isWCallIns(callIns)) return true;

					//DFS into function
					llvm::Function* called = callIns->getCalledFunction();

					if(called != NULL)
					{
//						callIns->dump();
//						called->dump();

						if(called->empty()) continue;

//						errs()<<"To analyze: "<<called->getName()<<'\n';

						if(findPathDFS( &called->getEntryBlock() ))
						{
							if(callIns->getParent()->getParent() == hInst->getParent()->getParent())
							{
								firstCallInPath = callIns;
							}
							return true;
						}
					}
				}
			}

			//recursive searching all successor Blocks
			const TerminatorInst *terInst = aBlock->getTerminator();
			for (unsigned I = 0, succNO = terInst->getNumSuccessors(); I < succNO; ++I)
			{
				if( findPathDFS(terInst->getSuccessor(I)))
					return true;
			}
			colorMap[aBlock] = Visited;
			path.pop_back();

			return false;
		}

		////

		void scanControlFlow()
		{
			assert (path.empty() == false);

			const BasicBlock* hBlock = path.front();
			const BasicBlock* wBlock = path.back();

			const llvm::Function* hFunc = hBlock->getParent();
			const llvm::Function* wFunc = wBlock->getParent();

			//multiple entries or multiple exits?

			//case 1: two functions
			if(hFunc != wFunc)
			{
				isSingleEntry = false;

				/**
				 * TODO: is it necessary to search all other exits along path, to improve performance?
				 * 		but it also makes fixing complicated
				 *
				 * Find the 1st called function in path, and check whether each path from hBlock to endBlock
				 * contains the called function
				 *
				 * TODO: make sure that Function.front() and Function.back() return the very beginning block
				 * 		and the very last block, respectively.
				 **/

				for(auto it = path.begin(); it != path.end(); it++)
				{
//					errs() <<"Path block: "<< (*it)->getName()<<" from function: " << (*it)->getParent()->getName() <<'\n';

					if( hFunc != (*it)->getParent() )
					{
						it--;
						callingBlock = *(it);
						break;
					}
				}

				assert(callingBlock != NULL);

//				errs() <<"Calling block: "<< callingBlock->getName()<<'\n';

				isSingleExit = isInEachFromTo(hBlock, &hFunc->back(), callingBlock);

			}
			//case 2: one function
			else
			{
				isSingleEntry	= isInEachFromTo(&hFunc->front(), wBlock, hBlock);
				isSingleExit	= isInEachFromTo(hBlock, &hFunc->back(), wBlock);
			}

			//any loop
			for(int i=0; i< path.size(); i++)
			{
				const llvm::BasicBlock* bb = path[i];
				const StringRef bbName = bb->getName();

				if(bbName.startswith("for.cond") || bbName.startswith("while.cond"))
				{
					bool hasEnd = false;

					//validate whether the loop wraps our target block.
					for(int inner_i = i+1; inner_i < path.size(); inner_i ++)
					{
						const llvm::BasicBlock* leftBB = path[inner_i];
						if(bb->getParent() != leftBB->getParent()) continue;

						const StringRef leftBBName = leftBB->getName();
						if( (leftBBName.startswith("for.end") || leftBBName.startswith("while.end") )
								&& bb == leftBB->getSinglePredecessor())
							hasEnd = true;
					}

					if( ! hasEnd) bbInLoop.push_back(bb);
					//test
//					errs() <<"Found loop: \n";
//					bb->dump();
				}

				for(auto insIt = bb->begin(); insIt != bb->end(); insIt ++)
				{
					if (auto callIns = llvm::dyn_cast<llvm::CallInst>(&(*insIt)))
					{
						if(ignoreCallIns(callIns)) continue;

						if(callIns->getNumOperands() >1)
						{
							unsigned NOOperand = callIns->getNumOperands();
							if(callIns->getOperand( NOOperand -1)->getName().str() == acqName )
							{
								if( callIns != hInst && callIns != wInst)
									Lp.push_back(callIns);
							}
							else if(callIns->getOperand( NOOperand -1)->getName().str() == waitName)
							{
								WNk.push_back(callIns);
							}

						}
					}
				}//
			}

			if(bbInLoop.size() > 0) hasLoop = true;

			errs() <<" Done scanning control flow:\n";
			errs() <<"  isSingleEntry: "<< (isSingleEntry? "Yes" : "No") <<'\n';
			errs() <<"  isSingleExit: "<< (isSingleExit? "Yes" : "No") <<'\n';
			errs() <<"  hasLoop:      "<< (hasLoop? "Yes" : "No") << ", # of loops: "<< bbInLoop.size() <<'\n';
		}

		std::size_t getPriority() const
		{
			return this->WNk.size() + this->Lp.size();
		}

		bool operator () (const PerThread* first, const PerThread* second)
		{
			return  first->getPriority() < second->getPriority();
		}

		/**
		 * Currently, all blocks should be within a same function.
		 * TODO: extend this implementation to find all early returns without reaching wSite.
		 **/
		bool isInEachFromTo(const BasicBlock* fromBlock, const BasicBlock* toBlock, const BasicBlock* targetBlock)
		{
			assert(fromBlock->getParent() == toBlock->getParent());

//			errs() <<"check from "<<fromBlock->getName() << " to " << toBlock->getName() <<", target: " << targetBlock->getName() <<'\n';
			if(targetBlock == fromBlock || targetBlock == toBlock ) return true;
			if(fromBlock == toBlock) return false;

			const TerminatorInst *terInst = fromBlock->getTerminator();
			for (unsigned I = 0, succNO = terInst->getNumSuccessors(); I < succNO; ++I)
			{
				if( ! isInEachFromTo(terInst->getSuccessor(I), toBlock, targetBlock) )
					return false;
			}

			return true;
		}

		/**
		 *	find all first blocks that do not bypass targetBlock from fromBlock to toBlock
		 *	@return whether any reachable block found.
		 **/
		bool findBlocksSkipTarget(const BasicBlock* fromBlock, const BasicBlock* toBlock,
				const BasicBlock* targetBlock,
				std::set<const BasicBlock*>& retBlocks)
		{
			if (targetBlock == fromBlock ||
					targetBlock == toBlock ) return true;

			if(fromBlock == toBlock) return false;

			std::set<const BasicBlock*> thisRetBlocks;

			const TerminatorInst *terInst = fromBlock->getTerminator();
			unsigned succNO = terInst->getNumSuccessors();
			unsigned reachedNO = 0;

			for (unsigned I = 0; I < succNO; ++I)
			{
				if( findBlocksSkipTarget(terInst->getSuccessor(I), toBlock, targetBlock, thisRetBlocks) )
					reachedNO ++;
			}

			//Three cases:
			//case 1: all successors reach targetBlock, return thisRetBlocks.
			if (reachedNO == succNO )
			{
				retBlocks.insert(thisRetBlocks.begin(), thisRetBlocks.end());
			}
			//case 2: no successor reach targetBlock, return { fromBlock }, i.e., the current block.
			else if( reachedNO == 0)
			{
				retBlocks.insert(fromBlock);
			}
			//case 3: some successors reach targetBlock but some do not reach targetBlock,
			//return all returned from reaching successors
			else
			{
				retBlocks.insert(thisRetBlocks.begin(), thisRetBlocks.end());
			}

			return reachedNO != 0;
		}

		//Add a string right before (file, lineNO, colNO, aLine)
		const char* cmd_A_format = "A %s %d:%d \t/* DFixer added:*/ %s\n";

		//Delete chars from (file, lineNO, colNO) until a ';' is encountered.
		//Here, deleting means replace of each char with a space for convenience.
		const char* cmd_D_format = "D %s %d:%d \t/* DFixer: %s*/\n";

		//Append a string right after the statement (file, lineNO, colNO, aLine).
		const char* cmd_P_format = "P %s %d:%d \t/* DFixer appended:*/ %s\n";

		/**
		 * TODO:
		 *  Is the following possible?
		 *  if a generated statement should be put together with an immediate statement
		 *  after/before the generated one, but before fixing, the statement is within a "if" block
		 * 	and there is not pair of "{" and "}" to limit the scope of "if.body". E.g.,
		 * 	 - Before: "if(...) XXX;"
		 * 	 - After:  "if(...) Patched; XXX;", which should be "if(...){ Patched; XXX;}".
		 * 	 How to fix it?
		 */

		void genFixingCommand()
		{
			char* buffer = new char[1024];
			string tmp = "";

			fixingCmd.append("// DFixer command {{{\n");

			//step 1: generate preAcquire(hLock & wLock) call
			sprintf(buffer, cmd_D_format, hAcqFile.c_str(), hAcqRow, hAcqCol, "original hLock");
			fixingCmd.append(buffer);

			sprintf(buffer, cmd_D_format, hAcqFile.c_str(), wAcqRow, hAcqCol, "original wLock");
			fixingCmd.append(buffer);

			if(isSingleEntry)
			{
				sprintf(buffer, "/* DFixer preAcquisitoin */ %s(& %s, & %s);", preAcqName.c_str(), hLock.c_str(), wLock.c_str());
			}
			else
				//add: "v_w = true"
			{
				sprintf(buffer, "/* DFixer preAcquisitoin */ %s(& %s, & %s); /* DFixer multiple entries (set) */ setPreAcqTaken ( & %s );",
						preAcqName.c_str(), hLock.c_str(), wLock.c_str(),  wLock.c_str());
			}
			tmp.clear();
			tmp.append(buffer);

			sprintf(buffer, cmd_A_format, hAcqFile.c_str(), hAcqRow, hAcqCol,  tmp.c_str());
			fixingCmd.append(buffer);


			//step 2: a branch condition?
			if( ! isSingleEntry)
			{
				//add: "v_w = true"
				//sprintf(buffer, "/* DFixer multiple entries (set) */ setPreAcqTaken ( & %s );", wLock.c_str());
				//tmp.clear();
				//tmp.append(buffer);

				//sprintf(buffer, cmd_A_format, hAcqFile.c_str(), hAcqRow, hAcqCol, tmp.c_str());
				//fixingCmd.append(buffer);

				//add: if(! v_w) { acq(wLock); }
				sprintf(buffer, "/* DFixer multiple entries (clear)*/  if( ! preAcqTaken( & %s )) { %s( &%s); } ",
						wLock.c_str(), acqName.c_str(), wLock.c_str() );
				tmp.clear();
				tmp.append(buffer);

				sprintf(buffer, cmd_A_format, wAcqFile.c_str(), wAcqRow, wAcqCol, tmp.c_str());
				fixingCmd.append(buffer);

				//add: v_w = false; right before original rel(w)
				sprintf(buffer, "/* DFixer multiple entries (clear) */  clearPreAcq( & %s);  ", wLock.c_str() );
				tmp.clear();
				tmp.append(buffer);

				sprintf(buffer, cmd_A_format, wRelFile.c_str(), wRelRow, wRelCol, tmp.c_str());
				fixingCmd.append(buffer);
			}


			//step 3: any release on other branch?
			//TODO: currently, we only take a single function containing hSite
			if( ! isSingleExit)
			{
				if(isSingleEntry)
				{
					sprintf(buffer, "/* DFixer multiple exits */ if( ! preAcqTaken( & %s )) {%s ( & %s ); } ",
							wLock.c_str(), relName.c_str(), wLock.c_str());
				}
				else
					//clear again
				{
					sprintf(buffer, "/* DFixer multiple exits */ if( ! preAcqTaken( & %s )) {%s ( & %s ); "
							"/* DFixer multiple entries (clear again) */  clearPreAcq( & %s); } ",
							wLock.c_str(), relName.c_str(), wLock.c_str(), wLock.c_str());
				}
				tmp.clear();
				tmp.append(buffer);

				const BasicBlock* targetBlock;

				//TODO: for each branch, add the line
				if(wInst->getParent()->getParent() != hInst->getParent()->getParent())
				{
					targetBlock = this->callingBlock;
				}
				else targetBlock = wInst->getParent();

				std::set<const BasicBlock*> blocksToPatch;

				//bool reachable =
				findBlocksSkipTarget(hInst->getParent(), &(hInst->getParent()->getParent()->back()),
						targetBlock, blocksToPatch);

//				errs() <<"++++ BlocksToPatch, size: "<< blocksToPatch.size()<<'\n';

				/**
				 * Optimization: some control flows may contain multiple blocks where Multiple-exits-handlers
				 * are to be inserted. Just remove them.
				 * */
				bool changed = false;
				do{
					changed = false;

					for(auto bb: blocksToPatch)
					{
						const Instruction* ins = bb->getFirstNonPHI();
						if(auto brIns = llvm::dyn_cast<llvm::BranchInst>(ins))
						{
							if( brIns->isUnconditional())
							{
								//Now, the case is two blocks (bb -> nextBB), we should remove bb and insert nextBB.
								errs()<<" Erase: " <<bb->getName()<<'\n';
								blocksToPatch.erase(bb);

								const BasicBlock* nextBB = brIns->getSuccessor(0);
								errs()<<" Insert: " <<nextBB->getName()<<'\n';
								blocksToPatch.insert(nextBB);

								changed = true;
								break;
							}
						}
					}
				}while(changed);


//				errs()<<" Num blocks to patch: "<< blocksToPatch.size()<<'\n';

				int rowNO, colNO;

				for(auto bb: blocksToPatch)
				{
					//errs() <<"++++ BlocksToPatch, name: "<<bb->getName()<<'\n';

					//TODO: something wrong with position of the first insertion point of each block, correct it.
					const DebugLoc debugLoc = bb->getFirstNonPHI()->getDebugLoc();
					rowNO = debugLoc.getLine();
					colNO = debugLoc.getCol();

//					errs()<<" Insert multiple exits handler at: "<<rowNO<<":"<<colNO<<'\n';

					sprintf(buffer, cmd_A_format, hAcqFile.c_str(), rowNO, colNO, tmp.c_str());
					fixingCmd.append(buffer);
				}
				//hInst->getParent()->getParent()->viewCFG();
			}


			//step 4: any loops?
			/**
			 * Take rel(wLock) out of any loop containing the original acq(wLock).
			 * Currently, we simplify them as two cases depending on whether the hLock and wLock are within a same function.
			 **/
			if(hasLoop)
			{
				int rowNO, colNO;
				if(wInst->getParent()->getParent() == hInst->getParent()->getParent())
				{
					//find the out-most loop and add a rel into the loop.end
					const BasicBlock* succBB = NULL;
					const TerminatorInst *terInst = (bbInLoop[0])->getTerminator();
					for (unsigned I = 0, succNO = terInst->getNumSuccessors(); I < succNO; ++I)
					{
						succBB = terInst->getSuccessor(I);
						const StringRef succBBName = succBB->getName();
						if(succBBName.startswith("for.end") || succBBName.startswith("while.end"))
						{
							break;
						}
					}
					assert(succBB != NULL);

					const llvm::Instruction* firstIns = succBB->getFirstNonPHI();
					const DebugLoc debugLoc = firstIns->getDebugLoc();

					rowNO = debugLoc.getLine();
					colNO = debugLoc.getCol();
				}
				else
				{
					//find the callInst and add a rel right after the call
					assert(firstCallInPath != NULL);
					const DebugLoc debugLoc = firstCallInPath->getDebugLoc();
					rowNO = debugLoc.getLine();
					colNO = debugLoc.getCol();
				}

				//take out rel statement

				if(isSingleEntry)
				{
					sprintf(buffer, "/* DFixer: loop */ if ( preAcqTaken( & %s) ) { %s ( & %s ); } ",
							wLock.c_str(), relName.c_str(), wLock.c_str());
				}
				else
					//and clear: v_hw=false
				{
					sprintf(buffer, "/* DFixer: loop */ if ( preAcqTaken( & %s) ) { %s ( & %s ); "
									"/* DFixer multiple entries (clear again) */  clearPreAcq( & %s); } ",
							wLock.c_str(), relName.c_str(), wLock.c_str(), wLock.c_str() );
				}
				tmp.clear();
				tmp.append(buffer);

				sprintf(buffer, cmd_P_format, hAcqFile.c_str(), rowNO, colNO, tmp.c_str());
				fixingCmd.append(buffer);


				//remove original statement
				sprintf(buffer, cmd_D_format, wRelFile.c_str(), wRelRow, wRelCol, "original rel(wLock) in loop");
				fixingCmd.append(buffer);

				sprintf(buffer, "/* DFixer: loop */ if ( !preAcqTaken( & %s) ) { %s ( & %s); }",
						wLock.c_str(), relName.c_str(), wLock.c_str());
				tmp.clear();
				tmp.append(buffer);

				sprintf(buffer, cmd_A_format, wRelFile.c_str(), wRelRow, wRelCol, tmp.c_str());
				fixingCmd.append(buffer);
			}


			//step 5: other locks and wait().
			//other locks
			if(Lp.size() >0 )
			{
				for(auto callInst: Lp)
				{
					/* Original: acq(p)
					 * After: v_hw = true; rel(w); acq(w&p); v_hw = false;
					 */
					DILocation loc( callInst->getMetadata("dbg") );

					sprintf(buffer, cmd_D_format, loc.getFilename().data(), loc.getLineNumber(), loc.getColumnNumber(),
							" original third lock.");
					fixingCmd.append(buffer);

					sprintf(buffer, "/* DFixer: handle other lock acquisitions */ "
							"setHWCondOn( &%s, &%s); %s( &%s); %s( &%s, &%s); "
							"setHWCondOff( &%s, &%s);",
							hLock.c_str(), wLock.c_str(),
							relName.c_str(), wLock.c_str(),
							preAcqName.c_str(), callInst->getOperand(0)->getName().data(), wLock.c_str(),
							hLock.c_str(), wLock.c_str());

					tmp.clear();
					tmp.append(buffer);

					sprintf(buffer, cmd_A_format, loc.getFilename().data(), loc.getLineNumber(), loc.getColumnNumber(), tmp.c_str());
					fixingCmd.append(buffer);
				}

				const PerThread* aSecondThread = NULL;

				for(auto aThread: allThreads)
				{
					if(aThread->hLock == this->wLock)
					{
						aSecondThread = aThread;
						break;
					}
				}

				assert(aSecondThread != NULL);

				/* Original: acq(p)
				 * After: while(tryAcq(w){ if(v_hw) rel(w); else break; }
				 */

				DILocation loc( aSecondThread->hInst->getMetadata("dbg") );

				sprintf(buffer, cmd_D_format, loc.getFilename().data(), loc.getLineNumber(), loc.getColumnNumber(),
						" original acq(h) of a second thread. ");
				fixingCmd.append(buffer);

				sprintf(buffer, "/* DFixer: handle other lock acquisitions (the second thread) */ "
						" while(%s(&%s)){ if( getHWCond( &%s, &%s)) %s(&%s); else break; } ",
						tryAcqName.c_str(), aSecondThread->hLock.c_str(),
						aSecondThread->hLock.c_str(), aSecondThread->wLock.c_str(),
						relName.c_str(), aSecondThread->hLock.c_str());
				tmp.clear();
				tmp.append(buffer);

				sprintf(buffer, cmd_A_format, loc.getFilename().data(), loc.getLineNumber(), loc.getColumnNumber(), tmp.c_str());
				fixingCmd.append(buffer);
			}

			//wait()
			if( WNk.size() > 0)
			{
				for(auto callInst: WNk)
				{
					//a special case: the lock k of wait(k) is actually hLock.
					if(callInst->getOperand(1)->getName().equals(hLock) ) continue;

					/* Original: wait(p)
					 * After: v_hw = true; rel(w); wait(p); rel(p); acq(w&p); v_hw = false;
					 */

					DILocation loc( callInst->getMetadata("dbg") );

					sprintf(buffer, cmd_D_format, loc.getFilename().data(), loc.getLineNumber(), loc.getColumnNumber(), " original third lock.");
					fixingCmd.append(buffer);

					const char* lockK = callInst->getOperand(1)->getName().data();
					const char* lockCond = callInst->getOperand(0)->getName().data();

					sprintf(buffer, "/* DFixer: handle wait(k) */ setHWCondOn( &%s, &%s);"
							" %s(&%s); %s(&%s, &%s); "
							"%s( &%s); %s( &%s, &%s); "
							"setHWCondOff( &%s, &%s);",

							hLock.c_str(), wLock.c_str(),
							relName.c_str(), wLock.c_str(),
							waitName.c_str(), lockCond, lockK,
							relName.c_str(), lockK,
							preAcqName.c_str(), lockK, wLock.c_str(),
							hLock.c_str(), wLock.c_str());

					tmp.clear();
					tmp.append(buffer);

					sprintf(buffer, cmd_A_format, loc.getFilename().data(), loc.getLineNumber(), loc.getColumnNumber(), tmp.c_str());
					fixingCmd.append(buffer);
				}
			}

			fixingCmd.append("// }}}\n\n");

			//errs() <<fixingCmd.c_str();

			delete buffer;
		}
};


void loadSyncs(string aLine )
{
	istringstream parseLine(aLine);
	string tmp;
	parseLine>>tmp;
	if(tmp == "acq:")			parseLine >>acqName;
	else if(tmp == "rel:")		parseLine >>relName;
	else if(tmp == "wait:")		parseLine >>waitName;
	else if(tmp == "notify:")	parseLine >>notifyName;
	//TODO: add more
}


void loadADeadlock()
{
	errs()<<" Deadlock File: " <<::dlkFile<<'\n';
	std::ifstream dlkStream(dlkFile);

	string aLine;
	getline(dlkStream, aLine);

	int threadsNO;
	istringstream parseLine(aLine);

	parseLine>>threadsNO;

	errs() <<"NO of threads: "<<threadsNO<<'\n';

	//load deadlocks
	for(int i=0; i< threadsNO; i++)
	{
		getline(dlkStream, aLine);

		PerThread* aThread = new PerThread;
		aThread->read(aLine);
		allThreads.push_back(aThread);
	}

	//load sync primitives
	while(getline(dlkStream, aLine))
	{
		loadSyncs(aLine);
	}

//	errs() <<"acq: "<< acqName <<", rel: " << relName <<", wait: "<<waitName<<", notify: "<<notifyName<<'\n';

	dlkStream.close();
}

void saveFixingCmd()
{
	//save to cmdFile
	ofstream cmdFileStream;
	cmdFileStream.open(cmdFile, ios::out | ios::trunc);

	allThreads.sort(PerThread());

	int i = 1;
	for(auto aThread: allThreads)
	{
		cmdFileStream << "# Fixing "<< i <<'\n';
		cmdFileStream << aThread->fixingCmd.c_str() <<'\n';

		errs() << "# Fixing "<< i <<'\n';
		errs() <<aThread->fixingCmd.c_str() << "\n";

		i++;
	}
	cmdFileStream.close();
}


struct DFixer: public ModulePass
{
		static char ID;
		DFixer() : ModulePass(ID)
		{
			errs() <<" Running DFixer ...\n";
			loadADeadlock();
		}

		bool runOnModule(Module &M) override
		{
			for(auto aThread: allThreads)
			{
				if( !findHSite(M, aThread))
				{
					errs()<<"Failed to find HSite.\n";
					exit(0);
				}else
					aThread->printHSite();

				if( !aThread->findPath())
				{
					errs() <<"Failed to find WSite.\n";
					exit(0);
				}
				aThread->scanControlFlow();
			}

			for(auto aThread: allThreads)
			{
				aThread->genFixingCommand();
			}

			saveFixingCmd();
			return false;
		}

		bool findHSite(Module& M, PerThread* aThread)
		{
			for(auto &Func: M)
			{
				//add filter here...
//				errs() <<"----------------------------------------\n";
//				errs() <<"Enter function: "<< Func.getName()<<'\n';
//				if(Func.getName().equals("_Z2f4v")) Func.viewCFG();
//				Func.dump();
//				errs() <<"----------------------------------------\n";
				for(auto &BB : Func)
				{
					for(auto &Ins: BB)
					{
						if (auto callIns = llvm::dyn_cast<llvm::CallInst>(&Ins))
						{
							if(aThread->isHCallIns(callIns))
							{
								return true;
							}
						}
					}
				}
			}
			return false;
		}

};
}

char DFixer::ID = 0;
static RegisterPass<DFixer> X("dfixer", "Automated Deadlock Fixing");
