[XRAY] A Color Choosing helper for XRay Graph

[varno]

Summary

In Preparation for graph comparison, this patch breaks out the color
choice code from xray-graph into a library and adds polynomials for
the Sequential and Difference sets from ColorBrewer.

Depends on D29005

[varno]

• respond to comments

[varno]

• add in generation script

[dblaikie]

tools/llvm-xray/xray-color-helper.cc

525–527

usually skip the {} on single line blocks

tools/llvm-xray/xray-color-helper.h

24

I think this is probably google style clang-tidy (one space indenting the private/protected/etc) - don't think it's LLVM's style?

[dberris]

tools/llvm-xray/xray-color-helper-gen.wls

1–4 ↗

(On Diff #86567)

Probably needs top-matter to bear the correct license.

tools/llvm-xray/xray-color-helper.cc

56

Formatting suggestion:

static constexpr double Coeffs[][3][21] = {
  { // Describe 2D array
    {  // Describe this array
      -6.878460665e6, ...
       ...
    },
    {  // Describe this array
      -2.54152823e6, ...
      ...
    },
    ...
  },
  ...
};

tools/llvm-xray/xray-color-helper.h

23

This would benefit hugely from documentation. Show how to use it, what to use it for, etc.?

61

I might be missing something, but would it work better if you returned an RGB tuple?

[varno]

• Address Reviewer comments

[varno]

tools/llvm-xray/xray-color-helper.h

61

Not really, I would just have to convert it later, and the format specification is a little hard. If someone wants raw RGB tuples (unlikely) then they can add another function to do so easily enough. But as it is I would never use such a function.

[varno]

• Address Reviewer comments
• clang-format

[dberris]

tools/llvm-xray/xray-color-helper.cc

40

Is this first polynomial for the "red" component? If so, document that clearly here (both to clearly mark the start of the array, and as an indentation guide).

399

Explain what "Diverging Polynomials" means. Really this whole file shouldn't assume that readers will have time to look at the mentioned website just to understand what the names/mnemonics/short-cuts mean.

582–590

Reading this, it looks like you do just want to give a tuple<uint8_t, uint8_t, uint8_t> as the result, then the caller can transform it where they need it. Right now it's assuming that the caller will always want the string value rather than the triple, which seems like a bad assumption to make.

[varno]

• Address Reviewer comments
• clang-format
• addres reviwer comments

[varno]

• fix comments

[dberris]

Almost there...

tools/llvm-xray/xray-color-helper.cc

40

I hate to do this again, but this would look better if the comment was the same line as the { and the numbers were indented after the brace. Like so:

{ // Red coefficients
  -6.878...,
},
{ // Green coefficients
  -2.545...,
},

633–639

Does the initialisation have to happen in the constructor body, or could some (or all) of these go on an initialiser list instead?

666

Should also probably be a const member function.

678

Should probably be a const member function.

[varno]

• Address Reviewer comments
• clang-format
• addres reviwer comments
• fix comments
• Address Reviewer comments

[varno]

Git Rebase

[chandlerc]

Sorry to jump in with a peanut gallery comment, but just wanted to push back on some of the complexity we're adding here.

tools/llvm-xray/xray-color-helper.cc

23–36

I really think this is more complexity than is reasonable to add to LLVM for this use case.

IMO, we don't need perfectly accurate color interpolation here. We need roughly accurate, *simple* interpolation so that it is useful even where it isn't perfect.

I would strongly suggest switching to what I understand is the very common scheme of RGB -> HSV, linear interpolate, HSV -> RGB process for interpolating colors. That seems likely to be good enough for all realistic usages LLVM will have, and much easier to understand and maintain going forward.

[varno]

tools/llvm-xray/xray-color-helper.cc

23–36

Hi Chandler.

Colors are hard. Really hard. Especially when you want perceptual uniformity, as we do here. We want our perception of color to present a sense of distance quality. This is an attempt to have good perceptual uniformity in the least complicated way possible.

I have not heard of anyone interpolating in HSV, can you show an example. Everyone who does this sort of thing interpolates either in RGB very, very carefully (with many had chosen intermediate pointe) or in LAB like I am doing (or using bisection in delta-E).

[varno]

• [XRAY] A Color Choosing helper for XRay Graph
• Address Reviewer Comments and moved to piecewise HSV interpolation

[varno]

• clang-format

[chandlerc]

tools/llvm-xray/xray-color-helper.cc

23–36

I understand that colors are hard. I just don't believe that it is actually important to have (perfect) perceptual uniformity for these particular use cases.

I think that for tools like this, being close or having a rough correspondence is more than enough. If someone wants to get precise, they should use the actual data and not colors. The colors are to help *at a glance*.

Interpolating using HSV is the first answer to the first SO question I find when I search on Google for "interpolating between two colors":
http://stackoverflow.com/questions/13488957/interpolate-from-one-color-to-another

So, I guess not everyone?

Still, my comment remains in essence: this is too complicated for the value it brings. We should use a simpler solution with lower quality because the qualitative difference won't matter here. SO suggests one approach that seems reasonably simple. I'm happy for you to suggest other approaches, but they need to be similarly simple.

[varno]

tools/llvm-xray/xray-color-helper.cc

23–36

Hi Chandler

This patch implements the interpolation in HSV as requested.

[chandlerc]

tools/llvm-xray/xray-color-helper.cc

23–36

Thanks, this is already tremendously simpler.

I'd also suggest starting with a fairly small set of colors / schemes. I think 2 or 3 are fine. IT is easy to add more if and when we have a compelling use case for more color schemes. Until then, YAGNI -- we shouldn't add the code.

[varno]

• Reduce number of available ColorMaps as requested

[chandlerc]

(FWIW, I like the more minimal schemes here. We have a couple of sequential ones, and a solid divergent ones. Enough to be very useful, but no more than we really have use cases for today. That part LGTM, but leaving the code review proper to others.)

[dberris]

LGTM -- thanks very much for making the changes. I'll test and land soon.

test/tools/llvm-xray/X86/graph-color-simple-case.yaml

records:
   - { type: 0, func-id: 8, cpu: 1, thread: 111, kind: function-enter, tsc: 10700 }
   - { type: 0, func-id: 8, cpu: 1, thread: 111, kind: function-exit,  tsc: 10780 }
   - { type: 0, func-id: 9, cpu: 1, thread: 111, kind: function-enter, tsc: 10800 }
   - { type: 0, func-id: 9, cpu: 1, thread: 111, kind: function-exit,  tsc: 10890 }
 ---
 
 
 #EDGE:     digraph xray {
-#EDGE-DAG: F0 -> F7 [label="7.{{[0-9]*}}e+01" color="#B00100"];
-#EDGE-DAG: F0 -> F2 [label="2.{{[0-9]*}}e+01" color="#FD9965"];
+#EDGE-DAG: F0 -> F7 [label="7.{{[0-9]*}}e+01" color="#B00000"];
+#EDGE-DAG: F0 -> F2 [label="2.{{[0-9]*}}e+01" color="#FC9963"];
 #EDGE-DAG: F0 -> F9 [label="9.{{[0-9]*}}e+01" color="#7F0000"];
-#EDGE-DAG: F0 -> F4 [label="4.{{[0-9]*}}e+01" color="#E8543b"];
-#EDGE-DAG: F0 -> F6 [label="6.{{[0-9]*}}e+01" color="#C5140a"];
-#EDGE-DAG: F0 -> F1 [label="1.{{[0-9]*}}e+01" color="#FDC58c"];
-#EDGE-DAG: F0 -> F8 [label="8.{{[0-9]*}}e+01" color="#990101"];
-#EDGE-DAG: F0 -> F3 [label="3.{{[0-9]*}}e+01" color="#F5744d"];
-#EDGE-DAG: F0 -> F5 [label="5.{{[0-9]*}}e+01" color="#D83323"];
+#EDGE-DAG: F0 -> F4 [label="4.{{[0-9]*}}e+01" color="#E75339"];
+#EDGE-DAG: F0 -> F6 [label="6.{{[0-9]*}}e+01" color="#C4150D"];
+#EDGE-DAG: F0 -> F1 [label="1.{{[0-9]*}}e+01" color="#FDC48D"];
+#EDGE-DAG: F0 -> F8 [label="8.{{[0-9]*}}e+01" color="#970000"];
+#EDGE-DAG: F0 -> F3 [label="3.{{[0-9]*}}e+01" color="#F4744E"];
+#EDGE-DAG: F0 -> F5 [label="5.{{[0-9]*}}e+01" color="#D83220"];
 #EDGE-DAG: F7 [label="@(7)"];
 #EDGE-DAG: F2 [label="@(2)"];
 #EDGE-DAG: F9 [label="@(9)"];
 #EDGE-DAG: F4 [label="@(4)"];
 #EDGE-DAG: F6 [label="@(6)"];
 #EDGE-DAG: F1 [label="@(1)"];
 #EDGE-DAG: F8 [label="@(8)"];
 #EDGE-DAG: F3 [label="@(3)"];
 #EDGE-DAG: F5 [label="@(5)"];
 #EDGE-NEXT:     }
 #
 #VERTEX:     digraph xray {
 #VERTEX-DAG: node [shape=record];
 #VERTEX-DAG: F0 -> F7 [label=""];
 #VERTEX-DAG: F0 -> F2 [label=""];
 #VERTEX-DAG: F0 -> F9 [label=""];
 #VERTEX-DAG: F0 -> F4 [label=""];
 #VERTEX-DAG: F0 -> F6 [label=""];
 #VERTEX-DAG: F0 -> F1 [label=""];
 #VERTEX-DAG: F0 -> F8 [label=""];
 #VERTEX-DAG: F0 -> F3 [label=""];
 #VERTEX-DAG: F0 -> F5 [label=""];
-#VERTEX-DAG: F7 [label="{@(7)|7.{{[0-9]*}}e+01}" color="#B00100"];
-#VERTEX-DAG: F2 [label="{@(2)|2.{{[0-9]*}}e+01}" color="#FD9965"];
+#VERTEX-DAG: F7 [label="{@(7)|7.{{[0-9]*}}e+01}" color="#B00000"];
+#VERTEX-DAG: F2 [label="{@(2)|2.{{[0-9]*}}e+01}" color="#FC9963"];
 #VERTEX-DAG: F9 [label="{@(9)|9.{{[0-9]*}}e+01}" color="#7F0000"];
-#VERTEX-DAG: F4 [label="{@(4)|4.{{[0-9]*}}e+01}" color="#E8543b"];
-#VERTEX-DAG: F6 [label="{@(6)|6.{{[0-9]*}}e+01}" color="#C5140a"];
-#VERTEX-DAG: F1 [label="{@(1)|1.{{[0-9]*}}e+01}" color="#FDC58c"];
-#VERTEX-DAG: F8 [label="{@(8)|8.{{[0-9]*}}e+01}" color="#990101"];
-#VERTEX-DAG: F3 [label="{@(3)|3.{{[0-9]*}}e+01}" color="#F5744d"];
-#VERTEX-DAG: F5 [label="{@(5)|5.{{[0-9]*}}e+01}" color="#D83323"];
+#VERTEX-DAG: F4 [label="{@(4)|4.{{[0-9]*}}e+01}" color="#E75339"];
+#VERTEX-DAG: F6 [label="{@(6)|6.{{[0-9]*}}e+01}" color="#C4150D"];
+#VERTEX-DAG: F1 [label="{@(1)|1.{{[0-9]*}}e+01}" color="#FDC48D"];
+#VERTEX-DAG: F8 [label="{@(8)|8.{{[0-9]*}}e+01}" color="#970000"];
+#VERTEX-DAG: F3 [label="{@(3)|3.{{[0-9]*}}e+01}" color="#F4744E"];
+#VERTEX-DAG: F5 [label="{@(5)|5.{{[0-9]*}}e+01}" color="#D83220"];
 #VERTEX-NEXT: }

tools/llvm-xray/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   DebugInfoDWARF
   Object
   Support
   Symbolize
   XRay)
 
 set(LLVM_XRAY_TOOLS
   func-id-helper.cc
   xray-account.cc
+  xray-color-helper.cc
   xray-converter.cc
   xray-extract.cc
   xray-extract.cc
   xray-graph.cc
   xray-registry.cc)
 
 add_llvm_tool(llvm-xray llvm-xray.cc ${LLVM_XRAY_TOOLS})

tools/llvm-xray/xray-color-helper.h

+//===-- xray-graph.h - XRay Function Call Graph Renderer --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// A class to get a color from a specified gradient.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef XRAY_COLOR_HELPER_H
+#define XRAY_COLOR_HELPER_H
+
+#include <tuple>
+
+#include "llvm/ADT/ArrayRef.h"
+
+namespace llvm {
+namespace xray {
+
+/// The color helper class it a healper class which allows you to easily get a
+/// color in a gradient. This is used to color-code edges in XRay-Graph tools.
+///
+/// There are two types of color schemes in this class:
+///   - Sequential schemes, which are used to represent information from some
+///     minimum to some maximum. These take an input in the range [0,1]
+///   - Diverging schemes, which are used to represent information representing
+///     differenes, or a range that goes from negative to positive. These take
+///     an input in the range [-1,1].
+/// Usage;
+/// ColorHelper S(ColorHelper::SequentialScheme::OrRd); //Chose a color scheme.
+/// for (double p = 0.0; p <= 1; p += 0.1){
+///   cout() << S.getColor(p) << " \n"; // Sample the gradient at 0.1 intervals
+/// }
+///
+/// ColorHelper D(ColorHelper::DivergingScheme::Spectral); // Choose a color
+///                                                        // scheme.
+/// for (double p= -1; p <= 1 ; p += 0.1){
+///   cout() << D.getColor(p) << " \n"; // sample the gradient at 0.1 intervals
+/// }
+class ColorHelper {
+  double MinIn;
+  double MaxIn;
+
+  ArrayRef<std::tuple<uint8_t, uint8_t, uint8_t>> ColorMap;
+
+public:
+  /// Enum of the availible Sequential Color Schemes
+  enum class SequentialScheme {
+    // Schemes based on the ColorBrewer Color schemes of the same name from
+    // http://www.colorbrewer.org/ by Cynthis A Brewer Penn State University.
+    Blues,
+    Greens,
+    Greys,
+    Oranges,
+    Purples,
+    Reds,
+    BuGn,
+    BuPu,
+    GnBu,
+    OrRd,
+    PuBu,
+    PuBuGn,
+    PuRd,
+    RdPu,
+    YlGn,
+    YlGnBu,
+    YlOrBr,
+    YlOrRd
+  };
+
+  ColorHelper(SequentialScheme S);
+
+  /// Enum of the availible Diverging Color Schemes
+  enum class DivergingScheme {
+    // Schemes based on the ColorBrewer Color schemes of the same name from
+    // http://www.colorbrewer.org/ by Cynthis A Brewer Penn State University.
+    BrBG,
+    PiYG,
+    PRGn,
+    PuOr,
+    RdBu,
+    RdGy,
+    RdYlBu,
+    RdYlGn,
+    Spectral
+  };
+
+  ColorHelper(DivergingScheme S);
+
+  // Sample the gradient at the input point.
+  std::tuple<uint8_t, uint8_t, uint8_t> getColorTuple(double Point) const;
+
+  std::string getColorString(double Point) const;
+
+  // Convert a tuple to a string
+  static std::string getColorString(std::tuple<uint8_t, uint8_t, uint8_t> t);
+};
+}
+}
+#endif

tools/llvm-xray/xray-color-helper.cc

+//===-- xray-graph.cc - XRay Function Call Graph Renderer -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// A class to get a color from a specified gradient.
+//
+//===----------------------------------------------------------------------===//
+#include <algorithm>
+
+#include "xray-color-helper.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+using namespace xray;
+
+//  Sequential ColorMaps, which are used to represent information
+//  from some minimum to some maximum.
+
+static const std::tuple<uint8_t, uint8_t, uint8_t> SequentialMaps[][9] = {
+    {// The blues color scheme from http://colorbrewer2.org/
+     std::make_tuple(247, 251, 255), std::make_tuple(222, 235, 247),
+     std::make_tuple(198, 219, 239), std::make_tuple(158, 202, 225),
+     std::make_tuple(107, 174, 214), std::make_tuple(66, 146, 198),
+     std::make_tuple(33, 113, 181), std::make_tuple(8, 81, 156),
+     std::make_tuple(8, 48, 107)},
+    {// The greens color scheme from http://colorbrewer2.org/
+     std::make_tuple(247, 252, 245), std::make_tuple(229, 245, 224),
+     std::make_tuple(199, 233, 192), std::make_tuple(161, 217, 155),
+     std::make_tuple(116, 196, 118), std::make_tuple(65, 171, 93),
+     std::make_tuple(35, 139, 69), std::make_tuple(0, 109, 44),
+     std::make_tuple(0, 68, 27)},
+    {// The greys color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 255, 255), std::make_tuple(240, 240, 240),
+     std::make_tuple(217, 217, 217), std::make_tuple(189, 189, 189),
+     std::make_tuple(150, 150, 150), std::make_tuple(115, 115, 115),
+     std::make_tuple(82, 82, 82), std::make_tuple(37, 37, 37),
+     std::make_tuple(0, 0, 0)},
+    {// The oranges color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 245, 235), std::make_tuple(254, 230, 206),
+     std::make_tuple(253, 208, 162), std::make_tuple(253, 174, 107),
+     std::make_tuple(253, 141, 60), std::make_tuple(241, 105, 19),
+     std::make_tuple(217, 72, 1), std::make_tuple(166, 54, 3),
+     std::make_tuple(127, 39, 4)},
+    {// The purples color scheme from http://colorbrewer2.org/
+     std::make_tuple(252, 251, 253), std::make_tuple(239, 237, 245),
+     std::make_tuple(218, 218, 235), std::make_tuple(188, 189, 220),
+     std::make_tuple(158, 154, 200), std::make_tuple(128, 125, 186),
+     std::make_tuple(106, 81, 163), std::make_tuple(84, 39, 143),
+     std::make_tuple(63, 0, 125)},
+    {// The reds color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 245, 240), std::make_tuple(254, 224, 210),
+     std::make_tuple(252, 187, 161), std::make_tuple(252, 146, 114),
+     std::make_tuple(251, 106, 74), std::make_tuple(239, 59, 44),
+     std::make_tuple(203, 24, 29), std::make_tuple(165, 15, 21),
+     std::make_tuple(103, 0, 13)},
+    {// The BuGn color scheme from http://colorbrewer2.org/
+     std::make_tuple(247, 252, 253), std::make_tuple(229, 245, 249),
+     std::make_tuple(204, 236, 230), std::make_tuple(153, 216, 201),
+     std::make_tuple(102, 194, 164), std::make_tuple(65, 174, 118),
+     std::make_tuple(35, 139, 69), std::make_tuple(0, 109, 44),
+     std::make_tuple(0, 68, 27)},
+    {// The BuPu color scheme from http://colorbrewer2.org/
+     std::make_tuple(247, 252, 253), std::make_tuple(224, 236, 244),
+     std::make_tuple(191, 211, 230), std::make_tuple(158, 188, 218),
+     std::make_tuple(140, 150, 198), std::make_tuple(140, 107, 177),
+     std::make_tuple(136, 65, 157), std::make_tuple(129, 15, 124),
+     std::make_tuple(77, 0, 75)},
+    {// The GnBu color scheme from http://colorbrewer2.org/
+     std::make_tuple(247, 252, 240), std::make_tuple(224, 243, 219),
+     std::make_tuple(204, 235, 197), std::make_tuple(168, 221, 181),
+     std::make_tuple(123, 204, 196), std::make_tuple(78, 179, 211),
+     std::make_tuple(43, 140, 190), std::make_tuple(8, 104, 172),
+     std::make_tuple(8, 64, 129)},
+    {// The OrRd color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 247, 236), std::make_tuple(254, 232, 200),
+     std::make_tuple(253, 212, 158), std::make_tuple(253, 187, 132),
+     std::make_tuple(252, 141, 89), std::make_tuple(239, 101, 72),
+     std::make_tuple(215, 48, 31), std::make_tuple(179, 0, 0),
+     std::make_tuple(127, 0, 0)},
+    {// The PuBu color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 247, 251), std::make_tuple(236, 231, 242),
+     std::make_tuple(208, 209, 230), std::make_tuple(166, 189, 219),
+     std::make_tuple(116, 169, 207), std::make_tuple(54, 144, 192),
+     std::make_tuple(5, 112, 176), std::make_tuple(4, 90, 141),
+     std::make_tuple(2, 56, 88)},
+    {// The PuBuGn color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 247, 251), std::make_tuple(236, 226, 240),
+     std::make_tuple(208, 209, 230), std::make_tuple(166, 189, 219),
+     std::make_tuple(103, 169, 207), std::make_tuple(54, 144, 192),
+     std::make_tuple(2, 129, 138), std::make_tuple(1, 108, 89),
+     std::make_tuple(1, 70, 54)},
+    {// The PuRd color scheme from http://colorbrewer2.org/
+     std::make_tuple(247, 244, 249), std::make_tuple(231, 225, 239),
+     std::make_tuple(212, 185, 218), std::make_tuple(201, 148, 199),
+     std::make_tuple(223, 101, 176), std::make_tuple(231, 41, 138),
+     std::make_tuple(206, 18, 86), std::make_tuple(152, 0, 67),
+     std::make_tuple(103, 0, 31)},
+    {// The RdPu color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 247, 243), std::make_tuple(253, 224, 221),
+     std::make_tuple(252, 197, 192), std::make_tuple(250, 159, 181),
+     std::make_tuple(247, 104, 161), std::make_tuple(221, 52, 151),
+     std::make_tuple(174, 1, 126), std::make_tuple(122, 1, 119),
+     std::make_tuple(73, 0, 106)},
+    {// The YlGn color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 255, 229), std::make_tuple(247, 252, 185),
+     std::make_tuple(217, 240, 163), std::make_tuple(173, 221, 142),
+     std::make_tuple(120, 198, 121), std::make_tuple(65, 171, 93),
+     std::make_tuple(35, 132, 67), std::make_tuple(0, 104, 55),
+     std::make_tuple(0, 69, 41)},
+    {// The YlGnBu color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 255, 217), std::make_tuple(237, 248, 177),
+     std::make_tuple(199, 233, 180), std::make_tuple(127, 205, 187),
+     std::make_tuple(65, 182, 196), std::make_tuple(29, 145, 192),
+     std::make_tuple(34, 94, 168), std::make_tuple(37, 52, 148),
+     std::make_tuple(8, 29, 88)},
+    {// The YlOrBr color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 255, 229), std::make_tuple(255, 247, 188),
+     std::make_tuple(254, 227, 145), std::make_tuple(254, 196, 79),
+     std::make_tuple(254, 153, 41), std::make_tuple(236, 112, 20),
+     std::make_tuple(204, 76, 2), std::make_tuple(153, 52, 4),
+     std::make_tuple(102, 37, 6)},
+    {// The YlOrRd color scheme from http://colorbrewer2.org/
+     std::make_tuple(255, 255, 204), std::make_tuple(255, 237, 160),
+     std::make_tuple(254, 217, 118), std::make_tuple(254, 178, 76),
+     std::make_tuple(253, 141, 60), std::make_tuple(252, 78, 42),
+     std::make_tuple(227, 26, 28), std::make_tuple(189, 0, 38),
+     std::make_tuple(128, 0, 38)}};
+
+ColorHelper::ColorHelper(ColorHelper::SequentialScheme S)
+    : MinIn(0.0), MaxIn(1.0), ColorMap(SequentialMaps[static_cast<int>(S)]) {}
+
+// Diverging ColorMaps, which are used to represent information
+// representing differenes, or a range that goes from negative to positive.
+// These take an input in the range [-1,1].
+
+static const std::tuple<uint8_t, uint8_t, uint8_t> DivergingCoeffs[][11] = {
+    {// The BrBG color scheme from http://colorbrewer2.org/
+     std::make_tuple(84, 48, 5), std::make_tuple(140, 81, 10),
+     std::make_tuple(191, 129, 45), std::make_tuple(223, 194, 125),
+     std::make_tuple(246, 232, 195), std::make_tuple(245, 245, 245),
+     std::make_tuple(199, 234, 229), std::make_tuple(128, 205, 193),
+     std::make_tuple(53, 151, 143), std::make_tuple(1, 102, 94),
+     std::make_tuple(0, 60, 48)},
+    {// The PiYG color scheme from http://colorbrewer2.org/
+     std::make_tuple(142, 1, 82), std::make_tuple(197, 27, 125),
+     std::make_tuple(222, 119, 174), std::make_tuple(241, 182, 218),
+     std::make_tuple(253, 224, 239), std::make_tuple(247, 247, 247),
+     std::make_tuple(230, 245, 208), std::make_tuple(184, 225, 134),
+     std::make_tuple(127, 188, 65), std::make_tuple(77, 146, 33),
+     std::make_tuple(39, 100, 25)},
+    {// The PRGn color scheme from http://colorbrewer2.org/
+     std::make_tuple(64, 0, 75), std::make_tuple(118, 42, 131),
+     std::make_tuple(153, 112, 171), std::make_tuple(194, 165, 207),
+     std::make_tuple(231, 212, 232), std::make_tuple(247, 247, 247),
+     std::make_tuple(217, 240, 211), std::make_tuple(166, 219, 160),
+     std::make_tuple(90, 174, 97), std::make_tuple(27, 120, 55),
+     std::make_tuple(0, 68, 27)},
+    {// The PuOr color scheme from http://colorbrewer2.org/
+     std::make_tuple(127, 59, 8), std::make_tuple(179, 88, 6),
+     std::make_tuple(224, 130, 20), std::make_tuple(253, 184, 99),
+     std::make_tuple(254, 224, 182), std::make_tuple(247, 247, 247),
+     std::make_tuple(216, 218, 235), std::make_tuple(178, 171, 210),
+     std::make_tuple(128, 115, 172), std::make_tuple(84, 39, 136),
+     std::make_tuple(45, 0, 75)},
+    {// The RdBu color scheme from http://colorbrewer2.org/
+     std::make_tuple(103, 0, 31), std::make_tuple(178, 24, 43),
+     std::make_tuple(214, 96, 77), std::make_tuple(244, 165, 130),
+     std::make_tuple(253, 219, 199), std::make_tuple(247, 247, 247),
+     std::make_tuple(209, 229, 240), std::make_tuple(146, 197, 222),
+     std::make_tuple(67, 147, 195), std::make_tuple(33, 102, 172),
+     std::make_tuple(5, 48, 97)},
+    {// The RdGy color scheme from http://colorbrewer2.org/
+     std::make_tuple(103, 0, 31), std::make_tuple(178, 24, 43),
+     std::make_tuple(214, 96, 77), std::make_tuple(244, 165, 130),
+     std::make_tuple(253, 219, 199), std::make_tuple(255, 255, 255),
+     std::make_tuple(224, 224, 224), std::make_tuple(186, 186, 186),
+     std::make_tuple(135, 135, 135), std::make_tuple(77, 77, 77),
+     std::make_tuple(26, 26, 26)},
+    {// The RdYlBu color scheme from http://colorbrewer2.org/
+     std::make_tuple(165, 0, 38), std::make_tuple(215, 48, 39),
+     std::make_tuple(244, 109, 67), std::make_tuple(253, 174, 97),
+     std::make_tuple(254, 224, 144), std::make_tuple(255, 255, 191),
+     std::make_tuple(224, 243, 248), std::make_tuple(171, 217, 233),
+     std::make_tuple(116, 173, 209), std::make_tuple(69, 117, 180),
+     std::make_tuple(49, 54, 149)},
+    {// The RdYlGn color scheme from http://colorbrewer2.org/
+     std::make_tuple(165, 0, 38), std::make_tuple(215, 48, 39),
+     std::make_tuple(244, 109, 67), std::make_tuple(253, 174, 97),
+     std::make_tuple(254, 224, 139), std::make_tuple(255, 255, 191),
+     std::make_tuple(217, 239, 139), std::make_tuple(166, 217, 106),
+     std::make_tuple(102, 189, 99), std::make_tuple(26, 152, 80),
+     std::make_tuple(0, 104, 55)},
+    {// The Spectral color scheme from http://colorbrewer2.org/
+     std::make_tuple(158, 1, 66), std::make_tuple(213, 62, 79),
+     std::make_tuple(244, 109, 67), std::make_tuple(253, 174, 97),
+     std::make_tuple(254, 224, 139), std::make_tuple(255, 255, 191),
+     std::make_tuple(230, 245, 152), std::make_tuple(171, 221, 164),
+     std::make_tuple(102, 194, 165), std::make_tuple(50, 136, 189),
+     std::make_tuple(94, 79, 162)}};
+
+ColorHelper::ColorHelper(ColorHelper::DivergingScheme S)
+    : MinIn(-1.0), MaxIn(1.0), ColorMap(DivergingCoeffs[static_cast<int>(S)]) {}
+
+// Takes a tuple of uint8_ts representing a color in RGB and converts them to
+// HSV represented by a tuple of doubles
+static std::tuple<double, double, double>
+convertToHSV(const std::tuple<uint8_t, uint8_t, uint8_t> &Color) {
+  double Scaled[3] = {std::get<0>(Color) / 255.0, std::get<1>(Color) / 255.0,
+                      std::get<2>(Color) / 255.0};
+  int Min = 0;
+  int Max = 0;
+  for (int i = 1; i < 3; ++i) {
+    if (Scaled[i] < Scaled[Min])
+      Min = i;
+    if (Scaled[i] > Scaled[Max])
+      Max = i;
+  }
+
+  double C = Scaled[Max] - Scaled[Min];
+
+  double HPrime = (Scaled[(Max + 1) % 3] - Scaled[(Max + 2) % 3]) / C;
+  HPrime = HPrime + 2.0 * Max;
+
+  double H = (HPrime < 0) ? (HPrime + 6.0) * 60
+                          : HPrime * 60; // Scale to between 0 and 360
+
+  double V = Scaled[Max];
+
+  double S = (V == 0.0) ? 0.0 : C / V;
+
+  return std::make_tuple(H, S, V);
+}
+
+// Takes a double precision number, clips it between 0 and 1 and then converts
+// that to an integer between 0x00 and 0xFF with proxpper rounding.
+static uint8_t unitIntervalTo8BitChar(double B) {
+  double n = std::max(std::min(B, 1.0), 0.0);
+  return static_cast<uint8_t>(255 * n + 0.5);
+}
+
+// Takes a typle of doubles representing a color in HSV and converts them to
+// RGB represented as a tuple of uint8_ts
+static std::tuple<uint8_t, uint8_t, uint8_t>
+convertToRGB(const std::tuple<double, double, double> &Color) {
+  const double &H = std::get<0>(Color);
+  const double &S = std::get<1>(Color);
+  const double &V = std::get<2>(Color);
+
+  double C = V * S;
+
+  double HPrime = H / 60;
+  double X = C * (1 - std::abs(std::fmod(HPrime, 2.0) - 1));
+
+  double RGB1[3];
+  int HPrimeInt = static_cast<int>(HPrime);
+  if (HPrimeInt % 2 == 0) {
+    RGB1[(HPrimeInt / 2) % 3] = C;
+    RGB1[(HPrimeInt / 2 + 1) % 3] = X;
+    RGB1[(HPrimeInt / 2 + 2) % 3] = 0.0;
+  } else {
+    RGB1[(HPrimeInt / 2) % 3] = X;
+    RGB1[(HPrimeInt / 2 + 1) % 3] = C;
+    RGB1[(HPrimeInt / 2 + 2) % 3] = 0.0;
+  }
+
+  double Min = V - C;
+  double RGB2[3] = {RGB1[0] + Min, RGB1[1] + Min, RGB1[2] + Min};
+
+  return std::make_tuple(unitIntervalTo8BitChar(RGB2[0]),
+                         unitIntervalTo8BitChar(RGB2[1]),
+                         unitIntervalTo8BitChar(RGB2[2]));
+}
+
+// The Hue component of the HSV interpolation Routine
+static double interpolateHue(double H0, double H1, double T) {
+  double D = H1 - H0;
+  if (H0 > H1) {
+    std::swap(H0, H1);
+
+    D = -D;
+    T = 1 - T;
+  }
+
+  if (D <= 180) {
+    return H0 + T * (H1 - H0);
+  } else {
+    H0 = H0 + 360;
+    return std::fmod(H0 + T * (H1 - H0) + 720, 360);
+  }
+}
+
+// Interpolates between two HSV Colors both represented as a tuple of doubles
+// Returns an HSV Color represented as a tuple of doubles
+static std::tuple<double, double, double>
+interpolateHSV(const std::tuple<double, double, double> &C0,
+               const std::tuple<double, double, double> &C1, double T) {
+  double H = interpolateHue(std::get<0>(C0), std::get<0>(C1), T);
+  double S = std::get<1>(C0) + T * (std::get<1>(C1) - std::get<1>(C0));
+  double V = std::get<2>(C0) + T * (std::get<2>(C1) - std::get<2>(C0));
+  return std::make_tuple(H, S, V);
+}
+
+// Get the Color as a tuple of uint8_ts
+std::tuple<uint8_t, uint8_t, uint8_t>
+ColorHelper::getColorTuple(double Point) const {
+  double IntervalWidth = (MaxIn - MinIn);
+  double OffsetP = Point - MinIn;
+  double SectionWidth = IntervalWidth / (ColorMap.size() - 1);
+  int SectionNo = static_cast<int>(OffsetP / SectionWidth);
+  double T = (OffsetP - SectionNo * SectionWidth) / SectionWidth;
+
+  auto &RGBColor0 = ColorMap[SectionNo];
+  auto &RGBColor1 = ColorMap[SectionNo + 1];
+
+  auto HSVColor0 = convertToHSV(RGBColor0);
+  auto HSVColor1 = convertToHSV(RGBColor1);
+
+  auto InterpolatedHSVColor = interpolateHSV(HSVColor0, HSVColor1, T);
+  return convertToRGB(InterpolatedHSVColor);
+}
+
+// A helper method to convert a color represented as tuple of uint8s to a hex
+// string.
+std::string
+ColorHelper::getColorString(std::tuple<uint8_t, uint8_t, uint8_t> t) {
+  return llvm::formatv("#{0:X-2}{1:X-2}{2:X-2}", std::get<0>(t), std::get<1>(t),
+                       std::get<2>(t));
+}
+
+// Gets a color in a gradient given a number in the interval [0,1], it does this
+// by evaluating a polynomial which maps [0, 1] -> [0, 1] for each of the R G
+// and B values in the color. It then converts this [0,1] colors to a 24 bit
+// color as a hex string.
+std::string ColorHelper::getColorString(double Point) const {
+  return getColorString(getColorTuple(Point));
+}

tools/llvm-xray/xray-graph.h

 
 #ifndef XRAY_GRAPH_H
 #define XRAY_GRAPH_H
 
 #include <string>
 #include <vector>
 
 #include "func-id-helper.h"
+#include "xray-color-helper.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Program.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/XRay/Graph.h"
 #include "llvm/XRay/Trace.h"
 #include "llvm/XRay/XRayRecord.h"
public:
 
   /// Use a Map to store the Function stack for each thread whilst building the
   /// graph.
   ///
   /// FIXME: Perhaps we can Build this into LatencyAccountant? or vise versa?
   PerThreadFunctionStackMap PerThreadFunctionStack;
 
   /// Usefull object for getting human readable Symbol Names.
-  FuncIdConversionHelper &FuncIdHelper;
+  const FuncIdConversionHelper &FuncIdHelper;
   bool DeduceSiblingCalls = false;
   TimestampT CurrentMaxTSC = 0;
 
   /// A private function to help implement the statistic generation functions;
   template <typename U>
   void getStats(U begin, U end, GraphRenderer::TimeStat &S);
   void updateMaxStats(const TimeStat &S, TimeStat &M);
 
   /// Calculates latency statistics for each edge and stores the data in the
   /// Graph
   void calculateEdgeStatistics();
 
   /// Calculates latency statistics for each vertex and stores the data in the
   /// Graph
   void calculateVertexStatistics();
 
   /// Normalises latency statistics for each edge and vertex by CycleFrequency;
   void normalizeStatistics(double CycleFrequency);
 
+  /// An object to color gradients
+  ColorHelper CHelper;
+
 public:
   /// Takes in a reference to a FuncIdHelper in order to have ready access to
   /// Symbol names.
-  explicit GraphRenderer(FuncIdConversionHelper &FuncIdHelper, bool DSC)
-      : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC) {
+  explicit GraphRenderer(const FuncIdConversionHelper &FuncIdHelper, bool DSC)
+      : FuncIdHelper(FuncIdHelper), DeduceSiblingCalls(DSC),
+        CHelper(ColorHelper::SequentialScheme::OrRd) {
     G[0] = {};
   }
 
   /// Process an Xray record and expand the graph.
   ///
   /// This Function will return true on success, or false if records are not
   /// presented in per-thread call-tree DFS order. (That is for each thread the
   /// Records should be in order runtime on an ideal system.)

tools/llvm-xray/xray-graph.cc

case GraphRenderer::StatType::SUM:
     S << Sum;
     break;
   case GraphRenderer::StatType::NONE:
     break;
   }
   return S.str();
 }
 
-// Evaluates a polynomial given the coefficints provided in an ArrayRef
-// evaluating:
-//
-//    p(x) = a[n-0]*x^0 + a[n-1]*x^1 + ... a[n-n]*x^n
-//
-// at x_0 using Horner's Method for both performance and stability reasons.
-static double polyEval(ArrayRef<double> a, double x_0) {
-  double B = 0;
-  for (const auto &c : a) {
-    B = c + B * x_0;
-  }
-  return B;
-}
-
-// Takes a double precision number, clips it between 0 and 1 and then converts
-// that to an integer between 0x00 and 0xFF with proxpper rounding.
-static uint8_t uintIntervalTo8bitChar(double B) {
-  double n = std::max(std::min(B, 1.0), 0.0);
-  return static_cast<uint8_t>(255 * n + 0.5);
-}
-
-// Gets a color in a gradient given a number in the interval [0,1], it does this
-// by evaluating a polynomial which maps [0, 1] -> [0, 1] for each of the R G
-// and B values in the color. It then converts this [0,1] colors to a 24 bit
-// color.
-//
-// In order to calculate these polynomials,
-//   1. Convert the OrRed9 color scheme from http://colorbrewer2.org/ from sRGB
-//      to LAB color space.
-//   2. Interpolate between the descrete colors in LAB space using a cubic
-//      spline interpolation.
-//   3. Sample this interpolation at 100 points and convert to sRGB.
-//   4. Calculate a polynomial fit for these 100 points for each of R G and B.
-//      We used a polynomial of degree 9 arbitrarily based on a fuzzy goodness
-//      of fit metric (using human judgement);
-//   5. Extract these polynomial coefficients from matlab as a set of constants.
-static std::string getColor(double point) {
-  assert(point >= 0.0 && point <= 1);
-  const static double RedPoly[] = {-38.4295,  239.239, -600.108, 790.544,
-                                   -591.26,   251.304, -58.0983, 6.62999,
-                                   -0.325899, 1.00173};
-  const static double GreenPoly[] = {-603.634,   2338.15, -3606.74, 2786.16,
-                                     -1085.19,   165.15,  11.2584,  -6.11338,
-                                     -0.0091078, 0.965469};
-  const static double BluePoly[] = {-325.686, 947.415,  -699.079, -513.75,
-                                    1127.78,  -732.617, 228.092,  -33.8202,
-                                    0.732108, 0.913916};
-
-  uint8_t r = uintIntervalTo8bitChar(polyEval(RedPoly, point));
-  uint8_t g = uintIntervalTo8bitChar(polyEval(GreenPoly, point));
-  uint8_t b = uintIntervalTo8bitChar(polyEval(BluePoly, point));
-
-  return llvm::formatv("#{0:X-2}{1:X-2}{2:x-2}", r, g, b);
-}
-
 // Returns the quotient between the property T of this and another TimeStat as
 // a double
 double GraphRenderer::TimeStat::compare(StatType T, const TimeStat &O) const {
   double retval = 0;
   switch (T) {
   case GraphRenderer::StatType::COUNT:
     retval = static_cast<double>(Count) / static_cast<double>(O.Count);
     break;
void GraphRenderer::exportGraphAsDOT(raw_ostream &OS, const XRayFileHeader &H,
   if (VT != StatType::NONE)
     OS << "node [shape=record];\n";
 
   for (const auto &E : G.edges()) {
     const auto &S = E.second.S;
     OS << "F" << E.first.first << " -> "
        << "F" << E.first.second << " [label=\"" << S.getAsString(ET) << "\"";
     if (EC != StatType::NONE)
-      OS << " color=\"" << getColor(S.compare(EC, G.GraphEdgeMax)) << "\"";
+      OS << " color=\"" << CHelper.getColorString(S.compare(EC, G.GraphEdgeMax))
+         << "\"";
     OS << "];\n";
   }
 
   for (const auto &V : G.vertices()) {
     const auto &VA = V.second;
     if (V.first == 0)
       continue;
     OS << "F" << V.first << " [label=\"" << (VT != StatType::NONE ? "{" : "")
        << (VA.SymbolName.size() > 40 ? VA.SymbolName.substr(0, 40) + "..."
                                      : VA.SymbolName);
     if (VT != StatType::NONE)
       OS << "|" << VA.S.getAsString(VT) << "}\"";
     else
       OS << "\"";
     if (VC != StatType::NONE)
-      OS << " color=\"" << getColor(VA.S.compare(VC, G.GraphVertexMax)) << "\"";
+      OS << " color=\"" << CHelper.getColorString(VA.S.compare(VC, G.GraphVertexMax))
+         << "\"";
     OS << "];\n";
   }
   OS << "}\n";
 }
 
 // Here we register and implement the llvm-xray graph subcommand.
 // The bulk of this code reads in the options, opens the required files, uses
 // those files to create a context for analysing the xray trace, then there is a