<commit_before>package shadow.output.llvm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.UnsupportedEncodingException;
import java.math.BigInteger;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

import shadow.CompileException;
import shadow.ShadowException;
import shadow.interpreter.InterpreterException;
import shadow.interpreter.ShadowBoolean;
import shadow.interpreter.ShadowCode;
import shadow.interpreter.ShadowDouble;
import shadow.interpreter.ShadowFloat;
import shadow.interpreter.ShadowInteger;
import shadow.interpreter.ShadowInterpreter;
import shadow.interpreter.ShadowNull;
import shadow.interpreter.ShadowString;
import shadow.interpreter.ShadowUndefined;
import shadow.interpreter.ShadowValue;
import shadow.output.AbstractOutput;
import shadow.output.Cleanup;
import shadow.output.TabbedLineWriter;
import shadow.parse.Context;
import shadow.tac.TACBlock;
import shadow.tac.TACConstant;
import shadow.tac.TACMethod;
import shadow.tac.TACModule;
import shadow.tac.TACVariable;
import shadow.tac.nodes.TACAllocateVariable;
import shadow.tac.nodes.TACArrayRef;
import shadow.tac.nodes.TACBaseClass;
import shadow.tac.nodes.TACBinary;
import shadow.tac.nodes.TACBranch;
import shadow.tac.nodes.TACCall;
import shadow.tac.nodes.TACCast;
import shadow.tac.nodes.TACCatch;
import shadow.tac.nodes.TACChangeReferenceCount;
import shadow.tac.nodes.TACClass;
import shadow.tac.nodes.TACConstantRef;
import shadow.tac.nodes.TACCopyMemory;
import shadow.tac.nodes.TACFieldRef;
import shadow.tac.nodes.TACGenericArrayRef;
import shadow.tac.nodes.TACGlobalRef;
import shadow.tac.nodes.TACLabel;
import shadow.tac.nodes.TACLabelAddress;
import shadow.tac.nodes.TACLandingpad;
import shadow.tac.nodes.TACLength;
import shadow.tac.nodes.TACLoad;
import shadow.tac.nodes.TACLocalLoad;
import shadow.tac.nodes.TACLocalStorage;
import shadow.tac.nodes.TACLocalStore;
import shadow.tac.nodes.TACLongToPointer;
import shadow.tac.nodes.TACMethodRef;
import shadow.tac.nodes.TACNewArray;
import shadow.tac.nodes.TACNewObject;
import shadow.tac.nodes.TACNode;
import shadow.tac.nodes.TACOperand;
import shadow.tac.nodes.TACParameter;
import shadow.tac.nodes.TACPhi;
import shadow.tac.nodes.TACPointerToLong;
import shadow.tac.nodes.TACReference;
import shadow.tac.nodes.TACResume;
import shadow.tac.nodes.TACReturn;
import shadow.tac.nodes.TACSequence;
import shadow.tac.nodes.TACSequenceElement;
import shadow.tac.nodes.TACSingletonRef;
import shadow.tac.nodes.TACStore;
import shadow.tac.nodes.TACThrow;
import shadow.tac.nodes.TACTypeId;
import shadow.tac.nodes.TACUnary;
import shadow.tac.nodes.TACUpdate;
import shadow.typecheck.TypeCheckException;
import shadow.typecheck.type.ArrayType;
import shadow.typecheck.type.ClassType;
import shadow.typecheck.type.InterfaceType;
import shadow.typecheck.type.MethodSignature;
import shadow.typecheck.type.MethodTableType;
import shadow.typecheck.type.ModifiedType;
import shadow.typecheck.type.PointerType;
import shadow.typecheck.type.SequenceType;
import shadow.typecheck.type.SimpleModifiedType;
import shadow.typecheck.type.SingletonType;
import shadow.typecheck.type.Type;
import shadow.typecheck.type.TypeParameter;

public class LLVMOutput extends AbstractOutput {
	private Process process = null;
	private int tempCounter = 0;
	private List<String> stringLiterals = new LinkedList<String>();	
	private HashSet<Type> unparameterizedGenerics = new HashSet<Type>();
	private int classCounter = 0;
	private HashSet<MethodSignature> usedSignatures = new HashSet<MethodSignature>();
	private HashSet<TACConstantRef> usedConstants = new HashSet<TACConstantRef>();

	private Set<String> genericClasses = new TreeSet<String>();
	private Set<String> arrayClasses = new TreeSet<String>();

	private TACModule module;
	private boolean skipMethod = false;
	
	private final ArrayType OBJECT_ARRAY = new ArrayType(Type.OBJECT);
	private final ArrayType METHOD_TABLE_ARRAY = new ArrayType(Type.METHOD_TABLE);
	private final ArrayType CLASS_ARRAY = new ArrayType(Type.CLASS);

	private static final Charset UTF8 = Charset.forName("UTF-8");

	public LLVMOutput(Path file) throws ShadowException {
		super(file);
	}

	//used to do an LLVM check pass for debugging
	public LLVMOutput(boolean mode) throws ShadowException {
		if (!mode) {
			try {
				process = new ProcessBuilder("opt", "-S", "-O3").start();
			}
			catch (IOException ex) {
				throw new CompileException(ex.getLocalizedMessage());
			}
			writer = new TabbedLineWriter(process.getOutputStream());
		}
		writer.setLineNumbers(mode);
	}

	private String temp(int offset)
	{
		return '%' + Integer.toString(tempCounter - offset - 1);
	}
	private String nextTemp()
	{
		return '%' + Integer.toString(tempCounter++);
	}

	/**
	 * Determines either the next temporary variable or the local variable 
	 * that will store the result of this action. That name is stored in the
	 * data member of the node.
	 * 
	 * Caution: Calling this method *may* or *may not* update the current
	 * temporary counter.
	 * 
	 * @param node
	 * @return String giving the variable name where the operation is stored
	 */
	private String nextTemp(TACOperand node)
	{
		String name;
		if( node.hasLocalStore() ) 
			name = name(node.getLocalStore());
		else 
			name = nextTemp();		
		node.setData(name);
		return name;
	}

	// Class type flags
	public static final int INTERFACE = 1, PRIMITIVE = 2, GENERIC = 4, ARRAY = 8, SINGLETON = 16, METHOD = 32;

	private void writePrimitiveTypes() throws ShadowException {
		writer.write("%boolean = type i1");
		writer.write("%byte = type i8");
		writer.write("%ubyte = type i8");
		writer.write("%short = type i16");
		writer.write("%ushort = type i16");
		writer.write("%int = type i32");
		writer.write("%uint = type i32");
		writer.write("%code = type i32");
		writer.write("%long = type i64");
		writer.write("%ulong = type i64");
		writer.write("%float = type float");
		writer.write("%double = type double");		
	}
	private void writeTypes() throws ShadowException {
		writePrimitiveTypes();

		Type moduleType = module.getType();

		//type references
		HashSet<Type> definedGenerics = new HashSet<Type>();
		for (Type type : moduleType.getUsedTypes()) {			
			//write type and method table declarations (even for current types!)
			if(type != null && !(type instanceof ArrayType)  ) {	
				if( !type.isParameterized() ) {
					writeTypeDefinition(type);

					//external stuff for types outside of this file
					if( !moduleType.encloses(type) ) {					
						writer.write(classOf(type) +
								" = external constant %" + raw(Type.CLASS));					
						if( type instanceof ClassType )				
							writer.write(methodTable(type) +
									" = external constant " + methodTableType(type));					
						if (type instanceof SingletonType) //never parameterized
							writer.write('@' + raw(type, "_instance") +
									" = external global " + type(type));
					}
				}
				else {
					Type unparameterizedType = type.getTypeWithoutTypeArguments();
					//if unparameterized version has not been declared yet, do it
					if( definedGenerics.add(unparameterizedType) ) {				
						writeTypeDefinition(unparameterizedType);						

						if( !moduleType.encloses(unparameterizedType) ) {
							writer.write(classOf(unparameterizedType) +
									" = external constant %" + raw(Type.CLASS));
							if(  type instanceof ClassType ) {
								writer.write( interfaceData(unparameterizedType) +
										" = external constant { %ulong, [" + type.getAllInterfaces().size() + " x " + type(Type.METHOD_TABLE) + "]}");
								writer.write(methodTable(unparameterizedType) +
										" = external constant " + methodTableType(unparameterizedType));
							}						
						}
					}

					if( type.isFullyInstantiated()  )
						writeGenericClassSupportingMaterial(type); //junk that all generic classes need
				}
			}
		}

		for (Type type : moduleType.getMentionedTypes()) {
			if(type != null && !(type instanceof ArrayType) && !moduleType.getUsedTypes().contains(type)  ) {	
				if( !type.isParameterized() ) {
					writeTypeDeclaration(type);

					//external stuff for types outside of this file
					if( !moduleType.encloses(type) )
						writer.write(classOf(type) +
								" = external constant %" + raw(Type.CLASS));					
				}
				else {
					Type unparameterizedType = type.getTypeWithoutTypeArguments();
					//if unparameterized version has not been declared yet, do it
					if( definedGenerics.add(unparameterizedType) ) {				
						writeTypeDeclaration(unparameterizedType);						

						if( !moduleType.encloses(unparameterizedType) ) {
							writer.write(classOf(unparameterizedType) +
									" = external constant %" + raw(Type.CLASS));											
						}						
					}				
				}
			}
		}

		writer.write();
	}

	private void writeTypeDeclaration(Type type) throws ShadowException {
		StringBuilder sb = new StringBuilder();		
		if( type instanceof InterfaceType ) {
			sb.append(methodTableType(type)).append(" = type opaque");			
			writer.write(sb.toString());
		}
		else if (type instanceof ClassType) {	
			if( type.isUninstantiated() ) {
				sb.append('%' + raw(type)).append(" = type opaque");
				writer.write(sb.toString());
			}
		}
	}

	private void writeTypeDefinition(Type type) throws ShadowException {
		StringBuilder sb = new StringBuilder();

		if( type instanceof InterfaceType ) {
			sb.append(methodTableType(type)).append(" = type { ");			
			writer.write(sb.append(methodList(type.orderAllMethods(), false)).
					append(" }").toString());
		}
		else if (type instanceof ClassType) {	
			if( type.isUninstantiated() ) {
				sb.append(methodTableType(type)).append(" = type { ");				
				writer.write(sb.append(methodList(type.orderAllMethods(), false)).
						append(" }").toString());

				sb.setLength(0);
				
				//first thing in every object is the reference count
				sb.append('%' + raw(type)).append(" = type { ");
				sb.append(type(Type.ULONG)).append(", ");

				//second thing in every object is the class
				sb.append(type(Type.CLASS)).append(", ");

				//then the method table
				sb.append(methodTableType(type)).append("* ");


				if (type.isPrimitive()) //put wrapped value in for primitives
					sb.append(", ").append(type(type));
				else {			
					for (Entry<String, ? extends ModifiedType> field :
						((ClassType)type).orderAllFields())					
						sb.append(", ").append(type(field.getValue()));					
				}
				writer.write(sb.append(" }").toString());
			}
		}	
	}

	protected void writeModuleDefinition(TACModule module) throws ShadowException {
		Map<String, ShadowValue> constants = new HashMap<String, ShadowValue>();		
		writeModuleDefinition(module, constants);		
	}

	private void writeModuleDefinition(TACModule module, Map<String, ShadowValue> constants) throws ShadowException {		
		Type moduleType = module.getType();
		writer.write("; " + moduleType.toString(Type.PACKAGES | Type.TYPE_PARAMETERS | Type.PARAMETER_BOUNDS));
		writer.write();

		//Class fields (since the order is all changed)
		//used for debugging
		if( moduleType instanceof ClassType ) {
			ClassType classType = (ClassType) moduleType;
			writer.write("; 0: reference count (ulong)");
			writer.write("; 1: class (Class)");
			writer.write("; 2: _methods");
			int counter = 3;			
			for (Entry<String, ? extends ModifiedType> field :
				(classType).orderAllFields()) {	

				writer.write("; " + counter + ": " + field.getKey() + " (" + field.getValue().getType() + ")" );
				++counter;				
			}

			writer.write();
		}


		Set<String> localConstants = new HashSet<String>();		

		//constants
		for (TACConstant constant : module.getConstants()) {
			ShadowInterpreter interpreter = new ShadowInterpreter(constants);
			String name = constant.getName();
			Context node = module.getType().getField(name);
			try {
				interpreter.walk(constant.getNode());
				TACNode constantNode = constant.getNode().getPrevious(); //gets last node (value node)
				if( !(constantNode instanceof TACOperand ))
					throw new CompileException(
							TypeCheckException.makeMessage(null, "Could not initialize constant " + name, node ));

				Object result = TACOperand.value((TACOperand)constantNode).getData();
				if (!(result instanceof ShadowValue))
					throw new CompileException(
							TypeCheckException.makeMessage(null, "Could not initialize constant " + name, node ));				
				
				ShadowValue value = (ShadowValue) result;
				if( !value.getType().equals(node.getType()))
					value = value.cast(node.getType());

				String fullName = constant.getPrefixType().toString() + ":" + name; 
				constants.put(fullName, value);				
				localConstants.add(fullName);
				writer.write(name(constant) + " = constant " +
						typeLiteral(value));
			}
			catch(InterpreterException e) {
				String message = TypeCheckException.makeMessage(null, "Could not initialize constant " + name + ": " + e.getMessage(), node );
				throw new CompileException(message);
			}

			Cleanup.getInstance().walk(constant.getNode());
		}

		//interfaces implemented (because a special object is used to map the methods correctly)
		ArrayList<InterfaceType> interfaces = moduleType.getAllInterfaces();
		int interfaceCount = interfaces.size();

		if( module.isClass() ) {
			//no need to write interface data for interfaces				
			StringBuilder interfaceData = new StringBuilder( interfaceData(moduleType) + " = ");			

			//if( !moduleType.isParameterizedIncludingOuterClasses() )
			//interfaceData.append("private " );			

			//generic classes don't list interfaces (because their parameterized versions have those)
			//but they do share interfaceData (the actual methods)
			interfaceData.append("unnamed_addr constant { %ulong, [").
			append(interfaceCount).append(" x ").
			append(type(Type.METHOD_TABLE)).append("]} { %ulong -1, [" + interfaceCount + " x " + type(Type.METHOD_TABLE) + "] [");
			StringBuilder interfaceClasses = new StringBuilder( interfaces(moduleType) + " = private ");

			interfaceClasses.append("unnamed_addr constant { %ulong, [").
			append(interfaceCount).append(" x ").
			append(type(Type.CLASS)).append("]} { %ulong -1, [" + interfaceCount + " x " + type(Type.CLASS) + "] [");

			boolean firstData = true;
			boolean firstClass = true;

			for(InterfaceType type : interfaces) {			
				if( module.isClass() ) {
					List<MethodSignature> methods = type.orderAllMethods(module.
							getClassType());

					String methodsType = methodList(methods, false);
					writer.write("@_class" + classCounter +
							" = private unnamed_addr constant { " + methodsType +
							" } { " + methodList(methods, true) + " }");
					if( firstData )
						firstData = false;
					else
						interfaceData.append(", ");
					interfaceData.append(type(Type.METHOD_TABLE)).append(" bitcast ({ ").
					append(methodsType).append(" }* @_class").append(classCounter).
					append(" to ").append(type(Type.METHOD_TABLE)).append(")");
				}				

				if( firstClass )
					firstClass = false;
				else
					interfaceClasses.append(", ");
				if( type.isFullyInstantiated() )
					interfaceClasses.append(typeText(Type.CLASS, "bitcast (" + type(Type.GENERIC_CLASS) + " " + classOf(type) + " to " + type(Type.CLASS) + ")"));
				else
					interfaceClasses.append(typeText(Type.CLASS, classOf(type)));
				classCounter++;
			}
			writer.write(interfaceData.append("]}").toString());

			if( !moduleType.isParameterized() )	
				writer.write(interfaceClasses.append("]}").toString());
		}

		//method declarations (but not definitions)
		List<MethodSignature> methods = moduleType.orderAllMethods();

		int flags = 0;
		if (moduleType.isPrimitive())
			flags |= PRIMITIVE;
		if( moduleType instanceof SingletonType )
			flags |= SINGLETON;
		if (module.isClass()) {
			//add in methods that are inherited from parent classes
			for( MethodSignature signature : methods)			
				if( (signature.getOuter() instanceof ClassType) && !module.getType().encloses(signature.getOuter()) && !signature.isWrapper() )
					usedSignatures.add(signature);

			ClassType parentType = ((ClassType)moduleType).getExtendType();
			writer.write(methodTable(moduleType) + " = constant " +
					methodTableType(moduleType) + " { " +					
					methodList(methods, true) + " }");

			//nothing will ever be the raw, unparameterized class ...now they will!
			//if( !moduleType.isParameterizedIncludingOuterClasses() ) {
			writer.write(classOf(moduleType) + " = constant %" +
					raw(Type.CLASS) + " { " + 
					
					type(Type.ULONG) + " " + literal(-1) + ", " + //reference count 

					type(Type.CLASS) + " " + classOf(Type.CLASS) + ", " + //class
					methodTableType(Type.CLASS) + "* " + methodTable(Type.CLASS) + ", " + //methods
					
					type(METHOD_TABLE_ARRAY) + " {" + pointerType(METHOD_TABLE_ARRAY) + " " +   //interfaceTables
					" bitcast ({%ulong, [" +
					interfaceCount + " x " + type(Type.METHOD_TABLE) +
					"]}* " + interfaceData(moduleType) + " to " + pointerType(METHOD_TABLE_ARRAY) + "), " +
					typeText(Type.CLASS, classOf(Type.METHOD_TABLE)) + ", " +
					"%ulong " + literal((long)interfaceCount) +
					"}, " + 
					type(CLASS_ARRAY) + //interfaces 

					( moduleType.isParameterized() ?							
							" zeroinitializer, " :		

								" {" + pointerType(CLASS_ARRAY) + " " + 
								"bitcast ({%ulong, [" +
								interfaceCount + " x " + type(Type.CLASS) +
								"]}* " + interfaces(moduleType) + " to " + pointerType(CLASS_ARRAY) + "), " +
								typeText(Type.CLASS, classOf(Type.CLASS)) + ", %ulong " + literal((long)interfaceCount) + "}, " )	+

					typeLiteral(moduleType.toString(Type.PACKAGES)) + ", " +  //name

					typeText(Type.CLASS, parentType != null ?  //parent class
							classOf(parentType) : null) + ", " +
					
					typeLiteral(flags) + ", " +			//flags
					typeText(Type.INT, sizeof(moduleType)) + //size 
					" }" );
			//}
		}
		else {
			flags |= INTERFACE;

			//nothing will ever be the raw, unparameterized class...NOW THEY Will!
			//if( !moduleType.isParameterizedIncludingOuterClasses() )
			writer.write(classOf(moduleType) + " = constant %" +
					raw(Type.CLASS) + " { " + 
					
					type(Type.ULONG) + " " + literal(-1) + ", " + //reference count

					type(Type.CLASS) + " " + classOf(Type.CLASS) + ", " + //class
					methodTableType(Type.CLASS) + "* " + methodTable(Type.CLASS) + ", " + //methods
				
					type(METHOD_TABLE_ARRAY) + " zeroinitializer, " + //interfaceTables
					type(CLASS_ARRAY) +  " zeroinitializer, " + //interfaces
					
					typeLiteral(moduleType.toString(Type.PACKAGES)) + ", " + //name 
					type(Type.CLASS) + " null, " + //parent

					typeLiteral(flags) + ", " +
					typeText(Type.INT, sizeof(moduleType)) + //size 
					" }");
		}

		if (moduleType instanceof SingletonType)
			writer.write('@' + raw(moduleType, "_instance") + " = thread_local global " +
					type(moduleType) + " null");

		writer.write();

		if( moduleType.isParameterized() )
			unparameterizedGenerics.add(moduleType.getTypeWithoutTypeArguments());		

		//recursively do inner classes
		for( TACModule innerClass : module.getInnerClasses() )
			writeModuleDefinition(innerClass, constants);		

		//remove constants defined in current class
		//inner classes can use outer constants but not the converse
		for( String name : localConstants )
			constants.remove(name);
	}

	private void writeGenericClasses() throws ShadowException {		
		for (Type type : module.getType().getUsedTypes() ) {
			if( type.isFullyInstantiated() && !(type instanceof ArrayType) )
				writeGenericClass(type);	
		}

		writer.write();
	}
	private void writeArrayClasses() throws ShadowException {
		for (Type type : module.getType().getUsedTypes() ) {
			if( type instanceof ArrayType && !((ArrayType)type).containsUnboundTypeParameters()  )
				writeArrayClass((ArrayType)type);	
		}

		writer.write();		
	}

	public static void readGenericAndArrayClasses(Path llvmFile, Set<String> generics, Set<String> arrays ) throws IOException {
		BufferedReader llvm = Files.newBufferedReader(llvmFile, UTF8);
		String line;

		//first skip all of the type declarations
		while( !(line = llvm.readLine()).isEmpty() );

		//first read in all the generic classes
		while( !(line = llvm.readLine()).isEmpty() )
			generics.add(line.split("\\s+")[0]);

		//then read in all the array classes
		while( !(line = llvm.readLine()).isEmpty() )
			arrays.add(line.split("\\s+")[0]);

		llvm.close();
	}


	@Override
	public void startFile(TACModule module) throws ShadowException {		
		this.module = module;

		//write all regular types including class objects and method tables
		writeTypes();		

		writeGenericClasses();		
		writeArrayClasses();
		//writeClasses();

		// Methods for exception handling
		writer.write("declare i32 @__shadow_personality_v0(...)");
		writer.write("declare void @__shadow_throw(" + type(Type.OBJECT) + ") noreturn");
		writer.write("declare " + type(Type.EXCEPTION) + " @__shadow_catch(i8* nocapture) nounwind");
		writer.write("declare i32 @llvm.eh.typeid.for(i8*) nounwind readnone");
		//memcopy
		writer.write("declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1)");
		writer.write("declare void @__arrayStore({%ulong," + type(Type.OBJECT) + "}*, %ulong, " + type(Type.OBJECT) + ", " + type(Type.CLASS) + ")");
		writer.write("declare " + type(Type.OBJECT) + " @__arrayLoad({%ulong," + type(Type.OBJECT) + "}*, %ulong, " + type(Type.CLASS) + ", " + type(Type.METHOD_TABLE) + ", %boolean)");
		writer.write("declare void @free(i8*) nounwind");
		
		writer.write("declare void @__incrementRef(%shadow.standard..Object*) nounwind");
		writer.write("declare void @__incrementRefArray({%ulong, %shadow.standard..Object*}* %arrayData) nounwind");		
		writer.write("declare void @__decrementRef(%shadow.standard..Object* %object) nounwind");
		writer.write("declare void @__decrementRefArray({{%ulong, %shadow.standard..Object*}*, %shadow.standard..Class*, %ulong} %array) nounwind");
		
		writer.write("declare noalias %shadow.standard..Object* @__allocate(%shadow.standard..Class* %class, %shadow.standard..Object_methods* %methods)");
		writer.write("declare noalias {%ulong, %shadow.standard..Object*}* @__allocateArray(%shadow.standard..Class* %class, %ulong %elements)");
		
		writer.write();

		//defines class and recursively defines inner classes  
		writeModuleDefinition(module);		
	}

	private String methodList(Iterable<MethodSignature> methods, boolean name)
			throws ShadowException {
		StringBuilder sb = new StringBuilder();
		for (MethodSignature method : methods) {			
			sb.append(", ").append(methodType(method));
			if (name)
				sb.append(' ').append(name(method));
		}

		if( sb.length() > 0 )
			return sb.substring(2);
		else
			return sb.toString();  //no methods!
	}

	public void writeStringLiterals() throws ShadowException
	{
		int stringIndex = 0;
		ArrayType byteArray = new ArrayType(Type.BYTE);
		for (String literal : stringLiterals)
		{
			byte[] data = null;
			try
			{
				data = literal.getBytes("UTF-8");
			}
			catch (UnsupportedEncodingException ex)
			{
				System.err.println(ex.getLocalizedMessage());
				System.exit(1);
			}
						
			StringBuilder sb = new StringBuilder(data.length);
			//include INT_MAX as -1 at the beginning of the array representation
			//to mark the array as non-gc			
			boolean ascii = true;
			for (byte b : data)
			{
				if (b < 0)
					ascii = false;
				if (b != '\"' && b >= 0x20 && b < 0x7f)
					sb.appendCodePoint(b);
				else
					sb.append('\\').
					append(Character.forDigit((b & 0xff) >>> 4, 16)).
					append(Character.forDigit(b & 0xf, 16));
			}
			writer.write("@_array" + stringIndex + " = private unnamed_addr " +
					"constant {%ulong, [" + data.length + " x " + type(Type.BYTE) +
					"]} { %ulong -1, [" + data.length + " x " + type(Type.BYTE) +
					"] c\"" + sb + "\" }");
			writer.write("@_string" + stringIndex + " = private unnamed_addr " +
					"constant %" + raw(Type.STRING) + " { " +
					type(Type.ULONG) + " " + literal(-1) + ", " +					
					type(Type.CLASS) + " " + classOf(Type.STRING) + ", " +
					methodTableType(Type.STRING) + "* " + methodTable(Type.STRING) + ", " +					
					type(byteArray) + 
					" {" + pointerType(byteArray) + " bitcast (" + 
					"{" + type(Type.ULONG) + ", [" + data.length + " x " + type(Type.BYTE) + "]}* " +
					"@_array" + stringIndex + " to " + pointerType(byteArray) + "), " +
					typeText(Type.CLASS, classOf(Type.BYTE)) + ", " + 
					type(Type.ULONG) + " " + literal((long)data.length) + "}, " +
					typeLiteral(ascii) + " }");
			stringIndex++;
		}		
	}

	@Override
	public void endFile(TACModule module) throws ShadowException {
		Type moduleType = module.getType();

		//declare a few strange methods that are not called through normal channels  
		if (moduleType instanceof ClassType ) {
			if( !moduleType.encloses(Type.ARRAY) )
				writer.write("declare " + type(Type.ARRAY) + " @" +
						raw(Type.ARRAY, "_Mcreate_" + OBJECT_ARRAY.
								toString(Type.MANGLE)) + '(' +
						type(Type.OBJECT) + ", " +
						type(OBJECT_ARRAY) + ')');


			if( !moduleType.encloses(Type.ARRAY_NULLABLE) )
				writer.write("declare " + type(Type.ARRAY_NULLABLE) + " @" +
						raw(Type.ARRAY_NULLABLE, "_Mcreate_" + OBJECT_ARRAY.
								toString(Type.MANGLE)) + '(' +
						type(Type.OBJECT) + ", " +
						type(OBJECT_ARRAY) + ')');				
		}

		//declare the two sets used to keep track of all generic classes and array classes
		writer.write();
		writer.write("@_genericSet = external global " + type(Type.CLASS_SET));
		writer.write("@_arraySet = external global " + type(Type.CLASS_SET));
		writer.write();

		//print only the constant fields that are used
		for( TACConstantRef constant : usedConstants )
			writer.write("@" + 				
					constant.getPrefixType().toString(Type.MANGLE) + "_C" + //c for constant 
					constant.getName() + " = external constant " + type(constant.getType()));
		writer.write();

		//print only the (mostly private) methods that are called directly
		for( MethodSignature method : usedSignatures )
			writer.write("declare " + methodToString(method));
		writer.write();

		writeStringLiterals();

		if (process != null)
			try {
				String line;
				BufferedReader reader;
				process.getOutputStream().close();

				reader = new BufferedReader(new InputStreamReader(
						process.getInputStream()));
				while ((line = reader.readLine()) != null)
					System.out.println(line);
				reader.close();

				try {
					Thread.sleep(11); //why is this 11?
				}
				catch (InterruptedException ex)	{}

				reader = new BufferedReader(new InputStreamReader(
						process.getErrorStream()));
				while ((line = reader.readLine()) != null)
					System.err.println(line);
				reader.close();

				try {
					process.waitFor();
				} catch (InterruptedException ex) { }
				int exit = process.exitValue();
				if (exit != 0)
					System.exit(exit);
			}
		catch (IOException ex) {
			throw new CompileException( ex.getLocalizedMessage() );
		}
	}


	@Override
	public void startMethod(TACMethod method, TACModule module) throws ShadowException {
			
		MethodSignature signature = method.getSignature();
		if (module.getType() instanceof InterfaceType ) {
			skipMethod = true;
		}
		else if (signature.isNative() || signature.isExternWithoutBlock()) {
			writer.write("declare " + methodToString(method));
			writer.write();
			skipMethod = true;
		}
		else {
			SequenceType parameters = signature.getSignatureWithoutTypeArguments().getFullParameterTypes();
			tempCounter = parameters.size();
			writer.write("define " + methodToString(method) +
					(signature.isWrapper() ? " unnamed_addr" : "" ) +
					(method.hasLandingpad() ? " personality i32 (...)* @__shadow_personality_v0 {" : " {"  ));
			writer.indent();
		}
	}

	private String name(TACVariable variable)
	{		
		return '%' + variable.getName();
	}

	@Override
	public void walk(TACNode nodes) throws ShadowException {
		if( !skipMethod )
			super.walk(nodes);
	}

	@Override
	public void endMethod(TACMethod method, TACModule module) throws ShadowException {

		if( !skipMethod ) {
			writer.outdent();
			writer.write('}');
			writer.write();
		}
		skipMethod = false;
		method = null;
	}

	@Override
	public void visit(TACLongToPointer node) throws ShadowException {
		writer.write(nextTemp(node) + " = inttoptr " + type(Type.ULONG) + " " +
				symbol(node.getOperand(0)) + " to " + type(node.getType())); 
	}

	@Override
	public void visit(TACPointerToLong node) throws ShadowException {		
		writer.write(nextTemp(node) + " = ptrtoint " + typeSymbol(node.getOperand(0)) +
				" to " + type(Type.ULONG));
	}

	@Override
	public void visit(TACCopyMemory node) throws ShadowException {
		TACOperand destinationNode = node.getDestination();
		TACOperand sourceNode = node.getSource();
		TACOperand size = node.getSize();
	
		String destination = typeSymbol(destinationNode);
		String source = typeSymbol(sourceNode);

		if( destinationNode.getType() instanceof ArrayType ) {
			ArrayType arrayType = (ArrayType) destinationNode.getType();
			writer.write(nextTemp() + " = extractvalue " +
					destination + ", 0");
			writer.write(nextTemp() + " = getelementptr " + pointerType(arrayType, false) + ", " +
					pointerType(arrayType) + " " + temp(1) + ", i32 0, i32 1");
			destination = typeText(arrayType.getBaseType(), temp(0), true);			
		}

		if( sourceNode.getType() instanceof ArrayType ) {
			ArrayType arrayType = (ArrayType) sourceNode.getType();
			writer.write(nextTemp() + " = extractvalue " +
					source + ", 0");
			writer.write(nextTemp() + " = getelementptr " + pointerType(arrayType, false) + ", " +
					pointerType(arrayType) + " " + temp(1) + ", i32 0, i32 1");
			source = typeText(arrayType.getBaseType(), temp(0), true);			
		}		
				
		writer.write(nextTemp() + " = bitcast " + destination + " to i8*");
		writer.write(nextTemp() + " = bitcast " + source + " to i8*");
		
		//regular objects (used in copy() and freeze()) have an 8 byte reference count that should *not* be copied
		//this is already taken care of with arrays
		if( !(destinationNode.getType() instanceof ArrayType) && !(sourceNode.getType() instanceof ArrayType) ) {
			writer.write(nextTemp() + " = getelementptr i8, i8* " + temp(2) + ", i32 8"); //destination
			writer.write(nextTemp() + " = getelementptr i8, i8* " + temp(2) + ", i32 8"); //source			
			writer.write(nextTemp() + " = sub i64 " + symbol(size) + ", 8");
			writer.write("call void @llvm.memcpy.p0i8.p0i8.i64(i8* " + temp(2) + ", i8* " + temp(1) + ", i64 " + temp(0) + ", i32 1, i1 0)");
		}
		else			
			writer.write("call void @llvm.memcpy.p0i8.p0i8.i64(i8* " + temp(1) + ", i8* " + temp(0) + ", i64 " + symbol(size) + ", i32 1, i1 0)");		
	}

	@Override
	public void visit(TACMethodRef node) throws ShadowException {
		if (node.getOuterType() instanceof InterfaceType) {
			writer.write(nextTemp() + " = extractvalue " +
					type(node.getOuterType()) + " " + symbol(node.getPrefix()) + ", 0");
			writer.write(nextTemp() + " = getelementptr " +
					methodTableType(node.getOuterType()) +
					", " + methodTableType(node.getOuterType()) + "* " +
					temp(1) + ", i32 0, i32 " + node.getIndex());
			String back1 = temp(0);
			writer.write(nextTemp(node) + " = load " + methodType(node) + ", " + methodType(node) +
					"* " + back1);
		}
		else if (node.hasPrefix() && 
				//Devirtualization conditions below
				!node.getOuterType().isPrimitive() &&
				!node.getOuterType().getModifiers().isLocked() &&
				!node.getType().getModifiers().isLocked() &&
				!(node.getOuterType() instanceof SingletonType) &&
				!node.getType().getModifiers().isPrivate() &&
				!node.isSuper() ) {	
			writer.write(nextTemp() + " = getelementptr inbounds %" +
					raw(node.getPrefix().getType()) + ", " + 					
					typeSymbol(node.getPrefix()) + ", i32 0, i32 2");

			writer.write(nextTemp() + " = load " + methodTableType(node.getPrefix().getType()) + "*, " +
					methodTableType(node.getPrefix().getType()) + "** " + temp(1));

			writer.write(nextTemp() + " = getelementptr inbounds " +
					methodTableType(node.getPrefix().getType()) + ", " + 
					methodTableType(node.getPrefix().getType()) + "* " +
					temp(1) + ", i32 0, i32 " + node.getIndex()); //may need to + 1 to the node.getIndex() if a parent method table is added	

			String back1 = temp(0);
			writer.write(nextTemp(node) + " = load " + methodType(node) + ", " + methodType(node) +
					"* " + back1);
		}
		else {			
			node.setData(name(node));
			MethodSignature signature = node.getSignature();
			if( !module.getType().encloses(signature.getOuter()) && !signature.isWrapper()  )
				usedSignatures.add(signature.getSignatureWithoutTypeArguments());
		}
	}

	@Override
	public void visit(TACClass node) throws ShadowException {		
		node.setData(node.getClassData().getData());
	}

	@Override
	public void visit(TACSequence node) throws ShadowException {
		String current = "undef";
		for (int i = 0; i < node.size(); i++) {
			writer.write(nextTemp() + " = insertvalue " + typeText(node,
					current) + ", " + typeSymbol(node.get(i)) + ", " + i);
			current = temp(0);
		}
		node.setData(current);
	}

	@Override
	public void visit(TACSequenceElement node ) throws ShadowException {	
		writer.write(nextTemp(node) + " = extractvalue " +
				typeSymbol(node.getOperand(0)) + ", " + node.getIndex());		
	}	

	private void writeObjectToArray(TACCast node, ArrayType arrayType, TACOperand source) throws ShadowException {
		String srcName = symbol(source);
		Type srcType = source.getType();		
		Type genericArray;

		if( arrayType.isNullable()  )
			genericArray = Type.ARRAY_NULLABLE;
		else			
			genericArray = Type.ARRAY;

		if (!srcType.equals(genericArray)) {
			writer.write(nextTemp() + " = bitcast " + typeSymbol(source) + " to " + type(genericArray));
			srcType = genericArray;
			srcName = temp(0);
		}		

		String arrayTypeName = type(arrayType);
		writer.write(nextTemp() + " = getelementptr inbounds %" + raw(srcType) + ", " +
				typeText(srcType, srcName) + ", i32 0, i32 3");
		writer.write(nextTemp() + " = bitcast " + type(OBJECT_ARRAY) + "* " + temp(1) + " to " + arrayTypeName + "*");
		String reference = temp(0);
		writer.write(nextTemp(node) + " = load " + arrayTypeName + ", " + arrayTypeName + "* " + reference);
	}

	private void writeArrayToObject(TACCast node, ArrayType arrayType, TACOperand source, TACClass arrayClass) throws ShadowException {
		Type genericArray;
		if( arrayType.isNullable() )
			genericArray = Type.ARRAY_NULLABLE;				
		else
			genericArray = Type.ARRAY;				

		String newObject;
		writer.write(nextTemp() + " = bitcast " + typeText(Type.GENERIC_CLASS, symbol(arrayClass.getClassData())) + " to " + type(Type.CLASS));
		writer.write((newObject = nextTemp()) + " = call noalias " +
				type(Type.OBJECT) + " @__allocate(" + typeTemp(Type.CLASS,1) + ", " +
						methodTableType(Type.OBJECT) + "* bitcast(" + methodTableType(genericArray) + "* " +  symbol(arrayClass.getMethodTable()) + " to " + methodTableType(Type.OBJECT) + "*)" + 
				')');
		
		String symbol = symbol(source);
		
		String objectArray;
		if( arrayType.getBaseType().equals(Type.OBJECT) )
			objectArray = symbol;
		else {
			//stupid LLVM can't cast between struct types
			writer.write(nextTemp() + " = extractvalue " + typeText(arrayType, symbol) + ", 0");
			writer.write(nextTemp() + " = bitcast " + pointerType(arrayType) + " " + temp(1) + " to " + pointerType(OBJECT_ARRAY));
			writer.write(nextTemp() + " = insertvalue " + type(OBJECT_ARRAY) + " undef, " + pointerType(OBJECT_ARRAY) + " " + temp(1) + ", 0");
			writer.write(nextTemp() + " = extractvalue " + typeText(arrayType, symbol) + ", 1");
			writer.write(nextTemp() + " = insertvalue " + typeTemp(OBJECT_ARRAY, 2) + ", " + typeTemp(Type.CLASS, 1) + ", 1");
			writer.write(nextTemp() + " = extractvalue " + typeText(arrayType, symbol) + ", 2");
			writer.write((objectArray = nextTemp()) + " = insertvalue " + typeTemp(OBJECT_ARRAY, 2) + ", " + typeTemp(Type.ULONG, 1) + ", 2");
		}

		SequenceType arguments = new SequenceType();
		arguments.add(new SimpleModifiedType(OBJECT_ARRAY));		
		MethodSignature arrayCreate = genericArray.getMatchingMethod("create", arguments);						
		writer.write(nextTemp(node) + " = call " + type(genericArray) + " " +
			name(arrayCreate) + '(' +
			typeText(Type.OBJECT, newObject) + ", " +						
			typeText(OBJECT_ARRAY, objectArray) + ')');
	}

	@Override
	public void visit(TACCast node) throws ShadowException { 
		TACOperand value = node.getUpdatedValue(); 
		//no precomputation done
		if( value == null ) {
			TACOperand source = node.getOperand(0);		
			Type destType = node.getType();
			Type srcType = source.getType();
			String back1, back2;		
			String srcTypeName;
			String destTypeName;

			switch(node.getKind()) {		
			case ARRAY_TO_OBJECT:
				writeArrayToObject(node, (ArrayType)srcType, source, (TACClass)node.getOperand(1));
				break;
			case INTERFACE_TO_OBJECT:
				writer.write(nextTemp(node) + " = extractvalue " +
						typeSymbol(source) + ", 1");			
				break;
			case ITEM_TO_SEQUENCE:
				writer.write(nextTemp(node) + " = insertvalue " + type(node) +
						" undef, " + typeSymbol(node.getOperand(1)) + ", 0");	
				break;
			case NULL_TO_ARRAY:
				writer.write(nextTemp(node) + " = insertvalue " + type(node) +
						" zeroinitializer, " + type(((ArrayType)node.getType()).getBaseType()) + "* null, 0");
				break;		
			case NULL_TO_INTERFACE:
				writer.write(nextTemp(node) + " = insertvalue " + type(node) +
						" zeroinitializer, " + type(Type.OBJECT) + " null, 1");
				break;
			case OBJECT_TO_ARRAY:
				writeObjectToArray(node, (ArrayType)destType, source);
				break;
			case OBJECT_TO_INTERFACE:
				//operand 1 is the interface method table
				writer.write(nextTemp() + " = bitcast " + typeSymbol(node.getOperand(1)) +
						" to " + methodTableType(destType) + '*');
				writer.write(nextTemp() + " = insertvalue " + type(destType) +
						" undef, " + methodTableType(destType) + "* " + temp(1) +
						", 0");
				writer.write(nextTemp() + " = bitcast " +
						typeSymbol(source) + " to " + type(Type.OBJECT));			
				back1 = temp(0);
				back2 = temp(1);
				writer.write(nextTemp(node) + " = insertvalue " + typeText(destType,
						back2) + ", " + typeText(Type.OBJECT, back1) + ", 1");
				break;			
			case OBJECT_TO_OBJECT:
				srcTypeName = type(srcType, true); // nullable takes care of primitives in object form
				destTypeName = type(destType, true);
				writer.write(nextTemp(node) + " = bitcast " +
						srcTypeName + ' ' + symbol(source) + " to " + destTypeName);
				break;			
			case OBJECT_TO_PRIMITIVE:
				writer.write(nextTemp() + " = bitcast " + typeSymbol(source) + " to %" + raw(destType) +  "*");
				writer.write(nextTemp() + " = getelementptr inbounds %" +
						raw(destType) + ", %" + 
						raw(destType) + "* " + temp(1) + ", i32 0, i32 3");
				back1 = temp(0);
				writer.write(nextTemp(node) + " = load " +  type(destType) + ", " + typeText(destType, back1, true));			
				break;
			case PRIMITIVE_TO_OBJECT:
				writer.write(nextTemp() + " = call noalias " +	type(Type.OBJECT) + " @__allocate(" + 
						type(Type.CLASS) + ' ' +
						classOf(srcType) + ", " + methodTableType(Type.OBJECT) + "* bitcast(" +
						methodTableType(srcType) + "* " + methodTable(srcType) + " to " +
						methodTableType(Type.OBJECT) + "*)" + ")");			
				back1 = temp(0);
				String result = nextTemp(node); 
				writer.write(result + " = bitcast " + typeText(Type.OBJECT,
						back1) + " to %" + raw(srcType) + "*");
				writer.write(nextTemp() + " = getelementptr inbounds %" +
						raw(srcType) + ", %" + raw(srcType) + "* " + result + ", i32 0, i32 3");
				writer.write("store " + typeSymbol(source) + ", " +
						typeText(srcType, temp(0), true));
				break;
			case PRIMITIVE_TO_PRIMITIVE:	
				String instruction;
				int srcWidth = Type.getWidth(source), destWidth = Type.getWidth(node);
				srcTypeName = type(srcType);
				destTypeName = type(destType);
				if( srcType.isFloating() ) {
					if( destType.isFloating() )
						instruction = srcWidth > destWidth ? "fptrunc" : (srcWidth < destWidth ? "fpext" : "bitcast");
						else if( destType.isSigned() )
							instruction = "fptosi";
						else
							instruction = "fptoui";
				}
				else if( srcType.isSigned() ) {
					if( destType.isFloating() )
						instruction = "sitofp";
					else if( destType.isSigned() )
						instruction = srcWidth > destWidth ? "trunc" : (srcWidth < destWidth ? "sext" : "bitcast");
						else
							instruction = srcWidth > destWidth ? "trunc" : (srcWidth < destWidth ? "zext" : "bitcast");
				}
				else {//  srcType.isUnsigned() must be true
					if( destType.isFloating() )
						instruction = "uitofp";
					else
						instruction = srcWidth > destWidth ? "trunc" : (srcWidth < destWidth ? "zext" : "bitcast");
				}		
				writer.write(nextTemp(node) + " = " + instruction + ' ' +
						srcTypeName + ' ' + symbol(source) + " to " + destTypeName);
				break;
			case SEQUENCE_TO_ITEM:			
				writer.write(nextTemp(node) + " = extractvalue " +
						typeSymbol(source) + ", 0");	
				break;
			case SEQUENCE_TO_SEQUENCE:
				String current = "undef";
				String location;
				int index = 0;			
				for (int i = 0; i < node.getNumOperands(); i++) {
					if( i == node.getNumOperands() - 1 )
						location = nextTemp(node);
					else
						location = nextTemp();
					writer.write(location + " = insertvalue " + typeText(node,current) + ", " +
							typeSymbol(node.getOperand(i)) + ", " + index);
					current = location;
					index++;
				}			
				break;
			}
		}
		else
			//unusual case when casting from one primitive constant to another			
			node.setData(value.getData());
	}	

	@Override
	public void visit(TACNewObject node) throws ShadowException {				
		Type type = node.getClassType();	

		TACOperand _class = node.getClassData();
		TACOperand methods = node.getMethodTable();	

		//this is pretty ugly, but if we retrieved a generic type parameter's method table, it'll be stored as MethodTable*, not an Object_methods*
		if( type instanceof TypeParameter )
			writer.write(nextTemp() + " = bitcast " + type(Type.METHOD_TABLE) + " " +  symbol(methods) +  " to "  + methodTableType(Type.OBJECT) + "*");
		//any other method table will be of the correct type but needs cast to Object_methods* for compatibility with allocate()
		else 
			writer.write(nextTemp() + " = bitcast " + methodTableType(type.getTypeWithoutTypeArguments()) + "* " +  symbol(methods) +  " to "  + methodTableType(Type.OBJECT) + "*");
		String back1 = temp(0);		
		writer.write(nextTemp(node) + " = call noalias " + type(Type.OBJECT) +
				" @__allocate(" + type(Type.CLASS) +
				" " + symbol(_class) + ", " + methodTableType(Type.OBJECT) + "* " + back1 +
				" )");
	}

	@Override
	public void visit(TACNewArray node) throws ShadowException {		
		String allocationClass = typeSymbol(node.getBaseClass());		

		writer.write(nextTemp() + " = call noalias " + pointerType(OBJECT_ARRAY) + " @__allocateArray(" +
				allocationClass + ", " + typeSymbol(node.getSize()) + ')');
		writer.write(nextTemp() + " = bitcast " + pointerType(OBJECT_ARRAY) + " " +
				temp(1) + " to " + pointerType(node.getType()));
		writer.write(nextTemp() + " = insertvalue " + type(node) +
				" zeroinitializer, " + pointerType(node.getType()) + " " + temp(1) + ", 0");
		writer.write(nextTemp() + " = insertvalue " + type(node) + " " +
				temp(1) + ", " + allocationClass + ", 1");
		
		String last = temp(0);
		writer.write(nextTemp(node) + " = insertvalue " + type(node) + " " + 
				last + ", " + typeSymbol(node.getSize()) + ", 2");
	}
	

	@Override
	public void visit(TACBaseClass node) throws ShadowException {
		writer.write(nextTemp(node) + " = extractvalue " +
				typeSymbol(node.getArray()) + ", 1");
	}

	@Override
	public void visit(TACLength node) throws ShadowException {
		if( node.isLong() )
			writer.write(nextTemp(node) + " = extractvalue " +
					typeSymbol(node.getArray()) + ", 2");
		else {		
			writer.write(nextTemp() + " = extractvalue " +
					typeSymbol(node.getArray()) + ", 2");
			String oldTemp = temp(0);
			writer.write(nextTemp(node) + " = trunc " + type(Type.LONG) + " " + oldTemp + " to " + type(Type.INT));
		}
	}

	@Override
	public void visit(TACUnary node) throws ShadowException {
		TACOperand value = node.getUpdatedValue();
		//no precomputation done
		if( value == null ) {
			switch (node.getOperation()) {
			case "-":
				if( node.getType().isFloating() )
					visitUnary(node, "fsub", "-0.0");
				else
					visitUnary(node, "sub", "0");
				break;
			case "~":
			case "!":
				visitUnary(node, "xor", "-1");
				break;
			}
		}
		else
			node.setData(value.getData());
	}
	private void visitUnary(TACUnary node, String instruction, String first)
			throws ShadowException {

		writer.write(nextTemp(node) + " = " + instruction + ' ' + typeText(node,
				first) + ", " + symbol(node.getOperand()));
	}
	
	@Override
	public void visit(TACAllocateVariable node) throws ShadowException { 
		TACVariable local = node.getVariable();
		writer.write(name(local) + " = alloca " + type(local));
		writer.write("store " + type(local) + " " + literal(new ShadowNull(local.getType())) + ", " + typeText(local, name(local), true));
	}
	
	@Override
	public void visit(TACChangeReferenceCount node) throws ShadowException { 
		ModifiedType reference;
		TACFieldRef field = null;
		TACVariable variable = null;
		
		String name;
		
		String objectArrayType = type(OBJECT_ARRAY);
		
		if( node.isField() )			
			reference = field = node.getField();		<commit_msg>Removed initial store of null to allocated local GC variables.<commit_after>package shadow.output.llvm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.UnsupportedEncodingException;
import java.math.BigInteger;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeSet;

import shadow.CompileException;
import shadow.ShadowException;
import shadow.interpreter.InterpreterException;
import shadow.interpreter.ShadowBoolean;
import shadow.interpreter.ShadowCode;
import shadow.interpreter.ShadowDouble;
import shadow.interpreter.ShadowFloat;
import shadow.interpreter.ShadowInteger;
import shadow.interpreter.ShadowInterpreter;
import shadow.interpreter.ShadowNull;
import shadow.interpreter.ShadowString;
import shadow.interpreter.ShadowUndefined;
import shadow.interpreter.ShadowValue;
import shadow.output.AbstractOutput;
import shadow.output.Cleanup;
import shadow.output.TabbedLineWriter;
import shadow.parse.Context;
import shadow.tac.TACBlock;
import shadow.tac.TACConstant;
import shadow.tac.TACMethod;
import shadow.tac.TACModule;
import shadow.tac.TACVariable;
import shadow.tac.nodes.TACAllocateVariable;
import shadow.tac.nodes.TACArrayRef;
import shadow.tac.nodes.TACBaseClass;
import shadow.tac.nodes.TACBinary;
import shadow.tac.nodes.TACBranch;
import shadow.tac.nodes.TACCall;
import shadow.tac.nodes.TACCast;
import shadow.tac.nodes.TACCatch;
import shadow.tac.nodes.TACChangeReferenceCount;
import shadow.tac.nodes.TACClass;
import shadow.tac.nodes.TACConstantRef;
import shadow.tac.nodes.TACCopyMemory;
import shadow.tac.nodes.TACFieldRef;
import shadow.tac.nodes.TACGenericArrayRef;
import shadow.tac.nodes.TACGlobalRef;
import shadow.tac.nodes.TACLabel;
import shadow.tac.nodes.TACLabelAddress;
import shadow.tac.nodes.TACLandingpad;
import shadow.tac.nodes.TACLength;
import shadow.tac.nodes.TACLoad;
import shadow.tac.nodes.TACLocalLoad;
import shadow.tac.nodes.TACLocalStorage;
import shadow.tac.nodes.TACLocalStore;
import shadow.tac.nodes.TACLongToPointer;
import shadow.tac.nodes.TACMethodRef;
import shadow.tac.nodes.TACNewArray;
import shadow.tac.nodes.TACNewObject;
import shadow.tac.nodes.TACNode;
import shadow.tac.nodes.TACOperand;
import shadow.tac.nodes.TACParameter;
import shadow.tac.nodes.TACPhi;
import shadow.tac.nodes.TACPointerToLong;
import shadow.tac.nodes.TACReference;
import shadow.tac.nodes.TACResume;
import shadow.tac.nodes.TACReturn;
import shadow.tac.nodes.TACSequence;
import shadow.tac.nodes.TACSequenceElement;
import shadow.tac.nodes.TACSingletonRef;
import shadow.tac.nodes.TACStore;
import shadow.tac.nodes.TACThrow;
import shadow.tac.nodes.TACTypeId;
import shadow.tac.nodes.TACUnary;
import shadow.tac.nodes.TACUpdate;
import shadow.typecheck.TypeCheckException;
import shadow.typecheck.type.ArrayType;
import shadow.typecheck.type.ClassType;
import shadow.typecheck.type.InterfaceType;
import shadow.typecheck.type.MethodSignature;
import shadow.typecheck.type.MethodTableType;
import shadow.typecheck.type.ModifiedType;
import shadow.typecheck.type.PointerType;
import shadow.typecheck.type.SequenceType;
import shadow.typecheck.type.SimpleModifiedType;
import shadow.typecheck.type.SingletonType;
import shadow.typecheck.type.Type;
import shadow.typecheck.type.TypeParameter;

public class LLVMOutput extends AbstractOutput {
	private Process process = null;
	private int tempCounter = 0;
	private List<String> stringLiterals = new LinkedList<String>();	
	private HashSet<Type> unparameterizedGenerics = new HashSet<Type>();
	private int classCounter = 0;
	private HashSet<MethodSignature> usedSignatures = new HashSet<MethodSignature>();
	private HashSet<TACConstantRef> usedConstants = new HashSet<TACConstantRef>();

	private Set<String> genericClasses = new TreeSet<String>();
	private Set<String> arrayClasses = new TreeSet<String>();

	private TACModule module;
	private boolean skipMethod = false;
	
	private final ArrayType OBJECT_ARRAY = new ArrayType(Type.OBJECT);
	private final ArrayType METHOD_TABLE_ARRAY = new ArrayType(Type.METHOD_TABLE);
	private final ArrayType CLASS_ARRAY = new ArrayType(Type.CLASS);

	private static final Charset UTF8 = Charset.forName("UTF-8");

	public LLVMOutput(Path file) throws ShadowException {
		super(file);
	}

	//used to do an LLVM check pass for debugging
	public LLVMOutput(boolean mode) throws ShadowException {
		if (!mode) {
			try {
				process = new ProcessBuilder("opt", "-S", "-O3").start();
			}
			catch (IOException ex) {
				throw new CompileException(ex.getLocalizedMessage());
			}
			writer = new TabbedLineWriter(process.getOutputStream());
		}
		writer.setLineNumbers(mode);
	}

	private String temp(int offset)
	{
		return '%' + Integer.toString(tempCounter - offset - 1);
	}
	private String nextTemp()
	{
		return '%' + Integer.toString(tempCounter++);
	}

	/**
	 * Determines either the next temporary variable or the local variable 
	 * that will store the result of this action. That name is stored in the
	 * data member of the node.
	 * 
	 * Caution: Calling this method *may* or *may not* update the current
	 * temporary counter.
	 * 
	 * @param node
	 * @return String giving the variable name where the operation is stored
	 */
	private String nextTemp(TACOperand node)
	{
		String name;
		if( node.hasLocalStore() ) 
			name = name(node.getLocalStore());
		else 
			name = nextTemp();		
		node.setData(name);
		return name;
	}

	// Class type flags
	public static final int INTERFACE = 1, PRIMITIVE = 2, GENERIC = 4, ARRAY = 8, SINGLETON = 16, METHOD = 32;

	private void writePrimitiveTypes() throws ShadowException {
		writer.write("%boolean = type i1");
		writer.write("%byte = type i8");
		writer.write("%ubyte = type i8");
		writer.write("%short = type i16");
		writer.write("%ushort = type i16");
		writer.write("%int = type i32");
		writer.write("%uint = type i32");
		writer.write("%code = type i32");
		writer.write("%long = type i64");
		writer.write("%ulong = type i64");
		writer.write("%float = type float");
		writer.write("%double = type double");		
	}
	private void writeTypes() throws ShadowException {
		writePrimitiveTypes();

		Type moduleType = module.getType();

		//type references
		HashSet<Type> definedGenerics = new HashSet<Type>();
		for (Type type : moduleType.getUsedTypes()) {			
			//write type and method table declarations (even for current types!)
			if(type != null && !(type instanceof ArrayType)  ) {	
				if( !type.isParameterized() ) {
					writeTypeDefinition(type);

					//external stuff for types outside of this file
					if( !moduleType.encloses(type) ) {					
						writer.write(classOf(type) +
								" = external constant %" + raw(Type.CLASS));					
						if( type instanceof ClassType )				
							writer.write(methodTable(type) +
									" = external constant " + methodTableType(type));					
						if (type instanceof SingletonType) //never parameterized
							writer.write('@' + raw(type, "_instance") +
									" = external global " + type(type));
					}
				}
				else {
					Type unparameterizedType = type.getTypeWithoutTypeArguments();
					//if unparameterized version has not been declared yet, do it
					if( definedGenerics.add(unparameterizedType) ) {				
						writeTypeDefinition(unparameterizedType);						

						if( !moduleType.encloses(unparameterizedType) ) {
							writer.write(classOf(unparameterizedType) +
									" = external constant %" + raw(Type.CLASS));
							if(  type instanceof ClassType ) {
								writer.write( interfaceData(unparameterizedType) +
										" = external constant { %ulong, [" + type.getAllInterfaces().size() + " x " + type(Type.METHOD_TABLE) + "]}");
								writer.write(methodTable(unparameterizedType) +
										" = external constant " + methodTableType(unparameterizedType));
							}						
						}
					}

					if( type.isFullyInstantiated()  )
						writeGenericClassSupportingMaterial(type); //junk that all generic classes need
				}
			}
		}

		for (Type type : moduleType.getMentionedTypes()) {
			if(type != null && !(type instanceof ArrayType) && !moduleType.getUsedTypes().contains(type)  ) {	
				if( !type.isParameterized() ) {
					writeTypeDeclaration(type);

					//external stuff for types outside of this file
					if( !moduleType.encloses(type) )
						writer.write(classOf(type) +
								" = external constant %" + raw(Type.CLASS));					
				}
				else {
					Type unparameterizedType = type.getTypeWithoutTypeArguments();
					//if unparameterized version has not been declared yet, do it
					if( definedGenerics.add(unparameterizedType) ) {				
						writeTypeDeclaration(unparameterizedType);						

						if( !moduleType.encloses(unparameterizedType) ) {
							writer.write(classOf(unparameterizedType) +
									" = external constant %" + raw(Type.CLASS));											
						}						
					}				
				}
			}
		}

		writer.write();
	}

	private void writeTypeDeclaration(Type type) throws ShadowException {
		StringBuilder sb = new StringBuilder();		
		if( type instanceof InterfaceType ) {
			sb.append(methodTableType(type)).append(" = type opaque");			
			writer.write(sb.toString());
		}
		else if (type instanceof ClassType) {	
			if( type.isUninstantiated() ) {
				sb.append('%' + raw(type)).append(" = type opaque");
				writer.write(sb.toString());
			}
		}
	}

	private void writeTypeDefinition(Type type) throws ShadowException {
		StringBuilder sb = new StringBuilder();

		if( type instanceof InterfaceType ) {
			sb.append(methodTableType(type)).append(" = type { ");			
			writer.write(sb.append(methodList(type.orderAllMethods(), false)).
					append(" }").toString());
		}
		else if (type instanceof ClassType) {	
			if( type.isUninstantiated() ) {
				sb.append(methodTableType(type)).append(" = type { ");				
				writer.write(sb.append(methodList(type.orderAllMethods(), false)).
						append(" }").toString());

				sb.setLength(0);
				
				//first thing in every object is the reference count
				sb.append('%' + raw(type)).append(" = type { ");
				sb.append(type(Type.ULONG)).append(", ");

				//second thing in every object is the class
				sb.append(type(Type.CLASS)).append(", ");

				//then the method table
				sb.append(methodTableType(type)).append("* ");


				if (type.isPrimitive()) //put wrapped value in for primitives
					sb.append(", ").append(type(type));
				else {			
					for (Entry<String, ? extends ModifiedType> field :
						((ClassType)type).orderAllFields())					
						sb.append(", ").append(type(field.getValue()));					
				}
				writer.write(sb.append(" }").toString());
			}
		}	
	}

	protected void writeModuleDefinition(TACModule module) throws ShadowException {
		Map<String, ShadowValue> constants = new HashMap<String, ShadowValue>();		
		writeModuleDefinition(module, constants);		
	}

	private void writeModuleDefinition(TACModule module, Map<String, ShadowValue> constants) throws ShadowException {		
		Type moduleType = module.getType();
		writer.write("; " + moduleType.toString(Type.PACKAGES | Type.TYPE_PARAMETERS | Type.PARAMETER_BOUNDS));
		writer.write();

		//Class fields (since the order is all changed)
		//used for debugging
		if( moduleType instanceof ClassType ) {
			ClassType classType = (ClassType) moduleType;
			writer.write("; 0: reference count (ulong)");
			writer.write("; 1: class (Class)");
			writer.write("; 2: _methods");
			int counter = 3;			
			for (Entry<String, ? extends ModifiedType> field :
				(classType).orderAllFields()) {	

				writer.write("; " + counter + ": " + field.getKey() + " (" + field.getValue().getType() + ")" );
				++counter;				
			}

			writer.write();
		}


		Set<String> localConstants = new HashSet<String>();		

		//constants
		for (TACConstant constant : module.getConstants()) {
			ShadowInterpreter interpreter = new ShadowInterpreter(constants);
			String name = constant.getName();
			Context node = module.getType().getField(name);
			try {
				interpreter.walk(constant.getNode());
				TACNode constantNode = constant.getNode().getPrevious(); //gets last node (value node)
				if( !(constantNode instanceof TACOperand ))
					throw new CompileException(
							TypeCheckException.makeMessage(null, "Could not initialize constant " + name, node ));

				Object result = TACOperand.value((TACOperand)constantNode).getData();
				if (!(result instanceof ShadowValue))
					throw new CompileException(
							TypeCheckException.makeMessage(null, "Could not initialize constant " + name, node ));				
				
				ShadowValue value = (ShadowValue) result;
				if( !value.getType().equals(node.getType()))
					value = value.cast(node.getType());

				String fullName = constant.getPrefixType().toString() + ":" + name; 
				constants.put(fullName, value);				
				localConstants.add(fullName);
				writer.write(name(constant) + " = constant " +
						typeLiteral(value));
			}
			catch(InterpreterException e) {
				String message = TypeCheckException.makeMessage(null, "Could not initialize constant " + name + ": " + e.getMessage(), node );
				throw new CompileException(message);
			}

			Cleanup.getInstance().walk(constant.getNode());
		}

		//interfaces implemented (because a special object is used to map the methods correctly)
		ArrayList<InterfaceType> interfaces = moduleType.getAllInterfaces();
		int interfaceCount = interfaces.size();

		if( module.isClass() ) {
			//no need to write interface data for interfaces				
			StringBuilder interfaceData = new StringBuilder( interfaceData(moduleType) + " = ");			

			//if( !moduleType.isParameterizedIncludingOuterClasses() )
			//interfaceData.append("private " );			

			//generic classes don't list interfaces (because their parameterized versions have those)
			//but they do share interfaceData (the actual methods)
			interfaceData.append("unnamed_addr constant { %ulong, [").
			append(interfaceCount).append(" x ").
			append(type(Type.METHOD_TABLE)).append("]} { %ulong -1, [" + interfaceCount + " x " + type(Type.METHOD_TABLE) + "] [");
			StringBuilder interfaceClasses = new StringBuilder( interfaces(moduleType) + " = private ");

			interfaceClasses.append("unnamed_addr constant { %ulong, [").
			append(interfaceCount).append(" x ").
			append(type(Type.CLASS)).append("]} { %ulong -1, [" + interfaceCount + " x " + type(Type.CLASS) + "] [");

			boolean firstData = true;
			boolean firstClass = true;

			for(InterfaceType type : interfaces) {			
				if( module.isClass() ) {
					List<MethodSignature> methods = type.orderAllMethods(module.
							getClassType());

					String methodsType = methodList(methods, false);
					writer.write("@_class" + classCounter +
							" = private unnamed_addr constant { " + methodsType +
							" } { " + methodList(methods, true) + " }");
					if( firstData )
						firstData = false;
					else
						interfaceData.append(", ");
					interfaceData.append(type(Type.METHOD_TABLE)).append(" bitcast ({ ").
					append(methodsType).append(" }* @_class").append(classCounter).
					append(" to ").append(type(Type.METHOD_TABLE)).append(")");
				}				

				if( firstClass )
					firstClass = false;
				else
					interfaceClasses.append(", ");
				if( type.isFullyInstantiated() )
					interfaceClasses.append(typeText(Type.CLASS, "bitcast (" + type(Type.GENERIC_CLASS) + " " + classOf(type) + " to " + type(Type.CLASS) + ")"));
				else
					interfaceClasses.append(typeText(Type.CLASS, classOf(type)));
				classCounter++;
			}
			writer.write(interfaceData.append("]}").toString());

			if( !moduleType.isParameterized() )	
				writer.write(interfaceClasses.append("]}").toString());
		}

		//method declarations (but not definitions)
		List<MethodSignature> methods = moduleType.orderAllMethods();

		int flags = 0;
		if (moduleType.isPrimitive())
			flags |= PRIMITIVE;
		if( moduleType instanceof SingletonType )
			flags |= SINGLETON;
		if (module.isClass()) {
			//add in methods that are inherited from parent classes
			for( MethodSignature signature : methods)			
				if( (signature.getOuter() instanceof ClassType) && !module.getType().encloses(signature.getOuter()) && !signature.isWrapper() )
					usedSignatures.add(signature);

			ClassType parentType = ((ClassType)moduleType).getExtendType();
			writer.write(methodTable(moduleType) + " = constant " +
					methodTableType(moduleType) + " { " +					
					methodList(methods, true) + " }");

			//nothing will ever be the raw, unparameterized class ...now they will!
			//if( !moduleType.isParameterizedIncludingOuterClasses() ) {
			writer.write(classOf(moduleType) + " = constant %" +
					raw(Type.CLASS) + " { " + 
					
					type(Type.ULONG) + " " + literal(-1) + ", " + //reference count 

					type(Type.CLASS) + " " + classOf(Type.CLASS) + ", " + //class
					methodTableType(Type.CLASS) + "* " + methodTable(Type.CLASS) + ", " + //methods
					
					type(METHOD_TABLE_ARRAY) + " {" + pointerType(METHOD_TABLE_ARRAY) + " " +   //interfaceTables
					" bitcast ({%ulong, [" +
					interfaceCount + " x " + type(Type.METHOD_TABLE) +
					"]}* " + interfaceData(moduleType) + " to " + pointerType(METHOD_TABLE_ARRAY) + "), " +
					typeText(Type.CLASS, classOf(Type.METHOD_TABLE)) + ", " +
					"%ulong " + literal((long)interfaceCount) +
					"}, " + 
					type(CLASS_ARRAY) + //interfaces 

					( moduleType.isParameterized() ?							
							" zeroinitializer, " :		

								" {" + pointerType(CLASS_ARRAY) + " " + 
								"bitcast ({%ulong, [" +
								interfaceCount + " x " + type(Type.CLASS) +
								"]}* " + interfaces(moduleType) + " to " + pointerType(CLASS_ARRAY) + "), " +
								typeText(Type.CLASS, classOf(Type.CLASS)) + ", %ulong " + literal((long)interfaceCount) + "}, " )	+

					typeLiteral(moduleType.toString(Type.PACKAGES)) + ", " +  //name

					typeText(Type.CLASS, parentType != null ?  //parent class
							classOf(parentType) : null) + ", " +
					
					typeLiteral(flags) + ", " +			//flags
					typeText(Type.INT, sizeof(moduleType)) + //size 
					" }" );
			//}
		}
		else {
			flags |= INTERFACE;

			//nothing will ever be the raw, unparameterized class...NOW THEY Will!
			//if( !moduleType.isParameterizedIncludingOuterClasses() )
			writer.write(classOf(moduleType) + " = constant %" +
					raw(Type.CLASS) + " { " + 
					
					type(Type.ULONG) + " " + literal(-1) + ", " + //reference count

					type(Type.CLASS) + " " + classOf(Type.CLASS) + ", " + //class
					methodTableType(Type.CLASS) + "* " + methodTable(Type.CLASS) + ", " + //methods
				
					type(METHOD_TABLE_ARRAY) + " zeroinitializer, " + //interfaceTables
					type(CLASS_ARRAY) +  " zeroinitializer, " + //interfaces
					
					typeLiteral(moduleType.toString(Type.PACKAGES)) + ", " + //name 
					type(Type.CLASS) + " null, " + //parent

					typeLiteral(flags) + ", " +
					typeText(Type.INT, sizeof(moduleType)) + //size 
					" }");
		}

		if (moduleType instanceof SingletonType)
			writer.write('@' + raw(moduleType, "_instance") + " = thread_local global " +
					type(moduleType) + " null");

		writer.write();

		if( moduleType.isParameterized() )
			unparameterizedGenerics.add(moduleType.getTypeWithoutTypeArguments());		

		//recursively do inner classes
		for( TACModule innerClass : module.getInnerClasses() )
			writeModuleDefinition(innerClass, constants);		

		//remove constants defined in current class
		//inner classes can use outer constants but not the converse
		for( String name : localConstants )
			constants.remove(name);
	}

	private void writeGenericClasses() throws ShadowException {		
		for (Type type : module.getType().getUsedTypes() ) {
			if( type.isFullyInstantiated() && !(type instanceof ArrayType) )
				writeGenericClass(type);	
		}

		writer.write();
	}
	private void writeArrayClasses() throws ShadowException {
		for (Type type : module.getType().getUsedTypes() ) {
			if( type instanceof ArrayType && !((ArrayType)type).containsUnboundTypeParameters()  )
				writeArrayClass((ArrayType)type);	
		}

		writer.write();		
	}

	public static void readGenericAndArrayClasses(Path llvmFile, Set<String> generics, Set<String> arrays ) throws IOException {
		BufferedReader llvm = Files.newBufferedReader(llvmFile, UTF8);
		String line;

		//first skip all of the type declarations
		while( !(line = llvm.readLine()).isEmpty() );

		//first read in all the generic classes
		while( !(line = llvm.readLine()).isEmpty() )
			generics.add(line.split("\\s+")[0]);

		//then read in all the array classes
		while( !(line = llvm.readLine()).isEmpty() )
			arrays.add(line.split("\\s+")[0]);

		llvm.close();
	}


	@Override
	public void startFile(TACModule module) throws ShadowException {		
		this.module = module;

		//write all regular types including class objects and method tables
		writeTypes();		

		writeGenericClasses();		
		writeArrayClasses();
		//writeClasses();

		// Methods for exception handling
		writer.write("declare i32 @__shadow_personality_v0(...)");
		writer.write("declare void @__shadow_throw(" + type(Type.OBJECT) + ") noreturn");
		writer.write("declare " + type(Type.EXCEPTION) + " @__shadow_catch(i8* nocapture) nounwind");
		writer.write("declare i32 @llvm.eh.typeid.for(i8*) nounwind readnone");
		//memcopy
		writer.write("declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1)");
		writer.write("declare void @__arrayStore({%ulong," + type(Type.OBJECT) + "}*, %ulong, " + type(Type.OBJECT) + ", " + type(Type.CLASS) + ")");
		writer.write("declare " + type(Type.OBJECT) + " @__arrayLoad({%ulong," + type(Type.OBJECT) + "}*, %ulong, " + type(Type.CLASS) + ", " + type(Type.METHOD_TABLE) + ", %boolean)");
		writer.write("declare void @free(i8*) nounwind");
		
		writer.write("declare void @__incrementRef(%shadow.standard..Object*) nounwind");
		writer.write("declare void @__incrementRefArray({%ulong, %shadow.standard..Object*}* %arrayData) nounwind");		
		writer.write("declare void @__decrementRef(%shadow.standard..Object* %object) nounwind");
		writer.write("declare void @__decrementRefArray({{%ulong, %shadow.standard..Object*}*, %shadow.standard..Class*, %ulong} %array) nounwind");
		
		writer.write("declare noalias %shadow.standard..Object* @__allocate(%shadow.standard..Class* %class, %shadow.standard..Object_methods* %methods)");
		writer.write("declare noalias {%ulong, %shadow.standard..Object*}* @__allocateArray(%shadow.standard..Class* %class, %ulong %elements)");
		
		writer.write();

		//defines class and recursively defines inner classes  
		writeModuleDefinition(module);		
	}

	private String methodList(Iterable<MethodSignature> methods, boolean name)
			throws ShadowException {
		StringBuilder sb = new StringBuilder();
		for (MethodSignature method : methods) {			
			sb.append(", ").append(methodType(method));
			if (name)
				sb.append(' ').append(name(method));
		}

		if( sb.length() > 0 )
			return sb.substring(2);
		else
			return sb.toString();  //no methods!
	}

	public void writeStringLiterals() throws ShadowException
	{
		int stringIndex = 0;
		ArrayType byteArray = new ArrayType(Type.BYTE);
		for (String literal : stringLiterals)
		{
			byte[] data = null;
			try
			{
				data = literal.getBytes("UTF-8");
			}
			catch (UnsupportedEncodingException ex)
			{
				System.err.println(ex.getLocalizedMessage());
				System.exit(1);
			}
						
			StringBuilder sb = new StringBuilder(data.length);
			//include INT_MAX as -1 at the beginning of the array representation
			//to mark the array as non-gc			
			boolean ascii = true;
			for (byte b : data)
			{
				if (b < 0)
					ascii = false;
				if (b != '\"' && b >= 0x20 && b < 0x7f)
					sb.appendCodePoint(b);
				else
					sb.append('\\').
					append(Character.forDigit((b & 0xff) >>> 4, 16)).
					append(Character.forDigit(b & 0xf, 16));
			}
			writer.write("@_array" + stringIndex + " = private unnamed_addr " +
					"constant {%ulong, [" + data.length + " x " + type(Type.BYTE) +
					"]} { %ulong -1, [" + data.length + " x " + type(Type.BYTE) +
					"] c\"" + sb + "\" }");
			writer.write("@_string" + stringIndex + " = private unnamed_addr " +
					"constant %" + raw(Type.STRING) + " { " +
					type(Type.ULONG) + " " + literal(-1) + ", " +					
					type(Type.CLASS) + " " + classOf(Type.STRING) + ", " +
					methodTableType(Type.STRING) + "* " + methodTable(Type.STRING) + ", " +					
					type(byteArray) + 
					" {" + pointerType(byteArray) + " bitcast (" + 
					"{" + type(Type.ULONG) + ", [" + data.length + " x " + type(Type.BYTE) + "]}* " +
					"@_array" + stringIndex + " to " + pointerType(byteArray) + "), " +
					typeText(Type.CLASS, classOf(Type.BYTE)) + ", " + 
					type(Type.ULONG) + " " + literal((long)data.length) + "}, " +
					typeLiteral(ascii) + " }");
			stringIndex++;
		}		
	}

	@Override
	public void endFile(TACModule module) throws ShadowException {
		Type moduleType = module.getType();

		//declare a few strange methods that are not called through normal channels  
		if (moduleType instanceof ClassType ) {
			if( !moduleType.encloses(Type.ARRAY) )
				writer.write("declare " + type(Type.ARRAY) + " @" +
						raw(Type.ARRAY, "_Mcreate_" + OBJECT_ARRAY.
								toString(Type.MANGLE)) + '(' +
						type(Type.OBJECT) + ", " +
						type(OBJECT_ARRAY) + ')');


			if( !moduleType.encloses(Type.ARRAY_NULLABLE) )
				writer.write("declare " + type(Type.ARRAY_NULLABLE) + " @" +
						raw(Type.ARRAY_NULLABLE, "_Mcreate_" + OBJECT_ARRAY.
								toString(Type.MANGLE)) + '(' +
						type(Type.OBJECT) + ", " +
						type(OBJECT_ARRAY) + ')');				
		}

		//declare the two sets used to keep track of all generic classes and array classes
		writer.write();
		writer.write("@_genericSet = external global " + type(Type.CLASS_SET));
		writer.write("@_arraySet = external global " + type(Type.CLASS_SET));
		writer.write();

		//print only the constant fields that are used
		for( TACConstantRef constant : usedConstants )
			writer.write("@" + 				
					constant.getPrefixType().toString(Type.MANGLE) + "_C" + //c for constant 
					constant.getName() + " = external constant " + type(constant.getType()));
		writer.write();

		//print only the (mostly private) methods that are called directly
		for( MethodSignature method : usedSignatures )
			writer.write("declare " + methodToString(method));
		writer.write();

		writeStringLiterals();

		if (process != null)
			try {
				String line;
				BufferedReader reader;
				process.getOutputStream().close();

				reader = new BufferedReader(new InputStreamReader(
						process.getInputStream()));
				while ((line = reader.readLine()) != null)
					System.out.println(line);
				reader.close();

				try {
					Thread.sleep(11); //why is this 11?
				}
				catch (InterruptedException ex)	{}

				reader = new BufferedReader(new InputStreamReader(
						process.getErrorStream()));
				while ((line = reader.readLine()) != null)
					System.err.println(line);
				reader.close();

				try {
					process.waitFor();
				} catch (InterruptedException ex) { }
				int exit = process.exitValue();
				if (exit != 0)
					System.exit(exit);
			}
		catch (IOException ex) {
			throw new CompileException( ex.getLocalizedMessage() );
		}
	}


	@Override
	public void startMethod(TACMethod method, TACModule module) throws ShadowException {
			
		MethodSignature signature = method.getSignature();
		if (module.getType() instanceof InterfaceType ) {
			skipMethod = true;
		}
		else if (signature.isNative() || signature.isExternWithoutBlock()) {
			writer.write("declare " + methodToString(method));
			writer.write();
			skipMethod = true;
		}
		else {
			SequenceType parameters = signature.getSignatureWithoutTypeArguments().getFullParameterTypes();
			tempCounter = parameters.size();
			writer.write("define " + methodToString(method) +
					(signature.isWrapper() ? " unnamed_addr" : "" ) +
					(method.hasLandingpad() ? " personality i32 (...)* @__shadow_personality_v0 {" : " {"  ));
			writer.indent();
		}
	}

	private String name(TACVariable variable)
	{		
		return '%' + variable.getName();
	}

	@Override
	public void walk(TACNode nodes) throws ShadowException {
		if( !skipMethod )
			super.walk(nodes);
	}

	@Override
	public void endMethod(TACMethod method, TACModule module) throws ShadowException {

		if( !skipMethod ) {
			writer.outdent();
			writer.write('}');
			writer.write();
		}
		skipMethod = false;
		method = null;
	}

	@Override
	public void visit(TACLongToPointer node) throws ShadowException {
		writer.write(nextTemp(node) + " = inttoptr " + type(Type.ULONG) + " " +
				symbol(node.getOperand(0)) + " to " + type(node.getType())); 
	}

	@Override
	public void visit(TACPointerToLong node) throws ShadowException {		
		writer.write(nextTemp(node) + " = ptrtoint " + typeSymbol(node.getOperand(0)) +
				" to " + type(Type.ULONG));
	}

	@Override
	public void visit(TACCopyMemory node) throws ShadowException {
		TACOperand destinationNode = node.getDestination();
		TACOperand sourceNode = node.getSource();
		TACOperand size = node.getSize();
	
		String destination = typeSymbol(destinationNode);
		String source = typeSymbol(sourceNode);

		if( destinationNode.getType() instanceof ArrayType ) {
			ArrayType arrayType = (ArrayType) destinationNode.getType();
			writer.write(nextTemp() + " = extractvalue " +
					destination + ", 0");
			writer.write(nextTemp() + " = getelementptr " + pointerType(arrayType, false) + ", " +
					pointerType(arrayType) + " " + temp(1) + ", i32 0, i32 1");
			destination = typeText(arrayType.getBaseType(), temp(0), true);			
		}

		if( sourceNode.getType() instanceof ArrayType ) {
			ArrayType arrayType = (ArrayType) sourceNode.getType();
			writer.write(nextTemp() + " = extractvalue " +
					source + ", 0");
			writer.write(nextTemp() + " = getelementptr " + pointerType(arrayType, false) + ", " +
					pointerType(arrayType) + " " + temp(1) + ", i32 0, i32 1");
			source = typeText(arrayType.getBaseType(), temp(0), true);			
		}		
				
		writer.write(nextTemp() + " = bitcast " + destination + " to i8*");
		writer.write(nextTemp() + " = bitcast " + source + " to i8*");
		
		//regular objects (used in copy() and freeze()) have an 8 byte reference count that should *not* be copied
		//this is already taken care of with arrays
		if( !(destinationNode.getType() instanceof ArrayType) && !(sourceNode.getType() instanceof ArrayType) ) {
			writer.write(nextTemp() + " = getelementptr i8, i8* " + temp(2) + ", i32 8"); //destination
			writer.write(nextTemp() + " = getelementptr i8, i8* " + temp(2) + ", i32 8"); //source			
			writer.write(nextTemp() + " = sub i64 " + symbol(size) + ", 8");
			writer.write("call void @llvm.memcpy.p0i8.p0i8.i64(i8* " + temp(2) + ", i8* " + temp(1) + ", i64 " + temp(0) + ", i32 1, i1 0)");
		}
		else			
			writer.write("call void @llvm.memcpy.p0i8.p0i8.i64(i8* " + temp(1) + ", i8* " + temp(0) + ", i64 " + symbol(size) + ", i32 1, i1 0)");		
	}

	@Override
	public void visit(TACMethodRef node) throws ShadowException {
		if (node.getOuterType() instanceof InterfaceType) {
			writer.write(nextTemp() + " = extractvalue " +
					type(node.getOuterType()) + " " + symbol(node.getPrefix()) + ", 0");
			writer.write(nextTemp() + " = getelementptr " +
					methodTableType(node.getOuterType()) +
					", " + methodTableType(node.getOuterType()) + "* " +
					temp(1) + ", i32 0, i32 " + node.getIndex());
			String back1 = temp(0);
			writer.write(nextTemp(node) + " = load " + methodType(node) + ", " + methodType(node) +
					"* " + back1);
		}
		else if (node.hasPrefix() && 
				//Devirtualization conditions below
				!node.getOuterType().isPrimitive() &&
				!node.getOuterType().getModifiers().isLocked() &&
				!node.getType().getModifiers().isLocked() &&
				!(node.getOuterType() instanceof SingletonType) &&
				!node.getType().getModifiers().isPrivate() &&
				!node.isSuper() ) {	
			writer.write(nextTemp() + " = getelementptr inbounds %" +
					raw(node.getPrefix().getType()) + ", " + 					
					typeSymbol(node.getPrefix()) + ", i32 0, i32 2");

			writer.write(nextTemp() + " = load " + methodTableType(node.getPrefix().getType()) + "*, " +
					methodTableType(node.getPrefix().getType()) + "** " + temp(1));

			writer.write(nextTemp() + " = getelementptr inbounds " +
					methodTableType(node.getPrefix().getType()) + ", " + 
					methodTableType(node.getPrefix().getType()) + "* " +
					temp(1) + ", i32 0, i32 " + node.getIndex()); //may need to + 1 to the node.getIndex() if a parent method table is added	

			String back1 = temp(0);
			writer.write(nextTemp(node) + " = load " + methodType(node) + ", " + methodType(node) +
					"* " + back1);
		}
		else {			
			node.setData(name(node));
			MethodSignature signature = node.getSignature();
			if( !module.getType().encloses(signature.getOuter()) && !signature.isWrapper()  )
				usedSignatures.add(signature.getSignatureWithoutTypeArguments());
		}
	}

	@Override
	public void visit(TACClass node) throws ShadowException {		
		node.setData(node.getClassData().getData());
	}

	@Override
	public void visit(TACSequence node) throws ShadowException {
		String current = "undef";
		for (int i = 0; i < node.size(); i++) {
			writer.write(nextTemp() + " = insertvalue " + typeText(node,
					current) + ", " + typeSymbol(node.get(i)) + ", " + i);
			current = temp(0);
		}
		node.setData(current);
	}

	@Override
	public void visit(TACSequenceElement node ) throws ShadowException {	
		writer.write(nextTemp(node) + " = extractvalue " +
				typeSymbol(node.getOperand(0)) + ", " + node.getIndex());		
	}	

	private void writeObjectToArray(TACCast node, ArrayType arrayType, TACOperand source) throws ShadowException {
		String srcName = symbol(source);
		Type srcType = source.getType();		
		Type genericArray;

		if( arrayType.isNullable()  )
			genericArray = Type.ARRAY_NULLABLE;
		else			
			genericArray = Type.ARRAY;

		if (!srcType.equals(genericArray)) {
			writer.write(nextTemp() + " = bitcast " + typeSymbol(source) + " to " + type(genericArray));
			srcType = genericArray;
			srcName = temp(0);
		}		

		String arrayTypeName = type(arrayType);
		writer.write(nextTemp() + " = getelementptr inbounds %" + raw(srcType) + ", " +
				typeText(srcType, srcName) + ", i32 0, i32 3");
		writer.write(nextTemp() + " = bitcast " + type(OBJECT_ARRAY) + "* " + temp(1) + " to " + arrayTypeName + "*");
		String reference = temp(0);
		writer.write(nextTemp(node) + " = load " + arrayTypeName + ", " + arrayTypeName + "* " + reference);
	}

	private void writeArrayToObject(TACCast node, ArrayType arrayType, TACOperand source, TACClass arrayClass) throws ShadowException {
		Type genericArray;
		if( arrayType.isNullable() )
			genericArray = Type.ARRAY_NULLABLE;				
		else
			genericArray = Type.ARRAY;				

		String newObject;
		writer.write(nextTemp() + " = bitcast " + typeText(Type.GENERIC_CLASS, symbol(arrayClass.getClassData())) + " to " + type(Type.CLASS));
		writer.write((newObject = nextTemp()) + " = call noalias " +
				type(Type.OBJECT) + " @__allocate(" + typeTemp(Type.CLASS,1) + ", " +
						methodTableType(Type.OBJECT) + "* bitcast(" + methodTableType(genericArray) + "* " +  symbol(arrayClass.getMethodTable()) + " to " + methodTableType(Type.OBJECT) + "*)" + 
				')');
		
		String symbol = symbol(source);
		
		String objectArray;
		if( arrayType.getBaseType().equals(Type.OBJECT) )
			objectArray = symbol;
		else {
			//stupid LLVM can't cast between struct types
			writer.write(nextTemp() + " = extractvalue " + typeText(arrayType, symbol) + ", 0");
			writer.write(nextTemp() + " = bitcast " + pointerType(arrayType) + " " + temp(1) + " to " + pointerType(OBJECT_ARRAY));
			writer.write(nextTemp() + " = insertvalue " + type(OBJECT_ARRAY) + " undef, " + pointerType(OBJECT_ARRAY) + " " + temp(1) + ", 0");
			writer.write(nextTemp() + " = extractvalue " + typeText(arrayType, symbol) + ", 1");
			writer.write(nextTemp() + " = insertvalue " + typeTemp(OBJECT_ARRAY, 2) + ", " + typeTemp(Type.CLASS, 1) + ", 1");
			writer.write(nextTemp() + " = extractvalue " + typeText(arrayType, symbol) + ", 2");
			writer.write((objectArray = nextTemp()) + " = insertvalue " + typeTemp(OBJECT_ARRAY, 2) + ", " + typeTemp(Type.ULONG, 1) + ", 2");
		}

		SequenceType arguments = new SequenceType();
		arguments.add(new SimpleModifiedType(OBJECT_ARRAY));		
		MethodSignature arrayCreate = genericArray.getMatchingMethod("create", arguments);						
		writer.write(nextTemp(node) + " = call " + type(genericArray) + " " +
			name(arrayCreate) + '(' +
			typeText(Type.OBJECT, newObject) + ", " +						
			typeText(OBJECT_ARRAY, objectArray) + ')');
	}

	@Override
	public void visit(TACCast node) throws ShadowException { 
		TACOperand value = node.getUpdatedValue(); 
		//no precomputation done
		if( value == null ) {
			TACOperand source = node.getOperand(0);		
			Type destType = node.getType();
			Type srcType = source.getType();
			String back1, back2;		
			String srcTypeName;
			String destTypeName;

			switch(node.getKind()) {		
			case ARRAY_TO_OBJECT:
				writeArrayToObject(node, (ArrayType)srcType, source, (TACClass)node.getOperand(1));
				break;
			case INTERFACE_TO_OBJECT:
				writer.write(nextTemp(node) + " = extractvalue " +
						typeSymbol(source) + ", 1");			
				break;
			case ITEM_TO_SEQUENCE:
				writer.write(nextTemp(node) + " = insertvalue " + type(node) +
						" undef, " + typeSymbol(node.getOperand(1)) + ", 0");	
				break;
			case NULL_TO_ARRAY:
				writer.write(nextTemp(node) + " = insertvalue " + type(node) +
						" zeroinitializer, " + type(((ArrayType)node.getType()).getBaseType()) + "* null, 0");
				break;		
			case NULL_TO_INTERFACE:
				writer.write(nextTemp(node) + " = insertvalue " + type(node) +
						" zeroinitializer, " + type(Type.OBJECT) + " null, 1");
				break;
			case OBJECT_TO_ARRAY:
				writeObjectToArray(node, (ArrayType)destType, source);
				break;
			case OBJECT_TO_INTERFACE:
				//operand 1 is the interface method table
				writer.write(nextTemp() + " = bitcast " + typeSymbol(node.getOperand(1)) +
						" to " + methodTableType(destType) + '*');
				writer.write(nextTemp() + " = insertvalue " + type(destType) +
						" undef, " + methodTableType(destType) + "* " + temp(1) +
						", 0");
				writer.write(nextTemp() + " = bitcast " +
						typeSymbol(source) + " to " + type(Type.OBJECT));			
				back1 = temp(0);
				back2 = temp(1);
				writer.write(nextTemp(node) + " = insertvalue " + typeText(destType,
						back2) + ", " + typeText(Type.OBJECT, back1) + ", 1");
				break;			
			case OBJECT_TO_OBJECT:
				srcTypeName = type(srcType, true); // nullable takes care of primitives in object form
				destTypeName = type(destType, true);
				writer.write(nextTemp(node) + " = bitcast " +
						srcTypeName + ' ' + symbol(source) + " to " + destTypeName);
				break;			
			case OBJECT_TO_PRIMITIVE:
				writer.write(nextTemp() + " = bitcast " + typeSymbol(source) + " to %" + raw(destType) +  "*");
				writer.write(nextTemp() + " = getelementptr inbounds %" +
						raw(destType) + ", %" + 
						raw(destType) + "* " + temp(1) + ", i32 0, i32 3");
				back1 = temp(0);
				writer.write(nextTemp(node) + " = load " +  type(destType) + ", " + typeText(destType, back1, true));			
				break;
			case PRIMITIVE_TO_OBJECT:
				writer.write(nextTemp() + " = call noalias " +	type(Type.OBJECT) + " @__allocate(" + 
						type(Type.CLASS) + ' ' +
						classOf(srcType) + ", " + methodTableType(Type.OBJECT) + "* bitcast(" +
						methodTableType(srcType) + "* " + methodTable(srcType) + " to " +
						methodTableType(Type.OBJECT) + "*)" + ")");			
				back1 = temp(0);
				String result = nextTemp(node); 
				writer.write(result + " = bitcast " + typeText(Type.OBJECT,
						back1) + " to %" + raw(srcType) + "*");
				writer.write(nextTemp() + " = getelementptr inbounds %" +
						raw(srcType) + ", %" + raw(srcType) + "* " + result + ", i32 0, i32 3");
				writer.write("store " + typeSymbol(source) + ", " +
						typeText(srcType, temp(0), true));
				break;
			case PRIMITIVE_TO_PRIMITIVE:	
				String instruction;
				int srcWidth = Type.getWidth(source), destWidth = Type.getWidth(node);
				srcTypeName = type(srcType);
				destTypeName = type(destType);
				if( srcType.isFloating() ) {
					if( destType.isFloating() )
						instruction = srcWidth > destWidth ? "fptrunc" : (srcWidth < destWidth ? "fpext" : "bitcast");
						else if( destType.isSigned() )
							instruction = "fptosi";
						else
							instruction = "fptoui";
				}
				else if( srcType.isSigned() ) {
					if( destType.isFloating() )
						instruction = "sitofp";
					else if( destType.isSigned() )
						instruction = srcWidth > destWidth ? "trunc" : (srcWidth < destWidth ? "sext" : "bitcast");
						else
							instruction = srcWidth > destWidth ? "trunc" : (srcWidth < destWidth ? "zext" : "bitcast");
				}
				else {//  srcType.isUnsigned() must be true
					if( destType.isFloating() )
						instruction = "uitofp";
					else
						instruction = srcWidth > destWidth ? "trunc" : (srcWidth < destWidth ? "zext" : "bitcast");
				}		
				writer.write(nextTemp(node) + " = " + instruction + ' ' +
						srcTypeName + ' ' + symbol(source) + " to " + destTypeName);
				break;
			case SEQUENCE_TO_ITEM:			
				writer.write(nextTemp(node) + " = extractvalue " +
						typeSymbol(source) + ", 0");	
				break;
			case SEQUENCE_TO_SEQUENCE:
				String current = "undef";
				String location;
				int index = 0;			
				for (int i = 0; i < node.getNumOperands(); i++) {
					if( i == node.getNumOperands() - 1 )
						location = nextTemp(node);
					else
						location = nextTemp();
					writer.write(location + " = insertvalue " + typeText(node,current) + ", " +
							typeSymbol(node.getOperand(i)) + ", " + index);
					current = location;
					index++;
				}			
				break;
			}
		}
		else
			//unusual case when casting from one primitive constant to another			
			node.setData(value.getData());
	}	

	@Override
	public void visit(TACNewObject node) throws ShadowException {				
		Type type = node.getClassType();	

		TACOperand _class = node.getClassData();
		TACOperand methods = node.getMethodTable();	

		//this is pretty ugly, but if we retrieved a generic type parameter's method table, it'll be stored as MethodTable*, not an Object_methods*
		if( type instanceof TypeParameter )
			writer.write(nextTemp() + " = bitcast " + type(Type.METHOD_TABLE) + " " +  symbol(methods) +  " to "  + methodTableType(Type.OBJECT) + "*");
		//any other method table will be of the correct type but needs cast to Object_methods* for compatibility with allocate()
		else 
			writer.write(nextTemp() + " = bitcast " + methodTableType(type.getTypeWithoutTypeArguments()) + "* " +  symbol(methods) +  " to "  + methodTableType(Type.OBJECT) + "*");
		String back1 = temp(0);		
		writer.write(nextTemp(node) + " = call noalias " + type(Type.OBJECT) +
				" @__allocate(" + type(Type.CLASS) +
				" " + symbol(_class) + ", " + methodTableType(Type.OBJECT) + "* " + back1 +
				" )");
	}

	@Override
	public void visit(TACNewArray node) throws ShadowException {		
		String allocationClass = typeSymbol(node.getBaseClass());		

		writer.write(nextTemp() + " = call noalias " + pointerType(OBJECT_ARRAY) + " @__allocateArray(" +
				allocationClass + ", " + typeSymbol(node.getSize()) + ')');
		writer.write(nextTemp() + " = bitcast " + pointerType(OBJECT_ARRAY) + " " +
				temp(1) + " to " + pointerType(node.getType()));
		writer.write(nextTemp() + " = insertvalue " + type(node) +
				" zeroinitializer, " + pointerType(node.getType()) + " " + temp(1) + ", 0");
		writer.write(nextTemp() + " = insertvalue " + type(node) + " " +
				temp(1) + ", " + allocationClass + ", 1");
		
		String last = temp(0);
		writer.write(nextTemp(node) + " = insertvalue " + type(node) + " " + 
				last + ", " + typeSymbol(node.getSize()) + ", 2");
	}
	

	@Override
	public void visit(TACBaseClass node) throws ShadowException {
		writer.write(nextTemp(node) + " = extractvalue " +
				typeSymbol(node.getArray()) + ", 1");
	}

	@Override
	public void visit(TACLength node) throws ShadowException {
		if( node.isLong() )
			writer.write(nextTemp(node) + " = extractvalue " +
					typeSymbol(node.getArray()) + ", 2");
		else {		
			writer.write(nextTemp() + " = extractvalue " +
					typeSymbol(node.getArray()) + ", 2");
			String oldTemp = temp(0);
			writer.write(nextTemp(node) + " = trunc " + type(Type.LONG) + " " + oldTemp + " to " + type(Type.INT));
		}
	}

	@Override
	public void visit(TACUnary node) throws ShadowException {
		TACOperand value = node.getUpdatedValue();
		//no precomputation done
		if( value == null ) {
			switch (node.getOperation()) {
			case "-":
				if( node.getType().isFloating() )
					visitUnary(node, "fsub", "-0.0");
				else
					visitUnary(node, "sub", "0");
				break;
			case "~":
			case "!":
				visitUnary(node, "xor", "-1");
				break;
			}
		}
		else
			node.setData(value.getData());
	}
	private void visitUnary(TACUnary node, String instruction, String first)
			throws ShadowException {

		writer.write(nextTemp(node) + " = " + instruction + ' ' + typeText(node,
				first) + ", " + symbol(node.getOperand()));
	}
	
	@Override
	public void visit(TACAllocateVariable node) throws ShadowException { 
		TACVariable local = node.getVariable();
		writer.write(name(local) + " = alloca " + type(local));		
	}
	
	@Override
	public void visit(TACChangeReferenceCount node) throws ShadowException { 
		ModifiedType reference;
		TACFieldRef field = null;
		TACVariable variable = null;
		
		String name;
		
		String objectArrayType = type(OBJECT_ARRAY);
		
		if( node.isField() )			
			reference = field = node.getField();		
{'fraction_non_alphanumeric': 0.1506192220477935, 'fraction_numerical': 0.00612680969823827, 'mean_word_length': 3.630439172135285, 'pattern_counts': {'":': 12, '<': 73, '<?xml version=': 0, '>': 75, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7143345', 'n_tokens_mistral': 34390, 'n_tokens_neox': 28961, 'n_words': 6002}