Why most of processor only provide finite number of logic operations (NAND/NOR/XOR) while there are clearly 14 different logic gates available? I understand that we can implement any Boolean logic with only NAND/NOR . But practically, providing less gates make operations such as NIMPLY/IMPLY takes more than 1 cycle to finish as we need to implement them with composition of other gates. It seems to me that if ALU provides the whole set of hardware optimized logic gates we might be able to optimize software performance. Fanout might be an issue if all logic gates' output drive the same bus, but it seems logic operations aren't always the bottleneck of a modern processor because there are much more time consuming operations such as multiplication that limit the clock cycle. So my question is why we seldom see processors provide the full set of logic gates? What are the considerations involved? How do processor designers reach the optimal number of different logic operations the ALU is going to provide?
If you would like to understand how processor designers reach their 'optimal' instruction set, you might want to look at some books, for example "Computer Architecture, A Quantitative Approach" by Hennessy & Patterson
There are quite a lot of papers freely available on the web about computer architecture, and Instruction Set Architecture (ISA).
I'd suggest read the papers and watch the videos at http://riscv.org
As a concrete example, look at the The RISC-V Compressed Instruction Set Manual
Their process for the "RISC-V Compressed Instruction Set Manual" was to gather sets of recognised, representative, 'benchmark' programs, in high level languages like C, and run analysis across them. For example, they might use an existing C compiler, modify its code generation to generate their prototype ISA, pass their benchmark programs through it, and analyse the results. That relies to some extent on the compiler having a rich enough model to make use of their ISA's instructions.
In the specific case of that compressed instruction set analysis, they wanted to identify which instructions were sufficiently common, that providing a compressed instruction would have reduce the code significantly. However, that analysis uses techniques which have been applied before.
The compressed instruction set analysis showed that only 31 instructions accounted for the vast majority of code, so compressing those by 50% reduced total program size by 25%. As quite a lot of code is data, that suggests that a lot of instructions are rarely used.
Remember, adding more instructions, and expanding the ALU is not necessarily free. To maximise throughput (i.e. doing useful work) we try to get a balance between latency (delay) through the ALU, power consumption, and overall instruction time. Adding an instruction which might make the CPU run 5% slower on every instruction, for 0.1% of the code to run 2x faster makes no sense.
This is a version of Amdahl's Law, which essentially says no matter how much one part of a system is improved, if it only accounts for 1% of (a programs) resources (time or space), then the improvement can only benefit the system's performance by 1%.
The vast majority of instructions executed by a program are loads, stores, simple arithmetic, jumps and conditional branches. As long as they execute well, adding a few specialised instructions to make rarely used operations faster will make virtually no difference. Worse, if the addition of specialised instructions slows the common instructions by a tiny amount, then it's likely better to remove them.
To learn more, look for older (1980s) RISC research papers. Maybe start with John L. Hennessy and David Patterson as they were quite prolific publishers, and Hennesey founded MIPS, and Patterson's work became SUN SPARC.
There are sixteen basic bitwise logic operations available with 0, 1 or 2 inputs. (Zero inputs constitute constant values 0 and 1.) The 74LS181 4-bit ALU, used in such classic computers as the PDP-11, VAX 11/780 and many others computers implemented all of them. I am using this chip as an example because its datasheet exposes the internals circuitry and other details of the ALU. Such information is generally not available for microprocessors today. The sixteen operations (listed in the order they are addressed in the 74LS181) are:
~A NOT A ~(A&B) NAND ~A+B A IMPLY B can also be written ~(A & ~B) 1 constant 1 ~(A+B) NOR ~B NOT B ~(A^B) XNOR A+~B B IMPLY A can also be written ~(~A & B) ~A&B B NIMPLY A A^B XOR B B A+B OR 0 constant 0 A&~B A NIMPLY B A&B AND A A
where ~ = bitwise NOT, & = AND, | = OR, and ^ = XOR as used in C and other languages.
I am not sure whether modern ALU's provide all sixteen operations, since there is no way to get to many of them via their processors' instruction sets.
Virtually all processors provide the four basic bitwise logic operations NOT, AND, OR and XOR in their machine level instruction sets, since all the other operations can be built up from them, as shown in the above table.
So a compiler generating code for the high level statement:
C = A & ~B; // A NIMPLY B
might generate something like (using a hypothetical instruction set):
mov R0, A ; A => R0 mov R1, B ; B => R1 not R1 ; ~R1 => R1 and R0, R1 ; R0 & R1 => R0 mov C, R0 ; R0 => C
Now it would be nice when a compiler recognized a pattern like C = A & ~B it was able to generate an instruction to tell the ALU to perform the A & ~B operation in one cycle (avoiding having to complement B first):
mov R0, A ; A => R0 mov R1, B ; B => R1 nimply R0, R1 ; R0 NIMPLY R1 => R0 mov C, R0 ; R0 => C
but without the machine instruction for NIMPLY, it can't do this. However doing so only saves one instruction, is it worth it?
With the exception of the 80x86 family, whose CISC (Complex instruction set) dates back almost 40 years (1978), most processors today use some version of RISC (Reduced instruction set). Thus specialized, seldom used instructions like IMPLY and NIMPLY have no place in RISC processors.