How do I trace "fate" of a particular value?

I see some value in some place, but unsure where it has originated in my program. How do I figure out where this value initially comes from?

I expect the following event types to be logged:

A value originated from constant, arithmetical expression or syscall - the initial event;
The value was assigned to (or retrieved from) some variable;
The value was passed as an argument or returned from some function;
The value was stored to (or retrieved from) some struct;
By annotating source code with something specific, I triggered the history dump for this value.

For example, for this sample code:

#include <stdlib.h>

struct SomeStruct {
    int a;
    int b;
};

struct SomeStruct *globalvar;

int f1(struct SomeStruct* par) {
    return par->a;
}

int f2(struct SomeStruct* par, int q) {
    par->a = q;
    return par->b;
}

void trace_value(int g) {} /* dummy */

int main(void) {
    int f = 31337;

    globalvar = malloc(sizeof(*globalvar));
    f2(globalvar, f);
    struct SomeStruct q = *globalvar;
    int g = f1(&q);

    trace_value(g);

    return 0;
}

it should return something like

value 31337 originated from constant at fate.c:18
assigned to variable at fate.c:18
retrieved from variable at fate.c:21
passed as argument to function at fate.c:21
received as arument to a function at fate.c:12
assigned to struct field at fate.c:13
copied as a part of struct at fate.c:22
retrieved from struct field at fate.c:9
returned from function at fate.c:10
assigned to variable at fate.c:23
retrieved from variable at fate.c:25
traced at fate.c:25

How do I do this or something similar? I expect Valgrind or GDB or some combination should be able to do this.

Solution

Combined idea1 of using reverse gdb and idea2 from MarkPlotnick's comment of using gdb watchpoints. Here is the demo session, more complete than in original answer:

$ gcc -ggdb -Dtrace_value=exit fate.c -o fate
$ gdb -quiet -args ./fate 
Reading symbols from /home/vi/code/_/fate...done.
(gdb) break main
Breakpoint 1 at 0x8048482: file fate.c, line 18.
(gdb) r
Starting program: /home/vi/code/_/fate 
warning: Could not load shared library symbols for linux-gate.so.1.
Do you need "set solib-search-path" or "set sysroot"?

Breakpoint 1, main () at fate.c:18
18      int f = 31337;
(gdb) record
(gdb) break 25
(gdb) # traced at fate.c:25
Breakpoint 2 at 0x80484d2: file fate.c, line 25.
(gdb) c
Continuing.

Breakpoint 2, main () at fate.c:25
25      trace_value(g);
(gdb) # retrieved from variable at fate.c:25
(gdb) watch g
Hardware watchpoint 3: g
(gdb) reverse-continue 
Continuing.
Hardware watchpoint 3: g

Old value = 31337
New value = 134513899
0x080484ce in main () at fate.c:23
23      int g = f1(&q);
(gdb) # assigned to variable at fate.c:23
(gdb) # returned from function at fate.c:10
(gdb) reverse-step
f1 (par=0xffffd670) at fate.c:10
10  }
(gdb) list
5   
6   struct SomeStruct *globalvar;
7   
8   int f1(struct SomeStruct* par) {
9       return par->a;
10  }
11  
12  int f2(struct SomeStruct* par, int q) {
13      par->a = q;
14      return par->b;
(gdb) # retrieved from struct field at fate.c:9
(gdb) print par
$3 = (struct SomeStruct *) 0xffffd670
(gdb) print ((struct SomeStruct *) 0xffffd670)->a
$4 = 31337
(gdb) watch ((struct SomeStruct *) 0xffffd670)->a
Hardware watchpoint 4: ((struct SomeStruct *) 0xffffd670)->a
(gdb) reverse-continue 
Continuing.
Hardware watchpoint 4: ((struct SomeStruct *) 0xffffd670)->a

Old value = 31337
New value = -134716508
0x080484ba in main () at fate.c:22
22      struct SomeStruct q = *globalvar;
(gdb) # copied as a part of struct at fate.c:22
(gdb) print globalvar->a
$5 = 31337
(gdb) watch globalvar->a
Hardware watchpoint 5: globalvar->a
(gdb) reverse-continue 
Continuing.
Hardware watchpoint 5: globalvar->a

Old value = 31337
New value = 0
0x0804846f in f2 (par=0x804a008, q=31337) at fate.c:13
13      par->a = q;
(gdb) # assigned to struct field at fate.c:13
(gdb) # received as arument to a function at fate.c:12
(gdb) list
8   int f1(struct SomeStruct* par) {
9       return par->a;
10  }
11  
12  int f2(struct SomeStruct* par, int q) {
13      par->a = q;
14      return par->b;
15  }
16  
17  int main() {
(gdb) bt
#0  0x0804846f in f2 (par=0x804a008, q=31337) at fate.c:13
#1  0x080484b0 in main () at fate.c:21
(gdb) reverse-finish 
Run back to call of #0  0x0804846f in f2 (par=0x804a008, q=31337) at fate.c:13
0x080484ab in main () at fate.c:21
21      f2(globalvar, f);
(gdb) # passed as argument to function at fate.c:21
(gdb) # retrieved from variable at fate.c:21
(gdb) watch f
Hardware watchpoint 6: f
(gdb) reverse-finish 
"finish" not meaningful in the outermost frame.
(gdb) reverse-continue 
Continuing.
Warning:
Could not insert hardware watchpoint 6.
Could not insert hardware breakpoints:
You may have requested too many hardware breakpoints/watchpoints.

(gdb) delete
Delete all breakpoints? (y or n) y
(gdb) watch f
Hardware watchpoint 7: f
(gdb) reverse-continue 
Continuing.

No more reverse-execution history.
main () at fate.c:18
18      int f = 31337;
(gdb) # assigned to variable at fate.c:18
(gdb) # value 31337 originated from constant at fate.c:18

All expected messages in the question statement correspond to some info you have seen in gdb output (as shown in comments).