From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id S932852AbcGHOGw (ORCPT <rfc822;w@1wt.eu>);
	Fri, 8 Jul 2016 10:06:52 -0400
Received: from merlin.infradead.org ([205.233.59.134]:37339 "EHLO
	merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
	with ESMTP id S932747AbcGHOFi (ORCPT
	<rfc822;linux-kernel@vger.kernel.org>);
	Fri, 8 Jul 2016 10:05:38 -0400
Message-Id: <20160708133059.031522978@infradead.org>
User-Agent: quilt/0.63-1
Date: Fri, 08 Jul 2016 15:30:59 +0200
From: Peter Zijlstra <peterz@infradead.org>
To: mingo@kernel.org, acme@kernel.org, linux-kernel@vger.kernel.org
Cc: andi@firstfloor.org, eranian@google.com, jolsa@kernel.org,
        torvalds@linux-foundation.org, davidcc@google.com,
        alexander.shishkin@linux.intel.com, namhyung@kernel.org,
        kan.liang@intel.com, khandual@linux.vnet.ibm.com, peterz@infradead.org
Subject: [RFC][PATCH 0/7] perf: Branch stack annotation and fixes
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

Hi,

These here patches improve the perf branch-stack support and add branch-stack
support to perf-annotate.

They appear to work for me; but some of it is fairly hairy code so please have
a hard look.


The last patch includes the userspace changes; and includes samples
output of 'perf annotate branches', but since email doesn't do color,
lots of information is lost. A screenshot of the same data can be found
here:

  http://programming.kicks-ass.net/sekrit/peterz1.png

And the actual program can be found below.


--- branches.c ---

#include <stdlib.h>
#include <stdio.h>

#define B(x) (1 << x)

long lfsr_taps[] =
{
	[2] = B(0) | B(1),
	[3] = B(0) | B(2),
	[4] = B(0) | B(3),
	[5] = B(1) | B(4),
	[6] = B(0) | B(5),
	[7] = B(0) | B(6),
	[8] = B(1) | B(2) | B(3) | B(7),
	[9] = B(3) | B(8),
	[10] = B(2) | B(9),
	[11] = B(1) | B(10),
	[12] = B(0) | B(3) | B(5) | B(11),
	[13] = B(0) | B(2) | B(3) | B(12),
	[14] = B(0) | B(2) | B(4) | B(13),
	[15] = B(0) | B(14),
	[16] = B(1) | B(2) | B(4) | B(15),
	[17] = B(2) | B(16),
	[18] = B(6) | B(17),
	[19] = B(0) | B(1) | B(4) | B(18),
	[20] = B(2) | B(19),
	[21] = B(1) | B(20),
	[22] = B(0) | B(21),
	[23] = B(4) | B(22),
	[24] = B(0) | B(2) | B(3) | B(23),
	[25] = B(2) | B(24),
	[26] = B(0) | B(1) | B(5) | B(25),
	[27] = B(0) | B(1) | B(4) | B(26),
	[28] = B(2) | B(27),
	[29] = B(1) | B(28),
	[30] = B(0) | B(3) | B(5) | B(29),
	[31] = B(2) | B(30),
	[32] = B(1) | B(5) | B(6) | B(31),
};

unsigned long taps;

static unsigned long lfsr(unsigned long lfsr)
{
	lfsr = (lfsr>>1) ^ ((0x0u - (lfsr & 0x1u)) & taps);
	return lfsr;
}

void lfsr_init(long bits)
{
	taps = lfsr_taps[bits];
}

unsigned volatile long acc = 0;

void branches(unsigned long seed, unsigned long iterations)
{
	long i, reg = seed;

	for (i = 0; i < iterations; i++) {
		if (reg & 0x1)
			acc++;
		else
			acc--;

		reg = lfsr(reg);

		if (seed & 1)
			acc >>= 2;

		if (~reg & 0x1)
			acc--;
		else
			acc++;

		reg = lfsr(reg);
	}
}

int main(int argc, char **argv)
{
	long bits = 22;
	long seed = 2;

	if (argc > 1)
		bits = atoi(argv[1]);

	if (argc > 2)
		seed = atoi(argv[2]);

	lfsr_init(bits);
	branches(seed, 1 << bits);

	return 0;
}