Assertion failure on switch statement with case label in nested block

[dkolsen-pgi]

ClangIR hits an assertion failure when a switch statement contains a case label that is within a nested block statement.

int g(int x) {
  switch (x) {
    case 1:
      return -1;
    {
      case 2:
        return -20;
    }
  }
  return x;
}

clang++: .../clang/lib/CIR/CodeGen/CIRGenStmt.cpp:300: 
mlir::LogicalResult cir::CIRGenFunction::buildSimpleStmt(const clang::Stmt*, bool): 
Assertion `0 && "Should not get here, currently handled directly from SwitchStmt"' failed.

While code like this is unlikely to appear in production and will usually be found in test suites that try to break the compiler, it is legal code in both C and C++ and should not trigger an internal compiler error.

[bcardosolopes]

While code like this is unlikely to appear in production

Famous "last words" haha, I just hit this in prod! Some "temporary" workaround is using this.

Now that @gitoleg work has landed we probably have the machinery to solve this. Any chance (or any plans) you might work on this soon @gitoleg? (cc. @wenpen)

[gitoleg]

I will take a look in the next few days, sure

[gitoleg]

Now that @gitoleg work has landed we probably have the machinery to solve this.

This is all about codegen, so I would say the previous work has nothing to do with it.

Speaking about the current issue, it's still not obvious for me how to handle it properly, though I think I can suggest an approach.
First of all, I'm not sure we do the proper thing when we attach random statements to the previous case (or I miss something important here):

   for (auto *c : compoundStmt->body()) {
      if (auto *switchCase = dyn_cast<SwitchCase>(c)) {
        res = buildSwitchCase(*switchCase, condType, caseAttrs);
      } else if (lastCaseBlock) {  // !!! This clause
        // This means it's a random stmt following up a case, just
        // emit it as part of previous known case.
        mlir::OpBuilder::InsertionGuard guardCase(builder);
        builder.setInsertionPointToEnd(lastCaseBlock);
        res = buildStmt(c, /*useCurrentScope=*/!isa<CompoundStmt>(c));
      } else {
        llvm_unreachable("statement doesn't belong to any case region, NYI");
      }

      lastCaseBlock = builder.getBlock();

      if (res.failed())
        break;
    }

The original codegen even doesn't emit any random code as far I can see, and I think we need to do the same. We could extend the current issue example (will refer it as example 1) to make it a little more interesting (example 2):

int g(int x) {
  int y = 1;
  switch (x) {
    case 1:
      return -1;
    {
      y = 42;
      case 2:
        return y;
    }
  }
  return x;
}

The y = 42 statement is not taken in account and g(2) returns exactly 1. So I would say, we need to ignore this statement as well or at least place it in some unreachable scope.

Now, what I would do. I would create a small class for the switch stmt processing with several fields like case attributes, maybe switch variable type - and maintain a pointer to it in the CIRGenFunction.h. Once we enter buildSwitchStmt in the CIR codegen, we would save the current pointer in the temp var, create a new instance of this class, store the pointer into the member field. Once we leave the buildSwitchStmt we restore the pointer. Almost the same is done in the original codegen.

So we will able to handle nested switch statements and we can fix the example 1 .
The second example is less trivial ( and one need to take it into account when will fix the issue, even if it will be me :) ) . But I believe it's doable as well.

@bcardosolopes what do you think? Is it a good/workable solution? Or I miss some details here?

[bcardosolopes]

This is all about codegen, so I would say the previous work has nothing to do with it.

Right, I wasn't implying that, sorry for the misunderstanding. My initial thinking is that we could probably map these weird inner cases with synthetic gotos/labels, since they violate some scope control-flow.

Speaking about the current issue, it's still not obvious for me how to handle it properly, though I think I can suggest an approach.

Thanks for looking into this.

First of all, I'm not sure we do the proper thing when we attach random statements to the previous case (or I miss something important here):
...
The original codegen even doesn't emit any random code as far I can see, and I think we need to do the same. We could extend the current issue example (will refer it as example 1) to make it a little more interesting (example 2):
..
The y = 42 statement is not taken in account and g(2) returns exactly 1. So I would say, we need to ignore this statement as well or at least place it in some unreachable scope.

If the original codegen is doing that (I haven't checked), I agree we should do the same - It'd probably be nice to maintain the statement for the sake of providing unrecheable diagnostics later on, e.g. even though we ignore the emission, we could emit an empy scope with source loc on a basic block that is unrecheable. But just initially supporting lowering works for me. I also don't see any current warnings for these types of unrecheable statements in clang.

Now, what I would do. I would create a small class for the switch stmt processing with several fields like case attributes, maybe switch variable type - and maintain a pointer to it in the CIRGenFunction.h. Once we enter buildSwitchStmt in the CIR codegen, we would save the current pointer in the temp var, create a new instance of this class, store the pointer into the member field. Once we leave the buildSwitchStmt we restore the pointer. Almost the same is done in the original codegen.

Yep, we currently track some of it already as part of LexicalScopes, we could increment it with more needed info.

So we will able to handle nested switch statements and we can fix the example 1. The second example is less trivial ( and one need to take it into account when will fix the issue, even if it will be me :) ) . But I believe it's doable as well.
@bcardosolopes what do you think? Is it a good/workable solution? Or I miss some details here?

Sounds great to me, thanks for sharing a solution. Do you have any interest to work on this?

[gitoleg]

@bcardosolopes

Sounds great to me, thanks for sharing a solution. Do you have any interest to work on this?

I do) But I can't promise I'll do it soon. So if someone wants to do it earlier, just let me know, e.g. right here. Otherwise I'll return to this issue later and keep you informed about the progress/problems etc.

[bcardosolopes]

@wenpen do you want to work on this one?

[bcardosolopes]

@piggynl this could be a good issue to tackle as well.

[wenpen]

I'm still working on #528, and I feel these problems should be resolved in a unified solution.
So I need to do some more test, will update my proposal soon when I figure out it.

[wenpen]

I have a proposal to fix this issue by modifying the definition of SwitchOp

What's the limitation of current SwitchOp?

Current SwitchOp have a list of caseAttr, one caseAttr is corresponding to one region.
But case could be used very flexibly just like goto. consider the following code

switch (x) {
  while (y) {
    if (z) {
      case 1:
      ...
    } else {
      case 2:
      ...
    }
  }
}

The case is contained by WhileOp, SwitchOp should have only one block containing WhileOp, and we can't split it into two regions.

How does the original clang codegen handle switch?

CodeGenFunction class have a pointer member llvm::SwitchInst *SwitchInsn to maintain the current switch information. SwitchInsn will record the case value and destination block, which is similar to SwitchFlatOp. When emit SwitchStmt, it will update the pointer SwitchInsn, and recursively process the body statement by calling EmitStmt(). When emit CaseStmt, it will call SwitchInsn->addCase(...) to store the case value and destination block.

Proposal for the new definition of SwitchOp

As the behavior of switch/case is similar to goto/label, we could refer to the design of goto.

Specifically, add a new op CaseOp to store the case value, then SwitchOp have exactly one region. And we won't handle CaseStmt in buildSwitchStmt, instead we would do the work in buildSimpleStmt.
The above example code would generate cir

cir.scope {
  cir.switch (%1) {
    cir.scope {
      cir.while {
        cir.condition(%2)
      } do {
        cir.scope {
          cir.if %3 {
            cir.case 1
            ...
          } else {
            cir.case 2
            ...
          }
        }
      }
    }
  }
}

In FlattenCFG, we could replace SwitchOp with SwitchFlatOp simply. Just walk in the SwitchOp, collect the case value and (destination) blocks when we find out CaseOp, then we could remove SwitchOp & CaseOp and build SwitchFlatOp.

Besides, it could resolve some other switch related issues, including unreachable code(#520 #521) and incorrect implementation of getOrCreateRetBlock (talked about in #528).

[bcardosolopes]

@wenpen thanks for taking the time to propose a holistic solution, very nice writeup.

I think it overall makes sense, the part that bothers me is having a design that prioritize the corner case of the language in detriment of the common use cases, but I think this is hinting at the right direction.

Given your proposal, few questions:

• How would a "normal" switch use case be represented by this, can you paste few examples?
• Have you thought about some mixed approach? Examples:
  • As the CaseAttr becomes a CaseOp, perhaps cir.case could optionally have regions to maintain the old behavior, so that cases with underlying scopes could be directly represented. Because new cir.switch will only have one region, this means a "normal" switch use case would be just a sequential number of cir.cases.
  • What's your plan for handling fallthroughs? For breaks, we'll likely need a region within a cir.case to represent it, or do you have alternative ideas?
  • If you look at cir.try_call, it might or might not be within a direct cir.try, doing similar for cir.case/cir.switch makes sense too.

Thanks!

[wenpen]

How would a "normal" switch use case be represented by this, can you paste few examples?

Here is an example code to discuss the mixed (common and corner) case.

switch(x) {
  statement0;
case 1:
case 2:
  statement1;
  {
    case 3
    statement2;
  }
  break;
case 4:
  statement3;
case 5:
  statement4;
  break;
default:
  statement5;
}

cir.scope {
  cir.switch (%1) {
    statement0

    cir.case (anyof, [1, 2])
    statement1
    cir.scope {
      cir.case (equal 3)
      statement2
      cir.yield
    }
    cir.break
    
    cir.case (equal 4)
    statement3

    cir.case (equal 5)
    statement4
    cir.break

    cir.case (default)
    statement5
    cir.yield
  }
}

As the CaseAttr becomes a CaseOp, perhaps cir.case could optionally have regions to maintain the old behavior, so that cases with underlying scopes could be directly represented. Because new cir.switch will only have one region, this means a "normal" switch use case would be just a sequential number of cir.cases.

Good point! I feel it's a better structure to make cir.case have a region for "normal" use case. So, I'd like to keep the current logic to scan CaseStmt in switch compound body. And the other (who nested in other op) CaseStmt won't have any region.
The cir would be as below, and it will be easy to change cir.case to have exactly one region once we need.

cir.scope {
  cir.switch (%1) {
    statement0
    cir.case (anyof, [1, 2]) {
      statement1
      cir.scope {
        cir.case (equal 3)
        statement2
        cir.yield
      }
      cir.break
    }
    cir.case (4) {
      statement3
      cir.yield
    }
    cir.case (5) {
      statement4
      cir.break
    }
    cir.case (default) {
      statement5
      cir.yield
    }
    cir.yield
  }
}

What's your plan for handling fallthroughs? For breaks, we'll likely need a region within a cir.case to represent it, or do you have alternative ideas?

My thought is same with the current implement: use cir.break and cir.yield for exit and fallthroughs, then replace them with cir.br in FlattenCFG.cpp. The above code show the usage.

If you look at cir.try_call, it might or might not be within a direct cir.try, doing similar for cir.case/cir.switch makes sense too.

Yes, it looks similar. But when I tried some code to see the cir, it crashed. Have created issue 688 for it. Will have another try later.

Thanks for your suggestions~ @bcardosolopes

[ChuanqiXu9]

@gitoleg @wenpen hi, are you still working on this? I'd like to work on it if you haven't started it yet.

[gitoleg]

I'm not, sorry

[wenpen]

@ChuanqiXu9 Sorry my work is hold on, happy to see you take it~

[ChuanqiXu9]

As the CaseAttr becomes a CaseOp, perhaps cir.case could optionally have regions to maintain the old behavior, so that cases with underlying scopes could be directly represented. Because new cir.switch will only have one region, this means a "normal" switch use case would be just a sequential number of cir.cases.

Good point! I feel it's a better structure to make cir.case have a region for "normal" use case. So, I'd like to keep the current logic to scan CaseStmt in switch compound body. And the other (who nested in other op) CaseStmt won't have any region. The cir would be as below, and it will be easy to change cir.case to have exactly one region once we need.

Out of curiosity, what's the benefit to make a region for a case? I feel it is less straight forward. Can we make it simpler to treat all cases like labels?

@bcardosolopes @wenpen

[ChuanqiXu9]

Some updates after I played around it in the early stage: I feel it is more or less over designed to make each case to have its own region. Even if we ignore the gotos and the case of cases in other scopes, I feel it is less meaningful to make each case have its own region. Given every case has at least an edge from the switch, non case will dominate other cases and all cases will be reachable as long as the switch are reachable. So from my understanding of regions, I feel it won't make analysis and passes more easier. On the other hand, the codes to implement switch will be much more easier to understand to maintain.

Since I think CIR is in the early stage, the risks to break the so-called old behavior may be under control. Even if there is anything going wrong, we can fix it. We can avoid the technical debt at the young age.

[bcardosolopes]

If the alternative here is pure basic blocks instead, I don't see what goodness it brings either, once it becomes all basic block we lose the higher level view too early. What approach were you thinking about?

I like the regions, it becomes more logical to think about the code (let's say we want to look at a lower level switch/case with some structuring) and merge similar case's, make transformations with the switch, etc. Some lifetime checker violations implemented on switch/cases have a nice abstraction to work with as well right now.

I prefer not to design around the edge case, the common case sounds more appealing to me. When we hit the edge cases, we should map that somehow (for example, we could use symbolic cir.goto to be later be solved in the pipeline) but without losing the granularity of the common case (be able to look at a lower level switch/case statements at will).

[ChuanqiXu9]

I don't see what goodness it brings either, once it becomes all basic block we lose the higher level view too early. What approach were you thinking about?

Yeah, this is what confuses me and I tried to discuss in #978. What is a region in CIR?
Originally I thought it corresponds to a scope in C/C++. Then I think we shouldn't lower case to a region naturally since a case doesn't form a scope. In C/C++, when we want a scope for a case, we would write:

case 42: {
    ...
}

So this was the reason why I thought we shouldn't lower a case to a region.

But later I think more, I feel like, may be, CIR models the regions as relationships between control flows (ignoring some special cases @sitio-couto mentioned in #978). Then it makes sense. I come from LLVM and regions are not a first class concept there. So I preferred to use blocks to model the control flow relationships. But if the CIR (or the MLIR) preferring using regions to model the control flows, I am fine with that. (Correct me if I am wrong)

Although this may sound pedantic, but I feel it is important. Otherwise we can't think seriously.

I prefer not to design around the edge case

But we have to care about the edge cases. What I care about here is consistency. Given the discuss in #978, we know that the region concept in CIR are not strict and we somewhat, not care about if the regions are isolated or not before flattening (We're going to teach passes to skip these inlegal regions if I read correctly).

Then how about always creating a region for every case?

[dkolsen-pgi]

I prefer not to design around the edge case.

But we have to care about the edge cases.

Both those statements are true. The edge cases absolutely have to work. But we hopefully don't have to sacrifice a nice design in the process. The design should be optimized for the normal case. If that design also works well for the edge cases, that's great. But it's not always possible.

What I care about here is consistency.

Consistency is a good goal. But it is not the top priority. Sometimes it has to lose out to other priorities. In this case, the design of C and C++ make it hard to be both consistent and useful. The flexibility of case labels in switch statements that the languages allow means there is no representation that will work in all cases that doesn't immediately resort to unstructured control flow, which we don't want to do because it throws away too much information.

The vast, vast majority of switch statements out there in the wild are in the normal form, with all the case/default labels at the top level and every group of case labels ending with a break or a return or a fall-through. switch statements that have that normal form are well represented in CIR with a region for each group of adjacent case labels, as is currently done. To me that looks like a good design.

For the very small number of switch statements that don't fit that pattern, we have to get creative. For case labels that are nested within an inner scope, this idea comes to mind: During CIR code gen replace that nested case label with a regular label, then create a region for that case label at the top of the switch statement where the region contains only a goto to the compiler-generated label. That is, CIR code gen would pretend that

switch (x) {
  case 1:
    if (y) {
    case 2:
      return 42;
    } else {
      return 99;
    }
}

were actually written as

switch (x) {
  case 1:
    if (y) {
    __label_2:
      return 42;
    } else {
      return 99;
    }
  case 2:
    goto __label_2;
}

If that works (and I don't know if it actually will), that preserves the nice design of a switch as being a collection of case labels and regions while still handling the edge cases with a not-so-pretty but acceptable workaround.

[ChuanqiXu9]

I prefer not to design around the edge case.

But we have to care about the edge cases.

Both those statements are true. The edge cases absolutely have to work. But we hopefully don't have to sacrifice a nice design in the process. The design should be optimized for the normal case. If that design also works well for the edge cases, that's great. But it's not always possible.

What I care about here is consistency.

Consistency is a good goal. But it is not the top priority. Sometimes it has to lose out to other priorities. In this case, the design of C and C++ make it hard to be both consistent and useful. The flexibility of case labels in switch statements that the languages allow means there is no representation that will work in all cases that doesn't immediately resort to unstructured control flow, which we don't want to do because it throws away too much information.

The vast, vast majority of switch statements out there in the wild are in the normal form, with all the case/default labels at the top level and every group of case labels ending with a break or a return or a fall-through. switch statements that have that normal form are well represented in CIR with a region for each group of adjacent case labels, as is currently done. To me that looks like a good design.

For the very small number of switch statements that don't fit that pattern, we have to get creative. For case labels that are nested within an inner scope, this idea comes to mind: During CIR code gen replace that nested case label with a regular label, then create a region for that case label at the top of the switch statement where the region contains only a goto to the compiler-generated label. That is, CIR code gen would pretend that

switch (x) {
  case 1:
    if (y) {
    case 2:
      return 42;
    } else {
      return 99;
    }
}

were actually written as

switch (x) {
  case 1:
    if (y) {
    __label_2:
      return 42;
    } else {
      return 99;
    }
  case 2:
    goto __label_2;
}

If that works (and I don't know if it actually will), that preserves the nice design of a switch as being a collection of case labels and regions while still handling the edge cases with a not-so-pretty but acceptable workaround.

hi, thanks for the written up. But let's try to see if we can still have a consistent design for it: e.g., always creating a region for all caseOps.

[ChuanqiXu9]

I believe there is only remaining blocking issue for me to send my PR and I feel like I need some inputs here.

The question is: what's the motivation/goal/intention to create a new return for each cases?

clangir/clang/lib/CIR/CodeGen/CIRGenFunction.h

Lines 2249 to 2256 in cab2b44

	mlir::Block *getOrCreateRetBlock(CIRGenFunction &CGF, mlir::Location loc) {
	unsigned int regionIdx = 0;
	if (isSwitch())
	regionIdx = SwitchRegions.size() - 1;
	if (regionIdx >= RetBlocks.size())
	return createRetBlock(CGF, loc);
	return &*RetBlocks.back();
	}

clangir/clang/lib/CIR/CodeGen/CIRGenFunction.h

Lines 2209 to 2213 in cab2b44

	// On switches we need one return block per region, since cases don't
	// have their own scopes but are distinct regions nonetheless.
	llvm::SmallVector<mlir::Block *> RetBlocks;
	llvm::SmallVector<std::optional<mlir::Location>> RetLocs;
	llvm::SmallVector<std::unique_ptr<mlir::Region>> SwitchRegions;

Here is a comment but I can't understand the underlying problem. I mean, what's the problem and how do we "solve" that by the current solution.

Initially I thought it was related to the lifetime/cleanups for variables. But I failed to get more insight. Following are some random thoughts. They are more or less in chaos. I am not sure if it helps.

First, I think, if the case is followed by a {}, it is a different story, right? e.g.,

switch(a) {
    case 1: {
         return a;
     }
}

Here the return will live in a different scope (but the won't be treated as a switch scope), so the above discussion won't take place here. But the related confusing question is, even if in this case, when we return, we still need to cleanup all the variables in the function. And why it is fine in this case now if the real reason to treat return specially was the lifetime issues?

CC @bcardosolopes @sitio-couto

[ChuanqiXu9]

Sent #1006

I guess my above question not come from CIR semantics, but from the restrict from MLIR: a block may not refer to blocks in other regions. Correct me if I am wrong.