Pure annotation for stateless functions

language design
61

Did a little dig further, by opt -O2 -print-after-all, we can locate that it is exactly the second EarlyCSEPass of LLVM that conducts the optimization.

By looking at the source code of LLVM, the core logic is in these lines:

    // If this is a read-only or write-only call, process it. Skip store
    // MemInsts, as they will be more precisely handled later on. Also skip
    // memsets, as DSE may be able to optimize them better by removing the
    // earlier rather than later store.
    if (CallValue::canHandle(&Inst) &&
        (!MemInst.isValid() || !MemInst.isStore()) && !isa<MemSetInst>(&Inst)) {
      // If we have an available version of this call, and if it is the right
      // generation, replace this instruction.
      std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
      if (InVal.first != nullptr &&
          isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
                              &Inst) &&
          InVal.first->mayReadFromMemory() == Inst.mayReadFromMemory()) {
        LLVM_DEBUG(dbgs() << "EarlyCSE CSE CALL: " << Inst
                          << "  to: " << *InVal.first << '\n');
        if (!DebugCounter::shouldExecute(CSECounter)) {
          LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
          continue;
        }
        combineIRFlags(Inst, InVal.first);
        if (!Inst.use_empty())
          Inst.replaceAllUsesWith(InVal.first);
        salvageKnowledge(&Inst, &AC);
        removeMSSA(Inst);
        Inst.eraseFromParent();
        Changed = true;
        ++NumCSECall;
        continue;
      }

      // Increase memory generation for writes. Do this before inserting
      // the call, so it has the generation after the write occurred.
      if (Inst.mayWriteToMemory())
        ++CurrentGeneration;

      // Otherwise, remember that we have this instruction.
      AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
      continue;
    }

Hmmmm, as far as I can tell, they just look at how the callee accesses memories as @comex said.

And I tried another thing: I copy-paste the attribute of foo in the pure version to the panic version in LLVM IR, and it turns out that the opt can still conduct CSE successfully :grinning_face_with_smiling_eyes:

62

I think there's a semantically consistent way to implement this: imagine a macro delayed_panic!(…) with the following behaviour: it allows the program to panic (with the given message) at any time after the call, and any subsequent execution of the progam must not depend on the value returned by delayed_panic! (i.e. the subsequent program execution can only do things that don't depend at all on the result of the delayed_panic!() call). This is always possible to implement because it could always be implemented as panicking immediately, but gives the compiler more scope for optimisation.

I fear that this might not actually work well in practice, though: it's very similar to C++'s ill-fated memory_order_consume which ended up being deprecated because no compiler was actually able to do nontrivial optimisations using it (they compiled it in a way that complied with the specification but ignored all the theoretical performance advantages). It might also be quite unintuitive, e.g. you couldn't use it at type () because then the delayed panic could be optimised out entirely, so it would mostly only be useful in "the value couldn't be calculated from these inputs" situations.

EDIT: I just realised that this sort of thing could maybe fix the drop(Rc::clone(rc)) problem – in current Rust that can't be optimised out because it has to check that the reference count isn't usize::MAX and panic if it is, but you conceptually want it to be able to be optimised out even if that changes the timing or existence of panics. That's actually making me think that the potential performance gains could be quite large, if the compiler could be made to provide them.

2 Likes