DCE rooting is possibly quadratic

[LegNeato]

I have updated https://github.com/LykenSol/rust-gpu-shadertoys to the latest versions of packages and rust-gpu. The compilation step for the shaders takes an extremely long time (>20 minutes), which is unexpected as the shaders do not have a ton of code.

While the compilation appears to hang, using tracing I can see it actually making progress and spending all the time in dce

[shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "Load", opcode: Load, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: MemoryAccess, quantifier: ZeroOrOne }] }, result_type: Some(1), result_id: Some(31036), operands: [IdRef(31035)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "Load", opcode: Load, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: MemoryAccess, quantifier: ZeroOrOne }] }, result_type: Some(1), result_id: Some(31036), operands: [IdRef(31035)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "InBoundsAccessChain", opcode: InBoundsAccessChain, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(357021), result_id: Some(31035), operands: [IdRef(30948), IdRef(2191)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "InBoundsAccessChain", opcode: InBoundsAccessChain, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(357021), result_id: Some(31035), operands: [IdRef(30948), IdRef(2191)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31034), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7815), IdRef(7815), IdRef(2239), IdRef(3021)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31034), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7815), IdRef(7815), IdRef(2239), IdRef(3021)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "FunctionCall", opcode: FunctionCall, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(1), result_id: Some(31033), operands: [IdRef(42), IdRef(31031), IdRef(4191), IdRef(1754)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "FunctionCall", opcode: FunctionCall, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(1), result_id: Some(31033), operands: [IdRef(42), IdRef(31031), IdRef(4191), IdRef(1754)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31032), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2194), IdRef(2606)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31032), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2194), IdRef(2606)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "FMul", opcode: FMul, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }] }, result_type: Some(1), result_id: Some(31031), operands: [IdRef(6876), IdRef(31029)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "FMul", opcode: FMul, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }] }, result_type: Some(1), result_id: Some(31031), operands: [IdRef(6876), IdRef(31029)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31030), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2194), IdRef(2180)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31030), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2194), IdRef(2180)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "FAdd", opcode: FAdd, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }] }, result_type: Some(1), result_id: Some(31029), operands: [IdRef(31027), IdRef(1754)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "FAdd", opcode: FAdd, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }] }, result_type: Some(1), result_id: Some(31029), operands: [IdRef(31027), IdRef(1754)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31028), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2502), IdRef(2578)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31028), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2502), IdRef(2578)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "FSub", opcode: FSub, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }] }, result_type: Some(1), result_id: Some(31027), operands: [IdRef(31022), IdRef(31025)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "FSub", opcode: FSub, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }] }, result_type: Some(1), result_id: Some(31027), operands: [IdRef(31022), IdRef(31025)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31026), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2937), IdRef(2547)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31026), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2937), IdRef(2547)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "Load", opcode: Load, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: MemoryAccess, quantifier: ZeroOrOne }] }, result_type: Some(1), result_id: Some(31025), operands: [IdRef(31024)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "Load", opcode: Load, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: MemoryAccess, quantifier: ZeroOrOne }] }, result_type: Some(1), result_id: Some(31025), operands: [IdRef(31024)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "InBoundsAccessChain", opcode: InBoundsAccessChain, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(357021), result_id: Some(31024), operands: [IdRef(30948), IdRef(2243)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "InBoundsAccessChain", opcode: InBoundsAccessChain, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(357021), result_id: Some(31024), operands: [IdRef(30948), IdRef(2243)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31023), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2938), IdRef(2547)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "ExtInst", opcode: ExtInst, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: LiteralExtInstInteger, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: ZeroOrMore }] }, result_type: Some(241), result_id: Some(31023), operands: [IdRef(2181), LiteralExtInstInteger(0), IdRef(1667), IdRef(7807), IdRef(7807), IdRef(2938), IdRef(2547)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "Load", opcode: Load, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: MemoryAccess, quantifier: ZeroOrOne }] }, result_type: Some(1), result_id: Some(31022), operands: [IdRef(31021)] } ^C[shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "Load", opcode: Load, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: One }, LogicalOperand { kind: MemoryAccess, quantifier: ZeroOrOne }] }, result_type: Some(1), result_id: Some(31022), operands: [IdRef(31021)] } [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::spread_roots [shadertoys-wgpu 0.0.0] rustc_codegen_spirv::linker::dce::root inst=Instruction { class: Instruction { opname: "InBoundsAccessChain", opcode: InBoundsAccessChain, capabilities: [], extensions: [], operands: [LogicalOperand { kind: IdResultType, quantifier: One }, LogicalOperand { kind: IdResult, quantifier: One }, LogicalOperand { kind: IdRef, quantifier: O

There are a lot of in progress patches for both rust-gpu and the shadertoys project so I am not pushing the code yet, but wanted to get this written.

[LegNeato]

Related: #21