1; RUN: llvm-profgen --format=text --unsymbolized-profile=%S/Inputs/profile-density.raw.prof --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t1 --use-offset=0 --show-density -hot-function-density-threshold=10  --trim-cold-profile=0 &> %t2
2; RUN: FileCheck %s --input-file %t2 --check-prefix=CHECK-DENSITY
3
4; RUN: llvm-profgen --format=text --unsymbolized-profile=%S/Inputs/profile-density-cs.raw.prof --binary=%S/Inputs/inline-noprobe2.perfbin --output=%t3 --show-density -hot-function-density-threshold=1 &> %t4
5; RUN: FileCheck %s --input-file %t4 --check-prefix=CHECK-DENSITY-CS
6
7;CHECK-DENSITY: AutoFDO is estimated to optimize better with 3.1x more samples. Please consider increasing sampling rate or profiling for longer duration to get more samples.
8;CHECK-DENSITY: Minimum profile density for hot functions with top 99.00% total samples: 3.2
9
10;CHECK-DENSITY-CS: Minimum profile density for hot functions with top 99.00% total samples: 128.3
11
12; original code:
13; clang -O3 -g -fno-optimize-sibling-calls -fdebug-info-for-profiling qsort.c -o a.out
14#include <stdio.h>
15#include <stdlib.h>
16
17void swap(int *a, int *b) {
18	int t = *a;
19	*a = *b;
20	*b = t;
21}
22
23int partition_pivot_last(int* array, int low, int high) {
24	int pivot = array[high];
25	int i = low - 1;
26	for (int j = low; j < high; j++)
27		if (array[j] < pivot)
28			swap(&array[++i], &array[j]);
29	swap(&array[i + 1], &array[high]);
30	return (i + 1);
31}
32
33int partition_pivot_first(int* array, int low, int high) {
34	int pivot = array[low];
35	int i = low + 1;
36	for (int j = low + 1; j <= high; j++)
37		if (array[j] < pivot) { if (j != i) swap(&array[i], &array[j]); i++;}
38	swap(&array[i - 1], &array[low]);
39	return i - 1;
40}
41
42void quick_sort(int* array, int low, int high, int (*partition_func)(int *, int, int)) {
43	if (low < high) {
44		int pi = (*partition_func)(array, low, high);
45		quick_sort(array, low, pi - 1, partition_func);
46		quick_sort(array, pi + 1, high, partition_func);
47	}
48}
49
50int main() {
51	const int size = 200;
52	int sum = 0;
53	int *array = malloc(size * sizeof(int));
54	for(int i = 0; i < 100 * 1000; i++) {
55		for(int j = 0; j < size; j++)
56			array[j] = j % 10 ? rand() % size: j;
57		int (*fptr)(int *, int, int) = i % 3 ? partition_pivot_last : partition_pivot_first;
58		quick_sort(array, 0, size - 1, fptr);
59		sum += array[i % size];
60	}
61	printf("sum=%d\n", sum);
62
63	return 0;
64}
65