After looking at the code I have two questions:

1. what is the relation between the third commit, 62aa049, and the problem you describe?

2. You change 'a t_store into ('a, 'ctx) t_store: an exit action is now identified by both an index and a context, and two actions keys are considered equal if the contexts are the same (the indices are ignored in this case). How does ('a, 'ctx) t_store with the new definition differs from using ('ctx * 'a) t_store with the old definition and a well-chosen equality function?

The problem is triggered when switches generated during translation to lambda code contain a limited number of cases, and no fail action. Since the switch structure also contains information about the number of constructors in the type, the following passes tend to generate actions for those missing cases, and those additional actions are not shared properly.
The third commit fixes the translation from lambda to flambda in this case, since the flambda AST can actually represent them accurately.

About the t_store type change, I first tried using a ('ctx * 'a) t_store in Cmmgen, but since the type given to t_store has to match the type act given as the argument to Switch.Make, it meant a lot of wrapping and unwrapping of expressions in Cmmgen.SArgBlocks and the functions using it.
While the changes would have been confined to Cmmgen, the diff would have been bigger, and this solution looks cleaner to me.

Following suggestions from @chambart I've duplicated the StoreExp module to reflect that the context is different between the standard switches and string switches.

(cc @maranget : do you have an opinion on this proposed change? )

Hi,

The change fixes a real problem. It uses the existing Store component appropriatly and should be scheduled for integration. Well done.

May I ask for the pull request authors to comment on the following suggestion:

Impact on file others than switch.ml and cmmgen.ml can be significantly reduced by renaming your Store module into, say, CtxStore and then adding a new Store module that would be the application of CtxStore with type context being unit.

Then, there would be no need to change matching.ml, lambda.ml etc.

I've pushed a commit that splits the t_store type and Store functor into context-aware and context-unaware versions, which indeed allows to revert the changes to unrelated files.

It is a bit disappointing that the zyva function had to be duplicated in the interface, but it logically follows from the duplication of the t_store type, which arose from the necessity to have differently typed act_store functions.
Turning zyva's argument from Arg.act t_store to Arg.act shared array would be cleaner, but again implies patches at every call to zyva.

Anyway, I'm not attached to any particular solution, so I can revert back or go for a middle ground solution if you think it's better.
Also, the two flambda commits are related to the problem but not to the solution, so I can remove them or re-submit them as part of an independent pull request if you'd prefer this patch to focus on the cmm switch.

(Personally I find the two zyva functions and the increase in number of functors and signatures a bit complex, and I find the patch and result less readable than just adding extra () parameters where the type-checker asks to.)

Im an not sure at all that the store_t type have to be duplicated. My idea was rather
for the old functor to be the application of the new one to a unit context:

In switch.mli

1. resurect the old Stored signature

module type Stored = sig
  type t
  type key
  val compare_key : key -> key -> int
  val make_key : t -> key option
end

(2) Define Stored with context as a signature "extension"

module type CtxStored = sig
  include Stored
  type context
  val make_key : context -> t -> key option
end

(3) then define the two functors for building sharing stores with and without context,
Notice the type of mk_store in the second functor signature.

module CtxStore(A:CtxStored) :
    sig
      val mk_store : unit -> (A.t, A.context) t_store
    end

module Store(A:Stored) :
    sig
      val mk_store : unit -> (A.t, unit) t_store
    end

...

In switch.ml, Store will basically be:

module Store(S:Stored) = struct
  module Me =
    CtxStore
      (struct
        include S
        type context = unit
        let make_key () = S.make_key
      end)
  let mk_store = Me.mk_store
end

....

Ok, that way we still have some strange () as first arguments in most act_store calls. However,
the similarily useless argument is no more present for make_key functions...
Or am I wrong somewhere?

It works, and removes part of the patches in lambda.ml, bytegen.ml and so on, but the parts that call act_store or act_store_shared would still need to be patched, so it would have come short of the goal of keeping unrelated files unchanged.

But as @gasche pointed out, this is not a goal that we absolutely need to reach. I'll update the pull request to revert the t_store duplication (but keep Store and CtxStore distinct), so it should get more or less to what you had in mind.