Locals are not treated as independent blocks in linker logic

[tlakollo]

Analyzer has a logic that handles blocks independently depending on their predecessor value meaning that the following code

Type[] arr = new Type[] { null };
if (i == 1)
    arr[0] = GetMethods ();
else
    arr[i] = GetFields ();
arr[0].RequiresAll ();

Gets translated to a structure similar to:

------[B1]------
-----/----\-----
--[B2]----[B3]--
-----\----/-----
------[B4]------

• The first block (B1) contains the array initialization
• Given that there could be different values depending on the result of the if statement, block 2 (B2) and block 3 (B3) handle the different results. Notice that they both start with a copy of the information on B1 which is their predecessor. B2 and B3 do not interact between them and generate their output based on merging the value of B1 and their own generated value.
• B2 executes GetMethods(); which has the return value PublicMethods, then we merge the values in index 0 which are: empty array from B1 and the return value in B2 (PublicMethods)
• B3 executes GetFields(); which has the return value PublicFields, then tries to access the array but the index is unknown so we return UnknownValue
• Block 4 (B4) executes RequiresAll(); in order to verify if arr[0] fulfills the requirements, we read the array which contains the result from the blocks B2 and B3. At that moment we attempt to merge the result from the different arrays, we verify that one of the results is unknown and therefore we cannot know if arr[0] fulfills the requirements.

Linker on the other hand has a concept of a global 'locals' structure, the structure would look similar to:

---[ l o c a l s ]---
---/----/---\----\---
-[B1]-[B2]-[B3]-[B4]-

• The first block (B1) contains the array initialization and it gets written as a local
• Block 2 (B2) and block 3 (B3) handle the if and else cases, the difference being that they get executed in a serialized way.
• B2 reads the local to obtain the value stored by B1, then updates the value with the return value of GetMethods(); (PublicMethods) and stores it back into locals.
• By the time B3 reads locals, it already contains the merged value (B1+B2) stored by B2 (in analyzer case B3 reads from B1). It mergers with its own unknown value (B1+B2+B3) and stores it in locals
• By the time B4 reads the array from locals it already contains PublicMethods+Unknown and produces two warnings instead of one.

This is only one example of the problems with the linker although there are many others that could surface, the linker already handles different stacks to behave like the analyzer when there are branches due to if conditions that allow to have a separation between stacks and then merge them together (see code) the solution should be to have a similar system that threats locals independently for each of the blocks and then something that merges the different local values.

[vitek-karas]

This is not entirely accurate about the linker. It does track values per basic block - all locals are stored with ValueBasicBlockPair which stores the basic block identification + the value. And in some cases when it stores locals it will store multiple values each with a different basic block ID. But it's not 100% consistent about doing this and it unfortunately completely ignores the basic block ID when reading the values in some cases. So the end result is that it's as if it doesn't track basic blocks, even though it tries, but fails.

I would not try to fix this in isolation. I think that once we start using CFG in linker a fix for this will be a side-effect of that change.