; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/artificial-branch.perfscript --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t  --skip-symbolization --use-offset=0
; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-EXT-ADDR
; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-noprobe2.perfscript --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t  --skip-symbolization --use-offset=0
; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-RAW-PROFILE
; RUN: llvm-profgen --format=text --unsymbolized-profile=%t --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t1 --use-offset=0
; RUN: FileCheck %s --input-file %t1 --check-prefix=CHECK

; RUN: llvm-profgen --format=extbinary --perfscript=%S/Inputs/inline-noprobe2.perfscript --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t --populate-profile-symbol-list=1
; RUN: llvm-profdata show -show-prof-sym-list -sample %t | FileCheck %s --check-prefix=CHECK-SYM-LIST

; CHECK-EXT-ADDR:      2
; CHECK-EXT-ADDR-NEXT: 400870-400870:2
; CHECK-EXT-ADDR-NEXT: 400875-4008bf:1
; CHECK-EXT-ADDR-NEXT: 2
; Value 1 is external address
; CHECK-EXT-ADDR-NEXT: 1->400875:1
; CHECK-EXT-ADDR-NEXT: 4008bf->400870:2


; CHECK-SYM-LIST: Dump profile symbol list
; CHECK-SYM-LIST: main
; CHECK-SYM-LIST: partition_pivot_first
; CHECK-SYM-LIST: partition_pivot_last
; CHECK-SYM-LIST: quick_sort
; CHECK-SYM-LIST: swap


;CHECK-RAW-PROFILE-NOT: 7f7448e889e4
;CHECK-RAW-PROFILE-NOT: 7f7448e88826

;CHECK: partition_pivot_first:3022:5
;CHECK:  0: 5
;CHECK:  1: 5
;CHECK:  2: 5
;CHECK:  3: 5
;CHECK:  3.1: 83
;CHECK:  4: 82
;CHECK:  4.1: 26
;CHECK:  4.2: 25
;CHECK:  4.3: 26
;CHECK:  5: 6
;CHECK:  6: 6
;CHECK:  65516: 5
;CHECK:  4.2: swap:300
;CHECK:   1: 25
;CHECK:   2: 25
;CHECK:   3: 25
;CHECK:  5: swap:102
;CHECK:   1: 6
;CHECK:   2: 6
;CHECK:   3: 6
;CHECK: main:1362:0
;CHECK:  0: 0
;CHECK:  3: 0
;CHECK:  4.1: 0
;CHECK:  4.3: 0
;CHECK:  5.1: 17
;CHECK:  5.3: 17
;CHECK:  6: 17
;CHECK:  6.1: 17
;CHECK:  6.3: 17
;CHECK:  7: 0
;CHECK:  8: 1 quick_sort:1
;CHECK:  9: 0
;CHECK:  11: 0
;CHECK:  14: 0
;CHECK:  65499: 0
;CHECK: partition_pivot_last:1210:7
;CHECK:  1: 6
;CHECK:  2: 6
;CHECK:  3: 6

;w/o duplication factor :  3.1: 18
;w/o duplication factor :  3.3: 18
;w/o duplication factor :  4: 19
;w/o duplication factor :  5: 9

;CHECK:  3.1: 36
;CHECK:  3.3: 36
;CHECK:  4: 38
;CHECK:  5: 18
;CHECK:  6: 5
;CHECK:  7: 5
;CHECK:  65526: 2
;CHECK:  5: swap:247

;w/o duplication factor :  1: 9
;w/o duplication factor :  2: 9
;w/o duplication factor :  3: 9

;CHECK:   1: 18
;CHECK:   2: 18
;CHECK:   3: 18
;CHECK:  6: swap:85
;CHECK:   1: 5
;CHECK:   2: 5
;CHECK:   3: 5
;CHECK: quick_sort:903:25
;CHECK:  1: 24
;CHECK:  2: 12 partition_pivot_last:7 partition_pivot_first:5
;CHECK:  3: 12 quick_sort:12
;CHECK:  4: 12 quick_sort:12
;CHECK:  6: 24
;CHECK:  65507: 12


; original code:
; clang -O3 -g -fno-optimize-sibling-calls -fdebug-info-for-profiling qsort.c -o a.out
#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
	int t = *a;
	*a = *b;
	*b = t;
}

int partition_pivot_last(int* array, int low, int high) {
	int pivot = array[high];
	int i = low - 1;
	for (int j = low; j < high; j++)
		if (array[j] < pivot)
			swap(&array[++i], &array[j]);
	swap(&array[i + 1], &array[high]);
	return (i + 1);
}

int partition_pivot_first(int* array, int low, int high) {
	int pivot = array[low];
	int i = low + 1;
	for (int j = low + 1; j <= high; j++)
		if (array[j] < pivot) { if (j != i) swap(&array[i], &array[j]); i++;}
	swap(&array[i - 1], &array[low]);
	return i - 1;
}

void quick_sort(int* array, int low, int high, int (*partition_func)(int *, int, int)) {
	if (low < high) {
		int pi = (*partition_func)(array, low, high);
		quick_sort(array, low, pi - 1, partition_func);
		quick_sort(array, pi + 1, high, partition_func);
	}
}

int main() {
	const int size = 200;
	int sum = 0;
	int *array = malloc(size * sizeof(int));
	for(int i = 0; i < 100 * 1000; i++) {
		for(int j = 0; j < size; j++)
			array[j] = j % 10 ? rand() % size: j;
		int (*fptr)(int *, int, int) = i % 3 ? partition_pivot_last : partition_pivot_first;
		quick_sort(array, 0, size - 1, fptr);
		sum += array[i % size];
	}
	printf("sum=%d\n", sum);

	return 0;
}