There is link-time optimization in gcc:

   -flto[=n]
       This option runs the standard link-time optimizer.  When invoked
       with source code, it generates GIMPLE (one of GCC's internal
       representations) and writes it to special ELF sections in the
       object file.  When the object files are linked together, all the
       function bodies are read from these ELF sections and instantiated
       as if they had been part of the same translation unit.

       To use the link-time optimizer, -flto needs to be specified at
       compile time and during the final link. 

Core of the Question: Header File vs Library Name

The core of the question was posted in the comments below the question itself:

For XListInputDevices, the appropriate include-line is #include <X11/extensions/XInput.h>. I'm wondering how I can tell based on that what -lSomething flag I need

To answer the question appropriately we need to understand the distinction between -lXi ( or rather libXi.so ) and XInput.h. The XInput.h is a header file and -l looks for object files. According to Red Hat documentation on gcc usage, section 16.1,

A special file name convention is used for libraries: A library known as foo is expected to exist as file libfoo.so or libfoo.a. This convention is automatically understood by the linking input options of GCC, but not by the output options

Both headers and libraries are needed and both are related, but not the same(ref):

... if you do #include the header the compiler does not insert the code for the function you call into program.o. It merely inserts a reference to them.

As mentioned, the headers and linkers are somewhat different, since headers store declarations (or in layman terms - descriptions) of functions and other stuff, and libraries - store actual objects (reference) or compiled version of those functions. As this answer puts it:

• The header is a phone number you can call, while...
• ...the library is the actual person you can reach there!

How do the headers and libraries play together ? They are both necessary steps in building an application. First, the description of functions and interfaces is gathered ( aka compiled ) and then the code you write is linked to a library where the actual interfaces and functions are implemented.

The library itself should be compiled with the header included (ref) into the library. In fact you can take a look at an example of how simple static library is created.

So the answer to your question, is as follows: there is no guaranteed relationship between the header and the library name. ( or at least I haven't found any so far ; see also this ref) . And, finding out how to match them is a matter of knowing what's in the package or in the source code.

In fact you can do this to prove the point:

$ echo '#include<errno.h> int main(){return 0;}' | gcc -S -lc

which shows that we're compiling against libc, but the header that is part of libc is different in name.

Another example to prove the point is #include <math.h> , which is part of libc but actual implementation is in libm.so.6 , so you will see code compiled with gcc -lm.

$ apt-file find  /lib/x86_64-linux-gnu/libm.so.6 
libc6: /lib/x86_64-linux-gnu/libm.so.6

Finding the related .so or .a library file

A lot of mysteries can be solved with documentation. Let's refer to gcc documentation for link options (note , emphasis in bold is mine):

-llibrary

-l library

Search the library named library when linking. (The second alternative with the library as a separate argument is only for POSIX compliance and is not recommended.)

The -l option is passed directly to the linker by GCC. Refer to your linker documentation for exact details. The general description below applies to the GNU linker.

OK, so the gcc itself isn't actually looking up the library. It is the linker's job. But let's read on.

The linker searches a standard list of directories for the library. The directories searched include several standard system directories plus any that you specify with -L.

So there is a standard list of directories. Great, this narrows down. How do we get that list ? One way among many is to use ldconfig -v which was generously explained by the user telotorium

But the gcc documentation goes further to explain:

Static libraries are archives of object files, and have file names like liblibrary.a. Some targets also support shared libraries, which typically have names like liblibrary.so. If both static and shared libraries are found, the linker gives preference to linking with the shared library unless the -static option is used.

It makes a difference where in the command you write this option; the linker searches and processes libraries and object files in the order they are specified. Thus, ‘foo.o -lz bar.o’ searches library ‘z’ after file foo.o but before bar.o. If bar.o refers to functions in ‘z’, those functions may not be loaded.

In other words, what you're really instructing gcc and subsequently ld to do, is to look for a file libxi.so (so being a shared object extension) or libxi.a in the list of standard paths. If say we store something in /opt and the ld linker doesn't know about it, passing anything to -l won't work.

The accepted answer seems to hint at this, by virtue of most debian package names for libraries corresponding to that libwhatever.so name. But I cannot confirm or deny that bit, as I know enough about debian packaging for my humble needs only, and not these minute details. What I do know is that apt may trigger ld cache to be rebuilt.

Now, what is also important to realize is that ld actually has all these directories in cache /etc/ld.so.cache. So if the directory is removed from cache, linker won't know of library's existence.

But of course if we want to test all the above theory based on the example of libxi-devel , we can do this:

    $ dpkg-query -L libxi-dev | grep -i '.so'
    /usr/share/man/man3/XIDefineCursor.3.gz
    /usr/lib/x86_64-linux-gnu/libXi.so
    /usr/share/man/man3/XIUndefineCursor.3.gz

and then check ldconfig to confirm that /usr/lib/x86_64-linux-gnu is on the list of searched directories . . . which it is:

$ ldconfig -p | grep libXi.so
    libXi.so.6 (libc6,x86-64) => /usr/lib/x86_64-linux-gnu/libXi.so.6
    libXi.so.6 (libc6) => /usr/lib/i386-linux-gnu/libXi.so.6
    libXi.so (libc6,x86-64) => /usr/lib/x86_64-linux-gnu/libXi.so

Now this also raises a question, is the .h file useless ? No, apparently gcc still needs it to exist at compilation time ( because gcc does check the include-paths and because some libraries can be header-only )

$ mv /usr/include/X11/extensions/XInput.h /tmp
$ echo '#include <X11/extensions/XInput.h> void main(){return 0;}' | gcc -lXi -E -
# 1 "<stdin>"
# 1 "<built-in>"
# 1 "<command-line>"
# 31 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 32 "<command-line>" 2
# 1 "<stdin>"
<stdin>:1:36: warning: extra tokens at end of #include directive
<stdin>:1:10: fatal error: X11/extensions/XInput.h: No such file or directory
compilation terminated.

From the ld (the GNU linker) documentation (http://sourceware.org/binutils/docs/ld/Options.html#Options):

The linker will search an archive only once, at the location where it is specified on the command line. If the archive defines a symbol which was undefined in some object which appeared before the archive on the command line, the linker will include the appropriate file(s) from the archive. However, an undefined symbol in an object appearing later on the command line will not cause the linker to search the archive again.

So if you specify the library too early, the linker will scan it, but not find anything of interest. Then the linker moves on to the object file produced by the compiler and finds references that need to be resolved, but it has already scanned the library and won't bother looking there again.

I wanted to know those flag, since i didn't know what argument to gave to pkg. But i found out how it was working:

In /usr/lib/pkgconfig there is everything we need. Only put one of those file in argument, + --cflag and --clib.

(i didnt know i was suppose to look at /usr/lib/pkgconfig)