#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "type.cuh"

#define UP     0
#define LEFT   1
#define UL     2
#define MAX(I, J)  ((I) > (J) ? (I) : (J))

typedef ChromType Pattern;


void LcsString(int **b, ChromType *x, int i, int j, ChromType *l, int li);
void MatPrint(int **cmat, int m, int n);

int EqualPat(ChromType *x, ChromType *y);

/* longest common subsequence implementation from CLR page 317 */
/* Sushil J. Louis */
/* x is newString and m is its length
   y is templateString and n is its length
*/

double DoLcs(ChromType *x, ChromType *y, int m, int n, 
	   ChromType *tmplate)
{
  int i, j;
  ChromType *tmp; /*  = "hello"; */
  int **cmat; /* DP matrix to track longest common subsequence */
  int **bmat; /* DP matrix to reconstruct string */
  int len;


  cmat = (int * *) malloc(sizeof(int *) * (m+1));
  for(i = 0; i < m + 1; i++){
    cmat[i] = (int *) malloc(sizeof(int) * (n+1));
  }

  bmat = (int * *) malloc(sizeof(int *) * (m+1));
  for(i = 0; i < m + 1; i++){
    bmat[i] = (int *) malloc(sizeof(int) * (n+1));
  }

  /* initialize cmat for main loop computation */
  for(i = 0; i < m + 1 ; i++){
    cmat[i][0] = 0;
  }
  for(j = 0; j < n + 1 ; j++){
    cmat[0][j] = 0;
  }

  /* main loop to calculate lcs */
  for(i = 1; i < m + 1; i++) {
    for(j = 1; j < n + 1; j++) {
      if(EqualPat(&x[i-1], &y[j-1])) {
	cmat[i][j] = cmat[i - 1][j - 1] + 1;
	bmat[i][j] = UL;
      } else if (cmat[i - 1][j] >= cmat[i][j - 1]) {
	cmat[i][j] = cmat[i - 1][j];
	bmat[i][j] = UP;
      } else {
	cmat[i][j] = cmat[i][j - 1];
	bmat[i][j] = LEFT;
      }
    }
  }

  /* tmp is temporary storage since we get the string in reverse */
  tmp = (ChromType *) malloc (sizeof(ChromType) * (m + 1));
  LcsString(bmat, x, m, n, tmp, 0);

  len = cmat[m][n]; /* length is the last entry in the matrix */

  /* reverse tmp to make the actual substring */

  for(i = 0; i < len ; i++){
    tmplate[i] = tmp[len - 1 - i];
  }


  for(i = 0; i < m + 1; i++){
    free(cmat[i]);
  }
  free(cmat);

  for(i = 0; i < m + 1; i++){
    free(bmat[i] );
  }
  free (bmat);
  free(tmp);

  return len;
}

void LcsString(int **b, ChromType *x, int i, int j, ChromType *l, int li)
{
  if(i == 0 || j == 0) {
    return;
  }
  if(b[i][j] == UL) {
      LcsString(b, x, i - 1, j - 1, l, li + 1);
      l[li] = x[i-1];
  } else if (b[i][j] == UP) {
      LcsString(b, x, i - 1, j, l, li);
  } else {
      LcsString(b, x, i, j - 1, l , li);
  }
}

void MatPrint(int **cmat, int m, int n)
{
  int i, j;

  for(i = 0; i < m ; i++){
    for(j = 0; j < n; j++){
      printf("%d ", cmat[i][j]);
    }
    printf("\n");
  }
}

int EqualPat(ChromType *x, ChromType *y)
{
  return (*x == *y);

}


	.file	"tmpxft_00280288_00000000-6_lcs.cudafe1.cpp"
	.text
#APP

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2033:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2033:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z9LcsStringPPiS_iiS_i
	.type	_Z9LcsStringPPiS_iiS_i, @function
_Z9LcsStringPPiS_iiS_i:
.LFB2028:
	.cfi_startproc
	endbr64
	pushq	%r13
	.cfi_def_cfa_offset 16
	.cfi_offset 13, -16
	movl	%edx, %eax
	pushq	%r12
	.cfi_def_cfa_offset 24
	.cfi_offset 12, -24
	movq	%r8, %r12
	pushq	%rbp
	.cfi_def_cfa_offset 32
	.cfi_offset 6, -32
	movq	%rsi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 40
	.cfi_offset 3, -40
	movslq	%r9d, %rbx
	pushq	%r10
	.cfi_def_cfa_offset 48
.L3:
	testl	%eax, %eax
	je	.L2
	testl	%ecx, %ecx
	je	.L2
	movslq	%eax, %r13
	movslq	%ecx, %rdx
	movq	(%rdi,%r13,8), %rsi
	movl	(%rsi,%rdx,4), %edx
	cmpl	$2, %edx
	jne	.L5
	leal	-1(%rax), %edx
	decl	%ecx
	leal	1(%rbx), %r9d
	movq	%r12, %r8
	movq	%rbp, %rsi
	call	_Z9LcsStringPPiS_iiS_i
	movl	-4(%rbp,%r13,4), %eax
	movl	%eax, (%r12,%rbx,4)
	jmp	.L2
.L5:
	testl	%edx, %edx
	jne	.L6
	decl	%eax
	jmp	.L3
.L6:
	decl	%ecx
	jmp	.L3
.L2:
	popq	%rax
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%rbp
	.cfi_def_cfa_offset 24
	popq	%r12
	.cfi_def_cfa_offset 16
	popq	%r13
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2028:
	.size	_Z9LcsStringPPiS_iiS_i, .-_Z9LcsStringPPiS_iiS_i
	.globl	_Z5DoLcsPiS_iiS_
	.type	_Z5DoLcsPiS_iiS_, @function
_Z5DoLcsPiS_iiS_:
.LFB2027:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	leal	1(%rdx), %r13d
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movslq	%r13d, %r13
	xorl	%r12d, %r12d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	leaq	0(,%r13,8), %rax
	movslq	%ecx, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	leal	1(%rbp), %r14d
	movl	%edx, %ebx
	movslq	%r14d, %r14
	subq	$56, %rsp
	.cfi_def_cfa_offset 112
	movq	%rdi, 24(%rsp)
	movq	%rax, %rdi
	movq	%rsi, 32(%rsp)
	movq	%r8, 40(%rsp)
	movq	%rax, 8(%rsp)
	call	malloc@PLT
	movq	%rax, %r15
	leaq	0(,%r14,4), %rax
	movq	%rax, 16(%rsp)
.L11:
	cmpl	%r12d, %ebx
	jl	.L33
	movq	16(%rsp), %rdi
	call	malloc@PLT
	movq	%rax, (%r15,%r12,8)
	incq	%r12
	jmp	.L11
.L33:
	movq	8(%rsp), %rdi
	xorl	%r14d, %r14d
	call	malloc@PLT
	movq	%rax, %r12
.L13:
	cmpl	%r14d, %ebx
	jl	.L34
	movq	16(%rsp), %rdi
	call	malloc@PLT
	movq	%rax, (%r12,%r14,8)
	incq	%r14
	jmp	.L13
.L34:
	xorl	%eax, %eax
.L15:
	cmpl	%eax, %ebx
	jl	.L35
	movq	(%r15,%rax,8), %rdx
	xorl	%esi, %esi
	incq	%rax
	movl	%esi, (%rdx)
	jmp	.L15
.L35:
	xorl	%eax, %eax
.L17:
	cmpl	%eax, %ebp
	jl	.L36
	movq	(%r15), %rdx
	xorl	%ecx, %ecx
	movl	%ecx, (%rdx,%rax,4)
	incq	%rax
	jmp	.L17
.L36:
	movl	$1, %eax
.L19:
	cmpl	%eax, %ebx
	jl	.L37
	xorl	%edx, %edx
	movl	$1, %esi
.L23:
	cmpl	%ebp, %esi
	jg	.L38
	movq	(%r15,%rax,8), %r11
	movq	(%r12,%rax,8), %r8
	leaq	4(%rdx), %rdi
	movq	32(%rsp), %r14
	movq	24(%rsp), %r10
	movq	-8(%r15,%rax,8), %rcx
	leaq	(%r11,%rdi), %r9
	addq	%rdi, %r8
	movl	(%r14,%rdx), %r14d
	cmpl	%r14d, -4(%r10,%rax,4)
	jne	.L20
	movl	(%rcx,%rdx), %ecx
	movl	$2, %edx
	incl	%ecx
	jmp	.L21
.L20:
	movl	4(%rcx,%rdx), %ecx
	movl	(%r11,%rdx), %r11d
	xorl	%edx, %edx
	cmpl	%r11d, %ecx
	jge	.L21
	movl	%r11d, %ecx
	movl	$1, %edx
.L21:
	movl	%edx, (%r8)
	incl	%esi
	movq	%rdi, %rdx
	movl	%ecx, (%r9)
	jmp	.L23
.L38:
	incq	%rax
	jmp	.L19
.L37:
	leaq	0(,%r13,4), %rdi
	call	malloc@PLT
	movq	24(%rsp), %rsi
	movl	%ebp, %ecx
	movl	%ebx, %edx
	movq	%rax, %r8
	xorl	%r9d, %r9d
	movq	%r12, %rdi
	movq	%rax, %r13
	call	_Z9LcsStringPPiS_iiS_i
	movq	8(%rsp), %rax
	movq	-8(%r15,%rax), %rax
	movslq	(%rax,%rbp,4), %rax
	movq	%rax, %rbp
	leaq	0(%r13,%rax,4), %rdx
	xorl	%eax, %eax
.L24:
	subq	$4, %rdx
	cmpl	%eax, %ebp
	jle	.L39
	movl	(%rdx), %ecx
	movq	40(%rsp), %rsi
	movl	%ecx, (%rsi,%rax,4)
	incq	%rax
	jmp	.L24
.L39:
	xorl	%r14d, %r14d
.L26:
	cmpl	%r14d, %ebx
	jl	.L40
	movq	(%r15,%r14,8), %rdi
	incq	%r14
	call	free@PLT
	jmp	.L26
.L40:
	movq	%r15, %rdi
	xorl	%r14d, %r14d
	call	free@PLT
.L28:
	cmpl	%r14d, %ebx
	jl	.L41
	movq	(%r12,%r14,8), %rdi
	incq	%r14
	call	free@PLT
	jmp	.L28
.L41:
	movq	%r12, %rdi
	call	free@PLT
	movq	%r13, %rdi
	call	free@PLT
	addq	$56, %rsp
	.cfi_def_cfa_offset 56
	cvtsi2sdl	%ebp, %xmm0
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2027:
	.size	_Z5DoLcsPiS_iiS_, .-_Z5DoLcsPiS_iiS_
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d "
.LC1:
	.string	"\n"
	.text
	.globl	_Z8MatPrintPPiii
	.type	_Z8MatPrintPPiii, @function
_Z8MatPrintPPiii:
.LFB2029:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	.LC0(%rip), %r15
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	movl	%edx, %r14d
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movq	%rdi, %r13
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movl	%esi, %r12d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	xorl	%ebx, %ebx
	pushq	%rcx
	.cfi_def_cfa_offset 64
.L43:
	cmpl	%ebx, %r12d
	jle	.L48
	xorl	%ebp, %ebp
.L45:
	cmpl	%ebp, %r14d
	jle	.L49
	movq	0(%r13,%rbx,8), %rax
	movq	%r15, %rsi
	movl	$2, %edi
	movl	(%rax,%rbp,4), %edx
	xorl	%eax, %eax
	incq	%rbp
	call	__printf_chk@PLT
	jmp	.L45
.L49:
	leaq	.LC1(%rip), %rsi
	movl	$2, %edi
	xorl	%eax, %eax
	incq	%rbx
	call	__printf_chk@PLT
	jmp	.L43
.L48:
	popq	%rax
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2029:
	.size	_Z8MatPrintPPiii, .-_Z8MatPrintPPiii
	.globl	_Z8EqualPatPiS_
	.type	_Z8EqualPatPiS_, @function
_Z8EqualPatPiS_:
.LFB2030:
	.cfi_startproc
	endbr64
	movl	(%rsi), %eax
	cmpl	%eax, (%rdi)
	sete	%al
	movzbl	%al, %eax
	ret
	.cfi_endproc
.LFE2030:
	.size	_Z8EqualPatPiS_, .-_Z8EqualPatPiS_
	.section	.text.startup,"ax",@progbits
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2056:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	movq	%rax, %rdi
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rdx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2056:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:


#include <hip/hip_runtime.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "type.cuh"

#define UP     0
#define LEFT   1
#define UL     2
#define MAX(I, J)  ((I) > (J) ? (I) : (J))

typedef ChromType Pattern;


void LcsString(int **b, ChromType *x, int i, int j, ChromType *l, int li);
void MatPrint(int **cmat, int m, int n);

int EqualPat(ChromType *x, ChromType *y);

/* longest common subsequence implementation from CLR page 317 */
/* Sushil J. Louis */
/* x is newString and m is its length
   y is templateString and n is its length
*/

double DoLcs(ChromType *x, ChromType *y, int m, int n, 
	   ChromType *tmplate)
{
  int i, j;
  ChromType *tmp; /*  = "hello"; */
  int **cmat; /* DP matrix to track longest common subsequence */
  int **bmat; /* DP matrix to reconstruct string */
  int len;


  cmat = (int * *) malloc(sizeof(int *) * (m+1));
  for(i = 0; i < m + 1; i++){
    cmat[i] = (int *) malloc(sizeof(int) * (n+1));
  }

  bmat = (int * *) malloc(sizeof(int *) * (m+1));
  for(i = 0; i < m + 1; i++){
    bmat[i] = (int *) malloc(sizeof(int) * (n+1));
  }

  /* initialize cmat for main loop computation */
  for(i = 0; i < m + 1 ; i++){
    cmat[i][0] = 0;
  }
  for(j = 0; j < n + 1 ; j++){
    cmat[0][j] = 0;
  }

  /* main loop to calculate lcs */
  for(i = 1; i < m + 1; i++) {
    for(j = 1; j < n + 1; j++) {
      if(EqualPat(&x[i-1], &y[j-1])) {
	cmat[i][j] = cmat[i - 1][j - 1] + 1;
	bmat[i][j] = UL;
      } else if (cmat[i - 1][j] >= cmat[i][j - 1]) {
	cmat[i][j] = cmat[i - 1][j];
	bmat[i][j] = UP;
      } else {
	cmat[i][j] = cmat[i][j - 1];
	bmat[i][j] = LEFT;
      }
    }
  }

  /* tmp is temporary storage since we get the string in reverse */
  tmp = (ChromType *) malloc (sizeof(ChromType) * (m + 1));
  LcsString(bmat, x, m, n, tmp, 0);

  len = cmat[m][n]; /* length is the last entry in the matrix */

  /* reverse tmp to make the actual substring */

  for(i = 0; i < len ; i++){
    tmplate[i] = tmp[len - 1 - i];
  }


  for(i = 0; i < m + 1; i++){
    free(cmat[i]);
  }
  free(cmat);

  for(i = 0; i < m + 1; i++){
    free(bmat[i] );
  }
  free (bmat);
  free(tmp);

  return len;
}

void LcsString(int **b, ChromType *x, int i, int j, ChromType *l, int li)
{
  if(i == 0 || j == 0) {
    return;
  }
  if(b[i][j] == UL) {
      LcsString(b, x, i - 1, j - 1, l, li + 1);
      l[li] = x[i-1];
  } else if (b[i][j] == UP) {
      LcsString(b, x, i - 1, j, l, li);
  } else {
      LcsString(b, x, i, j - 1, l , li);
  }
}

void MatPrint(int **cmat, int m, int n)
{
  int i, j;

  for(i = 0; i < m ; i++){
    for(j = 0; j < n; j++){
      printf("%d ", cmat[i][j]);
    }
    printf("\n");
  }
}

int EqualPat(ChromType *x, ChromType *y)
{
  return (*x == *y);

}


	.text
	.file	"lcs.hip"
	.globl	_Z5DoLcsPiS_iiS_                # -- Begin function _Z5DoLcsPiS_iiS_
	.type	_Z5DoLcsPiS_iiS_,@function
_Z5DoLcsPiS_iiS_:                       # @_Z5DoLcsPiS_iiS_
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	subq	$72, %rsp
	.cfi_def_cfa_offset 128
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movq	%r8, %r12
                                        # kill: def $ecx killed $ecx def $rcx
	movq	%rcx, 16(%rsp)                  # 8-byte Spill
	movl	%edx, %r13d
	movq	%rsi, %rbx
	movq	%rdi, %rbp
	leal	1(%r13), %r15d
	movslq	%r15d, %rax
	movq	%rax, 56(%rsp)                  # 8-byte Spill
	leaq	(,%rax,8), %rdi
	movq	%rdi, 8(%rsp)                   # 8-byte Spill
	callq	malloc
	movq	%rax, %r14
	movslq	16(%rsp), %rax                  # 4-byte Folded Reload
	testl	%r13d, %r13d
	movq	%r13, 24(%rsp)                  # 8-byte Spill
	movl	%r15d, 36(%rsp)                 # 4-byte Spill
	movq	%rax, 64(%rsp)                  # 8-byte Spill
	js	.LBB0_1
# %bb.11:                               # %.lr.ph
	leaq	4(,%rax,4), %rax
	movq	%rax, 48(%rsp)                  # 8-byte Spill
	movl	%r15d, %r13d
	xorl	%r15d, %r15d
.LBB0_12:                               # =>This Inner Loop Header: Depth=1
	movq	48(%rsp), %rdi                  # 8-byte Reload
	callq	malloc
	movq	%rax, (%r14,%r15,8)
	incq	%r15
	cmpq	%r15, %r13
	jne	.LBB0_12
# %bb.13:                               # %._crit_edge
	movq	8(%rsp), %rdi                   # 8-byte Reload
	callq	malloc
	movq	%rax, 8(%rsp)                   # 8-byte Spill
	movq	24(%rsp), %rax                  # 8-byte Reload
	testl	%eax, %eax
	js	.LBB0_14
# %bb.18:                               # %.lr.ph124
	xorl	%r15d, %r15d
	movq	%r13, 40(%rsp)                  # 8-byte Spill
	movq	48(%rsp), %r13                  # 8-byte Reload
.LBB0_19:                               # =>This Inner Loop Header: Depth=1
	movq	%r13, %rdi
	callq	malloc
	movq	8(%rsp), %rcx                   # 8-byte Reload
	movq	%rax, (%rcx,%r15,8)
	incq	%r15
	cmpq	%r15, 40(%rsp)                  # 8-byte Folded Reload
	jne	.LBB0_19
# %bb.15:                               # %.preheader118
	cmpl	$0, 24(%rsp)                    # 4-byte Folded Reload
	movq	40(%rsp), %rdx                  # 8-byte Reload
	js	.LBB0_14
# %bb.16:                               # %.lr.ph127.preheader
	xorl	%eax, %eax
	movq	8(%rsp), %r13                   # 8-byte Reload
	movq	16(%rsp), %r15                  # 8-byte Reload
.LBB0_17:                               # %.lr.ph127
                                        # =>This Inner Loop Header: Depth=1
	movq	(%r14,%rax,8), %rcx
	movl	$0, (%rcx)
	incq	%rax
	cmpq	%rax, %rdx
	jne	.LBB0_17
	jmp	.LBB0_3
.LBB0_14:
	movq	8(%rsp), %r13                   # 8-byte Reload
	jmp	.LBB0_2
.LBB0_1:                                # %._crit_edge.thread
	movq	8(%rsp), %rdi                   # 8-byte Reload
	callq	malloc
	movq	%rax, %r13
.LBB0_2:                                # %.preheader117
	movq	16(%rsp), %r15                  # 8-byte Reload
.LBB0_3:                                # %.preheader117
	testl	%r15d, %r15d
	js	.LBB0_5
# %bb.4:                                # %.lr.ph130
	movq	(%r14), %rdi
	movl	%r15d, %eax
	leaq	4(,%rax,4), %rdx
	xorl	%esi, %esi
	callq	memset@PLT
.LBB0_5:                                # %.preheader116
	cmpl	$0, 24(%rsp)                    # 4-byte Folded Reload
	jle	.LBB0_25
# %bb.6:                                # %.preheader115.lr.ph
	leal	1(%r15), %eax
	movl	36(%rsp), %ecx                  # 4-byte Reload
	decq	%rax
	movl	$1, %edx
.LBB0_7:                                # %.preheader115
                                        # =>This Loop Header: Depth=1
                                        #     Child Loop BB0_9 Depth 2
	testl	%r15d, %r15d
	jle	.LBB0_24
# %bb.8:                                # %.lr.ph133
                                        #   in Loop: Header=BB0_7 Depth=1
	movq	-8(%r14,%rdx,8), %rsi
	movq	(%r13,%rdx,8), %rdi
	xorl	%r8d, %r8d
.LBB0_9:                                #   Parent Loop BB0_7 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movl	-4(%rbp,%rdx,4), %r9d
	cmpl	(%rbx,%r8,4), %r9d
	jne	.LBB0_20
# %bb.10:                               #   in Loop: Header=BB0_9 Depth=2
	movl	(%rsi,%r8,4), %r9d
	incl	%r9d
	movq	(%r14,%rdx,8), %r10
	movl	%r9d, 4(%r10,%r8,4)
	movl	$2, %r9d
	jmp	.LBB0_23
.LBB0_20:                               #   in Loop: Header=BB0_9 Depth=2
	movl	4(%rsi,%r8,4), %r10d
	movq	(%r14,%rdx,8), %r9
	movl	(%r9,%r8,4), %r11d
	cmpl	%r11d, %r10d
	jge	.LBB0_21
# %bb.22:                               #   in Loop: Header=BB0_9 Depth=2
	movl	%r11d, 4(%r9,%r8,4)
	movl	$1, %r9d
	jmp	.LBB0_23
.LBB0_21:                               #   in Loop: Header=BB0_9 Depth=2
	movl	%r10d, 4(%r9,%r8,4)
	xorl	%r9d, %r9d
.LBB0_23:                               #   in Loop: Header=BB0_9 Depth=2
	movl	%r9d, 4(%rdi,%r8,4)
	incq	%r8
	cmpq	%r8, %rax
	jne	.LBB0_9
.LBB0_24:                               # %._crit_edge134
                                        #   in Loop: Header=BB0_7 Depth=1
	incq	%rdx
	cmpq	%rcx, %rdx
	jne	.LBB0_7
.LBB0_25:                               # %._crit_edge137
	movq	56(%rsp), %rdi                  # 8-byte Reload
	shlq	$2, %rdi
	callq	malloc
	movq	%rax, %rbx
	movq	%r13, 8(%rsp)                   # 8-byte Spill
	movq	%r13, %rdi
	movq	%rbp, %rsi
	movq	24(%rsp), %rbp                  # 8-byte Reload
	movl	%ebp, %edx
	movl	%r15d, %ecx
	movq	%rax, %r8
	xorl	%r9d, %r9d
	callq	_Z9LcsStringPPiS_iiS_i
	movslq	%ebp, %rax
	movq	(%r14,%rax,8), %rax
	movq	64(%rsp), %rcx                  # 8-byte Reload
	movl	(%rax,%rcx,4), %r13d
	testl	%r13d, %r13d
	jle	.LBB0_28
# %bb.26:
	movq	%r13, %rax
.LBB0_27:                               # %.lr.ph140
                                        # =>This Inner Loop Header: Depth=1
	movl	-4(%rbx,%rax,4), %ecx
	movl	%ecx, (%r12)
	addq	$4, %r12
	decq	%rax
	jne	.LBB0_27
.LBB0_28:                               # %.preheader
	testl	%ebp, %ebp
	movl	36(%rsp), %eax                  # 4-byte Reload
	js	.LBB0_29
# %bb.30:                               # %.lr.ph143.preheader
	movl	%eax, %r15d
	xorl	%r12d, %r12d
.LBB0_31:                               # %.lr.ph143
                                        # =>This Inner Loop Header: Depth=1
	movq	(%r14,%r12,8), %rdi
	callq	free
	incq	%r12
	cmpq	%r12, %r15
	jne	.LBB0_31
# %bb.32:                               # %._crit_edge144
	movq	%r14, %rdi
	callq	free
	cmpl	$0, 24(%rsp)                    # 4-byte Folded Reload
	movq	8(%rsp), %r12                   # 8-byte Reload
	js	.LBB0_35
# %bb.33:                               # %.lr.ph148.preheader
	xorl	%r14d, %r14d
.LBB0_34:                               # %.lr.ph148
                                        # =>This Inner Loop Header: Depth=1
	movq	(%r12,%r14,8), %rdi
	callq	free
	incq	%r14
	cmpq	%r14, %r15
	jne	.LBB0_34
	jmp	.LBB0_35
.LBB0_29:                               # %._crit_edge144.thread
	movq	%r14, %rdi
	callq	free
	movq	8(%rsp), %r12                   # 8-byte Reload
.LBB0_35:                               # %._crit_edge149
	movq	%r12, %rdi
	callq	free
	movq	%rbx, %rdi
	callq	free
	cvtsi2sd	%r13d, %xmm0
	addq	$72, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end0:
	.size	_Z5DoLcsPiS_iiS_, .Lfunc_end0-_Z5DoLcsPiS_iiS_
	.cfi_endproc
                                        # -- End function
	.globl	_Z8EqualPatPiS_                 # -- Begin function _Z8EqualPatPiS_
	.type	_Z8EqualPatPiS_,@function
_Z8EqualPatPiS_:                        # @_Z8EqualPatPiS_
	.cfi_startproc
# %bb.0:
	movl	(%rdi), %ecx
	xorl	%eax, %eax
	cmpl	(%rsi), %ecx
	sete	%al
	retq
.Lfunc_end1:
	.size	_Z8EqualPatPiS_, .Lfunc_end1-_Z8EqualPatPiS_
	.cfi_endproc
                                        # -- End function
	.globl	_Z9LcsStringPPiS_iiS_i          # -- Begin function _Z9LcsStringPPiS_iiS_i
	.type	_Z9LcsStringPPiS_iiS_i,@function
_Z9LcsStringPPiS_iiS_i:                 # @_Z9LcsStringPPiS_iiS_i
	.cfi_startproc
# %bb.0:
	testl	%edx, %edx
	je	.LBB2_11
# %bb.1:
	testl	%ecx, %ecx
	je	.LBB2_11
# %bb.2:                                # %.lr.ph.preheader
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%r12
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r12, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movl	%r9d, %r14d
	movq	%r8, %rbx
	movq	%rsi, %r15
	movslq	%edx, %r12
.LBB2_3:                                # %.lr.ph
                                        # =>This Loop Header: Depth=1
                                        #     Child Loop BB2_4 Depth 2
	movq	(%rdi,%r12,8), %rax
	movslq	%ecx, %rdx
	movl	%edx, %ecx
	negl	%ecx
	decq	%rdx
.LBB2_4:                                #   Parent Loop BB2_3 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movl	4(%rax,%rdx,4), %esi
	testl	%esi, %esi
	je	.LBB2_7
# %bb.5:                                #   in Loop: Header=BB2_4 Depth=2
	cmpl	$2, %esi
	je	.LBB2_6
# %bb.9:                                # %tailrecurse
                                        #   in Loop: Header=BB2_4 Depth=2
	incl	%ecx
	movq	%rdx, %rsi
	decq	%rsi
	testl	%edx, %edx
	movq	%rsi, %rdx
	jne	.LBB2_4
	jmp	.LBB2_10
.LBB2_7:                                # %tailrecurse.outer
                                        #   in Loop: Header=BB2_3 Depth=1
	decq	%r12
	testl	%r12d, %r12d
	je	.LBB2_10
# %bb.8:                                # %tailrecurse.outer
                                        #   in Loop: Header=BB2_3 Depth=1
	negl	%ecx
	jb	.LBB2_3
	jmp	.LBB2_10
.LBB2_6:
	leal	-1(%r12), %edx
	notl	%ecx
	leal	1(%r14), %r9d
	movq	%r15, %rsi
	movq	%rbx, %r8
	callq	_Z9LcsStringPPiS_iiS_i
	movslq	%r12d, %rax
	movl	-4(%r15,%rax,4), %eax
	movslq	%r14d, %rcx
	movl	%eax, (%rbx,%rcx,4)
.LBB2_10:
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	.cfi_restore %rbx
	.cfi_restore %r12
	.cfi_restore %r14
	.cfi_restore %r15
.LBB2_11:                               # %common.ret72
	retq
.Lfunc_end2:
	.size	_Z9LcsStringPPiS_iiS_i, .Lfunc_end2-_Z9LcsStringPPiS_iiS_i
	.cfi_endproc
                                        # -- End function
	.globl	_Z8MatPrintPPiii                # -- Begin function _Z8MatPrintPPiii
	.type	_Z8MatPrintPPiii,@function
_Z8MatPrintPPiii:                       # @_Z8MatPrintPPiii
	.cfi_startproc
# %bb.0:
	testl	%esi, %esi
	jle	.LBB3_7
# %bb.1:                                # %.preheader.lr.ph
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	pushq	%rax
	.cfi_def_cfa_offset 64
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	%edx, %ebx
	movq	%rdi, %r14
	movl	%esi, %r15d
	movl	%edx, %r12d
	xorl	%r13d, %r13d
.LBB3_2:                                # %.preheader
                                        # =>This Loop Header: Depth=1
                                        #     Child Loop BB3_4 Depth 2
	testl	%ebx, %ebx
	jle	.LBB3_5
# %bb.3:                                # %.lr.ph
                                        #   in Loop: Header=BB3_2 Depth=1
	xorl	%ebp, %ebp
.LBB3_4:                                #   Parent Loop BB3_2 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	movq	(%r14,%r13,8), %rax
	movl	(%rax,%rbp,4), %esi
	movl	$.L.str, %edi
	xorl	%eax, %eax
	callq	printf
	incq	%rbp
	cmpq	%rbp, %r12
	jne	.LBB3_4
.LBB3_5:                                # %._crit_edge
                                        #   in Loop: Header=BB3_2 Depth=1
	movl	$10, %edi
	callq	putchar@PLT
	incq	%r13
	cmpq	%r15, %r13
	jne	.LBB3_2
# %bb.6:
	addq	$8, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	.cfi_restore %rbx
	.cfi_restore %r12
	.cfi_restore %r13
	.cfi_restore %r14
	.cfi_restore %r15
	.cfi_restore %rbp
.LBB3_7:                                # %._crit_edge11
	retq
.Lfunc_end3:
	.size	_Z8MatPrintPPiii, .Lfunc_end3-_Z8MatPrintPPiii
	.cfi_endproc
                                        # -- End function
	.type	.L.str,@object                  # @.str
	.section	.rodata.str1.1,"aMS",@progbits,1
.L.str:
	.asciz	"%d "
	.size	.L.str, 4

	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_

	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.amdgpu_metadata
---
amdhsa.kernels:  []
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
