You already answered my question earlier, perhaps by accident. It was mostly about clarifying which optimizations are being talked about. I'll paraphrase myself here:
I was curious whether, when only using optimizations that involve re-ordering instructions/finding instructions that can be executed in parallel, there is proof that the optimal solution is incomputable.
In context it appeared that may be what you meant, but you clarified that you didn't.
Under these constraints one might say it appears somewhat obvious that the optimal solution, i.e. a solution that executes the most instructions in parallel is computable. It's done by building the dependency graph of instructions, then ordering/distributing the instructions across execution units. For anything more than that you will run into the halting problem, but anything more would involve changing/removing/adding instructions or otherwise making changes to the program logic, which is not allowed.
One might complain that the optimizer now in some cases can't know whether two instructions depend on one another without running the program (writing, then reading unknown memory addresses for example), but any attempt to optimize cases where we can't statically infer or where the memory addresses are only sometimes the same would result in changing or adding instructions anyways (inserting a branch)[1], so as far as we are concerned these always depend on one another. We're not allowed to add/change instructions after all.
A valid criticism of this class of optimizers is that they fail spectacularly for self-modifying programs or programs that read their own instructions. A contrived example would be a program that reads some parts of its own code. We can't really do anything about this since we're not allowed to rewrite these instructions to make them still work correctly - if we even can. It's more useful to just exclude that class of program.
Anyways, a short proof that it is possible might look like this: There is only a finite number of permutations of the original program that satisfy these constraints (re-ordered/parallelized instructions), generating them all is trivial and choosing the one with the most instructions executed in parallel is as well.
Which brings me back to:
> The best we can do is identify _some_ concurrency optimizations
So my point was really, that assuming "concurrency optimizations" only includes re-ordering instructions and distributing them across execution units using whatever technology, intuitively it would seem that we can identify all of them.
But that's not what you meant. You included things such as completely replacing the algorithms with equivalent ones in "concurrency optimizations".
[1] There is an assumption here that one could disprove by example. The assumption is this: You can statically infer two values are the same when they are always the same. If this doesn't hold and the instructions using them could be run in parallel but aren't, I'm just wrong.
That is true, if you restrict yourself to only reorder and execute in parallel, you can probably optimize for number of instructions. That is just not particular interesting as you miss many optimizations, and you certainly cannot find the optimal optimization.
I was curious whether, when only using optimizations that involve re-ordering instructions/finding instructions that can be executed in parallel, there is proof that the optimal solution is incomputable.
In context it appeared that may be what you meant, but you clarified that you didn't.
Under these constraints one might say it appears somewhat obvious that the optimal solution, i.e. a solution that executes the most instructions in parallel is computable. It's done by building the dependency graph of instructions, then ordering/distributing the instructions across execution units. For anything more than that you will run into the halting problem, but anything more would involve changing/removing/adding instructions or otherwise making changes to the program logic, which is not allowed.
One might complain that the optimizer now in some cases can't know whether two instructions depend on one another without running the program (writing, then reading unknown memory addresses for example), but any attempt to optimize cases where we can't statically infer or where the memory addresses are only sometimes the same would result in changing or adding instructions anyways (inserting a branch)[1], so as far as we are concerned these always depend on one another. We're not allowed to add/change instructions after all.
A valid criticism of this class of optimizers is that they fail spectacularly for self-modifying programs or programs that read their own instructions. A contrived example would be a program that reads some parts of its own code. We can't really do anything about this since we're not allowed to rewrite these instructions to make them still work correctly - if we even can. It's more useful to just exclude that class of program.
Anyways, a short proof that it is possible might look like this: There is only a finite number of permutations of the original program that satisfy these constraints (re-ordered/parallelized instructions), generating them all is trivial and choosing the one with the most instructions executed in parallel is as well.
Which brings me back to:
> The best we can do is identify _some_ concurrency optimizations
So my point was really, that assuming "concurrency optimizations" only includes re-ordering instructions and distributing them across execution units using whatever technology, intuitively it would seem that we can identify all of them.
But that's not what you meant. You included things such as completely replacing the algorithms with equivalent ones in "concurrency optimizations".
[1] There is an assumption here that one could disprove by example. The assumption is this: You can statically infer two values are the same when they are always the same. If this doesn't hold and the instructions using them could be run in parallel but aren't, I'm just wrong.